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.

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.

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?

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.

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"...?

Quote:Original post by Funkymunky
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"...?

I meant to say that if the sphere touches at least one of the frustrum planes or is fully within the frustrum it is considered active as long as it satisfies the error condition, which determines when the camera is close enough to consider a node active. The paper explains frustrum culling better than I can on page ten.