（计算数学专业论文）poisson曲线曲面细分技术研究.pdf

西北工业大学硕士学位论文 摘要 随着计算机技术的普及和应用的日益广泛，细分方法近年来已经成为几何 造型、计算机辅助几何设计和计算机图形学领域内的一个国际研究热点。由于 细分方法易于产生性能良好的曲线曲面，因此细分曲线曲面造型技术已经成为 一种强大的曲线曲面造型工具。p o i s s o n 曲线曲面有着良好的几何性质和代数性 质，而且它可以表示特殊曲线曲面或超越曲线曲面，本文主要研究p o i s s o n 细分 曲线曲面的造型方法。 本文首先简要地介绍了细分方法的构造思想、发展历史、特点及其细分的 模式，并对典型的细分曲线曲面做出了比较详细的综述。按极限曲线曲面是否 过初始控制顶点，细分模式可以分为插值细分模式和逼近细分模式。本文主要 研究的是逼近细分模式。 其次，本文研究基于d ec a s t e l j a u 算法的b d z i c r 曲线细分。1 9 6 2 年法国雷 诺汽车公司的工程师b z i e r 构造出一种独创的参数多项式曲线，这种曲线采用 一组独特的多项式基函数，使得它具有许多优良的性质。1 9 6 3 年法国雪铁龙公 司的d ec a s t e l j a u 提出了b d z i g r 曲线的分割，s t h r k 和常庚哲分别给予了证明。 d ec a s t e l j a u 算法可以递推地定义一条具有有限个控制顶点的b d z i c r 曲线，此算 法也是一个细分算法。根据b e r n s t c i n 基函数的分割公式： ( 川= 乏( ，) 哆( r ) ，f 【o ，1 】，r f 就得到了b d z i c r 曲线细分算法。 再次，由于b d z i e r 曲线与p o i s s o n 曲线有许多相似点，例如，都是采用由 控制多边形定义曲线的方法，曲线都可以通过移动控制顶点来调整形状，而且， 在区间 0 ，玎】上再次b e m s t e i n 基函数，当厅- - yo o 时，就得到了p o i s s o n 曲线的基 函数，尤其值得注意的是p o i s s o n 基函数也有类似的分割公式。根据b d z i c r 曲 线细分技术，本文提出了p o i s s o n 曲线细分算法。因为任何一个解析函数都可 以表示成一个p o i s s o n 曲线，而解析函数也可以作t a y l o r 展开，但是与t a y l o r 逼近相比，此细分逼近算法具有很好的逼近效果。即当细分不断进行时，且参 数，_ 0 时，控制多边形趋于( 逼近) 解析函数。进一步本文还提出了n 阶p o i s s o n 西北工业大学硕士学位论文 曲线细分算法，最后发现常见的p o i s s o n 曲线( 1 阶) 细分算法只是n 阶p o i s s o n 曲线细分算法的一种特殊情形。 另外，本文还将曲线的细分延伸到曲面细分，从而提出了张量积p o i s s o n 曲面细分算法，此算法是一种稳定的逼近细分算法。 f m i n 在1 9 8 8 年提出了有理d ec a s t c l j a u 算法，1 9 8 5 年汪国昭、沈金福提 出了有理b 6 z i e r 曲线的细分和几何性质。基于此，本文也给出了有理p o i s s o n 曲线分割算法。 文中对上述的几种算法都给出了计算实例。从文中算例可以看出这些细分 算法具有很好的逼近效果，更具有实用性。 本文最后指出未来的研究方向，即基于权因子的有理p o i s s o n 曲线细分算 法，有理p o i s s o n 曲线的非均匀细分算法等，有理p o i s s o n 曲面细分算法，有理 p o i s s o n 曲线的升阶或降阶公式等。 关键词：细分曲线，b 6 z i e r 曲线，p o i s s o n 曲线，d ec a s t d j a u 算法，张量积曲面 l l 西北工业大学硕士学位论文 a b s t r a c t w i t ht h ep r e v a l e n c ea n dp r o g r e s s i v e l yb r o a da p p l i c a t i o no f c o m p u t e rt e c h n o l o g y , s u b d i v i s i o nm e t h o dh a sr e c e n t l yb e a 3 0 m eaf o c u so fs t u d yi ng e o m e t r i cm o d e l i n g ， c o m p u t e ra i d e dg e o m e t r i cd e s i g na n dc o m p u t e rg r a p h i c si nt h ew o r l d s u b d i v i s i o n a l l o w st og e n e r a t es m o o t hc u r v e sa n ds u r f f w , e sb ya p p l y i n gs i m p l er e f i n e m e n tr u l e st o t h eg i v e nc o n t r o lp o l y g o na n dc o n t r o lm e s h s u b d i v i s i o nm e t h o dh a sb e c o m ea p o w e r f u lt o o li nc o m p u t e ra i d e dg e o m e t r i cd e s i g na n dc o m p u t e rg r a p h i c sr e c e n t l y p o l s s o nc u r v e sa n ds n r f a c e sh a v es o n i ce x c e l l e n tg e o m e t r i ca n da l g e b r a i cp r o p e r t i e s ， b u ts o m es p e c i a lc u r 、，e sa n ds n r f a c e s c o m m o nt r a n s c e n d e n t a lc u r v e sa n ds u r f a c e sa r e r e p r e s e n t e da sp o i s s o nc r t w c sa n ds u r f - - sa c c u r a t e l y t h i st h e s i ss t u d i e sm o d e l i n go f s u b d i v i s i o ns c h e m ef o rp o i s s o nc t r v e sa n ds n , r a c c s a tf i r s t , t h i st h e s i sb r i e f l yi n t r o d u c e sc r e a t i v et h o u g h t s ，h i s t o r y , e h a r a c t e ra n d m o d e l so fs u b d i v i s i o na l g o r i t h m ，b u tw ei n t r o d u c et y p i c a ls u b d i v i s i o nc u r v e sa n d s u r f a c e si n d e t a i l a c c o r d i n g t os u b d i v i s i o nm o d e l s ，i nt h i st h e s i sw es t u d y a p p r o x i m a t i n gs u b d i v i s i o nm o d e l s s e c o n d l y , t h i st h e s i ss t u d i e sas u b d i v i s i o nf o rb d z i e rc u r v e sb a s e do nd ec a s t e l j a u a l g o r i t h m i n1 9 6 2f r e n c he n g i n e e rb d z i e rd e v e l o p e dak i n do fs p e c i a lp a r a m e t r i c p o l y n o m i a lc l j r y 娲t h i sc l l v e sh a v en l l m e r o u sr e m a r k a b l eg e o m e t r i cf e a t u r e s i n1 9 6 3 d ec a s t d j a up r e s e n t e das u b d i v i s i o nf o rb d z i e rc t n v e s s t i r ka n dc h a n gg e n - z h e g a v ei t sp r o o fr e s p e c t i v e l y d ec a s t e l j a na l g o r i t h mi sb o t h 锄e v a l u a t i o na n da s u b d i v i s i o np r o c e d u r e t h i sa l g o r i t h md e f m e sab 6 z i e rc n r v e a c c o r d i n gt o s u b d i v i s i o nf o r m u l ao f b e m s t e i nb a s i sf u n c t i o n 露( ，) 。荟( r ) 哆( f ) ，f 【o ，1 】，r r w e g e tas u b d i v i s i o na l g o r i t h mf o rb d z i e ro t u v e s ， t h i r d l y , s o m ep r o p e r t i e so fap o i s s o nc u l v ea r es i m i l a rt ot h o s eo fab d z i e r c u r v e f o re x a m p l e t h e ya r ec h a m c t 芒丽z i 甜b yt h e i rc o n t r o lp o l y g o n s ，a n dt h e i rs h a p e c a nb em o d i f i e di n t u i t i v e l yb ym o v i n gt h e i rc o n t r o lp o i n t s ，b u tp o i s s o nb a s i si sa i 塑j ! 三些查堂堡主兰堡笙壅 l i m i t i n gc a s eo ft h eb e r u s t e i nb a s i s ，a s g o e st oi n f i n i t e ，b e r u s t e i nb a s i sb e c o m e p o i s s o nb a s i s n o t i c e a b l y , t h ep o i s s o nb a s i sa l s oh a sas u b d i v i s i o nf o r m u l a e x t e n d i n g t h ed ec a s m u a ns u b d i v i s i o na l g o r i t h mt oa ni n f i n i t es e q u e n c eo fc o n t r o lp o i n t s d e f i n e san e wf a m i l yo fe u r v e s - - - - p o i s s o nc u r v e s ，t h i st h e s i sp r e s e n t sas u b d i v i s i o n s c h e m ef o rp o i s s o nc u r v e sb a s e d0 1 1d ec a s t e l j a ua l g o r i t h m t h ep r o p e r t i e so f p o i s s o n c u r v e sa r et h es a m ea sw h i c ho f t h eb d z i e rc u r v e s b e c a u s ea n y a n a l y t i cf i a n c t i o nfo i l t h ei n t e r v a l 【o ，回d e f i n e sap o i s s o nc u r v eo nt h i ss a m ei n t e r v a l b u tt h ea n a l y t i c f u n c t i o nfa l s oe x p r e s s e st a y l o rs e r i e si nt e r m so ft h e o r i e so ff u n c t i o no fc o m p l e x v a r i a b l e i nc o n t r a s tt ot a y l o ra p p r o x i m a t i o n , t h i ss u b d i v i s i o na l g o r i t h m sh a v eg o o d a p p r o x i m a t i n gr e s u l t s t h a ti s 。a st h ec u r v es u b d i v i d e di n c e s s a n t l ya n dp a r a m e t e r ， g o e st oz e r o ，c o n t r o lp o l y g o n sq ( r ) = ( 蜴( ，) ，蜴r ) , - - ) a p p r o x i m a t e ( c o n v e r g e st o ) t h ea n a l y 虹ef u n c t i o nc u r v eei nt h em e a n t i m e ，t h i st h e s i sp r e s e n t ss u b d i v i s i o ns c h e m e f o rp o i s s o nd e g r e eu i nt h el a s t , w ef m dt h a tas u b d i v i s i o ns c h e m ef o ro r d i n a r y p o i s s o nc l l r v e $ o n l yi sas p e c i a le x a m p l eo f p o i s s o nc l v e $ d e g r e e 儿 w h a t sm o r e ，b ye x t e n d i n gs u b d i v i s i o ns c h e m e sf o rp o i s s o nt op o i s s o ns u r f a c e s ， t h i st h e s i sp r e s e n t sas u b d i v i s i o na l g o r i t h mf o rt e n s i o np r o d u c tp o i s s o ns u r f a c e s t h i s a l g o r i t h mi ss t a t i o n a r ya p p r o x i m a t i n gs u b d i v i s i o n i n1 9 8 8f r a i np r e s e n t sd ec a s t e l j a ua l g o r i t h mo fr a t i o n a lb d z i e rc u r v e s ，i n1 9 8 5 c r u o z h a ow a n ga n dj i n f us h e np r e s e n ts u b d i v i s i o na n dp r o p e r t i e so fr a t i o n a lb d 西e r c u r v e s s ot h i st h e s i sa l s op r e s e n t sas u b d i v i s i o na l g o r i t l m af o rr a t i o n a lp o i s s o n c u r v e s ht h i st h e s i s , s o m ec a s e s 勰g i v e nt oi l l u s t r a t et h ee f f i c i e n c yo ft h ea l g o r i t h m s f r o mt h e s ec a s e sw ef r e dt h e s es u b d i v i s i o na l g o r i t h m sh a v ea p p r o x i m a t i n gr e s u l t sa n d p r a c t i c a b i l i t y f i n a l l y , t h et h e s i sp r e s e n t sr e s e a r c hi n t e r e s t si nt h ef i t t u r e , t h a ti sa na l g o r i t h mf o r t h es u b d i v i s i o no f r a t i o n a lp o i s s o nc n r v e sb a s e do nw e i g h t s a i lu n e v e na l g o r i t h mf o r t h es u b d i v i s i o no f r a t i o n a lp o i s s o nc u r v e s ，as u b d i v i s i o no f r a t i o n a lp o i s s o n s u r f a c e s ， d e g r e ee l e v a t i o na n dd e g r e er e d u c t i o no f r a t i o n a lp o i s s o nc u r v e s ，e t e i v 西北工业大学硕士学位论文 k e yw o r d s ： s u b d i v i s i o nc l l r v e s , b 6 z i e tc u r v e , p o i s s u nc l l r v e , d ec a s t e l j a u v 西北工业大学业 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期间论文工作 的知识产权单位属于西北工业大学。学校有权保留并向国家有关部门或机构送交论文的复 印件和电子版。本人允许论文被查阅和借阅。学校可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 同时本人保证，毕业后结合学位论文研究课题再撰写的文章一律注明作者单位为西北工业 大学。 保密论文待解密后适用本声明。 学位论文作者签名 办矿弓月押 f 指导教师签名- 麴 2 学。- | 每弓a 蕊 西北工业大学 学位论文原创性声明 秉承学校严谨的学风和优良的科学道德，本人郑重声明：所呈交的学位论文，是本 人在导师的指导下进行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容 和致谢的地方外，本论文不包含任何其他个人或集体己经公开发表或撰写过的研究成 果，不包含本人或其他已申请学位或其他用途使用过的成果。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式表明。 本人学位论文与资料若有不实，愿意承担一切相关的法律责任。 学位论文作者签名 a 们年 瓣 孑， 西北工业大学硕士学位论文 第一章绪论 随着计算机技术的发展和普及，计算机辅助设计与制造技术 ( c a d ( c o m p u t o - a i d e dd e s i g n ) c a m ( c o m p u t e r a i d e dm a u f a c t u r e ) ) 得到了迅猛 的发展，他们推动了许多领域的设计革命，c a d c a m 技术的发展和应用水平 已经成为衡量一个国家现代化水平的重要标志之一。而计算机辅助几何设计 ( c o m p u t e ra i d e dg e o m e t r yd e s i g n , 简称c a g d ) 是c a d c a m 的理论基础和关 键技术，一旦c a g d 中有一种新的几何造型出现，往往就能很快地应用到 c a d c a m 系统中。早期是由数学放样和外形设计的实际需要，作为样条函数 及函数逼近论等在飞机、汽车、船舶制造中的实际应用而发展起来的。现在， 它已与许多学科有了紧密联系，成为一门新兴的交叉学科和边缘学科。c a g d 主要研究在计算机图像系统的环境下对曲面信息的表示、逼近、分析和综合。 现在，越来越多的科研人员从事这方面的研究，并取得了瞩目的成果。其应用 范围已从最初的飞机、汽车以及船舶制造业发展到建筑设计、生物工程、医疗 卫生事业、航天材料、电子工程、服装设计、多媒体技术、动画制作等各个技 术领域。随着计算机图形显示对于真实性、实时性和交互性的日益增强，图形 工业和制造工业迈向一体化、信息化和网格化步伐的日益加快，c a g d 得到了 飞速的发展。它经历了从离散到连续，再从连续到离散的发展过程。但是，当 细分( s u b d i v i s i o n ) 技术出现以后，这种造型方法得到了很大的改进，人们可以直 接从离散到离散，减少了过去的建立连续函数的那个环节。 本章主要介绍细分方法产生的背景、发展概况、特点、分类、应用以及细 分发展的新思想趋势等，并将扼要介绍几种常用的基本细分方法。最后顺便给 出了本文的主要研究内容。 1 1 细分方法产生的背景 曲线曲面造型是计算机辅助几何设计和计算机图形学( c o m p u t e r g r a p h i c s ，简称c g ) 的一项重要内容，主要研究在计算机图像系统的环境下对曲 面的表示、设计、显示和分析。它起源于汽车、飞机、船舶、叶轮等的外形放 西北工业大学硕士学位论文 样工艺，由c o o n s 、b 6 z i e r 等大师于2 0 世纪6 0 年代奠定理论基础。2 0 世纪6 0 年代是c o o n s 技术和b a i l e r 技术，7 0 年代是b 样条技术，8 0 年代是有理b 样 条技术，现在己形成了已非均匀有理b 样条( n o n - u n i f o r mr a t i o n a lb s p l i n e ，简 称n u r b s ) 参数化特征设计和隐式代数曲面表示这两类方法为主体，以插值 ( i n t e r p o l a t i o n ) 、拟合f l i t t i n g ) 、逼近( a p p r o x i m a t i o n ) 为骨架的几何理论体系。 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 年法国雷诺( r e n a u l t ) 汽车公司的b 6 五盯提出一种由控制多边形设计 曲线的新方法，设计人员可以通过移动控制顶点来达到控制曲线形状的目的， 并可以预测曲线的变化趋势。这种方法不仅简单易用，而且解决了整体形状控 制问题，且具有局部保凸的性质，把曲线曲面的设计向前推进了一大步，为曲 面造型的进一步发展奠定了坚实的基础。早些时候，法国雪铁龙( c i t r o s n ) 汽车 公司的d ec a s t e l j a u 也独立研究出同b a f i e r 类似的方法。随后，美国通用汽车 公司的g o r d o n 和r i e s e n f e l d 提出了矩形域上的张量积曲面和三角域上的 b e m s t e i n b 6 z i c r 曲面( b b 曲面) ，但该方法仍存在连接问题和局部修改问题。 1 9 7 2 年d e b o o r 和c o x 分别提出了关于b 样条的一套标准算法，即d e b o o r - c o x 递推公式，1 9 7 4 年g o r d o n 和r i e s e n f e l d 又把b 样条理论应用于形状 描述，最终提出了b 样条方法。这种方法继承了b 6 z i e r 方法的一切优点，克服 了b 6 z i 盯方法存在的缺点，较成功地解决了局部控制问题，又轻而易举地在参 数连续性基础上解决了连接问题，从而使自由曲线曲面形状的描述问题得到较 好解决。但是该方法不能精确的表示除抛物线和抛物面之外的二次曲线曲面， 如圆锥截线和球面、椭球面等初等解析曲面，只能给出近似表示。1 9 7 5 年美国 s y r a c u s e 大学的v e r s p r i l l e 首次提出了有理b 样条方法，来克服上述的缺陷。后 来经过p i e g l 和t i l l e r 等人的努力，发展并健全了非均匀有理b 样条方法。该 方法可以精确的表示二次规则曲线曲面，从而可以用统一的数学形式表示规则 曲面与自由曲面；另外，该方法中引入了权因子，可以方便的通过调整权因子 2 西北工业大学硕士学位论文 来控制曲线曲面的形状。 国际标准化组织( i s o ) 于1 9 9 1 年颁布了关于工业产品数据交换的s t e p 国 际标准，将n u r b s 方法定义为工业产品几何形状的唯一数学描述方法。虽然 n u r b s 方法在造型方面有许多优势，但是，仍存在一定的缺陷。 m 瓜b s 方法的主要缺点是： 单一的n u r b s 曲面与其它参数曲面一样，仅限于表示在拓扑上 等价于一张纸、一张圆柱面或圆环面，若用它来表示更复杂的曲 面片，必须用。退化片”，或者多片4 缝合”的技术，相当繁琐。 n u r b s 曲面的光滑拼接也是一个非常复杂和困难的问题。例如 为了表示如人的头、手或服饰，必须要对分片的n u r b s 曲面进 行裁剪和修复，尽管目前有一些商用的系统软件可以对n u r b s 曲面进行裁剪，但是代价昂贵，而且有一定的数值误差，加之模 型是活动的，要在曲面的缝接除保持光滑，即使是近似的光滑也 有一定的难度。 由于n u r b s 方法不能表示任意拓扑结构的曲面。而细分方法却能够很好 地产生拓扑结构复杂的曲面，因此，成为近些年曲线曲面造型技术研究的一个 热点。 1 2 细分方法的概述 1 2 1 细分曲线曲面的构造思想 细分方法容易产生性能良好的蓝线曲面，近些年已成为计算机辅助几何 设计及计算机图形学领域内一项重要的研究课题。其构造思想是从一个控制 多边形或初始控制网格出发，按照事先选取的细分规则( 一般是加权平均) ， 在给定的初始控制多边形或控制网格中插入新顶点( 这些新顶点是初始控制 多边形或控制网格上某几个顶点的加权平均) ，再连接这些新顶点得到新控制 多边形或控制网格，所得新控制多边形或控制网格是初始控制多边形或控制 网格的加细。不断重复上述过程，随着细分的不断进行，控制多边形或控制 网格就被逐渐加细，其极限状态为一条曲线或一张曲面，称为递归细分曲线 西北工业大学硕士学位论文 或递归细分曲面。其实质是一类从序列到序列的迭代算法。 1 2 2 细分方法发展历史 细分算法的由来最早可以追溯到1 9 5 6 年d er a h m g 提出的割角( c u t t i n g c o m e 0 思想。其思想是通过对折线角点进行切割生成光滑。1 9 7 4 年，c h a i k i n 1 j 提出了类似的生成曲线的细分方法。1 9 7 8 年，c a t m u l l 和c l a r k ! 封提出了著名的 c a a n u l l c l a r k 细分模式，标志着细分方法正式成为曲面建模的手段。此时，d o o 和s a b l a 采用离散f o u r i e r 变换的方法，对c a t m u l l c l a r k 模式的收敛性进行了 分析，开创了细分模式收敛性矩阵特征分析的先河。 纵观细分发展历史大致可以分成如下三个阶段： 第一阶段：1 9 8 0 年前后，提出并初步发展时期。1 9 7 4 年，c h a i k i n 用害角 法产生曲线，把离散细分的概念引入到图形学界。1 9 7 8 年，c a t m u l l 和c l a r k , d o o 和s a b i n 分别将双三次和双二次b 样条推广到任意拓扑结构的网格上。 c a t m u l l c l a r k 细分模式和d o o - s a b i n 关于奇异点处行为的分析理论标志着细分 方法正式成为曲线曲面造型的一种手段。由于c a r n u l l - c l a r k 细分法能用较少的 控制顶点迅速生成具有任意形状的光滑曲面( 除奇异点处为c 1 连续外，曲面处处 为c 2 连续) ，此方法很快在造型和动画领域付诸应用，从此离散细分曲面造型得 到广泛的研究。 第二阶段：8 0 年代末到9 0 年代初的形成时期。这一阶段出现了许多著名 的细分方法，如1 9 8 7 年o y n 提出四点法曲线插值模式及六点法曲线插值模式， 1 9 9 1 年d y n 又提出b i n a r y 细分模式，稳定细分模式 c a v a r e t t a1 9 9 1 1 ，l 0 0 p 模式 l o o p1 9 8 7 ，蝶形模式 o y n1 9 9 0 1 等。在此期阃，也有一些方法是对旧方法进行 改进 n a s a l1 9 8 7 ，1 9 9 1 ；h a l s t e a d1 9 9 3 ；h o p p e1 9 9 4 ；z o 咖1 9 9 6 l o o p 模式是一种 基于三角网格的细分算法，其实质是四次三方向箱样条在任意拓扑三角网格上 的推广。在缨分曲线造型方面，引入均差细分、生成多项式、生成函数等概念 描述细分过程，关于细分模式的收敛性、连续性分析已有了系统的研究成果。 在细分曲面造型方面，引入了细分矩阵描述细分过程，引入离散f o u r i e r 方法、 矩阵特征根法、矩阵逼近论等方法多种细分曲面进行特征分析及收敛性连续性 分析。 4 西北工业大学硕士学位论文 第三阶段：9 0 年代中期至今为发展时期。这一阶段出现了一些新的细分方 法，也有一些方法是对老方法进行改进。在细分曲线造型方面，蔡志杰对非均 匀有序控制顶点时的四点法及变参数四点法的收敛性和连续性进行了分析；骆 岩林研究了生成曲线的有理稳定细分方法；丁友东提出了非线性四点插值细分 法；金建荣提出了非均匀四点插值细分法，生成的曲线达到g 1 连续。2 0 0 2 年， h a s s a n 提出了t e r n a r y 四点插值细分法，生成的曲线达到g 2 连续。在曲面造型 方面，p e t e r s 和r i e f 提出m i d - e d g e 细分模式；s e d e r b e r g 等在任意拓扑网格上引 入非均匀节点区间的概念，推广得到非均匀细分曲面；d e r o s e 将细分曲面造型 方法用于人物动画的设计；v e l h o 和z o r i n 提出了4 8 细分法，其实质是c 4 连续 的四方向样条在任意网格拓扑结构上的推广，在正常点是c 4 连续的，在奇异点 是c 1 连续的；k o b b e l t 先提出了适合四边形网格的插值算法，后来又提出了3 细分模式；n a s d n 提出了使细分曲面插值预先指定的二次样条曲线的算法；l e v i n 设计了细分规则用于网格曲线插值的联合细分模式；h a b b i b 提出了基于顶点和 边插入的曲线网插值方法；b i e r m a n n 提出了边界法向插值方法等等。y m g 和 z o 血提出一种可以用于构造非流形曲面的细分方法。近些年提出的细分模式还 瞧 有：i v r i s s i m t z i s 等 1 w i s s i m t z i s2 0 0 4 的5 模式；p e t e r s p e t e r s2 0 0 3 1 基j4 3 模式； h a s s a n 等 h a s s a n2 0 0 2 的t e r n a r y 四点插值细分；j e n a j e n a2 0 0 2 基于三角样条 的细分算法；2 0 0 4 年李桂清提出了2 细分等。 纵观细分发展的历程可以看出，细分的发展是从最初的曲线到张量积曲面， 再到任意拓扑结构网格的曲面；从单一的四边形网格或三角形网格到混合网格； 从样条推广到互压细分；从最初单一的细分到可以产生局部特征的造型曲 面。可见，细分是向着一个造型能力更强，使用更方便，更加经济有效的方向 发展的。 1 2 3 细分方法的特点 i 曲线曲面的生成显示速度快：符合计算机从离散到离散的造型特点。 数值稳定性( n u m e r i c a ls t a b i l i t y ) ：凸线性组合的细分方法是一个迭代过 程，有很好的数值计算稳定性。 西北工业大学硕士学位论文 i i i 模型简单( m o d e ls i m p l i c i t y ) ：细分方法的数学模型仅涉及初始数据网格和 细分规则，而细分规则往往简单明了，易于实现，效率也高。 可升级性( s c a l a b i l i t y ) ：细分算法具有多分辨的性质，特别适合于层次细 节技术。 v 适用于任意的拓扑网格( a r b i t r a r yt o p o l o g ym e s h e s ) ：细分曲面可以定义在 任意的拓扑网格上，三角形网格或者四边形网格或者两者的混合网格均 可。 表示的一致性( u n i f o r m i t yo f r e p r e s e n t a t i o n ) ：这里的一致性是指细分法把 曲面片与多面体的表示统一起来，使得造型系统有了统一处理曲面和多 面体表示的手段。 1 2 4 细分模式的分类 从不同角度可以对细分模式进行分类 按极限曲线曲面是否过初始控制顶点，细分模式可以分为插值细分模式 ( i n t e r p o l a t o r ys u b d i v i s i o ns c h e m e s ) 逼近细分模式( a p p r o x i m a t i n g s u b d v i s i o ns c h e m e s ) 。 按控制点列的改进规则的特点，细分模式可分为顶点插入细分模式& 割角 细分模式。 按不同层细分规则的特点，细分模式可分为稳定细分模式( s t a t i o n a r y s c h e m e s ) 非稳定细分模式( n o n - s t a t i o n a r ys c h e m e s ) 。不同细分层次采 用相同细分规则的细分模式称为稳定细分模式，否则成为非稳定细分模 式。经典的细分模式大多为稳定细分模式。 按同一层细分规则的特点，细分模式可分为均匀细分模式( u n i f o r m s c h e m e s ) 非均匀细分模式( n o n - u n i f o r ms c h e m e s ) 。每一层细分中网格 的不同部分采用相同细分规则的细分模式称为均匀细分模式，否则称为非 均匀细分模式。 按初始控制网格的类型，细分曲面模式可分为基于三角形网格的细分模式 基于四边形网格的细分模式。 根据拓扑分裂类型分类，一个是面分裂( f a c es p l i t ) ，另一个是点分裂( v e r t e x s p l i t ) 。第一种方式的细分方法称为基本型( p r i m e ) ，即组成网格的每一个 6 西北工业大学硕士学位论文 面被分裂为四个，旧点拓扑位置保持不变，自每条网格边上插入一个新点， 对四边形网格，每一个网格面中也要插入一个新点。第二种方式的细分方 法称为对偶型( d u a l ) ，对应于每个旧点，有多个新点产生，每个点对应一 个与这个旧点相邻的网格面；对应于每一条网格边，生成一个新面；旧的 网格面保持不变。 1 3 典型的细分曲线曲面造型 本节将具体地介绍一些常见的细分曲线和细分曲面。 1 3 1 典型的细分曲线造型 最早产生细分曲线算法的是1 9 5 6 年d e r h a m g 提出的称为割角的细分算法， 11 该算法的思想就是将平面上的一个多边形的每一条边按去专：三的比例分割，然 r - t r 后将每一个角去掉，得到一个新的多边形，不断的重复此过程，就得到一个多 边形序列，它的极限是一条连续可微的曲线，细分进程如图1 1 所示。 1 9 7 4 年c h a i k i n 进一步推广了该算法。其算法本质是一种双割角法，实际 二 ， 上产生了二次b 样条曲线，因而是c 1 连续的。 图1 1c h a i k i n 割角法细分示意图，( a ) 表示初始控制多边形；( b ) _ q ) 表示经过一次，二次 和三次细分后的控制多边形 7 西北工业大学硕士学位论文 同所有的细分一样c h a 救i n 细分也有两个基本规则，即拓扑规则和几何规则。 i上 44 c：o 图1 2 c l m i k i n 细分的拓扑规则图1 3c h a i k j n 细分的掩模( 实心圆点表示新顶点) 拓扑规则( 如图1 2 所示) 1 ) 对每一个旧顶点叶，插入两个新顶点v 2 。，屹。l ， 2 ) 连接新顶点v 2 ，吃，“，旧顶点一被边屹jv 2 。替换，旧边的长度( 如e _ 。) 相对新边长度( 如屹。吃。+ 2 ，) 明显减少 几何规则 屹2 孑一+ i 哆“2 i v + i 一 根据上面介绍，现在总结一下细分曲线的特点。 c h a i n 割角法可以推广到一般的均匀割角法：给定初始有序控制顶点集 p o = 弓o j ，n l o + l ，口r 。，设一- - c 矿j ) j - ”0 1 为第七次细分后的有序控制顶点集，细 分规则如下： 嚣2终芒麓osi编_2knpp。娜矧, 0 i 【与：=+ ( 1 一声) 罐i ， 2 捍 一。 其中口，为割角参数，当口= ，= 时，恰好为c l a a i k i n 割角法。当 44 o 昙，口：昙+ 时，上述割角法可达到c t 连续，但是不能达到c ：连续。 设给定初始有序控制顶点集p o = p ；，e 山 ，芎，其中以为初始有序 控制顶点集的有限下标集。设= 彤；，以 为第七此细分后的有序控制顶点 集，以为相应的有限下标集。则细分规则可以写成一个方程为： 8 西北工业大学硕士学位论文 彤“= 彳 坨z 其中口= 哆 为实系数序列，只有有限个分量不为零称为掩模( i n a s k ) 由细分法s 的掩模口所确定的多项式烈力2 莩q 一称为细分算法s 的生成 当p = 2 ，口= 争l ，3 ，3 ，l 】时，对应的细分规则为 p = 丢彳+ i 3 p 。k ，到玎 l 制= 三口+ i 1p 。k ，o f 鲋珂 当p = 2 ，口= _ 【1 一仍u ，互1 + 口，1 ，j 1 + ，0 国】时，对应的细分规则为 f 露“= 彳， 一l i 2 k n + l 。i 磋：= 一喊+ 哼1 + 国) 彳+ 哇+ 国) # 毛一蟛：，一1 f 2 栉+ l 即是著名的d ) ，n 四点插值法。当j 缈i j 1 ，四点插值极限曲线存在；当 o 丁, 5 - 1 ，四点法插值曲线的极限曲线是c 1 连续的。 当p = 3 时，细分曲线为t e r n a r y 曲线。 当p = 3 ，口= i 1 呜，o ，q ，l ，吃，o ，吻】时，其中，嘞= 一丙1 一吉， 啊：罢+ 要，：三一委，鸭；一去+ = 1 ，细分曲线为四点t c n m i y 细分插 啊2 丙+ j 2 丙一i 鸭5 一丙+ i 捌分凹线刀凹扁t c n m i y 剐万佃 f= 劈 搿= 礞。+ 喁彳+ 礞。+ 吗礞： 【嗽= 瑞+ 锡学+ 礞。+ 砹： 其中为形状参数，当西1 3 时，危= 面3 。 2 ) 边界点的处理与c a t m u l l c l a r k 细分模式相同。 图11 ( a ) 一( d ) 为l o o p 细分模式各类顶点的模板。 图1 2 ( a ) - ( d ) 为l o o p 细分曲面的形成。 4 改进的蝶形细分模式 该算法首先由d y n 提出的，由于其面具有与蝴蝶相似而得名。蝶形模式采 用1 - 4 三角形分裂，它是一种c 1 插值型细分算法，但只适合于规则网格( 如图 1 1 3 ( a ) ) 。且生成的曲面在奇异点处只达到c o 连续。 瘩：畿 ( a ) c o )( c ) 图1