Surface reconstruction from limited information
Samuel P. Uselton · 1981
One of the least investigated and most tedious and error-prone tasks associated with computer graphics is producing a description of a complex object in a form suitable for manipulation by a graphics system. The information required for this description is generally of two types: (1) three dimensional coordinates of certain points and (2) some organization of these points into sets describing portions of the surface, usually as polygonal faces. This is accomplished in two distinct stages, one for each of the two types of information, or by alternating between the two. Several means of automating the first stage, the collection of coordinates, have been suggested. This discussion centers on the second stage, that of generating polygonal descriptions of the surface. Several existing object description methods are described and their benefits and limitations discussed. A very general algorithm, assuming only knowledge of the point co-ordinates is presented. This algorithm can be modified to use any one of a large class of cost functions in choosing from among the many topologically legitimate surfaces possible. This algorithm is analyzed for its worst case execution speed using standard techniques. A discussion of how to evalute the quality of the approximations generated by this algorithm (or any other for the same purpose) is pursued, resulting in a metric and two algorithms useful in computing it. One algorithm computes the intersection (and symmetric difference) of two polyhedra. The other algorithm computes the volume of an arbitrary polyhedron (or set of polyhedra). Finally, several extensions to the main algorithm are presented. The theme of these extensions is the incorporation of additional knowledge which may be available.