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移除所有待移除的对象，分别在三个轴上更新排序。更新时只处理移动过的对象，采用插入排序。在三个轴上都重叠的AABB即重叠。

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收集新增、持续、消失的重叠对。

算法分析

基于 NVIDIA PhysX 3.4 源码（Engine/Source/ThirdParty/PhysX3/PhysX_3.4/Source/LowLevelAABB/）的实现分析。

1. 总体设计对比

维度	SAP（BroadPhaseSap）	MBP（BroadPhaseMBP / MBP / Region）
核心思想	对 3 个轴各自维护一份按浮点值排序的端点表（min/max），在帧间通过冒泡式增量插入保持有序，并在端点 swap 时维护活跃 pair 集合	把世界切成若干 Region，每个 Region 内部独立执行一次"主轴排序 + Sweep（Complete/Bipartite Box Pruning）"，跨 Region 由对象同时归属多个 Region 来覆盖
是否需要世界边界	否，无限世界	是，必须由用户通过 addRegion 注册 region，未覆盖区域的对象会进入"out-of-bounds" 列表（见 MBP::addToOutOfBoundsArray）
排序粒度	全局 3 个轴端点链表（共 2N + 2 个 sentinel-保护的元素）	区域内的"主轴 minX" 单轴排序（基数排序 RadixSort）
帧间状态	强增量 —— 上一帧 pair 列表直接保留，本帧只处理 swap 引发的 add/remove	半增量 —— Pair 列表保留并通过 isNew/isUpdated 标记，几何上每帧重新做 box pruning
数据结构	端点数组 + 双向链表（mListPrev/mListNext）+ 活跃区间 BroadPhaseActivityPocket	MBPEntry 表 + mStaticBoxes/mDynamicBoxes SoA-like 数组 + Radix sort 缓冲
Pair 容器	SapPairManager（开放寻址 hash 表 + 状态位 PAIR_INARRAY/PAIR_REMOVED/PAIR_NEW）	MBP_PairManager（开放寻址 hash 表 + isNew/isUpdated 标志）
AABB 编码	32-bit ValType，将 float 通过 encodeFloat 编码成可整数比较的值，min 偶数对齐 / max 奇数对齐	同样使用 encodeFloat，但右移 1 位（>>1）以保留 31 位精度同时让 min/max 区分；可选启用 MBP_SIMD_OVERLAP 的 SIMD_AABB（XMXMYZ 布局）
静态 vs 动态	不区分（所有对象都在统一的 3 轴端点表里），通过 mBoxGroups 过滤	显式区分：每个 Region 维护 mStaticBoxes + mDynamicBoxes，静态盒子可以做"延迟一次性排序"（staticSort）
并行性	3 个轴并行（BroadPhaseBatchUpdateWorkTask mBatchUpdateTasks[3]）	每个 Region 之间天然并行（Region::findOverlapsMT）
适用场景	大量休眠物体、世界规模未知或动态扩张	大量同时运动物体、大型/规则世界、需要多线程扩展

---

2. SAP 算法实现剖析

2.1 数据结构

SapBox1D*                   mBoxEndPts[3];          //Position of box min/max in sorted arrays of end pts (needs to have mBoxesCapacity).
ValType*                    mEndPointValues[3];     //Sorted arrays of min and max box coords
BpHandle*                   mEndPointDatas[3];      //Corresponding owner id and isMin/isMax for each entry in the sorted arrays of min and max box coords.

PxU8*                       mBoxesUpdated;  
BpHandle*                   mSortedUpdateElements;  
BroadPhaseActivityPocket*   mActivityPockets;
BpHandle*                   mListNext;
BpHandle*                   mListPrev;

• mEndPointValues[axis]：长度 2 * boxes + 2（前后各一个 sentinel），存放每个 AABB 的 min/max 端点编码值。
• mEndPointDatas[axis]：与值数组一一对应，低 1 bit 表示 isMax，高位是 owner_box_id（见 setData/getOwner/isMax）。
• mBoxEndPts[axis][box]：从 box ID 反查它在端点表中的 min/max 索引（SapBox1D::mMinMax[2]），用于 O(1) 取出某 box 在某轴上的位置。
• mListPrev/mListNext：以端点索引为节点的双向链表，被增量更新阶段用来"先逻辑挪动、再统一回写数组"，避免 swap 时大量重复访存。
• BroadPhaseActivityPocket：一段连续被改动过的端点索引区间 [mStartIndex, mEndIndex]，用于把链表式 swap 的结果只在受影响的子区间内回写到 mEndPointValues/Datas 数组。
• SapPairManager（BpBroadPhaseSapAux.h）：哈希表 + 状态位，使一次 AddPair / RemovePair 是 O(1)，并能区分 "本帧新加 / 本帧删除 / 之前就存在"。

端点编码用了一个巧妙的 trick：min 编码后强制偶数（& ~1），max 强制奇数（| 1），这样在相等端点处的排序具有稳定的"max 排在 min 之后"语义（见 setMinSentinel、encodeMin/encodeMax）。

2.2 一帧的执行流程

入口：BroadPhaseSap::update(...)，详细顺序：

void BroadPhaseSap::update(const PxU32 numCpuTasks, PxcScratchAllocator* scratchAllocator, const BroadPhaseUpdateData& updateData, PxBaseTask* continuation, PxBaseTask* narrowPhaseUnblockTask)
{
    ...
    const bool success = setUpdateData(updateData);

    if(success)
    {
        mScratchAllocator = scratchAllocator;
        resizeBuffers();
        ...
        mSapPostUpdateWorkTask.setContinuation(continuation);
        mSapUpdateWorkTask.setContinuation(&mSapPostUpdateWorkTask);
        mSapPostUpdateWorkTask.removeReference();
        mSapUpdateWorkTask.removeReference();
    }
}

Task 链：SapUpdateWorkTask → SapPostUpdateWorkTask → continuation，前者内部串行调用：

void BroadPhaseSap::update(PxBaseTask* continuation)
{
    ...
    batchRemove();
    ...
    mBatchUpdateTasks[0].runInternal();
    mBatchUpdateTasks[1].runInternal();
    mBatchUpdateTasks[2].runInternal();
}

虽然这里写的是顺序 runInternal，但每个 BroadPhaseBatchUpdateWorkTask 是独立 Task，理论上可以并行（每个轴只读其他两个轴的 SapBox1D，写自己轴的端点表与自己 task 的 pair 数组），后续 postUpdate 把 3 个轴产生的 pair 合并。

Step 1：batchRemove（删除对象）

void BroadPhaseSap::batchRemove()
{
    ...
    for(PxU32 Axis=0;Axis<3;Axis++)
    {
        ...
        for(PxU32 i=0;i<mRemovedSize;i++)
        {
            ...
            BaseEPData[MinIndex] = PX_REMOVED_BP_HANDLE;
            BaseEPData[MaxIndex] = PX_REMOVED_BP_HANDLE;
            ...
        }
        // 从 MinMinIndex 起做一次"原地压缩"，去掉所有 PX_REMOVED_BP_HANDLE
        ...
    }
    ...
    mPairs.RemovePairs(bitmap);
    ...
}

要点：把要删除对象的端点先打 sentinel 标记 PX_REMOVED_BP_HANDLE，再做一次原地压缩；最后用 BitMap 一次性扫一遍 mPairs，把涉及到删除 box 的所有 pair 标记移除。

Step 2：batchUpdate（按轴并行批量更新）

batchUpdate 是 SAP 的核心。BroadPhaseSap::batchUpdate(axis, ...) 自适应分了两个分支：

void BroadPhaseSap::batchUpdate
(const PxU32 Axis, BroadPhasePair*& pairs, PxU32& pairsSize, PxU32& pairsCapacity)
{
    if(mUpdatedSize == 0)
        return;

    //If number updated is sufficiently fewer than number of boxes (say less than 20%)
    if((mUpdatedSize*5) < mBoxesSize)
    {
        batchUpdateFewUpdates(Axis, pairs, pairsSize, pairsCapacity);
        return;
    }
    ...
}

• 当 updated < 20% 总数 → batchUpdateFewUpdates：先用 quicksort/bucket sort 收集"只处理被更新的端点"的索引 mSortedUpdateElements，然后只对这些位置做反向冒泡。
• 否则 → batchUpdate：从左到右扫描整条端点表，当某端点对应 box 在本帧被 update 或它正在与一个活跃 pocket 重叠时，走 swap 逻辑。

核心逻辑（节选）：

for(; !isSentinel(BaseEPDatas[ind]); ++ind)
{
    BpHandle ThisData = BaseEPDatas[ind];
    const BpHandle handle = getOwner(ThisData);

    if(updated[handle] || wasUpdated)
    {
        ...
        ValType ThisValue = startIsMax ? encodeMax(...) : encodeMin(...);
        BaseEPValues[ThisIndex] = ThisValue;
        ...
        BpHandle CurrentIndex = mListPrev[ThisIndex];
        ValType CurrentValue = BaseEPValues[CurrentIndex];

        if(CurrentValue > ThisValue)
        {
            ...
            if(!isMax(ThisData))
            {
                // min 向左滑：每越过一个 max，就意味着可能 *新增* 一对 overlap
                do
                {
                    BpHandle CurrentData = BaseEPDatas[CurrentIndex];
                    const BpHandle IsMax = isMax(CurrentData);
                    if(IsMax)
                    {
                        const BpHandle ownerId=getOwner(CurrentData);
                        SapBox1D* PX_RESTRICT id1 = asapBoxes + ownerId;
                        // Our min passed a max => start overlap
                        if(
                            BaseEPValues[id1->mMinMax[0]] < boxMax && 
                            Intersect2D_Handle(...)
                            && (group!=asapBoxGroupIds[ownerId])
                            )
                        {
                            ...
                            pairs[numPairs].mVolA=BpHandle(PxMax(handle, ownerId));
                            pairs[numPairs].mVolB=BpHandle(PxMin(handle, ownerId));
                            numPairs++;
                        }
                    }
                    ...
                }
                while(ThisValue < CurrentValue);
            }           
            else 
            {
                // max 向左滑：每越过一个 min，可能 *移除* 一对 overlap（见同函数下方）
                ...
            }
            ...
        }
    }
    ...
}

可以清楚看到 SAP 增量更新的灵魂： - min 向左越过某 max → 该轴上原本不重叠的两个 box，现在在该轴重叠了（潜在 add pair）。 - max 向左越过某 min → 该轴上原本重叠的两对 box，现在分开了（潜在 remove pair）。 - 仅"该轴重叠"并不代表 3D 重叠，因此还要调用 Intersect2D_Handle 在另外两个轴上做 2D 重叠测试，得到的才是真正的候选 pair。 - pair 用 (min(a,b), max(a,b)) 标准化方向：mVolA>mVolB 表示 add，否则表示 remove（由 postUpdate 中的判断 if(volA > volB) 区分）。 - BroadPhaseActivityPocket + mListPrev/mListNext 让链表式 swap 可以延迟到"pocket 结束时再回写"，大幅降低了 swap 时的内存写量；最后 pocket 段内做 in-place 收缩。

Step 3：batchCreate（新增对象）

void BroadPhaseSap::batchCreate()
{
    if(!mCreatedSize)   return;
    ...
    for(PxU32 Axis=0;Axis<3;Axis++)
    {
        // 1) 给所有新 box 生成 min/max 端点数据
        ...
        // 2) 用 RadixSortBuffered 对新端点做基数排序
        const PxU32* Sorted = RS.Sort(keys, numEndPoints, Cm::RADIX_UNSIGNED).GetRanks();
        ...
        // 3) 把已排序的新端点合并进现有的全局端点数组
        InsertEndPoints(bufferValues, bufferDatas, numEndPoints, mEndPointValues[Axis], mEndPointDatas[Axis], 2*(mBoxesSize-mCreatedSize)+NUM_SENTINELS, mBoxEndPts[Axis]);
    }
    ...
    const Gu::Axes axes(Gu::AXES_XYZ);
    performBoxPruning(axes);
}

新对象会触发一次"批量端点插入 + box pruning"。performBoxPruning 又拆成 New-New（新创建之间）和 New-Old（新创建 vs 之前已有），都使用了 1D sweep 的经典写法（见 BpBroadPhaseSapAux.cpp 中的 performBoxPruningNewNew/NewOld）。

这也解释了官方注释中"large numbers of objects are added to or removed from the broad phase"会显著掉性能 —— 大批量创建意味着 3 个轴各做一次 radix sort + merge insertion + box pruning，比纯增量更新昂贵得多。

Step 4：postUpdate —— 把 3 个轴产生的"候选"合并为最终 add/remove

void BroadPhaseSap::postUpdate(PxBaseTask* /*continuation*/)
{
    ...
    for(PxU32 i=0;i<3;i++)
    {
        const PxU32 numPairs=mBatchUpdateTasks[i].getPairsSize();
        const BroadPhasePair* PX_RESTRICT pairs=mBatchUpdateTasks[i].getPairs();
        for(PxU32 j=0;j<numPairs;j++)
        {
            const BroadPhasePair& pair=pairs[j];
            const BpHandle volA=pair.mVolA;
            const BpHandle volB=pair.mVolB;
            if(volA > volB)
                AddPair(volA, volB, ...);
            else
                RemovePair(volA, volB, ...);
        }
    }

    batchCreate();

    ComputeCreatedDeletedPairsLists(
        mBoxGroups,
        mData,mDataSize,
        mScratchAllocator, 
        mCreatedPairsArray,mCreatedPairsSize,mCreatedPairsCapacity,
        mDeletedPairsArray,mDeletedPairsSize,mDeletedPairsCapacity,
        mActualDeletedPairSize,
        mPairs);
    ...
}

最终通过 SapPairManager 的状态位（PAIR_INARRAY/PAIR_NEW/PAIR_REMOVED）一次性扫出 created/deleted pair 报告给上层。

2.3 复杂度

• 单帧增量更新（少量移动）：单轴上的 swap 数与 endpoint 移动总距离 d 成正比，整体接近 O(N + d + k)，k 为新增 / 删除 pair 数，这就是 SAP 的"时间相干性"优势。
• 全员移动（最坏）：单轴上每个端点的相对位置都可能改变，复杂度退化到 O(N²) 量级（每次 swap 都要做 2D 重叠测试）。
• 大批量插入：每轴 O((N + M) log M)（radix sort + merge insert），加上 box pruning。

---

3. MBP 算法实现剖析

3.1 数据结构

MBP 是分层结构：BroadPhaseMBP → MBP → Region。

// We have one of those for each Region within the MBP
struct RegionData : public Ps::UserAllocated
{
    MBP_AABB    mBox;       // Volume of space controlled by this Region
    Region*     mBP;        // Pointer to Region itself
    Ps::IntBool mOverlap;   // True if overlaps other regions
    void*       mUserData;  // Region identifier, reused to contain "first free ID"
};

    #define MAX_NB_MBP  256

    class MBP : public Ps::UserAllocated
    {
        ...
        PxU32                   mNbPairs;
        PxU32                   mNbRegions;
        MBP_ObjectIndex         mFirstFreeIndex;    // First free recycled index for mMBP_Objects
        PxU32                   mFirstFreeIndexBP;  // First free recycled index for mRegions
        Ps::Array<RegionData>   mRegions;
        Ps::Array<MBP_Object>   mMBP_Objects;
        MBP_PairManager         mPairManager;

        BitArray                mUpdatedObjects;    // Indexed by MBP_ObjectIndex
        BitArray                mRemoved;           // Indexed by MBP_ObjectIndex
        Ps::Array<PxU32>        mHandles[MAX_NB_MBP+1];
        ...
#ifdef USE_FULLY_INSIDE_FLAG
        BitArray                mFullyInsideBitmap; // Indexed by MBP_ObjectIndex
#endif
        ...
    };

• 每个 Region 是一段"封装的 1D Sweep-Like" 小型 BP，内部维护自己的 mStaticBoxes/mDynamicBoxes（按 minX 排序的 AABB 列表）。
• 一个对象可以同时归属多个 Region（MBP_Object::mNbHandles 记录归属数），这是 MBP 跨 Region 边界检测重叠的核心机制。
• 全局只共享一个 MBP_PairManager，所以同一对物体跨多个 Region 重叠也只会产生一条 pair（hash 表自动去重）。
• mFullyInsideBitmap 是优化：若一个对象完全落在它所归属的全部 Region 之内，那么新加 Region 时无需测试这个对象；新加 Region 时只遍历"不在 fully-inside 集合中"的对象（详见 populateNewRegion 的位扫描实现）。

Region 自身的关键字段：

//      private:
        BoxPruning_Input    PX_ALIGN(16, mInput);
        PxU32               mNbObjects;
        PxU32               mMaxNbObjects;
        PxU32               mFirstFree;
        MBPEntry*           mObjects;
        PxU32               mMaxNbStaticBoxes;
        PxU32               mNbStaticBoxes;
        PxU32               mMaxNbDynamicBoxes;
        PxU32               mNbDynamicBoxes;
        MBP_AABB*           mStaticBoxes;
        MBP_AABB*           mDynamicBoxes;
        MBP_Mapping         mInToOut_Static;    // Maps static boxes to mObjects
        MBP_Mapping         mInToOut_Dynamic;   // Maps dynamic boxes to mObjects
        PxU32*              mPosList;
        PxU32               mNbUpdatedBoxes;
        PxU32               mPrevNbUpdatedBoxes;
        BitArray            mStaticBits;
        RadixSortBuffered   mRS;
        bool                mNeedsSorting;
        bool                mNeedsSortingSleeping;
        MBPOS_TmpBuffers    mTmpBuffers;

注意：MBP 把 dynamic 数组里"被更新"的对象通过 MTF（move-to-front） 移到前 mNbUpdatedBoxes 个位置（见 MTF() 函数），帧之间不需要 sort 静态/睡眠对象。

3.2 一帧的执行流程

入口：BroadPhaseMBP::update(...)，同样基于 task：

void BroadPhaseMBP::update(const PxU32 numCpuTasks, PxcScratchAllocator* scratchAllocator, const BroadPhaseUpdateData& updateData, physx::PxBaseTask* continuation, physx::PxBaseTask* narrowPhaseUnblockTask)
{
    ...
    setUpdateData(updateData);
    ...
    mMBPPostUpdateWorkTask.setContinuation(continuation);
    mMBPUpdateWorkTask.setContinuation(&mMBPPostUpdateWorkTask);
    mMBPPostUpdateWorkTask.removeReference();
    mMBPUpdateWorkTask.removeReference();
}

setUpdateData 在主线程内直接调用 removeObject / addObject / updateObject，并最后调用 mMBP->prepareOverlapsMT()（每个 Region 各自 staticSort + 后续每帧的 preparePruning 是在工作 task 内通过 findOverlapsMT 上下文里准备的）。

Step 1：apply removed/created/updated（主线程，setUpdateData）

const BpHandle* removed = updateData.getRemovedHandles();
if(removed)
{
    ...
    const bool status = mMBP->removeObject(mMapping[index]);
    ...
}

const BpHandle* created = updateData.getCreatedHandles();
if(created)
{
    ...
    IntegerAABB bounds(boundsXYZ[index], updateData.getContactDistance()[index]);
    MBP_AABB aabb;
    aabb.mMinX  = bounds.mMinMax[IntegerAABB::MIN_X]>>1;
    ...
    const MBP_Handle mbpHandle = mMBP->addObject(aabb, index, isStatic);
    mMapping[index] = mbpHandle;
}

const BpHandle* updated = updateData.getUpdatedHandles();
if(updated)
{
    ...
    const bool status = mMBP->updateObject(mMapping[index], aabb);
    ...
}
...
mMBP->prepareOverlapsMT();

MBP::addObject 会逐个 Region 测试新 AABB 与 region box 的相交，把 box 加入所有相交 region（region->addObject）。MBP::updateObject 同理，但有"上一帧只在一个 region 且该 region 不与别人 overlap、且新 box 仍完全在该 region 内"的快速路径，跳过遍历所有 region。

Step 2：每个 Region 静态排序 / 准备数据（prepareOverlapsMT）

void Region::prepareOverlapsMT()
{
    if(!mNbUpdatedBoxes && !mNeedsSorting)
        return;

    if(mNeedsSorting)
    {
        staticSort();
        // 当 static 端被改动后，下一帧需要把所有动态 box 也全部当作 updated，
        // 这样它们会在 BipartiteBoxPruning 中跟新静态盒子整体重测
        mNbUpdatedBoxes = mNbDynamicBoxes;
        ...
    }

    preparePruning(mTmpBuffers);
    prepareBIPPruning(mTmpBuffers);
}

• staticSort：分两段—— 已经在排好序的静态 box 视为"sorted set"，新增/改动的静态 box 单独 radix sort，最后做双路合并排序写回。这样静态盒子绝大多数帧都只是 O(N) 合并，没有重排序。
• preparePruning：把"动态 box"分成 updated（前 mNbUpdatedBoxes 个，由 MTF 维护在数组头）和 sleeping（其余），各做一次 radix sort，得到 mInput。
• prepareBIPPruning：构造 dynamic vs static 的 bipartite 输入 mInput.mBIPInput。

Step 3：实际 box pruning（findOverlapsMT）

入口：MBPUpdateWorkTask::runInternal → MBP::findOverlapsMT → Region::findOverlapsMT：

void Region::findOverlapsMT(MBP_PairManager& pairManager, const BpHandle* PX_RESTRICT groups, const MBP_Object* PX_RESTRICT mbpObjects)
{
    PX_ASSERT(!mNeedsSorting);
    if(!mNbUpdatedBoxes)
        return;

    if(mInput.mNeeded)
        doCompleteBoxPruning(&pairManager, mInput, groups, mbpObjects);

    if(mInput.mBIPInput.mNeeded)
        doBipartiteBoxPruning(&pairManager, mInput.mBIPInput, groups, mbpObjects);

    mNbUpdatedBoxes = 0;
}

• doCompleteBoxPruning：经典的"主轴 sweep + 限制 max 范围扫描 + 2D 重叠测试"算法。MBP_OVERLAP_TEST 在启用 MBP_SIMD_OVERLAP 时会扩展成一条 SSE 比较，可一次性完成 yz 的重叠检验（见 BpBroadPhaseMBPCommon.h 的 SIMD_AABB 布局：mMinX 与 mMaxX 相邻，便于 SSE 比较）。

    // Prune the list
    const PxU32 lastSortedIndex = nbUpdated;
    PxU32 sortedIndex = 0;
    PxU32 runningIndex = 0;
    while(runningIndex<lastSortedIndex && sortedIndex<lastSortedIndex)
    {
        const PxU32 index0 = sortedIndex++;
        const MBP_AABB& box0 = updatedDynamicBoxes[index0];
        const PxU32 limit = box0.mMaxX;
        SIMD_OVERLAP_PRELOAD_BOX0
        const PxU32 l = box0.mMinX;
        while(updatedDynamicBoxes[runningIndex++].mMinX<l);

        if(runningIndex<lastSortedIndex)
        {
            PxU32 index1 = runningIndex;
            while(updatedDynamicBoxes[index1].mMinX<=limit)
            {
                MBP_OVERLAP_TEST(updatedDynamicBoxes[index1])
                {
                    outputPair_DynamicDynamic(...);
                }
#ifdef TEST2
                ...
                index1+=2;
#else
                index1++;
#endif
            }
        }
    }

• doBipartiteBoxPruning：dynamic ↔︎ static 之间的两向扫描，结构对称（先 dynamic 推 static，再 static 推 dynamic），尾部带 MBP_USE_SENTINELS 哨兵以省掉边界判断。
• TWO_AT_A_TIME 宏让 bipartite 内部一次处理两个候选静态盒子，进一步利用指令级并行。

新生成的 pair 通过 MBP_PairManager::addPair 写入：

MBP_Pair* MBP_PairManager::addPair(PxU32 id0, PxU32 id1, const BpHandle* PX_RESTRICT groups, const MBP_Object* objects)
{
    ...
    if(groups)
    {
        ...
        if(groups[object0] == groups[object1])
            return NULL;
    }
    sort(id0, id1);
    const PxU32 fullHashValue = hash(id0, id1);
    PxU32 hashValue = fullHashValue & mMask;
    {
        MBP_Pair* PX_RESTRICT p = findPair(id0, id1, hashValue);
        if(p)
        {
            p->isUpdated = true;
            return p;   // Persistent pair
        }
    }
    ...
    MBP_Pair* PX_RESTRICT p = &mActivePairs[mNbActivePairs];
    p->id0      = id0;
    p->id1      = id1;
    p->isNew    = true;
    p->isUpdated= false;
    ...
    return p;
}

注意：已存在的 pair 不会重复添加，只是 isUpdated = true；全新的 pair 才打 isNew = true。

Step 4：postUpdate → finalize

void BroadPhaseMBP::postUpdate(physx::PxBaseTask* /*continuation*/)
{
#ifndef USE_SINGLE_THREADED_REFERENCE_CODE
    {
        PxU32 Nb = mMBP->mNbRegions;
        const RegionData* PX_RESTRICT regions = mMBP->mRegions.begin();
        for(PxU32 i=0;i<Nb;i++)
        {
            if(regions[i].mBP)
                regions[i].mBP->mNbUpdatedBoxes = 0;
        }
    }
    mMBP->finalize(this);
#endif
}

MBP::finalize → MBP_PairManager::removeMarkedPairs 一次扫过 mActivePairs，根据： - isNew==true → 输出到 mCreated； - isUpdated==false && (任意一端涉及 updated/removed) → 输出到 mDeleted 并物理移除该 pair； - 其余视为持续存在的 pair。

这也解释了 MBP 为什么"对全员同时运动也不会爆炸"：它本质是每帧重算几何，时间相干性只用来快速识别 add/remove 报告，几何复杂度不被 swap 数主导。

3.3 复杂度

• 单 region 内：Complete Box Pruning 经典复杂度大约 O(N log N + K)，K 为该 region 实际产生的候选对数；动态盒子较少的 region 几乎是 O(N)。
• 多 region：N 个对象、R 个 region，时间 ≈ sum_r (n_r log n_r) + 区域间通过对象多归属自动覆盖。Region 之间天然并行（Region::findOverlapsMT）。
• 大批量插入：O(M) 次 addObject，每个对象只对 region 数（≤256）做相交测试，几乎与对象总数 N 无关。
• 全员移动：所有动态 box 都进 updated 集合，等价于做一次完整 box pruning，性能比 SAP 在同场景下稳定得多。

---

4. 关键算法子模块对比

子模块	SAP	MBP
Pair 存储	SapPairManager（开放寻址 hash + Hash32Bits_1）	MBP_PairManager（开放寻址 hash + Ps::hash）
Pair 持久化	上一帧 pair 直接保留，本帧只增/减 swap 触发的差量	全部 pair 在 hash 表里跨帧持久存在，每帧打 isUpdated，未被刷新的判为 lost
增量识别新对	mVolA > mVolB 表 add，反之表 remove；最后由 ComputeCreatedDeletedPairsLists 汇总	addPair 返回时 isNew=true 表新建；removeMarkedPairs 集中处理 lost pair
排序	增量保持有序 + 批量插入时 Cm::RadixSortBuffered	每帧对 updated dynamic 做 RadixSort；static 用 incremental "排序-合并"
AABB 几何测试	1D：值比较；2D：Intersect2D_Handle 使用端点索引（依赖严格顺序）做无浮点比较	1D：mMinX<=limit sweep；2D：可选 SIMD（SIMD_OVERLAP_TEST），布局 mMinX/mMaxX/mMinY/mMinZ/mMaxY/mMaxZ 对 SSE 友好
Group / 过滤	BP_SAP_TEST_GROUP_ID_CREATEUPDATE 在内层循环就过滤同组	MBP_PairManager::addPair 入口处过滤同组（groups[object0]==groups[object1]）
出界处理	没有"出界"概念	不与任何 region 相交的对象进入 mOutOfBoundsObjects，由上层报告
Origin shift	BroadPhaseSap::shiftOrigin 逐端点 decode → shift → encode，并修正排序失效（testPostShiftOrder）	MBP::shiftOrigin 直接对每个 region box 和每个 object box 重新 encode；下一帧自然重新做 box pruning

---

5. 并行化策略

5.1 SAP 的并行

SAP 把"按轴更新"封装为 3 个并行 Task：

BroadPhaseBatchUpdateWorkTask mBatchUpdateTasks[3];

各 task 写自己的端点数组和 pair 缓冲；postUpdate 串行合并 3 个 pair 数组到 SapPairManager。并行度的上限只有 3。

5.2 MBP 的并行

MBP 的并行粒度是 region：每个 region 内部串行做 sweep，region 之间天然独立（互不写对方的数组）。MBP::findOverlapsMT 当前的实现是简单的 for 循环，但实际生产中通常把这层包成多个 task 并发分发（在 PhysX 3.4 的代码里直接顺序调用，是因为 region 数量上限 256，实际场景通常 16~64 个）。并行度的上限取决于 region 数。

这也是 MBP 在多核机器上比 SAP 更容易扩展的一个直接原因。

---

6. 内存对比

内存项	SAP	MBP
每个 box 的常驻数据	3 轴 × 1 个 SapBox1D（含 min/max 在端点表中的索引）+ 每端点 ValType + BpHandle	MBP_Object（含归属 region 列表）+ 每个所属 region 内 MBP_AABB + MBP_Index（6 × 32bit）
排序/工作缓冲	3 个轴各自的端点表（2N + 2）+ mListNext/mListPrev 双向链表 + mActivityPockets	每个 region 内 mPosList、mTmpBuffers（sleeping/updated SoA） + mRS（基数排序）
跨帧持久 pair	SapPairManager 的 hash 表 + 状态位字节	MBP_PairManager 的 hash 表 + MBP_Pair 数组（含 isNew/isUpdated）
额外结构	无 region 概念	mFullyInsideBitmap、mUpdatedObjects、mRemoved、mOutOfBoundsObjects、MAX_NB_MBP=256 个 region 桶

总体上： - SAP：内存几乎与对象数线性相关，没有 region/overlap 元数据； - MBP：内存比 SAP 略大（多了 region 桶、fully-inside 位图、跨 region 重复挂载等），但常数项可控（region 数 ≤ 256）。

---

7. 接口差异

7.1 SAP（不实现 region API）

virtual PxBroadPhaseType::Enum      getType()                   const   { return PxBroadPhaseType::eSAP;    }
virtual void                        update(...);
virtual void                        fetchBroadPhaseResults(physx::PxBaseTask*) {}
virtual PxU32                       getNbCreatedPairs()     const       { return mCreatedPairsSize;     }
virtual BroadPhasePairReport*       getCreatedPairs()                   { return mCreatedPairsArray;    }
virtual PxU32                       getNbDeletedPairs()     const       { return mDeletedPairsSize;     }
virtual BroadPhasePairReport*       getDeletedPairs()                   { return mDeletedPairsArray;    }
virtual void                        resizeBuffers();
virtual void                        freeBuffers();
virtual void                        shiftOrigin(const PxVec3& shift);

SAP 不重写 getNbRegions/addRegion/removeRegion，因为根本不需要。

7.2 MBP（额外实现 region API）

virtual bool                        getCaps(PxBroadPhaseCaps& caps)                                                     const;
virtual PxU32                       getNbRegions()                                                                      const;
virtual PxU32                       getRegions(PxBroadPhaseRegionInfo* userBuffer, PxU32 bufferSize, PxU32 startIndex=0) const;
virtual PxU32                       addRegion(const PxBroadPhaseRegion& region, bool populateRegion);
virtual bool                        removeRegion(PxU32 handle);
virtual PxU32                       getNbOutOfBoundsObjects()   const;
virtual const PxU32*                getOutOfBoundsObjects()     const;

并在 BroadPhaseMBP::getCaps 中明确声明 needsPredefinedBounds = true 与 maxNbRegions = 256：

bool BroadPhaseMBP::getCaps(PxBroadPhaseCaps& caps) const
{
    caps.maxNbRegions           = 256;
    caps.maxNbObjects           = 0;
    caps.needsPredefinedBounds  = true;
    return true;
}

---

8. 适用场景与调优建议

场景	推荐	理由
大量物体绝大多数处于休眠	SAP	端点几乎不动，增量更新近 O(N)
大型世界（无明显空间边界）	SAP	无须 region；MBP 在无边界场景里只能划一个超大区域，退化为单 region 内部 box pruning
大量同时移动的活动对象	MBP	SAP 的 swap 数随活动数 × 平均移动距离爆炸增长
一帧内创建 / 销毁大量对象	MBP	SAP 的 batchCreate 需要 3 个轴各做一次 RadixSort + InsertEndPoints
关卡可划分为规则块状区域（房间、街区、网格）	MBP	用 PxBroadPhaseExt::createRegionsFromWorldBounds 一行代码生成；region 之间可并行
多核 CPU 上希望宽相位线性扩展	MBP	并行粒度 = region 数；SAP 的并行粒度恒为 3
角色控制器 / 大量动力学 ragdoll	MBP	同上
不希望显式管理世界边界	SAP	MBP 强制 needsPredefinedBounds=true
内存紧张、世界稀疏	SAP	没有 region 桶 / fully-inside 位图等附加结构

8.1 SAP 使用建议

• 避免一次性 addActor 巨量对象，分帧分批可以摊平 batchCreate 开销。
• 让物理 island 尽量休眠（PxRigidDynamic::setSleepThreshold 等），SAP 在休眠下接近免费。
• 若必须批量重建场景，可考虑切到 MBP。

8.2 MBP 使用建议

• Region 不宜过细（hash 冲突、跨 region 对象增多）也不宜过粗（单 region 内退化为整体 sweep）。官方注释提到的 4×4 区域是经验值。
• 让动态对象尽量只属于一个 region：跨 region 对象会被 每个 region 处理，多归属带来重复工作（但靠 hash 去重最终 pair 只有一条）。
• 借助 PxBroadPhaseExt::createRegionsFromWorldBounds 快速生成均匀 region 网格；运行时可热插拔 region（addRegion/removeRegion）。
• 对象若长期落在 region 内部不出边界，会自动进入 mFullyInsideBitmap，新 region 加入时不会被重测，几乎零开销。

9. 总结

• SAP 适合"少量东西在动、世界规模不可预知"的场景；优点是无 region 配置、休眠效率极高，缺点是全员同时大量运动 / 大批量增删时复杂度恶化、可并行度只有 3。
• MBP 适合"大量东西同时动、世界规模和边界相对清晰、需要多核扩展"的场景；优点是每帧重算几何对运动量不敏感、region 间天然可并行，缺点是必须显式定义 region 且 region 划分的好坏直接影响性能与内存。

两者通过统一的 BroadPhase 接口（BroadPhase::create 工厂方法）暴露给上层 BpSimpleAABBManager，因此切换时业务代码只需要修改 PxSceneDesc::broadPhaseType 一处即可。