Dallas, August 18-22 Volume 20, Number 4, 1986

II I

Atmospheric Illumination and Shadows

Nelson L. Max
Lawrence Livermore National Laboratory

(4) Preprocessing (Nishita, Okamura, and Nakamae [4], Bouknight

Abstract and Kelly [5]). Compare a given object to every other, to get a list
The shadow volume algorithm o f Frank Crow was reorganized o f objects which can cast shadows on the given object. Use this
to provide information on the regions of illuminated space in front list to determine the shadows while rendering the objects in scan
o f each visible surface. This information is used to calculate the extra line order.
intensity due to atmospheric scattering, so when the atmosphere is (5) Ray tracing (Whirled [6], Cook, Porter, and Carpenter [7}). At
partly in shadow, columns o f scattered light will be visible. For effi- each sampled surface point, trace a ray towards the light source
ciency in sorting the shadow edges, the image is computed in polar and see if it hits any other objects first.
coordinates. The first three methods can readily provide the necessary in-
formation for atmospheric shadow effects. To use the first method,
Key Words transform the ray from the eye into the light-source view, and as it
Shadows, atmospheric scattering, Watkins hidden surface algorithm, crosses each pixel, compare its depth with that in the Z buffer to see
polar coordinates, shadow polygon. whether it is in shadow. As in the original cast-shadow application,
there are aliasing problems which are aggravated because the sam-
Introduction piing in the two views does not correspond. In general, the Z-buffer
algorithms are not good at anti-aliasing, but have the advantage o f
Sunlight scattering from water or dust in the air causes the atmo- handling diverse object types easily. Every pixel on each transformed
sphere to glow. This glow is particularly visible in beams or columns ray must be considered, which makes the atmospheric shadow com-
of light in an otherwise shadowed environment. The goal o f this putation o f order n 3, if the two views are n by n.
work is to simulate these atmospheric shadow effects. To use the second method, the ray is again transformed to the
To compute the glow from the scattering along a ray from the light-source view and compared in depth to the plane equation o f
eye, one must know which parts o f the ray are illuminated and which each subdivided polygon it crosses in that view, in order to deter-
are in shadow. The hidden-surface/shadow algorithm must be able mine the regions o f illumination. There are now no sampling prob-
to provide the extra information. lems, because the area subdivision is defined with floating point ac-
There are five basic types o f shadow algorithms in current use. curacy instead o f at some image resolution. There is also some
(1) Z buffer (Williams [1]). Compute the light-source and viewpoint coherency from the polygons crossed by the transformed ray, so the
images by depth buffer algorithms. Transform the viewpoint im- computation is not necessarily o f order n 3, but depends instead on
age to the light-source image and compare depths. If the visible the complexity o f the scene. It is a challenging computational geome-
point at a pixel is farther from the light than the corresponding try problem for future research to create a data structure for the area
depth in the light-source image, it is in shadow. subdivision which can be efficiently intersected with the transformed
(2) Area subdivision (Atherton and Weiler [2]). In both the viewpoint rays.
and light-source projections, divide the image into polygonal re- The first two methods both require a finite, flat, light-source
gions in which a single surface is visible. Transform the illumi- view, which may not be possible if the light source is inside the
nated regions in the light source view into object space and paint window visible from the viewpoint.
t h e m as surface detail before the v i e w p o i n t p r o j e c t i o n is I have chosen to implement the third method, modified by reor-
rendered. ganizing the sorting and scan line processing to provide the atmo-
(3) Shadow volumes (Crow [3]). Create shadow polygons, which, to- spheric shadow information more efficiently.
gether with the polygons in the original data base, bound the Although the last two m e t h o d s are capable o f rendering the pen-
volume o f space shadowed by each object. The new shadow umbras from area light sources, the information necessary for atmo-
polygons lie in planes joining the light source to edges in the data spheric shadows is not readily available.
base. Include these shadow polygons in the z sort o f a scan-line
hidden-surface algorithm, and count the parity o f the shadow 1. Polar coordinate scan lines
polygons in front of a visible surface to see if it is in shadow. I wanted to render forest scenes with shadows of many small
leaves. In such scenes, every line segment on a leaf edge generates a
shadow polygon, and there are no savings from considering only
contour edges as suggested by Crow [3]. In the usual orientation,
Permission to copy without fee all or part of this material is granted most o f the leaves are at the top half o f the frame, and their shadow
provided that the copies are not made or distributed for direct polygons extend past the bottom. Therefore, for a horizontal scan
commercial advantage, the ACM copyright notice and the title of the line in the lower half o f a scene containing N leaf edges, all N shadow
publication and its date appear, and notice is given that copying is by polygons must be considered and sorted in x and in z. Normally, a
permission of the Association for Computing Machinery. To copy scan-line algorithm gains efficiency because in a complex scene with
otherwise, or to republish, requires a fee and/or specific permission. many small polygons, most polygon edges can be expected to cross
only a few scan lines. This expected efficiency is negated by the situa-
© 1986 ACM 0-89791-196-2/86/008/0117 $00.75 tion described above.

117
 S I G G R A P H '86

V Segment block data structure

1. Pointer to previous segment block in r sort.

2. Pointer to next segment block in r sort.

3. Polygon number.

4. Pointer to next segment in active segment list.

5. Pointer to next segment on test list.

Z
6. Left edge data for 0, r, z, color, nnrmals, and u, v texture
parameters.

7. Right edge data for 0, r, z, color...etc.

8. Left shadow edge block.

a. shadow sort parameter
b. shadow polygon plane equation
c. pointer to next 0 / m a n y change
d. pointer to next 0 / 1 / m a n y change
e. value (0, 1, or 2) of current shadow multiplicity

9. Right shadow edge block (same data as for left edge).

lO. Bit which is 1 if the polygon is front lit.

11. N a m e of texture map.

Figure 1. Four scan planes, meeting at the line L between the eye E
and the light source S. They intersect the picture plane T in four 12. U and V partial derivative vectors, for bump mapping.
lines, meeting at the point P, which is the projection of the light
source. 13. Plane equation of polygon with sun on positive side.
Table 1.
However, if the s u n is directly o v e r h e a d a n d the picture plane is
vertical, the efficiency can be regained by using vertical scan lines. to the endpoint with positive 8, a n d one from the other e n d p o i n t
T h e scan planes corresponding to these scan lines all m e e t in a verti- until 0 = - ~r. T h e y are thus entered into two different 8 buckets.
cal line through the viewer's eye. Since the s u n direction also lies in A further p r o b l e m exists i r a polygon's projection contains P in
this vertical line, the s h a d o w polygon generated by an edge will cross its interior. If P is inside the polygon, an extra edge s u r r o u n d i n g P
only those scan planes that the edge itself crosses. m u s t be created, going from 0 = x t o O = - ~r, with r = 0. T h e d e p t h
It is possible to generalize this situation by using radial scan a n d shading attributes at P are f o u n d by intersecting the line L o f
lines in polar coordinates. Consider the line L between the eye E a n d Figure 1 with the polygon, a n d are entered at both e n d p o i n t s o f the
the light source S, or in the direction o f a n infinite light source. As new edge.
s h o w n in Figure 1, this line intersects the picture plane T in a point P, T h e e n d p o i n t d e p t h and shading inforination for each edge are
a n d a family o f scan planes meeting in the line L intersect T in a converted to integers a n d packed efficiently into the 64-bit words o f
family o f lines meeting at P. As above, since each scan plane contains the Cray- 1. T h e y are u n p a c k e d w h e n the edges are r e m o v e d f r o m the
both the eye a n d the light source, the only s h a d o w polygons inter- bucket sort a n d placed in the appropriate entries in the data blocks
secting a scan plane c o m e from edges which also intersect that scan for scan line processing o f t h e scan-plane/polygon intersection seg-
plane. This technique greatly simplifies the sorting o f s h a d o w poly- ments. T h e s e segment blocks contain r, depth, a n d s h a d i n g i n f o r m a -
gons a n d should be useful even if a t m o s p h e r i c s h a d o w s are n o t tion for the left a n d right edges of the segment, as s h o w n in Table 1,
required. and various pointers discussed below.
T h e point P is the origin for a system o f polar coordinates on the Since a straight polygon edge projection in the picture plane T
image, with radial scan lines. P m a y lie inside or outside the image intersects the radial polar coordinate lines in a non-linear way, the r,
window. T h e case j u s t discussed, where the sun is exactly overhead, z, a n d shading i n f o r m a t i o n cannot be updated from one scan line to
is a degenerate one where P is at infinity because the line L is parallel the next by the usual incremental addition. Instead, the edge's inter-
to T, and is n o t h a n d l e d in the i m p l e m e n t a t i o n reported here. section with each scan line is c o m p u t e d explicitly, a n d the other data
are interpolated from their values at the edge endpoints. T h e hidden-
2. T h e 0-r (z, shadow) sort surface processing t h e n proceeds as in the Watkins algorithm, with
the r sort taking the place o f the traditional x sort, a n d the scan plane
My algorithm is a polar coordinate modification o f an existing
x - z sort turning into an r - z sort. A n r sorted list o f s e g m e n t
Watkins hidden-surface algorithm available at L L N L (see Watkins
blocks is m a i n t a i n e d from one scan line to the next, using pointers
[8], N e w m a n a n d Sprouli [9], Rogers [10] a n d the a c k n o w l e d g m e n t
(items 1 a n d 2 in Table 1). T h e scan line is rendered as a sequence o f
section below). It sorts first in 0, next in r, a n d t h e n separately a n d spans, along which a single polygon is k n o w n to be visible. Polygons
s i m u l t a n e o u s l y in z a n d a s h a d o w distance parameter. potentially affecting the current span are kept in an active segment
T h e angular coordinate 0 goes counterclockwise a n d edges are list (item 4 in Table 1). For further details on the Watkins algorithm,
sorted into buckets according to the greatest 0 o f their two endpoints. see [8], [9], or [101.
Scan lines are processed by decreasing 0 in analogy to the s t a n d a r d
video scan with decreasing y. If P lies outside the image window, 3. The shadow sort
there is an interval o f possible 0 v a l u e s , b u t i f P lies inside, there is a
whole circle o f values. In this latter case, scan line processing starts at Every polygon edge defines a s h a d o w plane containing it a n d the
O = zc a n d e n d s at 0 = -~r. Edges which cross from positive to light source, a n d a semi-infinite shadow polygon in this plane. (See
negative 0 m u s t be broken into two parts, one extending from 0 = rc Crow [3].) T h e s h a d o w polygons intersect a given scan plane in

118
Dallas, August 18-22 Volume 20, Number 4, 1986
II

J
S
"7
°\
E
T

B A

Figure 2a. A scan plane through the viewpoint E and the light
source S, intersecting the view plane in line T, and three polygons in Figure 2b. Same data as in Figure 2a, rotated so that the light
segments AB, CD, and FG. The light source is in front of the view- source is behind the viewpoint.
point.

shadow edges, a n d the plane equations for the shadow polygons are the position at which it begins.
stored in shadow edge blocks, which are physically part o f the seg- In order for this to work, the scan plane m u s t be swept out in
m e n t blocks, but are also linked into separate lists. (See Table 1, order by rays from the eye m a k i n g increasing angles ~ with the light
items 8 and 9.) source direction, so that before a polygon is rendered, all polygons
In order to c o m p u t e the a t m o s p h e r i c shadows, these shadow which could cast s h a d o w s on it have been considered a n d merged
edges m u s t be sorted in the order o f increasing distance from the eye. into the shadow sort.
Since the shadow edges are all parallel, or all radiate from the light In the case s h o w n in Figure 2a, the light source is in front o f the
source, they never cross except (possibly) at the light source. There- viewer, a n d increasing ~ corresponds to increasing r, so the Watkins
fore they can be sorted in an order which r e m a i n s valid from one algorithm proceeds in the order o f increasing r. However, in the case
viewing ray to the next along a scan plane. o f Figure 2b, where the light source is behind the viewer, the situa-
W h e n the light source is at infinity, the p a r a m e t e r for the tion is reversed, and the algorithm m u s t proceed in the order o f
shadow sort is the perpendicular distance between the shadow edge decreasing r.
a n d the eye. If the light source is finite, the extended shadow edge Suppose segment AB is the current span to be rendered. In both
passes through it, and the sort p a r a m e t e r is the angle between the Figures 2a a n d 2b, a n y polygon which can cast a s h a d o w on AB m u s t
shadow edge direction a n d the line L from the light source to the eye. interest the triangle SAB. By the time this current span is reached,
The shadow edges are linked into the shadow sort list by a separate any polygons contained in the semi-infinite angle SEA h a v e already
shadow sort pointer, which identifies the shadow edge block with the been merged into the shadow sort. But we m u s t treat carefully poly-
next highest sort p a r a m e t e r m a r k i n g a transition between light (0 gons intersecting the angle AEB, and in particular, the s e g m e n t AB
shadows) or darkness (1 or m o r e shadows). (See Table 1, item 8c.) itself.
We can think o f the scan plane as m a d e up o f a collection o f rays We say a polygon is front lit if the side facing the viewer also
from the eye, ordered by the r sort in increasing angles away from the faces the light source, as is true for polygon AB in the figures. In this
sun direction. Along these rays are regions in shadow, b o u n d e d at the case, the s e g m e n t AB is merged into the shadow sort only after the r
shadow sort parameters o f the shadow edges. These regions deter- processing h a s completely passed it; otherwise it would shadow itself.
m i n e the shadowed surfaces when rendering a span, and also the T h e neglected s h a d o w s caused by this delay will not affect the final
shadowed regions in the atmosphere. picture, because segments like C D and EF, which should have been
At the appropriate time, as discussed below, each polygon in shadowed by AB, are hidden by AB.
turn m u s t have its s h a d o w edges merged into the shadow sort. T h i s 11 is also necessary to refrain from merging segments C D a n d EF
could result in no change, if the new shadow region is already in until AB has been rendered, otherwise they will cast backwards shad-
shadow, or in one or two new shadow edges, depending on the over- ows onto AB. Since C D is front lit, it is delayed by the rule already
lap with existing shadows. Old shadow edges overlapped by the new m e n t i o n e d for AB. Back lit segments like F G are merged when one
region are unlinked from the sort list, which can thus grow shorter. If o f the following conditions b e c o m e s true: (a) the s e g m e n t FG over-
care is taken to join s h a d o w regions which exactly abut, then after a laps the span to be rendered a n d lies at least partly on the sunlit side
network o f polygons defining a c o n t i n u o u s surface has been pro- o f the polygon visible in the span, (b) the s e g m e n t FG is itself a b o u t
cessed, the result in the shadow sort is the s a m e as if only shadow to be rendered, or (c) the r processing has completely passed FG.
polygons for the profile edges had been entered. (See Crow [3].) W h e n a polygon is entered into the active s e g m e n t list, its plane
Consider the scan plane through the eye E and the light source S, equation is c o m p u t e d and entered into its segment block, as coef-
as shown in Figures 2a and 2b. In Frank Crow's algorithm, the ficients of an affine function which is positive on the side o f the
shadow edges would be considered togelher with the polygon seg- polygon containing the light source. (See item 13 in Table I.) Also a
m e n t s during the two-dimensional sort constituting the hidden sur- bit (item 10) is set to 1 if the viewpoint is on the positive side o f t h i s
face algorithm on this plane. Here, we treat the shadow edges sepa- plane, so that the polygon is front lit. Segments with this bit set are
rately, in the simpler o n e - d i m e n s i o n a l merge/sort just described, merged into the shadow sort at the l i m e they are r e m o v e d from the
which accounts only for the sort p a r a m e t e r o f a s h a d o w edge, and not active segment list.

119
 S I G G R A P H '86

I/ i

Not-yet-merged back lit active s e g m e n t s are linked into a sublist Z

called the test list (item 5 in Table 1), to facilitate checking conditions
(a), (b), a n d (c) before each span is rendered. T h e test for (a) uses the G T
plane equation (item 13) for the currently visible segment.

4. Translucency
In a forest, the leaves are translucent and light falling on the
sunlit side causes the other side to glow. (A s h a d o w is still cast, how-
ever, because the light is scattered in all directions, rather t h a n being
partially t r a n s m i t t e d along a u n i q u e refracted direction.) To get this
effect, I could n o t merely delay entering back lit translucent segments
into the s h a d o w sort, to prevent t h e m from s h a d o w i n g themselves, H G
because they m u s t still s h a d o w o t h e r polygons.
Instead, I m a i n t a i n a " ' 0 / 1 / m a n y " s h a d o w counter, which is 0 for
regions with no shadows, I for a single shadow, a n d 2 (representing
m a n y ) for regions blocked from the s u n by m o r e t h a n one polygon.
In each s h a d o w edge block is an entry for the count o f the region
b e y o n d that s h a d o w edge (item 8e in Table 1). T h e s h a d o w sort
pointer discussed above treats 2 the s a m e as 1 in deciding how to
merge a new s e g m e n t into the sort, so I call this the " 0 / m a n y " list. If
a scene h a s a n y translucent polygons, a separate 0 / l / m a n y list
pointer (item 8d) is m a i n t a i n e d for the potentially longer sort o f 0/1/
m a n y s h a d o w regions, a n d all s e g m e n t s are merged into both linked
lists. To do both merges at once, the m e r g e s u b r o u t i n e traces through Figure 3. A vertical plane through a ray R between the eye at O and
the 0 / m a n y pointers until the 0 / m a n y region containing the first a first polygon intersection point C. For clarity, the figure shows the
s h a d o w edge o f the new s e g m e n t has been found. It then follows the case w h e n the unit direction vector V to the sun lies in the s a m e
0 / m a n y a n d 0 / l / m a n y pointers separately from this point, and ad- vertical plane, so the parallel lines m a k i n g an angle of ~p with the
j u s t s the lists accordingly. If t h e 0 / m a n y list h a s N entries, the first vertical all represent sun rays or shadow edges. The ray R m a k e s an
search step takes t i m e o f order N. angle of 0 with the vertical and U is a unit vector along the ray. D E
Translucent polygons add 1 to the count o f the regions they and FG represent polygon segments casting shadows, and AB is an
shadow. W h e n the back lit side o f a translucent s e g m e n t is rendered, illuminated interval on the ray between the shadows. P = s U is a
1 is subtracted from the c o u n t to d e t e r m i n e which regions are glow- typical point in this interval. Q = s U + tV is a typical point on the
ing. O p a q u e polygons a n d front lit translucent polygons a d d 2 to the ray from P towards the sun.
count a n d are thus m o r e likely to shorten the 0 / 1 / m a n y list.
W h e n a visible s e g m e n t o f a polygon is rendered, its e n d p o i n t s
bedo of the particles, a n d on the scattering angle (see Blinn [ 11 ]). T h e
define a region o f the s h a d o w sort list, whose c o u n t s are used to
point P is at a distance s from the eye, so this scattered light is further
d e t e r m i n e the s h a d o w s on the segment. D u r i n g the sequential search
attenuated by a factor exp ( - bs). Therefore, the light reaching the
for this region in the 0 / m a n y list, t h e plane e q u a t i o n s for all s h a d o w
eye, scattered from the infinitesimal ray s e g m e n t o f length ds at P, is
polygons up to a n d including this region are copied into linearly
pI o exp [ - b (H - s cos 0) see q~] exp ( - bs) ds.
ordered data arrays. T h e s e arrays are t h e n used by the Cray-I in a
The total light reaching the eye, scatlered from the interval be-
vectorized ray/plane intersection c o m p u t a t i o n to d e t e r m i n e the illu-
t w e e n A = s i U a n d B = si + l U i s
m i n a t e d intervals along each ray from the eye. Since this ordered
data is needed, a m o r e sophisticated search taking t i m e o f order log
N cannot be used.
L~+'plo e x p [ - b H sec ~p - bs (1 - cos Osec ¢)] ds
i

5. Atmospheric illumination
;i~ I

We m u s t n o w calculate the integrated a t m o s p h e r i c glow along a

ray from the eye. T h i s c o m p u t a t i o n varies d e p e n d i n g on w h e t h e r the
= pI o exp ( - b H sec ~p)
fs
i
exp [ - bs(l - cos 0 sec gO] ds

distance to the light source is finite or infinite. e x p [ - b s ( 1 - cos Osec ~)] ~if,
First, a s s u m e the light source, like the sun, is at infinity. In Fig- = pI°exp(-bH sec ¢P) - b ( 1 - cos Osecfp)
ure 3, U is a unit vector from the eye along a viewing ray R, with the
eye at the origin O, a n d H is a height a b o v e which no data in the
which is o f the form C {exp [ - D (s i+ 1)] - exp [ - D (si)]/.
model extends. Also, V is a unit vector in the direction o f the sun, ~p
T h e constants C a n d D d e p e n d on the ray, but n o t on the dis-
is the angle between the s u n direction a n d the vertical a n d 0 is the
tances % so the s u m o f the scattered light reaching the eye from all
angle between the ray R a n d the vertical. We wish to c o m p u t e the
the illuminated intervals on a ray can be c o m p u t e d in a vectorizable
scattered light reaching the eye from a n o n - s h a d o w e d interval A B on
loop, using a vectorized exponential function.
the ray R. We first consider the absorption o f the sunlight due to the
T h i s calculation can be generalized for the case of layered fog,
haze above a point P on the interval AB.
whose density b(z) is a function o f only the altitude z a b o v e sea level.
A s s u m e that the haze h a s c o n s t a n t density a n d absorbs a frac-
Perlin [14] suggests that the integral g(z) = J~ b(u) d u be p r e c o m -
tion b dr o f the light along an infinitesimal length dr o f the ray R. If
puled and tabulated. Then, to find the total density between the eye
l(r) is the intensity at distance r t h r o u g h the haze, then [d I(r)]/I(r) =
a n d the point P = sU in Figure 3, we need only look up g (s cos 0)
- b dr, a n d by integration l(r) = I(0) exp ( - br). Let I o represent the
a n d multiply by see 0.
sunlight intensity at altitude H. In Figure 3, the z coordinate at P is
A s s u m e that the scattering coefficient p satisfies p = fib(z), with
s cos 0, so the distance r from P to T is r = P G sec q~ = (H - s cos 0)
the c o n s t a n t / 3 d e p e n d i n g only on the angle between the viewing ray
sec ~0, a n d the intensity reaching P is I o exp [ - b (H - s cos 69 sec ~p].
a n d the s u n direction. T h e n , because o f the lucky identity
In this paper, we a s s u m e a single scattering m o d e l for light diffu-
sion through haze, as described in Blinn [11] and M a x [12]. (For a
d/dz {exp [ - g(z)] } = - dg/dz [exp [ - g(z)l = - b(z) exp [ - g(z)] },
m o r e sophisticated m o d e l o f light scattering, see Kajiya [13].) Ac-
cording to the single scattering model, the dust particles or water it turns o u t that the analysis above for c o n s t a n t density can be re-
droplets in the air will scatter an a m o u n t p d s o f the light at P towards pealed for layered fog, giving a total scattering intensity o f the form
the eye. T h e scattering coefficient p d e p e n d s on the density a n d al- C see 0 {exp [ - D g (si. 1 cos 0)] - exp [ - D g (s i cos 0)]} with C a n d

120
Dallas, A u g u s t 18-22 V o l u m e 20, N u m b e r 4, 1986
III
|1 I

where.E is the total scattering energy c o m p u t e d in section 5. (Care

m u s t be taken so that this extra t e r m does not cause the color to
exceed the displayable range.)
T h e output o f the h i d d e n - s u r f a c e / s h a d o w algorithm is a collec-
tion o f visible surface segments, separated into illuminated or shad-
d owed intervals. Each color c o m p o n e n t fc, for c = r,g,b, m u s t be inter-
polated across every interval as a function o f the radius p a r a m e t e r r
along a radial scan line. These functions m a y be highly non-linear
since s r, sg, s b, T, a n d E all vary across the surface, a n d the perspec-
tive projection a n d exponential absorption are non-linear.
T h e functions fc(r) m u s t be accurately approximated, or else the
color m a y change suddenly where a new polygon or s h a d o w edge
/ - u interrupts a longer interval from the previous scan line. I chose to
a p p r o x i m a t e the fc using a hermite cubic interpolation p o l y n o m i a l to,
O which m a t c h e s the values o f f¢ a n d its derivatives at the interval e n d
points. (See M o r t e n s o n [15], Rogers a n d A d a m s [16].)
Figure 4. An illuminated interval AB on a ray. The eye is at the At a division point between a region o f s h a d o w a n d light on the
origin O, and the light source L is at a finite distance. The line LP is same visible surface, only Sr, sv a n d sb change suddenly. T a n d E
perpendicular to the ray, meeting it at P. The length d of LP is the remain continuous, a n d need be c o m p u t e d only once. Their deriva-
shortest distance from L to the ray. If U is a unit vector along the ray, tives are estimated from finite differences, by evaluating T and E at
then P = sou , where s o is the length of the segment PP. nearby points.
T h e endpoint color c o m p o n e n t s a n d their derivatives are used
D depending on ~p, H, and ft. to calculate the interpolated values to(l/2 ) o f the h e r m i t e p o l y n o m i -
a•s at the interval m i d p o i n t using the identity to(i/2 ) = fc(0)/2 +
In the case o f a finite light source, we m u s t take into account the
f~(I)/2 + f'c(0)/8 - f'c(l)/8.
inverse square law, a n d I only h a v e an easy answer for the case o f
c o n s t a n t density, n o absorption, a n d c o n s t a n t albedo i n d e p e n d e n t o f T h e actual colors at the interval m i d p o i n t are also c o m p u t e d by
the angles, which n o w change even along a single ray. Suppose a evaluating T, E, a n d (st, sg, s 0. If all three actual colors agree with
point source is at position L, as s h o w n in Figure 4, a n d a ray from the their interpolated values to within a specified tolerance, the cor-
eye approaches its closest distance d to L at point P = s o U. Let Q = responding herrnite p o l y n o m i a l is used for the interval. Otherwise,
the interval is s u b d i v i d e d recursively using the actual values f o u n d at
sU be a n y other point on the ray. T h e distance from Q to L is
•~ - T (s-'2~o)'. By the inverse square law, a s s u m i n g n o absorption, the m i d p o i n t (and at a nearby point for the finite difference) until the
the intensity at Q is K/[d 2 + (s - %)2]. tolerance criterion is met or the m a x i m u m permitted recursion level
So the intensity along an interval between A = si U a n d B = is reached.
s~,+l U is
7. Scan conversion with anti-aliasing
s~, ~ d_s T h i s p o l y n o m i a l shading i n f o r m a t i o n m u s t n o w be scan con-

• si+,

i +
K ds

rift,,1 dt
K

i 1 +
d

K[tan - | (tit,) - t a n - ' (ti)]/d

vetted into a standard rectilinear image. If the data were s a m p l e d at
discrete radial points into a polar coordinate array, it could be r e s a m -
pied by the m e t h o d s o f Catmull and Smith [17]. But this would m e a n
sacrificing the extra accuracy available in the c o n t i n u o u s radial di-
rection. Instead, 1 have used gaussian filtering on a n image which is
black except on the infinitely thin radial scan lines, where the inten-
d j 1 +t 2
sity is given by the polynomials. A n explanation o f this filtering will
appear in a f o r t h c o m i n g paper [18].
where t i = (s i - So)/d.
Using any o f the above m e t h o d s , the total scattered energy, E, is 8. Clipping
found by adding up the integrals from each o f the illuminated seg-
m e n t s along the ray from the eye to a surface point. For a perspective view without shadows, all polygons are usually
clipped to a view volume, as s h o w n in Figure 5.
6. Composite colors and their cubic interpolation
B B
T h e final c o m p o s i t e color o f a surface as influenced by the haze
S S
along a ray d e p e n d s on several quantities: the total scattered energy E
as c o m p u t e d above, the surface color (st, s v %) as d e t e r m i n e d from
the illumination and surface shading models, a n d a haze t r a n s m i s - C C
sion factor T. T h e use o f a "fog factor" T is already c o m m o n in
c o m p u t e r imagery. If the fog h a s constant density, with absorption 0
coefficient b, then the t r a n s m i s s i o n factor is T = exp ( - bs) where s
is the distance from the eye to the surface. For layered fog, T = exp
[ - sec 0 g (s cos 0)], where 0 is as s h o w n in Figure 3, a n d g is the
integral of the fog density along a vertical line as discussed above.
Even if the ray is entirely in shadow, the fog still imparts a color
(hr, hg, hb) from its a m b i e n t illumination. In this case, the standard
D D
m e t h o d for finding the o u t p u t color (fr, fv fb) is
Figure 5. Left: A view pyramid, bounded by four slanted triangles,
(fr,fg,fl})= T (St,Sg,Sb) + (] -- T)(hr, he, hb). and a far clipping plane ABCD. From the point of view of the light
source S, only faces OAB and OBC are visible, and the profile is the
N o w let (Jr,is,ib) represent the color of the haze whcn illumi- broken line OCBAO. Right: The larger clipping volume for shadows
nated, so that (cr, eg, eb) = (it, ig, ib) - (hr, hg, hb) is the extra glow. is formed by removing faces OAB and OBC, and adding faces SOC,
T h e n if a ray is partly illuminated, the output color is SCB, SBA, and SAP. The removed planes OAB and OBC, and the
near clipping plane, will later be used to separate off the visible poly-
(f~, fv fs) = T(s~, sg, Sb) + (1 - T)(hr, h v hb) + E(er, %, eb) , gons,

121
 ~ S I G G R A P H '86

This eliminates polygons which are invisible and prevents verti- The algorithm was adapted in incremental fashion from a direct
ces behind the eye from being incorrectly projected. For a view with descendant of the original Fortran program written by Gary Watkins
shadows, such clipping might eliminate polygons which could cast to test his proposed hardware hidden surface algorithm. It was re-
shadows on visible ones. Unless the light source is within the view written by Mike Achuleta at LLNL and later modified by Bruce
volume, a larger shadow-casting volume must be found, which in- Brown, Paul Renard, and Gene Cronshagen. I found incremental
cludes all polygons which could cast shadows into the view volume. changes to an existing program easier than planning a new algorithm
The planes bounding the shadow casting volume come from two from scratch, because I could use the pictures to debug each new
lists: a) the faces of the view volume whose outward normal points feature. I wish to thank Jules Bioomenthal for the tree trunk data and
away from the light source, and b) planes formed by joining the light bark texture, Mafia Lopez for typing this paper, and Charles Grant
source direction to profile edges of the view volume. The profile for carefully reading and commenting on it.
edges can be identified as those which appear exactly once among the
edges of the faces in list a). A third list c) contains the faces of the References
view volume not in list a), as well as a near clipping plane used to [1] Williams, Lance, "'Casting Curved Shadows on Curved Sur-
avoid division by zero. faces," SIGGRAPH "78 proceedings, pp. 270-274.
All polygons are clipped to the planes in lists a) and b) to remove [2] Athenon, Peter, Weiler, Kevin, and Greenberg, Donald, "Poly-
polygons or parts of polygons which are irrelevant to the image. gon Shadow Generation," SIGGRAPH '78 proceedings, pp.
Then the planes in list c) are used to break the resulting polygons into 275-281.
two groups: the visible polygons and the shadow-only polygons. [3] Crow, Franklin, "Shadow Algorithms for Computer Graph-
The shadow-only polygons are entered into the 0 bucket sort. ics," SIGGRAPH '77 proceedings, pp. 242-248.
They need not be entered into the Watkins r - z sort, but they must [4] Nishita, Tomoyuki, Okamura, Isao, and Nakamae, Eihachiro,
be merged together as non-translucent segments in the shadow sort "Shading Models for Point and Linear Sources," ACM Trans-
lists, before the r - z sort is started. actions on Graphics, Vol 4 no. 2 (1985), pp. 124-146.
[5] Bouknight, J., and Kelly, K., "'An algorithm for producing half-
9. Summary tone computer graphics presentations with shadows and mov-
Put all edges into 0 buckets. able light sources," SJCC, AFIPS, Vol 36 (1970), pp. 1-10.
For all buckets, in order of decreasing 0: [6] Whitted, Turner " A n Improved Illumination Model for
Enter all edges from bucket 0 into r sort segment blocks. Shaded Display," Communications of the ACM, Vol 23
Merge all shadow-only segments into shadow sort. (1980), pp. 343-349.
For each visible span generated by the Watkins r - z sort: [7] Cook, Robert, Porter, Thomas, and Carpenter, Loren, "'Dis-
Merge back lit polygon segments which satisfy conditions tributed Ray Tracing," SIGGRAPH '84 proceedings, pp. 137-
(a), (b), or (c) of section 3 into shadow sort. 145.
Find intervals of light and shade on the visible span. [8] Watkins, Gary, "A real-time visible surface algorithm," Ph.D.
For each interval, approximate color functions by recur- Thesis, University o f Utah (1970) UTECH-CSc-70-101.
sively defined piecewise cubic polynomials, and scan con- [9] Sproull, Robert, and Newman, William, "'Principles oflnterac-
vert each piece into rectilinear pixel array. rive Computer Graphics" (first edition is better on this sub-
Merge front lit polygon segments which end during the span ject), McGraw Hill, New York (1973).
into shadow sort. [10] Rogers, David, "Procedural Elements for Computer Graph-
Remove edges which terminate at this 0 from active r sort. ics," McGraw Hill, New York (1985).
Update edges for next radial scan line. [11] Blinn, James, "Light Reflection Functions for Simulation of
Output final picture. Clouds and Dusty Surface," SIGGRAPH '82 proceedings, pp.
21-29.
10. Results [12] Max, Nelson, "Light Diffusion through Clouds and Haze,"
Computer Vision Graphics, and Image Processing, Vol 33
Figure 6 shows a jack-o-lantern, lit by a candle inside it. The (1986), pp, 280-292.
finite light source is within the view volume. It took approximately [13] Kajiya, James, and Von Herzen, Brian, "'Ray Tracing Volume
20 seconds to compute on the Cray-1, at 512 by 512 resolution. Fig- Densities," SIGGRAPH '84 proceedings, pp. 165-174.
ure 7 shows vertical columns o f light coming through a hole in the [14] Perlin, Ken, "State of the Art in Image Synthesis '85 Course
clouds. The sun is at infinity directly overhead, and the methods of Notes," ACM SIGGRAPH '85, course 11.
Max [12] were used to compute the atmospheric shadows from the [15] Monenson, Michael, "Geometric Modelling," John Wiley and
partially transparent clouds. Sons, New York (1985).
Figure 8 shows three polygons casting shadows on each other, on [16] Rogers, David, and Adams, J. A., "'Mathematical Elements for
the ground below, and in the atmosphere. The contrast in the atmo- Computer Graphics," McGraw Hill, New York (1976).
spheric illumination is most apparent where there is a shadow poly- [17] Catmull, Ed, and Smith, Alvey Ray, "3-D Transformations of
gon almost parallel to the line of sight. The light is at infinity above Images in Scanline Order," SIGGRAPH '80 proceedings, pp.
and behind the viewer, so the atmospheric shadows appear smaller 279-285.
near the ground, due to the perspective forshortening. Figure 9 shows [18] Max, Nelson "Anti-Aliasing Scan Line Data" to be submitted
several trees, designed by Jules Bloomenthal (see [19]), with shadow- to IEEE Computer Graphics and Applications.
mapped bark (see [20]). [19] B l o o m e n t h a l , Jules, " M o d e l l i n g the Mighty M a p l e , "
These results show that it is possible to integrate atmospheric SIGGRAPH '85 proceedings, pp. 305-311.
illumination efficiently into a scan line hidden-surface algorithm, if [20] Max, Nelson, "Shadows for Bump Mapped Surfaces," in Ad-
radial scan lines are used. vanced Computer Graphics: Proceedings of Computer Graph-
ics Tokyo "86, T. L. Kunii, ed., Springer Verlag, Tokyo (1986),
Acknowledgments pp. 145-156. To be revised and submitted to The Visual
This work was performed under the auspices o f the U.S. Depart- Computer.
ment of Energy by Lawrence Livermore National Laboratory
(LLNL) under contract number W-7405-ENG-48.

122
Dallas, August 18-22 Volume 20, Number 4, 1986

Figure 6. A jack-o-lantern, lit by a candle. Figure 8. Three polygons casting atmospheric shadows.

Figure 7. Sunlight coming through a break in the clouds.

123
// S I G G R A P H '86

Figure 9. Several trees.

124