Gamasutra: The Art & Business of Making Gamesspacer
The Mechanics of Robust Stencil Shadows
View All     RSS
November 21, 2014
arrowPress Releases
November 21, 2014
PR Newswire
View All






If you enjoy reading this site, you might also want to check out these UBM Tech sites:


 
The Mechanics of Robust Stencil Shadows

October 11, 2002 Article Start Previous Page 6 of 6
 

Scissor Optimization

When using an attenuated light source, it is usually convenient to define a range r beyond which the light source does not contribute any illumination to the world. Although this is not a physically correct model, using an attenuation function that vanishes at a distance r from the light’s position allows us to quickly cull any light source whose sphere of illumination does not intersect the view frustum. When a light source’s sphere of illumination is visible, the area within the viewport that could possibility be affected by the light source may not be the entire viewport. By projecting the sphere of illumination to the image plane and using the scissor rectangle to limit our drawing to the projected area of influence, we can avoid a significant amount of superfluous rendering of both shadow volumes and illuminated surfaces.

Suppose that we have a point light source whose center lies at the point L in eye space and whose range is r, as shown in Figure 8. We wish to find four planes, two parallel to the x-axis and two parallel to the y-axis, that pass through the camera position (the origin in eye space) and are also tangent to the light source’s bounding sphere. Once these planes have been determined, we can locate their intersections with the image plane to find the rectangular boundary of the projection of the light source’s bounding sphere.





Figure 8. For a point light source at the position L having range r, we calculate the four planes that pass through the camera position C and are tangent to the light’s sphere of illumination. By calculating the intersection of each tangent plane with the image plane lying at a distance e from the camera, we can limit our drawing to an area smaller than the full size of the viewport.

We assume that the tangent planes parallel to the y-axis have a unit-length normal vector N whose y-coordinate is zero. Since the planes pass through the origin, each can be represented by a 4D vector T = <Nx,O,Nz,O>. We wish to calculate values of Nx and Nz such that the following conditions are satisfied.

(24)

(25)

By expanding the dot product and rearranging slightly, we can rewrite Equation (24) as

(26)

Squaring both sides of Equation (26) and making the substitution N2z=1-N2x, we have

(27)

This can be rewritten as a quadratic equation Nx in as follows.

(28)

The discriminant D is given by

(29)

D<0 precisely when L2x+L2z<r2 (i.e., when the origin falls within the projection of the sphere onto the x-z plane). When this happens, we know the light source’s bounding sphere fills the entire viewport and we do not continue.

If D>0, then we can solve equation (28) using the quadratic formula to obtain

(30)

This gives us two values for Nx. The corresponding values for Nz are calculated by making a small adjustment to Equation (26):

(31)

We only want to consider planes whose point of tangency with the light source’s bounding sphere lies in front of the camera. As illustrated in Figure 8, the point of tangency P lies in the plane <Nx,0,Nz,0> at a distance r from the point L, giving us the following two equations.

(32)

(33)

Equation (33) can be expanded to

(34)

Using the Pythagorean theorem, we can replace P2 with L2-r2 to obtain

(35)

For the point P to lie in front of the camera, we must require that Pz<0. Since the tangent plane is parallel to the y-axis, the values of Py and Ly are equal and the quantity L2y cancels in Equation (35). By solving Equation (32) for Px, we can make the substitution

(36)

in Equation (35) to arrive at the following equation written completely in terms of the unknown Pz.

(37)

Solving for Pz, we have

(38)

For any tangent plane <Nx,0,Nz,0> calculated using Equations (30) and (31), we calculate the corresponding value of Pz using Equation (38). If Pz < 0, then we have found a plane that may allow us to shrink the scissor rectangle. We now need to determine where the tangent plane intersects the image plane.

As shown in Figure 8, the image plane is perpendicular to the z-axis and lies at a distance e from the camera. On the image plane, the area of the viewport corresponds to x-coordinates in the range [-1,1] and y-coordinates in the range [-a,a], where a is the aspect ratio given by the height of the viewport divided by its width. Any point Q lying in the image plane has coordinates <x,y,-e>. A point Q lying in the plane tangent to the light source’s bounding sphere satisfies N · Q = 0, so we can solve for x:

(39)

This x-coordinate can be mapped to the viewport coordinate x' using the formula

(40)

where l is the left edge of the viewport and w is the viewport’s width, both in pixels.

Given a value x' calculated using Equation (40), we need to determine whether it represents a left-side boundary or a right-side boundary. This can be accomplished by plugging the value Pz given by Equation (38) into Equation (36) to obtain Px. If , then represents a left-side boundary because the point of tangency falls to the left of the light source. If Px>Lx, then x' represents a right-side boundary. Since the value may lie outside the viewport (if x Ï [-1,1]), we calculate the left and right edges of the scissor rectangle as follows.

(41)

The two tangent planes parallel to the x-axis are found in an almost identical manner. Each of these planes is represented by a 4D vector <0,NyNz,0>, whose nonzero components are given by the following formulas.

(42)

The z-coordinate of each corresponding tangent point is given by

(43)

If Pz<0, then the y-coordinate where each plane intersects the image plane is given by

(44)

where the viewport’s aspect ratio a has been added to the denominator. Finally, the viewport coordinate y' is calculated using the formula

(45)

where b is the bottom edge of the viewport and h is the viewport’s height, both in pixels.

To determine whether y' represents a bottom-side boundary or a top-side boundary, we calculate the y-coordinate of the point of tangency using the formula

(46)

If Py<Ly, then y' represents a bottom-side boundary. If Py>Ly, then y' represents a top-side boundary. As with the left and right sides, the values of y' should be clamped to the viewport’s range as follows.

(47)

Using the values given by Equations (41) and (47), the OpenGL scissor rectangle is enabled and set to the appropriate values using the following function calls.

glEnable(GL_SCISSOR_TEST);
glScissor(scissor.left, scissor.bottom,
scissor.right - scissor.left,
scissor.top - scissor.bottom);

The scissor rectangle affects the clear operation as well, so once rendering has been completed, one should either disable the scissor test or set the scissor rectangle back to the entire viewport rectangle by making the call glScissor(l, b, w, h).

Conclusion

The techniques described in this article can be used to efficiently render the shadow volumes needed to display a fully shadowed scene in real-time using stencil operations. Future graphics hardware will undoubtedly incorporate greater shadow volume functionality that will relieve the CPU from some of the work that it currently has to do, but the ultimate determination of speed will be innovative methods for minimizing the number of shadow volumes that must be rendered in the first place. Achieving high frame rates for complex scenes having multiple light sources is now the goal of larger-scale optimizations, and this is currently a hot area of 3D graphics research.

For Further Information

The following is the original paper discussing shadow volume capping and depth-fail stencil operations

Everitt, Cass and Kilgard, Mark J., “Practical and Robust Stenciled Shadow Volumes for Hardware-Accelerated Rendering”, NVIDIA Corporation, 2002.
http://developer.nvidia.com/view.asp?IO=robust_shadow_volumes

Mathematical derivations of different bounding volume tests that can be used to determine whether an object’s shadow volume might intersect the near rectangle can found in the Visibility Determination chapter of the following book.

Lengyel, Eric, Mathematics for 3D Game Programming & Computer Graphics, Charles River Media, 2002.

Information about the OpenGL extensions used in this article can be found at the OpenGL Extension Registry website:

http://oss.sgi.com/projects/ogl-sample/registry/

 

 

 


Article Start Previous Page 6 of 6

Related Jobs

Forio
Forio — San Francisco, California, United States
[11.21.14]

Web Application Developer Team Lead
DeNA
DeNA — San Francisco, California, United States
[11.21.14]

Senior Build and Release Engineer
Filament Games LLC
Filament Games LLC — Madison, Wisconsin, United States
[11.21.14]

Game Engineer
The Workshop
The Workshop — Marina del Rey, California, United States
[11.21.14]

Programmer





Loading Comments

loader image