Geometric Primitives - 3D Math Primer for Graphics and Game Development - page 338

/ / We ' r e concave

r e t u r n f a l s e ;

}

/ / We ' r e convex , w i t h i n t o l e r a n c e

r e t u r n t r u e ;

}
Listing 9.7
3D polygon convexity test using angle sum

Another method for determining convexity is to search for vertices that
are points of concavity. If none are found, then the polygon is convex.
The basic idea is that each vertex should turn in the same direction. Any
vertex that turns in the opposite direction is a point of concavity. We can
determine which way a vertex turns using by the cross product on the edge
vectors. Recall from Section 2.12.2 that in a left-handed coordinate system,
the cross product will point towards you if the vectors form a clockwise turn.
By “towards you,” we assume you are viewing the polygon from the front,
as determined by the polygon normal. If this normal is not available to us
initially, care must be exercised in computing it; because we do not know if
the polygon is convex or not, we cannot simply choose any three vertices to
compute the normal from. The techniques in Section 9.5.3 for computing
the best fit normal from a set of points can be used in this case.
Once we have a normal, we check each vertex of the polygon, computing
a normal at that vertex using the adjacent clockwise edge vectors. We take
the dot product of the polygon normal with the normal computed at that
vertex to determine if they point in opposite directions. If so (the dot
product is negative), then we have located a point of concavity.
In 2D, we can simply act as if the polygon were in 3D at the plane z = 0,
and assume the normal is [0,0,−1]. There are subtle di culties with any
method for determining convexity. Schorn and Fisher [60] discuss the topic
in greater detail.

9.7.3 Triangulation and Fanning
Any polygon can be divided into triangles. Thus, all of the operations and
calculations for triangles can be piecewise applied to polygons. Triangulat-
ing complex, self-intersecting, or even simple concave polygons is no trivial
task [12,52] and is slightly out of the scope of this topic.
Luckily, triangulating simple convex polygons is a trivial matter. One
obvious triangulation technique is to pick one vertex (say, the first one)
and “fan” the polygon around this vertex. Given a polygon with n vertices,
enumerated v 1 ... v n around the polygon, we can easily form n−2 triangles,
each of the form { v 1 , v i−1 , v i } with the index i going from 3 to n, as shown

in Figure 9.30.