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.     

Interactive vizualization of constructive solid geometry scenes on graphic processors

A ray-tracing algorithm for interactive visualization of very large and structurally complicated scenes presented in the constructive solid geometry (CSG) form is suggested. The algorithm is capable of visualizing such scenes in real time by using a graphic processor. As primitives, classical shapes and objects represented in an analytical form (in particular, second-order surfaces and implicit functions) are used. Unlike other similar algorithms, our algorithm produces the final image in a single pass and has no constraints on the maximum number of primitives and on the CSG tree depth. The key feature of the algorithm is a method for optimizing CSG models, which converts the input tree to an equivalent spatially coherent and well-balanced form (a completely balanced equivalent tree may not exist). The performance of visualization after applying the optimization technique is shown to depend on only the computational resource of the GPU (in contrast to multi-pass algorithms whose performance is restricted by memory capacity). It has been shown experimentally that our algorithm is capable of rendering CSG models consisting of more than a million CSG primitives with the tree depth up to 24.     

基于任意骨架的隐式曲面造型技术

给出了一个新的基于任意多面体网格骨架的构造性自由曲面造型算法.算法首先由每个给定骨架构造出一个距离场,然后利用隐函数光滑过渡技术和CSG(constructive solid geometry)表示技术将所构造的隐式曲面自由地两两粘合成一张光滑曲面.隐式曲面的多边形化算法则用来生成最终曲面网格.以任意骨架作为基本体素,突破了传统隐式曲面以点为基本骨架的限制.而且,距离曲面很好地逼近了原骨架形状,使用户可直观地对复杂曲面进行交互设计.而形变函数的引入,则极大地丰富了此方法的造型能力.实验结果表明,基于该算法的原型系统能够方便、直观地构造复杂的自由曲面.     

Deferred boundary evaluation of complex CSG models

In this paper we present a deferred method for evaluating a complete CSG tree based on triangulated solids. It allows the exact evaluation of the surface of the entire model in a single step, using regularized Boolean classifications. The overall performance with this approach is better than with the classical method, which incrementally evaluates a CSG tree with single Boolean operations. The deferred algorithm does not use any intermediate result for the nodes of the CSG tree. It uses a very simple data structure and an octree that speeds up spatial queries for the entire CSG tree. The algorithm intensively uses multitasking and is ready for working with very complex CSG expressions, including the application of an out-of-core based approach.     

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.     

A virtual punching method for shape optimization of openings on curved panels using CAD-based Boolean operations

This paper aims at developing new methodologies for shape optimization of openings on three-dimensional curved panels that are used widely in aeronautical and aerospace engineering. To circumvent the difficulties associated with the hole boundary shape parameterization, a virtual punching method that exploits Boolean operations of the CAD modeler is proposed for the definition of shape design variables. Compared with the parametric mapping method developed previously, the virtual punching method is shown to be an implicit boundary representation for this specific kind of structure. Instead, the parametric mapping method is based on the explicit boundary representation.A zero-order genetic algorithm (GA) is correspondingly implemented into the design procedure of the virtual punching method to execute the optimization process for two reasons. First, it makes it possible to avoid sensitivity analysis that is relatively difficult due to the implicit boundary representation formulation and the use of an unstructured mesh. Second, the computing cost of the GA is practically affordable in shape optimization because often only a small number of design variables are involved. Numerical tests are carried out for typical examples of the stress concentration minimization around openings on the curved panels.     

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.     

Efficient data-parallel tree-traversal for BlobTrees

The hierarchical implicit modelling paradigm, as exemplified by the BlobTree, makes it possible to support not only Boolean operations and affine transformations, but also various forms of blending and space warping. Typically, the resulting solid is converted to a boundary representation, a triangle mesh approximation, for rendering. These triangles are obtained by evaluating the corresponding implicit function (field) at the samples of a dense regular three-dimensional grid and by performing a local iso-surface extraction at each voxel. The performance bottleneck of this rendering process lies in the cost of the tree traversal (which typically must be executed hundreds of millions of times) and in the cost of applying the inverses of the space transformations associated with some of the nodes of the tree to the grid samples.Tree pruning is commonly used to reduce the number of samples for which the field value must be computed. Here, we propose a complementary strategy, which reduces the costs of both the traversal and of applying the inverses of the blending and warping transformations that are associated with each evaluation.Without blending or warping, a BlobTree can be reduced to a CSG tree only containing Boolean nodes and affine transformations, which can be reordered to increase memory coherence. Furthermore, the cumulative effects of the affine transformations can be precomputed via matrix multiplication. We propose extensions of these techniques from CSG trees to the fully general BlobTrees. These extensions are based on tree reordering, bottom-up traversal, and caching of the combined matrix for uninterrupted runs of affine transformations in the BlobTree.We show that these new techniques result in an order of magnitude performance improvement for rendering large BlobTrees on modern Single Program Multiple Data (SPMD) devices.     

Creation and boundary evaluation of CSG-models

This paper deals with one particular type of solid model representation. Constructive solid geometry (CSG) describes solids in terms of primitive shapes combined by Boolean operators. The goal of this paper is to present an algorithm suitable for the visualization of a given CSG-object for verification purposes. To accomplish this, the CSG representation is to be converted into a polygonal boundary representation (B-Rep), which allows the easy display of the solid's visible edges and surfaces. An algorithm performing this conversion is called a boundary evaluator. This paper describes the fundamental concepts leading to this new algorithm and presents some examples.The boundary evaluator described here follows the following steps: (1) A polygonal mesh is created that covers the primitive shapes. (2) Interfering polygons are repertedly subdivided until the resulting mesh contains the intersection curves between the primitives. (3) The location and validity of all polygons must be determined since only valid polygons reflect the solid's final shape. (4) Adjoining coplanar polygons are collected and merged by deleting their common edges. The final result of this procedure is a consistent, nonredundant polygon mesh describing the given solid model. Now the object may be displayed by simple perspective plots, by isometric projections, by hidden line drawings, or through the use of hidden surface removal techniques as color-shaded pictures. The algorithm presented here has been successfully used to create a variety of renderings of various CSG-models. The interpretation, display, and validation of computer-generated CSG models is essential for the successful use of such models in the engineering design process.     

A new space subdivision method for ray tracing CSG modelled scenes

A new algorithm for space tracing with CSG modelled scenes is presented. Space is divided in an irregular fashion to fit the objects as closely as possible. For this reason, primitive minimal bounding boxes are computed. Space subdivision is achieved in two steps: partitioning in projection plane and depth partitioning. A set of 3D regions named cells are then created. A Boolean CSG tree is distributed into the cell structure to form in each cell the minimal boolean CSG tree using the relevant primitives. The searching process for the next cell along the ray path is performed by using a local data structure associated with each cell. The goal of this structure is to link the cells together. An improvement, named mailbox, for all space tracing algorithms is detailed. Results are presented for two scenes to compare this new algorithm with Roth's algorithm.     

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.     

基于自适应延迟切割的三角网格布尔运算优化

规则化的布尔运算被广泛应用在三维建模系统中.近年来,随着图形硬件的发展,基于三角网格的规则化布尔算法由于输出结果能直接被图形硬件处理,表现出了明显的优势.但是传统的算法由于采用CSG树局部评估策略,使得面片在相交测试中反复被切割,并且由于面片分类在切割后的模型之间直接进行,导致算法无法在保证鲁棒性的同时实现高性能.为了避免这些问题,本文呈现了一种CSG树全局评估算法来统一执行单次和连续布尔运算.算法由两部分组成：自适应的延迟切割和全局化面片分类.在自适应的延迟切割阶段,算法通过仔细处理多个三角面片相交导致的各种情况使得延迟切割被扩展到整个CSG树来避免由于面片的反复切割带来的数值误差累积并利用自适应的八叉树使得相交测试能在线性时间内完成.在全局化面片分类阶段,算法通过分治法使得分类始终在切割后的面片和原始输入模型之间进行来保证分类的精度;通过结合组分类策略和自适应的八叉树来进一步优化了分类性能。实验结果表明,本文提出的算法无论是在执行单次或连续布尔运算时都能在保证鲁棒性同时性能优于其他的算法,因此本文算法可广泛应用于交互式建模系统中,如数字雕刻、计算机辅助设计和制造（CAD/CAM）等.     

Radial Supershapes for Solid Modeling

In the previous work, an efficient method has been proposed to represent solid objects as multiple combinations of globally deformed supershapes. In this paper, this framework is applied with a new supershape implicit function that is based on the notion of radial distance and results are presented on realistic models composed of hundreds of hierarchically globally deformed supershapes. An implicit equation with guaranteed differential properties is obtained by simple combinations of the primitives' implicit representations using R-function theory. The surface corresponding to the zero-set of the implicit equation is efficiently and directly polygonized using the primitives' parametric forms. Moreover, hierarchical global deformations are considered to increase the range of shapes that can be modeled. The potential of the approach is illustrated by representing complex models composed of several hundreds of primitives inspired from CAD models of mechanical parts.     

Direct boolean intersection between acquired and designed geometry

In this paper, a new shape modeling approach that can enable direct Boolean intersection between acquired and designed geometry without model conversion is presented. At its core is a new method that enables direct intersection and Boolean operations between designed geometry (objects bounded by NURBS and polygonal surfaces) and scanned geometry (objects represented by point cloud data).We use the moving least-squares (MLS) surface as the underlying surface representation for acquired point-sampled geometry. Based on the MLS surface definition, we derive closed formula for computing curvature of planar curves on the MLS surface. A set of intersection algorithms including line and MLS surface intersection, curvature-adaptive plane and MLS surface intersection, and polygonal mesh and MLS surface intersection are successively developed. Further, an algorithm for NURBS and MLS surface intersection is then developed. It first adaptively subdivides NURBS surfaces into polygonal mesh, and then intersects the mesh with the MLS surface. The intersection points are mapped to the NURBS surface through the Gauss-Newton method.Based on the above algorithms, a prototype system has been implemented. Through various examples from the system, we demonstrate that direct Boolean intersection between designed geometry and acquired geometry offers a useful and effective means for the shape modeling applications where point-cloud data is involved.     

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.     

Consistent Schemes for Addressing Surfaces when Ray Tracing Transparent CSG Objects

Constructive Solid Geometry (CSG) defines the shape of objects, i.e. the inside and the outside regions of objects, but it does not define the material properties of the space in the interior of objects. The definition is ambiguous. There are points of space lying in several primitives, which can consist of different materials. When visualizing transparent objects this ambiguity leads to strange results, which are not consistent with the CSG modelling scheme and must therefore be eliminated. This work describes how an unambiguous model can be built by asymmetric CSG-operators and how correct refraction and shading on material boundaries can be established by separating surface properties from material properties. This separation leads to a consistent view of CSG modelling also concerning materials and surfaces. Ray tracing CSG trees and the shading model are influenced by these asymmetric operators. We introduce an applied classification scheme to handle the requirements of the new operator definition.     

A new space subdivision for ray tracing CSG solids

Ray tracing successfully creates realistic images of constructive solid geometry (CSG) solids. We describe a nonuniform space subdivision scheme that reduces both the number of ray-object intersection computations and point classifications. Our method uses the face planes of the primitives' S-bounds in a bottom-up fashion and produces a subdivision wherein the localized CSG tree in each leaf voxel is greatly minimized. The use of S-bounds in the space subdivision effectively reduces the number of intersection computations as well. The reduction of the localized CSG tree in turn further reduces the number of intersection computations and point classifications. We briefly review existing methods for ray tracing CSG solids, describe our proposed space subdivision method, discuss our implementation and compare it to Bouatouch's (1987) method, and summarize our test results