Hmmm... intriguing concept, although I still have trouble visualising it. :)

My method is to use a single vertex buffer, with positional data only, for the entire terrain, and only store index values per quad node. Even then, I combine the node index arrays into a DynamicIndexBuffer before rendering with a single draw call. It seems to work well enough.

Other things: I've written up a bit of a checklist for those things I need to do before I'm ready to publically release the class.

• Stitching/Frustrum gaps - Occasionally I've noticed gap artifacts along some of the stitching lines, but they disappear when you move the viewport. An example can be seen in the bottom left quadrant of the screenshot (I worked out how to get blogger links working, so the link should work). I think the bounding frustrums are messing with the stitching algorithms.I'll need to track this one down before release: gap artifacts are annoying.
• Unnecessary Vertex Normals - My vertex struct still contains a Normal element, even though the shader no longer needs it. This would normally be easy to fix, but I'm using this normal value to do the flatstripping. I'll need to do some modification to fix this before I can delete the Vertex Normal field.
• Combine Shader and Quadtree Class - The terrain shader is an essential part of this class, but at the moment I'm making the effect and setting all the parameters outside of the class. Usability dictates that I combine the two, so that users can set effect parameter values via public variables in the terrain class.
• Cull Mode/Clockwise Indices - Currently I'm using Cull Mode: None in the shader, because some of the stitching and flatstrips are defined in a counter clockwise fashion. I need to track these down and set CullMode to CW (Or CCW, I'm not sure which).
• ?Sort Quadnodes? - I'm wondering whether it would be worthwhile sorting the order the quadnode indices are put into the DynamicIndexBuffer, to render nearby objects first and distant objects last, saving Fill Time... I'm currently not sure If this even applies during a single draw call...
• ?Geomorphing? - It's become doubtful I'll bother with geomorphing: converting to a DynamicVertexBuffer and resending the vertex data every frame seems like a performance issue, not to mention a lot of work.
• Optimise and Comment - And, of course, I need to go through and optimise the code both in XNA and the terrainShader, and then finish commenting for those people who want to try to understand how it works.

Once those are done, I'll mark it complete and provide a source download!

Cheers,
Quasar.

For your Cull Mode/Clockwise Indices problem, use CullCounterClockwiseFace

I think sorting the quadnodes is a worthwhile optimization.  It can really help out the pixel shader, a lot or a little depending upon current camera settings.  Overdraw can be a serious GPU thief, generally when the camera is looking towards a horizon.                      Just have a simple list, that you throw leafs on after you frustum cull.  Then sort that list based upon your distance check I saw in your code.  Collect the index data, after list is sorted.

 

I can't just change the cull mode: the problem is that a few of the polygons (flatstrips are the most obvious) are defined CCW, while most are defined CW. I just need to track them down and change the order the indices are added.

For sorting, thanks for the advice! I'll take it on board and see what I come up with.

I just had another thought for the checklist:

• Garbage collection - I honestly don't know how much of a problem this is, but I am creating a new Index array every frame, then adding it to the dynamic buffer just before I call DrawIndexedPrimitives(). Since I don't have a Xbox 360, I have no way of testing the effects of Garbage Collecting. Is this likely to be a problem? (the new-array-every-frame part, not the lack-of-Xbox part)

I just said to turn on ccw culling to see which ones need changed.  Fixing that should be easy, after you know which ones to fix. (Flip 2 of 3 index's positions)   Minor speed increase should be given once you only draw the one side.

As far as garbage collection, you are right to be concerned.  It will cause occasional stalls from what I've heard on the XBox. I don't have an XBox either :(

Just create an index array large enough to hold the largest array, then reuse it each frame by filling up from the start and keeping a count of how far into it you go.  This should also give a very minor speed increase. *But any speed increase is good :) *

gorky:

I just said to turn on ccw culling to see which ones need changed.  Fixing that should be easy, after you know which ones to fix. (Flip 2 of 3 index's positions)   Minor speed increase should be given once you only draw the one side.

Oh, OK, I misread you. That's exactly what I intend to do, and it's actually how I know the flatstrips and the stitching are the problem. :D

I'd tell you how much I'd achieved, but I haven't actually had time to work on it. But that changes today! Because today I finally get a laptop, and can make use of the two hours I spend on the train getting to work! Hooray!

gorky:

Just create an index array large enough to hold the largest array, then reuse it each frame by filling up from the start and keeping a count of how far into it you go.

Good idea. I was originally doing something very similar, but I wasn't keeping track of how many indices I needed, which meant I was rendering a large number of 0,0,0 primitives. Now that I'm having to create a new array each frame, I've already got a renderedIndices value ready to go (used to define the array size). I'll be able to change my draw call to use it.

I think I'm going to need someone with an Xbox 360 to quickly test this class before I release it. If anyone's interested, feel free to drop a post in this thread.

gorky:

This should also give a very minor speed increase. *But any speed increase is good :) *

That's very true. I only expect minor increases now: I'm not going to stumble on another of these, but if I was the type to pass up a speed increase why the hell would I be making a Terrain LOD algorithm? ;) They all add up, and since I'm planning on making this public it needs to be as resource friendly as possible... ^-^

In a right-handed system, you want to cull away clockwise faces, and render counter-clockwise, else the right-hand rule for where your triangle normal points doesn't work.

Btw: geomorphing can be done entirely in shader, by storing the source and destination positions both in the vertex, and using a blend weight between 0 and 1 in the shader.

jwatte:

In a right-handed system, you want to cull away clockwise faces, and render counter-clockwise, else the right-hand rule for where your triangle normal points doesn't work.

I have absolutely no idea which way my polygons are defined, but I've got a few of both and I haven't noticed any problem with the normals. I'm intending to just redefine the minority and use whichever cullmode works. :D

jwatte:

Btw: geomorphing can be done entirely in shader, by storing the source and destination positions both in the vertex, and using a blend weight between 0 and 1 in the shader.

I am intrigued, and would like to subscribe to your newsletter...

How do you then feed the blending weight for every vertex into the shader? If you just use setData on the vertex buffer, isn't that the same as dynamically updating the vertex positions? Or am I missing something important (which seems more than likely)?

You can find your winding order by checking out how your index buffers are being created.

If you're creating your indices clockwise you'd have something like

x+1, y+1
x, y
x+1, y

x+1, y+1
x, y+1
x, y

Imagine two triangles defined by four vertices:

1---2
| \    |
|  \   |
|   \  |
3---4

Clockwise could be:
4, 1, 2
4, 3, 1

or

1, 2, 4
1, 4, 3

or

2, 4, 1
3, 1, 4

Counterclockwise could be:
4, 2, 1
4, 1, 3

or

1, 4, 2
1, 3, 4

Clockwise just means that the order of the numbers is clockwise based on a diagram like the two triangles above.

Thanks Lord Ikon: I already understand cullmodes: it's just that my index creation is a little complex...

 

 

...and I'm too lazy to go through and try to work out whether every different type of primitive creation (1 standard, 2 flatstrips and 3x4 for stitching) from the code alone. It's easier to just look at it graphically and work out what primitives to modify.

Which I just did! Cull mode is now set to CCW, and everything looks good. So that's one thing to cross off the list. :)

Heres another thing to cross off: Quadnode sorting. The Quadnodes are shoved into a list, the list is sorted with a simple distance comparison, and the indices are shoved onto the index buffer.

I also did a small bit of optimising, phasing out Sqrt calls in favor of simply multiplying the other side by itself, as well as a few other small fixes.

My laptop has arrived, and doesn't have quite the same power as my desktop... which is good, because it makes performance changes easier to notice. Cull mode resulted in a small but consistant increase, while sorting dramatically increases my FPS when I'm staring at a wall.

I'm noticing the FPS effect of too many texture samplers, as well... reducing the number increases perf on my laptop, but not on my desktop, strangely.

Complex, maybe. But understanding the winding is easy. My example works with your code.

Looking at it, you're using:

x, y + #
x + #, y
x, y

x, y + #
x + #, y + #
x + #, y

Using zero as an offset

0 --- 1
|     / |
|   /   |
| /     |
2 --- 3

We see that we have
0, 1 or 2
1, 0 or 1
0, 0 or 0

0, 1 or 2
1, 1 or 3
1, 0 or 1

Your winding order is counterclockwise, which you've already noticed by now.

Certain cards are faster with texture samplers than others, my guess is the card in your desktop is faster with them than your laptop's card.

Hmm... you're right, I can see that pattern in my code now that you've pointed it out. Cheers.

Oh, and here's a current screenshot running on my laptop. It's looking good.

Crud.

I had a slight setback. Whilst transferring my LOD project from one computer to the other, I accidently overwrote a newer version with an older version from about 2 days ago. So you can uncross-out those checklist items I'd crossed out.

And now you can double-cross them out again, because I've got a good memory of how I implemented them and had an hour of free time this morning. With luck, I'll be able to reinstate the garbage collection solution (which I had managed as well before the overwrite, darn it) some time this afternoon.

I've also identified the problem for the stitching/frustrum gaps, so I should be able to work out a solution for it soon.

So, my checklist as of tomorrow:

• Stitching/Frustrum Gaps
• Unnecessary Vertex Normals
• Combine Shader and Quadtree Class
• Cull Mode/Clockwise Indices
• Sort Quadnodes
• Garbage Collection
• ?Geomorphing?
• Optimise and Comment

I'm amazed by your progress, especially considering the few hours that you have to actually work on this!

You might consider, making a local backup on each pc, that you always update after your done with some work.  I do this. I also make occasional CD based code backups too.

 

gorky:

You might consider, making a local backup on each pc, that you always update after your done with some work.  I do this. I also make occasional CD based code backups too.

That's a good idea, but doing it is sort of what caused the accident in the first place! :D

I had 3 copies of Terrain.sln: an old one on my desktop, one in the shared folder on my laptop, and one in My Documents (again, on my laptop). Without realising it, I had been working on the one in the Shared rather than the one in My Documents.

So when I tried to update my desktop's copy over the local network, I started by copying the version in My Documents on top of the version in Shared... and then kicked myself and swore a lot.

 

Strangely, I haven't been able to reproduce the Garbage Collection solution yet: it seems to be severely screwing up the geometry. I'll keep trying to see if I can work it out.

I did, however, manage to fix the stitching/frustrum gaps: they were easier to work out than anticipated. I also changed something that wasn't really a 'problem', but the change makes the terrain look a little better. I don't have a USB drive with me, or I'd provide pictures, but heres what happens: if a square has 1 vertex up high (on a cliff) and 3 on the ground, then there is two ways it can be rendered: the diagonal can go flat across the ground, or it can go up the cliff. If the diagonal goes up the cliff, it causes a 'foot', which sticks out from the smooth cliff face. This doesn't look great when the foot of a cliff has lots of little 'feet' all the way along its length, and also creates a bad looking 'lots of squares' effect at the top of cliffs.

By testing the height difference between opposite vertices, I now work out which way to orientate the diagonal, which results in an improvement in the appearance of the edges of sharp cliffs and walls. I'll provide pictures tomorrow. :)

Finally, I added a float in my shader to set the strength of the detail normal map, which is something I've been meaning to do for a while. Works well.

Cheers!
Qu.

• Stitching/Frustrum Gaps
• Unnecessary Vertex Normals
• Combine Shader and Quadtree Class
• Cull Mode/Clockwise Indices
• Sort Quadnodes
• Garbage Collection
• ?Geomorphing?
• Optimise and Comment
• Cliff Feet
• Changable Detail Map Strength

You might consider putting a shortcut on your desktop to your solution.  That way, when you click it, you will always open the "right" project.  (Not too mention, it opens visual studio and your project with one click.)

I'm very willing to do a code walk through, for you when your close to finished.

 

Eureka! [Translation: "Someone give me a towel!"]

I worked out the probelm I was having with the garbage collection solution, and fixed it. There is no longer a single instance of the 'new' keyword in the update call of the terrain (or the draw call, either).

I also solved the Unnecessary Vertex Normals: each element of the vertex buffer now contains a single Vector3 for position.

And I thought up another thing to add to the list: Many things don't need to be called more than once per Draw call, so they can go into the DrawTerrain method (rather than the UpdateTerrain method, where they currently reside).

I'm haven't decided what I'm going to work on next... either combining the shader and terrain, or moving stuff to the draw call.

And the verdict is still out on geomorphing, but I suspect I'm not going to bother. Converting to a dynamic index array still seems like a problem...

• Stitching/Frustrum Gaps
• Unnecessary Vertex Normals
• Combine Shader and Quadtree Class
• Cull Mode/Clockwise Indices
• Sort Quadnodes
• Garbage Collection
• ?Geomorphing?
• Optimise (Sqrt, ...) and Comment.
• Cliff Feet
• Changable Detail Map Strength
• Move stuff from Update to Draw

Also: I promised cliff feet pictures:

Obvious Cliff Feet.
Same shot using my Anti-Cliff-Feet-Algorithm.
The ACFA on a more standard terrain.

Promise kept. ;) :D

Edit: About putting a shortcut on the desktop... good idea. I'll do that: it might save me more stuff-ups.
About doing a code walkthrough: That'd be pretty awsome of you. I'll comment it a bit more first, though: some parts are so strange and/or complicated even I don't understand them. And there's a few segments I don't even remember coding at all: they were just 'there' the next morning, and I had amnesia and a suspicious headache. [Joke] ;)

OK, that's it... it's just about finished.

I've combined the shader and class, and shoved comments in throughout, and now I think it's almost ready for release.

I worked out that my biggest performance issue (on my laptop at least) is the texture lookups - which is actually a good thing, because it means I can save significantly on framerate by simply using lower detail textures. :)

So then... give me one more day to clean up the project file and change the accessors of those variables the user doesn't need access to, and I'll provide a download file for the full source code. :D



By the way guys, thanks for all the help, suggestions and encouragment in this thread. The fact that I'm almost ready to release is in part thanks to everyone who responded. Thank you all!

Cheers!
Qu.

Sounds like it'll be pretty sweet, can't wait to see it.

Sorry I don't have a download for you guys today... Riemer's setting up a 'Community Projects' section on his site, and I'm going to upload it there rather than attempt to deal with free file hosting sites again. So it might be a little bit more time, but it does give me a chance to do a bit more debugging, and make sure it's polished. :P

OK, if you're brave enough to try downloading from a file hosting site, here's a sample *.ccgame file.

The entire source code for this file, as well as the textures and height map, is what I'm going to share once Riemer.net is set up.

http://myfreefilehosting.com/f/e62c5d4d5f_2.98MB

This sample is a full 1025x1025 QuadTerrain running with a quadnode size of 33, with the indices being shared over over 5 Vertex buffers. The shader is using 4 512x512 diffuse textures, 1 256x256 blend texture, 1 256x256 detail normal map and the 1025x1025 global normal map.

Controls are fairly simple: WASD to move, Mouse to look around, Spacebar to fly and TAB to toggle between Point, Wireframe and Solid fillmodes.

First, very cool, and it works great, can't wait to see how it was done.

Here are my suggestions/critisisms:

1.) Holy crap the normal mapping on the terrain is strong, probably about 5-10x as high as you want it to be. I shouldn't be able to see very very small bumps on the terrain on the other side of the map. Are you mip-mapping your textures?

2.) Just curious on the decision for a quadnode size of 33. Such a small size causes quite a bit of CPU overhead on mine, you end up checking many thousands of bounding boxes for collision rather than many hundred. This may be why I get 150fps when looking at the whole map vs 500-600fps when I'm in the middle of it. Mine is less extreme, I get around 150fps when looking along the whole map, but around 300 when in the middle (of course I have no geomorphing/geomipmapping/dynamic-lod). What happens if you use a larger quadnode size, like 64/65? Also, if your nodes are 33, then you must be overlapping them, as 33 is neither multiple of 1025 or 1024. Curious how that is working out.

3.) The camera movement is locked to terrain when over it, which can be annoying when you want to look around  I see you have spacebar for "fly mode".

4.) Day-Night cycle frequency, as well as camera movement, seems framerate-based rather than time based. The sunlight would make an entire cycle in around 10 seconds when I was at 150fps, but would do it in only a second or two when I was in the center of the map at 400-500fps. Camera moves insanely fast (bear in mind my fps is pretty damn high, possibly because of 2x 8800GTS 512s in SLI).

5.) Escape key does nothing, having to hit Alt+F4 is a pain, and if I accidentally am holding in one key, and bump the other twice, I close something else on accident.

6.) You may want to only use the mouse for camera movement when player is holding in a mouse key. If I open your program and alt+tab to another program, I cannot use my mouse cursor.

Again, very cool program.

 

Lord Ikon:

1.) Holy crap the normal mapping on the terrain is strong, probably about 5-10x as high as you want it to be. I shouldn't be able to see very very small bumps on the terrain on the other side of the map. Are you mip-mapping your textures?

The normal mapping strength is set via a shader parameter... I think what you're looking at there is detailMapStrength = 2f.

I'm pretty sure I'm mipmapping textures (I don't have to do anything special to make this happen, right?), but I have noticed the effect you're talking about. I put it down to lack of antialiasing, but I'll do a quick check in a few hours to see if I can identify it as something else.

Might it be an idea to get the shader to fade out detail mapping in the distance?

Lord Ikon:

2.) Just curious on the decision for a quadnode size of 33. Such a small size causes quite a bit of CPU overhead on mine, you end up checking many thousands of bounding boxes for collision rather than many hundred. This may be why I get 150fps when looking at the whole map vs 500-600fps when I'm in the middle of it. Mine is less extreme, I get around 150fps when looking along the whole map, but around 300 when in the middle (of course I have no geomorphing/geomipmapping/dynamic-lod).

I chose 33 for a number of reasons, but the coder can set it to whatever they want via a value in the constructor. Here's why I chose 33:

• It's fairly easy to see, without being over the top aggressive.
• It's a good testing number: it displays a good depth of LOD (the highest LOD is quite coarse, while the lowest is nice and fine).
• It achieves a reasonable balance between CPU and GPU on my computer.

You mentioned that you are running 2 512mb graphics cards in SLI. That explains why I'm fiillrate limited but you are CPU limited: I've got a very similar machine, but I'm using a single 768mb 8800GTX. When you get the source code I'll be interested to see what QuadNode size you use.

Lord Ikon:

What happens if you use a larger quadnode size, like 64/65? Also, if your nodes are 33, then you must be overlapping them, as 33 is neither multiple of 1025 or 1024. Curious how that is working out.

Many of my values are using the 2ⁿ +1 format. So 33 can be reduced to 32+1, or 2⁵+1. The quad nodes here, for example, have a quadnode value of nine: you can see that if you count the vertices along an edge (remember that the stitching hides every second vertex).

Lord Ikon:

4.) Day-Night cycle frequency, as well as camera movement, seems framerate-based rather than time based. The sunlight would make an entire cycle in around 10 seconds when I was at 150fps, but would do it in only a second or two when I was in the center of the map at 400-500fps. Camera moves insanely fast

Yeah, I know. [embarrassed]. I was using FixedTimeStep = true to set all the values, but then I turned it off to get the framerate and never bothered implementing proper gameTime. Tell you what, I'll do a quick fix of this before release. Should be fairly simple.

Lord Ikon:

5.) Escape key does nothing, having to hit Alt+F4 is a pain, and if I accidentally am holding in one key, and bump the other twice, I close something else on accident.

OK, I can fix that easily enough as well. Sort of forgot about it after it became habit to simply alt-F4 out of the program.

Lord Ikon:

6.) You may want to only use the mouse for camera movement when player is holding in a mouse key. If I open your program and alt+tab to another program, I cannot use my mouse cursor.

Hmmm... I'll think about it, but I can see a problem or two that might slow me down a bit...

 

Thanks for the criticism, compliments and suggestions!
#4 and #5 will be fixed in the release, #6 should be if I don't run into unexpected problems, and I'll look into #1. Most if it's to do with the sample "game", not the terrain itself, which means I've done my job well!

And if you come up with any other stuff, by all means let me know!

Thanks!
Qu.

I'm attaching a screen shot, link of what it looks like on my pc. (Radeon x1300)

Qu's Lod

I don't see a day/night cycle on my end.  It almost seems like I'm stuck in a twilight light direction.

I'm guessing that you don't have mipmapping on, for your textures.  It's based upon the twinkle effect I see on the textures in the mid to far distance.  Make sure that your detail and diffuse textures have mipmapping turned on for each one in the content folder of the project.

BTW, besides what Lord Icon already mentioned, if you point the mouse down, you can flip the camera upside down without knowing it happened.  Then all camera movements are backwards (left becomes right, up is down, etc..)

gorky:

I'm attaching a screen shot, link of what it looks like on my pc. (Radeon x1300)

Qu's Lod

Whoa! That's... scary.

It's clearly the normals which are being screwed up... and based on the size of each pixel, it's the global normal map. It's almost as if the map has been corrupted, or something. Which is really strange, because it's generated from the heightmap when you build the terrain.

It's not a channel problem, because even if it was swapping things around it would still al the very least relate to the heightmap, even if it looked messed up... hmm... if you zoom out and view the full terrain from a distance, is there a pattern, or is it random?

I'll see if I can't spot anything in the meantime, but I honestly have no idea why it could be doing that. All the other textures are working fine, judging by your image.

gorky:

I don't see a day/night cycle on my end.  It almost seems like I'm stuck in a twilight light direction.

Yep, that's exactly what it's meant to do. I tried a day-night cycle, but it was annoying when everything went black for 15 seconds while you waited for the sun to come back up. So I instead circle it around the sky, like in Antarctica.

gorky:

I'm guessing that you don't have mipmapping on, for your textures.  It's based upon the twinkle effect I see on the textures in the mid to far distance.  Make sure that your detail and diffuse textures have mipmapping turned on for each one in the content folder of the project.

Oooh, thank you! I'd completely forgotten about setting mipmaps in the properties dialog, and that was exactly the problem! All fixed now.

gorky:

BTW, besides what Lord Icon already mentioned, if you point the mouse down, you can flip the camera upside down without knowing it happened.  Then all camera movements are backwards (left becomes right, up is down, etc..)

Oh yeah, I'd forgotten about that. You're not quite accurate: the horisontal axis doesn't change, but the vertical axis becomes inverted. Like the inverted controls setting in Halo. I'll fix it before release too.

:D

Qu:

You mentioned that you are running 2 512mb graphics cards in SLI. That explains why I'm fiillrate limited but you are CPU limited: I've got a very similar machine, but I'm using a single 768mb 8800GTX. When you get the source code I'll be interested to see what QuadNode size you use.

I've got a E8500 at 3.8Ghz, I hope I'm not too CPU limited. Of course, limited to 400fps isn't the end of the world.

However, my comments about quadnode sizes I chose when I first made my terrain programs were on my nVidia 7900gs go and my ATi Radeon 9800se (almost 5 years old).