Skip to content

Hierarchy in wiki:

宽阶段

title: Collision Detection 整理 2 - Broad Phase 阶段
date: 2022-03-28

介绍几种在各类代码库中应用的 Broad Phase 算法

来源包括但不限于：

  1. Unity
  2. UE
  3. Nvidia
  4. PhyX
  5. 各大博客
  6. 论文

Broad Phase Algorithms

根据 Nvidia-GPU Gems 3^1的描述，Broad Phase最主要的还是依靠一些最基础的观察来降低时间复杂度。主要的算法有：

  1. Sort and Sweep：按Axis排序，然后扫描分段，认为每一个在Axis上相邻的即可能会相交。
  2. Spatial Subdivision：空间细分算法。可以有两种主要的形式，包括固定空间划分（每个格子尺寸一致）
  3. BVH（层次包围盒 – AABB/k-DOP/OBB，更基础的还有oct-tree这些数据结构）算法。实际上固定的空间划分算法和Sort And Sweep可以互相转化。

不考虑并行的情况下，固定的空间划分算法是明显慢的。但考虑到Spatial Subdivision可以在GPU上运行，实际上这类算法也很常用。

在实际的游戏引擎中，为了达到实时的要求，使用的算法也相对简单：

  1. Sweep-based：考察物体运动所划过的面积，是否相互接触。计算TOI（impact 产生时刻），然后重新计算。 — 会增加 CPU 的负载、角速度大时会产生误差。
  2. Speculative CCD：计算运动过程中的AABB，然后对于覆盖到的物体进行针对性检查。 – maybe cheaper，但是会出现误检为collision 的问题。

其次，对于每一个物体，其也可能有针对性的优化措施，例如在Unreal Engine中，每一个物体的碰撞处理可以设置为不同的细度，从而获取不同的效果。同时其也对于输入的物体Mesh/Obj进行

  1. 凸包变换（V-HACD^2），并使用适用于凸包的 Collision Detect 来进行碰撞的判断
  2. 设置 k-DOP

无一例外，这些算法都是BVH的变体。

其他的，例如 PhysX 中，碰撞检测还可以通过光线投射（Raycast）算法计算得出。

  • 对于高速物体–低速物体的情形，可以考虑在每一次计算得到无碰撞位移后，通过Raycast算法得出运动路径上是否与其余物体有碰撞产生。

Overview of Collision in PhysX

  • Broadphase
  • AABB vs AABB, 3 axis sweep and prune
  • Midphase
  • AABB tree vs (AABB, OBB, sphere,capsule,plane, ray) – OPCODE AABB tree

对于 Narrow Phase：

  • 流体-SPH Fluids (CCD)

  • Particles vs static triangle mesh • Particles vs dynamic primitives

  • 布料-Cloth (CCD)

  • Vertices vs static triangle mesh • Vertices vs dynamic primitives

  • 刚体-Rigid body (Discrete) – GJK or SAT

  • Convex mesh and primitives vs static triangle mesh

  • Convex, primitives vs Convex, primitives

Nvidia- Sort and sweep

Sweep Method 的角速度过大，导致CCD失败

speculative ccd

考虑两种情形：

  1. 只有 Rigid Body：不可能产生自交问题，这样子的话
  2. Rigid + Deformed：Rigid肯定不会自交，但是Deformed物体可能存在自交问题、Rigid-Deformed之间可能产生相交

BVH 和 Spatial Hashing 来实现