Game Development Reference
In-Depth Information
Figure 8.8.
Splitting a polygon with the planes of a brush.
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
shownin
Figure8.9
aT-junctionoccursonanedgeifonlyonefaceissplitbutthe
coincident edge of the adjacent face is not. This forms a tiny crack in the mesh that
can cause flickering of pixels of the background to show through when rendering
due to discrepancies in rasterization of the two faces that use different vertices.
To help avoid T-junctions and ensure a robust mesh representation, polygon
edges are represented using the half-edge data structure as described in [Weiler 85].
Asshownin
Figure8.10
,
withthehalf-edgedatastructure,alledgesaresplitinto
two half edges and contain only a single vertex, a pointer to the next half edge on
the same polygon and a “twin” pointer that leads to the half edge on the other
side of the edge. Using this sparse data structure, it's possible to quickly traverse
a mesh in a variety of ways. This is useful, for example, to find both polygons on
both sides of an edge or to find all the polygons or edges that are connected to a
single vertex.
A T-junction can also occur when separate meshes representing different volu-
metric primitives are placed adjacent to each other but with coincident edges that
have different endpoints. Section 8.3.1 describes a global T-junction detection and
elimination algorithm that can be applied as a post-processing step on the global
CSG scene.
Figure 8.9.
A crack in a mesh caused by a T-junction.
