# SOAR terrain...

## Recommended Posts

Funkymunky    1413
Hopefully this time around someone can help a brother out! Has anyone actually implemented a working SOAR engine? I've seen the Ranger MKII stuff, that's my inspiration. Can anyone explain the algorithm to me in words other than those used in the articles? Like, without just saying to cull for the error metrics, etc. Thanks in advance to anyone who can actually help me with this stuff! *update* Here is what my current attempt looks like: I've calculated a series of radii for the different levels of refinement, basically 64 radius values. Then, when refining, I check if a sphere with a radius at that level of refinement centered at that vertex is within the view camera's view frustrum. I don't think it works too good... what's the problem? [Edited by - Funkymunky on November 26, 2005 4:19:30 PM]

##### Share on other sites
Basiror    241

I have found this page here but I don t know if its related to what you are doing at all

http://www.cc.gatech.edu/~lindstro/papers/vis2001a/supplemental/

##### Share on other sites
Funkymunky    1413
yeah that page is like a comprehensive summary of the SOAR technique. The Ranger link is what I'd seen. Anyone understand this stuff?

##### Share on other sites
Trienco    2555
Unless you are using a sphere for every triangle the screenshot looks more like your different lods don't match at the edges and hence ugly gaps. Culling isn't your problem. Can you switch to a wireframe view?

##### Share on other sites
biki_    236
i have working implementation of SOAR,
the whole trick behind it is properly calculate errors
and bounding spheres
binary triangle tree is quite old idea but SOAR is the first that
solves the problem of cracks as precalc.
1. spheres must fully enclose their children spheres.
2. errors for each level must be largest or equal than any of children
if you find max error you don't only check children of this triangle
but also triangles that are neighbours, its easy to do with layers.

##### Share on other sites
Guest Anonymous Poster
It appears you're getting cracks in your terrain mesh because you haven't nested your error and bounding sphere radius values properly.

In order to maintain a continuous mesh, it is essential that for any give node which is active, both its parents and all their ancestors must also be active. Properly nesting will achieve this.

Remember, bounding spheres have two purposes, to test for frustrum visibilty, and when inflated using the error value, to test when the node is close enough to be considered active.

Read this paper if you are having difficulty: Terrain Simplification Simplified: A General Framework for View-Dependent Out-of-Core Visualisation.

##### Share on other sites
Funkymunky    1413
Yes I believe the nesting errors thing is definately my problem. Right now what I do is I just have a list of numbers that represent the sphere radii at the levels of refinement, then when I'm refining I check for visiblity of the sphere with the refinement level of the vertex I have found my way to and centered at the vertex as well. If it's visible I continue refining.

Also, I am using DirectX. Right now what I do is read in a picture, create a set of vertices that represent basically a height map of that picture, and then assign indices during refinement. So basiscally when the map is generated it is just figuring out a triangle strip of the indices. This doesn't seem to allow me to use the key feature of having huge datasets, so what am I doing wrong?

And can anyone help me understand the nesting error metrics thing? I've read the article many times, and that part of it is gibberish to me. Lots of math symbles and relationships but no visual description of what is going on.

##### Share on other sites
Funkymunky    1413
BUMP anyone?

##### Share on other sites
Guest Anonymous Poster
The SOAR terrain file should be an array of nodes, one for each elevation value on your map. The structure of each node should be like this:

class Node
{
public:
Float e, r;
Vector3D v;
};

So, if your elevation file’s dimensions are 1025x1025 – files must always be square and a power of two plus one, the bigger the more efficient the SOAR algorithm becomes, especially if you use hierarchical indexing – it would be about 20MB in size assuming 32-bit floats. You don’t need to store dimensional information because that is easily determined from the number of bytes in the file. I believe it is also advantageous to store node location in full, rather than only elevation, because it is faster at refinement time and you can map your terrain data onto any shape, such as a plane or sphere, in the pre-processing algorithm without having to make any special arrangements in the refinement algorithm.

Every interior node has four children and two parents unless it is on the map boundary, in which case it has two children and one parent. Leaf nodes, of course, have no children.

In the refinement stage, for a node to be active, its un-inflated bounding sphere must at least straddle, or be fully within the viewing frustrum, and the inflated (with the error value) bounding sphere must encompass the camera’s viewpoint. To avoid cracks in the terrain, also known as a continuous mesh, ALL its ancestors must also be active. This means, there needs to be a relationship between a node and its parents. A relationship in which an ancestor’s error value will be at least as big as the largest of its four children, and it radius will be larger than its four children. This ensures that if the viewpoint is within a node’s sphere, it must by definition be within all its ancestor’s spheres. All this information is computed at the pre-processing stage, usually a different application to the refinement program, in a bottom up manner, starting with the leaf nodes and ascending all the way up to the top level.

The radius value of a node is computed by looking at each of the four child node radii, adding the distance to that node - different for each one because they are likely to be at varying elevations - and taking the maximum value of the four. Leaf nodes have zero radii.

The error value of a node is usually the vertical distance between the parent triangle’s longest edge midpoint and the actual elevation at that location or the largest error value of its four children, whichever is the biggest.

Hope it helps,

Justin.

##### Share on other sites
Funkymunky    1413
That actually helps a great deal. I'm excited now, I think I'm getting closer to grasping this thing

So, for these nodes:

For the node at C... are it's two parents B and A? And it's children D and E and D and F?

And for node B, it's parent is node A, and it's children are C and the node unlabeled on the midpoint of the right leg? Is that right?

##### Share on other sites
Guest Anonymous Poster
Strictly speaking, for node C, its parent is B and its GRANDparent is A. Its child is D and further descendants are E and F.

However, to avoid terrain cracks in your example, an additional node would have to be active on edge A to B, and would result in two extra triangle bisections to join with F.

##### Share on other sites
Guest Anonymous Poster
And having posted that, I've just noticed there would have to be a couple of other edge bisections in the right hand triangle to avoid other cracks.

Justin.

##### Share on other sites
Funkymunky    1413
Thanks but this is speculative, I'm just trying to understand how there are two parents and four children

##### Share on other sites
Funkymunky    1413
Alright now I see it, it has to do with that Directed Acyclic Graph they kept talking about.

In this, for node A, the children are b, c, d, and e, and the parents are P1 and P2. This is why you precalc from the bottom up and refine from the top down. Nodes on the edge only have two because the other two are outside the map's boundaries.

What I'm becoming curious about now is screen space error. Apparently during runtime you're supposed to project the object space error of a node onto it's bounding sphere at the closest point to the camera to get "screen space error." What is that all about?

Also, how do I handle the index list? I mean, do i allocate a huge chunk of data for indices ahead of time and then repeatedly fill it in during refinement? This seems like a waste since I would probably have to do something like 6 times the product of the dimensions of the map just to ensure i don't run out of space for indices. Maybe this is a problem with trying to do SOAR in DirectX instead of OpenGL; OpenGL is procedural, wheras DirectX is more OO. Should I be using dynamic VBs and IBS?

Finally, are you telling me that I should have a separate application which first creates a huge data structure with pointers to children and parents, calculates all the errors and whatnot, and then saves this information to a file for me to load by my refinement program (which therefore will not have to explicitly keep track of these children and parents)?

[Edited by - Funkymunky on December 7, 2005 10:03:10 PM]

##### Share on other sites
biki_    236
you don't need any pointers at all
all you can do with simple array of heights and max-errors
the structure is recursive so you don't really need to keep it anywhere.

##### Share on other sites
Funkymunky    1413
so how do you traverse from bottom up then? How do you know which the parents and children are?

##### Share on other sites
biki_    236
easy.
if this is root level

*---*
|\ |
| \ |
| \|
*---*

then you subdivide it like this

*---*
|\ /|
| + |
|/ \|
*---*

and array at position '+'keeps all information (it's 2,2 here)
then if you split right triangle you get

*---*
|\ /|
| *-+
|/ \|
*---*

data at 4,2

and so on

i just don't understand why would you want any information about parents at all
whole idea behind SOAR is not to use it at all
only when precalculating you need properly set errors
and for that you need only to lookc carefully at patterns triangles create

like

odd level
*-*-*
|/|\|
*-*-*
|\|/|
*-*-*

even level

*---*
|\ /|
| * |
|/ \|
*---*

##### Share on other sites
Funkymunky    1413
So, do I go through the whole process of recursively splitting down the triangles until i get to the leaves, or is there some formula I can use to find the parents and children for any given node?

##### Share on other sites
biki_    236
you don't need parents
you calculate errors bottom up
for each triangle error is calculated based on its children
(easy to find) and children of it's simmetric triangle
so if you have triangle ABC

A---B
| /
| /
|/
C

you find symmetric triangle BDC

A---B
| /|
| / |
|/ |
C---D

then to find children you find O

A---B
| /|
| O |
|/ |
C---D

and children are AOB,COA,DOC,BOD
you take their errors (calculated on lower level)
calculate new error for CB line as distance of O to real terrain
find MAX and keep that value in array at position O

##### Share on other sites
Funkymunky    1413
So how about this question, do the nodes in the corners of the map have error values? Because they will never be found as midpoints.

I simply don't understand. That point O could be in any number of triangles, from the huge one that encompasses the whole bottom portion of the map, to the tiniest little one that is a piece of a mountain at the map's center. How do you assign a single error to it?

Biki thanks for this help, you are a godsend my friend

[Edited by - Funkymunky on December 9, 2005 3:26:58 AM]

##### Share on other sites
biki_    236
of course, some of the positions in your error-array will be unused
but it's still more efficient than creating whole hierarchy with pointers

##### Share on other sites
Justin Nixon    133
The five base nodes - the four corners and the centre - are, in most implementations, always considered active. Therefore, the error and radius values for these nodes are unused and can be left unset if you wish. In practice, however, with the central node being at the top level minus one, its error and radius will have been computed by taking into account EVERY descendant node in the map, all the way down to the mass of leaf nodes. Its radius will be the largest in the map - because it will encompass every other radius - and its error will at least be as large as the largest in the map.

Assuming linear indexing and your triangle's points are called i, j, k, with i being the apex and j to k being the longest edge, the index of the midpoint is computed by taking the average of the indices contained in j to k. Using DWORDs as the indexing type, you can do it like this:

inline DWORD ChildIndex(DWORD j, DWORD k)
{
return (j+k) >> 1;
}

The index of the SW of the map is zero, while the NE is the last node in your file.

Justin.

##### Share on other sites
Guest Anonymous Poster
The five base nodes - the four corners and the centre - are, in most implementations, always considered active. Therefore, the error and radius values for these nodes are unused and can be left unset if you wish. In practice, however, with the central node being at the top level minus one, its error and radius will have been computed by taking into account EVERY descendant node in the map, all the way down to the mass of leaf nodes. Its radius will be the largest in the map - because it will encompass every other radius - and its error will at least be as large as the largest in the map.

Assuming linear indexing and your triangle's points are called i, j, k, with i being the apex and j to k being the longest edge, the index of the midpoint is computed by taking the average of the indices contained in j to k. Using DWORDs as the indexing type, you can do it like this:

inline DWORD ChildIndex(DWORD j, DWORD k)
{
return (j+k) >> 1;
}

The index of the SW of the map is zero, while the NE is the last node in your file.

##### Share on other sites
Funkymunky    1413
I still don't understand how you go about traversing from the bottom up. If you go through each node how do know where it will be in the process of recursing from top down?

##### Share on other sites
Guest Anonymous Poster
The logic of pre-processing in a bottom-up fashion is quite complicated. You can do it less efficiently, but it would still work, by using a similar recursive algorithm to your top-down refinement method, except I think you have to process the entire map twice to ensure error and radius values are propogated up to both parents.

process
{
fill entire file with zeroes

may do this more than once
{
subprocess western triangle
subprocess northern triangle
subprocess eastern triangle
subprocess southern triangle
}
}

subprocess
{
if(not on bottom level)
{
compute child index
compute and write location to child node
compute and write the error to child node - take the maximum
subprocess left child triangle
subprocess right child triangle
write error to parent (apex of current triangle) - take the maximum
compute and write radius to parent - take the maximum
}
}

When I say "take the maximum" you use the max() macro to ensure you don't overwrite any useful data that may have already been written to that node because this approach will visit each one more than once.

Even if I've made an error in the above pseudo code, you should now have enough insight into SOAR to get your own implementation working.