ROAM Algorithm: Realtime Optimally-Adapting Meshes

Realtime 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

The paper can be downloaded as: [PostScript] [PDF] [Gzipped Tar].
UCRL-JC-127870
Last modified: October 19, 1997

Abstract:

Terrain visualization is a difficult problem for applications requiring accurate images of large datasets at high frame rates, such as flight simulation and ground-based aircraft testing using synthetic sensor stimulation. On current graphics hardware, the problem is to maintain dynamic, view-dependent triangle meshes and texture maps that produce good images at the required frame rate. We present an algorithm for constructing triangle meshes that optimizes flexible view-dependent error metrics, produces guaranteed error bounds, achieves specified triangle counts directly, and uses frame-to-frame coherence to operate at high frame rates for thousands of triangles per frame.

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 are supported.

"ROAM Using Surface Triangle Clusters (RUSTiC)"

by Alex A. Pomeranz, U.C. Davis and LLNL

The paper can be downloaded as: [PDF].
June, 2000

Abstract:

Interactive visualization of terrain and general complex surfaces is a difficult problem that requires large data sets to be displayed and manipulated at high frame rates. Operations such as rotation and panning must be supported so a user can examine the data in critical areas, while maintaining highly accurate images. While previous surface approximation algorithms have yielded accurate and attractive-looking images, these algorithms are using only a fraction of the power of current graphics hardware due to being CPU bound. RUSTiC is an attempt to take advantage of the simplicity and accuracy of ROAM (Real-time Optimally Adapting Meshes), a previously developed surface approximation algorithm, while increasing the displayable polygon count by at least one order of magnitude.

Implementation Notes

This information is for those working on ROAM-like optimizers. Gathered here are guidelines on how to build the data structures and code, along with answers to questions that have come up in discussions with those who have been working on such implementations.

Introductory Source code

Here is an open-source set of code for use in learning about possible ROAM implementations. This code is maintained by Mark Duchaineau on a volunteer basis and is otherwise unsupported. Currently this compiles on SGI boxes and on recent Linux distributions after installing OpenGL/GLX-compliant drivers and libraries.

LibGenROAM010206.tgz

Many 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]
cHdsharp.tile.gz [13meg]
th7.tile.gz [9meg]

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 .

Contact Information

For further information, contact:

Mark A. Duchaineau -- duchaine@llnl.gov

Updated March 15, 2003