基于圖形旋轉(zhuǎn)系統(tǒng)的漸進層次細節(jié)方法研究.pdf

1、層次細節(jié)(Levels of Detail，LOD)方法是一種全新的模型表示方法，改變了傳統(tǒng)的“圖形質(zhì)量越精細越好"的觀點，在實時圖象通信、碰撞檢測、限時圖形繪制、交互式可視化和虛擬現(xiàn)實等領(lǐng)域有廣泛的應(yīng)用。層次細節(jié)方法通過建立原始精細模型的多個近似簡化模型，表示原始模型不同程度的細節(jié)，使得圖形繪制系統(tǒng)可以在不同情況下針對待繪制景物的重要度、對繪制時間的實時性要求等因素，選用或重建適當(dāng)?shù)膶哟渭毠?jié)模型，快速、有效的對復(fù)雜場景進行繪制，在保證

2、實時圖形顯示的前提下，最大程度地提高視覺效果。漸進層次細節(jié)方法是連續(xù)分辨率的表示法，圖形可以逐漸地變化，網(wǎng)格的形狀不會出現(xiàn)突然的變化。 拓撲簡化通過改變模型的拓撲來對網(wǎng)格進行簡化，能夠?qū)⑷我饩W(wǎng)格逐漸簡化至一個最簡單的虧格為0的表面(稱為四面體)。在層次細節(jié)方法中應(yīng)用拓撲簡化，能夠?qū)喕^程進行優(yōu)化，產(chǎn)生更好的簡化效果。目前還沒有一種漸進層次細節(jié)方法能夠進行拓撲簡化。 現(xiàn)有的層次細節(jié)方法不能一直保持模型的二維流形性。在計算

3、機圖形學(xué)中，如何保持模型的二維流形性是一個基礎(chǔ)性的重要課題。許多在計算機圖形學(xué)中常用的算法都要求或假設(shè)被操作的模型是二維流形的，比如細分(subdivision)操作，就要求網(wǎng)格必須是一個有效的二維流形體。如果模型是非二維流形體，這些算法或者不能處理，或者采取特例的方式來處理，但算法往往會變得非常復(fù)雜。在層次細節(jié)的運算中，如果不能保證模型的二維流形性，一些意想不到的奇異體就會出現(xiàn)。 本文研究并提出了一種能夠進行拓撲簡化，并一直保

4、持模型的二維流形性的漸進層次細節(jié)方法，主要取得了以下創(chuàng)新性成果： 1．提出了一種新的基于圖形旋轉(zhuǎn)系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)——雙鏈接旋轉(zhuǎn)系統(tǒng)(Doubly Linked Rotation System，DLRS)數(shù)據(jù)結(jié)構(gòu)，并在DLRS數(shù)據(jù)結(jié)構(gòu)上構(gòu)造了一種完備(Complete)的和健全(Sound)的操作集合。大多數(shù)現(xiàn)有的數(shù)據(jù)結(jié)構(gòu)不能一直保持模型的二維流形性。本文提出的DLRS數(shù)據(jù)結(jié)構(gòu)只支持二維流形體的表示，能夠完整地表示多面體的頂點、邊、

5、面之間的所有9種拓撲關(guān)系，是一種完全拓撲關(guān)系表達的數(shù)據(jù)結(jié)構(gòu)。本文提出的DLRS數(shù)據(jù)結(jié)構(gòu)上的操作集合是完備的和健全的，完備的是指任何一個二維流形體都可以通過該操作集合中的一系列操作來生成，健全的是指一個二維流形體如果使用該操作集合中的任何一個操作都仍然保持著二維流形性。因此，采用DLRS數(shù)據(jù)結(jié)構(gòu)表示網(wǎng)格模型，并只采用其操作集合中的操作來對模型進行操作，就可以保證模型始終是二維流形的。與雙鏈接面列表(DLFL)相比，DLRS結(jié)構(gòu)更為簡單直觀

6、，算法實現(xiàn)簡單，與圖形鄰接表和雙鏈接邊列表(DCEL)相比，DLRS效率更高。并且，一個圖的DLRS數(shù)據(jù)結(jié)構(gòu)表示與其DLFL和DCEL數(shù)據(jù)結(jié)構(gòu)表示能夠在線性時間內(nèi)互相轉(zhuǎn)化。 2．提出了一種新的漸進層次細節(jié)方法——基于圖形旋轉(zhuǎn)系統(tǒng)的漸進層次細節(jié)方法(Progressive LOD based on Graph Rotation System，PLG 方法)。PLG 方法能夠進行拓撲簡化，并且保持模型的二維流形性。PLG方法采用漸進

7、方式，圖形可以逐漸地變化，是一種無損的方法。PLG方法采用本文提出的DLRS數(shù)據(jù)結(jié)構(gòu)表示模型，以基網(wǎng)格和操作序列的形式表示及存儲層次細節(jié)。PLG方法分為兩個部分，一個部分用于生成層次細節(jié)，是一個離線的前處理過程，另一個部分在線使用層次細節(jié)，是一個實時繪制過程。生成層次細節(jié)過程的操作分為兩個層次：直接操作層次和間接操作層次。直接操作層次的操作是DLRS數(shù)據(jù)結(jié)構(gòu)操作集合里的操作，在前處理過程中得到的操作序列就是這些操作。間接操作層次的操作分

8、為兩類，一類是不改變拓撲的操作，另一類是拓撲改變操作。PLG方法支持三角形網(wǎng)格和多邊形網(wǎng)格，支持多種誤差估計方法。 3．提出了基于圖形旋轉(zhuǎn)系統(tǒng)的邊收縮(Edge Collapse)操作、頂點刪除(Vertex Decimation)操作、 CutTunnel/CreateTunnel 操作和PCreateTunnel/PCutTunnel 操作，這 6 種操作都能夠保持模型的二維流形性?；趫D形旋轉(zhuǎn)系統(tǒng)的邊收縮操作和頂點刪除操作

9、是PLG方法間接操作層次的不改變拓撲的操作。CutTunnel/CreateTunnel操作和PCutTunnel/PCreateTunnel操作是拓撲改變操作。CutTunnel操作能夠切斷一根復(fù)雜的柄，也可以封閉一個洞，CreateTunnel是其逆操作。這兩個操作使用方便，執(zhí)行速度快。PCutTunnel操作用一個平面切斷一根柄，在切斷柄處的模型視覺上不會發(fā)生變化，操作效果好，PCreateTunnel操作是其逆操作。PCutTu

10、nnel/PCreateTunnel操作解決了CutTunnel/CreateTunnel操作對模型外觀改變較大的問題。 4．采用本文提出的DLRS數(shù)據(jù)結(jié)構(gòu)、PLG方法和基于圖形旋轉(zhuǎn)系統(tǒng)的邊收縮操作、頂點刪除操作、CutTunnel/CreateTunnel操作和PCutTunnel/PCreateTunnel操作，對Stanford大學(xué)的cow、bone、bunny、dragon和buddhaf模型進行了實驗，實驗?zāi)Ｐ瓦\行速度