ROAMing Terrain - Real-time Optimally Adapting Meshes

CSC 572 Final Project under Professor Zoƫ Wood - Spring 2010


Designed by

Ben Davini

Computer Science Department

California Polytechnic State University


Project Description

Many types of geometric data compete for limited polygon budgets. Terrain is one of those types of geometric data. Terrain, however, is challenging because it is not naturally decomposed into parts whose complexity can be adjusted independently. Specifically, it is difficult to render dynamic, view dependent triangle meshes at high FPS. ROAM attempts to address some of these concerns by utilizing a pre-processed multi-resolution terrain - which increases memory requirements, but decreases the computation required during runtime. Using the pre-computed terrain, ROAM uses a split-queue and merge queue to manage the number of rendered triangles.

This project is a very rudimentary implementation of the ROAM algorithm, in which only the split-queue operations are implemented.

The Project


Image Description
The image to the left shows an example (and robust) roam terrain. In this image, the viewer is flying over the terrain. Note that the triangles on the more mountainous left side are higher resolution, while the triangles on the right side are very coarse. This is the desired result, as more undulating areas require a larger number of triangles to maintain a correct appearance, while flat areas can easily be represented in only a few triangles
This image is a plot of Matlab's "peaks" function. "Peaks(n)" returns an n x n matrix filled with values that, once plotted, show up as peaks and valleys. Note that the resolution of the function is identical everywhere in this picture, even in the flat areas in the corners. This area could easily be represented by a few flat triangles.
This image shows a birds-eye view of the "peaks" height map, as implemented in my version of ROAM. Note that the triangles on the right are more numerous (finer resolution) than those on the left. This is due to the fact that the camera is actually closer to the right side of the image, and the "error metric" breaks the triangles that are closer to the camera. This is desired and reasonable, because as the viewer gets closer to a part of terrain, they will likely want to see more detail.
This image is a side-view of the peaks function; here, one can more closely see the peaks and valleys. Again, it is difficult to see, but the triangulation of above is maintained - that is, the triangles closest to the camera show the greatest level of detail, while those in "the distance" are more coarse and less accurate.


The lower two of the above images show my work in implementing ROMS. The Matlab image above exists to show what type of "terrain" I was trying to reduce; the first image above is of ROAM in action. It is from the author(s) of the ROAM paper, and is of course more robust than my wireframe images.


I implemented a simplified version of ROAM by using a normalized n x n height map - that is, once the height map was transformed to a set of vertices, those vertices had no magnitude larger than 1 in any of the dimensions. (as an example, the height of the peak in the middle is 1 in the z-direction; the limits of the x and y coordinates are -1 and 1. The bottom left corner, for example, is (-1, -1, 0)). To enable more simple splitting and management of the "terrain", I enforced that the height map must be of dimensions 2n+1. This makes it such that at each level of subdivision, all triangles can be split down the middle. The height map visualized above is 9x9.


A "split" function is called if a triangle center is within a threshold distance of the camera; this call may force a split of one or more of the triangles neighbors in order to maintain a smooth (crack-less) terrain. In a full implementation, a "merge" function would be called on triangles that were once split, but are now beyond that threshold distance.

Keyboard and Mouse Options

When viewing the terrain, the user can drive around by using the following keys


Press 'w': Moves forward (into/towards the terrain).

Press 's': Moves backward (away from the terrain).

Press 'q': Strafe left around the terrain

Press 'w': Strafe right around the terrain


Mouse Click and Drag: Move to look left, right, up, or down.



Visual C++ Express 2010 solution


ROAM Paper article on Binary Triangle Trees and Terrain Tessellation

Lew Hitchner's BinTree slides (ask Zoe)