干涉检查与碰撞检测

摘要

在机械设计、计算机图形学、机器人路径规划、虚拟仿真以及游戏开发等领域，干涉检查（Interference Check）与碰撞检测（Collision Detection）是核心基础技术。干涉检查通常指在静态装配体中查找零件之间的重叠区域，而碰撞检测则侧重于动态运动中物体是否发生接触或穿透。本文将从基本概念出发，深入剖析这两类问题的数学原理与算法实现，涵盖AABB（Axis-Aligned Bounding Box）、OBB（Oriented Bounding Box）、分离轴定理（SAT）以及GJK（Gilbert-Johnson-Keerthi）算法，并提供完整的C++代码示例，帮助读者从理论到实践全面掌握该技术。

---

1. 引言

想象一下：你设计了一个复杂的机械臂，在装配时发现两个齿轮“长”在了一起；或者你正在开发一款3D游戏，角色穿墙而过——这些问题的根源都是干涉或碰撞没有被正确检测。

干涉检查关注的是静态物体之间的几何重叠，例如在CAD软件中检查装配体是否存在零件干涉。碰撞检测则关注动态过程中物体间的接触与穿透，例如机器人运动规划中避免与环境障碍物相撞。尽管目标略有不同，但底层算法高度重合：都需要高效判断两个几何体是否相交。

本文将以循序渐进的方式，从最简单的包围盒方法讲起，逐步深入到凸体碰撞检测的经典算法，并给出可运行的代码实现。

---

2. 基础概念与数学准备

2.1 几何体表示

在计算机中进行碰撞检测，首先需要将物体抽象为数学表示。常见表示方法有：

• 多边形网格（Polygon Mesh）：最通用，但计算量大。
• 隐式曲面（Implicit Surface）：如球体、圆柱体，检测简单。
• 凸包（Convex Hull）：许多高效算法（如GJK）要求物体为凸体。
• 包围盒（Bounding Volume）：用于快速排除不相交的物体。

2.2 包围体（Bounding Volume）

为了加速检测，通常先使用简单的包围体进行粗略测试，只有包围体相交时才进行精确检测。常见包围体有：

• AABB（轴对齐包围盒）：各边与坐标轴平行，检测效率最高。
• OBB（有向包围盒）：可旋转，更紧密但检测稍复杂。
• 包围球（Bounding Sphere）：检测极快，但紧密性差。
• k-DOP（离散方向多面体）：紧密性与效率的折中。

2.3 分离轴定理（Separating Axis Theorem, SAT）

SAT是凸体碰撞检测的核心理论：如果两个凸体不相交，则存在一条分离轴，使得两个物体在该轴上的投影区间不重叠。 反之，如果所有可能的轴上投影都重叠，则物体相交。

对于凸多边形（2D），需要检查每条边的法线作为分离轴；对于凸多面体（3D），需要检查每个面的法线以及每条边与另一物体每条边的叉积方向。

---

3. AABB碰撞检测详解

AABB是最简单也最常用的碰撞检测方法。一个AABB由最小点min和最大点max定义。

3.1 算法原理

两个AABB相交当且仅当它们在三个坐标轴上的投影区间都重叠。即：

重叠条件（3D）：
a.min.x <= b.max.x && a.max.x >= b.min.x &&
a.min.y <= b.max.y && a.max.y >= b.min.y &&
a.min.z <= b.max.z && a.max.z >= b.min.z

3.2 代码实现

#include <iostream>

struct AABB {
    float minX, minY, minZ;
    float maxX, maxY, maxZ;

    AABB(float minX_, float minY_, float minZ_, float maxX_, float maxY_, float maxZ_)
        : minX(minX_), minY(minY_), minZ(minZ_), maxX(maxX_), maxY(maxY_), maxZ(maxZ_) {}
};

bool AABBIntersect(const AABB& a, const AABB& b) {
    // 检查X轴
    if (a.minX > b.maxX || a.maxX < b.minX) return false;
    // 检查Y轴
    if (a.minY > b.maxY || a.maxY < b.minY) return false;
    // 检查Z轴
    if (a.minZ > b.maxZ || a.maxZ < b.minZ) return false;
    return true;
}

int main() {
    AABB box1(0, 0, 0, 2, 2, 2);
    AABB box2(1, 1, 1, 3, 3, 3);
    AABB box3(3, 3, 3, 5, 5, 5);

    std::cout << "Box1与Box2相交: " << AABBIntersect(box1, box2) << std::endl; // 1
    std::cout << "Box1与Box3相交: " << AABBIntersect(box1, box3) << std::endl; // 0
    return 0;
}

3.3 优缺点

• 优点：检测仅需6次比较，速度极快；更新AABB容易（只需重新计算min/max）。
• 缺点：紧密性差，尤其对于旋转后的细长物体，会产生大量误报。

---

4. OBB碰撞检测与分离轴定理

OBB可以随物体旋转，因此比AABB更紧密。但检测也复杂得多，需要应用SAT。

4.1 OBB的定义

一个OBB由中心点center、三个正交轴axes[3]（表示方向）以及三个半长halfSize[3]定义。

4.2 SAT应用于OBB

两个OBB的相交检测需要检查15条可能的分离轴（3D中）：

• 每个OBB的3个面法线（共6条）
• 两个OBB的边方向两两叉积（3×3=9条）

如果所有轴上投影都重叠，则相交；否则不相交。

4.3 核心实现（C++）

#include <iostream>
#include <cmath>
#include <vector>

struct Vector3 {
    float x, y, z;
    Vector3(float x_ = 0, float y_ = 0, float z_ = 0) : x(x_), y(y_), z(z_) {}
    Vector3 operator-(const Vector3& v) const { return Vector3(x - v.x, y - v.y, z - v.z); }
    float dot(const Vector3& v) const { return x * v.x + y * v.y + z * v.z; }
    Vector3 cross(const Vector3& v) const {
        return Vector3(y * v.z - z * v.y, z * v.x - x * v.z, x * v.y - y * v.x);
    }
    float length() const { return std::sqrt(x * x + y * y + z * z); }
};

struct OBB {
    Vector3 center;      // 中心点
    Vector3 axes[3];     // 三个正交轴（单位向量）
    Vector3 halfSize;    // 三个方向的半长

    OBB(const Vector3& c, const Vector3& a0, const Vector3& a1, const Vector3& a2, const Vector3& h)
        : center(c), halfSize(h) {
        axes[0] = a0; axes[1] = a1; axes[2] = a2;
    }
};

// 计算OBB在某个轴上的投影区间
void getProjection(const OBB& obb, const Vector3& axis, float& min, float& max) {
    float centerProj = obb.center.dot(axis);
    float radius = 0.0f;
    for (int i = 0; i < 3; ++i) {
        radius += std::abs(obb.axes[i].dot(axis)) * obb.halfSize.x; // 注意这里halfSize对应轴
        // 实际应使用对应分量，但为了简化，假设halfSize各分量对应各个轴
    }
    // 更精确的半径计算：
    // radius = std::abs(obb.axes[0].dot(axis)) * obb.halfSize.x
    //        + std::abs(obb.axes[1].dot(axis)) * obb.halfSize.y
    //        + std::abs(obb.axes[2].dot(axis)) * obb.halfSize.z;
    min = centerProj - radius;
    max = centerProj + radius;
}

// 检查两个OBB是否在给定轴上分离
bool overlapOnAxis(const OBB& a, const OBB& b, const Vector3& axis) {
    float aMin, aMax, bMin, bMax;
    getProjection(a, axis, aMin, aMax);
    getProjection(b, axis, bMin, bMax);
    return !(aMax < bMin || bMax < aMin);
}

bool OBBIntersect(const OBB& a, const OBB& b) {
    // 收集所有可能的分离轴
    std::vector<Vector3> testAxes;

    // 添加两个OBB的面法线
    for (int i = 0; i < 3; ++i) {
        testAxes.push_back(a.axes[i]);
        testAxes.push_back(b.axes[i]);
    }

    // 添加边方向叉积
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            Vector3 axis = a.axes[i].cross(b.axes[j]);
            if (axis.length() > 1e-6f) { // 忽略零向量
                axis = Vector3(axis.x / axis.length(), axis.y / axis.length(), axis.z / axis.length());
                testAxes.push_back(axis);
            }
        }
    }

    // 逐轴测试
    for (const auto& axis : testAxes) {
        if (!overlapOnAxis(a, b, axis)) {
            return false; // 找到分离轴，不相交
        }
    }
    return true; // 所有轴都重叠，相交
}

int main() {
    // 创建两个简单的OBB
    OBB obb1(Vector3(0, 0, 0), Vector3(1, 0, 0), Vector3(0, 1, 0), Vector3(0, 0, 1), Vector3(1, 1, 1));
    OBB obb2(Vector3(1.5, 0, 0), Vector3(1, 0, 0), Vector3(0, 1, 0), Vector3(0, 0, 1), Vector3(1, 1, 1));
    OBB obb3(Vector3(3, 0, 0), Vector3(1, 0, 0), Vector3(0, 1, 0), Vector3(0, 0, 1), Vector3(1, 1, 1));

    std::cout << "OBB1与OBB2相交: " << OBBIntersect(obb1, obb2) << std::endl; // 1
    std::cout << "OBB1与OBB3相交: " << OBBIntersect(obb1, obb3) << std::endl; // 0
    return 0;
}

4.4 注意事项

• 代码中getProjection的半径计算使用了简化方式，实际应分别乘以halfSize的对应分量。
• 叉积可能为零向量（两轴平行时），需要跳过。
• SAT适用于凸体，对于凹体需要先分解为凸体组合。

---

5. GJK算法：凸体碰撞检测的利器

GJK算法是一种迭代算法，用于计算两个凸体之间的最小距离，并判断是否相交。它比SAT更高效，尤其适合3D场景。

5.1 核心思想

GJK利用闵可夫斯基差（Minkowski Difference）：两个凸体A和B的闵可夫斯基差定义为：

C = A ⊖ B = { a - b | a ∈ A, b ∈ B }

两个凸体相交当且仅当原点在它们的闵可夫斯基差内部。

GJK通过迭代构建一个单纯形（simplex：点、线段、三角形、四面体），并判断它是否包含原点。

5.2 支持函数（Support Function）

支持函数返回凸体在给定方向上的最远点。例如，对于球体，支持函数就是沿方向移动半径；对于凸多边形，它是顶点中投影最大的点。

// 支持函数：返回凸体在方向d上的最远点
Vector3 support(const std::vector<Vector3>& vertices, const Vector3& d) {
    float maxProj = -1e9f;
    Vector3 bestPoint;
    for (const auto& v : vertices) {
        float proj = v.dot(d);
        if (proj > maxProj) {
            maxProj = proj;
            bestPoint = v;
        }
    }
    return bestPoint;
}

// 两个凸体的闵可夫斯基差上的支持点
Vector3 supportMinkowski(const std::vector<Vector3>& vertsA, const std::vector<Vector3>& vertsB, const Vector3& d) {
    Vector3 a = support(vertsA, d);
    Vector3 b = support(vertsB, Vector3(-d.x, -d.y, -d.z)); // 注意方向取反
    return a - b;
}

5.3 迭代过程

GJK算法的伪代码如下：

1. 初始化单纯形为空，选择一个初始方向d（如(1,0,0)）
2. 计算支持点p = supportMinkowski(A, B, d)
3. 将p加入单纯形
4. 循环：
   a. 如果单纯形包含原点，返回相交
   b. 计算原点在单纯形上的最近点，得到新的方向d
   c. 如果d点乘(p - 原点) < 0，说明无法接近原点，返回不相交
   d. 计算新支持点p = supportMinkowski(A, B, d)
   e. 将p加入单纯形，并更新单纯形（只保留必要的顶点）

5.4 完整实现（2D简化版）

为便于理解，这里实现2D版本的GJK，判断两个凸多边形是否相交。

#include <iostream>
#include <vector>
#include <cmath>

struct Point2D {
    float x, y;
    Point2D(float x_ = 0, float y_ = 0) : x(x_), y(y_) {}
    Point2D operator-(const Point2D& p) const { return Point2D(x - p.x, y - p.y); }
    float dot(const Point2D& p) const { return x * p.x + y * p.y; }
    float cross(const Point2D& p) const { return x * p.y - y * p.x; }
    Point2D operator*(float s) const { return Point2D(x * s, y * s); }
    Point2D operator+(const Point2D& p) const { return Point2D(x + p.x, y + p.y); }
    float length() const { return std::sqrt(x * x + y * y); }
};

// 2D支持函数
Point2D support2D(const std::vector<Point2D>& poly, const Point2D& d) {
    float maxProj = -1e9f;
    Point2D best;
    for (const auto& p : poly) {
        float proj = p.dot(d);
        if (proj > maxProj) {
            maxProj = proj;
            best = p;
        }
    }
    return best;
}

Point2D supportMinkowski2D(const std::vector<Point2D>& A, const std::vector<Point2D>& B, const Point2D& d) {
    Point2D a = support2D(A, d);
    Point2D b = support2D(B, Point2D(-d.x, -d.y));
    return a - b;
}

// 判断原点是否在线段上
bool pointOnSegment(const Point2D& a, const Point2D& b, const Point2D& p) {
    // 先检查是否共线，再检查范围
    float cross = (b - a).cross(p - a);
    if (std::abs(cross) > 1e-6f) return false;
    float dot = (b - a).dot(p - a);
    float lenSq = (b - a).dot(b - a);
    return dot >= 0 && dot <= lenSq;
}

// 判断原点是否在三角形内
bool originInTriangle(const Point2D& a, const Point2D& b, const Point2D& c) {
    // 使用重心坐标法
    Point2D v0 = c - a;
    Point2D v1 = b - a;
    Point2D v2 = Point2D(0, 0) - a;
    float dot00 = v0.dot(v0);
    float dot01 = v0.dot(v1);
    float dot02 = v0.dot(v2);
    float dot11 = v1.dot(v1);
    float dot12 = v1.dot(v2);
    float invDenom = 1.0f / (dot00 * dot11 - dot01 * dot01);
    float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
    float v = (dot00 * dot12 - dot01 * dot02) * invDenom;
    return (u >= 0) && (v >= 0) && (u + v <= 1);
}

// 2D GJK算法
bool GJK2D(const std::vector<Point2D>& polyA, const std::vector<Point2D>& polyB) {
    // 初始方向
    Point2D d(1, 0);