Sign in to follow this  
ErnieDingo

Question: Automated minimal bounding box Decomposition

Recommended Posts

ErnieDingo    606

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

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