[Algorithms] Re: ROAM

[Eric G. <eg...@gl...>]

> Now, chapter 7 is where the dilemma is. I could teach the reader all about
> ROAM, but I'm wondering if I should really bother. Its a great algorithm,
> and I do not doubt its power, but I really do think its lacking in speed, at
> least compared to the previously mentioned algorithms.

I second previous replies on the ROAM algorithm (and family, since there are
so many variants depending on how far the implementation goes, its goals, etc.).
It is still quite valid and IMO will remain so.
Geomipmapping can only go so far when terrain and visible range get large,
and pure quadtree is CPU bound.

For illustration, the implementation I've been playing with uses chunks in a
similar fashion to Seumas McNally Treadmarks / split-only ROAM, with infinite
terrain, but either brute-force rendering (for chunks close to the observer) 
or ROAM patches ("far" chunks). This allows high-triangle count for the 
short-range (ala geomipmapping), while still allowing long visibility range.
Far chunks don't need many triangles, meaning that even a basic ROAM
implementation is already very effective (drastic triangle count reduction, 
"optimal" tesselation ie. quality, limited memory use,  simplified screen-space error 
computation etc.). 
Seams are solved by simply force-splitting along brute-force/ROAM chunks edges
(simple and fast, only adds a minimum of triangles).
During render, the brute-force chunks are sent to the graphics hardware first,
which allows some GPU/CPU parallelization of the ROAM computation 
while automagically "sorting" the chunks front-to-back (good for early Z tests).
(Delphi source code available at http:\\glscene.org, part of the library)

IMHO you cannot expose terrain rendering without explaining at least the most
basic forms of ROAM, especially if the reader wants to leave the short-range
terrain rendering area later on (flight-sims f.i.). 
You often have to make choices and trade-ofs, but knowing the full range of tools
available helps in making those choices, by allowing to pick or combine whatever
suits your own specific case.

Eric Grange
eg...@gl...