吳捷　+唐紅鎖

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

關鍵詞關鍵詞：實時渲染；LOD；半邊折疊

DOIDOI：10.11907/rjdk.1431086

中圖分類號：TP317.4

文獻標識碼：A文章編號

文章編號：16727800（2015）004014503

0引言

實時渲染技術一直是圖形學領域研究的熱點。當需要生成具有真實感的模型時，由于模型本身的復雜性，實時實現往往很難。

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

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

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

1基于半邊折疊的網格簡化算法

1.1算法關鍵問題

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

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

1.2算法核心內容

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

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

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

N（v）=與該頂點相關聯的面的法向量之和[]與該頂點相關聯的面的數量

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

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

頂點尖銳度：對于每個頂點，定義其所關聯的特征邊數量為其尖銳度。

1.3數據結構設計

某些文獻在構造LOD模型時，往往缺乏連續(xù)性，不能逆向恢復。本文因為采用了半邊折疊算法，不會產生新的頂點，所以非常便于設計數據結構來保持模型的連續(xù)性和簡化過程的可逆性。

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

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

2實驗結果及分析

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

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

頂點數較少時，采用本文算法得到的簡化模型在臉部重要

特征的保持上仍然做得較好。圖4是本文算法和Garland算法對牛模型進行簡化的效果比較。可以看出，用Garland算法簡化后的網格分布比較均勻，但模型的重要特征保留不夠明顯，而本文算法對牛的眼睛、鼻孔、耳朵等重要特征保持得更好。表1給出了本文算法和Garland算法的對比數據，采用本文方法進行簡化時，因為采用半邊折疊算法，不需要進行新頂點位置的計算，所以執(zhí)行速度更快。數據顯示：當簡化率為79.4%時，所用的時間為1.32s，而Garland算法需要1.57s，所以本文算法更加有利于LOD模型的構建。

3結語

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

參考文獻參考文獻：

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

[2]薛峰，袁成鳳.保持外形特征的網格簡化算法[J].計算機應用，2010，30（9）：24312433.

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

[4]唐杰，張福炎.一種基于誤差控制的網格多分辨模型生成算法[J].計算機學報，2005，28（9）：15341539.

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

責任編輯（責任編輯：杜能鋼）