轴对齐边界盒(AABB)算法

Created by miccall (转载请注明出处 miccall.tech)

目录

最近发布的 DXR 很多人都看了,都是赞不绝口,什么 光线追踪的有一次革命来了,实时光线追踪不远了,什么什么的。。。

然后莫名其妙一群人就开始搞光线追踪了,网上相关的文章蜂拥而至。迫于这个压力,我把尘封已久的光线追踪代码拿出来又看了一下。想想那时还是一个大一的孩子,然而现在的我却看不懂当初的代码。然后又研究了一下AABB算法,当时看的我一脸懵逼,看看网上也没有相关合理的解释,我就想写一篇文章总结一下,顺便发挥一下我ipad的生产力工具的作用。

首先,从基本的球开始 ,光线追踪的原理就是当光线方程与球体方程相交时,联立两个方程,求出一个t值。

光线追踪方程 R(t) = O + t * D , 球的方程 R^{2} = x^{2} +y^{2} +z^{2}

具体的方法我就不细说了,只要知道,他其实是一个二元一次方程,t 就是他的根 。

但是,当场景里面的物体增多时,就会使得计算变得十分的复杂,光线的计算也会变得非常缓慢,这还不包括射线击中之后,递归调用的反射光线 。

所以在前人的智慧下,用了很多算法来避免复杂的计算,这就时我今天介绍的AABB算法 。

AABB算法的全称是 - axis aligned bounding box (轴对齐-边界盒) ,说白了,他就是一个理想的盒子而已,因为判断 光线 与复杂的物体相交是一个比较费时的计算,当我们用一个包围盒取包围它时,盒子的计算就会降低很多时间 。


图片转自 :
3D数学 AABB(轴对齐矩形边界框)
设想一下这样的边界框带给我们的判断 :


理解了基本思路,我们继续分析,当物体增多时,光有一个边界框时不够的,我们还需要对他们进行分类,分类单纯的分一下就好了,并不是按照对象的什么什么属性分类。

我们要根据它所在的位置,对光线的大致方向做一个预判就OK了。

我们举个例子,把他们分为两个部分,由图可见,当然这两个部分是可以重叠的。我们根据重叠,还可以构建更大的box来表示他们 。

这仿佛又回到了数据结构的范畴,我们就要一层一层的分析他与光线的相交判断。


好了,大概思路就是这样,我们从基本的地方开始,完成这个的全部过程:

射线相交判断:


拓展到三维当中的话,就是这样的:

我们知道了,当光线与平面相交的 t 值 ,也就理解为 ,当 t0 时刻,与平面X0 相交了,在t1时刻,又与X1平面相交了。

但是,这是理想的平面呀,他没有大小,我们的盒子是有大小的呀。

我们可以根据这个原理,分别计算x,y,z,三个方向的t值 。

总结一下这些图 , 在三维空间中,我们必须保证,三个方向都相交,否则,盒子就没有被光线击中。

反过来讲,只要一个面没有被击中,盒子就没有被击中。

我们介绍了光线与一个盒子的相交判断,然后我们来介绍一下,何如对一个球体,构建一个盒子:

一个盒子,其实我们只要有两个点来约束它,就可以知道他的边界了 :max点,他的xyz三个分量,与min点,他的xyz三个分量 ,分别约束了 三个面 :

对于一个球来说,最大的这个边界点,就是他的球心坐标,每个分量都加上他的半径值,

最小的边界点,就是他的球心坐标,每个分量都减去他的半径值。


这样,我们就为一个球体,构建了一个边界框,然后呢,对于场景中,所有的物体都用构建,我们只能运用循环的方式遍历这些物体,为他们添加边界框。

构建边界框的同时,我们不要忘了,还要最重要的一步,就是重叠的边界框,我们要为其构建一个更大的边界框来表示他们。


好了 , 所有的边界框都做完了,我们就来构建这个数据结构,方便我们更快速的进行光线追踪 :

构建方法:

1 .随机选取一个轴

2 .根据当前轴的距离,对物体进行线性排序

3 .递归调用构建,左子树存放最近的盒子,右子数存放第二近的盒子。如果剩下一个盒子了,就在左右两边各复制一个。

最后,就是构建完之后的判断了: