Graphics Reference
In-Depth Information
Algorithm
Category
Comments
Schumacker-Brand-Gilliland-Sharp
(2)
The first list priority algorithm.
Newell-Newell-Sancha
(2), (3)
A depth sort list priority algorithm.
The BSP algorithm
(1), (2)
A list priority algorithm.
Warnock
(2), (3)
An area subdivision image precision algorithm.
Weiler-Atherton
(2), (3)
A more sophisticated area subdivision algorithm.
The Z-buffer algorithm
(1)
The
algorithm used originally on high-end graphics
work stations but now in most graphics systems.
Watkins
(1), (2)
A scan line algorithm that is still worthy of
consideration in certain applications because it is
much
faster than a ray-tracing-type algorithm.
Ray tracing
(1)
The
approach used in conjunction with radiosity
methods if one wants the highest quality realistic
images. It is discussed at length in Chapter 10.
Octree
(1)
A list priority algorithm useful for volume
rendering
The Blinn curved surface algorithm
(2), (3)
The algorithms above, except for the ray-tracing algorithm, will be discussed in Sec-
tions 7.3-7.10. Section 7.2 will describe a preprocessing step called back face removal,
which is easy to carry out and saves the algorithms a lot of needless work, but can
also be used all by itself to provide some rudimentary realism to scenes. When we
discuss the visible surface determination algorithms, the reader needs to be aware
about one assumption that is made because it is convenient. Unless explicitly stated
otherwise, we shall assume the following:
The orthogonal projection assumption:
We assume that the world has been transformed
into a coordinate system where the eye is at infinity, so that the projection to the view plane
is an orthogonal projection (rather than a central projection) and corresponds to simply
dropping the z-coordinate.
Finally, it should be mentioned that there are also
visible line determination
or
hidden line removal
algorithms. These algorithms are used mainly in the context of
wireframe displays. Every visible surface determination algorithm can be modified
into a visible line determination algorithm, but not vice versa. For an example of this
see [PokG89]. The earliest visible line determination algorithm was developed by
Roberts in [Robe63]. It assumed all lines came from edges of convex polyhedra. First,
back edges were removed. (A
back edge
is a common edge of two back faces.) Each
remaining edge was then checked against all the polyhedra that might obscure it.
[Roge98] describes this algorithm in great detail. A more general purpose visible line
determination algorithm was described by Appel in [Appe67]. Appel introduced a
notion of the
quantitative invisibility of a point
, which was the number of front-facing
polygons that obscured the point. A point was visible if and only if its quantitative
invisibility was zero. Visible line determination lost its importance as computers
became more powerful.
