基于半邊結構細分曲面的研究與實現

楊　龍　代　媛　何東健

摘 要：作為CAD和計算機輔助幾何設計的重要技術之一，細分曲面為實體造型提供了新的離散造型方法。在闡述細分曲面主要思想基礎上，采用Catmull－Clark四邊形模式介紹細分曲面生成算法；并用半邊結構表示和存儲實體的面、邊和點之間的拓撲關系。以Catmull－Clark模式為例基于半邊數據結構演示細分曲面的生成。結果表明，細分曲面具有規則簡單、易于實現、且在適當數據結構支持下僅需較少初始控制網格信息就可得到極限曲面的優點，因而細分曲面技術成為三維實體造型的一種有效途徑。

關鍵詞：細分曲面；CAGD；Catmull－Clark模式；半邊結構

中圖分類號：TP391 文獻標識碼：B 文章編號：1004－373X(2009)04－099－03

Research and Implementation of Sub－division Surface Based on Half－edge Structure

YANG Long,DAI Yuan,HE Dongjian

(Northwest A & F University,Yangling,712100,China)

Abstract：Subdivision surface as an important technology of CAD and CAGD,a new discrete method for geometric solid modeling is provided.The main thought of subdivision is illuminatad,Catmull－Clark mode is adopted to introduce the algorithm of subdivision surface.The topological relationship among face,edge and vertex of solids is represented and stored based on Half－Edge structure.The example of subdivision surface is demonstrated through Catmull－Clark mode.The result shows that the rule of subdivision surface is simple and easy to implement and it only needs less information of the original control net to get the limit surface as long as supported by proper data structure.Therefore,subdivision surface becomes an effective approach of 3D solid modeling.

Keywords：subdivision surface;CAGD;Catmull－Clark mode;half－edge structure

0 引 言

隨著計算機圖形學的發展和計算機輔助幾何設計(CAGD)在工業和形體設計中的廣泛應用，實體造型中幾何對象的多樣性、復雜性和拓撲結構任意性趨勢日益明顯，用戶對圖形系統顯示的真實性、實時性和交互性要求越來越高，以傳統的曲面造型技術為主的實體造型方法已逐漸不能滿足上述要求。而細分技術［1］是一種全新的形體表示思路。

細分技術可以用較少的數據量和簡單的規則表示復雜的幾何形體。它具有拓撲任意性、仿射不變性、數值穩定性、表示一致性以及規則簡單性等良好性質,因此細分造型技術已作為重要的實體造型手段而得到了廣泛的研究與應用。從飛機、輪船、汽車到家電、服裝等工業品，甚至山脈、云、江河等自然現象；從靜態模擬到動態仿真、細分都以其簡潔的表示、處理任意拓撲的能力使得細分技術成為了幾何造型領域最活躍的研究熱點之一。

1 細分技術

細分技術成為曲線曲面造型領域的一種重要方法,特別是近些年，細分概念在一些復雜形體表示與設計、動畫制作、工業設計以及虛擬現實等方面的成功應用使得細分技術在實體造型中大有后來居上之勢。

細分是一種基于多邊形或多面體的技術，指對初始控制網格依據一定的細分規則通過不斷細化產生光滑的極限曲線或曲面的過程。與傳統連續曲線曲面造型方法相比，它只需記錄少量的初始信息，在指定的規則下通過若干次分割初始控制網格就可以得到滿意精度的結果曲線或曲面，是一種易于計算機直接生成的離散造型技術。

1.1 細分曲面

細分曲面［2］是從給定的初始控制網格M0出發（一般為多面體），遞歸地調用細分規則Sj 加密控制網格,即Mj+1 =SjM j ,依次可得到M1,M2,…，最終在極限意義下，即當j → ∞ 時，網格序列收斂到結果曲面R = M∞ 上。根據細分規則S j 的不同，曲面R 或者插值或者逼近M0 。而且,通常規則Sj 具有局部性，Mj+1 中的頂點是Mj 中對應有限個控制頂點的仿射組合。細分曲面可理解為是一種過程化、層次化的采樣技術，它將形體屬性巧妙地轉換成了細分規則。

細分曲面的主要處理過程為：從初始的控制網格開始，按照某種規則，遞歸地產生新點逐漸加密控制網格。隨著細分不斷進行，控制網格被逐漸磨光，最終生成離散點插值或逼近的光滑的曲面。常見的細分曲面方法有：Catmull－Clark四邊形細分模式；Doo－Sabin四邊形模式［3］；Loop三角形模式［4］；Butterfly三角形模式［5］等。

1.2 Catmull－Clark細分模式

Catmull－Clark模式［6］是一種基于四邊形網格的1～4面分裂靜態逼近細分割模式。當初始控制網格為任意多邊形時，可對其做1次分割得到四邊形網格，再采用細分算法進行遞歸細分。其細分規則如下：

(1) F－頂點(面點)：如圖1（a）所示，設四邊形面的4個頂點為V0，V1，V2，V3，則相應的FВ頂點取為：

ИVF=(V0+V1+V2+V3)／4И

(2) E－頂點(邊點)：如圖1（b），設內部邊的端點為V0，V1，共享此邊的2個四邊形面分別為(V0，V1，V2，V3)和(V0，V1，V4，V5)，則與此內部邊相對應的E－Фサ鬮：

ИVE=（3／8）(V0+ V1)+（1／16）?

(V2+V3+V4+V5)И

(3) V－頂點：如圖1（c），若內部頂點V的一環的邊界頂點依次為V0，V1，… ，V2n-1，其中偶數下標的頂點為鄰點，奇數下標的頂點為其四邊形面上的對角頂點，相應的VВ頂點為：

ИVv=anV+βnn∑n－1i=1V2i+γnn∑n－1i=0V2i+1И

其中：權值為Е耼 = 3／(2n)；γn = 1／(4n)；αn= 1-βn-γn。

(4) 邊界邊(V0，V1)上的EВ頂點如圖1（d）所示。

ИV E =（1／2）(V0+V1)И

(5) 邊界邊(V0，V1)上的V－頂點：如圖1（e）所示。

ИVv=（1／8）(V0+V1)+（3／4）VИ

1.3 半邊結構

如何記錄幾何實體中面、邊和點間的拓撲關系，對提高曲面生成效率，減少數據冗余，有著重要影響。因此，細分曲面數據結構的研究對曲面的有效生成有著重要意義。

圖1 Catmull－Clark細分規則

Martti Mantyla提出的以邊為核心組織數據的半邊結構［7］(Half－Edge Structure)能有效表示幾何模型的拓撲關系。在半邊結構中,將1條邊一分為二,其中一條半邊屬于它一個相鄰面的邊環,而另一條半邊屬于它另一個相鄰面的邊環(如圖2所示)。每一條半邊僅存儲它的起點指針,這樣2條半邊就能夠表示1條邊的2個端點,當搜索1個面的各端點時,只需沿著半邊順序遍歷即可。

圖2 半邊結構

半邊結構是一個多能的邊界表示法，存儲了非常明確的朝向信息在網格幾何體中。它可以高效地找出點、邊、面等幾何元素間的連接關系，能實現非常快的鄰接查詢。而且半邊網格結構運行也相當迅速，包圍1個頂點的邊的查詢，面面相臨，所有這些都能夠實時的完成耗時也只是常數時間［8］。

采用半邊數據結構可以精確表示物體，其具有覆蓋域大，表示能力強，容易確定幾何元素間的連接關系，幾何變換比較容易，繪制速度快的優點。

2 細分曲面的實現

在VC++中OpenGL環境下，采用半邊結構定義3個結構體分別記錄頂點結構、邊結構和面結構：

struct HE_vert

{

float x;

float y;

float z;

HE_edge* edge; //one of the half－edge emanating

from the vertex

};

struct HE_edge

{

HE_vert* vert; //vertex at the end of the half_edge

HE_edge* pair; //oppositely oriented adjacent half

_edge

HE_face* face; //face the half－edge borders

HE_edge* next; //next half－edge around the face

};

struct HE_face

{

HE_edge* edge;//one of the half－edges bordering the face

};

按Catmull－Clark規則對初始單位正方體控制網格進行細分割，初始控制網格和第一次細分、第二次細分結果如圖3所示。圖4顯示結果為經過5次細分割后的曲面，經多次細分后其逼近極限曲面為球面。

圖3 初始單位正方體及前兩次細分后所得曲面

圖4 第5次細分后所得曲面

由于采用半邊數據結構表示實體，僅需要存儲實體的頂點信息、邊信息和面信息就能較容易地求得新的面點、邊點和頂點，以及它們之間的拓撲關系。隨著細分次數的增加和數據量增多，其具有比一般矩陣標記法節省存儲空間，查找效率高的優點。

3 結 語

結合半邊數據結構對細分曲面造型技術進行討論。說明細分曲面方法在適當的數據結構支持下能夠有效地實現幾何形體的離散造型，且具有拓撲任意性、仿射不變性、數值穩定性以及規則簡單、易于實現的優點。因此，細分曲面技術已經成為新的實體造型的重要手段。當前許多新的細分模式被不斷的提出，尤其在表示一些拓撲復雜的三維實體時，在一些特殊點的連續性處理問題上以及數值穩定性方面，其展現了傳統造型方法無法比擬的優勢。

參 考 文 獻

［1］鄧軍民，賓鴻贊，區士頎,等.細分造型技術在CAD系統中的應用研究［J］.光學精密工程,2002,10(2):226－230.

［2］鄭立垠，周笑天，于萍,等.基于Euler 操作的四邊形網格細分算法設計與實現［J］.計算機工程與設計,2007,28(3):3 151－3 156.

［3］Doo D,Sabin M.Behaviour of Recursive Division Surfaces near Extraordinary Points.CAD,1978,10(6):356－360.

［4］Loop C.Smooth Subdivision Surfaces Based on Triangles［D］.Utah:University of Utah,Department of Mathematics,1987.

［5］Nira Dyn,David Levin.The Subdivision Experience.In Curves and Surfaces II,1991:1－17.

［6］Catmull E,Clark J.Recursively Generated B－spline Surfaces on Arbitrary Topological Meshes.AD,1978,10(6):350－355.

［7］嚴寧，李啟炎.半邊結構的三維實體在OpenGL中的表示［J］.微型電腦應用,2002,18(9):51－53.

［8］Max McGuire.The Half－edge Data Structure ［EB/OL］.http://www.flipcode.com/articles/article_halfedge.shtml.2000.8.

［9］胡海龍,劉樹群.Catmull－Clark細分曲面的紋理映射技術.微計算機信息,2007(18):274－281,282.

［10］陳旭.Catmull－Clark曲面控制網格的收斂性質.數學研究,2007,40(4):386－391.

作者簡介 楊 龍 男，1982年出生，陜西岐山人，碩士研究生。主要從事圖形學、虛擬現實技術的研究。

代 媛 女，1981年出生，碩士研究生。主要從事智能化檢測與監控系統的研究。

何東健 男，1957年出生，博士，教授，博士生導師。主要從事圖像分析與識別、智能化檢測與控制及虛擬現實技術應用等研究工作。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。