Terrain, Part 6

By Shamus Posted Friday Feb 10, 2006

Filed under: Programming 11 comments

Lighting & Shadows

Work continues on the terrain engine. Part one is available here.

Now comes a moment where I have to make a major choice that will affect many decisions down the road. I want to add shadows, so that the hills can cast shadows on one another. Shadows are very striking and add a great deal of realisim, but they come at a significant price.

Up until now I haven’t really worried about lighting. My program tells OpenGL “The sunlight is such-and-such color and is shining from this direction, the ground is this color.” OpenGL then takes all those numbers and crunches them for me, making light fall on the terrain. Hills have a light side and a dark side and everything looks pretty. This took about two minutes to set up and takes up just a few lines of code. It’s easy, simple, and effective. All this simplicity comes at a price, of course. The downside to all of this is that the lighting in OpenGL isn’t very flexible. It lights things. It can’t do shadows. If it could, then it wouldn’t be so simple to use.

As it stands, I can’t really add shadows to the existing OpenGL lighting paradigm. This is all or nothing. The upshot is that if I want shadows, I have to write my own lighting code. All that nice stuff OpenGL is doing for me, all the lighting, is now in my hands. I have to add a ton of new code just to get my program to do what OpenGL was already doing. This isn’t hard, but it is a lot of new code and complexity just to duplicate what was already being done. Once that code is done, then I can add shadows.

So, I replace the built-in lighting with my own:

For this image, the sun is very low on the horizon, and I exaggerated the height of the mountains. I was going to have a side-by side comparison here of the new and old lighting systems. I didn’t make any effort to make sure my system would come up with the exact same results as OpenGL. I expected this would lead to slight variations in lighting. Turns out they look exactly the same anyway.

And now it’s time to add shadows. Originally I was going to implement a system where my program does what is called line-of-sight checking. This would work by tracing a line from a given spot on the terrain towards the sun. If the line intersects with any polygon, then something is blocking the sun and the spot is assumed to be in shadow. This would work fine, although it can get a little CPU intensive. Checking to see if an arbitrary line intersects with any of my half-million polygons can get out of hand very quickly.

Then I thought of an interesting shortcut: What if I make the assumption that the sun will only travel east / west and never be angled to the north or south? If I did this, then I wouldn’t have to do all the fancy polygon-checking.

Let’s say the sun is shining from the west. The western most point on the map cannot therefore be in shadow, since there is nothing to the left of this first point. The sun is striking it. I save the height of this point as my “everything below this point is in shadow”. Just so I don’t have to type that out every time, let’s call it EBTPIIS.

If the sun was right on the horizon, then the next point over would need to be higher than EBTPIIS to get any sunlight. However, if the sun is coming down at an angle then EBTPIIS needs to be lowered every time we move to the next point. If the sun was coming down at a forty-five degree angle, EBTPIIS would drop by exactly one unit, which is how far apart the points are horizontally. If this next point is above EBTPIIS, then the point is in sunlight and EBTPIIS will be set to the height of this new point. If the point is below EBTPIIS, then the point is in shadow and EBTPIIS remains unchanged. I pass over a single row of the terrain grid like this, moving from west to east. (If the sun is coming from the east, I pass over the grid in the other direction). The result is something like this:

The blue lines mark the height of EBTPIIS.

I know the explanation might sound odd, but these calculations are very, very fast. This is at least ten times faster than line-of-sight checking. It is also far simpler to code. The only drawback is, as I mentioned before, is that the sunlight will only work on the plane defined by the east-west and up-down axis. I couldn’t use this system if I wanted the sun to come from the northwest, for example. This is a pretty minor tradeoff. I’m happy with how this turned out.

Now with shadows!

Judging Performance

One of the problems I face on a project like this is figuring out what the various tradeoffs are. I mentioned a while ago out the quality vs. speed tradeoff. I can use less polygons and make the framerate better at the expense of visual quality. But the tradoff is non-linear. Very non-linear. So, finding the sweet spot is tricky. Let’s have a look.

For the purposes of this experiment, I made the terrain much larger and the hills very extreme. This creates a worst-case scenario, which will make the tradeoffs more obvious. So, this time my terrain is 1024 x 1024 squares. Thats 2,097,152 polygons. Ouch! Two million and change.

In the above image I turned the optimization down to almost nothing. This terrain is a stunning 2,095,088 polygons. This thing is a lot to render. My 2-year-old computer actually has trouble with this. My framerate is just a little better than 10fps.

Now I turn it up a bit and the polygon count drops to 1,078,685. I just cut out half of the polygons from the previous image. I can’t even tell the difference. So, we cut poly count in half and lost no quality.

In this image we are down to 461,121 polys. At about half a million, I have once again cut the poly count in half. This time however, we can just barely see the difference. It still looks great, though, and my framerate is smooth again.

I cut poly count in half again, down to 249,033. At a quarter million, it still looks good, but the quality loss is visible now.

Half again. Down to 112,225. We are getting to the point where each step down is taking more and more away from quality. I think this one and the previous one encompas the high and low end of the “sweet spot” on the curve. If this were a game, there would no doubt be some “quality” or “detail” sliders in the options. I would tune things so that high detail would produce the last image, and low detail would yield this one.

51,066. It’s starting to look very bland. The black dots are shadows, which are still appearing even though the hills that created those shadows have been removed. This is unavoidable, unless I want to make the shadow-casting code much more complex. It would not make sense to improve the shadow code so that shadows can look great on horrible terrain. That is just not a good investment of time.

And here we are near the bottom at 21,539. Obviously the thing looks totally unacceptable now. We’re down to 1% of the original poly count, but the cost to quality is so severe that we are clearly way past the sweet spot.

This data reinforces what I’ve suspected for a while now: You can dump 85% to 90% of the terrain polygons and get acceptable results, but once you dip below this point by even a few percent the cost in quality becomes pretty drastic.


From The Archives:

11 thoughts on “Terrain, Part 6

  1. Zenja says:

    I’m really enjoying these articles about terrain rendering. It’s a great coincidence, since I too am wrestling around the terrain rendering aspects of a RTS I’m developing. Cant wait to see how much our designs/implementations will differ/be similar.

    Wait until you start populating objects into the world…

  2. Shamus says:

    Thanks. I’m glad someone is enjoying these. Good luck on your own project as well.

  3. Waista says:

    OMG! Bigfoot sighting! In the gully to the right of the centre two peaks. Even though the resolution is way too low, I’m going to file this as conclusive proof.

    Great articles by the way. Thanks.

  4. Richard Braakman says:

    You know, I actually like the last picture (with 1% of the polygons) better than the earlier ones. It looks like grasslands between hills, with a convincing amount of erosion. I can almost see the sheep grazing.

    It might not be the terrain you had in mind, but it does look better! Now you just need to fix the shadows…

  5. yoron says:

    Yes, you made a very concice and clear explanation of how to do/create a 3D map and render it so far.
    Very cool :)


  6. Incognito says:

    I agree with richard, I like the last image better. I’m realling enjoying your work!

  7. Piero says:

    Hi Shamus,

    nice work, very similar to the hobby project I started lately. Did you improve anything in the while?
    Please have a look to mine: http://www.youtube.com/watch?v=LPAGmfcy1H0


  8. Neil Roy says:

    Very nice work. I created a similar project, probably around the same time you did this article many years ago now. Only, actually started with a 1024×1024 terrain with no optimization on the terrain at all. LOL… it ran pretty well unless I added too many trees to it (and I did). I didn’t know anything about optimizing polygons at the time, I used triangle strips which were easy to do, I guess that’s why it didn’t lag too badly. Another way to do shadows, and the first time I did shadows, was to create a shadow map. This is how Battlefield 1942 done things, shadow map, cube skybox etc, I used to run that game just to look around and see how they did things, I created my skybox the same as their so that where the sky reached the terrain, it was shaded to match the fog colour so it blended seamlessly. It’s a good game to get ideas from. They would copy the terrain part of the map (not objects on it) to the surrounding areas off shore so if you flew out a ways off map you could see another island off in the distance (it was the same one) before you crashed from being off map. Great idea for smaller maps to give something in the distance.

    Anyhow, nice series, I am spending far too much time on your site. I wish I had found this years ago, it would have given me new ideas on how to do things. ;)

  9. Volfram says:

    Wow, this was written in 2006?

    Shamus, I came here because I wanted to let you know that I read this article about one year ago, and this past week, I was implementing a shadowing algorithm in a game engine I am currently working on. I remembered this article and copied your EBTPIIS algorithm. I modified it a bit so that it can handle lights from any direction in the hemisphere of the sky, but your article here probably saved me several day of pure thought, and the EBTPIIS algorithm is likely an order of magnitude faster than anything I would have come up with myself. Shadow calculations are actually the fastest component in the pipeline I’m using them for.

    To Shamus in 2006, from 7 years in the future, thank-you.

  10. WJS says:

    It’s fun trying to think of optimisations (that may or may not have actually been used). One that springs to mind is that you could, if careless, do the trig function to work out the angle of the sun once per point, rather than once per lighting update. The sun isn’t going to move while you’re updating the shadow map, however, so you’ll end up doing the expensive trig functions a million times more often (assuming a 1024×1024 heightmap) than you would if you just calculated the slope once, then used that stored number to update each pixel. I know premature optimisation is bad and all, but if you’re not sure how a function is going to be used, it’s not a good idea to assume that some chucklehead isn’t going to call it from inside a loop (in this case, the likely case would be someone animating the sun and recalculating the shadow map each frame, I guess?).

Thanks for joining the discussion. Be nice, don't post angry, and enjoy yourself. This is supposed to be fun. Your email address will not be published. Required fields are marked*

You can enclose spoilers in <strike> tags like so:
<strike>Darth Vader is Luke's father!</strike>

You can make things italics like this:
Can you imagine having Darth Vader as your <i>father</i>?

You can make things bold like this:
I'm <b>very</b> glad Darth Vader isn't my father.

You can make links like this:
I'm reading about <a href="http://en.wikipedia.org/wiki/Darth_Vader">Darth Vader</a> on Wikipedia!

You can quote someone like this:
Darth Vader said <blockquote>Luke, I am your father.</blockquote>

Leave a Reply

Your email address will not be published.