二維流形圖形建模系統完備操作集研究＊

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

（中南大學 信息科學與工程學院，湖南 長沙 410083）

二維流形圖形建模系統完備操作集研究＊

費耀平，陳建二，陳松喬，李 敏?

（中南大學 信息科學與工程學院，湖南 長沙 410083）

針對目前大多數二維流形建模系統不能保證二維流形結構的問題，如歐拉操作會產生非二維流形網格結構，通過對基于網格結構的二維流形建模系統中的各種數據結構及非流形和流形結構的研究，提出了一套新的基于圖形旋轉系統的完備的網格建模操作.與現有二維流形建模系統中的數據結構和網格建模操作相比，新提出的數據結構和網格建模操作更加直觀有效并更方便用戶使用.

歐拉操作；圖形建模；二維流形；網格結構

網格是計算機圖形學中最常用的結構［1－2］.具有簡單有效的用戶接口的二維流形建模系統是計算機圖形學與計算機輔助設計中的重要問題.現有的二維流形建模在處理非流形結構時，通常會使建模算法變得非常復雜［1，3］.另外，一些廣泛使用的建模操作如細分算法需要更有效的二維流形結構，否則細分操作執行在非二維流形結構上時，這些建模系統如Maya可能無法正常工作.

理論上說，一個二維流形的網格結構由3個主要部分組成：頂點集、邊集、和面集以及這些部分間的9種鄰接關系［4］.描述網格結構已有許多數據結構，一些數據結構是基于面集的［5－6］，另一些是基于邊集的.最有名的基于邊集的表示是Baumgart提出的翼型邊結構（winged-edges structure）［7］及其以后的許多翼型邊結構的變種［8－9］.這些數據結構可以用來描述網格在二維流形上的嵌入，也可以用來描述網格在非二維流形上的嵌入.

另一個重要問題是應用在網格結構上的操作集.如果操作集中每一個操作作用于一個二維流形上都產生一個有效的二維流形并且每個二維流形都能由操作集中的操作產生，則我們稱這一操作集是一個完備操作集.例如，在實體建模中，應用最多的是集合操作，但集合操作可能產生非二維流形結構［1］.因此，集合操作不是一個完備操作集.

Mantyla［2］研究了歐拉操作并證明它們對二維流形建模形成一個完備操作集.Guibas and Stolfi［10］在四方邊結構的基礎上提出了接合（splice）操作.并證明這一操作也形成一個完備操作集.另外還有其他對這個方向的研究［1－2］.

一些學者提出了用于評價二維流形網格建模方案的質量準則［1－2］，包括：有效性（結構能否有效表示所有二維流形結構），完備性（網格建模操作集是否是一個完備操作集），簡單性（結構與操作是否簡單直觀）和效率性（結構與操作是否有高效率的數據結構和算法）.

本文將進一步研究網格結構建模方面的上述標準，并提出一套新的網格結構建模操作集，證明其形成一套二維流形網格建模的完備操作集.與現有二維流形建模系統相比，新提出的數據結構和網格建模操作更加直觀有效并更方便用戶使用.

1 二維流形的翼形邊結構和DLFL結構

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

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

令G為二維流形S上的一個網格.G中的每個頂點v在S上有一個同胚于開單位圓的鄰域N.相交于頂點v的邊在N中有一個循環排列順序（按逆時針順序排列）.這一順序對表示一個二維流形網格非常重要.Baumgart提出的經典翼型邊結構［7，12］本質上來說是基于此形式上.翼型邊結構的主要單元是邊結點.每個邊結點由9個單元組成：（name，vs，ve，fcw，fccw，ncw，pcw，nccw，pccw），name是邊的名字；vs與ve是邊的起始與結束端點（也就為邊指定了一個方向）；fcw與fccw表示當沿著邊的方向行走時邊的左邊和右邊的面的名字；ncw與pccw分別為面fcw和面fccw中的下條邊，而pcw與nccw分別為當逆著邊的方向行走時面fcw和面fccw中的下條邊.如圖1所示.

圖1 翼型邊結構中一個邊結點的9個單元Fig.1 A edge node in the winged-edge structure

Guibus與Stolfi［10］研究四方邊結構時定義了網格中邊的代數式與其對偶式.每條邊給定一個確定方向，從而確定了邊的左面和右面.由此，每條邊有4個不同的方向，并且有4種屬性：兩個端點Org與Dest（等價于翼型邊結構中的vs與ve），二維流形上邊的兩側上的左邊面與右邊面（等價于翼型邊結構中的fcw與fccw）.在定向的有向邊集合上通過定義Flip，Onext與Rot3個函數引入了邊代數.Flip定義了邊翻轉的方向，Onext給定了在Org函數基礎上的下一條邊，是按照其朝以逆時針的順序來看（與翼型邊結構中的nccw類似），Rot是旋轉邊（這一定義較復雜在此略去其細節描述）.定向與不定向的二維流形均可由邊代數描述.邊代數必須對原網格及其對偶網格給出結構.Guibus與Stolfi提出了用四方邊結構來表示網格結構的邊代數［10］.

在基于面的數據結構中，Akleman和Chen［5］介紹一種數據結構DLFL（Doubly Linked Face List）.對于圖形旋轉系統的基本操作，采用DLFL數據結構有著很好的空間和時間復雜度.DLFL數據結構是基于面表達的數據結構，是一個三元組結構L＝＜F，V，E＞，｛F｝是包含所有的面的集合，每個面可以用樹結構來表示，葉節點為圍成面的面角序列.｛V｝是包含所有定點的集合，其中每一項元素是一個指向面中葉節點的指針.｛E｝是包含所有邊的集合，其中每一項元素指向共享該邊的兩個或多個面對應的兩個面角，DLFL的表達實例如圖2所示［13］.

圖2 正四面體的DLDF數據結構表示Fig.2 DLDF data structure for a regular tetrahedron

2 擴展的圖形旋轉系統和操作的完整性和穩固性實現

2.1 擴展的圖形旋轉系統

假定G是嵌入二維流形S上的一個網格.圖G中每個連通子圖對應S中一個特定曲面［14］.S上每個點有一個同胚于開單位圓的鄰域，假設站在S上對應于圖的頂點v的位置上，則我們可以看見在v點的小范圍鄰域中，相交于v點的所有邊端點按逆時針的方向形成一個旋轉順序排列.這給出了這些邊端點的一個旋轉順序［14］.例如，如果v是沒有相交邊的孤立頂點，則包含v的曲面是虧格為0的球面S2，而S2－ ｛v｝同胚于一個邊界退化為單個點v的開單位圓［15－16］.

因此，網格G在二維流形S上的嵌入對每個G中的頂點的所有邊端點都引入了一個旋轉順序.有以下重要概念［17］.

定義1 設G為有n個頂點的圖.圖G中的每條邊有兩個不同的邊端點.如果對圖G中相交于每一頂點的所有邊端點給一固定的旋轉順序，則這些對應于頂點的所有邊端點的旋轉順序的集合稱為圖G的一個旋轉系統.

備注1 上述的定義是拓撲圖論中同一概念的擴展.最初用于拓撲圖論的圖旋轉系統不包括孤立點的概念［13］.這種包含孤立點的擴展的圖旋轉系統在二維流形網格建模研究中具有重要作用.

備注2 定義的圖旋轉系統中，圖G并不一定要連通，并允許多邊（即允許多于一條邊與同一頂點對相連）與自循環（即一條邊的兩個端點可為同一個頂點）.當然，在多邊存在的情況下，必須區別有同樣端點的不同邊.自循環的兩個端點也應該被區分.

備注3 圖G中一條邊的兩個對應邊端點可用與該邊相交的兩個頂點來表示.如u和v是不同的頂點，則我們可以用 ＜u，v＞ 和 ＜v，u＞ 來分別表示邊 ［u，v］相交于節點u和相交于節點v的兩個邊端點.如果邊 ［u，v］是自循環的，即u＝v，則根據備注2，邊［u，u］的兩個邊端點可區別記為u’和u’’，而其兩個邊端點為 ＜u’，u’’＞ 和＜u’’，u’＞.如用符號e表示一邊端點.則同一條邊的另一邊端點記為rev（e）.所以，如e＝ ＜u，v＞，則rev（e）＝ ＜v，u＞.

備注4 一個擴展的圖旋轉系統ρ（G）給出了圖G的頂點集和邊集.另外，通過由一個叫做Face－Trace的算法［17］，我們可以唯一構造出從一個邊端點出發對應的面元素.因此，反復利用FaceTrace算法，可以構造出所有的面元素，從而重構出圖G在一個二維流形上的嵌入［17］.事實上，這種二維流形的重構是唯一的，如定理1所述.

定理1［17］一個擴展的圖的旋轉系統ρ（G）唯一確定了圖G在一有效二維流形上的嵌入，從而唯一確定了對應的二維流形.

網格建模中的操作是重要的，特別是對于擁有可靠與強大的用戶接口的建模系統.定理1為二維流形的網格建模操作問題提供了堅實的理論基礎.二維流形建模在建模操作上存在三個重要的問題，分別為完整性，穩固性與有效性.產生任何二維流形結構需要的操作都是從集合S中得到，那么稱集合S是操作上完備的.如果運用集合S中的操作于二維流形都能產生有效的二維流形結構，那么集合S的操作是穩固的.定理1將網格建模操作的健全與完備問題變成基于圖形旋轉系統的表示問題：只要能證明提出來的操作集合能創建所有且僅限于有效的圖形旋轉系統，那么就能保證操作集合的健全與完備.

2.2 完備與健全的操作集合

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

第一個操作是邊插入操作，簡單記作E-INSERT，設ρ（G）為一個圖形旋轉系統，u和v是G中的兩個頂點.在面拐角（＜u，x＞，＜u，x’＞）與（＜v，y＞，＜v，y’＞）間插入一條邊［u，v］，也就是在邊端＜u，x＞與＜u，x’＞間的旋轉點v處插入邊端＜u，v＞和在邊端＜v，y＞與＜v，y’＞間的旋轉點v處插入邊端＜v，u＞.與插入相反的為邊刪除操作，簡單記作E-DELETE.同樣設ρ（G）為一個圖形旋轉系統，e＝［u，v］為G中的一條邊，刪除邊e即在旋轉點u處刪除＜u，x＞和在v處刪除＜v，u＞.

其他主要的操作有創建頂點，簡單記作V-CREATE，此操作在旋轉系統中創建不帶邊的孤立點，對應相反的操作為移除點，V-REMOVE，是在旋轉系統中移除一個孤立點.

定 理 2 由 E-INSERT／E-DELETE 和V-CREATE／V-REMOVE組成的操作集合是完備與健全的.

證 操作集合明顯有健全性：在能夠表示有效二維流形結構的圖形旋轉系統上應用4種操作會產生有效的二維流形結構.

前面已經說明，任意二維流形S的多孔網格結構導出唯一的旋轉系統ρ（G）.先后運用一系列的EDELETE與V-REMOVE操作后，會得到沒有頂點與邊的空旋轉系統.反過來，即先后運用一系列的V-CREATE與E-INSERT操作后，會從一個空旋轉系統中重建旋轉系統ρ（G）.由此可見，通過一系列的集合中的操作能得到任何多孔網格結構，任意虧格的曲面也能通過本文提出的操作集合構造出來.證畢

與［2，8］中提出與研究的歐拉操作相比，本文提出的操作集合更加簡單、直觀、一致和更易于用戶使用且提出的集合僅由更少的操作組成.避免了系統層與用戶層及內部表示與拓撲完整性的不一致問題.

2.3 基于頂點的數據結構的實現

在鄰接表結構上實現 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’的兩個結點之間插入包含w的結點和在表示頂點w鏈表中分別包含y’與y’的兩個結點之間插入包含u的結點.同理，在表示頂點u鏈表中刪除w和表示頂點w鏈表中刪除u來在鄰接表結構上對邊［u，w］實行E-DELETE操作.最后，V-CREATE操作對應的是增加一個帶有空鏈表的新頂點到鄰接表中，VREMOVE操作則對應從鄰接表中移除一個帶有空鏈表的頂點.

在鄰接表上執行 V-CREATE與 V-REMOVE操作所需時間為一常數.而 E-INSERT 與E-DELETE操作執行時則需要查找對應兩個頂點的鏈表，當頂點的價很大時會很耗時.用平衡樹代替鏈表存儲與頂點相關的端點，E-INSERT與 E-DELETE操作執行的時間復雜度可以得到改進，只需樹大小的對數的時間復雜度［10］.此外，實現中，只需要增加一個邊表來支持對結構中邊端的有效查找.

2.4 基于邊的數據結構的實現

為了實現V-CREATE與V-REMOVE操作，需要在翼型邊線結構中引入輔助的頂點表.頂點表中包含頂點結點，其指針指向任意邊結點中端點v.孤立頂點包含空指針.實現V-CREATE操作只需簡單地往結構中增加一個帶空指針的新頂點結點.VREMOVE操作則是從結構中移除一個帶空指針的頂點結點.

在翼型邊線結構上執行E-INSERT與E-DELETE操作算法見圖3，其中子程序FaceTrace即是文獻［17］中的FaceTrace的算法.從一個邊端點出發，子程序FaceTrace構造出對應的面元素.操作E-INSERT是在面拐角c1＝（＜u，x＞，＜u，x’＞）與c2＝ （＜w，y＞，＜w，y’＞）間插入一條邊＜u，w＞，操作E-DELETE則是刪除邊e.執行操作后，相關邊的ncw，pcw，，nccw，pccw部分會更新.需要解釋的是對fcw與fccw的更新.首先考慮E-INSERT，如果面拐角c1與c2屬于不同的面，那么在它們之間插入邊e＝［u，v］的操作得到的一個新面會代替網格中的兩個面，這個新面的邊界包含e的邊端＜u，w＞與＜w，u＞.這種情形下，步驟5中子程序FaceTrace（＜u，w＞）會跟蹤新面的邊界并適時更新有關邊結點中面部分的信息.特別地，步驟6中子程序FaceTrace不會執行.另一方面，如果面拐角c1與c2屬于同一面，那么在它們之間插入邊e＝［u，v］的操作得到的兩個新面會代替網格中的一個面，這兩個新面的邊界包含e的邊端＜u，w＞與＜w，u＞.這種情形下，步驟5中子程序Face－Trace會跟蹤一個新面的邊界并適時更新有關邊結點中面部分的信息.步驟6中子程序FaceTrace則會跟蹤另一個新面的邊界并適時更新有關邊結點中面部分的信息.

圖3 翼邊結構的E-INSERT和E-DELETE算法Fig.3 E-INSERT and E-DELETE on winged-edge structure

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

算法E-INSERT與E-DELETE的時間復雜度分析.由于每個算法都需執行一個或兩個時間復雜度正比于相關面大小的FaceTrace子程序，當面較小時（如在三角化網格上）耗時較小，在面很大的情況下，將耗費大量時間.可以得到定理3的結論.

定理3 對于一般的翼型邊線結構，算法E-INSERT與E-DELETE的運行時間復雜度為O（s），s是有關面的大小，特別地，對于沒有fcw與fccw信息部分的翼型邊線結構其算法E-INSERT與EDELETE的運行時間復雜度為O（1）.

在翼型邊線結構上執行E-INSERT與E-DELETE操作可容易地擴展到其他的基于邊的數據結構上.

2.5 基于面的數據結構的實現

DLFL結構有一個面表，一個邊表和一個頂點表.面表中每個面結點是對應面邊界的邊端序列，邊表中每個邊結點有兩個指向面表中對應的邊端的指針，而頂點表中的每個頂點結點則有一個指向面表中以該頂點為極的邊端的指針.

V-CREATE與V-REMOVE操作實現是簡單的.V-CREATE（v）創建面表中面邊界退化為單個頂點v的面結點，也創建頂點表中的頂點結點，這個結點的指針指向相應的新面.V-REMOVE操作則從面表中移除一個面邊界退化為單個頂點v的面結點，也移除頂點表中的表示v的頂點結點.

在DLFL結構上實現E-INSERT和E-DELETE的算法，如圖4所示，其正確性可從前面的證明得到檢驗.下面考慮算法的時間復雜度.

既然邊表中的邊結點有兩個指向面表中的邊端的指針，對于每條邊，可以在時間為常數的情形下，從面表中獲取它的端點.對于面表中的每個面結點f，有一個包含端點的循環鏈表與面邊界對應.如果采用平衡樹結構實現這個循環鏈表（如2－3樹結構［1］）那么檢測兩個端點是否屬于同一個面，把一個端點表分為兩個，合并兩個端點表的操作均可以在時間復雜度為O（s）下完成，s是有關面的大小（更多的細節描述與檢驗見［17］）.注意到，每次在DLFL結構上執行E-INSERT與E-DELETE算法都是由一個或多個檢測測端點表，分離與合并操作組成.因此，在實現面結點端點表的循環鏈表下，算法E-INSERT與E-DELETE的運行時間復雜度限制為O（log s）.結論如定理4所示.

定理 4 在 DLFL 結構上，V-CEATE 與V-REMOVE操作運行時間復雜度限定為O（1），EINSERT與E-DELETE操作的運行時間復雜度限制為O（log s），s是有關面的大小（至多涉及兩個面）.

同時指出在DLFL結構上實現V-CEATE，VREMOVE，E-INSERT與E-DELETE操作，它們的運行時間復雜度與有關頂點的價無關.

圖4 DLFL的E-INSERT和 E-DELETE算法Fig.4 E-INSERT and E-DELETE on DLFL structure

3 實驗結果

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

4 結 論

帶有一個簡單而強大的用戶接口的健壯的網格拓撲建模是計算機圖形學與計算機輔助幾何設計中的重點.本文研究了包括對二維流形網格建模的表示，數據結構與操作的一些基本問題.拓展了圖形旋轉系統在拓撲圖論的理論研究并表明擴展了的圖形旋轉系統為二維流形網格建模提供了一個堅實的理論基礎.在此基礎上，提出了一種新的二維流形網格建模操作集合，并且證明這個操作集合是完備與健全的，通過這個集合中的操作序列能構造任意的二維流形網格結構.此外，本文還介紹了在基于點，邊和面的數據結構上能有效地實現本文的操作.

圖5 長方體、正四面體和帶柄方體結構及其對應的一次細分算法結果Fig.5 Cuboid，regular tetrahedron and cube with handle and their corresponding subdivision results

［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］.計算機輔助設計與圖形學學報，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 1997Symposium on Interactive 3DGraphics.ACM，1997：155－162.

［13］張曄芝，谷士文，費耀平.基于圖形旋轉系統的漸進網格研究［J］.湖南大學學報：自然科學版，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＇09ACM SIGGRAPH 2009Papers.ACM，2009：78－83.

［17］費耀平，陳松喬，李敏.二維流形建模系統的拓撲有效性測試算法［J］.計算機輔助設計與圖形學學報，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）

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）

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 proof was 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.

Euler operation；shape modeling；2-manifold；mesh-structure

TP 301

A

1674-2974（2014）05-0118-07

2013-11-01

新世紀優秀人才支持計劃資助項目（NCET-12-0547）

費耀平（1959－），男，河北平山人，中南大學教授

?通訊聯系人，E-mail：limin＠mail.csu.edu.cn