圖解光線追蹤中，軸對齊邊界盒（AABB）演算法

最近發布的 DXR 很多人都看了，都是讚不絕口，什麼 光線追蹤的有一次革命來了，實時光線追蹤不遠了，什麼什麼的。。。

然後莫名其妙一群人就開始搞光線追蹤了，網上相關的文章蜂擁而至。迫於這個壓力，我把塵封已久的光線追蹤代碼拿出來又看了一下。想想那時還是一個大一的孩子，然而現在的我卻看不懂當初的代碼。然後又研究了一下AABB演算法，當時看的我一臉懵逼，看看網上也沒有相關合理的解釋，我就想寫一篇文章總結一下，順便發揮一下我ipad的生產力工具的作用。

首先，從基本的球開始 ，光線追蹤的原理就是當光線方程與球體方程相交時，聯立兩個方程，求出一個t值。

光線追蹤方程 , 球的方程

具體的方法我就不細說了，只要知道，他其實是一個二元一次方程，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 .遞歸調用構建，左子樹存放最近的盒子，右子數存放第二近的盒子。如果剩下一個盒子了，就在左右兩邊各複製一個。

最後，就是構建完之後的判斷了：

第一次在知乎發文章，如果有大佬過目 ，請多包含與指教 。