ROAM Algorithm: Realtime Optimally-Adapting MeshesRealtime display of complex surfaces is provided by dynamically computing a multiresolution triangular mesh for each view. The meshes minimize geometric distortions on the screen while maintaining a fixed triangle count. Pop-ups are minimized in several ways, and efficient mesh corrections ensure selected lines of site or object proximity are correctly represented. An incremental priority-queue algorithm uses frame-to-frame coherence to quickly compute these optimal meshes. This page provides the original ROAM paper relating to terrain display, plus implementation notes for those wishing to create ROAM-like optimizers.
ROAM Version 2.0 -- Work in Progress, Sample Code, New Techniques...For the latest developments in ROAM (theory, implementation hints, tutorials and source code), go to this page.
"ROAMing Terrain: Real-time Optimally Adapting Meshes"by Mark Duchaineau, LLNL, Murray Wolinsky, LANL, David E. Sigeti, LANL, Mark C. Miller, LLNL, Charles Aldrich, LANL, Mark B. Mineev-Weinstein, LANL
Our method, dubbed Real-time Optimally Adapting Meshes (ROAM), uses
two priority queues to drive split and merge operations that maintain continuous
triangulations built from pre-processed bintree triangles. We introduce
two additional performance optimizations: incremental triangle stripping
and priority-computation deferral lists. ROAM execution time is proportionate
to the number of triangle changes per frame, which is typically a few percent
of the output mesh size, hence ROAM performance is insensitive to the resolution
and extent of the input terrain. Dynamic terrain and simple vertex morphing
"ROAM Using Surface Triangle Clusters (RUSTiC)"by Alex A. Pomeranz, U.C. Davis and LLNL
The paper can be downloaded as: [PDF].
LibGenROAM010206.tgzMany of the concepts of the code and data formats are covered in the implementation notes above. I've tried to make the code directly related to ROAM clean and readable. Comments are at a minimum (that's what implementation notes are for...). The main code subdirectories related to ROAM are Tile and Qscene.
For testing this (and other) implementations, a few test datasets (.tile files) are available:
disk.tile.gz [.5meg]These were all constructed using our subdivision-surface editor, mesh (see the subdirectory Surftools/Mesh).
Compilation instructions are in LibGen*/README (generally, just cd into LibGen* and type "make"). Executables will be in LibGen*/bin . The primary site for LibGen distributions is http://www.cognigraph.com/LibGen .
Mark A. Duchaineau -- firstname.lastname@example.orgCopyright Notice
Updated March 15, 2003