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
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.
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.
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.
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.
Figure 11 Calculation of intersection points with a bounding box.
Figure 12 Small spans.
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.
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.
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.
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.