Ben Davini - ROAM

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

Images

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.

Discussion

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 2ⁿ+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.

ROAMing Terrain - Real-time Optimally Adapting Meshes

Project Description

The Project

Images

Discussion

Keyboard and Mouse Options

Downloads

References