Real-Time Constructive Solid Geometry - Game Development Tools - page 84

Original
Categorization

Inside Touching

Aligned

Touching
Inversed

Outside

After “not”
Operation

Outside Touching

Inversed

Touching
Aligned

Inside

Tab l e 8.2. Logical “not” operation.

8.2.2 CSG Operations

Table8.1 describesthemostcommonCSGoperationsandtheonesimplementedby
our algorithm. It is helpful to think of CSG operations in terms of Boolean algebra
on sets, specifically sets of points in a 3D volume. By extension, our algorithm
performs these logical operations on sets of categorized geometry. In a similar way,
the CSG tree can be thought of as analogous to a logical expression tree, and similar
transformations can be applied.
The “logical or” operation is a matter of taking the categorization results of
the left and right child and using them both to determine new categorization.
Table8.3 showshowtocombinetheresultsofthecategorizationsoftheleftand
right nodes.
For example, as noted in Table 8.1 , each CSG operation can be expressed as
a combination of the “logical not” (for 0-2 child nodes) and “logical or” opera-
tions. To calculate the “logical not,” or the inverse of the volume of a CSG tree

Result of Categorization of Right Child
Inside

Touching
Aligned

Touching
Inversed

Outside

Inside Inside Inside Inside Inside

Touching
Aligned

Inside Touching

Aligned

Inside Touching

Aligned

Touching
Inversed

Inside Inside Touching

Inversed

Touching
Inversed

Outside Inside Touching

Aligned

Touching
Inversed

Outside

Tab l e 8.3. Logical “or” operation.