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     

Heuristics for ray tracing using space subdivision

Ray tracing requires testing of many rays to determine intersections with objects. A way of reducing the computation is to organize objects into hierarchical data structures. We examine two heuristics for space subdivisions using bintrees, one based on the intuition that surface area is a good estimate of intersection probability, one based on the fact that the optimal splitting plane lies between the spatial median and the object median planes of a volume. Traversal algorithms using cross links between nodes are presented as generalizations of ropes in octrees. Simulations of the surface area heuristic and the cross link scheme are presented. These results generalize to other hierarchical data structures.     

Solving CSG equations for checking equivalency between two different geometric models

For two given parametric constructive solid geometry (CSG) models, the problem of determining their parameter domains in which the two models are equivalent is addressed. Here, two CSG models are equivalent if they represent the exact same region in R³, although their constituent features and feature attributes may differ. In this paper, an approach for solving the problem in a limited scope is proposed, in which a CSG model is polyhedral, its parametric form is explicit and its feature orientations are fixed. The solution includes the equivalent parameter domain for each model and parameter mapping that associates these two models on their equivalent parameter domains. One application of this research is to identify the equivalent parameter domains of two parametric part models, respectively, in the design option space and in the capability envelope set of a parametric machining process in order to facilitate the interoperation between part design and process planning through the generated parameter mapping between these two different kinds of models.     

An efficient algorithm for ray casting of CSG animation frames

This paper presents a new algorithm to generate ray-cast CSG animation frames. We consider sequences of frames where only the objects can move; in this way, we take advantage of the high screen area coherence of this kind of animation. A new definition of bounding box allows us to reduce the number of pixels to be computed for the frames after the first. We associate a CSG subtree and two new flags, denoting if the box has changed in the current frame and if it will change in the next frame, with each box. We show with three examples the advantages of our technique when compared with an algorithm which entirely renders each frame of an animation. Intersections with CSG objects may be reduced to about one-fifth, while the rendering may be computed up to four times faster for the test sequences. © 1998 John Wiley & Sons, Ltd.     

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.     

Dispersive refraction in ray tracing

Dispersive refraction is the property that gives gemstones their fire, and that makes prisms produce a spectrum from white light. Modeling disperison in a ray tracing environment requires solution of some new problems, but allows production of more exciting images. The mechanism of dispersive refraction is discussed, and its implementation is described. Pictures of a prism and of several diamonds are included. Images generated by this technique are realistic, but are computationally expensive.This work was supported in part by the National Science Foundation (DCR-8341796 and MCS-8121750), the Defense Advanced Research Projects Agency (DAAK11-84-K-0017), and the Office of Naval Research (N00014-82-K-0351). All opinions, findings, conclusions or recommendations expressed in this document are those of the author and do not necessarily reflect the views of the sponsoring agencies     

Analysis of an algorithm for fast ray tracing using uniform space subdivision

Ray tracing is becoming popular as the best method of rendering high quality images from three dimensional models. Unfortunately, the computational cost is high. Recently, a number of authors have reported on ways to speed up this process by means of space subdivision which is used to minimize the number of intersection calculations. We describe such an algorithm together with an analysis of the factors which affect its performance. The critical operation of skipping an empty space subdivision can be done very quickly, using only integer addition and comparison. A theoretical analysis of the algorithm is developed. It shows how the space and time requirements vary with the number of objects in the scene.     

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 solid analysis: a hierarchical, geometry-based meshless analysis procedure for integrated design and analysis

In this paper, we propose an analysis methodology that is procedurally analogous to Constructive Solid Geometry (CSG) integrating design and analysis, and thereby enabling efficient optimal design. The procedure, due to its analogous nature to CSG, is termed Constructive Solid Analysis (CSA). The analysis methodology is partitioned, hierarchical and is based on constructing the boundary value problem for a compound geometry through operations on the field quantities defined on the primitives. Although the CSA procedure will allow any basis for approximating the fields, Non-Uniform Rational B-Splines (NURBS), currently popular in the geometric modeling literature, are used to represent the geometry of the primitives as well as the analysis fields. The use of the same basis to represent geometry and analysis fields enables ‘representational’ integration, and further, the developed methodology may be classified as a partition of unity meshless analysis scheme. A more general null-space solution scheme and a somewhat restrictive range-space solution scheme are outlined to solve the discretized equations resulting from the use of NURBS. Several representative problems from the field of linear elasticity are solved to demonstrate the validity of the procedure and to evaluate its computational cost relative to the finite element method. The optimal orientation of an elliptical hole to applied tractions is determined to demonstrate the power of the proposed methodology for shape optimal design.     

A new interpolation subdivision scheme for triangle/quad mesh

In this paper, we present a new interpolation subdivision scheme for mixed triangle/quad meshes that is C¹ continuous. The new scheme is capable of reproducing the well-known four-point based interpolation subdivision in the quad region but does not reproduce Butterfly subdivision in the triangular part. The new scheme defines rules that produce surfaces both at the regular quad/triangle vertices and isolated, extraordinary points. We demonstrate the visually satisfying of our surfaces through several examples.     

A functional model for constructive solid geometry

A system of constructive solid geometry (CSG) enables an engineering desiger to compose three dimensional (3D) shapes by combining simpler ones. Most existing systems, however, actually represent solid shapes as boundaries of surface patches. At the Kunii Laboratory, University of Tokyo, we have produced an experimental system in which solids are modelled functionally by procedures which describe their properties. These primitive objects are combined with the aid of a new octree structure. Careful study of the data structures in this system reveals some interesting aspects of program efficiency.     

Extending CSG with projections: Towards formally certified geometric modeling

We extend traditional Constructive Solid Geometry (CSG) trees to support the projection operator. Existing algorithms in the literature prove various topological properties of CSG sets. Our extension readily allows these algorithms to work on a greater variety of sets, in particular parametric sets, which are extensively used in CAD/CAM systems. Constructive Solid Geometry allows for algebraic representation which makes it easy for certification tools to apply. A geometric primitive may be defined in terms of a characteristic function, which can be seen as the zero-set of a corresponding system along with inequality constraints. To handle projections, we exploit the Disjunctive Normal Form, since projection distributes over union. To handle intersections, we transform them into disjoint unions. Each point in the projected space is mapped to a contributing primitive in the original space. This way we are able to perform gradient computations on the boundary of the projected set through equivalent gradient computations in the original space. By traversing the final expression tree, we are able to automatically generate a set of equations and inequalities that express either the geometric solid or the conditions to be tested for computing various topological properties, such as homotopy equivalence. We conclude by presenting our prototype implementation and several examples.     

Visualization algorithm for CSG polyhedral solids

An algorithm is presented here to visualize here to visualize CSG solids in wireframe with hidden faces eliminated. The approach taken is to construct the image of the CSG solid directly from the CSG tree. This algorithm takes into account the face coherence property and the depth of the faces to minimize the number of rays fired during the process. It mixes a two-dimensional polygonal clipping and a ray-casting algorithm.     

A subdivision method for computing nearest gcd with certification

A new subdivision method for computing the nearest univariate gcd is described and analyzed. It is based on an exclusion test and an inclusion test. The exclusion test in a cell exploits Taylor expansion of the polynomial at the center of the cell. The inclusion test uses Smale’s α-theorems to certify the existence and unicity of a solution in a cell.Under the condition of simple roots for the distance minimization problem, we analyze the complexity of the algorithm in terms of a condition number, which is the inverse of the distance to the set of degenerate systems.We report on some experimentation on representative examples to illustrate the behavior of the algorithm.     

LSM: A layer subdivision method for deformable object matching

A deformation technique is a method to deform any part of, or an entire object, into a desired shape. Existing deformation methods take a lot of computational cost to represent smoothness correctly due to the constraints caused by differential coefficients of high degree. Thus, it is very difficult to find a general solution. In this paper we propose a LSM (layered subdivision method) that integrates a controlling mechanism, surface deformation, and mesh refinement processing 3D modeling and free-form deformable object matching. The proposed method is considerably more efficient and robust when compared to the existing method of free-form surface, because of the computation of the reference points of deformation edge using geometry of free-form surface. This approach can be applied to automatic inspection of NURBS models and object recognition.     

Efficient parallel spatial subdivision algorithm for object-based parallel ray tracing

Parallel ray tracing of complex scenes on multicomputers requires the distribution of both computation and scene data to the processors. This is carried out during preprocessing and usually consumes too much time and memory. The paper presents an efficient parallel subdivision algorithm that decomposes a given scene into rectangular regions adaptively and maps the resultant regions to the node processors of a multicomputer. The proposed algorithm uses efficient data structures to identify the splitting planes quickly. Furthermore the mapping of the regions and the objects to the node processors is performed while parallel spatial subdivision proceeds. The proposed algorithm is implemented on an Intel iPSC/2 hypercube multicomputer and promising results have been obtained.     

Techniques for reducing Boolean evaluation time in CSG scan-line algorithms

Atherton's scan-line hidden surface algorithm for Boolean combinations of plane-faced primitives is intended for fast image generation of complex models.

An important step in the algorithm is the Boolean evaluation at the required positions on each scan-line. This step, however, can be very time consuming if performed in a straightforward way.

Some techniques are presented here that considerably reduce the time needed for the Boolean evaluation. These include a fast bottom-up evaluation technique and partial backface elimination.     

A new subdivision based approach for piecewise smooth approximation of 3D polygonal curves

This paper presents an algorithm dealing with the data reduction and the approximation of 3D polygonal curves. Our method is able to approximate efficiently a set of straight 3D segments or points with a piecewise smooth subdivision curve, in a near optimal way in terms of control point number. Our algorithm is a generalization for subdivision rules, including sharp vertex processing, of the Active B-Spline Curve developed by Pottmann et al. We have also developed a theoretically demonstrated approach, analysing curvature properties of B-Splines, which computes a near optimal evaluation of the initial number and positions of control points. Moreover, our original Active Footpoint Parameterization method prevents wrong matching problems occurring particularly for self-intersecting curves. Thus, the stability of the algorithm is highly increased. Our method was tested on different sets of curves and gives satisfying results regarding to approximation error, convergence speed and compression rate. This method is in line with a larger 3D CAD object compression scheme by piecewise subdivision surface approximation. The objective is to fit a subdivision surface on a target patch by first fitting its boundary with a subdivision curve whose control polygon will represent the boundary of the surface control polyhedron.     

A 4-point interpolatory subdivision scheme for curve design

A 4-point interpolatory subdivision scheme with a tension parameter is analysed. It is shown that for a certain range of the tension parameter the resulting curve is C¹. The role of the tension parameter is demonstrated by a few examples. The application to surfaces and some further potential generalizations are discussed.