層次包圍體（Bounding volume hierarchies, BVH）是一種基于圖元（Primitive，構成場景的基本元素，如三角形、球面等）劃分的空間索引結構。說它是基于圖元的，是因為它是將場景中的圖元劃分成不相交集的層次結構（Hierarchy of disjoint sets）；與之相對的基于空間（Spatial）劃分的空間索引結構（例如下一節里介紹的KdTree）則是將空間劃分成不相交集的層次結構。

上圖展示了一個簡單場景的BVH，圖元被存儲在葉節點上，每一個節點都存儲了一個包圍了其所有子節點內圖元的包圍盒。

基于圖元劃分的空間索引結構的有幾個重要性質：

• 每一個圖元在整個結構中只會出現一次。但是同一塊空間區域可能會被多個節點所包含。
• 基于圖元劃分的空間索引結構消耗內存的上限是已知的。若每一個節點僅包含兩個子節點，葉節點只存儲一個圖元，所有非葉節點的度都為 ，則總結點的個數為 （ 個葉節點， 個非葉節點，二叉樹的性質）。

BVH相比于KdTree構建效率更高，但是遍歷效率略低。另外，BVH相較于KdTree擁有更好的數值魯棒性，更不容易因為浮點數舍入誤差而導致棄真（實際相交，但是計算結果為不相交）情況的出現。

BVH的構建

整個構建過程可以大致分為三步（第二步和第三步可以直接合并，不過分成三步實現更加便于學習和理解）：

• 計算場景中每一個圖元的AABB包圍盒、質心（一般取包圍盒的中心）并存儲到數組中。
• 根據不同的劃分策略構建樹狀索引結構。
• 將得到二叉樹轉化更加緊湊的表示形式（無指針，內存連續）。

PBRT中第二步得到的樹中，非葉節點持有指向其子節點的指針，葉節點持有指向其所包含圖元數組第一個元素的指針和所包含圖元的個數。

整個構建的過程是一個遞歸（可以通過棧轉化為循環）的過程。每一次遞歸接受一個左閉右開的區間

，處理數組中第 個到第 個圖元。若區間中的圖元數小于一個給定的值（葉節點最大圖元數目），則遞歸終止并返回一個葉節點。否則我們就需要考慮將區間內的圖元按照一定的策略劃分為 和 兩部分（劃分的過程可以使用std::partition函數對原數組進行更新），并遞歸地對劃分好的 和 進行構造并返回子節點的指針。

構建過程中最重要的問題就是如何對圖元進行劃分。對于非葉節點，假設其只有兩個子節點，若其包含了

個圖元，則總共有 中劃分的可能（ 個圖元，每一個圖元可以被分到左邊或者右邊，則總共有 種情況，然后減去全部被分到一邊的情況即可得到）。這顯然太多了，因此一般我們都是沿著某一個坐標軸進行劃分，這樣一來所有的情況只有 （書上是這么寫的，不知道怎么算出來的。根據書中的插圖我感覺應該是：將 個圖元沿著坐標軸依次排開，并將圖元簡化為質心，則一共有 個間隙，則總共有 種劃分的可能）。劃分時要盡可能減少劃分后兩部分包圍盒重疊的體積，因為重疊的體積越大，Ray穿過重疊區域的可能性越大，遍歷兩個子樹的可能性就越高，計算消耗越多。

因為我們最終的目的是要減少劃分后左右子節點重疊的體積，因此一般在圖元跨度最大的坐標軸上進行劃分。這里，圖元的跨度可以用圖元的包圍盒來衡量也可以用圖元的質心來衡量。

兩種最簡單的劃分方法是：

• 取坐標軸跨度的中點 ，若節點的坐標小于 則將其劃分到左節點，否則將其劃分到右鍵點（中點劃分）。
• 最左邊的 個被劃分到左節點，最右邊的 個被劃分到左節點（等量劃分）。

當圖元分布不均勻的時候，上面兩種方法得到的劃分結果會變得很差。

左：中點劃分或等量劃分；右：比較理想的劃分

一種更為常用且效果更好的方法是基于表面積的啟發式評估劃分方法（Surface Area Heuristic，SAH），這種方法通過對求交代價和遍歷代價進行評估，給出了每一種劃分的代價（Cost），而我們的目的便是去尋找代價最小的劃分。

假設當前節點的包圍體中存在

個物體，設對每一個物體求交的代價為 ，如果不做劃分依次對其求交則總的代價為： 如果這些物體劃分為2組，這兩組物體分別處于它們的包圍盒A和B中。設光線擊中它們的概率分別為 和 ，需要注意包圍盒 和 之間存在重疊，且它們并不一定會填滿其父節點的包圍體，因此 和 的和不一定為1，且它們的和越大說明 和 的重疊程度越大。綜上所述，當前節點求交的代價可以寫為： 其中 表示遍歷樹狀結構的代價。一般來說，我們假設對所有圖元的求交代價是相同的，可設 ，又遍歷的代價小于求交的代價，可設 。設包圍盒A中圖元的個數為 ，B中圖元的個數為 ，則： 光線擊中包圍盒的概率可以根據包圍體的表面積來估計，即在父節點的包圍體C中，A和B的表面積越大它們被擊中的概率也就越大，設 ， 和 的表面積為 ， 和 ，則有：

SAH考慮到了圖元在空間中的分布也考慮到了子節點包圍體的重疊程度，在實際應用中擁有很好的效果。

在實現的時候，相比于計算可能劃分的代價然后尋找代價最小的劃分，一種更好的辦法是將節點

所包圍的空間沿著跨度最長的那個坐標軸的方向將空間均等的劃分為若干個桶（Buckets），劃分只會出現在桶與桶之間的位置上。如圖所示，若桶的個數為 則只會有 種劃分的可能。

圖中節點沿著坐標軸的方向被劃分為了6個桶

設圖元質心在劃分坐標軸上位置坐標的分量為

，則該圖元所處桶的索引號為：

遍歷

中所有的圖元，統計每一個桶中圖元的個數以及每一個桶的包圍盒。注意，桶與桶之間存在重疊。得到這些信息后，就能計算每一種劃分的代價：

需要注意的是，若當前所有圖元質心的位置都相同，則需要進行特殊處理，一般有兩種方法：

• 直接建立一個葉節點，該葉節點直接包含這些質心位置相同的圖元。
• 按照數量均等的分給兩個子節點。

既然這些圖元都靠在一起了，那么無論你怎么分都沒用，反正都要挨個求次交，所以第一種方法更好一些。

總結

以上是生活随笔為你收集整理的c++ 结构体遍历_PBRT-E4.3-层次包围体(BVH)（一）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。