GAMES103课程笔记09-Collision Handling
这个系列是GAMES103：基于物理的计算机动画入门(GAMES 103: Intro to Physics Based Animation)的同步课程笔记。本课程是计算机动画的入门课程，着重介绍各种基于物理的动画仿真模拟技术。本节课介绍物理仿真中的碰撞检测和处理。
Collision Detection
碰撞检测(collision detection)是物理仿真中非常重要的一环。根据检测的精细程度不同，碰撞检测的流程可以大体分为broad-phase和narrow-phase两个步骤：broad-phase用来产生碰撞物体的候选，然后在narrow-phase中执行具体的检测。
Spatial Partitioning
空间划分(spatial partitioning/hashing)是broad-phase检测中常用的一种方式。它的基本思想是把空间划分成若干个互不重叠的区域，然后把每个物体放置在这些区域中，这样进行碰撞检测时只需要在相邻的格子中进行判断即可。由于物体可能会和不同的格子相交，因此在放置这些物体时需要把物体放置在所有相交的格子中。
为了减少碰撞检测时的内存需求我们可以将物体和它所在的格子按照编号进行排序，这样就可以避免为空的格子分配内存。
除此之外还可以利用Morton code来进一步优化访问时的缓存需求。Morton code是一种按照Z形进行编码的顺序。在对格子进行编号时我们不再按照先行后列的方式而是使用Morton code进行编号，这样可以保证访问时每个格子的邻居在内存中存储的位置都在它的附近从而提升访问的效率。
Bounding Volume Hierarchy
BVH是另一种常用的broad-phase检测方法，它的实现细节可以参考PBRT中的内容。简单来说BVH的核心是将整个物体使用一棵树来表示，树的叶节点是每个部件的包围盒，中间节点则是它两个子节点包围盒的并集。
当需要判断物体是否与其他物体相交时只需要从根节点出发对树进行遍历即可：如果查询物体的包围盒与当前节点的包围盒相交则继续向下遍历，测试它是否与两个子节点包围盒是否相交；否则停止遍历，查询物体不可能与当前节点下的任意部件相交。
除了遍历之外BVH还需要考虑树的内部是否存在碰撞的情况，检测的算法可参考下图：
综合对比spatial partitioning和BVH两种算法，spatial partitioning的优势在于它容易实现而且适合部署在GPU上，但它的缺陷在于当场景中的物体发生运动后需要更新划分；BVH的实现方式则比较复杂，而且不适合在GPU上运行，但对于物体发生运动的情况则可以通过对树进行遍历来更新，无需重新构造BVH。
Discrete Collision Detection
获得碰撞的候选单元后就可以执行实际的碰撞检测了。根据检测的类型可以将检测算法分为discrete collision detection(DCD)和continuous collision detection(CCD)两种：DCD是对静态的单元进行碰撞检测，而CCD则可以对运动的单元进行检测。
对于离散时刻下单元的不同位置，DCD的思想是在每一时刻判断边与三角形是否相交：如果相交则说明出现碰撞，反之则没有碰撞。对于边\(\mathbf{x}_a\mathbf{x}_b\)，我们可以通过边上任意点与三角形构成的平面是否相交来进行判断，如果边与平面相交则需要进一步判断交点是否在三角形内：
Continuous Collision Detection
DCD的一个缺陷在于无法处理穿透的情况：两个三角形可能在两个离散时刻不相交，但在运动过程中会出现相互穿透。这样的现象称为tunneling：
而CCD则可以处理这样的问题。假设每个节点在时间间隔内为线性运动，我们首先判断顶点在运动过程中是否出现共面，如果四个顶点发生共面则继续检测边是否相交从而完成两条边的碰撞检测：
而对于点和三角形是否发生碰撞，可以使用类似的方法来进行检测：
总体来看，CCD的实现要比DCD复杂得多而且在运行时需要更多的计算资源。同时值得注意的是CCD涉及到求解三次方程，如果直接使用求根公式来计算会引入不能忽略的浮点误差，因此在实现时一般会使用数值求解的方法。
Collision Handling
完成碰撞单元的检测后就可以着手处理碰撞了。目前主流的碰撞处理方法包括内点法(interior point methods)和impact zone optimization两种：
Interior Point Methods
记发生碰撞时单元的位置为\(\mathbf{x}^{[1]}\)，处理后的位置为\(\mathbf{\bar{x}}^{[1]}\)。内点法的思想是在安全区域内进行状态更新并找到最接近\(\mathbf{x}^{[1]}\)的位置作为\(\mathbf{\bar{x}}^{[1]}\)。内点法的一个经典例子是使用log-barrier来将相交的单元弹开，在实际应用时往往还会设置一个截断来处理排斥力永远存在的问题：
在此基础上就可以定义一个优化问题来处理碰撞。我们可以通过梯度下降或是其他的方式来求解，求解的结果即为不发生碰撞条件下单元的位置：
使用内点法来处理碰撞问题一般需要进行不断的迭代，因此内点法的运行效率一般会比较低。不过它的优势在于即使没有得到最优解，内点法的计算结果仍然在安全区域内，即内点法可以保证一定能够得到一个安全(没有碰撞)的结果。
Impact Zone Optimization
impact zone optimization的思想是忽略状态更新的过程，直接从\(\mathbf{x}^{[1]}\)开始进行不断的投影和优化，直到新的状态\(\mathbf{\bar{x}}^{[1]}\)位于安全区域内。实际上impact zone optimization等价于求解一个约束优化问题：
不过需要注意的是impact zone optimization可能找不到约束优化问题的解，即impact zone optimization的解可能不会在安全区域内。
Rigid Impact Zones
如果实在没有办法完美解决碰撞的问题，还可以选择把会发生碰撞的单元恢复到碰撞前的状态，这样的方法称为rigid impact zone method。
Intersection Elimination
在一些情况下我们并不关系何时何处发生碰撞，我们只希望能将碰撞解除掉。在这样的情况下碰撞处理要容易得多：对于有体积的物体，我们只需要利用SDF将碰撞的顶点推出碰撞区域即可：
但对于布料这类没有体积概念的物体，我们则没有办法使用SDF来进行处理。具体的处理算法可以参考论文Resolving Surface Collisions through Intersection Contour Minimization。