引言
碰撞检测是游戏物理引擎、机器人路径规划、计算机图形学的核心问题。轴对齐包围盒（AABB, Axis-Aligned Bounding Box）是最基础且高效的碰撞检测方法之一，因其结构简单、计算 O(1) 而被广泛应用于商业游戏引擎中。
本文将用 Java 从零实现 AABB 碰撞检测系统，从基础相交测试、扫描剪裁、四叉树空间划分到完整游戏场景模拟，呈现这一基础算法的工程实践。
AABB 基础
定义
AABB 是一个与坐标轴平行的矩形（或长方体）包围盒。在 2D 中表示为：
class AABB {
float minX, minY; // 左下角
float maxX, maxY; // 右上角
}
相交判定
两个 AABB 相交当且仅当它们在所有轴上都有重叠：
AABB A 与 AABB B 相交 ⟺
A.minX ≤ B.maxX 且 A.maxX ≥ B.minX 且
A.minY ≤ B.maxY 且 A.maxY ≥ B.minY
package com.algorithm.aabb;
import java.util.Objects;
/**
* 2D 轴对齐包围盒
* 不可变结构，便于缓存与共享
*/
public final class AABB {
public final float minX, minY;
public final float maxX, maxY;
public AABB(float minX, float minY, float maxX, float maxY) {
// 保证 minX ≤ maxX 等
if (minX > maxX || minY > maxY) {
throw new IllegalArgumentException("Invalid AABB bounds");
}
this.minX = minX;
this.minY = minY;
this.maxX = maxX;
this.maxY = maxY;
}
public static AABB fromCenter(float cx, float cy, float halfWidth, float halfHeight) {
return new AABB(cx - halfWidth, cy - halfHeight, cx + halfWidth, cy + halfHeight);
}
public float width() { return maxX - minX; }
public float height() { return maxY - minY; }
public float area() { return width() * height(); }
/**
* 判断两个 AABB 是否相交（包含边界）
* 复杂度：O(1)
*/
public boolean intersects(AABB other) {
return minX <= other.maxX && maxX >= other.minX &&
minY <= other.maxY && maxY >= other.minY;
}
/**
* 判断 AABB 是否包含点 (x, y)
*/
public boolean contains(float x, float y) {
return x >= minX && x <= maxX && y >= minY && y <= maxY;
}
/**
* 计算两个 AABB 的相交区域
* @return 相交 AABB，不相交返回 null
*/
public AABB intersection(AABB other) {
float ixMin = Math.max(minX, other.minX);
float iyMin = Math.max(minY, other.minY);
float ixMax = Math.min(maxX, other.maxX);
float iyMax = Math.min(maxY, other.maxY);
if (ixMin > ixMax || iyMin > iyMax) return null;
return new AABB(ixMin, iyMin, ixMax, iyMax);
}
/**
* 平移 AABB，返回新对象
*/
public AABB translate(float dx, float dy) {
return new AABB(minX + dx, minY + dy, maxX + dx, maxY + dy);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof AABB)) return false;
AABB other = (AABB) o;
return Float.compare(minX, other.minX) == 0 &&
Float.compare(minY, other.minY) == 0 &&
Float.compare(maxX, other.maxX) == 0 &&
Float.compare(maxY, other.maxY) == 0;
}
@Override
public int hashCode() {
return Objects.hash(minX, minY, maxX, maxY);
}
}
运动 AABB 与扫掠测试
对于高速运动的物体，需要做扫掠测试（Swept AABB）以避免”穿透”现象。
package com.algorithm.aabb;
/**
* 运动 AABB：用于移动物体的连续碰撞检测
* 通过在每个轴上求解进入/离开时间，避免穿透
*/
public class MovingAABB {
public final AABB box; // 当前位置
public final float dx, dy; // 位移向量
public final float invDx, invDy; // 位移倒数（用于快速求交）
public MovingAABB(AABB box, float dx, float dy) {
this.box = box;
this.dx = dx;
this.dy = dy;
// 避免除零
this.invDx = (dx == 0) ? Float.POSITIVE_INFINITY : 1.0f / dx;
this.invDy = (dy == 0) ? Float.POSITIVE_INFINITY : 1.0f / dy;
}
/**
* 静态 AABB 的扩展 AABB（包含扫掠路径）
*/
public AABB sweptBoundingBox() {
return new AABB(
dx > 0 ? box.minX : box.minX + dx,
dy > 0 ? box.minY : box.minY + dy,
dx > 0 ? box.maxX + dx : box.maxX,
dy > 0 ? box.maxY + dy : box.maxY
);
}
}
SAP 扫描剪裁算法
当物体在某一轴上排序后，可以利用扫描剪裁（SAP, Sweep and Prune）大幅减少碰撞检测的次数。
package com.algorithm.aabb;
import java.util.*;
/**
* SAP（Sweep and Prune）扫描剪裁算法
* 适用于大量物体在某一方向相对静止或缓慢移动的场景
* 时间复杂度：O(n log n + k)，其中 k 为实际碰撞对数
*/
public class SweepAndPrune {
private final List<AABB> objects;
private float[] endPoints; // 端点数组：偶数索引为 min，奇数为 max
private int[] indices; // 端点对应的物体索引
private boolean[] active; // 物体是否激活
private int size;
public SweepAndPrune(int capacity) {
this.objects = new ArrayList<>(capacity);
this.endPoints = new float[capacity * 2];
this.indices = new int[capacity * 2];
this.active = new boolean[capacity];
this.size = 0;
}
public int addObject(AABB box) {
int id = size++;
objects.add(box);
active[id] = true;
endPoints[id * 2] = box.minX;
endPoints[id * 2 + 1] = box.maxX;
indices[id * 2] = id;
indices[id * 2 + 1] = id;
return id;
}
/**
* 对端点排序（按 X 坐标）
* 使用插入排序：相邻帧的端点变化小
*/
public void sortEndpoints() {
// 简化实现：使用 ArrayList 排序
List<float[]> list = new ArrayList<>();
for (int i = 0; i < size; i++) {
list.add(new float[]{endPoints[i * 2], indices[i * 2]});
list.add(new float[]{endPoints[i * 2 + 1], indices[i * 2 + 1]});
}
list.sort(Comparator.comparingDouble(a -> a[0]));
for (int i = 0; i < list.size(); i++) {
if (i % 2 == 0) {
endPoints[i] = list.get(i)[0];
indices[i] = (int) list.get(i)[1];
} else {
endPoints[i] = list.get(i)[0];
indices[i] = (int) list.get(i)[1];
}
}
}
/**
* 检测所有碰撞对
*/
public List<int[]> findCollisions() {
sortEndpoints();
Set<Long> pairs = new HashSet<>();
List<int[]> collisions = new ArrayList<>();
Set<Integer> open = new HashSet<>();
for (int i = 0; i < size * 2; i++) {
int objId = indices[i];
if (i % 2 == 0) {
// 物体开始：检查所有已开启的物体
for (int other : open) {
if (objId == other) continue;
AABB a = objects.get(objId);
AABB b = objects.get(other);
if (a.intersects(b)) {
long key = ((long) Math.min(objId, other) << 32) |
Math.max(objId, other);
if (pairs.add(key)) {
collisions.add(new int[]{Math.min(objId, other),
Math.max(objId, other)});
}
}
}
open.add(objId);
} else {
// 物体结束：从开启集合中移除
open.remove(objId);
}
}
return collisions;
}
}
四叉树空间划分
四叉树（Quadtree）通过递归地将二维空间划分为四个象限，将碰撞检测从 O(n²) 降到 O(n log n)。
package com.algorithm.aabb;
import java.util.ArrayList;
import java.util.List;
/**
* 四叉树：2D 空间划分数据结构
* 适用于稀疏分布的对象集合
* 节点容量满时分裂为 4 个子节点
*/
public class Quadtree {
private static final int MAX_OBJECTS = 4; // 节点最大容量
private static final int MAX_LEVELS = 5; // 最大深度
private final int level;
private final AABB bounds;
private final List<AABB> objects; // 当前节点的对象
private final List<Quadtree> children; // 四个子节点
public Quadtree(int level, AABB bounds) {
this.level = level;
this.bounds = bounds;
this.objects = new ArrayList<>();
this.children = new ArrayList<>();
}
/**
* 清除四叉树
*/
public void clear() {
objects.clear();
for (Quadtree child : children) {
child.clear();
}
children.clear();
}
/**
* 插入对象
*/
public void insert(int objectId, AABB box) {
// 如果有子节点，递归插入
if (!children.isEmpty()) {
int index = getIndex(box);
if (index != -1) {
children.get(index).insert(objectId, box);
return;
}
}
// 否则加入当前节点
objects.add(box);
// 容量超限且未达最大深度：分裂
if (objects.size() > MAX_OBJECTS && level < MAX_LEVELS) {
if (children.isEmpty()) split();
// 重新分配已有对象
List<AABB> remaining = new ArrayList<>();
for (AABB obj : objects) {
int index = getIndex(obj);
if (index != -1) {
children.get(index).insert(objectId, obj);
} else {
remaining.add(obj);
}
}
objects.clear();
objects.addAll(remaining);
}
}
/**
* 分裂为四象限
*/
private void split() {
float subWidth = bounds.width() / 2;
float subHeight = bounds.height() / 2;
float x = bounds.minX;
float y = bounds.minY;
children.add(new Quadtree(level + 1,
new AABB(x + subWidth, y, x + 2 * subWidth, y + subHeight))); // 右上
children.add(new Quadtree(level + 1,
new AABB(x, y, x + subWidth, y + subHeight))); // 左上
children.add(new Quadtree(level + 1,
new AABB(x, y + subHeight, x + subWidth, y + 2 * subHeight))); // 左下
children.add(new Quadtree(level + 1,
new AABB(x + subWidth, y + subHeight, x + 2 * subWidth, y + 2 * subHeight))); // 右下
}
/**
* 确定 AABB 属于哪个象限
* @return 0-3 象限索引，完全跨界返回 -1
*/
private int getIndex(AABB box) {
int index = -1;
double verticalMidpoint = bounds.minX + bounds.width() / 2;
double horizontalMidpoint = bounds.minY + bounds.height() / 2;
// 上半部分（y < horizontalMidpoint）
boolean topQuadrant = box.maxY < horizontalMidpoint;
// 下半部分
boolean bottomQuadrant = box.minY > horizontalMidpoint;
// 左半部分
boolean leftQuadrant = box.maxX < verticalMidpoint;
// 右半部分
boolean rightQuadrant = box.minX > verticalMidpoint;
if (leftQuadrant) {
if (topQuadrant) index = 1;
else if (bottomQuadrant) index = 2;
} else if (rightQuadrant) {
if (topQuadrant) index = 0;
else if (bottomQuadrant) index = 3;
}
return index;
}
/**
* 检索与目标 AABB 可能有碰撞的所有对象
*/
public List<AABB> retrieve(AABB box) {
List<AABB> found = new ArrayList<>();
int index = getIndex(box);
if (index != -1 && !children.isEmpty()) {
found.addAll(children.get(index).retrieve(box));
} else {
for (Quadtree child : children) {
found.addAll(child.retrieve(box));
}
}
found.addAll(objects);
return found;
}
}
动态 AABB 演示
package com.algorithm.aabb;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
/**
* 动态 AABB 演示：模拟大量移动物体的碰撞检测
* 对比朴素 O(n²) 与四叉树/SAP 的性能差异
*/
public class CollisionDemo {
static class MovingObject {
AABB box;
float vx, vy;
int id;
MovingObject(int id, AABB box, float vx, float vy) {
this.id = id;
this.box = box;
this.vx = vx;
this.vy = vy;
}
void update() {
// 简化：随机移动并反弹
float nx = box.minX + vx;
if (nx < 0 || nx + box.width() > 1000) vx = -vx;
box = box.translate(vx, vy);
float ny = box.minY + vy;
if (ny < 0 || ny + box.height() > 1000) vy = -vy;
}
}
/**
* 朴素 O(n²) 碰撞检测
*/
public static int bruteForceCollision(List<MovingObject> objects) {
int count = 0;
for (int i = 0; i < objects.size(); i++) {
for (int j = i + 1; j < objects.size(); j++) {
if (objects.get(i).box.intersects(objects.get(j).box)) {
count++;
}
}
}
return count;
}
/**
* 四叉树碰撞检测
*/
public static int quadtreeCollision(List<MovingObject> objects) {
Quadtree tree = new Quadtree(0, new AABB(0, 0, 1000, 1000));
for (MovingObject obj : objects) {
tree.insert(obj.id, obj.box);
}
int count = 0;
for (MovingObject obj : objects) {
List<AABB> candidates = tree.retrieve(obj.box);
for (AABB other : candidates) {
if (other != obj.box && obj.box.intersects(other)) {
count++;
}
}
}
return count / 2; // 每对被检测两次
}
public static void main(String[] args) {
int n = 1000;
Random rand = new Random(42);
List<MovingObject> objects = new ArrayList<>();
for (int i = 0; i < n; i++) {
float x = rand.nextFloat() * 900;
float y = rand.nextFloat() * 900;
float size = 20 + rand.nextFloat() * 30;
AABB box = new AABB(x, y, x + size, y + size);
float vx = (rand.nextFloat() - 0.5f) * 4;
float vy = (rand.nextFloat() - 0.5f) * 4;
objects.add(new MovingObject(i, box, vx, vy));
}
// 性能对比
long start = System.nanoTime();
int c1 = bruteForceCollision(objects);
long t1 = System.nanoTime() - start;
start = System.nanoTime();
int c2 = quadtreeCollision(objects);
long t2 = System.nanoTime() - start;
System.out.printf("物体数: %d%n", n);
System.out.printf("朴素 O(n²): %d 碰撞对, 耗时 %d μs%n", c1, t1 / 1000);
System.out.printf("四叉树: %d 碰撞对, 耗时 %d μs%n", c2, t2 / 1000);
System.out.printf("加速比: %.1fx%n", (double) t1 / t2);
}
}
复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 朴素两两检测 | O(n²) | O(1) | 物体数 < 50 |
| 空间哈希 | O(n) 平均 | O(n) | 物体均匀分布 |
| SAP 扫描剪裁 | O(n log n + k) | O(n) | 沿轴相对静止 |
| 四叉树 | O(n log n) | O(n) | 稀疏不均匀分布 |
| 八叉树 (3D) | O(n log n) | O(n) | 3D 空间 |
| BVH | O(n log n) 构建 | O(n) | 静态场景 |
应用场景
- 2D 游戏碰撞检测：Mario、Platformer 游戏中玩家与地砖
- 弹道预测：子弹与目标扫掠测试
- 物理引擎：Box2D 内部大量使用 AABB 粗筛
- GUI 框架：鼠标点击命中测试
- CAD 软件：对象选取
- 机器人路径规划：障碍物检测
- VR/AR：虚拟对象与现实场景交互
进阶话题
旋转 AABB：OBB
AABB 仅适合轴对齐的物体。旋转物体的更紧致包围盒是 OBB（Oriented Bounding Box），使用 SAT（Separating Axis Theorem）检测，复杂度 O(轴数 × 面数)。
连续碰撞检测
对于高速物体（子弹、赛博物理），离散 AABB 检测会产生穿透现象。需要 CCD（Continuous Collision Detection），常见算法包括：
- 扫掠测试：求解进入/离开时间
- 二次积分：保留历史位置做时间切片
- GJK + EPA：凸体之间的精确距离计算
SIMD 加速
现代 CPU 的 SIMD 指令（SSE/AVX）可同时检测 4-8 对 AABB 碰撞，性能提升显著。
总结
AABB 碰撞检测是游戏与图形学的”基础设施”。其优势在于实现简单、计算高效、内存紧凑；不足是不适合旋转对象。工程实践中，AABB 常作为粗筛阶段，再与 OBB、GJK 等精细检测组合使用。掌握 AABB 与空间划分（SAP、四叉树）能让我们设计出支持大量物体的物理引擎。
参考资料
- Ericson, C. (2004). Real-Time Collision Detection. Morgan Kaufmann.
- Akenine-Möller, T., Haines, E., & Hoffman, N. (2018). Real-Time Rendering 4th Edition. CRC Press.
- Box2D Physics Engine – https://box2d.org/
- Christer Ericson’s GameDev Articles: https://realtimecollisiondetection.net/
