# BSP Collision Problems

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

## Recommended Posts

Hi, I'm working on implementing a leafy BSP tree for detecting collisions in an FPS. I (think I) have built the BSP appropriately, but when I go to do ray based collision against it, I end up checking against practically every polygon (sometimes more, since polygons spanning the splitting plane are duplicated on the front and back lists when building the tree). I have referenced numerous books/internet articles to try and get this working, but I'm just not having any luck. Help would be greatly appreciated. Posted below is my code for generating the tree and for doing collision.
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++;
}
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 = classifyTriangle(mSplitter, **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);
}


if (mIsLeaf)
{
vector<float> distances;
cout << mTriangles.size() << endl;
for (int i = 0; i < mTriangles.size(); i++)
{
if (ray.intersectTriangle(*mTriangles, d))
{
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);
float pd;
if (!hit && ray.intersectPlane(mSplitter, pd))
{
hit = f->rayIntersect(ray, d);
}
return hit;
}

}



1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 14
• 12
• 9
• 12
• 37
• ### Forum Statistics

• Total Topics
631434
• Total Posts
3000048
×