Features

The Mechanics of Robust Stencil Shadows

Silhouette Determination

The stencil shadow algorithm requires that the models in our world be closed triangle meshes. In mathematical terms, the surface of any object that casts a shadow must be a two-dimensional closed manifold. What this boils down to is that every edge in a mesh must be shared by exactly two triangles, disallowing any holes that would let us see the interior of the mesh.

Edge connectivity information must be precomputed so that we can determine a mesh’s silhouette for shadow volume rendering. Suppose that we have an indexed triangle mesh consisting of an array of N vertices V₁,V₂,…,V_N and an array of M triangles T₁,T₂,…,T_M. Each triangle simply indicates which three vertices it uses by storing three integer indexes i₁, i₂, and i₃. We say that an index i_p precedes an index i_q if the number p immediately precedes the number q in the cyclic chain 1®2®3®1. For instance, i₂ precedes i₃ and i₃ precedes i₁, but i₂ does not precede i₁.

The indexes i₁, i₂, and i₃ are ordered such that the positions of the vertices V_i1, V_i2, and V_i3 to which they refer are wound counterclockwise about the triangle’s normal vector. Suppose that two triangles share an edge whose endpoints are the vertices V_a and V_b as shown in Figure 5. The consistent winding rule enforces the property that for one of the triangles, the index referring to V_a precedes the index referring to V_b, and that for the other triangle, the index referring to V_b precedes the index referring to V_a.

	Figure 5. When consistent winding is enforced, it is always the case that the indexes referring to the vertices Va and Vb of exactly one of the two triangles sharing an edge satisfies the property that the index referring to Va precedes the index referring to Vb.

As demonstrated in Listing 1, the edges of a triangle mesh can be identified by making a single pass through the triangle list. For any triangle having vertex indexes i₁, i₂, and i₃, we create an edge record for every instance in which i₁< i₂, i₂< i₃, or i₃< i₁and store the index of the current triangle in the edge record. This procedure creates exactly one edge for every pair of triangles that share two vertices V_a and V_b, duplicating any edges that are shared by multiple pairs of triangles.

Once we have identified all the edges, we make a second pass through the triangle list to find the second triangle that shares each edge. This is done by locating triangles for which i₁> i₂, i₂> i₃, or i₃> i₁ and matching it to an edge having the same vertex indexes that has not yet been supplied with a second triangle index.

Armed with the edge list for a triangle mesh, we determine the silhou¹ette by first calculating the dot product between the light position and the plane of each triangle. For a triangle whose vertex indexes are i₁, i₂, and i₃, the (unnormalized) outward-pointing normal direction N is given by

(12)

since the vertices are assumed to be wound counterclockwise. The 4D plane vector K corresponding to the triangle is then given by

(13)

Let L represent the 4D homogeneous position of the light source. For point light sources, L_W≠0, and for infinite directional light sources, L_W=0. A triangle faces the light source if K·L>0; otherwise, the triangle faces away from the light source. The silhouette is equal to the set of edges shared by one triangle facing the light and one triangle facing away from the light.

Shadow Volume Construction

Once the set of an object’s silhouette edges has been determined with respect to a light source, we must extrude each edge away from the light’s position to form the object’s shadow volume. In this section, we present methods that perform the extrusion by making use of widely available vertex programming hardware exposed by the GL_NV_vertex_program and GL_EXT_vertex_shader extensions to OpenGL.

For a point light source, the extrusion of the silhouette edges consists of a set of quads, each of which has the two unmodified vertices belonging to an edge and two additional vertices corresponding to the extrusion of the same edge to infinity. For an infinite directional light source, all points project to the same point at infinity, so the extrusion of the silhouette edges can be represented by a set of triangles that all share a common vertex. We distinguish between points that should be treated normally and those that should be extruded to infinity by using 4D homogeneous coordinates. A w-coordinate of one is assigned to the unmodified vertices and a w-coordinate of zero is assigned to the extruded vertices. The extrusion methods that we present utilize the information stored in the w-coordinate to perform the appropriate vertex modifications.

Before we examine the extrusion methods, we must prepare the appropriate quad list or triangle list (depending on whether we are using a point light or infinite directional light). We need to make sure that the vertices of each extrusion primitive are wound so that the face’s normal direction points out of the shadow volume. Suppose that a silhouette edge E has endpoints A and B. The edge-finding code presented in Listing 1 associates the triangle for which the vertices A and B occur in counterclockwise order as the first triangle sharing the edge E. Thus, if the first triangle faces toward the light source, then we want the vertices A and B to occur in the opposite order for the extruded primitive so that its vertices are wound counterclockwise. If the first triangle faces away from the light source, then we use the vertices A and B in the same order for the extruded primitive. Table 1 lists the vertices of the extrusion of the edge E for point light sources and infinite directional light sources for the cases that the first triangle associated with the edge E faces toward or away from the light source.

Table 1. Given a silhouette edge E having endpoints A and B, this table lists the object-space vertices of the extruded shadow volume face corresponding to E. The first triangle associated with the edge E is the triangle for which the vertices A and B occur in counterclockwise order.

Using the GL_NV_vertex_program extension, we can employ a couple simple vertex programs to perform edge extrusion and transformation to clip space. In each program, we assume that the product of the projection matrix and model-view matrix has been tracked into constant registers c[0]–c[3] and that the object-space light position has been stored in constant register c[4]. Vertex programs are enabled and these constants are loaded using the following function calls, where lx, ly, lz, and lw represent the light position.

glEnable(GL_VERTEX_PROGRAM_NV);
glTrackMatrixNV(GL_VERTEX_PROGRAM_NV, 0,
      GL_MODELVIEW_PROJECTION_NV, GL_IDENTITY_NV);
glProgramParameter4fNV(GL_VERTEX_PROGRAM_NV, 4, lx, ly, lz, lw);

For a point light source residing at the point L in object space, a vertex V from Table 1 is unmodified if its w-coordinate is one and is extruded if its w-coordinate is zero by using the formula

(14)

The following vertex program applies this formula and then transforms the resulting vertex position into clip space.

!!VP1.0
ADD       R0.xyz, v[OPOS], -c[4];
MAD       R0, v[OPOS].w, c[4], R0;
DP4       o[HPOS].x, c[0], R0;
DP4       o[HPOS].y, c[1], R0;
DP4       o[HPOS].z, c[2], R0;
DP4       o[HPOS].w, c[3], R0;
END

In the case that shadow volume caps must be rendered (see the next section), a vertex program nearly identical to the one above should be used to transform vertices belonging to triangles that face away from the light source. Such vertices can be treated as if their w-coordinates are zero, so the MAD instruction has no effect and can be removed when projecting a back cap.

For an infinite light source residing at the point L (having w-coordinate zero) in object space, a vertex V is unmodified or extruded by using the formula

(15)

The following vertex program applies this formula and then transforms the resulting vertex position V' into clip space.

!!VP1.0
ADD       R0, v[OPOS], c[4];
MAD       R0, v[OPOS].w, R0, -c[4];
DP4       o[HPOS].x, c[0], R0;
DP4       o[HPOS].y, c[1], R0;
DP4       o[HPOS].z, c[2], R0;
DP4       o[HPOS].w, c[3], R0;
END

The formulas given by Equations (14) and (15) can also be implemented using the GL_EXT_vertex_shader extension. Within our vertex shaders, we need to track model-view-projection matrix and the current vertex position, and we need to define an invariant corresponding to the object-space light position. Vertex shaders are enabled and these values are initialized using the following code, where lpos points to the first component of the light position.

glEnable(GL_VERTEX_SHADER_EXT);
GLuint mvp_matrix = glBindParameterEXT(GL_MVP_MATRIX_EXT);
GLuint vertex_pos = glBindParameterEXT(GL_CURRENT_VERTEX_EXT);
GLuint light_pos = glGenSymbolsEXT(GL_VECTOR_EXT,
      GL_INVARIANT_EXT, GL_FULL_RANGE_EXT, 1);
glSetInvariantEXT(light_pos, GL_FLOAT, &lpos);

For a point light source, Equation (14) can be implemented using the following vertex shader code, which also performs the transformation into clip space. We define a few temporary variables to hold intermediate results.

glBeginVertexShaderEXT();

GLuint temp1 = glGenSymbolsEXT(GL_VECTOR_EXT,
      GL_LOCAL_EXT, GL_FULL_RANGE_EXT, 1);
GLuint temp2 = glGenSymbolsEXT(GL_SCALAR_EXT,
      GL_LOCAL_EXT, GL_FULL_RANGE_EXT, 1);
GLuint swiz = glGenSymbolsEXT(GL_VECTOR_EXT,
      GL_LOCAL_EXT, GL_FULL_RANGE_EXT, 1);

glShaderOp2EXT(GL_OP_SUB_EXT, temp1, vertex_pos, light_pos);
glExtractComponentEXT(temp2, vertex_pos, 3);
glSwizzleEXT(swiz, temp1, GL_X_EXT, GL_Y_EXT,
      GL_Z_EXT, GL_ZERO_EXT);
glShaderOp3EXT(GL_OP_MADD_EXT, temp1, temp2, light_pos, swiz);
glShaderOp2EXT(GL_OP_MULTIPLY_MATRIX_EXT,
      GL_OUTPUT_VERTEX_EXT, mvp_matrix, temp1);

glEndVertexShaderEXT();

For an infinite light source, we can replace the operations performed in the point light case with the following code to implement Equation (15).

glShaderOp2EXT(GL_OP_ADD_EXT, temp1, vertex_pos, light_pos);
glExtractComponentEXT(temp2, vertex_pos, 3);
glSwizzleEXT(swiz, temp1, GL_NEGATIVE_X_EXT,
      GL_NEGATIVE_Y_EXT, GL_NEGATIVE_Z_EXT, GL_NEGATIVE_W_EXT);
glShaderOp3EXT(GL_OP_MADD_EXT, temp1, temp2, temp1, swiz);
glShaderOp2EXT(GL_OP_MULTIPLY_MATRIX_EXT,
      GL_OUTPUT_VERTEX_EXT, mvp_matrix, temp1);

join | contact us | advertise | write | my profile
news | features | companies | jobs | resumes | education | product guide | projects | store



Copyright © 2003 CMP Media LLC

privacy policy | terms of service