（计算数学专业论文）指数多项式曲线细分重构与插值细分曲面快速计算.pdf

大连理工大学博士学位论文 摘要 细分方法已经广泛应用于任意拓扑的光滑曲面造型、交互计算机图形学( c g ) 、计 算机动画以及计算机辅助设计( c a d ) 等领域从上个世纪八十年代以来，得到了广泛而 深入的研究至今研究多集中在各种静态细分规则的构造、细分方法的收敛性与连续性 分析以及基于多项式理论的细分格式的实用算法等方面而在非静态细分格式的构造和 分析、特殊曲线( 如圆锥曲线等) 的细分生成、非多项式细分格式的快速计算方面还有很 多工作要做 本文在对细分方法的背景、发展历史与概况、特点、基本概念、格式分类及细分 收敛性分析进行综述的基础上，研究构造动态的重构指数多项式细分格式的理论框架， 包含格式构造、收敛性和光滑性分析等；研究能够精确生成圆锥曲线的h e r m i t e 细分格 式：研究缺乏解析表达式的插值细分曲线曲面的精确求值等问题论文的主要工作如下： 多数细分法文献侧重研究静态细分法的构造、收敛性和光滑性分析及其在曲线曲 面造型中的应用而静态细分格式一般生成的是多项式曲线曲面，象圆锥曲线这样的简 单几何却无法得到，重构指数多项式空间在理论上还有许多工作要做本文提出了一种 构造动态细分格式的框架性方法，利用该框架构造出的细分格式可以重构指数多项式空 间，而且含有一个松弛参数可以调整极限曲线的形状以及光滑性的阶数对于指数多项 式空间维数的奇偶不同分别按两种方式构造细分方法，奇数维空间对应p r i m a l 格式，偶 数维对应d u a l 格式，这两种格式是按照细分自然参数化的不同方式来定义的按照本文 的构造方法构造的细分格式可以包含重构多项式空间的静态插值细分方法，以及一些逼 近细分方法等构造过程主要是解掩模所满足的线性方程组，求解可得细分系数本文 给出了线性方程组的解的存在唯一性证明指数多项式空间是通过常微分方程的解来定 义的，空间中的函数在等间隔离散采样点上的值，可以通过求解常微分方程对应的差分 方程来得到而细分是对指数多项式空间中的函数在等距离散采样点上的值来做递归加 细的，因此细分掩模自然的就与差分方程建立了联系，本文将利用差分方程理论给出细 分掩模更具体的形式在此框架下，多项式作为指数多项式的特殊情况，其细分掩模可以 更容易的给出，本文给出了比较详细的结果对于动态格式我们给出了收敛性及光滑性 的证明，采用的是渐近一致等价的技巧，可以用经典的静态格式分析理论给出光滑性阶 数由于圆锥曲线是指数多项式空间的一个特例，这说明利用本文的方法可以给出重构 圆锥曲线的格式而由于有了一个松弛参数，我们还给出了一种通过调整松弛参数来重 构圆锥曲线的细分格式实例说明本文构造的格式可以包含几种重要的细分方法，并能 产生新的具有良好性质的格式 为了能够精确生成圆锥曲线，本文提出了一种带松弛参数的h e r m i t e 插值细分格式， 构造方法同样是是求解细分掩模满足的线性方程组如果第k 层上的点是所对应函数曲 i 指数多项式曲线细分重构与插值细分曲面快速计算 线上的点，则新产生的点也要是同一个函数在规定的参数上的点，然后求解满足上述条 件的线性方程组，得到细分系数利用分析动态细分格式的渐近一致等价的定理、结论 和线性h e r m i t e 插值细分格式的理论，对构造的细分格式进行了理论分析和证明，找到 了与其渐近一致等价的格式构造的细分格式提供了一个松弛参数，当该松弛参数取值 在一定的范围并且任意增大时生成的极限曲线将越来越逼近于初始控制多边形当恰当 地选择松弛参数不同的初值时，该细分格式能够精确生成三次多项式、三角函数和双曲 函数因此，选择特殊的松弛参数初值我们就能够生成所有的圆锥曲线段最后给出一 些实例来说明利用不同的松弛参数初值和改变切向量对极限曲线的影响 插值细分方法一方面由于能够保持初始网格上的顶点信息而受到广泛关注和应用， 另一方面由于该类方法大多缺乏解析性表示，使得对插值细分曲线曲面的精确求值变得 非常困难本文提出了一种可以精确求值插值细分曲线、细分曲面( 四边形网格情形) 的 算法，并将算法推广到了非多项式情形通过分析了静态插值细分格式与双尺度方程( 加 细方程) 的关系，提供了本文求值算法的理论基础构造了与细分格式相关的矩阵序列， 并对给定有理数进行m 进制分解，通过特征分解循环节对应算子乘积，计算得到控制顶 点权值，从而实现对称型静态匀m - a r y 插值细分曲线曲面的有理点精确求值( 含位置信 息以及切向量) ，算法适用于一维曲线细分以及四边形网格情形本文同时给出了对于奇 异顶点附近的参数化方法和求值算法，实现了对任意拓扑网格的插值细分曲面求值进 一步地，将算法推广到了其他非多项式形式细分中具体细分实例证明算法的可行性与 有效性 本文提出了基于三角网格的b u t t e r f l y 细分插值细分眭面的精确求值算法通过分 析b u t t e r f l y 细分曲面的局部参数化，给出了加细过程中参数域的变换过程基于对给定 参数的二进制分解，提出了三个参数分量分解数列所对应的序列构造方法构造了以给 定面邻接二环的局部加细矩阵，提出了求值正则极限曲面的三种算法本文同时还给出 了处理非奇异网格的矩阵方法，使得求值算法可处理任意拓扑网格并给出了利用该算 法进行三角网格重采样的实例以锈细分格式为例，把该文算法推广到求值其他非多 项式三角网格细分情形 关键词：细分方法；计算机辅助几何设计；h e r m i t e 细分；指数多项式重构；圆锥曲线重构； 非静态细分格式；精确求值；加细方程 c o n s t r u c t i o no fe x p o n e n t i a l sr e p r o d u c i n gs u b d i v i s i o ns c h e m e sa n d r a p i de v a l u a t i o no fi n t e r p o l a t o r ys u b d i v i s i o ns u r f a c e s a b s t r a c t s u b d i v i s i o nm e t h o dh a sb e e nap o w e r f u lt 0 0 1t og e n e r a t es u r f a c e sw i t ha r b i t r a r y t o p o l o g yb 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 ot h eg 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 sa r eat o p i co fp r a c t i c a li m p o r t a n c ei nc o m p u t e rg r a p h i c s ，c o m p u t e ra n i m a t i o n ， c o m p u t e ra i d e dd e s i g ne t c t h el a s tf e wy e a r sh a v es e e i lr a p i dd e v e l o p m e n to ff a i r l y c o m p r e h e n s i v et h e o r i e sa n da l g o r i t h m sf o rb a s i cs u r f a c es u b d i v i s i o n ，r e a c h i n gac e r t a i n l e v e lo fm a t u r i t y h o w e v e r ，m o s to ft h er e s e a r c ho ns u b d i v i s i o nf o c u s e do nc o n s t r u c t i o n ， a n a l y s i so fc o n v e r g e n c ea n ds m o o t h n e s s ，a p p l i c a t i o n sa n do t h e rf i e l d sb a s e do np o l y n o - m i a lr e p r o d u c i n gs c h e m e s a n dm u c hm o r ew o r k ss h o u l db ed o n ei ns o m ef i e l d ss u c h a sc o n s t r u c t i o na n dt h e o r e t i c a la n a l y s i so fn o n - s t a t i o n a r ys c h e m e s ，s p e c i a lc u r v e s ( e g c o n i c s ) r e p r o d u c t i o n ，e x a c t l ye v a l u a t i o no fn o n - p o l y n o m i a ls c h e m e s ( e g i n t e r p o l a t o r y s c h e m e s ) e t c f i r s t l yab r i e fr e v i e wo ft h eb a c k g r o u n d ，m a i na d v a n t a g e s ，d e v e l o p i n gh i s t o r ya n d m a i nr e s e a r c hf i e l d so fs u b d i v i s i o na r eg i v e n t h e ns o m en e c e s s a r yd e f i n i t i o n sa n dl e m - m a so ns u b d i v i s i o nm e t h o d s ，a n dt w oc l a s s i f i 【c a t i o n so fs u b d i v i s i o ns c h e m e sa n db a s i c k n o w l e d g eo fc o n v e r g e n c ea n ds m o o t h n e s sa r ei n t r o d u c e da sw e l l i nt h i sd i s s e r t a t i o n ， w ep r o p o s e dac o m p l e t et h e o r e t i c a lf r a m e w o r ko nt h en o n - s t a t i o n a r ys u b d i v i s i o ns c h e m e s r e p r o d u c i n ge x p o n e n t i a lp o l y n o m i a ls p a c e s ，a n da c l a s so fh e r m i t et y p es c h e m e sr e p r o - d u c i n gc o n i c s ，ac l a s so fe v a l u a t i o na l g o r i t h m sf o ri n t e r p o l a t o r ys u b d i v i s i o ns u r f a c e sa n d o t h e rn o n - p o l y n o m i a ls u b d i v i s i o ns c h e m e s m o r ew o r kw h i c hf o c u s e do ns t a t i o n a r ys c h e m e sh a sb e e nd o n e u n f o r t u n a t e l y , g e n - e r a l l ys p e a k i n g ，o n l yp o l y n o m i a ls u r f a c e sc a nb er e p r o d u c e db ys t a t i o n a r ys c h e m e s ，b u t s o m eo t h e rs i m p l ec u r v e ss u c ha sc o n i c sa r ed i f f i c u l tt oo b t a i nb ys t a t i o n a r ys u b d i v i s i o n s c h e m e s w ep r o p o s ean o v e la p p r o a c ht oc o n s t r u c tn o n - s t a t i o n a r ys u b d i v i s i o ns c h e m e s w i t hat e n s o rc o n t r o lp a r a m e t e rw h i c hc a nr e p r o d u c ef u n c t i o n si naf i n i t e - d i m e n s i o n a l s u b s p a c eo fe x p o n e n t i a lp o l y n o m i a l s t h ec o n s t r u c t i o np r o c e s si sm a i n l yi m p l e m e n t e d b ys o l v i n gl i n e a rs y s t e m sf o rp r i m a la n dd u a ls u b d i v i s i o ns c h e m e sr e s p e c t i v e l y , w h i c ha r e b a s e do nd i f f e r e n tp a r a m e t e r i z a t i o n s t h es c h e m e sc o n s t r u c t e di nt h i sd i s s e r t a t i o nc o n - t a i nm o s to ft h ei 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 sr e p r o d u c i n gp o l y n o m i a l s t h er u l e i i i 指数多项式曲线细分重构与插值细分曲面快速计算 a tr e f i n e m e n tl e v e lk o p e r a t e so nv a l u e st a k e nf r o ma ne x p o n e n t i a lp o l y n o m i a lo ft h e a f o r e s a i ds p a c e ，r e p r o d u c i n gv a l u e so ft h es a i n ee x p o n e n t i a lp o l y n o m i a la tr e f i n e m e n t l e v e lk + 1 c o m p u t et h em a s ka f t e rg i v i n gt h es y s t e ma c c o r d i n gt ot h er e p r o d u c t i o n c o n d i t i o n a l s o t h ee x i s t e n c ea n du n i q u e n e s so ft h es o l u t i o na r ea n a l y z e d t h es p a c e o fe x p o n e n t i a lp o l y n o m i a l si sd e r i v e df r o mc o n s t a n td i f f e r e n t i a le q u a t i o na n dt h ed i s c r e t e v a l u e so ft h es a m ef u n c t i o nc a nb eo b t a i n e df r o mt h ec o r r e s p o n d i n gd i f f e r e n c ee q u a t i o n s i n c et h er e f i n e m e n ti so p e r a t e do nt h ev a l u e so fe q u i d i s t a n tp a r a m e t e r s ，t h e r ei sa s t r o n g c o n n e c t i o nb e t w e e nm a s ka n dd i f f e r e n c ee q u a t i o na n ds o m es p e c i f i cf o r m a t i o n so ft h e m a s ka r em a i n l yb a s e do nt h i sf a c t i nt h i sd i s s e r t a t i o n ，t h em a s k sw ec o n s t r u c tf o r p o l y n o m i a l si se a s yt oc o m p u t ea n ds o m eu n i f o r me x p r e s s i o n sa r eg i v e n a san e c e s s a r y s t e p ，t h ec o n v e r g e n c ea n ds m o o t h n e s sa r ea n a l y z e da n dt h e r ea r es t a t i o n a r ys u b d i v i s i o n s c h e m e sw h i c ha r ea s y m p t o t i c a l l ye q u i v a l e n tt ot h en o n s t a t i o n a r ys c h e m e si nt h i sd i s s e r - t a t i o n h e n c et h es m o o t h n e s so r d e rc a nb eg i v e nb a s e do nc l a s s i c a lt h e o r e m a sas p e c i a l c a s e ，t h ec o n i cc u r v e sc a nb er e p r o d u c e de a s i l yb yo u rc o n s t r u c t i o nm e t h o d s i n c et h e r e a r et e n s o rc o n t r o lp a r a m e t e r si no u rs c h e m e s ，w ec a ns e l e c tt h ep a r a m e t e r st om a k et h e s c h e m e sr e p r o d u c ep o l y n o m i a l s i no r d e rt or e p r o d u c ec o n i c se x a c t l y , w ep r o p o s eah e r m i t es u b d i v i s i o ns c h e m ew i t h at e n s o rp a r a m e t e rt oc o n t r o lt h es h a p e so ft h el i m i tc u r v e s t h es c h e m ec a na l s or e p - r e s e n te l e m e n t si nc u b i cp o l y n o m i a l s ，t r i g o n o m e t r i cf u n c t i o n sa n dh y p e r b o l i cf u n c t i o n s t h r o u g hs o l v i n gt h el i n e a rs y s t e ma s s o c i a t e dw i t ht h ef u n c t i o n s ，t h es c h e m em a s ki so b - t a i n e d t h ec o n v e r g e n c ea n ds m o o t h n e s so ft h es c h e m ea r ea l s og i v e nb yt h ep o w e rt o o l s a s y m p t o t i ce q u i v a l e n c ea n dt r a d i t i o n a lr e s u l t so fl i n e a rh e r m i t e - i n t e r p o l a t o r ys c h e m e s t h es c h e m ep r o v i d e su s e r sw i t hat e n s o rp a r a m e t e rw h i c hc a nc o n t r o lt h es h a p e sv e r y w e l l t h r o u g hp r o p e ra d j u s t m e n tw i t h i ni t sr a n g eo fd e f i n i t i o n ，t h es c h e m ec a nr e p r o d u c e c u b i cp o l y n o m i a l s ，t r i g o n o m e t r i cf u n c t i o n sa n dh y p e r b o l i cf u n c t i o n s m o r e o v e r ，f o rc e r - t a i ng i v e np a r a m e t e r s ，a l lc o n i cs e c t i o n sc a nb er e p r o d u c e de x a c t l yb yt h i ss c h e m e t h e c o n v e r g e n c ea n a l y s i so ft h e s u b d i v i s i o nm e t h o di sg i v e na sw e l l f i n a l l y , w ei l l u s t r a t et h e e f f e c t so fu s i n gt h et e n s i o np a r a m e t e ra n dt a n g e n tv e c t o r st og e n e r a t ed i f f e r e n ts u b d i v i s i o n c u r v e s i nm a n ya p p l i c a t i o n ss u c ha sf i t t i n g ，r e p a r a m e t e r i z a t i o na n dr e s a m p l i n g ，i ti sr e - q u i r e dt oe v a l u a t ep o i n t so nt h es u b d i v i s i o ns u r f a c e sa ta na r b i t r a r yd o m a i nl o c a t i o n t h ei 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 ei sw i d e l yu s e dd u et oi t sb e h a v i o ro fp r e s e r v i n go l d v e r t i c e so nt h ei n i t i a lm e s h h o w e v e r ，u n l i k ea p p r o x i m a t i n gs c h e m e s ，t h eg e o m e t r yo ft h e l i m i ts u r f a c eo b t a i n e dv i ai 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 sd o e sn o th a v ec l o s e d f o r m a n a l y t i ce x p r e s s i o ne v e nf o rar e g u l a rm e s h s oi t i sv e r yd i 伍c u l tt oe v a l u a t el i m i ts u r - i v 大连理工大学博士学位论文 f a c e sg e n e r a t e db yt h ei n t e r p o l a t o r ys c h e m e s t 地d i s s e r t a t i o np r e s e n t san e wm e t h o d f o re x a c te v a l u a t i o no fal i m i ts u r f a c eg e n e r a t e db ys t a t i o n a r yi n t e r p o l a t o r ys u b d i v i s i o n s c h e m e sa n di t sa s s o c i a t e dt a n g e n tv e c t o r sa ta r b i t r a r yr a t i o n a lp o i n t s t h ea l g o r i t h mi s d e s i g n e db a s e do nt h ep a r a m e t r i cm - a r ye x p a n s i o na n dc o n s t r u c t i o no fa s s o c i a t e dm a t r i x s e q u e n c e t h ee v a l u a t i o ns t e n c i lo ft h ec o n t r o lp o i n t so nt h ei n i t i a lm e s hi so b t a i n e d ， t h r o u g hc o m p u t a t i o nb ym u l t i p l y i n gt h ef i n i t em a t r i xs e q u e n c ec o r r e s p o n d i n gt ot h e e x - p a n s i o ns e q u e n c ea n de i g e nd e c o m p o s i t i o no ft h ec o n t r a c t i v em a t r i xr e l a t e dt ot h ep e r i o d o fr a t i o n a ln u m b e r s t h ee v a l u a t i o no ft h es u r f a c e sw i t he x t r a o r d i n a r yv e r t i c e s ( e o p ) i s q u i t es i m p l e t h em e t h o dp r o p o s e di nt h i sd i s s e r t a t i o nw o r k sf o ro t h e rn o n - p o l y n o m i a l s u b d i v i s i o ns c h e m e sa sw e l l a nm e t h o df o re v a l u a t i o no fb u t t e r f l ys u b d i v i s i o ns u r f a c e si sg i v e n t h ea l g o r i t h mi s p r o p o s e db a s e do nt h ep a r a m e t r i cb i n a r yd e c o m p o s i t i o n ，m a t r i xe i g e n - d e c o m p o s i t i o na n d r e l a t e do p e r a t i o n s am e t h o do fl o c a lp a r a m e t e r i z a t i o no fb u t t e r f l yl i m i ts u r f a c e si sg i v e n t h r o u g ha n a l y s i so ft h el o c a lr e f i n e m e n tb e h a v i o r t h ew e i g h t sa s s o c i a t e dw i t hc o n t r o l p o i n t so nt h ei n i t i a lm e s ha r eo b t a i n e db yc o m p u t a t i o no ft h em a t r i xs e q u e n c e sc o r r e - s p o n d i n gt ot h ed e c o m p o s i t i o ns e q u e n c e s w eg i v et h em e t h o da r o u n de o p t oe v a l u a t e t h es u r f a c e sg e n e r a t e db ya r b i t r a r yt o p o l o g ym e s h e s s o m er e m e s h i n ge x a m p l e sv i ao u r e v a l u a t i o na l g o r i t h ma r eg i v e na sw e l l 。髓ea l g o r i t h mi si n d e p e n d e n to ft h em e s hd a t a s t r u c t u r e ，a v o i d i n gt h o s ee x h a u s t i n go p e r a t i o n ss u c ha sc o m p u t a t i o no fn e i g h b o r h o o d s ， a n dc a nb eg e n e r a l i z e dt oo t h e rt r i a n g u l a ri 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 se a s i l y , e g 锈s u b d i v i s i o ns c h e m e k e yw o r d s ：s u b d i v i s i o n ；c a g d ；h e r m i t e - t y p es u b d i v i s i o n ；e x p o n e n t i a lp o l y n o m i a l s r e p r o d u c t i o n ；c o n i c sr e p r o d u c t i o n ；n o n - s t a t i o n a r ys u b d i v i s i o n ；e x a c te v a l u a t i o n ；r e - f i n e m e n te q u a t i o n v 独创性说明 作者郑重声明：本博士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 辫日期犁 大连理工大学博士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部i - j 或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅本人授权大连理工 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也可 采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名 导师签名 湃年上月罟日沙争年上月* 日 1 2 7 大连理工大学博士学位论文 1 绪论 本章先略述c a g d 中曲线曲面造型方法发展与细分方法产生的背景然后较为详 细地阐述了细分方法的发展历史与概况，并扼要说明细分方法的特点最后对本文的主 要工作及后续章节的内容组织进行扼要介绍 1 1 背景 曲线曲面造型是c a d c a m c a e ( c o m p u t e r a i d e dd e s i g n m a n u f a c t u r e e n g i n e e r i n g ，计算机辅助设计制造m 程) 、c g ( c o m p u t e rg r a p h i c s ，计算机图形学) 、c a g d ( c o m p u t e ra i d e dg e o m e t r i cd e s i g 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 年法国雷诺汽车公司的b 6 z i e r 提出一种由控制多边形设 计曲线的新方法，这种方法不仅简单易用，而且很好的解决了形状控制问题，为曲线曲面 造型的进一步发展奠定了坚实的基础随后f o r r e s t 和g o r d o n 等人对b 6 z i e r 方法做了深 入的研究，使b 6 z i e r 方法具有更坚实的理论基础，并最终发展成一套自由型曲线曲面设 计系统u n i s u r f 但是b 6 z i e r 方法存在连接问题和局部修改问题1 9 7 2 年d eb o o r 给出 了关于b 样条的一套标准算法1 9 7 4 年g o r d o n 和p d e s e n f e l d 把b 样条理论应用于形状 描述，最终提出了b 样条方法，这种方法继承了b 6 z i e r 方法的优点，同时又解决了局部 控制问题，而且在参数连续性的意义下解决了光滑拼接问题，从而使得自由型曲线曲面 形状的描述问题得到很好的解决b 样条方法在设计自由曲线曲面时显示了强大的实力， 但是经典的b 样条表示方法有一个缺陷，就是不能精确地表示球面等常用的初等二次曲 面为了满足工业界的要求，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 u e r 等人的研究，终于使n u r b s ( n o n - u n i f o r mr a t i o n a l b s p l i n e ，非均匀有理b 样条) 成为现代曲线曲面造型的广泛使用的技术并成为工业标 准1 卅 如今经过三十多年的发展，曲线曲面造型现在已形成了以有理b 样条曲面( r a t i o n a l b - s p l i n es u r f a c e ) 参数化特征设计和隐式代数曲面( i m p l i c i ta l g e b r a i cs u r f a c e ) 表示这 两类方法为主体，以插值( i n t e r p o l a t i o n ) 、拟合( f i t t i n g ) 、逼近( a p p r o x i m a t i o n ) 这三种 手段为骨架的几何理论体系在这一发展过程中，我国以浙江大学、清华大学、中国科 1 指数多项式曲线细分重构与插值细分曲面快速计算 学院计算所、复旦大学、北京航空航天大学、中国科学技术大学、吉林大学、中山大 学、西北工业大学、山东大学、大连理工大学等单位为代表的学术团队作出了重要贡 献p 随着计算机图形显示对于真实性、实时性和交互性要求的日益增强，随着几何设计 对象向着多样性、特殊性和拓扑结构复杂性靠拢这一趋势的日益明显，随着图形工业和 制造工业迈向一体化、集成化和网络化步伐的日益加快，曲线曲面造型近几年得到了长 足的发展目前曲线曲面的表示方法主要有以下几种： 隐式代数曲面表示方法； 参数化曲面表示方法； 多边形网格表示方法： 细分表示方法： 其他表示方法如变形曲面表示方法，基于形状混合的曲面表示方法，p d e 方法， 等等 上述几种方法我们不做展开，参文 1 4 其中曲面造型的经典参数化方法，总要将 用户给定的离散控制顶点和其他信息输入计算机，通过插值、逼近或者拟合的方法转 化为连续表示，然后在显示和其他处理环节再次转换回离散形式这是一个“离散辛连 续兮离散”的过程而且当形体变得复杂后，以上处理往往随之复杂，造成计算代价的 明显增加多边形网格表示的直接方法虽然避免了当中的连续转换环节，但其存储代价 高、冗余表示多，不利于统一处理细分方法是基于网格加细的离散表示方法，它可以从 任意拓扑网格构造光滑曲面其基本思想实际上就是统一了多边形网格和参数化方法， 实现了只须存储离散点列，从离散直接到离散的过程，大大加快了计算和生成显示的速 度与此同时这种方法克服了参数曲面处理任意拓扑网格存在的困难在不规则拓扑处 只需采用特殊的加细规则，就可以解决拼接的问题 经过三十年的发展，在细分格式的构造、细分曲面性质分析及其在多分辩率表示中 的应用等方面的研究都取得了长足的进步细分方法已经成为图形学的一个标准造型技 术在被学术圈所理解的同时也被工业界所广泛接受例如，象a u t o d e s k 公司的m a y a ， s o f t i m a g e l x s i ，p i x a r 公司的r e n d e r m a a ，n e w t e k 公司的l i g h t w a v e3 d ，以及m p e g4 标准等等都将细分作为一种曲面表示方法p 。 1 2 细分发展历史与概况 细分方法可以追溯到上个世纪5 0 年代，d er h a m 在文 17 】中给出了使用多边形割 角( c o r n e rc u t t i n g ) 生成光滑曲线的思想而真正把这个思想应用到造型领域的是图形 艺术家c h m k i n ( 1 8 1 ，他在1 9 7 4 年u t a h 大学举行的c a g d 国际会议上给出了一种基于割 角思想快速生成曲线的算法从此拉开了细分方法作为一个研究领域的序幕 2 大连理工大学博士学位论文 细分方法的发展历史大致可以分成如下三个阶段p 叫： 第一阶段：1 9 8 0 前后，提出并初步发展时期1 9 7 4 年，c h a i k i n 口划用割角法快速产生 光滑曲线，把离散细分的概念引入到图形学界随后r i e s e n f e l d 和f o r r e s t 从理论上证明 了这种极限曲线的数学本质是均匀二次b 样条曲线，由此揭开了均匀b 样条( u n i f o r m b - s p l i n e ) 与细分这个新兴理论的联系 把一维的加细理论扩展到二维曲面又花费了几年的时间1 9 7 8 年c a t m u l l 和 c l a r k 2 0 开创性地提出了迭代细分四边形网格生成双三次b 样条和双二次b 样条曲面片 的方法该文令人兴奋的创新点在于张量积参数曲面上需要的正则网格( r e g u l a rg r i d ) ， 在细分方法中已不再强求，这是将参数曲面推广到任意拓扑网格情形的一个开始p “几 乎同时地，d o o 和s a b i n 口冽把双二次b 样条细分中的加细过程用矩阵乘积来描述，并且 利用矩阵谱的特征分析，给出了在奇异顶点附近的分析方法这个工作后来被b a l l 和 s t o r r y 做了进一步的扩展弘文矧c a t m u l l - c l a r k 细分格式以及d o o 和s a b r a 关于奇异点 处的分析理论标志着细分方法正式成为曲线曲面造型的一种手段从此离散细分曲面造 型方法得到了广泛的研究 第二阶段，8 0 年代末到9 0 年代初的形成时期在这一阶段，提出了很多著名的算法 比较有代表性的有： l o o p 细分格式