Terrain, Part 4

By Shamus Posted Monday Feb 6, 2006

Filed under: Programming 5 comments

Now that my program has distance-based polygon reduction, I need the terrain to change whenever the user moves around. If they are on the east side of a mountain, the area nearby should be detailed, and everything else should be more simplified. If they move to the west side of the mountain, the detail should appear there instead of on the east side. To set this up, my program comes up with a set of polygons optimized for viewing near a given location.

OpenGL has something called “lists”, which is a list of stuff you want OpenGL to do. A set of directions, if you will. When I create a new terrain (a new group of optimized polygons) I send all of the vertices (the points) and polygons (the triangles) over to OpenGL and all of that data is stored as a list. Later, when it’s time to render the scene, I just tell OpenGL to draw the list I created.

Think of it this way: The list is a series of directions for how to get to Pittsburgh. Get on this highway, turn left here, take this exit, etc. Once I feed it the directions, I can tell it “go to Pittsburgh” anytime I want without having to give the detailed directions again.

But I’m noticing that sending over this stuff to build the list is causing a problem. As I fly around the terrain, there are little pauses every few seconds. Lots of games have these from time to time. Some people call this “stuttering”. It’s acceptable once every minute or two, but once every five seconds is annoying. I’m sending so much data at once that it’s causing a slight pause (perhaps a quarter-second) as OpenGL chokes down all that data. I suspect that the major problem is that I’m sending too many points. I need to fix this. Let’s get to it:

Let’s imagine we need to draw eight triangles, as pictured on the right. Up until now, I’ve been drawing polygons using the simplest method possible. I just send it 3 vertices and it draws a polygon. This means that I need 3 vertices for every polygon I draw. If I have half a million polygons, I’ll have to play connect-the-dots with 1.5 million dots.
To draw triangle A, I send it the the vertices pictured.

Keep in mind that “sending” a vertex is kind of a big deal. Each vertex has its own location in 3-d space, a color, some data for how the texture should be painted on, and what direction the point is “facing”. Multiply this by 1.5 million and suddenly we’re talking about a lot of data.

And now I want to draw polygon B. I send it 3 more points, as pictured. Notice something about the points? I just sent point #1 again. Also, point #2 is the same point I used as #3 in triangle A. Now here I am, sending the same data for that vertex all over again. My program is choking as it sends vertex data, and I’m making things worse by sending most points more than once! Can’t it just, you know, re-use them somehow?

Actually, yes. This situation is fairly common and OpenGL has a tool for dealing with it. It’s called a triangle “fan”.

When using a fan, you send a whole bunch of vertices at once. Each triangle is still made of 3 points, but the points get re-used in an interesting way. The first triangle still comes from the first three points, as in the triangle A image above. After that, each vertex I add creates another polygon, which comes from the very first vertex in the series, and the last two.

So, if I send all the verts in a fan, I get:

Triangle A is points 1, 2, 3
Triangle B is points 1, 3, 4
Triangle C is points 1, 4, 5
Triangle D is points 1, 5, 6
Triangle E is points 1, 6, 7
Triangle F is points 1, 7, 8
Triangle G is points 1, 8, 9
Triangle H is points 1, 9, 10

Point 10 is the exact same vertex as point 2, which means I do have to send a bit of redundant data by sending that vertex twice. However, this is still a lot less than before. Originally I needed 24 verts for 8 triangles, and now I’m down to 10. That’s some impressive savings.

Of course, things are never this simple. If you remember the wireframe images from earlier updates, you’ll notice that we almost never get nice, neat triangles like the ones in our example. Instead, the grid is a mess of different-sided triangles that don’t always form nice fans. Let’s look at one example:

In the outlined block, you can see that B, E, F, and G appear normally, but A and H are merged into one big triangle. Even more interesting is C and D, which are actually broken down into a smaller group with their own set of A through H triangles. (And this entire highlighted square is in itself a sub-group made from the E and F area of an even larger block. Confused? Sorry. Almost done.)

The code to figure out how to make fans in these situations is fairly complex. It took some time to look at all of the variations and come up with an optimal system. (Assuming I did)

The result? Let’s see:


And After:

So, I nearly cut the number of points in half. But now the bad news: After all of this, I didn’t solve the slight stuttering problem I was having. The terrain-rebuilding pause was reduced, but I can still detect it when the framerate is smooth. This just won’t do.


The problem is that I’m doing the whole terrain in one go. I’m sending the whole mesh to OpenGL at once, which just takes too long. I knew from the start that I could fix this problem by breaking the terrain into many seperate sections and sending the terrain over to OpenGL a section at a time. I would take that quarter-second delay and spread it out over several seconds worth of animation. This will fix the problem for sure, but this is a complex step and I didn’t want to take it if I didn’t need to. I had hoped that just switching over to triangle fans would fix the problem. It didn’t, and now I have to take the more drastic step of breaking the whole terrain into smaller sections that can be sent one at a time.

Once this was finished, the stuttering went away and the program now runs smoothly all the time.

This probably seems like an awful lot of work to eliminate a quarter-second hitch. It was, but I think the effort was worth it. If this were a game, this would be one of those nagging issues that annoyed players and would lead critics to mention poor performance in their reviews. You have to take care of stuff like this if you want good performance.


From The Archives:

5 thoughts on “Terrain, Part 4

  1. vadkul says:

    I want to build Terrain Engine for Strategy Game. Is diffrent from shooter engine terrain. What ideas do you have to implement this engine and optimize

  2. Chemizt says:

    Hmmm there is something that doesn’t add up for me.. You mentioned that using the lindstrom approach you succeeded in making the triangulation happen, from which I concluded that you ended up with a triangle strip (see figure 6 in the lindstrom paper). Triangle strips don’t exhibit the problem of duplicate vertices so basically you don’t really even need triangle fans.. That is what section D in the lindstrom paper describes. I would be interested to know what that approach does for your FPS; could be very promising.

    1. Neil Roy says:

      I realize this post is several years old now, but I just wanted to comment on this for anyone else reading. I think strips would probably be better, IF you’re rendering the entire terrain at once, which you can’t do, especially once you get more detail and objects on it. The terrain has to be broken up into chunks to be more efficient, and if you break up the terrain into chunks, those strips will also need to be broken up, eliminating any benefit they made have had over fans. Fans on the other hand, because they operate in square sections can be sent in chunks without breaking them up like you would have to do with strips.

      I actually use strips in my own project and the idea of using fans seems better to me for this reason and I will probably switch to using them when I work on it again.

  3. Ghashnik says:

    I have another random, ignorant question:
    I noticed that you said that OpenGL has lists, and when you send the data to be processed, the huge amount of data causes the terrain to render slowly causing glitches.
    Would it be possible to set up the lists so that while one step is being processed, the next step is being loaded into place, ready to go?
    I’m thinking in terms of YouTube videos. Normally, I have to wait for one video to load, play it, then wait for the next video to load, and play it. Is it possible to prime a video to load, so while I’m playing the first video, the second video is loading at the same time. Then, when I’m finished with the first video, I’m already ready to start the second.
    Would it be possible to apply this same concept, except instead of videos, it’s terrain data?
    I imagine that this would work for games like Half-Life 2. My loading screens between areas were significant. It seems like all the time I was wandering around like an idiot and killing Combine, the next area could have been loading.

    TL;DR Version: While Step 1 is being processed, can Steps 2-4 be loading?

    1. Doc says:

      You can do that by implementing multithreading. I’m no programmer, getting my grasp on concepts by reading articles like this as I learn my first language (C#, which in 5.0 uses the new async/await methods to implement multithreading). From what I understand new threads are normally introduced to prevent the UI from freezing up, however I’m sure they could be used in this instance as well. The problem is that whether or not you’re spreading these activities onto different threads, you’re still pulling from the same pool of processing power.
      I believe this only works well if you make sure the activities are small enough to be handled in tandem, and spread them out among the processor cores.
      As I write this I realize that GPU’s are probably a completely different story, and have no idea how to optimize threads for use in CUDA cores and what not… I’m pretty sure that’s how it’d be done, though.

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.