Terrain, Part 5

By Shamus
on Feb 8, 2006
Filed under:

We continue this series where I demonstrate the steps I’m taking to create a program for rendering terrain. For many of you (as if there were many of you, pfft!) some of this will be pretty technical. If nothing else, enjoy the pretty pictures as this thing takes shape.

Polygon Optimization Revisited

Back in Part 2 I added code to look for flat areas and make them low-polygon, while looking for “hilly” areas and making them more high-polygon. I made a serious mistake with this. My program should not care if an area is “hilly”. Right now, the steeper a slope is, the more polygons you get. This is a stupid and wrongheaded way to think of things. For correcting this, I replaced my original terrain with a big ramp:

The solid black incline is actually being rendered wireframe just like the flat area, but the polygons are so dense that it looks solid. This illustrates the problem fairly well. There is no reason this hill needs to be so polygon-heavy. Instead of having my program ask “is this block steep?” it should instead be asking “is this block coplanar?”. The surface of the incline above doesn’t need to be any more dense than the flat land below it. All of those tiny little triangles are perfectly coplanar and could be simplified into much larger polygons.

So, I ripped the code out that was doing this and re-wrote it. It always hurts to throw away code, particularly code on which I’ve spent a lot of time. This is even worse when it’s code I’ve written recently. However, there is just no sense in keeping bad code. If you build a house with a bad foundation, you don’t keep it because you like the roof. You rip it down and rebuild it properly.

The new system yields some impressive results on my test terrain:

I didn’t note the polygon count change but I don’t think it matters. This test case was made to allow me to view the problem clearly. It isn’t really useful as a measuring stick for how the system will perform on real terrain. I’m not sure why I’m still getting so many tiny polygons at the corners. This is problably some situation I havn’t thought about fully just yet. Still, I can’t let myself be distracted. I make a note to examine this more fully later and move on.

We need to see how the new system works on real terrain:

Left: Old and busted. Right: new hotness.

If you look at the image above you’ll see that with the old system, the sides of the mountain are dense with polygons. With the new one, they are much less so.

At this point, my program is eliminating 90% of the polygons from the original count of half a million. But the differences between the old system and the new one are even bigger than they seem. The new system I’m writing is actually simpler and requires a lot less code. It’s faster. I don’t need to keep a bunch of versions of the map in memory at different resolutions (the quad tree). As an added bonus, the new system makes better choices when choosing what polygons to keep and which ones to reduce. The new one looks better than the old. So, to sum up, the new system:

  • Is smaller by about 300 lines of code.
  • Uses about 8MB less memory.
  • Is faster at optimizing the terrain. (I didn’t note the improvements here, although I doubt the savings is very large)
  • Uses significantly less polygons.
  • Generates terrain that, despite all the savings listed above, looks better.

Good deal. Okay, now back to the earlier problem where the edges had a ton of tiny little triangles. If you remember from above:

This was just a simple bug. Once fixed, the poly count dropped even more.

Okay, that is three posts in a row where I agonize over polygon counts. I think we’re done with this phase. Next time, let’s see if we can’t add something cool.

Enjoyed this post? Please share!

4Four comments. Fantastic.

From the Archives:

  1. Marijana says:

    pretty pictures? Right!

  2. Marijana says:

    Oh, aaaaaaaaaand First!!!!

  3. Childwanderer says:

    What does coplanar mean in this context? I understand coplanar to mean “lying or acting on the same plane”. This definition requires the subject to be plural; if you use only one subject, you beg the question “With what is the block coplanar?”

    • RandomInternetGuy says:

      I think this is meant to imply coplanar with anything at all; i.e. if a triangle is coplanar to any other triangles, then the block can be simplified.

Leave a Reply

Comments are moderated and may not be posted immediately. Required fields are marked *


Thanks for joining the discussion. Be nice, don't post angry, and enjoy yourself. This is supposed to be fun.

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>