The QuadTerrain LOD (Quadtree Terrain Level of Detail Algorithm) is finished! Actually it's been finished for a while, but the official announcement is this thread. The original thread is over here.

Those who have been following the original thread know what I've been up to, but I'll reiterate and explain this project here in tutorial format.

For those not interested, the summary is this: you can use the downloadable files at the bottom of the page to create a massive terrain complete with Quadtree LOD and easily import it as the ground for your game! Multitexturing, normal mapping and detail mapping are all included in the shader.

The Basics
A terrain is an object or mesh which represents the 'ground' in an outdoor environment. Because it's normally orientated along a flat plane, most terrains can be represented by a heightmap or heightfield, and it is fairly usual to generate the terrain mesh from the heightmap itself.

This is exactly what is done in the Generated Geometry Sample, and in Riemers Series 1 and Series 4.

But a terrain is a very large and complex object. Generating one from a 1024x1024 heightmap results in over a million vertices, which is far too many for an efficient real-time game element.

This is where Level Of Detail (LOD) algorithms come in. An LOD algorithm renders distant objects with less detail, and thus fewer vertices, than close objects. After all, there's no point rendering every rock on a distant cliff face!

There are many different styles of terrain LOD: ROAM, Quadtree, Geomipmapping... even Brute Force (where you just render everything) is a valid method for a good graphics card and a low detail terrain.

This project makes use of a Quadtree method.

The QuadTree
A quadtree is a hierarchical data structure where every object in the structure has 4 children. In 2D space, this translates to a square cut into 4 squares, each of which is cut into 4 more squares, and so on.

In the context of a terrain, suppose you were to accompany each square (quad-nodes) with a mesh, which covers the same area that the square covers. Larger quadnodes would cover large areas, but would have low detail, while small nodes would only cover the immediate area but would render with lots of detail. You could then start at the top 'root' node, and sink down through the tree, sinking further where more detail is needed.

By only rendering the meshes associated with the nodes we sink to (known as 'leaf' nodes), we can cut the detail level of nodes very quickly, especially since we don't need to check any nodes below a leaf node.

The Stitching
Of course, nothing is perfect. Two same sized quadnode meshes next to each other will fit seamlessly, but imagine a high detail node next to a low detail node. The result will be artifacts known as gaps.

This can be fixed by 'stitching', where you either add or remove edge vertices from the nodes so that they match each other. In this case, I removed vertices from the higher detail node, creating a triangle pattern which connects to the lower detail node. In this screenshot, you can see it applied to every edge of every quadnode. In this one, it is applied correctly.

Of course, this isn't as simple as it sounds: each quadnode is now accompanied by 9 meshes, 1 for no stitching, 4 for a single edge stitched, and another 4 for two stitched edges. Since these are generated at runtime, however, they aren't a problem.

The Bounding Frustrums
It isn't only distant objects need to be LODd. Nearby nodes which are not in view because you are looking in the opposite direction need not be rendered at all.

By doing a collision test between the camera's "Bounding Frustrum" (a 3d shape representing the cameras viewport) and a quadnodes bounding box, we can determine which nodes are outside the view and quickly cut a whole heap of geometry from the render. By combining this with the distance testing, we can stop that from sinking further into off-screen nodes as well!

The Multiple Vertex Buffers
One of the things I spent a lot of time on was converting the terrain to run with more than one vertex buffer.

The vertex buffer contains all the vertices read off of the heightmap. In general, it's best to use a single buffer, because each buffer must be rendered with a separate Draw call. Unfortunately, there is a maximum limit to the number of vertices that can be rendered at once on the graphics card, and going above this limit will force the call to be rendered on the CPU (resulting in death by frame rate).

This limit varies, but on my home computer over a million vertices (a 1024x1024 terrain) is just a bit too much.

So, I implemented a nasty and complex algorithm to separate the terrain into a number of vertex buffers, based on the idea that each quadnode could be entirely contained within a parent vertex buffer if we split it correctly. This (eventually) came out well: it is now possible to split your terrain based on a size value. A 1024x1024 terrain split by 512 vertex buffers will come out as 4, 512x512 vertex buffers, with a fifth for all quadnodes which cover an area greater than 512 (only the root node, in this case).

It's worth noting that I may have managed this whilst drunk, tired or otherwise incapacitated, as I cannot remember actually coding it, and have no really idea how or why it works. But it does, and seems to be bug free.

The Global Normal Map
This shader was my first attempt at HLSL (High Level Shader Language), and came out brilliantly in my opinion.

Dynamically changing the geometry can have a nasty effect: although the shape of a low detail node may be very similar to that of a high detail node, the shading can result in a fairly large difference in appearance if done per vertex.

To solve this, I took advantage of the power of HLSL, and told the terrain shader to use a global normal texture rather than per vertex normals. The advantage was twofold: My vertex buffers halved in size, and more importantly shading no longer changes between high and low detail quadnodes.

The Detail Normal Map
Initially, I didn't understand the mathematics behind normal mapping, and thought that by simply adding a detail normal map value to my global value in the shader I could create detail normal mapping. The result looked OK, but it wasn't accurate: the detail normal 'pulled' the global normal upwards. When I tested with a high strength value for the detail normal, this was instantly apparent: the entire terrain was shaded as if it was a lot flatter than it truly was.

It wasn't until after I'd finished the multitexturing that I worked out how to fix this, but when I did the difference was apparent (see below).

The Multitexuring
Using a single texture for the entire terrain has two problems: the terrain is too big to be covered with a single texture with a high enough resolution, and tiling the same ground texture over the entire terrain is very bland. Therefore, I went for a multitexturing approach that made use of a blend texture.

In short, mutitexturing is using more than one texture on the same object, and a blend texture uses it's red, green and blue channels to define the amount of each texture to show. In the sample, Blue represents sand, Green - grass, Red - Foliage and Black displays as Rock.

Quickly back on the subject of Detail Normal Mapping: you can see the difference between my original method, and my final method.

The Versatility
I've done my best to make the QuadTerrain class as versatile as possible, and as a result the different features and the reason for them may take a bit of explaining.

The constructor looks like this:

• GraphicsDevice - speaks for itself. Plug the Graphics device into this field to provide the Quadterrain a link to it.
• Effect - You will need to load the TerrainShader with Content.Load, and provide the resulting effect as this parameter to establish a link between the two.
• Heightmap - Load your Heightmap as a Texture2D, and provide it as this parameter.
  • IMPORTANT: To create the quadtree structure, your heightmap's dimensions must be square, and of the format 2ⁿ+1.
    • Examples of good dimensions are 257x257, 513x513 and 1025x1025.
• QuadNodeSize - The most important versatility element of the class, QuadNodeSize sets the number of vertices along each edge of each Quadnode.
  • Increasing the size of this value will decrease the aggressiveness of the LOD, resulting in less CPU work (because the quadtree is not as deep) and a shorter loading time, at the expense of more GPU work (because there will be more polygons to render). A good idea if you are CPU bound.
  • Decreasing the size will increase the aggressiveness of the LOD, and will decrease the amount of work being performed on the GPU. The trade-off, as you may have guessed, will be CPU work and a longer loading time. A good idea if you are GPU bound.
  • The absolute minimum value for this field is 5: any less will result in an error. The absolute maximum was never tested, but it kind of ruins the whole point of LOD to use a value close to the size of the terrain.
  • IMPORTANT: Like the heightmaps dimensions, this value must be of the format 2ⁿ+1.
    • Examples of good values include 17, 33 and 64.
• VertexBufferSize - If this value is less than the size of the heightmap, the quad terrain will be split into several vertex buffers, each of which will be rendered with a different draw call.
  • In general, a value the same size as the heightmap is recommended, but for a large heightmap it may be necessary to split the Vertex buffer.
  • You can get the number of vertices supported on your graphics card with:
    • device.GraphicsDeviceCapabilitie.MaxVertexIndex
  • IMPORTANT: Like the last one, this value must be of the format 2ⁿ+1.
    • Examples of good values include the size of your heightmap. :D 
• XZScale - This is simply the number of distance units between the horisontal positions of consecutive vertices.
  • Terrain scaling is a great way to increase the size of the terrain without adding extra load. Consider using a smaller heightmap and increasing this value to compensate if you're having trouble milking good performance out of your game.
• YScale - This is the terrain height scaling factor.
  • Making this larger will increase the height of your hills and mountains, but be wary: because the heightmap colour can only be an integer between 0 and 255, making this value too high might make smooth changes between hills and flat area's impossible.

The Update command also has a few important fields:

• CameraPosition - You must plug in a Vector3 representing the XYZ co-ordinates of your camera to allow the terrain to update. This is because the LOD has to know which quadnodes are distant and which ones are near to status them ready for rendering.
• BoundingFrustrum - For the frustrum tests, the terrain needs to know the BoundingFrustrum for the camera. Plug it into this field.
• LODLevel - A scaling factor which is applied to the distance checks which determine the distance a node must be away from the camera to be considered 'not detailed enough'.
  • This value is contained in the update command because, unlike the values in the constructor, the terrain is capable of changing it at runtime. Thus, if your game is running slowly (or if you don't have any performance issues at all), you can dynamically change it to gain performance or improve the visual quality of the terrain.

The Final

Yippy Skippy, the Evil!

The sample is below. To use it in your own game, copy QuadTerrain.cs and TerrainShader.fx into your project, Load the shader, some textures of your own, and add the constructor and update methods! I highly recommend you don't try to build up off of the sample, because it's not great code.

If you want to go into the QuadTerrain.cs code and mess about, go for it! This is my first 'proper' XNA project, so there's no reason to assume I got it all right. Any feedback you can give will be considered and appreciated.

If you use this class (or a modification of it) in your game, give a post in this thread and let me know! I'd love to see what people are doing with it! Mentioning me in your game credits would be nice too, given the time and effort it took me to build this, but you don't have to. :)

And for my final point: The QuadTerrain class is not an excuse to avoid learning how to use Vertex and Index Buffers! Visit Riemers XNA tutorials, Ziggyware, Shawns Blog and all the other sites I can't remember off the top of my head, go though the samples, read and participate in the forums and learn everything you can, and the games you create will be so much better for it!

Download QuadTerrain

Cheers!
Quasar.

http://www.gamedev.pl/projects.php?x=view&id=373

Project name is XNA Submarine

Cheers.

Peter

Looks good! Love the water, and the sky looks pretty awsome too. And thanks for mentioning me!

On another note: there's a few things I forgot in the first post, so I'll add them here:

The Distance Sorting
Overdraw is a term used when the pixel shader renders a distant object, then renders a closer object which completely obscures the distant object. Obviously, rendering the distant object was unnecessary: it didn't end up being drawn on the screen, and rendering it simply hurt the fill-rate.

The GPU can overcome this if the near object is drawn first: when rendering the distant object, the fact that an object with a smaller Z-Buffer value has already been rendered will be detected, and the rendering process will be skipped.

Therefore, it is to our advantage to render the near quadnode before the far ones. Since a list of Quadnodes to be drawn is built seconds before the quadnodes indices are compiled into the index buffer, it's a relatively easy fix to add a sort function in between.

The GetHeight and GetHeightFast Methods
I realise the descriptions of these methods may be a little ambiguous, so here's how they work:

GetHeightFast gets the four vertices around the pixel the point is in from the heightmap (not from the LOD'd geometry), and linearly interpolates between them. This will be accurate along edge lines, but in the middle of squares it may not. The same method is used in the Generated Geometry Sample. It is only a teensy tiny bit faster than GetHeight, so I don't recommend using it.

GetHeight gets the four vertices around the pixel the point is in from the heightmap (also not from the LOD'd geometry), then determines which way the diagonal runs. Once it has determined this, it linearly interpolates using whichever triangle the point is in. This will be perfectly accurate, because it follows the triangles and not the squares.

Note that neither takes into account the LOD. This is brilliant for physics: you dont want objects being thrown into the air due to pop-up, or creatures walking up cliff-faces which are less steep due to larger polygons. But it may result in distant objects being obscured by the ground, or appearing to float in the air.

I realise this is a problem, and have decided to build a 'GetLODHeight' function as soon as I can. I'll report when it's done.

I don't recognise the error straight off... and I can't replicate it here...

Hmm... does the sample work? If so, then that means that the QuadTerrain code is working fine, but is being fed something wrong. All I can suggest at the moment (assuming the sample works) is that you compare the Game1 files in the sample and your project, and look for differences in how they handle the quadterrain and graphics device... in particular during the updateTerrain call (since that's where the error occurs).

 The reason I ask is that that I want the center of the terrain at 0,0,0 so the player will spawn in the middle of the heightmap.  I also looked at going through the constructor and modifying each position by the TerrainWidth*.5 and TerrainHeight*.5 (in the x and z directions) as the allVertices array is being filled up, but I was wondering if there was an easier way.  Any help you could give me would be huge man, I'm really new to XNA programming and I'm learning a ton about it just implementing and rewriting your Terrain class.  It's cool stuff for sure.  Again, thanks for you help.

Hmm... well, I can think of three ways to do it. The first would be what you already suggested: find all the vertex constructors (Ctrl-F would help), and change their position manually.

The second might be easier: feed a different world matrix into the terrain shader. This would change where everything rendered by that shader (the terrain) is positioned.

Both of these have a problem: Functions such as GetHeight will stop working, because they don't take offset values into account. There may be other functions which will also be adversely affected, such as the distance LOD.

Which is why I recommend the third (and easiest) method: move your player spawn point to (TerrainWidth*TerrainScale*0.5) before you start the game. I did something similar with the camera in the sample: it's position is set at (200, 0, 200) during initialisation.

Hello!

Can I use your QuadTree Engine in my Project for DreamBuildPlay?

Your entry in the credits will be certain!

Bethsoftfan: Sure! Can't wait to see what you do with it. :D
 
badwolf: Thanks. :) About the close up problem: could it be your near-clip-plane? If it is, simply make it smaller. Otherwise, perhaps a screenshot would clarify what exactly is happening.
 
As to expanding it into a full engine, I made it for a project I'm working on, so when I do expand it it'll probably become more specific to that project, and less of a generic terrain function. One thing I am planning on adding (once I can wrap my head around instanced models, custom importers, etc.), is a vegetation system. But I'm not sure whether I'll implement this as a part of the terrain or as a seperate quadtree entirely.

I've also finished the getLODHeight function, which takes the LOD into account when getting height values from the terrain, and have added a getNormal function, which provides a 'smoothed' normal. I'm working out how to add a getNormal function which provides more accurate (but less smooth) normals directly from the plane of the triangle. I'll probably have it done after the weekend, and I'll upload the 'new' version then.

Very big thanks and again, your LOD is very good!

But :

It don't want to run.

Code :C# entry C# QuadTerrainHelp submitted by Bethsoftfan. Last modified: August 22nd, 2008 at 15:35:34

      
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15      

QuadTerrain terrain;
Effect TerrainEffect;

protected override void LoadContent()
{
     TerrainEffect = Content.Load<Effect>("MapContent/terrainShader");
     terrain = new QuadTerrain(graphics.GraphicsDevice, TerrainEffect, Content.Load<Texture2D>("MapContent/hmap_10243"),
                9, 1025, 10.0f, 3.0f);
}

protected override void Update(GameTime gameTime)
{
BoundingFrustum boundingFrustum = new BoundingFrustum(view * proj);
terrain.UpdateTerrain(avatarPosition, boundingFrustum, 3.5f);
}

What else I need to add?

This Code are the only Lines, wich handle about the Quadtree terrain (is this expression ok?^^)

Hmmm...

Although I can't say for certain (since I don't know the stats of your graphics card), it's likely that the problem is your vertex buffer size: 1025 is simply too big for most cards, including mine. Try 513 instead.

I also recommend handling a few of the terrains input paramaters: here's the list from the sample. They mostly speak for themselves.

OK, new version uploaded! New additions are the GetLODHeight function, the GetNormalSmooth function and the GetNormalSharp function.

If you're already using it for something, just replace QuadTerrain.cs with the new version.

GetLodHeight
Performs a calculation similar to the one performed by GetHeight, but with a major difference: this function checks the quadtree and uses the vertices of the nodes current Level Of Detail (rather than the highest detail, as GetHeight does).

GetNormalSmooth
Uses the same method as GetHeightFast (bilinear interpolation), but uses the normals rather than the heights. Provides a smooth 'rolling' value between vertices.

GetNormalSharp
Gets the current polygon, and does a cross product on it's vertices. Provides a sharp value, discreet value for each triangle.

The two GetNormal functions are currently untested, so if you try to use them make sure you test them to make sure they work first, and let me know if I screwed anything up. I'm fairly certain GetNormalSmooth will work fine: GetNormalSharp I'm unsure about.

Oh, sorry. I updated the download link in the original post: it now points to the new version.

I'm not sure what you mean about the getHeight function: it seems to work fine in the sample... but I'll take a look and see if I can't track down the problem.

Peter

Hey, awsome! You found a bug!

You're right: the statement should not read terrainHeight - Scale.  I can only assume I was thinking in terms of actual position rather than grid position at the time.

I'll fix it ASAP. Thanks! :D

Hello again!

I got it, I just look at the example code!

But, when I start it, it runns about 2 sec. then a Massage come : InvalidOperationException. The operation was aborted. You may not modify a resource that has been set on a device, or after it has been used within a tiling bracket. At Line 1469!

 I have checked all values, but all are the same as in the sample!

Code : (Updatemethod in my game)

elapsedTimingValue = (float)gameTime.ElapsedGameTime.TotalMilliseconds / 10f;

float xV3 = (float)Math.Sin(iii);

float zV3 = (float)Math.Cos(iii);

Vector3 actualDirection = new Vector3(xV3, .8f, zV3);

Vector3.Normalize(actualDirection);

KeyboardState keyState = Keyboard.GetState();

if (cCamera.Pitch > Math.PI / 2f)

cCamera.Pitch = (float)Math.PI / 2f;

if (cCamera.Pitch < -Math.PI / 2f)

cCamera.Pitch = -(float)Math.PI / 2f;

if (keyState.IsKeyDown(Keys.W))

if (keyState.IsKeyDown(Keys.A))

if (keyState.IsKeyDown(Keys.D))

if (keyState.IsKeyDown(Keys.S))

Vector3 positionOnHeightmap = cCamera.cameraPosition;

float cZ = q.getHeight(positionOnHeightmap.X, positionOnHeightmap.Z);

if (!keyState.IsKeyDown(Keys.Space))

if (cCamera.cameraPosition.Y > cZ + 2f)

//Fall

cCamera.cameraPosition = new Vector3(cCamera.cameraPosition.X, cCamera.cameraPosition.Y - 1f * elapsedTimingValue, cCamera.cameraPosition.Z);

//Remain above the ground

if (cCamera.cameraPosition.Y < cZ + 2f)

cCamera.cameraPosition = new Vector3(cCamera.cameraPosition.X, cZ + 2f, cCamera.cameraPosition.Z);

//5 is camera height above ground

MouseState MS = Mouse.GetState();

BoundingFrustum x = new BoundingFrustum(cCamera.viewMatrix * cCamera.projectionMatrix);

base.Update(gameTime)

Code2 : (Drawmethod in my game)

graphicsDevice.Clear(ClearOptions.Target,

Color.CornflowerBlue, 0, 0);

WorldMatrix.SetValue(Matrix.Identity);

Hey BethsoftFan.

Just a quick tip: if you're going to post code, use the "Format Code Block" button (next to the hyperlink button). Makes it a lot easier to read.

As to your problem, I've never encountered it but Reynolds mentioned it up here, and solved it with his next post.

Reynolds:

Hey man, thanks for responding so fast.  I got some help with the error at school and it turns out that I had to set the device.Indices to null in the drawterrain function.  I put it in right before pass.End() and now the code works fine.  Thanks again for posting so quickly.

Hey cool... that's another one to fix in the next update. Thanks Reynolds: I should have paid more attention to your post first time around. ;)

Cheers!
Qu.

Oh ***, I couldn't saw it, I go out and buy new Glasses, It wasn't with ... you know what I mean, but I don't know the english word! Really Sorry for that.

Thank you again!

Edit : The bad words list works perfactly fine! :-D

Qu:

Hey, awsome! You found a bug!

You're right: the statement should not read terrainHeight - Scale.  I can only assume I was thinking in terms of actual position rather than grid position at the time.

I'll fix it ASAP. Thanks! :D

Great!!! that I can help:)!!!

Does anyone try tu use this nice project on xbox 360? It is crashing in many places for me and I can't figure why?

Cheers Peter

Hi Qu.  I was able to get your QuadTerrain class working in my game, but I need a little assistance from the developer ;-)

I want to instantiate multiple QuadTerrain classes to provide a "continuous" terrain capability in my game.  As the player moves through the world I perform Frustum checks and load/render the appropriate QuadTerrain containing that particular section of the world.  All of this works fine, with one exception.

I need to pass an offsetX and offsetY parameter to the QuadTerrain class so that the particular section of terrain is drawn at the proper coordinates in the world space.  The problem is that once I do this the QuadNode function throws exceptions because it is expecting the x/y coordinates to fall within the height/width of the heightmap loaded.  Can you provide some guidance as to where in the code I would need to apply the offsetX and offsetY values?  When I apply them within the QuadNode class it throws exceptions, so apparently there is something in the code logic I am not seeing.

Thanks in advance for any help you can provide.

Thanks,

Mike