DEV Community

loading...

The Oriented Bounding Box Problem

the_wooden_h profile image Wooden H Studio ・2 min read

Recently at Wooden H Studio, we have been working on creating an entirely custom physics system for our up-and-coming game engine. Up until this point collision and resolution has been smooth sailing until we got to the dread Oriented Bounding Box, OBB for short.

The Problem

OBBs are similar to its other cubic brethren the AABB (Axis Aligned Bounding Box) as they are both boxes but, are different in every other way. For starters an OBB is not aligned to any axis, meaning it has 360 degrees of freedom whilst the AABB doesn’t rotate at all. So, this meant we couldn’t check for collision or resolution the same way as the AABB’s, so we had to come up with another solution.

The Separating Axis

In-game physics there is a theory that to determine if there is a collision between 2 objects there is a plane that separates the two objects, if there is then there is no collision, otherwise, the two objects collide. This is called the Separating Axis test and we used this test numerous times throughout our development to detect a collision, and even determine the resolution needed as well.

How does it work?

At first, I thought this same question, in fact, it took me a while to understand how to write it into code, but it is much simpler than it sounds. What we need to do is project the box onto a line that is parallel to the axis we want to test and determine the smallest and largest value per bounding box. Once we have each of the boxes projected onto this line all we need to do is check to see if either of the boxes smallest value was less than the other largest value. If these values overlap, then there is collision along this axis. But this isn’t always the case. Say two boxes are sitting flat on a plane, side by side and we wanted to check the axis perpendicular to the plane, we’ll use the vector {0,1,0}. If we project the boxes onto this axis technically there would be no gap between the 2 projects thus concluding there is a collision, even where there isn’t. The solution to this problem to continue doing this test using different axes until we find one that has a gap. Since there theoretically can be an infinite number of axes, we need to devise a plan to shrink that number to something more reasonable.

The solution for our dreaded OBB is to take the X, Y and Z axis of each bounding box and test them, after that the first box’s axes must be crossed with each axis of the second box’s axes. This results in the separating axis test being run 15 times at a minimum! While this might not seem great for computation the theory works and gives us very accurate collision detection and helped boost our thought process with the rest of the collision perils. This system works great especially for different object types like OBB to AABB and really helped boost our productivity after learning about this insane method.

By Gage Dietz

Discussion (0)

Forem Open with the Forem app