Jump to content
  • Advertisement
Sign in to follow this  
Wavesonics

BSP Tree traversal

This topic is 4517 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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: Geometry On Here is a screen of the overlay without the geometry: Geometry Off 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

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
Quote:
Original post by Wavesonics
The Leafs are not finer areas of space than the nodes like I thought.


Could you post some of the code where you construct your bsp tree?

Share this post


Link to post
Share on other sites
Quote:
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.


Yes thats correct.

Quote:
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.


Your root would have infinite boundary. Each division, if done properly, should lead to a smaller (more finite) boundary assigned to the children. Are you sure your tree is being constructed properly? A child node should not have the same boundary as its parent (unless there is a special circumstance that I cant think of).

Share this post


Link to post
Share on other sites
Ok, I may have been wrong about the leafs having the exact same bounding boxes as the nodes. I'm currently doing some more testing...

I also found my Camera class that was keeping track of the cameras cordinates in the world was incorrect about it's possition, so I have to fix this first before I get back to the BSP Tree problem.

For the cam position problem, there's not some easy OGL function i'm over looking to get that is there? Right now i'm messing around w\ taking the translation data and using it to modify x,y,z varriables in a camera object. But there is a little complexity w\ that i could fix if i just had some damn time to look it over...

Sorry for posting before I knew this.

But I do know that the root node does not have an infinate huge bounding box, which is exactly what I thought it should be as well. But really, I never test the bounding box of the root any way, I just start by testing it's childeren, so it's really inconsequential. But the root has a min and max of:

min: -5 0 3
max: 1 3 -5

Any way, I need to fix the camera possition tracking first, maybe after work tomorrow...

(BTW I divide all the cordinates by 64, thats why thay're so small)

Share this post


Link to post
Share on other sites
Quote:
Original post by Wavesonics
But I do know that the root node does not have an infinate huge bounding box, which is exactly what I thought it should be as well. But really, I never test the bounding box of the root any way, I just start by testing it's childeren, so it's really inconsequential. But the root has a min and max of:

min: -5 0 3
max: 1 3 -5


I didnt mean to say it had to be infinity. In a situation where you dont necessarily know how big the boundary is then making it infinity is the only way to ensure you capture everything... of course that doesnt mean that its a problem to make it finite if you know its max size before hand.

The theory remains the same, instead of being subdivisions of an infinite range, the children would then become subdivisions of the root's finite boundary.

Share this post


Link to post
Share on other sites
Ok I worked a lot of long standing issues out with my camera class, and it now records it's possition cordinates correctly.

So Here is the code I'm using to traverse the BSP Tree:
It's currently returning -1 with out fail. It only ever hit's the root node, then stops.


// Will retirn the index of the leaf the camera was found in
__int16 BSPManager::traverseBSPTree(Point3D pos)
{
// nodes[0] is the root node of the BSP tree
return traverseBSPNode(pos, nodes);
}

// 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((curNode->maxs[0] >= pos.x) && (curNode->maxs[1] >= pos.y) && (curNode->maxs[2] >= pos.z))
{
if((curNode->mins[0] <= pos.x) && (curNode->mins[1] <= pos.y) && (curNode->mins[2] <= pos.z))
{
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((curLeaf->maxs[0] >= pos.x) && (curLeaf->maxs[1] >= pos.y) && (curLeaf->maxs[2] >= pos.z))
{
if((curLeaf->mins[0] <= pos.x) && (curLeaf->mins[1] <= pos.y) && (curLeaf->mins[2] <= pos.z))
{
leafIndex = node->children*-1;
}
}
}
}
return leafIndex;
}






So Lets look at this, root node is:
Quote:

Node 0 numFaces 2
children[0]: 1
children[1]: -54
min: -5 0 3
max: 1 3 -5


our starting position is (-3, 0, -3)
So first we check out max, all my position cords MUST be less than or equal to the max cords, in this case they are, so thats all good.

Now we check to see if out position cords are greater than or equal too our min cords, they are not! -3 is NOT greater then or equal to -5!

So already we are not contained in the root node which is suppose to be the biggest one!

Well by passing this, I check the left child, node index 1:
Quote:

Node 1 numFaces 2
children[0]: -2
children[1]: 2
min: -5 0 3
max: 1 3 -5


and we immediately see that it has the exact same bounding box as it's parent (the root node). So thats kinda crap...

Well, next we check the right child, it has a negative index value so it is a leaf, it's also out of range of the leafs array... but what ever, if we subtract 1 from every leaf they seem to map out fine, so going under this assumption we go to leaf index 53:
Quote:

Leaf 53
min: -5 0 3
max: 1 3 3


Now this 1 is just f*ed... It's not even a 3D box! it's more of a 2D rectangle.
Sooooo... it's going to be pretty damn hard to be contained in a 2D object in 3 space...

I am using the standard Half-Life BSP compile tools (which is to say q2 tools since thats what they use) compiling from the Valve Hammer Editor. So I mean... I think it really has to be producing it correctly since these BSP files run in Half-Life just find.

Any ideas?

Share this post


Link to post
Share on other sites
I just made a new map and put an "info_player_start" entity in it, in half-life it is the thing that tells where the player will start. I don't currently read entity information into my engine but I thought it would be interesting to see how if at all it affected the compile.

Well it did, alot. First it screwed up the geometry rendering since I'm just statically culling the backs of polygons, I think once I get the BSP data and I can selectively render I won't need to cull and that will fix this problem.

So! Onto the more pressing issue of how it affected the Leafs Bounding boxes!
The answer is no! I ran a diff on a file that has every nodes and leafs bounding boxes in it from 1 run with the player_start and one with out, and they are identical.

So I now am very confident that it is being compiled correctly.

Share this post


Link to post
Share on other sites
I dont quite understand the negative leaf index you are using.

Since you are using an array implementation we have the following:

1. parent (or current root) is at position i.
2. parents children are at position i+1 and i+2 as long as they arent equal to the size of your array.

You now have the option, since you used an array implentation, to either traverse the tree, or start at the end of the array...

/*
currentNode = root
leafIndex = -1

while the current node exists
if the current node is an internal node
check its children to see which would contain the camera
if child could contain camera, current node = child
else current node = 0
else if the current node is a leaf node
find camera
if leaf node contains camera
leafIndex = camera index


return leafIndex
*/





[edit] that non recursive version doesnt exactly work but hopefully you get the idea

I dont know how you designed the bsp tree but an internal node, IMO, would be differentiated from a leaf node by checking the size of whatever structure is used to hold the points.

BSPNode
{
leftchild, rightchild
vecPoints?
}

So if vecPoints were empty it would be an internal node...

Share this post


Link to post
Share on other sites
I am not constructing the tree, the tree is constructed and stored in the .bsp file by the bsp compile tool i'm using which is the q2 tool provided with half-life.

This is what the node struct straight from the HL SDK looks like w\ original comments:

// Nodes lump contains node structures
struct node
{
unsigned int plane_idx; // Index into planes lump
signed short children[2]; // If greater than 0, then indices into nodes; otherwise, bitwise inverse = indices into leaves
signed short mins[3], maxs[3]; // Bounding box
unsigned short firstface, numfaces; // Index and count into faces lump
};



Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!