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 = new OctTree();
mChildren->setBoundingBox(newBoundingBox);
mChildren->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->getBoundingBox(), td, maxDistance))
{
if (mChildren->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, 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.
