以下为个人学习笔记整理。参考 PhysX SDK 3.4.0 文档，部分代码可能来源于更高版本。

# Collision 分享

碰撞检测常常用来计算物体之间的碰撞，在动作游戏的攻击受击、射击游戏中子弹命中等有广泛的运用。常用的检测方式有以下三种：

Overlaps：重叠检测。
Raycasts：射线检测。
Sweeps：扫描检测。

三者在检测流程上都比较接近，因此这里以 Overlaps 的检测模式来介绍一下检测流程。

# 接口说明

	bool NpSceneQueries::overlap(
	const PxGeometry& geometry, const PxTransform& pose, PxOverlapCallback& hits,
	const PxQueryFilterData& filterData, PxQueryFilterCallback* filterCall) const
	{
	// ...
	return multiQuery<PxOverlapHit>(input, hits, PxHitFlags(), NULL, filterData, filterCall, NULL);
	}

其中涉及到的几个参数：

PxGeometry：检测物体本身的几何数据，物体形状材质等信息。
PxTransform：检测物体的坐标及朝向。
PxOverlapCallback：获取碰撞检测命中结果的容器，其中会保存命中的详细检测结果如法线、坐标、距离等。
PxQueryFilterData：过滤碰撞物标记，开发者定制。
PxQueryFilterCallback：过滤处理函数，用来处理过滤规则，开发。

其中 PxQueryFilterData 和 PxQueryFilterCallback 共同实现了碰撞过滤，这个后面再说。

# 场景查询

要知道，一个场景下的物体少则上万多则上亿，每次对所有对象计算碰撞开销过大，而实际会发生碰撞的物体微乎其微，如何精确高效的筛选出可能发生碰撞的物体，从而减少检测次数提高运行效率尤为重要。PhysX 把查询分成了两个阶段 Broad Phase / Narrow Phase

# Broad Phase

该阶段主要是过滤出空间中可能发生碰撞的物体，常见的方法有三种：SAP/MBP/BVH。三者都是对物体的包围盒做碰撞检测：

# SAP

Sweep And Prune 算法。简单来说就是计算对象包围盒在各个轴的投影，然后取交集：

# MBP

Multi Box Pruning 算法。把整个场景划分为若干网格，然后把对象归入不同网格内，这样就只需要对该网格内的对象做检测即可，有点类似 AOI 里的九宫格。

另外：通常为了加速还会在每个网格内实现一次 SAP。

# BVH

Bounding Volume Hierarchy 算法，也是目前 PhysX 采用的算法。本质上是把所有对象的包围盒作为树的叶节点构建出一棵查询树结构，然后对这棵树进行查询。

PhysX 中查询结构的实现比较复杂，为了支持动态增删、多线程访问、高性能，进行了非常多的优化调整：

把场景中的对象拆分到了两个容器中存储，一个静态对象容器 (StaticPruner)，一个动态对象容器 (DynamicPruner)。
- 静态容器中的对象存放常驻且不发生位移的对象，例如不可移动的场景物件。
- 动态对象存储会创建销毁移动的场景物件、Npc、玩家等。
动态对象容器为了尽可能的节约内存又被拆解成了两个部分，RunTime && BuildTime：
- 把构建好的动态树转为静态化。因为静态结构不需要额外分配内存或者指针，存储的数据也可以尽可能压缩因此可以降低内存占用且提高查询效率。
- 双树结构分离构建和修改。由于动态树的静态化耗时很长，为了不影响性能一般会采用分帧的方式，但是如果在构建过程中有需要进行查询和变更将变得非常麻烦，因此引入了双树结构，旧的树会记录下上个时刻的快照，并把所有构建期间的修改加入到动态树中，在构建完成后替换旧的静态树，并用新的动态树构建下一次新的静态树。
- 对于聚合物体的优化，支持以树为单位建树。例如一棵树有树干和叶子等内容，它们的位置高度集中，因此可以直接视作一棵 BVH，插入到其他的 BVH 中，这种提前建好树直接插入的方式可以减少建树的耗时。

DynamicPruner 对于增量和非增量还划分了 IncrementalAABBTree && AABBTree，增量情况下的增删改介绍：

首先，每个 DynamicPruner 都是由两棵 AABBTree 和一个 ExtendedBucketPruner 组成，而 ExtendedBucketPruner 又包含两棵 IncrementalAABBTree，就像下面这样～

这里值得一提的是，AABBTree 同时只会有一棵参与工作，而 IncrementalAABBTree 两颗都会同时参与工作。

再来聊聊增删改操作吧：
- 由于 DynamicPruner 在初始状态下，AABBTree 和 IncrementalAABBTree 都只有一棵，而所有包围盒数据都会储存在 PruningPool 内，PruningPool 可以简单理解为一个数组，内部是连续的，对外是稀疏的，主要是因为外部对象通常会持有内部数据的下标，频繁删除会导致下标变化需要反复持有对象的数据，因此做了一层额外映射。回到正题，最初的包围盒数据会用于创建 CurTree（红色部分标注），之后新增的数据会插入到数组尾部，并追加到 TreeA 里（紫色）
但长此以往，TreeA 势必会越来越大，最后 CurTree 就失去价值了，因此会定时进行一次重建。但是重建非常耗时、为了保证重建过程依旧可用新增才有了 NewTree 和 TreeB。这里 TreeA 和 CurTree 的数据会被用来构建 NewTree，而构建过程中新增的数据则会存储在 TreeB，然而 NewTree 并非立刻是可用的，因此会出现 CurTree 和 TreeA && TreeB 同时工作的情况，此外构建过程中如果删除或是修改了 CurTree 或是 TreeA，由于它们都和 NewTree 共享数据，所以也是基本可以体现在 NewTree 的。

带到 NewTree 构建完成后，CurTree 和 TreeA 就失去作用了，并会在下次构建开启时重新发挥作用：

# 碰撞过滤

碰撞过滤分别在 Broad Phase 和 Narrow Phase 执行完成后工作，本质是提供给业务层的上层过滤规则。PhysX 通过 PxFilterData 四个通道标记和 PxQueryFilterCallback 的过滤接口为开发者提供了自定义筛选的可能。

# PxFilterData

	struct PxFilterData
	{
	PxU32 word0;
	PxU32 word1;
	PxU32 word2;
	PxU32 word3;
	};

# PxQueryFilterCallback

PxQueryFilterCallback 提供了两个虚函数：preFilter、postFilter。

	class PxQueryFilterCallback
	{
	public:
	virtual PxQueryHitType::Enum preFilter(
	const PxFilterData& filterData, const PxShape* shape, const PxRigidActor* actor, PxHitFlags& queryFlags) = 0;
	virtual PxQueryHitType::Enum postFilter(const PxFilterData& filterData, const PxQueryHit& hit) = 0;
	virtual ~PxQueryFilterCallback() {}
	};

这两个接口的执行时机和参数不同，也决定了用法不同：

前者负责对 Broad Phase 阶段的碰撞做筛选，由业务指定哪些碰撞「会发生」。
后者负责对 Narrow Phase 结果中的命中点做过滤。

过滤的实现还是比较简单的，但如何定制高效且易扩展的过滤模式和方法，用好 PhysX 提供的 4 个 word，压力就来到了开发者这边～🤔

# UE 中的过滤

Unreal 中定义了两种碰撞方式：Block && Touch。

Block：表示碰撞会被拦截：如人和墙壁之间的碰撞，相撞后就会被阻挡，如果看到一个物体，那么它后面的内容将被挡住。
Touch：表示碰撞但会穿过物体：如人和水、云等碰撞，如果看到一个半透明或者透明物体，那么它后面的内容也可以被看见。

这是一张碰撞关系表，只有当两个物体都具备 Block 特性的情况下，碰撞才会被拦截。

通过上图的关系，就可以引申出 word1 && word2 的定义。

Word1：在 UE4 中也被称为 BlockingBits。代表该对象会和哪些 ECollisionChannel 发生 Block 碰撞。
Word2：在 UE4 中也被称为 TouchingBits。代表该对象会和哪些 ECollisionChannel 发生 Touch 碰撞。

word0 和 word3 相对复杂一下：

word0 的含义比较复杂，在不同的查询模式下代表了不同的内容。
- Query 模式下代表 Query 类型。
- Object 模式下用于描述物体指代的 ActorID。
- Simulate 模式下标识所属于 Body 中的编号。
word3 的成分比较复杂：FMaskFilter [6] + ECollisionChannel [5] + EPhysXFilterDataFlags [21]
- 6 位用来标记掩码，给程序定义用来屏蔽某类对象的碰撞。
- 5 位用来标识该对象的通道类型。
- 21 位用来标记检测的特性标志位，不同的标记会决定使用哪种检测算法和检测模式。

# 项目组的过滤

组内的过滤规则是基于 UE4 并进行了一些调整：

word0：默认都是场景掩码，应该是场景公用规则下的过滤位。
word1：Object 模式和 Simulate 模式下用来描述对象自身的类型通道；Query 模式下表示总通道 (包括对象通道和查询通道)
word2：查询通道。
word3：Object 模式和 Simulate 模式下用来描述对象的总通道，Query 模式表示需要查询的对象通道。

	// 碰撞通道
	enum EnmCollisionChannel
	{
	// 对象通道
	ECC_OBJECT_CHANNEL_INVALID = 0x00000,
	ECC_OBJECT_CHANNEL_PLAYER = 0x00001,
	ECC_OBJECT_CHANNEL_NPC = 0x00002,
	ECC_OBJECT_CHANNEL_TERRAIN = 0x00004,
	ECC_OBJECT_CHANNEL_COVER = 0x00008,
	ECC_OBJECT_CHANNEL_TRIGGER = 0x00010,
	ECC_OBJECT_CHANNEL_PROJECTILE = 0x00020,
	ECC_OBJECT_CHANNEL_VEHICLE = 0x00040,
	ECC_OBJECT_CHANNEL_WIDGET = 0x00080,

	// 查询通道
	ECC_QUERY_CHANNEL_MOVE = 0x00100000,
	ECC_QUERY_CHANNEL_VISIABLE = 0x00200000,
	ECC_QUERY_CHANNEL_WEAPON = 0x00400000,
	ECC_QUERY_CHANNEL_DAMAGE = 0x00800000,

	ECC_OBJECT_CHANNEL_ALL = ENM_OBJECT_CHANNEL_MASK,
	ECC_QUERY_CHANNEL_ALL = ENM_QUERY_CHANNEL_MASK,
	ECC_CHANNEL_ALL = 0xFFFFFFFF
	};

# 碰撞检测

# Narrow Phase

精细检测用来进一步确认 Broad Phase 阶段的物体是否真的会发生碰撞，由于要计算出物体间的碰撞可能及碰撞点位，对于参与碰撞的对象有着严格的要求。

下面是 Overlap 操作中基于 GJK 算法可以支持检测的碰撞类型组：

	GeomOverlapTable gGeomOverlapMethodTable[] =
	{
	//PxGeometryType::eSPHERE
	{
	GeomOverlapCallback_SphereSphere, //PxGeometryType::eSPHERE
	GeomOverlapCallback_SpherePlane, //PxGeometryType::ePLANE
	GeomOverlapCallback_SphereCapsule, //PxGeometryType::eCAPSULE
	GeomOverlapCallback_SphereBox, //PxGeometryType::eBOX
	GeomOverlapCallback_SphereConvex, //PxGeometryType::eCONVEXMESH
	GeomOverlapCallback_SphereMesh, //PxGeometryType::eTRIANGLEMESH
	GeomOverlapCallback_HeightfieldUnregistered, //PxGeometryType::eHEIGHTFIELD
	},

	//PxGeometryType::ePLANE
	{
	0, //PxGeometryType::eSPHERE
	GeomOverlapCallback_NotSupported, //PxGeometryType::ePLANE
	GeomOverlapCallback_PlaneCapsule, //PxGeometryType::eCAPSULE
	GeomOverlapCallback_PlaneBox, //PxGeometryType::eBOX
	GeomOverlapCallback_PlaneConvex, //PxGeometryType::eCONVEXMESH
	GeomOverlapCallback_NotSupported, //PxGeometryType::eTRIANGLEMESH
	GeomOverlapCallback_NotSupported, //PxGeometryType::eHEIGHTFIELD
	},

	//PxGeometryType::eCAPSULE
	{
	0, //PxGeometryType::eSPHERE
	0, //PxGeometryType::ePLANE
	GeomOverlapCallback_CapsuleCapsule, //PxGeometryType::eCAPSULE
	GeomOverlapCallback_CapsuleBox, //PxGeometryType::eBOX
	GeomOverlapCallback_CapsuleConvex, //PxGeometryType::eCONVEXMESH
	GeomOverlapCallback_CapsuleMesh, //PxGeometryType::eTRIANGLEMESH
	GeomOverlapCallback_HeightfieldUnregistered, //PxGeometryType::eHEIGHTFIELD
	},

	//PxGeometryType::eBOX
	{
	0, //PxGeometryType::eSPHERE
	0, //PxGeometryType::ePLANE
	0, //PxGeometryType::eCAPSULE
	GeomOverlapCallback_BoxBox, //PxGeometryType::eBOX
	GeomOverlapCallback_BoxConvex, //PxGeometryType::eCONVEXMESH
	GeomOverlapCallback_BoxMesh, //PxGeometryType::eTRIANGLEMESH
	GeomOverlapCallback_HeightfieldUnregistered, //PxGeometryType::eHEIGHTFIELD
	},

	//PxGeometryType::eCONVEXMESH
	{
	0, //PxGeometryType::eSPHERE
	0, //PxGeometryType::ePLANE
	0, //PxGeometryType::eCAPSULE
	0, //PxGeometryType::eBOX
	GeomOverlapCallback_ConvexConvex, //PxGeometryType::eCONVEXMESH
	GeomOverlapCallback_ConvexMesh, //PxGeometryType::eTRIANGLEMESH //not used: mesh always uses swept method for midphase.
	GeomOverlapCallback_HeightfieldUnregistered, //PxGeometryType::eHEIGHTFIELD //TODO: make HF midphase that will mask this
	},

	//PxGeometryType::eTRIANGLEMESH
	{
	0, //PxGeometryType::eSPHERE
	0, //PxGeometryType::ePLANE
	0, //PxGeometryType::eCAPSULE
	0, //PxGeometryType::eBOX
	0, //PxGeometryType::eCONVEXMESH
	GeomOverlapCallback_NotSupported, //PxGeometryType::eTRIANGLEMESH
	GeomOverlapCallback_NotSupported, //PxGeometryType::eHEIGHTFIELD
	},

	//PxGeometryType::eHEIGHTFIELD
	{
	0, //PxGeometryType::eSPHERE
	0, //PxGeometryType::ePLANE
	0, //PxGeometryType::eCAPSULE
	0, //PxGeometryType::eBOX
	0, //PxGeometryType::eCONVEXMESH
	0, //PxGeometryType::eTRIANGLEMESH
	GeomOverlapCallback_NotSupported, //PxGeometryType::eHEIGHTFIELD
	},
	};

	Sphere	Plane	Capsule	Box	Convex Mesh	Triangle Mesh	HeightField
Sphere	√
Plane	√	×
Capsule	√	√	√
Box	√	√	√	√
Convex Mesh	√	√	√	√	√
Triangle Mesh	√	×	√	√	√	×
HeightField	×	×	×	×	×	×	×

# 总结

简单梳理下一次 Overlap 会做哪些事情：

【step.1】：需要构建一个特定的过滤规则，用于 preFilter。
【step.2】：对 BVH 进行查询。
- 【step.2.1】：先查询一下存放静态物体的静态树「 $O(log n)$ 」。
- 【step.2.2】：再查询一下存放动态物体的静态树和动态增量树「 $O(log n)$ + $O(log m)$ 」。
- 【step.2.3】：还需要查询一下存放聚合物体的静态树「 $O(log n)$ 」。
【step.3】：对查询结果做 preFilter「 $O(n)$ 」。
【step.4】：对所有过滤结果做 Narrow Phase「 $O(n)$ 」，Narrow Phase 本身的开销可能应该远不止 $O(n)$ 。
【step.5】：对所有命中做 postFilter「 $O(n)$ 」。
【step.6】【可能】：更具需要对所有结果做排序，取最近的命中点「 $O(nlogn)$ 」。

希望本文能够对理解基本的碰撞检测有所帮助，对 Raycast、Overlap、Sweep 操作的大致开销和内部所做的逻辑有个概念。