• Advertisement
Sign in to follow this  

BSP Collision Problems

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

If you intended to correct an error in the post then please contact us.

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;	
	}
		
}

Share this post


Link to post
Share on other sites
Advertisement
Sign in to follow this  

  • Advertisement