快速移动物体的六边形碰撞检测?

一个对象有一个位置和一个速度向量。 通常只有位置被用来检查两个物体是否碰撞,这对于移动速度非常快的物体是有问题的,因为在第一次碰撞检查中物体移动得太快以至于在第一个物体的前面,第二次碰撞检查。

边界框碰撞失败

现在还有基于行的碰撞检查,其中只检查每个对象的运动vector是否与另一个对象的边界框相交。 这可以被看作是一个点的扩展。 这只有在快速移动的物体非常小时才起作用。

六角形碰撞赢

所以我的想法是,而不是扩大一点,为什么不扩大矩形? 这导致了Hexagon。

现在,这么好。 但是我怎样才能检查这两个六边形是否相交呢? 请注意,这些是非常具体的六角形。

六角形规格

奖金问题 :是否有可能计算碰撞发生的确切地点(或者确切地说在多less时间之后)? 这对于检测真正发生的事情非常有用,比如在何处以及在多大的功率下模拟它们在碰撞和帧结束之间的时间内如何移动。

解决scheme实际上比预期的简单。 诀窍是在你的六边形技术之前使用Minkowski减法 。

这里是矩形A和B,速度为vAvB 。 请注意, vAvB实际上不是速度,而是一帧期间行进的距离

步骤1

现在用一个点P代替矩形B,用矩形C = A +( – B)代替矩形A,矩形A的尺寸是A和B的尺寸之和.Minkowski加法属性表示点和新矩形之间发生碰撞当且仅当原始两个矩形之间发生碰撞时:

第2步

但是,如果矩形C沿vectorvA移动,并且点P沿着vectorvB移动,则参考框架的简单改变告诉我们,如果矩形C仍然是一样的,并且点P沿vectorvB-vA

步骤3

然后,您可以使用一个简单的分段交集公式来确定新参考框架中发生碰撞的位置。

最后一步是回到正确的参考框架。 只要将点所经过的距离除以vectorvB-vA的长度,直到圆圈的交点,就会得到0 < s < 1的值。 碰撞发生在时间s * T ,其中T是你的帧的持续时间。

评论者madshogo
与Beast自己的回答相比,这种技术的巨大优势在于,如果不存在旋转,那么可以为所有后续的时间步骤计算一次“闵可夫斯基相减” A +( – B)

因此,唯一需要花费时间的algorithm(Minkowski和,复杂度O(mn) ,其中mA中顶点的数量, nB中顶点的数量)只能使用一次,有效地使得碰撞检测成为一个常量 -时间问题!

后来,一旦你确定AB位于你的场景的不同部分(你的四叉树?),你就可以把这笔钱扔掉,不会再碰撞了。

相比之下,Beast先生的方法在每个时间步骤都需要进行相当多的计算。

另外,对于轴alignment的矩形, A +( – B)的计算要比通过顶点实际计算所有和,即顶点的计算简单得多。 通过将B的高度加上其高度并将B的宽度加到其宽度(每边的一半)来扩展A。

但是,只有在AB都不旋转且两者都是凸的情况下,所有这些才有效。 如果有旋转,或者如果使用凹形,则必须使用扫描体积/面积。
评论结束

首先,在轴alignment的矩形的情况下,凯文·里德的答案是最好的,algorithm是最快的。

其次,对于简单的形状,使用相对速度(如下所示)和碰撞检测的分离轴定理。 它告诉你在直线运动(不旋转)的情况下是否发生碰撞。 如果有旋转,你需要一个小的时间步,这是精确的。 现在回答这个问题:


在一般情况下如何判断两个凸形是否相交?

我会给你一个适用于所有凸形而不仅仅是六边形的algorithm。

假设XY是两个凸形。 它们相交,当且仅当它们有一个共同点,即有一个点x &in; X和一个点y&in; Y这样x = y 。 如果将空间视为一个向量空间,那么这就等于说x – y = 0 。 现在我们来到这个明科夫斯基的业务:

XY的Minkowski和是x&的所有x + y集合; XY& Y。


X和Y的一个例子


X,Y和它们的Minkowski和,X + Y

假设(-Y)y的所有-y的集合; Y ,那么在前面的段落中, XY相交当且仅当X +(-Y)包含0 ,即原点

旁注:为什么我写X +( -Y 而不是X-Y ? 那么,因为在math中,有一种叫做AB的闵可夫斯基(Minkowski)差异的操作,它有时被写成X – Y,而与x的所有x – y的集合无关; XY& Y (真正的Minkowski差异更复杂一点)。

所以我们想计算X-Y的Minkowski和,找出它是否包含原点。 与任何其他点相比,原点并不特别,为了find原点是否在某个域内,我们使用一个algorithm来告诉我们是否有任何给定点属于该域。

XY的Minkowski和具有冷却性质,即如果XY是凸的,那么X + Y也是。 并且发现一个点是否属于一个凸集合比这个集合不是(已知)是凸的容易得多。

我们不可能计算x&的所有x – y ; XY& Y是因为有这样一个点xy的无穷大,所以希望XYX + Y是凸的,所以我们可以使用定义形状XY的“最外层”点,它们是顶点,我们会得到X + Y的最外面的点,还有更多。

这些附加点被X + Y的最外侧的“包围”,使得它们不有助于定义新获得的凸形。 我们说他们没有定义一组点的“ 凸包 ”。 所以我们所做的是我们摆脱它们,准备最终的algorithm,告诉我们原点是否在凸包内。


X + Y的凸包。 我们删除了“内部”顶点。

我们因此得到

第一,天真的algorithm

 boolean intersect(Shape X, Shape Y) { SetOfVertices minkowski = new SetOfVertices(); for (Vertice x in X) { for (Vertice y in Y) { minkowski.addVertice(xy); } } return contains(convexHull(minkowski), Vector2D(0,0)); } 

这些循环显然具有复杂度O(mn) ,其中mn是每个形状的顶点数。 minkoswki集最多包含mn个元素。 convexHullalgorithm的复杂度取决于您使用的algorithm ,您可以瞄准O(k log(k)) ,其中k是点集的大小,所以在我们的情况下,我们得到O(mn log(mn ))containsalgorithm的复杂度与凸包的边(2D)或面(3D)的数量是线性的,所以它确实取决于您的起始形状,但不会大于O(mn)

我会让你谷歌的contains凸形状algorithm,这是一个很常见的。 如果我有时间的话,我可以把它放在这里。


但是这是我们正在做的碰撞检测,所以我们可以优化很多

我们最初有两个身体AB在时间步dt (从我可以通过查看你的照片来看)没有旋转。 我们称v Av B分别为AB的速度,这些速度在我们的持续时间dt的时间步长内是恒定的。 我们得到以下内容:

而且,正如你在照片中所指出的那样,这些身体在移动时会扫过整个区域 (或3D)

在时间步后他们最终成为A'B'

为了在这里应用我们的朴素algorithm,我们只需要计算扫描体积。 但是我们没有这样做。

B的参考框架中, B不移动(duh!)。 而且A 相对于B 有一定的速度 可以通过计算v A – v B得到 (你可以做相反的处理,计算A的参考系中B的相对速度)。

相对运动

从左到右:基准参考系中的速度; 相对速度; 计算相对速度。

通过将B固定在其自己的参考框架中, 您只需计算A在其间以相对速度v A – v B移动的过程中扫过的体积

这减less了在闵可夫斯基和计算中使用的顶点的数量(有时很大)。

另一种可能的优化是在计算由一个物体扫过的体积的位置,假设A.您不必翻译构成A的所有顶点。只有那些属于边缘(3D的脸部)的物体外部正常“面对”扫地的方向。 当然,你已经注意到,当你计算你的扫描区域的正方形。 您可以通过扫描方向来判断法线是否朝向扫掠方向,而扫掠方向必须是正值。

最后的优化与您的关于交叉点的问题无关,在我们的例子中非常有用。 它使用我们提到的相对速度和所谓的分离轴方法。 当然你已经知道了。

假设你知道AB相对于它们的质心 (也就是质心和离它最远的顶点之间的距离)的半径 ,就像这样:

只有A的边界圆可能与B的边界圆相遇,才会发生碰撞。 我们在这里看到,它不会,以及如何告诉计算机计算从C BI的距离,如下图所示,确保它大于AB的半径之和。 如果它更大,没有碰撞。 如果它更小,那么碰撞。

这对于形状相当长的形状来说效果并不好,但在正方形或其他形状的情况下, 排除碰撞是非常好的启发式。

然而,应用于B的分离轴定理和由A扫过的体积确实告诉你是否发生碰撞。 相关algorithm的复杂性与每个凸形状的顶点数之和成线性关系,但实际处理碰撞的时间却不那么神奇。

我们新的更好的algorithm,使用交叉点来帮助检测碰撞,但仍然不如分离轴定理,以便实际判断是否发生碰撞

 boolean mayCollide(Body A, Body B) { Vector2D relativeVelocity = A.velocity - B.velocity; if (radiiHeuristic(A, B, relativeVelocity)) { return false; // there is a separating axis between them } Volume sweptA = sweptVolume(A, relativeVelocity); return contains(convexHull(minkowskiMinus(sweptA, B)), Vector2D(0,0)); } boolean radiiHeuristic(A, B, relativeVelocity)) { // the code here } Volume convexHull(SetOfVertices s) { // the code here } boolean contains(Volume v, Vector2D p) { // the code here } SetOfVertices minkowskiMinus(Body X, Body Y) { SetOfVertices result = new SetOfVertices(); for (Vertice x in X) { for (Vertice y in Y) { result.addVertice(xy); } } return result; } 

我不认为使用“六边形”是有帮助的。 下面是对轴alignment的矩形进行精确碰撞的一种方式的草图:

当且仅当它们的X坐标范围重叠并且它们的Y坐标范围重叠时,两个轴alignment的矩形重叠。 (这可以看作是分离轴定理的特例)。也就是说,如果将矩形投影到X轴和Y轴上,则可以将问题简化为两条线条交点。

计算一个轴上两条直线相交的时间间隔 (例如,它从时间开始(物体的当前分离/相对接近物体的速度)),对另一个轴执行相同的操作。 如果这些时间间隔重叠,则重叠内的最早时间是碰撞时间。

我不认为有一个简单的方法来计算多边形的多边形比矩形的碰撞。 我会把它分解成像线条和方块的原始形状:

 function objectsWillCollide(object1,object2) { var lineA, lineB, lineC, lineD; //get projected paths of objects and store them in the 'line' variables var AC = lineCollision(lineA,lineC); var AD = lineCollision(lineA,lineD); var BC = lineCollision(lineB,lineC); var BD = lineCollision(lineB,lineD); var objectToObjectCollision = rectangleCollision(object1.getRectangle(), object2.getRectangle()); return (AC || AD || BC || BD || objectToObjectCollision); } 

对象的路径和最终状态的插图

请注意 ,我如何忽略每个对象的开始状态,因为在之前的计算过程中应该检查它们。

分离轴定理

分离轴定理说: “如果我们可以find一个两个凸形不相交的轴,那么这两个形状就不会相交” ,对于IT来说更实用:

“两个凸形只有在所有可能的轴上相交时才相交。”

对于轴alignment的矩形,正好有两个可能的轴:x和y。 但是这个定理并不局限于矩形,只要加上形状可以相交的其他轴就可以应用于任何凸形。 有关该主题的更多详细信息,请查看N的开发人员: http : //www.metanetsoftware.com/technique/tutorialA.html#section1

实现它看起来像这样:

 axes = [... possible axes ...]; collision = true; for every index i of axes { range1[i] = shape1.getRangeOnAxis(axes[i]); range2[i] = shape2.getRangeOnAxis(axes[i]); rangeIntersection[i] = range1[i].intersectionWith(range2[i]); if(rangeIntersection[i].length() <= 0) { collision = false; break; } } 

轴可以表示为标准化的向量。

范围是一维线。 开始时应设置最小的投影点,结束到最大的投影点。

将其应用于“有音”的矩形

问题中的六边形是通过“扫掠”物体的AABB产生的。 扫描将恰好一个可能的碰撞轴添加到任何形状:运动vector。

 shape1 = sweep(originalShape1, movementVectorOfShape1); shape2 = sweep(originalShape2, movementVectorOfShape2); axes[0] = vector2f(1.0, 0.0); // X-Axis axes[1] = vector2f(0.0, 1.0); // Y-Axis axes[2] = movementVectorOfShape1.normalized(); axes[3] = movementVectorOfShape2.normalized(); 

到目前为止这么好,现在我们已经可以检查两个六边形的相交了。 但它变得更好。

这种解决scheme将适用于任何凸形(例如三角形)和任何形状的凸形(例如八角形的八角形)。 然而,形状越复杂,效果就越差。


奖励:魔法发生的地方。

正如我所说,唯一的附加轴是运动向量。 这个运动是时间乘以速度的,所以从某种意义上说,它们不是空间轴, 而是时间轴。

这意味着我们可以从这两个轴中得出碰撞可能发生的时间。 为此,我们需要find移动轴上两个交点之间的交点。 在我们可以做到这一点之前,我们需要对两个范围进行标准化,所以我们可以比较它们。

 shapeRange1 = originalShape1.getRangeOnAxis(axes[2]); shapeRange2 = originalShape2.getRangeOnAxis(axes[3]); // Project them on a scale from 0-1 so we can compare the time ranges timeFrame1 = (rangeIntersection[2] - shapeRange1.center())/movementVectorOfShape1.project(axes[2]); timeFrame2 = (rangeIntersection[3] - shapeRange2.center())/movementVectorOfShape2.project(axes[3]); timeIntersection = timeFrame1.intersectionWith(timeFrame2); 

当我问这个问题的时候,我已经接受了这个方法会有一些罕见的误报。 但是我错了,通过检查这个时间交集,我们可以testing碰撞是否“实际”发生,我们可以将这些误报排除在外:

 if(collision) { [... timeIntersection = see above ...] if(timeIntersection.length() <= 0) collision = false; else collisionTime = timeIntersection.start; // 0: Start of the frame, 1: End of the frame } 

如果您发现代码示例中有任何错误,请告诉我,我还没有实现它,因此无法testing它。

只要扫掠区域都是闭合的(在边缘线所形成的边界上没有缝隙),下面的工作就可以实现(只需要减less碰撞testing就可以直线和点 – 直角/点三):

  1. 他们的边缘接触? (线条碰撞)检查扫描区域的任何边缘线是否与其他扫描区域的任何边缘线相交。 每个扫描区域有6个边。

  2. 大的内部是小的吗? (使用轴alignment的形状(point-rect和point-tri))重新定位(旋转)扫描区域,使较大的轴alignment,testing较小的是否内部(通过testing是否有任何角点应该是全部或全部)都在轴alignment的扫描区域内)。 这是做你的hex分解成三和rects。

你首先做哪个testing取决于每个testing的可能性(首先做最常见的testing)。

您可能会发现使用扫掠边界圆(胶囊而不是hex)更容易,因为它更容易将其分成两个半圆,而当它与轴alignment时则更容易。 我会让你画出解决scheme