检查两个移动的AABB相交的最快方法是什么?

我有两个AABB正在移动,检查它们是否会在一个框架下相交的最快方法是什么?

通过移动我的意思不只是检查通常的矩形交集方法,我的意思是某种简单的易扫描testing,只返回一个布尔值,没有命中时间或其他任何东西。

我想是这样做的:

这个

但是这个Hexagon相当复杂,我不知道如何计算一个AABB – 多边形交集,有没有更简单的方法?

任何你最喜欢的编程语言,我都可以轻松移植它。

谢谢。

使用Minkowski和

解决这个问题的一个好方法就是考虑一条运动线( v )转换到原点( v' )和在原点( A' )旋转180度的A的Minkowski和与它的障碍物(只是B在这种情况下):A'B。

在下面的图片中,我将任意一个坐标系的原点放在一个点上 。 这简化了理解,因为将A旋转180度导致A' ,并且将v翻译为原点等于v'

闵可夫斯基和是绿色的矩形,移动的A和静止的B的交点可以通过行AABB交点find 。 这些点用蓝色圆圈标记。

闵可夫斯基和 - 退化的情况

在下面的图片中使用了不同的原点,并find了相同的交点。

闵可夫斯基总和 - 更一般的情况

多个移动的AABB

为了使这两个在特定时间段内以线性方式运动的AABB能够工作,可以从A的速度vector中减去B的速度vector,并将其用作线AABB交点的线段。

伪代码

def normalize(aabb): return {x1: min(aabb.x1, aabb.x2), x2: max(aabb.x1, aabb.x2), y1: min(aabb.y1, aabb.y2), y2: max(aabb.y1, aabb.y2), def rotate_about_origin(aabb): return normalize({x1: -aabb.x1, x2: -aabb.x2 y1: -aabb.y1, y2: -aabb.y2}) # given normalized aabb's def minkowski_sum(aabb1, aabb2): return {x1: aabb1.x1+aabb2.x1, x2: aabb1.x2+aabb2.x2, y1: aabb1.y1+aabb2.y1, y2: aabb1.y2+aabb2.y2} def get_line_segment_from_origin(v): return {x1: 0, y1: 0, x2: vx, y2: vy} def moving_objects_with_aabb_intersection(object1, object2): A = object1.get_aabb() B = object2.get_aabb() # get A'⊕B rotated_A = rotate_about_origin(A) sum_aabb = minkowski_sum(rotated_A, B) # get v' total_relative_velocity = vector_subtract(object1.get_relative_velocity(), object2.get_relative_velocity()) line_segment = get_line_segment_from_origin(total_relative_velocity) # call your favorite line clipping algorithm return line_aabb_intersection(line_segment, sum_aabb) 

碰撞响应

根据游戏玩法,你要么执行更细粒度的碰撞检测(也许AABB包含网格),要么前进到下一个阶段:碰撞响应。

当发生碰撞时,线AABB相交algorithm将返回1或2个交点,这取决于A是否在B内移动或者通过它。 (这是对A在沿着它们两侧或沿着它们各自的一个角落啃食B的退化情况的折扣。)

无论哪种方式,沿着线段的第一个交点就是碰撞点,你可以把它转换回世界坐标系中的正确位置(沿着原始v的第二张图中的第一个浅蓝色圆圈,称之为p ),然后决定(例如,通过在p上沿着碰撞法线reflectionv的弹性碰撞)框架结尾处的A的实际位置将是( At + 1 )。

碰撞响应

如果只有两个以上的对撞机,这将会变得更复杂一些,因为你想要做第二个碰撞检测,反映出v的一部分。

面向OBB的边界框。 这是一个教程

实际上,一个边界框与对象A的速度vectoralignment为y轴(向上)。 它的宽度和高度可以通过对象A的开始点和结束点来计算。然后将它与对象B的AABB(将其视为OOBB)以及您的金色进行比较。

如果您只是在寻找一个快速交叉点testing来查看它们可能相交的位置,则可以在起始位置和结束位置创建一个包围对象A的AABB的AABB。 如果一个AABB不与所有包含AABB的相交,那么就没有相交; 但是,这可能会导致误报,所以您只能将其作为初步testing。

您不需要OOB,也不需要使用时间步进碰撞检测。 只需使用正常的AABB扫频testing,看看这个链接 。 在本质上,它的确如你在图表中所做的那样:移动的AABB从起点到终点被“扫描”,然后用于对其他静态AABB的碰撞检测。

如果你担心这个扫描testing是比较昂贵的,因为它返回一个“影响时间”,我认为你提前优化。

有关扫频testing的更深入的信息可以在Christer Ericson的“ 实时碰撞检测”一书中find。

AABB近似边缘案例无力

您需要首先将运动分解为更小的步骤,并使用该信息来计算高级AABB。 如果大AABB相交,则可以检查更小的步骤以更准确。

如果仅使用开始位置和结束位置来检查AABB(或OOBB)来估计是否可能发生了碰撞,则可能会错过任何一个对象快速旋转并且在一个维度上长于另一维度的对象。

要计算更精确的估计AABB,请将运动分解为更小的步骤,并且仅使用初始AABB(不是对象网格),旋转AABB(现在只是一个框,而不是轴alignment),因为对象将旋转并在每个步。 每个轴的最大和最小点将为您提供围绕物体整个运动的AABB。

如果与较大的AABB有交叉点,则可以使用已计算的较小的AABB来确定碰撞的可能位置。 对于与其他对象相交的每个较小的AABB,您可以执行更昂贵的网格交集检测。

你将不得不将运动分解成更小的运动步骤。 例如:

您想要使用更大的组件(在这种情况下为X轴)分解运动,然后检查每个步骤中的碰撞。

这可能看起来太昂贵了,但是考虑到一个对象在每个周期内移动的速度比它自己的宽度要快得多,所以这种情况并不像你第一次想象的那么普遍。

您还应该使用相对速度进行碰撞检查,以便一个AABB是“静态”,另一个以其自己速度的速度减去“静态”速度。

看他们是否可能相交的最快方法是以速度扩展移动的AABB。

例如,AABB以0.1 x /帧向右移动,然后扩展它,使左边缘保持不变,右边缘进一步变为0.1。 然后你可以检查新的AABB。 如果错误,则不会发生碰撞。 (提前回来,准确的小速度)。

然后你可以检查移动物体的结束和开始AABB是否相交。 如果是true,则返回true。

否则,您需要检查对角线是否与静态ABB相交。

这包括获得对角线的坐标,其中x =静态的左边缘,右边缘看y是否在底部和顶部。 (重复其他方式)