|
Author Topic:   Adaptive Quadtrees vs. ROAM
Achilles
New Member
posted April 27, 2000 05:23 PM            
Anybody implemented/experimented with BOTH approaches? I've just completed a variation of the quadtree method, but my interest in ROAM implementations was piqued with Bryan's Gamasutra article.

Anyone who has knowledge of both care to correspond regarding the pros/cons of each?

Specifically, memory requirements, texturing issues, variable resolution, and scaling.

Nice to find a spot where others are dealing with terrain rendering challenges...

IP:

Bryan T
Member
posted April 28, 2000 02:21 PM            
Achilles,

Welcome to the forum! I've not implemented both algorithms yet, but hopefully someone here who has will enlighten us..

Till then, give a look at the following links, and perhaps some of the authors of these projects could help as well. http://www.vterrain.org http://www.vterrain.org/LOD/runtime-reg.html /forums/archive/ubb/Forum3/HTML/000111.html /forums/archive/ubb/Forum3/HTML/000074.html

Chris C has implemented both algorithms, and his viewer framework was the base I used in my demo, I recall he said QuadTree was his choice due to simplicity, but that BinTree with frame coherence would probably have a speed advantage. Chris, are you around?

--Bryan

IP:

Achilles
New Member
posted April 28, 2000 02:28 PM            
Thanks for responding. Actually I made a mistake, since ROAM IS a quadtree based method. What I really meant was, essentially, Adaptive Quadtrees vs. Bintree based methods (like the one used in Tread Marks). I'm curious which method of tesselation is "better" given the pros/cons of each. Any ideas?

IP:

Chris C
Member
posted April 28, 2000 08:51 PM         
Yep, I'm around!

Technically, the quadtree algorithm I implemented is not adapative in the sense of the recent Gamasutra article. Adaptive in this case means that an incomplete quadtree is used to store the terrain map. In other words, the terrain is stored at varying levels of detail. Hence you can have bigger terrains that take up less memory. An algorithm using adaptive quadtrees is unlikely to run very much faster than one using complete quadtrees, though.

With respect to performance, I did consider frame-coherent ROAM to be faster than the quadtree algorithm I implemented. But, the adapative quadtree algorithm presented by Thatcher Ulrich in his Gamasutra article in fact used a frame-coherent method similar to that used in ROAM. I haven't implemented this, but I can guess the results are probably on par with ROAM - I'd really like to implement this and see how it performs.

I feel I should point out that I read some GDC presentation slides by Jonathon Blow on http://www.bolt-action.com where ROAM was attacked for being quite poor for large triangle counts. He came up with some quadtree algorithm using isosurfaces which seemed to work better for him. Not sure I totally follow his reasoning, but it's good to read about someone else's discoveries.

The main pros of bintrees are slightly better tesselations (allegedly!) and no need to fix cracks in the terrain mesh. On the downside, bintrees are tricky for texturing and are awkward to arrange into strips/fans particularly if using some kind of frame-coherent technique.

Quadtrees are certainly easier to work with (simpler data structure), and most quadtree LOD systems make constructing triangle fans a piece of cake. The square nature of the nodes also makes managing surface textures easy. I'd say the biggest problem with quadtrees is the need for some kind of crack fixing mechanism in the LOD algorithm.

Which is best? I personally prefer the quadtree approach, and looking around the various games and other apps out there, it seems that it's probably the most widely-used technique. Then again, one look at Tread Marks and its clear to see that bintrees can be used to brilliant effect. Experiment with both and see which fits best with what you want to do.

Chris

IP:

Klaus Hartmann
Member
posted April 28, 2000 11:39 PM            
Note, that I haven't implemented ROAM, but I'd like to add a couple of things...

Every continuous LOD system needs some sort of crack-fixing. But some CLOD algorithms make this easier than others. It should be relatively easy in ROAM, and it is definitely easy with Röttger's algorithm (quadtree). An example where crack-fixing is a real pain is the CLOD algorithm from Peter Lindstrom (quadtree).

Memory requirements are also important. As to my understanding, Röttger's algorithm has the smallest memory requirements, then comes ROAM, and then Lindstrom's algorithm.

The support of geomorphing is another important feature. All of the three systems support geomorphing, but Lindstrom doesn't explain how it works in his algorithm (because Siggraph papers are limited to 8 pages, and he already had 10 pages).
As for geomorphing in Lindstrom's algorithm: "The geomorphs are based on using the isovalue of the implicit function to adjust the height of each vertex. The equation for the bialy isosurface is replaced with that of of an enclosing ellipsoid to get a smoother and more coherent morph." (whatever that means ).

A final word on Lindstrom's algorithm. The above may sound as if Lindstrom's algorithm was bad. It's not! It's a classic, really. It was the first terrain CLOD algorithm that was published.

IP:

Chris C
Member
posted April 29, 2000 08:48 AM         
I forgot to mention geomorphing!

I also made a couple of mistakes in that previous post - Jon Blow's algorithm DID use a triangle bintree, not a quadtree as I said. The problem he found with ROAM was that recomputing the priority for every triangle in a given triangulation becomes very costly for high detail triangulations (50k polys per triangulation). He came up with a method that uses bounding spheres to represent the distance at which a given tri needs to be split. These spheres are approximations to more accurate isosurfaces that would take into account projected pixel error etc. The spheres are arranged into a hierarchy so that finding out which tris to split/merge can be computed efficiently. It seems like a good idea, but his description is not incredibly clear - has anyone else looked at this?

If I remember correctly, Jon Blow reckoned Lindstrom's algorithm actually performs better for detailed triangulations than ROAM, but his sphere tree method performs better than either of them. This might be worth investigating.

Chris

IP: