Boolean Operations on n-Dimensional Objects

Computation of the union, intersection, and difference of n-dimensional objects plays a central role in several computer-aided geometric design problems. An algorithm for computing these operations that uses a boundary classification technique is presented here. The algorithm is recursive in structure, with the recursion being on the dimensions of objects dealt with at each stage. The representation treats all entities as objects, making no distinction between faces, edges, or vertices. The objects produced are "regularized"; that is, there are no degenerate boundaries such as dangling edges. The sample application given involves hidden-surface removal.     

Surface area estimation of digitized 3D objects using quasi-Monte Carlo methods

A novel and efficient quasi-Monte Carlo method for estimating the surface area of digitized 3D objects in the volumetric representation is presented. It operates directly on the original digitized objects without any surface reconstruction procedure. Based on the Cauchy-Crofton formula from integral geometry, the method estimates the surface area of a volumetric object by counting the number of intersection points between the object's boundary surface and a set of uniformly distributed lines generated with low-discrepancy sequences. Using a clustering technique, we also propose an effective algorithm for computing the intersection of a line with the boundary surface of volumetric objects. A number of digitized objects are used to evaluate the performance of the new method for surface area measurement.     

Efficient and accurate B-rep generation of low degree sculptured solids using exact arithmetic: II—computation

We present efficient algorithms for exact boundary computation on low degree sculptured CSG solids using exact arithmetic. These include algorithms for computing the intersection curves of low-degree trimmed parametric surfaces, decomposing them into multiple components for efficient point location queries inside the trimmed regions, and computing the boundary of the resulting solid using topological information and component classification tests. We also employ a number of previously developed algorithms such as algebraic curve classification and multivariate Sturm sequences. We present some results from a preliminary implementation of our approach. This paper follows a previous paper which described the representations used in our approach.     

Laplace-Beltrami spectra as ‘Shape-DNA’ of surfaces and solids

This paper introduces a method to extract ‘Shape-DNA’, a numerical fingerprint or signature, of any 2d or 3d manifold (surface or solid) by taking the eigenvalues (i.e. the spectrum) of its Laplace-Beltrami operator. Employing the Laplace-Beltrami spectra (not the spectra of the mesh Laplacian) as fingerprints of surfaces and solids is a novel approach. Since the spectrum is an isometry invariant, it is independent of the object's representation including parametrization and spatial position. Additionally, the eigenvalues can be normalized so that uniform scaling factors for the geometric objects can be obtained easily. Therefore, checking if two objects are isometric needs no prior alignment (registration/localization) of the objects but only a comparison of their spectra. In this paper, we describe the computation of the spectra and their comparison for objects represented by NURBS or other parametrized surfaces (possibly glued to each other), polygonal meshes as well as solid polyhedra. Exploiting the isometry invariance of the Laplace-Beltrami operator we succeed in computing eigenvalues for smoothly bounded objects without discretization errors caused by approximation of the boundary. Furthermore, we present two non-isometric but isospectral solids that cannot be distinguished by the spectra of their bodies and present evidence that the spectra of their boundary shells can tell them apart. Moreover, we show the rapid convergence of the heat trace series and demonstrate that it is computationally feasible to extract geometrical data such as the volume, the boundary length and even the Euler characteristic from the numerically calculated eigenvalues. This fact not only confirms the accuracy of our computed eigenvalues, but also underlines the geometrical importance of the spectrum. With the help of this Shape-DNA, it is possible to support copyright protection, database retrieval and quality assessment of digital data representing surfaces and solids.A patent application based on ideas presented in this paper is pending.     

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.     

Shape description by medial surface construction

The medial surface is a skeletal abstraction of a solid that provides useful shape information, which compliments existing model representation schemes. The medial surface and its associated topological entities are defined, and an algorithm for computing the medial surface of a large class of B-rep solids is then presented. The algorithm is based on the domain Delaunay triangulation of a relatively sparse distribution of points, which are generated on the boundary of the object. This strategy is adaptive in that the boundary point set is refined to guarantee a correct topological representation of the medial surface     

Loop detection in surface patch intersections

A condition is presented for guaranteeing that all branches of the curve of intersection of two parametric surfaces patches contain a point on at least one of the patch boundary curves. This is of value because it eliminates a robustness limitation which arises when computing surface intersections using the marching method, namely, assuring that all branches of the intersection curve have been found. The intersection curve of any two surface patches meeting the prescribed condition can be computed by locating points where patch boundary curves intersect the opposing patch, and then using those points as starting points for the marching algorithm.     

An application of algebraic topology to solid modeling in molecular biology

A recurring problem in solid modeling, computer graphics, and molecular modeling is the computation of the intersection of two objects. A general solution to this problem is obtained by applying two ideas of algebraic topology: (1) a chain complex, and (2) a boundary formula for the intersection of two objects. A general data structure for a chain complex made up of piecewise polynomial cells is described, as are algorithms for connectivity, containment and intersection. The basic ideas of this work are abstract, topological, and for the most part, independent of the shape and dimensionality of the objects. An application to structural molecular biology is presented. The application identifies convex and concave features of protein surfaces.     

Display techniques and boundary evaluation of a Sweep-CSG modeller

Among the various techniques for displaying solid objects, ray tracing is the most popular method for sweep-generated objects, owing to its simplicity and effectiveness. The main problem in ray tracing is to find the point of intersection between the ray and the object. By taking consideration of the special features of a surface generated by sweep, the ray/object intersection problem can be reduced to 2-D planar problem. This paper presents a raycasting technique for displaying Sweep-CSG-represented solids. This technique works directly on the Sweep-CSG representation and does not require explicit boundary information. Boundary information is, however essential for line-drawing outputs. In this paper, boundary-evaluation techniques for obtaining edges of a Sweep-CSG solid are described. Special techniques for evaluating the boundaries of a solid generated by sweeping another solid are also discussed.     

Computing medial axes of generic 3D regions bounded by B-spline surfaces

A new approach is presented for computing the interior medial axes of generic regions in R³ bounded by C⁽⁴⁾-smooth parametric B-spline surfaces. The generic structure of the 3D medial axis is a set of smooth surfaces along with a singular set consisting of edge curves, branch curves, fin points and six junction points. In this work, the medial axis singular set is first computed directly from the B-spline representation using a collection of robust higher order techniques. Medial axis surfaces are computed as a time trace of the evolving self-intersection set of the boundary under the the eikonal (grassfire) flow, where the bounding surfaces are dynamically offset along the inward normal direction. The eikonal flow results in special transition points that create, modify or annihilate evolving curve fronts of the (self-) intersection set. The transition points are explicitly identified using the B-spline representation. Evolution of the (self-) intersection set is computed by adapting a method for tracking intersection curves of two different surfaces deforming over generalized offset vector fields. The proposed algorithm accurately computes connected surfaces of the medial axis as well its singular set. This presents a complete solution along with accurate topological structure.     

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.     

Isogeometric segmentation: Construction of cutting surfaces

The objective of Isogeometric Segmentation is to generate a decomposition of a solid, given in boundary representation, into a collection of a relatively small number of base solids, which can easily be subdivided into topological hexahedra. This can be achieved by repeatedly splitting the solid. In each splitting step, one chooses a cutting loop, which is a cycle of curves around the boundary of the solid, and constructs a cutting surface that splits the solid into two simpler ones. When only hexahedra or pre-defined base solids are left this process terminates.The construction of the cutting surface must ensure that two essential properties are fulfilled: the boundary curves of the surface interpolate the previously constructed cutting loop and the surface neither intersects itself nor the boundary of the solid. A novel method for generating the cutting surface is presented in this paper. The method combines two steps: First we generate an implicit guiding surface, which is subsequently approximated by a trimmed spline surface in the second step.     

Solid modeling of polyhedral objects by Layered Depth-Normal Images on the GPU

We introduce a novel solid modeling framework taking advantage of the architecture of parallel computing on modern graphics hardware. Solid models in this framework are represented by an extension of the ray representation — Layered Depth-Normal Images (LDNI), which inherits the good properties of Boolean simplicity, localization and domain decoupling. The defect of ray representation in computational intensity has been overcome by the newly developed parallel algorithms running on the graphics hardware equipped with Graphics Processing Unit (GPU). The LDNI for a solid model whose boundary is represented by a closed polygonal mesh can be generated efficiently with the help of hardware accelerated sampling. The parallel algorithm for computing Boolean operations on two LDNI solids runs well on modern graphics hardware. A parallel algorithm is also introduced in this paper to convert LDNI solids to sharp-feature preserved polygonal mesh surfaces, which can be used in downstream applications (e.g., finite element analysis). Different from those GPU-based techniques for rendering CSG-tree of solid models Hable and Rossignac (2007, 2005) [1] and [2], we compute and store the shape of objects in solid modeling completely on graphics hardware. This greatly eliminates the communication bottleneck between the graphics memory and the main memory.     

Data partitioning for parallel solid modelling

Solid modelling involves processing large amounts of geometric data. Distributed processing is a promising technique for improving the speed of computationally intensive processes. Solid modelling is thus a good candidate for parallel processing. We present a method for distributing entities of solid models in an array of processors for intersection tests in evaluating boolean operations. We employ distributed boundary representation and a recursive spatial subdivision technique for data partitioning. Parallel algorithms distribute entities among the array of processors mapped to a set of 3D rectangular regions in the object space. Entities intersecting or residing in the intersection regions of the objects are distributed. An experimental system was implemented on a DECmpp 12000/Sx/8K distributed memory SIMD computer.     

Automatic decomposition of 3D solids into contractible pieces using Reeb graphs

This work is motivated by the need to generate volumetric spline models for isogeometric analysis. There exist numerous constructions of volumetric spline models that represent contractible solids. We present a novel decomposition algorithm that splits general solids into pieces that can be dealt with by these existing methods. More precisely, we present a method to automatically decompose solid objects in boundary representation into pieces with fewer or no tunnels by cutting them with auxiliary surfaces. The segmentation is guided by a reduced form of the object’s boundary and volume Reeb graphs with respect to several Morse functions, the level sets of which define the cutting surfaces. Special attention is paid to the selection of suitable cutting surfaces, where we employ a quality criterion to avoid the creation of badly shaped pieces.     

基于几何法表示的曲面实体的分割算法

分割是实体造型的重要步骤,而边界问题是影响分割算法效率和稳定性的主要因素。工程中常用的二次曲面有自封闭的特性,在相交时交线会出现退化和自交等情况,给拓扑表示和帝体重建带来困难,另外,边界重合也是实体分割时经常要遇到的问题,该文在二次曲面几何法表示的基础上,针对二次曲面相交时交线的特性,设计了合理的分割策略,提出了有效的分割算法,并对边界重合等问题做了很好的处理,同时用实例验证了本文算法的有效性。     

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.     

Modelling polyhedral solids bounded by multi-curved parametric surfaces

Since the beginning of geometric modelling as a field of CAD a decade ago, the methods for interactive design of solid objects and interactive design of free-formed surfaces (of degree three and higher) were developed along parallel yet disjoint lines. One led to the development of techniques for representing and manipulating the shape of polyhedral solids bounded mostly by planes, while the other led to the development of techniques for the mathematical representation of curved surfaces, without paying attention to their combination into volumetric solids. Though the need for integrating solid object modelling with surface modelling for the design of such artefacts as machine parts, aircraft, cars and ships has been widely recognized, there is so far no single modelling system which provides such capabilities in a general way.An integrated solids modelling system for representing and manipulating polyhedral objects bounded by bicubic parametric surfaces is presented. Its basic capabilities include the representation of solids through a surface-based model, such that the surface underlying any face can be replaced by another surface that has been modelled independently. Other functionalities include scaling, rotation and translation of shapes and their pairwise combination into more complex shapes by means of spatial set operators.     

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.