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.
BSP Tree traversal
Author
Yes I was thinking that actually, made that change just now.
But really thats not the problem, i'm sitting well inside these leafs.
But really thats not the problem, i'm sitting well inside these leafs.
Author
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...]
[Edit: I just created a new test file that will be sure to have several different well defined leaves. Testing it now...]
Author
Ok, my old test data WAS flawed.
The new test data produces a MUCH cleaner BSP tree:
With Geometry off:
With Geometry on:
Inside Geometry:
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:
The new test data produces a MUCH cleaner BSP tree:
With Geometry off:
With Geometry on:
Inside Geometry:
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?
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.
Author
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:
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:
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:
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:
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:
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]
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- 30numFaces: 49numEdges: 126numVerts: 78numLeafs: 6numNodes: 22Node # Info-+-+-+- -+-+-+-+-+-Node 0 numFaces 3 children[0]: 1children[1]: -1min: -6 -1 2max: 5 1 -9 Node 1 numFaces 3 children[0]: 2children[1]: 6min: -6 -1 2max: 5 1 -9 Node 2 numFaces 1 children[0]: -1children[1]: 3min: -6 -1 -7max: 5 1 -9 Node 3 numFaces 4 children[0]: -1children[1]: 4min: -6 -1 -7max: 4 1 -9 Node 4 numFaces 4 children[0]: 5children[1]: -1min: -6 -1 -7max: 4 1 -9 Node 5 numFaces 4 children[0]: -1children[1]: -2min: -6 0 -7max: 4 1 -9 Node 6 numFaces 3 children[0]: 7children[1]: -1min: -6 -1 2max: 5 1 -7 Node 7 numFaces 2 children[0]: 8children[1]: 20min: -6 -1 2max: 5 1 -7 Node 8 numFaces 1 children[0]: -1children[1]: 9min: -4 -1 2max: 5 1 -5 Node 9 numFaces 2 children[0]: 10children[1]: 17min: -4 -1 2max: 4 1 -5 Node 10 numFaces 1 children[0]: 11children[1]: 14min: 0 -1 2max: 4 1 -5 Node 11 numFaces 2 children[0]: -1children[1]: 12min: 0 -1 -3max: 4 1 -5 Node 12 numFaces 2 children[0]: 13children[1]: -1min: 0 -1 -3max: 4 1 -5 Node 13 numFaces 2 children[0]: -1children[1]: -3min: 0 0 -3max: 4 1 -5 Node 14 numFaces 2 children[0]: -1children[1]: 15min: 0 -1 2max: 2 1 -3 Node 15 numFaces 2 children[0]: -1children[1]: 16min: 0 -1 2max: 1 1 -3 Node 16 numFaces 2 children[0]: -4children[1]: -1min: 0 -1 2max: 1 1 -3 Node 17 numFaces 1 children[0]: -1children[1]: 18min: -4 -1 2max: 0 1 -1 Node 18 numFaces 1 children[0]: 19children[1]: -1min: -4 -1 2max: 0 1 0 Node 19 numFaces 1 children[0]: -1children[1]: -5min: -4 0 2max: 0 1 0 Node 20 numFaces 3 children[0]: 21children[1]: -1min: -6 -1 2max: -4 1 -7 Node 21 numFaces 3 children[0]: -1children[1]: -6min: -6 0 2max: -4 1 -7 Leaf 0 min: 0 0 0max: 0 0 0Leaf 1 min: -6 0 -7max: 4 1 -8Leaf 2 min: 0 0 -3max: 4 1 -4Leaf 3 min: 0 0 2max: 1 1 -3Leaf 4 min: -4 0 2max: 0 1 0Leaf 5 min: -6 0 2max: -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:
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]
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?
Author
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!
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]
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]
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
[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]
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]
Author
I'm writing a logging class to replace my inline reporting functions so I can track the recursive function.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement