Graphics Reference
In-Depth Information
whereas image precision algorithms are of the form
for each
pixel on the screen
do
begin
Determine the visible object
O
that is pierced
by the ray from the viewer determined by the pixel;
if
there is such an
O
then
display the pixel appropriately
else
display the pixel in the background color;
end
;
Both types of algorithms do all their computations to the same precision in which the
objects were defined. The main difference between them is that the former accurately
compute
all
the visible parts of the world whereas the latter only determine visibility
in a
sampled
number of directions. The complexity of image precision algorithms
depends on the resolution of the screen, whereas the complexity of object precision
algorithms does not (except at the last stage when regions have to be scan converted).
In that sense, with the former one has to worry about aliasing. Pure object precision
algorithms were used only in the early days of graphics, mainly on vector graphics
devices. Given a raster graphics device it is only natural to use the discreteness of the
pixels to help make the algorithm efficient.
Ray tracing captures the essence of image precision algorithms, which can be
further subdivided into whether they deal with areas or points (
area
versus
point
sampling
). The Warnock algorithm is an example of the former. The Z-buffer
algorithm, the Watkins algorithm, and ray tracing are examples of the latter.
List priority algorithms fall somewhere in between object and image precision
algorithms. They differ from pure image precision algorithms in that they precom-
pute, in object space, a visibility ordering
before
scan converting objects to image
space in a simple back-to-front order. Obtaining such an ordering may involve split-
ting objects. The Schumacker, Newell-Newell-Sancha, and BSP tree algorithm are
examples of this type of algorithm.
Like in Chapter 3, each algorithm described in this chapter was selected with
certain considerations in mind, which were:
(1) It is currently an acceptable approach in its intended application.
(2) The algorithm was interesting for historical reasons and easy to describe.
(3) It involved the use of some interesting techniques, even though it itself is no
longer a recommended method.
This led to the following list categorized by (1)-(3) above:
