Background Information and Techniques - Computer Animation: Algorithms and Techniques - page 429

downward-pointing normal vector of the plane. This normal can be computed as N ¼ ( L (0, 1,

0)) L (in right-hand space). Refer to the point found in this step as P 3 . The triangle on the convex

hull is defined by these three points. A consistent ordering of the points should be used so that
they, for example, compute an outward-pointing normal vector ( N ¼

( P 2 P 1 ), N y >
0.0) in right-hand space. Initialize the list of convex hull triangles with this triangle and its outward-
pointing normal vector. Mark each of its three edges as unmatched to indicate that the triangle that
shares the edge has not been found yet.
4. Search the current list of convex hull triangles and find an unmatched edge. Construct the triangle of
the convex hull that shares this edge by the following method. Find the point that, when connected
by a line from a point on the edge, makes the smallest angle with the plane of the triangle while
creating a dihedral angle (interior angle between two faces measured at a shared edge) greater than
90 degrees. The dihedral angle can be computed using the angle between the normals of the two
triangles. When the point has been found, add the triangle defined by this point and the marked edge
to the list of convex hull triangles and the unmarked edge. The rest of the unmarked edges in the list

( P 3 P 1 )

FIGURE B.23
Bounding sphere code.