Jump to content
  • Advertisement
Sign in to follow this  
ajas95

AABB BVH creation

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

My goal is to write a space partitioning algorithm for static geometry. This isn't for rendering purposes (yet), but for collision detection purposes. I've chosen to use a BVH of AABBs where each node can have up to 8 child nodes. My question is if anyone knows of good algorithms for generating this type of partitioning. My instinct is that SAH can be used the same way as for k-d trees, and I've written a very nice, very fast SAH k-d tree compiler. However, how to apply that principle to choosing candidate child AABBs is far from obvious, the search space would be huge! My second thought was that maybe I should go bottom-up instead, treating each triangle as its own leaf, grouping those into 8's, then group those groups into 8's, until we arrive at a root node... However, the process of choosing those groups in a robust way is not very clear either. If anyone has ideas or links regarding this type of algorithm/heuristic, I'd be very interested.

Share this post


Link to post
Share on other sites
Advertisement
I do this for my level editor, although I think I just use one leaf per triangle ( inefficient, I know. ).

I use the SAH to split the tree.

Next, I group bottom up in groups of ~1000 triangles for rendering purposes.

For my game engine's collision detection, I use an octtree of AABB trees, using 4-8 tris per leaf, again using the SAH if possible, and median split if it fails to produce a split.

Share this post


Link to post
Share on other sites
Quote:
Original post by ajas95
My second thought was that maybe I should go bottom-up instead, treating each triangle as its own leaf, grouping those into 8's, then group those groups into 8's, until we arrive at a root node... However, the process of choosing those groups in a robust way is not very clear either. If anyone has ideas or links regarding this type of algorithm/heuristic, I'd be very interested.


I've gone with this approach and found it to work quite well, the trick is to allow your algorithm to use different metrics for grouping nodes. For example you could group the nearest nodes (ie minimize distance), group to minimize the volume of nodes, or group to minimize 'wasted space' (that is, the difference between the sum of the volume of the child nodes and the volume of the parent node). You can then select the metric which produces the best results for each geometry set.

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!