3145 字
16 分钟
AABB包围盒和BVH空间划分
2026-05-10
2026-05-26
光线追踪
图形学
/
蒙特卡洛光线追踪器

包围盒的核心思想#

找出一个能够包围物体的盒子,如果光线错过了盒子那么也就会错过盒子里的物品,以此来加速计算.

伪代码:

if (光线 hits 包围盒){
  return 光线是否hits盒中物体
}else{
  return false
}

这里使用的是BVH空间划分,也就是说包围盒可能相交.

图中二叉树没有顺序关系,仅表示包含关系.

伪代码:

if(hits 紫盒子){
  hit0 = hits 蓝盒子中的最近物体
  hit1 = hits 红盒子中的最近物体
  if(hit0 or hit1)
    return true and hit最近物体的信息
}
return false

AABB包围盒#

意思是盒子的面平行于轴平面

我们可以利用区间的重叠部分来表示AABB包围盒

首先我们要求出和包围盒的交点

我们考虑一维的情况

根据光线的定义我们可以求出t0和t1

而考虑二维乃至三维的情况:
我们会发现,仅当光线穿过有界盒体时，绿色与蓝色区间才会产生重叠：

光线与AABB的相交检测#

方式很简单:

interval_x ← compute_intersection_x(ray, x0, x1) // 计算光线位于 AABB 的 x 方向范围 [x0, x1] 内时，对应的光线参数 t 区间
interval_y ← compute_intersection_y(ray, y0, y1) // 计算光线位于 AABB 的 y 方向范围 [y0, y1] 内时，对应的光线参数 t 区间
interval_z ← compute_intersection_z(ray, z0, z1) // 计算光线位于 AABB 的 z 方向范围 [z0, z1] 内时，对应的光线参数 t 区间


return overlaps(interval_x, interval_y, interval_z) // 判断三个方向的 t 区间是否存在公共交集；若存在，则光线与 AABB 相交

但这也存在一定的问题:

t0=x0−Qxdxt1=x1−Qxdx\begin{aligned} t_0 &= \frac{x_0 - Q_x}{d_x} \\ t_1 &= \frac{x_1 - Q_x}{d_x} \end{aligned}

假设光线沿负 𝐱 方向传播。如上计算得出的区间 (𝑡𝑥0,𝑡𝑥1) 可能会反转，例如变成 (7,3) 。其次，分母 𝑑𝑥 可能为零，从而产生无穷值。如果光线原点恰好位于某个平板边界上，由于分子和分母都可能为零，我们会得到一个 NaN 。此外，在使用 IEEE 浮点数时，零会带有正负号

对 𝑑𝑥=0 而言，好消息是 𝑡𝑥0 与 𝑡𝑥1 将相等：若非介于 𝑥0 和 𝑥1 之间，则同为 +∞ 或 -∞。因此，使用最小值和最大值应能得出正确结果：

tx0=min⁡(x0−Qxdx,x1−Qxdx)tx1=max⁡(x0−Qxdx,x1−Qxdx)\begin{aligned} t_{x0} &= \min\left( \frac{x_0 - Q_x}{d_x}, \frac{x_1 - Q_x}{d_x} \right) \\ t_{x1} &= \max\left( \frac{x_0 - Q_x}{d_x}, \frac{x_1 - Q_x}{d_x} \right) \end{aligned}

如果这样做，剩下的棘手情况是当 𝑑𝑥=0 且 𝑥0−𝑄𝑥=0 或 𝑥1−𝑄𝑥=0 时，我们会得到一个 NaN 。在这种情况下，我们可以任意将其解释为命中或未命中，但我们稍后会重新讨论这个问题。

如何判断区间是否重叠,方法很简单,给出两个区间,其中区间的右端点的最小值小于左端点的最大值即认为区间有重叠.

bool overlaps(t_interval1, t_interval2)
    t_min ← max(t_interval1.min, t_interval2.min)
    t_max ← min(t_interval1.max, t_interval2.max)
    return t_min < t_max

如果有任何 NaN 在附近运行，比较将返回 false，因此我们需要确保边界框有一些填充，如果我们关心擦边情况（我们应该关心，因为在光线追踪器中所有情况最终都会出现）。

如果我们认为“擦边也算相交”，就应该给包围盒加一点点 padding，让包围盒稍微变大。这样可以减少因为浮点误差或极端边界情况导致的漏判

为了实现这一点，我们首先添加一个 interval 类的新函数 expand ，它按给定量填充区间：

interval expand(double delta) const {
  auto padding = delta/2;
  return interval(min - padding, max + padding);
}

aabb.h

#ifndef AABB_H
#define AABB_H


#include"interval.h"
#include"vec3.h"
#include"ray.h"


class aabb {
  public:
    // AABB 在三个坐标轴上的投影区间。
    interval x, y, z;


    aabb() {} // 默认 AABB 为空，因为 interval 的默认构造就是空区间。


    aabb(const interval& x, const interval& y, const interval& z)
      : x(x), y(y), z(z) {}


    aabb(const point3& a, const point3& b) {
        // 将 a 和 b 视为包围盒的两个对角顶点；下面分别取每个轴上的较小值和较大值，
        // 因此调用者不需要保证 a 一定是最小角点、b 一定是最大角点。


        x = (a[0] <= b[0]) ? interval(a[0], b[0]) : interval(b[0], a[0]);
        y = (a[1] <= b[1]) ? interval(a[1], b[1]) : interval(b[1], a[1]);
        z = (a[2] <= b[2]) ? interval(a[2], b[2]) : interval(b[2], a[2]);
    }


    const interval& axis_interval(int n) const {
        // 根据轴编号返回对应的投影区间：0 -> x，1 -> y，2 -> z。
        if (n == 1) return y;
        if (n == 2) return z;
        return x;
    }


    bool hit(const ray& r, interval ray_t) const {
        // 使用 slab 方法检测光线是否穿过 AABB。
        // ray_t 表示当前允许的光线参数范围，并会被每个轴的相交区间逐步收窄。
        const point3& ray_orig = r.origin();
        const vec3&   ray_dir  = r.direction();


        for (int axis = 0; axis < 3; axis++) {
            const interval& ax = axis_interval(axis);
            const double adinv = 1.0 / ray_dir[axis];


            // 计算光线与当前轴两侧边界平面相交时的参数 t。
            auto t0 = (ax.min - ray_orig[axis]) * adinv;
            auto t1 = (ax.max - ray_orig[axis]) * adinv;


            // 若光线在该轴方向为负，t0 和 t1 的先后顺序会反过来；
            // 用较大的进入时间更新下界，用较小的离开时间更新上界。
            if (t0 < t1) {
                if (t0 > ray_t.min) ray_t.min = t0;
                if (t1 < ray_t.max) ray_t.max = t1;
            } else {
                if (t1 > ray_t.min) ray_t.min = t1;
                if (t0 < ray_t.max) ray_t.max = t0;
            }


            // 三个轴对应的 t 区间必须存在公共交集；一旦交集为空，就不可能命中 AABB。
            if (ray_t.max <= ray_t.min)
                return false;
        }
        return true;
    }
};

tenter=max(tmin)t_{enter} = max(t_{min}) 进入三个面才叫进入 texit=min(tmax)t_{exit} = min(t_{max}) 离开其中一个面就是离开 需要进入时间 < 离开时间 以上代码即实现对每个对面求出进入时间和离开时间,并缩短区间,看看是否满足.

为可命中物体构建包围盒#

解决了包围盒的计算问题,现在来解决如何在物体上添加包围盒

对sphere类 这里用两个对顶点来求出包围盒

sphere(const point3& center, double radius, std::shared_ptr<material> mat)
        : center(center), radius(std::fmax(0, radius)), mat(mat)
    {
        auto rvec = vec3(radius,radius,radius);
        bbox = aabb(center - rvec, center + rvec); //创建包围盒
    };

我们在这里为interval新增一个构造函数,能够用两个区间来生成一个新的区间并集.

interval(const interval& a, const interval& b) {
  // Create the interval tightly enclosing the two input intervals.
  min = a.min <= b.min ? a.min : b.min;
  max = a.max >= b.max ? a.max : b.max;
}

为aabb类添加构造函数来实现两个小的包围盒合并成一个大的包围盒

aabb(const aabb& bbox0, const aabb& bbox1){
  x = interval(bbox0.x, bbox1.x);
  y = interval(bbox0.y, bbox1.y);
  z = interval(bbox0.z, bbox1.z);
}

为hittable_list创建包围盒#

#include "aabb.h"
#include "hittable.h"


#include <vector>


class hittable_list : public hittable {
  public:
    std::vector<shared_ptr<hittable>> objects;


    ...
    void add(shared_ptr<hittable> object) {
        objects.push_back(object);
        bbox = aabb(bbox, object->bounding_box());
    }


    bool hit(const ray& r, interval ray_t, hit_record& rec) const override {
        ...
    }


    aabb bounding_box() const override { return bbox; }


  private:
    aabb bbox;
};

在添加对象的时候同时将包围盒合并在一起,我们将hittable_list也看作是一个物体

BVH节点类#

将以二叉树的形式来分割包围盒,叶子节点存储物体.

#ifndef BVH_H
#define BVH_H


#include "aabb.h"
#include "hittable.h"
#include "hittable_list.h"


// BVH 节点本身也是一个 hittable。
// 它不是直接表示某个具体物体，而是把一组物体分成左右两部分，
// 并用一个大的包围盒 bbox 把这两部分整体包起来。
// 光线求交时可以先测试 bbox，如果光线连大包围盒都没碰到，
// 就不用继续检查这个节点下面的所有物体，从而加速渲染。
class bvh_node : public hittable {
  public:
    // 从一个 hittable_list 构建整棵 BVH。
    // 这里把整个 list 的 objects 数组交给另一个构造函数处理，
    // start 为 0，end 为 objects.size()，表示使用全部物体。
    bvh_node(hittable_list list) : bvh_node(list.objects, 0, list.objects.size()) {
        // 这里有一个 C++ 的细节。这个构造函数没有传入区间下标，它会隐式拷贝一份
        // hittable_list，而后续构建 BVH 时会修改这份拷贝。这个拷贝出来的 list 生命周期
        // 只持续到构造函数结束。这样没问题，因为我们真正需要保留下来的是最终构建出的
        // 包围体层次结构。
    }


    // 从 objects[start, end) 这一段物体构建一个 BVH 节点。
    // 这个函数通常会：
    // 1. 选择一个坐标轴；
    // 2. 按物体包围盒在该轴上的位置排序；
    // 3. 把物体分成左右两半；
    // 4. 递归构建 left 和 right；
    // 5. 用左右子节点的包围盒合并出当前节点的 bbox。
    bvh_node(std::vector<shared_ptr<hittable>>& objects, size_t start, size_t end) {
        // 稍后实现。
    }


    // 判断光线是否击中当前 BVH 节点里的任意物体。
    bool hit(const ray& r, interval ray_t, hit_record& rec) const override {
        // 先用当前节点的大包围盒做快速测试。
        // 如果光线没有进入这个包围盒，那么它不可能打中里面的任何物体。
        if (!bbox.hit(r, ray_t))
            return false;


        // 光线打中了大包围盒，才继续检查左右子节点。
        bool hit_left = left->hit(r, ray_t, rec);


        // 如果左子节点已经命中，rec.t 会记录当前最近的命中距离。
        // 右子节点只需要寻找比 rec.t 更近的交点；更远的交点即使命中也不会被采用。
        bool hit_right = right->hit(r, interval(ray_t.min, hit_left ? rec.t : ray_t.max), rec);


        // 只要左边或右边任意一个命中，就说明当前 BVH 节点被命中。
        return hit_left || hit_right;
    }


    // 返回当前节点的包围盒。
    // 对叶子节点来说，它包住具体物体；
    // 对内部节点来说，它包住 left 和 right 两个子节点。
    aabb bounding_box() const override { return bbox; }


  private:
    // 左右子节点可以是具体物体，比如 sphere；
    // 也可以是另一个 bvh_node，因此类型统一写成 shared_ptr<hittable>。
    shared_ptr<hittable> left;
    shared_ptr<hittable> right;


    // 当前节点的轴对齐包围盒，包住 left 和 right 代表的所有物体。
    aabb bbox;
};


#endif

分割包围盒空间#

如何切割BVH

  • 选择一个轴
  • 按这个轴给物体排序
  • 把物体分成左右两半
  • 左右两半递归构建 BVH
  • 当前节点 bbox = 左右 bbox 合并
bvh_node(std::vector<shared_ptr<hittable>>& objects, size_t start, size_t end) {
  int axis = random_int(0,2); //随机选择一个坐标轴进行切分


  auto comparator = (axis == 0) ? box_x_compare
          : (axis == 1) ? box_y_compare
                  : box_z_compare; //将随机数转换成x,y,z轴的比较器


  size_t object_span = end - start; //计算区间里有多少个物体


  if (object_span == 1) {
    left = right = objects[start]; //只有一个物体
    //为什么会指向同一个? 原因是后面的代码会检验光线是否射中左右指针,这样写不需要特判
  } else if (object_span == 2) { //只有两个物体,左右指针各指一个
    left = objects[start];
    right = objects[start+1];
  } else {
    //多个物体
    std::sort(std::begin(objects) + start, std::begin(objects) + end, comparator); //按照选定的坐标轴排序


    auto mid = start + object_span/2;
    //递归对半切
    left = make_shared<bvh_node>(objects, start, mid);
    right = make_shared<bvh_node>(objects, mid, end);
  }


  bbox = aabb(left->bounding_box(), right->bounding_box()); //合并成包围盒作为头节点
}

rtweekend.h中的新函数返回随机整数

inline int random_int(int min, int max) {
    // Returns a random integer in [min,max].
    return int(random_double(min, max+1));
}

盒体比较函数#

返回物体包围盒按照轴左区间排序的比较器(递增)

static bool box_compare(
  const shared_ptr<hittable> a, const shared_ptr<hittable> b, int axis_index
) {
  auto a_axis_interval = a->bounding_box().axis_interval(axis_index);
  auto b_axis_interval = b->bounding_box().axis_interval(axis_index);
  return a_axis_interval.min < b_axis_interval.min;
}


static bool box_x_compare (const shared_ptr<hittable> a, const shared_ptr<hittable> b) {
  return box_compare(a, b, 0);
}


static bool box_y_compare (const shared_ptr<hittable> a, const shared_ptr<hittable> b) {
  return box_compare(a, b, 1);
}


static bool box_z_compare (const shared_ptr<hittable> a, const shared_ptr<hittable> b) {
  return box_compare(a, b, 2);
}

在main函数中添加:

world = hittable_list(make_shared<bvh_node>(world));

就可以运行看看结果了,渲染速度大概是之前的近六倍半. 此时运行时间为:478.031 秒

另一个BVH加速#

与其随机选择分割轴,不如每次我们都选择轴最长来进行分割.

以下代码

  1. 计算当前物体区间 [start, end) 的整体包围盒；
  2. 找出这个整体包围盒最长的轴；
  3. 后面会沿这个轴排序并分割物体，用来构建左右 BVH 子树。
bvh_node(std::vector<shared_ptr<hittable>>& objects, size_t start, size_t end) {
  bbox = aabb::empty; //当前节点初始化为空盒子
  for (size_t object_index=start; object_index < end; object_index++)
    bbox = aabb(bbox, objects[object_index]->bounding_box()); //和每一个物体的包围盒合并


  int axis = bbox.longest_axis(); //这个包围盒在哪个方向上最长 0, 1, 2


  ...
}

对aabb.h进行修改,返回最长轴的方法

class aabb {
  public:
    ...


    bool hit(const ray& r, interval ray_t) const {
        ...
    }


    int longest_axis() const {
        if (x.size() > y.size())
            return x.size() > z.size() ? 0 : 2;
        else
            return y.size() > z.size() ? 1 : 2;
    }


    static const aabb empty, universe;
};


const aabb aabb::empty    = aabb(interval::empty,    interval::empty,    interval::empty);
const aabb aabb::universe = aabb(interval::universe, interval::universe, interval::universe);

速度大约快了18%

AABB包围盒和BVH空间划分
https://dingfengbo.vercel.app/posts/rtiow/aabb包围盒和bvh空间划分/
作者
Eureka
发布于
2026-05-10
许可协议
CC BY-NC-SA 4.0
机器学习 (六) : 支持向量机
多线程
© 2026 Eureka. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Fuwari