计算机图形学入门：碰撞检测详解
计算机图形学入门：碰撞检测详解
碰撞检测是计算机图形学中的一个重要课题，广泛应用于游戏开发、虚拟现实等领域。本文将介绍碰撞检测的基本原理和常用方法，帮助读者快速入门这一领域。
碰撞检测的两个阶段
碰撞检测主要分为两个阶段：碰撞剔除和实际碰撞检测。
碰撞剔除
碰撞剔除的目的是去除不可能发生碰撞的元素，输出可能碰撞的备选目标。常用的两种方法是Spatial Hashing和BVH（Bounding Volume Hierarchy）。
Spatial Hashing：
Spatial Hashing将整个空间划分成许多小区域，每个元素在空间上的分布被存入这些区域中。这样，当需要检测某个元素（如三角形t3）是否与其他元素相交时，只需检查t3所在的小区域中有哪些其他元素即可。
对于运动中的元素，可以将其运动轨迹上的所有小区域都存入。这种方法的缺点是存储量大，且可能有很多空区域。为了解决这个问题，可以先存入序列，然后根据小区域的顺序进行排序，对每个区域只存储开始和结束的位置。
为了优化内存访问的连续性，还可以对整个空间进行细分。
BVH（Bounding Volume Hierarchy）：
与Spatial Hashing不同，BVH是根据物体的结构进行划分，使用包围盒的方法。通过构建一个层次化的包围盒结构，可以快速剔除不会发生碰撞的元素对。最常见的是AABB（轴对齐包围盒），它不需要复杂的数值计算，只需要进行大小比较。
对于自相交的处理，可以通过递归检测整体节点及其子节点来实现。
两种方法的对比：
- 空间划分方法（如Spatial Hashing）写起来相对容易，对GPU友好，但计算资源消耗较高。
- BVH代码实现较复杂，对GPU不太友好（因为是树结构），但更新容易。
实际碰撞检测
实际碰撞检测分为离散检测和连续检测。
离散检测（DCD）：
离散检测主要检测相交，而不是真正的碰撞。这种方法不考虑运动概念，因此对于快速运动的物体可能检测不到相交。
连续检测：
连续检测需要检测状态之间的点-三角形、边-边的检测。
连续检测计算量较大，但在游戏中大多使用DCD，除非需要特别高的精度。在手术模拟等需要实时性的场景中，也常使用DCD。
碰撞处理方法
碰撞处理主要有两种方法：内点法和冲击区优化。
内点法
内点法的思路是保证点始终在合理区域内，逐步接近最优解。这种方法虽然较慢，但总能成功。实现时，步长选择很重要，每走一步都需要进行碰撞检测。
冲击区优化
冲击区优化通过直接优化不安全的结果到安全的结果，速度较快，但可能在步长较大的情况下失败。
离散碰撞处理
当发现可能碰撞时，可以回到前一帧，封住整个区域。对于有体积的物体，如果发生相交，可以将物体推出去。