Game Development Reference
In-Depth Information
It has a geometric representation (preferably this should be watertight to
avoid holes in the final geometry). From here on, we will refer to these
volumes as brushes following popular convention used in Id Tech and Unreal
Engines.
Even though CSG is technically a volumetric representation, like many CSG
implementations, this algorithm only computes the outer shell of the volume defined
by the CSG tree and rejects fragment polygons based on their final categorization.
As a result, the algorithm never needs to create any new polygons; it only needs
to split existing geometry and remove all the fragments that are determined to be
inside or outside the final CSG volume. Occasionally, polygons need to be inverted
by reversing the order of their vertices.
The advantage of using convex polytopes as primitive volumes is that all the
splits are done using planes, and the resulting fragments are guaranteed to be convex
as well. The resulting output mesh is suitable for a quick preview and many other
uses. In Section 8.3, we'll discuss some methods to further optimize and improve
the triangulation of the final mesh for production use.
8.2.1 Categorization
To determine the final geometry of the CSG tree, polygons are categorized as being
inside, outside, or touching the final CSG volume. When a polygon cannot be cate-
gorized as being completely inside, outside, or touching, it is split up into individual
fragments that can then be categorized separately. The splitting is performed at
the leaf level of the tree and is described in Section 8.2.3, “Cutting and categorizing
polygons with a brush.”
Polygons that are touching the CSG volume are categorized into two different
sub categories; either aligned with the CSG tree or inverse aligned. Aligned touch-
ing polygons are a part of the final CSG shell with normals facing in the same
direction as the CSG volume. Inversed touching polygons have normals facing in
the opposite direction of the CSG volume. It is important to keep track of these
categories through the intermediate steps, as some operations will invert the origi-
nal polygons. It is also required to properly handle the situations where brush faces
are overlapping as illustrated i
n
Figure 8.3
.
Considertheexampleoftwobrusheswithoverlappingfacesthatarecombined
usingaunionoperation.In
Figure8.3(a
)
,oneofthebrushesisinsidetheother,
andtheiroverlappingpolygonsarefacingthesamedirection.Toavoidduplicate
polygons, it is important to have a globally consistent way to decide which brush's
polygon to keep and which to reject. A simple way to decide which surface to reject
is by comparing the order of the brushes in the tree, keeping the shared area of the
brush that has the highest order in the tree, and removing the shared area of the
otherbrush.However,inthesituationin
Figure8.3(b)
,
bothbrushesareadjacent
but not intersecting. In this case, the overlapping polygons have opposite normals,
