Page 52 - Computer Graphics Handout

2.4.4 Triangulation
We have been using the terms polygon and triangle somewhat interchangeably. If we are interested in objects with interiors, general
polygons are problematic. A set of vertices may not all lie in the same plane or specify a polygon that is neither simple nor convex.
Such problems do not arise with triangles. As long as the three vertices of a triangle are not collinear, its interior is well defined and
the triangle is simple, flat, and convex. Consequently, triangles are easy to render, and for these reasons triangles are the only fillable
geometric entity that OpenGL recognizes. In practice, we need to deal with more general polygons. The usual strategy is to start
with a list of vertices and generate a set of triangles consistent with the polygon defined by the list, a process known as triangulation.
Figure 2.16 shows a convex polygon and two different triangulations. Although every set of vertices can be triangulated, not all
triangulations are equivalent. Consider the quadrilateral in Figure 2.17. If we triangulate it as in Figure 2.17(b), we create two long
thin triangles rather than two triangles closer to being equilateral as in Figure 2.17(c). As we shall see when we discuss lighting in
Chapter 5, long thin triangles can lead to visual artifacts when rendered. There are some simple algorithms that work for planar
convex polygons. We can start with the first three vertices and form a triangle. We can then remove the second vertex from the list
of vertices and repeat the process until we have only three vertices left, which form the final triangle. This process is illustrated in
Figure 2.18, but it does not guarantee a good set of triangles nor can it handle concave polygons. In Chapter 6, we will discuss the

triangulation of simple but nonconvex polygons as part of rasterization. This technique will allows us to render more general
polygons than triangles.
We will delay a discussion of more general triangulation algorithms until we discuss curves and surfaces in Chapter 10. One reason
for this delay is that there are a number of related processes that arise when we consider modeling surfaces. For example, laser-
scanning technology allows us to gather millions of unstructured threedimensional vertices. We then have to form a surface from
these vertices, usually in the form of a mesh of triangles. The Delaunay triangulation algorithm finds a best triangulation in the
sense that if we consider the circle determined by any triangle, no other vertex lies in this circle. Triangulation is a special case of
the more general problem of tessellation, which divides a polygon into a polygonal mesh, not all of which need be triangles. General
tessellation algorithms are complex, especially when the initial polygon may contain holes.

52