虛擬現(xiàn)實(shí)場(chǎng)景內(nèi)三維模型復(fù)雜度的優(yōu)化處理研究

高飛

摘要：虛擬現(xiàn)實(shí)是計(jì)算機(jī)平臺(tái)對(duì)客觀現(xiàn)實(shí)世界的可視化仿真，虛擬現(xiàn)實(shí)的關(guān)鍵在于虛擬環(huán)境場(chǎng)景的構(gòu)建，而三維模型是虛擬現(xiàn)實(shí)環(huán)境建立的基礎(chǔ)。本文介紹網(wǎng)格簡(jiǎn)化的原則和主要方法，重點(diǎn)介紹了邊折疊網(wǎng)格簡(jiǎn)化算法的二次誤差測(cè)度算法的計(jì)算過(guò)程，利用該算法對(duì)模型進(jìn)行了簡(jiǎn)化處理，結(jié)果表明，該算法可有效降低三維模型的復(fù)雜度，在虛擬漫游中發(fā)揮著非常重要的作用。

關(guān)鍵詞：二次誤差測(cè)度算法 網(wǎng)格簡(jiǎn)化 模型復(fù)雜度

中圖分類號(hào)：TP319 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2016）09-0117-02

現(xiàn)如今，虛擬漫游在現(xiàn)代社會(huì)各個(gè)技術(shù)領(lǐng)域內(nèi)具有非常好的應(yīng)用前景，虛擬漫游不僅具有較好的真實(shí)性和直觀性，同時(shí)為用戶提供一個(gè)更好的沉浸感和實(shí)時(shí)互動(dòng)的功能。但是，當(dāng)滿足虛擬漫游的真實(shí)度較高的情況下，虛擬場(chǎng)景內(nèi)物體的模型復(fù)雜度就會(huì)越來(lái)越大，此時(shí)，數(shù)據(jù)量也將變得越來(lái)越大，這不僅給硬件的設(shè)備帶來(lái)巨大的運(yùn)行負(fù)擔(dān)，而且在網(wǎng)絡(luò)端下載大數(shù)據(jù)量的虛擬展示模型時(shí)的下載時(shí)間過(guò)長(zhǎng)，從而導(dǎo)致用戶在瀏覽時(shí)出現(xiàn)內(nèi)容不順暢，體驗(yàn)感下降的問(wèn)題。因此，降低三維模型的復(fù)雜度的研究，對(duì)于虛擬漫游來(lái)說(shuō)，起著至關(guān)重要的作用。本文的內(nèi)容主要是圍繞如何降低三維模型的復(fù)雜度進(jìn)行開展研究。

1 網(wǎng)格簡(jiǎn)化

在計(jì)算機(jī)的圖形學(xué)領(lǐng)域中，通常用多邊形網(wǎng)格來(lái)對(duì)場(chǎng)景中的對(duì)象模型進(jìn)行描述。所謂網(wǎng)格簡(jiǎn)化，就是通過(guò)相應(yīng)的算法，以網(wǎng)格模型的外觀的各種特征不改變的前提下，盡可能的縮減頂點(diǎn)的數(shù)目，將原始模型通過(guò)近似模型的方式來(lái)表示。

一般情況下，網(wǎng)格簡(jiǎn)化采取的方法是將一些對(duì)模型的整體外觀影響非常小的圖元（三角形、邊或頂點(diǎn)）從多邊形網(wǎng)格中移出來(lái)，從而簡(jiǎn)化了模型。

網(wǎng)格簡(jiǎn)化算法：網(wǎng)格模型簡(jiǎn)化的主要算法是二次誤差測(cè)度算法（Quadric Error Metric，QEM），它是一種基于邊折疊操作的典型的簡(jiǎn)化算法。QEM算法的主要原理是通過(guò)計(jì)算頂點(diǎn)到與其相關(guān)聯(lián)平面距離的平方和作為誤差度量，依據(jù)該誤差度量計(jì)算邊收縮代價(jià)。該算法與其他算法比較起來(lái)相對(duì)簡(jiǎn)單，且運(yùn)行速度快，內(nèi)存消耗小，簡(jiǎn)化后的網(wǎng)格與原模型具有非常高的相似度。同時(shí)，在簡(jiǎn)化過(guò)程中，會(huì)產(chǎn)生不同層次結(jié)構(gòu)的簡(jiǎn)化模型，可以生成多分辨率的細(xì)節(jié)層次模型，以此顯示細(xì)節(jié)層次模型。該模型不僅可以為物體提供不同的層次，而且還可以加速圖形的繪制速度和控制場(chǎng)景的復(fù)雜度。

通過(guò)計(jì)算網(wǎng)格中每個(gè)頂點(diǎn)的誤差矩陣，即用二次誤差測(cè)度來(lái)測(cè)量邊的折疊代價(jià)，然后再選取一些有效的頂點(diǎn)對(duì)進(jìn)行邊折疊操作。具體步驟如下：

（1）設(shè)三維網(wǎng)格中頂點(diǎn)v的坐標(biāo)為（vx，vy，vz）T，平面P為ax+by+cz+d=0，其中a2+b2+c2=1，記P=（a，b，c，d）T。頂點(diǎn)v到平面P的距離平方為：

為新頂點(diǎn)的二次誤差測(cè)度矩陣。

（2）有效頂點(diǎn)對(duì)選擇。

三維網(wǎng)格中將滿足以下兩個(gè)條件的頂點(diǎn)對(duì)（V1 ，V2）稱為有效頂點(diǎn)對(duì)：

①（V1，V2）為某一表面上的相鄰點(diǎn)，是一條邊；

②（V1，V2）不是在一條邊上的，但||V1，V2||t。

其中||V1，V2||代表的是兩個(gè)點(diǎn)之間的距離，t代表閾值參數(shù)，它由用戶給定。

t的取值對(duì)模型的簡(jiǎn)化程度有很大的影響。當(dāng)t=0時(shí)，算法為邊折疊算法。當(dāng)t值比較大的情況下，網(wǎng)格模型中將連接原本不相接的部分；當(dāng)t值非常大的情況下，原本相距很遠(yuǎn)的點(diǎn)將合并起來(lái)，模型的簡(jiǎn)化質(zhì)量將受到很大的影響。所以，算法不允許模型中本來(lái)不相連的部分連接了起來(lái)，頂點(diǎn)合并將以下面的形式存在。

（a）邊收縮形式。即對(duì)模型中的任意一條邊L（V1，V2）進(jìn)行邊收縮操作，將一條邊的兩點(diǎn)合并成一點(diǎn)，由（V1，V2）生成了一個(gè)新頂點(diǎn)v。

（b）不構(gòu)成邊的頂點(diǎn)對(duì)合并形式。當(dāng)兩個(gè)頂點(diǎn)不構(gòu)成邊的情況下，且滿足||V1，V2||t，將這兩個(gè)頂點(diǎn)進(jìn)行合并。

（3）新頂點(diǎn)計(jì)算。

假如方程沒有解，那么我們就選取該條邊的兩個(gè)端點(diǎn)V1，V2或其中心點(diǎn)三點(diǎn)位置處，對(duì)二次誤差測(cè)度值最小的點(diǎn)，進(jìn)行收縮操作，使之成為新的頂點(diǎn)。

（4）完成（3）后，會(huì)產(chǎn)生很多新的頂點(diǎn)，此時(shí)，對(duì)網(wǎng)格中所有的頂點(diǎn)對(duì)進(jìn)行更新，對(duì)每一對(duì)頂點(diǎn)的Q值進(jìn)行重新計(jì)算。

（5）最后，如果簡(jiǎn)化的模型符合要求，則結(jié)束迭代這個(gè)過(guò)程，如果不符合要求，重新選擇有效的可進(jìn)行折疊的頂點(diǎn)對(duì)，計(jì)算這些頂點(diǎn)對(duì)每一對(duì)的二次誤差，將誤差存入堆棧中，再次重新計(jì)算所有的每一對(duì)頂點(diǎn)的Q值，直至滿意為止。

2 結(jié)果

通過(guò)利用網(wǎng)格模型簡(jiǎn)化的主要算法二次誤差測(cè)度算法對(duì)模型進(jìn)行簡(jiǎn)化，效果如圖1、圖2和圖3。

參考文獻(xiàn)

[1]張欣，秦茂玲，謝堂龍.基于特征保持的三角形折疊網(wǎng)格簡(jiǎn)化算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2012，22（1）：94-97.

[2]俞靜.三維復(fù)雜場(chǎng)景優(yōu)化處理的研究與實(shí)現(xiàn)：（碩士學(xué)位論文）[D].成都：西南交通大學(xué)，2011.