Determining the Three-dimensional Convex Hull of a Polyhedron
by A. Appel, P. M. Will
A method is presented for determining the three-dimensional convex hull of a real object that is approximated in computer storage by a polyhedron. Essentially, this technique tests all point pairs of the polyhedron for convex edges of the convex hull and then assembles the edges into the polygonal boundaries of each of the faces of the convex hull. Various techniques for optimizing this process are discussed. A computer program has been written, and typical output shapes are illustrated. Finding the three-dimensional convex hull is approximately the same computer burden as eliminating hidden lines.
PDF