丁田妹，徐發(fā)達

（中國汽車技術(shù)研究中心有限公司，天津，300380）

0 引言

LOD（細(xì)節(jié)層次，Levels of Detail）技術(shù)最早于1976年提出，快速發(fā)展時期在21 世紀(jì)初，應(yīng)用的行業(yè)涉及各個領(lǐng)域，尤其是游戲、建筑、地理等行業(yè)，均涉及到大量的三維模型。在這些行業(yè)中，為了追求圖形圖像的高精度及視覺效果的真實性，模型的面片數(shù)據(jù)量非常龐大，再加上高分辨率的貼圖，這樣精細(xì)化的三維模型在交互的過程中，時有卡頓現(xiàn)象，為用戶體驗帶來了極大的困難。而LOD 技術(shù)核心思想就是針對不同狀態(tài)顯示不同分別率的模型數(shù)據(jù)，能有效地降低用戶交互過程中模型顯示卡頓現(xiàn)象。因此，運用LOD 技術(shù)如何高效、準(zhǔn)確地可視化海量模型數(shù)據(jù)，使用戶直觀交互感受，是計算機圖形學(xué)模型數(shù)據(jù)可視化研究中亟待解決的問題。

在三維圖像的顯示中，一個物體的視覺表現(xiàn)主要由三維空間拓?fù)浣Y(jié)構(gòu)、材質(zhì)/貼圖、光照信息組成。近年來，產(chǎn)生了諸多思想也是基于這幾個方面實現(xiàn)多層次模型的可視化。文獻[1]～[3]提出了將空間模型按照語義層次劃分不同的物體塊，基于視覺調(diào)用不同的塊組合，實現(xiàn)不同的層次級別的LOD；文獻[4]則從模型的貼圖入手，利用景深原理將映射到屏幕中的視角距離遠的物體的貼圖進行模糊處理，實現(xiàn)近實遠虛的效果，這種方式大為提高了模型內(nèi)存占用率和加載率；文獻[5]～[6]基于顯示器的像素，通過算法對點云數(shù)據(jù)進行特征提取匹配，完成LOD 動態(tài)繪制；文獻[7]～[11]從三維模型的拓?fù)浣Y(jié)構(gòu)出發(fā)，通過算法簡化模型的網(wǎng)格面數(shù)進行LOD 實時繪制。以上方法是實現(xiàn)LOD 繪制的主要思想，其中優(yōu)化模型拓?fù)浣Y(jié)構(gòu)和優(yōu)化圖形繪制速率是該領(lǐng)域研究最為熱門的方向。作為被廣泛應(yīng)用的四叉樹算法，其核心思想也是通過優(yōu)化場景模型拓?fù)浣Y(jié)構(gòu)而提高模型的顯示效果。本文將從最具代表性的四叉樹算法入手進行歸納整理，了解各類算法的優(yōu)缺點，深入分析其發(fā)展?fàn)顩r，為計算機圖形化的發(fā)展提供一定的借鑒參考意義。

1 多層次細(xì)節(jié)LOD 算法研究

構(gòu)建不同級別面數(shù)模型是LOD 技術(shù)應(yīng)用成功的關(guān)鍵。LOD 模型主要分為三類：一是離散LOD 模型，即LOD 模型保存多個不同分辨率副本的模型，在運用的過程中根據(jù)當(dāng)前的實際需要調(diào)用不同的分辨率副本；二是連續(xù)LOD 模型，即運用相關(guān)算法實時生成不同分辨率的模型，模型的變化根據(jù)視角到物體的距離連續(xù)變化；三是多分辨率LOD 模型，針對單個物體模型來說，物體模型各局部的分辨率根據(jù)視角的遠近顯示不同細(xì)節(jié)層次的水平，即單個物體的不同部分的分辨率與視角距離有關(guān)，并且隨著視角的移動連續(xù)變化?？傮w來看，離散型模型的分辨率是隨著視角的變化進行跳躍性變化，連續(xù)型模型的分辨率隨著視角的變化進行連續(xù)性變化，多分辨率型模型的分辨率隨著視角的變化進行局部細(xì)節(jié)的連續(xù)性變化。其中多分辨率型模型適合于地面、高山、海洋等大場景繪制。以上三類模型在算法上具有共性，多分辨率LOD 模型算法可用于實現(xiàn)離散LOD 模型和連續(xù)LOD 模型，其只是在顯示時的加載方式不同。因此本文將著重對多分辨率LOD的經(jīng)典算法四叉樹算法進行歸納整理。

分析國內(nèi)外現(xiàn)有文獻，將基于四叉樹分割LOD 算法過程大致分為：節(jié)點評價、裂縫修復(fù)改進、渲染。大致流程如圖1 所示。

圖1 四叉樹算法流程

■1.1 節(jié)點評價

（1）視距法則

視距指的是觀察者的視點到節(jié)點的距離，視距近的模型分辨率高，視距遠的模型分辨率低。如圖2所示，L 為視點到某節(jié)點中心點的距離，d 為節(jié)點的邊長，通過定義控制因子C1 來控制視點距離對于細(xì)節(jié)程度的影響關(guān)系，規(guī)則為L/d<1C。

圖2 視距原理

當(dāng)視點距離節(jié)點越近，即L 值越小，節(jié)點的邊長越小，即d 值越小，則節(jié)點被細(xì)分?？刂埔蜃覥1 值為常量，根據(jù)實際需要可進行修改。L在傳統(tǒng)算法中可以直接計算視點（x0，y0，z0）與目標(biāo)點（x1，y1，z1）的距離，即：

上述計算過程中涉及開方運算，而在大規(guī)模模型計算中節(jié)點數(shù)量龐大，因此大量的開方運算會嚴(yán)重導(dǎo)致運行效率降低，基于此，文獻[8]采用如下的計算方法來優(yōu)化改進：

（2）粗糙度法則

僅僅考慮視點距離這一因素顯然是不夠的，當(dāng)一個節(jié)點的崎嶇程度較大時，即使該節(jié)點距離視點很遠，依然需要將其進行細(xì)分，這就需要考慮到粗糙度。一般常用每個網(wǎng)格四條邊的起伏程度和中心點起伏程度中的最大值來定義網(wǎng)格的粗糙度。利用公式（3）構(gòu)造d0來度量物體表面的起伏形態(tài)，各模型塊邊的中點處的高程值和邊界端點高程值的平均值之差即dh0、dh1、dh2、dh3、dh4。

當(dāng)模型結(jié)構(gòu)越復(fù)雜時，則細(xì)分程度將會越高。

圖3 表面粗糙度

綜合視距法則，定義評價函數(shù)：

其中控制因子C2 值為常量。除此以外，也有眾多學(xué)者考慮更多影響因子，對傳統(tǒng)節(jié)點評價方法進行優(yōu)化。文獻[9]采用9 個中心點與臨界處的點的相對標(biāo)準(zhǔn)方差來表示控制因子。文獻[8]綜合考慮視點距離，粗糙程度因素之后，將視點移動速度考慮進去，極大程度上還原人眼真實的渲染效果。此外還有學(xué)者將屏幕投影所帶來的誤差考慮進去、模型與不同軸向夾角的影響等，在此不一一贅述。

綜合考慮時間的因素，大部分學(xué)者應(yīng)用時只簡單的將視距法則和粗糙度法則結(jié)合，這種做法略顯片面。部分學(xué)者綜合考慮視點移動速度、屏幕投影等因素，更加能真實的描述視覺的真實體驗，但也同時增加了運算量，對計算機的硬件系統(tǒng)帶來了極大的考驗。

■1.2 裂縫修改

經(jīng)過評價系統(tǒng)的細(xì)化，由于不同網(wǎng)格頂點的高度不一致，因此容易產(chǎn)生裂縫，目前，對于裂縫修復(fù)國內(nèi)外學(xué)者進行了很多嘗試。文獻[8]采用加邊法，通過將細(xì)分程度較低的節(jié)點增加邊來平衡高度差，使塊間裂縫消除。有加邊法，同樣就存在刪邊法，文獻[9]通過在兩個相鄰節(jié)點的拼接處刪掉較高分辨率上造成裂縫的一條邊，得到了較為理想的效果，文獻[10]采用線性插值算法實現(xiàn)不需控制相鄰節(jié)點之間的層級差來消除裂縫，而且該方法不需額外繪制面片。通過對比發(fā)現(xiàn)，刪除法會降低模型的分辨率，當(dāng)相鄰兩個網(wǎng)格模型精度差距較大時，刪除法降低模型精度會更為嚴(yán)重，且不能實現(xiàn)相鄰節(jié)點細(xì)分程度大于1的情況的裂縫消除，因此大部分的刪邊法會構(gòu)造約束關(guān)系，確保相鄰面塊間的層級差不超過1。除此以外，也有學(xué)者綜合這兩種方法，對層級超過1的相鄰面塊采用加邊法，對層級是1的相鄰面塊采用刪邊法，還有學(xué)者通過對裂縫直接修補進行裂縫消除。

圖4 裂縫產(chǎn)生

相對來說，減邊和加邊操作比較簡單，但對裂縫的處理較粗糙；同時，減邊會增加約束條件也增加部分計算；裂縫直接修補法在視覺細(xì)節(jié)上不夠好，同時對數(shù)據(jù)會進行重復(fù)的處理。綜上所述，雖然國內(nèi)外學(xué)者對模型裂縫做了許多研究，但平衡視覺感受和簡便化的模型算法仍需進一步突破。

■1.3 渲染優(yōu)化

隨著計算機技術(shù)的發(fā)展，部分學(xué)者開始利用GPU的處理進行三維模型實時顯示渲染處理。文獻[11]中提出了四叉樹節(jié)點四個附屬子節(jié)點同時分割的方法，有效提高空間圖像的渲染速度以及精細(xì)程度，雖然該方法模型的拓?fù)渚W(wǎng)格變得復(fù)雜，但渲染的速度提高了；文獻[12]提出了一種CPUGPU 協(xié)同構(gòu)網(wǎng)模式，通過紋理映射技術(shù)對高度圖進行頂點采樣，并映射到網(wǎng)格頂點上，結(jié)合視點動態(tài)完成渲染。雖然部分學(xué)者已經(jīng)開始注意到利用GPU 進行模型繪制，但現(xiàn)階段的研究還較為少，其發(fā)展還存在一些瓶頸，同時鑒于計算機硬件技術(shù)的制約，從該方向入手還需要更深入的研究。

圖5 加邊、減邊方法的前后對比

圖6 文獻[11]所述優(yōu)化算法前后對比

表1 文獻[11]所述方法渲染效果對比

圖7 CPU-GPU 協(xié)同構(gòu)網(wǎng)模式

2 總結(jié)

LOD 模型繪制技術(shù)涉及的環(huán)節(jié)較為復(fù)雜，必須綜合考慮各個步驟之間的相互影響。本文不僅對近幾年比較熱門的LOD 模型可視化顯示的處理思想進行了歸納，并重點梳理了利用四叉樹原理進行網(wǎng)格模型的構(gòu)造方法，主要圍繞了節(jié)點評價、裂縫消除以及渲染優(yōu)化三個方面的研究，總結(jié)分析了各類方法的優(yōu)缺點，實現(xiàn)了對LOD 模型的部分總結(jié)。從現(xiàn)有文獻來看，網(wǎng)格中的裂縫消除法目前還沒有較為高效的解決方案，從渲染優(yōu)化角度處理網(wǎng)格模型的思想目前還沒有受到研究者的重視，還需要進一步的深入研究。