Before continuing, the it may help for the reader to be familiar with the concepts presented in Section 14.
Constructive solid geometry (CSG) models are constructed through the
intersection (
), union (
), and subtraction (
) of
solid objects, some of which may be CSG objects themselves[17].
The tree formed by the binary CSG operators and their operands is
known as the CSG tree. Figure 4 shows an example of a
CSG tree and the resulting model.
The representation used in CSG for solid objects varies, but we will consider a solid to be a collection of polygons forming a closed volume. ``Solid'', ``primitive'', and ``object'' are used here to mean the same thing.
CSG objects have traditionally been rendered through the use of ray-casting, which is slow, or through the construction of a boundary representation (B-rep).
B-reps vary in construction, but are generally defined as a set of polygons that form the surface of the result of the CSG tree. One method of generating a B-rep is to take the polygons forming the surface of each primitive and trimming away the polygons (or portions thereof) that don't satisfy the CSG operations. A B-rep models are typically generated once and then manipulated as a static model because they are slow to generate.
Drawing a CSG model using stencil usually means drawing more polygons than a B-rep would contain for the same model. Enabling stencil also may reduce performance. Nonetheless, some portions of a CSG tree may be interactively manipulated using stencil if the remainder of the tree is cached as a B-rep.
The algorithm presented here is from a paper by Tim F. Wiegand describing a GL-independent method for using stencil in a CSG modelling system for fast interactive updates. The technique can also process concave solids, the complexity of which is limited by the number of stencil planes available. A reprint of Wiegand's paper is included in the Appendix.
The algorithm presented here assumes that the CSG tree is in
``normal'' form. A tree is in normal form when all intersection and
subtraction operators have a left subtree which contains no union
operators and a right subtree which is simply a primitive (a set of
polygons representing a single solid object). All union operators are
pushed towards the root, and all intersection and subtraction
operators are pushed towards the leaves. For example,
is in
normal form; Figure 5 illustrates the structure
of that tree and the characteristics of a tree in normal form.
A CSG tree can be converted to normal form by repeatedly applying the following set of production rules to the tree and then its subtrees:
X, Y, and Z here match both primitives or subtrees. Here's the algorithm used to apply the production rules to the CSG tree:
normalize(tree *t)
{
if(isPrimitive(t))
return;
do{
while(matchesRule(t)) /* Using rules given above */
applyFirstMatchingRule(t);
normalize(t->left);
}while( ! (isUnionOperation(t) ||
(isPrimitive(t->right) &&
! isUnionOperation(T->left))));
normalize(t->right);
}
Normalization may increase the size of the tree and add primitives which do not contribute to the final image. The bounding volume of each CSG subtree can be used to prune the tree as it is normalized. Bounding volumes for the tree may be calculated using the following algorithm:
findBounds(tree *t)
{
if(isPrimitive(t))
return;
findBounds(t->left);
findBounds(t->right);
switch(t->operation){
case union:
t->bounds = unionOfBounds(t->left->bounds,
t->right->bounds);
case intersection:
t->bounds = intersectionOfBounds(t->left->bounds,
t->right->bounds);
case subtraction:
t->bounds = t->left->bounds;
}
}
CSG subtrees rooted by the intersection or subtraction operators may be pruned at each step in the normalization process using the following two rules:
The normalized CSG tree is a binary tree, but it's important to think of the tree rather as a ``sum of products'' to understand the stencil CSG procedure.
Consider all the unions as sums. Next, consider all the intersections
and subtractions as products. (Subtraction is equivalent to
intersection with the complement of the term to the right. For
example, 
.) Imagine all the unions flattened
out into a single union with multiple children; that union is the
``sum''. The resulting subtrees of that union are all composed of
subtractions and intersections, the right branch of those operations
is always a single primitive, and the left branch is another operation
or a single primitive. You should read each child subtree of the
imaginary multiple union as a single expression containing all the
intersection and subtraction operations concatenated from the bottom
up. These expressions are the ``products''. For example, you should
think of 
as
meaning 
.
Figure 6 illustrates this process.
At this time redundant terms can be removed from each product. Where
a term subtracts itself (
), the entire product can be deleted.
Where a term intersects itself (
), that intersection
operation can be replaced with the term itself.
All unions can be rendered simply by finding the visible surfaces of
the left and right subtrees and letting the depth test determine the
visible surface. All products can be rendered by drawing the visible
surfaces of each primitive in the product and trimming those surfaces
with the volumes of the other primitives in the product. For example,
to render 
, the visible surfaces of A are trimmed by the
complement of the volume of B, and the visible surfaces of B are
trimmed by the volume of A.
The visible surfaces of a product are the front facing surfaces of the
operands of intersections and the back facing surfaces of the right
operands of subtraction. For example, in 
, the
visible surfaces are the front facing surfaces of A and C, and the
back facing surfaces of B.
Concave solids are processed as sets of front or back facing surfaces.
The ``convexity'' of a solid is defined as the maximum number of pairs
of front and back surfaces that can be drawn from the viewing
direction. Figure 7 shows some examples of the
convexity of objects. The nth front surface of a k-convex
primitive is denoted 
, and the nth back surface is
. Because a solid may vary in convexity when viewed from
different directions, accurately representing the convexity of a
primitive may be difficult and may also involve reevaluating the CSG
tree at each new view. Instead, the algorithm must be given the
maximum possible convexity of a primitive, and draws the nth
visible surface by using a counter in the stencil planes.
The CSG tree must be further reduced to a ``sum of partial products'' by converting each product to a union of products, each consisting of the product of the visible surfaces of the target primitive with the remaining terms in the product.
For example, if A, B, and D are 1-convex and C is 2-convex:
Because the target term in each product has been reduced to a single front or back facing surface, the bounding volumes of that term will be a subset of the bounding volume of the original complete primitive. Once the tree is converted to partial products, the pruning process may be applied again with these subset volumes.
In each resulting child subtree representing a partial product, the leftmost term is called the ``target'' surface, and the remaining terms on the right branches are called ``trimming'' primitives.
The resulting sum of partial products reduces the rendering problem to rendering each partial product correctly before drawing the union of the results. Each partial product is rendered by drawing the target surface of the partial product and then ``classifying'' the pixels generated by that surface with the depth values generated by each of the trimming primitives in the partial product. If pixels drawn by the trimming primitives pass the depth test an even number of times, that pixel in the target primitive is ``out'', and discarded. If the count is odd, the target primitive pixel is ``in''', and kept.
Because the algorithm saves depth buffer contents between each object, we optimize for depth saves and restores by drawing as many of target and trimming primitives for each pass as we can fit in the stencil buffer.
The algorithm uses one stencil bit (
) as a toggle for trimming
primitive depth test passes (parity), n stencil bits for
counting to the nth surface (
), where n is the
smallest number for which 
is larger than the maximum convexity
of a current object, and as many bits are available (
) to
accumulate whether target pixels have to be discarded. Because
will require the GL_INCR operation, it must
be stored contiguously in the least-significant bits of the stencil
buffer. and are used in two separate steps, and
so may share stencil bits.
For example, drawing 2 5-convex primitives would require 1 bit,
3 bits, and 2 bits. Because and
are independent, the total number of stencil bits required would be 5.
Once the tree has been converted to a sum of partial products, the individual products are rendered. Products are grouped together so that as many partial products can be rendered between depth buffer saves and restores as the stencil buffer has capacity.
For each group, writes to the color buffer are disabled, the contents of the depth buffer are saved, and the depth buffer is cleared. Then, every target in the group is classified against its trimming primitives. The depth buffer is then restored, and every target in the group is rendered against the trimming mask. The depth buffer save/restore can be optimized by saving and restoring only the region containing the screen-projected bounding volumes of the target surfaces.
for each group
glReadPixels(...);
classify the group
glStencilMask(0); /* so DrawPixels won't affect Stencil */
glDrawPixels(...);
render the group
Classification consists of drawing each target primitive's depth value and then clearing those depth values where the target primitive is determined to be outside the trimming primitives.
glClearDepth(far);
glClear(GL_DEPTH_BUFFER_BIT);
a = 0;
for each target surface in the group
for each partial product targeting that surface
render the depth values for the surface
for each trimming primitive in that partial product
trim the depth values against that primitive
set Sa to 1 where Sa = 0 and Z < Zfar;
a++;
The depth values for the surface are rendered by drawing the primitive
containing the the target surface with color and stencil writes
disabled. () is used to mask out all but the target
surface. In practice, most CSG primitives are convex, so the algorithm
is optimized for that case.
if(the target surface is front facing)
glCullFace(GL_BACK);
else
glCullFace(GL_FRONT);
if(the surface is 1-convex)
glDepthMask(1);
glColorMask(0, 0, 0, 0);
glStencilMask(0);
draw the primitive containing the target surface
else
glDepthMask(1);
glColorMask(0, 0, 0, 0);
glStencilMask(Scount);
glStencilFunc(GL_EQUAL, index of surface, Scount);
glStencilOp(GL_KEEP, GL_KEEP, GL_INCR);
draw the primitive containing the target surface
glClearStencil(0);
glClear(GL_STENCIL_BUFFER_BIT);
Then each trimming primitive for that target surface is drawn in turn.
Depth testing is enabled and writes to the depth buffer are disabled.
Stencil operations are masked to and the bit in the
stencil is cleared to 0. The stencil function and operation are set
so that is toggled every time the depth test for a fragment
from the trimming primitive succeeds. After drawing the trimming
primitive, if this bit is 0 for uncomplemented primitives (or 1 for
complemented primitives), the target pixel is ``out'', and must be
marked ``discard'', by enabling writes to the depth buffer and storing
the far depth value (
) into the depth buffer everywhere that
the indicates ``discard''.
glDepthMask(0); glColorMask(0, 0, 0, 0); glStencilMask(mask for Sp); glClearStencil(0); glClear(GL_STENCIL_BUFFER_BIT); glStencilFunc(GL_ALWAYS, 0, 0); glStencilOp(GL_KEEP, GL_KEEP, GL_INVERT); draw the trimming primitive glDepthMask(1);
Once all the trimming primitives are rendered, the values in the depth
buffer are for all target pixels classified as ``out''. The
bit for that primitive is set to 1 everywhere that the depth
value for a pixel is not equal to , and 0 otherwise.
Each target primitive in the group is finally rendered into the frame
buffer with depth testing and depth writes enabled, the color buffer
enabled, and the stencil function and operation set to write depth and
color only where the depth test succeeds and is 1. Only the
pixels inside the volumes of all the trimming primitives are drawn.
glDepthMask(1);
glColorMask(1, 1, 1, 1);
a = 0;
for each target primitive in the group
glStencilMask(0);
glStencilFunc(GL_EQUAL, 1, Sa);
glCullFace(GL_BACK);
draw the target primitive
glStencilMask(Sa);
glClearStencil(0);
glClear(GL_STENCIL_BUFFER_BIT);
a++;
There are further techniques described in [50] for adding clipping planes (half-spaces), including more normalization rules and pruning opportunities. This is especially important in the case of the near clipping plane in the viewing frustum.
A demo program showing complex CSG expressions rendered using the stencil buffer is on the website.
Source code for dynamically loadable Inventor objects implementing this technique is available at the Martin Center website at Cambridge, http://www.arct.cam.ac.uk/mc/cadlab/inventor/.