I'm hoping to solicit information for everyone to share in this thread about best practices when dealing with large terrain.  While this topic can be application specific, generally some techniques are better than others. 

All insight is welcomed here.  Feel free to talk about what your doing and why you think its a good example to follow.

---

1) The CLOD/LOD/Display Technique:

• Brute force
• Geomipmapping
• Roam
• QuadTree
• Others
• Combinations of the above.

2) Heightmap Generation

• Use 3d party application e.g. Terragen
• Simple bitmap/raw manipulation
• Full blown game editor with this feature.

3) Terrain Patch's.

• 16 vs. 32 vs. 64 vs. 256 sizes
• square vs. rectangles and other non square patches
• Dealing with edges of patches

4) Texturing Techniques

• Texture Bombing
• Detail texturing
• Height based selection
• Opacity based selection
• High/low based selection - choosing texture based upon slope

5) Misc.

• Single vertex buffer vs. multiples
• Single index buffer vs. multiples
• Converting heightmap into model(s) in processor v.s. using heightmap to generate at runtime
• red channel for heightmap and other channels for something else

Thats a good bit of topics to banter about.

Let me start with a few questions and ideas of mine.

1) I'm debating whether to go with Brute force or geomipmapping.  The problem I have with most clod techniques I've seen in action, is that the normals change as you pop trianges while moving the camera.  This is much more noticable at a dusk/dawn light setting.  Brute force doesn't have this problem.  But it ends up sending a lot more triangles to the video card.

I am left wondering what is really happening on the card.  How often does vertex, index, and texture data get left on the card between frames vs. the card having to pull the data every frame?  If the GPU is pulling in data all the time, setting/swapping index buffers wouldn't be a big deal, because you have already got this cost.  But if I'm having to resubmit vertex data to generate new normals for the lost/added triangles, that would be more costly.  Granted you will probably not be doing this every frame unless your doing a low flying jet fighter based flight sim, but none the less it might be semi frequent and noticable.

2) I'd love to create  a full blown terrain editor in my editor, but time is the problem.  If there is an easy to use 3rd party application that would do most things I want, I'd use it.  But most that I've seen don't really help with combining differing landscapes.  I need the ability to seemlessly join one landscape with all of it's surrounding neighbors.

3) I'm probably going to go with 256 patch size to minimize the draw calls/effect changes.  No idea how to deal with patch edges at this point.

4) My texture technique is open to all suggestions at the moment.  It will be heavily influenced by how to seemless join patches.

5) I'll be using one vertex buffer with one index buffer per patch.  I might be tempted to try a single index buffer if I can keep the index buffer resident on the GPU vs. reloading it per frame.   Its really a pity you cannot supply the card with an array of index's to use. In essence an index of index's.  Perhaps you can do this in a geometry shader.

I'll probably be converting the terrain patches into models, with collision info in the models tag.

Here's my weird thought to add that I've never seen before:  The last bullet point I mention using the red part of the color for the heightmap and the others for something else.  Perhaps the blue channel can be the x bias, and the green channel can be the z bias.  These values allow the respective x and z values of the vertex to move in or out from thier current spot.  Just like the red channel allows the y to grow/shrink, they behave the same.  Granted you would want very small ranges of movement vs. what is possible with the height.  But I think this would allow for cliffs and even overhangs to exist. 

For example normally if one vertex had a value of 0,0,0 and it's neighbor had a value of 1,50,0, this would be a very steep slope.  A good mountain slope but not an actual cliff.  With the bias of say 200 on x we could recitify that. In the heightmap, a value of 123 would not move the vertex/triangle.  But anything above that amount would move the vertice/triangle toward's one neighbor and anything under that would move the vertice/triangle toward the opposite neighbor.  Perhaps values of 56 and 200 would place the vertice under/above its neighbor.  Of course if the heights were the same, they would co-exist.  Anything above/below those thresholds would slide past thier neighbors.  (Overhangs)

Creating these bitmaps would involve writing to the green and blue channels seperatly.  In essense drawing a line.  This line becomes a possible cliff with the right values. These channels would be mostly one color (123), with the actual cliff's showing up as lines with stronger/weaker values. 

You might have to modify the UV coordinates in some cases.  You might be able to use these others channels to help select a texture to use in the shader.  Rock vs. grass.  If a cliff, use a rock texture.

Finally in the alpha component of the shader, you can paint the walk zones for your game.  You don't want them walking up the cliffs, and you also don't want them going out of the game boundaries.  Perhaps you keep them strictly on the path/racetrack areas.  The mountain is too steep, paint it.

CLOD and GeoMipmapping aren't the same thing. CLOD (Continuous Level Of Detail) is the domain of ROAM etc, whereas GeoMipmapping is all about raw power and discrete LODs.

In my terrain system, I have made the following choices. I'll describe them here, rather than directly answer your questions, because my requirements may be different from yours.

1) Terrain data is a (2^n+1)x(2^n+1) texture in DDS R32F format. That means I can have high mountains without height quantization problems. My typical size is 1025x1025, with 2 meters vertically per sample, for a level size of slightly larger than 2km * 2km. My game has pretty fast vehicles, as well as human-sized avatars, so 2x2km is really the minimum size I can accept for good gameplay. Some levels may be 4x4km. I can also do stretchy versions (1x4, etc).

2) Each patch is 129x129. The edge vertices are shared with the next patch. Each patch can get LOD-ed down to 65x65, 33x33 or 17x17. I decided to do this, rather than use fixed-size blocks that change extents, because it was easier to implement. There's a hash grid at the top for the blocks to do culling and whatnot.

3) One vertex buffer per block. I calculate the buffers on demand at runtime. If I have to change a bunch of blocks all at the same time, it generates a jerk in frame rate, so I will later limit the number of blocks re-calculated per frame, or I will push it off to a thread. Given that my shader is so expensive, I don't think the different buffers cost much. Also, I've heard that switching vertex formats is much more expensive than switching vertex buffers; don't know how much truth there is in that.

4) One index buffer per LOD per border combination. I only allow differences of 1 LOD between neighboring tiles. The higher detail tile will generate degenerate triangles along the border to the lower-detail tile along borders. This leads to 16 different index buffers per LOD, easily generated based on a bit mask of which neighbors are lower detail. Because there are 4 LODs, this means a total of 64 index buffers that get re-used wherever needed.

5) The vertex buffers only contain position. I generate texture coordinates by projecting the ground plane, and I use a world-space normal map for normals. This makes for slimmer vertex buffers :-)

6) World-space normal map means there is no lighting pop when changing LOD. I'm not doing geomorphing; the popping I get is not bad enough to warrant the extra work. The normal map is pre-calculated.

7) I texture using a control texture based blending shader. I blend 5 different layers of textures (rock, sand, etc) based on one RGB control texture. That plus the normal map gives me 7 textures used, but it runs pretty well. I use the alpha of the texture layers to drive the blend between the layers, so that I get fringing between grass and sand, say, rather than the dull plain blend.

8) I have a heightmap compiler content processor which compiles the texture2d<single> into a build heightmap asset. That asset contains blocks of 129x129 float data arrays, as well as references to the shader and textures. Parameters for the processor are used to specify the control texture and the layer textures. This processor also builds the normal map texture, and it verifies the control texture so that the sum of the layers ends up between 0 and 1 (if the sum is >1, I'd get over-brightening).

Hmm... Yeah, that's about it, I think. Works pretty well, except for that stutter when switching tons of blocks at the same time.

I've seen others refer to to geomipmapping as CLOD.  I even have a book that says it is.  But to be honest, I trust your opinion more.  I'll change the post to "CLOD & LOD" to be more accurate.

1) How did you generate your terrain data?  Ever considered combining multiple terrain data in game? (aka. Oblivion)

2) 64 total patches seems adequate.  It seems like you have an un-named home grown algorithym in use.  The WatteLOD Hash technique similar to geomipmapping.

3) I guess I shouldn't be surprised you didn't use one vertex buffer given the size involved.

4) Reusing the ib's makes sense, just not sure about your 16 different IB's per LOD.

5) Very clever stuff! I may have to try this if I can figure it out.

6) This will solve my main concern of changing normals.  Another great idea.  How did you generate the normal map? Programatically or with a tool? 1025x1025 4 channels?  Another very cool thing about this is the fact that the normals do not need to be passed through the vertex shader at all (faster code).  The are simply just used in the pixel shader.  I love it. 

7) I'm not sure if I want to use PS 3_0 yet.  So I may have a limit of 4 textures.  How did you get 5 textures out of three color channels?  I like the concept with the alpha channel, so I'm guessing that "red != rock" for example.  Instead you use a range of a color "0 to 50" or such for the rock texture instead.

Like always, very informative!

I do a very similar system, with a couple of minor differences.

1) I use a fractal system to generate the heightmaps instead of a bitmap.

The fractal is generated at 512 by 512, each pixel of this is a patch of land. 2048 by 2048 metres in size, sorry old school coder so everything ends up as a power of 2

This gives me roughly a million metres per world,  which is very small I know but gives enough variation in terrain to make it feel right.

The same fractal generator is used to generate each patch of land at 256 by 256 so you don't get any nasty edges that don't meet between patches.

I then use a stack based system to add and remove patches that the camera can see.

The problem I have at the moment is getting the fractal terrain generator fast enough to be called on the fly. At the moment I cache 16 or so patches and generate new ones as I need them, which is fine when you are moving slowly, but in the descent to planet sequence you can get judders as you pass the limits of the cache and lots of patches have to be generated.

2) the patches are rendered using a very simple level of detail algo, I pre calculate 0.5, 0.25, and 0.125 scale versions in the patch generator and pick which one to use based on distance from camera.

Can't put up any screen shots or videos yet as this may be used in a commercial product, but would love to see some shots of yours.

 

gorky:

1) How did you generate your terrain data?  Ever considered combining multiple terrain data in game? (aka. Oblivion)

Photoshop CS2 FTW! It allows me to paint in 16-bit and 32-bit precision grayscale, and there are a number of filters and blending modes that make it easy to get the result you want.

For scenes, I have an XML file that can instantiate entities, which are just collections of behaviors. One behavior is "model" and another behavior is "collision model," so putting, say, a building in is a matter of declaring and entity with those two behaviors, and the parameters for the behaviors (the model mesh name, position and orientation in that case). I actually have behaviors for particle systems, vehicle physics, input controllers, weapon types and even simple "drone" controllers, so I'm close to having a "living world" at this point.

4) Reusing the ib's makes sense, just not sure about your 16 different IB's per LOD.

You have no choice. Each edge may neighbor a tile of the same resolution, or a tile of lower resolution. (higher resolution counts as "the same") Two states for four edges equals 16 different IBs. The fact that I LOD constant-world-size tiles means that I need a different IB set per LOD. If your tiles are always, say, 33x33, and you instead split or collapse a top-level quad tree, then you get away with 16 IBs total, rather than 16 IBs per LOD set. You would instead have to make the IB address the right indices using some trickery such as setting a different vertex stride, or re-shuffling the vertex buffers. My method was simpler to implement, which is why I chose it (programmer time is scarce when you have a demanding day job and a family with three kids and a multitude of pets...)

6) This will solve my main concern of changing normals.  Another great idea.  How did you generate the normal map?

Using a small (2x2, I think) Sobel filter in the terrain heightmap importer. The normal map is actually output as part of the terrain heightmap compilation process. Because the input is (2^n+1) in size, the normal map itself of size (2^n) contains normals for the faces between vertices, rather than for the vertices, which is actually exactly what you want.

Sadly, I can't claim credit to this technique; I heard about it on some online forum years ago. But I can claim credit for unabashedly adopting and promoting it ;-)

7) I'm not sure if I want to use PS 3_0 yet.  So I may have a limit of 4 textures.  How did you get 5 textures out of three color channels?  I like the concept with the alpha channel, so I'm guessing that "red != rock" for example.  Instead you use a range of a color "0 to 50" or such for the rock texture instead.

My shader is ps_2_0. You get 8 textures in that profile. You only get 4 textures if you're using ps_1_1.
I actually use a Dxt5 compressed texture with RGBA information. The formula for the output color is similar to:
float4 control = tex2D(ControlSampler, uv.xy);
float baseweight = 1.0 - dot(control, float4(1,1,1,1));
float4 outcolor = tex2D(BaseMap, uv.xy * 37) * baseweight;
outcolor += tex2D(RedMap, uv.xy * 38) * control.x;
outcolor += tex2D(GreenMap, uv.xy * 38) * control.y;
outcolor += tex2D(BlueMap, uv.xy * 38) * control.z;
outcolor += tex2D(AlphaMap, uv.xy * 38) * control.w;

It's actually slightly more complex because I use the alpha value of each of the maps to define fringing. In my custom terrain processor, I walk through the control texture, and normalize it down so the sum of components is never greater than 1.

Stainless:

1) I use a fractal system to generate the heightmaps instead of a bitmap.

We did that for There.com. However, that has the problem that artists can't generate the kind of planet they want, without adding a lot of control data for the fractal, which in the end ends up being as much space as just storing a heightmap would be. It also turns out that, without significant effort, fractally generated landscapes grow boring very, very quickly, because the computer doesn't know how to generate "interesting" or "good" terrain for specific gameplay. And the "significant effort" really means man-years in coming up with different specialized algorithms for different types of terrain (stratified canyons, citiscapes, river deltas, etc) and then different algorithms for stringing them together to make for interesting gameplay. "Rolling Hills" or "Craggy Mountains" are pretty easy, but also not very useful for most game types.

It may be that your kind of game is of the kind where fractal terrain makes total sense, though. I'm just describing what experience I had that made me decide against that approach. It is a lot of fun to poke at the various terrain generator functions, and see what you can come up with, though!

jwatte:

My shader is ps_2_0. You get 8 textures in that profile. You only get 4 textures if you're using ps_1_1.

Grrr!  Another misleading site for me.

http://en.wikipedia.org/wiki/High_Level_Shader_Language

At least this MSDN one that Shawn supplied is more correct.

http://msdn2.microsoft.com/en-us/library/bb219846(VS.85).aspx

jwatte:

We did that for There.com. However, that has the problem that artists can't generate the kind of planet they want, without adding a lot of control data for the fractal, which in the end ends up being as much space as just storing a heightmap would be. It also turns out that, without significant effort, fractally generated landscapes grow boring very, very quickly, because the computer doesn't know how to generate "interesting" or "good" terrain for specific gameplay.

I have added a little frigg, I store a small table of special locations in the planet definition.

These are patches of land 2048 by 2048 that are hand built. They do the settlements, caves, etc. that give that bit of variety you need.

My fractal system does produce very believable planets though the challenge would be to extend it to have an environment engine on the top to generate vegetation, rivers, etc.

 

 

very believable planets

Oh, I believe you! If all your game requires is "believable" then that's fine. However, it's been our experience that gameplay typically requires something different than "believable." In fact, if you played a large-scale terrain game on Earth itself, it wouldn't be that great from a gameplay point of view.

gorky:

Grrr!  Another misleading site for me.

http://en.wikipedia.org/wiki/High_Level_Shader_Language

At least this MSDN one that Shawn supplied is more correct.

http://msdn2.microsoft.com/en-us/library/bb219846(VS.85).aspx

Did you fix it? Thats the beauty of wikipedia...

 

It's fixed. At least until someone else breaks it :)

jwatt,

I have a few questions about your implementation, if you have time to answer:

Regarding 4, I've been able to choose the level of detail of a particular terrain patch by distance/pixel error tolerance but this allows for neighboring patches LOD's to have differences of more than one off.  How are you determining which level of detail to use for each terrain patch when introducing the restriction that neighboring patches can only be one LOD away?  I understand the requirement but I have a hard time enforcing this requirement as changing an LOD of a particular patch could require changes to all neighbors which could require a change to all neighbors...

Regarding 6, how do you use the normal map created during the content pipeline processing in the shader?  I'm assuming the sampling occurs in the pixel shader but I suppose it could happen in the vertex shader as well.  Any implementa