雖然之前的簡單的包圍盒技術(shù)能夠減少計算開銷，但是對于整個光線跟蹤算法來講算法的效率還是沒有顯著地提高，究其原因主要在于，每一根被跟蹤的光線都需要與場景的包圍盒進行計算，算法的效率還是受到限制，其算法的復(fù)雜度為 O(N)，其中 N 為場景中物體的個數(shù)，即三角形數(shù)目。為了提高包圍盒技術(shù)的效率，通過將包圍盒組織成層次結(jié)構(gòu)來改進簡單的包誒和技術(shù)。其基本的思想為將整個場景按照場景的包圍盒進行組織，根據(jù)物體在場景中的分布，相距很近的物體形成局部場景，然后這些局部場景又可組成更大的組，這樣就形成了整個場景的樹形層次結(jié)構(gòu)。
如何分組時形成樹形層次結(jié)構(gòu)的關(guān)鍵步驟，理想的分組是建立在理想狀況下物體間的相距距離，通過距離的遠近對場景進行分組。層次結(jié)構(gòu)的形狀取決于場景中景物的空
間分布，通常越靠近樹狀結(jié)構(gòu)的底層，包圍盒則越小。建立層次結(jié)構(gòu)常用的策略即“中分面”技術(shù)，該技術(shù)通過二叉剖分技術(shù)對場景進行從上到下的遞歸分組。

使用層次包圍盒技術(shù)的光線跟蹤算法，跟蹤光線首先和場景包圍盒求交，與場景包圍盒相交后再和場景包圍盒割分的包圍盒求交，知道光線和最小包圍盒相交后與最小包圍盒內(nèi)包含的物體面片求交，最終求得交點或是光線與物體無交。在建立場景的層次結(jié)構(gòu)時最重要的步驟就是對整個場景中的物體進行合理的分組，一個理想的層次結(jié)構(gòu)是基于物體之間距離的遠近來進行分組的，層次結(jié)構(gòu)的形狀則依賴于場景中物體在空間的分布情況，一般來說，越靠近底層的結(jié)點，其包圍盒會越小。在建立包圍盒層次結(jié)構(gòu)時常用的方法是——中分面（median-cut）技術(shù)，該技術(shù)使用二叉剖分技術(shù)對整個場景進行自上而下的遞歸劃分。在每一結(jié)點處，首先將其所包含的景物按其 x 坐標(biāo)軸的值進行大小排序，并將該結(jié)點的包圍盒的 x 方向的中分面作為分割面對所含物體劃分為兩組而產(chǎn)生其兩個子結(jié)點，再將兩個子結(jié)點各自依次沿 y 軸和 z 軸兩個方向依照 x 軸進行分組。將上述步驟遞歸進行，直至當(dāng)前結(jié)點只包含一個物體為止。

可以看出，層次包圍盒技術(shù)一方面利用包圍盒技術(shù)避免了跟蹤光線與不相交物體進行無效求交測試，同時又利用包圍盒比較簡單容易與光線進行求交測試，快速的確定于光線相交的物體。這與上小節(jié)中論述的內(nèi)包圍盒的改進算法有相似之處。本方法最終是只包含一個物體，光線只同一個物體進行求交測試，之前的大部分求交都是同包圍盒的求交測試（比較簡單）。

層次包圍盒極大的降低了光線與景物求交測試的計算復(fù)雜度，但是計算量仍然很大，包圍盒通常在空間是無序的，而光線跟蹤需要找到離光線起始點最近的交點，而對于位
于光線后的物體求交計算式無用的。同時光線與物體的求交的效率通常與劃分的層次結(jié)構(gòu)有關(guān)，不同場景求交的效率可能大不相同。雖然包圍體的形狀可以是千奇百怪，可以
使球形也可以是立方體，但是要快速判斷光線與包圍盒的關(guān)系，那么軸對齊包圍盒（AABB）是最簡單的包圍結(jié)構(gòu)，所以通常都選用軸對齊包圍盒作為結(jié)點類型 。

均勻網(wǎng)格

傳統(tǒng)光線跟蹤算法效率不高的主要原因在于光線與物體求交的盲目性、廣泛性，跟蹤光線必須和場景中的所有物體逐一進行求交測試，而且由于光線與物體求交測試的無序性，求交后還要對各交點進行遠近排序以找到最近的交點。從提高光線跟蹤算法效率的方面看，一方面一些物體和光線根本不相交還要作求交測試，另一方面在交點排序中排在后面的交點的求取是無用的。對每一條跟蹤光線，我們所需要的僅僅是它在場景中最先相交的那個物體交點 [2] 。
考慮到場景中的各物體的空間位置是固定的，為了減少光線求交的盲目性，可以將場景空間進行剖分，剖分成很多位置固定的小方格。這些小方格在空間的位置是固定的，而且相互緊密連接著跟蹤光線依次穿越小方格，光線只與它穿越的小方格中的物體面片求交，這就是空間剖分技術(shù)。這些小方格有序的被組織成了層次結(jié)構(gòu)，其葉節(jié)點記錄了它所包含的物體面片表，光線跟蹤時只需要與它依次跨越的各網(wǎng)格空間內(nèi)所含物體作求交測試；另一方面，由于網(wǎng)格空間排列的有序性，光線總會和它最先相遇的物體作求交測試，一旦有交則該光線的跟蹤就結(jié)束，該交點即為最近交點，避免了對最近交點后面物體的求交測試計算及交點的排序。這也是空間剖分技術(shù)的優(yōu)勢之處。

1986 年，Fujimoto 等提出了一個基于空間均勻網(wǎng)格剖分技術(shù)的快速光線跟蹤算法。該技術(shù)將場景空間剖分成一系列的大小均勻的三維網(wǎng)格，每個網(wǎng)格包含一系列的面片。

從而建立起一個稱為 SEADS 的輔助數(shù)據(jù)結(jié)構(gòu)（Spatially Enumerated Auxiliary Data structure）通過指針將包含在網(wǎng)格內(nèi)的面片一一鏈接起來，在跟蹤光線時，只需要計算跟光線經(jīng)過空間的網(wǎng)格內(nèi)的面片進行求交計算。如圖 3.1 給出了包含 10 個面片二維場景的網(wǎng)格剖分及其 SEADS 結(jié)構(gòu)。從圖 3.1 中可以看出，光線 1 只需與面片 7 進行求交測試，而光線 2 則需要分別于面片 5、6、3、4 和 0 進行求交測試，最后得到的交點位于面片 4上。

在 SEADS 機構(gòu)中，每一個剖分出的小立方體可用一個整數(shù)的三維空間坐標(biāo)（i，j，k）來標(biāo)示其位置，每個立方體中均含有其所包含的物體面片信息。光線只與其跟蹤方向上的立方體相交，而且最先穿越的還是最近的，光線和它索穿越的立方體中的物體面片求交，一旦求得交點即為最近交點，這就是 3d-DDA 算法。

（1）若光線和垂直于 i、j 坐標(biāo)軸的當(dāng)前網(wǎng)格界面均相交，那么將距光線起點較近的交點所處界面相對應(yīng)的坐標(biāo)方向設(shè)為增量方向；若光線和這兩個邊界面無交，取主軸方向為增量方向；若和一個邊界面相交，將和光線相交的邊界面相對應(yīng)的坐標(biāo)方向設(shè)為增量方向。
（2）當(dāng)前網(wǎng)格沿第(1)步確定的增量方向位移一格，即得到下一網(wǎng)格的坐標(biāo)。
雖然均勻網(wǎng)格能夠提高光線跟蹤算法的效率，但是它仍然存在一定的弊端，它要求場景中的三角形面片分布比較均勻，這樣在仿真時對場景要進行限制，如果場景中的面片分布不均勻，則均勻網(wǎng)格則不能達到很好的加速效果。特別是當(dāng)場景中物體的三角形面片分布相當(dāng)?shù)南∈钑r，對網(wǎng)格的劃分會包含很多空白網(wǎng)格，這些網(wǎng)格不包含三角形面片，然而在光線在到達含有交點的網(wǎng)格之前，需要穿過很多這樣的空白網(wǎng)格，這樣會大大降低算法的效率。同時由于它在空間劃分的特殊性，多個體素很可能包含相同三角形的多個引用，這就意味相同的光線與相同的三角形存在多次求交測試。

總結(jié)

以上是生活随笔為你收集整理的层次包围盒和均匀网格的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。