Jump to content
  • Advertisement
Sign in to follow this  

Binary Space Partioning

This topic is 3504 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

So I was thinking of using this for collision detection. Anyone know where would be a good place to check out? Lot's of the examples online are too confusing for me or don't implement collision detection. Also I was wondering how I would construct the tree from a set of polygons, say a model. Wouuld I have to get the plane equation of all the poly's ? Thanks all. :)

Share this post

Link to post
Share on other sites
If you haven't written collision detection before I'd probably steer clear of a true BSP (there are quite a number of corner case issues, floating point accuracy etc..)

Probably best if you look at a KDTree (Axis aligned BSP) with no splitting.

Simple implementation:
1. For each group of triangles find the axis aligned bounding box
2. Find the longest edge
3. Make a split half way along
4. For each triangle, if all vertices are left of the split put into child group1, if all vertices are right of the split put in child group2, else add to group for this split
5. Recurse child groups 1 & 2 until below a certain number of triangles, say 25.

Now to perform collision, for each node
1. Test collision query against triangles which did not fit into either child group
2. If query spans left of split, recurse left child
3. If query spans right of split, recurse right child

Share this post

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

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!