Contents  Fake Shadows  Vertex Projection  Shadow Z-Buffers  Shadow Volumes  Combining  Algorithms  Printable version  Discuss this article  in the forums

Combining Algorithms

Although this article presents only different algorithms, I thought it would be nice to let everyone know that many of these algorithms can be combined to form even better ways of doing things. I don’t mean just supporting several of them and using different algorithms for different situations. What I’m talking about is combining two or more algorithms into a single algorithm. For example, the Shadow Volume algorithm and the Shadow Z-Buffer algorithm can be combined into a single algorithm. Although this has been done already, there are more combinations possible. Another possibility would be to use the vertex projection technique on uneven surfaces; it would just take a little effort and ingenuity. Seeing as how it would be difficult to imagine combining these algorithms without an example, so I will present you with the combination shown above, the new algorithm is called Shadow Volume Reconstruction.

The basic algorithm is that you create a Z-Buffer from the point of view of the light (just like in the Shadow Z-Buffer algorithm). After that you run the light Z-Buffer that you just produced through an edge filter. This edge filter is then used to produce a silhouette polygon. The silhouette polygon is then used to create a shadow volume. This may seem a little excessive, but the results do look smoother than the usual Shadow Z-Buffer algorithm, and it is easier and faster than the Shadow Volume method.

Ok, now that you know the basics of the method, it’s time to go into a little depth. There are seven general steps to the Shadow Volume Reconstruction method. The first step is to render the shadow z-buffer. The next step is to render the scene from the standard camera view. The third step is to reset all of the buffers (the stencil buffer, the depth buffer, etc.). After resetting the buffers, you need to create the silhouette image. This can be done with a simple edge detection algorithm (see listing 6.1). By using the silhouette image you just created, you can now reconstruct the shadow volume. All that is left to do after creating the shadow volume is cap it, and then darken the shadowed pixels.

Listing 6.1

void edge_detect (int u[], int v[])
{
  int x, y;

  for (x=0; x<SCREEN_WIDTH; x++)
  {
    for (y=0; y<SCREEN_HEIGHT; y++)
    {
      u[x, y] = (|Dx z[x, y]| > q)
      v[x, y] = (|Dy z[x, y]| > q)
    }
  }
}

Where:

D_x z[x, y] = |z[x, y] - z[x + 1, y]|
D_y z[x, y] = |z[x, y] - z[x, y + 1]|

The first step is simple; you’ve done it before. You just render from the light’s point of view like you did in the Shadow Z-Buffer algorithm. The second step also follows the Shadow Z-Buffer algorithm. You just create the z-buffer as you normally would when rendering any scene. The next step is simply to make sure the data is correct. You reset the stencil buffer (this is used to determine whether an object is in shadow or not) and disable writing to the screen and z-buffers. The fourth step is when we start to deviate from the Shadow Z-Buffer method. What we need to do now is run the shadow map through an edge detection filter. This is fairly simple and doesn’t require an overly complex filter (an example of a suitable filter is presented in listing 6.1). Now is when things start to get a little complicated. What we need to do now is create a shadow volume based on the silhouette image. This can be done in two different ways. The first approach is to generate the parts of a mesh that touch at least one silhouette edge (this sounds confusing so take a look at figure 6.1). The second method is similar, only it uses a lookup table to determine what the mesh should look like. The lookup table would simple contain the 16 possible combinations of four adjacent pixels. This is also a confusing concept, so look at figure 6.2 to better understand what is going on.

Figure 6.1

Generating the mesh - Approach I

Figure 6.2

Generating the mesh - Approach II

Ok, so now that you have seen the algorithm, you might wonder what makes it better than any of the other algorithms. Well, this algorithm is a compromise; it doesn’t have the speed of the Shadow Z-Buffer method. However, it looks smoother, but not as smooth as the Shadow Volume method. It is an in-between, and it was intended to show that Shadow Volumes and Shadow Z-Buffers are similar and have different strengths that can be combined in a hybrid.

Conclusion

So, now that you have seen several different algorithms, and even a hybrid, you are ready to create your own shadows. These algorithms are not the only choices, the possibilities are endless, new algorithms could be created, or older algorithms could be combined. The sky is the limit.

Experiment! Only if you dare to be different and create your own methods will you make progress. Even if your method is not as fast or accurate, it is more than likely that it can be used as a stepping stone, for yourself and others, to make real-time shadows more accurate. So, don’t just sit there! Explore, create, expand, EXPERIMENT!

If you are inspired by this article and create a brand new algorithm, or just have an existing one you would like to let me know about, please send me an e-mail to let me know about it. Also, if this article was helpful to you in any way or you have any questions, suggestions, or comments, feel free to e-mail me at mike91285@aol.com.