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 Rendering of CSG Models

We describe a CSG rendering algorithm that requires no evaluation of the CSG tree beyond normalization and pruning. It renders directly from the normalized CSG tree and primitives described (to the graphics system) by their facetted boundaries. It behaves correctly in the presence of user defined, “near” and “far” clipping planes. It has been implemented on standard graphics workstations using Iris GL¹ and Open GL² graphics libraries. Modestly sized models can be evaluated and rendered at interactive (less than a second per frame) speeds. We have combined the algorithm with an existing B-rep based modeller to provide interactive rendering of incremental updates to large models.     

Ordered Boolean List (OBL): reducing the footprint for evaluating Boolean expressions

An Expanded Boolean Expression (EBE) does not contain any XOR or EQUAL operators. The occurrence of each variable is a different literal. We provide a linear time algorithm that converts an EBE of n literals into a logically equivalent Ordered Boolean List (OBL) and show how to use the OBL to evaluate the EBE in n steps and O(log log n) space, if the values of the literals are each read once in the order prescribed by the OBL. (An evaluation workspace of 5 bits suffices for all EBEs of up to six billion literals.) The primary application is the SIMD architecture, where the same EBE is evaluated in parallel for different input vectors when rendering solid models on the GPU directly from their Constructive Solid Geometry (CSG) representation. We compare OBL to the Reduced Ordered Binary Decision Diagram (ROBDD) and suggest possible applications of OBL to logic verification and to circuit design.     

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

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.     

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.     

Efficient slicing procedure based on adaptive layer depth normal image

In layered modeling for rapid prototyping of products, compromising slicing accuracy and time is a critical issue. Based on adaptive Layer Depth Normal Image (LDNI), this paper proposes an efficient algorithm to achieve this compromise for complex Constructive Solid Geometry (CSG) models. First, each primitive at the tree leaf is converted into an adaptive LDNI solid whose Boolean operation can be performed efficiently. Then, a layered model is constructed directly from the Booleaned LDNI solid since it is actually a set of a layered and ordered point cloud. In addition to speed, efficient use of memory is also taken into account in design of the LDNI-based slicing algorithm. The capability and efficiency of this slicing algorithm are demonstrated by examples.     

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 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.     

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.     

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.     

Visualization and Computer Graphics on Isotropically Emissive Volumetric Displays

The availability of commodity volumetric displays provides ordinary users with a new means of visualizing 3D data. Many of these displays are in the class of isotropically emissive light devices, which are designed to directly illuminate voxels in a 3D frame buffer, producing x-ray-like visualizations. While this technology can offer intuitive insight into a 3D object, the visualizations are perceptually different from what a computer graphics or visualization system would render on a 2D screen. This paper formalizes rendering on isotropically emissive displays and introduces a novel technique that emulates traditional rendering effects on isotropically emissive volumetric displays, delivering results that are much closer to what is traditionally rendered on regular 2D screens. Such a technique can significantly broaden the capability and usage of isotropically emissive volumetric displays. Our method takes a 3D data set or object as the input, creates an intermediate light field, and outputs a special 3D volume data set called a lumi-volume. This lumi-volume encodes approximated rendering effects in a form suitable for display with accumulative integrals along unobtrusive rays. When a lumi-volume is fed directly into an isotropically emissive volumetric display, it creates a 3D visualization with surface shading effects that are familiar to the users. The key to this technique is an algorithm for creating a 3D lumi-volume from a 4D light field. In this paper, we discuss a number of technical issues, including transparency effects due to the dimension reduction and sampling rates for light fields and lumi-volumes. We show the effectiveness and usability of this technique with a selection of experimental results captured from an isotropically emissive volumetric display, and we demonstrate its potential capability and scalability with computer-simulated high-resolution results.     

Screen-Area Coherence for Interactive Scanline Display Algorithms

This article proposes and demonstrates a technique enabling polygon-based scanline hidden-surface algorithms to be used in applications that require a moderate degree of user interaction. Interactive speeds have been achieved through the use of screen-area coherence,a derivative of frame-to-frame coherence and object coherence. This coherence takes advantage of the face that most of the area of the screen does not change from one frame to the next in applications that have constant viewing positions for a number of frames and in which a majority of the image remains the same. One such application, the user interface of constructive solid geometry (CSG) based modelers, allows a user to modify a model by adding, deleting, repositioning, and performing volumetric Boolean operations on solid geometric primitives. Other possible applications include robot simulation, NC verification, facility layout, surface modeling, and some types of animation. In this article, screen-area coherence is used as the rationale for recalculating only those portions of an image that correspond to a geometric change. More specifically, this article describes a scanline hidden-surface removal procedure that uses screen-area coherence to achieve interactive speeds. A display algorithm using screen-area coherence within a CSG-based scanline hidden-surface algorithm was implemented and tested. Screen-area coherence reduced the average frame update time to about one quarter of the original time for three test sequences of CSG modeling operations.     

Mobility culling: an efficient rendering algorithm using temporal coherence

Interactive display of complex scenes is a challenging problem in computer graphics. Such current approaches as z‐buffer, level of detail and visibility culling have not fully used the temporal coherence between consecutive frames. When the viewing condition is fixed, the color and depth values of static polygons can be obtained from the result of the previous frame and only the remaining dynamic polygons require rendering. We present a method that enhances the speed of the conventional z‐buffer algorithm by exploiting the above temporal coherence. This algorithm is simple to combine with existing graphics hardware that supports the conventional z‐buffer algorithm. It can manipulate any scene suitable for the z‐buffer algorithm without preprocessing or human intervention. The rendering time is proportional to the number of dynamic polygons in each frame. Experimental results show that our method is faster than the conventional z‐buffer algorithm and the performance enhancement becomes higher as the fraction of static polygons increases. Copyright © 2001 John Wiley & Sons, Ltd.     

Construction and optimization of CSG representations

Boundary representations (B-reps) and constructive solid geometry (CSG) are widely used representation schemes for solids. While the problem of computing a B-rep from a CSG representation is relatively well understood, the inverse problem of B-rep to CSG conversion has not been addressed in general. The ability to perform B-rep to CSG conversion has important implications for the architecture of solid modelling systems and, in addition, is of considerable theoretical interest.

The paper presents a general approach to B-rep to CSG conversion based on a partition of Euclidean space by surfaces induced from a B-rep, and on the well known fact that closed regular sets and regularized set operations form a Boolean algebra. It is shown that the conversion problem is well defined, and that the solution results in a CSG representation that is unique for a fixed set of halfspaces that serve as a ‘basis’ for the representation. The ‘basis’ set contains halfspaces induced from a B-rep plus additional non-unique separating halfspaces.

An important characteristic of B-rep to CSG conversion is the size of a resulting CSG representation. We consider minimization of CSG representations in some detail and suggest new minimization techniques.

While many important geometric and combinatorial issues remain open, a companion paper shows that the proposed approach to B-rep to CSG conversion and minimization is effective in E², In E³, an experimental system currently converts natural-quadric B-reps in PARASOLID to efficient CSG representations in PADL-2.     

Direct rendering of Boolean combinations of self-trimmed surfaces

We explore different semantics for the solid defined by a self-crossing surface (immersed sub-manifold). Specifically, we introduce rules for the interior/exterior classification of the connected components of the complement of a self-crossing surface produced through a continuous deformation process of an initial embedded manifold. We propose efficient GPU algorithms for rendering the boundary of the regularized union of the interior components, which is a subset of the initial surface and is called the trimmed boundary or simply the trim. This classification and rendering process is accomplished in real time through a rasterization process without computing any self-intersection curve, and hence is suited to support animations of self-crossing surfaces. The solid bounded by the trim can be combined with other solids and with half-spaces using Boolean operations and hence may be capped (trimmed by a half-space) or used as a primitive in direct CSG rendering. Being able to render the trim in real time makes it possible to adapt the tessellation of the trim in real time by using view-dependent levels-of-detail or adaptive subdivision.