Graphics Reference
In-Depth Information
Figure 7.20.
Examples of geometric
coherence.
Curved objects satisfy similar types of coherence.
Visible surface determination algorithms need to be evaluated in the context of
the whole rendering algorithm. There is no “best” such algorithm. Differences in
algorithms stem from different requirements: different scenes, different complexity of
output. The choice of an algorithm also depends on the shading algorithm that is to
be used. For example, although the Watkins algorithm is a nice algorithm, one cannot
use it if one wants to use a global reflectance model as described later in Chapters 9
and 10. In general though, image space algorithms seem to be the most popular. In
fact, it is fair to say that Z-buffer algorithms, which are extremely simple and versa-
tile, are the de facto standard in high performance graphics system because the price
of memory is no longer such a problem. Furthermore, as mentioned earlier, because
these systems typically have hardware support for fast display of polygons, all sur-
faces, including curved ones, are treated as collections of polygons. Many of the
mathematical complications in algorithms like Blinn's are thereby avoided. Of course,
having a high-speed system is now more important than ever because of the large
number of polygons with which one has to deal.
The table below summarizes normalized speed results from Table VII in [SuSS74]:
Number of facets in the scene
Algorithm
100
2500
60000
Schumacker
30
179
1215
Newell-Newell-Sancha
1
10
507
Warnock
11
64
307
Z-buffer
54
54
54
Watkins
3
21
457
In the table we have normalized the Newell-Newell-Sancha algorithm to 1. The
numbers are estimates only though and should mainly be used for comparison
purposes. Small differences are inconclusive and only orders of magnitude are
significant.
Depth sorting and scan line algorithms are good if there are only a small number
of surfaces (up to several thousand). Scan line algorithms take advantage of coher-
ence between successive scan lines and of span coherence within a scan line. They
reduce a three-dimensional problem to a two-dimensional one. One danger though is
that very narrow polygons can fall between scan lines. In general, depth sorting is
good if the scene is spread out in depth (relative overlap in z-direction) and scan line
or area-subdividing algorithms are good if surfaces are separated horizontally or
vertically.
