UE5 Chaos物理｜创建物理世界对象|算法|拓扑|新论文|spiderlinebreak

分享至

【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节点，如何合理地划分左右子树。回想在构造BVH时，有两种常用划分方法，一种是在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 ）。

近期精彩回顾

特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.