CMSC 425 Lecture Notes - Lecture 3: Constructive Solid Geometry, Directed Acyclic Graph, Solid Geometry
15 May 2018
School
Department
Course
Professor
CMSC 425 Dave Mount & Roger Eastman
CMSC 425: Lecture 14
Solid Modeling
Reading: The material on CSG comes from standard texts on solid modeling. The material on
DCELs comes from Chapter 2 in Computational Geometry: Algorithms and Applications by de
Berg, Cheong, van Kreveld, and Overmars. It is also covered in Chapter 2 of Foundations of
Multidimensional Data Structures by Samet.
Solid Object Representations: A major issue in geometric modeling for game assets is how
to represent solid geometric objects. There are two common ways in which to represent
solids. The first is based on representing an object’s boundary surface, called a boundary
representation or B-rep for short. The second is based on representing the object as boolean
operations applied to solid volumes, called CSG for constructive solid geometry. Both have
their advantages and disadvantages.
Volume Based Representations: One of the most popular volume-based representations is con-
structive solid geometry, or CSG for short. It is widely used in manufacturing applications.
One of the most intuitive ways to describe complex objects, especially those arising in man-
ufacturing applications, is as set of boolean operations (that is, set union, intersection, differ-
ence) applied to a basic set of primitive objects. Manufacturing is an important application of
computer graphics, and manufactured parts made by various milling and drilling operations
can be described most naturally in this way. For example, consider the object shown in Fig. 1.
It can be described as a rectangular block, minus the central rectangular notch, plus (union)
two cylindrical holes.
←
−
+
+
Fig. 1: Constructive Solid Geometry.
This idea naturally leads to a tree representation of the object, where the leaves of the tree
are certain primitive object types (rectangular blocks, cylinders, cones, spheres, etc.) and
the internal nodes of the tree are boolean operations, union (X∪Y), intersection (X∩Y),
difference (X−Y), etc. For example, the object above might be described with a tree of the
following sort. (In Fig. 1 we have used “+” for union.)
The primitive objects stored in the leaf nodes are represented in terms of a primitive object
type (block, cylinder, sphere, etc.) and a set of defining parameters (location, orientation,
lengths, radii, etc.) to define the location and shape of the primitive. The nodes of the tree
are also labeled by transformation matrices, indicating the transformation to be applied to
the object prior to applying the operation. By storing both the transformation and its inverse,
as we traverse the tree we can convert coordinates from the world coordinates (at the root of
the tree) to the appropriate local coordinate systems in each of the subtrees.
Lecture 14 1 Spring 2018
CMSC 425 Dave Mount & Roger Eastman
−
+
+
Fig. 2: CSG Tree.
This method is called constructive solid geometry (CSG) and the tree representation is called
a CSG tree. One nice aspect to CSG and this hierarchical representation is that once a
complex part has been designed it can be reused by replicating the tree representing that
object. (Or if we share subtrees we get a representation as a directed acyclic graph or DAG.)
Point membership: CSG trees are examples of unevaluated models. For example, unlike a B-rep
representation in which each individual element of the representation describes a feature that
we know is a part of the object, it is not generally possible to infer the existence of any feature
locally (without looking at the entire tree).
Consider the simple membership question: Given a point P, does Plie inside or outside an
object described by a CSG tree? (For now, let us ignore the degenerate case where it lies on
the boundary.) How would you write an algorithm to solve this problem? The idea is to work
recursively, solving the problem on the subtrees first, and then combining results from the
subtrees to determine the result at the parent. We will write a procedure isMember(Point p,
CSGnode u) where pis the point, and uis pointer to a node in the CSG tree. This procedure
returns True if the object defined by the subtree rooted at ucontains pand False otherwise.
If uis an internal node, let u.left and u.right denote the children of u. The algorithm breaks
down into the following cases.
Membership Test for CSG Tree
bool is Me mb er ( P oin t p , CSG no de u ) {
if (u. isLeaf )
return u.primitiveMemberTest(p);
else if ( u. isUnion )
return is Me mb er (p , u . lef t ) || is Me mb er (p , u . ri ght ) ;
else if ( u. isIntersect )
return is Me mb er (p , u . lef t ) && is Me mb er (p , u . ri ght ) ;
else if (u.isDifference)
return is Me mb er (p , u . lef t ) && ! i sM em ber ( p , u . ri ght ) ;
}
Note that the semantics of operations “||” and “&&” avoid making recursive calls when they
are not needed. For example, in the case of union, if plies in the right subtree, then the left
subtree need not be searched.
Regularized boolean operations (Optional): There is a tricky issue in dealing with boolean
operations. This goes back to a the same tricky issue that arose in polygon filling, what to
Lecture 14 2 Spring 2018
