Jump to content

  • Log In with Google      Sign In   
  • Create Account

Like
0Likes
Dislike

Real-Time Heightmap Self-Shadowing Using the Strider Technique

By Matthew Strahan | Published Jul 22 2004 07:29 AM in Game Programming

point shadow shadowed sun technique loop line shadows heightmap
If you find this article contains errors or problems rendering it unreadable (missing images or files, mangled code, improper text formatting, etc) please contact the editor so corrections can be made. Thank you for helping us improve this resource




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">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;



<span class="codecomment">//Get how far the decent is for each unit of distance.</span>

float yfor1dist = lightdirection.y /

                  (float(sqrt((lightdirection.x * lightdirection.x) +

                              (lightdirection.z * lightdirection.z))));



<span class="codecomment">//Set all points as unshadowed - start from a clean slate.</span>

for(z = 0; z < size * size; z++)

  shadowed[z] = false;





<span class="codecomment">//Loop away from the sun (from positive x)</span>

for(int x = size - 1; x > 0; x --)



{

  <span class="codecomment">//It doesn't matter which way this one goes.</span>

  for(z = 0; z < size; z++)

  {

    breakloop = false;

    wh = Height(x, z); //Working height

    cx = x;                        <span class="codecomment">//Current x point we're working with</span>

    cz = z;                        <span class="codecomment">//Current y point we're working with</span>

    if(!shadowed[x + (z * size)])  <span class="codecomment">//Skip if already shadowed</span>

    {

      while(!breakloop && (cx > 0) && (cz > 0))   <span class="codecomment">//Cast the line</span>

      {

        cx--;      <span class="codecomment">//We already know the line is diagonal.</span>

        cz--;      <span class="codecomment">//We just need to deincrement x and z to get the next point.</span>

        

        <span class="codecomment">//Just get the distance.</span>

        distance = (float)sqrt(((x - cx) * (x - cx)) + ((z - cz) * (z – cz)));

        

        ch = wh - (distance * yfor1dist);

        

        <span class="codecomment">//Find if the current height difference between line and point is smaller than 0</span>

        if(ch > Height(cx, cz))

          <span class="codecomment">//If it is, call it shadowed and continue</span>

          shadowed[cx + (cz * size)] = true;

        else

          <span class="codecomment">//Else, break the loop.</span>

          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:


  1. Find the direction of the sun (of course) to the accuracy of N S E W.
  2. Adjust the loop so that the loop cycles away from the sun.
  3. 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.








Comments

Note: Please offer only positive, constructive comments - we are looking to promote a positive atmosphere where collaboration is valued above all else.




PARTNERS