Terrain generation and rendering is an area that can seem pretty complicated, but it is really not. If you do a search for “Terrain Rendering,” you will find a decent amount of information from the ROAM system, to geometry clipmaps. Basically, when rendering terrain, a level of detail system is a necessity. Having studied the different types of terrain LOD systems, I was confused; but before I delve any further, my first implementation of a naive terrain system for Destination was a version of Geometry clip mapping, where all work was done on the video card. In the article, my views may seem somewhat cynical, but I am a perfectionist –the two go hand-in-hand. I will briefly cover some of the different rendering techniques, listed from worst to least worst, then follow with my new implementation.

The ROAM system is an oldie, but a goodie. It represents what happens when someone implements a terrain system after getting hit in the head with a blunt object. In the ROAM system, there are 16 different terrain tiles. These tiles are meant to fit together where different LOD sections meet, in order to prevent seams from appearing –I guess. This system –even when it came out– was a bad one and I shudder when thinking about it. When the point is to limit the amount of draw calls, this system falls flat on its face after drinking too much! If anyone suggests to use the ROAM system –run.

Geometry clipmaps are perfect! They are intuitive, and simple to work with — unless you use the first version you can find on the internet. The first implementation is taken from ShaderX 6, page 103, chapter 2.7, “Practical Geometry Clipmaps for Rendering Terrains in Computer Games,” written by Rafael P. Torchelsen, Joao L.D. Comba, and RUI Bastos. In their implementation, they have three different tiles to create their terrain. Great, this isn’t bad! But, after reading further, you find that their clipping ring has three different buffer zones. These zones are meant to make the transition between LOD’s blend correctly. The tiles can move within this buffer zone, which is a strange way of implementation. The one good thing, is that they choose to use the CPU for deform the terrain and build it, then send it to the GPU to be drawn. This is smart because the terrain doesn’t change often, so the CPU-GPU interaction is little to none. In a scale of 1 out of 10, this implementation is a 6.

Another example of clipmaps is in Chapter 2 in GPU gems 2, page 27, “Terrain Rendering Using GPU-Based Geometry Clipmaps,” written by Arul Asirvatham, and Hughes Hoppe. In their implementation, they do all work on the GPU. They have 4 different terrain tiles (better than the ROAM’s 16), and their draw calls per frame is 35 (using instancing) and 71 (without instancing). They make the same mistake that the previous example does: add a buffer zone between LOD’s

I will not go through the rest, because most are all like the previous two. In the GPU gems example, the height of the terrain is read as a texture in the Vertex Shader, which is great, right? I mean, the trend is to offload all work from the CPU to the GPU? To be fair, at the time the article was written, DX10 was not out. However, I still see this common mistake made: redundant calculations! Each frame, the height for the terrain is read in the Vertex shader, FOR EACH VERTEX! Remember, this is a stage before triangle culling and depth testing occurs. So, if 100,000 vertices are sent to be drawn, all 100,000 do a texture fetches in the Vertex shader –EACH FRAME!

Now, my implementation.

I do a version of geometry clipmaps; however, mine does not require any complex tile pieces and avoids redundant calculations in the Vertex Shader. I have tiles, 66×66 in size that overlap each other by one column and one row –that’s the reason for the size of 66, instead of 64. So, I build a static index buffer, and a static 2 component position vertex buffer, and send the height in on a separate stream. When the tiles overlap each other by one row and one column, there are no seams –even where the heights vary dramatically. This is because the overlapped region of the tiles contains the heights of the neighboring tiles, so the heights are equal and thus no seams occur. The only part that is a little difficult is ensuring proper translation of the different tiles, which took me a couple of hours to get right. The first picture is the complete clipping rings, the second is so you can see how the regions are overlapped, and the third is how the AABB’s are helpful for frustum culling. Don’ t pay attention to the draw calls because I have all culling turned off.

This next picture might scare some of you, because you initial reaction will be like mine, saying to yourself, “This cannot work!” The first picture is an areal view of the ground normals, as you can see the different LOD’s create different normals, because the geometry is different. There is also no height applied to the terrain, its flat at this point, but I used the normals to ensure that the heights were read correctly and matched with the different LOD’s using the normals. As you can see, they do match, but LOOK, the normals are different –this cannot work! Just wait . . . and keep reading.

In the next images, I took out one tile from each LOD so you can see the size difference, the little overlap and see how the normals appear. What is important to note, when scaling terrain like this, you MUST REMEMBER to transform your normals in the vertex shader by the Inverse Transpose of your world matrix! This is what happens when you do not. Notice how everything is red? Red represents the x coord. For a terrain such as this, it should be dominated by the green (y component), which indicates the normal is pointing up. In this case, most of the normals are pointing down the x axis, which is obviously incorrect.

This is what happens when you correctly apply the Inverse Transpose of the world matrix to the normals in the vertex shader. This reorients the normals properly in world space, and leads to this picture.

If you look hard on the bottom right hand side of the picture, you will see the finest LOD. The change is so minor it is very difficult to tell. A good way that helps alleviate LOD changes is to increase the distance of the tiles. I have a Cell spacing of 7 right now, at 64×64 unit tiles (one row and column is overlapped so the size is 64 x 64). From the pictures above you should note that I have a 4×4 grid for the finest LOD and each grid that surrounds it is twice as big as the next. This helps alot with placement. So, it is very hard to tell an LOD change if it is happening at 7 * 128 = 896 units away. If I change the Cell spacing to 1, then LOD becomes very apparent and the illusion breaks completely; however, so would every other LOD system if change to such a setting. Some may be scared having a setting of 7 or 10 for their cell spacing, but there are absolutely no problems with such a setting, the terrain will not appear pointy from being less tessellated. In most cases, it should be set to maximize the view distance while taking nothing away from the immediate visual appearance.

This is another view from the air so you can see the obvious difference in the LOD’s. I used the same texture tiled across the terrain for a very specific purpose — the human eye is excellent at seeing breaks in patterns and picking out discontinuities. So, if there is a problem with the terrain, I should be able to spot it very easy! The next few pictures point out some possible problem areas. The first picture is a picture an area where different LOD’s meet, and as you can see there is a difference in the normals.

The next picture is a close up up the normals, and you can see the difference is very noticeable now.

As I turn on the lighting, you can see that what I thought was a problem is not. The difference is completely unnoticeable.

Before I continue further, I want to point out that the above problem spot in the picture directly above is at a point where the LOD2 meets LOD3, which should be around CellSpacing * TileSize * LOD distance away from the viewer. (I chose to turn off the the updates to the video card so I could examine my terrain.) For my system it is, 7*128*3, which is 2688 units away from where the camera should be, so even if there was a small difference, at that distance, it would be 100% not noticeable. 3D programing is not about copying reality, its about doing what ever you can to make it close as close to reality as possible using what ever means possible. So, if something really far away appears correct, even though at close inspection it is completely wrong — it doesn’t matter. As long as the viewer never gets close enough there is no problem!

In the first of the two pictures above, I wanted you to see what the terrain looks like. My draw calls for the terrain range from 9 to 22 at the highest, which is very very small.  I only update the terrain when a player moves outside of my inner ring of the fine LOD. (I have two rings of the finest LOD.) This means that a player has a 128*cell spacing area to run around in and no updates need to sent to the video card. It takes .007 seconds to build and send a tile –regardless of LOD size– to the video card for rendering. So, when an update is made, I will only need to update 5 tiles at the most, which means a 5* .007 seconds = .035 seconds to do an update.

Another optimization is to pre compute the entire vertex buffer and store it in ram, then simply copy out what is needed and send it to the video card when an update is needed. I can store an area approximately 8 square miles, and precompute and store everything read to be sent to the video card as updates are needed in about 100 megs of ram. This would include an off screen staging area where I would pre load and pre compute terrain in the background as it needed. After completing this optimization, my update time per tile dropped to .0001 seconds.  Also The second picture is what the triangle mesh looks like. You can see that the triangles are passing through my far clip plane, that’s because a cell spacing of 10 means my terrain is drawing in a radius of  10*(128 + 356 + 512) = 10240 units, and my far plane is set to 10,000. The red circle in the first picture is of two large houses that I placed into the terrain so you can get an idea of distance. The houses are large two story houses too! Also, note that I could add another LOD to extend the ring which would mean a viewable distance of 20,000 units and only increase my draw calls by 2-5 per frame, and add 8,000 to 20,000 more triangles, which on today’s hardware is not a lot.

That is about it. If you have any questions about my implementation, e-mail me at smasherprog@gmail.com.