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

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

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

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

4、持模型的二維流形性的漸進(jìn)層次細(xì)節(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)只支持二維流形體的表示，能夠完整地表示多面體的頂點(diǎn)、邊、

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

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

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

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

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

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