6.常见碰撞检测算法
6.1 题目
碰撞检测的常用算法有哪些？(至少说出三种，并任选其中一个简单描述其原理)
6.2 深入解析
AABB（轴对齐包围盒，Axis-Aligned Bounding Box）
每个物体用一个与坐标轴对齐的矩形（或立方体）包围。AABB的碰撞检测通过检查两个包围盒是否重叠来判断物体是否碰撞OBB（有向包围盒，Oriented Bounding Box）
OBB是一个可以旋转的包围盒，能够适应旋转的物体。它通过最小化物体的外接矩形来表示物体的边界。相当于就是基于AABB，加入了矩形的角度SAT（分离轴定理，Separating Axis Theorem）
SAT 常用于 两个凸多边形/凸体（凹多边形需拆分或换算法）。若存在一条分离轴使两形状投影不重叠，则不相交；对所有必要轴都找不到分离轴，则相交。包围球（Bounding Sphere）
使用一个球形的包围体来包围物体，碰撞检测通过判断两个球体的中心距离是否小于它们半径的和来判断碰撞光线投射（Raycasting）
通过从某一点发射一条射线（光线）来检测物体的碰撞。它适用于检测射线与物体的交点，常用于检测射击、视线、物体间的接触等
等等
6.3 答题示例
常见的碰撞检测算法包括：
AABB（轴对齐包围盒）
- 原理：为每个物体构建一个与世界坐标轴对齐的最小矩形（2D）或长方体（3D）包围体，检测时只需比较它们在各轴上的投影区间是否重叠。
OBB（有向包围盒）
- 原理：包围盒可以随物体旋转，检测时需要在所有候选分离轴上投影多边形的顶点并比较区间重叠情况。
SAT（分离轴定理）
- 原理：对两个凸形状，在由边法线等张成的候选轴上检测投影是否分离；存在分离轴则不相交，否则相交（凹形需另行处理）。
示例：AABB 碰撞检测
我们可以对两个 AABB 分别计算它们在 X、Y（以及 Z）轴的最小和最大坐标值，只有当在所有轴上两者的最大值都大于对方的最小值时，才认为它们相交。例如，在 2D 中：bool AABBOverlap(Rect a, Rect b) { return a.xMin <= b.xMax && a.xMax >= b.xMin && a.yMin <= b.yMax && a.yMax >= b.yMin; }这种方法计算量少，适合大量简单刚体的快速初步筛选。
6.4 关键词联想
- 包围盒（Bounding Volume）
- 轴对齐 vs 有向（AABB vs OBB）
- 分离轴定理（SAT）
- 包围球检测
- 光线投射（Raycast）
- 宽相（broad-phase） vs 窄相（narrow-phase）
- 空间划分（四叉树/八叉树、网格分区）
- 碰撞响应（碰撞处理）
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
