# Subdived objects in different shapes

Currently I'm working on an Android OpenGL 3D game and now I want to implement a collision detection. For this I want to use oriented bounding boxes but here is my problem. For a normal oriented bounding box I have to store the middle and then the length into every dimension. Now let's say I have a tree and of course my character can walk under the treetop but not into the tree trunk. I tried to sketch up the different bounding boxes here:

Tree as two rectangels                         Normal bounding box

-----------------------                   ------------------------------
|                     |                   |                            |
-----------------------                   |                            |
|     |                           |                            |
|     |                           |                            |
|     |                           |                            |
|     |                           |             x              |
|     |                           |                            |
|     |                           |                            |
|     |                           |                            |
|     |                           |                            |
|     |                           |                            |
-------                           ------------------------------


If you think about the collision detection in the first sketch you can walk under the treetop because the border of the tree is subdivided into different shapes and the outline of a tree is still visible. In the second picture you can't tell something about the outline of the object because you only have one big box around the whole object so you can't walk under the treetop. You see the first method is much better then the second method for my plan.

Now my question: Do you have any ideas how I can subdivide my objects into different shapes? Maybe even in triangles, circles and so on. Is there an algorithm for this or do I have to do it by myself?

• you might find this paper interesting. Mar 19, 2015 at 13:46
• Thank you for this really great paper. That was perfectly what I was looking for. But I can't find a date when it was published. 2 seconds for 300 points looks really expansive for me. Of course most of my objects only have around 50 points or something like that and the algorithm has to calculate many different cases but is 2 seconds not a bit long? Mar 20, 2015 at 14:08