吳捷　+唐紅鎖

摘要摘要：實(shí)時(shí)渲染技術(shù)一直是圖形學(xué)中的熱點(diǎn)問題，大量模型數(shù)據(jù)給實(shí)時(shí)渲染帶來了極大的挑戰(zhàn)。作為一種有效的控制模型精度方法，LOD算法近年來得到了廣泛重視，但已有算法在計(jì)算復(fù)雜度和保持外形特征等方面兼顧不周。針對此問題，提出了一種基于半邊折疊的LOD模型構(gòu)造方法，在空間距離計(jì)算、尖銳特征保持、光照效果等幾方面進(jìn)行了改進(jìn)。實(shí)驗(yàn)結(jié)果表明，該算法能較好地保持模型的外形特征，實(shí)現(xiàn)起來快速有效。

關(guān)鍵詞關(guān)鍵詞：實(shí)時(shí)渲染；LOD；半邊折疊

DOIDOI：10.11907/rjdk.1431086

中圖分類號(hào)：TP317.4

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)

文章編號(hào)：16727800（2015）004014503

0引言

實(shí)時(shí)渲染技術(shù)一直是圖形學(xué)領(lǐng)域研究的熱點(diǎn)。當(dāng)需要生成具有真實(shí)感的模型時(shí)，由于模型本身的復(fù)雜性，實(shí)時(shí)實(shí)現(xiàn)往往很難。

所謂LOD技術(shù)，就是針對每個(gè)物體建立多個(gè)簡化模型，各個(gè)模型的簡化率互不相同。根據(jù)物體在屏幕上所占

區(qū)域的大小及距離用戶遠(yuǎn)近等視覺因素，為各物體選擇不同的簡化模型，從而減少實(shí)際顯示所需的數(shù)據(jù)量。由于網(wǎng)格特征的復(fù)雜性與多樣性，通常采用海量的三角網(wǎng)格對模型進(jìn)行描述，因而LOD模型生成就轉(zhuǎn)化為三角網(wǎng)格的簡化問題，即把一個(gè)復(fù)雜三角網(wǎng)格表示的模型用一系列簡化的模型表示，簡化模型保持了原模型的基本特征，但頂點(diǎn)數(shù)目少于原網(wǎng)格的頂點(diǎn)數(shù)目。

三角網(wǎng)格簡化的方法較多，主要有基于頂點(diǎn)刪除的簡化算法、重新劃分網(wǎng)格的簡化算法、小波分解的簡化算法、邊折疊的簡化算法等等。近年來國內(nèi)有很多關(guān)于網(wǎng)格簡化的研究成果。其中文獻(xiàn)[1]基于頂點(diǎn)聚類提出了新的網(wǎng)格簡化算法，實(shí)現(xiàn)快速，但是簡化結(jié)果誤差較大，對于尖銳特征比較明顯的模型，簡化效果欠缺；文獻(xiàn)[2]基于邊折疊，設(shè)計(jì)了一種保持外形特征的網(wǎng)格簡化算法，但是未能有效處理邊界點(diǎn)和邊界三角形。本文基于半邊折疊提出了一種新的網(wǎng)格簡化算法，并以此算法為基礎(chǔ)設(shè)計(jì)了LOD模型的構(gòu)造方法。

1基于半邊折疊的網(wǎng)格簡化算法

1.1算法關(guān)鍵問題

本文對傳統(tǒng)的邊折疊算法進(jìn)行了改進(jìn)，采用半邊折疊。作為邊折疊算法的特例，半邊折疊的簡化流程和邊折疊是一致的，一次半邊折疊移去一個(gè)頂點(diǎn)和兩個(gè)面。不同之處在于，半邊折疊不產(chǎn)生新的頂點(diǎn)，而是將待折疊的邊uv折疊到其中的一個(gè)頂點(diǎn)v 上，頂點(diǎn)u 被頂點(diǎn)v 所代替（如圖1），這樣就減少了內(nèi)存占用，且不必像文獻(xiàn)[3]那樣為了計(jì)算新頂點(diǎn)的位置而進(jìn)行復(fù)雜計(jì)算，有利于渲染系統(tǒng)構(gòu)建可以直接處理的數(shù)據(jù)結(jié)構(gòu)，提高渲染效率。

（u→v）與（v→u）是兩個(gè)不同的刪除操作，需要分別計(jì)算半邊折疊的代價(jià)，在簡化隊(duì)列中對半邊折疊代價(jià)進(jìn)行排序。本文算法的關(guān)鍵問題就在于如何確定半邊折疊順序，也就是頂點(diǎn)的先后刪除順序。

1.2算法核心內(nèi)容

為了確定頂點(diǎn)的先后刪除順序，本文引入了頂點(diǎn)“價(jià)值”概念：計(jì)算每個(gè)頂點(diǎn)的“價(jià)值”，并放入網(wǎng)格簡化隊(duì)列中。在進(jìn)行簡化時(shí)，價(jià)值越低的點(diǎn)先出隊(duì)并被刪除，然后更新隊(duì)列中受影響的頂點(diǎn)信息，再對隊(duì)列重新排序。本文給出的頂點(diǎn)價(jià)值計(jì)算公式為：Cost（v）=αD（v）+βN（v）+γC（v），其中D（v）為空間距離值，N（v）為頂點(diǎn)法矢值，C（v）為頂點(diǎn)尖銳度，α，β，γ為用戶設(shè)定參數(shù)。

空間距離值計(jì)算。Garland在1997年提出了二次誤差測度（QEM）概念，以新頂點(diǎn)到被折疊邊的兩個(gè)頂點(diǎn)相關(guān)聯(lián)平面的距離平方和作為誤差測度，取得了較好的簡化效果。近年來很多學(xué)者的研究都是基于Garland的算法進(jìn)行改進(jìn)；對QEM算法進(jìn)行研究發(fā)現(xiàn)，QEM計(jì)算的是點(diǎn)到三角網(wǎng)格所在平面的垂直距離，而不是點(diǎn)到三角面的實(shí)際距離[4]。本文以頂點(diǎn)到三角面的實(shí)際距離之和作為誤差的基本控制手段。下面給出點(diǎn)到三角面實(shí)際空間距離的計(jì)算過程：

（2）頂點(diǎn)法矢值計(jì)算。在實(shí)時(shí)渲染中往往會(huì)大量運(yùn)用光照，而由三維顯示原理可知， 在光照模型中，物體頂點(diǎn)和面的法向變化對視覺的影響很大。所以本文在頂點(diǎn)價(jià)值計(jì)算中加入了法矢值，本文設(shè)置的頂點(diǎn)法矢值N（v）計(jì)算公式為：

N（v）=與該頂點(diǎn)相關(guān)聯(lián)的面的法向量之和[]與該頂點(diǎn)相關(guān)聯(lián)的面的數(shù)量

（3）頂點(diǎn)尖銳度計(jì)算。很多簡化算法在處理時(shí)往往忽略了模型的尖銳特征，為了保持模型重要的細(xì)節(jié)特征，本文引入特征邊和頂點(diǎn)尖銳度概念。

特征邊：預(yù)先設(shè)定閾值θ，對于某一邊，若與該邊相連的兩個(gè)面的外法線夾角大于θ，則記該邊為特征邊。在有邊界的模型中，邊界邊也視為特征邊。

頂點(diǎn)尖銳度：對于每個(gè)頂點(diǎn)，定義其所關(guān)聯(lián)的特征邊數(shù)量為其尖銳度。

1.3數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

某些文獻(xiàn)在構(gòu)造LOD模型時(shí)，往往缺乏連續(xù)性，不能逆向恢復(fù)。本文因?yàn)椴捎昧税脒呎郫B算法，不會(huì)產(chǎn)生新的頂點(diǎn)，所以非常便于設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)來保持模型的連續(xù)性和簡化過程的可逆性。

本文進(jìn)行數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)時(shí)主要定義了兩個(gè)類：頂點(diǎn)類和三角面類。在三角面類中定義了該面所包含的頂點(diǎn)信息和法向量，在頂點(diǎn)類中定義了該頂點(diǎn)的坐標(biāo)、編號(hào)、尖銳度、相鄰頂點(diǎn)、頂點(diǎn)價(jià)值等信息。有了這些信息，就可以對模型進(jìn)行逆向恢復(fù)。比如當(dāng)折疊一條邊uv時(shí)，可以用類似map[v→id] = u→id這樣的語句來保存簡化記錄；當(dāng)需要對模型逆向恢復(fù)時(shí)，只需要依次調(diào)出記錄即可，非常適合LOD模型的構(gòu)建。

基于半邊折疊的簡化算法主要步驟：①讀入外部數(shù)據(jù)文件，設(shè)計(jì)結(jié)構(gòu)組織數(shù)據(jù)，用戶輸入簡化率、閾值θ及模型簡化參數(shù)α，β，γ；②計(jì)算每個(gè)頂點(diǎn)的空間距離值、頂點(diǎn)法矢值及頂點(diǎn)尖銳度，得到各個(gè)頂點(diǎn)的價(jià)值，并在簡化隊(duì)列中進(jìn)行排序；③按照簡化率要求刪除價(jià)值小的頂點(diǎn)，更新隊(duì)列，直至達(dá)到簡化要求。

2實(shí)驗(yàn)結(jié)果及分析

對Stan Melax[5]系統(tǒng)進(jìn)行一些改進(jìn)，可以非常方便地實(shí)現(xiàn)本文算法。本文選擇VC++和OpenGL作為三維開發(fā)工具，硬件配置是奔騰IV 3.0GHZ處理器，1G內(nèi)存，操作系統(tǒng)軟件是Windows XP（32位）。

圖3是采用本文算法對人頭模型進(jìn)行簡化的演進(jìn)圖。初始模型有6736個(gè)頂點(diǎn)，從圖3中可以看出，即使在

頂點(diǎn)數(shù)較少時(shí)，采用本文算法得到的簡化模型在臉部重要

特征的保持上仍然做得較好。圖4是本文算法和Garland算法對牛模型進(jìn)行簡化的效果比較?？梢钥闯?，用Garland算法簡化后的網(wǎng)格分布比較均勻，但模型的重要特征保留不夠明顯，而本文算法對牛的眼睛、鼻孔、耳朵等重要特征保持得更好。表1給出了本文算法和Garland算法的對比數(shù)據(jù)，采用本文方法進(jìn)行簡化時(shí)，因?yàn)椴捎冒脒呎郫B算法，不需要進(jìn)行新頂點(diǎn)位置的計(jì)算，所以執(zhí)行速度更快。數(shù)據(jù)顯示：當(dāng)簡化率為79.4%時(shí)，所用的時(shí)間為1.32s，而Garland算法需要1.57s，所以本文算法更加有利于LOD模型的構(gòu)建。

3結(jié)語

本文基于半邊折疊算法，提出了一種新的LOD模型生成方法，與其它網(wǎng)格簡化算法相比，本文算法在空間距離計(jì)算和尖銳特征保持等方面作了一些改進(jìn)。實(shí)驗(yàn)表明，該算法在網(wǎng)格數(shù)較少時(shí)能較好地保持模型的基本外形特征，并且實(shí)現(xiàn)快捷有效。

參考文獻(xiàn)參考文獻(xiàn)：

[1]吳有用， 萬旺根， 金龍存， 等. 一種新的連續(xù)性LOD實(shí)現(xiàn)算法[J]. 微電子學(xué)與計(jì)算機(jī)，2010，27（6）：185187.

[2]薛峰，袁成鳳.保持外形特征的網(wǎng)格簡化算法[J].計(jì)算機(jī)應(yīng)用，2010，30（9）：24312433.

[3]裴艷云，陳飛翔.一種基于不平滑度的網(wǎng)格簡化算法[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（14）：174177.

[4]唐杰，張福炎.一種基于誤差控制的網(wǎng)格多分辨模型生成算法[J].計(jì)算機(jī)學(xué)報(bào)，2005，28（9）：15341539.

[5]STAN MELAX. A simple， fast， and effective polygon reduction algorithm[J].Game Developer， 1998（11）：4449.

責(zé)任編輯（責(zé)任編輯：杜能鋼）