i
i
i
i
i
i
i
i
536 12. Polygonal Techniques
Figure 12.3. Ear clipping. A polygon with potential ears at v
2
, v
4
,andv
5
shown. On
the right, the ear at v
4
is removed. The neighboring vertices v
3
and v
5
are reexamined
to see if they now form ears; v
5
does.
Schneider and Eberly [1131], Held [540], O’Rourke [975], and de Berg
et al. [82] each give an overview of a variety of triangulation methods. The
most basic triangulation algorithm is to examine each line segment between
any two given points on a polygon and see if it intersects or overlaps any
edge of the polygon. If it does, the line segment cannot be used to split
the polygon, so examine the next possible pair of points; else split the
polygon into two parts by this segment and triangulate these new polygons
by the same method. This method is extremely inefficient, at O(n
3
). A
more efficient method is ear clipping,whichisO(n
2
)whendoneastwo
processes. First, a pass is made over the polygon to find the ears, that is,
to look at all triangles with vertex indices i, (i +1), (i + 2) (modulo n)and
check if the line segment i, (i + 2) does not intersect any polygon edges. If
so, then triangle (i + 1) forms an ear. See Figure 12.3. Each ear available
is removed from the polygon in turn, and the triangles at vertices i and
(i + 2) are reexamined to see if they are ears or not. Eventually all ears are
removed and the polygon is triangulated. Other, more complex methods
of triangulation are O(n log n) and some are effectively O(n)fortypical
cases. Pseudocode for ear clipping and other, faster triangulation methods
is given by Schneider and Eberly [1131].
Partitioning a polygon into convex regions can be more efficient in terms
of storage and further computation than triangulating it. Convex polygons
Figure 12.4. A polygon with three outlines converted to a single-outline polygon. Join
edges are shown in red. Arrows inside the polygon show the order in which vertices are
visited to make a single loop.
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)
i
i
i
i
i
i
i
i
538 12. Polygonal Techniques
Figure 12.5. The left figure is rendered as a quadrilateral; the middle is two triangles
with upper-right and lower-left corners connected; the right shows what happens when
the other diagonal is used. The middle figure is better visually than the right one.
that have a diffuse color per vertex, choose the diagonal which has the
smaller difference between the colors [5]. An example of this technique is
shown in Figure 12.5. A drawback of such schemes is that they will ruin
the regular nature of the data.
There are cases where triangles cannot properly capture the intent of
the designer. If a texture is applied to a warped quadrilateral, neither
triangulation preserves the intent; that said, neither does interpolation over
the non-triangulated quadrilateral (i.e., interpolating from the left to the
right edge). Figure 12.6 shows the problem. This problem arises because
Figure 12.6. The top left shows the intent of the designer, a distorted quadrilateral with
a square texture map of an “R.” The two images on the right show the two triangulations
and how they differ. The bottom row rotates all of the polygons; the non-triangulated
quadrilateral changes its appearance.
i
i
i
i
i
i
i
i
12.2. Tessellation and Triangulation 539
the image being applied to the surface is to be warped when displayed.
A triangle has only three texture coordinates, so it can establish an affine
transformation, but not a warp. At most, a basic (u, v) texture on a triangle
can be sheared, not warped. Woo et al. [1375] discuss this problem further.
A number of solutions are possible:
• Warp the texture in advance and reapply this new image.
• Tessellate the surface to a finer mesh; this only lessens the problem.
• Use projective texturing to warp the texture on the fly [518]; this has
the undesirable effect of nonuniform spacing of the texture on the
surface.
• Use a bilinear mapping scheme [518]; this is achievable with additional
data per vertex.
While texture distortion sounds like a pathological case, it happens to
some extent any time the texture data applied does not match the pro-
portions of the underlying quadrilateral. One extreme case occurs with a
common primitive: the cone. When a texture is applied to the cone and
the cone is faceted, the triangle vertices at the tip of the cone have different
normals. These vertex normals are not shared by the neighboring triangles,
so shading discontinuities occur [485].
Figure 12.6 also shows why rendering using only triangles is usually
better than interpolation across the original polygon: The quadrilateral’s
rendering is not rotation-invariant. Such shading will shift around when
animated; triangles’ shading and textures at least do not move. Interpola-
tion on a triangle is, in fact, equivalent to interpolating across the surface
using a triangle’s barycentric coordinates (see Section 16.8).
12.2.2 Edge Cracking and T-Vertices
Curved surfaces, discussed in detail in Chapter 13, are usually tessellated
into meshes for rendering. This tessellation is done by stepping along the
spline curves defining the surface and so computing vertex locations and
normals. When we use a simple stepping method, problems can occur
where spline surfaces meet. At the shared edge, the points for both surfaces
need to coincide. Sometimes this may happen, due to the nature of the
model, but often the points generated for one spline curve will not match
those generated by its neighbor. This effect is called edge cracking,and
it can lead to disturbing visual artifacts as the viewer peeks through the
surface. Even if the viewer cannot see through the cracks, the seam is often
visible because of differences in the way the shading is interpolated.
i
i
i
i
i
i
i
i
540 12. Polygonal Techniques
Figure 12.7. The left figure shows cracking where the two surfaces meet. The middle
shows the cracking fixed by matching up edge points. The right shows the corrected
mesh.
b
a
d
d
a
c
c
b
Figure 12.8. In the top row, the underlying mesh of a surface shows a shading discon-
tinuity. Vertex b is a T-vertex, as it belongs to the polygons to the left of it, but is
not a part of the triangle acd. One solution is to add this T-vertex to this triangle and
create triangles abd and bcd (not shown). Long and thin triangles are more likely to
cause other shading problems, so retriangulating is often a better solution, shown in the
bottom row.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.