窄相碰撞检测
使用宽相检测可以输出哪两个物体的AABB包围盒重叠后,就可以使用窄相检测进行进一步相交测试。如果发生碰撞,窄相还需要计算出碰撞的详细信息,即接触信息 (Contact Information),包括:接触点 (Contact Points)、接触法线 (Contact Normal)和穿透深度 (Penetration Depth)。这些信息是碰撞响应和约束求解的输入。
在窄相碰撞检测时,根据两个物体形状,选择不同的检测算法。根据及算法可以分成三大类:
基于解析公式的“专用几何体检测”算法
利用几何体的数学定义,直接通过公式进行计算:判断是否相交、求最近点和穿透深度。比如:Sphere-Sphere, sphere-plane, Capsule-Capsule,Ray-Primitive等。
SAT(分离轴定理)
SAT算法,用于检测两个凸多面体是否相交。原理是:如果能找到一条轴,使得两个凸多面体在该轴上的投影(区间)不重叠,那么这两个物体就没有发生碰撞。这条轴被称为分离轴。反之,如果找不到任何这样的分离轴,那么这两个物体就必然发生了碰撞。
GJK+EPA
GJK是另一种用于凸体碰撞检测的流行算法,它通常比SAT更快,尤其是在处理曲面形状(如球体、胶囊体)时。如果GJK确认了碰撞,接下来通过扩展多边形算法(Expanding Polytope Algorithm, EPA)的后续步骤来精确计算穿透法线和深度。
GJK的原理是:将两个凸物体的碰撞问题转化为“是否包含原点”问题。具体实现方法是通过逐步构建一个称为**单纯形(Simplex)**的小多边形(在3D中最多是一个四面体),来逼近并判断闵可夫斯基差形状是否包含原点。
EPA的原理是:从 GJK 得到的内点单纯形出发,沿凸集边界膨胀,找到原点到凸包表面最短距离,从而确定碰撞响应信息。