Practical Algorithms for 3D Computer Graphics, 2nd Edition

410 10. Modeling with polygonal datasets

(a)

(b) (c) (d)

Figure 10.37: The triangulation of a set of points. (a) The points, (b) enclosed by a

supertriangle, (c) triangulated and (d) with the supertria n g le removed (enlarged view).

The basic steps are:

1. Add a triangular facet in the same plane in which the points lie. Make it

large enough so that all points are inside it. Thus the initial triangulation

contains just a single triangle. Call th is the supertriangle.

2. With each point P in the list of points to be inserted, do the following:

(a) F in d an existing triangle that encloses P , say it is triangle k.

(b) Form three new triangles by connecting ...