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:
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:
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.
Shamus Plays LOTRO
As someone who loves Tolkein lore and despises silly MMO quests, this game left me deeply conflicted.
Quakecon 2012 Annotated
An interesting but technically dense talk about gaming technology. I translate it for the non-coders.
The product of fandom run unchecked, this novel began as a short story and grew into something of a cult hit.
Do you like electronic music? Do you like free stuff? Are you okay with amateur music from someone who's learning? Yes? Because that's what this is.
Let's ruin everyone's fun by listing all the ways in which zombies can't work, couldn't happen, and don't make sense.