GAMES103.王华民.09.Collision Handling

Posted on Edited on In Views:
碰撞检测（碰撞剔除、碰撞检测）、空间划分（SH、BVH）、碰撞检测（CCD、DCD）

碰撞处理

  • 理论不复杂，但是实际工程写起来不简单
  • 衣服布料的碰撞处理是最复杂的
  • 流程：碰撞检测 \(\to\) 碰撞响应
  • collision handling = collision detection + collision response

碰撞检测

  • collision detection
  • 笔记中的三角形只是一个代称，也可以是其他的几何原体、物体

Pipeline

  • 碰撞检测的 pipeline

  • 不可能两两的对所有的三角形做碰撞检测，复杂度太高了
    • \(O(n^2)\)
  • 因此需要分成两个部分
    • 第一部分：Broad-Phase Collision Culling
      • 去除完全不可能产生碰撞的三角形对
    • 第二部分：Narrow-Phase Collision Test
      • 对候选的三角形对进行碰撞检测
  • 碰撞检测结束之后，进一步处理碰撞
  • Collision Culling 的两种基本套路
    • Spatial Hashing（空间划分）
    • BVH（层次包围盒）

Collision Culling

Spatial Hashing

  • Spatial Partitioning
  • 空间划分
  • 将世界划分为格子，然后把三角形存到格子中
    • 如果三角形和这个格子有相交，则将其存入
  • 例子

  • 此时可能产生碰撞的三角形对，一定存储相同的格子中
    • 例如上面可能和 \(t_3\) 产生碰撞的三角形只有 \(t_0,t_5\)
  • 如果三角形是在运动的话，将整个运动轨迹作为一个物体，如果格子和这个运动轨迹相交，则将其存入格子

  • 实际操作可以在空间划分中做层次扩展
    • 例如八叉树（Octree）
  • 问题：内存浪费严重
    • 划分的格子可能很多
    • 每一个格子中保存的三角形数目不确定
      • 可能有少量格子中有大量三角形
      • 绝大部分格子中都是空的
  • 可以不事先分配内存，而是以三角形为基础建立（object-cell list）
    • 先列出三角形所在的格子，形成 pair（\(t_i,\text{position}\)），然后排序
      • 根据相同的格子 id 中找出可能产生碰撞的三角形对
    • 占用内存较小，和三角形的数目相当

Morton Code

  • 如何定义格子的 id
  • 因为 cache 的存在，我们希望内存访问是相对连续的
  • morton code
    • 目的就是让两次内存访问的地址更加接近，更好的利用缓存的局部性（locality）
  • 以 Z 字形为基础，不断细分

  • 拼接 XY 轴，按照拼接形成的数字大小排序，形成一个顺序

BVH

  • Bounding Volume Hierarchy
  • 根据物体的拓扑结构，对物体进行层次划分

  • 使用包围盒的目的
    • 优化碰撞检测，如果包围盒都不相交，那么包围盒中的物体也不会相交

包围盒类型

  • AABB：axis-aligned bounding box
    • AABB 相交当且仅当每一个轴上都相交
  • OBB：oriented bounding box
  • sphere

碰撞检测

  • 物体和 BVH 的碰撞检测流程
    • 和根节点进行碰撞检测
      • 如果有碰撞，递归的对子结点进行碰撞检测
      • 如果没有碰撞，则没有碰撞

自相交的碰撞检测

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 以 A 为根节点的子树内部相交
Process_Node(A) {
    For every A’s child: B
        Process_Node(B);
    For every A’s children pair <B, C>
        if B and C intersect
            Process_Pair(B, C);
}

// 以 B,C 为根节点的子树之间相交
Process_Pair(B, C) {
    For every B’s child: B’
        For every C’s child: C’
            if B’ and C’ intersect
                Process_Pair(B’, C’);
}

局限性

  • 虽然能够很快的提出远处不相交的物体，但是对周围的物体（靠的比较近）很难剔除
  • 基于能量（形变）的碰撞检测
    • Zheng and James. 2012. Energy-based Self-Collision Culling for Arbitrary Mesh Deformations. TOG (SIGGRAPH)

对比

  • SH（Spatial Hashing）
    • 很容易实现
    • GPU 友好
    • 当物体移动的时候需要重新计算
  • BVH
    • 实现复杂
    • GPU 不友好（对树结构不太友好）
    • 更新起来比较简单（只需要更新 BV）

Collision Test

  • DCD：Discrete Collision Detection
    • 离散碰撞检测
    • 基本检测单位为 edge-triangles 对
  • CCD：Continuous Collision Detection
    • 连续碰撞检测
    • 基本检测单位为 vertex-triangle 对和 edge-edge 对

DCD

  • 在每一个离散的时刻上检测是否存在碰撞
    • DCD tests if any intersection exists in each state at discrete time instant: \(\mathbf{x}^{[0]},\mathbf{x}^{[1]},\cdots\)
  • 基本检测：边——三角形
    • 检测边和三角形是否相交
    • 线段 \(\mathbf{x}_{a}\mathbf{x}_{b}\) 上任意一点可以表示为 \((1-t)\mathbf{x}_{a}+t\mathbf{x}_{b},t\in[0,1]\)

问题

  • 问题：两个相邻的时刻 \(\mathbf{x}^{[0]},\mathbf{x}^{[1]}\) 都不相交，但是实际上在这两个时刻之间发生了相交
  • 上面这种情况的碰撞通过 DCD 检测不出来
  • 示例：绿色三角形向下移动、蓝色三角形向上移动

  • 优点：高效、简单、稳定
  • 问题：
    • tunneling effects：隧穿效应
    • 运动太快会出现这种问题
      • 尤其是比较小、比较薄的物体，例如布料穿墙
    • 解决：要求物体运动的不能太快、减小时间步长

CCD

  • 检测任意的两个离散状态之间有没有相交（真正的碰撞检测）
    • CCD tests if any intersection exists between two states: \(\mathbf{x}^{[0]}\) and \(\mathbf{x}^{[1]}\)
  • 基本检测：点——三角形检测、边——边检测
  • 点——三角形检测：四点共面检测
    • 比 DCD 复杂，第一步需要求解一个一元三次方程
      • 求解尽量不要用求根公式，而使用二分法/牛顿法等数值方法
      • 求根公式中的 \(x^{1/3}\) 一项误差很大

  • 边——边检测
    • 先检测是否共面，在检测是否在内部相交

  • 只做点——三角形检测不行
    • 六芒星：红色向屏幕内移动、蓝色向屏幕外移动

问题

  • 实现相对困难
  • 计算复杂度比 DCD 要大
    • 有些观点：瓶颈在 collision culling 部分
  • 浮点精度的问题，计算误差大
    • 可以使用 epsilon，放宽限制 \(t\in[-\epsilon,1+\epsilon]\)
      • 可能会导致 false positive
    • 游戏的 GPU 以单精度浮点数 float 为主

课后阅读

  • Bridson et al. 2002. Robust Treatment of Collisions, Contact and Friction for Cloth Animation. TOG (SIGGRAPH).