A new approach for the voxelization of volumetric CSG graphs

This paper presents a new approach for the voxelization of volumetric scene graphs. The algorithm generates slices of each primitive intended to be voxelized using an FPGA based pixel processor. The Blist representation is used for the volume scene tree which reduces storage requirement for each voxel to the log(H+1) bits. The most important advantage of this voxelization algorithm is that any volume scene tree expression can be evaluated without using any computation or stack. Also the algorithm is not object specific, i.e. the same algorithm can be used for the voxelization of different types of objects (convex and concave objects, polygons, lines and surfaces).     

Approximating CSG trees of moving objects

A discussion of the relationship between two solid representation schemes is presented: CSG trees and recursive spatial subdivision exemplified by the bintree, a generalization of the quadtree and octree. Detailed algorithms are developed and analyzed for evaluating CSG trees by bintree conversion. These techniques are shown to enable the addition of the time dimension and motion to the approximate analysis of CSG trees. This facilitates the solution of problems such as static and dynamic interference detection. A technique for projecting across any dimension is also shown. For “well-behaved” CSG trees the execution time of the conversion algorithm is directly related to the spatial complexity of the object represented by the CSG tree (i.e., as the resolution increases, it is asymptotically proportional to the number of bintree nodes and does not depend on the size or form of the CSG tree representation). The set of well-behaved CSG trees include all trees that define multidimensional polyhedra in a manner that does not give rise to tangential intersections at CSG tree nodes. This is an expanded version of a paper titled “Bintrees, CSG Trees, and Time” which appeared inProceedings of the SIGGRAPH '85 Conference, San Francisco (July 1985), pp. 121–130. This work was supported in part by the National Science Foundation under Grants DCR-83-02118 and IRI-88-02457 and in part by the Finnish Academy Deceased on August 5, 1989     

Efficient editing of solid models by exploiting structural and spatial locality

Computer aided design systems based on solid modellers must provide fast visual feedback to users when objects are edited. This implies that boundary representations must be updated rapidly, because displays typically are generated in current-generation modellers from face, edge and vertex data.This paper describes algorithms for updating a boundary representation when an object's constructive solid geometry (CSG) representation is edited. The algorithms exploit the structural (representational) locality inherent in most object modifications by taking advantage of previously computed boundary representations for (sub-) objects that are not affected by the editing operations. They also exploit spatial locality by re-computing boundaries only within the spatial region where changes can occur. The algorithms are efficient, and are guaranteed to produce valid solids because they are based on CSG.     

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.     

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.     

An efficient algorithm for finding the CSG representation of a simple polygon

Modeling two-dimensional and three-dimensional objects is an important theme in computer graphics. Two main types of models are used in both cases: boundary representations, which represent the surface of an object explicitly but represent its interior only implicitly, and constructive solid geometry representations, which model a complex object, surface and interior together, as a boolean combination of simpler objects. Because neither representation is good for all applications, conversion between the two is often necessary.We consider the problem of converting boundary representations of polyhedral objects into constructive solid geometry (CSG) representations. The CSG representations for a polyhedronP are based on the half-spaces supporting the faces ofP. For certain kinds of polyhedra this problem is equivalent to the corresponding problem for simple polygons in the plane. We give a new proof that the interior of each simple polygon can be represented by a monotone boolean formula based on the half-planes supporting the sides of the polygon and using each such half-plane only once. Our main contribution is an efficient and practicalO(n logn) algorithm for doing this boundary-to-CSG conversion for a simple polygon ofn sides. We also prove that such nice formulae do not always exist for general polyhedra in three dimensions.The first author would like to acknowledge the support of the National Science Foundation under Grants CCR87-00917 and CCR90-02352. The fourth author was supported in part by a National Science Foundation Graduate Fellowship. This work was begun while the first author was visiting the DEC Systems Research Center.     

A self-stabilizing algorithm for constructing weakly connected minimal dominating sets

This paper presents a new distributed self-stabilizing algorithm for the weakly connected minimal dominating set problem. It assumes a self-stabilizing algorithm to compute a breadth-first tree. Using an unfair distributed scheduler the algorithm stabilizes in at most O(nmA) moves, where A is the number of moves to construct a breadth-first tree. All previously known algorithms required an exponential number of moves.     

Solid reconstruction from orthographic opaque views using incremental extrusion

The reconstruction of 3-D solids from 2-D projections is an important research topic in reverse engineering. The reconstruction can be grouped into two categories: single-view approach and multiple-view approach. Each approach can be classified as wireframe, BRep or CSG. However, not many CSG approaches have been reported in the literature. The methods are also restricted to uniform-thickness objects or require user interaction. The method proposed in this paper employs the CSG approach. A 3-D solid computer model is reconstructed from 2-D line drawings of six orthographic opaque views, viz. top, front, left, right, bottom and rear views. Firstly, the six views are grouped into three pairs. For each pair of views, segmented areas from one of the two views (called g-view) is incrementally extruded according to the information in the neighbouring view (called d-view). Extrusion primitive solids are generated during the incremental extrusion. All primitive solids are then unioned into an extrusion solid. Finally, all extrusion solids are intersected to give a unique 3-D solution object.     

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.     

Ray tracing CSG trees using the Sticks representation scheme

A fast ray tracing algorithm of CSG tree is presented. The algorithm uses an adaptive space subdivisions approach, based on the conversion of the objects of the scene into the volumetric Sticks representation scheme. This conversion scheme, which requires O(kn²) memory space to represent data in a n³ grid, makes it possible either to obtain very fast low-quality frontal orthographic projections, or to produce a high-quality rendering of the scene in time less than that needed by classical ray tracing and nearly independent of the number of objects in the scene. Furthermore, the characteristics of the Sticks scheme can be exploited to compute geometric or topological properties of the represented objects. Comparative analyses between the Sticks representation scheme and classical space subdivision schemes and between our Sticksbased ray tracing and classical algorithms are presented.     

An algorithm for converting the boundary representation of a CAD model to its octree representation

Present CAD systems store the solid model of an object using a convenient representation. Boundary models and CSG (Constructive Solid Geometry) models are the most frequently used representations. Based on recent research findings, octree representation of an object presents a promising approach in solving problems in the areas of Computer Graphics, Manufacturing and Robotics. The most notable use of octree representations is in CAD-based robotic path planning problems. Octree models have also been used in fast rendering of 3-D solid models using ray tracing methods. This paper presents an algorithm for converting the boundary representation of polyhedral models to its octree representation. Such an algorithm would provide the link between an object generated using a solid modelling system and the application involving an octree representation of an object. The algorithm is demonstrated by converting a polyhedral boundary model of a sample object to its octree representation.     

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.     

Representation and realistic rendering of natural phenomena with cyclic CSG graphs

A method for ray tracing recursive objects defined by parametric rewriting systems using constructive solid geometry (CSG) as the underlying method of object representation is introduced. Thus, the formal languages of our rewriting systems are subsets of the infinite set of CSG expressions. Instead of deriving such expressions to build up large CSG trees, we translate the systems into cyclic CSG graphs, which can be used directly as an object representation for ray tracing. For this purpose the CSG concept is extended by three new nodes. Selection nodes join all the rules for one grammar symbol, control flow by selecting proper rules, and are end-points of cyclic edges. Transformation nodes map the rays in affine space. Calculation nodes evaluate a finite set of arithmetic expressions to modify global parameters, which effect flow control and transformations. The CSG graphs introduced here are a very compact data structure, much like the describing data set. This property meets our intention to avoid both restrictions of the complexity of the scenes by computer memory and the approximation accuracy of objects.This project was supported by the Fond zur Förderung der wissenschaftlichen Forschung (FWF), Austria, (project no. P09818)     

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.     

Geometry-shader-based real-time voxelization and applications

This work proposes a new voxelization algorithm based on newly available GPU functionalities and designs several real-time applications to render complex lighting effects with the voxelization result. The voxelization algorithm can efficiently transform a highly complex scene in a surface-boundary representation into a set of voxels in one GPU pass using the geometry shader. Newly available 3D textures are used to directly record the surficial and volumetric properties of objects such as opaqueness, refraction, and transmittance. In the first, the usage of 3D textures can remove those strenuous efforts required to modify the encoding and decoding scheme when adjusting the voxel resolution. Second, surficial and volumetric properties recorded in 3D textures can be used to interactively compute and render more realistic lighting effects including the shadow of objects with complex occlusion and the refraction and transmittance of transparent objects. The shadow can be rendered with an absorption coefficient which is computed according to the number of surfaces drawing in each voxel during voxelization and used to compute the amount of light passing through partially occluded complex objects. The surface normal, transmittance coefficient and refraction index recorded in each voxel can be used to simulate the refraction and transmittance lighting effects of transparent objects using our multiple-surfaced refraction algorithm. Finally, the results demonstrate that our algorithm can transform a dynamic scene into a set of voxels and render complex lighting effects in real time without any pre-processing.     

Constructive shell representations for freeform surfaces and solids

We usually model freeform surfaces (mathematically, 2D r-sets embedded in 3D Euclidean space E³) as a finite union of patches represented in the traditional parametric or the recently developed algebraic forms. The article introduces a new representation scheme for freeform surfaces called constructive shell representation (CSR), that draws on recent research on algebraic patches. CSRs of surfaces that constitute boundaries of solids are very useful for solid modeling. They represent thick shells derived from freeform surfaces and provide a means to compute exact CSG representations of freeform solids     

DART+: Direction-aware bichromatic reverse k nearest neighbor query processing in spatial databases

This article presents a novel type of queries in spatial databases, called the direction-aware bichromatic reverse k nearest neighbor(DBRkNN) queries, which extend the bichromatic reverse nearest neighbor queries. Given two disjoint sets, P and S, of spatial objects, and a query object q in S, the DBRkNN query returns a subset P′ of P such that k nearest neighbors of each object in P′ include q and each object in P′ has a direction toward q within a pre-defined distance. We formally define the DBRkNN query, and then propose an efficient algorithm, called DART, for processing the DBRkNN query. Our method utilizes a grid-based index to cluster the spatial objects, and the B⁺-tree to index the direction angle. We adopt a filter-refinement framework that is widely used in many algorithms for reverse nearest neighbor queries. In the filtering step, DART eliminates all the objects that are away from the query object more than a pre-defined distance, or have an invalid direction angle. In the refinement step, remaining objects are verified whether the query object is actually one of the k nearest neighbors of them. As a major extension of DART, we also present an improved algorithm, called DART+, for DBRkNN queries. From extensive experiments with several datasets, we show that DART outperforms an R-tree-based naive algorithm in both indexing time and query processing time. In addition, our extension algorithm, DART+, also shows significantly better performance than DART.     

Approximating Parametric Curves With Strip Trees Using Affine Arithmetic

We show how to use affine arithmetic to represent a parametric curve with a strip tree. The required bounding rectangles for pieces of the curve are computed by exploiting the linear correlation information given by affine arithmetic. As an application, we show how to compute approximate distance fields for parametric curves. ACM CSS: I.3.3 Computer Graphics—Curve, surface, solid, and object representations, G.1.2 Numerical Analysis—Approximation of surfaces and contours, G.1.0 Numerical Analysis—Interval arithmetic