Game Development Reference
In-Depth Information
to create the same mesh. The next optimization phase will attempt to generate a
more optimal triangulation. Ideally, we want triangles that define the same outer
shell, but are as large as possible but fewer in number for ecient rendering on the
GPU. This procedure starts by detecting groups of coplanar polygons that share
the same material properties, determining their boundaries and holes, and then
supplying this information to a robust triangulation library.
The implementation of a triangulation library is beyond the scope of this article.
However, there are several freely available libraries as well as some references if you
want to build your own. [Narkhede 95,Schneider 03] The triangulation library must
be able to support complex polygons with holes as input. Our system should not
produce any self-intersecting polygons however.
The retriangulation phase builds contours of edges that form the boundary of
a group of fragment polygons created by the original CSG algorithm. The group
of fragment polygons must be coplanar and can be grouped based on material and
other user-defined properties. The grouping is done by sorting all the polygon
fragments based on their properties and grouping equivalent polygons that are
adjacent in the sorted list. The resulting contours are tested to see if they are
oriented in the clockwise direction, in which case they are outer boundaries, or
in the counterclockwise direction, in which case they are inner boundaries of a
polygonal hole. The well-formed nature of input CSG fragments ensures that each
inner boundary will be contained within exactly one outer contour. To determine
Figure 8.11.
Detecting contours form a group of convex brush fragments.
