Graphics Reference
In-Depth Information
In this text, when two or more faces are said to be co-planar it is assumed that the
faces are mergeable under these criteria.
Because the result of preprocessing is likely a triangle or quad mesh, one alternative
is to merge two or more co-planar faces as long as the resulting face is a triangle or
a quad. This straightforward approach is simple to implement. However, for it to
produce a near-optimal result large clusters of faces would have to be considered for
simultaneous merging. For example, for the spiral-like mesh given in Figure 12.12 no
combination of faces other than all nine faces together form a convex face. Thus, a
combinatorial number of face combinations would have to be tested for merging in
the worst case, which is impractical.
A more involved method, but which promises much better results, is to merge
all
co-planar neighboring faces into a single (concave) polygon in a first pass. In a sub-
sequent second pass, these polygons are then triangulated or otherwise decomposed
into the type of convex pieces desired for the end result.
If adjacency information is available, it is straightforward to merge neighboring
co-planar faces simply by visiting neighboring faces through the provided adjacency
links. For example, given an edge-face table the merging process is linear in the
number of edges, proceeding by looping over the edges and merging the faces con-
nected to the edge if co-planar. If no adjacency information is available, instead of
first computing adjacency information and then proceeding as described previously
an alternative option is to find nearly co-planar faces through a scheme similar to
environment cube mapping [Akenine-Möller02].
Figure 12.12
If two (or more) faces are only considered for merging when the resulting face
is convex, no merging can be done for this spiral-like mesh. If concave faces are allowed
during merging, this mesh can be merged into a single (quadrilateral) face.
