Re: [Algorithms] ROAM

[Mark D. <duc...@ll...>]

Tom Forsyth wrote:
> ROAM: excellent quality for a given number of triangles, but speed is hard
> to achieve with the standard algorithm. Good for changing landscapes (i.e.
> blowing up hills, etc)
> 

The main ideas of ROAM continue to be relevant:
  - split+merge queue
  - do as much work per frame as you have time for
  - happens in optimal order
  - fastest frustum culling around
  - flexibility to do lots of things with the split+merge priorities
    - line-of-sight correction
    - correct object placement (no floating or interpenetration)
    - easy silhouette enhancement
  - fast updates for dynamic terrain (as Tom mentions)
  - excellent frame-to-frame coherence (especially important for cached
    chunk implementations, see next item)

> ROAM meets VIPM: I'm not sure about the status or details on this - it's the
> ROAM principles, but with far more precalculation. Sounds promising.

Simplest case: use an AGP chunk of 256 uniform-size triangles to draw each
"ROAM triangle".  I've got free source that gets 40M tri/sec draw rates
right now with a fractal terrain created on the fly using this.

Adaptive case: use adaptive chunks, precomputed (see Alex Pomeranz's thesis
at www.cognigraph.com/ROAM_homepage) or cached (see upcoming IEEE Vis paper
by Joshua Levenberg).  The cache entries are static until replaced.
Both have research implementations that are not avaiable yet.  Thatcher
Ulrich's chunk demo is very similar in flavor in terms of the way chunks
are built, but the way boundaries are handled are much simpler with
the ROAM-style approach (there are no special fix-ups on the boundary
at all).

Next fancier case: sliding window "VIPM" ideas for the chunks.  Allows
"fractional splits" of a ROAM triangle patch.  Not implemented yet
as far as I know.  Seems straightforward, but a lot of implementation
work, and perhaps not that big an improvement (see next point).

My sense is that at this point the triangles are getting really small
on current graphics hardware, and that adaptivity within a chunk is
becoming less important.  For my 40Mtri/sec code, I just make a single
strip pattern hand-tuned to maximize vertex cache coherence and
minimize degenerate triangles.  The critical inner loops are very
fast compared to on-the-fly adaptive techniques with chunk caching.
So for now I'm sticking with uniform triangle sizes within a tri patch,
and keeping the CPU/memory-intensive adaptivity in the splitting and
merging of tri patches.

> And finally: just draw everything. Works just fine for games with a low
> viewpoint that don't need to draw very far, e.g. FPS games.
> 

Only if the number of triangles total is small enough of course.
Personally the terrain in all the games I've been playing lately
is really crude compared to what is possible at high frame rates.

Trent Polack wrote:
> > 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.

ROAM speed depends heavily on the details of the implementation.
Is 40Mtri/sec fast enough?  Just put AGP "patches" per ROAM tri.
I'll give my linux+nvidia code-in-progress to anyone who asks so
you can see this yourself.  You get a few thousand patches displayed
per frame, so you are really back in the situation we were in in 1996
when we first came up with ROAM (CPU dealing with 3000-6000 tris),
except now each "triangle" is a 256-triangle chunk, and ROAM is
*more* approprate than before since it optimizes the limited budget
of chunk-cache updates available per frame.

Also, there are lots of enhancements/variations on ROAM floating out
there, lots of implementation notes, and more coming out all the
time.

Overall I'd say the nicest aspect of ROAM, in hindsight, is that
it is really easy to "get" the idea of a minimal ROAM implementation
and code it up in a day, and then gradually add more and more
optimizations as your performance analysis dictates.  Other techniques
generally require a big ramp-up time before you get much of
anything going, at least for the scalable algorithms out there.
This makes it very attractive for anyone learning how to make
a display system for large terrains for the first time.

Cheers,

--Mark D.