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

FIGURE B.23—CONT'D

P 1

P 1

P 2

Step 1: Find the highest point Step 2: Find an edge of the convex hull

(0, 1, 0)

N

P 1

P 1

P 2

P 2

P 3

P 3

Step 3: Find an initial triangle Step 4: Construct each triangle of the convex hull

using one or two existing edges from previously
formed convex hull triangles

FIGURE B.24
Computing the convex hull.

must be searched to see if the two other edges of the new triangle already occur in the list. If either of
the new edges does not have a match in the list, then it should be marked as unmatched. Otherwise,
mark the edge as matched . Now, go back through the list of convex hull triangles and look for
another unmatched edge and repeat the procedure to construct a new triangle that shares that edge.
When there are no more unmatched edges in the list of convex hull triangles, the hull has been
constructed.

Step 4 in the previous algorithm does not handle the case in which there are more than three coplanar
vertices. To handle these cases, instead of forming a triangle, form a convex hull polygon for the copla-
nar points. This is done similarly in two and three dimensions. First, collect all of the coplanar points