UE PhysX BroadPhase

碰撞检测

Broad Phase介绍

Broad Phase是碰撞检测的第一步，基于物体的AABB进行碰撞检测，目标是快速剔除大部分不可能发生碰撞的物体对，只把可能重叠的候选对传给后续的Narrow Phase做精确检测。

PhysX的Speculative CCD即通过根据速度和时间步长膨胀AABB来避免高速漏检。

void FPhysScene_PhysX::InitPhysScene(const AWorldSettings* Settings)初始化PhysX场景，在这里对Broad Phase进行配置。

PxBroadPhaseType::Enum physx::PxSceneDesc::broadPhaseType指定使用哪种算法，如果不指定，默认初始化为eSAP。

struct PxBroadPhaseType
{
    enum Enum
    {
       eSAP,     //!< 3-axes sweep-and-prune
       eMBP,     //!< Multi box pruning
       eGPU,

       eLAST
    };
};

eSAP 指Sweep And Prune，通过对所有物体在坐标轴上的范围进行排序来检测重叠。初始化时采用基数排序，物体移动时采用插入排序。当大量物体处于静止时性能很好，内存开销低。当多数物体都在运动或频繁添加/删除时性能显著下降。

eMBP指Multi Box Pruning，将世界划分为若干区域，每个区域单独进行基数排序，从而进行重叠检测。适用于移动物体较多的场景，在所有物体都移动或大量插入/删除时通常比eSAP更快。但需要预定义子划分数，设子划分数为N，区域数量为N*N（在水平面上做二维划分），过大会影响性能和内存；当很多物体静止时不如eSAP。

eGPU依赖GPU硬件加速实现，需要硬件支持SM3.0或更新标准。

如何配置MBP

SAP不需要特别配置，MBP则需要配置。

Project Settings窗口的默认Broadphase配置全局生效，World Settings窗口的Broadphase配置可以覆盖默认配置，只对当前关卡生效。

可配置项对应AWorldSettings的FBroadphaseSettings AWorldSettings::BroadphaseSettings的成员变量。

Use MBPOn Client — 对应bUseMBPOnClient

Use MBPOn Server — 对应bUseMBPOnServer

Use MBPOuter Bounds — 对应bUseMBPOuterBounds，选择是否设置MBPOuter Bounds

MBPBounds：

Min (X, Y, Z) — 对应MBPBounds.Min

Max (X, Y, Z) — 对应MBPBounds.Max

MBPOuter Bounds：

Min (X, Y, Z) — 对应MBPOuterBounds.Min

Max (X, Y, Z) — 对应MBPOuterBounds.Max

MBPBounds和MBPOuter Bounds之间会创建四个区域，如图示：

（PhysX只提供了添加区域的接口，是UE自己设计的）

MBPNum Subdivs — 对应MBPNumSubdiv，即划分数。

在控制台配置：

p.ForceMbpClient：强制在客户端场景使用MBP。

p.ForceMbpServer：强制在服务器场景使用MBP。

p.OverrideMbpNumSubdivisionsClient：覆盖客户端MBP子划分数（非 0 才生效）。

p.OverrideMbpNumSubdivisionsServer：覆盖服务器MBP子划分数（同上）。

（这些CVar只在场景创建时生效，运行时修改需要重建/重新创建场景才能应用）

（p.ForceMbpClient和p.ForceMbpServer没有作用）

算法流程

PhysX将工作拆分为Task，每个Task对应一个函数，入参为下一个Task。通过定义这些Task之间的先后依赖关系，由线程池中的空闲线程去动态执行。

Sc::Scene::rigidBodyNarrowPhase内创建Task链条： mBroadPhase -> mPostBroadPhase -> mPostBroadPhase2 -> mPostBroadPhase3 -> *continuation。*continuation为rigidBodyNarrowPhase函数入参，由其调用者传入，即TaskmRigidBodyNarrowPhase执行完后的下一个Task。

mBroadPhase、mPostBroadPhase、mPostBroadPhase2、mPostBroadPhase3均为由Cm::DelegateTask绑定到指定函数的Task。

mBroadPhase对应函数Sc::Scene::broadPhase，执行Board Phase碰撞检测。它调用 mAABBManager->updateAABBsAndBP，更新所有动态物体的 AABB（轴对齐包围盒），并将这些变化传递给底层的Board Phase算法（SAP或MBP），从而计算出新产生的重叠对和消失的重叠对。

updateAABBsAndBP处理AABB更新后调用finalizeUpdate，finalizeUpdate调用mBroadPhase->update(const PxU32 numCpuTasks, PxcScratchAllocator* scratchAllocator, const BroadPhaseUpdateData& updateData, physx::PxBaseTask* continuation, physx::PxBaseTask* narrowPhaseUnblockTask)（BroadPhase& mBroadPhase是BroadPhaseSap或BroadPhaseMBP实例）。

在使用MBP的情况下，在其中创建Task链条：mMBPUpdateWorkTask->mMBPPostUpdateWorkTask-> *continuation，mMBPUpdateWorkTask、mMBPPostUpdateWorkTask均为由Cm::Task继承而来的Task，分别调用函数update，postUpdate（入参均为PxBaseTask*），对应Unreal Insights中的性能统计项BpMBP.updateWork、BpMBP.postUpdateWork。

使用SAP同上。

mPostBroadPhase对应函数Sc::Scene::postBroadPhase，通知Narrow Phase上下文Board Phase已完成，调用mAABBManager->postBroadPhase获取并处理Board Phase产生的重叠对结果，清理已改变的 AABB 管理器句柄映射，调用 finishBroadPhase开始创建新的交互对象（Interactions）和接触管理器（Contact Managers）。

mPostBroadPhase2对应函数:Sc::Scene::postBroadPhaseStage2，处理因失去接触而需要唤醒的物体，释放预分配的接触管理器和形状交互对象的内存回池。

PhysX 使用“岛屿”来分组相互作用的物体。如果一个岛屿中的所有物体都静止不动且能量低于阈值，整个岛屿会进入睡眠状态以节省 CPU/GPU 计算资源。

例如，一开始物体A和B相互堆叠，A在B的下面，都静止并进入睡眠状态（属于同一个睡眠岛屿）。随后，A受到了一个瞬时力，导致A醒来并开始移动，A与B失去接触。

此时如果不唤醒B，B仍然认为自己是睡眠岛屿的一部分。但在下一帧，由于A已经移开，B本应因为重力开始下落，却没有下落，导致bug。

因此，必须唤醒B，以便在下一帧重新计算其受力情况和运动状态。

mPostBroadPhase3对应函数 Sc::Scene::postBroadPhaseStage3，调用finishBroadPhaseStage2 完成最后的清理工作。

SAP

BroadPhaseSap::update调用batchRemove移除所有待移除的对象，分别在三个轴上更新排序。更新时只处理移动过的对象，采用插入排序。

BroadPhaseSap::postUpdate收集三个轴上的新增对和重叠对。

MBP

PhysX提供了添加区域的接口createRegionsFromWorldBounds、addBroadPhaseRegion，UE在FPhysScene_PhysX::InitPhysScene函数内根据用户配置的边界和子划分数生成区域。

PhysX定义最大区域数量为256，#define MAX_NB_MBP 256，因此，UE对配置的NumSubdivisions（默认为2）clamp到1到16，用于将MBPBounds划分为区域。在bUseMBPOuterBounds为true的情况下，NumSubdivisions最高仅为15，因为在MBPBounds和MBPOuterBounds之间会生成四个区域作为Outer区域。

// Must have at least one and no more than 256 regions, subdivision is num^2 so only up to 16
NumSubdivisions    = FMath::Clamp<uint32>(NumSubdivisions, 1, BroadphaseSettings.bUseMBPOuterBounds ? 15 : 16);

BroadPhaseMBP::update（仅在多线程模式下有操作，否则在setUpdateData中同步完成碰撞检测）调用mMBP->findOverlapsMT(mGroups)遍历所有区域，调用每个区域内部的重叠检测。在此之前，Region::prepareOverlapsMT已经对静态/动态物体按X轴最小值进行基数排序。findOverlapsMT使用doCompleteBoxPruning检测动态-动态对和动态-睡眠动态对，doBipartiteBoxPruing检测动态-静态对。

BroadPhaseMBP::postUpdate重置每个区域的"已更新"计数器，调用finalize统计新增、持续、消失的重叠对。