RTTNW-ch2:Bounding Volume Hierarchies

这部分是迄今为止我们正在研究的光线追踪器中最困难的部分。

我们的光线与物体相交点是光线追踪器的主要时间瓶颈,时间是与物体的数量呈线性关系。但它是对同一个模型的重复搜索,所以我们可以使用二分搜索进行对数查找。

两个最常见的排序方法是划分空间和划分对象。后者通常是编码起来更容易,而且大多数模型的运行速度都很快。

关键在于在找到一个边界体积包围所有物体。

 

我们要把物体分离到不同的边界框中去,任何一个物体都在一个边界盒中,边界盒有可能重叠。如果我们使用矩形分成红色和蓝色两组,得到如下:

红色框和蓝色框都被包围在紫色盒子中,但是它们可能会重叠,而且它们不是有序的 ,它们都在里面。 所以树上显示的树没有左孩子和右孩子的概念。

一个好的射线与层次包围相交需要快速,并且边界需要紧凑,轴对齐是个不错的方案。

从现在开始,我们将调用轴对齐的边界矩形平行六面体(真的,也就是说,他们需要如何调用)轴对齐边界框或AABB。 任何你想用来与AABB相交的方法很好。 所有我们需要知道的是否我们击中了它; 我们不需要相交点或法线或任何东西需要我们显示的对象。
大多数人使用“slab”方法。 这是基于n维的观察AABB只是n轴对齐的区间的交集,通常称为“平板”。 间隔只是两个端点之间的点,例如,x使得3 <x <5,或者更简洁地x  in(3,5)。 在2D中,两个重叠的区间构成一个2D AABB(一个矩形):

对于一个射线击中一个区间,我们首先需要确定射线是否碰到边界。
例如,在2D中,这是射线参数t0和t1。(如果射线平行于平面那些将是未定义的。)

在3D中,这些边界是平面。平面的方程为x = x0,x = x1。
射线在哪里撞到平面? 回想一下,射线可以被认为只是一个方法,给定一个t返回一个位置p(t):

\(p(t)=A+tB\)

该公式适用于所有三个x / y / z坐标。 例如\(x(t)=Ax+t*Bx\)。这条射线在t满足这个方程时碰到平面x = x0:

\(x_{0}=Ax+t_{0}*Bx\)

因此,t在碰撞点是:

\(t_{0}=(x_{0}-Ax)/Bx\)

同理得到:

\(t_{1}=(x_{1}-Ax)/Bx\)

在一维空间中判定一次命中的关键是在t时间间隔内要有重叠。在二维空间中,如果有命中,绿色和蓝色会有一个重叠,如下面的那条射线。

用代码描述“在slab的t间隔是否重叠”:

在3D中,slab方法依然可以工作,这也是人们喜欢它的原因。

有一些注意事项我们要知道,首先,假设射线在负x方向上行进。间隔(tx0,tx1)如上所述计算可能会逆转,例如(7,3)。第二,那里的鸿沟可能会给我们带无限可能。如果射线源位于一个slab边界上,我们可以得到一个NaN。那里
这些问题在许多光线追踪器的AABB中处理的方式有很多。 (也有像SIMD这样的矢量化问题,我们不在这里讨论。)
目的,只要我们使速度合理快速,这不太可能成为主要瓶颈,所以让我们走最简单的,无论如何,这往往是最快的!首先让我们看看计算间隔:

\(tx_{0}=(x_{0}-Ax)/Bx\),

\(tx_{1}=(x_{1}-Ax)/Bx\)

一个麻烦事是如果Bx=0,造成分离为0.这样的射线有的是在平板内的,有些不在,而且这个0会带正负号。在IEEE浮点标准下,在Bx=0时,t0和t1会都是 正无穷或者负无穷,反正不是x0和x1之间的数字,所以我们可以使用最大值和最小值来解决问题

\(tx_{0}=min((x_{0}-Ax)/Bx,(x_{1}-Ax)/Bx)\),

\(tx_{1}=min((x_{0}-Ax)/Bx,(x_{1}-Ax)/Bx)\)

如果我们这样做,剩下的麻烦情况是如果Bx = 0并且x0-Ax = 0或者x1-Ax= 0,所以我们得到一个NaN。在这种情况下,我们可以返回不命中作为结果。
现在,我们来看看这个重叠函数。假设我们可以假设间隔不是反转(所以第一个值小于间隔中的第二个值),我们想要在那种情况下返回true。布尔重叠也计算重叠区间(f,F)(d,D)和(e,E)的间隔为:

如果有任何NaN在那里运行,比较将返回false,所以我们需要确保我们的边界盒有一些填充。

创建AABB包围盒的类:

我们现在需要添加一个函数来计算所有需求的边界框,并生成它们,这是个重载函数:

sphere的bounding_box函数:

moving_sphere的bounding_box函数:

hitable_list的bounding_box函数:

对于移动球体,我们可以在t0处取球体的方框,在t1处取球体的方框,将t0时的盒子和t1时的盒子放进一个大盒子里:

一个BVH也将是一个可以击中的 ,就像击中列表一样。 这真的是一个容器,但是
它可以回应询问“这光线击中了你?”。 一个设计问题是我们是否有两个类,一个用于树,另一个用于树中的节点; 或者我们只有一个类,并且根只是我们指向的一个节点。这里我们使用一个类:

这里的左右节点都是基类Hitable类型,这样BVH的子节点也有可能是另一个BVH节点或者是一个物体,如果是BVH的话就继续检测其子节点:

任何效率结构中最复杂的部分就是构建这个结构。关于BVH的一个很酷的事情是,只要BVH节点中的对象列表被分成两个子列表,命中检测就可以工作。如果合适分隔,这将最高效,为了生成一个尽量小的,包含所有对象的盒子,我们让每个节点沿一个轴分割列表:

1.  随机选择一个轴
2. 将节点内的对象进行排序
3. 左右子树各放一半

当列表进入是两个元素时,我在每个子树中放一个并结束递归。遍历算法应该是平滑的,不必检查空指针,所以如果我只需要在每个子树中复制一个元素。 明确检查三个元素只是在一次递归之后可能会有所帮助,但我认为整体方法稍后会得到优化。 这产生:

检查是否有边界框是为了防止你发送像一个无限平面一样的东西,它们没有边界框.

x轴compare函数:

 

参考书籍:《Ray Tracing The Next Week》

RTTNW系列项目地址:GitHub