C++如何实现基于AABB树的高性能碰撞检测

在游戏物理引擎中，碰撞检测是需要频繁执行的核心逻辑，当场景中存在大量可碰撞物体时，朴素的两两检测会带来极高的时间复杂度，严重影响性能。AABB树通过层次化组织物体的轴对齐包围盒，能够快速剔除不可能发生碰撞的物体对，大幅降低检测开销。

AABB树核心原理

AABB即轴对齐包围盒，是一个与坐标轴对齐的长方体，能够完全包裹对应的物体。AABB树是一棵二叉树，每个节点对应一个AABB包围盒：叶子节点存储单个物体的AABB和物体引用，内部节点存储其两个子节点包围盒的并集，同时记录子节点的指针。

进行碰撞检测时，首先检测两个根节点的包围盒是否相交，若不相交则整棵树中的物体都不可能碰撞；若相交则递归检测两个子节点，直到叶子节点，再对叶子节点对应的实际物体做精确碰撞检测。这种方式可以将检测复杂度从O(n²)降低到接近O(n log n)。

C++实现AABB树的基础结构

AABB包围盒定义

首先需要定义AABB的结构，包含最小点和最大点的坐标，以及相交判断、并集计算的方法：

#include <vector>
#include <algorithm>
#include <cmath>

// 三维向量结构
struct Vec3 {
    float x, y, z;
    Vec3(float x = 0, float y = 0, float z = 0) : x(x), y(y), z(z) {}
    Vec3 operator+(const Vec3& other) const {
        return Vec3(x + other.x, y + other.y, z + other.z);
    }
    Vec3 operator-(const Vec3& other) const {
        return Vec3(x - other.x, y - other.y, z - other.z);
    }
};

// AABB包围盒结构
struct AABB {
    Vec3 min; // 最小点
    Vec3 max; // 最大点

    AABB() : min(Vec3(INFINITY, INFINITY, INFINITY)), max(Vec3(-INFINITY, -INFINITY, -INFINITY)) {}

    // 判断两个AABB是否相交
    bool intersects(const AABB& other) const {
        return (min.x <= other.max.x && max.x >= other.min.x) &&
               (min.y <= other.max.y && max.y >= other.min.y) &&
               (min.z <= other.max.z && max.z >= other.min.z);
    }

    // 计算两个AABB的并集
    AABB merge(const AABB& other) const {
        AABB result;
        result.min.x = std::min(min.x, other.min.x);
        result.min.y = std::min(min.y, other.min.y);
        result.min.z = std::min(min.z, other.min.z);
        result.max.x = std::max(max.x, other.max.x);
        result.max.y = std::max(max.y, other.max.y);
        result.max.z = std::max(max.z, other.max.z);
        return result;
    }

    // 计算AABB表面积，用于构建树时选择划分方式
    float surfaceArea() const {
        float dx = max.x - min.x;
        float dy = max.y - min.y;
        float dz = max.z - min.z;
        return 2 * (dx * dy + dx * dz + dy * dz);
    }
};

AABB树节点定义

树的节点分为内部节点和叶子节点，我们用一个统一的结构表示，通过是否为叶子节点来区分：

// 可碰撞物体基类，实际物体可继承该结构
struct CollidableObject {
    AABB aabb;
    // 其他物体属性，如位置、形状等
    virtual void updateAABB() = 0; // 更新物体的AABB
};

// AABB树节点结构
struct AABBNode {
    AABB aabb; // 节点的包围盒
    AABBNode* left; // 左子节点
    AABBNode* right; // 右子节点
    CollidableObject* object; // 仅叶子节点存储物体，内部节点为nullptr
    bool isLeaf; // 是否为叶子节点

    AABBNode() : left(nullptr), right(nullptr), object(nullptr), isLeaf(false) {}

    // 判断是否为叶子节点
    bool leaf() const { return isLeaf; }
};

AABB树的构建逻辑

构建AABB树的核心是选择合适的划分方式，通常可以按照物体的AABB中心坐标排序后，从中间划分，或者选择表面积增长最小的方式划分。这里采用按X轴中心排序后二分的方式实现：

class AABBTree {
private:
    AABBNode* root;

    // 递归构建AABB树
    AABBNode* buildTree(std::vector<CollidableObject*>& objects, int start, int end) {
        if (end - start == 0) return nullptr;
        AABBNode* node = new AABBNode();
        // 如果是单个物体，创建叶子节点
        if (end - start == 1) {
            node->aabb = objects[start]->aabb;
            node->object = objects[start];
            node->isLeaf = true;
            return node;
        }
        // 计算当前所有物体的总包围盒
        AABB totalAABB;
        for (int i = start; i < end; i++) {
            totalAABB = totalAABB.merge(objects[i]->aabb);
        }
        node->aabb = totalAABB;
        // 按照X轴中心排序划分
        std::sort(objects.begin() + start, objects.begin() + end, [](CollidableObject* a, CollidableObject* b) {
            float centerA = (a->aabb.min.x + a->aabb.max.x) / 2.0f;
            float centerB = (b->aabb.min.x + b->aabb.max.x) / 2.0f;
            return centerA < centerB;
        });
        int mid = (start + end) / 2;
        // 递归构建左右子树
        node->left = buildTree(objects, start, mid);
        node->right = buildTree(objects, mid, end);
        node->isLeaf = false;
        return node;
    }

public:
    AABBTree() : root(nullptr) {}

    // 初始化构建树
    void build(std::vector<CollidableObject*>& objects) {
        root = buildTree(objects, 0, objects.size());
    }
};

碰撞检测实现

碰撞检测从根节点开始递归，先检测节点包围盒是否相交，再深入子节点，直到叶子节点执行精确检测：

// 精确碰撞检测函数，这里简化为AABB相交检测，实际可根据物体形状扩展
bool preciseCollisionCheck(CollidableObject* a, CollidableObject* b) {
    return a->aabb.intersects(b->aabb);
}

class AABBTree {
private:
    AABBNode* root;

    // 递归检测碰撞对
    void queryCollision(AABBNode* nodeA, AABBNode* nodeB, std::vector<std::pair<CollidableObject*, CollidableObject*>>& results) {
        if (!nodeA || !nodeB) return;
        // 两个节点的包围盒不相交，直接返回
        if (!nodeA->aabb.intersects(nodeB->aabb)) return;
        // 如果两个都是叶子节点，执行精确检测
        if (nodeA->leaf() && nodeB->leaf()) {
            if (preciseCollisionCheck(nodeA->object, nodeB->object)) {
                results.emplace_back(nodeA->object, nodeB->object);
            }
            return;
        }
        // 递归检测子节点
        if (nodeA->leaf()) {
            queryCollision(nodeA, nodeB->left, results);
            queryCollision(nodeA, nodeB->right, results);
        } else if (nodeB->leaf()) {
            queryCollision(nodeA->left, nodeB, results);
            queryCollision(nodeA->right, nodeB, results);
        } else {
            queryCollision(nodeA->left, nodeB->left, results);
            queryCollision(nodeA->left, nodeB->right, results);
            queryCollision(nodeA->right, nodeB->left, results);
            queryCollision(nodeA->right, nodeB->right, results);
        }
    }

public:
    AABBTree() : root(nullptr) {}

    // 构建树的方法省略，同上文

    // 检测与指定物体碰撞的所有物体
    void queryCollisions(CollidableObject* object, std::vector<CollidableObject*>& results) {
        if (!root) return;
        queryCollision(root, object, results);
    }

    // 检测树中所有可能碰撞的物体对
    void getAllCollisions(std::vector<std::pair<CollidableObject*, CollidableObject*>>& results) {
        if (!root) return;
        queryCollision(root, root, results);
    }

private:
    // 辅助函数：检测单个节点与另一个节点的碰撞
    void queryCollision(AABBNode* treeNode, CollidableObject* object, std::vector<CollidableObject*>& results) {
        if (!treeNode->aabb.intersects(object->aabb)) return;
        if (treeNode->leaf()) {
            if (preciseCollisionCheck(treeNode->object, object)) {
                results.push_back(treeNode->object);
            }
            return;
        }
        queryCollision(treeNode->left, object, results);
        queryCollision(treeNode->right, object, results);
    }
};

树的动态更新与优化

当物体移动时，其AABB会发生变化，如果重新构建整棵树开销过大，可以采用局部更新的方式：当叶子节点的AABB变化超过一定阈值时，将该节点从树中移除，再重新插入到合适的位置。同时可以定期重构整棵树，避免树的层次失衡导致性能下降。

实际应用中还可以结合其他优化策略，比如给节点添加高度信息，在更新时优先调整高度差较大的节点，或者采用更优的划分策略来降低树的表面积，进一步提升碰撞检测的效率。

AABB_treecollision_detectionC++修改时间：2026-06-13 05:18:52