Octree creation via C.S.G. definition

The common method for generating the octrees of complex objects, is based upon generating the octrees of several pre-defined primitives and applying Boolean operations on them. Regardless how the octrees representing the primitives are generated (top-down or bottom-up) the octree of a desired object is obtained by performing Boolean operations among the primitives comprising the object according to the object's CSG (constructive solid Geometry) representation. When carrying out this procedure, most of the computing and memory resources are used for generating and storing the octants comprising the primitives. However, the majority of those octants are not required for the representation of the final object. In this paper the extention of the top-down approach to the CSG level (i.e., generating the octree of an object directly from its CSG representation) is proposed. With this method there is no need to generate the octrees of the primitives comprising the object nor to perform Boolean operations on them. Moreover, only these octants which belong to the final object are generated.     

Boolean operations with implicit and parametric representation of primitives using R-functions

We present a new and efficient algorithm to accurately polygonize an implicit surface generated by multiple Boolean operations with globally deformed primitives. Our algorithm is special in the sense that it can be applied to objects with both an implicit and a parametric representation, such as superquadrics, supershapes, and Dupin cyclides. The input is a constructive solid geometry tree (CSG tree) that contains the Boolean operations, the parameters of the primitives, and the global deformations. At each node of the CSG tree, the implicit formulations of the subtrees are used to quickly determine the parts to be transmitted to the parent node, while the primitives' parametric definition are used to refine an intermediary mesh around the intersection curves. The output is both an implicit equation and a mesh representing its solution. For the resulting object, an implicit equation with guaranteed differential properties is obtained by simple combinations of the primitives' implicit equations using R-functions. Depending on the chosen R-function, this equation is continuous and can be differentiable everywhere. The primitives' parametric representations are used to directly polygonize the resulting surface by generating vertices that belong exactly to the zero-set of the resulting implicit equation. The proposed approach has many potential applications, ranging from mechanical engineering to shape recognition and data compression. Examples of complex objects are presented and commented on to show the potential of our approach for shape modeling.     

拉伸类特征的高效实现

在特征造型系统中,对于复杂零件的造型,特征实现的效率问题越来越突出。对于拉伸类特征：孔、槽、凸台等,通常将其特性轮廓线拉伸形成标准特征体,然后用布尔操作与基本体结合。但是,由于布尔操作存在效率低、操作的可预见性差等问题,效果并不令人满意。针对这些问题,我们提出了布操作的一种替代,将轮廓线直接拉伸到实体的边界。该算法作为一种有效的造型手段。已在特征造型系统ZD－MCADⅡ中用于拉伸类特征的实现。     

Voxelized Minkowski sum computation on the GPU with robust culling

We present a new approach for computing the voxelized Minkowski sum (excluding any enclosed voids) of two polyhedral objects using programmable Graphics Processing Units (GPUs). We first cull out surface primitives that will not contribute to the final boundary of the Minkowski sum, analyzing and adaptively bounding the rounding errors of the culling algorithm to solve the floating point error problem. The remaining surface primitives are then rendered to depth textures along six orthogonal directions to generate an initial solid voxelization of the Minkowski sum. Finally we employ fast flood fill to find all the outside voxels. We generate both solid and surface voxelizations of Minkowski sums without enclosed voids and support high volumetric resolution of 1024³ with low video memory cost. The whole algorithm runs on the GPU and is at least one order of magnitude faster than existing boundary representation (B-rep) based algorithms. It avoids the large number of 3D Boolean operations needed in most existing algorithms and is easy to implement. The voxelized Minkowski sums can be used in a variety of applications including motion planning and penetration depth computation.     

Volumetric T-spline construction using Boolean operations

In this paper, we present a novel algorithm for constructing a volumetric T-spline from B-reps inspired by constructive solid geometry Boolean operations. By solving a harmonic field with proper boundary conditions, the input surface is automatically decomposed into regions that are classified into two groups represented, topologically, by either a cube or a torus. We perform two Boolean operations (union and difference) with the primitives and convert them into polycubes through parametric mapping. With these polycubes, octree subdivision is carried out to obtain a volumetric T-mesh, and sharp features detected from the input model are also preserved. An optimization is then performed to improve the quality of the volumetric T-spline. The obtained T-spline surface is C ² everywhere except the local region surrounding irregular nodes, where the surface continuity is elevated from C ⁰ to G ¹. Finally, we extract trivariate Bézier elements from the volumetric T-spline and use them directly in isogeometric analysis.     

A simpler counterexample to a long-standing conjecture on the complexity of Bryantʼs apply algorithm

In 1986 in his seminal paper Bryant has introduced Ordered Binary Decision Diagrams (OBDDs) as a dynamic data structure for the representation and manipulation of Boolean functions which allow efficient algorithms for important operations like synthesis, the combination of two Boolean functions by a Boolean operator, and equivalence checking. Based on his empirical evaluation he has conjectured that his apply algorithm for the synthesis works in linear time with respect to the input and output size. Recently in 2012, Yoshinaka et al. have presented a counterexample which contradicts this conjecture but their example has the drawback that the chosen variable ordering for the OBDD representation of the input and output is bad. Therefore, they have raised the question whether Bryant?s conjecture may still stand for reasonable variable orderings. Here, a negative answer is given by presenting a simple counterexample which works for such kind of variable orderings.     

Constructive non-regularized geometry

Solid modelling is concerned with the construction and manipulation of unambiguous computer representations of solid objects. These representations permit us to distinguish the interior, the boundary and the complement of a solid. They are conveniently specified in Constructive Solid Geometry (CSG) by a construction tree that has solid primitives as leaves and rigid body motions or regularized Boolean operations as internal nodes. Algoriths for classifying sets with respect to CSG trees and for evaluating the boundaries of the corresponding solids are known, at least for simple geometric domains. Emerging CAD applications require that we extend the domain of solid modellers to support more general and more structured geometric objects. The focus is on dimensionally non-homogeneous, non-closed pointsets with internal structures. These entities are well suited for dealing with mixed-dimensional (‘non-manifold’) objects in ⁿ that have dangling or missing boundary elements, and that may be composed of several regions. A boundary representation for such objects has been described elsewhere. We propose to specify and represent inhomogeneous objects in terms of Constructive Non-Regularized Geometry (CNRG) trees that extend the domain of CSG by supporting non-regularized primitive shapes as leaves, and by providing more general set-theoretic and topological operators at interior nodes. Filtering operations are also provided that construct CNRG objects from aggregates of selected regions of other CNRG objects. A syntax and semantics of the operators in CNRG are presented, and some basic algorithms for classifying pointsets with respect to the regions of objects represented by CNRG trees are outlined.     

Simultaneous and incremental feature-based multiresolution modeling with feature operations in part design

This paper proposes a new feature-based multiresolution modeling approach that can provide multiresolution representation of dynamically changing CAD models of intermediate design stage. Feature-based multiresolution modeling provides simplified shapes of parts of various levels of detail (LOD) by suppressing the detailed features according to a certain LOD criterion. Unlike previous research having mainly focused on the multiresolution representation of the final design model, our approach can carry out simultaneous and incremental multiresolution representation on the intermediate design models. To implement the system supporting this capability, we developed history-based selective Boolean operations, in which if the order of the Boolean operations for a part is altered, the regions affected by the operations are redefined according to the history of the Boolean operations so that the resultant shape may be the same as the original shape of the part. The system implemented using these operations guarantees a unique and valid shape for each intermediate LOD in the simultaneous multiresolution modeling environment. Since the system provides the designer immediately with various detail levels of the CAD model in any design stage, the design process is expected to be accelerated.     

EXPLOITING THE POTENTIALS OF WIREFRAME MODELING

Solid modeling with precise NURBS boundaries compliant with STEP standard representsthe most promising way of designing complicated mechanical products in a CIM environment. In paral-lel to the traditional approach of putting together volumetric primitives with Boolean operations, an al-ternative way of applying the wireframe and skinning techniques is under development. The latter ap-proach is easy to implement, robust and capable of handling the most sophisticated models, while suf-fers the drawbacks of low efficiency in identifying interactively the boundaries of each surface patchwhen the line segments are interlaced and located close to each other. This paper describes the essentialsof the wireframe and skinning techniques which produce the identical product information model as asolid modeler.     

Extending the CSG Tree. Warping, Blending and Boolean Operations in an Implicit Surface Modeling System

Automatic blending has characterized the major advantage of implicit surface modeling systems. Recently, the introduction of deformations based on space warping and Boolean operations between primitives has increased the usefulness of such systems. We propose a further enhancement which will extend the range of models that can be easily and intuitively defined with a skeletal implicit surface system. We describe a hierarchical method which allows arbitrary compositions of models that make use of blending, warping and Boolean operations. We call this structure the BlobTree . Blending and space warping are treated in the same way as union, difference and intersection, i.e. as nodes in the BlobTree . The traversal of the BlobTree is described along with two rendering algorithms; a polygonizer and a ray tracer. We present some examples of interesting models which can be made easily using our approach that would be very difficult to represent with conventional systems.     

Interactive Boundary Computation of Boolean Combinations of Sculptured Solids

We present algorithms and systems for interactive boundary computation of Boolean combinations of sculptured solids. The algorithm is applicable to all spline solids and computes an accurate boundary representation. To speed up the computation, the algorithm exploits parallelism at all stages. It has been implemented on a multi-processor SGI and takes one second on average per boolean operation to compute the boundary of high degree primitives. The system has also been integrated with an immersive design and manipulation environment. The resulting system is able to interactively evaluate boundaries of the models, display them for model validation and place them at appropriate position using collision detection algorithms.     

Multi-level Editing of Hierarchical Documents

Collaborative editing enables a group of people to edit documents collaboratively over a computer network. Customisation of the collaborative environment to different subcommunities of users at different points in time is an important issue. The model of the document is an important factor in achieving customisation. We have chosen a tree representation encompassing a large class of documents, such as text, XML and graphical documents and here we propose a multi-level editing approach for maintaining consistency over hierarchical-based documents. The multi-level editing approach involves logging edit operations that refer to each node. Keeping operations associated with the tree nodes to which they refer offers support for tracking user activity performed on various units of the document. This facilitates the computation of awareness information and the handling of conflicting changes referring to units of the document. Moreover, increased efficiency is obtained compared to existing approaches that use a linear structure for representing documents. The multi-level editing approach involves the recursive application of any linear merging algorithm over the document structure and we show how the approach was applied for real-time and asynchronous modes of collaboration.     

A B-spline based framework for volumetric object modeling

With the recent development of Iso-geometric Analysis (IGA) (Cottrell et al., 2009) and advanced manufacturing technologies employing heterogeneous materials, such as additive manufacturing (AM) of functionally graded material, there is a growing emerging need for a full volumetric representation of 3D objects, that prescribes the interior of the object in addition to its boundaries. In this paper, we propose a volumetric representation (V-rep) for geometric modeling that is based on trimmed B-spline trivariates and introduce its supporting volumetric modeling framework. The framework includes various volumetric model (V-model) construction methods from basic non-singular volumetric primitives to high level constructors, as well as Boolean operations’ support for V-models. A V-model is decomposed into and defined by a complex of volumetric cells (V-cells), each of which can also represent a variety of additional varying fields over it, and hence over the entire V-model. With these capabilities, the proposed framework is able of supporting volumetric IGA needs as well as represent and manage heterogeneous materials for AM. Further, this framework is also a seamless extension to existing boundary representations (B-reps) common in all contemporary geometric modeling systems, and allows a simple migration of existing B-rep data, tools and algorithms. Examples of volumetric models constructed using the proposed framework are presented.     

Signed algebraic level sets on NURBS surfaces and implicit Boolean compositions for isogeometric CAD–CAE integration

Boundary-representation (B-rep) geometrical models, often mathematically represented using Non-Uniform Rational B-Spline (NURBS) surfaces, are the starting point for complex downstream product life-cycle evaluations including Computer-Aided Engineering (CAE). Boolean operations during B-rep model generation require surface intersection computations to describe the composed entity. However, for parametric NURBS surfaces, intersection operations are non-trivial and typically carried out numerically. The numerical intersection computations introduce challenges relating to the accuracy of the resulting representation, efficiency with which the computation is carried out, and robustness of the result to small variations in geometry. Often, for downstream CAE evaluations, an implicit, procedural knowledge of the Boolean operations between the composed objects that can resolve point containment queries (exact to the original NURBS bounding surfaces) maybe sufficient during quadrature. However, common point containment queries on B-rep models are numerical, iterative and relatively expensive. Thus, the first goal of the present paper is to describe a purely algebraic, and therefore non-iterative, approach to carrying out point containment queries on complex B-rep models built using low-degree NURBS surfaces. For CAE operations, the boundary representation of B-rep solids is, in general, not convenient and as a result, the B-rep model is converted to a meshed volumetric approximation. The major challenges to such a conversion include capturing the geometric features accurately when constructing the secondary (meshed) representation, apart from the efficiency of carrying out such a mesh generation step repeatedly as the geometric shape evolves. Thus, an ideal analysis procedure would operate directly on B-rep CAD models, without needing a secondary mesh, and would procedurally unify the geometric operations during CAD as well as CAE stages. Therefore, the second and broader goal of the present paper is to demonstrate CAD–CAE integration using signed algebraic level set operations directly on B-rep models by embedding or immersing the bounding surfaces within a discretized domain while preserving the geometric accuracy of the surfaces exact to the original NURBS representation during analysis.     

3-D shape recovery using distributed aspect matching

An approach to the recovery of 3-D volumetric primitives from a single 2-D image is presented. The approach first takes a set of 3-D volumetric modeling primitives and generates a hierarchical aspect representation based on the projected surfaces of the primitives; conditional probabilities capture the ambiguity of mappings between levels of the hierarchy. From a region segmentation of the input image, the authors present a formulation of the recovery problem based on the grouping of the regions into aspects. No domain-independent heuristics are used; only the probabilities inherent in the aspect hierarchy are exploited. Once the aspects are recovered, the aspect hierarchy is used to infer a set of volumetric primitives and their connectivity. As a front end to an object recognition system, the approach provides the indexing power of complex 3-D object-centered primitives while exploiting the convenience of 2-D viewer-centered aspect matching; aspects are used to represent a finite vocabulary of 3-D parts from which objects can be constructed     

Logical reasoning in natural language: It is all about knowledge

A formal, computational, semantically clean representation of natural language is presented. This representation captures the fact that logical inferences in natural language crucially depend on the semantic relation of entailment between sentential constituents such as determiner, noun, adjective, adverb, preposition, and verb phrases.The representation parallels natural language in that it accounts for human intuition about entailment of sentences, it preserves its structure, it reflects the semantics of different syntactic categories, it simulates conjunction, disjunction, and negation in natural language by computable operations with provable mathematical properties, and it allows one to represent coordination on different syntactic levels.The representation demonstrates that Boolean semantics of natural language can be successfully modeled in terms of representation and inference by knowledge representation formalisms with Boolean semantics. A novel approach to the problem of automatic inferencing in natural language is addressed. The algorithm for updating a computer knowledge base and reasoning with explicit negative, disjunctive, and conjunctive information based on computing subsumption relation between the representations of the appropriate sentential constituents is discussed with examples.     

Boolean operations on multi-region solids for mesh generation

An algorithm for Boolean operations on non-manifold models is proposed to allow the treatment of solids with multiple regions (internal interfaces) and degenerate portions (shells and wires), in the context of mesh generation. In a solid modeler, one of the most powerful tools to create three-dimensional objects with any level of geometric complexity is the Boolean set operators. They are intuitive and popular ways to combine solids, based on the operations applied to point sets. To assure that the resulting objects have the same dimension as the original objects, without loose or dangling parts, a regularization process is usually applied after a Boolean operation. In practice, the regularization is performed classifying the topological elements and removing internal or lower-dimensional structures. However, in many engineering applications, the adopted geometric model may contain idealized internal parts, as in the case of multi-region models, or lower-dimensional parts, as in the case of solids that contain dangling slabs that are represented as zero-thickness surfaces or wireframes in the model. Therefore, the aim of this work is the development of a generic algorithm that allows the application of the Boolean set operations in a geometric modeling environment applied to finite and boundary element mesh generation. This environment adopts a non-manifold boundary representation that considers an undefined number of topological entities (group concept), and works with objects of different dimensions and with objects not necessarily plane or polyhedral (parametric curved surfaces). Numerical examples are presented to illustrate the proposed methodology.     

A topologically robust algorithm for Boolean operations on polyhedral shapes using approximate arithmetic

We present a topologically robust algorithm for Boolean operations on polyhedral boundary models. The algorithm can be proved always to generate a result with valid connectivity if the input shape representations have valid connectivity, irrespective of the type of arithmetic used or the extent of numerical errors in the computations or input data. The main part of the algorithm is based on a series of interdependent operations. The relationship between these operations ensures a consistency in the intermediate results that guarantees correct connectivity in the final result. Either a triangle mesh or polygon mesh can be used. Although the basic algorithm may generate geometric artifacts, principally gaps and slivers, a data smoothing post-process can be applied to the result to remove such artifacts, thereby making the combined process a practical and reliable way of performing Boolean operations.     

一种数字波形的链表示方法及其在波形识别中的应用

本文叙述了在保持原始数字波形过零点位置信息的条件下,用几个具有不同斜率的直线 段逼近原始波形的算法.根据波形的复杂度和所要求的精度可以方便地调整基元数目.一般 说来用三个基元组成的链保存了原有波形的大部分信息并可用于对波形的句法识别.在某些 地震信号上进行的试验说明了这种链表示的有效性.