Résumé: This paper discusses the hidden-surface problem from the point of view of sorting. The various surfaces of an object to be shown in hidden-surface or hidden-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 sorting and the types of sorting used form differences among the existing hidden-surface algorithms To reduce the work of sorting, each algorithm capitalizes on some coherence property of the objects represented. "Scan-line 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 picture does not change very much between successive frames of a motion picture can be very helpful if it is applicable. By systematically looking for addltmnal kinds of coherence and untried sorting orders and sorting types, the paper is able to suggest two promtsing new approaches to the hidden-surface problem. The first, a combination of three existing algorithms, is promising because it 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

Langue: Anglais
Thème Informatique

Mots clés:
Cohérence des données
Computer graphics
Sorting
hidden-line elimination
hidden-surface elimination
analysis of algomthms