zhouqijie

概述：碰撞检测

碰撞检测的主要用途是判断游戏世界的物体是否接触(contact)。每个逻辑对象会以一个或者多个几何形状代表。碰撞系统判断在某指定时刻这些图形是否相交。所以碰撞系统本质上是几何相交测试器。但是碰撞系统不仅要判断图形是否相交，也要提供接触的相关信息。

1.可碰撞实体

希望某个逻辑对象和其他对象碰撞，需要为该对象提供一个碰撞表达形式，区分于对象的游戏性表达形式和视觉表达形式。

从检测相交的角度来说，通常希望形状在几何和数学上是简单的，例如石头建模为球形、人体建模成一组胶囊体(capsule)。只有当简单的表达形式无法达到需求时，才会使用更复杂的形状。

Cre：在Unity中碰撞表达形式对应Collider组件、游戏性表达形式对应Script组件、视觉表达形式对应MeshRenderer组件。
Havok采用可碰撞体(collidable)一词来描述一个参与碰撞检测的独立刚体，使用hkpCollidable类实例表示每个可碰撞体。
PhysX采用演员(actor)一词描述它的刚体，用NxActor类实例表示。

变换：

可碰撞实体不仅要包含形状还要包含变换，原因有三：

  1. 形状通常以位于原点的中心来定义，并且对齐坐标轴，需要变换使其合适地放置及转向于世界空间中。
  2. 动态对象移动时。如果只有形状没有变换，需要把形状的顶点或面逐一移动才能移动形状，那是很耗时的操作。
  3. 可以实现同一形状的重复使用（共享）。

Cre：Unity的组件模型使得Collider组件直接使用Transfrom组件的变换（Collider自己也有偏移属性）。




2.物理世界

碰撞世界：

碰撞系统通常通过一个名为碰撞世界(collision world)的数据结构，管理所有的可碰撞实体。碰撞世界是专门为碰撞检测而设的游戏世界完整表达方式。

Havok的碰撞世界是hkpWorld类实例，Physx的碰撞世界是NxScene类实例，ODE使用dSpace类实例表示碰撞世界。

相比把碰撞信息存储在游戏对象，把所有碰撞信息维护于独立的数据结构的优点：

  1. 碰撞世界只包含可碰撞体，能高效组织数据，优化缓冲一致性。
  2. 碰撞世界是一个有效的封装机制，对于可理解性、可维护性、可测试性、可重用性都有帮助。

物理世界：

如果游戏含有刚体动力学系统，该系统通常会紧密地和碰撞系统整合。动力学系统可能会和碰撞系统共享一个”世界”数据结构，并把刚体关联至碰撞体。
这种设计是因为通常是物理系统驱动碰撞系统的运作，物理系统每个模拟时步中指挥碰撞系统一次或者多次碰撞测试。所以碰撞世界有时称为物理世界。
尽管这是一个紧密的整合，但是大多数物理SDK都会尝试分离碰撞库和刚体动力学模拟，这样做可以把碰撞系统作为独立库使用。

在Havok中，每个hkpRigidBody类实例都含有一个指针指向一个hkpColliable。
在PhysX中，可碰撞体和刚体两个概念混合在一起，用NxActor类兼具两个用途，虽然刚体物理性质是分开存储在NxBodyDesc的。
两个SDK都可以令一个刚体的位置定向固定于空间，让它不参与动力学模拟，仅作为碰撞体。

Cre：在Unity中设置刚体的IsKinematic来使其固定不参与动力学模拟。




3.关于形状

形状可以理解为一个由边界所指明的空间区域，能清楚地界定形状之内和之外。
有些游戏对象类型比如地形和水体，最好用表面(surface)表示，表面没有内外之分只有前后之分，碰撞库通常会提供挤压(extrusion)，使表面拥有体积，帮助减少细小高速物体错失碰撞的情况。

相交(Intersection)：

相交/交集(intersction)是集合论概念。在几何学上两个形状的交集仅仅是同时位于两个形状中所有点的无穷大集合。

接触(Contact)：

在游戏中我们通常不会要求严格意义上的点集合表示的交集，我们只希望得知两个物体是否相交。

碰撞事件发生时，碰撞系统会提供额外的接触信息，通常会把接触信息打包成方便的数据结构。接触信息一般会包含一个分离矢量(sparating-vector)，把物体沿这个矢量移动就能高效地脱离碰撞。接触信息一般还会包含碰撞体的形状、碰撞体投影在分离矢量上的速度等。

凸性(Convex)：

技术上来说，凸形状的定义是由形状内发射的射线不会穿越形状两次或以上。

凸性是很重要的属性，凸形状之间检测相交，一般比凹形状需要的运算少。




4.碰撞原型

碰撞检测系统只能支持有限的形状类型，称为碰撞原型(collision primitive)，这些形状可以组成更复杂的形状。

Ye：碰撞检测中不一定要用一个完全原物体的包围体积，只需逼近即可。但是在可见性判断中，必须构建完全包围原物体的包围体积。

球体(sphere)

球体是最高效的碰撞原型。球可以由球心和半径表示，打包到一个四维浮点向量中，对SIMD数学库能运作得特别好。

胶囊体(capsult)

胶囊体通常是由两点和半径表示的。计算胶囊体的相交比圆柱和长方体高效，因此胶囊体常用来为接近圆柱体的物体建模。

轴对齐包围盒(AABB)

轴对齐包围盒可以仅仅由两个点定义，即三个轴上的最小坐标和最大坐标。
轴对齐包围盒的优点是可以高速地测试与另一AABB是否相交，而最大的限制在于它们必须保持轴对齐。

Ye：另一可行的AABB表示方式是存储最小坐标和尺寸，各有优劣，但是最小最大表示法的相交运算通常较快。

Jason：AABB只适合逼近大致轴对齐得长方体物体。

定向包围盒(OBB)

定向包围盒(oriented bounding box, OBB)通常表示为三个半棱长再加上变换。

Ye：半棱长也可以作为变换中的缩放，那么就可以用单个仿射矩阵表示OBB。

Jason：OBB是一种常用碰撞原型，因为他表示方式简单并且能较好地切合任意定向的物体。

离散定向多胞形(DOP)

离散定向多胞形(discrete oriented polytope, DOP)是比AABB和OBB更泛化的形状，AABB和OBB可以看作6-DOP。

Jason：一个构建DOP的方法是，先建立物体的OBB，再把角或者边以45°切割，加入更多平面试图做一个更紧密的逼近。

任意凸体积

Jason：可以用离线工具分析一个多面体是否为凸体积，如果是非凸的可以用多边形汤表示。

任意凸体积用k个平面方程，或者k个点加上k个法向量表示。

凸体积的相交测试比之前的几种几何原型更耗时。然而几种高效的相交算法如GJK都可以用于这些形状。

多边形汤

有些碰撞系统支持完全任意非凸形状，这种形状通常称为多边形汤(polygon-soup)。多边形汤常用于复杂的静态几何建模，例如地形或者建筑物。

使用多边形汤做碰撞检测是最费时的。碰撞引擎必须对每个三角形进行测试，还要处理伪相交问题。因此大多数引擎限制仅把多边形汤用在不参与动力学模拟的物体。

复合形状

有些物体用单个形状来逼近并不够，用一组形状来逼近就不错。复合形状还可以作为多边形汤的高效替代品。

Jason：有些碰撞系统例如Havok，会把复合形状的凸包围体积作为整体进行碰撞检测，如果不相交，则完全无需测试子形状的碰撞。Havok中称为中间阶段(midphase)。

(END)