Page 49 - Computer Graphics Handout

or not a polygon is simple, the cost of testing is sufficiently high (see Exercise 2.12) that most graphics systems require that the
application program does any necessary testing. We can ask what a graphics system will do if it is given a nonsimple polygon to
display and whether there is a way to define an interior for a nonsimple polygon. We will examine these questions further in Chapter
6.

From the perspective of implementing a practical algorithm to fill the interior of a polygon, simplicity alone is often not enough.
Some APIs guarantee a consistent fill from implementation to implementation only if the polygon is convex. An object is convex if
all points on the line segment between any two points inside the object, or on its boundary, are inside the object. Thus, in Figure
2.11, p1 and p2 are arbitrary
points inside a polygon and the entire line segment connecting them is inside the polygon. Although so far we have been dealing
with only two-dimensional objects, this definition makes reference neither to the type of object nor to the number of dimensions.
Convex objects include triangles, tetrahedra, rectangles, circles, spheres, and parallelepipeds (Figure 2.12). There are various tests
for convexity (see Exercise 2.19). However, like simplicity testing, convexity testing is expensive and usually left to the application
program.
In three dimensions, polygons present a few more difficulties because, unlike all two-dimensional objects, all the vertices that specify
the polygon need not lie in the same plane. One property that most graphics systems exploit, and that is the basis of OpenGL
polygons, is that any three vertices that are not collinear determine both a triangle and the plane in which that triangle lies. Hence,
if we always use triangles, we are safe—we can be sure that these objects will be rendered correctly. Often, we are almost forced
to use triangles because typical rendering algorithms are guaranteed to be correct only if the vertices form a flat convex polygon. In
addition, hardware and software often support a triangle type that is rendered faster than is a polygon with three vertices.

49