費耀平+陳建二+陳松喬+李敏

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

收稿日期：20131101

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

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

理論上說，一個二維流形的網(wǎng)格結(jié)構(gòu)由3個主要部分組成：頂點集、邊集、和面集以及這些部分間的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)格在非二維流形上的嵌入.

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

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

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

本文將進一步研究網(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)

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

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

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

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



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

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



Guibus與Stolfi[10]研究四方邊結(jié)構(gòu)時定義了網(wǎng)格中邊的代數(shù)式與其對偶式.每條邊給定一個確定方向，從而確定了邊的左面和右面.由此，每條邊有4個不同的方向，并且有4種屬性：兩個端點Org與Dest（等價于翼型邊結(jié)構(gòu)中的vs與ve），二維流形上邊的兩側(cè)上的左邊面與右邊面（等價于翼型邊結(jié)構(gòu)中的fcw與fccw）.在定向的有向邊集合上通過定義Flip，Onext與Rot3個函數(shù)引入了邊代數(shù).Flip定義了邊翻轉(zhuǎn)的方向，Onext給定了在Org函數(shù)基礎(chǔ)上的下一條邊，是按照其朝以逆時針的順序來看（與翼型邊結(jié)構(gòu)中的nccw類似），Rot是旋轉(zhuǎn)邊（這一定義較復(fù)雜在此略去其細節(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)有著很好的空間和時間復(fù)雜度.DLFL數(shù)據(jù)結(jié)構(gòu)是基于面表達的數(shù)據(jù)結(jié)構(gòu)，是一個三元組結(jié)構(gòu)L = ，{F}是包含所有的面的集合，每個面可以用樹結(jié)構(gòu)來表示，葉節(jié)點為圍成面的面角序列.{V}是包含所有定點的集合，其中每一項元素是一個指向面中葉節(jié)點的指針.{E}是包含所有邊的集合，其中每一項元素指向共享該邊的兩個或多個面對應(yīng)的兩個面角，DLFL的表達實例如圖2所示[13].



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

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

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

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

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

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

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

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

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

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

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

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

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

網(wǎng)格建模中的操作是重要的，特別是對于擁有可靠與強大的用戶接口的建模系統(tǒng).定理1為二維流形的網(wǎng)格建模操作問題提供了堅實的理論基礎(chǔ).二維流形建模在建模操作上存在三個重要的問題，分別為完整性，穩(wěn)固性與有效性.產(chǎn)生任何二維流形結(jié)構(gòu)需要的操作都是從集合S中得到，那么稱集合S是操作上完備的.如果運用集合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)有的建模操作的各個方面作比較.

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

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

定理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).先后運用一系列的EDELETE與VREMOVE操作后，會得到?jīng)]有頂點與邊的空旋轉(zhuǎn)系統(tǒng).反過來，即先后運用一系列的VCREATE與EINSERT操作后，會從一個空旋轉(zhuǎn)系統(tǒng)中重建旋轉(zhuǎn)系統(tǒng)ρ(G).由此可見，通過一系列的集合中的操作能得到任何多孔網(wǎng)格結(jié)構(gòu)，任意虧格的曲面也能通過本文提出的操作集合構(gòu)造出來．證畢

與[2,8]中提出與研究的歐拉操作相比，本文提出的操作集合更加簡單、直觀、一致和更易于用戶使用且提出的集合僅由更少的操作組成.避免了系統(tǒng)層與用戶層及內(nèi)部表示與拓撲完整性的不一致問題.

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

在鄰接表結(jié)構(gòu)上實現(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之后），只需在表示頂點u鏈表中分別包含x與x的兩個結(jié)點之間插入包含w的結(jié)點和在表示頂點w鏈表中分別包含y與y的兩個結(jié)點之間插入包含u的結(jié)點.同理，在表示頂點u鏈表中刪除w和表示頂點w鏈表中刪除u來在鄰接表結(jié)構(gòu)上對邊[u, w]實行EDELETE操作.最后，VCREATE操作對應(yīng)的是增加一個帶有空鏈表的新頂點到鄰接表中，VREMOVE操作則對應(yīng)從鄰接表中移除一個帶有空鏈表的頂點.

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

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

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

在翼型邊線結(jié)構(gòu)上執(zhí)行EINSERT與EDELETE操作算法見圖3，其中子程序FaceTrace即是文獻[17]中的FaceTrace的算法.從一個邊端點出發(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]的操作得到的一個新面會代替網(wǎng)格中的兩個面，這個新面的邊界包含e的邊端<u, w>與<w, u>.這種情形下，步驟5中子程序FaceTrace（<u, w>）會跟蹤新面的邊界并適時更新有關(guān)邊結(jié)點中面部分的信息.特別地，步驟6中子程序FaceTrace不會執(zhí)行.另一方面，如果面拐角c1與c2屬于同一面，那么在它們之間插入邊e=[u, v]的操作得到的兩個新面會代替網(wǎng)格中的一個面，這兩個新面的邊界包含e的邊端<u, w>與<w, u>.這種情形下，步驟5中子程序FaceTrace會跟蹤一個新面的邊界并適時更新有關(guān)邊結(jié)點中面部分的信息.步驟6中子程序FaceTrace則會跟蹤另一個新面的邊界并適時更新有關(guān)邊結(jié)點中面部分的信息.

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



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

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



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

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

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

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

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

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

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

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

定理4 在DLFL結(jié)構(gòu)上，VCEATE與VREMOVE操作運行時間復(fù)雜度限定為O(1), EINSERT與EDELETE操作的運行時間復(fù)雜度限制為O(log s)，s是有關(guān)面的大?。ㄖ炼嗌婕皟蓚€面）.

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



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

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



3 實驗結(jié)果

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

4 結(jié) 論

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

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

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

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

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

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



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

and their corresponding subdivision results





建模操作集合，并且證明這個操作集合是完備與健全的，通過這個集合中的操作序列能構(gòu)造任意的二維流形網(wǎng)格結(jié)構(gòu).此外，本文還介紹了在基于點，邊和面的數(shù)據(jù)結(jié)構(gòu)上能有效地實現(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］ 趙明喜，馬利莊，毛志宏. 基于改進的圖形旋轉(zhuǎn)系統(tǒng)的高虧格造型系統(tǒng)[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 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］張曄芝，谷士文，費耀平. 基于圖形旋轉(zhuǎn)系統(tǒng)的漸進網(wǎng)格研究[J]. 湖南大學(xué)學(xué)報:自然科學(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］費耀平, 陳松喬,李敏. 二維流形建模系統(tǒng)的拓撲有效性測試算法[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 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)

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

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



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

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



3 實驗結(jié)果

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

4 結(jié) 論

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

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

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

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

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

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



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

and their corresponding subdivision results





建模操作集合，并且證明這個操作集合是完備與健全的，通過這個集合中的操作序列能構(gòu)造任意的二維流形網(wǎng)格結(jié)構(gòu).此外，本文還介紹了在基于點，邊和面的數(shù)據(jù)結(jié)構(gòu)上能有效地實現(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］ 趙明喜，馬利莊，毛志宏. 基于改進的圖形旋轉(zhuǎn)系統(tǒng)的高虧格造型系統(tǒng)[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 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］張曄芝，谷士文，費耀平. 基于圖形旋轉(zhuǎn)系統(tǒng)的漸進網(wǎng)格研究[J]. 湖南大學(xué)學(xué)報:自然科學(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］費耀平, 陳松喬,李敏. 二維流形建模系統(tǒng)的拓撲有效性測試算法[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 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)

定理4 在DLFL結(jié)構(gòu)上，VCEATE與VREMOVE操作運行時間復(fù)雜度限定為O(1), EINSERT與EDELETE操作的運行時間復(fù)雜度限制為O(log s)，s是有關(guān)面的大?。ㄖ炼嗌婕皟蓚€面）.

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



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

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



3 實驗結(jié)果

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

4 結(jié) 論

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

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

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

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

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

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



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

and their corresponding subdivision results





建模操作集合，并且證明這個操作集合是完備與健全的，通過這個集合中的操作序列能構(gòu)造任意的二維流形網(wǎng)格結(jié)構(gòu).此外，本文還介紹了在基于點，邊和面的數(shù)據(jù)結(jié)構(gòu)上能有效地實現(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］ 趙明喜，馬利莊，毛志宏. 基于改進的圖形旋轉(zhuǎn)系統(tǒng)的高虧格造型系統(tǒng)[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 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］張曄芝，谷士文，費耀平. 基于圖形旋轉(zhuǎn)系統(tǒng)的漸進網(wǎng)格研究[J]. 湖南大學(xué)學(xué)報:自然科學(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］費耀平, 陳松喬,李敏. 二維流形建模系統(tǒng)的拓撲有效性測試算法[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 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)