Sign in to follow this  
Nairb

BSP Collision Problems

Recommended Posts

Nairb    766
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[i], 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;	
	}
		
}

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this