Shadow Rendering Algorithms
02.september.1997
GFX
by Hin Jang
Shadows provide a visual cue to the spatial relationships among objects in a given scene. Simulating hard shadows is possible using clever approximations [1]. More robust algorithms that simulate shadows cast by moving, complex objects onto multiple planar surfaces have also been developed [2, 3]. Soft shadows caused by extended light sources, however, require greater computation; those areas with an umbra (fully shadowed regions) and penumbra (partially shadowed regions). At true interactive rates, simulating soft shadows in a dynamic and complex scene require high-end, parallel hardware. The principle of shadow generation is based on a modified perspective projection and is easily incorporated into any rendering pipeline.
A point P(x, y, z) that is illuminated by a light source L(x, y, z) casts a shadow at
S = a(L - P) - Pand assuming the shadow falls upon a ground plane, where z = 0, solving for a yields
zP
a = ---------
zL - zPThe coordinates of the shadow point S are then
xPzL - xLzP
xS = ----------
zL - zP
yPzL - yLzP
yS = ----------
zL - zPAssuming a homogeneous coordinate system where
xS = xS' / wS'
yS = yS' / wS'
wS' = zL - zPS can be calculated using matrix multiplication
| zL 0 0 0 |
| 0 zL 0 0 |
[ xS' yS' 0 wS' ] = [ xP yP zP 1 ] | -xL -yL 0 -1 |
| 0 0 0 zL |To generalise the 4x4 matrix so that the algorithm can perspectively project a shadow point onto any plane, consider an arbitrary point on the line from P to L represented in homogeneous coordinates
aP + bLwhere a and b are scalars. The matrix above assumes a ground plane G whose normal is represented as a four-element column vector.
| 0 |
| 0 |
G = | 1 |
| 0 |The point on the shadow line that intersects G is given by (a, b) where
(aP + bL) . G = 0Rearranging the equation yields
a(P . G) + b(L . G) = 0which can be satisfied by any scalar multiple of
a = (L . G)
b = -(P . G)The shadow point S is then
S = (L . G)P - (P . G)LRecall that P and L are row vectors and G is a column vector. Matrix multiplication is associative; therefore,
(P . G)L = P(GL)and note that GL is a 4x4 matrix and (L . G) is a scalar. Given that I is a 4x4 identity matrix
S = P[(L . G)I - GL]The generalised 4x4 matrix used to perspectively project a shadow point onto any plane is
[(L . G)I - GL]where G is the normal of the plane onto which S is cast.
Shadows points, or a given subset, forms the vertices of a hard shadow. The real world, however, contains mostly soft shadows. The ideal method of computing soft shadows should 1) have a memory requirement independent of the number of light source samples and 2) exploit graphics hardware that determines visibility and calculates shading. If such hardware is unavailable, calculations can be done in software using a graphics subroutine interface, as such OpenGL. The premise of the algorithm developed by Heckbert and Herf is to precompute the emitted radiance at each point on every polygon to produce a set of hard shadows [2]. These shadows are then averaged to compute the soft shadow image.
The emitted radiance from a surface is given by summing the contributions over all sample points on all light sources
Lc(x) = pc(x)Lac
nl
---- ---- cos+tli cos+tli' Lc(xli')
+ \ \ (ali pc(x)) ------------------------- v(x, xli')
/ / pi rli2
---- ----
l i=1where
- x = (x, y, z) is a point on the reflective surface, and xli' is the sample point i on light source l
- ali is the area associated with sample point i
- t is the polar angle (angle from normal) at x, t' is the angle at xli'
- r is the distance between x and xli'
- t, t' and r are functions of x and xli'
- Lc is the outgoing radiance at point x for color channel c
- Lac is the ambient radiance
- pc is reflectance
- v(x, xli') is a Boolean visibility function that equals 1 if point x is visible from point xli', else 0
- cos+t = max(cost, 0), for backface testing
- pi is the constant
The summand is the product of three factors
- the area times the reflectance of the receiving polygon
- the cosine of the angle on the receiver times the cosine of the angle on the light source times the radiance of the light source divided by pi r2
- the visibility between a point on a light source and each point on the receiver
To generate the set of hard shadow images, the algorithm requires a projective transformation. For a given parallelogram P fitted around the receiver polygon, a pyramid can be constructed with P as its base and the light point as its apex. The 4x4 homogeneous transformation that accomplishes this is the matrix tranform M of interest. The pyramid lies in object space with coordinates (xo, yo, zo) with apex a and its parallelogram base has one vertex at b and edge vectors ex and ey. Applying M yields a parallelepiped in unit screen space with coordinates (xu, yu, zu). Viewed from a, the left and right sides of the volume map to parallel planes xu = 0 and xu = 1. The bottom and tops sides map to yu = 0 and yu = 1, and the base plane and the plane parallel through the apex map to zu = 0 and zu -> infinity.
The matrix M has the form
/ axnxx axnxy axnxz -axnx.b \
M = | aynyx aynyy aynyz -ayny.b |
| 0 0 0 1 |
\ awnwx awnwy awnwz -awnw.a /where
nx = ew × ey ax = 1 / (nx . ex)
ny = ex × ew and ay = 1 / (ny . ey)
nw = ey × ex aw = 1 / (nw . ew)Averaging the hard shadows is done by a weighted, linear combination of images
----
Ac(x, y) = \ aiIic(x, y)
/
----
iwhere Iic is a channel (red, green or blue) for image i, ai is the weight, and Ac is a channel of the accumulator array. The algorithm to precompute radiance textures is then
RadianceTexture()
{
for (each receiver polygon R) {
select resolution of receiver's texture (sx X sy pixels)
clear accumulator image of sx X sy pixels to black
create temporary image of sx X sy pixels
for (each light source l) {
if (l is behind R || R is behind l)
skip to next l
for (each sample point i on light source l) {
if (xli' is behind R)
skip to next i
compute transform matrix M, where a = xli'
with parallelogram base fitted around R
set transform matrix to scale (sx, sy, 1) . M
set clipping planes to zu.near = 1 - e
and zu.far = big
draw R with illumination from xli', as
described in the equation for Lc, into
temporary image
for (each other object in scene) {
draw object with ambient colour into temporary image
}
add temporary image into accumulator image with weight
al / nl
}
}
save accumulator image as texture for polygon R
}
}To render a scene with shadows, simply
RenderWithShadows()
{
for (each object in scene)
if (object receives shadows)
draw object with radiance textures and no illumination
else draw object with illumination
}[1] Blinn, J. F., "Me and My (Fake) Shadow," IEEE Computer Graphics and Applications, 8(1):82-86, January 1988
[2] Heckbert, P., and M. Herf, Simulating Soft Shadows with Graphics Hardware, CMU-CS-97-104, CS Dept, Carnegie Mellon University, January 1997
[3] Loscos, C., and G. Drettakis, Interactive High Quality Soft Shadows in Scenes with Moving Objects, iMAGIS/GRAVIR-INRIA, 1997
[4] Stewart, J. A., and S. Ghali, Fast Computation of Shadow Boundaries Using Spatial Coherence and Backprojections, Department of Computer Science, University of Toronto, 1995
