（计算数学专业论文）细分方法及其应用.pdf

致谢 首先，我要感谢我的导师冯玉瑜教授和陈发来教授，感谢他们 把我引入了对s u b d i v i s i o n 的研究中，并带我走进了计算机辅助几 何设计和计算机图形学科研的最前沿。他们渊博的知识、严谨的治 学、谦逊的为人、诚实的作风一直都深深影响着我。本文从选题到 得出初步结果，以至最后的成文，都是在他们精心指导下完成的， 每一页都凝聚着他们大量的心血。在此，请允许我向他们表示崇高 的敬意和衷心的感谢。 其次，还要感谢常庚哲教授，与他在微软中国研究院共同研究 以来，蒙他悉心教导，使我受益匪浅 此外，我还要感谢我的师兄邓建松博士，他不但为我论文的完 成提出了宝贵意见和建议，还为我提供了编辑本论文的方便的工 具感谢c a g d 小组的陈效群博士、汤兴博士、曾芳龄博士以及 c a g d 小组的其他师弟们，与他们经常的学术讨论总是让我受益 良多另外，他们还给了我多方面的支持和帮助，在此一并致谢 同时，师母黄素琴老师一直对我的学习、工作和生活致以无微 不至的关心，在此表示深深的谢意 我还要感谢我的父母，他们博大而细微的爱是我不断前进的动 力，让我能在求学的道路上始终保持乐观、自信和坚定的步伐 特别地，将此文献给曹蕾小姐，谢谢她一直以来的支持和鼓励。 摘要 【细分的基本思想是通过对初始分片线性函数，o ( z ) 不断地加细 加密得到一系列越来越精细的函数列，1 ( z ) ，厂2 ( z ) ，最终得到该 函数列的极限函数i ( x ) 自上世纪7 0 年代c a t m u l l c l a r k 格式提 出以来，s u b d i v i s i o n 方法得到了迅速发展，并已经成为计算机图 形学领域的一项重要内容本文主要研究细分方法及其应用，所做 的工作包括四点小波的构造、尖锐特征造型和二次曲面造型。 细分方法在图形学很多领域都有重要应用其中一个重要方向 就是多分辨率分析，例如曲面网格的多分辨率分析、医学数据的多 分辨率分析等。由于细分方法自然提供了层次细节表示，而多分辨 率分析的核心就是层次细节表示，利用细分方法和多分辨率分析之 间的这种紧密联系，我们在插值四点细分格式的基础上，构造了一 类小波函数，称之为四点小波它们具有局部支集，并且是对称的 和稳定的，相应的分解和合成算法都具有线性时间复杂度。对不同 的权w ，相应的尺度函数和小波函数具有不同的光滑度，因此我 们可以根据实际应用的需要选择合适的小波函数 f 尖锐特征造型方法有两类：一类是在原来细分格式的基础上 通过修改几何规则来达到目的；另一类是通过修改控制网格的拓扑 结构来实现尖锐特征造型。前一种方法存在如下不足之处：首先， 新规则的构造不直观，即不容易以明确的几何意义来指导新面具 ( m a s k ) 的选取；其次，由于新规则的引进，需要重新对这些特殊 的规则进行连续性分析。后一种方法通过边和顶点分裂操作把控制 网格上需要生成尖锐特征的相关顶点和内部边组成的路径变成两 条由边界顶点和边界边组成的路径，此方法克服了前一种方法的缺 点，但其造型受到了很大的限制。本文利用上述两种生成尖锐特征 方法的优点，研究基于l o o p 格式的尖锐特征的生成。一种基于网 格拓扑结构修改的方法把诸如折痕、角、尖刺、锥和交点的生成统 一了起来并且本文第一次提出了两条或多条折痕交点尖锐特征的 生成仅仅修改交点处的拓扑结构不能确保每条折痕整体的e 1 连 续性，所以我们在修改交点处拓扑结构的同时，还修改了交点附近 的细分格式，从而确保了每条折痕整体的c 1 连续性弦y 7 l v 2 0 0 2 年中国科学技术大学博士学位论文 第v 页 摘要 长久以来，s u b d i v i s i o n 方法对一些看似简单却又在计算机图 形学中有着重要作用的曲线曲面( 如二次曲线曲面) 的造型非常困 难，即使是对简单的圆和球的生成也很困难已有的一些生成球或 二次曲面的s u b d i v i s i o n 方法一般都有太复杂、不能自然弧长参数 化或者计算量太大等缺点席文设计出了生成除抛物线和抛物面外 的二次曲线曲面的s u b d i v i s i o n 格式。该格式只需要给定矩形( 长 方体) 作为椭圆( 椭球) 的控制多边形( 多面体) ，就能方便地生成与 给定矩形( 长方体) 内切的椭圆( 椭球) ，同时双曲线和双曲面也可 以由简单的变换得到 关键词：四点小波，多尺度分析，尖锐特征，二次曲面 k e y w o r d s ：f o u r p o i n tw a v e l e t f e a t u r e q u a d r i c s a b s t r a c t t h eb a s i ci d e ab e h i n dr e c u r s i v es u b d i v i s i o ni st oc r e a t eaf u n c t i o nb y r e p e a t e d l yr e f i n i n g a ni n i t i a lp i e c e w i s e l i n e a rf u n c t i o nf 0 ( z ) t op r o d u c ea s e q u e n c eo fi n c r e a s i n g l yd e t a i l e df u n c t i o n sf 1 ( z ) ，f 2x ) t h a tc o n v e r g et o al i l n i tf u n c t i o n ，( z ) s i n c ec a t m u l l c l a r ks c h e m ew a sp r o p o s e di n 1 9 7 0 s ， s u b d i v s i o nm e t h o dh a sd e v e l o p e dr a p i d l y ，a n dh a sb e e na ni m p o r t a n tp a r t o fc o m p u t e r g r a p h i c s i nt h i st h e s i s ，w ew i l li n v e s t i g a t es u b d i v i s i o nm e t h o d a n di t sa p p l i c a t i o n ，i n c l u d i n gc o n s t r u c t i o no f f o u r p o i n tw a v e l e t s ，g e n e r a t i o n o fs h a r pf e a t u r e sa n d q u a d r i c s s u b d i v i s i o nh a sb e e nw i d e l yu s e di nm a n yf i e l d so fc o m p u t e rg r a p h i c s m u l t i r e s o l u t i o na n a l y s i s ( m r a ) i so n eo ft h em o s ti m p o r t a n tf i e l d s ，s u c ha s m u l t i r e s o l u t i o na n a l y s i si ns u r f a c em e s h e s m u l t i r e s o l u t i o na n a l y s i si nm a d i c a ld a t ae t c t r a d i t i o n a l l y ，w a v e l e tb a s e sa r et r a n s l a t e sa n dd i l a t e so fa m o t h e rw a v e l e t ，t h e ya d m i th i e r a r c h i c a ld e c o m p o s i t i o n ，w h i c hi st h em o s t i m p o r t a n tp r o p e r t i e so fa 1 1 a sw eh a v ek n o w n ，t h ef u n c t i o n st h a tc a ub eh i e r a r c h i c a l l yd e c o m p o s e d c a nb eg e n e r a t e dt h r o u g ha s i m p l ep r o c e s sk n o w na s r e c u r s i v es u b d i v i s i o n ( s u b d i v i s i o nf o rs h o r t ) t h ed e e pa n dn a t u r a lc o n n e c t i o nb e t w e e ns u b d i v i s i o na n dw a v e l e t sl c a d su st oc r e a t eh i e r a r c h i c a lb a s e s f o rm u l t i r e s o l u t i o na n a l y s i sb ys u b d i v i s i o n i nt h i st h e s i s w ew i l lc o n s t r u c ta f a m i l yo fw a v e l e t s ，w h i c hw ec a l lf o u r - p o i n tw a v e l e t s t h ef o u r p o i n tw a v e l e t s a r eo fl o c a ls u p p o r t ，s y m m e t r i ca n ds t a b l e ，a n dt h ea n a l y s i sa n ds y n t h e s i s f i l t e r sa r e s p a r s e ，s ot h ea l g o r i t h m st oc o n s t r u c ta n a l y s i sa n ds y n t h e s i sf i l t e r s a r eo fl i n e a rt i m ec o m p l e x i t ya st h e r ea r eaf a m i l yo f f o u r p o i n tw a v e l e t s w i t hr e s p e c tt ot h ew e i g h tp a r a m e t e rw ，a n dt h e s ew a v e l e t sa r eo fd i f i e r e n t d e g r e eo fs m o o t h n e s sd e p e n d i n go nd i f f e r e n tw e i g h tv a l u ew ，w ec a nc h o o s e s u i t a b l ew a v e l e t sa c c o r d i n gt od i f f e r e n tp r a c t i c a lp r o b l e m s e s p e c i a l l y ，w h e n t h ev a l u eo fp a r a m e t e rwi s r e l a t i v e l yl a r g e ，t h ec o r r e s p o n d i n gs c a l i n gf u n c t i o n sa n dw a v e l e t sa r ef r a c t a l l i k e ，a n dw ef o u n dt h e s ew a v e l e t sa r es u i t a b l e f o rc o p i n gw i t hs i g n a l sw h i c hh a v es i m i l a r s h a p e s 、 t h o u g ht h es m o o t h n e s so fs u r f a c e si s o n eo ft h em a i nr e q u i r m e n t si n f r e ef o r ms u r f a c em o d e l i n g ，n o n s m o o t he f f e c t ss u c ha s s h a r pf e a t u r e sa r e r e q u i r e di ns o m eo c c a s i o n s t h e r ea r et w ok i n d so fm e t h o d st o g e n e r a t e v l 2 0 0 2 年中国科学技术大学博士学位论文 第v i i 页 ：! ! ! ! 竺! ! 一 s h a r pf e a t u r e s o n ei sb yc h a n g i n gs u b d i v s i o nm a s k n e a rs h a r pf e a t u r e s ，t h e o t h e ri sb ym o d i f y i n gm e s ht o p o l o g ya n du n i f y i n gt h eg e n e r a t i o no fs h a r p f e a t u r e si n t ob o u n d a r yp r o c e s st h ef i r s tm e t h o dc a ng e n e r a t ed i f f e r e n tk i n d s o fc o m p l e xs h a r pf e a t u r e s ，b u tt h er u l e sa r en o tu n i f i e d t h el a t t e rn e e d n tt o c r e a t es p e c i a ls u b d i v i s i o nr u l e sf o rd i f f e r e n ts h a r pf e a t u r e s ，s oi ti ss i m p l e ，b u t t h ef e a t u r e si tc a ng e n e r a t ea r el i m i t e d w et a k ea d v a n t a g e so ft h ea b o v et w o m e t h o d sf o rt h eg e n e r a t i o no fs h a r pf e a t u r e sb a s e do i it h el o o p ss c h e m ef o r c o n e s ，c r e a s e s jd a r t sa n dc o r n e r s ，w eo n l ym o d i f yt h em e s ht o p o l o g yf o rt h e g e n e r a t i o no fs h a r pf e a t u r e s f o rc r o s s e s ，w h i c hn oo n eh a se v e rc o n s i d e r e d b e f o r e ) w e w i l lh a v et om o d i f yt h es u b d i v i s i o nm a s ka sw e l la sm e s h t o p o l o g y i no r d e rt oe n s u r et h ec 1c o n t i n u i t yo fc r e a s e sa tc r o s s a l t h o u g hm a n ys u b d i v i s i o ns c h e m e ss u g g e s t e d ，t h e yc a ng e n e r a t eo n l ya f i n i t ek i n d so fc u r v e sa n ds u r f a c e sm o r eo f t e n ，w en e e dt od e s i g ns u b d i v i s i o n s c h e m e sf o rc e r t a i nk n o w ns u r f a c e s u n f o r t u n a t e l ys u b d i v i s i o ns c h e m ec a n d ol i t t l ef o rt h i s ) e v e nf o rs o m es i m p l eb u to fb a s i ci m p o r t a n c ec u r v e sa n d s u r f a c e s ( s u c ha se l l i p s o i d sa n dh y p e r b o l o i d s ) t r a d i t i o n a l l ye l l i p s o i d sa n d h y p e r b o l o i d sa r em o d e l e d a si m p l i c i ts u r f a c e so rt h r o u g ht h eu s eo fr a t i o n a l s u r f a c es c h e m e s t h ee x i s t i n gm e t h o d sf o rg e n e r a t i n gs p h e r e so rq u a d r i c s h a v es h o r t c o m i n gs u c ha st h er a t i o n a lp a r a m e t e r i z a t i o n sf o rt h e s es u r f a c e s a r en o u u n i f o r m ，t h e r e s u l t i n gs c h e m e c a n n o tr e p r e s e n tt h e s es u r f a c e si nt h e i r n a t u r a la c r - l e n g t hp a r a m e t e r i z a t i o na n dt h ei m p l e m e n t a t i o no ft h es c h e m e i sc o m p l e x i nt h i st h e s i s ，w ed e s i g nas u b d i v i s i o ns c h e m et og e n e r a t ec o n i c s a n dq u a d r i c s g i v e nt h ec o n t r o lp o l y g o n ( p o l y h e d r o n ) ，t h ec o r r e s p o n d i n g e l l i p s e ( e l l i p s o i d ) i sg e n e r a t e dc o n v e n i e n t l y t h eh y p e r b o l aa n dh y p e r b o l o i d c a nb eg e n e r a t e db a s e do nt h eg e n e r a t i o no fe l l i p s ea n de l l i p s o i db ys i m p l e t t a n s f o r i l l a t i o n 第一章引言 本章简要介绍细分方法的历史背景及发展历程，同时介绍本文所作的工 作以及本文内容的安排。 1 1 历史背景 1 9 7 8 年，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 格式的收敛性进行分析的文章的发表标志着细分方法在曲面造型中应 用的开始。如今，细分方法已经在计算机辅助几何设计和计算机图形学的诸 多领域中得到了广泛的应用。 细分方法的起源还得从曲面造型说起。在计算机辅助几何设计和计算机 图形学中，曲面造型始终是一个中心内容。曲面造型主要研究在计算机图象 系统的环境下对曲面的表示、设计、显示和分析它起源于汽车、飞机、船 舶、叶轮等的外形放样工艺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 4 z i e r 提出一种由控制多边形设计曲线的新方法这种方 法不仅简单易用，而且漂亮地解决了整体形状控制问题，把曲线曲面的设计 向前推进了一大步，为曲面造型的进一步发展奠定了坚实的基础。但b z i e r 方法仍存在连接问题和局部修改问题到1 9 7 2 年，d e b o o r 总结、给出了 关于b 样条的一套标准算法，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 4 z i e r 方法存在的缺点，较成功地解决了局部控制 问题，又轻而易举地在参数连续性基础上解决了连接问题，从而使自由型曲 线曲面形状的描述问题得到较好解决但随着生产的发展，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 l l e r 等人的功绩，终于使非 8 2 0 0 2 年中国科学技术大学博士学位论文 第9 页 第一章引言 引言 均匀有理b 样条( n u r b s ) 方法成为现代曲面造型中最为广泛流行的技术 旖法中1 9 9 4 ，f a r i n1 9 9 7 ，朱心雄2 0 0 0 ，李桂清2 0 0 1 i 。 n u r b s 方法的突出优点是：可以精确地表示二次规则曲线曲面，从而 能用统一的数学形式表示规则曲面与自由曲面，而其它非有理方法无法做 到这一点；具有可影响曲线曲面形状的权因子，使形状更易于控制和实现； n u r b s 方法是非有理b 样条方法在四维空间的直接推广，多数非有理b 样条曲线曲面的性质及其相应算法也适用于n u r b s 曲线曲面，便于继承和 发展由于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 曲面与其 他参数曲面一样，仅限于表示在拓扑上等价于一张纸、一张圆柱面或一张圆 环面的曲面，不能表示任意拓扑结构的曲面，大大限制了曲面造型的自由度 | f 失名2 0 0 0 1 。例如为了表达特征动画中更复杂的形状，如人的头、手或服饰， 我们面临着一场技术挑战。当然，我们可以用最普通的复杂光滑曲面的造型 方法，例如对n u r b s 的修剪来对付目前确实已经存在一些商用系统，诸 如a l i a s w a v e f r o n t 和s o f t i m a g e 等可以作到这一点，但是它们至少会遇到 以下困难：修剪是昂贵的，而且有数值误差；要在曲面的按缝处保持光滑， 即使是近似的光滑也是困难的，因为模型是活动的这时需要一种新的曲面 造型方法能有效地表示任意拓扑形状的曲面 细分方法( s u b d i v i s i o n ) 正是应这种要求而产生的细分曲面为一个 网格序列的极限，网格序列则是通过采用细分规则( 加权平均) 在给定初始 网格中插入新顶点从而不断加密加细得到。细分方法把经典b 样条曲面片 推广到任意拓扑结构，这意味着对曲面片不用上述修剪由于其递归结构， 细分方法自然具有层次细节，这可以使得有限的硬件资源如低端p c 得到充 分利用同时，细分方法把曲面片与多面体表示统一起来，使得造型系统有 了统一处理曲面和多面体表示的手段细分方法还具有数值稳定性和易于实 现、效率高等特点 自上世纪8 0 年代末细分方法开始引起图形学界注意以来，细分方法得 2 0 0 2 年中国科学技术大学博士学位论文 第1 0 页 第一章引言 引言 到了很大的发展，提出了很多著名的细分格式，如l o o p 格式 l o o p1 9 8 7 、 蝶形格式d y n1 9 9 0 1 等d e r o s e 成功地应用了c a t m u l l c l a r k 细分曲面造 型法，同时发明了构造光滑的变半径的轮廓线及合成物的实际技术，提出了 在服饰模型中碰撞检测新的有效算法，构造了关于细分曲面的光滑因子场方 法。凭借这些数学和软件基础，他形象逼真地表现了g e r i 老头的头壳、手 指和衣服，包括茄克衫、裤子、领带和鞋。开创了把细分方法应用于解决图 形学中实际问题之先河，为细分方法的广泛应用作出了巨大贡献 激光测距扫描等三维数据采样技术和日益完善的硬件设备，为几何形状 不能或难于用n u r b s 曲面表示的对象建模提供了强有力的工具例如医学 的人体器官建模f l o r e n s o n1 9 8 7 1 、考古学中的古代器件和艺术领域的雕塑 怍品三维重构f l e v o y2 0 0 0 1 等等然而这类建模的数据量非常大，通常需要 对这些数据进行处理，多分辨率分析为其提供了重要的工具细分方法得到 的是不同分辨率的网格序列，细分方法与多分辨率分析、小波变换之间的这 种内在联系也为细分方法的发展和应用提供了新的舞台 与此同时，细分方法理论方面的研究也得到了很大的发展，单变元细分 格式任意阶光滑的充要条件c a v a r e t t a1 9 9 1 ，m i c c h e l l i1 9 9 3 1 的提出以及多 变元格式任意拓扑情形下收敛性分析的理论框架w a r r e n1 9 9 5 ，r e i f1 9 9 5 a ， z o r i n1 9 9 8 1 的建立，揭示了各种细分格式的内在联系，如z o r i n 等为主( p r i r e a l ) 四边形网格细分格式和对偶( d u a l ) 四边形网格细分格式建立了统 一的框架z o r i n2 0 0 0 1 细分方法如今已成为了国际图形界在曲面造型理论 研究和实际应用中的热点，得到了广泛的应用。 1 2 内容简介 应曲面造型的需要而产生的细分方法，最初的想法是为了解决任意拓扑 网格下曲面造型时的问题随着细分方法的发展，它已经在c a g d 和计算 机图形学、微分方程求解以及其他诸多领域中得到了广泛的应用特别是细 分方法和多尺度分析、小波函数之间的深刻联系，使得细分方法倍受关注 本文主要研究细分方法及其应用，所做的工作包括四点小波的构造、尖锐特 征造型和二次曲面造型。 细分方法在很多领域都有重要应用其中一个重要方向就是多分辨率分 析，例如曲面网格的多分辨率分析、医学数据的多分辨分析等由于细分方 2 0 0 2 年中国科学技术大学博士学位论文 第1 1 页 兰三兰! ! 童 ! ! 法自然提供了层次细节表示，而多分辨率分析的核心就是层次细节表示，利 用细分方法和多分辨率分析之间的这种紧密联系，我们在插值四点细分格式 的基础上，构造了一类小波函数，称之为四点小波。它们具有局部支集，并 且是对称的和稳定的，相应的分解和合成算法都具有线性时间复杂度。对不 同的权叫，相应的尺度函数和小波函数具有不同的光滑度，因此我们可以 根据实际应用的需要选择合适的小波函数 尖锐特征造型方法有两类：一类是在原来细分格式的基础上通过修改几 何规则来达到目的；另一类是通过修改控制网格的拓扑结构来实现尖锐特征 造型。前一种方法存在如下不足之处：首先，新规则的构造不直观，即不容易 以明确的几何意义来指导新面具( m a s k ) 的选取；其次，由于新规则的引进， 需要重新对这些特殊的规则进行连续性分析后一种方法通过边和顶点分裂 操作把控制网格上需要生成尖锐特征的相关顶点和内部边组成的路径变成 两条由边界顶点和边界边组成的路径，此方法克服了前一种方法的缺点，但 其造型受到了很大的限制本文利用上述两种生成尖锐特征方法的优点，研 究基于l o o p 格式的尖锐特征的生成一种基于网格拓扑结构修改的方法把 诸如折痕、角、尖刺、锥和交点的生成统一了起来并且本文第一次提出了 两条或多条折痕交点尖锐特征的生成，仅仅修改交点处的拓扑结构不能确保 每条折痕整体的e 1 连续性，所以我们在修改交点处拓扑结构的同时，还修 改了交点附近的细分格式，从而确保了每条折痕整体的g 1 连续性 长久以来，s u b d i v i s i o n 方法对一些看似简单却又在计算机图形学中有 着重要作用的曲线曲面( 如二次曲线曲面) 的造型非常困难，即使是对简单 的圆和球的生成也很困难已有的一些生成球或二次曲面的s u b d i v i s i o n 方 法一般都有太复杂、不能自然弧长参数化或者计算量太大等缺点。本文设计 出了生成除抛物线和抛物面外的二次曲线曲面的s u b d i v i s i o n 格式该格式 只需要给定矩形( 长方体) 作为椭圆( 椭球) 的控制多边形( 多面体) ，就能方 便地生成与给定矩形( 长方体) 内切的椭圆( 椭球) ，同时双曲线和双曲面也 可以由简单的变换得到 1 3 内容组织 第一章即本章简要介绍了细分方法的历史背景和发展历程，以及本文将 要做的工作 2 0 0 2 年中国科学技术大学博士学位论文 第一章引言 第1 2 页 引言 第二章介绍细分方法的一些基本概念。详细介绍了各种细分格式( 如 c a t m u l l c l a r k 格式、l o o p 格式、d o o s a b i n 格式等) 以及它们的一些应 用，同时对细分方法的理论分析( 如细分格式收敛性分析) 作了较详细的阐 述。我们将从几个细分曲线的例子开始介绍一些基本概念( 这些概念可以平 行推广到二维情形) ，这将简化描述，同时更易于理解接着，介绍二维细分 格式所特有的基本概念以及相关理论。 第三章到第五章依次介绍本文的工作第三章介绍四点小波的建立 第四章描述三角网格细分曲面尖锐特征生成。第五章讨论生成二次曲面的 s u b d i v i s i o n 方法。 第二章细分方法综述 2 1 细分的思想 细分方法的基本思想是：定义一个网格序列的极限，网格序列是采用细 分规则( 加权平均) 在给定初始网格中插入新顶点并不断加密加细得到的。 图2 1 1 为对顺次连接四顶点得到的曲线细分的过程。左一为初始曲线。 左二是细分一次后得到的曲线，初始曲线的顶点保持不变，每相邻两点间插 入一新的点。重复上述过程，我们得到看起来越来越光滑的曲线，见右二、 右一。 图2 1 1 ：曲线细分过程 图2 12 为曲面细分过程初始瞳面( 左一) 中每一个四边形被分割为 四个，得到新的曲面( 左二) 重复上述过程，我们得到看起来越来越光滑的 曲面，见右二、右一。 图2 12 ：曲面细分过程 上述两例都描述的插值型细分格式，初始点保持不变，同时插入新点。 下面我们将看到样条函数一般不是插值的，也可以通过细分方法生成。此时 在细分的每一步，插入新点的同时，原来的点也被移动到其他地方，这类细 分格式被称为逼近性细分格式 1 3 2 0 0 2 年中国科学技术大学博士学位论文 第1 4 页 ! 三兰竺坌童童竺兰 ! ! ：! 丝坌丝兰叁 由一层顶点计算下一层顶点的方法很多。显然，最终得到的曲线或曲面 的光滑性由所选的计算规则所决定我们一般要求所选的计算规则应具有以 下性质： 高效性：可以高效地计算出新点； 紧支集：初始网格上任一顶点只能影响极限曲线或曲面的有限局部； 局部定义：新点的得到只依赖于拓扑上相邻的有限个点； 仿射不变性：若初始网格被变换，如平移、放缩或旋转等，极限曲线或 曲面也被同样变换； 简单性：规则简单； 连续性：极限曲线或曲面应具有一定光滑性。 如图211 ，由于计算新点的规则只与相邻两点有关，因此该规则非常 高效，且具有紧支集和局部性；同时由于权的和为1 ，所以也具有仿射不变 性；实现也很简单；极限曲线也具有e 1 连续性。 在介绍这些规则如何选取之前，我们先简要对细分方法和其他常用的造 型方法作一个比较 1 高效性：计算代价是造型方法的一个重要标志细分方法易于实现并且 高效，只需少量的相邻的上一层顶点来计算新点，这和样条造型方法中 的节点插入很类似，事实上，很多细分方法只是节点插入的简单推广 而隐式曲面造型计算代价则高得多。 2 任意拓扑结构：希望建立任意拓扑结构的曲面。隐式曲面在这方面有很 大优势，它甚至允许在造型过程中修改拓扑结构经典样条造型方法对 任意拓扑结构控制网格造型则非常困难此处的“任意拓扑结构”有两 方面的含义：第一，网格的亏格和相应曲面的拓扑结构是任意的；第二， 由网格的顶点和边所构成的图形为任意的，特别地，每一顶点的度( 即 与该顶点有边直接相连的顶点数) 可以是任意的 当把矩形样条曲面片应用于任意拓扑结构时，要在奇异点( 见2 4 节) 处得到高阶光滑性是非常困难的，表示也很复杂隐式曲面可以具 有任意亏格，但是，亏格、精确位置和曲面的连接都很难控制。变分曲 面比其他方法都能更好地处理任意拓扑结构情形，但计算代价很大。细 分方法很高效地处理任意拓扑网格，这是它的关键的优点之一细分方 法也可以说是应处理任意拓扑网格而产生的 3 曲面特征：经常需要控制曲面特征( 如折痕、尖刺等) 的形状和尺寸变分 2 0 0 2 年中国科学技术大学博士学位论文第1 5 页 第= 章细分方法综述2 2b 样条细分方法 曲面为建立曲面特征提供了最灵活和精确控制的工具。隐式曲面则很难 控制，因为所有的造型都是非直接的，曲面本身的几何结构很难控制。 样条曲面允许精确控制，但代价太高，尤其是对任意拓扑结构。细分方 法则提供了更为灵活的控制方法不仅可以通过选择控制点，还可以通 过采用不同的细分规则来得到特殊效果，如折痕、尖刺等 4 几何复杂度：对交互式应用，效率至关重要细分方法是基于递归加密 加细的，它自然为层次细节渲染和互联网压缩提供了很好的工具。在交 互式编辑过程中，局部的自适应的细分方法可以提供合适精细程度的曲 面，例如，对同一曲面进行观察时，可以根据分辨率的不同，提供具有 不同精细程度的曲面 由于多数细分方法都是基于样条或是样条的推广，接下来我们将简要回 顾一些与样条和细分相关的基本概念，本节定理的证明略，详见f w a r r e n1 9 9 5 ， s i g g r a p h2 0 0 0 2 2b 样条细分方法 2 2 1 零次b 样条 零次b 样条的特征函数u ( t ) 为 卅 。1 妊 职( ) = u ( t i ) 为u ( t ) 的平移函数易知，仉( t ) 的支集为 i ，i + 1 ，且在 支集上值为1 。零次b 样条函数f ( t ) 可以表示为u ( t ) 平移函数的加权和 邢) = p 。阢( ) 由于其节点是等距分布的，所以f ( t ) 为均匀b 样条。 u ( t ) 的二分加密函数w ( t ) 定义为 u i ( t ) = o r ( 2 t i ) 同时u ( t ) 可以表示为其加密函数的和 u ( t ) = u ( 2 t ) + u ( 2 t 一1 ) 2 0 0 2 年中国科学技术大学博士学位论文 第1 6 页 篁三兰丝窒童童竺兰 ! ! 兰呈堑坌窒坌童兰 相应地有 叫( t ) = 嘴1 ( ) + 叫j 。+ l 对，( t ) 细分就是要将，( ) 表示为矿( t ) 越来越密的二分加密函数叼( ) 的加权和 坤) = 旌叼( t ) 0 记u j ( t ) 为行向量，第i 个元素为w ( t ) ，则上式表示为向量形式得 f ( t ) = u 3 ( ) 矿 ( 2 2 1 ) 同时有 u ( t ) = u j + 1 ( ) s ， 其中s 为一矩阵，其第( 2 i ，i ) 和( 2 i + l ，i ) 元素为1 ，其余元素为o s 的 一有限部分为 s 称为细分矩阵若初始点列p o 为p ，由( 2 2 1 ) 得 矿+ l = s 矿 即将s 作用到矿得到新的点列矿+ 1 2 2 2 高阶b 样条 可以有多种方式定义高阶b 样条。最简单方式是通过卷积两函数g ( z ) 和h ( x ) 的连续卷积如下 9 ( ) 。 ( ) = ，9 ( s ) 一s ) d s 0 o 0 0 0 o o 0 0 o 0 0 0 o o 0 o 0 0 o 0 0 1 1 0 0 0 0 1 1 o o o o l l o 0 o o 1 l 0 o 0 o 0 0 o o 0 0 o 0 0 o o 0 o 0 o 0 0 o 2 0 0 2 年中国科学技术大学博士学位论文 第1 7 页 兰三兰丝坌奎兰竺兰 坠! 呈堑垒竺坌童童 下面介绍卷积的几个重要的性质。 定理2 2 1 ，w a r r e n1 9 9 5 若，( ) 为c 光滑的，则u ( t ) 圆f ( t ) 为c 2 + 1 光 滑。 定理2 2 2 w a r r e n1 9 9 5 设m ( t ) 为g ( t ) 和h ( t ) 的卷积，则有： g ( t i ) h ( t j ) = m ( t i j ) ， g ( 2 t ) h ( 2 t ) = 去州2 t ) n 阶b 样条基函数| ) 、k ( ) 满足 ( ) = 哆u ( ) z = u 定义 聊( ) = n ( 2 j t i ) 则n 阶均匀b 样条函数f ( t ) 可以表示为 因为 f ( t ) =p ? 埘( t ) ( ) 2 璺u ( ) = 鱼( u ( 2 ) + u ( 2 t 一1 ) ) 根据定理22 2 得 万1 ( 2 f ) _ 垒u ( 2 t ) 以及定理22 1 知，a _ ( t ) 可以表示为埘的组合，即有 心( t ) = s k n ( 2 t 一女) s k 的具体计算将在后面给出 相应地可以得到 ? ( t ) = s * l 如( t ) t ( 22 2 ) 2 0 0 2 年中国科学技术大学博士学位论文 第1 8 页 苎三兰丝坌童童竺兰 ! ! ：! 呈堑叁塑窒童童 写为矩阵形式有 n j ( t ) = n j ( t ) s ， 其中细分矩阵s 的元素岛。，：= 吼，其余元素为0 。控制点列( 列向量) 矿和矿“具有如下关系 矿+ 、= s 矿 ( 22 ，3 ) 2 2 3 离散卷积细分 上一小节中，细分过程被描述为将细分矩阵s 不断地作用于给定点列 的过程。对b 样条，我们可以用离散卷积来描述上述细分过程。 序列a 和b 的卷积c 为 c * = n 。幻 i + j = k 离散卷积可以看成是多项式相乘设c 对应的产生多项式为c ( z ) ，即 e ( z ) = c k z 2 下面以小写字母如a 表示序列，相应的大写字母如a ( z ) 表示对应的产生多 项式。 由离散卷积的定义得 c ( z ) = a ( z ) b ( z ) 所以序列的离散卷积可以看成是相应的产生多项式相乘，反之亦然。 由下面定理知，离散卷积可以用来从两基函数的连续卷积中得到细分格 式。 定理2 2 3 w a r r e n1 9 9 5 设 ( ) 为，( t ) 和9 ( t ) 的连续卷积，如果，( ) 和 g ( t ) 满足下面细分格式 ，( f ) = n 。f ( 2 t i ) 9 ( ) = b j g ( 2 t j ) 2 0 0 2 年中国科学技术大学博士学位论文 第1 9 页 篁三兰竺坌童兰竺兰 ! ! ：! 呈堑垒竺窒童童 那么， ( t ) 满足细分格式 h ( t 1 = 其中e ( 。) ：；a ( 。) b ( z ) 因为 u ( t ) = u ( 2 t ) + u ( 2 t 1 ) 所以相应的产生多项式为1 + z 又 | v j ( ) = 哆( u ( 2 ) + u ( 2 t 1 ) ) l = u 由定理2 23 知( 2 2 2 ) 中系数s 对应的产生函数为 s ( z ) = 去( 1 十z ) 州 ( 224 ) s t 可以由二项式展开精确得到 如二次b 样条细分矩阵s 的一有限部分为 0 ； 00 0 0 00 00 00 0 o 0