
				\|\|\|\|

By Eric Lengyel
Gamasutra
[Author's Bio]
October 11,2002

Algorithm Overview

Infinite View Frustums

Silhouette Determination

Determining Whether Caps are Necessary

Rendering Shadow Volumes

Scissor Optimization

	Printer Friendly Version

Game Developer Magazine Back Issues four CD Set.
Every issue 1994 to April 2002.
Price: $189.00 + S&H

Letters to the Editor:

Write a letter

View all letters

Features

The Mechanics of Robust Stencil Shadows

Infinite View Frustums

To ensure that shadow volumes surround every last bit of space for which light is blocked by an object, we must extrude the object’s silhouette to infinity. Using a standard perspective projection matrix would cause such a shadow volume to be clipped by the far plane. To avoid this unwanted effect, we can actually place the far plane at an infinite distance from the camera.

Recall that the projection matrix transforms points from eye space to clip space. In OpenGL, eye space is the coordinate system in which the camera lies at the origin, the x-axis points to the right, the y-axis points upward, and the camera points down the negative z-axis. In clip space, a 4D homogeneous point <x,y,z,w> is inside the view frustum if -w<x<w, -w<y<w, and -w<z<w. Once primitives have been clipped, a vertex is transformed into a 3D point in normalized device coordinates by performing a perspective divide by its w-coordinate. This results in a point whose x, y, and z coordinates all lie in the range [-1,1]. In the final transformation before rasterization, these coordinates are remapped to the dimensions of the viewport and the physical range of the depth buffer.

The standard OpenGL perspective projection matrix P has the form

(1)

where n is the distance to the near plane, f is the distance to the far plane, and l, r, b, and t represent the left, right, bottom, and top edges of the rectangle carved out of the near plane by the view frustum. By evaluating the limit as f tends to infinity, we obtain the matrix

(2)

The matrix P_¥ transforms a 4D homogeneous eye-space point V_eye=<x,y,z,w> to the clip-space point V_clip as follows.

(3)

Assuming w>0 (it is normally the case that w=1), the resulting z-coordinate of is always less than the resulting w-coordinate of V_clip, ensuring that projected points are never clipped by the far plane. A point at infinity is represented by 4D homogeneous vector having a w-coordinate of zero in eye space. For such a point, (V_clip)_z = (V_clip)_w, and the perspective divide produces a 3D point in normalized device coordinates having the maximal z-value of one.

In practice, the limitations of hardware precision can produce points having a normalized z-coordinate slightly greater than one. This causes severe problems when the z-coordinate is converted to an integer value to be used in the depth buffer because the stencil operations that depend on the depth test to render shadow volumes may no longer function correctly. To circumvent this undesirable effect, we can map the z-coordinate of a point at infinity to a value slightly less than one in normalized device coordinates. The z-coordinate of a 3D point D in normalized device coordinates is mapped from a value D_z in the range [-1,1] to a value D'_z in the range [-1,1-e], where e is a small positive constant, using the relation

(4)

We need to find a way to modify the z-coordinate of V_clip in order to perform this mapping as points are transformed from eye space into clip space. We can rewrite Equation (4) as an adjustment to (V_clip)_z by replacing D_z with (V_clip)_z / (V_clip)_w and D'_z with (V'_clip)_z / (V_clip)_w as follows.

(5)

Plugging in the values of and given by equation (3), we have

(6)

Solving for and simplifying yields

(7)

We can incorporate this mapping into the projection matrix P_¥ given by Equation (2) as follows to arrive at the slightly tweaked matrix P'_¥that we actually use to render a scene.

(8)

If the graphics hardware supports depth clamping, then use of the matrix P'_¥ given by Equation (8) is not necessary. The GL_NV_depth_clamp extension to OpenGL allows a renderer to force depth values in normalized device coordinates to saturate to the range [-1,1], thus curing the precision problem at the infinite far plane. When depth clamping is enabled using the function call

glEnable(GL_DEPTH_CLAMP_NV);

the projection matrix P_¥ given by Equation (2) can safely be used.

The question of depth buffer precision arises when using an infinite projection matrix. It is true that placing the far plane at infinity reduces the number of discrete depth values that can occur within any finite interval along the z-axis, but in most situations this effect is small. Consider the function that uses the matrix P given in Equation (1) to map an eye-space point V=<V_x,V_y,V_z,1> to its corresponding depth in normalized device coordinates:

(9)

We obtain a different dfunction d_¥(V) by using the matrix P_¥ given by Equation (2) to map an eye-space point V to its normalized depth:

(10)

Given two eye-space points V₁and V₂, we can compare the differences in depth values produced by the functions d and d_¥ as follows.

(11)

This demonstrates that the standard projection matrix P maps the points V₁and V₂ to a range that is a factor f /(f-n) larger than the range to which the points are mapped by the infinite projection matrix , thus equating to greater precision. For practical values of f and n, where f is much larger than one and n is much smaller than one, is close to unity, so the loss of precision is not a significant disadvantage.

______________________________________________________

Silhouette Determination