A Solution to the Hidden-Line Problem for Computer-Drawn Polyhedra

The "hidden-line problem" for computer-drawn polyhedra is the problem of determining which edges, or parts of edges, of a polyhedra are visible from a given vantage point. This is an important problem in computer graphics, and its fast solution is especially critical for on-line CRT display applications. The method presented here for solving this problem is believed to be faster than previously known methods. An edge classification scheme is described that eliminates at once most of the totally invisible edges. The remaining, potentially visible edges are then tested in paths, which eventually cover the whole polyhedra. These paths are synthesized in such a way as to minimize the number of calculations. Both the case of a cluster of polyhedra and the illumination problem in which a polyhedron is illuminated from a point source of light are treated as applications of the general algorithm. Several illustrative examples are included.