Fast Visibility Maps and 3D Graphics

Hans P. Moravec
Carnegie-Mellon University

March 15, 1981


Introduction

	We are developing a program which will be able to rapidly
generate views of three dimensional scenes described by large numbers
of planar faces. The techniques used can represent the effect of
shadows and produce intervisibility maps as special cases.

	Our method relies on a new hidden surface removal algorithm
@cite(Fuchs80) which generates views in linear time after a somewhat
more expensive view-independent presort which must be done just once
for the scene.

	It generates intermediate images which contain high resolution
views of the scene, but which only indicate which face is visible at
each pixel, not its brightness.  Because these @i(face identity
pictures) consist of large contiguous regions with the same value they
can be represented very efficiently in @i(quad tree) structures which
recusively subdivide along edges, but represent large constant areas
single nodes. The cost of both computing and storing the face identity
quad trees grows as @b(O)(@i(n)log@i(n)) with the picture resolution
(and edge length), allowing very high resolutions.  The cost of a
conventional raster grows quadraticaly with the resolution.

	The face identity pictures are used in a number of ways.  By
replacing each pixel with the results of a light model calculation for
the surface it represents, a realistic image of the scene can be
constructed. If the face identity map is kept to a higher resolution
than the ultimate picture, a very economical spatial frequency
filtering process to overcome aliasing @cite(Crow81) is possible.
Pixels representing uniform regions in the final picture can be
instantly identified in the quad tree, and painted with their correct
coloration with a single calculation. Near edges where the quad tree
subdivides, a pixel can be colored with a weighted sum of the results
of calculations of the color of the different subregions of the pixel
in the inhomogeneous area.  This can eliminate stairstepping and other
undesirable artifacts near edges.

	By computing a face identity map for each lightsource as well
as for the eye, shadows may be shown in the generated pictures.  As
each pixel is painted, the three dimensional point it represents is
projected into the face identity maps of each lightsource.  If a
ligthsource's map indicates the same face at that point as the eye's
map, that point is illuminated from that source, otherwise it is in its
shadow.  Maintaining the lightsource maps to high resolution allows
anti-aliasing of shadow edges.

	A terrain visibility map can be generated with these techniques
simply by placing a simulated light source at the position from which
we wish to determine visibility, and viewing the terrain from a great
simulated height.  The portions of the terrain illuminated by the
lightsource are the visible portions, those in its shadow are not.  The
light model can, of course, be very simple in other respects for this
application.

	The nature of the terrain data permits a further economy, if
terrain is represented as a square grid of elevation values.  In this
case the tree structure needed for the new hidden surface algorithm can
be selected to be perfectly balanced and regular, and known a-prioiri,
and the sort phase of the algorithm can be eliminated.

@heading(The Hidden Surface Algorithm)

	A scene is a collection of faces, each a polygon in three
space. The process begins by sorting the faces in a scene into a
viewpoint-independent priority tree according to a new hidden surface
algorithm given by Fuchs, Kedem and Naylor @cite(Fuchs80).  Once the
scene is structured into such a tree, a list of the faces in occlusion
priority order can be produced by a simple linear time enumeration of
the tree nodes, with the traversal order depending on the eye
position.  When faces are painted onto an image plane in priority
order, with new faces overpainting prior ones, the result is a
correctly hidden surface eliminated picture.  Any face that obscures
another from the current point of view occurs later in the priority
ordering.

	A face is chosen from the face list of the scene.  The plane in
which this face lies divides the rest of three space into two
half-spaces, one in front of and one behind the plane. If the viewing
position is in one of these half-spaces, no face in the other
half-space can obstruct either the dividing face or any face in the
same half-space as the eye. The algorithm divides the remaining faces
into two sublists; those in front of the dividing plane and those
behind. Faces that cross the division are cut in two, and the pieces
are placed in the appropriate sublists. The algorithm is applied
recursively to each sublist, each application causing a new dividing
face to be chosen and further splitting of the list. This goes on until
every list is empty. The resulting structure is stored as a tree, with
each node containing a left and a right pointer, and a representation
of a dividing face.

	To view a scene represented in this way, we choose an eye
position, than paint a picture face by face, with new faces
overpainting previous ones. The order of the face enumeration is given
by a traversal of the scene tree. We begin at the top node of the tree,
which represents the first dividing plane.  We enumerate first the
subtree connected to this node which represents those faces on the
other side of the top dividing plane from the eye, then we produce the
face in the dividing plane, then we enumerate the faces in the subtree
on the same side of the division.  Enumerate in this case means
recursively apply this procedure.  This enumeration encounters each
polygon exactly once, and the cost is linear in the number of faces.
Once the scene tree is generated we can produce a picture from any
point of view in linear time.

	For terrain data, the algorithm is modified and greatly
simplified. The terrain is specified as a square grid of elevation
values. We connect adjacent points in this data by line segments to
produce a triangular tesselation, and we view each small triangle as an
opaque face.  The division planes of the hidden surface algorithm,
however, are not chosen from these triangular faces. Instead we divide
the terrain by cuts made perpendicular to the horizontal and exactly
through rows and columns of elevation values. By cutting through the
vertices we avoid further subdividing the small traingles. The first
cut divides the space into two equal parts in (say) the @b(X)
direction. The second order cuts are perpendicular to the first one, in
the @b(Y) direction, and after them the model is divided into four
equal quadrants. This process continues alternately in @b(X) and @b(Y)
until we have divided down to individual squares, and these are finally
cut along the triangle boundaries. The resulting tree is perfectly
balanced, and need not be explicitly represented. The ordering of the
triangles required to generate the picture from a given point of view
is known a-priori, and does not depend on the actual elevation values.

	We can generate pictures very efficiently using this idea by
splitting a large file of terrain elevations into several smaller
files, each representing an equal subtree of the whole, say one quarter
or one sixteenth.  If these files are small enough to be read into
existing physical memory one at a time, a picture or visibility map can
be generated by simply reading each file exactly once, with the file
order depending on viewing position. The data values within each file
are also examined exactly once, again in an order depending on
viewpoint.  Our map can thus be generated by a single scan through the
data, a potentially very fast process.


@heading(The Face Identity Picture)

	In present day realistic 3D drawing programs, the bulk of
the computation goes into calculation of the light model; what color
and how bright to make each surface point visible in the image plane.
A naive application of a the occlusion priority would do a light
model calculation an average of several times for each pixel, one
for each of surfaces penetrated by a particular ray from the eye,
increasing the cost several times.  Our program overcomes this problem
by first generating a @i(face identity image), which is like a
normal picture except that each pixel contains merely an indication
of which surface is visible there, rather than its visible color.
Once the priority enumeration into a face identity image is complete,
the expensive light model calculation can be done exactly once for
each pixel.

	The face identity picture