概要:

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

一、LOD技術(shù)簡介

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

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

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

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

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

01 近平面合并法

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

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

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

（3）簡單而且魯棒的三角化。

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

02 幾何元素（頂點/邊/面）刪除法

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

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

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

03 聚類算法

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

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

04 重新劃分算法

Turk的重新劃分算法先將一定數(shù)量的點分布到原有網(wǎng)格上 ，然后新點與老頂點生成一個中間網(wǎng)格，后刪除中間網(wǎng)格中的老頂點，并對產(chǎn)生的多邊形區(qū)域進(jìn)行局部三角化，形成以新點為頂點的三角形網(wǎng)格。其中分布新點采用排斥力算法，即先隨機(jī)分布新點，然后計算新點之間的排斥力，根據(jù)排斥力在網(wǎng)格上移動這些新點，使它們重新分布。排斥力的大小與新點之間的距離、新點所在三角形的曲率和面積有關(guān)。

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

05 小波分解算法

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

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

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

（3）重新采樣：對基本網(wǎng)格進(jìn)行j次遞歸細(xì)分就得到網(wǎng)格Kj，并且通過使用參數(shù)化過程中建立的參數(shù)將Kj的頂點映射到3維空間中得到網(wǎng)格Kj的坐標(biāo)。

此算法可以處理任意拓?fù)浣Y(jié)構(gòu)的網(wǎng)格，而且可以提供：有界誤差、緊湊的多分辨率表示和多分辨率尺度下的網(wǎng)格編輯。

三、漢振HANCHINE 3D渲染庫

01 LOD技術(shù)處理

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

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

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

圖2. 模型LOD-Level1示意圖

圖3. 模型LOD-Level2示意圖

圖4. 模型LOD-Level3示意圖

03 對于點云數(shù)據(jù)的優(yōu)化

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

圖5. 點云LOD-Level1示意圖

圖6. 點云LOD-Level2示意圖

圖7. 點云LOD-Level3示意圖

圖8. 點云LOD-Level4示意圖

圖9. 點云LOD-Level5示意圖