ROAM Algorithm Version 2.0 -- work in progress

[ROAM Algorithm Homepage]

ROAM at 40 million triangles per second On modern graphics hardware using AGP chunks, ROAM is shown here running with 1.56 million triangles at 25.6 frames per second. The geometry in this case is generated procedurally during flight using midpoint displacement with smooth interpolatory subdivision. [NOTE 2003-03-24: On my new RADEON 9700 the roamtest code clocks in at 56 million tris/sec].

ROAM Tutorial Code -- Diamonds, Split-Only and Fast Split-Merge Code is provided to introduce the diamond data structure and its use in split-only and split-merge ROAM implementations. The diamond point of view is used for the main "backbone" data structure for the upcoming ROAM 2 Algorithm. The code is developed in several small steps, up through a full split-merge optimizer with fast bucket-based queues. It compiles under both windows and linux.

This page outlines and journals the recent best theory, debates, experiments and overall progress in the development of an updated and extended version of the Realtime Optimally Adapting Meshes (ROAM) Algorithm, to be called ROAM 2.

ROAM Version 2 contains all the efficiencies of the original ROAM, but is updated to:

1) use diamonds instead of triangles as the backbone data structure [completed]

2) be fast for modern graphics hardware through AGP chunking [completed] and, in addition, progressive vertex arrays [theory complete, partial implementation]

3) deal with texture split-merge (replacing clipmapping) [theory complete, partial implementation]

4) allow paging and streaming of geometry and texture [fairly complete implementation, not ready for prime time]

5) work on arbitrary geometry (not just terrain) [complete]

6) shade via pixel lighting to get full dynamic illumination without per-vertex artifacts [theory and software-only implementation -- see LibGen/Surftools/Mesh]

7) generate procedural geometry on the fly using high quality midpoint displacement [complete but not fancy] and possibly coarse-to-fine river basin generation [partial theory]

8) provide runtime occlusion culling as a kind of per-patch frustum culling [implementation by Lucas Ackerman looking good, not quite ready for prime time]

9) reduce storage and bandwidth with wavelet compression of the texture and geometry [theory complete, components complete but not integrated into a full view-dependent optimizer]

This is work in progress, by myself and others working at LLNL or at UC Davis. I gave author Trent Polack an early heads-up on the basic diamond data structure based on his interest in using it for a recent book, Focus On 3D Terrain Programming. The book contains tutorial material on the basic ROAM 2 backbone data structure, the diamond, along with its use in a split-merge ROAM implementation. Certainly I should acknowledge the great ideas from Lucas Ackerman, Peter Lindstrom, Valerio Pascucci, Ken Joy, David Sigeti, Alex Pomeranz, Ben Gregorski and many others that have permeated into this effort. I take full responsibility for any inaccuracies, ommisions or other discrepancies on these pages. This web site (and related code) is maintained as a personal hobby in my spare time and should not be considered to be affiliated with my employer (yadda yadda...).

-- Mark Duchaineau, duchaine@cognigraph.com

Updated 2003-02-20

Updated 2008-01-22 -- corrected spelling of "Polack" and updated link to his book