Efficient Display of Quadric CSG Models

Reinier van Kleij

Faculty of Technical Mathematics and Informatics
Delft University of Technology
Julianalaan 132
2628 BL Delft
The Netherlands
email: rein@duticg.tudelft.nl

Abstract

CSG (Constructive Solid Geometry) is a method for defining complex solid objects as a combination of simple primitives. This paper gives a short overview of modelling with CSG and of methods for generating shaded images of CSG models. An efficient scanline algorithm for CSG models with quadric primitives is presented, which gives reasonable display times on a general-purpose workstation. Some remarks on the performance on future workstations are made.

Keywords: Display algorithms, constructive solid geometry, quadrics, scanline algorithms

1. Introduction

Constructive solid geometry (CSG) is a powerful technique for modelling complex mechanical parts (Requicha 1980). With CSG, simple parametrized objects, called primitives, are positioned in space and dimensioned using the geometric transformations translation, rotation, scaling and skewing. By applying the binary, volumetric set operations union ([[union]]), intersection ([[intersection]]) and difference (-), the primitives are combined into more complex, composite objects onto which the set operations can be applied again. The set operations are stored in the nodes of the so-called CSG tree; references to the primitives are stored in the leafs; the root node represents the composite object (see Figure 1).

Hakala et al. (1983) state that 90 - 95% of the mechanical parts can be described as a combination of blocks, cylinders, cones and spheres, the so-called natural quadrics. These surfaces result from all kinds of machining operations: milling, turning, cutting etc., which can be represented by the difference operator. So a CSG modelling system with natural quadrics as primitives supports the geometric modelling of mechanical parts; furthermore such a system can be used in other applications such as flight simulation and molecular modelling (stick and ball models). Pictures 14d, 14e and 14f give examples of CSG models with natural quadrics.

CSG is also well suited for interactive modelling by direct manipulation. For example, in the GeoNode-system developed at the Delft University of Technology, the primitives can be manipulated directly in a wire-frame drawing by picking and dragging using a mouse. The CSG-expression can be created interactively by clicking in the solid parts of the composite object (the constituents) in orthogonal wire-frame projections (van Emmerik 1990).

Figure 1 A simple object and its CSG tree.

During the design of an object, visual feedback is important. To visualize CSG models, there are basically two approaches. In the first approach the CSG model is converted into a boundary-representation (Brep), and then a standard visible-surface algorithm is applied. This approach has a serious drawback: conversion from a CSG model into a Brep is a time-consuming and numerically sensitive process, even for polygonal primitives. Moreover, this conversion must be done before display each time the model is changed, which happens frequently during design. The second approach is to take the CSG model as input for a direct display algorithm, which during display determines by traversing the CSG tree whether a face of a primitive is on the boundary of the composite object; this process is called classification of faces (Bronsvoort 1988). Well-known direct display algorithms are the CSG ray-cast algorithm (Roth 1982), the CSG scanline algorithm (Atherton 1983) and the CSG depth-buffer algorithm (Rossignac and Requicha 1986). Although the CSG ray-cast algorithm gives good picture quality, it is computational expensive. The CSG depth-buffer algorithm is only feasible using special-purpose hardware.

The CSG scanline algorithm described by Atherton (1983), on the other hand, gives reasonable display times on a general-purpose workstation. The drawback here is the use of polygonal approximations of the primitives, and although the faces can be made to look smooth by Gouraud or Phong shading, the silhouette and the intersection curves still look jagged. This can be avoided by using many polygons for approximation, but this leads to a large number of spans and abundant memory usage.

It is therefore worthwhile to look for CSG scanline display techniques using quadrics directly. In the last decade, several papers have been written on scanline display of CSG models with quadrics. Chung (1984) describes an image space CSG ray-cast algorithm for quadrics that uses silhouette curves, and span and scanline coherence to gain efficiency. The method described by Pueyo and Mendoza (1987) performs a classification of all intersection curves of the scanplane and the primitives, i.e. the scanplane sections, before determining visibility with a standard depth-buffer algorithm.Our goal was to develop an algorithm for general-purpose hardware to efficiently display CSG models composed of quadrics. The developed algorithm is based on the CSG scanline algorithm for polyhedral objects described by Atherton (1983), and uses the notion of subdividing the scanplane sections into monotonic pieces (Pueyo and Mendoza 1987). The mixture of these two concepts gives a new, efficient algorithm. It differs from the algorithm of Pueyo and Mendoza (1987), in that only the faces up to and including the visible surface of the composite object are classified. In contrast to the algorithm of Chung (1984), the depths of the faces are computed only at the span boundaries, and explicitly calculating c-polygons (Chung 1984) is not necessary. To improve efficiency in displaying complex models even more, an efficient span selection procedure was developed to reduce the number of spans to be processed.

Section 2 briefly describes the CSG scanline algorithm for polyhedral objects and the merits of the scanline approach in general. Section 3 discusses the adaptation of this algorithm for the correct display of CSG models with quadrics, and the efficient span selection procedure. Section 4 gives some measurements on different CSG models. Section 5 concludes this paper with some remarks on the algorithm.

2. The polyhedral CSG scanline algorithm

Atherton (1983) describes an elegant algorithm for displaying polyhedral CSG models, which is based on the standard scanline visible-surface algorithm for polyhedral objects. The algorithm consists of two parts: preprocessing and display. In the preprocessing part, the primitives in the CSG model are transformed to image space (see Figure 2a), and their edges are sorted on minimal Y-value into the edge-buckets. An edge-bucket is a linked list of edges that occur for the first time at the scanline the bucket belongs to (see Figure 2b).

The display part draws the image in scanline order, from the bottom of the screen to the top. A scanline is drawn from left to right. Two important data structures are used in the display part:

* The Active Edge List (AEL): a list of all edges intersecting the current scanline, sorted on increasing x-value of the edges on the scanline (see Figure 2c). Two adjacent edges determine a span (see Figure 2d)

* The Active Face List (AFL): the list of all faces that might be visible on the current span (see Figure 2e).

The AEL is updated when the next scanline is to be drawn: edges in the AEL not intersecting the next scanline are removed from the list, the intersections of the remaining edges with the next scanline are computed incrementally and the AEL is sorted with a bubble sort; finally edges in the bucket of the next scanline are merged into the AEL. Figure 3 gives a pseudo-code version of the algorithm.

Figure 2 Objects and data structures in the scanline algorithm

perform viewing transformation;

sort all edges on minimal Y-value in edge-bucket;

for each scanline do

begin

update the AEL;

while AEL is not processed do

begin

get edge from the AEL;

remove face(s) left of edge from the AFL;

insert face(s) right of edge into the AFL;

handlespan (X-value of edge, X-value of next edge in AEL);

end;

end;

Figure 3 Basic scanline algorithm.

The handlespan procedure (see Figure 4) determines the visible face as follows: the faces in the AFL are sorted on increasing depth-value at the left side of the span, and, starting from the first face in the AFL, the faces are classified until either a face is classified as being on the composite object, which is then the visible face, or all faces in the AFL have been classified, in which case there is no visible face. So only the faces in front of and including the visible face are classified. The same is done at the right side of the span. When the depth-order of the faces up to and including the visible face is equal on both sides of the span, the span can be drawn with the colour of the visible face. When the depth-order is not the same, there are at least two intersecting faces, and the intersection of the first two different faces is computed. The span is then subdivided into two subspans, which are recursively handled by the handlespan procedure.

procedure handlespan_for_polyhedral_objects ( left, right );

{left: X-value of left span boundary }

{right:X-value of right span boundary}

begin

sort faces at left and determine visible face;

sort faces at right and determine visible face;

if the order of the faces is the same up to and

including visible face at left and right then

if there is a visible face then

colour the span with the colour of the visible face;

else

colour the span with the background colour;

else

begin

determine the intersection point ip in the scanplane of the first pair of different faces;

handlespan_for_polyhedral_objects (left, ip);

handlespan_for_polyhedral_objects (ip, right);

end;

end; {handlespan_for_polyhedral_objects}

Figure 4 The handlespan procedure for polyhedral objects.

The CSG scanline algorithm is efficient by exploiting several kinds of coherence:

* coherence between scanlines: the x-value of edges on a scanline can be computed incrementally on successive scanlines and the AEL can be sorted efficiently with a bubble sort

* coherence between spans: the depth-order of the faces on two successive spans will vary slowly, so the AFL can be sorted efficiently with a bubble sort

* coherence on a span: mostly the same face will be visible at the left and right side of a span, so subdivisions will rarely occur, and the span can be drawn with one call to the handlespan procedure.

Bronsvoort (1986) gives a number of improvements on the CSG classification, which include pruning of the CSG tree, bottom-up classification with a status tree, and the notion that at the right side of the span the faces need only be sorted to detect intersecting faces.

3. A CSG scanline algorithm for quadrics

The previous section discussed the Atherton scanline algorithm, which displays CSG models with polygonal primitives and serves as a basis for the algorithm presented here. In order to display CSG models with quadrics, both the preprocessing part and the display part of this algorithm need to be adjusted. The preprocessing part must be able to transform quadrics to image space. By computing the silhouette edges and sorting them into the edge-buckets, it is avoided that a quadric might be active at the left of its edges or that a quadric is active on a scanline while its edges do not intersect the scanline (see Figure 5a). The silhouette edges are the loci of the points for which the Z-component of the normal is zero and are calculated by intersecting the quadric with the polar plane of the quadric and the eyepoint (Blinn 1984). The quadric is split into a front- and a backface by the silhouette edges (see Figure 5b).

Figure 5 Silhouettes of a quadric.

Another problem is the fact that a quadratic edge bounding a quadric may intersect a scanline twice, which hinders efficient processing of the AEL (see Figure 6a). The solution for this is to split the edge at the Y-extreme(s) into monotonic pieces, which intersect a scanline at most once (see Figure 6b), and sort them into the edge-buckets. With these monotonic pieces, the exact range of the scanlines of a primitive on the screen is simply found by determining the minimal and maximal Y-coordinate of the vertices of all edges of the primitive.

Figure 6 Splitting quadratic edges.

Even in case of an equal order of faces on the span boundaries, intersection points can still occur (see Figure 7a). In this situation intersection points must be calculated between every pair of faces in the AFL. This can be avoided by sorting the X-silhouettes into the edge-buckets. An X-silhouette is defined as the locus of the points where the X-component of the normal is zero, and is calculated by intersecting the quadric with the polar plane of the quadric and the point at infinity on the X-axis of the image space. The silhouette and the X-silhouette divide the scanplane section of a quadric into monotonic pieces (see Figure 7b).

An important property of monotonic scanplane sections is that two faces can only intersect when there is depth-overlap between these faces (see Figure 8). Consequently, it is not necessary to calculate the depths of all faces for each pixel on the span to determine whether there are intersections: the depths of the faces at both sides of the span are computed, and only when depth-overlap of two faces up to and including the visible face occurs (see Figure 8a, b), the two faces are tested for intersection points by the method described below.

Figure 7 X-silhouettes and monotonic scanplane sections.

Note that the intersection of two monotonic, quadratic faces can lead to two intersection points (see Figure 8a), so the handlespan procedure for quadrics (see Figure 9) needs to be able to handle two intersection points on a span.

Figure 8 Depth-overlap may indicate intersection points.

Testing for intersection points

When two faces have equal depth-order at both sides of the span, and depth-overlap on the span, a test for intersection points is required. This is done by splitting the span into two subspans, and again testing whether the two faces have different depth-order on both sides of a subspan (see Figure 10a). If they do, there is an intersection point on the left and right subspan, and the intersections are calculated with the procedure described below. If there is equal depth-order, each subspan is tested for depth-overlap of the faces. If there is depth-overlap on a subspan, it is again subdivided, and the tests are repeated (see Figure 10b, c). This process continues until either there are intersection points in the subspan, or there is no depth-overlap (see Figure 10d), or the subspan becomes smaller than a pixel, in which case there might be two intersection points in one pixel, but these are discarded for efficiency reasons.

procedure handlespan_for_quadric_objects ( left, right );

{left: X-value of left span boundary }

{right:X-value of right span boundary }

{equal:Boolean indicating whether order of faces is }

{ equal at left and right }

begin

determine the visible face at left;

sort faces at right;

equal := true if the order of the faces up to and including

the visible face is the same at left and right

false otherwise;

if equal and the AFL contains quadric faces then

begin

test each face up to and including the visible face

against all faces that have depth-overlap with it

for intersection points;

equal := false if there are intersection points;

end;

if equal then

if there is a visible face then

colour the span with the colour of the visible face;

else

colour the span with the background colour;

else

begin

{there are intersections}

calculate intersection point(s) of the two intersecting faces in the scanplane;

case number of intersection points of

1 :

handlespan_for_quadric_objects (left, ip);

handlespan_for_quadric_objects (ip, right);

2 :

{two intersection points, ip1 and ip2, ip1 < ip2 }

handlespan_for_quadric_objects (left, ip1);

handlespan_for_quadric_objects (ip1, ip2);

handlespan_for_quadric_objects (ip2, right);

end;

end;{handlespan_for_quadric_objects}

Figure 9 The handlespan procedure for quadric objects.

Figure 10 Testing for intersection points.

Intersection point calculation

The intersection point of two faces with different depth-order on both sides of the span is calculated as follows. First the smallest box in which the intersection must lie is computed; this box is the intersection of the two bounding boxes of the faces on the span or subspan resulted from the intersection test done before. The central point of this box is the initial point for a Newton-Raphson iteration of the system of the two quadratic equations representing the intersecting faces (see Figure 11a). In most cases the iteration will converge to the intersection point in the box within a few steps, but sometimes it diverges or it converges to an intersection point outside the box. In that case a new box is determined by considering the depth-order and the depth-values of the two faces at the left side, in the middle and at the right side of the span; the span is subdivided and the central point of the new box is computed for a repeated iteration (see Figure11b). This process is repeated until convergence is achieved or the box's width becomes smaller than a threshold value, which occurs rarely.

Figure 11 Calculation of intersection points with a bounding box.

Span selection

The CSG scanline algorithm is an efficient display algorithm through its exploitation of several kinds of coherence (see Section 2). Displaying complex CSG models, i.e. models with 50 or more primitives, may, however, lead to a large number of very small spans. Exploiting span coherence in that case does not contribute much to the efficiency of the algorithm, since most spans are smaller than one pixel. In order to gain more from span coherence with complex models, an efficient procedure for selecting spans has been developed, which reduces the number of spans, and thereby increases their average length. It consists of methods for efficiently selecting the left and right edge determining a span.

Left-edge selection

The left-edge selection procedure used here is based on the observation that when there is more than one span in the area of a pixel, only one span contributes to the colour of the pixel (see Figure 12). Let <ej,ej+1> be the last span processed by handlespan giving pixel [pi,pi+1] a colour. Now it is unnecessary to process span <ej+1,ej+2>, because pixel [pi,pi+1] has its colour already; the next span to be processed is <ej+2,ej+3> for colouring pixel [pi+1,pi+2]. The left-edge selection procedure will skip the edge ej+1 and select ej+2 as the left boundary of the next span. Obviously the left-edge selection procedure cannot be used when doing anti-aliasing.

Figure 12 Small spans.

Right-edge selection

In order to exploit span coherence fully, spans should be as long as possible. When displaying complex models, there are often many spans smaller than possible, even when left-edge selection is used. This inefficiency is caused by the fact that the edge after the selected left edge in the AEL is regarded as the right span boundary, even if this edge does not result in a different visible face (see Figure 13).

Figure 13 The edges between ej and ek do not result in a different visible face.

Observing this fact, a technique was implemented that first determines the visible face at the left span boundary and then selects an edge as the right boundary of a span only when it may change visibility. This is the case, if the edge satisfies one of the following conditions:

* the edge is in front of or on the visible face

* the edge belongs to a face that has depth-overlap with the visible face, and so this face might intersect the visible face.

The right-edge selection procedure exploits invisibility coherence (Crocker 1984) on the span. Let edge ej be selected as the left boundary of the span in Figure 13; the right-edge selection procedure will skip all the edges between ej and ek because these edges are behind the visible face. Note that during selecting the right edge, the AFL is updated at every edge skipped; this complicates the handlespan procedure when intersection points are detected: the AFL may contain faces other then those active on the left subspan and so the AFL needs to be reset to its state at the intersection point by scanning the AEL from the right edge to the left and updating the AFL until an edge left of the intersection point is encountered.

4. Results

The display algorithm is embedded in the CSG solid modelling system Quamo (QUAdric MOdeller) developed at Delft University of Technology (van Kleij 1990). Quamo is written in C and runs on an HP 9000 Series 400 under the HP_UX operating system. For display, a window of 512 x 512 pixels is used. In the algorithm the improvements mentioned by Bronsvoort (1986) were incorporated.

The results are given for the models of three objects in Figure 14: a simple model with 4 primitives (see Figure 14a), an average complex model containing 28 primitives (see Figure 14b), and a complex model containing 65 primitives (see Figure 14c). The display times, ranging from 17 seconds for the simple model to 54 seconds for the complex model, are competitive with the display times of polygon models using 16 polygons for a cylinder or cone surface and 64 polygons for a sphere. Using the exact representation of quadrics the picture quality is better: silhouettes and intersection curves looks smoother and shading is better, while memory usage is about 4 times as low.

The measurements were done with four versions of the algorithm: the 'naive' version without left- and right-edge selection, so every two successive edges in the AEL define a span, in the second version span selection is done only with the left-edge selection procedure, in the third version span selection is done only with right-edge selection, and in the fourth version span selection is a combination of left-edge selection and right-edge selection.

Chart 1 gives the number of processed spans in the different versions. Left-edge selection gives a reduction of the number of spans by up to 29%. Right-edge selection reduces the number of spans by up to 63%. Combining left-edge selection with right-edge selection gives only a few per cents more reduction: the right-edge selection procedure skips almost all the edges that are also skipped with left-edge selection.

Chart 1 Number of processed spans.

Chart 2 gives the execution times of the four versions of the algorithm in seconds. The right-edge selection procedure gives the best reduction in complex cases. The relative reduction in execution time is not equal to the relative reduction in number of spans. Left-edge selection seems to remove only spans on which the visible face is easily computed. In the right-edge selection procedure, unlike the naive version, depth calculations on edges and the visible face are required; also there is some loss of coherence on the span, because after updating the AFL in case of intersection points, the AFL may become more random sorted and the bubble sort will be less efficient.

Chart 2 Display times in seconds.

5. Conclusions

A new and efficient algorithm for direct display of CSG models with quadric primitives that produces pictures of good quality in reasonable time, has been presented. The use of monotonic scanplane sections requires the computation of the depths of the faces only at span boundaries. Only when there is depth overlap on a span, it is necessary to calculate a few more depths of the two overlapping faces to test for intersection points. Our algorithm differs from the algorithm of Pueyo and Mendoza (1987), in that we classify only the faces up to and including the visible surface of the composite object. It is also different from the algorithm of Chung (1984), in that we compute the depths of faces only at span boundaries, and we use intersection points to subdivide spans. A comparison between the algorithm of Chung and the presented algorithm is now being made.

The span selection procedures give reductions in execution times of up to 23%, and may be combined with other techniques for reducing display times, such as invisibility coherence (Crocker 1984). They may also be incorporated in other scanline algorithms such as the CSG scanline algorithm for polyhedral objects or the scanline algorithm for algebraic surfaces (Sederberg and Zundel 1989) to reduce execution times.

Exploiting scanline coherence even more by following Mahl's suggestion (Mahl 1972) to store the intersection points in a list and calculating the intersection point on the next scanline by using the Newton-Raphson method, gave a slightly worse performance: the intersection calculation method with the box is almost as efficient as the Newton-Raphson method, and it does not have the overhead of manipulating the list of intersection points.

The use of exact representations for displaying CSG models with quadrics pays off in time and memory space, because the number of geometric elements that must be transformed to and handled in image space, and the number of spans, are much smaller than for polygon representations. Intersection curves and silhouettes look smoother and the shading is more accurate. Observing the current speed-up rate of general-purpose workstations the algorithm will display fairly complex models within a few seconds in about five years from now.

Currently it is investigated to what extent a parallel display architecture with a scanline algorithm might benefit from using exact representations. Certainly there is less overhead in communication of the geometric data between processors than with polygon representations, which is quite substantial (Sato et al. 1985) and this might be a good approach to achieve real-time performance.

Acknowledgements

I would like to thank Ronald Roussou for putting together lots of code, Wim Bronsvoort for clarifying the text, him, Erik Jansen and Xavier Pueyo for their valuable suggestions during the development of the algorithm and Aadjan van de Helm and Peter Kailuhu for their technical support.

References

Atherton PR (1983) A scan-line hidden surface removal procedure for constructive solid geometry. Computer Graphics 17(3): 73-82

Blinn JF (1984) The algebraic properties of homogeneous second order surfaces. Report Jet Propulsion Laboratory

Bronsvoort WF (1986) Techniques for reducing Boolean evaluation time in CSG scan-line algorithms. Computer-Aided Design 18(10): 533-538

Bronsvoort WF (1988) Boundary evaluation and direct display of CSG models. Computer-Aided Design 20(7): 416-419

Chung WL (1984) A new method of view synthesis for solid modelling. In: Proceedings CAD '84, Brighton, UK, pp 470-480

Crocker GA (1984) Invisibility coherence for faster scan-line hidden surface algorithms. Computer Graphics 18(3): 95-102

Emmerik MJGM van (1990) Interactive design of parametrized 3D models by direct manipulation. PhD Thesis. Delft University Press.

Hakala DG, Hillyard RC, Nourse BE and Malraison PJ (1983) Natural quadrics in mechanical design. In: Proceedings Autofact West, pp 222 - 238

Kleij R van (1990) Implementation of a solid modelling system with quadratic surfaces. Report 90-41, Faculty of Technical Mathematics and Informatics, Delft University of Technology

Mahl R (1972) Visible surface algorithms for quadric patches. IEEE Transactions on Computers C-21(1): 1-4

Pueyo X and Mendoza JC (1987) A new scan line algorithm for the rendering of CSG trees. In: Proceedings Eurographics '87, G. Maréchal (ed), Elsevier Science Publishers, pp 347-361

Requicha AAG (1980) Representations of rigid solids: theory, methods and systems. ACM Computing Surveys 12(4): 437-464

Rossignac JR, Requicha AAG (1986) Depth buffering display techniques for CSG. IEEE Computer Graphics & Applications 6(9): 29-39

Roth SD (1982) Ray casting for modeling solids. Computer Graphics and Image Processing 18(2): 109-144

Sato H, Ihsii M, Sato K, Ikesaka M, Ishihata H, Kakimoto M, Hirota K and Inoue K (1985) Fast image generation of constructive solid geometry using a cellular array processor. Computer Graphics 19(3): 95-102

Sederberg TW, Zundel AK (1989) Scan line display of algebraic surfaces. Computer Graphics 23(3): 147-156

Figure 14 CSG models with quadrics and display resolutions.