ROAM with Caching Library Support

Sean Forsberg
CSC572 - Dr Zoe Wood


94k triangles at LOD 20 and tolerance of 1.00

Description

ROAM is a dynamic LOD terrain visualization system which allowed for real time visualization of a high level of perceived detail. Along with the visual algorithm, the developers of ROAM also presented several interesting aspects including memory layout for cache friendly accessing.

Starting with the concepts of ROAM and building their algorithm around an index accessor C++ class allowed for the use of another co-developed key/value caching system, CaDiDs (previously called PIMP), for predictive loading and caching data. The co-developed library investigated how an advanced cache system would affect performance of various applications.

ROAM Overview

The concept behind the scheme is using longest-edge bisection which aligns with the data points in a 2n+1 square height map (as seen above.) In addition to matching up with the data points, this algorithm prevents cracks (caused by 'T' intersections) by including it's parents in radial spheres when creating it's error metrics. With these,

CaDiDs Overview

As previously mentioned, the CaDiDs system is a distributed and caching key/value storage API. In addition to provide the standard key/value tracking, a plug-in system allows application developers to move data storage & data structure optimizations from application and into an API plug-in. Although the lines of code may be similar (or possibly even a bit more), a updated plug-in algorithm can be shared across all the applications.

Another key benefit of the distributed aspect of the project allows the key/value pairs to be cached locally and in other system's memory. This avoids the need to swap and rebuild data acceleration structures for large datasets. As this functionality is already available in the API, the plug-in developer simply needs to create key/value pairs and provide a prediction of use for said pairs.

This last item was the key reason for this API being included in this project. Imagine having a distributed system of a global ROAM dataset instead of a relatively small region! In the previous implementation of ROAM, this would not be feasible due to the terabytes of data that would be required for 1-10m resolution.

Included in the the main directory './docs' is a white paper on the cache project (as it stands) in much more detail.


What As Implemented


Gallery

(Left) LOD 1, Tri 4 & (Right) LOD 2, Tri 4
LOD 10, Tol 5.00, Tri 462
LOD 10, Tol 0.00, Tri 2,048
LOD 20, Tol 5.00, Tri 799
LOD 20, Tol 3.00, Tri 3,062
LOD 20, Tol 1.50, Tri 7,861
LOD 20, Tol 1.00, Tri 36,038
LOD 20, Tol 0.00, Tri 2,010,514

Note regarding last pair: The rivers are not correctly refining to full detail due to an error somewhere in the refinement step. The actually number of a full refine terrain should actually result in 2,097,152 triangles (width x height x trisPerSquare.) The problem is the extremely low error found at the rivers since they are at 0 elevation.


Discussion

CaDiDs

While of course goals were high, delays in the co-development of CaDiDs directly impacted the main goal of specific data collection. Unfortunately the caching project was WAY more complex than expected! Although this should not have been a surprise, it was a reality check.

On the positive, it is working. Additionally, it proved the ease of quick implementation of a plug-in to a graphics environment to be fairly easy. Though the plug-in is not currently quick (when using the CaDiDs API), the direct (non-key/value) file I/O through the plug-in is. Once the CaDiDs system is quicker, the key/value system will automatically be quicker. Also, the plug-in can be re-written to be quicker without ANY changes to the ROAM nor CaDiDs applications.

ROAM

I was able to take care of the T-intersections that were forming. The cause was trying to scale the camera and terrain data separately.

I'm still unsure why they say there is only 10 levels of detail when 20 are possible with the dataset. True, dataset has 1025 data points (equal to 210+1), there are two Levels of Detail possible to every edge point. On each even refinement (we'll call it "Split Cube"), a new 'n' data point level is added. However, odd refinements (we'll call it "Pyramid") simply use tie that point to a previous one. One will note that each refinement looks like the refinement of 2 steps previously, just 1/4 of size. I'd day they were actually simply referring to the 'n' value, but their data doesn't seem to match that.


Future Work


Compile/Run

To build the application, the full CaDiDs API has to be build.

Simply unpack the tar and run 'make clean;make' in the base directory. Once successfully compile, 'cd app-roam'.

There are two different options for compiling the application itself...

  1. Linear Indexed File
  2. CaDiDs Lib Access

To toggle between the two, edit './app-roam/src/plugin/ROAMPlugin.h' and modify '#define PIMP_PLUGIN [x]' to either 0 (File) or 1 (Lib)

Finally, type 'make' in ./app-roam/'

Controls

The following controls will move the camera and adjust the level of detail options


Links and Resources