二維流形圖形建模系統(tǒng)完備操作集研究

2014-08-08 14:22:04費(fèi)耀平陳建二陳松喬李敏

湖南大學(xué)學(xué)報(bào)·自然科學(xué)版 2014年5期

費(fèi)耀平+陳建二+陳松喬+李敏

文章編號：16742974(2014)05011807

收稿日期：20131101

基金項(xiàng)目：新世紀(jì)優(yōu)秀人才支持計(jì)劃資助項(xiàng)目(NCET120547)

作者簡介：費(fèi)耀平（1959-），男，河北平山人，中南大學(xué)教授

通訊聯(lián)系人，Email:limin@mail.csu.edu.cn

摘要：針對目前大多數(shù)二維流形建模系統(tǒng)不能保證二維流形結(jié)構(gòu)的問題，如歐拉操作會產(chǎn)生非二維流形網(wǎng)格結(jié)構(gòu)，通過對基于網(wǎng)格結(jié)構(gòu)的二維流形建模系統(tǒng)中的各種數(shù)據(jù)結(jié)構(gòu)及非流形和流形結(jié)構(gòu)的研究，提出了一套新的基于圖形旋轉(zhuǎn)系統(tǒng)的完備的網(wǎng)格建模操作.與現(xiàn)有二維流形建模系統(tǒng)中的數(shù)據(jù)結(jié)構(gòu)和網(wǎng)格建模操作相比，新提出的數(shù)據(jù)結(jié)構(gòu)和網(wǎng)格建模操作更加直觀有效并更方便用戶使用.

關(guān)鍵詞：歐拉操作;圖形建模;二維流形;網(wǎng)格結(jié)構(gòu)

中圖分類號：TP 301 文獻(xiàn)標(biāo)識碼：A

Research on the Complete Operation Set

of Modeling 2Manifold Mesh



FEI Yaoping, CHEN Jianer, CHEN Songqiao, LI Min

(School of Information Science and Engineering, Central South Univ, Changsha，Hunan 410083, China)

Abstract:Most current modeling systems do not guarantee the 2manifold structures and may generate nonmanifold structures. In this paper, a new vertexbased representation for mesh structures was proposed, and a formal proofwas given to show that this representation characterizes precisely 2manifold structures. It has been shown that the new proposed mesh modeling operations are more intuitive, more efficient, and more userfriendly, compared with previously proposed methods in related literatures.

Key words:Euler operation; shape modeling; 2manifold; meshstructure



網(wǎng)格是計(jì)算機(jī)圖形學(xué)中最常用的結(jié)構(gòu)[1-2].具有簡單有效的用戶接口的二維流形建模系統(tǒng)是計(jì)算機(jī)圖形學(xué)與計(jì)算機(jī)輔助設(shè)計(jì)中的重要問題.現(xiàn)有的二維流形建模在處理非流形結(jié)構(gòu)時(shí)，通常會使建模算法變得非常復(fù)雜[1,3].另外，一些廣泛使用的建模操作如細(xì)分算法需要更有效的二維流形結(jié)構(gòu),否則細(xì)分操作執(zhí)行在非二維流形結(jié)構(gòu)上時(shí)，這些建模系統(tǒng)如Maya可能無法正常工作. 

理論上說，一個(gè)二維流形的網(wǎng)格結(jié)構(gòu)由3個(gè)主要部分組成：頂點(diǎn)集、邊集、和面集以及這些部分間的9種鄰接關(guān)系[4].描述網(wǎng)格結(jié)構(gòu)已有許多數(shù)據(jù)結(jié)構(gòu)，一些數(shù)據(jù)結(jié)構(gòu)是基于面集的[5-6]，另一些是基于邊集的.最有名的基于邊集的表示是Baumgart提出的翼型邊結(jié)構(gòu)(wingededges structure)[7]及其以后的許多翼型邊結(jié)構(gòu)的變種[8-9].這些數(shù)據(jù)結(jié)構(gòu)可以用來描述網(wǎng)格在二維流形上的嵌入，也可以用來描述網(wǎng)格在非二維流形上的嵌入.

另一個(gè)重要問題是應(yīng)用在網(wǎng)格結(jié)構(gòu)上的操作集.如果操作集中每一個(gè)操作作用于一個(gè)二維流形上都產(chǎn)生一個(gè)有效的二維流形并且每個(gè)二維流形都能由操作集中的操作產(chǎn)生，則我們稱這一操作集是一個(gè)完備操作集.例如，在實(shí)體建模中，應(yīng)用最多的是集合操作，但集合操作可能產(chǎn)生非二維流形結(jié)構(gòu)[1].因此，集合操作不是一個(gè)完備操作集.

Mantyla[2]研究了歐拉操作并證明它們對二維流形建模形成一個(gè)完備操作集.Guibas and Stolfi[10]在四方邊結(jié)構(gòu)的基礎(chǔ)上提出了接合(splice)操作.并證明這一操作也形成一個(gè)完備操作集.另外還有其他對這個(gè)方向的研究[1-2].

一些學(xué)者提出了用于評價(jià)二維流形網(wǎng)格建模方案的質(zhì)量準(zhǔn)則[1-2]，包括：有效性（結(jié)構(gòu)能否有效表示所有二維流形結(jié)構(gòu)），完備性（網(wǎng)格建模操作集是否是一個(gè)完備操作集），簡單性（結(jié)構(gòu)與操作是否簡單直觀）和效率性（結(jié)構(gòu)與操作是否有高效率的數(shù)據(jù)結(jié)構(gòu)和算法）.

本文將進(jìn)一步研究網(wǎng)格結(jié)構(gòu)建模方面的上述標(biāo)準(zhǔn)，并提出一套新的網(wǎng)格結(jié)構(gòu)建模操作集，證明其形成一套二維流形網(wǎng)格建模的完備操作集.與現(xiàn)有二維流形建模系統(tǒng)相比，新提出的數(shù)據(jù)結(jié)構(gòu)和網(wǎng)格建模操作更加直觀有效并更方便用戶使用.

1 二維流形的翼形邊結(jié)構(gòu)和DLFL結(jié)構(gòu)

一個(gè)二維流形是一個(gè)拓?fù)淇臻g，其中每個(gè)點(diǎn)都有一個(gè)鄰域與開單位圓同胚.一個(gè)二維流形如果不包含一個(gè)墨比策帶，則這一二維流形稱為定向的.本文假定討論中所有的二維流形都是定向的.一個(gè)連通的二維流形稱為一個(gè)曲面.因此，一個(gè)二維流形是多個(gè)不相交的曲面的并集.根據(jù)歐拉特征定理[11]，每個(gè)曲面同胚于有0個(gè)或多個(gè)柄的球面S.球面S擁有的柄數(shù)稱為曲面的虧格.一個(gè)二維流形的虧格是其曲面虧格的和.

一個(gè)二維流形S上的網(wǎng)格G指相應(yīng)二維流形S上圖G的嵌入，即從圖G到二維流形S的一個(gè)一對一的連續(xù)映射ρ.圖G不一定要連通，也允許同一頂點(diǎn)對之間有多條邊以及一個(gè)頂點(diǎn)為同一邊的兩個(gè)端點(diǎn).如果每個(gè)Sρ(G)的局部最大連通子空間都同胚于開單位圓，則稱此網(wǎng)格G為一正常嵌入網(wǎng)格.本文只考慮正常嵌入網(wǎng)格.每個(gè)Sρ(G) 局部最大連通子空間加上圖G中包圍此子空間的邊稱為網(wǎng)格的一個(gè)面.對于一個(gè)虧格為g的二維流形上的網(wǎng)格G，假定曲面數(shù)目、頂點(diǎn)數(shù)目、邊的數(shù)目、與面的數(shù)目分別為d, v, e, f，則著名的歐拉龐加萊定理可由這些參數(shù)表示如下：

v-e+f= 2(d-g)

令G為二維流形S上的一個(gè)網(wǎng)格.G中的每個(gè)頂點(diǎn)v在S上有一個(gè)同胚于開單位圓的鄰域N.相交于頂點(diǎn)v的邊在N中有一個(gè)循環(huán)排列順序（按逆時(shí)針順序排列）.這一順序?qū)Ρ硎疽粋€(gè)二維流形網(wǎng)格非常重要.Baumgart提出的經(jīng)典翼型邊結(jié)構(gòu)[7,12]本質(zhì)上來說是基于此形式上. 翼型邊結(jié)構(gòu)的主要單元是邊結(jié)點(diǎn).每個(gè)邊結(jié)點(diǎn)由9個(gè)單元組成：（name, vs, ve, fcw, fccw, ncw, pcw, nccw, pccw），name是邊的名字；vs與ve是邊的起始與結(jié)束端點(diǎn)（也就為邊指定了一個(gè)方向）；fcw與fccw表示當(dāng)沿著邊的方向行走時(shí)邊的左邊和右邊的面的名字；ncw與pccw分別為面fcw和面fccw中的下條邊，而pcw 與nccw分別為當(dāng)逆著邊的方向行走時(shí)面fcw和面fccw中的下條邊.如圖1所示．



圖1 翼型邊結(jié)構(gòu)中一個(gè)邊結(jié)點(diǎn)的9個(gè)單元

Fig.1 A edge node in the wingededge structure



Guibus與Stolfi[10]研究四方邊結(jié)構(gòu)時(shí)定義了網(wǎng)格中邊的代數(shù)式與其對偶式.每條邊給定一個(gè)確定方向，從而確定了邊的左面和右面.由此，每條邊有4個(gè)不同的方向，并且有4種屬性：兩個(gè)端點(diǎn)Org與Dest（等價(jià)于翼型邊結(jié)構(gòu)中的vs與ve），二維流形上邊的兩側(cè)上的左邊面與右邊面（等價(jià)于翼型邊結(jié)構(gòu)中的fcw與fccw）.在定向的有向邊集合上通過定義Flip，Onext與Rot3個(gè)函數(shù)引入了邊代數(shù).Flip定義了邊翻轉(zhuǎn)的方向，Onext給定了在Org函數(shù)基礎(chǔ)上的下一條邊，是按照其朝以逆時(shí)針的順序來看（與翼型邊結(jié)構(gòu)中的nccw類似），Rot是旋轉(zhuǎn)邊（這一定義較復(fù)雜在此略去其細(xì)節(jié)描述）.定向與不定向的二維流形均可由邊代數(shù)描述.邊代數(shù)必須對原網(wǎng)格及其對偶網(wǎng)格給出結(jié)構(gòu).Guibus與Stolfi提出了用四方邊結(jié)構(gòu)來表示網(wǎng)格結(jié)構(gòu)的邊代數(shù)[10].

在基于面的數(shù)據(jù)結(jié)構(gòu)中，Akleman和Chen[5]介紹一種數(shù)據(jù)結(jié)構(gòu)DLFL(Doubly Linked Face List).對于圖形旋轉(zhuǎn)系統(tǒng)的基本操作，采用DLFL數(shù)據(jù)結(jié)構(gòu)有著很好的空間和時(shí)間復(fù)雜度.DLFL數(shù)據(jù)結(jié)構(gòu)是基于面表達(dá)的數(shù)據(jù)結(jié)構(gòu)，是一個(gè)三元組結(jié)構(gòu)L = ，{F}是包含所有的面的集合，每個(gè)面可以用樹結(jié)構(gòu)來表示，葉節(jié)點(diǎn)為圍成面的面角序列.{V}是包含所有定點(diǎn)的集合，其中每一項(xiàng)元素是一個(gè)指向面中葉節(jié)點(diǎn)的指針.{E}是包含所有邊的集合，其中每一項(xiàng)元素指向共享該邊的兩個(gè)或多個(gè)面對應(yīng)的兩個(gè)面角，DLFL的表達(dá)實(shí)例如圖2所示[13].



圖2 正四面體的DLDF數(shù)據(jù)結(jié)構(gòu)表示

Fig.2 DLDF data structure for a regular tetrahedron

2 擴(kuò)展的圖形旋轉(zhuǎn)系統(tǒng)和操作的完整性

和穩(wěn)固性實(shí)現(xiàn)

2．1 擴(kuò)展的圖形旋轉(zhuǎn)系統(tǒng)

假定G是嵌入二維流形S上的一個(gè)網(wǎng)格.圖G中每個(gè)連通子圖對應(yīng)S中一個(gè)特定曲面[14].S上每個(gè)點(diǎn)有一個(gè)同胚于開單位圓的鄰域，假設(shè)站在S上對應(yīng)于圖的頂點(diǎn)v的位置上，則我們可以看見在v點(diǎn)的小范圍鄰域中，相交于v點(diǎn)的所有邊端點(diǎn)按逆時(shí)針的方向形成一個(gè)旋轉(zhuǎn)順序排列.這給出了這些邊端點(diǎn)的一個(gè)旋轉(zhuǎn)順序[14].例如，如果v是沒有相交邊的孤立頂點(diǎn)，則包含v的曲面是虧格為0的球面S2，而S2- {v}同胚于一個(gè)邊界退化為單個(gè)點(diǎn)v的開單位圓[15-16].

因此，網(wǎng)格G在二維流形S上的嵌入對每個(gè)G中的頂點(diǎn)的所有邊端點(diǎn)都引入了一個(gè)旋轉(zhuǎn)順序.有以下重要概念[17].

定義1 設(shè)G為有n個(gè)頂點(diǎn)的圖.圖G中的每條邊有兩個(gè)不同的邊端點(diǎn).如果對圖G中相交于每一頂點(diǎn)的所有邊端點(diǎn)給一固定的旋轉(zhuǎn)順序，則這些對應(yīng)于頂點(diǎn)的所有邊端點(diǎn)的旋轉(zhuǎn)順序的集合稱為圖G的一個(gè)旋轉(zhuǎn)系統(tǒng).

備注1 上述的定義是拓?fù)鋱D論中同一概念的擴(kuò)展.最初用于拓?fù)鋱D論的圖旋轉(zhuǎn)系統(tǒng)不包括孤立點(diǎn)的概念[13].這種包含孤立點(diǎn)的擴(kuò)展的圖旋轉(zhuǎn)系統(tǒng)在二維流形網(wǎng)格建模研究中具有重要作用.

備注2 定義的圖旋轉(zhuǎn)系統(tǒng)中，圖G并不一定要連通，并允許多邊（即允許多于一條邊與同一頂點(diǎn)對相連）與自循環(huán)（即一條邊的兩個(gè)端點(diǎn)可為同一個(gè)頂點(diǎn)）.當(dāng)然，在多邊存在的情況下，必須區(qū)別有同樣端點(diǎn)的不同邊.自循環(huán)的兩個(gè)端點(diǎn)也應(yīng)該被區(qū)分.

備注3 圖G中一條邊的兩個(gè)對應(yīng)邊端點(diǎn)可用與該邊相交的兩個(gè)頂點(diǎn)來表示.如u和v是不同的頂點(diǎn)，則我們可以用 <u, v> 和 <v, u> 來分別表示邊 [u, v] 相交于節(jié)點(diǎn)u和相交于節(jié)點(diǎn)v的兩個(gè)邊端點(diǎn).如果邊 [u, v] 是自循環(huán)的，即u = v，則根據(jù)備注2，邊[u, u]的兩個(gè)邊端點(diǎn)可區(qū)別記為u和u，而其兩個(gè)邊端點(diǎn)為 <u, u> 和 <u, u>.如用符號 e表示一邊端點(diǎn).則同一條邊的另一邊端點(diǎn)記為 rev (e).所以，如 e = <u, v>，則rev(e) = <v, u>.

備注4一個(gè)擴(kuò)展的圖旋轉(zhuǎn)系統(tǒng)ρ(G)給出了圖G的頂點(diǎn)集和邊集.另外，通過由一個(gè)叫做FaceTrace的算法[17]，我們可以唯一構(gòu)造出從一個(gè)邊端點(diǎn)出發(fā)對應(yīng)的面元素.因此，反復(fù)利用FaceTrace算法，可以構(gòu)造出所有的面元素，從而重構(gòu)出圖G在一個(gè)二維流形上的嵌入[17].事實(shí)上，這種二維流形的重構(gòu)是唯一的，如定理1所述．

定理1 [17]一個(gè)擴(kuò)展的圖的旋轉(zhuǎn)系統(tǒng)ρ(G)唯一確定了圖G在一有效二維流形上的嵌入，從而唯一確定了對應(yīng)的二維流形.

網(wǎng)格建模中的操作是重要的，特別是對于擁有可靠與強(qiáng)大的用戶接口的建模系統(tǒng).定理1為二維流形的網(wǎng)格建模操作問題提供了堅(jiān)實(shí)的理論基礎(chǔ).二維流形建模在建模操作上存在三個(gè)重要的問題，分別為完整性，穩(wěn)固性與有效性.產(chǎn)生任何二維流形結(jié)構(gòu)需要的操作都是從集合S中得到，那么稱集合S是操作上完備的.如果運(yùn)用集合S中的操作于二維流形都能產(chǎn)生有效的二維流形結(jié)構(gòu)，那么集合S的操作是穩(wěn)固的.定理1將網(wǎng)格建模操作的健全與完備問題變成基于圖形旋轉(zhuǎn)系統(tǒng)的表示問題：只要能證明提出來的操作集合能創(chuàng)建所有且僅限于有效的圖形旋轉(zhuǎn)系統(tǒng)，那么就能保證操作集合的健全與完備.

2．2 完備與健全的操作集合

與以往提出的相比，本文提出的建模操作集合更簡單，直觀與方便用戶使用.下面將討論操作集合的健全性及完備性，操作集合S是“完備”和“健全”的.“完備”的含義是指：通過S中的操作可以構(gòu)造任意的二維流形體.“健全”的是指：S中的操作對二維流形體是封閉的.考量其在各種建模數(shù)據(jù)結(jié)構(gòu)上執(zhí)行的有效性，并與現(xiàn)有的建模操作的各個(gè)方面作比較.

第一個(gè)操作是邊插入操作，簡單記作EINSERT，設(shè)ρ(G)為一個(gè)圖形旋轉(zhuǎn)系統(tǒng)，u和v是G中的兩個(gè)頂點(diǎn).在面拐角(<u, x>, <u, x>)與(<v, y>, <v, y>)間插入一條邊[u, v]，也就是在邊端<u, x>與< u, x>間的旋轉(zhuǎn)點(diǎn)v處插入邊端< u, v>和在邊端<v, y>與<v, y>間的旋轉(zhuǎn)點(diǎn)v處插入邊端<v, u>.與插入相反的為邊刪除操作，簡單記作EDELETE.同樣設(shè)ρ(G)為一個(gè)圖形旋轉(zhuǎn)系統(tǒng)，e=[u, v]為G中的一條邊，刪除邊e即在旋轉(zhuǎn)點(diǎn)u處刪除<u, x>和在v處刪除<v, u>.

其他主要的操作有創(chuàng)建頂點(diǎn)，簡單記作VCREATE，此操作在旋轉(zhuǎn)系統(tǒng)中創(chuàng)建不帶邊的孤立點(diǎn)，對應(yīng)相反的操作為移除點(diǎn)，VREMOVE，是在旋轉(zhuǎn)系統(tǒng)中移除一個(gè)孤立點(diǎn).

定理2 由EINSERT/EDELETE和VCREATE/V REMOVE組成的操作集合是完備與健全的.

證操作集合明顯有健全性：在能夠表示有效二維流形結(jié)構(gòu)的圖形旋轉(zhuǎn)系統(tǒng)上應(yīng)用4種操作會產(chǎn)生有效的二維流形結(jié)構(gòu).

前面已經(jīng)說明，任意二維流形S的多孔網(wǎng)格結(jié)構(gòu)導(dǎo)出唯一的旋轉(zhuǎn)系統(tǒng)ρ(G).先后運(yùn)用一系列的EDELETE與VREMOVE操作后，會得到?jīng)]有頂點(diǎn)與邊的空旋轉(zhuǎn)系統(tǒng).反過來，即先后運(yùn)用一系列的VCREATE與EINSERT操作后，會從一個(gè)空旋轉(zhuǎn)系統(tǒng)中重建旋轉(zhuǎn)系統(tǒng)ρ(G).由此可見，通過一系列的集合中的操作能得到任何多孔網(wǎng)格結(jié)構(gòu)，任意虧格的曲面也能通過本文提出的操作集合構(gòu)造出來．證畢

與[2,8]中提出與研究的歐拉操作相比，本文提出的操作集合更加簡單、直觀、一致和更易于用戶使用且提出的集合僅由更少的操作組成.避免了系統(tǒng)層與用戶層及內(nèi)部表示與拓?fù)渫暾缘牟灰恢陋﹩栴}.

2．3 基于頂點(diǎn)的數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)

在鄰接表結(jié)構(gòu)上實(shí)現(xiàn)EINSERT，EDELETE和VCREATE，VREMOVE操作非常簡單.若在面拐角(<u, x>, <u, x>)與(<w, y>, <w, y>)間插入一條邊[u, w]（在表示u的鏈表中x在x之后，表示w的鏈表中y在y之后），只需在表示頂點(diǎn)u鏈表中分別包含x與x的兩個(gè)結(jié)點(diǎn)之間插入包含w的結(jié)點(diǎn)和在表示頂點(diǎn)w鏈表中分別包含y與y的兩個(gè)結(jié)點(diǎn)之間插入包含u的結(jié)點(diǎn).同理，在表示頂點(diǎn)u鏈表中刪除w和表示頂點(diǎn)w鏈表中刪除u來在鄰接表結(jié)構(gòu)上對邊[u, w]實(shí)行EDELETE操作.最后，VCREATE操作對應(yīng)的是增加一個(gè)帶有空鏈表的新頂點(diǎn)到鄰接表中，VREMOVE操作則對應(yīng)從鄰接表中移除一個(gè)帶有空鏈表的頂點(diǎn).

在鄰接表上執(zhí)行VCREATE與VREMOVE操作所需時(shí)間為一常數(shù).而EINSERT與EDELETE操作執(zhí)行時(shí)則需要查找對應(yīng)兩個(gè)頂點(diǎn)的鏈表，當(dāng)頂點(diǎn)的價(jià)很大時(shí)會很耗時(shí).用平衡樹代替鏈表存儲與頂點(diǎn)相關(guān)的端點(diǎn)，EINSERT與EDELETE操作執(zhí)行的時(shí)間復(fù)雜度可以得到改進(jìn)，只需樹大小的對數(shù)的時(shí)間復(fù)雜度[10].此外，實(shí)現(xiàn)中，只需要增加一個(gè)邊表來支持對結(jié)構(gòu)中邊端的有效查找.

2．4 基于邊的數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)

為了實(shí)現(xiàn)VCREATE與VREMOVE操作，需要在翼型邊線結(jié)構(gòu)中引入輔助的頂點(diǎn)表.頂點(diǎn)表中包含頂點(diǎn)結(jié)點(diǎn)，其指針指向任意邊結(jié)點(diǎn)中端點(diǎn)v.孤立頂點(diǎn)包含空指針.實(shí)現(xiàn)VCREATE操作只需簡單地往結(jié)構(gòu)中增加一個(gè)帶空指針的新頂點(diǎn)結(jié)點(diǎn).VREMOVE操作則是從結(jié)構(gòu)中移除一個(gè)帶空指針的頂點(diǎn)結(jié)點(diǎn).

在翼型邊線結(jié)構(gòu)上執(zhí)行EINSERT與EDELETE操作算法見圖3，其中子程序FaceTrace即是文獻(xiàn)[17]中的FaceTrace的算法.從一個(gè)邊端點(diǎn)出發(fā)，子程序FaceTrace構(gòu)造出對應(yīng)的面元素.操作EINSERT是在面拐角c1=(<u, x>, <u, x>)與c2= (<w, y>, <w, y>)間插入一條邊<u, w>，操作EDELETE則是刪除邊e.執(zhí)行操作后，相關(guān)邊的ncw，pcw，，nccw，pccw部分會更新.需要解釋的是對fcw與fccw的更新.首先考慮EINSERT，如果面拐角c1與c2屬于不同的面，那么在它們之間插入邊e=[u, v]的操作得到的一個(gè)新面會代替網(wǎng)格中的兩個(gè)面，這個(gè)新面的邊界包含e的邊端<u, w>與<w, u>.這種情形下，步驟5中子程序FaceTrace（<u, w>）會跟蹤新面的邊界并適時(shí)更新有關(guān)邊結(jié)點(diǎn)中面部分的信息.特別地，步驟6中子程序FaceTrace不會執(zhí)行.另一方面，如果面拐角c1與c2屬于同一面，那么在它們之間插入邊e=[u, v]的操作得到的兩個(gè)新面會代替網(wǎng)格中的一個(gè)面，這兩個(gè)新面的邊界包含e的邊端<u, w>與<w, u>.這種情形下，步驟5中子程序FaceTrace會跟蹤一個(gè)新面的邊界并適時(shí)更新有關(guān)邊結(jié)點(diǎn)中面部分的信息.步驟6中子程序FaceTrace則會跟蹤另一個(gè)新面的邊界并適時(shí)更新有關(guān)邊結(jié)點(diǎn)中面部分的信息.

對邊e實(shí)現(xiàn)EDELETE操作，如果e的兩個(gè)端點(diǎn)在兩個(gè)不同面的邊界上，那么刪除e會合并兩個(gè)面為一個(gè)面.步驟5中子程序FaceTrace會跟蹤新面的邊界并適時(shí)更新有關(guān)邊結(jié)點(diǎn)中面部分的信息.另一方面，如果e的兩個(gè)端點(diǎn)在同一面的邊界上，那么刪除e會分離這個(gè)面為兩個(gè)面.步驟5與步驟6中的子程序FaceTrace會分別跟蹤兩個(gè)新面的邊界并適時(shí)更新有關(guān)邊結(jié)點(diǎn)中面部分的信息.



圖3翼邊結(jié)構(gòu)的EINSERT 和 EDELETE 算法

Fig.3 EINSERT and EDELETE on wingededge structure



算法EINSERT與EDELETE的時(shí)間復(fù)雜度分析.由于每個(gè)算法都需執(zhí)行一個(gè)或兩個(gè)時(shí)間復(fù)雜度正比于相關(guān)面大小的FaceTrace子程序，當(dāng)面較小時(shí)（如在三角化網(wǎng)格上）耗時(shí)較小，在面很大的情況下，將耗費(fèi)大量時(shí)間.可以得到定理3的結(jié)論.

定理3 對于一般的翼型邊線結(jié)構(gòu)，算法EINSERT與EDELETE的運(yùn)行時(shí)間復(fù)雜度為O(s)，s是有關(guān)面的大小，特別地，對于沒有fcw與fccw信息部分的翼型邊線結(jié)構(gòu)其算法EINSERT與EDELETE的運(yùn)行時(shí)間復(fù)雜度為O(1).

在翼型邊線結(jié)構(gòu)上執(zhí)行EINSERT與EDELETE操作可容易地?cái)U(kuò)展到其他的基于邊的數(shù)據(jù)結(jié)構(gòu)上.

2．5 基于面的數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)

DLFL結(jié)構(gòu)有一個(gè)面表，一個(gè)邊表和一個(gè)頂點(diǎn)表.面表中每個(gè)面結(jié)點(diǎn)是對應(yīng)面邊界的邊端序列，邊表中每個(gè)邊結(jié)點(diǎn)有兩個(gè)指向面表中對應(yīng)的邊端的指針，而頂點(diǎn)表中的每個(gè)頂點(diǎn)結(jié)點(diǎn)則有一個(gè)指向面表中以該頂點(diǎn)為極的邊端的指針.

VCREATE與VREMOVE操作實(shí)現(xiàn)是簡單的.VCREATE（v）創(chuàng)建面表中面邊界退化為單個(gè)頂點(diǎn)v的面結(jié)點(diǎn)，也創(chuàng)建頂點(diǎn)表中的頂點(diǎn)結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)的指針指向相應(yīng)的新面.VREMOVE操作則從面表中移除一個(gè)面邊界退化為單個(gè)頂點(diǎn)v的面結(jié)點(diǎn)，也移除頂點(diǎn)表中的表示v的頂點(diǎn)結(jié)點(diǎn).

在DLFL結(jié)構(gòu)上實(shí)現(xiàn)EINSERT和EDELETE的算法，如圖4所示，其正確性可從前面的證明得到檢驗(yàn).下面考慮算法的時(shí)間復(fù)雜度.

既然邊表中的邊結(jié)點(diǎn)有兩個(gè)指向面表中的邊端的指針，對于每條邊，可以在時(shí)間為常數(shù)的情形下，從面表中獲取它的端點(diǎn).對于面表中的每個(gè)面結(jié)點(diǎn)f，有一個(gè)包含端點(diǎn)的循環(huán)鏈表與面邊界對應(yīng).如果采用平衡樹結(jié)構(gòu)實(shí)現(xiàn)這個(gè)循環(huán)鏈表（如2-3樹結(jié)構(gòu)［1］）那么檢測兩個(gè)端點(diǎn)是否屬于同一個(gè)面，把一個(gè)端點(diǎn)表分為兩個(gè)，合并兩個(gè)端點(diǎn)表的操作均可以在時(shí)間復(fù)雜度為O(s)下完成，s是有關(guān)面的大?。ǜ嗟募?xì)節(jié)描述與檢驗(yàn)見[17]）.注意到，每次在DLFL結(jié)構(gòu)上執(zhí)行EINSERT與EDELETE算法都是由一個(gè)或多個(gè)檢測測端點(diǎn)表，分離與合并操作組成.因此，在實(shí)現(xiàn)面結(jié)點(diǎn)端點(diǎn)表的循環(huán)鏈表下，算法EINSERT與EDELETE的運(yùn)行時(shí)間復(fù)雜度限制為O(log s).結(jié)論如定理4所示.

定理4 在DLFL結(jié)構(gòu)上，VCEATE與VREMOVE操作運(yùn)行時(shí)間復(fù)雜度限定為O(1), EINSERT與EDELETE操作的運(yùn)行時(shí)間復(fù)雜度限制為O(log s)，s是有關(guān)面的大小（至多涉及兩個(gè)面）.

同時(shí)指出在DLFL結(jié)構(gòu)上實(shí)現(xiàn)VCEATE，VREMOVE，EINSERT與EDELETE操作，它們的運(yùn)行時(shí)間復(fù)雜度與有關(guān)頂點(diǎn)的價(jià)無關(guān).



圖4DLFL的EINSERT 和 EDELETE 算法

Fig.4 EINSERT and EDELETE on DLFL structure



3 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證本文的算法，對于基本的圖形旋轉(zhuǎn)系統(tǒng)的操作，插入、刪除邊，創(chuàng)建，刪除點(diǎn)操作都是流形的封閉操作，因此構(gòu)建的網(wǎng)格結(jié)構(gòu)都是二維流形的.如圖5（a）所示，左邊分別為構(gòu)建的一個(gè)方體結(jié)構(gòu)、正四面體結(jié)構(gòu)和帶柄方體結(jié)構(gòu)，右邊為對應(yīng)的進(jìn)行一次細(xì)分算法的結(jié)果.從細(xì)分的結(jié)果可以看出所構(gòu)建的基本網(wǎng)格結(jié)構(gòu)是流形的.

4 結(jié) 論

帶有一個(gè)簡單而強(qiáng)大的用戶接口的健壯的網(wǎng)格拓?fù)浣Ｊ怯?jì)算機(jī)圖形學(xué)與計(jì)算機(jī)輔助幾何設(shè)計(jì)中的重點(diǎn).本文研究了包括對二維流形網(wǎng)格建模的表示，數(shù)據(jù)結(jié)構(gòu)與操作的一些基本問題.拓展了圖形旋轉(zhuǎn)系統(tǒng)在拓?fù)鋱D論的理論研究并表明擴(kuò)展了的圖形旋轉(zhuǎn)系統(tǒng)為二維流形網(wǎng)格建模提供了一個(gè)堅(jiān)實(shí)的理論基礎(chǔ).在此基礎(chǔ)上，提出了一種新的二維流形網(wǎng)格

（a）長方體結(jié)構(gòu)

（b）正四面體結(jié)構(gòu)

（c）帶柄方體結(jié)構(gòu)

圖5 長方體、正四面體和帶柄方體結(jié)構(gòu)

及其對應(yīng)的一次細(xì)分算法結(jié)果



Fig.5Cuboid, regular tetrahedron and cube with handle 

and their corresponding subdivision results



建模操作集合，并且證明這個(gè)操作集合是完備與健全的，通過這個(gè)集合中的操作序列能構(gòu)造任意的二維流形網(wǎng)格結(jié)構(gòu).此外，本文還介紹了在基于點(diǎn)，邊和面的數(shù)據(jù)結(jié)構(gòu)上能有效地實(shí)現(xiàn)本文的操作.

參考文獻(xiàn)

［1］ HOFFMANN C M, VANECEK G. Fundamental techniques for geometric and solid modeling[J]. Manufacturing and Automation Systems: Techniques and Technologies, 1990,48:347-356.

［2］ MANTYLA M. An introduction to solid modeling[M]. Michigan: University of Michigan,Computer Science Press,2007:30-120.

［3］ MANTYLA M. Boolean operations of 2manifolds through vertex neighborhood classification[J]. ACM Transaction on Graphics, 1986, 5(1): 1-29.

［4］ WEILER K. Edgebased data structures for solid modeling in curvedsurface environments[J]. IEEE: Computer Graphics & Applications, 1985,5(1): 21-40.

［5］ AKLEMAN E, CHEN Jianer. Guaranteeing the 2manifold property for meshes with doubly linked face list[J]. International Journal of Shape Modeling, 1999, 2(5): 149-177.

［6］趙明喜，馬利莊，毛志宏. 基于改進(jìn)的圖形旋轉(zhuǎn)系統(tǒng)的高虧格造型系統(tǒng)[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2006,18(3):421-425.

ZHAO Mingxi, MA Lizhuang, MAO Zhihong. A high genus modeling system based on improved graph rotation system[J]. Journal of Computer Aided Design & Computer Graphics,2006,18(3):421-425.(In Chinese)

［7］ BAUMGART Bruce G. Wingededge polyhedron representation[R]. Stanford: Stanford University,1972.

［8］ BRAID I, HILLYARD R, STROUD I. Stepwise construction of polyhedra in geometric modeling[M]. New York/London: Academic Press, 1980: 123-141. 

［9］ FUJIO Yamaguchi, TOSHIYA Tokiead. Frontiers in computer graphics［M］.Tokyo:Springer Japan, 1985:44-65.

［10］GUIBAS L, STOLFI J. Primitives for the manipulation of general subdivision and computation of Voronoi diagrams[J]. ACM Transaction on Graphics, 1985, 4(2): 74-123.

［11］GROSS J, TUCKER T. Topological graph theory[M]. Mineola, New York : Dover Publications, 2001:20-60.

［12］MURALI T, FUNKHOUSER T. Consistent solid and boundary representations from arbitrary polygonal data computer graphics［C］//Proceedings of the 1997 Symposium on Interactive 3D Graphics. ACM, 1997:155-162.

［13］張曄芝，谷士文，費(fèi)耀平. 基于圖形旋轉(zhuǎn)系統(tǒng)的漸進(jìn)網(wǎng)格研究[J]. 湖南大學(xué)學(xué)報(bào):自然科學(xué)版, 2004, 31(4):10-16.

ZHANG Yezhi, GU Shiwen, FEI Yaoping. Study of progressive mesh based on graph rotation system[J]. Journal of Hunam University:Natural Sciences, 2004,31(4):10-16.(In Chinese)

［14］CHEN J. Algorithmic graph embeddings［J］.Lecture Notes in Computer Science,1975,959(S):151-160.

［15］AKLEMAN E, CHEN J Gross. Extended graph rotation systems as a model for cyclic weaving on orientable surfaces [J]. Computer Science & Engineering, 2009, 9(5): 52-57.

［16］AKLEMAN Ergun, CHEN Jianer. Cyclic plainweaving on polygonal mesh surfaces with graph rotation systems [C]// Proceeding of SIGGRAPH'09 ACM SIGGRAPH 2009 Papers. ACM, 2009:78-83.

［17］費(fèi)耀平, 陳松喬,李敏. 二維流形建模系統(tǒng)的拓?fù)溆行詼y試算法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2011, 23(8):1337-1348.

FEI Yaoping, CHEN Songqiao, LI Min. On testing topological validity for manifold modeling systems[J]. Journal of ComputerAided Design & Computer Graphics, 2011, 23(8):1337-1348.(In Chinese)