• Advertisement
Sign in to follow this  

BSP Tree traversal

This topic is 4247 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
Well the tree is constructed when the BSP file is compiled, I simply read the nodes & leafs in from the file.

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
I would be willing to bet that the way they implemented the bsp tree you are traversing that it includes the min bounds, but is less than (not less than and equal to) the max bound when it assigns bounds to each node.

I remember doing my kdtree and doing this because you dont want two bounding boxes to include the edge where they meet, only one of them gets that border or plane in your case.

[edit] this would only affect points directly on those planes. I think I understand what they are doing now. Ill post something in a few when I get it together.

Share this post


Link to post
Share on other sites
Yes I was thinking that actually, made that change just now.

But really thats not the problem, i'm sitting well inside these leafs.

Share this post


Link to post
Share on other sites
Thank you so much for the helpfullness and responsfullness by the way!

[Edit: I just created a new test file that will be sure to have several different well defined leaves. Testing it now...]

Share this post


Link to post
Share on other sites
Ok, my old test data WAS flawed.

The new test data produces a MUCH cleaner BSP tree:

With Geometry off:
Geo Off

With Geometry on:
Geo ON

Inside Geometry:
Geo ON

Interesting to note how the bounding boxes are placed in teh hallways. They evne purtrude out of the geometry a bit...

Also note how there is a section of hallway where the leaf is 2D and doesnt cover it at all, if you were standing there you would not be in a leaf, how the ef would that work?

[EDIT]
This is something I wrote to describe to someone my understanding of how to render a BSP file, thought it might help you to see if there is a flaw in my core logic:

Quote:

This is my current understanding of BSP Trees and .bsp file rendering, please correct me where I am wrong:

Using the location of the camera, you start at the root node of the BSP tree, which is the first element in the 'nodes' chunk of the BSP file. You test your location against the bounding box defined by the 'min' and 'max' vertices in the nodes children.

Normally this would be used to solve the painter's problem of drawing the closest geometry first, but with OpenGLs depth testing function this is rather unnecessary, but it is my understanding you can still use the BSP tree to locate the leaf in which the camera resides.

With this you can find your PVS (Potentially Visible Set) which will contain all the geometry you need to draw for your current location.


Does that sounds right?

Share this post


Link to post
Share on other sites
leafIndex = node->children*-1;

I agree with what you wrote for your traverse function except I would have subtracted 1 in the line above before assigning it to leafIndex. Dont know if there was a specific reason as to why you had it like that.

Quote:
This is my current understanding of BSP Trees and .bsp file rendering, please correct me where I am wrong:

Using the location of the camera, you start at the root node of the BSP tree, which is the first element in the 'nodes' chunk of the BSP file. You test your location against the bounding box defined by the 'min' and 'max' vertices in the nodes children.

Normally this would be used to solve the painter's problem of drawing the closest geometry first, but with OpenGLs depth testing function this is rather unnecessary, but it is my understanding you can still use the BSP tree to locate the leaf in which the camera resides.

With this you can find your PVS (Potentially Visible Set) which will contain all the geometry you need to draw for your current location.


Does that sounds right?


Yes that sounds right with one exception. You go straight to testing the children's bound boxes before their parents. Although theres technically nothing wrong you could potentially do extra comparisons not needed. For example, what if your root really didnt contain the point you are looking for? Then you would have checked both children for nothing.

Another question that pops into my head is how did they decided where to place the dividing plane in constructing the BSP tree.

Regardless it is odd that you have 2D bounding planes... as you said if ur not on that 2D plane the point wouldnt even be in the bsp tree at all.

They seem to have a very weirdly implemented BSP tree. The only way I can think of where you would get a 2D plane is if you tried to divide a 3D area that was already far too small to be divided again.

Are there any links to online documentation you could point me towards? Maybe that will give me more ideas.

Share this post


Link to post
Share on other sites
Well looks like you were exactly right about the area being too small, I expanded the hallway and the bounding box expanded to a reasonable 3D size:
expanded geometry

There just isn't too much documentation out there on this version of the BSP file format sadly. Most info I got from looking @ the source in the SDK, and from people on forums here and there, I still don't have a complete idea of it because there are many different versions of the format (this one is v30) and a lot of what you find on the net is the wrong version.

This is the closest resource I can find, but it is for version 38.
Flip Code Q2 Tutorial

Moving on:
This seems to be a common thing, and I'm pretty DAMN sure that the test data is correct now, so this is strange, the root node almost always seems to have 1 leaf and 1 node as childeren, also it seems that the node child always has exactly the same bounding box as the root node it's self:
Quote:

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


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


In this case the right child is leaf 1, which if we are going w\ our math of:
leafIndex = (leafIndex * -1) - 1;
that means it corresponds to leaf 0:
Quote:

Leaf 0
min: 0 0 0
max: 0 0 0


Mmmmmm aint that helpfull lol...

All the other leaves seem to be perfectly valid and happy. It's just those first two stupid childeren that seem to be efed up...

Also, if the camera were to be outside any leaf, what the hell would you render?

This is the full list of nodes and leaves:

//==================================
// Black Engine: -= 3dpoints.txt =-
//
// Description:
// ---------------
// This textfile was created by
// traversing
// [BSPFile] <nodes[]> <leafs[]>
// in BSPManager.cpp
//
// [.bsp used]: "maps/q2/curTest.bsp"
//==================================

Header: version- 30

numFaces: 49
numEdges: 126
numVerts: 78
numLeafs: 6
numNodes: 22

Node # Info
-+-+-+- -+-+-+-+-+-


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


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


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


Node 3 numFaces 4
children[0]: -1
children[1]: 4
min: -6 -1 -7
max: 4 1 -9


Node 4 numFaces 4
children[0]: 5
children[1]: -1
min: -6 -1 -7
max: 4 1 -9


Node 5 numFaces 4
children[0]: -1
children[1]: -2
min: -6 0 -7
max: 4 1 -9


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


Node 7 numFaces 2
children[0]: 8
children[1]: 20
min: -6 -1 2
max: 5 1 -7


Node 8 numFaces 1
children[0]: -1
children[1]: 9
min: -4 -1 2
max: 5 1 -5


Node 9 numFaces 2
children[0]: 10
children[1]: 17
min: -4 -1 2
max: 4 1 -5


Node 10 numFaces 1
children[0]: 11
children[1]: 14
min: 0 -1 2
max: 4 1 -5


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


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


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


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


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


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


Node 17 numFaces 1
children[0]: -1
children[1]: 18
min: -4 -1 2
max: 0 1 -1


Node 18 numFaces 1
children[0]: 19
children[1]: -1
min: -4 -1 2
max: 0 1 0


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


Node 20 numFaces 3
children[0]: 21
children[1]: -1
min: -6 -1 2
max: -4 1 -7


Node 21 numFaces 3
children[0]: -1
children[1]: -6
min: -6 0 2
max: -4 1 -7


Leaf 0
min: 0 0 0
max: 0 0 0

Leaf 1
min: -6 0 -7
max: 4 1 -8

Leaf 2
min: 0 0 -3
max: 4 1 -4

Leaf 3
min: 0 0 2
max: 1 1 -3

Leaf 4
min: -4 0 2
max: 0 1 0

Leaf 5
min: -6 0 2
max: -4 1 -7

-+-+-+-+ -+-+-+-+-+-










Which now looking at closer, I notice that every 2 nodes have exactly the same bounding box. As in Node 0 and 1, 2 and 3, ect. Very strange.

Also i now have the bounding boxes from the nodes drawing:
Nodes
Not nearly as compact or clean, theres 22 nodes for 6 leaves.

And here is another resource I found, again not sure on the version it's for:
Quake Specs

[Edited by - Wavesonics on June 28, 2006 10:48:09 PM]

Share this post


Link to post
Share on other sites
Did that list come out of the traverse function or did you just go ahead and dump the data from the node and leaf arrays?

Share this post


Link to post
Share on other sites
AAHHHHHH!!!!!

BRAIN FART!!!!

I need to check if the cam is BETWEEN the max and min, not just less than or greater than!

This is the code that seems to do it!

// See if we are in the current nodes bounding box
if((curNode->maxs[0] < pos.x && pos.x < curNode->mins[0]) || (curNode->maxs[0] > pos.x && pos.x > curNode->mins[0]))
if((curNode->maxs[1] < pos.y && pos.y < curNode->mins[1]) || (curNode->maxs[1] > pos.y && pos.y > curNode->mins[1]))
if((curNode->maxs[2] < pos.z && pos.z < curNode->mins[2]) || (curNode->maxs[2] > pos.z && pos.z > curNode->mins[2]))
{
leafIndex = traverseBSPNode(pos, curNode);
}





The cam @ 0,0,0 SHOULD be inside the root node's bounding box, and w\ this check it passes, but in the end the function still returns -1, and my logging to not rebust enuf to follow the resursive algorithm more then one level down, so I don't know how far it's going.

Oh well. Done enuf for today, time to sleep and tackle this tomorrow,
I'm close I can smell it ;)

[Edit: I just dumped the arrays to a flat file to generate that list]

Share this post


Link to post
Share on other sites
Ahh that makes sense.

So that means you can check to see if the sum of the distances from the point to each plane in a single dimesion is greater then the distance between the two planes in that given dimension.

For example

for each dimension i
see if (dist from pt.i to min.i) + (dist from pt.i to max.i-1) > (dist from min.i to max.i-1)
if it is, then the point is not contained by the bound...





[edit] forgot to subtract 1

Theres probably a more accurate way of doing that mathematically but I dont know it...

[Edited by - ju2wheels on June 29, 2006 1:48:19 PM]

Share this post


Link to post
Share on other sites
I'm writing a logging class to replace my inline reporting functions so I can track the recursive function.

Share this post


Link to post
Share on other sites
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() called



traverseBSPNode() called

Cur Pos: 0, 0, 0
New Node:
Child[0] 1
Child[1] -
=pass===
Child[1] -
Is Node
Max: 7, 4, 8
Min: 2, 2, 4
Traverse this node

traverseBSPNode() called

Cur Pos: 0, 0, 0
New Node:
Child[0] 2
Child[1] 6
=pass===
Child[1] 6
Is Node
Max: 7, 4, 8
Min: 2, 2, 4
=pass===
Child[1] 6
Is Node
Max: 7, 4, 8
Min: 2, 2, 4
Is Node
Max: 5, 1, 4
Min: 4, 4, 4
Traverse this node

traverseBSPNode() called

Cur Pos: 0, 0, 0
New Node:
Child[0] 7
Child[1] -
=pass===
Child[1] -
Is Node
Max: 7, 4, 8
Min: 2, 2, 4
Traverse this node

traverseBSPNode() called

Cur Pos: 0, 0, 0
New Node:
Child[0] 8
Child[1] 2
=pass===
Child[1] 2
Is Node
Max: 7, 4, 8
Min: 2, 2, 4
Traverse this node

traverseBSPNode() called

Cur Pos: 0, 0, 0
New Node:
Child[0] -
Child[1] 9
=pass===
Index to Leaf
Max: 0, 0, 0,
Min: 0, 0, 0,
=pass===
Index to Leaf
Max: 0, 0, 0,
Min: 0, 0, 0,
Is Node
Max: 7, 4, 8
Min: 2, 2, 4
Traverse this node

traverseBSPNode() called

Cur Pos: 0, 0, 0
New Node:
Child[0] 1
Child[1] 1
=pass===
Child[1] 1
Is Node
Max: 7, 4, 8
Min: 2, 2, 4
=pass===
Child[1] 1
Is Node
Max: 7, 4, 8
Min: 2, 2, 4
Is Node
Max: 4, 1, 4
Min: 0, 4, 2
--=end=======--


--=end=======--


=pass===
Child[1] 2
Is Node
Max: 7, 4, 8
Min: 2, 2, 4
Is Node
Max: 5, 1, 4
Min: 4, 4, 2
--=end=======--


=pass===
Index to Leaf
Max: 0, 0, 0,
Min: 0, 0, 0,
--=end=======--


--=end=======--


=pass===
Index to Leaf
Max: 0, 0, 0,
Min: 0, 0, 0,
--=end=======--


Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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]

Share this post


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

  • Advertisement