0
\$\begingroup\$

The following code is a current attempt at a function I have to determine if two bounding boxes overlap. The bounding box structures are [min[x,y,z], max[x,y,z]] The following .gif shows the current undesired behavior.

aabbOverlap(otherWorldAABB){
  // copied from
  // http://blog.meltinglogic.com/2015/04/aabb-overlapping-area/
  // Vector3 min = Vector3(max(min1.x, min2.x), max(min1.y, min2.y), max(min1.z, min2.z));
  // Vector3 max = Vector3(min(max1.x, max2.x), min(max1.y, max2.y), min(max1.z, max2.z))

  return [
    [
      Math.max(this.worldAABB[0][0], otherWorldAABB[0][0]),
      Math.max(this.worldAABB[0][1], otherWorldAABB[0][1]),
      Math.max(this.worldAABB[0][2], otherWorldAABB[0][2]),
    ],

    [
      Math.min(this.worldAABB[1][0], otherWorldAABB[1][0]),
      Math.min(this.worldAABB[1][1], otherWorldAABB[1][1]),
      Math.min(this.worldAABB[1][2], otherWorldAABB[1][2]),
    ]
  ]
}

The gif has a render of the two entities bounding boxes the house and robot they are rendered in pink and then green when they overlap. Then I try to render the verts and the volume for the overlap section in White. You can see in the gif that some of the verts are way off from what you would expect and the volume gets skewed

Overlap example gif

Why I need this

I am using the AABB collision as the broad phase of my detection test. I want to calculate the overlap to restrict the narrow phase algorithim to within that overlap space. The narrow phase pass i'm using is a swept-sphere-to-triangle detection. I want to limit the mount of triangles scanned to within the overlap.

\$\endgroup\$
  • 1
    \$\begingroup\$ Are you taking into account that the AABB could be rotated? If that's the case you need to recalculate the world-space AABB from the rotated AABB (oriented bounding box), and then use that for overlap test. \$\endgroup\$ – Steven Jan 8 at 17:15
  • 1
    \$\begingroup\$ Your gif seems to show an OBB, not an AABB. Attempting to treat an OBB as an AABB seems to be the root of your issue. \$\endgroup\$ – DMGregory Jun 6 at 19:32
1
\$\begingroup\$

The first point to note, is that an axis aligned bounding box(AABB) is a special case of the Orientated Bounding box(OBB), thus, it is possible to treat AABB as OBB.

Secondly, you will need a robust and reliable narrow phase collision detection algorithm. I recommend starting with Separating Axis Theorem, or SAT for short. It's fast-ish, and easy to understand.

The basic idea is this:

Each box has 3 positive axes, or face normals if you like. The other 3 for each box can be ignored, as they are mirrors of the first 3. Think of these as the boxes local X, Y and Z axes. But you need another 9 axes to test for accuracy. You get these by producing a cross product of each axis from box A, and each axis of box B:

vec3 tempAxes[15];
tempAxes[0] = boxA.getlocalAxes()[0];
tempAxes[1] = boxA.getlocalAxes()[1];
tempAxes[2] = boxA.getlocalAxes()[2];
tempAxes[3] = boxB.getlocalAxes()[0];
tempAxes[4] = boxB.getlocalAxes()[1];
tempAxes[5] = boxB.getlocalAxes()[2];
vec3 axesA[3] = boxA.getlocalAxes();
vec3 axesB[3] = boxB.getlocalAxes();


var i;
var index = 6;
for (i = 0; i < 3; i++)
{
    var j;
    for (j = 0; j < 3; j++)
    {
        tempAxes[index] = cross(axesA[i], axesB[j]);
        index++;
    }
}

Now that you have generated all your axes to test on, you need to project all the corners of each box onto each axis, one axis at a time, and get the min and max values.

Using these values, we can say that if maxA < minB, or maxB < minA then you have an axis of separation and thus, they are not colliding.

var axis;
for ( axis = 0; axis < 15; axis++)
{
     if (tempAxes[axis] !=== tempAxes[axis])
         continue; //handles degenerate axes: just skip them
     pair A = project(tempAxes[i], boxA); //implementation dependent
     pair B = project(tempAxes[i], boxB); //implementation dependent
     if ( A[1] < B[0] || B[1] < A[0] )
          return false;
}

return true;

If you reach the end of the function, then no axis of separation is detected, and thus you have a positive collision.

To compute your projections, you just need to get the dot product of the axis, and each corner of your box. You then compare it to the current minimum and maximum values for the box, and replace if current is < min or current > max.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ This response is not answering the OBB/AABB overlap question and is off topic explanation of SAT near-phase collision. I already have a near-phase collision detection system that uses swept-sphere-triangle collision. I am looking for this Bounding box overlap to limit the amount of triangles that get passed to the swept-sphere-triangle near phase as it can be expensive. \$\endgroup\$ – kevzettler Jan 8 at 15:41
  • 1
    \$\begingroup\$ Your title is unclear if you think this is off topic. The effective way of testing overlap of AABB and an OBB is using SAT. If you are trying to accelerate your broadphase then you want to use AABB against AABB, which is a very cheap overlap test at the cost of less exact bounds. You can't have both. That is why most collision libraries use AABBs for their broadphase and a costlier, geometry-specific, tighter representation for narrow phase. If you only care about AABB v AABB, then you should change the title. \$\endgroup\$ – Steven Jan 8 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.