概要:

在機(jī)器視覺項(xiàng)目和標(biāo)準(zhǔn)軟件的研發(fā)過程中，如何提高大數(shù)量級(jí)點(diǎn)云和復(fù)雜3D模型的渲染速度，一直是軟件開發(fā)人員的關(guān)注重點(diǎn)。本文將介紹漢振智能如何利用LOD技術(shù)，提高3D軟件的交互性，大幅減少3D渲染所占用的計(jì)算機(jī)資源，以及更快更有效率地展示模型和點(diǎn)云的數(shù)據(jù)。

一、LOD技術(shù)簡(jiǎn)介

細(xì)節(jié)層次（Levels of Detail，簡(jiǎn)稱LOD）模型的概念，普遍認(rèn)為當(dāng)物體覆蓋屏幕較小區(qū)域時(shí)，可以使用該物體描述較粗的模型，并給出了一個(gè)用于可見面判定算法的幾何層次模型，以便對(duì)復(fù)雜場(chǎng)景進(jìn)行快速繪制。1982年，Rubin結(jié)合光線跟蹤算法，提出了用復(fù)雜場(chǎng)景的層次來(lái)表示算法及相關(guān)的繪制算法，從而使計(jì)算機(jī)能以較少的時(shí)間繪制復(fù)雜場(chǎng)景。

LOD技術(shù)在不影響畫面視覺效果的條件下，通過逐次簡(jiǎn)化景物的表面細(xì)節(jié)來(lái)減少場(chǎng)景的幾何復(fù)雜性，從而提高繪制算法的效率。該技術(shù)通常對(duì)每一原始多面體模型建立幾個(gè)不同逼近精度的幾何模型。與原模型相比，每個(gè)模型均保留了一定層次的細(xì)節(jié)。在繪制時(shí)，根據(jù)不同的標(biāo)準(zhǔn)選擇適當(dāng)?shù)膶哟文Ｐ蛠?lái)表示物體。

目前，LOD技術(shù)已廣泛地應(yīng)用于實(shí)時(shí)圖像通信、交互式可視化、虛擬現(xiàn)實(shí)、地形表示、飛行模擬、碰撞檢測(cè)、及*圖形繪制等領(lǐng)域，成為一項(xiàng)要害技術(shù)。很多造型軟件和VR開發(fā)系統(tǒng)都開始支持LOD模型表示。

圖1. 經(jīng)過LOD技術(shù)處理后不同顆粒度的3D模型示意圖

二、典型的LOD實(shí)現(xiàn)方式

01 近平面合并法

Hinkler等的幾何優(yōu)化方法檢測(cè)出共面或近似共面的三角面片，將這些三角面片合并為大的多邊形，然后用較少數(shù)目的三角形將這個(gè)多邊形重新三角化。這個(gè)方法的步驟是：

（1）迅速地將面片分類為近似共面的集合；

（2）快速合并這些集合中的面片；

（3）簡(jiǎn)單而且魯棒的三角化。

面片分類依據(jù)的是他們各自的法線之間的夾角。該算法的誤差衡量標(biāo)準(zhǔn)可以歸為全局誤差，但是由于它僅僅依據(jù)法線之間的夾角，其誤差評(píng)估準(zhǔn)確性較差。它不能保證一定誤差限制。

02 幾何元素（頂點(diǎn)/邊/面）刪除法

幾何元素刪除法由局部幾何優(yōu)化機(jī)制驅(qū)動(dòng)，要計(jì)算每次刪除產(chǎn)生的近似誤差。

Schroeder的頂點(diǎn)刪除算法通過刪除滿足距離或者角度標(biāo)準(zhǔn)的頂點(diǎn)來(lái)減小三角網(wǎng)格的復(fù)雜度。刪除頂點(diǎn)留下的空洞要重新三角化*。該算法速度快，但不能保證近似誤差。它估算局部誤差時(shí)，未考慮新面片同原始網(wǎng)格的關(guān)系和誤差積累。

Hoppe的漸進(jìn)網(wǎng)格算法包含基于邊折疊的網(wǎng)格簡(jiǎn)化方法、能量函數(shù)優(yōu)化和新的多分辨率表示。算法采用了單步和可逆的邊折疊操作，可以將整個(gè)簡(jiǎn)化過程存入一個(gè)多分辨率數(shù)據(jù)結(jié)構(gòu)（稱為漸進(jìn)網(wǎng)格表示（PM））。PM方案由一個(gè)簡(jiǎn)化網(wǎng)格Mk和一系列細(xì)化記錄（通過與從原始網(wǎng)格M0得到簡(jiǎn)化網(wǎng)格Mk的簡(jiǎn)化步驟的相反步驟得到）, 這些細(xì)化記錄可以使網(wǎng)格Mk通過逐步求精得到任意精確度的網(wǎng)格Mi。在簡(jiǎn)化過程中，將每條邊按照其折疊的能量代價(jià)排序得到一個(gè)優(yōu)先級(jí)隊(duì)列，通過這個(gè)隊(duì)列實(shí)現(xiàn)邊折疊操作。該算法也是采用全局誤差度量。

03 聚類算法

Rossignac等的頂點(diǎn)聚類算法通過檢測(cè)且合并相鄰頂點(diǎn)的聚類來(lái)簡(jiǎn)化網(wǎng)格。每個(gè)聚類被一個(gè)代表頂點(diǎn)取代，這個(gè)代表頂點(diǎn)可能是頂點(diǎn)聚類的中心或者是聚類中具有大權(quán)值的頂點(diǎn)（定義頂點(diǎn)的權(quán)值是為了強(qiáng)調(diào)相對(duì)的視覺重要性）。然后，去除那些由于聚類操作引起的重疊或者退化的邊或者三角形。

算法簡(jiǎn)化引入的誤差由用戶定義的準(zhǔn)確度控制，這個(gè)標(biāo)準(zhǔn)用來(lái)驅(qū)動(dòng)聚類尺寸的選擇。該算法實(shí)現(xiàn)簡(jiǎn)單、速度快，但是沒有考慮到保持原始網(wǎng)格的拓?fù)浜蛶缀谓Y(jié)構(gòu)，有可能生成非常粗糙的近似網(wǎng)格。

04 重新劃分算法

Turk的重新劃分算法先將一定數(shù)量的點(diǎn)分布到原有網(wǎng)格上 ，然后新點(diǎn)與老頂點(diǎn)生成一個(gè)中間網(wǎng)格，后刪除中間網(wǎng)格中的老頂點(diǎn)，并對(duì)產(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)。

這種方法對(duì)那些較光滑的模型是很有效的，但對(duì)于那些不光滑的模型 ，效果較差；由于根據(jù)排斥力重新分布新點(diǎn)，涉及到平面旋轉(zhuǎn)或投影，計(jì)算量和誤差都較大。

05 小波分解算法

Eck等的基于小波變換的多分辨率模型使用了帶有修正項(xiàng)的基本網(wǎng)格，修正項(xiàng)稱為小波系數(shù)，用來(lái)表示模型在不同分辨率情況下的細(xì)節(jié)特征。算法的三個(gè)主要步驟：

（1）分割：輸入網(wǎng)格M被分成一些（數(shù)目較少）三角形的區(qū)域T1,......,Tn, 由此構(gòu)成的低分辨率三角網(wǎng)格稱為基本網(wǎng)格K0。

（2）參數(shù)化：對(duì)于每個(gè)三角區(qū)域Ti，根據(jù)它在基本網(wǎng)格K0上相應(yīng)的表面進(jìn)行局部參數(shù)化。

（3）重新采樣：對(duì)基本網(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渲染庫(kù)

01 LOD技術(shù)處理

漢振通過對(duì)底層opengl底層函數(shù)的封裝和優(yōu)化，開發(fā)出了實(shí)用性更強(qiáng)的3D渲染庫(kù)，主要用于處理3D點(diǎn)云和模型數(shù)據(jù)的顯示和交互性操作，也提供部分3D數(shù)據(jù)的優(yōu)化算法。利用到LOD技術(shù)，實(shí)現(xiàn)了對(duì)大數(shù)量級(jí)的點(diǎn)云數(shù)據(jù)和復(fù)雜的大型模型的優(yōu)化顯示。不斷切換模型和點(diǎn)云的顆粒度，來(lái)實(shí)現(xiàn)更高效率的點(diǎn)云顯示，讓用戶操作過程中沒有受到數(shù)據(jù)量的拖累，極大的提高了用戶操作的體驗(yàn)，也釋放了更多的計(jì)算機(jī)資源給用戶和開發(fā)人員。

02 對(duì)于模型數(shù)據(jù)的優(yōu)化

對(duì)于模型而言，其實(shí)和點(diǎn)云的處理類似，不同的是，模型的各個(gè)頂點(diǎn)需要重新組合成面片，然后對(duì)不同層級(jí)的LOD模型進(jìn)行重新的渲染顯示。從圖2、圖3、圖4中可以看到，模型的顆粒度變化可能看起來(lái)不明顯，但是坐標(biāo)系下的LOD顆粒度變化明顯，通過不斷的拉近模型的距離，坐標(biāo)系的網(wǎng)格明顯增加，同時(shí)將不在攝像機(jī)范圍內(nèi)的渲染場(chǎng)景裁剪掉，來(lái)實(shí)現(xiàn)數(shù)據(jù)的渲染優(yōu)化。

圖2. 模型LOD-Level1示意圖

圖3. 模型LOD-Level2示意圖

圖4. 模型LOD-Level3示意圖

03 對(duì)于點(diǎn)云數(shù)據(jù)的優(yōu)化

在點(diǎn)云數(shù)據(jù)密集的時(shí)候，將點(diǎn)云數(shù)據(jù)進(jìn)行分別提煉，保留主要的點(diǎn)云數(shù)據(jù)，當(dāng)對(duì)點(diǎn)云進(jìn)行放大的時(shí)候，及時(shí)進(jìn)行點(diǎn)云的切割和分離，并降低提煉的等級(jí)，顯示出顆粒度更高的LOD級(jí)別的顯示內(nèi)容。如圖所示就是百萬(wàn)點(diǎn)云數(shù)據(jù)，不斷放大時(shí)，LOD細(xì)化的示意圖。通過有效的裁剪和LOD細(xì)化，將渲染的數(shù)據(jù)控制在合理的范圍內(nèi)，當(dāng)不斷地拉近點(diǎn)云時(shí)，將更多的細(xì)化點(diǎn)云數(shù)據(jù)，并且不斷裁剪場(chǎng)景視野外的內(nèi)容，減輕渲染壓力，獲得性能上的提升。圖5，6，7，8，9就是各個(gè)LOD層級(jí)下的細(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示意圖