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

這是侑虎科技第1966篇文章，感謝作者南京周潤發(fā)供稿。歡迎轉(zhuǎn)發(fā)分享，未經(jīng)作者授權(quán)請勿轉(zhuǎn)載。如果您有任何獨(dú)到的見解或者發(fā)現(xiàn)也歡迎聯(lián)系我們，一起探討。（QQ群：793972859）

作者主頁：

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

物理系統(tǒng)與物理世界

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

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

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

UE5的物理引擎已經(jīng)從PhysX改成了Chaos，可能物理查詢速度會慢些，但更適合做物理破壞效果，而且數(shù)據(jù)結(jié)構(gòu)和游戲引擎統(tǒng)一，不需要再做轉(zhuǎn)換。

物理世界類

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

示例：創(chuàng)建一個StaticMeshComponent

StaticMesh的物理配置

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

UBodySetup

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

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

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

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也是它的子類。會創(chuàng)建一個FBodyInstance作為其在物理世界中的代表。無論是UStaticMeshComponent還是USkeletalMeshComponent又或者UCapsuleComponent，實(shí)際最終都會通過FBodyInstance與物理世界進(jìn)行交互。此外還有UGeometryCollectionComponent等用于特定物理功能相關(guān)的Component，它們會持有額外的物理代理。

FBodyInstance

一個物理對象的實(shí)例，在Gameplay部分的表示，用于設(shè)置物理相關(guān)的各項(xiàng)屬性。引擎代碼注釋中對FBodyInstance的定義如下：

Container for a physics representation of an object

一些屬性舉例：

• TWeakObjectPtr BodySetup：關(guān)聯(lián)的BodySetup，BodyInstance本身并不包含具體的幾何形狀。

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

• FPhysicsActorHandle ActorHandle：實(shí)際是FSingleParticlePhysicsProxy*，為物理引擎內(nèi)部BodyInstance的呈現(xiàn)與代理。

• FName CollisionProfileName：碰撞的ProfileName。

至此，StaticMeshComponent創(chuàng)建完畢，其包含了BodyInstance，并關(guān)聯(lián)了BodySetup。

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

物理對象與Shape

直觀理解，物理世界就是大量的形狀構(gòu)成的。

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

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

FPhysicsActorHandle
using FPhysicsActorHandle = Chaos::FSingleParticlePhysicsProxy*;

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

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

除此之外還有描述Chaos破壞集合的FGeometryCollectionPhysicsProxy、描述關(guān)節(jié)約束的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

用于創(chuàng)建物理數(shù)據(jù)。Component在創(chuàng)建時會執(zhí)行RegisterComponent函數(shù)，其中執(zhí)行到OnCreatePhysicsState創(chuàng)建物理數(shù)據(jù)，OnCreatePhysicsState本身是虛函數(shù)，可以被PrimitiveComponent的不同子類重載。

重載了OnCreatePhysicsState的Component：

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

UPrimitiveComponent和FPhysicsActorHandle的映射

給UPrimitiveComponent創(chuàng)建完物理對象后，和PhysicsActorHandle的映射關(guān)系會存儲在PhysScene里，用于后續(xù)查詢。

值得注意的是，Component和PhysicsActorHandle是個一對多的關(guān)系，比如一個Component里面可以創(chuàng)建多個BodyInstance，自然就有了多個PhysicsActorHandle。

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

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

創(chuàng)建Actor（Particle）

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

最終的創(chuàng)建代碼如下，StaticMesh情況比較簡單，直接創(chuàng)建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：表示位置和旋轉(zhuǎn)；FVec3 MX；FRotation3f MR；MShapesArray是Particle所包含的Shape，一個GeometryParticle完全可以包含多個形狀，如球、長方體等，只是用的不多。

MNonFrequentData指向了低頻訪問的數(shù)據(jù)。

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

創(chuàng)建不同形狀的Shape

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

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

Sphere：對應(yīng)幾何類為TSPhere，記錄了圓心坐標(biāo)和半徑。

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

Capsule：對應(yīng)類型為FCapsule，照理說應(yīng)該記錄HalfHeight、Radius和中心Transform，但小小優(yōu)化了一下，改為記錄圓柱體上下兩個點(diǎn)+Radius。

Convex：除了這些基礎(chǔ)形狀，還有能處理任意形狀的凸包，對應(yīng)類型為FConvex，里面存儲了所有頂點(diǎn)數(shù)據(jù)，是三角形的集合。下圖是為一個錐體生成的凸包。

這里例子的StaticMesh只配置了Box類型的碰撞，會創(chuàng)建TBox類型的Geometry，包含了Min和Max兩個坐標(biāo)，其實(shí)就是HalfExtend的作用。

template
class TBox final : public FImplicitObject
{
    TAABB 

 AABB; 

};
class TAABB
{
    TVector 

 MMin, MMax; 

};

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

ChaosInterface::CreateGeometry函數(shù)負(fù)責(zé)根據(jù)配置的AggGeom數(shù)據(jù)，創(chuàng)建Geometry實(shí)例，然后存入Particle中。

至此，示例中StaticMesh對應(yīng)的物理Geometry已創(chuàng)建完畢。

Simple Collision & Complex Collision

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

把上面幾個類都聯(lián)系起來，總結(jié)關(guān)系如下。

寫入物理世界

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

FChaosScene::AddActorsToScene_AssumesLocked

物理世界寫鎖

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

寫入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作為標(biāo)識。

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

寫入空間加速結(jié)構(gòu)

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

Chaos::ISpatialAccelerationCollection 
3>* SolverAccelerationStructure;

雖然是一個Interface，但實(shí)際都用的是：

它只是一個Collection，里面劃分了多個底層的加速結(jié)構(gòu)。Chaos的默認(rèn)底層加速結(jié)構(gòu)為AABBTree，它是一個類似BVH的數(shù)據(jù)結(jié)構(gòu)，但實(shí)現(xiàn)更簡單。

為什么要劃分多個AABBTree？

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

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

Bucket的劃分

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

在FPBDRigidsSolver::RegisterObject函數(shù)中，會根據(jù)這個條件設(shè)置Bucket。

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

InnerIndex的設(shè)置

查看FChaosEngineInterface::CreateActor代碼，會發(fā)現(xiàn)根據(jù)Particle的Static/Dynamic，以及是否QueryOnly，分成了四類：

Defautl是Static Tree，Dynamic是Dynamic Tree。

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

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

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

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

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

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

具體寫入了什么數(shù)據(jù)

這里立即更新物理世界的加速結(jié)構(gòu)，UpdateElement就是把Geometry插入到AABB中。

寫入數(shù)據(jù)有Payload和PayloadInfo兩部分。

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

PayloadInfo是AABBTree葉節(jié)點(diǎn)真正存儲的數(shù)據(jù)，能反向關(guān)聯(lián)到Payload和Particle，類型為FAABBTreePayloadInfo。屬性如下：

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

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

typename StorageTraits::PayloadToInfoType PayloadToInfo;

AABBTree

既然AABBTree加速結(jié)構(gòu)很重要，不妨展開分析下。

核心思想

其實(shí)和BVH類似，都是把一群AABB包圍盒，通過啟發(fā)式的規(guī)則，不斷劃分成左右兩個AABB子樹，直到每個葉節(jié)點(diǎn)包含的AABB包圍盒少于一個閾值，本質(zhì)是一棵二叉樹。

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

其對應(yīng)的二叉樹結(jié)構(gòu)如下：

至于AABBTree的具體代碼實(shí)現(xiàn)，為了效率，沒有使用動態(tài)new節(jié)點(diǎn)的方法，而是用數(shù)組來表示了二叉樹的拓?fù)洹?/p>

TArray 

 Nodes; 

TLeafContainer 

 Leaves; 

Nodes存儲了所有節(jié)點(diǎn)，每個節(jié)點(diǎn)如下：

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

當(dāng)Node是葉節(jié)點(diǎn)時，ChildrenNodes[0]指向葉節(jié)點(diǎn)下標(biāo)，否則ChildrenNodes[0]和ChildrenNodes[1]分別指向兩個子樹。

ChildrenBounds是左右子節(jié)點(diǎn)的Bounds。

TAABBTreeLeafArray

TArray 

 > Elems; 

葉子節(jié)點(diǎn)數(shù)組只存儲AABB包圍盒，會略微擴(kuò)大一點(diǎn)，DynamicTreeLeafEnlargePercent=0.1，為了給Update做一點(diǎn)開銷緩沖，避免Update太頻繁。

葉節(jié)點(diǎn)包含最多8個AABB包圍盒，葉節(jié)點(diǎn)的Bounds是它們的并集。

8是默認(rèn)值，也可以通過CVar參數(shù)改變：

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

直接向葉節(jié)點(diǎn)插入元素

InsertLeaf

把Payload和Bounds插入到AABBTree中。簡單起見，假設(shè)已經(jīng)找到了最適配的那個葉節(jié)點(diǎn)，直接插入其中。

葉節(jié)點(diǎn)有個Elements數(shù)組，打包存儲了Payload和Bounds，元素類型如下：

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

具體代碼層面的實(shí)現(xiàn)上，一個Leaf節(jié)點(diǎn)還需要一個額外的Node節(jié)點(diǎn)來輔助。

下圖為AABBTree拓?fù)涞綄?shí)際存儲結(jié)構(gòu)的示例，可以看到樹的葉節(jié)點(diǎn)，需要一個Node節(jié)點(diǎn)與一個Leaf節(jié)點(diǎn)來表示。

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

struct NodeAndLeafIndices
{
    int32 NodeIdx;
    int32 LeafIdx;
};

然后這個數(shù)據(jù)就存儲在之前的FAABBTreePayloadInfo中。

如何尋找最合適的葉節(jié)點(diǎn)

葉節(jié)點(diǎn)滿了，新建一個Node，作為Parent。

FindBestSibling

如果一顆AABBTree層數(shù)較多，那么插入一個AABB包圍盒時，需要尋找“最合適”的葉節(jié)點(diǎn)插入。

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

下面看幾個例子。

例子1，新加入AABB在原先AABBTree的BoundingBox之內(nèi)。此時經(jīng)過對比BoundingBox增加的體積，應(yīng)該加入ChildTree[1]。

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

這里Root節(jié)點(diǎn)帶來的增量相同，顯然加入ChildTree[1]更合適。

例子3，多層子節(jié)點(diǎn)情況?？磦€更復(fù)雜的多層子節(jié)點(diǎn)例子，ChildTree[0]是Leaf層，但ChildTree[1]是中間節(jié)點(diǎn)，還有ChildTree[1][0]和ChildTree[1][1]兩個子樹。

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

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

因此這里顯然應(yīng)該把新節(jié)點(diǎn)加入ChildTree[0]中。

Leaf滿了怎么辦？

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

例子2的變體：

刪除元素

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

virtual bool RemoveElement(const TPayloadType& Payload)

首先從PayloadToInfo中找到Payload所屬的節(jié)點(diǎn)下標(biāo)，然后從節(jié)點(diǎn)的Element數(shù)組里把Payload移除即可，并且把到根節(jié)點(diǎn)鏈路上的所有Bounds再更新一遍。

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

Static AABBTree

AABBTree大體上分了Dynamic Tree和Static Tree兩類，其中Dynamic Tree最貼近原生的AABBTree實(shí)現(xiàn)，增、刪、改都直接操作AABBTree即可，而Static Tree則做了不少優(yōu)化，來提升效率。因?yàn)橥ǔtatic Tree里的元素遠(yuǎn)超Dynamic Tree。

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

Static AABBTree的構(gòu)建

構(gòu)造函數(shù)中提供一個能表示AABB的數(shù)組即可，像這里的數(shù)組元素有3202個。

接著執(zhí)行GenerateTree函數(shù)來構(gòu)造AABBTree。

GenerateTree(Particles);

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

舉個二維平面的例子。

按照Max-Min的方式，應(yīng)該用X軸劃分，按照方差方式，應(yīng)該按照Y軸劃分，結(jié)果上看方差方式更優(yōu)。

然后GenerateTree的具體實(shí)現(xiàn)上，也有兩個特點(diǎn)，一是支持分幀構(gòu)建，避免突然卡一下，另一個就是全程避免遞歸和動態(tài)內(nèi)存分配了，是比較值得學(xué)習(xí)的工程實(shí)踐。

Static AABBTree刪除Payload

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

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

Static AABBTree插入Payload

插入Payload比較有意思，既要不改變AABBTree的結(jié)構(gòu)，又要插入元素。UE做法是另外創(chuàng)建了一個容器，來存儲插入的元素，而且這個容器同樣支持空間加速查詢。一種實(shí)現(xiàn)是2D Grid，另一種實(shí)現(xiàn)是再加一個Dynamic AABBTree。還是比較復(fù)雜的。

Grid實(shí)現(xiàn)

默認(rèn)用Grid實(shí)現(xiàn)，首先Payload加入DirtyElements數(shù)組，然后把整個場景劃分為2D正方形Grid，再把Payload加入到Grid數(shù)據(jù)結(jié)構(gòu)中。

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

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

Grid示意圖如下：

DirtyElementTree實(shí)現(xiàn)

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

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

AABBTree可視化

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

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

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

碰撞通道設(shè)置

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

首先需要根據(jù)ColllisionProfileName加載對應(yīng)的各個碰撞響應(yīng)，每個BodyInstance都自己存了一份CollisionProfileName和CollisionResponses，加載函數(shù)為UCollisionProfile::ReadConfig。至于為什么每個BodyInstance都要存一份，而不是用BodySetup里的，是因?yàn)檫\(yùn)行時可以動態(tài)改變單個BodyInstance的碰撞設(shè)置。

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

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

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

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

編碼過程主要由CreateShapeFilterData函數(shù)實(shí)現(xiàn)。

SourceObjectID：UPrimitiveComponent的UniqueID。

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

SimFilter：物理模擬相關(guān)信息。

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的碰撞響應(yīng)。

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

QueryComplexFilter：ComplexCollision的碰撞響應(yīng)，響應(yīng)部分和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的設(shè)置：

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

PrimitiveComponent的銷毀

Component銷毀時，需要同步的清除掉物理世界數(shù)據(jù)，主要通過FBodyInstance::TermBody函數(shù)實(shí)現(xiàn)。

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

PhysicsProxyToComponentMap和ComponentToPhysicsProxyMap。

2. 從PhysScene的加速結(jié)構(gòu)中移除

FChaosScene::RemoveActorFromAccelerationStructure

就是從AABBTree移除，先從Buckets找到對應(yīng)的AABBTree，然后調(diào)用RemoveElement移除。

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

3. 從Solver中移除

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

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

近期精彩回顧