Shadow volumes

The purpose of this project was to provide a straightforward implementation of shadow volumes using the depth fail approach. The project is divided into the following sections:

  • After loading an object, detect duplicate vertices.
  • Build the object's edge list while identifying each face associated with an edge.
  • Identify the profile edges from the perspective of the light source.
  • Create the quadrilaterals defining the shadow volume by extruding the profile edges.
  • Create the shadow volume caps on either end of the shadow volume.
  • Render the scene utilizing the stencil buffer.
  • Final notes.
Shadow volumes.

Shadow volumes.

Shadow volumes (animated).

Shadow volumes (animated).

Shadow volumes.

Shadow volumes.

Identifying duplicate vertices.
This project employs Assimp to load a 3d model. Upon loading a model, any faces that may have used similar vertices now all have unique vertices. We first identify those vertices which are identical. This will allow us to identify the two faces sharing an edge. In the project code the aiMeshStats() function loads the model and then maps the similar vertices using the following loop:

	for (int i = 0; i < vertices.size(); i++) {
		for (int j = 0; j <= i; j++) {
			if (distance2(vertices[j].x, vertices[j].y, vertices[j].z,
				      vertices[i].x, vertices[i].y, vertices[i].z) < 0.000001) {
				vertices[i].v = j;
				break;
			}
		}
	}

The v property is a reference to either a previous vertex or itself if no similar vertex exists.

Building the edge list.
An edge list for our model is constructed by looping over the model faces (triangles). We use the v property identified above.

One crucial item to note is if and are two faces sharing an edge containing vertices, and , then if contains those vertices in the order, , then will contain those vertices in the order, . This is why we swap the vertex order when we first push the edge onto the list.

	__edge edge;
	for (int i = 0, f = 0; i < indices.size(); i+=3, f++) {
		int v0 = vertices[indices[i+0]].v;
		int v1 = vertices[indices[i+1]].v;
		int v2 = vertices[indices[i+2]].v;

		int e0 = findEdge(edges, v0, v1);
		if (e0 > -1) {
			edges[e0].f1 = f;
		} else {
			edge.v0 = v1;
			edge.v1 = v0;
			edge.f0 = f;
			edge.f1 = -1;
			edges.push_back(edge);
		}
		
		int e1 = findEdge(edges, v1, v2);
		if (e1 > -1) {
			edges[e1].f1 = f;
		} else {
			edge.v0 = v2;
			edge.v1 = v1;
			edge.f0 = f;
			edge.f1 = -1;
			edges.push_back(edge);
		}
		
		int e2 = findEdge(edges, v2, v0);
		if (e2 > -1) {
			edges[e2].f1 = f;
		} else {
			edge.v0 = v0;
			edge.v1 = v2;
			edge.f0 = f;
			edge.f1 = -1;
			edges.push_back(edge);
		}
	}		

The findEdge() function is defined below:

int findEdge(std::vector<__edge>& edges, int v0, int v1) {
	for (unsigned int i = 0; i < edges.size(); i++)
		if (v0 == edges[i].v0 && v1 == edges[i].v1)
			return i;
	return -1;
}

Identifying the profile edges.
In the following code we loop over our edge list, extract the indices and vertices for each face the edge identifies, and create a vector from the light source to each of the two faces. For each face, we find the inner product of the vector from the light source to the face and the face normal. This will allow us to identify whether each face is facing away from or towards the light source. If one face is facing away and the other towards, then this edge is part of the profile and will be an edge we extrude to create a quadrilateral for rendering the shadow volume.

Also note that we must push the vertices onto the profile list in the correct order. This order is defined by which face is facing towards the light source. This order becomes critical when we implement the stencil buffer.

	for (int i = 0; i < edges.size(); i++) {
		if (edges[i].f0 > -1 && edges[i].f1 > -1) {
		
			int i0_0 = edges[i].f0 * 3 + 0;
			int i1_0 = edges[i].f0 * 3 + 1;
			int i2_0 = edges[i].f0 * 3 + 2;

			int i0_1 = edges[i].f1 * 3 + 0;
			int i1_1 = edges[i].f1 * 3 + 1;
			int i2_1 = edges[i].f1 * 3 + 2;

			int v0_0 = indices[i0_0];
			int v1_0 = indices[i1_0];
			int v2_0 = indices[i2_0];
		  
			int v0_1 = indices[i0_1];
			int v1_1 = indices[i1_1];
			int v2_1 = indices[i2_1];
			
			vector3 p0_0(vertices[v0_0].x, vertices[v0_0].y, vertices[v0_0].z);
			vector3 p1_0(vertices[v1_0].x, vertices[v1_0].y, vertices[v1_0].z);
			vector3 p2_0(vertices[v2_0].x, vertices[v2_0].y, vertices[v2_0].z);
			
			vector3 p0_1(vertices[v0_1].x, vertices[v0_1].y, vertices[v0_1].z);
			vector3 p1_1(vertices[v1_1].x, vertices[v1_1].y, vertices[v1_1].z);
			vector3 p2_1(vertices[v2_1].x, vertices[v2_1].y, vertices[v2_1].z);

			vector3 v_0 = ((p0_0 + p1_0 + p2_0) * (1.0/3.0) - light_pos).unit();
			vector3 v_1 = ((p0_1 + p1_1 + p2_1) * (1.0/3.0) - light_pos).unit();

			vector3 n_0 = (p1_0 - p0_0).cross(p2_0 - p0_0).unit();
			vector3 n_1 = (p1_1 - p0_1).cross(p2_1 - p0_1).unit();

			if ((v_0*n_0) * (v_1*n_1) < 0) {
				if (v_0*n_0 < 0) {
					profile_indices.push_back(edges[i].v1);
					profile_indices.push_back(edges[i].v0);
				} else {
					profile_indices.push_back(edges[i].v0);
					profile_indices.push_back(edges[i].v1);
				}
			}
		}
	}

Extruding the profile edges.
With the profile edge list in hand, we extrude each edge vertex away from the light source to create a quadrilateral. These vertices should be extruded to infinity. The code below only extrudes the vertices by 100.0 units because this was sufficient to pass through the plane.

	for (unsigned int i = 0; i < profile_indices.size(); i+=2) {
		__vertex v;
		v.nx = v.ny = v.nz = 1.0;
		v.r  = v.g  = v.b  = 0.0;
		v.tx = v.ty = v.tz = 0.0;

		int i0 = profile_indices[i+0];
		int i1 = profile_indices[i+1];
		
		vector3 p0(vertices[i0].x, vertices[i0].y, vertices[i0].z);
		vector3 p1(vertices[i1].x, vertices[i1].y, vertices[i1].z);	
		
		vector3 l0 = (p0 - light_pos).unit();
		vector3 l1 = (p1 - light_pos).unit();
		
		v.x = p0.x;
		v.y = p0.y;
		v.z = p0.z;
		edge_vertices.push_back(v);
		edge_indices.push_back(edge_indices.size());
		
		vector3 ep0 = p0 + l0 * 100.0;
		v.x = ep0.x;
		v.y = ep0.y;
		v.z = ep0.z;
		edge_vertices.push_back(v);
		edge_indices.push_back(edge_indices.size());
		
		vector3 ep1 = p1 + l1 * 100.0;
		v.x = ep1.x;
		v.y = ep1.y;
		v.z = ep1.z;
		edge_vertices.push_back(v);
		edge_indices.push_back(edge_indices.size());
		
		v.x = p1.x;
		v.y = p1.y;
		v.z = p1.z;
		edge_vertices.push_back(v);
		edge_indices.push_back(edge_indices.size());
	}

Create the shadow volume caps.
The next step is to complete the shadow volume by adding a near cap and a far cap. The near cap is created from the set of all triangles facing the light source. To create the far cap, from the set of all triangles facing away from the light source, each triangles is projected away from the light source by the same distance the profile edges were extruded.

	for (int i = 0; i < indices.size(); i+=3) {
		vector3 p0(vertices[indices[i+0]].x, vertices[indices[i+0]].y, vertices[indices[i+0]].z);
		vector3 p1(vertices[indices[i+1]].x, vertices[indices[i+1]].y, vertices[indices[i+1]].z);
		vector3 p2(vertices[indices[i+2]].x, vertices[indices[i+2]].y, vertices[indices[i+2]].z);
		vector3 l = ((p0 + p1 + p2) * (1.0/3.0) - light_pos).unit();
		vector3 n = (p1 - p0).cross(p2 - p0).unit();
		__vertex v;
		v.nx = v.ny = v.nz = 1.0;
		v.r  = v.g  = v.b  = 0.0;
		v.tx = v.ty = v.tz = 0.0;
		if (l*n < 0) {
			v.x = p0.x;
			v.y = p0.y;
			v.z = p0.z;
			near_cap_vertices.push_back(v); near_cap_indices.push_back(near_cap_indices.size());
			
			v.x = p1.x;
			v.y = p1.y;
			v.z = p1.z;
			near_cap_vertices.push_back(v); near_cap_indices.push_back(near_cap_indices.size());
			
			v.x = p2.x;
			v.y = p2.y;
			v.z = p2.z;
			near_cap_vertices.push_back(v); near_cap_indices.push_back(near_cap_indices.size());
		} else {
			p0 = p0 + (p0 - light_pos).unit() * 100.f;
			p1 = p1 + (p1 - light_pos).unit() * 100.f;
			p2 = p2 + (p2 - light_pos).unit() * 100.f;

			v.x = p0.x;
			v.y = p0.y;
			v.z = p0.z;
			far_cap_vertices.push_back(v); far_cap_indices.push_back(far_cap_indices.size());
			
			v.x = p1.x;
			v.y = p1.y;
			v.z = p1.z;
			far_cap_vertices.push_back(v); far_cap_indices.push_back(far_cap_indices.size());
			
			v.x = p2.x;
			v.y = p2.y;
			v.z = p2.z;
			far_cap_vertices.push_back(v); far_cap_indices.push_back(far_cap_indices.size());
		}
	}

Rendering the scene.
The first step in rendering the scene is to render it as though everything were in shadow. We then render the shadow volume using the depth fail approach. Finally, we render the scene as though it were fully lit.

The glStencilOpSeparate() method is utilized to implement the depth fail approach. For each back facing quadrilateral we increment the stencil buffer when the depth test fails. The stencil buffer is increased upon depth fail for each front facing quadrilateral.

Note that we also set the depth test function to GL_LESS.

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// render the scene in shadow
		glEnable(GL_DEPTH_TEST);
		glDisable(GL_STENCIL_TEST);

		glStencilMask(0xFF);
		glDepthMask(GL_TRUE);
		glColorMask(GL_TRUE, GL_TRUE, GL_TRUE, GL_TRUE);

		glBindBuffer(GL_ARRAY_BUFFER, vbo_vertices);
		glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, ibo_indices);
		glEnableVertexAttribArray(vertex);
		glVertexAttribPointer(vertex, 3, GL_FLOAT, GL_FALSE, sizeof(__vertex), (char *)NULL +  0);
		glEnableVertexAttribArray(normal);
		glVertexAttribPointer(normal, 3, GL_FLOAT, GL_FALSE, sizeof(__vertex), (char *)NULL + 12);
		glEnableVertexAttribArray(color);
		glVertexAttribPointer(color,  3, GL_FLOAT, GL_FALSE, sizeof(__vertex), (char *)NULL + 24);
		glUniform1f(color_factor, 0.6f);
		glDrawElements(GL_TRIANGLES, indices.size(), GL_UNSIGNED_INT, 0);
		
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// update the stencil buffer
		glEnable(GL_DEPTH_TEST);
		glEnable(GL_STENCIL_TEST);

		glStencilFunc(GL_ALWAYS, 1, 0xFF);
		glStencilOpSeparate(GL_BACK, GL_KEEP, GL_INCR_WRAP, GL_KEEP);
		glStencilOpSeparate(GL_FRONT, GL_KEEP, GL_DECR_WRAP, GL_KEEP);
		glStencilMask(0xFF);
		glDepthMask(GL_FALSE);
		glColorMask(GL_FALSE, GL_FALSE, GL_FALSE, GL_FALSE);

		buildShadowQuads(light_pos, vertices, indices, edges, edge_vertices, edge_indices, profile_indices, far_cap_vertices, far_cap_indices, near_cap_vertices, near_cap_indices);
		
		
// render the sides of the shadow volume
		glBindBuffer(GL_ARRAY_BUFFER, vbo_edge_vertices);
		glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, ibo_edge_indices);
		glBufferData(GL_ARRAY_BUFFER, sizeof(__vertex) * edge_vertices.size(), &edge_vertices[0], GL_DYNAMIC_DRAW);
		glBufferData(GL_ELEMENT_ARRAY_BUFFER, sizeof(GLuint) * edge_indices.size(), &edge_indices[0], GL_DYNAMIC_DRAW);

		glEnableVertexAttribArray(vertex);
		glVertexAttribPointer(vertex, 3, GL_FLOAT, GL_FALSE, sizeof(__vertex), (char *)NULL +  0);
		glEnableVertexAttribArray(normal);
		glVertexAttribPointer(normal, 3, GL_FLOAT, GL_FALSE, sizeof(__vertex), (char *)NULL + 12);
		glEnableVertexAttribArray(color);
		glVertexAttribPointer(color,  3, GL_FLOAT, GL_FALSE, sizeof(__vertex), (char *)NULL + 24);
		glUniform1f(color_factor, 1.f);
		glDrawElements(GL_QUADS, edge_indices.size(), GL_UNSIGNED_INT, 0);

// render the near cap of the shadow volume
		glBindBuffer(GL_ARRAY_BUFFER, vbo_near_cap_vertices);
		glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, ibo_near_cap_indices);
		glBufferData(GL_ARRAY_BUFFER, sizeof(__vertex) * near_cap_vertices.size(), &near_cap_vertices[0], GL_DYNAMIC_DRAW);
		glBufferData(GL_ELEMENT_ARRAY_BUFFER, sizeof(GLuint) * near_cap_indices.size(), &near_cap_indices[0], GL_DYNAMIC_DRAW);

		glEnableVertexAttribArray(vertex);
		glVertexAttribPointer(vertex, 3, GL_FLOAT, GL_FALSE, sizeof(__vertex), (char *)NULL +  0);
		glEnableVertexAttribArray(normal);
		glVertexAttribPointer(normal, 3, GL_FLOAT, GL_FALSE, sizeof(__vertex), (char *)NULL + 12);
		glEnableVertexAttribArray(color);
		glVertexAttribPointer(color,  3, GL_FLOAT, GL_FALSE, sizeof(__vertex), (char *)NULL + 24);
		glUniform1f(color_factor, 1.f);
		glDrawElements(GL_TRIANGLES, near_cap_indices.size(), GL_UNSIGNED_INT, 0);
		
// render the far cap of the shadow volume
		glBindBuffer(GL_ARRAY_BUFFER, vbo_far_cap_vertices);
		glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, ibo_far_cap_indices);
		glBufferData(GL_ARRAY_BUFFER, sizeof(__vertex) * far_cap_vertices.size(), &far_cap_vertices[0], GL_DYNAMIC_DRAW);
		glBufferData(GL_ELEMENT_ARRAY_BUFFER, sizeof(GLuint) * far_cap_indices.size(), &far_cap_indices[0], GL_DYNAMIC_DRAW);

		glEnableVertexAttribArray(vertex);
		glVertexAttribPointer(vertex, 3, GL_FLOAT, GL_FALSE, sizeof(__vertex), (char *)NULL +  0);
		glEnableVertexAttribArray(normal);
		glVertexAttribPointer(normal, 3, GL_FLOAT, GL_FALSE, sizeof(__vertex), (char *)NULL + 12);
		glEnableVertexAttribArray(color);
		glVertexAttribPointer(color,  3, GL_FLOAT, GL_FALSE, sizeof(__vertex), (char *)NULL + 24);
		glUniform1f(color_factor, 1.f);
		glDrawElements(GL_TRIANGLES, far_cap_indices.size(), GL_UNSIGNED_INT, 0);

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// render the scene fully lit
		glEnable(GL_DEPTH_TEST);
		glEnable(GL_STENCIL_TEST);

		glStencilFunc(GL_EQUAL, 0, 0xFF);
		glStencilOpSeparate(GL_BACK, GL_KEEP, GL_KEEP, GL_KEEP);
		glStencilOpSeparate(GL_FRONT, GL_KEEP, GL_KEEP, GL_KEEP);
		glStencilMask(0xFF);
		glDepthMask(GL_TRUE);
		glClear(GL_DEPTH_BUFFER_BIT);
		glColorMask(GL_TRUE, GL_TRUE, GL_TRUE, GL_TRUE);
		
		glBindBuffer(GL_ARRAY_BUFFER, vbo_vertices);
		glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, ibo_indices);
		glEnableVertexAttribArray(vertex);
		glVertexAttribPointer(vertex, 3, GL_FLOAT, GL_FALSE, sizeof(__vertex), (char *)NULL +  0);
		glEnableVertexAttribArray(normal);
		glVertexAttribPointer(normal, 3, GL_FLOAT, GL_FALSE, sizeof(__vertex), (char *)NULL + 12);
		glEnableVertexAttribArray(color);
		glVertexAttribPointer(color,  3, GL_FLOAT, GL_FALSE, sizeof(__vertex), (char *)NULL + 24);
		glUniform1f(color_factor, 1.f);
		glDrawElements(GL_TRIANGLES, indices.size(), GL_UNSIGNED_INT, 0);

Final notes.
The object that is used to project a shadow volume must have exactly two faces for each edge.

This project includes a dynamic light, so we must update our shadow volume whenever the light's position changes. This is all done on the CPU, but a more efficient implementation would push as much of the shadow volume creation to the GPU as possible.

This project is available for download here: shadow_volumes.tar.bz2

The download is 43MB. It includes the source for Assimp 3.1.1 and GLM 0.9.2.6. You may need to rebuild Assimp.

Leave a Reply

Your email address will not be published. Required fields are marked *