UE5 Chaos物理｜物理查询的实现
- 作者：admin
- /
- 时间：3小时前
- /
- 浏览：18 次
- /
- 分类：厚积薄发
【USparkle专栏】如果你深怀绝技，爱“搞点研究”，乐于分享也博采众长，我们期待你的加入，让智慧的火花碰撞交织，让知识的传递生生不息！
射线检测接口
游戏业务常见的需求就是做各种射线检测/Overlap检测/Sweep检测，比如Character Movement Component。
下面例子是使用Visibility Channel做Line Trace，StaticMesh对其是Block的。
各种Trace，最终都调用到SceneTrace。
使用的TraceChannel，ObjectType等条件，最终都编码成四个4B的Word，下面是TraceChannel的例子。
物理查询，主要就是对AABB Tree的查询。
SceneTrace
ReadLock
要对物理场景做查询，首先加读锁。可以和其他Trace请求同时执行，但和写物理场景操作互斥。
然后获取加速结构Collection，里面有Static AABBTree和Dynamic AABBTree。
最后进到TSpatialAccelerationCollection::RaycastFast。
这里Types就是Buckets，TypeIdx是从0开始的下标，会逐个遍历Buckets，然后对里面的每个AABBTree，调用RaycastFast函数。
注意第一个Bucket存了非常大的AABB，也就是说如果场景内有很多大的物体，是会拖慢射线检测效率的。
TAABBTree::QueryImpl
比较大的函数，做AABBTree的遍历。
AABBTree非叶节点的遍历
经典的BVH检测方式，先检查射线和左右子树AABB是否相交，然后根据相交情况，不断对左右子树做遍历。加速方式为SIMD的应用，以及非递归的遍历AABBTree。
示意图如下：
SIMD版本的Slab算法值得一看，判断射线与AABB是否相交，并计算射线在AABB内经过的距离。全程无if...else...。
里面的VectorMax和VectorSwizzle的组合比较巧妙，用于在三个数中取最大的。
Slab算法简介
Slab算法（Slab Method）是计算机图形学和物理引擎中用于检测射线（Ray）与轴对齐包围盒（AABB）是否相交的最经典、最高效的算法。
它的核心思想非常简单直观：将3D的AABB盒子看作是三组无限大的“平板对”（Slabs）的交集。
假设射线的起点为P，方向为Dir，把射线写成时间t的方程：
射线进入每个“平板对”，都会有进入时间t0和离开时间t1，如果要与AABB发生重叠，三组t0和t1必定有都重叠的部分。
示意图如下：
处理叶节点
对于一个Leave节点，射线检测会执行RaycastFastSimd。
每个Leave节点默认最多有8个Element，它们没有位置关系，因此要逐个对这些Element做射线检测了。
对于Leave中的一个Element，计算和射线是否相交，会经过三道判断。第一道是检查Shape的AABB和射线是否相交，第二道是检查Shape的Channel和QueryChannel是否是Overlap或者Block关系，第三道是真正检查射线和Sphere、Box、凸包等几何体是否相交。前两道是轻量的，算BroadPhase，第三道很重，是NarrowPhase。
把Channel Response检查放到中间也是挺有意思的。按照正常人类思考逻辑，应该是射线碰到一个Geometry后，再判断这个Geometry对射线Channel响应是Block还是Overlap，但判断射线和Shape相交的操作比较重，尤其是面对凸包。因此从代码效率逻辑出发，就变成了不管Shape和射线是否真的相交，先判断Geometry对Channel的响应，如果是Ignore，就直接不管了。具体做法如下：
第一道，射线和AABB Bounds检查是否相交。
同样的，用SIMD判断射线和AABB是否相交，不再赘述。
第二道，射线检测用的Channel和Geometry的ResponseChannel & BlockChannel是否有重叠。
ResponseChannel & BlockChannel是两个int32，本身是每个Geometry的属性，但AABBTree为了效率，在Payload里都缓存了一份，为UnionQueryFilterData和UnionSimFilterData，CachedUniqueIdx则是所属UObject的UniqueIdx缓存。
具体的Channel Response过滤方法。
PrePreQueryFilter
首先从Word0中获取射线检测使用的Channel，然后检查Geometry自身的Word1和Word2，分别是BlockingChannel和OverlapChannel，做bit and操作，看是否有交集。
注意这里的函数名是PrePreQueryFilter，说明后面还有PreQueryFilter流程。
射线和各种几何体相交判断
第三道，真正的射线和几何体相交检测。
PreQueryFilter
几何检测前，先执行一些自定义逻辑的Filter做过滤，判断是否要做对Shape的射线检测，可以做游戏业务相关的操作。注意到例子中的射线检测是按照LineTrace BlockChannel做的，但目前OverlapChannel的Shape也还没被排除，排除操作就是在PreQueryFilter阶段做的，实际会调用FCollisionQueryFilterCallback::PreFilterBaseImp函数。
首先对比查询的Channel，和Shape的OverlapChannel & BlockingChannel，判断这次查询是Touch还是Block，称为CollisionQueryHitType。
如果是LineTraceSingle，那么只关心BlockingChannel，TouchChannel的Shape可以忽略。
查询的Touch/Block和Shape的ResponseChannel比对通过后，再判断IgnoreActors和IgnoreComponents是否需要过滤，LineTrace时通常会设置IgnoreActors。
FCollisionQueryFilterCallback::PreFilter检查通过后，正式进入射线和几何体相交计算。
世界空间坐标和Geometry局部空间坐标
此时射线的起点和方向都是世界坐标，在检测前先变换到Geometry的坐标空间，后面计算起来会更加方便。比如对Box检测时，直接用AABB射线检测算法即可。
射线和不同几何体相交计算
这里不仅要判断是否相交，还要得到射线接触的位置，初次接触几何体的距离，以及接触点的法线。每个几何体都实现了Raycast函数，观察不同几何体的实现。
TSphere
球形判断是最简单的。
令直线起点为P，方向为dir，直线方程为：
设圆心为C，半径为R，直线和圆相交，需要满足以下方程：
这是关于t的一元二次方程，用公式求出t即可。
有了时间t，就能快速求出交点坐标和交点法线了。
Tbox
最终执行的AABB，计算开销比球体高些。
对于三组Slab，都分别计算进出时间t0、t1，然后取交集，得到时间t，再得到交点。法线总是XYZ三个方向，计算t0属于哪个面即可。
FCapsule
Capsule可以想象成，到线段最短距离为r的点，形成的距离场，线段作为Capsule的轴心。
那么判断射线和胶囊体是否相交，计算这个轴心线段到射线的最短距离即可，具体计算上，需要找出一对距离最近的点。
真正困难的地方在于，线段上的最近点，位于线段中间。直接贴一个已有算法，核心是找出两个平面的相交线，理解起来需要点时间，但计算步骤并不多。
参考：
https://johnmayhk.wordpress.com/2012/02/02/shortest-distance-between-two-skew-lines/
如上所示，最短距离就是BD在MN上投影的长度，而MN同时垂直AB和CD，另外ABXCD得到的向量也同时垂直AB和CD，因此MN与（ABXCD）平行。由此可得到最短距离。
有了距离，就能解出两个点了。
UE也实现了这个算法，封装于SegmentDistToSegmentSafe函数，主要步骤如下：
当射线与Capsule相交后，还需要进一步求交点和normal。
分两种情况：
- 与上下两个半球相交，normal从球心出发
- 与中间圆柱体相交，计算圆柱体的normal
FConvex凸包
最复杂，使用了GJK算法，不再展开
和Shape发生碰撞后怎么办？
当前的Hit类型是ChaosInterface::FLocationHit，先填充Hit的这几个属性：
之后再给个机会执行FCollisionQueryFilterCallback::PostFilter，如处理bDiscardInitialOverlaps过滤等。
然后把Time作为Distance记下，表示射线已经打了多远，对后续Shape做射线检测时，将从最新的Distance开始，继续往后打射线。
回到AABB子树的遍历，如果要判断多个子树，但射线在之前已经Block了，就不用判断之后的子树了。
FHitResult的填充
FHitResult展开后有如下属性，其中大部分在之前射线发生碰撞时已经可以得到，只有黄线画出的几个需要看下如何获取。
PhysMat
命中点的物理材质，物理材质可以理解为类似渲染用的材质，只不过描述的是物体表面的摩擦力、密度等属性。当前已经有了FaceIndex，而Geometry中记录了FaceIndex和PhysicsMaterial的对应关系，因此可以得到PhysicsMaterial。
BoneName
命中点所属骨骼的名称。
对于示例中的StaticMesh，是没有骨骼的，因此是None，只有对于SkeletalMesh，这个BoneName才有意义。
观察SkeletalMesh的PhysicsAsset，多个骨骼上会挂接RigidBody，它们有各自对应的BodySetup，BoneName就存在BodySetup里。射线检测时，可以根据命中的GeometryParticle获取到BodyInstance，再获取到BodySetup，最终得到BoneName。
HitItem & ElementIndex
都属于一些Extra数据，不太重要。
HitItem是BodyInstance在整个PhysicsAsset中的序号，针对SkeletalMesh的情况。ElementIndex是Trace中Shape在Geometry的Shape数组中下标。对于示例中的StaticMeshComponent，它们都是0。
完整的LineTrace流程如下：
Overlap检测
第二种碰撞检测是Overlap检测，比LineTrace更复杂些，会判断一个体积内有没有和其他物体相交。这里以Box碰撞体为例，需要传入Box的位置和大小，区别于之前的LineTrace使用TraceChannel，这里使用了ObjectTypes，查询Box范围内重叠的其他Actor。但对于物理引擎而言，TraceChannel和ObjectTypes本质都是一样的，都是CollisionChannel。
首先，把查询的Geometry计算一个AABB包围盒，传入AABBTree做BroadPhase的检测。
AABBTree的左右子树Overlap
对左右子树分别做AABB的碰撞检测。
Leaf节点的处理
TAABBTreeLeafArray.OverlapFast
对Leaf中每个Payload Geometry，同样先做AABB碰撞检测。用了SIMD技术，四个Payload为一组。当AABB检测通过后，依然先执行PrePreFilter，做Channel之类的判断，再针对具体的Geometry Shape形状，做Narrow Phase的Overlap检测。
Shape可以有Sphere、Box、Capsule、凸包等各种几何形状，但它们都属于凸包。要判断两个凸包是否Overlap，就要用GJK算法，UE的实现是GJKIntersection函数，自然也是SIMD实现。
GJK算法
关于GJK算法的详细介绍，可以看这里：
总体过程是不断通过Support函数，在两个凸包上找一对点，计算闵可夫斯基差，然后让形成的三角形包含原点。GJK算法有点复杂，不展开了，但不同Shape的Support函数实现可以看下，具体就是每个Shape的SupportCore函数。
所谓Support函数，就是给定一个方向，找到Shape在这个方向上最远的一个点，下图就是两个例子。
简单起见只看SupportCore普通版本，SIMD版本思想类似。
TBox
等价于对一个AABB求Support点。不难理解，AABB在某个方向上的最远点必定是8个顶点之一，因此只要依次判断三个轴，做三次方向二分即可，2^3 = 8。
TSphere
最简单，球的中心加上半径*方向即可。
FCapsule
看似复杂，实则和Sphere一样简单。Capsule的Support点必定出现在两个半球上，因此首先根据Direction方向确定是哪个半球，然后类似Sphere处理即可。
FConvex
需要遍历所有凸包的顶点，与方向做点乘，找到最远的点。
这里实现也比较有意思，寻找凸包的Support点，理论上用启发式的“爬山法”更快，即从上个Support点往后找邻接点，不用遍历所有顶点，而且UE是保存了边的连接关系的：
那为什么不用爬山法？个人猜测是以下几个原因：
- 直接遍历Vertices数组，CPU Cache更友好，在顶点数量不多（也是大部分情况）情况下可能更快。
- 爬山法需要记录上一次的Support点序号，但碰撞检测可能多个线程并行，这样就需要为每个线程都记录一份上次的Support点了，实现有点麻烦，而且得保证线程安全。
如果要得到Overlap深度，就要使用GJKPenetration算法， 结合了GJK与EPA，这里不展开了。
Sweep检测
最复杂的情况，以Box Sweep为示例，会得到Sweep路径上发生重叠的物体。
BroadPhase
类似Overlap，但把Sweep经过的整个路径，作为AABB，查询与左右子树的碰撞情况。
NarrowPhase
对于Leaf节点中的每个Geometry，同样经过PrePreFilter，AABB检测，PreFilter。
对Geometry中每个Shape的Sweep检测，最后依然使用GJK算法。
如果是TriangleMesh复杂碰撞怎么办？
首先，Shape就变成了FTriangleMeshImplicitObject，类似Mesh，没有凸包的限制，可以表示任何形状。因此，类似GJK这种精妙的几何碰撞算法都不再适用，只能回归最原始的三角形相交判断。
Raycast & Overlap & Sweep
BroadPhase相同，使用AABBTree。
NarrowPhase不使用GJK算法了，而是每个TriangleMesh自己有一个BVH树，用BVH的碰撞检测方式。BVH子节点存储了三角形，在检测子节点内部碰撞时，采样逐三角形检测方式。
比如这个例子，BVH树有379个节点，模型总共有5760个面，还是非常复杂的。
Tips
综合上述碰撞检测流程，可以对物理场景优化做一些指导：
- 游戏中物体都设置专门的Simple Collision，避免查询复杂碰撞
- Shape的碰撞检测效率排序：Sphere > Capsule > Box >> Convex >>>> Triangle Mesh，尽量用效率高的Shape做近似
- 避免太长的LineTrace，以及范围太大的Overlap和Sweep
- LineTrace查询的开销最低，玩法上尽量用它
这是侑虎科技第1977篇文章，感谢作者南京周润发供稿。欢迎转发分享，未经作者授权请勿转载。如果您有任何独到的见解或者发现也欢迎联系我们，一起探讨。（QQ群：793972859）
作者主页：https://www.zhihu.com/people/xu-chen-71-65
再次感谢南京周润发的分享，如果您有任何独到的见解或者发现也欢迎联系我们，一起探讨。（QQ群：793972859）