Element 61

Monday, February 20, 2006

Geomipmapped Terrain, Part 1: The Basics

Geomipmapping is a fairly well known technique at this point. It's a relatively easy algorithm to implement, and provides extremely good results on medium-sized terrain. It is, however, somewhat more difficult to implement optimally, and the original paper leaves out a few important things, like how to deal with cracks in the landscape or how to compute errors for actual terrain data. There also aren't very many reference implementations, so seeing an example of it actually running is somewhat difficult. I'm one of the few people who has bothered to share significant code or methodology (on GameDev.Net) and to have actually explained all of the necessary steps to create a complete and usable terrain system. Since these explanations are scattered across a number of forum posts, and because I recently finished re-engineering my system to a set up that I believe to be near-optimal, it made sense for me to describe everything in detail.

First of all, it's necessary that you read Willem H. de Boer's original article, titled Fast Terrain Rendering Using Geometrical MipMapping. In the paper, de Boer discusses two things of note. One is the method of detail reduction, by removing every other vertex at each level. The other is the screen space error metric, which allows us to determine when to change our level of detail (abbreviated LoD from here on out). The detail reduction method is simple and indeed obvious; there is nothing groundbreaking about it. It's the screen-space error metric that makes geomipmapping different from earlier algorithms, which were generally ad-hoc distance based mechanisms. Until you've put that screen-space metric in, what you have isn't geomipmapping.

Most of the actual constraints on our terrain are described fairly well by de Boer himself. It'll be a uniform, square heightmap whose dimensions are 2n + 1. The plus one is critical here; most introductory terrain stuff, for example the NeHe tutorial, use a simple 2n heightmap. As it turns out, this breaks level of detail and complicates the quadtree as well.

I want to emphasize iterative development here as well, so what will happen is that we will start off with a simple terrain implementation and add more capabilities to it, keeping it in a usable state all the while. You don't want to write a thousand lines to come up with a black screen. It's damn near impossible to debug that much code at once, especially when several dozen bugs may be scattered through various parts of the system and interacting in unpredictable ways. The goal is that whenever we make a breaking change, the damage is easily localizable to a small subset of the code.

As far as the technical stuff. I'll be doing code samples in C#/MDX, but really they should be easy to follow no matter what your persuasions (or perversions, as the case may be). You OpenGL people should make sure you're comfortable with VBOs; this is a no vertex array (or god forbid immediate mode) zone. The goal is to render our terrain as fast as possible using 16 bit indices and a minimized number of batches. (These two goals conflict, and we'll handle that later.) We want to minimize the amount of CPU time spent, while maximizing GPU efficiency. These goals are aggressively pursued, often at the expense of extra memory. I'll discuss memory use at length later. For a 1025 terrain, the memory consumption of the terrain is about 50 MB. It tops out at around 25 million vertex and pixel shaded tris/sec when LoD is disabled on my Athlon64 3200+/X800 GTO, for which the theoretical maximum triangle throughput is 38 million tris/sec (and we all know how accurate those numbers are...). In reality you don't show nearly as high triangle throughput due to the simple fact that cards these days can shrug off 20K or 50K triangles per frame without caring at all; you get bottlenecked in other areas at that point and benchmarks are meaningless. So that's all for now. Next post I'll dive in and get things wired up. Keep in that since this is a blog, I won't be giving complete working code; there are too many dependencies on other parts of the engine anyway. I'll show enough that you can see what's going on. The engine source will be available in full sooner or later anyway.

Dot Plan: The Revival

So I guess this blog flared up briefly in the fall and died almost immediately. I'd like to bring it back, and to do things right this time. I'm shooting for bi-weekly updates, which seems reasonable. (Ignore the fact that I am competing in the Collegiate National Taekwondo Championships this week, and then flying down to Redmond for an interview with MS next week.)

As for content. I'm not terribly interested in the Quake 3 thing at this point, so hopefully somebody else will pick up. Although really, this is probably a good time to learn how to cope when a big existing code base is dropped on you. It's an important job skill. The resource management articles are going to be restarted from the beginning, due to significant re-engineering. There are now two versions, one in C++ and one in C#; I'll be discussing both soon. I'll be interleaving that discussion in between posts about the main thing I want to discuss right now, which is my completely re-engineered terrain system. Most people around GDNet know that I'm basically resident expert when it comes to geomipmapped terrains, but I haven't made a lot of noise about the redesigned system (now in C#/MDX), which is incredibly efficient. Later on I'll probably be discussing the rest of the engine architecture, which is looking like it will turn out to be fantastic. It's quite immature at the moment, though, so I want to let it settle down first. Most likely the source to the engine will be available before the blog posts discussing the design decisions in it. I'll toss up the first terrain article shortly. Hopefully this can be something that will work its way on to people's "things to read" list.