基于半邊結(jié)構(gòu)細(xì)分曲面的研究與實(shí)現(xiàn)

楊　龍　代　媛　何東健

摘 要：作為CAD和計(jì)算機(jī)輔助幾何設(shè)計(jì)的重要技術(shù)之一，細(xì)分曲面為實(shí)體造型提供了新的離散造型方法。在闡述細(xì)分曲面主要思想基礎(chǔ)上，采用Catmull－Clark四邊形模式介紹細(xì)分曲面生成算法；并用半邊結(jié)構(gòu)表示和存儲(chǔ)實(shí)體的面、邊和點(diǎn)之間的拓?fù)潢P(guān)系。以Catmull－Clark模式為例基于半邊數(shù)據(jù)結(jié)構(gòu)演示細(xì)分曲面的生成。結(jié)果表明，細(xì)分曲面具有規(guī)則簡(jiǎn)單、易于實(shí)現(xiàn)、且在適當(dāng)數(shù)據(jù)結(jié)構(gòu)支持下僅需較少初始控制網(wǎng)格信息就可得到極限曲面的優(yōu)點(diǎn)，因而細(xì)分曲面技術(shù)成為三維實(shí)體造型的一種有效途徑。

關(guān)鍵詞：細(xì)分曲面；CAGD；Catmull－Clark模式；半邊結(jié)構(gòu)

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：B 文章編號(hào)：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 引 言

隨著計(jì)算機(jī)圖形學(xué)的發(fā)展和計(jì)算機(jī)輔助幾何設(shè)計(jì)(CAGD)在工業(yè)和形體設(shè)計(jì)中的廣泛應(yīng)用，實(shí)體造型中幾何對(duì)象的多樣性、復(fù)雜性和拓?fù)浣Y(jié)構(gòu)任意性趨勢(shì)日益明顯，用戶對(duì)圖形系統(tǒng)顯示的真實(shí)性、實(shí)時(shí)性和交互性要求越來越高，以傳統(tǒng)的曲面造型技術(shù)為主的實(shí)體造型方法已逐漸不能滿足上述要求。而細(xì)分技術(shù)［1］是一種全新的形體表示思路。

細(xì)分技術(shù)可以用較少的數(shù)據(jù)量和簡(jiǎn)單的規(guī)則表示復(fù)雜的幾何形體。它具有拓?fù)淙我庑?、仿射不變性、?shù)值穩(wěn)定性、表示一致性以及規(guī)則簡(jiǎn)單性等良好性質(zhì),因此細(xì)分造型技術(shù)已作為重要的實(shí)體造型手段而得到了廣泛的研究與應(yīng)用。從飛機(jī)、輪船、汽車到家電、服裝等工業(yè)品，甚至山脈、云、江河等自然現(xiàn)象；從靜態(tài)模擬到動(dòng)態(tài)仿真、細(xì)分都以其簡(jiǎn)潔的表示、處理任意拓?fù)涞哪芰κ沟眉?xì)分技術(shù)成為了幾何造型領(lǐng)域最活躍的研究熱點(diǎn)之一。

1 細(xì)分技術(shù)

細(xì)分技術(shù)成為曲線曲面造型領(lǐng)域的一種重要方法,特別是近些年，細(xì)分概念在一些復(fù)雜形體表示與設(shè)計(jì)、動(dòng)畫制作、工業(yè)設(shè)計(jì)以及虛擬現(xiàn)實(shí)等方面的成功應(yīng)用使得細(xì)分技術(shù)在實(shí)體造型中大有后來居上之勢(shì)。

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

1.1 細(xì)分曲面

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

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

1.2 Catmull－Clark細(xì)分模式

Catmull－Clark模式［6］是一種基于四邊形網(wǎng)格的1～4面分裂靜態(tài)逼近細(xì)分割模式。當(dāng)初始控制網(wǎng)格為任意多邊形時(shí)，可對(duì)其做1次分割得到四邊形網(wǎng)格，再采用細(xì)分算法進(jìn)行遞歸細(xì)分。其細(xì)分規(guī)則如下：

(1) F－頂點(diǎn)(面點(diǎn))：如圖1（a）所示，設(shè)四邊形面的4個(gè)頂點(diǎn)為V0，V1，V2，V3，則相應(yīng)的FВ頂點(diǎn)取為：

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

(2) E－頂點(diǎn)(邊點(diǎn))：如圖1（b），設(shè)內(nèi)部邊的端點(diǎn)為V0，V1，共享此邊的2個(gè)四邊形面分別為(V0，V1，V2，V3)和(V0，V1，V4，V5)，則與此內(nèi)部邊相對(duì)應(yīng)的E－Фサ鬮：

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

(V2+V3+V4+V5)И

(3) V－頂點(diǎn)：如圖1（c），若內(nèi)部頂點(diǎn)V的一環(huán)的邊界頂點(diǎn)依次為V0，V1，… ，V2n-1，其中偶數(shù)下標(biāo)的頂點(diǎn)為鄰點(diǎn)，奇數(shù)下標(biāo)的頂點(diǎn)為其四邊形面上的對(duì)角頂點(diǎn)，相應(yīng)的VВ頂點(diǎn)為：

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

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

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

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

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

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

1.3 半邊結(jié)構(gòu)

如何記錄幾何實(shí)體中面、邊和點(diǎn)間的拓?fù)潢P(guān)系，對(duì)提高曲面生成效率，減少數(shù)據(jù)冗余，有著重要影響。因此，細(xì)分曲面數(shù)據(jù)結(jié)構(gòu)的研究對(duì)曲面的有效生成有著重要意義。

圖1 Catmull－Clark細(xì)分規(guī)則

Martti Mantyla提出的以邊為核心組織數(shù)據(jù)的半邊結(jié)構(gòu)［7］(Half－Edge Structure)能有效表示幾何模型的拓?fù)潢P(guān)系。在半邊結(jié)構(gòu)中,將1條邊一分為二,其中一條半邊屬于它一個(gè)相鄰面的邊環(huán),而另一條半邊屬于它另一個(gè)相鄰面的邊環(huán)(如圖2所示)。每一條半邊僅存儲(chǔ)它的起點(diǎn)指針,這樣2條半邊就能夠表示1條邊的2個(gè)端點(diǎn),當(dāng)搜索1個(gè)面的各端點(diǎn)時(shí),只需沿著半邊順序遍歷即可。

圖2 半邊結(jié)構(gòu)

半邊結(jié)構(gòu)是一個(gè)多能的邊界表示法，存儲(chǔ)了非常明確的朝向信息在網(wǎng)格幾何體中。它可以高效地找出點(diǎn)、邊、面等幾何元素間的連接關(guān)系，能實(shí)現(xiàn)非?？斓泥徑硬樵?。而且半邊網(wǎng)格結(jié)構(gòu)運(yùn)行也相當(dāng)迅速，包圍1個(gè)頂點(diǎn)的邊的查詢，面面相臨，所有這些都能夠?qū)崟r(shí)的完成耗時(shí)也只是常數(shù)時(shí)間［8］。

采用半邊數(shù)據(jù)結(jié)構(gòu)可以精確表示物體，其具有覆蓋域大，表示能力強(qiáng)，容易確定幾何元素間的連接關(guān)系，幾何變換比較容易，繪制速度快的優(yōu)點(diǎn)。

2 細(xì)分曲面的實(shí)現(xiàn)

在VC++中OpenGL環(huán)境下，采用半邊結(jié)構(gòu)定義3個(gè)結(jié)構(gòu)體分別記錄頂點(diǎn)結(jié)構(gòu)、邊結(jié)構(gòu)和面結(jié)構(gòu)：

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規(guī)則對(duì)初始單位正方體控制網(wǎng)格進(jìn)行細(xì)分割，初始控制網(wǎng)格和第一次細(xì)分、第二次細(xì)分結(jié)果如圖3所示。圖4顯示結(jié)果為經(jīng)過5次細(xì)分割后的曲面，經(jīng)多次細(xì)分后其逼近極限曲面為球面。

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

圖4 第5次細(xì)分后所得曲面

由于采用半邊數(shù)據(jù)結(jié)構(gòu)表示實(shí)體，僅需要存儲(chǔ)實(shí)體的頂點(diǎn)信息、邊信息和面信息就能較容易地求得新的面點(diǎn)、邊點(diǎn)和頂點(diǎn)，以及它們之間的拓?fù)潢P(guān)系。隨著細(xì)分次數(shù)的增加和數(shù)據(jù)量增多，其具有比一般矩陣標(biāo)記法節(jié)省存儲(chǔ)空間，查找效率高的優(yōu)點(diǎn)。

3 結(jié) 語

結(jié)合半邊數(shù)據(jù)結(jié)構(gòu)對(duì)細(xì)分曲面造型技術(shù)進(jìn)行討論。說明細(xì)分曲面方法在適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)支持下能夠有效地實(shí)現(xiàn)幾何形體的離散造型，且具有拓?fù)淙我庑?、仿射不變性、?shù)值穩(wěn)定性以及規(guī)則簡(jiǎn)單、易于實(shí)現(xiàn)的優(yōu)點(diǎn)。因此，細(xì)分曲面技術(shù)已經(jīng)成為新的實(shí)體造型的重要手段。當(dāng)前許多新的細(xì)分模式被不斷的提出，尤其在表示一些拓?fù)鋸?fù)雜的三維實(shí)體時(shí)，在一些特殊點(diǎn)的連續(xù)性處理問題上以及數(shù)值穩(wěn)定性方面，其展現(xiàn)了傳統(tǒng)造型方法無法比擬的優(yōu)勢(shì)。

參 考 文 獻(xiàn)

［1］鄧軍民，賓鴻贊，區(qū)士頎,等.細(xì)分造型技術(shù)在CAD系統(tǒng)中的應(yīng)用研究［J］.光學(xué)精密工程,2002,10(2):226－230.

［2］鄭立垠，周笑天，于萍,等.基于Euler 操作的四邊形網(wǎng)格細(xì)分算法設(shè)計(jì)與實(shí)現(xiàn)［J］.計(jì)算機(jī)工程與設(shè)計(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］嚴(yán)寧，李啟炎.半邊結(jié)構(gòu)的三維實(shí)體在OpenGL中的表示［J］.微型電腦應(yīng)用,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細(xì)分曲面的紋理映射技術(shù).微計(jì)算機(jī)信息,2007(18):274－281,282.

［10］陳旭.Catmull－Clark曲面控制網(wǎng)格的收斂性質(zhì).數(shù)學(xué)研究,2007,40(4):386－391.

作者簡(jiǎn)介 楊 龍 男，1982年出生，陜西岐山人，碩士研究生。主要從事圖形學(xué)、虛擬現(xiàn)實(shí)技術(shù)的研究。

代 媛 女，1981年出生，碩士研究生。主要從事智能化檢測(cè)與監(jiān)控系統(tǒng)的研究。

何東健 男，1957年出生，博士，教授，博士生導(dǎo)師。主要從事圖像分析與識(shí)別、智能化檢測(cè)與控制及虛擬現(xiàn)實(shí)技術(shù)應(yīng)用等研究工作。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。