Intersection between AABB and a capsule (swept sphere)

Question

I have an axis aligned bounding box in R3 space defined by minimum vector A and maximum vector B, and a capsule defined by a segment with end points a and b, and radius r. I would like to check if the two shapes intersect.

I know that the two shapes do in fact intersect if the capsule's defining segment intersects the AABB. However how do I handle the remaining case where the segment does not intersect the AABB, but the capsule still does.

Answer 1

Maybe you can try to thicken the cube by the radius of the capsule (basically, the box becomes a box with vertices replaced by spheres and you can think of the thickened box as spanned by these spheres) and replace the capsule by the line segment between the two centers of the sphere. The line segment intersects the thickened box exactly when the capsule intersects the original box.

Answer 2

If you only need to check whether the shapes intersected, and not where they intersected, you can reduce capsule-AABB intersection testing into capsule-capsule intersection testing.

• find closest point of both start and end point of capsule on AABB (effectively, clamp them to the AABB's bounds)
• if the two clamped points are equal, test capsule-point intersection with that point
  • same as capsule-sphere intersection with a sphere of radius 0
• if the two clamped points are different, test capsule-line segment intersection
  • same as capsule-capsule intersection, with the capsule formed by the line segment having a radius of 0

I've only tested this in 2D, but I think it should work in 3D too.

Answer 3

My approach is based on this answer and on the assumption that you consider a capsule that lies inside the AABB as an intersection. The idea is to extend the AABB by the radius of the capsule (Minkowski sum). This will give you a rectangle with rounded corners of radius r. Then, we check if the line segment defining the capsule intersects with that extended AABB.

1. Create an extended AABB with straight corners and check for intersections between the line segment and the AABB.
2. If the line segment lies within this AABB -> intersection.
3. If the line segment does not intersect within this AABB -> return false
4. If the line segment intersects with this AABB twice -> Check if both intersection points are in the same corner region of the extended AABB. -> If no, intersection. If yes -> check intersection between line segment and rounded corner (sphere).
5. If the line segment intersects with this AABB once -> Check if intersection point lies in a corner region of the extended AABB. If no -> intersection. If yes -> check intersection between line segment and rounded corner (sphere).

Here is a C++ implementation:

bool line_segment_aabb_intersection(const Point& p1, const Point& p2, const AABB& aabb, double& t1, double& t2) {
  // https://en.wikipedia.org/wiki/Liang%E2%80%93Barsky_algorithm
  double delta_x = p2.x - p1.x;
  double delta_y = p2.y - p1.y;
  double delta_z = p2.z - p1.z;
  std::vector<double> p = {-delta_x, delta_x, -delta_y, delta_y, -delta_z, delta_z};
  std::vector<double> q = {
    p1.x - aabb.min_[0],
    aabb.max_[0] - p1.x,
    p1.y - aabb.min_[1],
    aabb.max_[1] - p1.y,
    p1.z - aabb.min_[2],
    aabb.max_[2] - p1.z
  };
  t1 = 0.0;
  t2 = 1.0;
  for (int i=0; i<6; i++) {
    if (p[i] == 0) {
      if (q[i] < 0) {
        return false;
      }
    } else {
      double t = q[i]/p[i];
      if (p[i] < 0) {
        t1 = std::max(t1, t);
      } else {
        t2 = std::min(t2, t);
      }
    }
  }
  return t1 <= t2;
}

bool capsule_aabb_intersection(const Capsule& c, const AABB& aabb) {
  // Expand the AABB by the radius of the capsule
  AABB expanded_aabb = aabb;
  for (int i=0; i<3; i++) {
    expanded_aabb.min_[i] -= c.r_;
    expanded_aabb.max_[i] += c.r_;
  }
  // First check if the line segment intersects the expanded AABB
  double t1, t2;
  if (!line_segment_aabb_intersection(c.p1_, c.p2_, expanded_aabb, t1, t2)) {
    return false;
  }
  // Check if the intersection occurs in one of the rounded corners.
  if (t1 > 0 && t2 < 1) {
    // Check where the intersection occurs
    Point p1 = c.p1_ + (c.p2_ - c.p1_) * t1;
    Point p2 = c.p1_ + (c.p2_ - c.p1_) * t2;
    // Both points must lie outside the original AABB in the same direction
    Point potential_corner;
    // Dimension x
    if (!(p1.x < aabb.min_[0] && p2.x < aabb.min_[0] ||
        p1.x > aabb.max_[0] && p2.x > aabb.max_[0])) {
      return true;
    } else {
      if (p1.x < aabb.min_[0]) {
        potential_corner.x = aabb.min_[0];
      } else {
        potential_corner.x = aabb.max_[0];
      }
    }
    // Dimension y
    if (!(p1.y < aabb.min_[1] && p2.y < aabb.min_[1] ||
        p1.y > aabb.max_[1] && p2.y > aabb.max_[1])) {
      return true;
    } else {
      if (p1.y < aabb.min_[1]) {
        potential_corner.y = aabb.min_[1];
      } else {
        potential_corner.y = aabb.max_[1];
      }
    }
    // Dimension z
    if (!(p1.z < aabb.min_[2] && p2.z < aabb.min_[2] ||
        p1.z > aabb.max_[2] && p2.z > aabb.max_[2])) {
      return true;
    } else {
      if (p1.z < aabb.min_[2]) {
        potential_corner.z = aabb.min_[2];
      } else {
        potential_corner.z = aabb.max_[2];
      }
    }
    // Both points lie in the same corner.
    // Check if the corner of the original AABB is inside the capsule
    double dist = point_line_segment_dist(potential_corner, c);
    return dist < c.r_;
  } else if (t1 > 0 && t2 >= 1 || t1 <= 0 && t2 < 1) {
    Point p1;
    if (t1 > 0 && t2 >= 1) {
      p1 = c.p1_ + (c.p2_ - c.p1_) * t1;
    } else {
      p1 = c.p1_ + (c.p2_ - c.p1_) * t2;
    }
    // Check if the point is inside a corner
    Point potential_corner;
    // Dimension x
    if (p1.x > aabb.min_[0] && p1.x < aabb.max_[0]) {
      // Point does not lie in a corner
      return true;
    } else {
      if (p1.x < aabb.min_[0]) {
        potential_corner.x = aabb.min_[0];
      } else {
        potential_corner.x = aabb.max_[0];
      }
    }
    // Dimension y
    if (p1.y > aabb.min_[1] && p1.y < aabb.max_[1]) {
      // Point does not lie in a corner
      return true;
    } else {
      if (p1.y < aabb.min_[1]) {
        potential_corner.y = aabb.min_[1];
      } else {
        potential_corner.y = aabb.max_[1];
      }
    }
    // Dimension z
    if (p1.z > aabb.min_[2] && p1.z < aabb.max_[2]) {
      // Point does not lie in a corner
      return true;
    } else {
      if (p1.z < aabb.min_[2]) {
        potential_corner.z = aabb.min_[2];
      } else {
        potential_corner.z = aabb.max_[2];
      }
    }
    // Point lies in a corner
    // Check if the corner of the original AABB is inside the capsule
    double dist = point_line_segment_dist(potential_corner, c);
    return dist < c.r_;
  } else {
    // Line segment inside AABB
    return true;
  }
}