Back to General and Gameplay Programming

BSP Tree traversal

Adam Brown · 2006-07-04T17:18:46

I'm currently working on v30 BSP Tree traversal to locate the camera in a leaf. How I understand it is you start at the first element in the array which is the root node in the tree. Then you keep testing the children and going with the one that contains the camera until it narrows down to a leaf. But this understanding is flawed. First I rendered the bounding boxes for the nodes (none leaf tree nodes), then I rendered the bounding boxes for each leaf and overlaped them, they are exactly the same. The Leafs are not finer areas of space than the nodes like I thought. Also, the camera when started at (0,0,0) is not contained in any of the children of the root node. So the recursion stops there. So there is some large flaw in my understanding of how the BSP tree works, could anyone shed some light on this for me? Here is a screen of the overlay with the geometry: Here is a screen of the overlay without the geometry: Here is a file I'm producing after reading in the BSP file: (Note: I cropped out most of it because it's very large, but you can see the root node here) As you see each child has an index to a child node, if the index is negative it means it is an index to a leaf. The thing is though, there are in this case 54 leafs, meaning indicies 0-53, yet in the root node it has a negative index (leaf index) to 54, when like i just said, the indicies only go up to 53! It never seems to be off by more then 1, so maybe the key is to subtract 1, but that just seems illogical... Quote: //================================== // Black Engine: -= 3dpoints.txt =- // // Description: // --------------- // This textfile was created by // traversing // [BSP File] // in BSPManager.cpp // // [.bsp used]: "maps/q2/curTest.bsp" //================================== Header: version- 30 numFaces: 134 numEdges: 309 numVerts: 89 numLeafs: 54 numNodes: 52 Node # Info -+-+-+- -+-+-+-+-+- Node 0 numFaces 2 children[0]: 1 children[1]: -54 min: -5 0 3 max: 1 3 -5 Node 1 numFaces 2 children[0]: -2 children[1]: 2 min: -5 0 3 max: 1 3 -5 Node 2 numFaces 4 children[0]: -3 children[1]: 3 min: -5 0 3 max: 1 3 -5 Node 3 numFaces 2 children[0]: 4 children[1]: -53 min: -5 0 3 max: 1 3 -5 Node 4 numFaces 10 children[0]: 5 children[1]: -52 min: -4 0 3 max: 1 3 -5 Node 5 numFaces 2 children[0]: -4 children[1]: 6 min: -4 0 3 max: 1 3 -5 Node 6 numFaces 2 children[0]: 7 children[1]: 8 min: -4 0 3 max: 1 3 -5 Node 7 numFaces 2 children[0]: -5 children[1]: -6 min: -4 0 -4 max: 1 3 -5 Leaf 0 min: 0 0 0 max: 0 0 0 Leaf 1 min: -5 0 -5 max: 1 3 -5 Leaf 2 min: 1 0 3 max: 1 3 -5 Leaf 3 min: -4 3 3 max: 1 3 -5 Leaf 4 min: -2 0 -4 max: 1 3 -5 Leaf 5 min: -4 0 -4 max: -2 3 -5 Leaf 6 min: 0 0 -1 max: 1 3 -4 Leaf 7 min: 0 2 0 max: 1 3 -1

General and Gameplay Programming Programming

Started by Wavesonics June 27, 2006 06:58 PM

26 comments, last by Wavesonics 17 years, 9 months ago

Wavesonics

330

Author

June 29, 2006 04:39 PM

Ok my not exactly thread safe Logging class is complete and w\ a little fussing it reports the entire recursive algorithm:

[EDIT: the - signs are being chopped off of the leaf indicies, i'm fixing this...]

traverseBSPTree() calledtraverseBSPNode() calledCur Pos: 0, 0, 0New Node:Child[0] 1Child[1] -=pass===Child[1] -Is NodeMax: 7, 4, 8Min: 2, 2, 4Traverse this nodetraverseBSPNode() calledCur Pos: 0, 0, 0New Node:Child[0] 2Child[1] 6=pass===Child[1] 6Is NodeMax: 7, 4, 8Min: 2, 2, 4=pass===Child[1] 6Is NodeMax: 7, 4, 8Min: 2, 2, 4Is NodeMax: 5, 1, 4Min: 4, 4, 4Traverse this nodetraverseBSPNode() calledCur Pos: 0, 0, 0New Node:Child[0] 7Child[1] -=pass===Child[1] -Is NodeMax: 7, 4, 8Min: 2, 2, 4Traverse this nodetraverseBSPNode() calledCur Pos: 0, 0, 0New Node:Child[0] 8Child[1] 2=pass===Child[1] 2Is NodeMax: 7, 4, 8Min: 2, 2, 4Traverse this nodetraverseBSPNode() calledCur Pos: 0, 0, 0New Node:Child[0] -Child[1] 9=pass===Index to LeafMax: 0, 0, 0, Min: 0, 0, 0, =pass===Index to LeafMax: 0, 0, 0, Min: 0, 0, 0, Is NodeMax: 7, 4, 8Min: 2, 2, 4Traverse this nodetraverseBSPNode() calledCur Pos: 0, 0, 0New Node:Child[0] 1Child[1] 1=pass===Child[1] 1Is NodeMax: 7, 4, 8Min: 2, 2, 4=pass===Child[1] 1Is NodeMax: 7, 4, 8Min: 2, 2, 4Is NodeMax: 4, 1, 4Min: 0, 4, 2--=end=======----=end=======--=pass===Child[1] 2Is NodeMax: 7, 4, 8Min: 2, 2, 4Is NodeMax: 5, 1, 4Min: 4, 4, 2--=end=======--=pass===Index to LeafMax: 0, 0, 0, Min: 0, 0, 0, --=end=======----=end=======--=pass===Index to LeafMax: 0, 0, 0, Min: 0, 0, 0, --=end=======--

==============================
A Developers Blog | Dark Rock Studios - My Site

ju2wheels

167

June 29, 2006 05:06 PM

Why would two leaf nodes have boundaries of 0?

Do they define those structs differently from the node struct you posted last time?

[edit] see if this handles finding the origin properly

// Will retirn the index of the leaf the camera was found in__int16 BSPManager::traverseBSPNode(Point3D pos, BSPNode* node){    __int16 leafIndex = -1;    BSPNode *curNode;    BSPLeaf *curLeaf;    // Run once for each child    for(int i=0; i<2 && leafIndex == -1; ++i)    {        // If the index is possotive  it is an index into the nodes array        if((node->children) >= 0)        {            curNode = &nodes[node->children];            // See if we are in the current nodes bounding box            if((abs(curNode->min[0] - pos.x) + abs(curNode->max[0]-1 - pos.x) <= abs(curNode->min[0] - curNode->max[0]-1)) &&               (abs(curNode->min[1] - pos.y) + abs(curNode->max[1]-1 - pos.y) <= abs(curNode->min[1] - curNode->max[1]-1)) &&               (abs(curNode->min[2] - pos.z) + abs(curNode->max[2]-1 - pos.z) <= abs(curNode->min[2] - curNode->max[2]-1)))            {                     leafIndex = traverseBSPNode(pos, curNode);            }        }        // Else it is an index into the lead array, rationalize the index w\ *-1        else        {            curLeaf = &leafs[(node->children*-1)-1];            // See if we are in the current leafs bounding box                         if((abs(curLeaf->min[0] - pos.x) + abs(curLeaf->max[0]-1 - pos.x) <= abs(curLeaf->min[0] - curLeaf->max[0]-1)) &&                   (abs(curLeaf->min[1] - pos.y) + abs(curLeaf->max[1]-1 - pos.y) <= abs(curLeaf->min[1] - curLeaf->max[1]-1)) &&                   (abs(curLeaf->min[2] - pos.z) + abs(curLeaf->max[2]-1 - pos.z) <= abs(curLeaf->min[2] - curLeaf->max[2]-1)))                {                    leafIndex = node->children*-1;                }        }    }    return leafIndex;}

[Edited by - ju2wheels on June 29, 2006 6:06:30 PM]

Wavesonics

330

Author

June 29, 2006 07:38 PM

Well the test data has not changed, and that last post is a log generated from traversing the BSP tree not just dumping the arrays to a flat file.

The node struct has not changed either.

So I would assume, since there are 22 nodes and only 6 leaves, that more then 1 node point to the same leaf. But I don't know... I have to do some more testing, and look at the code you posted a bit.

I'm going away for the weekend though so, monday i guess.

[Edited by - Wavesonics on July 3, 2006 5:38:51 PM]

==============================
A Developers Blog | Dark Rock Studios - My Site

Wavesonics

330

Author

July 03, 2006 05:33 PM

Well your code is a step forward, when I fist spawn @ (0,0,0) it says I am in leaf 0 (that leaf index dervied of course from doing the (leafIndex*-1)-1 formula.

Which looking at the 3Dpoints file we see that leaf's bounding box is (0,0,0) to (0,0,0). So I guess it really did help find the origin. But after that it returns -1 after i move.

So is your snippet of code designed to just find the origin?

[EDIT]
OK!! VERY INTERESTING!!!

I removed the -1s from the ifs so it looks like this:

            // See if we are in the current nodes bounding box            /* IF            * (distance from the min to the current cord) + (distance from the max to the current cord)            * is less than or equal to            * (distance between the min and max)            * THEN            * cam is in this bounding box            */            if((abs(curNode->min[0] - pos.x) + abs(curNode->max[0] - pos.x) <= abs(curNode->min[0] - curNode->max[0])) &&               (abs(curNode->min[1] - pos.y) + abs(curNode->max[1] - pos.y) <= abs(curNode->min[1] - curNode->max[1])) &&               (abs(curNode->min[2] - pos.z) + abs(curNode->max[2] - pos.z) <= abs(curNode->min[2] - curNode->max[2])))

And it now returns leaf numbers as you change leaves!!

But it's not done yet, I was really just tinkering, i need to work out on paper what that math is doing to get a good grip on it to understand why and where I need to -1.

Also as I'm moving well with-in a leaf it keeps fluxing between -1 and the current leaf #, it's only when I stop inside a leaf it settels on a leaf # most of the time.

I say it's not done b/c of that and also, even when with in a leaf it some times returns -1.

Were you doing -1 to the max so that the edges of the leaves did not overlap?

But this is a huge step forward!
[/EDIT]

[Edited by - Wavesonics on July 3, 2006 5:33:20 PM]

==============================
A Developers Blog | Dark Rock Studios - My Site

ju2wheels

167

July 03, 2006 06:06 PM

Quote:Original post by Wavesonics
So is your snippet of code designed to just find the origin?

No it can find any point. If you visualize a box in 3D what my code basically says is that for the point to fall within (or on) this box, the distance from the point to each side of the box should add up to no more than the overall width of the box in any given dimension.

[edit]
ehh kinda gave the same explanation... heres a simpler explanation:

Say you have a number line from 0 to 10 representing a boundary.

Now lets say we have a point at position 5.

If we evaluate the points position relative to the ends of the boundary, we see that:
1. The distance from the point to 0 is 5.
2. The distamce from the point to 10 is also 5.
3. The sum of those is less than or equal to the distance from end to end which is 10. Thus concluding our point is bound.

Now lets move this point to position 11 (outside of our bound)
If we repeat steps 1 to 3 above... we find that 1 and 2 result in a total of 11 which is greater than the boundary... thus we can conclude our point is no longer contained. When repeated for each dimension of the box we can then determine if the point is contained in that box.

Quote:Original post by Wavesonics
But it's not done yet, I was really just tinkering, i need to work out on paper what that math is doing to get a good grip on it to understand why and where I need to -1.

I agree but I dont think this going to be an easy task without evaluating their code, as they have a pretty weird and custom implementation of a BSP tree to suite their specific needs.

[Edited by - ju2wheels on July 3, 2006 6:06:13 PM]

Zahlman

1,682

July 03, 2006 10:57 PM

Quote:Original post by Wavesonics
-3 is NOT greater then or equal to -5!

Uh, yes it is...

Wavesonics

330

Author

July 04, 2006 03:32 PM

He ya, I did out some math to show it did not always prove what I needed it to prove, then wrote some simpler math on here with out thinking bout or checking it. I am retarded.

==============================
A Developers Blog | Dark Rock Studios - My Site

Wavesonics

330

Author

July 04, 2006 05:18 PM

Kinda at a loss here, it's failing a check that it just shouldn't be failing on one of the nodes bounding boxes.

Here it is traversing this node, and if the "Total Dists" is lessthen or equal to the "Bound Dists" for every axis then it should print out "Traversing Node" and continue, but here you can see, they all are equal and yet, it stops and does not traverse. I took the individual checks for each axis and split them into seperate ifs and printed if they passed, and here Z is failing!!

Quote:
=pass===
Checking Left Child
Node 1
Max: 5, 1, -9
Min: -6, -1, 2

Total Dists X: 11
Bound Dists X: 11
Total Dists Y: 2
Bound Dists Y: 2
Total Dists Z: 11
Bound Dists Z: 11
X is bound
Y is bound

=pass===

if((abs((float)(curNode->min[0]) - pos.x) + abs((float)(curNode->max[0]) - pos.x) <= abs(curNode->min[0] - curNode->max[0])))    logger.appendActiveLog("\nX is bound");    if((abs((float)(curNode->min[1]) - pos.y) + abs((float)(curNode->max[1]) - pos.y) <= abs(curNode->min[1] - curNode->max[1])))    logger.appendActiveLog("\nY is bound");    if((abs((float)(curNode->min[2]) - pos.z) + abs((float)(curNode->max[2]) - pos.z) <= abs(curNode->min[2] - curNode->max[2])))    logger.appendActiveLog("\nZ is bound");

?!?!

==============================
A Developers Blog | Dark Rock Studios - My Site

BSP Tree traversal

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

BSP Tree traversal

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines