A Characterization of Ten Hidden-Surface Algorithms

This paper discusses the h~dden-surface problem from the point of view of sorting. The various surfaces of an object to be shown in hidden-surface or h~dden-line form must be sorted to find out which ones are visible at various places on the screen. Surfaces may be sorted by lateral position in the picture (XY), by depth (Z), or by other criteria. The paper shows that the order of sort ing and the types of sort ing used form differences among the existing hidden-surface algorithms To reduce the work of sorting, each algorithm capltahzes on some coherence property of the objects represented. Scan-hne coherence, the fact that one TV scan line of output is likely to be nearly the same as the previous TV scan hne, is one commonly used kind of coherence. Frame coherence, the fact that the entire pmture does not change very much between successive frames of a motion pzcture can be very helpful ff ~t is applicable. By systematical ly looking for addltmnal kinds of coherence and untrmd sorting orders and sorting types, the paper is able to suggest wo promtsing new approaches to the hidden-surface problem. The first, a combination of three existing algomthms, ~s promising because ~t would capitalize on both frame and scan-hne coherence The second new approach would sort in the order Y, Z, X,... the only sorting order for which an existing algomthm could not be found Key words a~d phrases hldden-hne l imination, hidden-surface el imination, sorting, coherence, computer graphics, raster-scan, perspective transformation, analysis of algomthms CR Categories: 8 2, 5 31.