Home Shadows Shadow Volumes
Shadow Volumes

This tutorial is going to be about shadow volumes in openGL and how you can use them to create sharp shadows projected on any type of surface.

First of all what is a shadow volume? Imagine a source of light (a light bulb for instance) and a 3d object. The object casts a shadow on the floor. The shadow volume is the entire space determined by the object and the projection on the floor:

 

The shadow volume of a teapot

 


The basic steps for forming a shadow volume are:

  1. Find all silhouette edges (the edges of contour that if projected determine the shadow)
  2. Extend all silhouette edges in the direction away from the light-source
  3. Add a front-cap and/or back-cap to each surface to form a closed volume (this depends on what algorithm you use to create the shadow from the shadow volume)

 1. Find all silhouette edges

It is important not to extend all edges, but only silhouette edges! 

A silhouette must fulfill the following 3 conditions:

  • It must belong to a triangle visible in the light
  • it must be between a visible (in the light - illuminated) triangle and a triangle that is not visible in the light (not illuminated)
  • It must be taken only once

 

Determining if a triangle is illuminated or not is very easy:all you need to do is check the sign of the dot product between the direction of the light and the normal to the triangle. The real problem of this algorithm is that for each triangle you need to know the 3 neighboring triangle. This information is not in the exported 3D Studio Max model. You need to determine this based on the geometry. Basically for each edge you would find another edge that starts from one of the vertexes. The algorithm is simple but it's O(n^4) in complexity so it's not something you want to do each time you need to recalculate the shadow volume. I suggest modifying the structures that hold the geometry information to hold this extra peace of information. I did that the GLMmodel structure by adding an array of 3 ints in the GLMtriangle struct, each element pointing to a neighboring triangle.


Here is a bit of pseudo-code to help you understand it:


for each group/object in the model do

for each triangle i of the object do
for each triangle j other then i belonging to the object do
for each edge ki of triangle i do
for each edge kj of the triangle j do

determine if the edges ki and kj are made by the same vertexes (may be reverser of not). If they are mark the triangles i and j and being neighbors.

 

 If you are interested here is my implementation of this algorithm for the geometric structures defined in GLM library:

inline void SetConnectivity(GLMmodel *model, GLMgroup *o)
{
    int p1i, p2i, p1j, p2j;
    int P1i, P2i, P1j, P2j;
    int i,j,ki,kj;

    if (o->numtriangles==0) return;
    // for each triangle
    for(i=0;i<o->numtriangles-1;i++)
        // for each triangle next to i
        for(j=i+1;j<o->numtriangles;j++)
            // for each edge of triangle i
            for(ki=0;ki<3;ki++)
                //if the edge's neighbour is not set yet
                if(model->triangles[o->triangles[i]].vecini[ki]>1000000) //o->planes[i].neigh[ki])
                {
                    // for each edge of triangle j
    ��������������� for(kj=0;kj<3;kj++)
Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? {
Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? p1i=ki;
Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? p1j=kj;
Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? p2i=(ki+1)%3;
Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? p2j=(kj+1)%3;
Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?
Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? p1i=model->triangles[o->triangles[i]].vindices[p1i];
Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? p2i=model->triangles[o->triangles[i]].vindices[p2i];
Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? p1j=model->triangles[o->triangles[j]].vindices[p1j];
Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? p2j=model->triangles[o->triangles[j]].vindices[p2j];

Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? P1i=((p1i+p2i)-abs(p1i-p2i))/2;
Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? P2i=((p1i+p2i)+abs(p1i-p2i))/2;
Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? P1j=((p1j+p2j)-abs(p1j-p2j))/2;
Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? P2j=((p1j+p2j)+abs(p1j-p2j))/2;

Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? if((P1i==P1j) && (P2i==P2j))
Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? {Â? //neighbours
Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? model->triangles[o->triangles[i]].vecini[ki] = j;
Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? model->triangles[o->triangles[j]].vecini[kj] = i;
Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? }
Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? }
Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? }
}

 

I'd also recommend calculating whenever you surface is illuminated or not offline (when you load the object not when you need to know if it's in the light or not). This is good if your light sources don't change and the scene is relatively static. I added a boolean variable to the GLMtriangle struct to tell me this. To calculate it I first calculated the normals to the plane determined by the triangle and made the dot product between it and the direction of the light. Here is how I implemented this:

void CalculateVisibleTriangles(GLMmodel * model, GLMgroup *o, float *light)
{Â?Â?Â?

Â?Â?Â? for (int i=0;i<o->numtriangles;i++)
Â?Â?Â? {
Â?Â?Â? Â?Â?Â? int index = model->triangles[o->triangles[i]].vindices[0];
Â?Â?Â? Â?Â?Â? float x1 = model->vertices[index*3+0];
Â?Â?Â? Â?Â?Â? float y1 = model->vertices[index*3+1];
Â?Â?Â? Â?Â?Â? float z1 = model->vertices[index*3+2];
Â?Â?Â? Â?Â?Â?
Â?Â?Â? Â?Â?Â? index = model->triangles[o->triangles[i]].vindices[1];
        float x2 = model->vertices[index*3+0];
        float y2 = model->vertices[index*3+1];
        float z2 = model->vertices[index*3+2];
       
        index = model->triangles[o->triangles[i]].vindices[2];
        float x3 = model->vertices[index*3+0];
        float y3 = model->vertices[index*3+1];
        float z3 = model->vertices[index*3+2];
// plane equation: Ax + By + Cz + D = 0, with the normal (A,B,C)

        float A = y1 *(z2 - z3) + y2 *(z3 - z1) + y3 *(z1 - z2);
        float B = z1 *(x2 - x3) + z2 *(x3 - x1) + z3 *(x1 - x2);
        float C = x1 *(y2 - y3) + x2 *(y3 - y1) + x3 *(y1 - y2);
        float D = -(x1 *(y2* z3 - y3* z2) + x2 *(y3* z1 - y1* z3) + x3 *(y1 *z2 - y2 *z1));
       
        float side = A*light[0]+B*light[1]+C*light[2]+D*light[3];
        if (side >0) model->triangles[o->triangles[i]].visible = TRUE;
                else
                    model->triangles[o->triangles[i]].visible = FALSE;
    }
}

Now that we have all this information we can draw the shadow volume. First of all let me tell you that the shadow volume isn't normally drawn on the screen. For debuging purposes maybe. Usualy you draw it in some specials buffers other then COLLOR_BUFFER (screen) with different options in order to create the shadow effect. What you have seen in the image above is the shadow volume actualy drawn on the screen. Obviously that's of no use to use. We want to create a shadow effect. That effect can be done by calling the following function several times with different buffer settings. I will explain the techniques of rendering shadows from this shadow volume in the next tutorial (since it's going to be very long anyway and present 2 different methods of doing it).

Â?This is how I've drawn the shadow volume:

void makeShadowVolume(GLMmodel * shadower, GLfloat light[3], GLfloat t, GLint dlist, bool cap)
{
Â?Â? Â?int i;
Â?Â? Â?GLfloat newv[3];
Â?Â? Â?static GLMgroup* group;

Â?Â?Â? // don't draw directly - instead create a compiled list of operations that can be called at any time - this will increase the speed a lot!
Â?Â? Â?glNewList(dlist, GL_COMPILE);

Â? Â? Â? Â? // shadow volume is drawn in special conditions in different buffers - one of these conditions is NO LIGHTS Â?Â? Â? Â?Â?Â?Â?
Â?Â? Â?Â?Â? Â?glDisable(GL_LIGHTING);Â?Â?

Â? Â? Â? Â? // add a color for debugging purposes - if you ever wanted to see on the screen how the volumes looks like make it green Â? Â?Â?Â? Â?Â?Â?Â?
Â?Â? Â?Â?Â? Â?glColor3f(.2f, .8f, .4f);Â?
Â?Â? Â?Â?Â? Â?group = shadower->groups;
Â?Â? Â?Â?Â? Â?while (group) // for each object in the model do this
Â?Â? Â?Â?Â? Â?{Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?
Â?Â? Â?Â?Â? Â?Â?Â? Â?glColor3f(.2f, .8f, .4f);

Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? // we will create a quad from each sihloutte egde - the other 2 points of the quad are the extention in the direction of the light
Â?Â? Â?Â?Â? Â?Â?Â?Â? glBegin(GL_QUADS);Â?Â?Â?Â? Â? Â?Â?Â?Â?
Â?Â? Â?Â?Â? Â?Â?Â? Â?for (i = 0; i < group->numtriangles; i++)
Â?Â? Â?Â?Â? Â?Â?Â? Â?{
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?GLMtriangle * ctriangle = &shadower->triangles[group->triangles[i]];

Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? // if the triangle is not visible it doesn't respect the silhouette edge conditions
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?if (!ctriangle->visible) continue;
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?for (int j=0;j<3;j++) // for each edge
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?{
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?int k = ctriangle->vecini[j]; // get a neighbor

Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? // it must either not have a neighbor or a neighboring triangle that is not visible in the light
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â?Â? if (k==-1 || k>1000000 || shadower->triangles[group->triangles[k]].visible==false)
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?{
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?int e0 = j;
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?int e1 = j+1;
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â?Â?Â?Â?Â? Â?
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?if( e1 > 2 )
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?e1 = 0;
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?GLfloat *cvertex = &shadower->vertices[3*ctriangle->vindices[e0]];
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?glVertex3fv(cvertex);
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?extend(newv, light, cvertex, t);

Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? // get the extension to the infinite of the vertex in the direction of the light
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â?Â? glVertex3fv(newv);Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?cvertex = &shadower->vertices[3*ctriangle->vindices[e1]];

Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? // get the extension to the infinite of the vertex in the direction of the light
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â?Â? extend(newv, light, cvertex, t);
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?glVertex3fv(newv);
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?glVertex3fv(cvertex);Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?}
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?}
Â?Â? Â?Â?Â? Â?Â?Â? Â?}
Â?Â? Â?Â?Â? Â?Â?Â? Â?glEnd();

Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â?Â? // you only need to draw the cap if you use the depth fail (also known as Carmaks reverse) shadow algorithm
Â? Â? Â?Â?Â? Â?Â?Â?Â? if (cap)
Â?Â? Â?Â?Â? Â?Â?Â? Â?{
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?glColor3f(1.0f, .1f, .1f);
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?for (int a = 0; a < group->numtriangles; a++)
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?{Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?GLMtriangle * tt = &shadower->triangles[group->triangles[a]];
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?if (!tt->visible)
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?{
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?glBegin(GL_TRIANGLES);
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?//the near cap
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?// invert the normal by taking the vertexes in reverse order
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?for (int b=2;b>=0;b--)
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?{
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?GLfloat *v = &shadower->vertices[3*tt->vindices[b]];
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?glVertex3fv(v);
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?}Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?// the far cap
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?for (int b=0;b<3;b++)
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?{
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?GLfloat *v = &shadower->vertices[3*tt->vindices[b]];
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?extend(newv, light, v, t);
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?glVertex3fv(newv);
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?}
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?glEnd();
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?}
Â?Â? Â?Â?Â? Â?Â?Â? Â?Â?Â? Â?}

Â?Â? Â?Â?Â? Â?Â?Â? Â?}
Â?Â? Â?Â?Â? Â?Â?Â? Â?group = group->next;
Â?Â? Â?Â?Â? Â?}Â?Â? Â?Â?Â? Â?
Â?Â? Â?Â?Â? Â?glEnable(GL_LIGHTING);Â?Â? Â?
Â?Â? Â?glEndList();
}

 

You have noticed that the above function draws a quad for each silhoutte edge. Two of the points belong to the edge and the other two to the projection of the edge at infinit in the direction of the light. Here is the function that calculate this extention:

/* simple way to extend a point to build shadow volume */
void extend(GLfloat nou[3], GLfloat light[3], GLfloat vertex[3], GLfloat t)
{
Â? GLfloat delta[3];

Â? delta[X] = vertex[X] - light[X];
Â? delta[Y] = vertex[Y] - light[Y];
Â? delta[Z] = vertex[Z] - light[Z];

Â? nou[X] = light[X] + delta[X] * t;
Â? nou[Y] = light[Y] + delta[Y] * t;
Â? nou[Z] = light[Z] + delta[Z] * t;
}

 

That's about it. In the next tutorial I will explain how this shadow volume can be use to create realistic shadows for 3D object on any surface and even on itself.

 
Copyright © 2012 Tudor Carean. All Rights Reserved.