# Polygon Soup Collision Detection BSP Tree Construction Help

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

## 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 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 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.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 28
• 16
• 10
• 10
• 11
• ### Forum Statistics

• Total Topics
634111
• Total Posts
3015577
×