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

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.

Ok, thanks for the guidance.

I just had trouble seeing how this all fit together.



- Iceshadow

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 thisvoid 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  changed.  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;    else      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:
http://www.llnl.gov/graphics/ROAM/




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

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

I think what i really dont'' understand the most is how to take the height map and make a mesh out of it.



- Iceshadow