The Terrain Engine
This article represents my thoughts on a general terrain engine.
Usually, when I render a chunk of terrain, I submit a bunch of triangle strips to the renderer for each strip, and assemble them into a square. Optimally, I would prepare data structures that could quickly be submitted to the given API for fast rendering. However, the data I prepare for terrain rendering here could change since I want to allow dynamic lighting resulting from the sun passing across the sky. So, I won't really deal with display lists or fast vertex buffers for now.
What I will be discussing is how I plan to deal with occlusion and level of detail.
My plan is to start out making a 1024x1024 grayscale texture representing a 1 square mile chunk of land (5 ft per pixel). This will be the heightmap I'll work with, and blend two textures (grass and dirt) on the surface based on the slop of the terrain. High slopes will have more dirt than grass.
At the highest level of detail, I'll start out working with 128x128 element terrain chunks at 5 ft per cell, and take the level of detail down to 3 levels. This means at level 1, 2 and 3, respectively, the 128x128 section could be drawn with a 64x64 (10 ft per cell), 32x32 (20 ft) and 16x16 (40 ft) chunks of data. I'll also need to worry about the border intersections of those squares of land, and put some thought into possibly working with shapes other than squares at a time.
I will also want to render back to front without depth testing (setting depth function to always fits the fill, since disabling depth testing usually keeps the polygons from writing their depth data). So the orientation and position of the viewpoint will be important here.
I'm not planning on incorporating smooth transitions between levels of detail. When a higher or lower level of detail is called for, the new detail will "pop" into its new state immediately.
So, how do we do this...
First, let's look at how intersections between levels of detail will look...
This is how I envision LOD intersections will be handled. I can't just render a lower LOD adjacent to a higher LOD terrain, since there will be gaps between the triangles. Rendering them like this will prevent the gaps. This means not only do I have to prepare full square sections of terrain for each LOD, I also have to prepare intersections. It would also be wise to tell the renderer the range of the terrain I would like to draw instead of always rendering a full square.
I don't imagine memory will be too much of an issue. Even if I generated LOD's all the way down to 1x1 chunks, it wouldn't take up more than 1.5x the memory of storing all the original 128x128's.
Perhaps I could store a mid-cell height value for purposes of intersections... that might prevent me from having to generate a single strip for purposes of intersections between LOD's...
I only have to worry about adjacent squares. I don't have to worry about corner-corner intersections, thankfully (it turns out I do, see below).
So, I provide the terrain renderer with the square I want to render, the position and direction of the viewpoint so I can render back to front, and at each border, whether or not to render to intersect with a higher level of detail (4 flags). During setup, I would need to make sure these borders have the mid-values they need. A higher rendering function will then be set up to render all the terrain squares needed to render to world around the viewpoint, figuring out which chunks to render and which to ignore based on occlusion and possibly distance.
I will assume that I will never have more than a difference of 1 LOD between squares.
The higher level rendering function will need to be provided with setting that determine when it renders lower levels of detail. The terrain loading routine will have to be told how deeply to LOD the terrain and automatically provide the mid-cell values to the lower LOD's. Each cell will need a mid-cell for top, left, lower and right, even though only one will be used at the edges and two at the corners. Hmm... how will that look...
and 
show what corner
cells will be rendered like depending on the placement of higher and lower LOD's.
A very computable problem. It appears they will have to be handled as triangle
fans for each cell. That will slow down the rendering, but I only have to do it
for the border strips.
It will be important to not have to do a lot of moving around of data as we move from one area to another, requiring more terrain chunks to be loaded and others to be dumped. The optimum solution would be to re-use what we have allocated and set world coordinate values so that they are used properly. This is probably best serviced using an index array of some sort, and how many of those we plan to use will need to be provided to the terrain world object as well.
Initial results
When I use initial terrain chunks of 128x128 cells, and 4 LODs, the worst case rendering is around 210k triangles and 26 fps. When I use terrain chunks of 64x64 cells with 4 LODs, the typical rendering case is 40k triangles at over 100fps. So I think I have my primary test-bed. I'm using LOD levels 0-4.
As I continued developing, I actually found a number of cases that I would have to worry about. The following graphic addresses joining a lower detail LOD with higher LOD's in all directions (assuming there is only 1 difference in the LOD).
Notice the various types of triangle arrangements that are necessary at the corners. The edges can be rendered as 3-element triangle fans in a loop. Two of the corners are 4-element triangle fans, and 2 are 4-element triangle strips. They aren't pretty, but they will ensure that there are no holes. It was an arduous task, but the methodology was fairly simple if not lengthy (including retrieving high or low resolution height values, illumination and shade values, and keeping texture coordinates and vertex locations consistent).
Whenever I knew I would need to perform LOD joins, I just submitted the next higher LOD version of a terrain block as well as the one I was primarily rendering, and referred to the higher resolution points as needed.
Other rendering strategies involve rendering each terrain cell as an X shape, which can actually simplify the geometry of the LOD joining at the edges.
There is one more possibility that I stumbled upon while I was exploring the rendered terrain:
The cell at the lower right is a 2x2 cell of a higher LOD terrain. The upper right and lower left cells represent the renderer joining lower LOD terrain chunks above and to the left of the higher LOD terrain. The cell at the upper left represents a cell of a terrain chunk that doesn't need any extra triangles to join up with adjacent chunks. However, there is one problem. The highlighted point in the upper left chunk would be an averaged height, since it's a lower LOD. The same point in the higher LOD chunk and the two adjacent lower LOD chunks would be the higher resolution height. So this is one case where a hole still remains (and does occur in rendering). I had to check for corner-corner adjacency and submit the higher LOD along with the lower LOD terrain, and temporarily replace the affected corners until rendering was complete.
I've kept the base chunk size at 64x64 for now. I also keep a table of distances to guide the render as to when it should implement lower LODs. It's important to set up that table so that no two adjacent blocks would use LODs of difference greater than 1. The easiest way to do this is not allow a difference in distances of less than 1.5x the world size of a terrain block. This way even distance across full corners won't cause more than a difference of 1.
Other terrain rendering algorithms sometimes call for select distant blocks to be rendered at a higher LOD, even though they are far away. I haven't gotten into that yet, but this algorithm using that method would require parsing through the planned rendering and making sure the adjacent LOD's aren't off more than 1 from each other.
Future plans