Game Development Reference
In-Depth Information
Figure 8.7.
Ordering of vertices around a polygon.
one polygon, we can then associate these edges with the planes they lie on and also
the polygons these edges are a part of.
All polygons have a consistent ordering of their vertices, and on each polygon
each vertex has two edges that touch it; one edge is going towards the vertex, and
one edge is leaving the vertex. We can order the edges by iteratively finding the
edge that leaves one vertex and then following it to its next vertex and build the
Cutting and categorizing polygons with a brush.
During the processing of each
node of the CSG tree, the polygons of each brush will be split by all the other
brushes that intersect with them, and the resulting fragments will be categorized
as being inside, outside, or touching the intersecting brush it is compared against
against each of the planes of the other brush. When a polygon is not completely
inside or outside, it needs to be split into two polygon fragments.
A polygon is split by first calculating the signed distance between each polygon
vertex and the splitting plane. When vertices of an edge fall on the opposite sides
of a plane, that edge needs to be split by inserting a new point where the edge
intersects the plane. For convex polygons, we can assume that a plane will split
two edges at most. Some vertices may lie exactly on the plane, in which case we
don't need to split and can use the existing vertex. Each resulting edge is attached
to one of the two polygon fragments resulting from the split. Some good references
for details of edge-splitting algorithms are [Foley 95] and [Schneider 03].
If the edge is split separately for both polygons, you may end up with slightly
different vertex coordinates over the course of many splits on both polygons, due to
floating-point imprecision. It is necessary to avoid this to ensure that the resulting
mesh is well formed, without T-junctions.
As an edge is split by a plane, it is important that the polygons adjacent to
that edge also reflect that split. If the edge is split separately for both polygons,
you may end up with slightly different vertex coordinates over the course of many
