Sign in to follow this  

Question: Automated minimal bounding box Decomposition

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. 



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