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]

yeah that page is like a comprehensive summary of the SOAR technique. The Ranger link is what I'd seen. Anyone understand this stuff?

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.

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.

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.

BUMP anyone?

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:
Node(Float Error, Float Radius, Vector3D &rV) : e(Error), r(Radius), v(rV) {}
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.

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?