ROAM Algorithm Tutorial Code -- Diamonds, Split-Only and Split-merge

[ROAM Algorithm Homepage] [ROAM Algorithm Version 2 work in progress]

Updated ideas on implementing ROAM-like terrain display

This is a screenshot (actual size) taken of the roam tutorial code running with full split-merge using the diamond data structure for a procedural terrain.

For those interested in learning some of the updated ideas on implementing ROAM-like terrain display, I have posted some fairly complete tutorial code (Win32 and Linux/Unix tested) that compiles into a simple demo.

So far no texturing or even "real" terrain, just fractal terrain with a grid texture. Instead the focus is on the core data structures and algorithms. Included are new ideas on a pure-pointer (index free) diamond-based data structure, and full split-merge queues with various optimizations. The tutorial progresses in modest steps from the utterly simple step 1 pure recursion, through frustum culling and the new diamond data structure, up to a fairly complete split-merge optimizer. At each step your extra learning and coding effort is (hopefully) rewarded by increased performance or flexibility of the code.

I invite you to try out the code and let me know of any problems or suggestions you have. I'd like to thank Thatcher Ulrich for helping get this working on Win32 boxes. It now works using both batch compiles and through the MSVC 6 IDE workspace. I'm quite a novice at MSVC so right now I have things mostly in default modes, e.g. it is compiling in Debug mode and is slowed than my Linux builds on the same box.

Lucas Ackerman helped enourmously with some profiling that identified bottlenecks at two stages in the implementation. As a result of the first profile, I moved to the pure-pointer diamond scheme instead of my first implementation using a "pointer free"/"pure index" scheme. The latter relied on hash lookups based on the 64-bit composite (i,j) index, and despite my best efforts that lookup was >50% on the profile.

The next "step" will likely be the use of chunks, wrapped on top of both display lists (the general fallback) or AGP vertex arrays (Vertex Array Range extension to OpenGL). Already the code uses a single big vertex array in step 4, but this is not compatible with high vertex coherence/stripping/fenced updates etc that are enabled by chunking.

Some early chunking code is available here. Unlike the tutorial code, this is not for the faint of heart.

-- Mark Duchaineau

Updated 2003-02-20 --