（计算数学专业论文）pnary细分曲线造型及其应用.pdf

p - n a r y 细分曲线造型及其应用 中文摘要 本文研究p - n a r y 细分曲线造型方法及其简单应用细分方法近年来已成为 计算机辅助几何设计及图形学领域的一项重要研究内容由于细分方法易于产 生性能良好的曲线曲面，因此细分曲线曲面造型技术已成为一种强大的曲线曲 面造型工具本文的目的是研究一些行之有效的细分曲线造型方法，以进一步提 高细分方法在光滑曲线造型方面的能力，同时探讨细分曲线造型方法的应用本 文研究的问题包括：b i n a r y 细分曲线造型、t e r n a r y 细分曲线造型、p - n a r y 细分曲 线造型 本文先简要地介绍了细分方法的构造思想、发展历史、特点及分类等，并 就典型的细分曲线及细分曲面两方面作出了较系统的综述 在b i n a r y 细分曲线造型方面，本文分别提出了包含两个形状参数的双参数 四点b i n a r y 细分法及双参数三点b i n a r y 细分法，其中双参数四点b i n a r y 细分法 是经典四点法的推广基于细分曲线造型的b i n a r y 细分法的收敛性连续性理论， 本文给出并证明了双参数四点b i n a r y 细分法及双参数三点逼近b i n a r y 细分法一 致收敛及k 阶连续的充分条件，并给出初始控制多边形给定的条件下，选择四 组不同的形状参数时极限曲线的图形理论和数值算例表明，引入双参数后，可 通过两个形状参数的选择来提高细分曲线的光滑度并控制、修改曲线。细分曲 线的光滑度可分别达到四阶和三阶采用本章的方法，既可造型光滑插值曲线， 又可造型满足高阶光滑的逼近曲线 在t e r n a r y 细分曲线造型方面，本文提出一类包含一个形状参数的单参数三 点t e r n a r y 插值细分法( 第三章) 及包含三个形状参数的三参数四点t e m a r y 插值细 分法( 第四章) ，给出并证明了单参数三点t e m a r y 插值细分法一致收敛、c 连续 的充分条件及三参数四点t e r n a r y 插值细分法一致收敛、c 1 连续、c 2 连续的充分 条件理论和数值算例表明，单参数三点t e r n a r y 插值细分法的光滑度与经典四 点插值细分法相同，而三参数四点t e r n a r y 插值细分法的光滑度与之相比则提高 了一阶 本文在b i n a r y 细分曲线造型方法及单参数三点t e r n a r y 插值细分曲线造型方 法的基础上，提出了p - n a r y 细分曲线造型方法b i n a r y 细分曲线造型方法为 p - n a r y 细分曲线造型方法当p = 2 时的特例，t e r n a r y 细分曲线造型方法则为p - n a r y 细分曲线造型方法当p = 3 时的特例本文引入了p n a r y 细分法及其均差细分法、 差分细分法、p - n a r y 细分法一致收敛、c k 连续、p - n a r y 细分法的生成多项式等基 本概念，分析了p - n a r y 细分法的一致收敛性及c 。连续性，给出并证明了p - n a r y 细分法一致收敛的必要条件、充要条件及c 2 连续的充分条件，并研究了p - n a r y 细分法的收敛性连续性理论的应用问题 关键词：曲线曲面造型，细分法，细分曲线，细分曲面，控制多边形，控制网 一致收敛，c 。连续，插值细分 2 ：! ! 垡塑坌些些堕型丛基生旦 a b s t r a c t t h i st h e s i ss t u d i e sm o d e l i n ga n da p p l i c a t i o no fs u b d i v i s i o nc u r v e s s u b d i v i s i o n m e t h o dh a sb e c o m ea ni m p o r t a n tt 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 d c o m p u t e rg r a p h i c sr e c e n t l y s u b d i v i s i o n a l l o w st o g e n e r a t e s m o o t hc u r v e sa n d s u r f a c e sb y a p p l y i n gs i m p l e r e f i n e m e n tr u l e st ot 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 l m e s h t h et h e s i si n v e s t i g a t e ss o m ee f f i c t i v em o d e l i n ga p p r o a c h e sf o re n h a n c i n gt h e a b i l i t vo fm o d e l i n gs m o o t hs u b d i v i s i o nc u r v e so ft h es u b d i v i s i o nm e t h o d s t h e i n v o l v e dp r o b l e m si n c l u d eb i n a r ys u b d i v i s i o nc u r v em o d e l i n g ，t e r n a r ys u b d i v i s i o a c u r v em o d e l i n ga n dp n a r ys u b d i v i s i o nc a l v em o d e l i n g a f e r b r i e f l yr e v i e w i n g t h ec l a s s i f i c a t i o na n dh i s t o r yo fc u r v ea n ds u r f a c e m o d e l i n g ，t h i sp a l e r d i s c u s s e st h eb a s i c c o n s t r u c t i n g i d e a s ，t h eh i s t o r y ，t h e c l a s s i f i c a t i o n ，t h ec h a r a c t e r sa n dt h ea d v a n t a g e so f s u b d i v i s i o ns c h e m e s a s u r v e yo f t h ec l a s s i c a ls u b d i v i s i o nc u r v e sa n ds u r f a c e si sp r e s e n t e d o n b i n a r y s u b d i v i s i o nc u r v e sm o d e l i n gt h et h e s i sf i r s tp r e s e n tak i n do f f o u r - p o i n t b i n a r ys u b d i v i s i o ns c h e m ew i t ht w op a r a m e t e r s ，w h i c hh a s ab e t t e rs m o o t h n e s s p r o p e r t yt h a nc l a s s i c a lf o u r - p o i n ts u b d i v i s i o ns c h e m e 。a n d a n o t h e rk i n d o f t h r e e - p o i n t b i n a r ys u b d i v i s i o ns c h e m e t h et h e s i sp r o v e st h es h 伍c e n tc o n d i t i o n so f t h eu n i f o r m c o n v e r g e n c ep r o p e r t i e sa n dc c o n t i n u i t yp r o p e r t i e so f t h e s et w ob i n a r ys u b d i v i s i o n s c h e m e sb a s e do nt h er e s u i t so ft h e c o u v e r g e u c ep r o p e r t i e sa n dt h ec o n t i n u i t y p r o p e r t i e so fb i n a r ys u b d i v i s i o ns c h e m e sp r e s e n t e db yd y n o n ec a l lm o d i f yt h e s h a p e o ft h es u b d i v i s i o nc u r v e sa n dg e ts m o o t hc u r v e s b yc h o o s i n gt h e s et w o p a r a m e t e r sa p p r o p r i a t e l y u s i n gt h ef o u r - p o i n tb i n a r ys u b d i v i s i o ns c h e m ew i t ht w o p a r a m e t e r sp r e s e n t e di nt h et h e s i s o n ec a r ln o to n l ym o d e ls m o o t hi n t e r p o r l a t i n g s u b d i v i s i o nc u r v e sb u ta l s oc a nm o d e la p p r o x i m a t i n gs u b d i v i s i o nc u r v e sw i t hh i g h s m o o t h n e s s i ti sp r o v e dt h a tt h ef o u r - p o i n tb i n a r ys u b d i v i s i o ns c h e m ep r e s e n t e di n t h i st h e s i sc a ng e n e r a t ec f u n c t i o n s ，a n dt h et h r e e - p o i n tb i n a r ys u b d i v i s i o ns c h e m e c a n p r o d u c e sc s f u n c t i o n s 0 nt e r n a r ys u b d i v i s i o nc u r v e sm o d e l i n gt h et h e s i sp r e s e n tak i n do ft h r e e p o i n t t e r n a r yi n t e r p o l a t i n gs u b d i v i s i o ns c h e m ew i t ho n ep a r a m e t e ri nc h a p t e r3 ，a n dl a t e r p r e s e n t ak i n do ff o u r - p o i n tt e r n a r y i n t e r p o l a t i n gs u b d i v i s i o ns c h e m ew i t ht h r e e p a r a m e t e r si nc h a p t e r4 t h et h e s i sp r o v e sm e s u f f i c e n tc o n d i t i o n so ft h eu n i f o r m c o n v e r g e n c ep r o p e r t i e s a n dc 1 c o n t i n u i t yp r o p e r t i e s o ft h e t h r e e - p o i n tt e r n a r y i n t e r p o l a t i n gs u b d i v i s i o ns c h e m ew i t ho n ep a r a m e t e r t h et h e s i sa l s op r o v e st h e s u f f i c e n tc o n d i t i o n so ft h eu n i f o l l nc o n v e r g e n c ep r o p e r t i e s 。c 1a n dc 2c o n t i n u i t y p r o p e r t i e s o ft h e f o u r - p o i n tt e r n a r yi n t e r p o l a t i n g s u b d i v i s i o ns c h e m ew i t ht h r e e p a r a m e t e r s b a s e do nt h er e s u l t so ft h eu n i f o r mc o n v e r g e n c ep r o p e r t i e sa n dc 。 c o n t i n u i t yp r o p e r t i e so f p n a r ys u b d i v i s i o ns c h e m e sp r e s e n t e di nc h a p t e r4 t h et h e s i sg e n e r a l i z e st h e b i n a r ys u b d i v i s i o ns c h e m e si nc h a p t e r2a n dt h e t h r e e p o i n tt e r n a r yi n t e r p o l a t i n g s u b d i v i s i o ns c h e m ei n c h a p t e r 3t o p - n a r y ：! 型塑坌些堑壅型垦基生旦 s u b d i v i s i o n s c h e m e s b i n a r y s u b d i v i s i o ns c h e m e si s a s p e c i a l c a s eo f p - n a r y s u b d i v i s i o ns c h e m e sw h e n pe q u a l s2 ，w h i l et e r n a r y s u b d i v i s i o ns c h e m e si sa s p e c i a l c a s eo fp - n a r ys u b d i v i s i o ns c h e m e sw h e npe q u a l s3 t h et h e s i sa l s op r o p o s e sa n d p r o v e s t h es u f f i c e n tc o n d i t i o n so ft h eu n i f o r mc o n v e r g e n c e p r o p e r t i e s a n dc c o n t i n u i t yp r o p e r t i e so f p - n a r ys u b d i v i s i o ns c h e m e s a tt h ee n d o f t h et h e s i sak i n do f f o u r - p o i n tt e r n a r yi n t e r p o l a t i n g s u b d i v i s i o ns c h e m ew i t ht h r e e p a r a m e t e r s i s p r e s e n t e d t od e s c r i b et h ea p p l i c a t i o no f t h ep - n a r ys u b d i v i s i o n t h e o r yp r e s e n t e di nt h e t h e s i s k e y w o r d s ：c u r v ea n d s u r f a c em o d e l i n g ，s u b d i v i s i o ns c h e m e s ，s u b d i v i s i o nc u r v e s ， s u b d i v i s i o ns u r f a c e s ，c o n t r o lp o l y g o n ，c o n t r o ln e t tu n i f o r m c o n v e r g e n c e ， c k - c o n t i n u i t y ，g e n e r a t i n gp o l y n o m i a l ，g e n e r a t i n gf u n c t i o n ，i n t e r p o l a o r y s u d i v i s i o n p - n a r y 细分曲线造型及基堕周 第1 章绪论 随着计算机技术的发展普及和高新技术领域对于计算机辅助设计与计算机 辅助制造( c a d c a m ) 技术、计算机图形学( c g ) 的日益广泛深入的需要， c a d c a m 高新级术得到了迅猛的发展，他们推进了许多领域的设计革命 c a d c a m 高新级术的发展和应用水平已经成为衡量一个国家科技现代化水平 的重要标志之一，c a d c a m 技术把人和机器的各自优点结合起来，具有应用范 围广、直观、优质、高效的特点经过十几年的发展和更新换代，从最初的c a d 系统只能用于绘图，已经发展到c a d c a m 系统的可视化、集成化、智能化、 网络化的阶段，其中计算机辅助几何设计( c o m p u t e r a i d e d g e o m e t r i cd e s i g n ，缩 写为c a g d ) 是它的理论基础和关键技术，c a g d 的产生和发展极大地影响着 c a d c a m 技术的水平新的几何造型技术一出现，往往很快就会反映到实用的 c a d c a m 系统中去近二十年发展起来的，且现在还在迅速发展的细分造型方 法，正是在c a d c a m 系统中日益受到青睐和应用的新的有效的几何造型技术 本章先略述c a g d 中常用的几何造型方法的发展背景再着重阐述细分方法的 基本构造思想、起源、发展历史、特点、分类，典型的细分曲线与曲面及其连 续性与光滑性分析最后介绍本章的研究内容 1 1 背景 c a g d 是随着汽车、飞机、船舶制造等现代制造工业和计算机技术的发展 而迅速发展起来的一门新兴制造技术早在1 9 7 1 年英国的f o r r e s t 认为c a g d 是 研究几何外形信息的计算机表示、分析与综合，以及形状信息的计算机控制问 题苏步青教授进一步指出，c a g d 是代数几何、微分几何、函数逼近论、计算 数学和数控技术的边缘学科伴随着计算机图形技术的发展，几何造型技术不仅 可应用于原有的外形设计，还可广泛应用于机械制造、医学可视化、虚拟场景 生成等众多领域几何造型技术的发展促进了它的应用领域的扩大，反过来应用 领域的扩大又丰富了几何的表现形式，促进了造型手段及造型技术的发展本文 所说的几何造型主要指曲线曲面造型技术 曲线曲面造型主要研究在计算机系统的环境下，对于曲线曲面的表示、设 计、显示和分析 长期以来，参数曲线曲面一直是描述几何形状的主要工具它起源于飞机、 船舶的外形放样设计，由c o o n s 、b d z i e r 等大师于6 0 年代奠定其理论基础 b o e h m 1 9 8 4 1 9 6 3 年，美国波音飞机公司的f e r g u s o n f e r g u s o n1 9 6 3 提出将曲线曲面表 示为参数的矢函数方法，并引入了参数三次曲线，构造了合成曲线和由四个角 点的位置矢量及两个方向的切矢定义的双三次曲面片1 9 6 4 年，m i t 的 c o o n s c o o n s1 9 6 4 发表了一个更具一般性的曲面描述方法，即一种由四条边界 2 ：! 婴塑坌些垡丝型墨基查旦 曲线确定的参数曲面一c o o n s 曲面片，从而使完整曲面的分片表示成为可能但 这两种曲面都存在形状控制和光滑拼接问题s c h o e n b e r g s c h o e n b e r g1 9 4 6 利h 样条函数成功解决了曲面片之间的拼接问题及插值问题，但插值样条曲线曲面 的自由度较少，难以用于自由型曲线曲面的设计法国r e n a u t 汽车公司的 b d z i e r b e z i e r1 9 7 2 于1 9 7 2 年发表了由控制多边形定义曲线的方法，可以很方便 地控制曲线的形状，并将其用于自由曲线曲面系统u n i s u r f 的设计后来 f o r r e s t f o r r e s t1 9 8 7 对最初的b d z i e r 曲线的形式作了重新处理，得到了当前常用 的基于有序控制顶点和b e r i n s t e i n 基表示的b d z i e r 曲线曲面的形式b d z i e r 曲线 曲面的优点在于通过简单移动控制顶点即可改变曲线曲面的形状，因而具有较 好的交互性在这个基础上，人们又陆续提出了矩形域上的张量积曲面和 b e r n s t e i n - b & i e r 曲面( 即b b 曲面) 但由于曲线曲面上任一点与所有的控制顶点 相关，因此对控制顶点的任何修改都会影响到曲线曲面的整体形状b d z i e r 曲线 曲面的缺陷在于它缺乏局部性，而且在处理曲面片之间的光滑拼接方面也存在 困难 7 0 年代初d eb o o r d e b o o r1 9 7 2 和c o x c o x1 9 7 2 1 分别独立提出了b 样条的 d eb o o r c o x 递推公式，美国通用汽车公司的g o r d o n 和鼬e s e n f e l d g o r d o n1 9 7 4 1 等人又进一步发展了b 样条曲线曲面的理论和算法，并首次将b 样条理论应用 于外形设计由于b 样条曲线保留了b 6 z i e r 曲线的大部分优点，另一方面，由 于是分段多项式，且允许局部控制，因而b 样条曲线曲面开始得以广泛应用但 是上述各种方法不能精确表示除抛物线和抛物面以外的二次曲线曲面，如圆锥 截线和球面椭球面等初等解析曲面，只能给出近似表示为此美国s y r a c u s e 大学 的v e r s p r i l l e v e r s p r i l l e1 9 7 5 于1 9 7 5 年首次提出有理b 样条方法克服上述缺陷 最后在p i g e l p i g e l1 9 8 7 ，1 9 8 9 a ，1 9 8 9 b ，1 9 9 5 ，1 9 9 7 和t i l l e r t i l l e r1 9 8 3 等众多 学者的努力下，终于在8 0 年代后期发展起非均匀有理b 样条m 0 1 1 u n i f o r m r a t i o n a lb - s p l i n e ，缩写n u r b s ) 的一整套方法，把有理和非有理b d z i e r 曲线和b 样条曲线曲面及圆锥曲线和初等解析曲面统一在一种表示之中由于n u r b s 方 法的突出优点和它在外形表示方面的强大功能与潜力，国际标准化组织( i s o ) 于 1 9 9 1 年颁布了关于工业产品数据交换的s t e p 国际标准，将n u r b s 方法作为定 义工业产品几何形状的唯一数学描述方法，从而使n u r b s 方法成为曲面造型技 术发展趋势中最重要的基础，在工业造型和动画制作中得到了广泛的应用，但 n u r b s 方法仍然存在着局限性 单一的n u r b s 曲面与其它参数曲面一样，仅限于表示在拓扑上等价于一张 纸、一张圆柱面或一张圆环面的曲面，若用它来表示五角片等多角片，必须用 “退化片”，或多片“缝合”的技术处理，非常繁琐，因此用n u r b s 方法难以直 接生成多角曲面：定义在任意拓扑上的复杂曲面通常不能由一张n u r b s 、b 样 条或b d z i e r 曲面表示出来，而n u r b s 曲面片之间的光滑连接是一个相当复杂而 困难的问题，因此用n u r b s 方法不能表示任意拓扑结构的曲面，难以进行复杂 物体造型为了表达特征动画中更复杂的形状，如人的头、手或服饰，我们可以 ：! ! 坚塑坌些垡鲨型壁基鏖旦 用最普通的复杂光滑曲面的造型方法，例如对n u r b s 的修剪来对付目前确实 已经存在一些商用系统，诸如a l i a s - w a v e f r o n t 和s o l , i m a g e 和m a y a 等商业软件 通过对n u r b s 作修剪来产生复杂光滑曲面，但代价是昂贵的，而且有数值误差， 对特征动画而言，要在曲面的接缝处保持光滑，即使是近似的光滑也是困难的， 因为模型是活动的因此人们开始开发所谓的基于节点插入的递归细分曲面 细分曲面无须修剪，活动模型的平滑度被自动地保证 1 2细分方法概述 1 2 1 细分曲线曲面的构造思想 细分方法曲线曲面的离散化造型方法，是根据初始数据由计算机直接生 成曲线曲面或其他几何形体的一类方法它的构造思想是：从一个控制多边形或 控制网格( 网格多半可用激光从手工模型上输入) 开始，先按照适当选取的细 分规则( 一般是加权平均) ，在给定初始控制多边形或控制网格中插入新顶点( 这 些新顶点是初始控制多边形或控制网格上某几个顶点的加权平均) ，再连接这些 新顶点得到薪控制多边形或控制网格，所得新控制多边形或控制网格是初始控 制多边形或控制网格的加细不断重复上述过程，随着细分的不断进行，控制多 边形或控制网格就被逐渐细化，其极限状态就是一条曲线或一张曲面，称为递 归细分曲线或递归细分曲面 细分曲线曲面与连续函数所描述的曲线曲面在方法和数据结构上有着本质 的区别曲线曲面设计的经典方法，是先从控制点列得到曲线曲面的数学表达式 ( 如b 6 z i e r 方法) ，然后用递归赋值算法进行赋值( 如d ec a s t e l j a u 算法) ，但这样需 要进行大量的计算曲线曲面的离散细分方法则从初始控制点列出发，用不断细 分的多边形和多边形网格在允许的误差范围内来代替曲线曲面，只须存储离散 点列，正好适合计算机存储和绘制曲线曲面的特点- 从离散直接到离散，而不 是从离散数据到连续或光滑曲线曲面，再到离散数据这就可以大大加快计算和 生成显示的速度，更适合于显示、加工和求交计算等，也更适合于外形设计 传统曲面造型方法遇到复杂物体造型时往往束手无策复杂物体的控制顶 点具有复杂的网格拓扑，这对于利用张量积方法构造的参数曲面而言，拼接或 剪裁( t r i m m i n g ) 的困难是显而易见的细分曲面则可以定义在任意拓扑网格 上，因为不规则拓扑处只须采用特殊的细分规则就可以了曲面的光滑性也由细 分模式的极限性质自动保证，因此细分曲面不存在拼接和剪裁的问题正是这些 优点使得细分曲面造型方法能更有效地处理传统方法所难以解决的问题 另一方面，由于激光测距扫描等三维数据采样技术和硬件设备的进步，可 以轻而易举地在计算机上产生物体的初始网络更重要的是因为图形工业对任 意拓扑结构的光滑曲面造型的需求变得日益迫切，传统的b 样条方法无法满足 p - n a r y 细分曲线造型及其避用 这一要求，而细分曲面能很好地产生拓扑结构复杂的曲面，为几何形状不能或 难于j 分析曲面表示的对象建模提供了有力的工具细分模式作为从给定规则 产生离散曲面的方法，统一了传统的参数曲面与多边形两种实体表面的表示此 外3 d 医学数据、散乱数据的获取也使曲面的3 d 逼近表示备受关注，为细分曲 面造型的应用提供了广阔的前景 1 2 2 细分方法的发展历史 细分方法可以追溯到5 0 年代gr h a m 通过对折线角点进行切害a j ( c o m e rc u t ) 生成光滑曲线的思想7 0 年代中期，c h a i k i n c h a i k i n1 9 7 4 1 生成曲线的细分方法 正是这种角切割思想的具体实现稍后c a t m u l l 和c l a r k c a t m u l l1 9 7 8 提出了著 名的c a t m u l l c l a r k 细分模式，标志着细分方法正式成为曲面建模的手段与此 同时，d o o 和s a b i n d 0 0 1 9 7 8 采用离散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 c h a i k i n1 9 7 4 1 研究曲线的快速绘制，用割角法产生曲线，把离散细分的概念引入到图形学界 1 9 7 8 年，c a t m u l l 和c l a r k c a t m u l l1 9 7 8 开创性地提出了迭代细分四边形网格生 成双三次b 样条曲面片的方法，并推广到任意拓扑网格的情形，d o o 和s a b i n d o o 1 9 7 8 也开创性地提出了迭代细分四边形网格生成双二次b 样条曲面片的方法， 并推广到了任意拓扑网格的情形c a t m u l l c l a r k 细分模式以及d o o s a b i n 关于奇 异点处行为的分析理论标志着细分方法正式成为曲线曲面造型的一种手段由 于c a t m u l l - c l a r k 细分法能用较少的控制顶点迅速生成具有任意形状的光滑曲面 ( 除奇异点( e x t r a o o d i n a r yp o i n t ) 处为c 1 连续外，衄面处处为c 2 连续) ，该方 法很快在造型和动画领域付诸应用，从此离散细分曲面造型得到了广泛的研究 第二阶段，8 0 年代末到9 0 年代初的形成时期在这一阶段，提出了很多著 名的细分方法，包括四点法曲线插值模式及六点法曲线插值模式 d y n1 9 8 7 1 ， b i n a r y 细分曲线模式 d y n1 9 9 1 ，稳定细分模式 c a v a r e t t a1 9 9 1 ，l o o p 模式 l o o p 1 9 8 7 】、蝶形模式 d y n1 9 9 0 等对旧方法也有许多改进以适应不同要求 n a s r i 1 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 i n1 9 9 6 】在细分曲线造型方面， 引入均差细分、生成多项式、生成函数等概念描述细分过程，关于细分模式的 收敛性、连续性分析已有了系统的研究成果在细分曲面造型方面，引入细分矩 阵_ j 于描述细分过程，引入离散f o u r i e r 方法、矩阵特征根法、矩阵逼近理论等 方法对多种细分曲面进行特征分析及收敛性连续性分析；在简单细分规则情形， 已有了较成熟的结论 第三阶段，9 0 年代中期到现在的发展时期在这一阶段，不断有新的细分 方法被提出，对旧方法也有许多新的适应不同要求的改进其中，在细分曲线造 型方面，蔡志杰【蔡志杰1 9 9 4 ，1 9 9 5 ；c a i1 9 9 5 ，1 9 9 8 对非均匀有序控制顶点时 p - n a r y 细分曲线造型及其应用 的四点法及变参数四点法的收敛性和连续性进行了分析；骆岩林 骆岩林1 9 9 8 b 】 研究了生成曲线的有理稳定细分方法；丁友东 丁友东2 0 0 0 b 提出了非线性四点 插值细分法，并研究了这类非线性四点插值细分法的保凸与分形性质；金建荣金 建荣2 0 0 0 提出了非均匀四点插值细分法，生成的曲线达到g 1 连续最近 h a s s a n h a s s a n2 0 0 2 提出了t e m a r y 四点插值细分法，生成的曲线可达到c 2 连续 在细分曲面造型方面，p e t e r s 和r e i t i p e t e r s1 9 9 7 提出了一类最简单的中边 ( m i d e d g e ) 细分模式；q i n q i n1 9 9 8 等人将“物理”性质引入c a t m u l l c l a r k 曲面， 开发出动态细分曲面模型，允许通过施加外力交互地使之变形：s e d e r b e r g 等 s e d e r b e r g1 9 9 8 参照非均匀b 样条的构造方法，在任意拓扑网格上引入非均匀 节点区间的概念，推广得到非均匀细分曲面( 简称n u r s s ) ；d e r o s e d e r o s e1 9 9 8 1 将细分曲面造型方法用于人物动画的设计；v e l h o 和z o r i n v e l h o2 0 0 1 提出了4 - 8 细分法，这些都是逼近的造型z o r i n z o i n1 9 9 6 等改进了基于三角形网格的 “b u t t e r f l y ”插值细分算法以得到更好的光滑性质；k o b b e l t k o b b e l t1 9 9 6 a 1 则提 出了适合四边形网格的插值算法，后来 k o b b e l t2 0 0 0 又提出了一种称为压模式 的细分算法；n a s r i n a s r i1 9 9 7 提出了使细分曲面插值预先指定的二次样条曲线 的算法；l e v i n l e v i n1 9 9 9 a ，1 9 9 9 b 设计了细分规则用于网格曲线插值的联合细 分模式；h a b b i b 【h a b b i b1 9 9 9 提出了基于顶点和边插入的曲线网插值方法： b i e r m a n n b i e r m a r m2 0 0 0 则提出了边界法向插值方法等等 这一时期开始建立较为系统的收敛性理论，提出了多变元模式任意拓扑情 形下收敛性分析的理论框架 w a r r e n1 9 9 5 ：r e i f1 9 9 5 ：z o d n1 9 9 8 这些理论反 过来指导细分模式的构造，尤其是二阶以上连续曲面的构造此外，各种细分模 式的内在联系也逐渐被揭示出来，例如z o r i n 和s c h r 6 d e r 将主( p r i m a l ) 四边形网 格细分模式和对偶( d u a 0 四边形网格细分模式建立了统一的框架 z o r i n2 0 0 0 更为重要的是，在这一时期，细分方法得到了广泛应用，尤其是复杂网格曲面 的多分辨率分析的研究取得了大量成果 1 2 3 细分方法的特点 细分曲线曲面造型方法与传统曲线曲面生成方法相比，有以下几个主要特 点： ( 1 ) 曲线曲面的生成显示速度更快由计算机根据离散数据直接生成离散曲线曲 面，只须存储离散点列，不必先由离散数据集构造连续曲线曲面的表达式，而 在曲线曲面显示时又再批量地计算曲线曲面上的点，没有生成曲线曲面解析表 达式这一- p 问环节，从而可以大幅度地提高曲线曲面的计算机计算、生成和显 示的速度 ( 2 ) 数值稳定。1 4 ：( n u m e r i c a ls m b i l i t y ) ：凸线性组合的细分方法是一个迭代过程， 有很好的数值计算稳定性 ( 3 ) 模型的简单性( m o d e ls i m p l i c i t y ) ：方法的数学模型仅涉及初始数据网格和细 p - n a r y 细分曲线造舅及玉堕用 分规则，而细分规则往往简洁明了，故其用于造形时易于实现，效率也很高 ( 4 ) 适用于任意拓扑网格( a r b i t r a r y t o p o l o g y m e s h e s ) ：细分曲面可以定义在任意 拓扑网格上用参数曲面或隐式曲面参数曲面处理任意拓扑网格时往往存在许 多难以克服的困难：受到矩形拓扑网格限制：在三角形网格或其它网格情形， 曲面构成复杂，且难以处理形状复杂而又光滑的曲面；曲面片之间不易作光滑 拼接等而细分方法有潜力克服上述造型困难 ( 5 ) 可升级性( s e a l a b i l i t y ) ：细分曲面由递归生成，可以不断细分，无限地细分， 在理论上可以细分到任意精度，故具有多分辨率性质，其多分辨率分析有坚实 的数学基础，特别适合于层次细节( l o d ) 技术，从而可充分利用有限的硬件 资源 ( 6 ) 表示的一致性( 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 细分模式的分类 我们可以从多个角度对细分模式进行分类： ( 1 ) 按极限曲线曲面是否过初始控制顶点，细分模式可分为插值细分模式 ( i n t e r p o l a t o r y s u b d i v i s i o n s c h e m e s ) 和逼近细分模式( a p p r o x i m a t i n gs u b d i v i s i o n s c h e m e s ) 典型的插值细分曲线模式有四点法插值模式、六点法插值模式；典型 的逼近细分曲线模式有c h a i k i n 割角模式等典型的插值细分髓面模式有 b u t t e r f l y 模式、k o b b e l t 细分模式、插值朽模式等；典型的逼近细分曲面模式有 c a t m u l l c l a r k 模式、d o o s a b i n 模式、l o o p 模式、中边细分模式、压模式等 ( 2 ) 按控制点列的改进规则的特点，细分模式可分为顶点插入细分模式f 如四点 法插值模式、六点法插值模式、c a t m u l l c l a r k 模式、l o o p 模式、b u t t e r f l y 模式、 k o b b e l t 细分模式、3 模式等) 和割角细分模式( 如c h a i k i n 割角模式、d o o s a b i n 模式、m i d - e d g e 细分模式等) ( 3 ) 按不同层细分规则的特点，细分模式可分为稳定细分模式( s t a t i o n a r ys 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 ) 不同细分层次采用相同细分规则 的细分模式称为稳定细分模式，否则称为非稳定细分模式经典的细分模式大多 为稳定细分模式 ( 4 ) 按同一层细分规则的特点，细分模式可分为均匀细分模式( u n i f o r ms c h e m e s l 和非均匀细分模式( n o n u n i f o r ms c h e m e s ) 每一层细分中网格的不同部分采朋 相同细分规则的细分模式称为均匀细分模式，否则称为非均匀细分模式 p - n a r y 细分曲线造型及其应用 ( 5 ) 按初始控制网格的类型，细分曲面模式可分为基于三角形网格的细分模式 ( 如l o o p 模式、b u t t e r f l y 模式、压模式等) 和基于四边形网格的细分模式( 如 c a t m u l l c l a r k 模式、d o o s a b i n 模式、m i d e d g e 模式、k o b b e l t 模式等) 1 3典型细分曲线 本节具体介绍一些典型的细分曲线，包括c h a i k i n 割角曲线 c h a i k i n1 9 7 4 1 ， 三次b 样条细分曲线，四次b 样条细分曲线，五次b 样条细分曲线，四点法插 值曲线 d ”1 9 8 7 1 ，六点法插值曲线【w 萌s s m a n1 9 9 0 ，变参数四点法插值曲线 蔡 志杰1 9 9 5 等此外，也介绍了这方面的一些最新结果，如非线性四点法插值曲 线【丁友东2 0 0 0 b 】t e m a r y 四点法插值曲线 h a s s a n2 0 0 2 等 1 3 1 c h a i k i n 割角曲线 著名的c h a i k i n 割角曲线是c h a i k i n c h a i k i n1 9 7 4 于1 9 7 4 年作