I was wondering... I've done my research on the various methods of Terrain LOD (I've finally settled on a Quadtree method, for it's simplicity), and I'm ready to begin implementing it.

So far I've got a QuadNode struct, each of which contains an array of 4 QuadNode structs (except the leaf nodes, of course). I plan to add the relevant geometry to each Quad Node, and display it only when necessary.

What I'm wondering is how I should implement the geometry. I had planned to make a class (called QuadTerrain), which contains all the information and functions to create, update and access the terrain an associated data. Then, in code, all I'd have to do would be create a new QuadTerrain and call various functions on it. Is this possible, or am I following a dead end? Should I use a custom content Processor, and if so, can I use it in the same 'user friendly' way? Can I use the MeshBuilder class, the heightMap.getpixel function and all the other content pipeline stuff in a normal class?

I tried various things for a few hours before coming here, but didn't really get anywhere... so any help would be appreciated. Examples or tutorials would be brilliant. :)

Thanks,
Qu.

I've been going through a similar process in trying to find information on quadtrees.  Here are several of the articles that I have come across:

http://www.kyleschouviller.com/wsuxna/quadtree-source-included/

http://www.google.com/custom?domains=GameDev.net&q=quadtree&sitesearch=GameDev.net&client=pub-3167291168602081&forid=1&ie=ISO-8859-1&oe=ISO-8859-1&cof=GALT%3A%23339966%3BGL%3A1%3BDIV%3A%233366CC%3BVLC%3A3366CC%3BAH%3Acenter%3BBGC%3AFFFFFF%3BLBGC%3AFFFFFF%3BALC%3A3366FF%3BLC%3A3366CC%3BT%3A000000%3BGFNT%3Agray%3BGIMP%3Agreen%3BLH%3A50%3BLW%3A225%3BL%3Ahttp%3A%2F%2Fimages.gamedev.net%2Fsitelogo.gif%3BS%3Ahttp%3A%2F%2Fwww.gamedev.net%3BFORID%3A1%3B&hl=en

I think you would be able to achieve your goal with a quadtree and these tutorials should be a good place to start.

Thanks for that, I've also spent time looking into Quadtrees. I think I've come to understand them quite well.

What I need now is the other stuff, for making and updating the terrain geometry. I'm not sure if I'm going to need a custom content processor, whether or not I should have each chunk as a seperate model or as a mesh within a main 'terrain' model, and how to implement things like meshBuilder in a custom class in either case. I'm detemined to get it working, but I need some help or I'm going to spend hours puzzling over every simple thing I come across. :)

Alright, I spent another few hours and finally worked out why I couldn't get this working: I didn't properly understand content processors. I didn't realise you could use them to create custom classes in addition to predefined classes such as Model Content.

I have only one question left: Should each QuadNode's geometry be represented by a Model, or is it possible to represent each one as a mesh within a larger "terrain" model? If it is, are there any advantages to this?

Each quad-tree can either have its own vertex and index buffer or can share part of an index and vertex buffer, orrrrr, a combination of those two.

I've always implemented it as a graphics mesh of indexed primitives, and a physics mesh created from the the same mesh. I haven't implemented anything through the content processor yet, but I highly recommend going that route, as calculating the entire terrain at runtime everytime takes awhile, especially if you do it on the 360.

" as calculating the entire terrain at runtime everytime takes awhile, especially if you do it on the 360."

On the other hand, if you want to deploy for 360 then presumably you will eventually want to make it available to others and with the limit of XNA games being only 150 MBs you want to make your data set as small as possible.

150MBs? Didn't know that. What a jip. I think I'll stick with my original idea of making it only for Windows...

I'm not sure I understand what Lord Ikon said about sharing part of an index and vertex buffer, but so far I've made the quadtree structure and have started generating geometry. Each QuadNode has it's own seperate Model, whose edge verticies match those of the one next to it (I'll either work out edge stitching or just cheap out and use skirts later on... for the moment I just want a working terrain).

I'm still not sure if this is the best way to do this... but at least I'm actually getting somewhere. Please tell me if I'm doing anything wrong, as I'd rather not find out the hard way.

Quasar:

150MBs? Didn't know that. What a jip. I think I'll stick with my original idea of making it only for Windows...

I'm not sure I understand what Lord Ikon said about sharing part of an index and vertex buffer, but so far I've made the quadtree structure and have started generating geometry. Each QuadNode has it's own seperate Model, whose edge verticies match those of the one next to it (I'll either work out edge stitching or just cheap out and use skirts later on... for the moment I just want a working terrain). I'm still not sure if this is the best way to do this... but at least I'm actually getting somewhere. Please tell me if I'm doing anything wrong, as I'd rather not find out the hard way.

If you'd like to see the code and example the link to the engine is in my sig. v0.182 is fairly simply compared to v0.19 and newer, and you would simply want to look in the Entities directory in your solution, and you'll find Terrain, TerrainPatch, and QuadTree classes. In fact, if you'd like a very small sample with terrain stuff encapsulated within it, check out the third sample on this page called Simple Physics Sample v0.12. It has most of the engines terrain system inside of it, but without the engine itself (if you don't need it). The same was created for XNA 1.0r, but I believe it will work on 2.0 just fine. 

What I mean by vertex/index buffers, is that I do not use a model, or at least not the XNA model. When you draw a model, you're really just looping through all the vertices of that model through its index buffer. So my heightfield is simply a vertex buffer (a bunch of verticies), and for each quadtree I loop through them using an index buffer, and draw that quadtree chunk of terrain. It is really much easier IMO than using XNA's model structure, as you can control access to your vertices and index buffers very easily, which allows me use terrain smoothing algorithms, and easily create different LODs.....although I'm sure this could be managed somehow with the Model class.

Quasar:

150MBs? Didn't know that. What a jip. I think I'll stick with my original idea of making it only for Windows...

{Puts on yorkshire  accent}

150 mega bytes, luxury!

eeee when I wer a lad you had 64k, and wer glad of it. Then t'operatin system had half of it.

{Takes off yorkshire accent}

Seriously though Starflight shipped on two 5 1/2 inch disks and contained 270 solar systems, 802 planets, half a dozen alien races, a plot, sub plot, you name it.

People have got lazy, I had a massive argument with a graphic artist because he refused to resize his textures from 2048 by 2048.

I have seen commercial games that just threw all the verts at the graphics card, don't bother with fustrum culling or anything, they just said "the game requires a 512M graphic card". They could have shipped the game for 32M graphic cards with a bit of coding.

150 megs is plenty, as long as you plan for it.

I might have missed something. What does the 150 mb limit apply to?

I know what you mean about having a massive argument with a graphic artist though: S.T.A.L.K.E.R on the PC was a good 8Gb on the hard drive, so he doesn't see any reason our games shouldn't be as big. I, on the other hand, appreciate a game where the developers have put a bit of effort into performance and storage. It generally shows that the game is ahead of its time. I always though Halo 1, UT2004 and SW BattleFront ran quite well on systems that couldn't run games which looked half as good. Stalker could probably have been released for systems with a quarter the power.

Back to Lord Ikon... I downloaded v0.182 (I also downloaded v0.19 and the physics thing, but didn't look at the former and the latter wouldn't run). After a couple hours moving backwards and forwards between Terrain, TerrainPatch and QuadTree I managed to work out how it worked and came to understand a little better what you meant about vBuffers and iBuffers.

Meanwhile, I realised that a custom content processor can export to a custom class, but only within the content processors solution (which explains HeightmapInfoContent and HeightMapInfo in the Generated Geometry Sample... now they make sense). Screw using the Model Class, Lord Ikons method is so much better, even if I do have to spend time working out exactly what an index buffer is, and just how it's connected to the vertex buffer.

After this, it's going to be easy doing the game logic. >:)

I'm not a graphics expert, so this may not be exact, but here goes....

An index buffer simply tells the video card which indeces to use from the vertex buffer.

So, picture it this way:

*---*
|   -|
|  - |
| -  |
*---*

Each asterisk (*) is a 3d point, otherwise known as a vert. To draw those two triangles you could simply give the video card each triangle. And it would draw each one
individually:

*---*    *
|   -     -|
|  -     - |
| -     -  |
*     *--*

That means drawing 6 sides total.

But when those two triangles are touching, they form a square. So why draw 6 sides if you're drawing a square? You would think you should only draw 4 sides. This is where index buffers come in. The video card takes care of the work, you just need to tell it what the index numbers of the vertices are.

Lets give the triangles points a cooresponding number:

0    1
*---*
|   -|
|  - |
| -  |
*---*
2    3

So the two triangles are defined as (clockwise):
0, 1, 2
and
1, 3, 2

If this were your entire terrain, your vertex buffer would have 4 vertices, which are points 0-3, and 6 indices, which were the 6 we just mentioned. Given this information, when you make a DrawIndexedPrimitives, you have to tell the video card which vertex buffer your index buffer cooresponds to, the size of each vertex (in bytes), and the starting offset of your vertices which is zero in this case because our first vertex in this draw call is truly our first vertex in the buffer.

What is nice is if you only want to draw the second triangle, you make the same call, and tell it that the vertex buffer offset is to start at 1 instead of zero (because the first triangle's earliest vertex is 1), and the index buffer would start at the 2nd triangle (which is the 4th index.

After writing this I remember seeing something on Riemer's site, his explanation has better pictures and is much more complete:

http://www.riemers.net/eng/Tutorials/XNA/Csharp/Series1/Indices.php

Thank you Lord Ikon! You and Riemer have saved me hours of work, and I thank you for it! I managed to get a full Vertex/Index terrain running after only 3 hours work last night, which puts me that much closer to a real terrain system!

OK, next question (I just keep going on don't I? sorry...) Would I be better storing a single Vertex Buffer, and doing my LOD via indicies, or storing a seperate VBuffer for each Quad? I'm currently considering the former.

The other thing I was wondering is when I get to my edge stitching (I don't want to use skirts), should I store a seperate Index Buffer for each edge-combination of the quads, or dynamically modify them on the fly? I'm trying to work out a way to implement the latter, because I don't like the idea of 13 IB's per quad.

Thanks again for the Index/Vertex stuff! It was a lifesaver!

Whether you do seperate vertex buffers or not is a matter of preference it seems. I've seen it done both ways.

If you're going to do dynamic LOD and stitching, then you'll probably need 4 IBs per quad for each LOD (or something like that), I haven't done dynamic LOD yet so I'm not positive.

Well, I spent the weekend playing around, and got working something that could loosely be called "dynamic LOD", continually updated based on distance to camera. It's got no stitching (hole artifacts everywhere), I haven't looked into Index and Vertex buffer objects (just using arrays), and I still need to fix some horrible little variables to make it work with terrains of larger size thaan 257x257, but I'm quite proud of anyway. :)

I'm using a single vertex array and an index array per Quad node (which currently gets compiled every frame into an "all indices" array, which is what is rendered).

I'm going to improve it and make it more versatile the next time I have spare time (most likely next weekend).

EDIT: By the way, for stitching, the minimum number of Index Buffers I can think of per QuadNode is 9: (Based on sides connected to a lower detail node -- None; Left; Right; Up; Down; LeftUp; LeftDown; RightDown; RightUp). And that's only if every Leafnode only connects to one with an LOD difference of either 1 or 0. That's why I'm going to try dynamically generating each quadNodes Index buffer every update based on those around it.

Sounds like you've learned a lot about terrain in a week.

Maybe you can save me some time by letting me peek at your dynamic LOD stuff when you're done. :)

I'm still Quasar, but I've been forced to create a new profile because my security system from our work computers won't let me put my work address in to sign in any more. If an admin or mod is reading this, could you change the old profile to respond to the e-mail on this profile, and remove this one (if that's even possible)? Thanks.

Sounds like you've learned a lot about terrain in a week.
Definately. I blame you and Riemer for that. ;)

Maybe you can save me some time by letting me peek at your dynamic LOD stuff when you're done. :)
:) Some parts of it are your code anyway! Heavily modified, of course.

I'm not sure what I'm going to do with it when I'm finished (I was only making it because I needed a rediculously sized terrain in one of my games anyway), but I'm thinking I might comment it and release it to the public. Afterall, my setup (a single 'terrain' class which does all the work for me) is very user friendly.

Even if I don't, I'll send you a copy.

Oh, and I got it working for heightmaps of any n^2+1 size... but then ran into the same problem I had in another thread: when I go above a 'threshold' somewhere between 513x513 and 1025x1025, the terrain simply does not appear. This happens even with the terrain content processor from the generated geometry samples, so it's nothing to do with LOD. My graphics card is a modern 756mb card, so I have no idea why this would be happening... :(

Wireframe View, SquareSize=9, 257x257
Solid View, SquareSize=9, 257x257
Solid View, 512x512

Qu:

I'm still Quasar, but I've been forced to create a new profile because my security system from our work computers won't let me put my work address in to sign in any more. If an admin or mod is reading this, could you change the old profile to respond to the e-mail on this profile, and remove this one (if that's even possible)? Thanks.

Sadly we can't... looks like you will have to have a work and home login for now.

If you run the QuickStart Engine v0.19, I believe (don't quote me on this) that the default terrain is 1024x1024. Does that terrain show up with your graphics card?

I know older cards have problems with index buffers larger than 16-bit (~32,500 indices), so I had to enforce a minimum quad-tree node size in the engine to make it compatible with older cards. But on an nVidia 8800 there is no way that is the issue.

Anyhow, nice pics, looks like it is coming along nicely, just some small stitching issues.

Well, I remember running that engine, and it seemed to run fine (albeit at 25fps), so I'll have to look into what's done differently there...

I'm working on my stitching algorithm, and I can easily stitch nodes that sit next to nodes the size of their parent nodes (try saying that five times fast ;) ), but I'm not sure what I'm going to do about nodes that sit next to nodes which are larger than that. I could either re-write the LOD selection algorithm to prevent this from ever occuring, or write a more versatile stitching algorithm... not sure which to use just yet...

25 fps in debug, especially if you're using JigLib rather than Ageia PhysX. Right now JigLib is default for Xbox compatibility.

In release mode I currently get anywhere from 200-400fps at 1024x1024, with 100 cubes reacting with terrain physics and each other

With 0.182b, set to lowest quality, I get 300-500fps with a 1024x1024 at low LOD.

That's a relief: I was using it in debug. And the 1024x1024 terrain displays fine in your engine. [confused frown]

Did a few tests and found the 'threshhold' value: Any heightmap larger than 725x725 (even 725x726) will not render at all on the Generated Geometry Sample. The sky renders, but not the terrain. A terrain with a smaller width but larger height (or vice versa) such as 72x1450 will display.

My graphics card is a 768MB NVIDIA GeForce 8800 GTX... so that shouldn't be the problem.

Also, I created the stitching and applied it to all the node edges. Next job is to apply it to only the relevant node edges.

Stitching at corner of four nodes
More overall view of stitching on all nodes
Stitching and nodes rendered together

project a screen space grid onto terrain plane

giving XYZ in world space and XY in terrain coordinates

vertex shader sets XY position and looks up Z using XY coordinates from heightfield texture

that gives you LOD for free with no holes to patch up

and the only data loaded into the GPU is a small grid and a heightfield

Qu:

That's a relief: I was using it in debug. And the 1024x1024 terrain displays fine in your engine. [confused frown]

Did a few tests and found the 'threshhold' value: Any heightmap larger than 725x725 (even 725x726) will not render at all on the Generated Geometry Sample. The sky renders, but not the terrain. A terrain with a smaller width but larger height (or vice versa) such as 72x1450 will display.

My graphics card is a 768MB NVIDIA GeForce 8800 GTX... so that shouldn't be the problem.

Also, I created the stitching and applied it to all the node edges. Next job is to apply it to only the relevant node edges.

Stitching at corner of four nodes
More overall view of stitching on all nodes
Stitching and nodes rendered together

Sample looks pretty good. I'd be willing to help you debug this issue if you'd like, it may not be specific to your card if you're not seeing the problem in the QuickStart Engine. Have you tried running the same program from a different video card? Do you get the same issue?

My guess is that this issue somehow has to do with the vertex buffer size, offset, or possibly even your vertex type if it is custom.

OK... I have news. :)

First things first: the mysterious terrain vanishing problem. Riemer gave me a bit of code to test my graphics card.           

The results... were unpleasant. Max primitives and Max Vertices both return a little over 1 million. As it turns out (I did a lot of testing), going above max vertices will drop your computer back to software vertex processing (Laaaaggg), and going above max primatives will make the terrain not render. This is what was causing my problem.

Now this means I have two problems to fix. The first is indices: that's easy. All I do is create a new index array of the correct size every frame, and copy all my indices to that, and then render it. Not optimal, but it works.

Not able to contain a 1024x1024 vertex array in the graphics card, though... that's annoying. I'm not sure how to implement multiple vertex arrays, and not really sure I want to. If anyone's got some ideas, I'd be grateful to hear them...

On to cooler stuff... I think this speaks for itself:

Compiled LOD

W,A,S,D and Mouse to move, Tab to toggle fill mode and Q,E to change the LOD level.

There are still a few problems: can't go above 512x512 for reasons given above, moveing the camera too far away from the terrain will cause an exception, almost-unnoticable single-polygon stitching artifacts can be seen occasionally and it has no frustrum culling... but it works!

My biggest problem is the single/multiple vertex array thing... I have no idea where to start.