Sign in to follow this  

Polygon Soup Collision Detection BSP Tree Construction Help

Recommended Posts

Hello,

 

So I have decided to use a bsp tree for optimizing the collision detection system with a static collision mesh for a level. The collision mesh is just a polygon soup. I now have to some how construct the tree, which I have an idea on how to do using a pre-processing stage. My question, is there any common ways on how a static collision mesh would be partitioned? That is, how a polygon soup would be partitioned. Any algorithms or useful math for such a problem? My goal is to partition the polygon soup into sectors of a triangle limit. When a dynamic object (such as player) is at a certain position, that position will determine what triangles it should test against for collisions.

 

Thanks.

Share this post


Link to post
Share on other sites
BSP tree as in plane division? Are you just storing dividing planes for each triangle? In that case there's probably not a great way to pick which dividing planes to use first. Maybe just find a plane that roughly cuts the space in half, at each subdivision. In my own stuff I would just throw all the triangles together and construct an AABB tree. I used really simple algorithm from game programing gems books, it worked well enough. Just use an easy to implement algorithm and test it out to see if it works. Try also looking up Ericson's orange book on Real-Time Collision Detection. Edited by Randy Gaul

Share this post


Link to post
Share on other sites

The goal is to take the triangles and separate them into groups. So if I had a collision mesh for a map with say 1000 triangles, I would like to partition these triangles with a plane a certain amount of times, BSP tree that is, and hopefully end up with a tree were each end node had a certain amount of these triangles, say 20. That way I would only need to check for collisions with those 20 triangles depending on the players position on the map. I'm going to try my first idea which is similar to a solution in Ericson's orange book. Use each triangles face as a plane and then find which plane had the best symmetrical cut and also least amount of triangle intersections, so I don't have to divide triangles in half. It's a tricky problem to get a perfect solution, best you could probably do is a close enough solution.

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