# Octrees and BSP Problems

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

## Recommended Posts

Hey guys, I've been working on my Octree and BSP tree structures to perform collision detection. I get a tree built, but unfortunately, when I drop a ray into the tree, I end up looking at way too many polygons (in the BSP's case, I actually end up looking at more polygons than the model originally has). In the Octree's case, I end up looking at about half the polygons, which doesn't really seem like much of a speed increase. I've referenced a few books (specifically, 3D Game Engine Programming, Computational Geometry in C, and a few Premier Press books I have lying around) and a bunch of internet articles, and I haven't been able to fix this problem, so I was hoping I could get some insight here. Here are general details about my methods: For both structures, I don't split polygons. I simply duplicate triangles when appropriate. I figure this is fine, since I'm only using these for collision detection. For my BSP tree, I choose the splitting plane based around whichever plane has approximately an even number of polygons on both sides. I'm only working with triangles. No fancy geometry here. My Octree has a maximum depth of about 4, since much higher than that causes the time to calculate it to increase dramatically. Below are the relevant functions, first for Octree.
void OctTree::constructFromTriangleList(list<SmartPtr<Triangle> > &tlist, bool isRoot, int depth)
{
if (isRoot)
{
mBoundingBox = calculateBoundingBox(tlist);
}

list<SmartPtr<Triangle> > trianglesInThisBranch;

//Calculate the triangles located in this region
list<SmartPtr<Triangle> >::iterator tri = tlist.begin();
while (tri != tlist.end())
{
if (mBoundingBox.isTriangleWithin(**tri))
{
trianglesInThisBranch.push_back(*tri);
}

tri++;
}
//Determine if this region is a leaf based on the number of triangles inside it
mIsLeaf = false;
if (trianglesInThisBranch.size() <= NUM_TRIANGLES_PER_LEAF || depth >= MAXIMUM_DEPTH)
{
mIsLeaf = true;
tri = trianglesInThisBranch.begin();
while (tri != trianglesInThisBranch.end())
{
mTriangles.push_back(*tri);
tri++;
}
}
else
{
Vector min = mBoundingBox.getMin(),
max = mBoundingBox.getMax(),
center = mBoundingBox.getCenter();
for (int i = 0; i < 8; i++)
{
BoundingBox newBoundingBox;
switch (i)
{
case OT_HIGHLEFTFRONT:
newBoundingBox.setMin(Vector(min[0], center[1], center[2]));
newBoundingBox.setMax(Vector(center[0], max[1], max[2]));
break;
case OT_HIGHLEFTBACK:
newBoundingBox.setMin(Vector(min[0], center[1], min[2]));
newBoundingBox.setMax(Vector(center[0], max[1], center[2]));
break;
case OT_HIGHRIGHTFRONT:
newBoundingBox.setMin(Vector(center[0], center[1], center[2]));
newBoundingBox.setMax(Vector(max[0], max[1], max[2]));
break;
case OT_HIGHRIGHTBACK:
newBoundingBox.setMin(Vector(center[0], center[1], min[2]));
newBoundingBox.setMax(Vector(max[1], max[2], center[3]));
break;
case OT_LOWLEFTFRONT:
newBoundingBox.setMin(Vector(min[0], min[1], center[2]));
newBoundingBox.setMax(Vector(center[0], center[1], max[2]));
break;
case OT_LOWLEFTBACK:
newBoundingBox.setMin(Vector(min[0], min[1], min[2]));
newBoundingBox.setMax(Vector(center[0], center[1], center[2]));
break;
case OT_LOWRIGHTFRONT:
newBoundingBox.setMin(Vector(center[0], min[1], center[2]));
newBoundingBox.setMax(Vector(max[0], center[1], max[2]));
break;
case OT_LOWRIGHTBACK:
newBoundingBox.setMin(Vector(center[0], min[1], min[2]));
newBoundingBox.setMax(Vector(max[0], center[1], center[2]));
break;
}

mChildren[i] = new OctTree();
mChildren[i]->setBoundingBox(newBoundingBox);
mChildren[i]->constructFromTriangleList(trianglesInThisBranch, false, depth+1);
}
}
}


bool OctTree::rayIntersect(const Ray &ray, float &distance, float maxDistance)
{
float td;
if (!ray.intersectAABB(mBoundingBox, td))
{
return false;
}

if (mIsLeaf)
{
list<SmartPtr<Triangle> >::iterator tri = mTriangles.begin();
float minDistance = -1;
bool wasHit = false;
while (tri != mTriangles.end())
{
if (ray.intersectTriangle(**tri, distance, maxDistance))
{

wasHit = true;
if (minDistance < 0 || distance < minDistance)
{
minDistance = distance;
}
}
tri++;
}
cout << mTriangles.size() << endl;
distance = minDistance;
return wasHit;
}
else
{
float minDistance = -1;
bool wasHit = false;

for (int i = 0; i < 8; i++)
{
if (ray.intersectAABB(mChildren[i]->getBoundingBox(), td, maxDistance))
{
if (mChildren[i]->rayIntersect(ray, distance, maxDistance))
{
wasHit = true;
if (minDistance < 0 || distance < minDistance)
{
minDistance = distance;
}
}
}
}
distance = minDistance;
return wasHit;
}
}


And now for the BSP Tree
void BSPTree::constructFromTriangleList(list<SmartPtr<Triangle> > &tlist)
{
mIsLeaf = false;

list<SmartPtr<Triangle> >::iterator tri = findBestSplitter(tlist);
//findBestSplitter returns the end of the list if no appropriate splitter is found.  If this happens,
//we're at a leaf node
if (tri == tlist.end())
{
mIsLeaf = true;

//Copy the geometry in to the leaf
list<SmartPtr<Triangle> >::iterator i = tlist.begin();
while (i != tlist.end())
{
mTriangles.push_back(*i);
i++;
}
cout << mTriangles.size() << endl;
return;
}

//If this isn't a leaf node and we did find a splitter...

mSplitter = Plane( (**tri)[0], (**tri)[1], (**tri)[2] );
list<SmartPtr<Triangle> > front, back;

tri = tlist.begin();
while (tri != tlist.end())
{
Classification c = mSplitter.classifyTriangle(**tri);
if (c == BEHIND || c == SPANNING)
{
back.push_back(*tri);
}
if (c == INFRONT || c == SPANNING)
{
front.push_back(*tri);
}
if (c == COINCIDING)
{
front.push_back(*tri);
}

tri++;
}

mFront = new BSPTree(front);
mBack = new BSPTree(back);
}


bool BSPTree::rayIntersect(const Ray &ray, float &d, float maxDistance)
{
if (mIsLeaf)
{
vector<float> distances;
for (int i = 0; i < mTriangles.size(); i++)
{
if (ray.intersectTriangle(*mTriangles[i], d, maxDistance))
{
distances.push_back(d);
}
}

if (distances.size() == 0)
{
return false;
}

d = *min(distances.begin(), distances.end());

return true;
}
else
{
SmartPtr<BSPTree> n, f;
if (mSplitter.classifyPoint(ray.getOrigin()) == BEHIND)
{
n = mBack;
f = mFront;
}
else
{
n = mFront;
f = mBack;
}
bool hit = n->rayIntersect(ray, d, maxDistance);
float pd;
if (!hit && ray.intersectPlane(mSplitter, pd, maxDistance))
{
hit = f->rayIntersect(ray, d, maxDistance);
}
return hit;
}

}


Any help would be greatly appreciated. Cheers, --Brian Note: I realize I have a post similar to this in the Math & Physics section. Since then, my BSP Tree has been working a little better, but still not satisfactory. Also, it didn't have anything for Octrees.

##### Share on other sites
i didnt look at it too long, but in the BSP tree your mIsLeaf variable gets set to true up in the leaf creation process... and that global member variable never gets set to false again that i saw... which means when it comes back around it searches triangles only on one leaf? will look more later if i have the time. in the meanwhile, seeing the output on number of tris, split planes, # of splitplanes, etc, might help.

##### Share on other sites
sorry about my previous post. ignore that. i was looking at your implementation wrong. each "BSPTree" object is actually a node on the tree and keeps track of its "leafiness". fair enough.

first off, there are non-recursive ways to run a BSP tree. as long as your tree depth doesnt get too big going thru the bother of doing it this way wont save you much, but if you get a deep tree (and probably the same problem with the "slow down" you see in the oct-tree) the call-stack for the function will slow you down WAY more than anything else. if nothing else, make sure your recursives are all "inline"d, "const"ed, and whatever else you need to make your compiler like them better.

second, as far as i can see, the only reason your BSP tree should be hitting more nodes is because it is splitting (duplicating) too much. this occurs very often if you use a mid-way splitting plane. basically, your BSP tree is very well balanced meaning any search on any leaf is going to be about the same time as any other leaf... but it is far from optmised. as an exampe: a search on any node will take between 60-62 poly checks. where a "more optimised" tree might get you a range of 20-70 poly checks. on the low end the "more optimised" looks worse... but on average it will perform much much quicker... here is a nice .pdf that goes at least a little more in depth about that kind of thing: [url]http://www.angelcode.com/refdb/resource.asp?id=500[/url]

third, as mentioned before if you optimise your oct-tree some more you should see better performance at higher depths. an oct-tree of depth 4 gives you 16x16x16 (4096) possible end cubes. most scenes i have been working with lately have around 100K triangles in them which would be (VERY optimally) 25 triangles PER cube... much too many to search thru if you have to go several depths in. i run at depth 6 for most of my scenes. however, this probably isnt the root of that problem. you shouldnt be hitting 1/2 the polys.

my only other guess here is it may be something to do with the scene you are using. scenes with large 2d parallel polys (many polys whos intersections with each other form parallel lines) complementing small highly complex random objects have a great tendancy to screw up oct-trees. an example would be a 80K poly teapot sitting on one end of a hallway with picture hangings... where the large picture hanging and walls all end up parallel to each other. basically you will end up counting those large wall polys over and over and over as you raytrace your way to the teapot. so, some more heuristics on what is actually counting poorly, and some sample of what the scene file is doing would be really beneficial. particularly how many spanning polys you end up with... i couldnt see anything glaringly bad about the code per se to cause the effect you are describing.

btw you might want to pull
float minDistance = -1;bool wasHit = false;

out of the "if" statements in your oct-tree check...

##### Share on other sites
wow... i cant leave this alone for some reason. i guess i love tree algs too much.

you are doing a double bounding box check in your oct tree check. notice the
if (!ray.intersectAABB(mBoundingBox, td))
at the beginning and the
if (ray.intersectAABB(mChildren[i]->getBoundingBox(), td, maxDistance))
before the recursive call.

further, you have no short circuit if there are 0 polys in a cube. throwing a check for that before all else can help you dump out of the code much quicker (doing it before even calling the recursive would be even better).

and the big winner: you are checking EVERY cube in the oct tree that the ray crosses. meaning optimally (a straight ray) you will end up checking 16 (leaf) cubes worth of stuff. worst case (a diagonal ray) you will end up checking ~2000 cubes (and pretty much "visiting" another 1000 besides). so a typical ray could hit in order of 1000 cubes of the 4000 and basically counting your dupe tris and the ones wholly enclosed that racks up your 1/2 polys visited right there. and the overhead of creating/traversing the oct tree pretty much makes the whole thing an exercise in futility.

the trick you are missing: check the closest cube first, then check the next closest along your ray... this way your ray will travel till it hits a surface and short circuit exits the program. basically, keep track of the point where the ray intersects the top node. then follow that point all the way down to your leaf cube (or until it determines the node it is following is empty). when you either hit a leaf cube or an empty cube, do the edge check, then follow the ray to its exit point on that cube, making it the new starting point. repeat algorithm till max_length is hit or you find a surface (or you run out the other side of the bounding box). this should reduce your search by a ton (since the whole point of an oct-tree and a bsp-tree is to be able to use a painter-algorithm approach to finding the nearest polygon).

##### Share on other sites
cheez_keeper: A big thanks.

My BSPTree problems stemmed from using a very poor model. I was using something practically convex, and obviously you can't find a good splitting plane in that scenario. When I made a realistic test level, I was getting *much* better results. Also, my choice of the splitting plane was bad, and once fixed, the results improved further.

You were right about the Octree not 'short circuiting.' For some reason I had it in my head that doing that would not guarantee returning the minimum distance. After thinking it through further, I realized how daft that was. I've since fixed that and am getting much better results.

Now I have another question:
What's a realistic way to do decent entity collision detection with this? My initial idea was to shoot a ray representing the entity's velocity and check that, but I realized that this method would let me pass through a lot of geometry I shouldn't. So my next idea was to project a ray on both ends of my entity's bounding sphere, but of course you can still make it through poly's protruding out of a wall that are thinner than the entity. As I deconstructed these ideas, I realized that to get really accurate collision, I either had to:
A) Send a lot of rays. Not particularly ideal.
B) Restrict the level design. A possibility, but still not perfect.
Is there a better solution that I'm not seeing?

Cheers,
--Brian