UE5 Chaos物理｜創建物理世界對象

【USparkle專欄】如果你深懷絕技，愛“搞點研究”，樂于分享也博采眾長，我們期待你的加入，讓智慧的火花碰撞交織，讓知識的傳遞生生不息！

這是侑虎科技第1966篇文章，感謝作者南京周潤發供稿。歡迎轉發分享，未經作者授權請勿轉載。如果您有任何獨到的見解或者發現也歡迎聯系我們，一起探討。（QQ群：793972859）

作者主頁：

https://www.zhihu.com/people/xu-chen-71-65

物理系統與物理世界

物理系統是每個游戲引擎必備的功能，可以讓游戲模擬真實世界的物理規則。而現代游戲引擎中的“物理”，應該稱為剛體動力學。剛體（Rigidbody）是理想化、無限堅硬、不變形的固體物理。動力學（Dynamics）是一個過程，計算剛體怎樣在力（Force）的影響下隨時間移動及相互作用。

在游戲世界背后，有一個鏡像的物理世界，其中不關心Actor的視覺表現，只關注Actor的形狀、物理材質等信息。簡單使用場景下，只要把所有Actor當成剛體處理即可。

以常見的StaticMeshActor為例。下圖左側是Editor窗口，右側是Chaos Visual Debugger看到的物理世界。

UE5的物理引擎已經從PhysX改成了Chaos，可能物理查詢速度會慢些，但更適合做物理破壞效果，而且數據結構和游戲引擎統一，不需要再做轉換。

物理世界類

UWorld是代表由Actor構成的整個游戲世界，它持有一個FPhysScene來代表物理世界，可以類比為渲染中的FScene，物理世界的步進（Advance）初始也由UWorld::Tick()發起。UWorld與物理相關的功能一般在PhysLevel.cpp中實現。FPhysScene等價于FPhysScene_Chaos，繼承自FChaosScene，是Chaos的首要入口。碰撞事件的注冊分發，物理網絡同步相關的內容也由其處理，物理模擬的步進也在該類開始（StartFrame）。

示例：創建一個StaticMeshComponent

StaticMesh的物理配置

編輯器中，可以給StaticMesh設置碰撞，這里直接使用和模型大小一樣的Box碰撞即可。還有其他很多選項，如Sphere、Capsule、凸包等，面對復雜模型時會用多種基礎形狀拼出一個碰撞。

UBodySetup

這些碰撞配置，最終會存儲到UBodySetup類里，作為資源的一部分，它會是StaticMesh的一個配置項。對于例子中添加的簡單幾何體碰撞，存儲在其AggGeom變量中。

class UBodySetup : public UBodySetupCore
{
    //...
    /** Simplified collision representation of this  */
    UPROPERTY(EditAnywhere, Category = BodySetup, meta=(DisplayName = "Primitives", NoResetToDefault))
    struct FKAggregateGeom AggGeom;
    //...
};

AggGeom里是一大串幾何體的數據，Box就位于BoxElems數組里。

struct FKAggregateGeom
{
    GENERATED_USTRUCT_BODY()
    UPROPERTY(EditAnywhere, editfixedsize, Category = "Aggregate Geometry", meta = (DisplayName = "Spheres", TitleProperty = "Name"))
    TArray 

 SphereElems; 

    UPROPERTY(EditAnywhere, editfixedsize, Category = "Aggregate Geometry", meta = (DisplayName = "Boxes", TitleProperty = "Name"))
    TArray 

 BoxElems; 

    UPROPERTY(EditAnywhere, editfixedsize, Category = "Aggregate Geometry", meta = (DisplayName = "Capsules", TitleProperty = "Name"))
    TArray 

 SphylElems; 

    UPROPERTY(EditAnywhere, editfixedsize, Category = "Aggregate Geometry", meta = (DisplayName = "Convex Elements", TitleProperty = "Name"))
    TArray 

 ConvexElems; 

    UPROPERTY(EditAnywhere, editfixedsize, Category = "Aggregate Geometry", meta = (DisplayName = "Tapered Capsules", TitleProperty = "Name"))
    TArray 

 TaperedCapsuleElems; 

    UPROPERTY(EditAnywhere, editfixedsize, Category = "Aggregate Geometry", meta = (DisplayName = "Level Sets", TitleProperty = "Name"))
    TArray 

 LevelSetElems; 

    UPROPERTY(EditAnywhere, editfixedsize, Category = "Aggregate Geometry", meta = (DisplayName = "(Experimental) Skinned Level Sets", TitleProperty = "Name"), Experimental)
    TArray 

 SkinnedLevelSetElems; 

    UPROPERTY(EditAnywhere, editfixedsize, Category = "Aggregate Geometry", meta = (DisplayName = "(Experimental) ML Level Sets", TitleProperty = "Name"), Experimental)
    TArray 

 MLLevelSetElems; 

    UPROPERTY(EditAnywhere, editfixedsize, Category = "Aggregate Geometry", meta = (DisplayName = "(Experimental) Skinned Triangle Meshes", TitleProperty = "Name"), Experimental)
    TArray 

 SkinnedTriangleMeshElems; 

};

UPrimitiveComponent

UPrimitiveComponent為所有持有幾何物體的基類，StaticMeshComponent也是它的子類。會創建一個FBodyInstance作為其在物理世界中的代表。無論是UStaticMeshComponent還是USkeletalMeshComponent又或者UCapsuleComponent，實際最終都會通過FBodyInstance與物理世界進行交互。此外還有UGeometryCollectionComponent等用于特定物理功能相關的Component，它們會持有額外的物理代理。

FBodyInstance

一個物理對象的實例，在Gameplay部分的表示，用于設置物理相關的各項屬性。引擎代碼注釋中對FBodyInstance的定義如下：

Container for a physics representation of an object

一些屬性舉例：

• TWeakObjectPtr BodySetup：關聯的BodySetup，BodyInstance本身并不包含具體的幾何形狀。

• FBodyInstance* WeldParent：一個BodyInstance所連接的父Body。

• FPhysicsActorHandle ActorHandle：實際是FSingleParticlePhysicsProxy*，為物理引擎內部BodyInstance的呈現與代理。

• FName CollisionProfileName：碰撞的ProfileName。

至此，StaticMeshComponent創建完畢，其包含了BodyInstance，并關聯了BodySetup。

簡單理解的話，StaticMeshComponent包含了Render和物理信息，而BodySetup+BodyInstance就表示物理信息。

物理對象與Shape

直觀理解，物理世界就是大量的形狀構成的。

物理世界如何表示"對象"

Game世界使用Actor、Component等類型來表示一個對象，但物理世界只關注一個物體的幾何形狀、位置、以及質量等屬性，它們構成了另一套PhysScene里的數據結構，以及PhysScene里的“對象”。這個對象稱為GeometryParticle，Game世界通過FPhysicsActorHandle類型來索引它。

FPhysicsActorHandle
using FPhysicsActorHandle = Chaos::FSingleParticlePhysicsProxy*;

看聲明代碼，等價于FSingleParticlePhysicsProxy*，既然叫XXProxy，那就是一個代理的作用。一個需要進行物理解算的對象在物理引擎內被稱為一個Particle，是一個約定俗成的名字，該類作為其代理充當與物理交互的接口。物理引擎只關注一個物體的幾何形狀、位置、以及質量等屬性，它們由TGeometryParticle持有。PhysicsActorHandle的TGeometryParticleHandle屬性指向了GeometryParticle，實現關聯。不僅如此，TGeometryParticle內部還有一個指向更底層物理SOA存儲的FGeometryParticleHandle，暫時用不到，先不管。概念比較多，之后會做總結。

注意，目前都只涉及物理世界，但不涉及物理線程。游戲線程和物理線程都可以讀寫物理世界，但物理線程主要負責物理模擬。

除此之外還有描述Chaos破壞集合的FGeometryCollectionPhysicsProxy、描述關節約束的FJointConstraintPhysicsProxy等。

FSingleParticlePhysicsProxy的屬性：

TUniquePtr 

 Particle; 

FParticleHandle* Handle;
FPhysicsObjectUniquePtr Reference;
int32 GravityGroupIndex;
TUniquePtr 

 InterpolationData; 

GetGameThreadAPI()是GameThread獲取操作類的方法，直接cast即可：

FORCEINLINE FRigidBodyHandle_External& GetGameThreadAPI()
{
    return (FRigidBodyHandle_External&)*this;
}

UPrimitiveComponent::OnCreatePhysicsState

用于創建物理數據。Component在創建時會執行RegisterComponent函數，其中執行到OnCreatePhysicsState創建物理數據，OnCreatePhysicsState本身是虛函數，可以被PrimitiveComponent的不同子類重載。

重載了OnCreatePhysicsState的Component：

而其中主要邏輯都在FBodyInstance::InitBody函數里，最終執行到FInitBodiesHelperBase::InitBodies。

UPrimitiveComponent和FPhysicsActorHandle的映射

給UPrimitiveComponent創建完物理對象后，和PhysicsActorHandle的映射關系會存儲在PhysScene里，用于后續查詢。

值得注意的是，Component和PhysicsActorHandle是個一對多的關系，比如一個Component里面可以創建多個BodyInstance，自然就有了多個PhysicsActorHandle。

一個例子是SkeletalMeshComponent，會有多個剛體組成。

/** Array of FBodyInstance objects, storing per-instance state about about each body. */
TArray Bodies;

創建Actor（Particle）

這里Actor是PhysX遺留的術語，可以視為物理場景中的一個對象，基本等價于Particle，也即前文的TGeometryParticle。這里的Particle和下文的Shapes都在CreateShapesAndActors函數中創建。

最終的創建代碼如下，StaticMesh情況比較簡單，直接創建TGeometryParticle即可：

void FChaosEngineInterface::CreateActor(const FActorCreationParams& InParams,FPhysicsActorHandle& Handle, UObject* InOwner)
{
    TUniquePtr 

 Particle; 

    // Set object state based on the requested particle type
    if(InParams.bStatic)
    {
        Particle = FGeometryParticle::CreateParticle();
        Particle->SetResimType(EResimType::ResimAsFollower);
    }
    //...
}

TGeometryParticle的屬性如下：

TChaosProperty 

 MXR; 

TChaosProperty 

 MNonFrequentData; 

void* MUserData;
FShapeInstanceProxyArray MShapesArray;
EParticleType Type;
FDirtyChaosPropertyFlags MDirtyFlags;

MXR：表示位置和旋轉；FVec3 MX；FRotation3f MR；MShapesArray是Particle所包含的Shape，一個GeometryParticle完全可以包含多個形狀，如球、長方體等，只是用的不多。

MNonFrequentData指向了低頻訪問的數據。

有了Particle，隨之就能創建PhysicsActorHandle了，把剛創建的FGeometryParticle指針存入即可。

創建不同形狀的Shape

Shape為一個幾何體，它包含碰撞、幾何與物理材質等數據，一個Particle可以有多個Shape。

Shape的形狀描述都在AggGeom里，總共有以下幾種基礎形狀：

Sphere：對應幾何類為TSPhere，記錄了圓心坐標和半徑。

Box：對應幾何類為TBox，記錄了Box的HalfExtent和中心Transform。

Capsule：對應類型為FCapsule，照理說應該記錄HalfHeight、Radius和中心Transform，但小小優化了一下，改為記錄圓柱體上下兩個點+Radius。

Convex：除了這些基礎形狀，還有能處理任意形狀的凸包，對應類型為FConvex，里面存儲了所有頂點數據，是三角形的集合。下圖是為一個錐體生成的凸包。

這里例子的StaticMesh只配置了Box類型的碰撞，會創建TBox類型的Geometry，包含了Min和Max兩個坐標，其實就是HalfExtend的作用。

template
class TBox final : public FImplicitObject
{
    TAABB 

 AABB; 

};
class TAABB
{
    TVector 

 MMin, MMax; 

};

然后對TBox再包一下，加上Box的Transform數據，生成ImplicitObjectTransformed對象。

ChaosInterface::CreateGeometry函數負責根據配置的AggGeom數據，創建Geometry實例，然后存入Particle中。

至此，示例中StaticMesh對應的物理Geometry已創建完畢。

Simple Collision & Complex Collision

通常一個對象會有簡單&復雜兩套碰撞，就需要分別創建兩個Shape和Geometry。勾選UseSimpleAsComplex則只用一套，但不建議這么做。

把上面幾個類都聯系起來，總結關系如下。

寫入物理世界

目前為止，只是創建了Particle、Shape等數據，還需要把它們注冊到物理世界中，就像把Actor注冊到UWorld。

FChaosScene::AddActorsToScene_AssumesLocked

物理世界寫鎖

首先物理世界會被多線程同時讀取與寫入，因此是個讀寫鎖的場景，寫入時需要加寫鎖，通過FPhysicsCommand::ExecuteWrite函數實現，執行到這時可能會阻塞在等待鎖上。

寫入Solver

Solver即為FPBDRigidsSolver，管理了物理世界所有Particle，如此理解即可，寫入代碼如下：

FPBDRigidsSolver::RegisterObject
RigidBody_External.SetUniqueIdx(GetEvolution()->GenerateUniqueIdx());
TrackGTParticle_External(*Proxy->GetParticle_LowLevel());    //todo: remove this

 Proxy->SetSolver(this);
Proxy->GetParticle_LowLevel()->SetProxy(Proxy);
AddDirtyProxy(Proxy);

 UpdateParticleInAccelerationStructure_External(Proxy->GetParticle_LowLevel(), EPendingSpatialDataOperation::Add);

然后Particle會被賦予一個UniqueIdx作為標識。

RigidBody_External.SetUniqueIdx(GetEvolution()->GenerateUniqueIdx());

寫入空間加速結構

這是一個重點。物理世界中有大量的幾何體，為了支持射線檢測、碰撞查詢、物理模擬等功能，必然要用到空間加速結構。這就是FChaosScene類中的SolverAccelerationStructure屬性。

Chaos::ISpatialAccelerationCollection 
3>* SolverAccelerationStructure;

雖然是一個Interface，但實際都用的是：

它只是一個Collection，里面劃分了多個底層的加速結構。Chaos的默認底層加速結構為AABBTree，它是一個類似BVH的數據結構，但實現更簡單。

為什么要劃分多個AABBTree？

整個物理場景使用一個超大的AABBTree來管理并不合適，元素多了效率會很低。所以分多個AABBTree子樹是合理的，劃分依據并不是空間遠近，而是Particle的Static/Movable屬性、QueryOnly/QueryAndPhysics屬性等，大方向是劃分了Static Tree和Dynamic Tree。因為Static Tree是很少做更新的，Particle移動時，更新單獨的Dynamic Tree效率更高。Particle的SpatialAccelerationIdx屬性就表示它屬于哪一個AABBTree，有16位，能表示8個Bucket，每個Bucket又有最多8192個AABBTree，但目前遠沒有用這么多，實際默認用了四個，最多能支持到8個。

struct FSpatialAccelerationIdx
{
    uint16 Bucket : 3;
    uint16 InnerIdx : 13;
}

Bucket的劃分

對于Bucket的劃分，只有兩種，一個是0，即默認的，另一個是1，當AABB的包圍盒過大時會放到Bucket 1里。這個包圍盒閾值默認為100米。

在FPBDRigidsSolver::RegisterObject函數中，會根據這個條件設置Bucket。

為什么超大AABB要單獨劃分？如果超大Particle和小Particle存儲在一棵樹中，會導致查詢效率變低。想象一個葉節點包含了一個超大Particle和若干小Particle，那么做射線檢測時，很容易與這個葉節點相交，但做逐Particle判斷時，大概率只和這個超大Particle相交，小Particle的射線檢測就都浪費了。

InnerIndex的設置

查看FChaosEngineInterface::CreateActor代碼，會發現根據Particle的Static/Dynamic，以及是否QueryOnly，分成了四類：

Defautl是Static Tree，Dynamic是Dynamic Tree。

Static Tree會存儲靜態對象，如場景中的樹木、石頭、房屋等。

例子中，Box的屬性是Static+QueryOnly，因此InnerIndex被設置成了ESpatialAccelerationCollectionBucketInnerIdx::DefaultQueryOnly。

Dynamic Tree存儲會移動的對象，如角色、載具、電梯。

DefaultQueryOnly是對Static Tree再細分出Query Only的Particle，DynamicQueryOnly類似，但目前沒啟用，通過p.Chaos.AccelerationStructureIsolateQueryOnlyObjects參數開啟。

通過Bucket和InnerIndex劃分AABBTree的示意圖如下：

例子中，Box的屬性是Static+QueryOnly，因此InnerIndex被設置成了DefaultQueryOnly。

具體寫入了什么數據

這里立即更新物理世界的加速結構，UpdateElement就是把Geometry插入到AABB中。

寫入數據有Payload和PayloadInfo兩部分。

Payload更像Key，類型是FAccelerationStructureHandle，包含Particle指針、UniqueIdx、FilterData等數據。

PayloadInfo是AABBTree葉節點真正存儲的數據，能反向關聯到Payload和Particle，類型為FAABBTreePayloadInfo。屬性如下：

struct FAABBTreePayloadInfo
{
    int32 GlobalPayloadIdx;         // GlobalPayloads里單獨存的NodeIndex，沒有BoundingBox
    int32 DirtyPayloadIdx;          // 單獨的DirtyElementTree里的NodeIdx
    int32 LeafIdx;                  // 常見情況，Leaf Node的Index
    int32 DirtyGridOverflowIdx;     // 用Dirty Grid而不是DirtyElementTree時，overflow的Index，少見情況
    int32 NodeIdx;                  // 常見情況，Tree Node的Index
}

最終Payload和PayloadInfo會存在PayloadToInfo這個Map里，其實是個數組，通過UniqueIndex索引，模擬成了Map。

typename StorageTraits::PayloadToInfoType PayloadToInfo;

AABBTree

既然AABBTree加速結構很重要，不妨展開分析下。

核心思想

其實和BVH類似，都是把一群AABB包圍盒，通過啟發式的規則，不斷劃分成左右兩個AABB子樹，直到每個葉節點包含的AABB包圍盒少于一個閾值，本質是一棵二叉樹。

以2D情況為例，AABB樹的非葉節點，會把葉節點的AABB給取并集，作為自己的AABB，葉子節點則包含了一定數量的AABB對象。下面Root的Child[1]節點就是葉子節點。

其對應的二叉樹結構如下：

至于AABBTree的具體代碼實現，為了效率，沒有使用動態new節點的方法，而是用數組來表示了二叉樹的拓撲。

TArray 

 Nodes; 

TLeafContainer 

 Leaves; 

Nodes存儲了所有節點，每個節點如下：

struct TAABBTreeNode
{
    TAABB 
3> ChildrenBounds[2];
    int32 ChildrenNodes[2];
    int32 ParentNode;
    bool bLeaf : 1;
    bool bDirtyNode : 1;
};

當Node是葉節點時，ChildrenNodes[0]指向葉節點下標，否則ChildrenNodes[0]和ChildrenNodes[1]分別指向兩個子樹。

ChildrenBounds是左右子節點的Bounds。

TAABBTreeLeafArray

TArray 

 > Elems; 

葉子節點數組只存儲AABB包圍盒，會略微擴大一點，DynamicTreeLeafEnlargePercent=0.1，為了給Update做一點開銷緩沖，避免Update太頻繁。

葉節點包含最多8個AABB包圍盒，葉節點的Bounds是它們的并集。

8是默認值，也可以通過CVar參數改變：

int32 FAABBTreeCVars::DynamicTreeLeafCapacity = 8;
FAutoConsoleVariableRef FAABBTreeCVars::CVarDynamicTreeLeafCapacity(TEXT("p.aabbtree.DynamicTreeLeafCapacity"), FAABBTreeCVars::DynamicTreeLeafCapacity, TEXT("Dynamic Tree Leaf Capacity"));

直接向葉節點插入元素

InsertLeaf

把Payload和Bounds插入到AABBTree中。簡單起見，假設已經找到了最適配的那個葉節點，直接插入其中。

葉節點有個Elements數組，打包存儲了Payload和Bounds，元素類型如下：

struct TPayloadBoundsElement
{
    TPayloadType Payload;
    TAABB 
3> Bounds;
};

具體代碼層面的實現上，一個Leaf節點還需要一個額外的Node節點來輔助。

下圖為AABBTree拓撲到實際存儲結構的示例，可以看到樹的葉節點，需要一個Node節點與一個Leaf節點來表示。

插入完成后，會返回Particle在AABBTree中的索引，索引由Node數組下標和Leaf數組下標兩部分組成，類型是NodeAndLeafIndices。

struct NodeAndLeafIndices
{
    int32 NodeIdx;
    int32 LeafIdx;
};

然后這個數據就存儲在之前的FAABBTreePayloadInfo中。

如何尋找最合適的葉節點

葉節點滿了，新建一個Node，作為Parent。

FindBestSibling

如果一顆AABBTree層數較多，那么插入一個AABB包圍盒時，需要尋找“最合適”的葉節點插入。

何謂“最合適”，加入新AABB，通常會使一些ChildNode的BoundingBox變大，需要使BoundingBox增加的體積盡量小，以此來判定“最合適”。這是一種啟發式的方法，認為BoundingBox大小直接影響到AABBTree查詢的效率，類似構建BVH使用的SAH表面積啟發算法。這個尋找過程稱為“FindBestSibling”。

下面看幾個例子。

例子1，新加入AABB在原先AABBTree的BoundingBox之內。此時經過對比BoundingBox增加的體積，應該加入ChildTree[1]。

例子2，新加入AABB在原先AABBTree的BoundingBox之外。此時不僅要考慮分別加入ChildTree[0]和ChildTree[1]所增加的體積，還要考慮加入AABBTree的Root節點增加的體積，把從Root節點到葉節點的所有增量都加起來。為什么要相加？推測是模擬運行時查找的情況，每一層的查找開銷是疊加的。

這里Root節點帶來的增量相同，顯然加入ChildTree[1]更合適。

例子3，多層子節點情況�？磦�更復雜的多層子節點例子，ChildTree[0]是Leaf層，但ChildTree[1]是中間節點，還有ChildTree[1][0]和ChildTree[1][1]兩個子樹。

對于ChildTree[0]，直接計算加入后的額外空間即可。

對于ChildTree[1]的兩個子樹，先要計算與ChildTree[1]產生的額外空間，再計算與兩個子樹的額外空間，最后都加起來。

因此這里顯然應該把新節點加入ChildTree[0]中。

Leaf滿了怎么辦？

當BestSibling找到的葉節點已經滿了，就無法直接添加，需要再新增兩個Node，一個作為中間節點，另一個作為新的Leaf。之后同樣要更新Leaf到根節點路徑上所有Parent的BoundingBox。

例子2的變體：

刪除元素

與插入元素對應的，就是刪除元素了，刪除邏輯會簡單很多。

virtual bool RemoveElement(const TPayloadType& Payload)

首先從PayloadToInfo中找到Payload所屬的節點下標，然后從節點的Element數組里把Payload移除即可，并且把到根節點鏈路上的所有Bounds再更新一遍。

但是特別的，當葉節點刪除Payload后整個都空了，就要精簡一下AABB樹了，把Parent節點和自己都刪掉，然后Parent節點的位置放Sibling節點即可。

Static AABBTree

AABBTree大體上分了Dynamic Tree和Static Tree兩類，其中Dynamic Tree最貼近原生的AABBTree實現，增、刪、改都直接操作AABBTree即可，而Static Tree則做了不少優化，來提升效率。因為通常Static Tree里的元素遠超Dynamic Tree。

“Static”并不意味著不更新，比如可以把石頭先改成Movable移動，再改回Static等等。Static Tree的構建總是先提供所有AABB對象，一次性建好，之后也能繼續添加/刪除/修改Payload，但樹節點結構不實時改變，只會重建。

Static AABBTree的構建

構造函數中提供一個能表示AABB的數組即可，像這里的數組元素有3202個。

接著執行GenerateTree函數來構造AABBTree。

GenerateTree(Particles);

一次性構造一整棵樹有個好處，就是能讓左右子樹盡量空間上均衡，提升之后的查找效率。如果是Dynamic那樣一個一個節點的插入，樹的質量和節點插入順序是有關系的。那么重點就是對于一群AABB節點，如何合理地劃分左右子樹�；叵朐跇嬙霣VH時，有兩種常用劃分方法，一種是在XYZ三個方向里選取Max-Min最大的一個作為劃分軸，然后取中點劃分；另一種是SAH表面積啟發算法，同樣是考慮XYZ三個軸，但在每個軸上要計算多種表面積劃分組合，再選取某個能使Cost最小的位置做劃分，計算量更大，但效果也更好。UE的AABBTree使用了更接近前者的簡單做法，但不會取Max-Min最大的作為劃分軸，而是計算每個軸上AABB 中心點形成的方差，取方差最大的軸作為劃分軸。計算中心點和方差的代碼如下，使用了流式數據常用的Welford算法。

舉個二維平面的例子。

按照Max-Min的方式，應該用X軸劃分，按照方差方式，應該按照Y軸劃分，結果上看方差方式更優。

然后GenerateTree的具體實現上，也有兩個特點，一是支持分幀構建，避免突然卡一下，另一個就是全程避免遞歸和動態內存分配了，是比較值得學習的工程實踐。

Static AABBTree刪除Payload

如果Static AABBTree要刪除Payload，過程反而更簡單，直接從Leaves數組中移除Payload即可，不用考慮樹的坍縮，也不用更新整個樹節點鏈路上的AABB包圍盒。

然后標記ShouldRebuild為true，等待后面一起更新樹，見PBDRigidsEvolution.cpp文件。

Static AABBTree插入Payload

插入Payload比較有意思，既要不改變AABBTree的結構，又要插入元素。UE做法是另外創建了一個容器，來存儲插入的元素，而且這個容器同樣支持空間加速查詢。一種實現是2D Grid，另一種實現是再加一個Dynamic AABBTree。還是比較復雜的。

Grid實現

默認用Grid實現，首先Payload加入DirtyElements數組，然后把整個場景劃分為2D正方形Grid，再把Payload加入到Grid數據結構中。

Grid的每個Cell大小為CVarDirtyElementGridCellSize，默認1000，如果一個Payload和某個Cell重疊，該Cell就會把Payload的DirtyPayloadIndx記下來。

但Grid也有大小限制和容量限制。首先，Payload所覆蓋的Cell不能過多，即Payload的AABB不能過大，然后每個Cell重疊的Payload數量不能過多，不然都會影響效率。目前前者配置是16，后者配置是32。如果超過了限制，Payload就要被加入到單獨的DirtyElementsGridOverflow數組，并把下標記錄在PayloadInfo中，后續也會單獨查詢。

Grid示意圖如下：

DirtyElementTree實現

新加的AABBTree稱為DirtyElementTree，Payload插入完成后，PayloadInfo會存儲其在DirtyTree中的Node下標。

如此一來，Grid/DirtyElementTree就是Static AABBTree的一部分了，往后的增/刪/改Payload，以及AABBTree做碰撞查詢，都要額外考慮它們。后面AABBTree重建了，再清空Grid/DirtyElementTree。

AABBTree可視化

最后，可以讀取AABBTree的所有元素，并畫出來，看下AABBTree都是什么樣。

遍歷PhysicsScene的SolverAccelerationStructure屬性即可，可以看到整個AABBTree還是比較復雜的。

尤其是中間角色，有多個BodyInstance。

碰撞通道設置

一個PrimitiveComponent，不僅包含幾何信息，還可以配置它的碰撞通道、ObjectType、CollisionType等信息，這些設置都會影響到PrimitiveComponent的物理表現。比如例子中的StaticMeshComponent，默認的ObjectType為WorldStatic，然后對所有CollisionResponses的響應都是Block。

首先需要根據ColllisionProfileName加載對應的各個碰撞響應，每個BodyInstance都自己存了一份CollisionProfileName和CollisionResponses，加載函數為UCollisionProfile::ReadConfig。至于為什么每個BodyInstance都要存一份，而不是用BodySetup里的，是因為運行時可以動態改變單個BodyInstance的碰撞設置。

此時這些碰撞設置還是一堆Bool和Enum，對于底層物理引擎存儲不太方便，因此要把它們進行編碼，最終會存入四個int32，用FCollisionFilterData表示。

struct FCollisionFilterData
{
    uint32 Word0;
    uint32 Word1;
    uint32 Word2;
    uint32 Word3;
};

在CreateShapes函數中，會對碰撞數據進行編碼，并且生成三個FCollisionFilterData實例，存儲不同用途的物理碰撞信息。

/** Helper struct holding physics body filter data during initialisation */
struct FBodyCollisionFilterData
{
    FCollisionFilterData SimFilter;
    FCollisionFilterData QuerySimpleFilter;
    FCollisionFilterData QueryComplexFilter;
};

編碼過程主要由CreateShapeFilterData函數實現。

SourceObjectID：UPrimitiveComponent的UniqueID。

InstanceBodyIndex：這是UPrimitiveComponent里的第幾個BodyInstance，比如常見的SkeletalMeshComponent有多個BodyInstance。

SimFilter：物理模擬相關信息。

inline void GetSimData(uint32 BodyIndex, uint32 ComponentID, uint32& OutWord0, uint32& OutWord1, uint32& OutWord2, uint32& OutWord3) const
{
    OutWord0 = BodyIndex;
    OutWord1 = BlockingBits;
    OutWord2 = ComponentID;
    OutWord3 = Word3;
}

QuerySimpleFilter：SimpleCollision的碰撞響應。

inline void GetQueryData(uint32 SourceObjectID, uint32& OutWord0, uint32& OutWord1, uint32& OutWord2, uint32& OutWord3) const
{
    OutWord0 = SourceObjectID;
    OutWord1 = BlockingBits;
    OutWord2 = TouchingBits;
    OutWord3 = Word3;
}

QueryComplexFilter：ComplexCollision的碰撞響應，響應部分和Simple是一樣的。

// Build filterdata variations for complex and simple
SimpleQueryData.Word3 |= EPDF_SimpleCollision;
if (bUseSimpleAsComplex)
{
    SimpleQueryData.Word3 |= EPDF_ComplexCollision;
}
ComplexQueryData.Word3 |= EPDF_ComplexCollision;
if (bUseComplexAsSimple)
{
    ComplexQueryData.Word3 |= EPDF_SimpleCollision;
}
OutFilterData.QuerySimpleFilter = SimpleQueryData;
OutFilterData.QueryComplexFilter = ComplexQueryData;

Word3的設置：

inline uint32 CreateChannelAndFilter(ECollisionChannel CollisionChannel, FMaskFilter MaskFilter)
{
    uint32 ResultMask = (uint32(MaskFilter) << NumCollisionChannelBits) | (uint32)CollisionChannel;
    return ResultMask << NumFilterDataFlagBits;
}

PrimitiveComponent的銷毀

Component銷毀時，需要同步的清除掉物理世界數據，主要通過FBodyInstance::TermBody函數實現。

1. 從PhysScene的幾個容器里移除

PhysicsProxyToComponentMap和ComponentToPhysicsProxyMap。

2. 從PhysScene的加速結構中移除

FChaosScene::RemoveActorFromAccelerationStructure

就是從AABBTree移除，先從Buckets找到對應的AABBTree，然后調用RemoveElement移除。

最終進入AABBTree的RemoveElement函數，根據DynamicTree屬性、使用Grid還是DirtyElementTree等情況，做移除。

3. 從Solver中移除

FPBDRigidsSolver::UnregisterObject，物理模擬信息的刪除。

文末，再次感謝南京周潤發的分享， 作者主頁：https://www.zhihu.com/people/xu-chen-71-65， 如果您有任何獨到的見解或者發現也歡迎聯系我們，一起探討。（QQ群： 793972859 ）。

近期精彩回顧