（计算机应用技术专业论文）基于细分曲面造型的研究.pdf

中文摘要 细分方法是一种新的离散造型技术，细分曲面通过定义控制网格的细分规则来 表示造型曲面。随着细分理论的不断发展，应用领域不断拓宽，细分曲面造型方法 已逐渐形成了自己的独立的学科体系。原有的细分曲面造型方法不断改进，新的细 分曲面造型方法层出不穷。同时，它与小波变换、多分辨率分析等理论结合起来， 获得了新的发展动力，呈现了强大的生命力，已经成为继n u r b s 之后的一种重要的 自由曲面造型方法。因此，曲面造型是c a d 、c g 中的一项重要内容，在工业技术领 域中有广泛的应用。 本文分析了常用曲面细分方法，总结了细分曲面的特点及它们的不足之处；针 对目前细分曲面的不足，根据线性代数中的判别准则：当空间三个向量线性相关时， 则这三个向量在同一平面上，提出了向量线性相关的三角网格自适应l o o p 细分方法。 该方法算法简单、时间效率高( 尤其对大量的数据点来说) ，提高了模型的处理速度， 大量实例证明了这些方法具有很好的应用前景。 法矢量和曲率作为重要的微分几何特征，描述了三角网格的局部几何特征，它 们直接关系到细分算法的精确度，在曲面造型中的地位非常重要。本文利用一种新 的面积角度加权顶点法矢计算公式，对吴剑煌等提出的顶点平坦度方法进行了改进， 提出了一种新的顶点法矢计算方法，它综合考虑了三角面片的面积和形状对三角网 格顶点法矢的影响，使顶点法矢的计算结果更为准确，也使求顶点平坦度的算法得 到了优化。 小波技术是一种可用于函数多层次分解和重构的数学工具，多分辨率分析是通 过小波变换来实现的，本文将小波变换和表面细分算法相结合，利用小波对细分曲 面进行后期处理，使得在不影响三维图形显示效果的情况下，尽可能减少三维模型 的数据量，提高了表面细分和重构的效率。 关键词：曲面造型；自适应细分l o o p 方法；顶点平坦度；向量线性相关；多分辨率分 析 b a s e do nt h es u r f a c em o d e l i n go fs u b d i v i s i o ns t u d y g r a d u a t en a m e ：w a n gy a n y a n m a jo r ：c o m p m e ra p p l i c a t i o nt e c h n o l o g y d i r e c t e db y ：z h a n gr o n g g u o a b s t r a c t s u b d i v i s i o ni san e wm e t h o do fd i s c r e t e m o d e l i n g b yd e f i n i n g t h e r e f i n e m e n tr u l e so fc o n t r o lm e s h e s ，s u b d i v i s i o ns u r f a c ec a nb ec o n s i d e r e da s am e t h o do fs u r f a c em o d e l i n g w i t hd e v e l o p m e n to ft h e o r ya n dw i d e n i n g s c o p eo fa p p l i c a t i o n ，t h es u b d i v i s i o ns u r f a c em o d e l i n gm e t h o dh a sg r a d u a l l y f o r m e di t so w ni n d e p e n d e n td i s c i p l i n a r y s y s t e m t h es u r f a c em o d e l i n g m e t h o di si m p r o v e d ；an e ws u b d i v i s i o ns u r f a c em o d e l i n gm e t h o di se n d l e s s a tt h es a m et i m e ，c o m b i n e dw i t hs o m en e wm a t h e m a t i c st h e o r i e s ，s u c ha st h e w a v e l e t ，t h em u l t i r e s o l u t i o na n a l y s i sa n ds oo n ，i th a so b t a i n e df l s t r o n g v i t a l i t y , a n db e c a m eo n ei m p o r t a n tf r e es u r f a c em o d e l i n gm e t h o df o l l o w e d n u r b s t h e r e f o r e ，t h es u r f a c em o d e l i n gi sa ni m p o r t a n te l e m e n ti nt h ec a d ， c gi th a saw i d ea p p l i c a t i o n si nt h ef i e l do fi n d u s t r i a lt e c h n o l o g y t h ee x i t i n gs u b d i v i s i o nh a sb e e na n a l y z e d ，t h e i rc h a r a c t e r i s t i ca n dt h e i r d e f i c i e n c yw e r es u m m a r i z e d b a s e do nt h el i n e a ra l g e b r ac r i t e r i o nt h a tt h r e e v e c t o r s o r i g i n a t i n gf r o ma v e r t e xb e i n gl i n e a rd e p e n d e n c ea r ec o p l a n a r , an e w a d a p t i v es u b d i v i s i o ns c h e m ei sp r e s e n t e d t h i sm e t h o da l g o r i t h mi ss i m p l e a n dh i 曲e f f i c i e n c y ( e s p e c i a l l yt om a s s i v ed a t ap o i n t s ) ，a n dt h em o d e l p r o c e s s i n gs p e e di sr a i s e d m a n yi n s t a n c e sh a dp r o v e nt h e s em e t h o d sh a v ea v e r yg o o da p p l i c a t i o np r o s p e c t t h ev e c t o ra n dc u r v a t u r ea r e i m p o r t a n tc h a r a c t e r i s t i c s o fd i f f e r e n t i a l g e o m e t r y ；t h e yd e s c r i b e dt h et r i a n g u l a rg r i do ft h el o c a lg e o m e t r yf e a t u r e t h e ya r ei n t i m a t e l yr e l a t e dt ot h ep r e c i s i o no ft h es u b d i v i s i o na l g o r i t h m ，a n d a r ev e r ys i g n i f i c a n ti nt h ep o s i t i o no fs u r f a c em o d e l i n g an o v e lf o r m u l af o r t h ee s t i m a t i o no ft r i a n g u l a rm e s hv e r t e xn o r m a lv e c t o ri sp r e s e n t e d i n s t e a d o fa r e aw e i g h t e d ，t h i sf o r m u l ai sa r e aa n da n g l ew e i g h t e d s o ，t h ef l a t n e s so f v e r t e xm e t h o db yw uj i a n h u a n gi si m p r o v e d t h ef o r m u l ac o n s i d e r e ds i z e a n ds h a p eo ft h et r i a n g u l a r 酣dv e r t e xo ft h ei m p a c to fv e c t o r , s ot h a tt h e v e r t e xv e c t o ro ft h er e s u l t sa r em o r ea c c u r a t ea n dt h ea l g o r i t h m sh a v eb e e n o p t i m i z e d w a v e l e ti sam u l t i 1 e v e lf u n c t i o n i tc a nb e u s e dt h em a t h e m a t i c a lt o o l sf o r d e c o m p o s i t i o na n dr e c o n s t r u c t i o n ，m u l t i r e s o l u t i o na n a l y s i si sc a r r i e do u tb y t h ew a v e l e tt r a n s f o r m t h i sa r t i c l ew i l li n t e g r a t ew a v e l e tt r a n s f o n nw i t h s u b d i v i s i o n ，u s i n gaw a v e l e tp o s t - p r o c e s s i n gf o r t h et h r e e d i m e n s i o n a lm o d e l w h i l e3 dw i l ln o tb ea f f e c t e dg r a p h i c sd i s p l a y , t h a ti sf a r t h e s tm i n i m i z et h e a m o u n to fd a t aa n di m p r o v et h es u b d i v i s i o na n dr e c o n s t r u c t i o ne f f i c i e n c y k e yw o r d s ：s u r f a c em o d e l i n g ；a d a p t i v el o o ps u b d i v i s i o ns c h e m e ；t h e f l a t n e s so fv e r t e x ；v e c t o rl i n e a rd e p e n d e n c e ；m u k i r e s o l u t i o na n a l y s i s 承诺 本人郑重声明：所呈交的学位论文，是在导师指导下 独立完成的，学位论文的知识产权属于太原科技大学。如 果今后以其他单位名义发表与在读期间学位论文相关的 内容，将承担法律责任。除文中已经注明引用的文献资料 外，本学位论文不包括任何其他个人或集体已经发表或撰 写过的成果。 学位论文作者( 签章) ：上轮禾兰 2 0 0 台年，月乒日 第一章绪论 第一章绪论 随着信息技术的快速发展，数字化己成为当今社会的主旋律，以数字声音、数 字图像、数字视频为代表的多媒体信息己渗透到现代社会的每一个角落，对人类生 活产生了深刻的影响。从技术发展的进程来看，多媒体信息的维数不断提高，出现 了以三维几何数据为代表的新型媒体形式，其互动性亦日益增强，鉴于这种三维媒 体在计算机辅助设计、虚拟现实和数字媒体等领域有着广阔的应用前景，如何高效 地获取和处理三维几何数据已成为当前计算机辅助设计和图形学研究最具挑战性的 问题之一。 由于多边形网格表示的简单性和普适性，以及与现代图形绘制流水线的兼容性， 多边形网格表示方法己成为三维几何媒体的主要表示形式。但其线性分片逼近特性， 使得该表示方法在刻画复杂细节表面时，往往需要大量的基本多边形，不仅导致巨 大的计算、存储耗费，而且还给后续处理带来了极大的困难。 本章将首先对形体的曲面表示方法进行简要介绍，然后介绍本论文的相关工作。 最后扼要介绍本文研究内容和主要创新点。 1 1 曲面造型的发展概况 曲面造型( s u r f a c em o d e l i n g ) 是c a d c a m ，c g 、计算机动画、计算机仿真、计 算机可视化等众多领域的一项重要内容，主要研究在计算机图像系统的环境下对曲 面的表示、设计、显示和分析。它起源于汽车、飞机、船舶、叶轮等的外形放样工 艺，由c o o n s 、b e z i e r 等大师于2 0 世纪6 0 年代奠定其理论基础。如今经过几十年的发 展，曲面造型现在已形成了以有理b 样条曲面( r a t i o n a lb s p l i n es u r f a c e ) 参数化特征 设计和隐式代数曲面( i m p l i c i t a l g e b r a i cs u r f a c e ) 表示这两类方法为主体，以插值 ( i n t e r p o l a t i o n ) 、拟合( f i t t i n g ) 、逼近( a p p r o x i m a t i o n ) 这三种手段为骨架的几何理论体 系f l l o 1 1 1 曲面造型的起源及特点比1 形状信息的核心问题是计算机表示，即要解决既适合计算机处理，且有效地满 足形状表示与几何设计要求，又便于形状信息传递和产品数据交换的形状描述的数 学方法。1 9 6 3 年美国波音飞机公司的f e r g u s o n 首先提出将曲线曲面表示为参数的矢 函数方法，并引人参数三次曲线。从此曲线曲面的参数化形式成为形状数学描述的 标准形式。1 9 6 4 年美国麻省理工学院的c o o n s 发表了一种具有一般性的曲面描述方 法，给定围成封闭曲线的四条边界就可定义一块曲面。但这种方法存在形状控制与 基于细分曲面造型的研究 连接问题。1 9 7 1 年法国雷诺汽车公司的b e z i e r 提出一种由控制多边形设计曲线的新 方法，这种方法简单易用。 曲面表示方法利用基本面元对实体的表面进行描述从而完成实体模型的构造， 是c a d & c g 中广泛采用的几何形体表示方法之一。按照基本面元的不同，曲面表示方 法可分为参数曲面表示、隐式曲面表示、多边形网格曲面表示以及其它表示方法等。 参数曲面使用连续的基函数，利用一组初始控制向量的线性( 或有理线性) 组合 来得到形体的连续表示。参数曲面的优点是赋值计算简单，易于离散且显示方便。 它适合于精确描述规则几何形状；又因与工业生产、国防建设密切相关，因此较早 受到关注，研究程度也最为深入，已经形成了以b e z i e r 和b 样条方法为代表，以插值、 拟合、逼近为主要处理手段的实用几何理论体系。但是，参数曲面在处理拼接和高 亏格曲面等问题时比较繁琐，表示具有丰富细节的复杂形体时比较困难。 隐式曲面由三维空间中的函数f ( x ，y ，z ) = 0 定义，具有几何求交容易，表 示封闭光滑形体方便等优点，在表现人体的肌肉、水滴、云、烟等物体的造型和动 画方面有很大的优势口3 。然而隐式曲面在表示丰富细节和尖锐特征时十分不便。 多边形网格直接使用点、直线段和平面面片来表示三维形体，数学原理简单， 容易理解，适合于绘制，配合纹理映射与光照材质，可以表现出极具真实感的绘制 效果。网格曲面具有表现丰富细节的能力，顺应了当前几何设计应用需求，适宜于 复杂形体造型，因此被越来越广泛地应用于三维几何媒体的表示。本文以网格曲面 作为主要研究对象。虽然光滑连续的几何模型可以给后续处理和工业生产带来方便， 但网格模型是分片线性的，所以，基于网格曲面的光滑连续曲面的构造问题必须妥 善解决： ( 1 ) 网格曲面的基本面元数量十分巨大，而且顶点之间几何无关，操控顶点或 面元的直接编辑方式不再适用，传统的f f d 方法又因易于造成细节丢失而不能很好地 运用于复杂细节网格模型的编辑，因此，寻找方便高效的编辑方法是当前网格曲面 造型的研究热点； ( 2 ) 参数曲面赋值计算简单、可精确表示规则形体等，在工业界被广泛使用， 因此，网格曲面向参数曲面转换是网格曲面模型步入工业生产的关键，寻找切实可 行的参数曲面重建方法是当前亟待解决的问题之一； 1 1 2 细分曲面造型的现状 随着几何设计对象向着多样性、特殊性和拓扑结构复杂性靠拢这一趋势日益明 显，随着图形工业和制造工业迈向一体化、集成化和网络化步伐的日益加快，随着 2 第一章绪论 激光测距扫描等三维数据采样技术和硬件设备的日益完善，曲面造型近几年得到了 长足的发展。这主要表现在研究领域的急剧扩展和表示方法的开拓创新两方面： ( 1 ) 从研究领域来看，曲面造型技术已从传统的研究曲面表示、曲面求交和曲面 拼接，扩充到曲面变形、曲面重建、曲面简化、曲面转换和曲面等距性。 ( 2 ) 从表示方法来看，以网格细分( s u b d i v i s i o n ) 为特征的离散造型与传统的连 续造型相比，大有后来居上的创新之势。 通常用参数曲面构造复杂拓扑结构的物体表面时，需要对曲面片进行剪裁或直接 在非规则的四边形网格上构造曲面片，无论哪种情况都要考虑片与片之间的光滑拼 接，这是很困难的。对于影视动画领域的活动模型，需要采用更加简便的方法来构 造任意拓扑结构曲面。 细分方法正是在这种情况下迅速发展起来，其基本思想是：采用一定的细分规 则，在给定的初始网格中渐进地插入新的顶点，从而不断细化出新的网格。重复运 用细分规则，在极限时，该网格收敛于一个光滑曲面。细分曲面就是由初始控制网 格按照一定的细分规则反复迭代而得到的极限曲面晦1 ，它具有以下优点：适应任意拓 扑结构、仿射不变、算法简洁、通用高效、应用规模可大可小。 正是由于细分曲面有着传统参数曲面所不具备的优点，现已广泛应用于计算机 辅助几何设计、计算机动画造型及商业造型软件等领域。 1 1 3 细分曲面造型的应用及发展趋势 随着对细分理论研究不断深入，针对细分曲面的应用研究也在多分辨率分析、 计算机动画、计算机图形学、科学计算可视化、数值计算、医学图象处理以及曲面 造型等领域逐步展开，细分曲面应用技术研究现状及发展趋势主要表现在如下几个 方面： ( 1 ) 基于细分的多分辨率分析 多分辨率分析的基本思想是把信号表示成低分辨率信号，同时生成一些能在不 同尺度上反映该信号的细节嘲。多分辨率模型( m u l t i r e s o l u t i o nm o d e l ) 也是一种曲 面表示方法，它支持物体表面从粗糙到细致的各个层次的模型重构。基于细分的多 分辨率分析，是把网格曲面看作是某一细分方法进行若干次细分后得到的结果，那 么该庞大的网格曲面就可以用一个简单的初始网格和若干细分规则来表示订1 。细分方 法通过拓扑规则提供了合理的加密采样模式，通过几何规则提供了合理的预测函数。 每次采样与预测之间存在误差，这就是多分辨率分析需要被保存的细节。这种扩展 的细分曲面，称为多分辨率曲面( m u l t i r e s o l u t i o ns u r f a c e ) 。 气 基于细分曲面造型的研究 在多分辨模型上可以根据需要在不同分辨率的控制网格上对控制顶点进行修 改，能够在局部修改曲面形状和全局修改曲面形状之间进行折衷选择，从而达到不 同的形状效果，这种曲面修改方式称为细分曲面多分辨率编辑口1 ，与计算机网络的结 合，将是基于细分的多分辨率曲面的一个重要研究方向。 ( 2 ) 三维动画造型 目前细分方法在影视动画、游戏等行业中的应用已相当普遍。这主要是因为， 用n u r b s 等参数曲面表示人的手、头和衣服皱褶等复杂拓扑对象时，需要由多片曲面 拼成，因此需要求解复杂的相容关系，当对象运动时原来的相容条件被破坏，需要 重新求解相容条件或者采用大量的手工操作以消除片之间的缝隙。对细分曲面来说， 由于细分曲面定义在任意拓扑网格上，所以不存在上述问题。曲面的光滑性也由细 分方法自动保证。在动画造型中需要解决的主要问题是特征生成i 形状保持以及纹 理映射。基于细分的变形( m o r p h i n g ) 技术是该方向上的研究热点，地形地貌的生成 与绘制也是实时动画中重要研究内容。 随着可编程图形加速硬件的出现，细分曲面的硬件实现将进一步提高细分速度， 同时也为细分曲面在三维动画与游戏中的应用提供更好的技术支持。 ( 3 ) 医学图像重建与模拟 q i nh o n g 等人提出将动态细分曲面( d y n a m i cs u b d i v i s i o ns u r f a c e ) 造型方法 用于医学图像重建与受力变形模拟。首先从三维核磁共振切片数据拟合小脑的 c a t m u l l 一c 1 a r k 细分曲面初始控制网格，然后建立拉格朗日动态力学模型，在此模型 的适当部位施加外力，通过计算模拟出不同外力下的的脑组织的变形结果。该方法 结合了细分方法对任意拓扑结构形体建模的灵活性与直观交互动态模拟曲面变形的 两方面优点。k a i h u a iq i n 也研究了类似的其它医学组织的细分曲面图像重建和模拟 方法。 ( 4 ) 工程曲面造型 虽然细分曲面在动画造型系统中已经获得了广泛的应用，但是在工程曲面造型 中的应用才刚刚起步，这是因为两种应用领域所追求的目标曲面要求不一样，动画 造型希望模型具有较好的光顺性等视觉效果：工程曲面造型要求模型具有较高的几 何精度和连续性等内在质量。这方面的应用研究主要包括：细分曲面的拟合、布尔运 算以及用细分方法解决参数曲面造型问题。 在c a d 领域中，常通过插值和逼近手段建立目标曲面。在细分曲面插值方面，己 有的细分曲面插值方法可以分为两类：一种是构造新的细分规则或修改已有的几何 4 第一章绪论 规则，使得细分曲面经过初始控制网格的部分或全部顶点；另一种则是利用己有细 分方法，通过构造适当的初始控制网格使细分曲面满足插值条件。虽然插值型细分 曲面( 如蝶形细分) 具有天生的插值能力，但是插值细分曲面的光顺性并不理想用细 分曲面精确表示几何模型仍然是细分曲面应用研究的重要内容。用细分方法解决其 它曲面造型方法中的问题，也是一个值得关注的应用方向。 1 2 课题的背景和意义 1 2 1 课题的背景 由于细分造型方法不受控制网格拓扑结构的限制，具有很强的曲面造型能力， 受到许多学者的关注，目前已是计算机图形学领域的一个研究热点。美国u t a h 大学 在这方面进行了较早的研究，提出了诸如c a t m u l l c l a r k 细分、l o o p 细分等著名的 细分方法；德国k a r l s r u h e 大学的p r a u t z s c h 和美国n e wy o r k 大学的z o r i n 系统分 析了静态细分方法的收敛性和连续性；美国a l i a s 公司的s t a i n 对细分曲面的几何 属性计算方法进行了深入地研究；美国p i x a r 公司的d e r o s e 等人成功地将 c a t m u l l c l a r k 细分用于三维动画造型。 国内直到2 0 0 0 年才有细分曲面方面的文章发表，也只是少数几所高校在这方面 进行了研究，其中清华大学的秦开怀等人研究了非均匀细分曲面连续性；浙江大学 的郑建民、张宏鑫、张纪文等人分别提出了非均匀递归细分方法、半静态细分方法、 基于c - b 样条的c a t m u l l - c l a r k 细分方法；南京航空航天大学王占东等人主要研究 了基于稀疏数据的细分曲面拟合方法。 由于细分理论还未完全成熟，仍在发展中，且己有的研究主要集中在理论方面。 要使细分曲面在c a d 领域得到真正的应用，还有很多问题需要研究，比如：如何根据 给定精度对细分曲面进行求交和布尔运算，如何使等距后的细分曲面仍然用细分曲 面精确表示，如何在光滑细分曲面上实现各种尖锐、半尖锐特征，如何用简洁的控 制网格去拟合带特征的复杂模型，如何用细分曲面表示高阶连续c a d 模型等等，均 是细分曲面应用于c a d 时需要解决的难点问题。 1 2 2 课题的意义 本文通过对细分曲面造型的方法进行研究，针对当前细分方法中存在的缺陷， 提出了一种新的自适应l o o p 细分方法：基于向量线性相关的自适应l o o p 细分方法， 该方法通过判断过同一项点的三条边是否线性相关，来判断该顶点是否平坦，从而 决定是否参与细分。该方法计算简便，具有较高的时间效率；利用卜邻域上三角形 基于细分曲面造型的研究 面积和形状对顶点法矢量影响，改进了原有的顶点法矢量计算公式，使得利用顶点 法矢量的曲面造型算法得到了优化。提高细分曲面的造型能力，扩展其应用范围。 本课题的研究对于探索基于细分的c a d 造型技术具有重要的工程意义。 利用小波对经过细分的曲面进行后期处理，把小波和l o o p 细分方法结合起来， 对三维模型进行多分辨率分析，使得在不影响三维模型显示的情况下，尽可能地降 低三维数据的存储量，减轻三维模型的网络传输负荷，提高三维模型的可视化效率。 在现有网络带宽和传输速度下，对图形的网络传输有着积极的影响，然而，小 波多分辨率分析在对三维图形处理方法还不成熟，本文也算做了一次大胆的尝试。 1 3 本文的主要内容 本文共分五章，各章的主要内容如下： 第一章，绪论。以细分方法的形成、发展、特点和细分曲面的应用为切入点， 阐述了目前该领域的发展概况。 第二章，叙述了细分理论基础与典型曲面细分方法。介绍了与细分方法密切相 关的数学基础和一些重要概念；对细分方法作了大概的介绍、分类、对其特点进行 了描述、对典型的细分方法作了大概的介绍，最后给出了选择细分方法的尺度和准 则。 第三章，本文针对当前存在的自适应细分方法算法复杂这个弊端，提出了一种新 的自适应l o o p 细分算法：向量线性相关的三角网格自适应l o o p 细分方法。据线性 代数中的判别准则：当空间三个向量线性相关时，则这三个向量在同一平面上， 提 出了一种新的l o o p 自适应细分方法；针对当前顶点法矢计算结果不符合实际这个 问题，利用一种新的面积角度加权顶点法矢计算公式对吴剑煌等提出的顶点平坦度 方法进行了改进，综合考虑了三角面片的面积和形状对三角网格顶点法矢的影响， 使顶点法矢的计算结果更为准确，也使求顶点平坦度的算法得到了优化。 第四章，利用梁俊提出的l o o p 细分小波对经过自适应l o o p 细分的曲面进行多分 辨率分析，它根据l o o p 细分算法的固有特征，对应于曲面简化和细化的双向处理。 实验证明用本算法来表示三维模型，可以降低三维数据的存储量，减轻三维模型的 网络传输负荷，提高三维模型的可视化效率。该方法有利于三维图形在网络上的渐 进传输，其基本思想是通过一定的传输策略，先传送粗糙的模型到客户端显示，再 不断补充细节信息来完善客户端的模型，最终完成模型整体的传输与绘制。它减少 了传输的总数据量和客户端等待的时间，提高了显示效果的真实性。这也是曲面构 6 第一章绪论 造的一个重要应用和发展前景之一。 第五章，总结与展望。总结全文的研究工作，并指出以后进一步研究方向。 7 基于细分曲面造型的研究 第二章细分理论基础与典型曲面细分方法 2 1 细分理论基础 2 1 1 基本概念 理论上的细分曲面是多边形网格无限细分后的极限状态，而在具体实现时只能 把它当作某一细分层次的多面体来考虑，细分方法所处理的就是多边形网格，因此 本文首先描述多边形网格的相关概念。 ( 1 ) 与网格相关的概念 定义2 1 由顶点、边和面构成的整个或部分多面体表面称为网格( m e s h ) 。如果 所有网格面均为三角形，称其为三角网格( t r i a n g u l a rm e s h ) ；如果所有网格面均为 四边形，称其为四边形网格( q u a d r i l a t e r a lm e s h ) ；如果网格面中包含有不同类型 的多边形面，则称为任意多边形网格( a r b i t r a r i l yp o l y g o n a lm e s h ) 。 定义2 2 如果网格的某一条边只属于一个面，称这条边为边界边( b o u n d a r y e d g e ) ；如果一个顶点处在边界边上则称此顶点为边界点( b o u n d a r yv e r t e x ) ；至少 包含一条边界边的面称为边界面( b o u n d a r yf a c e ) 。非边界的顶点、边和面分别称为 内部顶点( i n t e r n a lv e r t e x ) 、内部边( i n t e r n a le d g e ) 和内部面( i n t e r n a lf a c e ) 。 定义2 3 含有边界边的网格称为开网格( o p e nm e s h ) ，否则称之为闭网格( c l o s e m e s h ) 。 定义2 4 对于网格中的任意一个顶点以与其直接相连的边的数量称为顶点啪 价( v a l e n c e ) ，记为k 。 定义2 5 对于网格中的任意两个顶点虬和，如果存在最小的整数门，使得 边序列易，易e n 满足： k ，巧分别与易，和踟相连； 易与易q 相连，其中1 2 n _ l ；则称门为顶点k 与圪之间的距离。 定义2 6 对于网格中的任意一个顶点k ，以k 为中心，所有到k 的距离小于n 的顶点所构成的子网格，称为顶点k 的力一邻域( n - n e i g h b o r h o o d ) 。 定义2 7 对于网格中的任意一个多边形丁，以劝中心，所有到多边形啪距 离小于力的顶点所构成的子网格，称为多边形丁的n - 邻域。 定义2 8 正则点：网格上价为6 和边界上价为4 的点；否则为奇异点。正则网格： 没有奇异点的网格。 8 第二章细分理论基础与典型曲面细分方法 ( 2 ) 拓扑分裂算子 细分方法有两种典型的拓扑分裂( s p l i t t i n g ) 方式嘲；基于顶点的拓扑分裂规 则称为对偶分裂算子( d u a ls p l i t t i n go p e r a t o r ) ；基于面的拓扑分裂规则称为基 本分裂算子( p r i m a ls p l i t t i n go p e r a t o r ) 。基于顶点的拓扑分裂，是在原网格顶 点处拓扑分裂后，生成一个新的多边形面；基于面的拓扑分裂是在原始网格的边和 面上插入一定数量的新顶点，然后对每个面进行拓扑剖分，从而得到新网格。 ( 3 ) 细分方法的分类 细分过程就是网格不断细化的过程，它有两个操作步骤：一是拓扑分裂，所对 应的方法称为拓扑规则。二是计算所有顶点的新位置，这一过程称为几何位置平均， 所对应的方法称为几何规则。拓扑规则决定了细分后网格的几何元素的数量呈几何 数增加。几何规则决定了细分后曲线、曲面的极限性质。所以，构成一种细分方法 的三个基本要素是：拓扑规则、几何规则和控制网格。 根据三个基本要素的不同，细分方法有许多种分类，下面就其中几种重要的分 类方法简单说明如下： 根据拓扑分裂规则的不同，细分方法可以分为基本型( p r i m a l ) 细分和对偶型 ( d u a l ) 细分； 根据几何规则是否与细分层次相关，细分方法可分为静态( s t a t i o n a r y ) 细分和 动态( d y n a m i c ) 细分； 根据极限细分曲面是否插值初始控制顶点( 与几何规则有关) ，细分方法可以分 为：插值细分( i n t e r p o l a t o r ys u b d i v i s i o n ) 和逼近细分( a p p r o x i m a t i n g s u b d i v i s i o n ) 按照细分所生成的控制网格的形状，细分方法可区分为基于三角网格的细分、 基于四边形网格的细分、基于三角形和四边形网格的混合细分( h y b r i ds u b d i v i s i o n 等等。 2 1 2 细分方法的特点 细分方法能够处理任意拓扑的控制网格；在进行局部特征调控的同时，能够保 证曲面整体的光滑性，是联系连续模型和离散表示的桥梁；算法实现简单。与其它 造型方法相比，它有以下明显的优势： ( 1 ) 任意拓扑适应性：能够建立任意拓扑结构的曲面，这里的“任意拓扑 具 有两个方面的含义：一是网格的亏格( g e n u s ) 和相应曲面的拓扑结构是任意的；二 是由网格的顶点和边所构成的图形是任意的。 9 基于细分曲面造型的研究 ( 2 ) 表示的一致性：传统的造型方法，其曲面表示要么是多边形网格，要么是 参数曲面。而细分曲面既可以看作是由控制网格定义的连续曲面，又可以看作是离 散网格曲面。 ( 3 ) 可伸缩性：细分方法是基于递归细化控制网格，这使得细分曲面本身具有 多分辨率性质，使其在编辑、显示、网络传输方面具有其它造型技术和曲面表示方 法所无法比拟的优势。 ( 4 ) 简洁、高效性：常用的细分方法所定义的细分规则都很少，而且规则比较 简单，细分计算只是反复迭代，可以高效地计算出新的顶点。 ( 5 ) 仿射不变性：如对初始控制网格作线性变换，如平移、缩放、旋转等，所 得的细分曲线或曲面也会作相应的变换。、 2 2 典型曲面细分方法 为了说明各细分方法所涉及的变量，在这里统一做出以下规定： 大写的字母饼带有数字下标的都表示顶点，小写字母力并带数字下标的表示向 量，小写字母x 、y 、z 并带数字下标的表示顶点三个坐标，大写字母表示顶点法向 量，壤示顶点的价。 2 2 1l o o p 细分方法n 伽 1 9 8 7 年u t a h 大学的l o o p 提出一种基于三角网格的面分裂细分模式，所生成 的曲面是盒式样条曲面的推广。通过对非三角网格进行三角化处理，l o o p 模式也可 以应用于任意多边形网格。它是一种逼近的细分模式，所生成的曲面在正则曲面上 是c 2 连续，在奇异点处是c l 连续。l o o p 模式采用卜4 三角形分裂。 l o o p 细分模式各种顶点的模板如图2 1 所示： 8 33 1 8 屹 1 8 ( a ) 内部奇点模板 晷 ( b ) 内部偶点模板 1 陀l 陀 卜一 ( c ) 边界奇点模板 图2 1l o o p 细分模式模板示意图 内部奇点v 的计算如下： v= p 三! 兰q 兰至2 + 8 1 1 83 41 8 _ _ - - i - - _ - ( d ) 边界偶点模板 ( 2 - 1 ) 学m 第二章细分理论摹础与典型曲面细分方法 v f ，- f v ，+ yf v f l( 2 2 ) 其中胪半，哆= 昙+ ( 若c o s 等) 2 ，岛为顶点k 的价地为顶点k 的1 一 邻域顶点。 边界上的奇点和偶点，可用图2 - 1 中( c ) 、( d ) 的模板来计算。 2 2 2c a t m u l i c i a r k 细分方法1 1 c a t m u l l c l a r k 细分也是u t a h 大学的c a t m u l l 和c l a r k 提出，它是一种针对以四边 形为主的多边形控制网格细分方法，c a t m u l l c l a r k 细分是最早出现的曲面细分方 法，它是双三次b 样条曲面的推广，现已证明c a t m u l l - c l a r k 细分曲面在正则点处达 到俨连续，在奇异点处达到连续。 c a t m u ll - c l a r k 细分模式各种顶点的模板如图2 2 所示： l 加一i 锄矿 1 i c 4 矿 ( 曲面点一( b ) 逊点 ( c ) 顶点毫黔 图2 2 一c a t a m u c k 吐- k 细劳模板示麓图 、 计算新顶点的几何规则为： ( 1 ) 面点( f 点) ：设面的各个顶点为乃、巧、乃v n ，则对应的面点的位置 为： y ，= 菩。y ； 协3 ， ( 2 ) 边点( b 点) ：设内部边的端点为巧、巧，共享此边的两个面的p 一顶点分 别为局、乃，那么与此内部边相对应的细分后的顶点点的位置为： = 土4 ( _ + y ，+ e + r ) ( 2 4 ) ( 3 ) 顶点点( v - 点) ：若内部顶点y 的卜邻域顶点依次为、圪、，奇 数下标的顶点为v 的相连顶点，偶数下标的顶点为其四边形面上的对角顶点， 相应得细分后的顶点的位置为： 基于细分曲面造型的研究 杉= a n y 叫圪，+ ) ，k “( 2 5 ) i = ii = l 其中，a 2 1 一n ( f i x + y ) ，风2 寺，h2 寿 2 2 3 混合细分方法 由于实际造型的需要，一些模型的初始控制网格往往采用同时含有三角形和四 边形的混合网格来表示。对于这类混合控制网格，如果简单地运用上述l o o p 细分或 c a t m u l l 一c l a r k 细分方法，都不能生成光顺性较好的细分曲面。通过对多种细分方法 的分析，作者认为现有的细分方法与控制网格类型有着紧密的联系，因为不同类型 的细分方法所定义的正则顶点的标准不一样，用特定网格下的细分方法来处理其它 类型的控制网格必然会产生许多奇异顶点，从而导致不理想的细分效果。混合细分 方法可以获得c - 连续的细分曲面。 有关混合细分的拓扑剖分、内部顶点几何位置计算、边界顶点几何位置的计算， 大家可以去参考文献n 铂，作者在此不再赘述。 2 2 4 其它细分方法 常见的细分方法还有： ( 1 ) 基于四边形网格的对偶型d o o s a b i n 细分方法1 1 3 l ，它采用顶点分裂的拓扑剖 分规则，它细分可得到c 。连续的细分曲面。 ( 2 ) 基于三角网格的插值型蝶形细分方法1 1 4 l ，由于其模板与蝴蝶相似而得名，每 次细分后，上一次的顶点都保留，只对每条边生成新的边点。它生成的曲 面在奇异顶点处只能达到c d 连续，目前常用的是经z o r i n 在1 9 6 6 年改进的蝶 形细分方法1 1 列，改进的蝶形细分生成的曲面达到c 7 连续； ( 3 ) 基于六边形网格的蜂窝细分方法1 1 6 1 ，这种细分方法不断地切割网格的棱边 和脚，使之趋向光滑，其拓扑分裂规则为顶点分裂操作，因此只生成面点， 现已证明蜂窝细分得到一连续细分曲面。 还有许多细分方法是针对上述细分方法的改进，在此就不赘述了。 2 3 曲面细分方法的比较和选用 从上面的细分方法介绍来看，曲面细分方法很多，那么在工程应用中如何选用， 本文通过对现有曲面细分方法的比较，提出在工程应用中选择细分方法的一般原则。 ( 1 ) 曲面细分方法的比较 本文从细分曲面和控制网格之间的逼近程度、细分曲面质量( 曲面质量通常指曲 1 2 第二二章细分理论基础与典型曲面细分方法 面的光顺性和连续性) 和细分算法的复杂度三个方面对现有曲面细分方法作一比较。 细分面和控制网格之间的逼近程度 总的来说，插值型细分要比逼近型细分生成的曲面更加接近控制网格。逼近 型细分方法中，d o o s a b i n 细分l l c a t m u l l - c l a r k 细分和l o o p 细分更加逼近控制网 格。作者在实验中发现，控制网格曲率变化较大的地方，逼近细分生成的曲面与 控制网格相比有较大的收缩。 细分曲面质量 c a t m u l l - c l a r k 细分、l o o p 细分和混合细分生成的细分曲面质量都较高，其次 是d o o - s a b i n 细分，插值细分生成的细分曲面质量最差，可以说曲面越靠近控制网 格，光顺性越低，从而细分曲面质量也就越低。另外插值细分方法对于尖锐特征比 较敏感因此有尖锐特征时会降低曲面质量。 算法复杂度 除了常用的线性静态细分方法外，还有众多的非均匀细分、非线性细分和动态 细分方法，它们都是以增加细分算法的复杂度来实现的。随着细分算法的复杂度增 加，其性质变得难以分析。虽然复杂度的增加带来了一些形状调整自由度，但这些 自由度对一般用户来说并不容易控制。而且复杂度的增加丧失了细分方法的一个最 基本的优点：算法简单性。从而导致了虽然细分方法种类很多，但真正得到广泛应 用的也就是前面介绍的几种最简单的细分方法。 ( 2 ) 曲面细分方法的选用 在工程应用中选择细分方法时，可以从以下几个方面去考虑： 明确所要生成的细分曲面是插值初始控制网格还是逼近初始控制网格，如果 要求细分曲面通过初始控制网格顶点，可以选择蝶形细分、插值细分等细分 方法： 明确所要生成的细分曲面是流形曲面还是非流形曲面，如果是非流形曲面， 则应该在非流形控制网格上使用非流形细分方法； 考虑初始控制网格的形状，是三角形、四边形、六角形网格还是混合型网格， 从而选择对应的曲面细分方法； 考虑细分后控制网格几何元素的增加倍数，如果希望细分后的控制网格具有 较少的边和面，可以选择4 - 8 细分，以细分或者自适应细分方法； 分析所要求的细分曲面质量，如果期望细分曲面具有较好的光顺性和较高连 续性，应该选择c a t m u ll - c l a r k 细分矛i l o o p 细分等逼近型曲面细分方法。 1 3 基于细分曲面造型的研究 以上选择原则，在