PhysX4.1 Capsule-Heightfield地形碰撞检测源码分析
PhysX4.1 Capsule-Heightfield地形碰撞检测源码分析
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》
- 线段PQ与三角形边AB
- 线段PQ与三角形边BC
- 线段PQ与三角形边CA
- 线段端点P与三角形平面（P的投影位于三角形ABC内）
- 线段端点Q与三角形平面（Q的投影位于三角形ABC内）
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
