Sign in to follow this  

Binary Space Partioning

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

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