三維模型中多層次細(xì)節(jié)LOD 技術(shù)研究

丁田妹，徐發(fā)達(dá)

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

0 引言

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

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

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

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

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

圖1 四叉樹算法流程

■1.1 節(jié)點(diǎn)評(píng)價(jià)

（1）視距法則

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

圖2 視距原理

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

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

（2）粗糙度法則

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

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

圖3 表面粗糙度

綜合視距法則，定義評(píng)價(jià)函數(shù)：

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

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

■1.2 裂縫修改

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

圖4 裂縫產(chǎn)生

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

■1.3 渲染優(yōu)化

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

圖5 加邊、減邊方法的前后對(duì)比

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

表1 文獻(xiàn)[11]所述方法渲染效果對(duì)比

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

2 總結(jié)

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