（计算数学专业论文）c1连续的可调细分曲面.pdf

两北1 = 业大学坝+ l 论文 摘要 曲面的细分算法采用逐次细分、从离散到离散，最终得到所需要 的曲面，避免了以往的从离散到连续，再从连续到离散的程序。细分 算法的思想较为简单，实施也较方便，已成为计算机辅助设计与计算 机图形学在近些年来研究的热点之一。已有比较完善的细分算法体 系。典型的细分曲面算法有：c a t m u l l c l a r k 细分、l o o p 细分、蝶型 细分、以和i 细分以及混合网格细分等。这些细分算法的小足之处 是：一旦初始网格确定，并选定某一种细分算法后，则造型曲面也随 之确定，不具有修改功能。针对细分方法的这缺点，本文主要研究 f 连续的可调细分曲面。 细分算法可分解为线性插值、平均、纠正三大步骤。本文通过在 、f 均这个步骤中加入可调参数五和国来增加细分曲面的自由度，从而 达到调节造型曲面形状的目的。文中重点研究了三个问题：( 1 ) 三角 形网格的可调细分算法。即通过在平均算子中引入可调参数五，使得 细分曲面更加灵活、具有可调性，且当z 2 素时便是典型的l o o p 细分。 ( 2 ) 四边形网格的可调细分算法。即在平均算子中引入可调参数， 以调节细分曲面的形状。当t o = 土时，该算法即为著名的c a t m u l l c l a r k 4 细分。( 3 ) 混合网格的可调细分算法。即在平均算子中引入两个可调 参见、t o ，通过调节兄、0 9 的值可得到不同形状的细分曲面。这里的 z 和脚具有明显的几何意义，可通过修改参数达到修改造型曲面的目 的。该算法操作简便，既可得到光滑曲而，也可得一些特殊曲面，i ： 富了细分造型曲面的种类。当参数丑和取特殊值时，耐以得到典犁 的l ，o o p 细分和c a t m u l l c l a r k 细分。 文巾对上述的三种刚调细分算法都给；了c 1 连续的充分条件爿 f 以证明，并对各种算法给出了计算实例。从文中算例也可以看山， 本文提出的可调细分算法更灵活，更具有实用性。 关键词：儿何造型，细分曲面，混合细分，可调细分，c 1 连续 a b s l t - a c t s u b d i v i s i o ns u r f a c e sa r eg o t t e nb yi t e r a t i v cs u b d i v i s i o na l g o r i t h m sf r o ms t e p d i s c r e t i o nt os t e pd i s c r e t i o n ，w h i c ha v o i dc o n t i n u o u s s t e p b e c a u s et h ei d e a o f s u b d i v i s i o na l g o r i t h mi ss i m p l ea n dc o n v e n i e n lt oi m p l e m e n t ，s u b d i v i s i o na l g o r i t h m h a sb e e naf o c u si 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 l h e r eh a sb e e nap e r f e c ts u b d i v i s i o ns y s t e m ，s u c ha sc a t m u l l - c l a r ks u b d i v i s i o n ，l o o p s u b d i v i s i o n ，b u t t e r f l ys u b d i v i s i o n ，- , 5s u b d i v i s i o n ，征s u b d i v i s i o na n dh y b r i d s u b d i v i s i o ne t c o n c et h ei n i t i a lm e s hi sg i v e na n dt h es u b d i v i s i o na l g o r i t h mi sc h o s e n ， t h ef i n a ls u b d i v i s i o nm o d e l i n gt h a ti s n tm o d i f i e di sd e c i d e d c o n s i d e r i n gt h e s h o r t c o m i n g o fs u b d i v i s i o n a l g o r i t h m s ，w es t u d y c 1 c o n t i n u o u sm o d i f i e d s u b d i v i s i o na l g o r i t h mb a s e do nt r i a n g u l a rm e s h e s ，q u a dm e s h e sa n dh y b r i dm e s h e s s u b d i v i s i o na l g o r i t h mi sd i v i d e di n t ot h r e es t e p s ：l i n e a ri n t e r p o l a t i o n ，a v e m g e a n dc o r r e c t i o n i nt h i sp r o c e s s ，p a r a m e t e r saa n d0 9a r ei n t r o d u c e di nt h i ss t e pt o i m p r o v et h ef r e e d o mo fm o d e l i n g ，s ot h es h a p eo fl n o d e l i n gi sm o d i f i e db yc h a n g i n g p a r a m e t e r s aa n do , j t h ei n v o l v e dt h r e ep r o b l e m sa r e ：( 1 ) m o d i f i e ds u b d i v i s i o n a l g o r i t h mo ft r i a n g u l a rm e s h e s ，t h a ti s ，w ec a ng o tm o r es u b d i v i s i o ns u r f a c e sb y ”o 。“。“g m o d i f i e dp 8 。8 m 。8a , a n dw h e na2i ，1 y p 。8 1 。ps u b d i v i s i o n s u r f a c ei sg o t t e n ( 2 ) m o d i f i e ds u b d i v i s i o na l g o r i t h mo fq u a dm e s h e s ，t h a ti s ，t h e s n a e ct 。s u r r a c c st sm 。a i r i e db ya a a t n gp a r a m c t e rm ，a n aw n c n 。= 丢，w ec a ng c t f a m o u sc a t m u l l - c l a r ks u b d i v i s i o ns u r f a c e ( 3 ) m o d i f i e ds u b d i v i s i o na l g o r i t h mo f h y b r i dm e s h e s ，t h a ti s ，t w op a r a m e t e r s a a n d ( 2 p r o d u c e di nt h ea v e r a g ep r o c e s s c a nb cc h o s e nt om o d i f ys u r f a c e s ，s ow ec a ug e tc o l o r f u ls u r f a c en r o d e l s w h e n a n df ua r eg i v e ns p e c i a lv a l u e s w cc a as e p a r a t e l yg e tl o o ps u h d i v i s i o no n l r i a n g u l a rm e s h e sa n dc a l m u l l c l a r ks u b d i v i s i o no uq u a dm e s h e s 1 t e r e ，p m a m c t e r s aa n d ( ，h a v es p e c i f i cg e o m e t r i cm e a n i n g t h ea l g o r i t h mi ss i m p l ea n dc o n v e n i e n l t oi m p l e m e n t b yi tw ec a ng e tb o t hs m o o t hm o d e l sa n ds p e c i a lo n e s ，w h i c hr i c ht i l e t y p eo fs u b d i v i s i o n1 n o d d i n g 1 l lt h i s p a p c g es e p a r a l c l y g i v e s u f f i c i e n lc o n d i t i o n sf o rc c o n t i n u o u s m o d i f i e ds u b d i v i s i o na l g o r i t h ma n dp r o v et h e mb a s e do nd i f f e r e n tm e s h e s f i n a l l y ， s o l l l ec a s e sa r cg i v e nt oi l l u s t r a t et h ee f f i c i c n c yo ft h ea l g o l i t h m i na d d i t i o n ，cu s e s i m p l ed a t as t r n c t n r c ss u c ha sm a t r i xa n dl i s ti n s t e a do fc o m p l i c a t c dd a t as t r u c l u r e s k e yw o r d s ：g e o m e t r i cm o d e l i n g ， s u b d i v i s i o ns i l lf a c e s ，h y b r i ds n b d i v i s i o n m o d i f i c ds i l b d i v i s i o n ，c 1c o n t i n u o u s 第一章绪论 随着计算机技术突飞猛进的发展，计算机辅助设计( c o m p u t e r - a i d e d d e s i g n ) 、计算机辅助工程分析( c o m p u t e r - a i d e de n g i n e e r i n g ) 和计算机辅助制造 ( c o m p u t e r - a i d e dm a n u f a c t u r i n g ) 等相关应用技术也得到了巨大的发展。这三者简 称c a d 、c a e 、c a m 。计算机辅助几何设计( c o m p u t e r a i d e dg e o m e t r i cd e s i g n ， 简称c a g d ) 是这三项技术的理论支撑。c a g d 主要研究在计算机图像系统的环 境下对曲面信息的表示、逼近、分析和综合。c a g d 是一门迅速发展的新兴学科， 它的m 现和发展既是现代工业发展的要求，又对现代工业的发展有极大地促进作 门 。随着计算机图形显示对于真实性、实时性和交瓦性的日益增强，图形二t ：业和 制造1 业迈向一体化、信息化和网络化步伐的日益加快，c a g d 得到了飞速的发 展。它经历了从离散到连续( 如b 样条) ，再从连续到离散的发展过程。但是， 当细分( s u b d i v i s i o n ) 技术提出以后，这种造型方法得到了改进，人们可直接从离 散到离散，减少了过去的建立连续函数的那个瑚：节。这种造型方法已经成为 c a g d 的主要设计方法之一。 本章主要介绍细分方法产生的背景、发展状况、特点、分类以及典型的细分 方法。最后引出本文的主要研究内容。 1 1 细分方法产生的背景 计算机辅助几何设计起源于飞机、船舶的外形放样( l o f t i n g ) 2 1 2 艺，由c o o n s 、 b 6 z i e r 等人师r j 二2 0 世纪6 0 年代奠定理论基础。2 0 世纪6 0 年代是c o o n s 技术和 b 6 z i e r 技术，7 0 年代是b 样条技术，8 0 年代是有理b 样条技术，现在已形成了 以非均匀有理b 样条( n o n u n i f o r mr m i o n a lb - s p l i n e ) 参数化特征设计和隐式代数 曲面表示这两类方法为主体，以插值、拟合、逼近为骨架的几何理论体系。 1 9 6 3 年，美国波音飞机公司的f e r g u s o n 【lj 首先提出将曲线曲面表示为参数矢 函数的方法，并引入参数三次皓线，从此参数矢量表示开始成为一种主要的几何 形状表示工具。1 9 6 4 年，美国麻省理工学院的c o o n s 2 提出一个更具一般性的曲 面描述方法，由四边形的四条边界曲线来定义该曲面片，但是该方法有一个明显 的缺陷，就是存在形状控制和光滑拼接问题。 1 9 7 1 年法国雷诺( r e n a u t ) 汽车公司的b 6 z i e r 提出一种用控制多边形控制顶点 的矢量参数表示方法，从而可以简单通过多边形的形状来调节曲线的形状，且具 有局部保凸的性质。随后，美国通用汽车公司的g o r d o n 和r i e s e n f e l d 3 1 提出了矩 形域上的张量积曲面和三角域上的b e r n s t e i n - b e z i e r 曲面( b b 曲面) ，但该方法仍 西北1 业大学颂1 地文 然存在局部性和光滑拼接的问题。 7 0 年代初d eb o o r l 4 】和c o x l 5 j 分别提出了b 样条的d eb o o r 。c o x 递推公式，荧 国通用汽车公司的g o r d o n 和r e i e s e n f e l d 等人进一步发展了b 样条曲线 1 面的 理论和算法，并首次将b 样条理论应用于外形设计。由丁| b 样条是分段表示， 所以该方法保留了b 6 z i e r 方法的大部分优点，克服了b 6 z i e r 方法的缺点，即具 有局部控制的性质。因此该方法得到了广泛的应用。但是该方法不能精确的表示 除抛物线和抛物面之外的二次曲线曲面，如阒锥截线和球面椭球面等初等解 ! j i 曲 面，只能给出近似表示。为此美因s y r a c u s e 大学的v e r s p r i l l e f 7 1 首次提出有理b 样条方法，来克服上述的缺陷。最后经过p i g e l 8 1 帆u 0 【1 1 1 ，【1 2 j 和t i l l e r 【1 3 1 等的努力， 发展并健全了非均匀有理b 样条( n u r b s ) 方法。该方法可以精确的表示二次规 则曲线曲面，从而可以用统一的数学形式表示规则曲面与自由曲面；另外由于该 方法中引入了权因予，呵以方便的通过调整权因子来控制曲线曲面的形状。由于 n u r b s 方法的这两个突出优点，它在外形设计方面有强大功能和潜力。1 9 9 1 年 圈际标准化组织( 1 s o ) 颁布了关于：1 ：业产品数据交换的s t e p 国际标准，把 n u r b s 方法定义为工业产品几何形状的唯一数学捕述方法。但足n u r b s 方法 仍然存在一定的缺点，表现为：单一的n u r b s 曲面与其它参数曲而一样，仪限 于表示在拓扑l 二等价于张纸、一张圆柱面或圆环面，若用它来表示更复杂的曲 而片，必须用“退化片”，或者多片“缝合”的技术，相当繁琐；另外n u r b s 曲面晌光滑拼接也足个非常复杂和困难的问题。为了表示如人的头、手或服饰， 必须要刈分片的n u r b s 曲而进行裁剪和修复，尽管m 前有一些商用的系统软什， 如a l i a s w a v e f r o n t 、s o r t i m a g e 和m a y a 可以对n u r b s 曲面进行裁剪，但是代 价极其昂贵，而且有一定的数值误差，其次由于模型是活动的，要在曲面的缝接 处保持光滑，即使是近似的光滑也有一定的难度。因此n u r b s 方法不能表示任 意复杂拓扑结构的曲面。而计算机图形学和几何设计迫切需要种新的方法柬解 决这个问题，且随着计算机技术的进步和激光测距扫描等三维数据采样技术和硬 件设备的进步，可以容易地得到物体的控制网格。这两个条件都为细分方法的产 生作了铺垫。 1 2 细分方法概述 1 2 1 细分方法的发展史 细分的思想最早可以追溯到上个世纪5 0 年代d er a h m l l 4 1 提出的割角( c u t t i n g c o n e r ) 思想，即通过切割折线角点来生成光滑曲线。1 9 7 4 年，c h a i k i n ”1 提出了类 似的生成曲线的细分方法，细分思想得到了进一步的重视，并且r i e s e n f e l d 1 6 】和 f o r r e s t 0 7 j 证明了此细分的极限为均匀二次b 样条曲线。1 9 7 8 年，c a t m u l l 和 2 两北t 业大学硼i 论文 c l a r k l ig ，d o o 利s a b i n 1 9 1 分别将双二次和双_ 次b 样条推广到任意拓扑结构的网 格上，从此细分算法作为几何造型的种重要方法) i ：始应用。1 9 8 7 年l o o p 2 0 1 在其硕上论文中提出了一种基于三角网格的自分算法，该算法实质上是网次三方 f 门箱样条( q u a r t i c3 - d i r e c t i o n b o xs p l i n e ) 在任意拓扑i 角网格上的推广。上述细分 方法都是逼近形的，而在实际工程中有时需要儿何造型通过某些指定的点，即插 值某些点。为此，d y n 2 1 1 提出经典的四点插值细分| f n 线算法，并把其推广到三角 叫格的细分曲面上，即蝶形( b u t t e r f l y ) 细分算法b 2 j i “j 。一卜- 述四种方法是坌 | 分造型 方法的基础，后来的许多细分算法都足在此基础上发展和完善起来的。 1 9 9 8 年，在s i g g r a p h 会议上，s e d e r b e r g 等1 2 4 1 引入非均匀节点的概念， 在任意的拓扑刚格结构一卜产生非均匀的细分曲面洲u r s s ) 。该算法为几何造型提 供了更多的自由度，可通过调整引入的参数，米控制曲面的形状，还可以获得尖 点、褶皱、刺等特征。但是该算法也有一个明显的缺点，就是参数太多，且太复 杂，实际操作起来不方便。d e r o s e 2 5 1 等也向人们展示了c a t m u l l c l a r k 细分方法 在人物动作、人脸、服饰等造型方面的应用。陈为 2 6 1 等人则通过对初始刚格进 行权细分，实玑了对曲面形状的控制。李梅清f 2 7 1 和周海【2 8 1 分别硎究了子分曲面 尖锐特征生成和混合细分曲面尖锐和半尖锐特征生成，王为民2 9 】提出了可凋的 c a t m n l l c l a r k 细分曲面。曾庭俊【j w 对c a t m u l l c l a r k 细分曲嘶作了形状调整，能 产生c b 样条。p e t e r ”i l 和i f a b i b l 3 2 贝0 分别提出了在不规则的四边形网格r 产生 二次p q 方向的箱样条。p r a u t z s c h 口3 】改善和提高了三角网格上的l o o p 细分和 b u t t e r f l y 细分算法，可分别达到g 1 和g 2 连续曲面。s t a m t 3 4 ”1 针对四边形网格和 二角形网格给出了曲而t 任意一参数处数值的估算方法。q i n gp a n l 3 6 j 对1 ：改善的 l o o p 细分算法提出了一种快速估算任意一参数处数值的方法。这些成果为更好 的研究f m 面造型的性质提供了条件。 具有约束条什的细分研究也取得了一定的成果。如李桂清【3 7 l 通过三次b 样条 插值初始网格中指定的顶点，把法向插值转化为对模板的旋转变换。丁友东【3 8 】 研究了一类保凸的插值细分方法，张景峤1 3 9 】则提出了用非均匀c a t m u l l c l a r k 细 分方法来解决曲线插值问题。m a r i n o v 4o j 提出了具有几何控制的四点曲线插值方 法，b i e r m a n n l 4 1 1 提出了基于c a t m u l l c l a r k 细分和l o o p 细分的具有法向量控制的 分片光滑的细分算法。y a n 9 1 4 2 研究了具有形状优化的细分曲面插值。 以上细分算法在分裂时采用的都是1 - 4 分裂，即每个多边形( 最常用的是四边 形和三角形) 都分裂为四个小多边形，网格的增长速度特别快，因此造成计算过 程中需要大量的存贮单元，影响计算速度。针对这个问题，2 0 0 0 年k o b b e l t l 4 3 】 提出了用于三角网格的3 细分，其拓扑结构的分裂是1 3 ，减慢了网格的增长速 度，该算法除奇异点外达到c 2 连续。k o b b e l t t 的拈细分是逼近型的，因而l a b s i k l 4 4 提i 叶j 了三角网格上插值3 细分，其拓扑结构的分裂不变，几何规则与b u t t e r f l y 类似。2 0 0 1 年，v e l h o 4 5 】提出比打细分分裂更慢的细分算法4 8 细分，该方法也 只门 于三角网格，每次细分网格数增加一倍。4 _ 8 细分的实质是c 4 连续的四方m 箱样条在任意三角网格拓扑结构，l ：的推广，因此在m 常点是c 4 连续的，在奇异 点是c 1 连续的。对于p q 边形网格，2 0 0 4 年g u i q i n g l i t 4 6 j 提出了矗细分，拓扑网 格的分裂方式为1 2 ，减慢了刚格的增长速度，在舰则拓扑结构上产生的曲面足c 4 连续的，在奇异j i 为c 1 连续。 综观卜述的细分算法，要么只适用于叫边形网格，要么只适用于三角形网格， 但是在实际工程中经常会遇到三角网格与四边形网格的混合情形。当遇到这种情 况时，设计者就会束手无策，因此迫切需要研究这样的混合网格细分算法。 从2 0 0 0 年以来，基于因子分解的思想，出现了系列混合刚格细分的研究。 所谓因子分解就是把细分算法分解为若二f 步骤，这样就可以更清楚的了解细分算 法的本质。该思想最早来自丁二r e i e s e n f e l d ，但是一直没有引起人们的重视。2 0 0 3 年，s t m n 4 ”利用该思想提出了c 1 连续的混合网格细分，主要利用因子分解，解 决了混合踟格顶点缨分问题。该卸! 分算法在三角刚格卜和四边形网格上分别是传 统的l o o p 细分和c a m u l l c l a r k 细分，并且提出了混合网格中新规则点的概念。 陔算法在四边形碹| 格和三角形网格上都是c 2 连续的，在奇异点和混合阚格的边 界点是f 1 连续的。2 0 0 4 年，w a r r e n 4 8 1 对上述混合算法进行了改进，月首次提出 实现该算法不使用复杂的数据结构，如w i n g e d - e d g e ，h a l g e d g ，q u a d t r e e ，f o r e s t 等，且不j q 图的遍历，只使用顶点序列和矩阵就可实现该算法。在同一f t ，p e t e r l 4 9 1 提了4 3 方向的细分算法，该算法可保持曲率有界，在四边形网格上的细分“面 具”( m a s k ) 比c a t m u l l c l a r k 细分的小，能避免产生r i p p l e 现象，且在规则处是c 2 连续的，其它处足c 1 连续的。2 0 0 5 年，s c h a e f e 5 0 l 提出了c 2 连续的混台纲分算法， 在混合刚格边界( 三角形和四边形相连接的地方) 达到了c 2 连续，但是在普通 的奇异点仍然是c 1 连续的，达不到c 2 。该算法主要是通过把混台边界的细分“面 具”拆开，然后使得分别在四边形网格边界和三角形网格边界先达到c 2 连续， 然后再通过组合，产生新得边界细分“面具”。上述的混合网格细分算法都是逼 近型的。2 0 0 1 年，m a i l l o 【5 l j 通过引入新的参数，使得混合网格细分曲面可以在 插值和逼近之间变化，增加了细分曲面的调节范围，但该算法没有证明曲面的连 续性。2 0 0 2 年，张宏鑫【57 j 提出了类似的方法，即半静态回插细分方法。该方法 同样可把逼近和插值统一起来( 即把细分分解为两个步骤，线性插值和平均再加 一个回插的过程) ，且通过选择不同的权系数可以表示二次曲线曲面。 综上可以看出，细分的发展是从最初的曲线到张量积曲面，再到任意拓扑结 构网格的曲面；从单一的四边形网格或三角形网格到混合网格；从样条推广到 4 西北t 业大学顸： 论文 以、j 细分；从最初睢一的细分到 叮以产生局部特征的造型曲而。可见，细分 是向着一个造型能力更强，使用更方便，更加经济有效的方向发展的。 1 2 2 细分算法的连续性 根据细分算法的思想，可以多种方法构造细分曲线和细分曲面，但是必须保 证构造的细分算法有意义，其中有两个指标1 f 常重要，一是算法的收敛性，二是 连续性。众所周知，连续性通常是针对连续函数宁问来蜕的，但是对于细分这种 离散的造型方法也需要有一定的理论基础来保证其所构造的曲面具有一定的连 续性。怎样来证明离散造型的连续性，这无疑是个难点。 在细分曲线收敛性和连续性证明方面，d y n ”驯通过把数字序列的卷积转化为 l a u r e n t 多项式的乘积形式，引入均差细分、生成多项式、生成函数等概念来证 明细分算法的连续性。此种证明方法已有较为完善的理论体系。 关j 二细分曲面的连续性证明，1 9 7 8 年，d o o 和s a b i n 首先观察到细分算法的 旋转不变性，引入离散的傅立叶变换( d f t ) ，通过对奇异点周围在频域的细分矩 阼特征值的分村，束判断相应曲丽奇异点处的连续性。b a l l 和s t o r r y l 5 4 1 同样借助 离敝傅立叶变换得到了c a t m u l l c l a r k 细分曲- 由 在奇异点处保持切向量连续的条 什。但是这两种证明方法由 二没考虑到细分的基函数的作用，使得曲面在奇异点 的l 卜剐性不能保证。针剥1 这点，r i e f i s 5 提出了种统一的c 1 连续性证明的方法。 该方法首次引入特征图( c h a r a c t e r i s t i cm a p ) 概念。p r a u t z s c h 5 6 1 通过参数化细分曲 而，把r i e f 的理论推广得到可以产生c 连续的充分必要条件。该理论可应用于 所彳的静止细分算法。基于上述的理论框架，一些典型的细分算法的连续性证明 得到了较为完善的解决，如p e t e r s 和r e i 妒7 j 证明了d o o s a b i n 细分和 c a t m u l l c l a r k 细分的连续性；u m l a u f 5 8 】贝0 解决了l o o p 细分连续性的严格证明。 并且根据此理论框架，可以构造多种细分算法，如p r a u t z s c h 和u m l a u f l 3 3 1 ，【5 9 j ，【6 0 1 使得c a t m u l l c l a r k 细分和l o o p 细分在奇异点处达到了g 2 连续，b u t t e r f l y 细分达 到了g 1 连续。2 0 0 0 年，z o r i n t a q 提出了用z 多项式来证明任意细分的c t 连续性。 c 1 连续的理论体系已经比较完善，其主要理论基本上都依据r e 一”1 的c 1 连续性 证明。混合网格细分的c 1 连续性证明电是采用r e i f 的连续性定理。p r a u t z s c h 提 出了c 2 和c 的细分算法，该算法虽然可以达到c k 连续性，但是当 2 时，相应 的奇异点处曲率为0 ，出现平坦的区域，这是人们不希望看到的。实际上，构作 任意拓扑网格结构上曲率不为0 而整体又为c 2 连续的细分算法非常困难，到目 前为止还没有看到这样的细分算法。2 0 0 4 年，p e t e r s l 6 2 1 较为系统的对细分曲面的 形状特征提出了一些基本的准则。 两北工业 学坝i 。| 仑文 1 2 3 细分算法的思想及其特点 细分思想：从一个控制多边形或控制嘲格丌始，按照适当选耿的细分规则， 赴给定的初始控制多边形或控制网格中插入新顶点，冉连接这些新顶点得到新拧 制多边形或控制恻格，新的控制多边形或控制网格是初始控制多边形或控制i 蛳隋 的加细。不断重复上述过程，控制多边形或控制嘲格就被逐渐细化，其极限状态 就是曲线或曲面，且称之为递归细分曲线或递归细分曲面。 细分方法的特点： ( 1 ) 与传统的造型方法相比，细分足从离敞到离散，避免了从离散到连续 再到离散的步骤，大幅度地捉高了曲线曲而的计算机生成和显示的速度。 ( 2 ) 数值稳定性( n u m e r i c a ls t a b i l i t y ) 。凸线性组合的细分方法是一个迭代 过程，有很好的数值计算稳定性。 ( 3 ) 模型的简单性( m o d e ls i m p l i c i t y ) 。细分方法的数学模型仅涉及初始刚 格数据和细分规则，而细分规则往往简洁明了，易于实现，效率也高。 ( 4 ) 可升级性( s c a l a b i l i t y ) 。细分算法具有多分辨的性质，特别适合于层 次细节( l o d ) 技术。 ( 5 ) 适用于任意的拓扑网格( a r b i t r a r y t o p o l o g y m e s h e s ) 。细分曲面可以定义 存4 e 意的拓扑网格上，三角形网格或者四边形网格或者两者的混合网格均可。 ( 6 ) 表示的一致。 f 1 2 ( 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 h e r m i t e 细分【6 ”。h e r m i t e 细分源于h e r m i t e 插值函数。在工程应用中， 有时不仅要求构造的曲线曲面通过某些点，而且还要插值这些点的切向量或者更 高阶的导数，通过细分方法得到的插值曲线曲面就叫h e r m i t e 细分。 2 自适应细分【6 4 5 酣。通常的细分是全局的、整体的。然而在实际应用中， 当细分到一定次数之后，曲面的某些部分可能已经足够光滑，达到令人满意的状 态，而有些部分不能达到要求，仍需继续细分。如果再把细分规则运用到整个物 体上，必然造成浪费，因此，只需要进行局部细分即可。这样便产生了自适应细 分。自适应细分使得不同层次的点或者网格同时存在，且应尽量避免出现不同的 细分层相互连接处人为的痕迹。 3 逆向细分6 7 1 ，【6 8 1 ，【6 9 1 ，【7 0 1 。通常的细分都是由较粗层的点得到较细层的点， 而逆向细分刚好相反。逆向细分有两种方法，即逼近的回到粗层( 建立多分辨的 6 西北t 业人学碗i ：论文 f i 构) 和精确的回到粗层。 4 细分曲线曲面的多分辨表示。众所j 嗣知，i q 用多分辨分析编辑曲，因 此也有必要研究多分辨理论在细分算法中的应用。在细分算法中，直接的对象足 粗层和细层的点之间的关系，而纠分矩阵刚好反映了这一点。逆向细分和多分辨 理论通常有密切的关系，建立多分辨的同时，4 种逆向的细分关系也就建立。 1 2 5 典型的细分算法 1 2 5 1 细分算法的分类 细分算法可从不同的角度得到不同的分类。比如，根据初始顶点或网格与极 限曲线曲面的位置关系町以分为逼近细分和插值细分；根据同一层次纠分规则的 特点可以分为均匀细分和非均匀绌分；根据不同层次之间是甭采用同样的细分规 则可以分为静态细分和动态细分；根据拓扑分裂的方式可以分为p r i m e 细分和 d u a l 细分川，p r i m e 细分采用的是面分裂( f a c es p l i t ) ，d u a l 细分采用的足顶点分裂 f v e r t e xs p l i t ) ；根据网格类型的种类可以分为四边形网格细分、j 角网格细分和 混合网格细分等。 1 2 5 2 典型的细分算法 从上世纪7 0 年代到现在，细分算法得到了飞速的发展，本章将介纠一些具 柏1 弋表性的、在细分史一卜具有时代意义的典型细分算法。 一典型的细分曲线 细分算法一个重要的特点足通过点的加密米生成曲线，两个相邻绌分层次之 问点增加的倍数是不同的，根据增加的倍数p ，称之为p - n a r y 细分。奉节根据这 个特点来介绍曲线的细分。 给定初始有序控制顶点集合p o = p 是j j 。 ，p ? r 。，其l 一厶j , j 仞始有序 控制顶正i 的有限下标集。设p 。= p ；j 。 为第k 次细分后的有序控制顶点集， 儿为相应的有限下标集。则两层次之间点的对应关系为 g “= o ! j - p i 彤， 其中口= o r ， 为实系数序列，若只有有限个分量不为零称为掩摸( m a s k ) 。 该细分规则可写为算子的形式p “1 = s 。p 。其中咒为线性细分算子，筒记 为s 。由绌分算法s 的掩模c t 形成的多项式a ( z ) = o r ，z ，称为细分算法s 的生 成多项式。 。 当p = 2 时，细分曲线为b i n a r y 曲线造型。 1 当p = 2 、口= 争l ，3 ，3 ，l 】时，对应的细分规则为 两北1 ：业人学坝i j 论史 【瞄”= 丢# 2 + 去c ：。，。r z ”， i 磋：= 去只。+ 丢p ，o z 2 4 n ， 即是著名的c h a i k i n 割角曲线( 一二次b 样条曲线) 。 当p = z 、d = 一，o ，圭+ 。，1 ，圭+ 珊，o 一】时，对应的细分规则为 f呓“= 只。， 一1 墨f 茎2 + 1 ， k 。一趔+ ( 圭删牡( 圭埘) 瑞一眨，一 f 蚰， 1 即为经典的d y n 四点插值法。当l e o i j ，四点插值极限曲线存在；当 o 导，极限曲线是c 1 的。 当p = 3 时，细分曲线为t e r n a t yi l “线。 当p = 3 、d = 池，口。，0 ，口：，d ，1 ，d - ，口2 ，o ，口。，d ，】时，其中2 一去i 1 ， “，：嚣+ 去，d ：；素一丢，口，= 一去+ 吉，细分曲线为四点t e n m y 细分插 口l 2 丙+ i d 2 。两一i 口32 一瓦+ i 孙啪叫域川州 剐删田 值曲线。刑应的细分规则为 或? = p | p 鼎= 盯。t ，+ 口。群+ 口：峨，十口，碟z 1 只