Game Development Reference
In-Depth Information
node, it is simply a matter of reversing the categorization of the node's output
polygons.
Table8.2
showshowpolygoncategorizationischangedbythe“logical
not” operation.
The situation described in Section 8.2 is handled in the “logical or” operation
in Table 8.3. If the left and right children have a combination of the “touching
aligned” and “touching inversed” categorization, then we have the situation as
shown in
Figure 8.3(b)
, and we categorize it as being “inside.” On the other hand,
if the touching orientation is the same for both children, then we're dealing with
the situation as shown in
Figure 8.3(a)
, and we categorize it as either aligned or
inversed, depending on the original categorization.
This allows us to implement all CSG operations using a single “logical or” func-
tion that can optionally invert the polygon categorization of its children's polygons.
If a “logical not” operation needs to be performed on the results of the “logical or”
function, we reverse the categorization of the polygons. If the algorithm is imple-
mented by passing a list per category, in which to store the categorized polygons,
the “logical not” operation is simply a matter of reversing the order of the param-
eters of the “logical or” function.
The final categorization method is the one that categorizes and cuts the polygons
with a brush at the leaf level and is described in Section 8.2.3.
We should mention that an important optimization of this algorithm is to use a
bounding volume hierarchy, which can be used to skip entire branches in the CSG
tree when a brush does not intersect with them.
Table8.4
describeshowoperationscanbesimplified,andwithit,performance
can be improved even further when it's known beforehand if a brush intersects with
neither or only one of the child branches.
Operation
Only Intersecting
Left Branch
Only Intersecting
Right Branch
No Intersection
with Branches
Union
Skip current node,
jump to left branch
Skip current node,
jump to right branch
Categorize
everything as
outside
Intersection
Categorize
everything as
outside
Categorize
everything as
outside
Categorize
everything as
outside
Difference
Categorize
everything as
outside
Skip current node,
jump to right branch
Categorize
everything as
outside
Tab l e 8.4.
Operation simplifications.
