Hidden-line removal

In 3D computer graphics, solid objects are usually modeled by polyhedra. A face of a polyhedron is a planar polygon bounded by straight line segments, called edges. Curved surfaces are usually approximated by a polygon mesh. Computer programs for line drawings of opaque objects must be able to decide which edges or which parts of the edges are hidden by an object itself or by other objects, so that those edges can be clipped during rendering. This problem is known as hidden-line removal.

The first known solution to the hidden-line problem was devised by L. G. Roberts^[1] in 1963. However, it severely restricts the model: it requires that all objects be convex. Ruth A. Weiss of Bell Labs documented her 1964 solution to this problem in a 1965 paper.^[2] In 1966 Ivan E. Sutherland listed 10 unsolved problems in computer graphics.^[3] Problem number seven was "hidden-line removal". In terms of computational complexity, this problem was solved by Frank Devai in 1986.^[4]

Models, e.g. in computer-aided design, can have thousands or millions of edges. Therefore, a computational-complexity approach expressing resource requirements (such as time and memory) as the function of problem sizes is crucial. Time requirements are particularly important in interactive systems.

Problem sizes for hidden-line removal are the total number n of the edges of the model and the total number v of the visible segments of the edges. Visibility can change at the intersection points of the images of the edges. Let k denote the total number of the intersection points of the images of the edges. Both k = Θ(n²) and v = Θ(n²) in the worst case,^[4] but usually v < k.