高度場八叉樹的體特征表達算法

高藝，羅健欣，裘杭萍，唐斌，吳波

1.中國人民解放軍陸軍工程大學，南京210007

2.中國人民解放軍61175部隊

高度場八叉樹的體特征表達算法

高藝1，2，羅健欣1，裘杭萍1，唐斌1，吳波1

1.中國人民解放軍陸軍工程大學，南京210007

2.中國人民解放軍61175部隊

1 引言

場景表達是可視化技術的一個重要分支，也是計算機圖形學研究的熱點。體特征表達是其中必不可少的一項內容，它直接體現(xiàn)了場景的細節(jié)及真實感，對用戶理解環(huán)境、認知環(huán)境有著至關重要的作用。

當前，體特征表達主要采用網(wǎng)格模型或體素模型。

網(wǎng)格模型是采用隱式表面近似來表達三維物體的幾何信息。網(wǎng)格數(shù)量越多，越接近于原始曲面，但繪制耗費的時間也隨之增加。這使得網(wǎng)格模型僅適用于小規(guī)模對象的建模。當前，研究的主要問題集中在網(wǎng)格簡化[1-2]，對模型中遠離觀察者或相對較小的區(qū)域進行簡化，減少多邊形的數(shù)量，降低渲染開銷。常見的簡化機制包括頂點聚類[3]、增量式簡化、采樣[4]和自適應細分[5]等四種機制。對拓撲簡單、平滑的表面具有較好的效果，但對復雜的表面，要將多個表面用一個表面來表示常常涉及復雜的計算。

體素模型[6]在計算機處理能力有限的早期，在醫(yī)學成像如斷層掃描CT，核磁共振成像MRI等方面提供了極大的幫助。隨著圖形硬件的快速發(fā)展，體素模型再一次煥發(fā)活力。目前，研究的主要內容是如何組織體素數(shù)據(jù)，盡可能地跳過空體素，節(jié)省存儲空間，提高空間檢索的效率。

Laine與Karras[7]提出了有效的稀疏體素八叉樹（Efficient Sparse Voxel Octree，ESVO），該方法為每一個柵格單元都提供一個過濾的輪廓近似，如果該輪廓可以很好地近似原始幾何，則八叉樹不需要進一步細分到更深的層次。這種表達方法對具有大量平坦表面的場景有很好的壓縮性能，用近似輪廓在高分辨率下取代體素，能實現(xiàn)有效的存儲壓縮。Crassin等[8]注意到八叉樹中具有自相似特性的特性可以合并，K?mpe[9]利用這一思想通過將稀疏八叉樹轉化為有向圖（Directed Acyclic Graph，DAG）的方式實現(xiàn)了使用約1 GB內存對128K3解析率場景的建模。Villanueva[10]在此基礎上提出了一種通過相似變換將八叉樹的子節(jié)點合并，通過合并子樹來實現(xiàn)無損壓縮。

盡管如此，與高度場表達相比，網(wǎng)格表達和體素表達的存儲量仍遠高于高度場表達，且這兩種模型的渲染都不易于移植到GPU中。

網(wǎng)格模型的渲染效率會受到三角形面片數(shù)量的影響，很容易達到GPU渲染管線的性能極限，還可能因面片太小而導致重采樣的問題；體素模型因其三維的數(shù)據(jù)結構并不適合直接在GPU中進行快速地并行光線投射。

相反，高度場模型具有存儲量較小，易于調度更新的優(yōu)點，而且高度場數(shù)據(jù)可通過二維紋理的方式載入顯存，在GPU中能獲得極高的光線投射效率，性能優(yōu)勢明顯[11-13]。但是，高度場不具備體特征表達的能力，在表達場景時通常采用法線貼圖、視差貼圖等技術對對象表面實施偏移操作，得到具有凹凸感的表面。這僅僅是一種增強視覺效果的2.5維表達，不是真三維體特征表達。目前的相關研究，高度場模型若要實現(xiàn)對真三維體特征表達，需輔以網(wǎng)格模型或體素模型才能實現(xiàn)[14-16]。在同一場景中使用不同類型的數(shù)據(jù)模型會增加系統(tǒng)的復雜度，降低渲染效率，在層次細節(jié)（LoD）更新、視點運動處理等方面都難以同步，對系統(tǒng)的圖像質量有很大影響，影響用戶體驗。

基于上述討論，本文提出了一種高度場八叉樹的體特征表達算法。該算法既保留了傳統(tǒng)高度場的優(yōu)勢，又解決了其體特征表達能力不足的問題。該算法的提出使得在同一個場景中可以使用統(tǒng)一的表達方式建模，為場景的體特征表達提供了一種新的可行途徑。

2 基本原理

給出高度場八叉樹的形式化描述如下：

i表示當前八叉樹子節(jié)點深度，L表示八叉樹最大深度。

對圖1（a）中的任意模型，傳統(tǒng)的高度場z=h(x,y)是無法建模z方向上關于(x,y)的多值函數(shù)（圖1（b））問題；圖1（c）是體素八叉樹模型示例，基于體素的場景則是由許多三維體素表示的空間。

高度場八叉樹采用八叉樹對三維模型進行樹狀細分，在八叉樹的子節(jié)點內從三個坐標軸方向上判斷是否存在高度場的單值函數(shù)，若在其中一個方向上存在單值函數(shù)即存在單一高度場，則在子節(jié)點中進行均勻離散采樣，得到分布規(guī)則的高度場八叉樹模型。圖1（d）是一個高度場八叉樹模型示例，八叉樹不同層的高度場以不同的顏色進行標記區(qū)分，每層高度場的覆蓋范圍包含了從基平面到該層次表面所有的空間，各層疊加在一起構成了高度場八叉樹結構。

圖1 （d）高度場八叉樹建模示意圖

與所有的節(jié)點都是基于八叉樹細分的體素模型相比，八叉樹高度場模型只需要少量的子節(jié)點就可以表達一個網(wǎng)格內的連續(xù)空間。

2.1 高度場八叉樹約束體系

八叉樹是組織三維模型的一種重要數(shù)據(jù)結構。樹的根節(jié)點包含整個模型的數(shù)據(jù)及八個指針，每個指針指向一個子節(jié)點，每個節(jié)點關聯(lián)一個與軸對齊的包圍盒。傳統(tǒng)八叉樹子節(jié)點遞歸等分原則是八叉樹結構達到最大深度或子節(jié)點中三角面片數(shù)小于設定的閾值，但本文的高度場八叉樹約束體系是：

（1）八叉樹節(jié)點的最大深度。

（2）子節(jié)點中所有三角面片可用高度場表示。

2.2 節(jié)點編碼及類型

通常八叉樹采用八進制Morton編碼對節(jié)點進行編號，用0～7表示8個子節(jié)點的編號，在逐層構樹中，節(jié)點編碼的位數(shù)不斷增加。

八叉樹節(jié)點分為4個類型：內部節(jié)點、高度場節(jié)點、邊界節(jié)點和空節(jié)點。內部節(jié)點為可剖分節(jié)點，有8個子節(jié)點；高度場節(jié)點為可剖分節(jié)點即葉節(jié)點，其所代表的空間滿足約束體系（1）和（2），僅存儲高度場數(shù)據(jù)及相應的參考平面信息；邊界節(jié)點，其所代表的空間滿足約束體系（1）但不滿足約束體系（2）；空節(jié)點，其所代表的空間不包含三角面片。

2.3 算法流程

算法包含三個主要的階段：一是三角面片預處理，二是判斷是否存在單一高度場，三是高度場柵格化。算法流程如圖2所示。

圖2 算法流程圖

3 空間高度場化

將三角面片表示的網(wǎng)格模型轉換為二維的規(guī)則高度場并存儲在3D紋理中的方法，即網(wǎng)格模型空間高度場化。提出了一個簡單的高度場化方法，如圖3所示。首先，對每一個三角面片進行空間幾何求交，判斷在三個坐標方向的相交性，然后，根據(jù)相交性確定不相交的坐標方向即為坐標軸主導軸，主導軸所對應的平面即為主導軸平面，最后柵格化后生成高度場數(shù)據(jù)及其他屬性數(shù)據(jù)。

圖3 高度場化管線流程

3.1 三角面片預處理

三角面片作為模型的基本圖形單元，隨著八叉樹不斷切分，與八叉樹節(jié)點的一個或多個邊界盒相交并衍生出新的三角面片。將其抽象化，即三角形邊與邊界盒平面的相交及交點計算。

如圖4所示，三角面片（a）、（b）、（c）、（d）在父節(jié)點被剖分后，（b）、（c）、（d）與相應的子節(jié)點包圍盒的不同平面相交并產生交點。

圖4 八叉樹父節(jié)點包含多個三角面片

將邊界盒看作剖分區(qū)域，令待剖分的三角形網(wǎng)格模型為D，其頂點集和三角面片集為SV和ST，剖分后形成的三角形在剖分區(qū)域內為D+，在剖分區(qū)域外為D-，相應的頂點集和三角面片集分別記為VD+、TD+和VD-、TD-。令三角面片三個頂點(v1,v2,v3)所在剖分區(qū)域的Morton編碼為m(vi)，Ti為該三角面片的面片集。

按如下方式對三角面片進行處理：

（1）三個m(vi)值相等，三角面片的三個頂點都在剖分區(qū)域內。如圖5（a）（b）（c）所示，此種情況三角形沒有被分割，因此在網(wǎng)格模型數(shù)據(jù)中保留，則；VD+=VD+?Vi，TD-=TD-?Ti。

（2）三個m(vi)值兩兩相等，三角面片兩個頂點位于剖分區(qū)域內，一個節(jié)點在剖分區(qū)域外，此時參與求交運算的平面只有一個，需要分兩種情況分別討論。

如圖5（d）所示，三角形一個頂點在相交平面上，其對邊被剖切，此時原三角形被分割成兩個三角形；如圖5（e）所示，原三角形被剖分成一個四邊形和一個三角形，四邊形將根據(jù)對角線的長度，取較大的對角線為新三角形的邊，剖分為兩個新的三角形。原三角形在網(wǎng)格模型數(shù)據(jù)中刪除，新增的三角形面片及其頂點信息添加到VD+、TD+和VD-、TD-中繼續(xù)參與到下一層八叉樹剖分。

（3）三個m(vi)值均不等，三角面片一個頂點位于剖分區(qū)域內，另兩個頂點分別位于剖分區(qū)域外兩個不同的節(jié)點。如圖5（f）所示，相對于剖分區(qū)域而言，參與求交運算的平面有兩個，此時原三角形被分割為多個三角形，與上相同，新增的三角形面片及其頂點信息添加到VD+、TD+和VD-、TD-中繼續(xù)參與到下一層八叉樹剖分。

圖5 三角面片的三個頂點與邊界盒平面的相交關系

算法直接在三角網(wǎng)格模型的三角面片上實現(xiàn)剖分，經(jīng)過預處理后，模型依然保持網(wǎng)格拓撲信息的有效性，同時也保證了網(wǎng)格數(shù)據(jù)的完整性。

3.2 空間幾何求交

空間幾何求交的目的是判斷能否轉換成空間高度場的依據(jù)。若存在單一高度場，則該子節(jié)點內包含的所有三角面片將被高度場化；若不存在單一高度場，則當前子節(jié)點內所有三角面片仍將繼續(xù)參與剖分，直到能被高度場化為止。對空間幾何求交這一問題的求解通常采用降維計算，將幾何圖元轉換到相應的局部坐標系下，建立空間幾何與平面圖形間的映射關系，從而將三維的空間問題降為二維的平面問題，這是將復雜問題簡單化的一種有效方式?？臻g幾何的求交算法可簡單表述如下：

步驟1根據(jù)參與運算幾何圖元的性質，構造局部坐標系。以XZ平面為例，平面方程為ax+by+cz+d=0。O是平面中心點，E是體邊界盒的角點，EO單位向量為n1(a1,b1,c1),平面法向量n2,第三個向量n3=n1×n2。三個互相垂直的單位向量n1，n2，n3構成局部坐標投影系。如圖6所示。

圖6 空間幾何相交問題的降維過程

步驟2應用2D/3D對應理論建立空間幾何圖元降維前后的計算關系，形成投影面上的計算方案。

設頂點坐標為(x,y,z)的空間三角形，變換到局部坐標下的坐標為(x′,y′,z′)，其滿足(x'y'z'1)=(xyz1)PTT，其中P是投影矩陣，T是變換矩陣，如下式所示：

3.3 主導軸選取

定義三個坐標方向索引值，0為XY坐標方向，1為ZY坐標方向，2為XZ坐標方向，依次遍歷節(jié)點中的所有幾何圖元，向三個方向的任一平面做投影降維。經(jīng)過投影降維后的幾何圖元（三角面片）在二維平面上分別進行相交關系的判斷，如果投影三角面片互不相交，則該投影方向即為主導軸，該軸對應的平面即為參考平面。對于二維平面的判交已有成熟的研究[17]，本文不再贅述。

3.4 柵格化及數(shù)據(jù)生成

每一個三角片和其所在的參考平面將一起輸入到柵格化管線中。在柵格化的過程中，每一個三角面片都會生成一系列的2D片元，每一個片元都與主導軸相關聯(lián)，計算插值后的三角形頂點到主導軸平面的距離，這樣的2D片元即為高度場數(shù)據(jù)片元。

高度場數(shù)據(jù)通常包含高度值數(shù)據(jù)，還包含一些屬性數(shù)據(jù)如：顏色、法線以及在實際應用中所需的其他有用信息如材質等。這些值或許是從頂點屬性像素中插值得到，或許是從模型的2D表面紋理得到，最后會被寫入到3D紋理中。

整個空間高度場化的過程只有空間幾何求交部分在CPU中實現(xiàn)，其余過程均在GPU中實現(xiàn)，盡管CPU和GPU之間的通信會造成一定的時間耗費，但比起在CPU中已經(jīng)極大地提升了執(zhí)行效率。

4 高度場八叉樹光線投射

目前，高度場渲染從技術的角度來分，可以分為兩種：一種是將高度場轉換為三角形網(wǎng)格，用硬件渲染三角網(wǎng)格即基于高度場的光柵化方法。用GPU進行渲染時，需要將三角形面片發(fā)送至GPU的顯存中，而CPU與GPU之間進行數(shù)據(jù)交換的代價比較高，大量的數(shù)據(jù)發(fā)送必將導致很高的渲染耗時，降低系統(tǒng)性能。一種是使用光線投射直接渲染高度場，其優(yōu)點一是表達方式更簡潔，有較低的內存要求；二是對于大規(guī)模高度場數(shù)據(jù)集來說，光線追蹤是一個圖像的順序算法，本質上忽略了高度場的遮擋區(qū)域；三是高度場包含多個對象的表示，包括幾何、體積、全局光照效果如反射、折射、軟陰影等。

早期的高度場光線投射算法都在CPU中執(zhí)行，由于CPU的串行工作方式，算法只能逐光線渲染，渲染效率很低。隨著圖形硬件突飛猛進的發(fā)展，顯卡的處理能力不再是性能提升的瓶頸，基于GPU光線高度場光線投射算法再一次受到了重視?，F(xiàn)有的基于GPU高度場光線投射算法都是傳統(tǒng)的單層高度場，因此是在z-xoy坐標系中，以地面（xoy）作為參考平面，模型被看做各空間位置相對于z平面的距離值集合，在光線迭代時，使用如下公式進行相交測試：

式中，Hen為光線進入單元邊界處坐標，Hex為光線離開單元邊界處坐標，Height為光線進入的單元高度。如圖7所示[18]。

圖7 傳統(tǒng)的高度場光線投射光線與模型相交關系

圖8 高度場八叉樹光線投射光線與模型相交關系

在本文的高度場八叉樹中，高度場在空間中不再只是z=f(x,y)函數(shù)，還可能是y=f(x,z)或x=f(y,z)的函數(shù)，坐標系不同，相交規(guī)則也不同，因此重新定義相交規(guī)則如下式：

式中，Den=dist(Hen,plane)為光線進入單元邊界處到參考平面的距離，Dex=dist(Hex,plane)為光線離開單元邊界處參考平面的距離。如圖8所示。

光線在不同的參考平面上迭代，逐像素步進，在每個迭代位置，使用公式進行相交測試，若相交則輸出當前交點的顏色紋理，渲染在屏幕上。

5 實驗與分析

實驗使用C++與GLSL語言，在Microsoft Windows 7操作系統(tǒng)，OpenGL4.4.0上實現(xiàn)。實驗環(huán)境為Inter?CoreTMi5-3337U處理器，4 GB內存。顯卡為NVIDIA GeForce GT 620M。

為了驗證本文所述的稀疏空間高度場的表達能力及對所述模型算法進行重現(xiàn)驗證，實驗所用的數(shù)據(jù)來自NVIDIA SDK的Venusm模型、Lady和Rabbit三維模型。

圖9是不同分辨率下的Venusm模型渲染效果對比。從對比圖可知，Venusm模型場景分辨率為1 024×1 024時即可以得到質量較高的圖像。

圖9 基于稀疏空間高度場的Venusm模型在不同分辨率下的效果對比

表1給出了本文所用的模型參數(shù)和測試結果，在不同的分辨率下，對比了使用SVO和使用本文高度場八叉樹進行建模時兩者的占用存儲空間對比。從表1可知，使用高度場八叉樹在相同的分辨率情況下比SVO占用了更小的存儲空間。因為隨著分辨率的不斷提高，SVO除空節(jié)點外的每一個節(jié)點都有8個子節(jié)點，而高度場八叉樹中，只要存在單一高度場的節(jié)點將不再產生子節(jié)點。

表1 不同分辨率下規(guī)則八叉樹與本文算法占用存儲空間對比MB

圖10是使用SVO和高度場八叉樹的模型結構圖及參考平面（綠色）。從圖10可知，在樹深度相同的情況下，SVO生成的模型幾乎被八叉樹的子節(jié)點塊完全覆蓋，而本文算法在相對平坦（如兔子的腹部）或相對對稱（如人的腰部和腿部）的部分能快速地找到單一高度場，具有更少的節(jié)點數(shù)。

圖10 （a）最大深度為8的SVO結構圖

圖10 （b）最大深度為8的高度場八叉樹結構圖

圖10 （c）深度5時的單一高度場參考平面

圖10 （d）最大深度為8的SVO結構圖

圖10 （e）最大深度為8的高度場八叉樹結構圖

圖10 （f）深度3時的單一高度場參考平面

圖11是平面分辨率為4 096×4 096的Lady模型，在本文算法與文獻[7]算法下的光線投射幀速率對比。圖中橫坐標為渲染過程中的時間記錄，縱坐標為記錄的幀速率。根據(jù)幀速率公式[19]：

dt為幀時間，w×h為屏幕分辨率，文獻[7]的平均幀速率大約為55幀/s，而高度場八叉樹的平均幀速率大約為83幀/s，本文算法具有更高的光線投射效率。

圖11 兩種算法的光線投射效率對比

6 結束語

本文提出了一種基于高度場八叉樹的體特征表達算法。算法將傳統(tǒng)的z向高度場擴展到了x、y、z三個方向的高度場，借助八叉樹的空間分割，使得高度場具備了體特征表達的能力。與體素八叉樹表達相比，高度場八叉樹和體素八叉樹一樣，都是基于三維的空間網(wǎng)格結構，但高度場八叉樹的子節(jié)點是一個二維空間的高度場數(shù)據(jù)，而體素八叉樹的子節(jié)點是一個三維空間的體素數(shù)據(jù)，這使得高度場八叉樹在存儲空間和光線投射效率上都比體素八叉樹更有優(yōu)勢，實驗結果也進一步證明了算法的有效性。因此，本文算法在保持傳統(tǒng)高度場表達優(yōu)勢的同時，又解決了傳統(tǒng)高度場體特征表達能力不足的問題。

本文提出的算法還有需要優(yōu)化的方向：一是算法沒有考慮極端復雜的模型，對于已經(jīng)達到樹最大深度，仍然未找到高度場的節(jié)點采用網(wǎng)格模型渲染，下一步可以在此類節(jié)點中對高度場分層，形成層次高度場；二是八叉樹的構建過程需要不斷地進行三角面片剖分及相交判斷，影響了建樹的時間，下一步在GPU中實現(xiàn)這一過程，可以很好地解決這一問題。

[1] Kumar S，Manocha D.Interactive display of large scale trimmed NURBS models[R].University of North Carolina at Chapel Hill，1994.

[2] 韓敏，陳鴻博，鄭丹晨.基于分塊Morton壓縮和混合生成準則的地形簡化方法[J].計算機輔助設計與圖形學學報，2014，26（2）：293-301.

[3] 郭力真，吳恩華.多邊形模型簡化算法綜述[J].計算機應用研究，2005，22（8）：20-23.

[4] Akeley K.Reality engine graphics[C]//Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques，1993：109-116.

[5] Whitted T.An improved illumination model for shaded display[J].Communications of the ACM，1980，23：343-349.

[6] Kaufman A，Shimony E.3D scan-conversion algorithms for voxel-based graphics[C]//Proceedings of the 1986 Workshop on Interactive 3D Graphics，1987：45-75.

[7] Laine S，Karras T.Efficient sparse voxel octrees[J].IEEE Transactions on Visualization and Computer Graphics，2011，17（8）：1048-1059.

[8] Crassin C，Neyret F，Sainz M，et al.Interactive indirect illumination using voxel cone tracing[J].Computer Graphics Forum，2011，30（7）：1921-1930.

[9] K?mpe V，Sintorn E，Assarsson U.High resolution sparse voxel DAGs[J].ACM Transactions on Graphics，2013，32（4）：101.

[10] Villanueva A J，Marton F，Gobbetti E.SSVDAGs：Symmetryaware sparse voxel DAGs[C]//Proceedings of the 20th ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games，2016：7-14.

[11] Zhai R，Lu K，Pan W，et al.GPU-based real-time terrain rendering：Design and implementation[J].Neurocomputing，2016，171（C）：1-8.

[12] 羅健欣，胡谷雨，倪桂強.平行流形空間光線投射高度場可視化算法[J].計算機輔助設計與圖形學學報，2013，25（3）：356-362.

[13] Luo J，Hu G，Ni G.Dual-space ray casting for height fieldrendering[J].ComputerAnimationandVirtual Worlds，2014，25（1）：45-56.

[14] Paredes E G，Amor M，Bóo M，et al.Hybrid terrain rendering based on the external edge primitive[J].International Journal of Geographical Information Science，2016，30（6）：1095-1116.

[15] Ammann L，Dischler J M.Hybrid rendering of dynamic heightfields using ray-casting and mesh rasterization[C]//Graphics Interface.[S.l.]：Canadian Information Processing Society，2010：161-168.

[16] Koca ?，Güdükbay U.A hybrid representation for modeling，interactive editing，and real-time visualization of terrains with volumetric features[J].International Journal of Geographical Information Science，2014，28（9）：1821-1847.

[17] 于海燕，何援軍.空間兩三角形的相交問題[J].圖學學報，2013，34（4）：54-62.

[18] Luo J，Ni G，Cui P，et al.Quad-tree atlas ray casting：A GPU based framework for terrain visualization and its applications[M]//TransactionsonEdutainmentVII.Berlin Heidelberg：Springer，2012：74-85.

[19] van Wingerden T L.Real-time ray tracing and editing of large voxel scenes[D].Utrecht University，2015.

GAO Yi,LUO Jianxin,QIU Hangping,et al.Volumetric features representation algorithm using heightfields-octree.Computer Engineering andApplications,2018,54（6）：1-6.

GAO Yi1，2,LUO Jianxin1,QIU Hangping1,TANG Bin1,WU Bo1

1.PLAArmy Engineering University,Nanjing 210007,China
2.PLATroops of 61175,China

Volumetric features representation plays a vital role for user understanding and recognizing the virtual environment.The current algorithm is inefficient due to its large storage and inconvenient acceleration in GPU,and it is difficult to satisfy the real-time requirements of visualization.Aiming at this problem,an efficient volumetric features representation algorithm using heightfields-octree is proposed.The algorithm can not only solve the problem that the heightfields can only represent 2.5 dimensional scene,and cannot express the true 3 dimensional scene,but also provide a new feasible way for volumetric features representation.The heightfields representation of 3D scene is generated by octree structure,which extends the traditional heightfields of z to x,y and z three directions.Firstly,a preprocessing method of triangular is put forward,ensuring model accuracy and data integrity.Secondly,an algorithm of heightfields judgment and rasterization on projection transformation is proposed,converting geometric primitives into heightfields of two-dimensional space.Finally,the ray casting algorithm based on heightfields octree is realized.The experimental results show that the algorithm can dramatically reduce data storage capacity,and higher ray casting efficiency,and better expression of 3 dimensional scene.

volumetric features representation;heightfields-octree;projection transformation;ray casting

體特征表達對用戶理解和認知虛擬環(huán)境有著至關重要的作用。當前的體特征表達算法由于存儲量大且不易于在GPU中加速等問題，渲染效率低下，難以滿足場景可視化的實時性需求。針對這一問題，提出了一種高效的高度場八叉樹體特征表達算法，不僅解決了傳統(tǒng)高度場僅能表達2.5維模型，無法表達真三維模型的問題，而且為體特征表達提供了一種新的可行途徑。算法使用八叉樹結構生成三維模型的高度場表示，將傳統(tǒng)的z向高度場擴展到x，y，z三個方向的高度場。首先，提出了三角面片預處理方法，保證模型精度和數(shù)據(jù)的完整性;其次，提出了基于投影變換的高度場表示判斷及柵格化方法，將幾何圖元轉換成二維空間的高度場數(shù)據(jù);最后，提出了基于高度場八叉樹的光線投射算法。實驗結果表明，算法能極大地減少存儲量，具有較高的光線投射效率，表達三維模型時取得較好效果。

體特征表達；高度場八叉樹；投影變換；光線投射

2017-11-17

2018-01-26

1002-8331（2018）06-0001-06

A

TP393

10.3778/j.issn.1002-8331.1711-0245

國家部委科技基金；江蘇省青年科學基金（No.BK20150722）。

高藝（1982—），女，博士研究生，工程師，主要研究方向為虛擬現(xiàn)實與仿真，E-mail：iamninigao@163.com；羅健欣（1984—），男，博士，講師，主要研究方向為計算機圖形與圖像處理；裘杭萍（1965—），女，博士，教授，主要研究方向為系統(tǒng)工程；唐斌（1986—），男，博士，主要研究方向為計算機圖形與圖像處理；吳波（1977—），男，講師，主要研究方向為系統(tǒng)工程。