Game Development Reference
In-Depth Information
Figure 8.2.
An example CSG tree in 2D.
8.2 The CSG Algorithm
In most CSG algorithms, the final geometry is specified by a hierarchy of CSG
operations and the volumes that are operated on. Whereas most CSG algorithms
use either BSP trees to build their final geometry or rasterization techniques to
render their final geometry, our algorithm creates the final geometry separately
for each CSG node. This allows the algorithm to maximize parallelization and
minimizes the amount of work required when small incremental changes are made
to the CSG tree.
For simplicity, we've chosen to use a binary tree of CSG nodes in this imple-
mentation,butotherhierarchiesshouldworkaswell.
Figure8.2
showsanexample
of a CSG tree where every leaf is a volume and every node is a CSG operation
combining two volumes. We calculate the final geometry by iteratively categorizing
(see Section 8.2.1) all the polygons contained in the branches of each node. Sec-
tion 8.2.2 describes how each node categorizes each polygon depending on its CSG
operation.
The leaves in our implementation are primitive volumes generated from convex
polytopes, or brushes, defined as the volume bounded by a series of planes (see
Section 8.2.3). Any other geometric representation can also be used as long as it
satisfies the following constraints:
It can be used to determine if a given polygon is inside, outside, or touching
it.
It can be used to split a polygon into separate pieces when it cannot be
categorized as being either inside, outside, or touching it.
