高飛
摘 要:本文主要介紹細(xì)節(jié)層次模型的定義和生成方法,重點(diǎn)介紹了場景建模優(yōu)化的主要方法,利用邊折疊法即二次測度誤差的改進(jìn)算法對吉林動(dòng)畫學(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ì)算機(jī)技術(shù)的快速發(fā)展、網(wǎng)絡(luò)的普及、虛擬現(xiàn)實(shí)技術(shù)的應(yīng)用和理論研究已經(jīng)成為當(dāng)今信息技術(shù)領(lǐng)域內(nèi)最熱門的研究,在實(shí)際應(yīng)用中,大規(guī)模的虛擬現(xiàn)實(shí)場景內(nèi)有很多復(fù)雜的模型,由于計(jì)算機(jī)硬件和網(wǎng)絡(luò)速度的限制,場景在加載過程中,無法進(jìn)行實(shí)時(shí)顯示。因此,為了解決這個(gè)問題,本文采用邊折疊算法對模型進(jìn)行場景內(nèi)模型優(yōu)化,不僅可提高加載速度,同時(shí)也給用戶帶來更好的真實(shí)體驗(yàn)。
1 細(xì)節(jié)層次模型(LOD)
細(xì)節(jié)層次模型是指針對同一個(gè)對象模型,利用不同細(xì)節(jié)的描述方法得到一組模型。在實(shí)際繪制當(dāng)中,以視點(diǎn)距離對象模型的遠(yuǎn)近為依據(jù)進(jìn)行繪制。當(dāng)距離近時(shí),利用較細(xì)致的LOD模型來繪制;當(dāng)距離較遠(yuǎn)時(shí),便利用粗糙的LOD模型來繪制。在運(yùn)動(dòng)物體的場景中,當(dāng)物體移動(dòng)速度快時(shí),利用粗糙的LOD模型來繪制,當(dāng)物體移動(dòng)速度較慢或者處于靜止時(shí),利用細(xì)致的LOD模型來繪制。
2 LOD模型的生成
在計(jì)算機(jī)圖形學(xué)內(nèi),多邊形網(wǎng)格經(jīng)常被用來描述場景內(nèi)的對象模型,為物體提供不同層次的LOD模型,可有效控制場景復(fù)雜度及加速圖形繪制速度。而LOD模型通常是由網(wǎng)格簡化算法生成的。所謂網(wǎng)格簡化,就是在保持原網(wǎng)格模型的外觀特征基礎(chǔ)上,通過一些方法,減少頂點(diǎn)數(shù)量,將原始模型用近似模型表示出來。常用的方法是將對模型外觀特征影響不大的或不重要的頂點(diǎn)、三角形或邊從多邊形網(wǎng)格中移走,進(jìn)而簡化模型。簡化過程遵循的原則是:(1)頂點(diǎn)最少原則;(2)誤差最小原則;(3)效率最高原則。
3 幾何元素刪除型算法
該算法主要是對網(wǎng)格模型邊、三角形或者中點(diǎn)的重要性進(jìn)行判斷,將不重要的部分進(jìn)行刪除,再把刪除后的空洞進(jìn)行重新網(wǎng)格化,通過此方法來簡化網(wǎng)格。
該簡化方法主要可分為:近似平面合并型、折疊型和頂點(diǎn)刪除型。三角形算法和邊折疊算法是折疊型算法的主要兩種基本算法,主要思想是對網(wǎng)格中的三角形或者邊進(jìn)行折疊誤差計(jì)算,選擇折疊誤差小的三角形或者邊進(jìn)行折疊,生成新的頂點(diǎn)后,把與之有關(guān)聯(lián)的點(diǎn)進(jìn)行連接,然后將折疊區(qū)域重新網(wǎng)格化。邊折疊算法的過程如圖1所示。
邊折疊算法也稱二次誤差測度算法(Quadric Error Metric,QEM),不僅運(yùn)行速度快、內(nèi)存消耗小,算法計(jì)算簡單且簡化后的網(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)的頂點(diǎn)坐標(biāo)和與其連接的三角面片的頂點(diǎn)、序列等數(shù)據(jù)信息。
(2)求出網(wǎng)格內(nèi)各個(gè)頂點(diǎn)的離散曲率K(v)由式得出和局部區(qū)域面積LRA(v),將這兩個(gè)加權(quán)因子與矩陣Q(v)進(jìn)行加權(quán),得到網(wǎng)格內(nèi)每個(gè)頂點(diǎn)的二次誤差矩陣Q'(v):
式中,K(Lv)為包含頂點(diǎn)v的邊的高斯曲率,Kv為頂點(diǎn)v的高斯曲率。
Kv的表達(dá)式為:
式中,為頂點(diǎn)v的鄰接夾角;n為與頂點(diǎn)v相關(guān)聯(lián)的三角形數(shù)目;(v)為頂點(diǎn)v的鄰接三角網(wǎng)格面積之和,即局部區(qū)域面積(LRA)。
二次誤差矩陣表達(dá)式為:
(3)通過輸入適當(dāng)?shù)暮线m的閾值w=0.9,判斷是否為邊界,若為邊界,則設(shè)置。
(4)根據(jù)步驟2得到每個(gè)頂點(diǎn)的二次誤差矩陣Q(v),從而計(jì)算得出每條邊的收縮代價(jià)c,若(v1,v2)→收縮代價(jià)表達(dá)式為:
將其放入堆棧中,c值越大,在棧中的位置越靠后,反之,越靠前。
(5)從堆棧中取出收縮代價(jià)最小的邊進(jìn)行收縮操作,即棧頂,同時(shí)更新網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu),對新的邊折疊代價(jià)進(jìn)行計(jì)算并且更新堆棧序列。
(6)如果達(dá)到理想簡化要求,則算法結(jié)束,否則繼續(xù)重復(fù)上述過程,直到滿足簡化要求。
5 實(shí)驗(yàn)結(jié)果
通過邊折疊法對場景內(nèi)的模型進(jìn)行優(yōu)化處理,優(yōu)化后的場景不僅具有原有的特征,同時(shí)降低了場景復(fù)雜度,提高了加載速度(見圖2、圖3)。
參考文獻(xiàn)
[1] 張欣,秦茂玲,謝堂龍.基于特征保持的三角形折疊網(wǎng)格簡化算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2012,22(1):94-97.
[2] 俞靜.三維復(fù)雜場景優(yōu)化處理的研究與實(shí)現(xiàn)[D].成都:西南交通大學(xué),2011.endprint