第11章：碰撞检测算法

11.1 碰撞检测概述

11.1.1 碰撞检测的重要性

碰撞检测是计算机图形学和游戏开发中的核心问题，用于判断物体之间是否接触或重叠。

碰撞检测的应用

1. 游戏开发
   - 角色与环境碰撞
   - 子弹命中检测
   - 物理模拟

2. 机器人运动规划
   - 避障
   - 路径规划

3. 虚拟现实
   - 手与物体交互
   - 物体抓取

4. CAD/CAM
   - 装配验证
   - 干涉检测


碰撞检测的挑战：

复杂场景中可能有成千上万的物体：

┌───────────────────────────────────┐
│  ●  ■  ◆  ▲  ●  ■  ◆  ▲  ●  ■   │
│  ◆  ▲  ●  ■  ◆  ▲  ●  ■  ◆  ▲   │
│  ●  ■  ◆  ▲  ●  ■  ◆  ▲  ●  ■   │
│  ◆  ▲  ●  ■  ◆  ▲  ●  ■  ◆  ▲   │
└───────────────────────────────────┘

n 个物体需要 n(n-1)/2 次两两检测！
1000 个物体 → 约 50 万次检测

11.1.2 碰撞检测流程

碰撞检测的两阶段

第一阶段：粗检测（Broad Phase）
- 快速排除大量不可能碰撞的物体对
- 使用包围体、空间划分

第二阶段：精检测（Narrow Phase）
- 对可能碰撞的物体进行精确检测
- 使用 SAT、GJK 等算法


流程图：

所有物体对              可能碰撞的物体对         实际碰撞
    │                        │                    │
    │  粗检测                │  精检测            │
    │  O(n log n)           │  O(n)              │
    ▼                        ▼                    ▼
┌─────────┐              ┌─────────┐          ┌─────────┐
│ n(n-1)/2│   ──────►    │   m     │   ──────►│   k     │
│  物体对  │              │  物体对  │          │  碰撞   │
└─────────┘              └─────────┘          └─────────┘

通常 m << n(n-1)/2，大大减少计算量

---

11.2 包围体

11.2.1 包围体类型

常见包围体

1. AABB（轴对齐包围盒）
   - 与坐标轴平行的盒子
   - 检测最快
   - 不够紧凑

   ┌───────────┐
   │    ╱╲     │
   │   ╱  ╲    │
   │  ╱    ╲   │
   │ ╱______╲  │
   └───────────┘


2. OBB（有向包围盒）
   - 可以任意旋转
   - 更紧凑
   - 检测稍慢

      ╱─────────╲
     ╱    ╱╲     ╲
    ╱    ╱  ╲     ╲
   ╱    ╱    ╲     ╲
  ╱    ╱______╲     ╲
 ╲─────────────────╱


3. 包围球（Bounding Sphere）
   - 旋转不变
   - 检测最快
   - 最不紧凑

        ╭─────────╮
       ╱   ╱╲     ╲
      │   ╱  ╲     │
       ╲ ╱    ╲   ╱
        ╰─────────╯


4. 凸包（Convex Hull）
   - 最紧凑
   - 检测最慢

       ╱╲
      ╱  ╲
     ╱    ╲
    ╱______╲

11.2.2 AABB 碰撞检测

/**
 * AABB 类
 */
class AABB {
    constructor(min, max) {
        this.min = min; // { x, y, z }
        this.max = max; // { x, y, z }
    }
    
    /**
     * 从点集创建 AABB
     */
    static fromPoints(points) {
        const min = { x: Infinity, y: Infinity, z: Infinity };
        const max = { x: -Infinity, y: -Infinity, z: -Infinity };
        
        for (const p of points) {
            min.x = Math.min(min.x, p.x);
            min.y = Math.min(min.y, p.y);
            min.z = Math.min(min.z, p.z);
            max.x = Math.max(max.x, p.x);
            max.y = Math.max(max.y, p.y);
            max.z = Math.max(max.z, p.z);
        }
        
        return new AABB(min, max);
    }
    
    /**
     * AABB 与 AABB 碰撞检测
     */
    intersects(other) {
        return this.min.x <= other.max.x && this.max.x >= other.min.x &&
               this.min.y <= other.max.y && this.max.y >= other.min.y &&
               this.min.z <= other.max.z && this.max.z >= other.min.z;
    }
    
    /**
     * 2D AABB 碰撞检测
     */
    intersects2D(other) {
        return this.min.x <= other.max.x && this.max.x >= other.min.x &&
               this.min.y <= other.max.y && this.max.y >= other.min.y;
    }
    
    /**
     * 点是否在 AABB 内
     */
    containsPoint(point) {
        return point.x >= this.min.x && point.x <= this.max.x &&
               point.y >= this.min.y && point.y <= this.max.y &&
               point.z >= this.min.z && point.z <= this.max.z;
    }
    
    /**
     * 射线与 AABB 相交测试
     */
    intersectsRay(origin, direction) {
        let tmin = -Infinity;
        let tmax = Infinity;
        
        // 检查每个轴
        for (const axis of ['x', 'y', 'z']) {
            if (Math.abs(direction[axis]) < 1e-10) {
                // 射线平行于该轴
                if (origin[axis] < this.min[axis] || origin[axis] > this.max[axis]) {
                    return null;
                }
            } else {
                let t1 = (this.min[axis] - origin[axis]) / direction[axis];
                let t2 = (this.max[axis] - origin[axis]) / direction[axis];
                
                if (t1 > t2) [t1, t2] = [t2, t1];
                
                tmin = Math.max(tmin, t1);
                tmax = Math.min(tmax, t2);
                
                if (tmin > tmax) return null;
            }
        }
        
        return tmin >= 0 ? tmin : (tmax >= 0 ? tmax : null);
    }
    
    /**
     * 合并两个 AABB
     */
    merge(other) {
        return new AABB(
            {
                x: Math.min(this.min.x, other.min.x),
                y: Math.min(this.min.y, other.min.y),
                z: Math.min(this.min.z, other.min.z)
            },
            {
                x: Math.max(this.max.x, other.max.x),
                y: Math.max(this.max.y, other.max.y),
                z: Math.max(this.max.z, other.max.z)
            }
        );
    }
    
    /**
     * 获取中心点
     */
    getCenter() {
        return {
            x: (this.min.x + this.max.x) / 2,
            y: (this.min.y + this.max.y) / 2,
            z: (this.min.z + this.max.z) / 2
        };
    }
    
    /**
     * 获取尺寸
     */
    getSize() {
        return {
            x: this.max.x - this.min.x,
            y: this.max.y - this.min.y,
            z: this.max.z - this.min.z
        };
    }
    
    /**
     * 扩展 AABB
     */
    expand(amount) {
        return new AABB(
            {
                x: this.min.x - amount,
                y: this.min.y - amount,
                z: this.min.z - amount
            },
            {
                x: this.max.x + amount,
                y: this.max.y + amount,
                z: this.max.z + amount
            }
        );
    }
}

11.2.3 包围球碰撞检测

/**
 * 包围球类
 */
class BoundingSphere {
    constructor(center, radius) {
        this.center = center; // { x, y, z }
        this.radius = radius;
    }
    
    /**
     * 从点集创建最小包围球（简化版）
     */
    static fromPoints(points) {
        if (points.length === 0) return null;
        
        // 简单方法：使用 AABB 的中心和最远距离
        const aabb = AABB.fromPoints(points);
        const center = aabb.getCenter();
        
        let maxDistSq = 0;
        for (const p of points) {
            const dx = p.x - center.x;
            const dy = p.y - center.y;
            const dz = p.z - center.z;
            maxDistSq = Math.max(maxDistSq, dx*dx + dy*dy + dz*dz);
        }
        
        return new BoundingSphere(center, Math.sqrt(maxDistSq));
    }
    
    /**
     * 球与球碰撞检测
     */
    intersects(other) {
        const dx = this.center.x - other.center.x;
        const dy = this.center.y - other.center.y;
        const dz = this.center.z - other.center.z;
        const distSq = dx*dx + dy*dy + dz*dz;
        const radiusSum = this.radius + other.radius;
        
        return distSq <= radiusSum * radiusSum;
    }
    
    /**
     * 点是否在球内
     */
    containsPoint(point) {
        const dx = point.x - this.center.x;
        const dy = point.y - this.center.y;
        const dz = point.z - this.center.z;
        
        return dx*dx + dy*dy + dz*dz <= this.radius * this.radius;
    }
    
    /**
     * 射线与球相交测试
     */
    intersectsRay(origin, direction) {
        const oc = {
            x: origin.x - this.center.x,
            y: origin.y - this.center.y,
            z: origin.z - this.center.z
        };
        
        const a = direction.x*direction.x + direction.y*direction.y + direction.z*direction.z;
        const b = 2 * (oc.x*direction.x + oc.y*direction.y + oc.z*direction.z);
        const c = oc.x*oc.x + oc.y*oc.y + oc.z*oc.z - this.radius*this.radius;
        
        const discriminant = b*b - 4*a*c;
        
        if (discriminant < 0) return null;
        
        const t1 = (-b - Math.sqrt(discriminant)) / (2*a);
        const t2 = (-b + Math.sqrt(discriminant)) / (2*a);
        
        if (t1 >= 0) return t1;
        if (t2 >= 0) return t2;
        return null;
    }
}

---

11.3 SAT 算法

11.3.1 分离轴定理

分离轴定理（Separating Axis Theorem）

如果两个凸多边形不相交，则必然存在一条"分离轴"，
使得两个多边形在该轴上的投影不重叠。


图示：

不相交：                     相交：
   │                            │
   │   □                        │   □
   │   │                        │  ╱│
   │───┼───  分离轴             │ ╱ │
   │   │                        │╱  │
   │   ◇                        │◇──┼──
   │                            │   │


分离轴的候选：

2D 多边形：
- 每条边的法向量

3D 多面体：
- 每个面的法向量
- 两个物体边的叉积


SAT 算法：

1. 遍历所有可能的分离轴
2. 将两个形状投影到轴上
3. 检查投影是否重叠
4. 如果任一轴上不重叠 → 不碰撞
5. 所有轴都重叠 → 碰撞

11.3.2 SAT 实现

/**
 * 2D SAT 碰撞检测
 */
class SAT2D {
    /**
     * 检测两个凸多边形是否碰撞
     * @param poly1 顶点数组 [{x, y}, ...]
     * @param poly2 顶点数组
     * @returns 碰撞信息或 null
     */
    static testPolygons(poly1, poly2) {
        // 收集所有分离轴
        const axes = [
            ...this.getAxes(poly1),
            ...this.getAxes(poly2)
        ];
        
        let minOverlap = Infinity;
        let minAxis = null;
        
        // 测试每个轴
        for (const axis of axes) {
            const proj1 = this.project(poly1, axis);
            const proj2 = this.project(poly2, axis);
            
            const overlap = this.getOverlap(proj1, proj2);
            
            if (overlap <= 0) {
                // 找到分离轴，不碰撞
                return null;
            }
            
            if (overlap < minOverlap) {
                minOverlap = overlap;
                minAxis = axis;
            }
        }
        
        // 所有轴都重叠，碰撞
        return {
            overlap: minOverlap,
            normal: minAxis
        };
    }
    
    /**
     * 获取多边形的分离轴（边的法向量）
     */
    static getAxes(polygon) {
        const axes = [];
        
        for (let i = 0; i < polygon.length; i++) {
            const p1 = polygon[i];
            const p2 = polygon[(i + 1) % polygon.length];
            
            // 边向量
            const edge = { x: p2.x - p1.x, y: p2.y - p1.y };
            
            // 法向量（垂直于边）
            const normal = this.normalize({ x: -edge.y, y: edge.x });
            
            axes.push(normal);
        }
        
        return axes;
    }
    
    /**
     * 将多边形投影到轴上
     */
    static project(polygon, axis) {
        let min = Infinity;
        let max = -Infinity;
        
        for (const vertex of polygon) {
            const proj = vertex.x * axis.x + vertex.y * axis.y;
            min = Math.min(min, proj);
            max = Math.max(max, proj);
        }
        
        return { min, max };
    }
    
    /**
     * 计算两个投影的重叠量
     */
    static getOverlap(proj1, proj2) {
        return Math.min(proj1.max, proj2.max) - Math.max(proj1.min, proj2.min);
    }
    
    /**
     * 归一化向量
     */
    static normalize(v) {
        const len = Math.sqrt(v.x * v.x + v.y * v.y);
        return len > 0 ? { x: v.x / len, y: v.y / len } : { x: 0, y: 0 };
    }
    
    /**
     * 检测圆与多边形碰撞
     */
    static testCirclePolygon(circle, polygon) {
        // 圆心到最近边的检测
        let minDistSq = Infinity;
        let closestPoint = null;
        
        for (let i = 0; i < polygon.length; i++) {
            const p1 = polygon[i];
            const p2 = polygon[(i + 1) % polygon.length];
            
            const closest = this.closestPointOnSegment(circle.center, p1, p2);
            const distSq = this.distanceSquared(circle.center, closest);
            
            if (distSq < minDistSq) {
                minDistSq = distSq;
                closestPoint = closest;
            }
        }
        
        // 检查是否在圆内
        if (minDistSq <= circle.radius * circle.radius) {
            const dist = Math.sqrt(minDistSq);
            const normal = this.normalize({
                x: circle.center.x - closestPoint.x,
                y: circle.center.y - closestPoint.y
            });
            
            return {
                overlap: circle.radius - dist,
                normal: normal,
                point: closestPoint
            };
        }
        
        return null;
    }
    
    /**
     * 点到线段的最近点
     */
    static closestPointOnSegment(point, segStart, segEnd) {
        const dx = segEnd.x - segStart.x;
        const dy = segEnd.y - segStart.y;
        const lenSq = dx * dx + dy * dy;
        
        if (lenSq === 0) return segStart;
        
        let t = ((point.x - segStart.x) * dx + (point.y - segStart.y) * dy) / lenSq;
        t = Math.max(0, Math.min(1, t));
        
        return {
            x: segStart.x + t * dx,
            y: segStart.y + t * dy
        };
    }
    
    static distanceSquared(p1, p2) {
        const dx = p1.x - p2.x;
        const dy = p1.y - p2.y;
        return dx * dx + dy * dy;
    }
}

---

11.4 GJK 算法

11.4.1 GJK 原理

GJK 算法（Gilbert-Johnson-Keerthi）

GJK 是一种高效的凸体碰撞检测算法，
基于闵可夫斯基差（Minkowski Difference）。


闵可夫斯基差：

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

两个凸体碰撞 ⟺ 它们的闵可夫斯基差包含原点


图示：

   A           B              A ⊖ B
  ┌─┐         ┌─┐
  │ │    -    │ │    =     包含原点？
  └─┘         └─┘

如果 A 和 B 相交，则 A⊖B 包含原点。


GJK 的核心：
不需要实际计算闵可夫斯基差，
而是在其上迭代搜索，检查是否能"包围"原点。

支撑函数（Support Function）：
S(d) = 在方向 d 上最远的点

闵可夫斯基差的支撑函数：
S_A⊖B(d) = S_A(d) - S_B(-d)

11.4.2 GJK 实现

/**
 * GJK 碰撞检测
 */
class GJK {
    /**
     * 支撑函数：返回凸体在方向 d 上最远的点
     */
    static support(vertices, direction) {
        let maxDot = -Infinity;
        let maxVertex = null;
        
        for (const v of vertices) {
            const dot = v.x * direction.x + v.y * direction.y;
            if (dot > maxDot) {
                maxDot = dot;
                maxVertex = v;
            }
        }
        
        return maxVertex;
    }
    
    /**
     * 闵可夫斯基差的支撑函数
     */
    static supportMinkowski(shapeA, shapeB, direction) {
        const supportA = this.support(shapeA, direction);
        const supportB = this.support(shapeB, { x: -direction.x, y: -direction.y });
        
        return {
            x: supportA.x - supportB.x,
            y: supportA.y - supportB.y
        };
    }
    
    /**
     * GJK 碰撞测试
     * @param shapeA 凸多边形顶点数组
     * @param shapeB 凸多边形顶点数组
     * @returns 是否碰撞
     */
    static test(shapeA, shapeB) {
        // 初始方向（任意非零向量）
        let direction = { x: 1, y: 0 };
        
        // 单纯形（2D 中最多 3 个点）
        const simplex = [];
        
        // 第一个支撑点
        const firstPoint = this.supportMinkowski(shapeA, shapeB, direction);
        simplex.push(firstPoint);
        
        // 新方向指向原点
        direction = { x: -firstPoint.x, y: -firstPoint.y };
        
        const maxIterations = 100;
        
        for (let i = 0; i < maxIterations; i++) {
            // 获取新的支撑点
            const newPoint = this.supportMinkowski(shapeA, shapeB, direction);
            
            // 检查新点是否越过原点
            if (newPoint.x * direction.x + newPoint.y * direction.y <= 0) {
                // 无法越过原点，不碰撞
                return false;
            }
            
            simplex.push(newPoint);
            
            // 处理单纯形
            if (this.handleSimplex(simplex, direction)) {
                // 单纯形包含原点，碰撞
                return true;
            }
        }
        
        return false;
    }
    
    /**
     * 处理单纯形，更新搜索方向
     */
    static handleSimplex(simplex, direction) {
        if (simplex.length === 2) {
            return this.handleLine(simplex, direction);
        } else if (simplex.length === 3) {
            return this.handleTriangle(simplex, direction);
        }
        return false;
    }
    
    /**
     * 处理线段单纯形
     */
    static handleLine(simplex, direction) {
        const b = simplex[0];
        const a = simplex[1]; // 最新添加的点
        
        const ab = { x: b.x - a.x, y: b.y - a.y };
        const ao = { x: -a.x, y: -a.y };
        
        // 新方向垂直于 AB，指向原点
        direction.x = ab.y * (ab.y * ao.x - ab.x * ao.y);
        direction.y = -ab.x * (ab.y * ao.x - ab.x * ao.y);
        
        // 更简单的三重积计算
        const perp = this.tripleProduct(ab, ao, ab);
        direction.x = perp.x;
        direction.y = perp.y;
        
        return false;
    }
    
    /**
     * 处理三角形单纯形
     */
    static handleTriangle(simplex, direction) {
        const c = simplex[0];
        const b = simplex[1];
        const a = simplex[2]; // 最新添加的点
        
        const ab = { x: b.x - a.x, y: b.y - a.y };
        const ac = { x: c.x - a.x, y: c.y - a.y };
        const ao = { x: -a.x, y: -a.y };
        
        // AB 边的外法向量
        const abPerp = this.tripleProduct(ac, ab, ab);
        // AC 边的外法向量
        const acPerp = this.tripleProduct(ab, ac, ac);
        
        // 原点在 AB 外侧
        if (abPerp.x * ao.x + abPerp.y * ao.y > 0) {
            simplex.splice(0, 1); // 移除 C
            direction.x = abPerp.x;
            direction.y = abPerp.y;
            return false;
        }
        
        // 原点在 AC 外侧
        if (acPerp.x * ao.x + acPerp.y * ao.y > 0) {
            simplex.splice(1, 1); // 移除 B
            direction.x = acPerp.x;
            direction.y = acPerp.y;
            return false;
        }
        
        // 原点在三角形内
        return true;
    }
    
    /**
     * 三重积 (A × B) × C
     * 2D 简化版本
     */
    static tripleProduct(a, b, c) {
        // (A × B) × C = B(A·C) - A(B·C)
        const ac = a.x * c.x + a.y * c.y;
        const bc = b.x * c.x + b.y * c.y;
        
        return {
            x: b.x * ac - a.x * bc,
            y: b.y * ac - a.y * bc
        };
    }
}

---

11.5 连续碰撞检测

11.5.1 CCD 的必要性

连续碰撞检测（Continuous Collision Detection）

问题：离散碰撞检测可能错过高速物体的碰撞

帧 N：               帧 N+1：
  ●                        ○        ●（子弹）
  │                        │        ↓
  │   ═══  墙壁            │   ═══  墙壁
  │                        │
  ○                        ●

子弹在两帧之间"穿过"了墙壁！


CCD 的解决方案：

将运动轨迹视为"扫掠体"（Swept Volume）

  ●━━━━━━━━━━━━━━━●   子弹轨迹
       │
       │   ═══  墙壁
       │
  
检测轨迹是否与其他物体相交

11.5.2 CCD 实现

/**
 * 连续碰撞检测
 */
class ContinuousCollision {
    /**
     * 射线与 AABB 的最早碰撞时间
     */
    static rayAABB(origin, velocity, aabb) {
        let tmin = 0;
        let tmax = 1; // 本帧内
        
        for (const axis of ['x', 'y', 'z']) {
            if (Math.abs(velocity[axis]) < 1e-10) {
                // 静止
                if (origin[axis] < aabb.min[axis] || origin[axis] > aabb.max[axis]) {
                    return null;
                }
            } else {
                let t1 = (aabb.min[axis] - origin[axis]) / velocity[axis];
                let t2 = (aabb.max[axis] - origin[axis]) / velocity[axis];
                
                if (t1 > t2) [t1, t2] = [t2, t1];
                
                tmin = Math.max(tmin, t1);
                tmax = Math.min(tmax, t2);
                
                if (tmin > tmax) return null;
            }
        }
        
        return tmin >= 0 && tmin <= 1 ? tmin : null;
    }
    
    /**
     * 运动球与静止 AABB 的碰撞
     */
    static sphereAABB(sphere, velocity, aabb) {
        // 扩展 AABB（闵可夫斯基和）
        const expandedAABB = new AABB(
            {
                x: aabb.min.x - sphere.radius,
                y: aabb.min.y - sphere.radius,
                z: aabb.min.z - sphere.radius
            },
            {
                x: aabb.max.x + sphere.radius,
                y: aabb.max.y + sphere.radius,
                z: aabb.max.z + sphere.radius
            }
        );
        
        // 射线检测
        return this.rayAABB(sphere.center, velocity, expandedAABB);
    }
    
    /**
     * 两个运动圆的碰撞
     * @param c1 圆1 {center, radius}
     * @param v1 速度1
     * @param c2 圆2
     * @param v2 速度2
     */
    static movingCircles(c1, v1, c2, v2) {
        // 相对运动
        const relVel = {
            x: v1.x - v2.x,
            y: v1.y - v2.y
        };
        
        // 相对位置
        const relPos = {
            x: c1.center.x - c2.center.x,
            y: c1.center.y - c2.center.y
        };
        
        const sumRadius = c1.radius + c2.radius;
        
        // 二次方程求解碰撞时间
        // |relPos + t * relVel|² = sumRadius²
        const a = relVel.x * relVel.x + relVel.y * relVel.y;
        const b = 2 * (relPos.x * relVel.x + relPos.y * relVel.y);
        const c = relPos.x * relPos.x + relPos.y * relPos.y - sumRadius * sumRadius;
        
        // 当前是否已经重叠
        if (c < 0) return 0;
        
        // 没有相对运动
        if (a < 1e-10) return null;
        
        const discriminant = b * b - 4 * a * c;
        
        if (discriminant < 0) return null;
        
        const t = (-b - Math.sqrt(discriminant)) / (2 * a);
        
        if (t >= 0 && t <= 1) return t;
        
        return null;
    }
}

---

11.6 物理引擎基础

11.6.1 碰撞响应

碰撞响应

检测到碰撞后，需要：

1. 位置修正
   - 将重叠的物体分开
   - 使用穿透深度和法向量

2. 速度修正
   - 应用冲量改变速度
   - 考虑弹性系数


冲量公式（弹性碰撞）：

         -(1 + e)(v_rel · n)
j = ──────────────────────────────
     1/m_a + 1/m_b + ...

其中：
- e：弹性系数（0=完全非弹性，1=完全弹性）
- v_rel：相对速度
- n：碰撞法向量
- m_a, m_b：质量


速度更新：
v_a' = v_a + (j/m_a) × n
v_b' = v_b - (j/m_b) × n

11.6.2 简单物理引擎

/**
 * 简单 2D 物理引擎
 */
class SimplePhysics {
    constructor() {
        this.bodies = [];
        this.gravity = { x: 0, y: 9.8 };
    }
    
    /**
     * 添加刚体
     */
    addBody(body) {
        this.bodies.push(body);
    }
    
    /**
     * 更新物理
     */
    update(dt) {
        // 1. 应用力（重力）
        for (const body of this.bodies) {
            if (!body.isStatic) {
                body.velocity.x += this.gravity.x * dt;
                body.velocity.y += this.gravity.y * dt;
            }
        }
        
        // 2. 碰撞检测与响应
        this.handleCollisions();
        
        // 3. 更新位置
        for (const body of this.bodies) {
            if (!body.isStatic) {
                body.position.x += body.velocity.x * dt;
                body.position.y += body.velocity.y * dt;
            }
        }
    }
    
    /**
     * 处理碰撞
     */
    handleCollisions() {
        for (let i = 0; i < this.bodies.length; i++) {
            for (let j = i + 1; j < this.bodies.length; j++) {
                const bodyA = this.bodies[i];
                const bodyB = this.bodies[j];
                
                const collision = this.detectCollision(bodyA, bodyB);
                
                if (collision) {
                    this.resolveCollision(bodyA, bodyB, collision);
                }
            }
        }
    }
    
    /**
     * 碰撞检测（圆形）
     */
    detectCollision(bodyA, bodyB) {
        const dx = bodyB.position.x - bodyA.position.x;
        const dy = bodyB.position.y - bodyA.position.y;
        const distSq = dx * dx + dy * dy;
        const radiusSum = bodyA.radius + bodyB.radius;
        
        if (distSq < radiusSum * radiusSum) {
            const dist = Math.sqrt(distSq);
            return {
                normal: dist > 0 ? { x: dx / dist, y: dy / dist } : { x: 1, y: 0 },
                depth: radiusSum - dist
            };
        }
        
        return null;
    }
    
    /**
     * 碰撞响应
     */
    resolveCollision(bodyA, bodyB, collision) {
        const { normal, depth } = collision;
        
        // 1. 位置修正
        const totalMass = bodyA.mass + bodyB.mass;
        const moveA = bodyA.isStatic ? 0 : bodyB.mass / totalMass;
        const moveB = bodyB.isStatic ? 0 : bodyA.mass / totalMass;
        
        if (!bodyA.isStatic) {
            bodyA.position.x -= normal.x * depth * moveA;
            bodyA.position.y -= normal.y * depth * moveA;
        }
        if (!bodyB.isStatic) {
            bodyB.position.x += normal.x * depth * moveB;
            bodyB.position.y += normal.y * depth * moveB;
        }
        
        // 2. 速度修正（弹性碰撞）
        const relVel = {
            x: bodyA.velocity.x - bodyB.velocity.x,
            y: bodyA.velocity.y - bodyB.velocity.y
        };
        
        const relVelNormal = relVel.x * normal.x + relVel.y * normal.y;
        
        // 分离中则不处理
        if (relVelNormal > 0) return;
        
        // 弹性系数
        const e = Math.min(bodyA.restitution, bodyB.restitution);
        
        // 冲量大小
        const invMassA = bodyA.isStatic ? 0 : 1 / bodyA.mass;
        const invMassB = bodyB.isStatic ? 0 : 1 / bodyB.mass;
        
        const j = -(1 + e) * relVelNormal / (invMassA + invMassB);
        
        // 应用冲量
        if (!bodyA.isStatic) {
            bodyA.velocity.x += j * invMassA * normal.x;
            bodyA.velocity.y += j * invMassA * normal.y;
        }
        if (!bodyB.isStatic) {
            bodyB.velocity.x -= j * invMassB * normal.x;
            bodyB.velocity.y -= j * invMassB * normal.y;
        }
    }
}

/**
 * 刚体类
 */
class RigidBody {
    constructor(options = {}) {
        this.position = options.position || { x: 0, y: 0 };
        this.velocity = options.velocity || { x: 0, y: 0 };
        this.mass = options.mass || 1;
        this.radius = options.radius || 10;
        this.restitution = options.restitution ?? 0.5; // 弹性系数
        this.isStatic = options.isStatic || false;
    }
}

---

11.7 本章小结

碰撞检测算法对比

算法	适用形状	复杂度	优点
AABB	轴对齐盒	O(1)	最快
球体	球	O(1)	旋转不变
SAT	凸多边形	O(n²)	通用、准确
GJK	凸体	O(n)	高效、支持距离查询
CCD	运动物体	O(n)	防止穿透

碰撞检测流程

粗检测（Broad Phase）
        │
        ├── 空间划分（四叉树、八叉树）
        ├── 扫描排序（Sort and Sweep）
        │
        ▼
精检测（Narrow Phase）
        │
        ├── AABB / 包围球快速剔除
        ├── SAT / GJK 精确检测
        │
        ▼
碰撞响应
        │
        ├── 位置修正
        └── 速度修正（冲量）

关键要点

1. 使用两阶段检测：粗检测 + 精检测
2. AABB 是最快的包围体检测
3. SAT 适用于凸多边形，简单易懂
4. GJK 更高效，适合复杂凸体
5. 高速物体需要连续碰撞检测（CCD）

---

下一章预告：在第12章中，我们将学习空间索引与加速结构，包括四叉树、八叉树和 BVH。

---

文档版本：v1.0
字数统计：约 11,000 字