基于八叉樹的復雜產品模型實時繪制技術

趙 磊1, 2，趙 罡1, 2，談敦銘1, 2

?

基于八叉樹的復雜產品模型實時繪制技術

趙 磊，趙 罡，談敦銘

（1. 虛擬現實技術與系統國家重點實驗室，北京 100191；2. 北京航空航天大學機械工程及自動化學院，北京 100191）

給出基于OpenSceneGraph場景模型的信息提取方法，利用八叉樹對場景模型進行分割和視錐體剔除，有效提高了實時繪制的效率，尤其是對瀏覽場景細節時的繪制效率提高最為明顯。采用基于分頁技術的Pagelod方法，實現模型的動態調度，以減少I/O的負載，滿足在有限硬件條件下虛擬場景中復雜產品模型的實時繪制要求。

虛擬場景；實時繪制；復雜產品模型；八叉樹

隨著計算機技術的飛速發展，虛擬現實技術（Virtual Reality，簡稱VR），也稱為虛擬環境（Virtual Environment，簡稱VE），已經對現代社會產生重要影響，并在改變人類的生活和工作方式。目前虛擬現實技術已經成功地應用在醫學、軍事、航空、制造業、建筑、教育、娛樂、銷售等眾多領域。

實時繪制（Real Time Rendering）是指系統在滿足視覺無閃爍的限制內，完成對場景中各對象的位置和姿態的計算和場景、對象繪制；同時能夠對用戶的輸入立即做出響應，并同步更新畫面，實現用戶與系統的實時交互。

目前實時繪制技術主要在LOD技術(Levels of Detail)、可見性剔除、分布式并行計算三個方面展開研究。

LOD技術是根據距離等因素采用細節程度不同的模型進行繪制的技術。這些細節程度不同的模型可以提前生成，也可實時生成。應用中多采用提前生成的方式，且一次性將層次細節模型文件讀入內存。但當層次細節模型文件很大時將對計算機造成讀寫壓力，影響實時繪制的效果。

可見性剔除是將位于視錐體外或不在視野內的模型從內存中剔除的技術。傳統方法多通過計算場景中每一模型的包圍盒與視錐體的相對位置來判斷是否進行剔除。當場景中模型數量較大時，這種方式就會產生明顯的延時。

分布式并行計算是在一組互聯的計算機上同時實現虛擬現實技術，對計算機系統的I/O要求很高，這里不處理這種情況。

通過對復雜產品模型的分析，基于八叉樹對場景模型進行分割、構建層次細節模型和進行視錐體剔除。基于Pagelod實現對大數據模型的動態加載，解決傳統LOD文件需一次性讀入內存的問題。

1 開發平臺的介紹[7]

虛擬場景的渲染離不開3D API。目前通用的3D API有OpenGL和Direct3D。兩種API各有優點，相對于Direct3D，OpenGL是一種開放性的標準，具有良好的跨平臺性能。但OpenGL仍具有使用比較繁瑣、渲染效率較低、開發周期較長等缺點。為了解決OpenGL的這些缺點，出現了很多封裝OpenGL的高級3D API 如Open-SceneGraph（簡稱OSG），OpenGVS等，這其中又以OSG的性能最突出，渲染效率最高。

OSG圖形系統是一個基于工業標準OpenGL，采用C++語言開發的軟件接口。它讓開發人員能夠更快速、便捷地創建高性能、跨平臺的交互式圖形程序。

采用Visual Studio 2005 和OSG開發。

2 模型相關信息提取

虛擬場景中的模型多由外部軟件建模完成，并保存或轉換成能被虛擬場景支持的中間格式如.3ds，.obj等。OSG可以讀取這些中間格式文件，但為了實現對模型的分割，必須提取場景中每一模型的基本信息（如點、線、三角形等）。

2.1 OSG的渲染場景圖形組織方式

OSG場景圖形采用一種自頂向下的，分層的樹狀結構來組織空間數據集，來提升渲染效率。每個OSG程序只有一個根節點(Root)，該根節點可以有多個子節點，子節點可以是葉節點(Geode)或組節點(Group)，如圖1所示。葉節點保存了繪制場景所需要的幾何信息(Geometry)和狀態信息(State)，不能再有子節點。葉節點又由多個Geometry和State組成，每個Geometry都有一個State與其對應，這樣的一個組合用Drawable來表示。幾何信息集中了渲染本圖形單元所需要的頂點、頂點索引、法線、三角形等信息，這些信息又是以數組的方式保存的。而狀態則包含了渲染本圖形單元所需的材質等信息。組節點(Group)可以有任意個子節點，而這些子節點既可以是葉節點又可以是組節點，這就為管理節點提供了可能。OSG中常用的節點類型還有：MaxtrixTransform(MT)節點、PositionAttitudeTransform(PAT)節點等。

圖1 抽象的場景圖

2.2 OSG中模型信息提取方式

實際場景的組織方式很復雜，如何準確獲取其中每一葉節點的相關信息將會很困難。經過2.1節的總結可以看出，遍歷場景根節點的每一子節點，若此子節點是葉節點則提取模型信息，否則繼續遍歷該子節點的所有子節點，當新的子節點為葉節點時提取信息，直到遍歷完所有葉節點。根據這一思想，提出如下的模型信息提取方法：

Step 1 初始化

判斷根節點是否有子節點，若無子節點退出，否則提取根節點中子節點的數量。

Step 2 提取子節點信息

判斷節點類型，若為MT節點則要提取矩陣信息。若為PAT節點則要提取位置、朝向、姿態、比例等信息。MT節點和PAT節點都要提取參考框架(ReferenceFrame)類型。所有節點都要提取節點掩碼(NodeMask)等。

Step 3 提取葉節點信息

分析子節點中的每個葉節點，并提取葉節點中的每個Drawable的幾何和狀態信息。

Step 4 循環與退出

若根節點中還有未被提取信息的子節點則執行Step 2，反之退出。

通過對場景模型信息提取，就將場景中每一模型轉保存為一組基本信息，處理這些基本信息可以實現對場景進行精確分割、調整等操作。

3 模型分割

目前虛擬場景中的數據多采用樹狀結構的方法來表示。虛擬場景的樹狀結構表示減少了可見性計算、碰撞檢測等，可以提高圖形的實時繪制能力。目前通用的場景數據表示方法有：四叉樹、八叉樹、BSP樹等。

四叉樹是一種二維表示格式，是對二維平面在兩個方向上進行連續分割以形成象限的方式得到，如圖2(a)所示。由于該方法是一種二維表示方式，實際中多用于大地形數據的分割。

八叉樹是可以看作是對四叉樹在三維上的推廣，如圖2(b)所示。場景的八叉樹層次結構在預處理階段生成，在實時繪制階段根據視點或距離原則對樹結構進行自適應修改。

二叉樹（Binary Space Portioning Tree，簡稱BSP），其思想是依據空間中的平面，將整個空間分割成兩個半空間，根據這種思想實現場景分割，如圖2(c)所示。相對于前兩種方法，BSP樹簡單但是會產生更多的節點。

本文需要對復雜產品模型進行分割，從而生成層次細節模型。采用基于八叉樹對場景模型進行分割，該方法停止遞歸的條件為達到了設定的分割層數或已無模型在當前節點內。下面將介紹創建的八叉樹節點和模型分割算法。

(a) 四叉樹

(b) 八叉樹

(c) BSP樹

3.1 八叉樹節點

每個八叉樹節點不僅要保存本節點的信息，通過該八叉樹節點還應能夠找到父節點(如果存在)和子節點(如果存在)。下面直接用C++偽代碼描述八叉樹節點所含信息。

class OctreeNode

{ 節點名稱； 節點中心；

包圍盒的長寬高； 節點所含的模型；

是否是根節點； 是否是最后一級節點；

八叉樹的級別； 在父節點中位置；

八叉樹節點所含模型的數量；

八叉樹節點包圍盒的八個頂點；

八叉樹節點的八個子節點；

八叉樹節點的父節點；

……

}；

3.2 模型分割

采用初始模型的包圍盒作為八叉樹根節點。對場景進行基于八叉樹的分割，要通過多次遞歸才能實現，而其中一次的分割算法如下：

Step 1 初始化

待分割的模型(由一個或多個零件組成)，待計算的八叉樹節點。

Step 2 計算零件包絡體信息

提取待分割模型中的一個零件并計算其包圍盒、包圍球半徑。

Step 3 分割零件

計算Step 2求得的包圍盒的8個頂點與八叉樹節點的位置關系。若8個頂點都在八叉樹節點中，則將本零件加入到八叉樹節點模型中；若待分割模型仍有零件未被處理，轉Step 2；若待分割模型中不存在未被處理的零件則退出。若8個頂點不全在八叉樹節點中，依據2.2節中的方式提取零件信息。

Step 4 分割和重構三角形

對提取到的每個三角形，先計算其最小外接圓(半徑和圓心)，計算圓心和八叉樹節點中心的距離，依據，，之間的關系分別處理：

（1）若<(+)則這個三角形可能和八叉樹節點相交，計算三角形的三個頂點和八叉樹節點的包圍盒的關系，若三個頂點都在八叉樹中則將本三角形添加到相應的數組中，否則按一個頂點在八叉樹節點中、兩個頂點在八叉樹節點、三個頂點都不在八叉樹節點中，這三種情況計算三角形和八叉樹節點的交點，利用所求交點和原來在八叉樹節點中的頂點創建新的三角形（注意：三角形的法線一定要和原三角形的法線同向），將新三角形添加到相應的數組中；

（2）若≥(+)則三角形和八叉樹節點不相交。

Step 5 創建新葉節點

依據Step 3的結果新建Drawable，循環執行直到本節點中的Drawable都被處理。依據這些新建的Drawable創建新節點，并將這些新節點作為一個整體添加到八叉樹節點中。

Step 6 循環處理與退出

若待分割模型中仍有未被處理的子節點，則執行Step 2，否則退出。

圖3為模型分割方法在飛機機尾模型上的應用，圖3(a)為原始飛機機尾模型，圖3(b)為經過二級分割后的模型，其中的線框為分割后模型的每個八叉樹子節點的包圍盒，從圖中可以看出被分割后的機尾與原始模型相比不僅保留了完整性而且具有很好的外觀。

完成基于八叉樹的模型分割后，就可以將分割后的最后一級節點已.ive或.osg格式保存到硬盤，形成一級層次細節模型文件。對同一模型的不同精度等級的模型分別進行分割就可以形成多級層次細節模型文件，為實時繪制做預處理。

(a) 原始模型

(b) 二級分割后的模型

圖3 飛機機尾模型進行二級分割

4 動態加載和快速視錐體剔除方法

前文分析了傳統LOD的缺點，本節將基于Pagelod實現以視點到模型中心點的距離為原則的動態加載。

為加快視錐體剔除效率，采用八叉樹方式來構建場景，將視錐體與八叉樹節點進行比較，來實現視錐體剔除。

4.1 動態加載模型

Pagelod就是采用分頁數據庫技術，以距離為原則動態加載相應的層次細節模型文件，由單獨線程實現加載，因此效率遠高于傳統的LOD技術。

初始化時，只需給出保存層次細節模型文件的路徑和名稱，并設定各LOD節點在哪個距離段顯示即可。渲染場景時，系統將自動選取需渲染的節點。這種方法對于簡單的模型，視覺上會產生一定的跳躍，但是對于復雜的場景并采用比較連續的簡化模型將減少跳躍感。

4.2 基于八叉樹的視錐體剔除

本節將利用第3節的分割結果實現視錐體剔除。

計算機繪制場景的步驟為：視圖變換，模型變換，投影變換和視口變換。在實際應用中，尤其對于從文件讀取的模型不用進行模型變換，只要獲得視圖變換、投影變換和視口變換的矩陣，就可以獲得模型繪制對模型要進行的變換。

視錐體是一個平截頭體，其可以通過一個單位正方體的各面與一個變換矩陣()相乘獲得。這個變換矩陣，可以通過獲取當前場景的視圖變換矩陣()和投影變換矩陣()，并將它們相乘獲得，即：=*。例如：初始化單位正方體（如圖4(a)）的6個面分別為+++=0。以每個平面的參數，，，構造向量=（，，，），=*，設新=（′，′，′，′），則′，′，′，就為新平面方程的系數，如此則得到當前視錐體的六個面的平面方程，如圖4(b)所示。

(a) 初始的單位視錐體 (b) 變換后得到視錐體

采用如下的方法確定一個八叉樹節點是否位于視錐體外部：

判斷八叉樹根節點的八個頂點和八叉樹節點中心是否在視錐體外，若都在視錐體外部，則將根節點及其下所有子節點的位于視錐體外的標志量設為true，并將根節點下所有模型節點的可見屬性設為false；否則遞歸判斷八叉樹的八個子節點(節點中若沒有模型則不用判斷)是否在視錐體外。

位于視錐體外的節點再次進入視錐體內時：

首先判斷八叉樹節點的八個頂點是否位于是視錐體內，若都位于視錐體內部，且當前八叉樹節點的位于視錐體外的標志量為true，則將八叉樹節點和其子八叉樹節點的位于視錐體外的標志量設為false，并將本八叉樹節點下的所有模型節點的可見屬性設為true，并將這些模型節點加載到場景繪制中。

這種剔除方式對實時繪制速度有明顯的提高，尤其在瀏覽場景細節時提高的最為明顯。

5 實驗結果與分析

將上文的方法在PC機（奔騰4 CPU 3.00G,內存1.00G）上實現。原始模型如圖5(a)所示，由348萬個頂點、418萬個三角形組成。對該模型進行多級分割實驗，結果如表1所示。從表1中可以看出，二級分割和三級分割后增加的頂點數量和幀頻率的降低情況相近，而三級分割和四級分割則產生了太多的頂點同時幀頻率也產生了明顯降低。對模型進行二級分割后的結果如圖5(b)所示。

表1 模型多級分割數據

對原始模型簡化（每次減少10 %），形成了100%到10%的11級LOD。表2中的前三組數據給出了100%、50%、10%三組模型經實時繪制方法處理后的幀頻率變化情況。由于分割造成模型的頂點和三角形增多，所以幀頻率出現了一定的衰減，但衰減的量不多。表2中后兩組數據，分別為當場景中顯示如圖5(c)、圖5(d)的細節，采用實時繪制方法前后的幀頻率。從細節1的數據可以看出，雖然顯示相近的細節部分但采用實時繪制技術后場景中實際繪制的三角形數量卻減少了很多，幀頻率也出現了明顯的提高。細節2，相對于模型整體只顯示了很小一部分信息，大部分數據被剔除出場景，場景中繪制的三角形的數量非常少，極大地提高了幀頻率。

表 2 實時繪制五組數據

由以上實驗和分析可知，對模型采用合適的分割級數，可以明顯提高實時繪制的效率。

6 結束語

給出了模型信息提取的有效方法，基于八叉樹實現了對OSG場景中模型的分割算法和視錐體剔除方法，提高了模型繪制的速度，在顯示模型細節時繪制速度提高的更明顯。采用基于分頁數據庫的Pagelod實現了模型的動態加載。但由于八叉樹節點的構造是均勻的，沒有考慮模型在空間上分布的不均衡，所以當瀏覽模型細節時若細節所在處模型集中，則場景中繪制的頂點會很多，幀頻率只會產生一定的提高；當場景中顯示的細節不集中，則場景中繪制的頂點數會非常少，幀頻率能夠產生極大的提高。

(a) 原始模型???? (b) 分割后場景中的模型

(c) 細節1 ?????(d) 細節2

圖5 整體模型與細節顯示

[1] Stytz M. Distributed virtual environments [J]. IEEE Computer Graphics and Application, 1996, 16(3): 19-33.

[2] Burdea G C, Coiffet P. 虛擬現實技術[M]. 魏迎梅, 等譯. 北京: 機械工業出版社, 2005. 231-270.

[3] 冀俊峰. 細節模型實時繪制加速技術研究[D]. 北京:中國科學院研究生院, 2005.

[4] 陳雷霆. 三維復雜場景實時繪制技術[D]. 成都: 電子科技大學, 2007.

[5] DeHaemer Jr M, Zyda M J. Simplification of object rendered by polygonal approximations [J]. Computer & Graphics, 1991, 15(2): 175-184.

[6] Airey J. Towads image realism with interactive update rates in complex virtual building environm ents [J]. Computer Graphics, 1990, 24(1): 41-51.

[7] OpenSceneGraph 說明手冊[EB/OL]. http://www. open-scenegraph.org/projects/osg/wiki.

Real-time Rending for Complex Product Model Based on Octree

ZHAO Lei, ZHAO Gang, TAN Dun-ming

( 1. State Key Laboratory of Virtual Reality Technology and Systems, Beijing 100191, China; 2. School of Mechanical Engineering and Automation, Beijing University of Aeronautics and Astronautics, Beijing 100191, China )

In order to improve the efficiency of real-time rendering, a method to extract the model information of OpenSceneGraph using scene model dividing up and view frustum culling based on Octree is proposed. This method has a better performance when visualizing the detail scene of virtual environment. Pagelod, which is based on DatabasePager, is also applied to implement the dynamic data translation, reduce the I/O overload greatly and satisfy real-time requirement for complex product model in virtual environment under limited hardware resources.

virtual environment; real-time rendering; complex product model; octree

TP 391

A

1003-0158(2011)03-0069-06

2009-12-30

虛擬現實技術與系統國家重點實驗室探索性自選課題資助項目（200806123）

趙 磊（1986-），男，江蘇宿遷人，碩士研究生，主要研究方向為CAD/CAM。