Jump to content
  • Advertisement
Sign in to follow this  
ErnieDingo

Question: Automated minimal bounding box Decomposition

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

Just thinking through this as I have a need in my own project to automatically generate bounding boxes (and I mean boxes) to accurately enclose complex static models.  I've been doing some digging, minimum singular bounding boxes to contain a single hull, but what about multiple bounding boxes to contain a singular hull?

I do this as I am looking to enhance 2nd level grained collision detection in my game, I would like to break my current bounding box into multiple, eliminating the majority of empty space and localising the collision.   I'm not looking for something a super accurate, as I believe that's my final test post this phase.

Steps on collision detection:

1 - Establish what objects are in the region that potentially could be hit.

2 - Eliminate items with bounding sphere tests

3 - Model AABB bounding box test in the models local space.

4 - Less coarse AABB test - the ask here.

5 - Triangle/face collision test.

Example: Battleship, the bottom half of the bounding box is hull, so not much wasted space, but the top half, well it has a conning tower and various bits of super structure.  Therefore, smaller bounding boxes to establish a more accurate bounding volume.

My thoughts:

- If this ends up I have to do the boxes by hand then so be it.  But looking to you guys to know if I'm barking up the right tree.

- I dont think this will be truly be completely automated, I think I will need to assist with either some markers/indicators to the algorithm 

- Thinking of using a algorithm similar to the old days of a sprite cutter, Ie. Scan along one axis, until there is a break, then scan in another axis.  But this is a very naive scan. 

- This is only a small part of my development, I really don't have months to burn on this alone.  So hand crafting in a time vs effort is definitely in play.

References - I've found so far.

http://www.nada.kth.se/~danik/Papers/icra08.pdf 

- http://clb.demon.fi/projects/an-exact-algorithm-for-finding-minimum-oriented-bounding-boxes

 

Comments, your thoughts would be greatly appreciated.

Share this post


Link to post
Share on other sites
Advertisement
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!