Hidden line removal

Solid objects are usually modeled by polyhedra in a computer representation. 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. This problem is known as hidden line removal.

The first known solution to the hidden-line problem was devised by Roberts in 1963. However, it severely restricts the model: it requires that all objects be convex. In 1966 Ivan E. Sutherland listed 10 unsolved problems in computer graphics. Problem number seven was "Hidden line removal". In terms of computational complexity, this problem was solved by Devai in 1986.

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 but usually v < k.

Hidden-line algorithms published before 1984 divide edges into line segments by the intersection points of their images, and then test each segment for visibility against each face of the model. Assuming a model of a collection of polyhedra with the boundary of each topologically equivalent to a sphere and with faces topologically equivalent to disks, according to Euler's formula, there are Θ(n) faces. Testing Θ(n²) line segments against Θ(n) faces takes Θ(n³) time in the worst case. Appel's algorithm is also unstable, because an error in visibility will be propagated to subsequent segment endpoints.

Ottmann and Widmayer and Ottmann, Widmayer and Wood proposed O((n + k)log²n) time hidden-line algorithms. Then Nurmi improved the running time to O((n + k)log n). These algorithms take Θ(n²log²n), respectively Θ(n²log n) time in the worst case, but if k is less than quadratic, can be faster in practice.

Any hidden-line algorithm has to determine the union of Θ(n) hidden intervals on n edges in the worst case. As Ω(nlog n) is a lower bound for determining the union of n intervals it appears that the best one can hope to achieve is Θ(n²log n) worst-case time and hence Nurmi's algorithm is optimal.

...
Wikipedia