SOAR terrain...

could you post the link to this article

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/

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

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?

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.

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?

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?

Thanks but this is speculative, I'm just trying to understand how there are two parents and four children

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]

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.

so how do you traverse from bottom up then? How do you know which the parents and children are?

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

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

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?

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

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]

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

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.

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?

Excellent, thanks for your help! Now, when you said earlier "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" What do you mean by that? I have a function that checks if a bounding sphere is in the viewing frustrum... I do this with the radius, but what do you mean by the inflated sphere must "encompass"...?