基于優化八叉樹的場景視錐體裁剪算法

李穎穎，黃文培

（1.西南交通大學計算機與人工智能學院，四川 成都 611756；2.西南交通大學信息科學與技術學院，四川 成都 611756）

0 引 言

隨著數字孿生［1-2］、虛擬仿真［3］和增強現實［4］技術的迅速發展，瀏覽器端3D 模型可視化技術在建筑信息（Building Information Modeling，BIM）、智能制造、生物醫學成像等領域均得到了廣泛應用［5-6］。由于專業領域的模型通常結構復雜，頂點、法向量等幾何數據繁多且無序［7］，這無疑增加了計算機存儲消耗和CPU 處理壓力，以致于出現顯示卡頓、交互幀率過低、內存占用量過大等問題，從而整體上影響了三維模型的實時可視化。因此，采用一種有益于計算機存儲的空間數據結構管理模型構件［8］，并在此基礎上結合可見性裁剪算法，將有效提升大體量三維模型在瀏覽器端的可視化效果。

1 相關研究工作

常見的空間數據結構有層次包圍盒（BVH）、二叉樹（BSP）、八叉樹（Octree）［9］，應用模型場景不同，但各有優劣。本文所采用的八叉樹是一種多層級樹形結構，是四叉樹在三維場景的擴展［10］，適用組織大體量的模型數據，缺點是隨著模型數據與場景復雜度的增加，樹的層級逐漸增多，導致了節點查詢遍歷效率低、內存占用量大、適應性弱等問題。如何在提高空間壓縮效率同時具有較強的自適應性，成為了眾多學者的研究課題?，F如今研究方向主要分3 種：八叉樹存儲結構［11-12］、自適應性［13-14］與混合其他空間數據結構［15］。

鮑義東等人［16］采用改進編碼二進制的方式實現八叉樹存儲結構，與傳統八叉樹相比具有速度快、存儲量小的優勢；與線性八叉樹相比，對節點的分割、刪除和查找也很方便。并通過檢查三角形包圍體是否大于節點的1/3來確定是否細分和具有良好的自適應性。Dricot 等人［17］提出了一種模式決策模塊，基于失真最小化為每個8 位字節選擇最佳編碼模式，這種方式顯著提高了八叉樹的編碼效率，具有良好的壓縮性能。Koh等人［18］提出了一種截斷八叉樹的新型存儲結構，通過淺八叉樹表示深八叉樹提高壓縮率，提出了一種可變長度尋址方案，能自適應選擇八叉樹節點地址的長度，從而進一步壓縮。吳宇豪等人［19］基于線性八叉樹編碼進行了改進，采用Hilbert 碼標記節點，相比現有的Morton 碼轉換算法效率更高。周藤藤［20］采用八叉樹和層次包圍盒混合的空間劃分方式管理模型場景，能夠根據場景不同的特點選擇最優的劃分方式，從而加速了視錐體的剔除，達到很好的優化效果。

綜上所述，本文提出一種基于優化八叉樹的場景視錐體裁剪算法，在存儲結構與自適應性方面進行了優化。采用基于Morton 碼的分層存儲方式加速節點劃分與遍歷；依據視域與視點，對節點按需增量劃分同時設置視距標準作為劃分終止條件，使得八叉樹具有良好的自適應性。在優化八叉樹基礎上，采用雙層包圍體視錐體裁剪方式和基礎相交測試，加速視錐體裁剪。通過與傳統的八叉樹視錐體裁剪相比，本文的算法在空間壓縮率和渲染幀率上都有顯著的提高。

2 八叉樹數據結構

2.1 傳統八叉樹結構

八叉樹結構是將三維空間劃分為越來越小的體積，每個體積具有相同的時間和空間復雜度［21］，八叉樹的結構示意圖見圖1。主體積的邊界框對應樹的根節點，并包括所有的模型構件。將根節點按照一定的劃分規則通過循環遞歸的方法自頂向下均勻地分成2n×2n×2n節點（n為劃分的次數），直到節點所含構件數或達到目標深度后停止劃分。

圖1 八叉樹結構圖

2.2 存在的問題

目前傳統八叉樹存在以下一些問題：

1）在生成八叉樹結構和查詢節點的過程，需要遞歸執行查詢操作，花費大量的時間。

2）每個節點需存儲子節點的指針為0 或8 個，存儲空間占用較大。

3）劃分方式為剛性（即所含構件數或固定深度作為閾值），不具有靈活性，不能與視點等相關因素建立聯系。

4）采用靜態劃分的方式，不具有實時性，易造成在渲染時保持相當高的內存占用量。

3 優化八叉樹數據結構

針對傳統八叉樹存在的問題，本文在存儲結構和自適應2 個方面進行優化，構建流程如圖2 所示。優化過程如下：

圖2 優化八叉樹構建流程圖

1）存儲結構方面。逐層劃分時，采用Morton 碼的分層存儲方式，在每層節點生成時，先利用構件和當前節點的空間坐標，求出目標節點的Morton 碼；然后根據Morton 碼確定目標節點存儲的實際位置。

2）自適應方面。通過按需增量劃分和設置視距標準使得八叉樹在整體上具有自適應性。首先根據視域因素，按需對八叉樹節點進行劃分，控制八叉樹橫向的生長。然后根據視點因素，設置視距標準，作為節點劃分終止條件，控制八叉樹的縱向生長。從而在整體上實現自適應同時保證較低的空間消耗。

3.1 基于Morton碼分層存儲

與普通八叉樹相比，線性八叉樹是提高數據存儲壓縮率的有效方式，其存儲方式是將所有層級的葉節點混合在一起，然后按照Morton碼從小到大的順序依次存儲。本文在劃分過程中基于線性八叉樹Morton碼，在其存儲結構上采用了分層線性存儲的方式。

分層線性存儲的每一個層級都對應一維線性數組。在逐層劃分時，利用構件與當前節點（父節點）的空間位置信息，生成目標節點（子節點）的Morton碼，然后對目標節點按照M-Order（即節點Morton 碼對應的一維數組索引順序）存儲至相應層的一維數組中。目標節點的Morton 碼均采用6 位二進制表示，取值范圍0~26。分層線性存儲方式分為節點Morton碼的計算和利用Morton碼確定目標節點實際存儲位置2大步驟。

3.1.1 節點Morton的計算

節點Morton 碼是節點在對應實際存儲空間的索引，用一維的數值表示，其計算方式主要有2 種：利用查詢表計算與迭代交叉計算［22］。本文選擇后者，因其算法過程容易理解，并采用二進制移位運算的方式，可減少計算復雜度。計算過程如下：

1）輸入構件與父節點的空間位置，計算出目標節點所在正負區間inside；

其中：p為構件的BS 體的中心，r為半徑，min、max 為節點最大和最小頂點。

2）根據公式（2）計算目標節點分量的Morton 碼；設目標節點分量的Morton碼分別為Mx、My、Mz；

3）已知目標節點分量Morton 碼，使用公式（3）計算節點的Morton碼。

3.1.2 利用Morton碼確定目標節點實際存儲位置

一維線性數組的長度為8，可用3位二進制表示。每位可取0或1，表示每個軸向劃分的左右2個區間。

1）利用三層嵌套循環，對8個區間遍歷。

2）每層循環體中，分別使用公式（4）~公式（6）判斷，結果為false，跳出本層循環；x、y、z取值0或1。

3）在最內層循環中，通過公式（7）計算出節點在數組的實際存儲索引octant，octant 初始值為0，x、y、z取值0或1。

4）在索引位置生成節點對象。

3.1.3 分層線性存儲方式優勢

分層線性存儲方式具有以下優勢：

1）利用二進制移位操作，快速計算節點的Morton碼，減少計算量。

2）建立節點的Morton碼與存儲位置的對應關系，加速節點劃分與遍歷，提高空間壓縮效率。

3）不用存儲節點的Morton碼，節省了存儲空間。

3.2 按需增量劃分

實時渲染時，模型會以完全處于視域內或部分處于視域內2 種狀態存在。前者需渲染所有的模型構件，此種狀態下再創建多層級八叉樹將帶來無用的內存空間消耗；后者則只需要對與視域相交的節點增量劃分，對于在視域外和內的節點則不需生成?？紤]到以上情況，本文采用按需增量劃分的方式。該方式主要分為2個階段：

1）根節點生成。首先建立體積較小的根節點，然后判斷根節點是否包含每一個構件，如果都包含則輸出根節點；否則對舊的根節點依次進行上下邊界的擴充，生成新的根節點，遞歸調用判斷函數，直至包含該構件。新節點的寬度為舊節點的2 倍，并通過公式（8）得到新節點的位置信息。

2）實時渲染。當視錐體運動時，檢測出與之碰撞的節點，對這些節點動態地進行劃分，然后對每個子節點繼續檢測是否與視錐體碰撞，對于碰撞的子節點再次進行劃分，對于完全在視錐體內和外的節點會停止劃分。停止子結點劃分的3 種條件：①當節點滿足劃分終止條件時；②節點完全被視錐體包含時；③節點完全在視錐體外時。

此方式雖然在增量劃分時會產生一定的時間消耗，但也僅僅在面向相交節點時才會產生額外的計算。而且在大規模靜態場景中，可見構件的數據量遠小于場景中所有的構件數量，視點的移動范圍和速度也不會很大，因此不會造成與之相交的靜態八叉樹節點的頻繁變化。故采用這種方式，能夠在保證時間效率的前提下，減少無用的節點生成，從而控制八叉樹橫向的生長，具有很好的適應性。

3.3 設置劃分終止條件

采用自頂向下的八叉樹劃分方式，若不設置劃分終止條件，容易造成八叉樹縱向的不斷生長，從而導致棧溢出的問題。目前通過剛性的方式難以滿足復雜場景的需要。本文通過建立視距標準作為劃分終止條件，能使得模型場景滿足距離視點較近且密度較大的部分，使用較多的樹節點組織；距離較近且密度小的部分，使用較少的樹節點組織。

傳統的視距標準［23］，僅僅依賴視點與節點的距離對節點進行劃分，該方式過于片面。本文認為節點尺寸也是一個重要的因素，因為尺寸過大，在屏幕中也會占據較大的區域，如果不對當前節點進行劃分，會導致渲染中出現失真的現象，所以在對節點進行劃分時，應同時考慮視距和節點尺寸2 個因素。視距標準的示意圖如圖3所示。

圖3 視距標準圖

圖3 中L表示視點到節點中心的距離，S表示節點的尺寸，定義視距標準變量V，用以下公式判斷節點是否劃分：

當V＜1 時，對節點進行劃分，V≥1 時終止劃分；C為視距的控制變量，通過調整C的大小來改變視距對節點劃分的影響程度。經過實驗推導出，C與V的取值成反比，當C取值越大時，V越小，視點距離對節點劃分影響就越大，相反，視點距離對節點劃分影響越小。

關于視點距離L的計算，三維距離的計算方式常用有2 種，分別是歐幾里得公式、曼哈頓公式［24］。設視點坐標（x1，y1，z1），節點中心坐標（x2，y2，z2），2 種計算公式如下：

歐幾里得公式：

曼哈頓公式：

歐幾里得公式能精確反映2 點的距離，但涉及開方復雜運算；曼哈頓公式雖然求值結果會存在結果偏大的誤差，但是可以通過增大C來減小誤差，同時可以減少計算量?；诿看喂濣c劃分都要計算視點距離，故采用曼哈頓公式作為求2 點距離的表達公式，節省運算量。關于節點尺寸S的計算，八叉樹的節點是由AABB 包圍盒描述的，故取出包圍盒的最大頂點和最小頂點，并通過曼哈頓公式求2 點的距離，作為節點的尺寸S。實驗結果表明：本文設置的視距標準，創建的八叉樹具有合適的細分程度，可以保證不同距離的模型構件表現效果基本相同，使得八叉樹在縱向上與視點建立良好的適應性。

4 基于優化八叉樹的視錐體裁剪

4.1 視錐體裁剪原理

視錐體裁剪是對模型里的每一個構件判斷和視錐體的相交關系，如果構件在視錐體內或者相交，就將構件加入渲染列表，否則將其剔除。研究表明：隨著模型構件增加，每幀的視錐裁剪運行時間與構件的數量成線性關系，反而導致渲染幀數降低［25］。通過對場景中的模型建立空間數據結構，利用其空間相關性進行視錐體裁剪，能夠大幅度提高裁剪效率。

視錐體是由透視投影矩陣變換得到的結果，因此每個面的法線平面方程均可由透視投影矩陣推導出。在推導中可得出以下結論：平面方程的法向量指向視錐體內側，且若點到平面的距離為正，表示為與法向量同向，則判斷點在平面內側；若距離為負，則判斷點在平面外側［26］。通過此結論可以計算出包圍體與視錐體的碰撞結果。

使用包圍體對構件近似描述，可以解決復雜構件與視錐體碰撞檢測困難的問題。在本文中共定義了3 種包圍體（Bonuding Volume）：AABB 盒（AB）、OBB盒和BSphere 體（BS）。AB 盒用來描述樹節點，構建簡單，適用于粗略的碰撞檢測；OBB 包圍盒用來描述構件，構建復雜，但緊密性比AB 盒、BS 體表現都要好，適用于精確的碰撞檢測；BS 體構造簡單且碰撞檢測最為容易，但緊密性也是最差的，因此利用BS體對2種包圍盒進行包裹，可以加快碰撞檢測的速度。

本文裁剪算法在優化八叉樹基礎上，前期對八叉樹節點采用BS-AB 雙層包圍體方式逐層進行粗略篩選，后期對碰撞的潛在構件采用BS-OBB 雙層包圍體方式逐層進行精細篩選，最終得到渲染構件對象列表。

4.2 裁剪算法描述

1）粗略篩選。首先判斷節點BS體與視錐體的相交關系。測試結果為“包含”，則表示該節點以及子節點中的構件都是可見的，把節點及子節點所含的構件添加到渲染列表中，測試結束。測試結果為“不相交”，則表示該節點以及子節點內的構件都不可見，測試結束。測試結果為“相交”，則開始判斷節點AB 盒與視錐體的關系，包含，則將節點以及子節點所含構件添加至渲染列表，測試結束；不相交，測試結束；相交，則繼續遍歷子節點，對子節點同樣進行BS 體和AB盒的判斷，直至葉子節點。

2）精細篩選。取出葉子節點的所有構件，對構件的BS 體和OBB 盒逐層裁剪。先判斷構件BS 體與視錐體的關系，不相交時，測試結束；包含時，將構件放入渲染列表中，測試結束；相交時，則開始判斷構件OBB 盒，若OBB 盒與視錐體不相交，測試結束，相交或者包含時，把該構件放入渲染列表中。所有構件遍歷結束，則裁剪算法終止。整體裁剪算法流程如圖4 所示。

圖4 視錐體裁剪流程圖

4.3 雙層包圍體與視錐體的碰撞檢測

BS 體與視錐體的相交測試是直接根據BS 體中心到6 個平面的有向距離distance 與BS 體半徑radius判斷。若|distance|≤radius，則判斷相交；在相交不成立的情況下，若distance＞radius，那么BS 體在平面的內側，所有的平面都滿足時，則判斷包含；若distance＜-radius，那么BS 體在視錐體外側，任一平面滿足該條件時，則判斷為不相交，直接退出循環。

包圍盒與視錐體的精確相交測試，即包圍盒的8個頂點與視錐平面進行測試［27］。該方法實現過程簡單，但計算量非常大。本文采用Assarsson和Tomas在1999 年提出的視錐體剔除優化中的基礎相交測試方法［25］。該方法只需測試對角線與平面法線夾角最小的2 個頂點，分別記為頂點p和頂點n。測試流程為：找到一條穿過包圍盒中心且與平面法向量方向較為接近的包圍盒對角線向量V=，如果n頂點位于平面的外側，則整個包圍盒都在外面，停止測試，判斷結果為不相交；然后對p頂點進行測試，若p頂點在平面內側，判斷結果為包含，否則包圍盒和視錐體相交。p和n頂點的確定：設平面法向量為N，當N的第i個分量為正值，選擇pi=box.min［i］、ni=box.max［i］，保證了對角線向量Vi與平面法向量Ni相同符號；當平面法向量N第i個分量為負值，選擇pi=box.max［i］、ni=box.min［i］，同樣也保證了對角線向量Vi與平面法向量Ni相同符號。示意圖如圖5所示。

圖5 包圍盒與視錐體相交測試圖

5 實驗結果及分析

本文實驗的環境為64 位Windows 10 系統，CPU為Intel（R）Core（TM）i7-10510U CPU@1.80 GHz，內存為16 GB，顯卡為NVIDIA GeForce MX350，實驗的運行和調試平臺為Chrome 瀏覽器，開發軟件為vsCode，選擇Three.js 框架作為三維模型渲染平臺。本文所采用的列車轉向架三維模型來源于“面向產品全生命周期及閉環反饋的信息物理融合理論”國家重點研發項目，其模型格式為.glb，構件數量為9454個。

表1 為不同劃分方式在節點數和平均渲染時間上的比較，均為剛性劃分（同一目標深度）。從表1 數據中可以得出以下結論：

表1 按需劃分與靜態劃分對比

1）節點數的比較。視點位置相同的情況下，靜態劃分方式在運行過程中始終保持較高的節點數，但按需劃分方式則是隨著視角的變換，節點數穩定增加，且在同一個視角和多個視角的情況下節點數都是遠少于靜態劃分的。

2）平均渲染時間比較。雖然按需劃分方式所消耗時間多于靜態劃分，但差距不大，在可控范圍內。

根據以上結論，選擇按需劃分的方式可以較好地控制八叉樹橫向的生長，使其具有橫向的自適應性和較好的空間壓縮效率。

表2 為視距控制變量C來確定的實驗結果，劃分過程中，采用按需劃分的方式并以Morton碼的分層存儲方式管理子節點。表中構件剔除占比=（總構件數-渲染構件數）/總構件數，從表2 數據中可以得出以下結論：

表2 視距控制變量C的確定

1）當C取相同值時，隨著視點與節點的距離的不斷變小，八叉樹細分的程度越高，節點數越多，剔除的構件也逐漸變多。

2）當視點位置相同時，隨著C值不斷增大，剔除效果逐漸變好，節點數也是較穩定的增加，當C取40時，剔除效果和C取35 時幾乎相同，但節點數的增加幅度明顯變大。

根據以上結論，本文選擇C取35 計算視距標準，既保證剔除的良好性，又在縱向上具有自適應性。

表3 為傳統八叉樹與優化八叉樹在內存空間壓縮效率方面的比較，表中傳統八叉樹采用靜態劃分的方式和傳統的存儲結構，總內存占用量=（現在內存量-原內存量）/原內存量。通過表3數據可以看出：

表3 優化八叉樹與傳統八叉樹在內存空間壓縮效率對比

1）同一深度，優化八叉樹要比傳統八叉樹節點數少，且隨著深度的增加，優化八叉樹節點增加幅度要明顯小于傳統八叉樹。

2）在總內存占用量少，相對于傳統八叉樹，優化八叉樹減少了約38個百分點，具有較好的空間壓縮效率。

表4 為基于優化八叉樹的視錐體裁剪算法與傳統八叉樹裁剪算法在渲染幀率上面的比較。通過表4 結果可以看出：在傳統渲染的情況下最低幀數約為7幀，要比基于優化八叉樹的視錐體裁剪少5幀左右。原因是：初始加載時，整個模型處于場景內，需渲染所有的構件，剔除效果不明顯，這種情況下幀數都偏低，而本文算法通過按需增量劃分的方式，在初始時并未生成多層級的八叉樹結構，因此幀數要比傳統的略多。最多幀數這一欄，因視點距離模型較近時，可以剔除掉很多的構件，所以幀率可以達到60 幀（滿幀），傳統的未達到滿幀，是使用簡單的存儲結構，節點數較多引起的。平均渲染幀率是決定瀏覽是否卡頓的關鍵，傳統的僅僅只有17 幀，難以滿足流暢顯示與交互。在本文算法優化的情況下可以達到31 幀，已經可以滿足流暢的模型瀏覽。

表4 本文算法與傳統算法對比

6 結束語

本文針對于大體量模型在瀏覽器端渲染效果不佳的問題，提出了一種基于優化八叉樹的場景視錐體裁剪算法。針對傳統八叉樹存在的問題，在存儲結構和自適應性2 個方面進行了優化，達到了既具有高效的空間壓縮效率，又能根據視點位置和模型場景特點構建出自適應的八叉樹。在視錐體裁剪上，采用了雙層包圍體的方式同時對碰撞檢測進行了優化，既降低了裁剪的時間復雜度，又提高了裁剪的準確率。最后以高速列車實例模型作為應用場景，通過多次實驗證明了算法的可行性、合理性和有效性。