An Intersection-Sensitive Hidden-Surface Algorithm

Abstract

Given a set of pairwise disjoint planar polygonal faces with altogether N edges in the three-dimensional space. Let k be the number of intersection points of the projections of the edges in a projection plane, 0 < k < N(N-1)/2. An algorithm for the elimination of hidden surfaces in O((N+k)log N) time and O(N+k) space is proposed. If k is O(N), which is often the case in practice, the algorithm has O(N log N) expected time, regardless of the probability distribution of the input data. The constants of proportionality are low enough to make this algorithm of practical use. The method is a three-dimensional generalization of a two-dimensional scan-line algorithm, called the NlogN algorithm. A total order hide of faces is introduced. By determining the intersections of the projected edges, regions are designated within which visibility is unvaried. Then each region is visited, maintaining the total order hide, from which visible surfaces and rendering of partially transparent objects can be inferred.