計算機圖形學中BVH的構建和動態(tài)修改

計算機圖形學中BVH的構建和動態(tài)修改摘要：光線追蹤中射線與物體的求交運算需要線性的時間復雜度，而可交互粒子系統(tǒng)中的碰撞檢測更是達到了平方級的時間復雜度，只是緩存友好是不夠的，因此它們都需要用空間結構來優(yōu)化，而一種很好的樹形結構就是BVH（Boundingvolumehierarchy）。BVH的核心思想就是用體積略大而幾何特征簡單的包圍盒來近似描述復雜的幾何對象，并且這種包圍盒是嵌套的，只需要對包圍盒進行進一步的相交測試，就可以越來越逼近實際對象，從而達到加速的目的。關鍵詞：BVH；加速結構；光線追蹤；碰撞檢測；射線檢測一、基本結構BVH是一個二叉樹，它每個節(jié)點中的基本元素是包圍盒，只需存儲兩個向量即下界和上界作為成員，即可表示一個包圍盒。合并兩個包圍盒只需對二者的下界取最小，上界取最大，即可得到一個新的包圍盒。對于每個需要添加進BVH的物體，我們需要用擊中點坐標和法線向量來標識它。執(zhí)行光線追蹤的最簡單方法是逐個檢查每個物體并求解，如果物體數(shù)量很少那么這樣是可行的，但如果物體形狀很復雜或物體數(shù)量很多，那么在檢測這些復雜的物體之前，先檢測射線是否與包圍盒相交是很值得的。包圍盒的檢測會比物體的檢測快很多，因為我們不需要知道擊中點坐標或法線向量，我們只需要知道光線是否與包圍盒重疊。我們可以嘗試將更多的物體分組到更大的包圍盒內，這樣就可以在很多情況下跳過整個子樹。我們可以很輕易獲得BVH中每個包圍盒的表面積，因為它就是這個包圍盒的上界減去下界所得向量的模長。一旦使用了不止一層的包圍盒，就必須要制作一整棵二叉樹，這就是一個BVH。不只可以用包圍盒表示樹中的每個節(jié)點，其他形狀也是可以的，例如包圍球或包圍橢球。這棵樹由內部節(jié)點和葉節(jié)點組成，葉節(jié)點中存儲了具體的碰撞物體，而內部節(jié)點中只存儲了包圍盒，內部節(jié)點只是為了加速查詢而存在，注意在實際應用中我們常常將需要檢測的靜態(tài)物體和動態(tài)物體區(qū)分開。BVH不僅可用在光線追蹤和射線檢測中，還常用于加速碰撞檢測，這就需要先對BVH進行構建，再對劃分好的BVH進行動態(tài)修改，于是接下來我們就來研究如何對BVH進行構建及動態(tài)修改。二、BVH的構建方式有很多種構建二叉樹的方式，而BVH有它獨特的構建方式。對于BVH來說，每層節(jié)點之間的相對順序是完全沒有任何影響的的。我們可以在任何節(jié)點處交換它的左右子樹，所得的BVH與原始BVH是完全等價的。我們想要使用一種表面積啟發(fā)式的方法來構建BVH，而這首先需要提出一種判斷節(jié)點是否足夠好的衡量標準，也就是權重。同一組葉節(jié)點可以構造出很多種不同的BVH，這些BVH中所有葉節(jié)點的表面積均相同，根節(jié)點的表面積也相同，只有內部節(jié)點的表面積不同，而這個不同就是評判構建出來的BVH是否足夠好的關鍵標準。這里我們基于的假設是，對于光線求交來說，包圍盒表面積越大，與它碰撞的概率就越大。從傳播消耗的角度看，這是完全正確的。除此之外，該節(jié)點下的子節(jié)點數(shù)量越多，遍歷該節(jié)點的傳播消耗也一定越大，因為遍歷到它的次數(shù)很可能就越多，計算次數(shù)也就越多。表面積影響的是子節(jié)點被遍歷到的概率，而每個節(jié)點下模型的三角形個數(shù)就是要求交的次數(shù)。但是在構建BVH前，我們并不知道某個節(jié)點的子節(jié)點數(shù)量，因為很有可能不會劃分到每個葉節(jié)點都只有一個物體這么細微的程度，所以這里我們實際使用的是當前節(jié)點所包含的物體數(shù)量而不是子節(jié)點數(shù)量，用它來分別計算傳播消耗和碰撞概率，這兩者分別用包含的物體數(shù)量和包圍盒表面積表示，而每個節(jié)點的消耗就表示為這兩者的乘積。一棵BVH的總權重是所有節(jié)點的權重之和，表示為對傳播消耗與碰撞概率的乘積求和。一種最直接的做法是，首先根據(jù)莫頓碼或快速選擇算法對三個坐標軸之一進行排序，然后遍歷BVH中的每個節(jié)點，計算將當前節(jié)點劃分為兩個子節(jié)點所產生的權重。當每個節(jié)點都有一個權重之后，找到使劃分后兩子節(jié)點的權重和最小的劃分方式，如果劃分之后的權重仍大于劃分之前的，那么就不繼續(xù)劃分了，最后遞歸這個過程直至劃分完成即可。注意這是一個貪婪算法，并不能保證全局最小。光線擊中物體的概率與物體的表面積成正比，使用表面積函數(shù)，我們可以計算任何BVH的總權重。到底是繼續(xù)劃分還是直接遍歷求交，需要分別計算劃分后再遍歷的效率和直接遍歷的效率，也可以選不同的劃分位置，按兩個子節(jié)點被選擇的概率計算效率并比較來找出最佳劃分點，因為當評估BVH的遍歷效率時，每個個節(jié)點下子節(jié)點的層數(shù)只是原因之一，還有個必須考量的因素是每個節(jié)點下左右子樹的包圍盒的重疊程度。在實際計算時需要找到光線與每個包圍盒的交點中最近的交點，而且在沒有額外的信息知道兩個子節(jié)點是否重疊的情況下，也需要分別計算與兩個子節(jié)點的交點的來找出最近交點。但是實際上，可以有一些優(yōu)化操作在里面，比如在構建BVH時，可以用二進制位來標記一個包圍盒是否與其他同級別包圍盒重疊，對于沒有重疊的包圍盒，第一個碰到的，必然是最近的。另外，很多時候是不需要找到最近交點的，只需要判斷是否有遮擋就可以了，比如陰影投射光線，這時連額外的信息都不需要了。三、BVH的動態(tài)修改動態(tài)修改包括對象移動、對象創(chuàng)建和對象銷毀，方法仍是表面積啟發(fā)式，所以仍需要一種計算插入節(jié)點的成本的方法，其中一種方法是新節(jié)點的表面積即直接成本加上所有祖先節(jié)點增加的表面積即繼承成本，這就是新添加到樹中的表面積，每個節(jié)點的成本是直接成本和繼承成本之和。樹中的每個葉節(jié)點都是新節(jié)點的潛在父節(jié)點。每個選擇都會為樹添加不同的表面積。我們想找到為樹增加最少表面積的潛在父節(jié)點，不幸的是，評估每個潛在父節(jié)點的成本是昂貴的，所以采用分支定界算法，通過遞歸的方法使全局搜索更快，并跳過不可能更好的子樹。我們還想確定探索該節(jié)點的子節(jié)點是否是有必要的，即是否應繼續(xù)探索該節(jié)點的子樹？該節(jié)點的子節(jié)點的下限是該節(jié)點的表面積加上繼承成本。如果該節(jié)點的成本優(yōu)于最佳成本，則更新最佳成本。如果子樹的下限成本低于最佳成本，那么值得探索這些子樹并將它們推入優(yōu)先隊列。否則可以從搜索中修剪以該節(jié)點為根的整個子樹，這極大地提高了性能。為了在選擇了潛在父節(jié)點后修改樹的所有細節(jié)，必須依次處理邊緣情況，處理新節(jié)點的創(chuàng)建和連接，之后還要調整新葉祖先的包圍盒，這叫做改裝。排好序的輸入會破壞BVH。想象一下，我們連續(xù)有幾個對象，它們按排好序的順序插入到樹中，這會導致BVH變成鏈表。在這種情況下，增量無法提供良好的樹。老實說，很難找到一個不會失敗的合理成本指標，所以需要樹旋轉，即重新排列樹以降低成本。樹旋轉一般用于二叉平衡樹，但這里它們還可用于限制體積層次結構，以減少BVH的表面積并減輕排序輸入帶來的問題，所以可使用樹旋轉來解決BVH的順序輸入問題。這是一個局部操作，可以在重新改裝祖先包圍盒時優(yōu)化樹。參考文獻：?J.Goldsmith(1987)-AutomaticCreationofObjectHierarchies?S.Omohundro(1989)-FiveBalltreeConstructionAlgorithms?A.Kensler(2008)-TreeRotationsfor