Real-Time Heightmap Self-Shadowing Using the Strider Technique
by Matthew Strahan

Pictures taken from my demo illustrating dynamic terrain creation, entered into the NeHe Creative competition.

Introduction

Good real-time shadowing of heightmaps is hard and, using a traditional ray-tracing technique I have seen at http://www.gamedev.net/reference/articles/article1817.asp, takes a lot of CPU. In preparation of a demo I have made I created a method of realtime heightmap shadowing that I have dubbed the "Strider Technique", and should run on all modern hardware at great framerates. The difference should be unnoticeable especially when spread over several frames, while the results are definitely impressive. The technique currently relies on the source being directional, and though I will also give suggestions on how to adapt it to point lighting, I have not done any successful implementation of this kind of light. The technique can be used for any kind of heightmap, be it displacement- or bump-mapping, though bumpmapping is almost never used with directional sources.

The Strider Technique comprises of the basic reverse of the similar raytracing technique. It's similar to the shadow volume method of casting model shadows, in that it casts lines from the top of hills to test if points below are shadowed. It progresses along each row away from the light source, drawing a line from the top of the hills to the end of the shadow with all points that line passes being flagged flagged "shadowed" and skipped when the loop comes to them.

This is quite simple and easy to implement, though can be complicated when the sun's direction is ambiguous.

A Simple implementation

This is the C++ code for a simple implementation for this shadowing algorithm. It assumes that the sun is on a specific diagonal, simplifying things so you can get a good feel of how to implement a full blown implementation giving an ambiguous sun direction.

int z, cx, cz;
float distance, wh, ch;
bool breakloop;

//Get how far the decent is for each unit of distance.
float yfor1dist = lightdirection.y /
                  (float(sqrt((lightdirection.x * lightdirection.x) +
                              (lightdirection.z * lightdirection.z))));

//Set all points as unshadowed - start from a clean slate.
for(z = 0; z < size * size; z++)
  shadowed[z] = false;


//Loop away from the sun (from positive x)
for(int x = size - 1; x > 0; x --)

{
  //It doesn't matter which way this one goes.
  for(z = 0; z < size; z++)
  {
    breakloop = false;
    wh = Height(x, z); //Working height
    cx = x;                        //Current x point we're working with
    cz = z;                        //Current y point we're working with
    if(!shadowed[x + (z * size)])  //Skip if already shadowed
    {
      while(!breakloop && (cx > 0) && (cz > 0))   //Cast the line
      {
        cx--;      //We already know the line is diagonal.
        cz--;      //We just need to deincrement x and z to get the next point.
        
        //Just get the distance.
        distance = (float)sqrt(((x - cx) * (x - cx)) + ((z - cz) * (z – cz)));
        
        ch = wh - (distance * yfor1dist);
        
        //Find if the current height difference between line and point is smaller than 0
        if(ch > Height(cx, cz))
          //If it is, call it shadowed and continue
          shadowed[cx + (cz * size)] = true;
        else
          //Else, break the loop.
          breakloop = true;
      }
    }
  }
}

You may notice that several parts of this code, such as finding the exact distance instead of just incrementing the distance by 1.414 (square root of two) each loop, are not necessary unless there is an ambiguous light source, and this code can definitely be more optimized with that restriction, so this should be considered only as an example. I hope, however, that the commenting is clear about what it's doing.

Now to modify this simple algorithm to include an ambiguous sun direction you need to:

Find the direction of the sun (of course) to the accuracy of N S E W.
Adjust the loop so that the loop cycles away from the sun.
Cast the line so it is parallel to the sun's rays.

I have pretty much judged myself not a good enough programmer to even pretend that I can make a good readable set of code implementing this. The implementation I have created doing this, though the results look pretty enough, is bloated and unreadable, so I have not included it here.

Discussion

Edges of the Shadowing

The main problem with the ST is that it, like it is up there, looks so damned ugly close up! The next picture illustrates:

The shadow edges there are jagged. This is because the shadow only has as much a resolution as the heightmap itself, and the edges follow the points in the heightmap. This can be fixed with a band-aid by having the program check each unshadowed point to see if it borders on a shadow and adjust the shading if it's on an edge (the way I fixed my demo :P), though this gives ridiculously soft shadows and for shadows of only one point, the four/eight (depending on your anti-aliasing matrix) are also slightly shadowed looking unrealistic. I currently have no hard answers but I do have a couple of possibilities that someone else may like to try:

Use a pixel shader to draw a diagonal line when points in an L shape are detected or
Use a type of multisampling, giving a much higher resolution to the heightmap or
Both

Note that the second solution uses more than twice or four times (depending on whether you are using 2x or 4x multisampling) both cpu and memory.

Point Lights

I have not yet successfully implemented point lights. For point lights off the heightmap, it seems easy to slightly modify the implementation for the different gradients of the rays of light, yet for the larger shadows the lines find themselves diverging. The silhouette of the hill would thus give a shadow of many lines that fan out, not a complete shadow. The full shadows appear spotty on the side of the mountain (as the first unshadowed point shadows others and this loop continues) and the ends of the shadow appear overly jagged. (You may have to have a good imagination to see why.)

If this problem is conquered, then point lights should be quite feasible for terrain self-shadowing. For point lights over the terrain the loop would have to spiral or circle out, casting shadows this way.

Gradual Updating

If the sun is treated as the directional light source used in this algorithm, the algorithm can easily be done over several frames, requiring only slight amounts of CPU time each frame, however the catch is that the terrain cannot be updated gradually, since the algorithm requires a refresh of the array telling whether a point is shadowed or not, like the rendering of double buffers from a video card. As a result, gradual updating is usually fine with a slow moving source like the sun, but you have to make sure the time it takes to update gives a shadow change of at max one point.

Conclusion

The Strider Technique is quite adaptable and implementable, especially in light of it's speed advantage to other techniques. It's quite an elegant method of terrain self shadowing, giving great results.

I would love to hear of any implementations of this technique. Perhaps I will be a pioneer of a shadowing algorithm used everywhere it can – what has John Carmack done over the last couple of years? It is a joke . . . you are supposed to laugh.

Written By Matthew Strahan
Student of Software Engineering at University of New South Wales, Australia
e-mail: strider@strategyplanet.com
I'll be glad to hear any questions, comments, or of any examples!

See the demo that this was developed for at nehe.gamedev.net under the Creative Competition.

Discuss this article in the forums

Date this article was posted to GameDev.net: 7/22/2004
(Note that this date does not necessarily correspond to the date the article was written)