基于半边结构细分曲面的研究与实现

摘 要：作为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И

其中：权值为Еn = 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］./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格式阅读原文。