Game Development Reference
In-Depth Information
Figure 8.10. The half-edge data structure.
When a plane splits an edge, its twin edge is also automatically split, thus
updating the adjacent polygon and ensuring a well-formed mesh.
After the polygon has been split, one part will be in front of the plane (outside),
and the other part will be at the back side of the plane (inside). By categorizing the
piece of the polygon that is in front of the plane as outside, and continuing to split
the remainder by all the remaining planes, we eventually end up with a polygon
that completely lies inside, or is touching, the brush. If it's touching, the normal
of the plane we're touching needs to be compared to the normal of the polygon to
determine if the polygon is inverse aligned or aligned.
In Listing 8.1, we demonstrate the basic algorithm to cut all the polygons by the
planes of another brush. Keep in mind, however, that in this example, for the sake
of brevity, all polygons are always cut by all planes of the brush even if a polygon
actually lies outside that brush. This causes polygons to be split many more times
than required and should be avoided in production code. Always remember that
the more splits you have, the bigger the floating-point errors become, the more
work has to be done for all subsequent brush intersections, and the more work has
to be done at the final mesh-optimization stage.
One thing to consider is the necessity of performing the entire categorization
process in the local space of the brush whose polygons we're cutting. This can be
done by adding transformation data to all brushes and transforming the planes of
the brushes with which we split our mesh, with the relative transformation between
the mesh and the splitting brush. This gives us the following advantages:
It keeps the calculations as close to the origin as possible, where floating-point
accuracy is highest.
It makes it possible to cache the mesh we create for each brush before it is
cut by other brushes.
It allows the whole mesh of a CSG branch, with all the brushes already
intersected internally, to be cached, allowing us to skip a whole lot of work
when translating or rotating a group of brushes.
 
Search WWH ::




Custom Search