*一、LOD技術(shù)簡介
細(xì)節(jié)層次（Levels of Detail，簡稱LOD）模型的概念，普遍認(rèn)為當(dāng)物體覆蓋屏幕較小區(qū)域時(shí)，可以使用該物體描述較粗的模型，并給出了一個(gè)用于可見面判定算法的幾何層次模型，以便對復(fù)雜場景進(jìn)行快速繪制。1982年，Rubin結(jié)合光線跟蹤算法，提出了用復(fù)雜場景的層次來表示算法及相關(guān)的繪制算法，從而使計(jì)算機(jī)能以較少的時(shí)間繪制復(fù)雜場景。
LOD技術(shù)在不影響畫面視覺效果的條件下，通過逐次簡化景物的表面細(xì)節(jié)來減少場景的幾何復(fù)雜性，從而提高繪制算法的效率。該技術(shù)通常對每一原始多面體模型建立幾個(gè)不同逼近精度的幾何模型。與原模型相比，每個(gè)模型均保留了一定層次的細(xì)節(jié)。在繪制時(shí)，根據(jù)不同的標(biāo)準(zhǔn)選擇適當(dāng)?shù)膶哟文Ｐ蛠肀硎疚矬w。
目前，LOD技術(shù)已廣泛地應(yīng)用于實(shí)時(shí)圖像通信、交互式可視化、虛擬現(xiàn)實(shí)、地形表示、飛行模擬、碰撞檢測、及限時(shí)圖形繪制等領(lǐng)域，成為一項(xiàng)要害技術(shù)。很多造型軟件和VR開發(fā)系統(tǒng)都開始支持LOD模型表示。
圖1. 經(jīng)過LOD技術(shù)處理后不同顆粒度的3D模型示意圖
*二、典型的LOD實(shí)現(xiàn)方式
l 近平面合并法
Hinkler等的幾何優(yōu)化方法檢測出共面或近似共面的三角面片，將這些三角面片合并為大的多邊形，然后用較少數(shù)目的三角形將這個(gè)多邊形重新三角化。這個(gè)方法的步驟是：
（1）迅速地將面片分類為近似共面的集合；
（2）快速合并這些集合中的面片；
（3）簡單而且魯棒的三角化。
面片分類依據(jù)的是他們各自的法線之間的夾角。該算法的誤差衡量標(biāo)準(zhǔn)可以歸為全局誤差，但是由于它僅僅依據(jù)法線之間的夾角，其誤差評估準(zhǔn)確性較差。它不能保證一定誤差限制。
l 幾何元素（頂點(diǎn)/邊/面）刪除法
幾何元素刪除法由局部幾何優(yōu)化機(jī)制驅(qū)動(dòng)，要計(jì)算每次刪除產(chǎn)生的近似誤差。
Schroeder的頂點(diǎn)刪除算法通過刪除滿足距離或者角度標(biāo)準(zhǔn)的頂點(diǎn)來減小三角網(wǎng)格的復(fù)雜度。刪除頂點(diǎn)留下的空洞要重新三角化填補(bǔ)。該算法速度快，但不能保證近似誤差。它估算局部誤差時(shí)，未考慮新面片同原始網(wǎng)格的聯(lián)系和誤差積累。
Hoppe的漸進(jìn)網(wǎng)格算法包含基于邊折疊的網(wǎng)格簡化方法、能量函數(shù)優(yōu)化和新的多分辨率表示。算法采用了單步和可逆的邊折疊操作，可以將整個(gè)簡化過程存入一個(gè)多分辨率數(shù)據(jù)結(jié)構(gòu)（稱為漸進(jìn)網(wǎng)格表示（PM））。PM方案由一個(gè)簡化網(wǎng)格Mk和一系列細(xì)化記錄（通過與從原始網(wǎng)格M0得到簡化網(wǎng)格Mk的簡化步驟的相反步驟得到）, 這些細(xì)化記錄可以使網(wǎng)格Mk通過逐步求精得到任意精確度的網(wǎng)格Mi。在簡化過程中，將每條邊按照其折疊的能量代價(jià)排序得到一個(gè)優(yōu)先級隊(duì)列，通過這個(gè)隊(duì)列實(shí)現(xiàn)邊折疊操作。該算法也是采用全局誤差度量。
l 聚類算法
Rossignac等的頂點(diǎn)聚類算法通過檢測且合并相鄰頂點(diǎn)的聚類來簡化網(wǎng)格。每個(gè)聚類被一個(gè)代表頂點(diǎn)取代，這個(gè)代表頂點(diǎn)可能是頂點(diǎn)聚類的中心或者是聚類中具有最大權(quán)值的頂點(diǎn)（定義頂點(diǎn)的權(quán)值是為了強(qiáng)調(diào)相對的視覺重要性）。然后，去除那些由于聚類操作引起的重疊或者退化的邊或者三角形。
算法簡化引入的誤差由用戶定義的準(zhǔn)確度控制，這個(gè)標(biāo)準(zhǔn)用來驅(qū)動(dòng)聚類尺寸的選擇。該算法實(shí)現(xiàn)簡單、速度快，但是沒有考慮到保持原始網(wǎng)格的拓?fù)浜蛶缀谓Y(jié)構(gòu)，有可能生成非常粗糙的近似網(wǎng)格。
l 重新劃分算法
Turk的重新劃分算法先將一定數(shù)量的點(diǎn)分布到原有網(wǎng)格上 ，然后新點(diǎn)與老頂點(diǎn)生成一個(gè)中間網(wǎng)格，最后刪除中間網(wǎng)格中的老頂點(diǎn)，并對產(chǎn)生的多邊形區(qū)域進(jìn)行局部三角化，形成以新點(diǎn)為頂點(diǎn)的三角形網(wǎng)格。其中分布新點(diǎn)采用排斥力算法，即先隨機(jī)分布新點(diǎn)，然后計(jì)算新點(diǎn)之間的排斥力，根據(jù)排斥力在網(wǎng)格上移動(dòng)這些新點(diǎn)，使它們重新分布。排斥力的大小與新點(diǎn)之間的距離、新點(diǎn)所在三角形的曲率和面積有關(guān)。
這種方法對那些較光滑的模型是很有效的，但對于那些不光滑的模型 ，效果較差；由于根據(jù)排斥力重新分布新點(diǎn)，涉及到平面旋轉(zhuǎn)或投影，計(jì)算量和誤差都較大。
l 小波分解算法
Eck等的基于小波變換的多分辨率模型使用了帶有修正項(xiàng)的基本網(wǎng)格，修正項(xiàng)稱為小波系數(shù)，用來表示模型在不同分辨率情況下的細(xì)節(jié)特征。算法的三個(gè)主要步驟：
（1）分割：輸入網(wǎng)格M被分成一些（數(shù)目較少）三角形的區(qū)域T1,......,Tn,
由此構(gòu)成的低分辨率三角網(wǎng)格稱為基本網(wǎng)格K0。
（2）參數(shù)化：對于每個(gè)三角區(qū)域Ti，根據(jù)它在基本網(wǎng)格K0上相應(yīng)的表面進(jìn)行局部參數(shù)化。
（3）重新采樣：對基本網(wǎng)格進(jìn)行j次遞歸細(xì)分就得到網(wǎng)格Kj，并且通過使用參數(shù)化過程中建立的參數(shù)將Kj的頂點(diǎn)映射到3維空間中得到網(wǎng)格Kj的坐標(biāo)。
此算法可以處理任意拓?fù)浣Y(jié)構(gòu)的網(wǎng)格，而且可以提供：有界誤差、緊湊的多分辨率表示和多分辨率尺度下的網(wǎng)格編輯。
*三、漢振HANCHINE 3D渲染庫
l LOD技術(shù)處理
漢振通過對底層opengl底層函數(shù)的封裝和優(yōu)化，開發(fā)出了實(shí)用性更強(qiáng)的3D渲染庫，主要用于處理3D點(diǎn)云和模型數(shù)據(jù)的顯示和交互性操作，也提供部分3D數(shù)據(jù)的優(yōu)化算法。利用到LOD技術(shù)，實(shí)現(xiàn)了對大數(shù)量級的點(diǎn)云數(shù)據(jù)和復(fù)雜的大型模型的優(yōu)化顯示。不斷切換模型和點(diǎn)云的顆粒度，來實(shí)現(xiàn)更高效率的點(diǎn)云顯示，讓用戶操作過程中沒有受到數(shù)據(jù)量的拖累，極大的提高了用戶操作的體驗(yàn)，也釋放了更多的計(jì)算機(jī)資源給用戶和開發(fā)人員。
l 對于模型數(shù)據(jù)的優(yōu)化
對于模型而言，其實(shí)和點(diǎn)云的處理類似，不同的是，模型的各個(gè)頂點(diǎn)需要重新組合成面片，然后對不同層級的LOD模型進(jìn)行重新的渲染顯示。從圖2、圖3、圖4中可以看到，模型的顆粒度變化可能看起來不明顯，但是坐標(biāo)系下的LOD顆粒度變化明顯，通過不斷的拉近模型的距離，坐標(biāo)系的網(wǎng)格明顯增加，同時(shí)將不在攝像機(jī)范圍內(nèi)的渲染場景裁剪掉，來實(shí)現(xiàn)數(shù)據(jù)的渲染優(yōu)化。
圖2. 模型LOD-Level1示意圖
圖3. 模型LOD-Level2示意圖
圖4. 模型LOD-Level3示意圖
l 對于點(diǎn)云數(shù)據(jù)的優(yōu)化
在點(diǎn)云數(shù)據(jù)密集的時(shí)候，將點(diǎn)云數(shù)據(jù)進(jìn)行分別提煉，保留主要的點(diǎn)云數(shù)據(jù)，當(dāng)對點(diǎn)云進(jìn)行放大的時(shí)候，及時(shí)進(jìn)行點(diǎn)云的切割和分離，并降低提煉的等級，顯示出顆粒度更高的LOD級別的顯示內(nèi)容。如圖所示就是百萬級點(diǎn)云數(shù)據(jù)，不斷放大時(shí)，LOD細(xì)化的示意圖。通過有效的裁剪和LOD細(xì)化，將渲染的數(shù)據(jù)控制在合理的范圍內(nèi)，當(dāng)不斷地拉近點(diǎn)云時(shí)，將更多的細(xì)化點(diǎn)云數(shù)據(jù)，并且不斷裁剪場景視野外的內(nèi)容，減輕渲染壓力，獲得性能上的提升。圖5，6，7，8，9就是各個(gè)LOD層級下的細(xì)化表現(xiàn)。
圖5. 點(diǎn)云LOD-Level1示意圖
圖6. 點(diǎn)云LOD-Level2示意圖
圖7. 點(diǎn)云LOD-Level3示意圖
圖8. 點(diǎn)云LOD-Level4示意圖
圖9. 點(diǎn)云LOD-Level5示意圖