Performance of scanline algorithms for direct display of CSG

Direct display algorithms display a CSG model without first converting the model into a boundary representation. Three such algorithms are described. All three are based on the scanline display algorithm, and are able to handle both polygonal and quadratic faces.The first algorithm is based on Atherton's recursive subdivision scanline algorithm, the second is a combination of a scanline and a ray casting algorithm, and the third is a scanline version of the Trickle algorithm. A multiprocessor system in which these algorithms can be incorporated is also described.The performances of the algorithms are compared. It turns out that the algorithms efficiently display CSG models on general-purpose architectures. A comparison is also made between the performances for polygon-approximated models and exact models for objects bounded by quadratic faces, such as spherical, cylindrical and conical faces, to get an indication of how many polygons can at most be used to approximate quadratic faces and still have better performance.     

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.     

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.     

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.     

Experimental CSG environment for modelling solid

The purpose of this research is to develop an experimental environment for solid modelling which can provide a wide range of graphics primitives and operations toward making the modelling process more flexible. The system can handle different types of representations and combine them with an extended-CSG structure. A new geometric editor to enter and modify the data is also reported. To handle different types of representation, the system has an object-oriented structure and the idea of a common function is introduced to give the interface between them. Ray tracing is used as the rendering method. New techniques for generating images for complex objects are shown with several modelling examples.     

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.     

大规模网格模型间的快速视觉布尔运算

为了解决产品设计阶段中大规模网格模型间的布尔运算无法实现立等可得的速度瓶颈,提出了一种新算法。该算法利用离散化采样获得射线段点云模型,将三角面片间的3D布尔运算转换为射线段间的1D布尔运算,对相交处的交点进行高精度的求解和插值处理,使得布尔运算速度大为提高,从而大大提升复杂拓扑结构的产品设计效率。通过该算法所获得射线段点云模型可获得等同于基于三角网格的渲染效果,该方法可进行工程应用。     

An optimal parallel algorithm for triangulating a set of points in the plane

This paper presents an optimal parallel algorithm for triangulating an arbitrary set ofn points in the plane. The algorithm runs inO(logn) time usingO(n) space andO(_n) processors on a Concurrent-Read, Exclusive-Write Parallel RAM model (CREW PRAM). The parallel lower bound on triangulation is (logn) time so the best possible linear speedup has been achieved. A parallel divide-and-conquer technique of subdividing a problem into subproblems is employed.     

Applications of the 4×4 determinant method and the POLYGON ENGINE

In the first half of the paper, various types of processing pertaining to a polygon, using the 4×4 determinant theories are explained along with a new containment test algorithm of a point in a polygon. In the latter half of the paper, a general-purpose geometric processor, the POLYGON ENGINE, is presented which can deal with various types of interference problems, such as Boolean operations in solid modelling, hidden line and surface eliminations, ray tracing and so on. It is, a successor of the TRIANGLE PROCESSOR and is also based upon the 4×4 determinant theories [4–6]. While the TRIANGLE PROCESSOR processes a triangulated polygon on a triangle-by-triangle basis, the POLYGON ENGINE can treat a polygon without triangulation. The latter is expected to be more functional, more efficient and easier to use.     

Free-form deformation of constructive shell models

Free-form deformation (FFD) is known to be a powerful technique for deforming an object independent of its representation. A point on a solid is deformed by specifying the point relative to a coordinate system defined with a lattice of control points. Adjusting the control points of the lattice deforms the object. The deformed object can be visualized by sampling points on the object surfaces, or by approximating the object with a polyhedral model. However, a conversion of the polyhedral model to the underlining solid representation is required if further solid operations (e.g. Boolean operation) is to be applied. This paper presents a technique for applying FFD on constructive shell models (CSR). A CSR object is constructed by subtracting a set of depression (negative) trunctets from the union of a set of outer (positive) trunctets and a polyhedron core. FFD is applied to the polyhedron core and the trunctets of the model. A trunctet is deformed by applying FFD to a set of selected surface points on the trunctet. The deformed trunctet is obtained by interpolating a surface through the deformed surface points. In the deformation of a trunctet, an outer trunctet may become a depression trunctet (or vice versa). By using the concept of mating trunctet, and an approach for classifying the shape of a trunctet, shape changes of a trunctet in a deformation can be determined. Deformation of a trunctet may also result in an invalid trunctet that bulges out of its enclosing tetrahedron. Besides, the degree of the algebraic surface used determines the size of a trunctet relative to the distance between adjacent lattice control points. A subdivision of a trunctet may have to be performed to maintain the validity of a deformation.     

A linear algorithm for eliminating hidden-lines from a polygonal cylinder

A variety of applications have motivated interest in the hidden-line and hidden-surface problem. This has resulted in a number of fundamentally different solutions. However no algorithm has been shown to be optimal. A common trait among algorithms for hidden-line elimination is a worst case complexity ofO(n ²). It is the interent here to introduce an algorithm that exhibits a linear worst case complexity. The use of a restricted class of input, has been employed to achieve asymptotic improvement in complexity as well as simplifying the problem enough to permit theoretic analysis of the algorithm. The class of input is still general enough to conform to the requirements of a number of applications.     

A PDP constructive algorithm for system modelling

A new constructive algorithm is presented for building neural networks that learn to reproduce output temporal sequences based on one or several input sequences. This algorithm builds a network for the task of system modelling, dealing with continuous variables in the discrete time domain. The constructive scheme makes it user independent. The network's structure consists of an ordinary set and a classification set, so it is a hybrid network like that of Stokbro et al. [6], but with a binary classification. The networks can easily be interpreted, so the learned representation can be transferred to a human engineer, unlike many other network models. This allows for a better understanding of the system structure than just its simulation. This constructive algorithm limits the network complexity automatically, hence preserving extrapolation capabilities. Examples with real data from three totally different sources show good performance and allow for a promising line of research.     

An Algorithm to Evaluate Quantified Boolean Formulae and Its Experimental Evaluation

The high computational complexity of advanced reasoning tasks such as reasoning about knowledge and planning calls for efficient and reliable algorithms for reasoning problems harder than NP. In this paper we propose Evaluate, an algorithm for evaluating quantified Boolean formulae (QBFs). Algorithms for evaluation of QBFs are suitable for experimental analysis of problems that belong to a wide range of complexity classes, a property not easily found in other formalisms. Evaluate is a generalization of the Davis–Putnam procedure for SAT and is guaranteed to work in polynomial space. Before presenting the algorithm, we discuss several abstract properties of QBFs that we singled out to make it more efficient. We also discuss various options that were investigated about heuristics and data structures and report the main results of the experimental analysis. In particular, Evaluate is orders of magnitude more efficient than a nested backtracking procedure that resorts to a Davis–Putnam algorithm for handling the innermost set of quantifiers. Moreover, experiments show that randomly generated QBFs exhibit regular patterns such as phase transition and easy-hard-easy distribution.     

Reconstructing head models from photographs for individualized 3D‐audio processing

Visual fidelity and interactivity are the main goals in Computer Graphics research, but recently also audio is assuming an important role. Binaural rendering can provide extremely pleasing and realistic three‐dimensional sound, but to achieve best results it's necessary either to measure or to estimate individual Head Related Transfer Function (HRTF). This function is strictly related to the peculiar features of ears and face of the listener. Recent sound scattering simulation techniques can calculate HRTF starting from an accurate 3D model of a human head. Hence, the use of binaural rendering on large scale (i.e. video games, entertainment) could depend on the possibility to produce a sufficiently accurate 3D model of a human head, starting from the smallest possible input. In this paper we present a completely automatic system, which produces a 3D model of a head starting from simple input data (five photos and some key‐points indicated by user). The geometry is generated by extracting information from images and accordingly deforming a 3D dummy to reproduce user head features. The system proves to be fast, automatic, robust and reliable: geometric validation and preliminary assessments show that it can be accurate enough for HRTF calculation.     

Implicit Blending Revisited

Blending is both the strength and the weakness of functionally based implicit surfaces (such as F‐reps or soft‐objects). While it gives them the unique ability to smoothly merge into a single, arbitrary shape, it makes implicit modelling hard to control since implicit surfaces blend at a distance, in a way that heavily depends on the slope of the field functions that define them. This paper presents a novel, generic solution to blending of functionally‐based implicit surfaces: the insight is that to be intuitive and easy to control, blends should be located where two objects overlap, while enabling other parts of the objects to come as close to each other as desired without being deformed. Our solution relies on automatically defined blending regions around the intersection curves between two objects. Outside of these volumes, a clean union of the objects is computed thanks to a new operator that guarantees the smoothness of the resulting field function; meanwhile, a smooth blend is generated inside the blending regions. Parameters can automatically be tuned in order to prevent small objects from blurring out when blended into larger ones, and to generate a progressive blend when two animated objects come in contact.     

Hierarchical structure to winged-edge structure: a conversion algorithm

The winged-edge data structure is advantageous for traversing the topological graph of the boundary representation of a solid object. This paper presents an algorithm for converting hierarchical boundary representations into representations in the winged-edge data structure. As a result of the conversion, the adjacency relationships of geometric entities embedded in hierarchical boundary representations,-which may be evaluated through boundary evaluation on solid objects defined via Boolean set-operations, can be easily and efficiently accessed.     

An algorithm for partitioning trees augmented with sibling edges

We investigate a special case of the graph partitioning problem: the partitioning of a sibling graph which is an ordered tree augmented with edges connecting consecutive nodes that share a common parent. We describe the algorithm, XS, and present a proof of its correctness.     

An approximation algorithm for sequential rectangle placement

We present a constant factor, polynomial time approximation algorithm for the problem of scheduling a sequence of rectangles on a matrix. The approximation is on the area covered by the rectangles, and a rectangle is placed on the matrix only if all its preceding rectangles in the sequence were already placed.