|
Author Topic:   Simple Quad Tree Demo & Source
Bryan T
Member
posted June 28, 2000 02:06 PM            
Well, I finally got around to cleaning up my Quad Tree demo code. I posted it off GeoCities (link below). This engine makes use of the presentation at GDC '00 about using a simplified Quad Tree method. I've further simplified it using Seumas' split-only recursive scheme.

To date, this is the best and fastest algorithm I have been able to find. In terms of code complexity it is an order of magnitude simpler than the Binary Triangle Tree engine from my Gamasutra article.

I just realized that I forgot to turn Geomorphing back on too, but it's already written into the code. I'll leave that as an excersize for the reader It requres changing four lines.

Here's the engine & source: http://www.geocities.com/gone2rave/terrain.htm

Here's the article that discussed this method: http://www.3dgamedev.com/articles/LODPaper.zip

Please let me know if there are any major problems with it. I'm planning on using this engine to build the advanced features on to (frame coherence, texturing, etc). And I'd like a solid base to start from.

--Bryan

IP:

Prophylon
Member
posted June 28, 2000 02:37 PM            
Oww I got an illegal operation while trying to run it... whoops... It looks very promising though (again another great example!) Allow me to see if I can catch the error

[EDIT]
// DEBUG: Check for legal Height Field coordinates...
if (y < MAP_SIZE && x < MAP_SIZE)
return gHeightField[(y*MAP_SIZE)+(x) ];

gHeightField is empty (all zeros) on debug

trying something out, brb

[EDIT 2]
Ow heh the filename is a bit wrong, you had "Terrain Maps\\Height%d.raw" but that should just be "Height%d.raw" since you do not create any directories in the zip. You might want to fix that error checking code

[EDIT 3]
Well it looks very nice, it seems much simpler then the ROAM algo. I like it simple Going to find out how to enable GeoMorphing (should be easier with quadtrees then with ROAM) and see how that looks...

Thanks again for sharing your wisdom with us Bryan. You going to post this link on sites like Flipcode.com and stuff too? Or yer going to write another goodie article for gamasutra?

Thanks!

Joris.

[This message has been edited by Prophylon (edited June 28, 2000).]

IP:

Bryan T
Member
posted June 28, 2000 05:03 PM            
Doh! Tells me to check the archives I post, no?

The real fix for it is to create a folder called "Terrain Maps" and put the height map file into it. When I created the archive, the path names must have been wiped. I'll fix it when I get a chance.

I don't plan on writing an article or anything for this one, hopefully the demo & code, and discussion here will be enough for everyone to understand it.

--Bryan

IP:

Prophylon
Member
posted June 28, 2000 05:32 PM            
Well what I meant was that I see you are checking for errors (filehandle == null?) but that it isnt working, because it could not find the file and loaded fine (and then crashed )

Just adjusted the color code so I get per vertex coloring so that I can see the GeoMorphing better... Working now on how to get the second heightcoord (something tells me that I have to add two height values and divide by two...)

Anyway, nice work and thanks especially for sharing it with us!

Joris.

IP:

Bryan T
Member
posted June 29, 2000 09:29 AM            
Well, I'll just start collecting errors then. The lack of error checking was for my procedural heightfield generation algorithm, I forgot to add the error check back when I took it out for this demo.

Hopefully I'll get a chance to fix this and a few other error tonight. Someone else wanted me to re-enable the variance calculation too, I may throw that feature back in as well.

--Bryan

IP:

Revolver
Member
posted June 29, 2000 05:05 PM         
Here's a thought I had - why not implement a loose octree for terrain self-occlusion?

Where an octree is a heirarchy of cubes that possess eight children of equal volume and size, a loose octree is an octree wherein the children are of any size, and can overlap.

Essentially, you extend the quadtree into the third dimension, but handle the terrain LOD in the same manner. You test the bbox of each terrain node against the zbuffer (or really a software buffer, since messing with the hardware zbuffer isn't wise), if the box passes the test (is partly visible), then you do LOD. If it isn't then you simply discard all the triangles in that box, avoiding the costs of LOD, sending them to rasterisation, backface culling, and everything else.

This would give you the benefits of occlusion combined with the benefits of LOD. This self occlusion could also be used in static-LOD terrain environments as a speed-up. Obviously this self-occlusion is only beneficial when relatively low to the terrain. If it was viewed from above, there wouldn't be any occlusion, and LOD would be the only method of keeping the FPS up.

With the loose octree, the vertical extents of each terrain leaf would only be enough as to contain all the vertices in it. Thus, a mountain in front of you will block a significant amount of leaf nodes.

Any ideas/comments?

-Brian

[This message has been edited by Revolver (edited June 29, 2000).]

IP:

Prophylon
Member
posted June 30, 2000 02:57 AM            
That sounds like a good idea, especially in a hilly terrain... However how do you want to use a s/z/w buffer to know if your box is or is not visible? Since they are pixel based, you want to write an additional buffer drawing/testing only cubes? Hurm.. that might be possible Although I do not know that much about a zbuffer, if it could work it be great since in my terrain I have pretty much hills and you actually walk on the ground (not fly).

Ow and I think you must be careful, although I do not know how expensive software zbuffer operations are I think you will want to be careful that you do not do too much calculations. On the newer cards it might be better just to cram out more polygons and burn them through the pipeline (which is mostly hardware accelerated) instead of wasting CPU time to calc the zbuffer...
This is one of the reasons why a friend of mine doesnt use LOD at all for use engine, he just uses patches of vertex buffer and uses a quadtree to cram 'em out all at once.
Again, I really do not know how costly zbuffer is (I guess there is some reason for making it hardware accelerated?) so I might as well be talking crap...

Enlighten me

[EDIT]
Bryan, how much memory does your quadtree uses in comparison to others?
[/EDIT]
[EDIT2]
OW btw it might be better to hand calc the texture coords, since that is a bit faster then to let OpenGL calc them... But I am sure you are busy doing all sorts of fancy stuff with it already When you upload a new version you will let us know, right?
[/EDIT2]

[This message has been edited by Prophylon (edited June 30, 2000).]

IP:

haktan
New Member
posted July 10, 2000 06:15 PM            
Hi Bryan,

How do you ensure that there are no neighbors that have more than one level of detail difference?

IP:

Bryan T
Member
posted July 10, 2000 11:19 PM            
haktan,

I'm using a split decision algorithm that enforces the LOD distance. The algorithm in general comes from the GDC 2000 presentation entitled "Real Time Continuous Level of Detail (LOD) for PCs and Consoles". I was impressed with the simplicity of the algorithm, and I'm happy with the results.

A link to the presentation is given in the first message of this thread.

--Bryan

IP:

haktan
New Member
posted July 13, 2000 04:11 PM            
Hi Bryan,

OK. It is the split-decision function that enforces the max one level difference restriction.

But I can't really see that this function would work correct, if you have a very steep peak in a small area and the eye is located near the peak. Then the quad representing the peak would be split, but the distance to the surrounding neighbors could be big and therefor not split. As far as I can se, the paper only handles the 2d-case, but does it work, when you take the height into account?

IP:

jester
New Member
posted July 15, 2000 10:10 AM            
Bryan,

It's typical. Just as I finally get the binary tree LOD ready to post you go and produce something faster and better.

Good work, I'll have to get this baby moved to Java and see if I can squeeze more fps!

BEN

IP: