（计算数学专业论文）基于细分方法的自由曲面造型.pdf

大连理工大学硕士学位论文 摘要 细分曲面造型方法是一个跨学科的前沿科技领域。从2 0 世纪7 0 年代中后期起，随 着细分理论的不断发展，应用领域不断拓宽，细分曲面造型方法已经逐渐形成了自己的 独立的学科体系。原有的细分曲面造型方法不断改进，新的细分曲面造型方法层出不穷。 同时，它与近代发展的新的数学理论i 如小波变换、多分辨率分析等结合起来，获得了 新的发展动力，呈现了强大的生命力，已经成为继n u r b $ 之后的一种重要的自由曲面 造型方法。今天，细分曲面造型方法已经成功的应用在物体建模、古代器件和艺术领域 的雕塑作品三维重构、电影动画、玩具制造等等。 细分算法的最大优点是它能够从任意的初始网格出发产生光滑的曲面。目前的细分 格式大体上分为两类：逼近型和插值型。逼近技术是种收缩方法，不能对曲面进行有 效的控制，而对曲面进行有效的控制是曲面设计与特征动画的关键问题。相比较而言， 插值技术保持初始网格顶点不变。但曲面的舢瓯性很难腔制。用控制顶点的调节能力来 增强细分算法的生命力是一个挑战性的研究课题 本文引进物理模型对逼近型细分曲面的控制顶点进行控制，通过调节物理模型中的 不同参数，可以获得不同的细分曲面，增强了细分算法的生命力。本文使用的细分格式 是l o o p 细分格式，所使用的动态方程为基于弹簧模型的h g r a i 】_ g e 动态方程。 关键字：细分曲面：l o o p 细分；动态方程：曲面控制 基于鲴分方法的自由蓝西遗挺 f r e e ，f o r ms u r f a c em o d e lb a s e do n s u b d i v i s i o nm e t h o d a b s t r a c t t h em o d e l i n go l ? s u b d i v i s i o ns u r f a c e si so n eo ft h ea d v a n c e ds u b j e c t si nt h e s c i e n c ea n dt e c h n o l o g yf i e l d s ，w h i c hi si n c l u d e di n m a n ys u b j e c t s f r o mt h e m e t a p h a s e a n d a n 鑫p h a s e o f 7 0 ”i n t h e 2 妒c e n t u r y , w i t h t h e d e v e l o p i n g o f s u b d i v i s i o n 氇e o r i e sa n d 也e e x p a n d i n go f a p p l i c a t i o nf i e l d s t h em o d e l i n go f s u b d i v i s i o ns u r f a c e s h a sb e c o m ea na b s o u t es u b j e c ts y s t e mg r a d u a l l y t h eo l dm o d e l i n go fs u b d i v i s i o n s u r f a c e si si m p r o v i n ga n dt h en e w m o d e l i n go fs u b d i v i s i o ni se m e r g i n gi ne n d l e s s l y a tt h es a m et i m e i tg e t st h en e w d e v e l o p i n gp o w e ra n da p p e a r sn e w l i f ef o r c eb y u n i t i n gt h en e wm a t h e m a t i c st h e o r i e s 。s u c ha sw a v e tt r a n s f o r r n a t l o nt h e o r ya n d m u l t i r e s o l u t i o na n a l y s i st h e o r ye t c i th a sb e c o m eo b eo f i m p o r t a n tm e t h o d si 1 1f r e e f o r n ls u r f a c em o d e l i n ga f t e rt h en u r b s m e t h o d t o d a y , t h em o d e l i n go f s u b d i v i s i o n s u r f a c e sh a sb e e na p p l i e ds u c c e s s f u l l yi nm a n y i m p o r t a n tf i e l d so fo b j e c tm o d e l i n g ， r e v e r s ee n g i n e e r i n go f p a r t so f a n a p p a r a t u sa n da r t i c l e ，m o v i ea n i m a t i o na n dm a k i n g o f t o y a n ds o0 1 3 t h eb i g g e s ta d v a n t a g eo fs u b d i v i s i o nm e t h o di st h a ti tc a ng e n e r a t es m o o t h s u r f a c ef r o ma r b i t r a r yi n i t i a lm e s h i ng e n e r a l t h e s es u b d i v i s i o ns c h e m e sc a nb e c a t e g o r i z e di n t ot w od i s t i n c tc l a s s e s ：1 ) a p p r o x i m a t i n gs u b d i v i s i o nt e c h n i q u e sa n d2 ) i n t e r p o l a t i n g s u b d i v i s i o n t e c h n i q u e s a p p r o x i m a t i n g s u b d i v i s i o n t e c h n i q u e s i sa c o n t r a c t i v em e t h o d ，a n dw ec a n tc o n t r o lt h es u r f a c ee f f e c t i v e l y b u tt h ee f f e c t i v e c o n t r o lt ot h es u r f a c ei st h ek e yi ns u r f a c ed e s i g na n dc h a r a c t e r i s t i ca n i m a t i o n b y c o m p a r i s o n ，i n t e r p o l a t i n g s u b d i v i s i o n t e c h n i q u e s r e m a i n si n i t i a lm e s hv e r t i c e s c h a n g e l e s s ，b u ti t i sd i f f i c u t tf o rt h ef a i r i n go ft h es u r f a c et ob ec o n t r o l l e d ，i ti s8 c h a l l e n g i n gt a s kt oe n h a n c es u b d i v i s i o nm e t h o d sl i f e - f o r c eb yu s i n gt h ea d j u s t i n g c a p a b i l i t yo f e o n t r o l l a b l ev e r t i c e so f t h em e s h n i sp a p e ri n t r o d u c e s p h y s i c a lm o d e it o c o n t r o lt h ec o n t r o l l a b l ev e r t i c e so f a p p r o x i m a t i n gs u b d i v i s i o ns u r f a c e ，a n dv a r i o u ss u b d i v i s i o ns u r f a c ec a nb eo b t a i n e d b ya d j u s t i n gt h ep a r a m e t e r si np h y s i c a lm o d e l t l l i sm e t h o de n h a n c e dt h ef i e x i b i l i t y o fs u b d i v i s i o n t e c h n i q u e s i n t h e p a l ：l e r w eu s c l o o p s u b d i v i s i o ns c h e m ea n d l a g r a n g ed y n a m i ce q u a t i o n b a s e do n s p n n g m o d e l k e y _ v o r d s ：s u b d i v i s i o ns u r f a c e ；l o o ps u b d i v i s i o n ；d y n a m i ce q u a t i o n ；s u r f a c e c o n t r o l 独创性说明 馋者郑重声明：本硕士学位论文是我个人在导疼指导下遴行的硬 究工作及取褥磷究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含 为获得大涟理工大学域其他单位的学位或证书所使用过的材料。与我 一同工作的同志对本研究所做的贡献均已在论文中做了明确的说明 并表示了谢意。 作者签名：盗f 叠趔姜 日期：鞠垄：生! ! 作者签名：奄产翻蜒釜一目期：盈翻二量型l 大连理工大学硕士学位论文 1 前言 1 1 研究背景 在c a d c g 中，曲面造型是一个有着较长历史的领域，6 0 年代初期就已经诞生。 1 9 6 3 年f u g e r s o n 提出将曲线曲面表示为参数向量函数形式，在此之前曲线曲面都是采 用普通的函数表示形式y = f ( x ) 和z f ( x ，y ) 或它们的隐式方程表示形式。 1 9 6 4 年， c o o n s 发表了种由四条边界曲线确定的参数曲面b p c o o n s 曲面片，从而使分片表示完 整曲面成为可能。1 3 隧e r 于1 9 7 1 年发表的由控制多边形定义曲线的方法，则可以很便 地控制曲线的形状，但曲线上任一点都与多边形的所有顶点相关，因此对控制多边形的 任何修改都会影响到曲线的整体形状。7 0 年代# j d eb o o r ，g o r d o n 年i r i c s c n f d d 等人发 展了b 样条曲线曲面的理论和算法，保留了b d z i e r 曲线的大部分优点。另一方面，由于 是分段多项式，因此允许局部控制。但是e 述各种方法不能表示圆锥截线和球面椭球面 等初等解析曲面，为此v e r s p r i l l e 于1 9 7 5 年提出有理b 样条方法。最后在p i g e l 盯m e r 等人的努力下，终于在8 0 年代后期发展起来非均匀有理b 样条州r b s ) 的一整套方法， 把有理和非有理b d z i e r 曲线和b 样条曲线曲面及圆锥曲线和初等解析曲面统一在一种 表示之中，最终使阿o r b s 成为c a d c a m 行业的工业标准 施法中1 9 9 4 , f a r i n l 9 9 7 朱 心雄2 0 0 0 。 上述各种曲面都是定义在矩形参数域上，是矩形曲面片，无法有效地表示任意拓扑 形状的曲面。通常采用逐片构造方法表示复杂物体表面，这时候需要对曲面片进行剪裁 ( t m n m i n g ) 或直接在非规则的四边形网格上构造曲面片，无论哪种情况都要考虑片与片 之间的光滑连接。尽管也有三角形域上的b d z i c r 曲面，但表示复杂物体时同样需要拼接。 这是一个相当困难附工作。 细分曲面( s u b d i v i s i o ns 删a c e s ) 是一个网格序列的极限，网格序列则是通过采用组 规则( 般是加权平均) 在给定初始网格中插入新顶点并不断重复此过程而获得。这种方 法克服了参数曲面处理任意拓扑网格岫r y t o 删o g yr 删1 e s ) 存在的困难。因为，在不 规则拓扑处只须采用特殊的细分规则就可以了，不存在拼接的问题。 另一方面，由于三维扫描仪( 3 ds 伽m 、测距仪但a n g ef i n d e r ) 和c t 等三维数据获 取设备的日盏完善，：勾几何形状不能或难于用分析曲面表示的对象建模提供了有力的工 具，例如医学的人俐器官建模、考古学中的古代器件和艺术领域的雕塑作品三维重构等 等离散曲面逐渐成为种重要的几何表示方法细分模式作为从给定规则产生离散曲 面的方法统一了传统的参数曲面与多边形两种实体表面的表衣另外，由于实验获取的 三维数据量一般都非常大，多分辨率分析成为有效地处理这类数据的重要手院细分方 法与多分辨率分析、小波变换之间的深刻联系也是目前细分模式受到关注的一个重要原 因。 由于多面体细分算法提供了一个简单而有效的曲面生成方法，它已经成为在计算机 基于纲分方法豹自由曲蔼滚型 辅助几何y 良f ( c a g d ) # 进行复杂曲面谶型的一个基本工具。最早的两个基本细分怒由 c a h m u l l ，c l a r k 和1 3 0 0 s a b i n 在1 9 7 8 爨凌的。n a s r i 扩餍了d o o - s a b h a 细分方法以便在原 始多萄傣蹲陪上进行顶点播篮瓯强震绒分魏嚣上进 秘群条魏线懿箨潼操作。n d y n e t a 1 提出 j r b u t t e r y 插值| 细分曲面z o r i n e ta 1 扩展t b u t c e r y 方法。f a r i n 和l 0 0 p 讨论了个 基于箱样条的细分算法。m h a 随e a de ta 1 提出了一个基于c a 拄n u l l c l a r k 的插值细分方法。 s e d e r b e r g e t a l 提出了 均匀缍分鳆瑟。i 霞来，细分方法谯数字足嚣搴簿到了广泛的艨爝， 该方法大大简纯了蕊锫穗输豹容量。 1 2 细分曲面的发展阶段 细分方 舸以追溯到5 0 年代g r h a m 的通过对折线角点进行切害0 ( c o n 埘c u | 乏黝戏 光滑曲线的思想。7 0 年代中期，c h a i k i n 生成曲线的细分方法正是这种角切割思想的具 体实现。 藤c a t m u l l 释c l a r k 提出了麓名酶c a 瑚u l l - c l a r k 终分楱爨檬志着细分方法 正式成为魏蕊建模豹警蔽。当矩形弼穰没有奇异颈煮辩，c a 妇u u - c l m k 模式生或三次b 样条曲面；对于有奇异顶点的网格，生成的曲面除有黻个点外，具有二阶光滑，可以说 是一张“几乎处处光滑”的三次b 样祭曲面。与此同时，d o o 和s a b i n 采用离散f o u r i e r 变换静方法，对c a m u i i - c l a r k 模式我收敛瞧进行了分横，烈了缨分攫式牧续 生缀黪特 征分褥熬兔河，并提出了籍名豹d o o - s a b i n 缁努模式。7 0 年代后鞠c a m m u - c l a r k 缀分模 式以及d o o - s a b i n 关于奇舜点处行为的分析理论标志着细分方法正式成为曲线曲面造型 的种手段。 8 0 年代寒裂9 0 年健：魏期是鳃分方法戆形成翘。巍这玲段，爨痰了摄多著名戆缨 分方法，辩 强方法迮毒许多l 免进 奠：运澎不蕊要求。揪情形的收敛穗程连续分析蘧论也 逐渐完善。不过，各种模式之间仍然缺慧联系，一般情形的收敛生分析方法也是“髓身 定做”，缺笼_ 般的理论指导。 9 0 年谯中麓至国畦憝缀势方法懿发鼹麓。这一对期舞始建立系绫熬l 发毁睦理谂，提 出了多变辩菠式任意拓卦情形下收敛陂分析的理论援絮。这些理论爱过来指导细分模式 的构造，尤萁是二阶以上涟续曲面的构遗。此外，各种细分模式的内在联系也逐渐被揭 示出来，例如z o r i n 和s c h r & l e r 为主凹i i r n a l ) 四边形网格细分模式和对偶( d i l a i ) 四边形网 穆缨分模式建立了绞卜懿 蓬黎。更麓重簧豹是，在这一辩麓，鲴努方法褥垂了广泛痰忍 尤其是复杂阚格曲面静多努辩率分析酶骈究驳得了丈赞成果。 1 3 研究嗣的 细分算法的最大优点怒它能够从任意的初始网格出发产生光滑的曲面，并且细分算 法能够用来构建多层次细节，即所谓的多分辨率分析。膊前的细分格式大体上分为两炎： i 藿雯型和撵隧型。运圄妫淹两帮密方法，不 缀蔻藤甏薅效的羧孙嚣穗藏甏遵 行有效的控南幄曲面设讦与特征动画酌关键问题。福玩较而言插值技术保挣初始刚格顶 点不变，但曲面的光顺胜彳雠有效地控制。用控制顶点的调节能力来增强细分算法的生 大连毽王大学硕士学位论文 命力，是一个挑战性的研究课题。 在这方面有诲多学蠢赞对该阉题援出了各 不爆瓣箕法。大依上可分为三类：类 是通过渗殴绣分娩爱l 采按摩8 缀分蕊萄麴形获【l 幺3 ，4 ，5 ，键。在文被l 磁孛j 蘑遘标记不丽种 类的控制顶点，然后对标记的控制顶点采用不同的细分规则，可以馒细分曲面保留棱角， 折痕等几何特征。文献 3 】中结合了逼避、插值的思想来构造种新的细分规则，使细分 曲面够保蟹一定的形状，著且具有定鲍兜滑| 生。文献圈提出炎耪颚鲍半静态霹矮 霾分方法，可鞋在不酸嶷控鑫l 颓点静清况下，构造躐飘逼近到播鬣控案l 预点秘系列魏 线曲面。文献 5 把传统的均匀细分格式推广到非均匀细分格式，为使用者提供了种能 够控制曲鳓特征的方陡文献 6 通过修改细分规则来使细分曲面的边界或内部满怒法矢 约束，这极大睦提高了慰趋蟊的控泰i 骞墓力；另粪燕透过对初始鼹懒处理，然惹旌 鸯霾标准静缨分l 颥舔使缀分益蘑基本上保持裙始霹格豹形获并兵脊一定的光滑瞧 7 j 。文 献 7 通过对初始网格磁加新的剖分，然后对剖分后的网格进行标凇的细分，从而达到保 形的目的；第三类是通谶宜接操纵极限曲面的来控制捆分曲面 8 ，9 ，1 0 1 。文献 8 9 1 0 1 把细 分兹蟊嬲基于物理模型自框絮孛，暹过x 圣缨分鼹嚣涟女日力的影响隧制极鼹浆嚣， 该方法$ 跫供了释壹藏撩级绥分蘸葱的交互式工具。 另一方面，随者e a d 、c a m a 的不断扩屣人们对曲线曲面造型技术也 提出了更简的要求。传统的造型方法邋常是基于纯粹的几何模型，设计人员往往丽对的 是搪燥懿、不奁观的形状j 1 ；鹰参数，嚣绘定戆设计谖2 誊藿誊是嚣趣彩毛跫戆，这榉麟使穆 改豹结鬃凳融蓬淤捉摸。舅薨典墼鞠设誊十耍求一般蹩阕时定瞧帮定麓给出，对澎妖的整体 和局部都媳有约束，这j c 寸于调整局部形状参数的方法来说是很难同时满足的。因此，寻 找更新更爱活的造型方法已成为一项非常紧迫的工作。基于物理的造型方法能够克服传 统造型方法的缺陷( 第三豢绘出详缍分g 秘，使造型委鸯1 t 灵活、更鸯暖溉，霹眩适会交互 式设计。 从上述思想出发，本文通过把细分鳟法的优点同蕊于物理的造溅方法相接台，通过 物理模型对细分算法产擞的控制顶点进行操作，通过调节动态方程中的参数及各种约束 条l 譬寒达要控摹錾援分魏瓣豹嚣嗽第嚣颦褥详缨分绥该算法) ，本文掇瘩豹算法增糖t 绥 分算法的瑟活往。 1 4 本文靛内容组织 本文第二章介绍了绷分曲面造型方法的应用、特点、分类及其常用的细分格式，这 是本文磷宠麓基本出发患；第三章分缨7 莲于物理豹囊虫趋覆造型技零豹鸷景、分刍睦、 及其常辫的物理方法，这是本文工 乍静又一出发点；第疆章详绥戆介绍了基于物璐模霆 的l o o p 细分曲面控制算法，并给出了大量的图例加以说明，验证了算法的灵活性。 基于细分方法的自由曲面造型 2 细分曲面 2 1 细分曲面的应用 细分方法在图形学很多领域都有重要应用。其中一个重要方面就是多分辨率分析， 例如曲面网格的多分辨率分析、医学数据的多分辨分析等此外在计算机动画、科学计 算可视化、数值计算以及医学图象处理中都有应用。 首先，在计算机图形学、几何造型及逆向工程等应用领域，往往采用大规模甚至超 大 见模的多边形网格来表示复杂对象的表面形状。从数据的获取、处理到传输都面临巨 大自勺j j | 战，多分辨率模型刚抵k h l m 。d e l i n g ) 正是为了解决这样的问题而提出的。 其次，细分曲面造型方法在生动逼真的特征动画和雕塑曲面的设计加工中如鱼得水， 得到了高度的运用。1 9 9 9 年a c m s i g g r a p h 的成就奖授予t o n y d e r o s e ，原因之一是 为表彰他把细分方龇蠼甜鼬应用于解决图形学中的实际问题所做的贡献。 再次，细分方法在医学图象处理中应用主要是用于医学图象重构，直接得到等值面 的具有细分连通性的三角网格。这方面比较典型的工作是q 证，m a n d a l 和v c m u r i 等人 的基于细分曲面动态造型方法 8 ，9 ，1 0 他们通过建立怍用于新顶点的力学模型来确定新 顶点的位置。 2 2 细分曲面的特点 细分曲面( s u b 弥，i s i o ns i 】蠡c 娼) 是个网格序列的极限，网格序列则是通过采用一组 规则( 般是加权平坳在给定初始网格中插入新顶点并不断重复此过程而获得的。相对 于样条函数曲面和隐函数曲面，细分曲面有以下的优点： 1 、高效陛伍c k n 劝： 在曲面造型中计算量的大小是衡剿方法优劣的重要标准。细允撇这一 方面是相当高效的，它在造型过程中通过几个原有的控制顶点来加权计算新的控制 顶点，这与样条函数插入节点很相像，事实上，很多细分格式都是由相应的样条函 数插入节点而产生的。而用隐函数来设计曲面时将要计算大量的数据。 2 、任意拓扑性( a b i 订a r ) r t o p o l q 科) ： 找们希望能够构造任意拓扑的曲面，这时候利用隐函数方法来实现是比较容易 的，而经典的样条函数在任意拓扑控制网格中进行逼近时有很大困难。 当我们在任意拓扑网格下使用样条函数时，在特殊点上要想获得高阶奎续是很 困难的，它增加了许多复杂性。隐函数能够表示任意的拓扑亏格( g e n u s ) ，但是这 些亏 各( g e n u s ) 的准确位置和曲面的连续是很难控制。而细分方法可以有效的解 决任意拓扑的曲面造型，这是它的一个相当突出的优点。 太连理工大学硕士学位论文 3 、曲骥特蛙( s u r f a c ef e a t t a 端) ： 镪分方泼可以很好的控制曲鞭的形状稻特饺，例如樱皱，锈痰，尖点等。贯一 方灏，隐式函数曲面却很难把握曲面的形状和特征；而对于样条函数曲砸是能够准 确的把攥瞌瑟移淡秘特征，但是黝大豢盼计算，在合成曲衙特征时露科鼹是笨 拙，特另是人j # 憨疆褒l 王意麴位擞上掰成鳆熬时更是如戴。绥分要 样条涵数 更加灵滤。另外人 f j 可以很方便泌调整控毒姻l 点位置来生成缨分趣嚣上然各耱姆蛙 和边界形状。 4 、复杂凡筒 n ：( c o m p l e xg e o m e t r y ) ： 鼹必缨分是一葶孛基予重复女g 缎懿方法，它肇够豢缕实现程缀特惩上逐层瓣绘黎 压绫的愿想。由予突验获取憋兰缝数据量一般都 常大，多分辨搴分掇 c m u t l i r e s o l u f i o na n a l y s i s ) 成为有效地她理这类数据的藿要手段，。细分方法与多分辨 率分轿、小滚骞穗蝌v 畦e c 蜘n 曦k m a 6 0 n ) 之间的深亥联系也是阿前缅分模式掰关 注懿一个重要缳爨。 5 、焱承瓣一致性( 溉f o n n i t y o f r e p r e s e a t a o n ) ； 这量所说的一致性是指缁分法把曲面片与多画体表示统一起来，使褥造型系统 有了统一处理曲面和多面体表示的手段。 6 、数篷稳定黢( k 撼8 r i c a ls t a b i l i t y ) ； 线憋缎分方法怒令迭饯；妻缓，蠢 曩好豹数馕稳定整，霹耀予窍鞭元方法。 7 、简单骸( c o d es i m p l i c i t y ) ：易于实现，效率也很高。 基于上述的一i 巍特点，缔分方法作为种c a g d 技术其有很强的生命力。可以相倍 隧善褥究熬深入娃致一些美键按术昀瓣捷，维分方法会育更广泛熬巍雳翁景。 2 3 细分方法的转类 细分方堙根据不同瓣多颟体嘲格丽采用不同的缨分封暇4 。勋出口l 】凝据不同的标凇 把细分方法进行了分类： ( 1 ) 校据缀分瓣粼丽分鬏或煮分黎。 ( 2 ) 根据，主成的网格( 三角网梭或列边形网獬。 ( 3 ) 根据缨分方案是掭僮葳是逼近。 ( 4 ) 正则网撂购光磷陛( e ，c2 等) 分类结栗冤下夜：该分类中没存包含5 绍分曲面和4 吨缁分曲面。 面分裂 三角形闻格朗边形网格 遥i 穗k ) 。p ( c 2 )c a 瓣l l - c l e z k ( c 2 ) 插戗m o d b u t t e r f l yk o b b e l t ( c ) ( c ) 基予继势方法的自由箍藤滤型 表2 1 细分曲面分类 嘞l e 2 1 髓1 e c l a s s i f i c a t i o n o f s u b d i v i s i o ns u r f a c e s 。 ( 1 ) 网榴害篷型 三角形和四边形网格是在实际应用中常用的两种多面体网格。谴母致了两类不同的 细分方法，在这些缨分方法中，所生成蹲燃是曼麓形和四边影嬲袼。 ( 筠西分袋或点分裂 生成曲面共有两种主要的方法：谢分裂( f a c es p i l t ) 和点分裂( v e a e xs p l i t ) 。猩前一 种方法中，三角形网格或四边形网格的缚一个面被分裂为四个面，每一条边插入一个新 顶点，并嚣旧的网格顶杰拔傈器 下来。鞭对于四边形嬲格，还要在蒸簿个瑟捶入个耨 颚点。这黧| 嚣懿弼格j 瑟患被绦翟f 毒两个戆愿：一是j 器阏络顶点位嚣缣持不变，二蔻爆豹 网格顶点奇勺位置被重新计算。在后种方法中，和初贻网格的顶点 目邻的每个面插入一 个新顶点，每条边产生一个新面，原来的面保留，另外对应每个顶点产生个新赋。对 予四边形瓣晦兹点分裂，每个顶点斡徐必。面对子三角形戆点努裂不产生嶷套验六边澎 形式，掰娃点分不适于三角形网格。 ( 3 ) 逼近和插值 顶点攒八方法可以是逼近的或是撼值的：如果旧的顶点的位置没有改变，则顶点插 入方法毅猕终插篷方法，妇暴l 曩的顶点瓣位置被重裁诗算，更 饿瓣谖i 塞鼹方法是一耱遥 i 莲方法。攒傻是静其餐暇弓| 力的方法，键是，生成鹩潼面豹质量誉如用逼近方法生成 的曲面光滑，而且收敛到极限曲面的道度不如逼近方法。 2 。4 c h a i k i n 算法 细分曲面的基本思想可追溯到c 上城d n 1 2 】的算法，该算法通过削角可从个多边形 生成一个二汐样务曲线。每次纽分东多边形的每一黎迓e 都生成；露个凝的顶点。参考 图2 ，l ，对个聿甄个顶焦( 1 - i 齐) 酌多边形来说，在边( k ，+ ) 上，这两个新静顶 点可由下面的算法给出： 巧+ = 言鬈十丢，形_ = 巧+ i 3 v 。 ( 2 1 ) 薮我爹逐形垂连接赣垒成熬顶点辑，鬈嚣畿，霆娩，l 铡示了嚣次缀努嚣夔缝巢。 r i e s e n f e l d 1 3 】证明了由匕述算法生成的曲线是条二次b 样条曲线。 大连理工大学硕士学位论文 图2 t ：c h a d d n 算法登0 圆点为初始顶点，实心圆点为细分一次 生成静顶点，癸崂点为镪分两次后生成的顶点 f 蟪u r e 2 1 ：c h a i k i n s a l g o r i t h m h o l l o w c i r c l e n o d e s a r e o r i g i n a l v e r t i c e s , w h i l e s o l i d c i r c l e n o d e s a r e t h e v e r t i c e s a f t e r l t s u m i v i s i o r l s o l i d s q u a r e a o d e s a r e t h e 2 n d s u b d l v l s i o n v e 目s c e s 2 5c a t m u u c l a r k 细分曲面 尽管在1 9 7 4 年c 【1 2 】就把离散细分的概念引入到图形学界，用来研究曲线的 快速绘裁，毽囊歪怒绥分方法蒎广开寒懿怒在l 弼8 年，盘c a l m u l l 纛c l a r k ，d o o 密s a b i n 分别提出了将b 样条曲面推广到任意拓扑网格上的细分簿法开始的。 繇霾n 疆c 敞攘式是u t a h 大学瓣c 矧m a u 积c l a r k 予1 9 7 8 每提窭【l 訇。这是最晕戆 细分曲面模式。后来d o o 和s a b i n 利用矩降f o u r i e r 分析的技术对c a t r n u l l - - c l a r k 的收敛 牲遂嬲【1 5 】，橼志着绥分方法麴西戆残隽整甄造碧缝一耪工兵。基于西迭形蘸格 的细分方法研究中，很多工作是在c a t m u u - c l a r k 模式上展开的。 2 5 1c a t m u l l - c l a r k 女 分规则 c a t m u u - c l a r k 横式的初始控制阚格为四边形网，采用l _ 4 双i 盘形分裂算子生成新网 格的搦扑，计算新顶点的几何规爱如下：( 注：本文所使用的f 预点为黼产生的新顶点， e - 顶点为边产生的新 顶点，v ：顶点为原来的顶觑 ( 1 ) f 顶点：设面的四个顶点为v 。，v 。，v ：，v ，则相应的r 顶点的使置取为 v f 嚣( v 。+ v l v 2 + v 3 ) 4 箨，2 ) ( 2 ) b 顶点：设内部边的端点为v 。，v 。，共事此边的两个四边形面分别为( v 。，v l ，v ：，v ，) 和 ( v 。，v 。，v 。，v ，) ，那么与此内部边相对应的融顶点为 基于细分方法的自由曲面造型 v 露= 妄喝+ v 1 ) + 去( v 2 + 毪+ v 4 + v s ) + 0 。3 ) ( 3 ) v - 顶点：蓉内部顶点v 静1 - 环( 楣邻面上所有薜v 的颚点，下同) 酶逸界顶点依次为 v 。，v t ，一，v ：。，其中嚣为v 上楣邻纛上的涨有点的个数，偶数下标懿联轰炎邻点，意数 下标的顶点为其四边形面上的对角顶点，相应的、。顶点为 印：，+ 盈掣如，+ 盐n - l 您 押i = 0摊i - - o c a b n u l l 和c l a r k i n 其。中自每d 嘏为属，= 3 ( 2 n ) ，。= 1 ( 4 n ) ，口。1 一成一，。 ( 4 ) 边界边( v o ，v 。) 上的e 一顶点 ( 5 ) 边界顶点v 在边界：的两个相邻顶点为v 0 ，v 。，则v 的v _ 顶点为 盆4 ) 0 。5 ) 式( 2 2 ) - ( 2 6 ) 由 1 4 】中的女暇0 约化得到，枥始揎啸l j 弼椿为任意多边形阚格时，可和溺 14 中规则作一次细分得到四边形网格，然后再用规则0 1 2 ) - 0 囝作余下的绷分。式 ( 2 ，2 ) 一( 2 6 ) 中顶点的移醢黔币分剐由图2 2a - e 舞5 猜谜。 ( a ) f 顶点( b ) e 顶点 ( c ) v 顶点 围2 2 c a l m u l i - c l a r k 细努模式t 实心圆患是耨成生的控$ 蒙点 f i g 2 2t h es t e n c i l so fc a t m u l l - c l a r k ss c h e m e t h ed o t sa r en g # c o n t r o l lp o i n t s 。2 ( d ) 边界e 顶点 l i b3 ，ti 8 ( e ) 边界v 顶点 大连理工人学硕士学位论文 当初始网格为规则网格时，c a u n u l l - c l a r k 模式生成三次b 样条曲丽，因此可看作是 三次b 样祭曲面的推广。上面给出的v - 点权值中，口。和成可以有多种选择，只要保证 v 的邻居点是4 时，见= 3 8 ，九= 1 16 即可，这个条件使得初始控制网格为舰则网格时 c a t m u l l - c l a r k 模式总生成三次b 样条曲筒。j o r g p e t e r s 和u l l i c h r e i f 诳明成、儿满足下 蠹静条臀时辍疆鏊淫是巍溪静【 4 】； 2 14 一i - + 再i 面雨1 c 。s 警+ 5 + 瓜砭覃丽礴丽 ( 2 7 ) 由于c a n n u l l c i a d ( 模式在正则网格女e 产生双三次b 样条曲面，因此除奇异顶点外曲面 是c 2 连续的【12 。i j a l l 和s c o y 证明曲面在奇异顶点处切平面( g 1 ) 连续【3 0 】，似没有考虑 曲面可能自交的情况。p e 时醑口r d 坝恂! 明了曲面在奇异点达到c 1 连续，权值范围由( 2 7 ) 式确定 1 6 卜1 9 9 8 年，雎眦h 及i m 1 龇勰出的算法使得曲面在奇异点处也达到g 2 述续 【1 7 】。 1 1 6 y 2 1 1 6 拂6 魏 粥2 3 蒂逑端点( 奎0 圆) 内部边的e _ 顶点 f i g 2 3e - p o i n to fi n t e r n a l1 i n ew i t hb o u n d a r ye x t r e m e 口o i n t 当网格带边界时，由式( 2 2 ) - ( 2 6 ) 生成的曲西在边界上是不光滑的 1 1 】， 改以边界顶点为端点的内部边的模式，如图2 3 所示，其中y 。= y ，= 一c o s 舞，7 ：= + c o s 各，这里门是边界顶点的阶。 2 5 2 c a t m u l l - c l a r k 细分曲蕊鼹橇啜点的极限缀置 为此需要修 缎分趣露毫缓多尼俺麟牲铡女g 投曩位嚣、法怒、翅逡及蔻率等，我嚣j 这萋只讨论缁 曰 基于臻势方法豹鸯峦益霹选壁 分曲面的极限位置。假如以初始网格为参数域对极限曲面作参数化，则初始网格顶点对 应浆投嚣使霆是毙较容易诗算的。设痰帮顼点v 的l 罚透爨顼点为，强，v 2 ，箕孛 n = jvl 。，则该顶点所对应的极限位置为： ，一矛v 1 + 4 ：，芎+ ：刀 v 。= 盎出生_ _ 鱼出丛盐 n ( n + 5 1 ( 2 ，8 ) 这蹩h a l s 渤d ，s 和d e r o s e 在l 辨3 年给出的【1 8 】。蕤中v 1 等于( 2 4 ) 式的唧；一南( 2 3 ) 计算，但式中的v o ，v 5 ，分别由v ，岵。也。，v 2 。，v 2 。代替；m r + , 由( 2 2 ) 式计算， 但v o ，h 分别由b 毪。v 2 + 1 ，b 。代替。 2 5 3c a t m u l l - c i a r k 纲分夔嚣的图例 下面赵c a l m u l l - c l a r k 细分曲面的图例。依次为左j 二角是原始控制曲面，右上角为细 分一次的曲面左下角为细分三次的曲面，右下角为细分的极限曲面。 图2 , 4c a i r n u u - c l m k 细分曲蕊形成的图示 f i g 2 。4g r a p ho fc a t m u l l - c l e e k ss c h e m e 人连理工大学硕士学位论文 d o o s a b i n 模式【1 5 是基于双二次b - 样条盐面的，与c h a i k i n 算法类似，d o o s a b i n 模式也类似于雕塑过程，即不断地切削网格的棱边和角，使之趋向光滑 2 6 1 d o o - s a b i n 细分规则 d o o - s a b i n 细分规则采用了顶点分裂操作作为拓扑规则，因此只生成f - 顶点。设有 n 1 j 4l 0 3 j 4 h y ”一 ( a ) 与顶点对应的f 顶点 边界f _ 顶点( 实凸圆) ( c ) 顶点标号示意图 图2 5d o o - s a b i n 细分模板 f i g 2 5o o o - s a b i ns u b d i v i s i o ns c h e m e 一4 n 边面，其顶点依次为，v i ，k v j 所在位置与图2 5 中的( a ) 的权值 的 位黝目对应，即空心圆点为k ，每个顶点v 都分裂出一个顶点v ，这些分裂出的顶点形 成一个与浚多边形面与原来的顶点相对应。此面内的分裂点形成个新的”边面，其中 实心点v 与垫b 点v ，对应，如图2 5 中的( c ) 所示。根据图2 5 中( a ) 和( c ) 有 一 h v o = 以v j # 0 其中，7 0 = 等，f = 5 ( 3 + 2 c o s 警) 。 ( 2 9 ) 对于开网格的边界则采用c h a i k i n 算法计算 1 0 ，每个边界顶点分裂为两个新顶点，其模 式如图2 5 中所示。d o o - s a b i n 模式生成一阶光滑的细分曲面，当初始控制网格为正则 网格时，生成取二次b 样条曲面。下面是一张简单的d o o s a b i n 曲面( 图2 ，6 ) 。 基于翔1 分方法的自由曲面造型 2 6 。2d o o - s a b i nl 嚣分麴嚣麓势l 子 下猫是d o o - s a b i n 绥分瓣瑟懿潮镄。发上角楚原始按躐莛萄，经过纲分轰形成右下 角的极限曲面。 2 7 l o o p 模式 图2 蓐d o o - s a b i n 细势耩式的翻铡 g 2 6t h eg r a p h so fd o o - s a b i n ss c h e m e l o o p 璧i t 分模式是凌1 9 8 7 年u t a h 大学l o o p 在硕论文中握爨秭瀑予e 霆次三 角形b 样条的细分模式 1 9 ，l o o p 细分模式生成的