PhysX4.1的Capsule-Heightfield大致代码结构和Sphere-Heightfield差不多,都是遍历包围盒内的三角形,然后用Capsule和每个三角形做检测,不熟悉的读者可以看我的前一篇文章,这篇文章可能会更偏数学思路上的导读而非代码结构一点
Bairuo:PhysX4.1 Sphere-Heightfield地形碰撞检测源码分析
一.Segment-Triangle距离部分
核心函数在于求Segment和Triangle的最短距离及线段和三角形上对应的点
我们先从求点P和三角形ABC最短距离的思路说起
我们知道三角形可以表示为重心坐标:T(s,t)=A+s(B-A)+t(c-A),其中s≥0,t≥0,s+t≤1
那么P的最近点为二次函数d(s,t)=||T(s,t)-P||^2最小值,包括三种情形:某一顶点处、某一条边上以及三角形内部。
这种方法是向量微分的方法,学校解题中一般也只会谈这种方法,不过对于计算机中实现和这个特定应用来说,我们使用的是另外一种方法:考虑P位于三角形的哪一个区域(Voronoi域),将P正交投影至该特征域即可获得最近点Q
图和思路来自《Real-Time Collision Detection》
再来看一下求线段和线段的最短距离,假设线段中心点是c1,c2,of=c2-c1,带方向半长分别是d1,d2,想求的最近两点分别为c+sd和c+td,那么可以列出下面公式,求解即可
d1*s = n1(d2*t - of)
d2*t = n2(d1*s + of)
为什么列出这个公式,有图的话应该比较好理解
https://www.zhihu.com/video/1521918094776168448
最后回到线段与三角形最近距离,我们依然不使用向量微分的方法而是分类讨论,总的来说有这样几种情况,其中最短距离就是线段与三角形最短距离:
图来自《Real-Time Collision Detection》
Physx4.1这里具体的做法是求线段延长线位于三角形平面的区域,然后比较对应区域线段与边的距离,线段端点与三角形的距离,它代码中求线段延长线部分具体的公式比较晦涩,如果想具体推敲,可以先参考geometrictools的公式https://www.geometrictools.com/GTE/Mathematics/DistLine3Triangle3.h
| Dot(E1, E1) Dot(E1, E2) | | b[1] | = | Dot(E1, Y - V[0]) | | Dot(E1, E2) Dot(E2, E2) | | b[2] | = | Dot(E2, Y - V[0]) |
虽然我们知道三角形重心坐标表示法,但其实很多时候我们是拿边长直接求解的。假设三角形表示为V[0],E1(V[1]-V[0]),E2(V[2]-V[0]),这里有个等式,任意坐标Y-V[0]与边E1、E2的dot等于左边的内容。直接看公式可能不太好理解,可以在等式两边都除以|E1|,Y如果在三角形平面内是直接成立的,在空间中可以根据三垂面定理得到一样的结果,可以配合这张图,其中point9是Y,边0-2是E1
得到交点u,v后根据不同的情况分类讨论,fr为线段上的参数,fs,ft分别为三角形uv,比较不同情况下segment-segment,point-triangle的距离
https://www.zhihu.com/video/1521938594897494017
跑physx的算法,视频中point4,9为线段两端点,point8为求出来的点
physx在distanceSegmentTriangleSquared中在平行情况下有大量的无用计算,另外distanceSegmentTriangleSquared得到距离后又重复算了一次线段与三角形每条边的距离,这里本人不是太理解,觉得都是可以优化的部分,若有不同观点的大佬就麻烦指正了
二.距离为0时的处理部分
当线段与三角形相交的时候线段三角形距离为0,这个时候是无法得出碰撞法线的,physx的做法是拿三角形与线段做了一次SAT,分离轴分别是三角形法线、线段与每条激活edge的叉乘
激活edge是在处理每个三角形之前处理的,大致是遍历三角形的相邻三角形,只处理edge两边三角形为锐角的部分,这大概也能理解,如果是退化或非凸的边缘,不应该拿来做SAT