深度解析：2D图形碰撞检测的算法原理与工程实践

一、2D图形碰撞检测的基础概念与核心挑战

2D图形碰撞检测（2D Collision Detection）是游戏开发、物理模拟、CAD设计等领域的关键技术，其核心目标是快速、准确地判断两个或多个图形是否发生重叠。相较于3D场景，2D碰撞检测的复杂度较低，但需处理高频调用、实时响应等挑战，尤其在移动端或资源受限的环境中，性能优化成为首要任务。

1.1 碰撞检测的分类与适用场景

根据图形类型和精度需求，2D碰撞检测可分为以下三类：

• 精确碰撞检测：基于几何图形的数学表达式（如线段、圆、多边形）计算是否重叠，适用于需要高精度的场景（如物理引擎）。
• 近似碰撞检测：通过包围盒（Bounding Box）、包围球（Bounding Sphere）等简化形状快速排除不相交的图形，适用于性能敏感的场景（如大量物体的粗筛）。
• 混合检测：结合近似与精确检测，先通过包围盒过滤，再对可能碰撞的图形进行精确计算，平衡精度与效率。

1.2 核心挑战

• 实时性要求：游戏帧率通常需达到60FPS，单帧碰撞检测次数可能超过千次，算法需在毫秒级完成。
• 图形复杂性：不规则多边形、曲线图形的检测复杂度远高于简单形状（如矩形、圆）。
• 动态物体处理：移动物体的碰撞预测与连续碰撞检测（Continuous Collision Detection, CCD）需避免穿透问题。

二、核心算法详解与代码实现

2.1 包围盒检测（Axis-Aligned Bounding Box, AABB）

AABB是最简单的近似检测方法，适用于矩形图形。其核心逻辑是判断两个矩形的投影在X轴和Y轴上是否重叠。

算法步骤：

1. 获取矩形A的左（A.left）、右（A.right）、上（A.top）、下（A.bottom）边界。
2. 获取矩形B的对应边界。
3. 判断X轴投影是否重叠：A.left <= B.right && A.right >= B.left。
4. 判断Y轴投影是否重叠：A.bottom <= B.top && A.top >= B.bottom。
5. 若X轴和Y轴均重叠，则发生碰撞。

代码示例（JavaScript）：

function checkAABBCollision(rectA, rectB) {
    return (rectA.left <= rectB.right && rectA.right >= rectB.left) &&
           (rectA.bottom <= rectB.top && rectA.top >= rectB.bottom);
}

适用场景：快速筛选大量静态或低速移动的矩形物体（如砖块、平台）。

2.2 圆形碰撞检测

圆形碰撞基于两点间距离与半径之和的比较，计算简单且效率高。

算法步骤：

1. 计算两圆心坐标（(x1, y1)和(x2, y2)）的距离平方：dx² + dy²。
2. 计算两圆半径之和的平方：(r1 + r2)²。
3. 若距离平方小于等于半径平方和，则发生碰撞。

代码示例（Python）：

import math
def checkCircleCollision(circle1, circle2):
    dx = circle1.x - circle2.x
    dy = circle1.y - circle2.y
    distance_squared = dx**2 + dy**2
    radius_sum_squared = (circle1.radius + circle2.radius)**2
    return distance_squared <= radius_sum_squared

适用场景：粒子系统、弹球游戏等圆形物体密集的场景。

2.3 多边形碰撞检测（Separating Axis Theorem, SAT）

SAT是精确检测凸多边形碰撞的经典算法，其核心思想是：若存在一条直线（分离轴）能使两多边形在该直线上的投影不重叠，则两多边形不相交。

算法步骤：

1. 获取两多边形的边，计算每条边的法线作为分离轴。
2. 将两多边形投影到分离轴上，计算投影的最小和最大值。
3. 判断投影是否重叠：若任一分离轴上的投影不重叠，则不相交；否则相交。

代码示例（C#，简化版）：

bool CheckPolygonCollision(Polygon polyA, Polygon polyB) {
    foreach (var edge in polyA.Edges) {
        Vector2 axis = new Vector2(-edge.Y, edge.X).Normalized();
        float minA, maxA, minB, maxB;
        ProjectPolygon(polyA, axis, out minA, out maxA);
        ProjectPolygon(polyB, axis, out minB, out maxB);
        if (maxA < minB || maxB < minA) return false;
    }
    foreach (var edge in polyB.Edges) {
        Vector2 axis = new Vector2(-edge.Y, edge.X).Normalized();
        float minA, maxA, minB, maxB;
        ProjectPolygon(polyA, axis, out minA, out maxA);
        ProjectPolygon(polyB, axis, out minB, out maxB);
        if (maxA < minB || maxB < minA) return false;
    }
    return true;
}

适用场景：不规则形状的精确检测（如角色、地形）。

三、性能优化策略

3.1 空间分区技术

• 四叉树（Quadtree）：将2D空间递归划分为四个象限，仅检测同一分区或相邻分区的物体。
• 网格划分（Spatial Hashing）：将空间划分为固定大小的网格，物体仅与所在网格及相邻网格的物体检测。

优化效果：可减少90%以上的无效检测，尤其适用于大规模静态场景。

3.2 广播相位（Broad Phase）与窄相位（Narrow Phase）

• 广播相位：使用AABB或包围球快速筛选可能碰撞的物体对。
• 窄相位：对筛选后的物体对进行精确检测（如SAT）。

代码示例（伪代码）：

for each object in scene:
    update AABB
for each pair in broadPhase(objects):
    if narrowPhase(pair):
        resolveCollision(pair)

3.3 动态物体优化

• swept AABB：扩展AABB以包含物体的运动轨迹，避免高速物体穿透。
• 连续碰撞检测（CCD）：计算物体在时间步长内的运动路径，精确判断碰撞时间。

四、实际应用场景与建议

1. 游戏开发：优先使用AABB+SAT的混合方案，结合四叉树优化。
2. 物理引擎：实现连续碰撞检测以避免穿透，如使用GJK算法（Gilbert-Johnson-Keerthi）替代SAT。
3. CAD设计：采用空间分区技术处理复杂几何图形的交互。

建议：

• 对性能敏感的场景，优先使用近似检测+精确检测的混合方案。
• 动态物体需考虑CCD或swept AABB以避免穿透。
• 使用成熟的物理引擎（如Box2D、Chipmunk）可大幅降低开发成本。

五、总结与展望

2D图形碰撞检测的核心在于平衡精度与效率。从简单的AABB到复杂的SAT，开发者需根据场景需求选择合适的算法。未来，随着硬件性能的提升和AI技术的应用（如神经网络辅助检测），碰撞检测的效率和精度将进一步提升。对于开发者而言，掌握基础算法原理并灵活应用优化策略，是解决实际问题的关键。