This topic is now archived and is closed to further replies.


Terrain Approach Confusion

Recommended Posts

Hey all! As a beginner into terrain engines, i have done a lot of research into ROAM, Bezier patches, and so on. What i am trying to figure out is a good approach for visibility determination if i want to use Bezier patches, and from there, how does LOD fit in? Hope someone can guide me in the right direction. Thanks! - Iceshadow

Share this post

Link to post
Share on other sites
ROAM uses a bintree -- a triangle mesh. The color of the triangles are derived from a texture representing the shaded relief of the terrain. Therefore, the orientation of the triangles have no effect on the displayed shading.

What I am getting at, is why incur the overhaead of bezier patches? They will not improve the shading of your terrain because that comes from your texture. The only thing they will improve is the silhouette of ridge lines, etc. However, the whole point of ROAM is to minimize error of the ridge lines as seen by the viewer. In other words, if ROAM is correctly implemented, your bintree will have the most subdivision at ridge lines that are visible from the current view position.

ROAM is all about visibility and LOD and verex morphing. In fact, read the ROAM paper about 6 or 7 times and all your questions will be answered. I know that doesn''t sound helpful, but focus your effort on understanding ROAM.

Share this post

Link to post
Share on other sites
Guest Anonymous Poster
Ok, thanks for the guidance.

I just had trouble seeing how this all fit together.

- Iceshadow

Share this post

Link to post
Share on other sites
ROAM is kind of tricky to implement. Some of the things you will have to consider and take care of are:

You should probably have a data structure like this:

typedef struct triangle {
TRI *ln; // left neighbor

TRI *rn; // right neighbor

TRI *bn; // base neighbor

VERTEX *peak;
VERTEX *left;
VERTEX *right;
int level; the subdivision level

// and some code like this

void split_tri (TRI *parent)
// if the parent has a base neighbor and it is not

// subdivided to the same level as parent, then split
// the parent's base neighbor

if (parent->bn)
if (parent->bn->level < parent->level)
split_tri (parent->bn);

now, create 2 new triangles out of parent, and if
parent has a base, which should now be of the same
level as parent, create 2 new triangles out of the
parent's base also. Create 1 new vertex which becomes
the peak vertex for our 4 new triangles.

You must initialize all the neighbor links of our 4 new
triangles. And, you must initialize all the parent's n
neigboring triangle's to point to the 4 new triangles.
Be careful! One triangle's base does not mean that
base triangle's base pointer is what needs to be

Example below:

new_tri->bn = parent->bn;
if (new_tri->bn) {
base = new_tri->bn;
if (base->bn == parent)
base->bn = new_tri;
else if (base->ln == parent)
base->ln = new_tri;
base->rn = new_tri;

The mesh is stored as a binary tree.

Another binary tree that you will probably have to store is below:

Also, you should create a function which can lookup from a precomputed table the total elevation change of any triangle that might exist. This is all possible triangles, from the top level node down to the smallest. Because the table would be a binary tree, for compactness, I would store it in a linear fashion. Also, although at any one time you are limiting yourself to say a couple thousand triangles in the mesh, you have to store the elevation change for all the triangles, which could be potentially millions. Therefore, I would store the elevation change data in the table for all but the bottom 3 levels, and write a function to compute the elevation change data for the bottom 3 levels on the fly.

The function which computes the elevation change for any triangle is the following:

compute_elevation_change (tri)
if not deepest level:
elevation_change = MAX (altitude) of all children - MIN (altitude) of all children.

if deepest level:
elevation_change = MAX (altitude) of all triangle's vertices - MIN (altitude) of all triangle's vertices.

You can go here and download the PDF paper:

Edited by - bishop_pass on June 18, 2000 1:18:32 PM

Edited by - bishop_pass on June 18, 2000 1:19:33 PM

Share this post

Link to post
Share on other sites
I though ROAM wasn''t that hard to implement, a split-only version with no geomorphing at least. The original ROAM paper isn''t the best source, I think Bryan Turner ROAM article on gamasutra is much better.

Get it here.

Also, check out the message board at Longbow Digital Arts, lots of terrain freaks there

Greets Tobias

Share this post

Link to post
Share on other sites