i
i
i
i
i
i
i
i
12.2. Tessellation and Triangulation 537
can easily be represented by fans or strips of triangles, as discussed in
Section 12.4, which makes for faster rendering. Code for a robust convexity
test is given by Schorn and Fisher [1133]. Some concave polygons can
be treated as fans (such polygons are called star-shaped), but detecting
these requires more work [975, 1033]. Schneider and Eberly [1131] give two
convex partitioning methods, a quick and dirty method and an optimal
one.
Polygons are not always made of a single outline. Figure 12.4 shows
a polygon made of three outlines (also called loops or contours). Such
descriptions can always be converted to a single-outline polygon by care-
fully generating join edges (also called keyholed or bridge edges) between
loops. This conversion process can also be reversed in order to retrieve the
separate loops.
Tessellation and triangulation algorithms are an area of computational
geometry that has been well explored and documented [82, 920, 975, 1131].
That said, writing a robust and general tessellator is a difficult undertak-
ing. Various subtle bugs, pathological cases, and precision problems make
foolproof code surprisingly tricky to create.
One way to finesse the triangulation problem is to use the graphics
accelerator itself to directly render a complex polygon. The polygon is
rendered as a triangle fan to the stencil buffer. By doing so, the areas that
actually should be filled are drawn an odd number of times, the concavities
and holes drawn an even number. By using the invert mode for the stencil
buffer, only the filled areas are marked at the end of this first pass. In the
second pass the triangle fan is rendered again, using the stencil buffer to
allow only the filled area to be drawn [969]. The advantage of this method
is that it entirely avoids the problem of developing a robust triangulator.
The problem with it is that each polygon has to be rendered using two
passes and stencil buffer clears every frame.
12.2.1 Shading Problems
Often data will arrive as quadrilateral meshes and must be converted into
triangles for display, both to avoid bowtie problems and to provide proper
input to the renderer. Once in a great while, a quadrilateral will be concave,
in which case there is only one way to triangulate it (without adding new
vertices); otherwise, we may choose either of the two diagonals to split
it. Spending a little time picking the better diagonal can sometimes give
significantly better visual results.
There are a few different ways to determine how to split a quadrilateral.
The basic idea is to minimize differences. For a flat quadrilateral with
no additional data at the vertices, it is often best to choose the shortest
diagonal. For radiosity solutions or prelit quadrilaterals (see Section 15.4.4)