JIEZCODE
首页 文章 专题 项目 关于我
JIEZCODE

第-5-章-加速结构-bvh-与空间划分

Jiezcode avatarJiezcode   
         

Course: I wrote a Ray Tracer from scratch… in a Year

🎮 第 5 章：加速结构 —— BVH 与空间划分

🏛 适用环境：CPU 光线追踪 / GPU 路径追踪

🎯 目标：掌握层次包围体（Bounding Volume Hierarchy, BVH）的思想、AABB 计算、递归构建与高效相交测试。

🧭 引擎定位

本章对应渲染器的 Scene Traversal（场景遍历）模块。

在没有加速结构的情况下：

每条光线都要测试所有物体的相交 —— O(N)。

有了 BVH：

通过空间分层剪枝，平均复杂度 ≈ O(log N)。

这就是光线追踪能在现代 GPU 上实时运行的根基。

🏷 关键词速记

BVH｜层次包围体

AABB｜轴对齐包围盒

Spatial Partition｜空间划分

Bounding Volume｜包围体

Node｜节点

Ray–Box Intersection｜光线与包围盒相交

🎮 30 秒玩法摘要

想让光线追踪快？

就别让它乱撞 —— 用盒子一层层包起来，

先看打不打中盒子，再看打不打中物体。

📚 核心原理讲解

🔹 1. 什么是 BVH？

BVH（Bounding Volume Hierarchy） 是一种树形空间结构：

  • 每个节点包围一组物体（Bounding Box）
  • 子节点包围更小的范围
  • 光线只需与盒子相交，决定是否进入下一层

📦 结构示意

BVHNode
 ├── Left  → AABB(子场景)
 │     ├── Sphere #1
 │     └── Sphere #2
 └── Right → AABB(子场景)
       ├── Sphere #3
       └── Sphere #4

🔹 2. AABB（Axis-Aligned Bounding Box）

AABB 是一个沿世界坐标轴对齐的包围盒，定义为：

min=(xmin,ymin,zmin),max=(xmax,ymax,zmax) \text{min} = (x_{min}, y_{min}, z_{min}),\quad \text{max} = (x_{max}, y_{max}, z_{max})

📦 光线与 AABB 相交判断（slab 法）：

bool AABB::hit(const Ray& r, float t_min, float t_max) const {
    for (int a = 0; a < 3; a++) {
        float invD = 1.0f / r.dir[a];
        float t0 = (min[a] - r.origin[a]) * invD;
        float t1 = (max[a] - r.origin[a]) * invD;
        if (invD < 0.0f) std::swap(t0, t1);
        t_min = t0 > t_min ? t0 : t_min;
        t_max = t1 < t_max ? t1 : t_max;
        if (t_max <= t_min) return false;
    }
    return true;
}

✨ 原理：

对每个坐标轴计算射线进入与离开盒子的区间，若三个区间有重叠，则命中。

🔹 3. BVH 构建算法

核心思想：

递归地把物体按空间位置分为两组，

每组生成子节点，直到每个节点只包含少量物体。

📦 构建伪代码

BVHNode::BVHNode(std::vector<shared_ptr<Hittable>>& objects, int start, int end) {
    int axis = randomInt(0, 2);
    auto comparator = (axis == 0) ? boxXCompare
                      : (axis == 1) ? boxYCompare
                                    : boxZCompare;
    size_t objectSpan = end - start;

    if (objectSpan == 1)
        left = right = objects[start];
    else if (objectSpan == 2) {
        if (comparator(objects[start], objects[start+1])) {
            left = objects[start]; right = objects[start+1];
        } else {
            left = objects[start+1]; right = objects[start];
        }
    } else {
        std::sort(objects.begin()+start, objects.begin()+end, comparator);
        auto mid = start + objectSpan / 2;
        left = make_shared<BVHNode>(objects, start, mid);
        right = make_shared<BVHNode>(objects, mid, end);
    }

    AABB boxLeft, boxRight;
    left->boundingBox(boxLeft);
    right->boundingBox(boxRight);
    box = surroundingBox(boxLeft, boxRight);
}

每一层的包围盒范围 = 左右子节点包围盒的最小并集。

🔹 4. BVH 相交遍历

当光线与 BVH 根节点相交时：

1️⃣ 先检测与左右子盒是否相交

2️⃣ 若命中，递归检测子节点内容

3️⃣ 取最近命中点作为结果

📦 相交测试伪代码

bool BVHNode::hit(const Ray& r, float t_min, float t_max, HitRecord& rec) const {
    if (!box.hit(r, t_min, t_max)) return false;

    bool hitLeft = left->hit(r, t_min, t_max, rec);
    bool hitRight = right->hit(r, t_min, hitLeft ? rec.t : t_max, rec);
    return hitLeft || hitRight;
}

⚡ 注意：

如果左子节点已命中且更近，就可提前终止右子检测。

🔹 5. 性能比较

场景规模无 BVH启用 BVH提升倍数
10 物体线性≈线性1x
1,000 物体1000 次检测 / 光线≈10 次检测 / 光线💥 100x
1,000,000 物体不可用可实时🚀 1000x+

BVH 是路径追踪器从“概念验证”到“实用引擎”的分水岭。

🧪 实验与验证步骤

1️⃣ 无 BVH vs BVH 性能测试

  • 创建 1000 个随机球体，渲染 1 帧统计时间。

2️⃣ 盒子可视化

  • 在调试模式下绘制 AABB 线框。
  • 检查层次划分是否均匀。

3️⃣ 复杂场景测试

  • 让摄像机绕场景旋转，验证是否存在“漏光”或“盒错层”。

🪄 创作与实现建议

  • 使用 std::shared_ptr 统一管理节点生命周期。
  • 构建阶段可多线程排序（并行分区）。
  • 小物体数量少时可退化为线性检测。
  • 调试时建议启用包围盒“闪烁显示”，便于观察 BVH 深度分布。
  • 若后期 GPU 化，可直接用 Linear BVH (LBVH) 实现并行构建。

🧠 记忆口诀

“光线遍历别乱撞，盒中层层剪枝忙；

判区间，取重叠，性能百倍飞天翔。”

✅ 实践题

Q1：BVH 的主要作用是什么？

🅰️ 通过空间分层减少光线与物体的相交次数，提高性能。

Q2：AABB 与 OBB 有何区别？

🅰️ AABB 轴向固定，计算快但包围松；OBB 可旋转，包围紧但慢。

Q3：在 BVH 相交中为何要判断 t_max <= t_min？

🅰️ 说明光线已离开包围盒区间，无需继续检测。

是否继续生成第 6 章

👉 《路径追踪与全局光照》（讲解蒙特卡洛积分、间接光反弹、噪点消除与能量守恒）？

 Course Notes
 |