math - 如何计算两个 AABB 之间的 Minkowski 差（没有向量数学）？

Question

我正在实现我的碰撞检测库的第二个版本。这个特定的库应该处理轴对齐框（AABB）。我想开始在这个版本上跟踪快速移动的盒子。我认为计算两者之间的 Minkowski 差异将是一个很好的起点。

当我说 Minkowsky 差异时，我指的是Collision detection for Dummies中描述的几何操作。

问题是：那里描述的过程和算法非常通用。它使用相当先进的矢量数学来计算任何两个多边形的 MD。

就我而言，我有 AABB。鉴于它们的数值简单，该库到目前为止不需要向量概念 - 例如，我不需要计算单个点积。如果可能的话，我希望它保持这种状态。

所以我的问题是：

给定两个 AABB 的顶部、左侧、宽度和高度（{t1,l1,w1,h1}和{t2,l2,w2,h2}），我如何计算它们的 MD（如果可能，不使用向量数学）？

只需使用 Dummies 的碰撞检测小部件，我几乎可以肯定 MD 宽度将是一个宽度w1+w2和高度的框h1+h2。但我不知道如何计算它的上角或左角。

score 31 · Accepted Answer

两个轴对齐矩形 {t1, l1, w1, h1} 和 {t2, l2, w2, h2} 的 Minkowski 差异本身就是一个轴对齐矩形：

l = l1 - l2 - w2
t = t2 - t1 - h1
w = w1 + w2
h = h1 + h2

以下是一个简短的 javascript 演示，用于展示这一点。您可以拖动两个矩形中的任何一个。重叠时它们会改变颜色

无碰撞

检测到碰撞

1 回答 1