高飛

摘 要：本文主要介紹細(xì)節(jié)層次模型的定義和生成方法，重點介紹了場景建模優(yōu)化的主要方法，利用邊折疊法即二次測度誤差的改進(jìn)算法對吉林動畫學(xué)院的校園場景進(jìn)行簡化處理。結(jié)果表明，該方法有效降低了三維場景的復(fù)雜度。

關(guān)鍵詞：多層次細(xì)節(jié)模型 網(wǎng)格簡化 三維場景模型 邊折疊算法

中圖分類號：TP319 文獻(xiàn)標(biāo)識碼：A 文章編號：1674-098X（2017）09（c）-0113-02

隨著計算機(jī)技術(shù)的快速發(fā)展、網(wǎng)絡(luò)的普及、虛擬現(xiàn)實技術(shù)的應(yīng)用和理論研究已經(jīng)成為當(dāng)今信息技術(shù)領(lǐng)域內(nèi)最熱門的研究，在實際應(yīng)用中，大規(guī)模的虛擬現(xiàn)實場景內(nèi)有很多復(fù)雜的模型，由于計算機(jī)硬件和網(wǎng)絡(luò)速度的限制，場景在加載過程中，無法進(jìn)行實時顯示。因此，為了解決這個問題，本文采用邊折疊算法對模型進(jìn)行場景內(nèi)模型優(yōu)化，不僅可提高加載速度，同時也給用戶帶來更好的真實體驗。

1 細(xì)節(jié)層次模型（LOD）

細(xì)節(jié)層次模型是指針對同一個對象模型，利用不同細(xì)節(jié)的描述方法得到一組模型。在實際繪制當(dāng)中，以視點距離對象模型的遠(yuǎn)近為依據(jù)進(jìn)行繪制。當(dāng)距離近時，利用較細(xì)致的LOD模型來繪制；當(dāng)距離較遠(yuǎn)時，便利用粗糙的LOD模型來繪制。在運動物體的場景中，當(dāng)物體移動速度快時，利用粗糙的LOD模型來繪制，當(dāng)物體移動速度較慢或者處于靜止時，利用細(xì)致的LOD模型來繪制。

2 LOD模型的生成

在計算機(jī)圖形學(xué)內(nèi)，多邊形網(wǎng)格經(jīng)常被用來描述場景內(nèi)的對象模型，為物體提供不同層次的LOD模型，可有效控制場景復(fù)雜度及加速圖形繪制速度。而LOD模型通常是由網(wǎng)格簡化算法生成的。所謂網(wǎng)格簡化，就是在保持原網(wǎng)格模型的外觀特征基礎(chǔ)上，通過一些方法，減少頂點數(shù)量，將原始模型用近似模型表示出來。常用的方法是將對模型外觀特征影響不大的或不重要的頂點、三角形或邊從多邊形網(wǎng)格中移走，進(jìn)而簡化模型。簡化過程遵循的原則是：（1）頂點最少原則；（2）誤差最小原則；（3）效率最高原則。

3 幾何元素刪除型算法

該算法主要是對網(wǎng)格模型邊、三角形或者中點的重要性進(jìn)行判斷，將不重要的部分進(jìn)行刪除，再把刪除后的空洞進(jìn)行重新網(wǎng)格化，通過此方法來簡化網(wǎng)格。

該簡化方法主要可分為：近似平面合并型、折疊型和頂點刪除型。三角形算法和邊折疊算法是折疊型算法的主要兩種基本算法，主要思想是對網(wǎng)格中的三角形或者邊進(jìn)行折疊誤差計算，選擇折疊誤差小的三角形或者邊進(jìn)行折疊，生成新的頂點后，把與之有關(guān)聯(lián)的點進(jìn)行連接，然后將折疊區(qū)域重新網(wǎng)格化。邊折疊算法的過程如圖1所示。

邊折疊算法也稱二次誤差測度算法（Quadric Error Metric，QEM），不僅運行速度快、內(nèi)存消耗小，算法計算簡單且簡化后的網(wǎng)格與模型具有非常高的整體相似度。本文將原來的二次誤差測度算法（QEM）進(jìn)行改進(jìn)，利用改進(jìn)的QEM算法對場景建模進(jìn)行優(yōu)化處理。

4 改進(jìn)的二次誤差測度算法（QEM）

具體步驟如下。

（1）讀入原始網(wǎng)格數(shù)據(jù)，其中包含網(wǎng)格內(nèi)的頂點坐標(biāo)和與其連接的三角面片的頂點、序列等數(shù)據(jù)信息。

（2）求出網(wǎng)格內(nèi)各個頂點的離散曲率K（v）由式得出和局部區(qū)域面積LRA（v），將這兩個加權(quán)因子與矩陣Q（v）進(jìn)行加權(quán)，得到網(wǎng)格內(nèi)每個頂點的二次誤差矩陣Q'（v）：

式中，K（Lv）為包含頂點v的邊的高斯曲率，Kv為頂點v的高斯曲率。

Kv的表達(dá)式為：

式中，為頂點v的鄰接夾角；n為與頂點v相關(guān)聯(lián)的三角形數(shù)目；（v）為頂點v的鄰接三角網(wǎng)格面積之和，即局部區(qū)域面積（LRA）。

二次誤差矩陣表達(dá)式為：

（3）通過輸入適當(dāng)?shù)暮线m的閾值w=0.9，判斷是否為邊界，若為邊界，則設(shè)置。

（4）根據(jù)步驟2得到每個頂點的二次誤差矩陣Q（v），從而計算得出每條邊的收縮代價c，若（v1，v2）→收縮代價表達(dá)式為：

將其放入堆棧中，c值越大，在棧中的位置越靠后，反之，越靠前。

（5）從堆棧中取出收縮代價最小的邊進(jìn)行收縮操作，即棧頂，同時更新網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)，對新的邊折疊代價進(jìn)行計算并且更新堆棧序列。

（6）如果達(dá)到理想簡化要求，則算法結(jié)束，否則繼續(xù)重復(fù)上述過程，直到滿足簡化要求。

5 實驗結(jié)果

通過邊折疊法對場景內(nèi)的模型進(jìn)行優(yōu)化處理，優(yōu)化后的場景不僅具有原有的特征，同時降低了場景復(fù)雜度，提高了加載速度（見圖2、圖3）。

參考文獻(xiàn)

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

[2] 俞靜.三維復(fù)雜場景優(yōu)化處理的研究與實現(xiàn)[D].成都：西南交通大學(xué)，2011.endprint