C++ 构建 BVH 树网站首页 技术交流

C++ 构建 BVH 树

小哈龙 2026-06-27 00:01:04

简介C++ 构建 BVH 树

在 C++ 中构建 BVH 树 （Bounding Volume Hierarchy）涉及几个关键步骤，主要包括定义包围盒、构建树结构、递归划分空间等。这里我们将从基础的概念出发，介绍如何使用 C++ 构建 BVH 树。

1. 定义包围盒（Bounding Volume）

在 BVH 中，每个节点通常包含一个包围盒，常见的包围盒类型是 AABB（Axis-Aligned Bounding Box），它是与坐标轴对齐的矩形盒子。

首先，我们定义一个简单的 AABB 类来表示包围盒：

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

struct Vec3 {
    float x, y, z;

    Vec3() : x(0), y(0), z(0) {}
    Vec3(float x, float y, float z) : 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);
    }

    // 计算向量的最大值
    static Vec3 max(const Vec3& a, const Vec3& b) {
        return Vec3(std::max(a.x, b.x), std::max(a.y, b.y), std::max(a.z, b.z));
    }

    // 计算向量的最小值
    static Vec3 min(const Vec3& a, const Vec3& b) {
        return Vec3(std::min(a.x, b.x), std::min(a.y, b.y), std::min(a.z, b.z));
    }
};

struct AABB {
    Vec3 min, max;  // 包围盒的最小和最大坐标

    AABB() {
        min = Vec3(std::numeric_limits<float>::max(), std::numeric_limits<float>::max(), std::numeric_limits<float>::max());
        max = Vec3(-std::numeric_limits<float>::max(), -std::numeric_limits<float>::max(), -std::numeric_limits<float>::max());
    }

    AABB(const Vec3& min, const Vec3& max) : min(min), max(max) {}

    // 更新包围盒
    void expand(const Vec3& point) {
        min = Vec3::min(min, point);
        max = Vec3::max(max, point);
    }

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

2. 定义树节点结构

BVH 树的节点可以是两种类型：内部节点（包含子节点）和叶子节点（包含物体或三角形）。在这里我们定义一个简单的树节点类：

struct BVHNode {
    AABB bbox;      // 包围盒
    BVHNode* left;  // 左子节点
    BVHNode* right; // 右子节点
    std::vector<int> objects; // 对应物体的索引（叶子节点）

    // 叶子节点构造
    BVHNode(const AABB& bbox, const std::vector<int>& objects)
        : bbox(bbox), left(nullptr), right(nullptr), objects(objects) {}

    // 内部节点构造
    BVHNode(const AABB& bbox, BVHNode* left, BVHNode* right)
        : bbox(bbox), left(left), right(right) {}
};

3. 构建 BVH 树

构建 BVH 树的核心步骤是递归地分割物体集合，并为每个子集构建包围盒。通常的构建方法是基于分割轴的选择，常见的策略包括：

中位数分割（Median Split）：将物体集按某一轴（通常是 X、Y 或 Z）上的中位数进行分割。
表面面积启发式（SAH）：通过计算不同分割方式的表面面积，选择最佳的分割方案。

这里我们先实现一个简单的 中位数分割：

class BVH {
public:
    BVH(const std::vector<Vec3>& vertices) : vertices(vertices) {}

    BVHNode* build(std::vector<int>& objects) {
        return buildRecursive(objects, 0, objects.size());
    }

private:
    std::vector<Vec3> vertices;

    BVHNode* buildRecursive(std::vector<int>& objects, int start, int end) {
        if (end - start <= 1) {
            // 如果只有一个物体，返回叶子节点
            AABB bbox = computeBoundingBox(objects, start, end);
            return new BVHNode(bbox, {objects[start]});
        }

        // 计算包围盒
        AABB bbox = computeBoundingBox(objects, start, end);

        // 寻找分割轴，这里简单使用X轴
        int axis = 0;  // 0代表X轴，1代表Y轴，2代表Z轴
        std::sort(objects.begin() + start, objects.begin() + end, [this, axis](int a, int b) {
            return vertices[a][axis] < vertices[b][axis];
        });

        // 中位数分割
        int mid = (start + end) / 2;

        // 递归构建左右子树
        BVHNode* left = buildRecursive(objects, start, mid);
        BVHNode* right = buildRecursive(objects, mid, end);

        // 创建并返回当前节点
        return new BVHNode(bbox, left, right);
    }

    // 计算物体集合的包围盒
    AABB computeBoundingBox(const std::vector<int>& objects, int start, int end) {
        AABB bbox;
        for (int i = start; i < end; ++i) {
            bbox.expand(vertices[objects[i]]);
        }
        return bbox;
    }
};

4. 例子：构建 BVH 树

现在我们可以使用上面的类来构建一个简单的 BVH 树。假设我们有一些物体的顶点位置（vertices），以及它们在这些顶点上所代表的物体索引（objects）。

int main() 
{
    // 假设这些是三维物体的顶点位置
    std::vector<Vec3> vertices = {
        Vec3(1.0f, 2.0f, 3.0f),
        Vec3(4.0f, 5.0f, 6.0f),
        Vec3(7.0f, 8.0f, 9.0f),
        Vec3(2.0f, 3.0f, 1.0f),
        Vec3(5.0f, 6.0f, 7.0f)
    };

    // 假设物体的索引
    std::vector<int> objects = {0, 1, 2, 3, 4};

    BVH bvh(vertices);
    BVHNode* root = bvh.build(objects);

    std::cout << "BVH Tree Built!" << std::endl;
    return 0;
}