（机械制造及其自动化专业论文）catmullclark细分曲面自适应特征生成技术.pdf

大连理工大学硕士学位论文 摘要 细分方法是一种新的离散造型技术，它通过将特定的细分规则应用到给定的初始控 制网格上来生成模型曲面。与n u r b s 曲面以及贝齐尔张量积曲面这些目前较流行的曲 面造型方法相比，细分曲面具有明显的优点，它不仅能够表示任意的复杂拓扑结构，而 且在曲面拼接时不会产生上述参数曲面很难处理的连通性问题。在诸多的细分方法中， c a t m u l l c l a r k 细分曲面是双三次均匀b 样条曲面的推广，具有易于与n u r b s 曲面融合 的特点。本文正是以c a t m u l l c l a r k 细分曲面为切入点，对细分曲面的尖锐及半尖锐特征， 以及自适应细分方法进行研究，并将自适应细分方法应用到特征造型中，旨在促进细分 方法在c a d 中的应用。本文的研究内容如下： 1 尽管光滑性是自由曲面造型的一个主要追求目标，但是工程实际中也常需要在曲 面上产生一些不光滑的特殊效果，本文称它们为尖锐特征。本文介绍了两种尖锐特征造 型方法，即基于细分规则修改的造型方法和基于拓扑结构修改的造型方法。 2 实际上，所有物体的特征都不会是无限尖锐的，尤其对于机械零件来说，其尖锐 边更多的会用圆角过渡，本文称这种类似于圆角的特征为半尖锐特征。本文提出的半尖 锐特征生成方法是建立在尖锐特征细分规则的基础上，即先利用尖锐特征细分规则细分 若干次，当达到预期的特征效果后，再按照无特征的光顺细分规则细分迭代，这样得到 的细分曲面粗看有特征效果，细看是光滑的细分曲面。 3 针对多次细分后网格数据量急剧变大而导致计算负担加重，但复杂区域和特征区 域的逼近效果可能远不够理想的情况，提出一种基于二面角的自适应细分方法，基本思 想是，每次细分前扩大需要自适应细分的区域到该区域的r ( r = l ，2 ，3 ) 邻域，这样就使最终 生成的光滑曲面上指定区域与利用全局细分生成的曲面完全相同，同时使得细分深度不 同的区域光滑过渡。 关键词：细分曲面；c a t m u l1 - c l a r k 细分；尖锐特征；半尖锐特征；自适应细分 c a t m u l l - c l a r k 细分曲面自适应特征生成技术 t e c h n o l o g yo fg e n e r a t i n gf e a t u r e so fa d a p t i v es u b d i v i s i o ns u r f a c eb a s e d o nc a t m u l c l a r ks c h e m e a b s t r a c t s u b d i v i s i o ns c h e m ei san e wd i s c r e t em o d e l i n gt e c h n o l o g yw h i c hm o d e l st h es u r f a c e s t h r o u g hg l o b a l l ya p p l y i n gs o m ec e r t a i nr u l e st oag i v e nc o n t r o lm e s h s u b d i v i s i o ns u r f a c e s h a v eac l e a ra d v a n t a g eo v e rn u r b sa n db e z i e rt e n s o rp r o d u c tp a t c h e s ，t h a ta r et r a d i t i o n a l l y u s e di nc o m p u t e rm o d e l i n ga n da n i m a t i o na p p l i c a t i o n s ，b e c a u s es u b d i v i s i o ns u r f a c e sc a n d e s c r i b ea r b i t r a yc o m p l i c a t e dt o p o l o g y i na d d i t i o n , s u b d i v i s i o ns u r f a c e sd on o th a v et h e c o n t i n u i t yp r o b l e m sw h i c hp a r a m e t r i cp a t c h e sh a v ew h e nc o n n e c t i n gm u l t i p l ep a t c h e st o p r o d u c ep i e c e w i s es m o o t hs u r f a c e s a m o n ga l lt h es u b d i v i s i o ns c h e m e s ，c a t m u l l c l a r k s u b d i v i s i o ns c h e n l ei sg e n e r a l i z a t i o l lo fb i c u b i cu n i f o r i l lb - s p l i n ek n o ti n s e r t i o ns c h e m e ，a n d s oi ti se a s yt oa p p l yt h i ss c h e m et ot h ew i d e l y - u s e dc o m m e r c i a lm o d e l i n gs o f t w a r e s t 1 1 i s p a p e rf o c u s e so nt h em e t h o d so fg e n e r a t i n gs h a r pa n ds e m i s h a r pf e a t u r e so fs u b d i v i s i o n s u r f a c e s ，a n da l s oo nt h ea d a p t i v es u b d i v i s i o ns c h e m ew h i c hi sf i n a l l ya p p l i e dt ot h em o d e l i n g o ff e a t u r e sm e n t i o n e da b o v e r n l ep a p e ri sd i v i d e di n t ot h ef o l l o w i n ga s p e c t s ： 1 a l t h o u g hs u b d i v i s i o ns u r f a c e sh a v eg o o ds m o o t h n e s s ，s o m en o n - s m o o t he f f e c t sa r e r e q u i r e di ne n g i n e e r i n gs u r f a c em o d e l i n g t h e s ee f f e c t sa r ec a l l e ds h a r pf e a t u r e si nt h ep a p e r t w om e t h o d so fg e n e r a t i n gs h a r pf e a t u r e sb a s e do nc a t m u l l c l a r ks u b d i v i s i o ns c h e m ea r e d e s c r i b e di nt h i sp a p e r ，o n ei sb a s e do nm o d i f i e ds u b d i v i s i o ns c h l 奠t i c s ，t h eo t h e ri sb a s e d0 n t h er e c o n s t r u c t i o no fm e s ht o p o l o g y 2 a c t u a l l yr e a l - w o r l df e a t u r e sa r en e v e ri n f i n i t e l ys h a r p ，e s p e c i a l l yf o rm e c h a n i c a lp a r t s w h o s es h a r pf e a t u r e sa r eo f t e nc h a n g e di n t of i l l e t s t h ef e a t u r e ss i m i l a rt ot h e s ef i l l e t sa l e c a l l e ds e m i s h a r pf e a t u r e s t l l i sp a p e ri n t r o d u c e dam e t h o do fg e n e r a t i n gs e m i - s h a r pf e a t u r e s ， w h i c hi sb a s e do nt h es h a r pf e a t u r es c h e m e s t h eg e n e r a li d e ai s 幻u s ei n f i n i t e l ys h a r pr u l e s f o raf i n i t eb u ta r b i t r a r yn u m b e ro fs u b d i v i s i o ns t 印s ，f o l l o w e db yu s eo ft h es m o o t hr u l e sf o r s u b s e q u e n ts u b d i v i s i o ns t e p s i n t u i t i v e l yt h i sl e a d st os u r f a c e st h a ta r es h a r pa tc o a r s es c a l e s ， b u ts m o o t ha tf i n e rs c a l e s 3 t k sp a p e rd e v e l o p s 趾d n l e d r m a n g l e - b a s e da d a p t i v es u b d i v i s i o nm e t h o d ，i no r d e rt o s o l v et h ep r o b l e m st h a ta r i s ew h e na f t e raf e ws u b d i v i s i o ns t 印s ，t h ea m o u n to fv e r t i c e s i n c r e a s e ss h a r p l ya n dl e a d st oh e a v yc o m p u t a t i o n a ll o a d ，b u tt h es m o o t h n e s so f l l i 曲c u r v a t u r ea r e a sa n dt h ea r e a sc o n s i s t i n go ff e a t u r e sa r ef a ra w a yf r o mb e i n gs a t i s f y i n g n l i sm e t h o de x p a n d e dt h es p e c i f i e dr e g i o no ft h em e s ht oi t sr - r i n gn e i g h b o r h o o ds u c ht h a t w h e ni tw a sa d a p t i v e l ys u b d i v i d e d ，i tp r o d u c e das m o o t hs u r f a c ew h o s es e l e c t e da r e aw a s i i 大连理工大学硕士学位论文 i d e n t i c a lt ow h e nt h ee n t i r em e s hw a sr e f i n e d t h i st e c h n i q u ea l s op r o d u c e das u r f a c ew i n la l l i n c r e a s i n gl e v e lo fd e t a i lf r o mc o a l s et of i n ea r e a so ft h es u r f a c e k e yw o r d s ：s u b d i v i s i o ns u r f a c e ；c a t m u l l - c l a r ks c h e m e ；s h a r pf e a t u r e s ；s e m i - s h a r pf e a t u r e s ； a d a p t i v es u b d i v i s i o n i i i 人连理工人学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：堕趔二必垒通金鱼画鱼鱼鱼生圭i 垂堕丛盖 作者签名： 导师签名： 日期：三! ! 刍年j 月j 日 日期：4 年上月堕日 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：盆趟二丛4 兰垦彗鱼面鱼鱼垒生圭i 垂堡盛拯圭： 作者签名：叁墨壁 大连理工大学硕士学位论文 1绪论 本章首先介绍了细分曲面造型技术的历史背景及细分方法的优点，然后对细分技术 的发展过程进行了简单的综述，最后介绍了本文的研究目的与主要研究内容。 1 1 细分技术综述 1 1 1 细分技术的起源及特点 曲面造型是计算机辅助几何设计和计算机图形学的一项重要研究内容，主要研究在 计算机图形系统环境下对曲面的表示、设计、显示和分析等问题【l 】。目前曲面造型中的 曲面主要有多边形网格、隐式曲面、n u r b s 曲面等表示方法。 尽管多边形网格法可以表示任意拓扑结构的曲面，但该方法表示的曲面精度、光顺 性及可编辑性不及参数曲面方法，从而限制了它的应用。隐式曲面法适合于构造任意拓 扑复杂形体，而且曲面光顺性非常高，但利用该方法构造复杂形状曲面需要大量基本体 素，用户对此难以有效控制，因此不能进行细节造型【2 】。n u r b s ( 非均匀有理b 样条) 技术是目前曲线曲面描述中最为流行的技术，它的优点是能用统一的数学形式表示规则 曲面与自由曲面，且具有可影响曲线曲面形状的权因子，使得形状易于控制和实现，但 它也有明显的缺点。n u r b s 曲面只能表示敞开的矩形域面、柱面和环面等三种简单的 拓扑结构，而无法表示任意拓扑形状的曲面。通常n u r b s 曲面采用逐片构造方法来表 示复杂拓扑结构的物体表面，这时候需要对曲面片进行裁剪或直接在非规则的四边形网 格上构造曲面片，无论哪种情况都要考虑片与片之间的光滑拼接，这种裁剪或者拼接计 算不仅非常费时，而且有数值误差，另外要在曲面的接缝处保持光滑，即使是近似的光 滑也是困难的【3 1 。这时需要一种新的曲面表示方法来有效地表示具有任意拓扑结构的曲 面。 细分( s u b d i v i s i o n ) 方法【4 l i e 是在这种需求推动下快速发展起来的，细分方法是基 于网格细化的离散曲面表示方法，它可以从任意拓扑网格构造光滑曲面。其基本思想是： 定义一个网格序列的极限，网格序列采用一定的细分规则，在给定的初始网格中插入新 的顶点，从而不断细化出新的网格，重复运用细分规则，在极限时，该网格收敛于一个 光滑曲线( 或者曲面) 。可以通过下面的两个例子来具体说明： 图1 1 是对依次连接的四个顶点形成的折线进行细分，最终得到细分曲线的过程。 图1 1 ( a ) 是初始控制多边形，图1 1 ( b ) 是细分一次后的多边形，在细分过程中原有 顶点位置保持不变，每相邻两个顶点间插入一个新的点。重复这样的细分过程，可以看 出曲线越来越光滑，图1 1 ( d ) 是细分三次后的多边形【2 】。 c a l r n u l l 4 7 l a r k 细分曲面自适应特征生成技术 ( a ) 初始控制多变形( b ) 细分一次( 0 细分两扶( d ) 细分三次 i 笔j 1 1 曲线的细分过程 f i g 11p r o c e s s o f c u r v es u b d i v i s i o n 图12 表示的是网格细分过程。图12 ( a ) 是给定的韧始控制四边形网格，图i2 ( b ) 是细分一次后的网格，在细分过程中，每条边相邻两个顶点间插入一个新的边点， 每个面插入一个新面点，细分后新的顶点位置根据几何细分规则确定，并将原来的一个 四边形面分成四个面，重复这样的细分过程，可以看出曲面越来越光滑，图1 2 ( d ) 是 细分五次后的渲染图。 、， 鼢 r a ) 胡始控制网格 q ( b ) 细分1 次0 ) 细分3 次( 由细分5 次后渲染 图12 陆面的细分过程 f i g 12t h e p r o c e s so f s u r f a c es u b d i v i s i o n 细分方法是把参数曲面的逐片构造方法推广到任意拓扑结构的网格模型，即使模型 是_ 舌动的，其光滑连接也能被自动地保证。因为在不规则拓扑处只需采用特殊的细分规 则就可以了，它克服了参数曲面处理任意拓扑曲面时存在的困难。 与现有其它造型方法相比，细分方法具有如下显著特点”： ( 1 ) 任意拓扑适应性：能够建立任意拓扑结构的曲面。这里的“任意拓扑”具有 两个方面的含义；是网格和相应曲面的拓扑结构是任意的；二是由网格的顶点和边所 构成的图形是任意的。能够很好地解决任意拓扑问题是细分方法获得广泛应用的最主要 原因之一。 大连理工大学硕士学位论文 ( 2 ) 表示的一致性：传统的造型方法，其曲面表示要么是多边形网格，要么是参 数曲面。而细分曲面既可以看作是由控制网格定义的连续曲面，又可以看作是离散网格 曲面。 ( 3 ) 可伸缩性：细分方法是基于递归细化控制网格，这使得细分曲面本身具有多 分辨率性质，使其在编辑、显示、网络传输方面具有其它造型技术和曲面表示方法所无 法比拟的优势。 ( 4 ) 简洁、高效性：常用的细分方法所定义的细分规则都很少，而且规则比较简 单。细分计算只是反复迭代，可以高效地计算出新的顶点。 ( 5 ) 仿射不变性：如对初始控制网格作线性变换，如平移、缩放或者旋转等，所 得的细分曲线或者曲面也会做相应的变换。 1 1 2 细分方法的发展历程 5 0 年代中期到7 0 年代末是细分方法的孕育期。细分方法可以追溯到1 9 5 6 年 g d e r a h m 通过对多边形角点进行切割来生成离散形式光滑曲线的思想【6 】。真正把细分 概念引入到图形学，是1 9 7 4 年图形艺术家c h a i k i n 提出的一种曲线快速生成方法，该方 法也正是角切割思想的具体实现【_ 7 1 。随后r i e s e n f e l d 证明了这种极限曲线就是均匀二次 b 样条曲线f 8 】。1 9 7 8 年c a t m u l l 和c l a r k 提出了基于四边形的c a t m u l i c l a r k 细分方法 9 j ， 从此拉开了对细分方法进行广泛深入研究的序幕。 8 0 年代初到9 0 年代初是细分方法的发展期。在这一时期，典型的细分方法开始形 成，如1 9 8 7 年l o o p 在箱样条( b o xs p l i n e ) 细分算法【l o 】的基础上提出了一种基于三角 网格的l o o p 细分方法，将四次三向箱样条推广到任意三角网格【l 。1 9 9 0 年d y n 等人提 出蝶形细分曲面( b u t t e r f l ys u b d i v i s i o ns u r f a c e ) 1 2 】，该曲面能够插值初始控制网格的所 有顶点以及细分过程中所产生的新点，但是该方法要求初始控制网格是正则的三角网 格，即每个顶点的共点三角形数均为6 ，才能保证极限细分曲面是c 1 连续的。规则网格 的细分曲面收敛性和连续分析理论也逐步形成，如1 9 9 3 年c a v a r e t t a 给出了单变元( 曲 线) 细分方法达到任意阶光滑的充分必要条件【1 3 】。 9 0 年代中期到现在是细分理论的逐步完善期和细分方法应用的深入期。1 9 9 6 年， z o r i n 等人对蝶形细分方法进行了改进，使得该方法可以在任意控制网格上生成c 1 连续 的细分曲面【1 4 1 。k o b b e l t 提出基于变分的细分方法，通过能量函数最小来求解细分后控 制网格的新顶点位置，这种细分方法是整体性的，即每一个新点的位置依赖于上一层网 格的所有顶点【1 5 】。1 9 9 8 年，s e d e r b e r g 等人提出了广义的c a t m u l l c l a r k 细分方法和 d o o s a b i n 细分方法，在细分过程中引入了节点距，使得n u r b s 成为它的子集【1 6 1 。2 0 0 0 c a a n u l l c l a r k 细分曲面自适应特征生成技术 年，k o b b e l t 提出了3 细分方法，面分裂速度是一分为三，而不是一分为四，极限细分 曲面除在奇异点处c 1 连续外，其余达到c 2 连续【l7 1 。2 0 0 1 年，v e l h o 提出了比3 细分分 裂更慢的细分算法4 8 细分，该方法只适用于三角网格，网格数每次细分后增加一倍， 因此在非奇异点处可以达到c 4 连续，而在奇异点处是c 1 连续【l 引。2 0 0 4 年国内的李桂清 提出了2 细分模式，其拓扑网格的分裂方式是1 2 分裂i l 引。 在细分方法发展的同时，细分曲面的收敛性理论也逐步建立，提出了任意曲面拓扑 细分的收敛性、连续性分析体系，对细分规则开始加以统一。如2 0 0 1 年，z o r i n 提出了 针对四边形网格的统细分框架【2 0 】，o s w a l d 建立了一种基于三角网格的统一细分方法 2 q 。s t a m 在1 9 9 8 年给出了c a t m u l l c l a r k 和l o o p 细分曲面局部参数化的解析表利2 2 ，2 3 1 ， 利用此解析表达式，可快速精确地计算出极限细分曲面的位置、导矢等属性，为细分曲 面的几何属性计算打下了基础。2 0 0 2 年，z o r i n 提出了针对具有边界和特征的分片光滑 细分曲面在任意点的几何性质计算方、法【z 制。 1 1 3 细分曲面在工程曲面造型中的应用 在c a d 领域中，常通过插值和逼近手段建立目标曲面。在细分曲面插值方面，已 有的细分曲面插值方法可以分为两类：一种是构造新的细分规则或修改已有的几何规 则，使得细分曲面经过初始控制网格的部分或全部顶点；另一种则是利用已有细分方法， 通过构造适当的初始控制网格使细分曲面满足插值条件。虽然插值型细分曲面( 如蝶形 细分) 具有天生的插值能力，但是插值细分曲砸的光顺性并不理想【2 引。h a l s t e a d 等人也 对逼近型的c a t m u l l c l a r k 细分曲面上的光顺插值进行了研究【2 6 】，不过该方法所求出的 能量在奇异点处不收敛。n a s r i 提出插值于d o o s a b i n 细分曲面顶点法向量的细分曲面插 值方法f 2 7 】。l e v i n 通过组合细分( c o m b i n e ds u b d i v i s i o n ) 2 8 】构造了能插值任意曲线的细 分方法【2 9 】，并将其应用于n 边孔洞的修补问题【3 0 l 。 为了与实体造型系统相融合，细分曲面的求交和裁剪一直是有待于解决的难题。仿 造参数曲面的离散求交方法，n a s r i 曾提出一种基于d o o s a b i n 细分曲面边界生成方法的 d o o s a b i n 曲面求交算法f 3 ，只是获得近似的细分曲面交线。l i t k e 等人采用组合细分方 法对细分曲面进行剪裁【3 2 】，该方法通过对控制网格细分、网格删除、重新网格化来局部 调整裁剪曲线附近的控制网格。该方法可以插值任意逐段光滑的参数曲线，从而可以沿 曲面上任意曲线对曲面进行剪裁。利用细分曲面的多分辨率特性，b i e r m a n n 等人对细分 曲面的逻辑运算作了尝试性研究p 引。 细分曲面由于具有非常强的拓扑适应能力，所以比较适合于复杂自由曲面的模型重 建【4 】。s c h w e i t z e r 针对稀疏数据，提出先拟合细分曲线再分片拟合细分曲面，但所建的 大连理工大学硕士学位论文 曲面没有考虑内部特征【3 4 1 。h o p p e 的点云数据细分曲面重建方法相当复杂，需要求解庞 大的非线性能量优化方程组来求出细分曲面控制网格的顶点位置，所以其曲面重建的效 率很低【3 5 1 。s u z u k i 的细分曲面重建方法没有考虑待建曲面的特征信息，不能反映出待构 物体的细节特征，且只适用于拓扑等价于球的曲面重建【3 6 1 。t a k a s h i 和m a 研究了密集 网格模型的细分曲面重建方法【3 7 3 引，但这两种方法在拟合过程中都没有对控制网格进行 形状优化，不能有效地消除控制网格在拟合过程中产生的狭长三角形，影响拟合出的细 分曲面光顺性。同时以上这些方法都没有分析工程应用中比较关心的拟合误差控制问 题。 1 2 课题的研究意义 尽管光滑性是自由曲面造型的一个主要追求目标，但是工程实际中也常需要在曲面 上产生一些不光滑的特殊效果，例如折痕、尖点、角点等。同时，真实世界中的物体特 征往往不是无限尖锐的，比如在利用造型软件设计机械零件时，经常需要对一些尖锐边 进行倒角，使其具有一定的光滑性。基于以上两点，本文对细分曲面的特征造型技术进 行了研究，以期扩展细分曲面的造型能力，使其能够更好的应用到工程曲面造型中。 在曲面细分迭代过程中，控制网格上几何元素( 顶点、边、面) 的数量是按照一定 的比例不断增加的。比如在c a t m u l l c l a r k 和l o o p 细分模式中，细分一次后，控制顶点 的数量会增加一倍，控制网格的数量则增加三倍。即使是增长最慢的4 - 8 细分，其顶点 数量也是每次增加2 倍，网格面增加一倍。所以在对庞大复杂网格模型的细分过程中， 为了保存细分后的点、边、面和拓扑信息，将耗费大量的存储资源和运算时间。同时对 后续的显示、传输或者数控加工编程增加负担。而实际情况是，在细分迭代数次后，某 些区域( 如较平坦部分或者初始控制网格较稠密的部分) 其控制网格已较好地逼近极限 细分曲面，而在另外一些区域( 如尖锐和半尖锐特征部分以及其他曲率变化较大的部分) 其控制网格还比较粗糙，需要继续细分。在这种情况下，自适应细分通过仅仅多次细分 需要更细致表达的区域，从而用更少的网格建立整体模型，大大减少了计算机的运算量， 节省了时间。因此，本文研究了基于c a t m u l l c l a r k 细分模式的自适应细分方法，并提出 一种简单高效的策略，以改善造型效果，提高造型效率和造型质量。 1 3 本文主要内容 ， 本文共分五章，各章的主要内容如下： 第一章：绪论。首先介绍了细分曲面理论的形成背景、发展历程以及细分曲面在工 程曲面造型方面的一些研究状况，最后介绍了课题的研究意义及本文的主要内容。 c a t m u l l - c l a r k 细分曲面自适应特征生成技术 第二章：细分理论基础。本章以c h a i k i n 割角曲线为出发点，讨论了细分曲线的生 成方法。利用细分方法生成的极限曲线在本质上就是b 样条曲线，这些b 样条曲线的 生成为我们把细分方法推广到曲面创造了条件。然后介绍了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 细分方法作为研究对象的原因。 第四章：细分曲面特征造型技术。首先介绍了两种细分曲面尖锐特征造型方法，一 种以修改已有的细分规则为基础，另一种以修改网格的拓扑结构为基础。然后引进一种 半尖锐特征造型方法，对其加以改进，实现了复杂情况下角点的半尖锐特征。 第五章：自适应细分技术。提出一种简单高效的自适应细分方法，通过每次细分前 扩大需要自适应细分的区域到该区域的r ( r = 1 ，2 ，3 ) 邻域，使最终生成的光滑曲面上指定 区域与利用全局细分生成的曲面完全相同，同时使得细分深度不同的区域光滑过渡。给 出自适应尖锐及半尖锐特征实例，并与规则c a t m u l l c l a r k 细分进行比较。最后介绍了本 文实现自适应尖锐及半尖锐特征的数据结构。 大连理工大学硕士学位论文 2 细分理论基础 c a t m u l l c l a r k 细分模式的基础是三次均匀b 样条曲线曲面，所以本章先介绍了细分 思想的来源，然后着重介绍了三次均匀b 样条曲线曲面的细分过程。 2 1c h aikin 割角思想与二次均匀b 样条曲线细分 在三维空间里，给定某个控制多边形，用 b ，写，只 表示该控制多边形最初的顶 点序列，第k 次细分后顶点序列为 劈，芹，露 ，c h a i k i n 的割角过程可以描述为： p 乞= 百3p ，k - i + 三粥西+ 1 - 扣。1 + 百3 聃k - i ( 2 1 ) 细分后生成的新顶点呓和磅+ 。与细分前的线段彤1 和畴1 之间关系如2 1 图所示。 即细分新顶点与细分前线段两个端点的距离之比分别为1 ：3 和3 ：1 。 p k - i j 4 i l l t - - 喇 图2 1c h a i k i n 细分方法的新顶点 f i g 2 1 n e w p o i n t so fc h a i k i ns u b i d i v i s i o n 图2 2 是开多边形的割角细分过程，由图中可以看出，利用c h a i k i n 割角算法细分初 始多变形，极限情况下该多变形收敛于一条光滑曲线，理论上已经证明，这条极限曲线 就是均匀二次b 样条曲线【3 9 1 。 c a l a n u l l - c l a r k 细分曲面自适应特征生成技术 ( a ) 初始控制多边形( b ) 一次割角细分后 ( c ) 三次割角细分后( d ) 四次割角细分后 图2 2 开多边形的割角细分 f i g 2 2c o m e r - c u r i n gs u b d i v i s i o no fo p e np o l y g o n 2 2 三次均匀b 样条曲线细分 了解了二次均匀b 样条细分曲线就对细分的思想有了一定的认识，我们重点讨论三 次均匀b 样条细分曲线，因为它是c a t m u l l c l a r k 细分曲面的基础。 图2 3 三次均匀b 样条曲线细分 f i g 2 3 s u b d i v i s i o no fc u b i cu n i f o r mb s p l i n ec u f v e p 2 假设给定控制多变形p 风，p l ，p ：，p 3 ) ，定义一条三次均匀b 样条曲线： s ( u ) = u m p r ( 0 “1 ) ( 2 2 ) 一8 一 大连理工大学硕士学位论文 r1 41o 其中：u = c ，“2 “3 ，m = 丢l ；一： ； 吕l 。 l 一1 3 3 1 j 由于b 样条基函数具有对称性，这里只考虑0 “ 1 2 的情况，从而得到s ( u ，) ， 其中“。= “2 。根据方程2 2 可以得出： s ( u 1 ) = u s m p r ( 2 3 ) 其中：s = 1o 01 2 o o 0 0 0o oo l 4o 01 8 s ( 峨) 必定也是一个三次均匀b 样条曲线，设它的控制顶点为片 矗，p l ，p ：，p 1 ) ， 得出由# 定义的一条三次均匀b 样条曲线： s ( “) = 卅旧r 于是得出： s m p t = m 式 掣= p ： 科 p ： p ； = m 。鼬伊，= 吾r 三军萎辱刭 则可以 ( 2 4 ) ( 2 5 ) ( 2 6 ) 同理可得出1 2 ”l 的情况，最后的结果如图2 3 所示，可以用矩阵表示为： 1 = 8 44o0 1610 0440 0161 oo44刭 ( 2 7 ) = 坠业掣野坠型学螳 ( 2 8 ) 由式2 7 和2 8 可以看出，e o ，巨，易分别是原控制多边形各边的中点，称为新边点，v o 是 线8 2 e o p ,p 。巨连线的中点，巧的意义相同，称他们为新顶点，连接新边点和新顶点就 一9 一 露科反d 一 磊巨k 最 c a t m u l l - c l a r k 细分曲面自适应特征生成技术 得到新的控制多变形。不断的细分下去，初始控制多变形就收敛到一条均匀三次b 样条 曲线。 2 3 双三次均匀b 样条曲面细分 pi o p 图2 4 双三次均匀b 样条曲面控制网格 f i g 2 4 t h ec o n t r o lm e s ho f b i c u b eb s p l i n es u r f a c e 利用上一节的方法，我们同样可以对双三次均匀b 样条曲面的细分过程进行分析。 首先定义一个双三次b 样条曲面s ( u ，d ( o “，v 1 ) ，其控制网格如图2 4 所示，则可得 到双三次均匀b 样条曲面表达式： s ( u ，1 ，) = u m p m r v r ( 2 9 ) 其中： u = 【1 uu 2 u 3 】， v = 【l ，1 ，21 ，3 】，p = m ：1 6 l4 3o 36 13 lo 3o 30 3l p o o p o i p l oa i p 2 0 p 2 1 p 3 0 岛1 由于b 样条基函数具有对称性，这里只考虑0 “，v 0 ) 为细分曲面的控制网格，有时为了区分把m o 称为细分曲面的初始控制网格。 拓扑分裂规则和几何平均规则的集合称为细分方法。本文在表示与细分层次有关的控制 网格m ，控制顶点v 等符号中，上标k 代表细分层次。 3 3 细分模式的收敛性与连续性分析 细分曲面没有解析形式，曲面的连续性和光滑性分析无论从理论还是应用角度来说 都显得很重要，当然相对来说也比较困难。由于细分曲线控制多边形的拓扑结构相对要 简单得多，因此单变元细分模式的收敛性和连续性分析已形成较完整的框架体系。对于 曲面( 双变元) 细分模式，控制网格为正则情形时连续性分析相对也比较容易，一般只 需要研究奇异顶点处的极限行为。对于线性的静态细分模式，从迭代关系得到的局部细 分矩阵可用来对极限行为进行分析，大多数情况下得到的矩阵具有循环矩阵的一些特 点，离散f o u r i e r 变换可以简化矩阵特征根的求解，从而揭示迭代过程的收敛性m 】。 3 3 1 线性细分模式的矩阵表示 下面直接用向量字母表示网格顶点。设初始网格m o 的某个顶点子集序列为 p o = ( ，记一，v o 。，v o o ，v o ，口，) ，第k 次细分后网格m 。的某个顶点子集序列为 p = ( ，v _ k i ，t 。，诺，详，霄，) ，其中( 尼= l ，2 ，) 中的顶点只与p 扣1 中的顶点有关， 而与膨扣1 的其它顶点无关。对于线性细分方法，由于m “1 的顶点是m 顶点的线性组合， 因此有矩阵形式 尸+ l ：s p ( 3 1 ) c a u n u l l - c l a r k 细分曲面自适应特征生成技术 矩阵称为细分矩阵或迭代矩阵。如果p 和p “1 中分别包括了m 和m “1 中的全部顶 点，则称s 为全局细分矩阵，否则称为局部细分矩阵。 以单变元的c h a i k i n 算法为例，对p = ( ，t f 一，逆，诺，霄，嘭9o o ) 作一次c h a i k i n 细分得到p = ( ，v u , - - , t j l ，瞄州，讨州，0 “，) ，两次迭代的顶点之间满足关系： 略1 = ( 3 0 + 畦。) 4 ( 3 2 ) 屹k f + l + i = o , 7 + 3 歧。) 4 ( 3 3 ) 于是有如下全局矩阵表示 1 = 4 心 t ， 诺 讨 呓 ( 3 4 ) 上述矩阵的一个有限部牖l 嚣翳i 对于网格来说，全局矩阵的结构将会很复杂，且对不同的网格就会有不同的矩阵， 要以此对细分模式进行分析是很困难的。事实上这也是不必要的，因为网格的规则部分 的极限行为较容易分析，关键在于研究奇异顶点处的局部极限性态。下面以l o o p 模式 为例说明建立曲面模式的局部细分矩阵方法【n 】。l o o p 模式采用1 - 4 三角形分裂算子插入 新顶点，考虑以落为中心顶点，0 ，访为相邻顶点的伞状网格( 如图3 4