## 2005.08.18 - The story thus far…

#### One Point Five Years Ago

Early last year, I was playing around with a simple terrain engine. It was your basic height-field based terrain engine. It was also crap-tastic. But hey, you’ve gotta start somewhere. Thus, I started with this:

(Click To Enlarge)

Kinda lame, but it was a good test. Each chunk was LODified by using a Binary Triangle Tree, which was a great simplification method, though I did eventually switch to using progressive meshing (though leaving the edges in-tact…not the greatest LOD scheme ever). It was then that I had a vision. Well, not so much a vision, but an idea. Well, not even an idea. More of a thought. Cliffs! That’s right, cliffs. And caves. Those were two things that I would love to have, but they’re impossible with a straight-up heightfield renderer. So I set my tired code aside, and began my next crazy scheme.

#### Terrain Idea The Second!

So, I thought: what if I could model a level in a manner similar to making a topographical map. Something like this:

(Click To Enlarge)

In this system, each shape could be drawn, and given a height value. The editor would fill in the drawn shapes with polygons, connecting them to the other inner shapes (and outer shapes), adding slopes when asked (or making a given shape a plateau).

Sound crazy? It was. I coded it for about three months, working on logic to triangulate a complex polygon (overlapping not allowed) which contains children (which are holes in the parent polygon). Then I worked on smoothing the polygons by adding curves (see the first two screenshots for a comparison). Each edge was essentially a bezier curve, where the middle two control points were placed based on the angle of the connection to the next/previous line segments.

Now, right about now, you may be thinking to yourself: “How does this solve the problem of caves? How did you handle the LOD switching? Isn’t this a lot of work? What’s the meaning of life?” To answer your questions, in order: It doesn’t, I didn’t, Way too much, and free beer. This particular concoction was way too complex, and not near enough to what I wanted. So it, too, was scrapped.

#### The Not So Distant Past, Or: How to Totally Copy SSX’s Idea

I started browsing the web for other creative ways to generate terrain. It was then that I came upon THIS article. What a brilliant idea, I thought! Use curved surfaces to model terrain! So I started work on Terrain III: Terrain With a Vengeance. Not too long afterwards, I had a decent curved-surface terrain. The beziers were calculated in a vertex shader, given the matrix representation of the surface as a 4×4 matrix. Each vertex buffer simply contained the u and v coordinates (in the range [0, 1]) for the patch of the given resolution (different vertices in the vertex buffer were used for different tesselations). However, there were two big problems:

• The vertex shader was somewhat slow, with the extra matrix multiplications (three 4×4 multiplications and a dot product for position alone)
• There were cracks between the patches, due to floating-point rounding errors.

So, I thought, what if I calculated the patches in software in a big dynamic vertex buffer, using a better method? I ended up using de Casteljau’s Method on the edges of the patches, because it does not have the same floating-point issues that the matrix representation does. However, I continued using the matrix method on the interior points, for speed reasons. Each patch was cached into the vertex buffer using a cheap LRU cache. This eliminated the “sparkles” caused by the floating-point errors, and significantly improved my framerate. And now, screenshots:

(Click To Enlarge)

This method worked well, but there were issues with locking/unlocking the buffer. Also, 800 patches meant 800 DrawPrimitive calls, which is, how you say, lame. Thus, I rebuilt the cache algorithm (Yes, I have the technology) to cache items into a set of smaller vertex buffers (that I called “slices”), which were each bound to a specific material (i.e. grass, etc). Thus, they could be batched up better. Soon, 800 patches meant only about 30 draw primitive calls. Which was way better, but there was still a problem. With great caching comes great framerate instability. Since the caching algorithm would sometimes not have to do anything, but sometimes it would have to cache a lot of patches, the framerate became very unstable. Even though it was running faster than 100 fps almost the entire time, it was still highly visible stuttering (especially when I fillrate-limited it a bit). Plus, there became the question of how to actually MODEL such a terrain (I was going to have to write a super-complicated terrain editor). So I wavered. It seemed that there were many, many problems with this implementation and that, while it’s definitely cool, I don’t know that I’m going to be able to do what I want within my newly-created timeframe. So I decided to set this method aside as well, and move on.

#### The Present, But Not the Birthday Kind

And that brings us to now. I’ve decided that I’m going to use a simple mesh format for the terrain, though with LOD data built into it. That way, I can use an existing modeling program (I’m looking at you, Blender) to do the modeling, build some simple texture/material/atmosphere editing utilities (or one texture/material/atmosphere editing utility), and just use that. Break it up into LOD-able chunks, and I think I have a winner!

Also, I’ll probably keep the track editing interface that I already have (though I’ll have to improve on it, obviously, since it’s…clunky, at best). But it provided me with these:

(Click To Enlarge)

Which are fairly representative of the types of tracks I’m aiming to have.

Alright, class, that’s the end of your history lesson for today. Up next: New developments in code!