AABB和胶囊体（扫描球）之间的相交。

Question

我有一个沿轴对齐的三维边界框，由最小向量A和最大向量B定义，并且有一个由线段端点a和b以及半径r定义的胶囊体。 我想检查这两种形状是否相交。

我知道如果胶囊体的定义线段与AABB相交，则这两个形状实际上会相交。但是，如果线段不与AABB相交但仍然与胶囊体相交，我该如何处理剩余情况呢？

- Lenny White

---

你能计算球体-AABB相交吗？胶囊的两端是半球体，在线段中心，距离a或b为r。需要更多信息吗？ - Ripi2

@Ripi2 但是仅在胶囊的末端检查球体-AABB相交是不够的。 胶囊具有沿其定义的整个线段扫过的球体。 - Lenny White

整个段落？我不明白。你能发一张图片吗？ - Ripi2

Answer 1

如果您只需要检查形状是否相交，而不需要知道它们相交的位置，您可以将胶囊-AABB相交测试简化为胶囊-胶囊相交测试。

• 找到胶囊起点和终点在AABB上的最近点（有效地将它们夹紧到AABB的边界）
• 如果两个夹紧点相等，则使用该点进行胶囊-点相交测试
  • 与半径为0的球体进行胶囊-球体相交测试
• 如果两个夹紧点不同，则进行胶囊-线段相交测试
  • 与半径为0的线段形成的胶囊进行胶囊-胶囊相交测试

我只在2D中测试过这个方法，但我认为它在3D中也适用。

- zneak

Answer 2

也许你可以尝试通过胶囊的半径来加厚立方体（基本上，盒子变成了一个由球取代顶点的盒子，你可以将加厚的盒子看作是由这些球张成的），并用两个球心之间的线段替换胶囊。当胶囊与原始盒子相交时，线段恰好与加厚的盒子相交。

- Futurologist

---

我认为你在描述分离轴定理？我刚刚研究了它作为可能的解决方案。但是，如果投影沿着所有轴重叠，我认为两个形状会相交？如果我错了，请有人纠正我。 - Lenny White

@LennyWhite 是的，那就是我想要写的，我想在写完后没有仔细阅读自己的帖子。我会进行更正。 - Futurologist

分离轴定理似乎对这种情况不起作用。如果你将这个问题简化为2D情况，你会发现如果它们在两个坐标轴上的投影相交，AABB和胶囊体不一定要相交。 - Lenny White

是的，我能看到。 - Futurologist

这很好用，直到你的胶囊坐在AABB的一个面上，周围没有顶点。 - X Builder

这是在描述闵可夫斯基和，并非SAT。 - undefined

Answer 3

我的方法基于这个答案，并基于您认为位于AABB内部的胶囊体作为交集的假设。 这个想法是通过加上胶囊体的半径（Minkowski sum）来扩展AABB。这将给你一个带有半径r的圆角矩形。然后，我们检查定义胶囊体的线段是否与扩展的AABB相交。

1. 创建一个有直角的扩展AABB，并检查线段与AABB之间的相交关系。
2. 如果线段位于该AABB内部->相交。
3. 如果线段没有与该AABB相交->返回false。
4. 如果线段与该AABB相交两次->检查这两个交点是否在扩展AABB的同一角落区域内。->如果不是，则相交。如果是->检查线段与圆角（球体）之间的相交关系。
5. 如果线段与该AABB相交一次->检查交点是否位于扩展AABB的角落区域内。如果不是->相交。如果是->检查线段与圆角（球体）之间的相交关系。

以下是C ++实现：

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;
  }
}

- JakobThumm

Answer 4

流行的物理引擎，如Bullet，使用GJK算法来处理凸形状之间的相交（除了简单的形状）。由于这种相交问题似乎没有简单的解决方案，而且我需要为圆柱体、锥体、胶囊体和盒子等形状实现更多的相交检测，所以我决定采用GJK方法。你只需要实现一次，然后就可以通过为该形状定义支持函数来检测任意两个凸形状之间的相交。

一些常见形状的支持函数可以在这里找到。以下是胶囊体支持函数的摘录：

struct Capsule : Collider {
    float r, y_base, y_cap;

    vec3 support(vec3 dir){
        dir = matRS_inverse*dir; //find support in model space

        vec3 result = normalise(dir)*r;
        result.y += (dir.y>0) ? y_cap : y_base;

        return matRS*result + pos; //convert support to world space
    }
};

- Lenny White