• entries
17
19
• views
21406

Development of my terrain engine.

## Per-Patch Textures and Normal Maps

I've modified the Land-o-Rama terrain engine so that it applies a unique texture (or textures) to each terrain patch in the quadtree. I had no idea how much better it would look though.

Take a look at these two screenshots. Each screenshot shows the exact same view of a 32,768 x 32,768 heightmap.

First, here's Land-o-Rama with per-vertex normals in action, using a patch size of 33 x 33 vertices:

There are 623k triangles being rendered at a depressing 21 fps.

Now, here's Land-o-Rama with per-patch normal maps in action, using a patch size of only 17 x 17 vertices:

w00t, a huge difference in detail! Each quadtree patch has a 64 x 64 normal map generated from the same heightmap as the terrain mesh. Now there are only 302k triangles being rendered and the frame rate has almost doubled to 40 fps.

I'm not happy with how I got it to work though...

Land-o-Rama uses a patch size of 2n+1 x 2n+1 vertices. Because the terrain mesh and the normal-map texels are generated from the same heightmap data, the texture size must also be in the form 2m+1 x 2m+1 (although it doesn't need to be equal to the patch size.) This is a real problem since my graphics card does not support non-power-of-two textures in hardware (it's a 4 year-old NVidia GeForce FX 5950 Ultra.)

What I ended up doing was this: First, Land-o-Rama generates the 2m+1 x 2m+1 normal-map for the patch. But before uploading it to the graphics card, it removes the center row and column. I feel that this solution is a big steaming pile of kludge. There's got to be a better way.

What I may end up doing is rewriting the quadtree code so that the patch size is 2n-1 x 2n-1 instead. Then the normal-map size will also be in the form 2m-1 x 2m-1, which will fit inside of a 2m x 2m texture. No removing the center row and column! It will be quite a rewrite though.

Here's a screenshot with some terrain texturing added to the mix:

And here's another one with snow and cliffs in the foreground:

## Increasing the resolution of heightmaps

One of the reasons for the development of my terrain engine was so that I could go to any point on the world and explore the surrounding terrain. So I downloaded every single heightmap from the Shuttle Radar Topography Mission website (and likely pissed off my ISP in the process.) These heightmaps encompass all land between 60? North and 56? South. Each heightmap is a 1 degree by 1 degree tile made up of 1201 x 1201 elevation points. Each heightmap has a resolution of three arcseconds (about 90 meters.)

As I was playing around with my terrain engine, I began to notice that for ground-level explorations, a resolution of 90 meters wasn't going to cut it anymore. I needed a way to increase the resolution of these heightmaps.

At first, I simply resized a heightmap to 4801 x 4801 (4x in both directions) using bicubic interpolation and added some Perlin noise to it. It didn't look bad, but it didn't look natural either. So I looked for a way to simulate some sort of natural process to apply this detail. That's when I decided to use some sort of water erosion algorithm.

Searching the intarwebs, I found a paper called Realtime Procedural Terrain Generation (PDF warning). It contained an algorithm for hydraulic erosion. I implemented it but I found that the simulation was a little too perfect. It wore down the mountains and spewed the resulting sediment out into the valleys, choking many small lakes in the process. It was definitely cool to see, but it didn't serve my purpose. I just wanted to add some erosion-like features to the terrain.

I took some of the ideas from that paper and made an algorithm that would produce erosion-like features. When run on this heightmap:

it results in this heightmap:

The erosion algorithm in detail

Before running the erosion algorithm, the heightmap needs to be enlarged using bicubic interpolation. I also find adding a small bit of Perlin noise helps.

The erosion algorithm performs a number of iterations specified by the user. Each iteration performs the following three steps:

1. Select a random point on the heightmap

2. Make a river starting at that point

3. Carve out the ground under the river

(The above image comes from a heightmap with 128,000 iterations applied to it.)

The descriptions of these steps uses the following 5 x 5 heightmap in their examples:

Step 1: Select a random point on the heightmap

This step is self-explanatory. It simply selects a random point on the heightmap (in yellow):

Step 2: Make a river starting at that point

This is the most time-consuming step of the algorithm. It makes the river by selecting a series of points such that each point in the series has an elevation that is lower than its previous point.

The first thing it does is retrieve all the point's neighbors (in blue):

Rivers cannot flow uphill, so the algorithm ignores the neighbors (in red) that have a higher elevation than the current point:

Of the remaining neighbors, the algorithm randomly selects one to be the next point in the river. The lower the neighbor, the more likely it will be selected as the next point.

To calculate the probability for each neighbor, the algorithm first sums together all of the elevation differences between the current point and the neighbor points. In this example, the sum of the differences is:

(15 - 14) + (15 - 14) + (15 - 12) + (15 - 10) = 10.

The probability of selecting a neighbor for the next point in the river is equal to the elevation difference between the current point and the neighbor, divided by the sum of all elevation differences. For example:

• Right neighbor: (15 - 14) / 10 = 0.1 = 10%

• Bottom-left neighbor: (15 - 14) / 10 = 0.1 = 10%

• Bottom neighbor: (15 - 12) / 10 = 0.3 = 30%

• Bottom-right neighbor: (15 - 10) / 10 = 0.5 = 50%

Once it select the neighbor, the algorithm continues step 2 until there are no more lower neighbors (the river enters a "pit") or the river leaves the edge of the heightmap.

Step 3: Carve out the ground under the river

This step subtracts a constant elevation amount from each point in the river, except the last point.

Excluding the last point is important. This last point will have a lower elevation than all its surrounding neighbors, creating a 1 x 1 "pit" at the end of the river. Successive iterations of the erosion algorithm can cause these pits to become quite deep, which generally makes the resulting heightmap look like hell.

Problems with the erosion algorithm

One thing I've noticed about this algorithm was that some rivers were carved much too deeply into the terrain. If I reduced the number of iterations or reduce the carve amount, the main rivers didn't get as deep, but I could barely see the smaller rivers.

Take a look at the following difference map, which is created by taking the difference between the original heightmap and the eroded one:

The areas in red are at least 40 meters lower than the corresponding elevations from the original heightmap, which I found was too deep for a heightmap with a resolution of 22.5 meters. Also, the river edges were too sharp, showing up as aliasing artifacts on the heightmap. If I clamp the difference values to 40 meters (this parameter is user-defined) and blur them to remove the aliasing, the difference map looks like this:

To produce the final heightmap, simply subtract this difference map from the original heightmap.

## libnoise 1.0.0 (production version) is out

w00t, I finally got off my ass and released the first production build of libnoise 1.0.0. It's a library for generating coherent (smoothly changing) noise. It's useful for generating random terrain and textures.

For those of you who have used libnoise in the past, I've increased the speed of libnoise by a factor of 1.5 (but I still don't consider it realtime by any means .) The noise generator code made heavy use of floor(), which is incredibly slow (at least in Windows.) Replacing the floor() calls with a cast-to-int and a conditional caused the speed improvement.

## Terrain texturing

I've added some terrain-type textures to Land-o-Rama.

I'm using the Utah Teapot of terrain meshes: Mount Rainier, Washington. The viewer is facing north.

Land-o-Rama now supports four terrain-type textures: grass, forest, rock, and snow. For far distances, Land-o-Rama can use a different forest texture. This allows you to have a forest floor texture for close-up views and a forest texture for distant views. Combined with the three tiled normal-map textures, this version of Land-o-Rama performs 8 texture look-ups per pixel.

A terrain-type texture also use an alpha map to determine roughness. Rough areas have more bump mapping applied to them. So we can make the rock texture look very rough while making the snow texture look very smooth.

The terrain-type map

The terrain types are applied per-vertex by using a terrain-type map. This map has four channels:
• Red channel: Placement of rock textures.

• Green channel: Placement of grass textures.

• Blue channel: Placement of snow textures.

• Alpha channel: Placement of forest textures.

For each pixel, all channels add to 255.

Here is an example of a piece of a terrain-type map:

(To display this image, I replaced the alpha channel with black.)

Towards the right is part of Mount Rainier. The mountain is covered in rocks and snow. Towards the left are low-elevation areas covered in grass and trees. There's a clearcut in the top center of the image; it shows up as rock. The rivers are shown as rock because they are neither vegetation or snow. Eventually, I'll use a SRTM waterbody map to determine river and lake placements.

To build the terrain-type map for a region, Land-o-Rama imports four Landsat channels from that region: 2 (green), 3 (red), 4 (near-IR), and 5 (mid-IR). Land-o-Rama determines vegetation placement by feeding channels 3 and 4 to an algorithm that creates a normalized difference vegetation index (NDVI) map. Land-o-Rama determines snow placement by feeding channels 2 and 5 to a similar algorithm that creates a normalized difference snow index (NDSI) map. These two maps are combined to form the final terrain-type map. Areas that have an NDVI that exceeds a certain value is considered forest instead of grass. Areas that do not have either vegetation or snow is considered rock.

All four channels are then normalized so that they sum to 255.

The vertex shader hasn't really changed all that much from the last version.

The fragment shader has been updated significantly. Here is what it does now:
1. It samples the normal maps. (It also uses these normal maps as a source of noise.)

2. It samples the terrain-type maps.

3. It retrieves the terrain type as a four-component vector. (All components should sum to 1.0.)

4. It applies noise to the terrain types to make the boundaries between terrain types look better.

5. It raises each component of the terrain-type vector by a power of 8. This helps sharpen the boundaries between terrain types. If this was not done, the outlines of areas containing a single terrain type would appear blurry, which generally looks like hell.

6. It normalizes the terrain-type vector so that all components sum to 1.0.

7. It applies the rock terrain type to areas that have a steep slope. (It uses the z component of the normal to determine slope.)

8. It applies the textures according to the weight of the terrain-type vector, performs tangent-space lighting calculations, performs atmospheric calculations, then finally combines all these results together.

Once again, Land-o-Rama took a severe frame-rate hit. On my ancient PC (AMD Athlon 2000 XP, NVidia GeForce FX 5950 Ultra), the frame rate went down from ~24 to ~10 frames per second. I heard that this video card does not do well with pixel shaders. It also performs 8 texture lookups per pixel, so I'm sure that slows things down a lot. Or maybe I just suck making shaders.

Here's some more screenshots:

Mount Rainier, looking east from the ground. There is a big glacier on the mountain's eastern side. On the ground, there's some grass and steep cliffs.

This is Mount Rainier again, this time from the air.

Here's a view of a rocky cliff from somewhere within Yosemite National Park.

This view is within Kokanee Glacier Provincial Park, looking south. The cliff to the left is part of the mountain (I don't know what it's called) that contains the glacier itself.

I'm a little tired of working on Land-o-Rama, so I'm taking a break. Now I'm going to work on libnoise get it to a version 1.0 release. Then after that, who knows? I'd like to try to make a simple run-and-jump platform game. Definitely not a MMORPG :-)

## Terrain with tangent-space normal mapping

I've finally got tangent-space normal mapping working in Land-o-Rama. Here's a brand-new screenshot.

This is another view from inside Valhalla Provincial Park, looking southeast.

In this image, there are three 1024 x 1024 normal maps tiled over the terrain. Each normal map has a different UV scale. The GLSL fragment shader adds the normals from the three normal maps together, then normalizes the result. It looks correct, although I'm not sure if it's actually correct or not.

Land-o-Rama took a severe frame-rate hit. On my semi-ancient PC (AMD Athlon 2000 XP, NVidia GeForce FX 5950 Ultra), the frame rate went down from ~60 to ~24 frames per second. Strangely, it appears that the vertex shader is the bottleneck. If I look straight down so that only a few triangles appear in the view frustum, the frame rate goes up to ~80 fps. Hmmm, I though that it would have been the fragment shader that was the bottleneck.

Adding normal mapping to Land-o-Rama was quite the learning experience. And it was a little frustrating. I've learned two important things.

Generating tangent vectors isn't as easy as it looks:

A tangent vector is simply a vector that is perpendicular to the normal. Sounds easy to generate, right? Well it wasn't so easy to me :-)

There are an infinite number of vectors that are perpendicular to a given normal. You can't just pick one and use it. You need them to be consistently oriented.

I had two choices when it came to generating the tangent vectors:
• Pre-calculate the tangent vectors and create another GLSL attribute array to store them. This would require a lot of changes to Land-o-Rama.

• Calculate the tangent vectors within the vertex shader. The code to do this is somewhat complex and would probably slow down the shader. Since this calculation requires the UV coordinates from adjacent vertices, I'd have to create another GLSL attribute array to store these UV coordinates. In which case, I might as well use this array to store the tangent vectors instead, just like the first method mentioned above.

So it looked like a there was a lot of work ahead of me. But then I thought of something. Since I'm rendering a regular grid, maybe there's a shortcut I could use to generate tangent vectors. As mentioned above, tangent vectors must have a consistent orientation. What if in the vertex shader, you take the normal and rotate it 90 degrees in all three axes? This sounds like it would be consistent. I added that code to the shader and tried it out.

Wow, it appears to actually work! Lighting appears on the correct side of the bumps. w00t! I'm not sure if it is mathematically correct though. I don't pretend to understand the math behind generating these vectors. But so far, I haven't seen anything strange with the lighting.

My GLSL code for bump mapping looks like the following:

  /* Create a tangent vector for this normal.  Since we are rendering a     regular terrain grid, we can get away with rotating the normal 90 degrees     in each direction and using that as the tangent vector (I think). */  vec3 tangent = normal.zyx * vec3 (1.0, -1.0, 1.0);  /* Create a TBN matrix from the normal and tangent vectors.  This matrix     transforms vectors from eye space to tangent space. */  vec3 nPartOfTBNMatrix = normalize (gl_NormalMatrix * normal);  vec3 tPartOfTBNMatrix = normalize (gl_NormalMatrix * tangent);  vec3 bPartOfTBNMatrix = cross (tPartOfTBNMatrix, nPartOfTBNMatrix);  /* Transform the light vector from eye space to tangent space. */  vec3 eLightVector3 = gl_LightSource[0].position.xyz;  TangentLightVector.x = dot (eLightVector3, tPartOfTBNMatrix);  TangentLightVector.y = dot (eLightVector3, bPartOfTBNMatrix);  TangentLightVector.z = dot (eLightVector3, nPartOfTBNMatrix);

  /* Sample the normal-map textures. */  vec3 normal1 = texture2D (NormalMapSampler1, normalMapCoord1).xyz;  vec3 normal2 = texture2D (NormalMapSampler2, normalMapCoord2).xyz;  vec3 normal3 = texture2D (NormalMapSampler3, normalMapCoord3).xyz;  /* Add the normals from the three normal maps together, then normalize the     result.  Because normals have positive and negative values, we need to     map each normal from the (0..1) range to the (-0.5..+0.5) range.  We can     perform the mapping on all three normals at once by subtracting 1.5 from     the summed normal (0.5 * 3). */  vec3 normal = normal1 + normal2 + normal3 - 1.5;  normal = normalize (normal);  /* Calculate the lighting amount. */  float lightAmount = max (dot (TangentLightVector, normal), 0.0);

Texture quality is very important:

Texture quality makes a huge difference. Look at the textures in Resident Evil 4 on the Gamecube. I found that RE4 was easily the nicest looking game from the previous console generation, even though the Gamecube's hardware is inferior to the XBox's.

So even if you had the best engine in the world running on a quad-SLI NVidia 999900 Uber-XForce GT(TM), the resulting renderings would look like crap if the texture maps were of poor quality.

My first normal maps produced very shoddy renderings. After much playing around, I now have normal maps that produce much better results. They're not that great, but they're a hell of a lot better than they used to be.

This is the normal map I ended up using. Do what you want with it.

To create it, I used The GIMP and some other software. This is the process I used:
1. Create a grayscale image with some Perlin noise.

2. Use World Machine to apply some water erosion to the noise.

3. Use the GIMP Resynthesizer plugin to create a seamless texture from the eroded noise.

4. Generate another image with some more Perlin noise and apply a curve to it such that it produces lots of flat areas with some cracks in between.

5. Blend the two images together. I used a 70-30 blend; 70% came from the image from Step 3 and 30% came from the image from Step 4.

6. Use the GIMP normalmap plugin to generate the normal map.

Next, I'll add detail textures (rock, grass, etc.) to Land-o-Rama.

The next thing I did for Land-o-Rama was to write a basic atmospheric shader. I didn't like that horrible blue fog that passed for an atmosphere.

There's sure a lot of academic papers on implementing atmospheric shaders. The one thing that each paper has in common is math. A lot of math. With scary summation and integral symbols. All of this stuff was overwhelming; my math knowledge is limited to first-year calculus.

One of the things I learned from GPU programming books is that the rendering techniques don't have to be mathematically correct; it just has to look correct. So I just kludged together something that kind of looks right. It's definitely nowhere near as nice as some of the atmospheric shaders out there, but it's better than OpenGL uniform fog.

The Land-o-Rama atmospheric shader implements a simple height-dependent atmosphere. The atmospheric density falls off exponentially with increasing altitude. It doesn't take the view direction and the sun angle into account, so it doesn't render a cool red sunset or a light bloom around the sun. Someday, I'd like to do this though.

First thing I needed to figure out was how to calculate atmospheric density along the view ray. Looking through the paper Real Time Rendering of Atmospheric Scattering Effects for Flight Simulators by Ralf Stokholm Nielsen, I found out that it's surprisingly easy to do this. First, you measure the atmospheric density at the eye and at the vertex to draw. Then, you take the average of the two densities and multiply it by the ray's length. That's it! (You can also raise e to the power of this value to have exponential fog.)

Next, the shader calculates the atmospheric inscattering factor. This is the amount of light that is added to the view ray from outside sources, like the rest of the atmosphere. To do this, the shader simply multiplies the view-ray density by the sky color. (I used a bright blue in these examples.)

Next, the shader calculates the atmospheric extinction factor. This is the amount of light that is absorbed along the view ray. To do this, the shader multiplies the view-ray density by the inverse of the sky color. (The inverse of the sky color for a bright blue sky is a dark orange.)

To find the color of the vertex, the shader multiplies the terrain color by the extinction color, then it adds the inscattering color. That's the final color.

Here's a screenshot of this atmospheric shader.

Compare it to the screenshot from the previous journal entry.

Here is a bird's-eye view of the terrain. The yellow dot is the current position. Note the atmosphere gets bluer and more hazy with increasing distance.

Here's what happens when you increase the atmospheric density, increase the density falloff factor, and change the atmosphere color to white:

There's now mist in the valleys.

The next thing I worked on was adding per-pixel bump mapping. This also gets rid of the cross-shaped artifacts that you can see on the left side of the first image.

## Land-o-Rama with shaders and VBOs

In my last journal entry about Land-o-Rama, I had a basic terrain-rendering class in place. Land-o-Rama performs LOD using a quadtree of patches containing regularly spaced vertices. It adds artificial detail to the terrain mesh at runtime so that it can render terrains as large as 32K x 32K.

In the first renderer class I made, Land-o-Rama drew the patches using basic OpenGL 1.1 code and did the vertex and normal morphing between LODs entirely in software. So by using shaders and VBOs, I figured that I could greatly speed things up.

I created a new derived renderer class to use VBOs and shaders. Instead of storing the patch pool in system RAM, it stores it in video RAM using VBOs. All patches use the same index buffer, so I only have to create the index buffer once. I also created a vertex shader that implements a subset of the OpenGL lighting and fog equations, plus vertex, normal, and color morphing between LODs.

I had no idea how much of a difference shaders and VBOs would make! The OpenGL 1.1 renderer could manage about 10-12 frames per second, but look at the frame rate now:

79 frames per second! Holy crap!

The next thing I worked on was getting rid of that horrible blue fog and replacing it with something that looked like real atmospheric scattering.

## Oh noes

It's been many months since my last journal update. I've had a very busy year and haven't had a chance to write anything until now.

At the company I worked at, the entire IT staff got laid off. I got my notice in August that my last day would be in January. I was the last person to be laid off because I had a major project due.

Wow, these last few months were a nightmare, Not only did I had to push myself to get this project done on time, I had unemployment to look forward to when I was done [sad]. Our database guy on this project jumped ship, so I had to quickly get up to speed on Microsoft SQL Server. Our QA guy was also laid off, so our clients had to do QA. The clients kept wanting a bunch of minor changes (and a few major ones) done, even up until the last minute. We used a third-party data-bound grid control that was buggy as hell; their web forums described many kludgy workarounds to get certain features to work. I dropped my kendo classes to save a little cash. Fortunately, the project is now finished.

Despite the rant above, it's been a great company to work at. I've been with them for eight years. Our bosses were always good to us, even during this final project. Early on at this company, they took us on a Carribbean cruise, and even though we were paid during the cruise, we never had to discuss work. One year, the company even sent us to GenCon for the hell of it. Good times, good times.

So now that I'm laid off, I'm going to temporarily move in with family in my hometown. I'm going to update my resume and start looking around various job websites. I'm going to go talk to some of our former clients in the government's IT department and see if I can go work for them.

Even though I've been quite busy these past few months, I was able to put in a little bit of time to do some development on my terrain engine, Land-o-Rama. Now I can finally write about it! I'll start uploading journal entries for Land-o-Rama tonight.

Now that the terrain engine documentation is out of the way, I can finally put it away for awhile and move onto something more interesting: OpenGL shaders!

OK, after much dicking around, I've finally got something. Here's my first attempt at a GLSL shader:

This is my polka-dot shader. OK, it isn't the greatest thing, but I think it looks cool. It's based on the brick shader in Chapter 6 of the OpenGL Shading Language orange book.

Here are its features:
• Dot size, colors, and spacing are application-controlled

• Specular highlighting is applied only after the final color is computed

• Specular highlighting only appears on the dots

• The dots' edges are smooth; there's no aliasing.

What a right pain in the ass to get OpenGL shaders set up though.

I don't know about other operating systems, but it seems like in Windows, it's difficult to do any kind of development using OpenGL version 1.2 or greater. The opengl32.lib file is only set up to use OpenGL 1.1, so you end up having to use extensions.

I've played around with OpenGL extensions in the past (using the glActiveTextureARB multitexturing extension) so I know what it's like to get one function working. Basically, you have to use wglGetProcAddress() to get a pointer to the function, cast it to something like PFNOMGWTFBBQROFLCOPTERPROC (different for each function, so you have to look it up), make sure it actually exists, and then you can use it. This isn't bad when your code uses only a few extensions, but when you're doing shader programming, you have to do this for many, many functions.

There's got to be a better way. Fortunately, there is. On teh intarwebs, I found something called GLEW, the OpenGL Extension Wrangler. It fricking rocks! To get support for all extensions that your card supports, all you have to do is call glewInit(). That's it! Then you have your application check for a specific version of OpenGL and bail if your card doesn't support it. This relly makes my life easier. I recommend you download it if you're using OpenGL.

Now that this was out of the way, it was time to write OpenGL code to load and run the shaders. This also turned out to be much more difficult than I thought it would.

To do this, you have to create shader objects for the vertex and fragment program, load text into them using a pointer to an array of strings, compile them, check for errors, return the error log if it fails, create a program, attach the shaders to the program, link the shaders, check for errors, take it out for a dinner and movie, check for errors, and return the error log if it fails. Fortunately, I've encapsulated this into a single function that takes two source filenames as parameters, one for a vertex shader and one for a fragment shader.

Once everything was set up, it was nice and easy to actually write the vertex and fragment shaders. Now I can play around!

## w00t, finished at last!

I'm finally finished documenting my code for my terrain engine! Damn, was that ever tedious. It took me a month to do. But now I've reached a point in development that I can have fun with trying out all kinds of rendering techniques. However, I'm kind of tired of developing the terrain engine, so I'm going to put it away for awhile and go do something else.

I think I'm going to play around with shaders next. I just got OpenGL Shading Language (the orange book) and I've been dying to play around with shader programming. I got this book a month ago and it was really hard to document the terrain rendering code while this book was sitting on my desk taunting me: "Come on... you know you want to play around with nice, colorful, candy-like shaders, eh? You don't need to document code. Come have fun, mwa-ha-ha!"

When I feel like developing my terrain engine again, I'm going to create a new renderer. I've got a lot of ideas in improving what I got after getting some ideas by thumbing through OpenGL Shading Language.

Right now, this is what the OpenGL 1.1 renderer can do without using textures or shaders:

This image is taken from the south end of Valhalla Provincial Park, looking south.

I can't wait! Shader programming looks like fun!

## Yuck - code restructuring

Well it's been a long time since my last journal entry. I've finally refactored the code in my terrain engine. I moved stuff into their own classes, cleaned up the code, and found and squashed numerous bugs. Tedious as hell, but it had to be done.

Here's the Land-o-Rama library architecture so far:

Height-map class

A height map stores elevation values (you've probably figured this out :-) It contains an uncompressed m x n buffer.

There is an equivalent image class that stores pixels instead of elevation values.

Terrain class

When developing Land-o-Rama, I wanted it to support gigantic terrains (32k x 32k or greater). Of course, you cannot fit all this data in a height map -- a 32k x 32k height map would take up 4 gigabytes of RAM. So I needed a way to generate elevation points without storing all of the terrain in memory. Enter the terrain class.

A terrain class is the source of all elevation values used by Land-o-Rama. A terrain class fills a buffer with elevation values from a rectangular area of the terrain. The class also supports LOD.

A terrain class is an abstract base class. Currently, I have a derived class that stores a height-map object and applies artificial detail to it using a displacement map.

You could write a terrain class that doesn't even use a height map at all -- it could output Perlin noise, for example. I'm thinking at some point of creating a terrain class that outputs values generated from my libnoise library. You could even have a terrain class that used data compression to store a massive terrain in RAM.

There is an equivalent terrain image class that outputs pixels instead of elevation values.

Patch class

A patch stores a 2n+1 x 2n+1 square area of the terrain. (I'm currently using a patch size of 33 x 33.) It contains a vertex buffer, two normal buffers, and two color buffers. Land-o-Rama maintains a quadtree of patches.

The two normal buffers contain normals for the same area of the terrain, but one of these buffers is used by the triangle mesh at the next coarser LOD. These normals are blended together with the appropriate morph weights.

The two color buffers are morphed in the same way as the two normal buffers.

Renderer class

A renderer class renders the contents of a terrain object. It is also responsible for the following:
• Maintaining the quadtree of patch objects by adding/removing patches as the user moves around the terrain.

• Generating the terrain normals

The renderer class is an abstract base class. It doesn't actually render anything; its derived classes do the rendering. This allows me to easily experiment with different rendering techniques (or even different graphics libraries) without modifying the base renderer class. The base renderer class does not care whether you're using OpenGL, DirectX, or Joe-Blow's Software Renderer v0.67b(TM).

The base renderer code calls derived methods at appropriate times while rendering:
• After a new patch is created: This is where you use the terrain object to fill the contents of the patch, allocate the appropriate buffers on the graphics hardware, and upload the contents of that patch to those buffers.

• When a patch is deleted: This is where you free the allocated buffer on the graphics hardware.

• When the terrain is about to be rendered: This is where you set up things that need to be done before rendering, such as uploading texture maps, setting shader parameters, etc.

• When a patch needs to be rendered: Here is where you make the actual graphics-library calls to render the patch.

Currently, the only renderer class I've created is one that uses OpenGL 1.1. In this class, the vertex, normal, and color morphing are all done (very slowly) in software! I wanted to make sure my code worked before moving to GLSL.

Here's what the OpenGL 1.1 renderer looks like:

This is a 1024 x 1024 height map with a 2048 x 2048 image. The terrain size is 32k x 32k. OpenGL does the lighting. The terrain image is created from a vegetation map of the area. (The vegetation map is generated from the red and near-IR channels of a Landsat image of the area, with a brown-to-green gradient applied to the results.)

While all of this is fresh in my mind, I'm going to document the classes, their members, etc. This will probably take me awhile since I hate documenting stuff, but it must be done. When it's done, I can begin to apply GLSL to Land-o-Rama, w00t! I just got the OpenGL Shading Language orange book in the mail, so it'll be hard to do the documentation while it is sitting on my desk.

## Tossing away triangles

After playing around with Land-o-Rama for a bit, I noticed that it is rendering a boatload of triangles more than it needs to.

Here's the screenshot showing the terrain patches again:

The patches with the same color share the same LOD. The brightness inside of the patches indicates the morphing amount to use, where 0.0 (finest) is represented by a darker shade, while 1.0 (coarsest) is represented by a lighter shade.

Take a look at the patches with the big black X's in them. All the vertices in these patches have a morphing amount of 1.0, which means that their triangle meshes can be replaced by a one-quarter resolution triangle mesh with absolutely no decrease in rendering quality.

Now, when Land-o-Rama detects that all vertices in a patch contain morph amounts equal to 1.0, it replaces the standard index buffer with a smaller index buffer that skips every other vertex in both the x and y directions.

This cuts the number of triangles rendered by 30 to 40 percent, with a corresponding increase in frame rate. w00t!

## The hell of seamlessly joining adjacent patches

Now comes the time to seamlessly join adjacent terrain patches together. Here's a screenshot of the terrain with a normal map applied to it:

Note the black cracks between most of the patches. This is because most patches have a different morphing amount from their neighbors. So I had to figure out how to make the patches join together properly.

At first, I used skirts. A skirt "drapes around" the perimeter of a terrain patch so that it covers the cracks around each patch. I can see why many people here on gamedev.net don't like the idea of skirts. They are definitely a kludge. My biggest problem was determining how long to make the skirts. Too long, and you burn fill rate. Too short, and some cracks are not covered completely. I searched all over the intarweb but I couldn't find a good algorithm to determine skirt length without knowing the elevations of all adjacent points at LODs n + 1, n, and n - 1. (As you probably guessed, n is the LOD of the patch.) Yuck. Also, textures on skirts appear to be stretched vertically, so when you see a skirt, it generally looks like hell. So I gave up on them.

I think I found something that worked. In geometry clipmaps, each vertex has its own morphing amount, which is determined by the distance from the viewer. I'm using this idea in my terrain engine.

At first, it appeared to work, but some cracks occasionally appeared. It took me a while to find out the reason. When a terrain patch is split into four smaller patches, the vertices in these patches do not have the same morphing amount; this is because the morphing amount is determined by distance. Something similar happens when four smaller terrain patches are merged into a single patch. I modified the morph formula so that all vertices in the patches that are close enough to split have the same morph amount of 0.0 (finest), while all vertices in the patches that are far away enough to merge have the same morph amount of 1.0 (coarsest). In between, there is a linear blend between 0.0 and 1.0.

Here's a screenshot showing this in new morph forumla action:

The patches with the same color share the same LOD. The brightness inside of the patches indicates the morphing amount to use, where 0.0 (finest) is represented by a darker shade, while 1.0 (coarsest) is represented by a lighter shade.

Now here's a screenshot of the same normal-mapped terrain with the new morphing code:

Everything appears to work now. When flying around, it's kind of neat to see the terrain detail smoothly increase as you get closer.

Now the not-so-fun part:

Because I was experimenting with a lot of different terrain LOD techniques, most of the quadtree and rendering code is stored in a single file littered with global variables and other yucky things. I now have to clean up and document the code. Once I'm done all that, I'll have a terrain engine that I can play with. I can then begin to experiment with fun things like GLSL shaders. I can't wait!

I think this'll be my last journal entry for a while because I'm off to clean up and document the code! Bleah, I'll probably procrastinate and take until May to finish :-) And Metroid Prime Hunters comes out in a few weeks, so that'll be occupying some of my time.

## Vertex morphing action

OK, I've added some stuff to the Land-o-Rama terrain engine. I've got some vertex morphing action. It's quite slow since I'm currently doing these calculations in software... for every friggin' vertex and normal. Here's how it works:

Each terrain patch can have its own morphing amount. This morphing amount is shared among all its vertices. At a given LOD, the morphing amount can range from 0.0 (finest) to 1.0 (coarsest). Four adjacent patches from the same LOD with a morphing amount of 1.0 (coarsest) can be seamlessly replaced by a single patch from the next coarser LOD with a morphing amount of 0.0 (finest), and vice versa.

This screenshot shows patches that are shaded according to the sum of its LOD and its morphing amount:

At first, it seemed easy to figure out the morphing amount for a patch. At any given LOD, just make the morph amount a linear blend between 0.0 and 1.0 based on its distance from the viewer. Unfortunately, as I looked closer, I noticed that this method has a serious flaw. Take a look at the patch outlined in red:

... morphs to ...

In the left image, this patch is about to be split into four patches. In the right image, the split occurs, but each patch has a different morphing amount because their distances from the viewer are not the same. This will appear as a noticable "pop" to the viewer.

To fix this problem, I changed the formula for determining the morphing amount. Instead of a linear blend between 0.0 and 1.0, I changed it to a linear blend between 0.0 and 2.0 and clamped the resulting amount to 1.0. This way, when a patch is close enough to the viewer to be split into four smaller patches, these patches are guaranteed to have a morphing amount of 1.0:

... morphs to ...

Now I wanted to see what the morphing looks like in 3D. I quickly hacked in some wireframe code that I stole from my original version of Land-o-Rama. I loaded a 3-arcsecond (90-meter) SRTM heightmap of the West Kootenay region of British Columbia (N49W118.hgt) and rendered it. Here's a screenshot of Elephant Mountain, just north of Nelson BC:

(This is a rendering of a 1024 x 1024 section of the original 1201 x 1201 height map. Land-o-Rama automatically applies artificial detail to the height map, resulting in a resolution of 32k x 32k. The patch size is 33 x 33.)

Moving around the heightmap, it appears that the vertex morphing is working correctly. You can see the vertices smoothly change when you get closer or farther away from a patch! However, there are big gaps between adjacent patches. This will be fixed soon.

## Terrain Engine Details

I should be clearer in how my terrain engine (called Land-o-Rama) currently works. (It took me all of four seconds to come up with this dumb name and I really can't be bothered to think of a better name :-) I'm a programmer dammit, not a marketer.)

Land-o-Rama contains a pool of terrain patches that can be used and re-used when needed. Each patch contains several buffers (vertex, normal, color, etc.) Each patch holds the same amount of data. The patches are allocated when the engine starts up.

As mentioned in the previous journal entry, Land-o-Rama stores a quadtree of patches. A patch can be split into four smaller patches, and four smaller patches can be merged into a single patch.

When a terrain patch needs to be split into four smaller patches, the original patch is freed back into the pool, four unused patches are retrieved from the pool, and these patches are then filled with terrain data.

When four terrain patches need to be merged into one larger patch, the original four patches are freed back into the pool, one unused patch is retrieved from the pool, and that patch is then filled with terrain data.

In all terrain algorithms that use a quadtree of terrain patches, the algorithm needs to determine when to split and merge these patches. Usually, this decision is based on three things:
• The distance of the patch (usually its center point) to the viewer.

• The roughness of the terrain in the patch.

• Whether the patch intersects the view frustum or not.

For simplicity reasons, Land-o-Rama splits a patch based only on distance; terrain roughness is not taken into account. Also, the view frustum is not taken into account.

Why not take the view frustum into account? Why allocate the patches for terrain that is not visible by the viewer? The reason is that when the viewer looks around, the visible patches would have to be allocated and filled on the fly; this causes the framerate to drop noticably when looking around.

In Land-o-Rama, view-frustum intersection tests only occur when drawing the terrain patches. If the patch is not in the view frustum, it is not drawn.

One of the constraints that I need to have for Land-o-Rama is that each terrain patch can differ from its neighbor by no more than one LOD, so that it'll be relatively easy to join the edges of adjacent patches. Setting the split distance equal to the size of the patch did not work, so I ended up having to split when the distance is equal to double the size of the patch. This works, but it does increase the allocated patch count.

Here is a screenshot of the quadtree in action.

The screenshot doesn't look very exciting, but I need to work on one thing at a time. The light gray patches intersect the view frustum. The dark gray patches do not.

## Selecting a Terrain Engine

A few months ago, I implemented a terrain engine using the geometry clipmap technique as described in Chapter 2 of GPU Gems 2. Unfortunately, I discovered that the technique is patented (well, pending at the time this was written) by Microsoft. I tried to ask Microsoft Research for permission to use it, but there was no response.

Why NVidia allowed this technique to be published in GPU Gems 2, knowing full well that Microsoft applied for a patent on it, I'll never know. Does that mean that other techniques in that book are patented as well? Did I spend \$160 CDN on both books that are essentially ads for NVidia? ("Look at what our cards can do, but don't implement any of these techniques!")

Unfortunately, this meant that I had to scrap the geometry clipmap engine and replace it with a new engine. So I went over to VTerrain to see what other techniques I could use.

When selecting a new technique for rendering terrain, I needed one that:
• is able to handle very large terrains (64k x 64k). In the old engine, I used a base height map (e.g, 1024 x 1024) with some artificial detail applied to it in real-time.

• is GPU friendly. All vertices in a terrain patch must be placed in a single triangle strip so that the patch can be uploaded to video memory and drawn with one call to the graphics library.

• does not require height-map preprocessing. This allows me to use Perlin noise or some other algorithm to generate the vertices in real-time instead of using a static height map.

• is easy to add vertex morphing when terrain patches are transitioning between LODs.

With this in mind, I narrowed my choices down to three:
• Geometrical Mipmapping: This technique looks very easy to implement since each patch has a regular size and contains a regular grid. This also proves to be a drawback as well -- because I needed to be able to render a 64k x 64k grid, I'd either have to use a metric sh*tload of small patches (requiring a huge number of GL calls), or a small number of gigantic patches (requiring a huge number of vertices per patch)

• Chunked LOD: This method uses a quadtree of terrain patches of various sizes, depending on its LOD. This allows the use of gigantic terrain since the sizes of patches can vary; far-away patches are larger than nearby patches. Unfortunately, this method requires some preprocessing to decimate the number of triangles in each patch before use. Also, the mesh in each patch does not contain a regular grid of triangles, preventing me from easily determining the elevation of a specific point on the terrain.

• SOAR. I was playing around with a terrain demo called Ranger Mk II which makes use of the SOAR technique. This demo is very impressive. It is fast, it can handle long draw distances, and it can handle a monsterous-sized terrain. After looking at the code, I was really confused about how it worked; the algorithm appeared to be very complicated for my small little mind.

In the end, I ended up using a combination of Chunked LOD and Geometrical Mipmapping. The terrain is stored as a quadtree of patches, and each patch contained a regular grid of n x n vertices. As the viewpoint moves around the terrain, patches are allocated and reallocated as neccessary. Because each patch has the same number of vertices, I can create a reusable pool of patches on the video card. When a patch is needed, the engine selects an unused patch from the pool, and when a patch is no longer needed, the patch is returned to the pool. This technique does everything I need.

Next, I have to figure out how to perform vertex morphing on the patches. Details will come shortly.

(I'm not used to the funny HTML used in these journals :-)

## First Post!

This is my first entry. Just making sure that this is going to work. I'm currently building a terrain engine; details will appear in my journal shortly.