高飛

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

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

中圖分類號：TP319 文獻標識碼：A 文章編號：1007-9416（2016）09-0117-02

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

1 網(wǎng)格簡化

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

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

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

通過計算網(wǎng)格中每個頂點的誤差矩陣，即用二次誤差測度來測量邊的折疊代價，然后再選取一些有效的頂點對進行邊折疊操作。具體步驟如下：

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

為新頂點的二次誤差測度矩陣。

（2）有效頂點對選擇。

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

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

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

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

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

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

（b）不構(gòu)成邊的頂點對合并形式。當兩個頂點不構(gòu)成邊的情況下，且滿足||V1，V2||t，將這兩個頂點進行合并。

（3）新頂點計算。

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

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

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

2 結(jié)果

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

參考文獻

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

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