多边形碰撞检测算法 | 您所在的位置:网站首页 › 凹多边形和凸多边形相交对吗 › 多边形碰撞检测算法 |
AABB碰撞检测指轴对齐碰撞箱(Axis-aligned Bounding Box),是分别从x轴向和y轴向进行碰撞检测的算法。即对于需要检测的物体A和物体B我们需要将其用A盒和B盒套起来,判断A盒和B盒在x轴向和y轴向是否发生碰撞,只有在x轴向和y轴向都发生碰撞我们才判断它发生了碰撞。 在轴对齐包围矩形(Axis Aligned Bounding Box,AABB)基础之上,更为准确的是 转向包围矩形(Oriented Bounding Box,OBB) OBB 与 AABB 的差别在于物体旋转之后,AABB的大小会发生改变,保证每条边与某个坐标轴平行;OBB 的大小则不会改变,且将随物体一起旋转。 2、OBB碰撞检测算法OBB 就是找一个最小的包围物体的矩形,这在自动驾驶系统中也是最常用的,感知模块给出物体的轮廓通常就是此形状。另外,为了准确描述物体轮廓,感知模块在 bounding box 的基础上,通常还会给出 polygon(多边形)的形式,如下图所示。 分离轴定理(SAT): 分离轴定理(Separating Axis Theorem)的理论依据为超平面分离定理,即 令 A 和 B 是两个不相交的非空凸集,那么存在一个非零向量 v 和 实数 c,使得 ≤ c 且 ≥ c。其中,x 属于 A,y 属于 B。 简单来说,就是对于两个凸多边形,若存在一条直线将两者分开,则这两个多边形不相交。 实际应用中,遍历所有角度的分离轴是不现实的,受益于多边形的性质,对于两个都是多边形的物体,只需要依次在每条边的垂直线做投影即可,如下图所示。
在实际应用中,为了提高效率,通常先使用 基于轴对齐包围矩形(AABB)的方法进行粗略的碰撞检测,然后再使用分离轴定理(SAT)做精细碰撞检测。 3、GJK(Gilbert–Johnson–Keerthi)算法GJK是由Gilbert,Johnson,Keerthi 三位前辈发明的,用来计算两个凸多面体之间的碰撞检测,以及最近距离。GJK算法可以在O(M+N)的时间复杂度内,检测出碰撞,算法在每次迭代的过程中,都会优先选择靠近原点的方向,因此收敛速度会很快。算法的证明过程比较复杂,但是原理还是比较容易理解的。 相比 SAT 算法,GJK 算法更加高效。 GJK算法的核心就是闵可夫斯基差,即若两个多边形相交,则它们的闵可夫斯基差必然包括原点。 闵可夫斯基差,也可以叫做闵可夫斯基和,它的定义也很好理解,点集A与B的闵可夫斯基和被定义为: A + B = {a + b |a∈A,b∈B} 如果 A 和 B 是两个凸多边形,则 A + B 也是凸多边形。 闵可夫斯基和从几何上的直观理解是A集合沿B的边际连续运动一周扫过的区域与B集合本身的并集,也可以是B沿着A的边界连续运动扫过区域与A自身的并集。 GJK算法用到的不是闵可夫斯基和,而是闵可夫斯基差,即: A – B = {a – b |a∈A,b∈B} 虽然使用的是减法运算,但其仍然是闵可夫斯基和,相当于先对B中的所有点做负运算(相对原点的镜像),然后再与A做加法。 先来看两个例子。 对于两个不相交的多边形,shape1为矩形,shape2为三角形,如下图所示。 在GJK算法中,单纯形被大量使用。单纯形指的是点、线段、三角形或四面体。例如,0阶单纯形是点,1阶单纯形是线段,2阶单纯形是三角形,3阶单纯形是四面体。 对于上面两个相交的多边形例子,实际应用中,其实不需要求出完整的闵可夫斯基差,只需要在闵可夫斯基差内形成一个多边形,如下图所示,并使这个多边形尽可能包围原点,这个多边形就称为单纯形。即假如单纯形包围原点,则闵可夫斯基差必然包围原点。 如下图所示,在给定向量 a 方向上,shape1 的最远点为(4,2),在向量 -a 的方向上,shape2 的最远点为(5,3),这两个点作差即得到点(-1,-1)。利用这种方式得到的点都在闵可夫斯基差的边上。 |
CopyRight 2018-2019 实验室设备网 版权所有 |