（计算机应用技术专业论文）插值细分曲面设计与分析.pdf

插值细分曲面设计与分析 论文题目：插值细分曲面设计与分析 专业：计算机应用技术 硕士生：凌若天 指导教师：罗笑南教授，高成英博士 摘要 细分方法已经成为图形学中一项重要的研究内容，特别是近些年，细分方法 更成为了几何造型领域最活跃的研究热点之一。随着人们在细分领域的不断开拓 和研究，在细分的连续性理论、多分辨率表示、非正则规则构造技术等方面。人 们都取得了许多的进展，这些进展直接导致了许多具有不同特性的细分方法的涌 现。但是就目前来说，细分方法要取代传统c a d c a g d 方法的地位仍有许多未 完成的工作。 本文的目的是研究一些行之有效的造型方法，以进一步提高细分曲亟的造型 能力。细分模式大致可以分为插值细分和逼近细分两种。插值细分由于更加容易 控制生成网格的形状而得到广泛应用。本文将专注于研究三角形网格上的插值细 分的模式。一般说来，细分的运算速度与其新顶点生成掩膜的大小有着密切关系。 通过研究如何减少掩膜中参考顶点数，本文提出了一种快速的l 一4 分裂插值细 分方法。此外，观察到现有b u t t e r f l y 方法在细分曲面质量上的不足，本文重新 设计了细分掩膜以达到提高细分曲面效果的目的，随后通过傅立叶分析把正则掩 膜推广到任意拓扑的网格上。论文还引入了三角形网格上的l 一9 分裂拓扑规则， 在每一次细分后，三角形面片数量是原来的9 倍。这种细分模式是一种产连续 的曲线在三角形网格上的推广。随后论文还提出了相应的自适应细分算法，在不 降低模型效果的前提下减少了细分模型中三角形的数量。 关键词：曲面细分、插值曲面，三角形网格、1 - - 4 分裂、1 - - 9 分裂 插值细分曲面设计与分析 t i t l e ：t h ed e s i g na n d a n a l y s i so f i 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 m a j o r ：c o m p u t e r a p p l i c a t i o nt e c h n o l o g y n a m e ：r u o t i a nl i n g s u p e r v i s o r ：p r o f x i a o n a nl u o ，d r c h e n g y i n gg a o a b s t r a c t s u b d i v i s i o ns u r f a c e sa r cv a l u e di ng e o m e t r i cm o d e l i n gf o rt h e i rc o n v e n i e n c ea n d f l e x i b i l i t y t h e yp e r m i tt h er e p r e s e n t a t i o no fo b j e c t so fa r b i t r a r yt o p o l o g i c a lt y p ei na f o r mt h a ti se a s yt od e s i g n , r e n d e ra n dm a n i p u l a t e i nt h er e c e n td e c a d e ，s u b d i v i s i o n h a sb e c o m ea na c t i v er e s e a r c ha r e aa n do n ec a nf i n dal a r g en u m b e ro fo n g o i n g l i t e r a t u r e sa n dr e s e a r c h e so ni t a l t h o u g hm u c hp r o g 陀蟠h a sb e e nm a d eo v e rt h i sa r e a , s u b d i v i s i o ns c h e m e ss t i l lh a v es o m eu n r e s o l v e dp r o b l e m s , m a k i n gi td i f f i c u l tt ob e i n t e g r a t e di n t op r e s e n tc a d c a g ds y s t e m s g e n e r a l l y , s u b d i v i s i o ns c h e m e s c a nb e d i s t i n g u i s h e d i n t ot w o t y p e s ： i n t e r p o l a t o r yo n e sa n da p p r o x i m a t o r yo n e s b e c a u s et h es h a p eo fr e f i n e dm o d e l sc a n m o r ee a s i l yb ec o n t r o l l e db yi n t e r p o l a t o r ys c h e m e s ，t h i st y p eo fs c h e m e sd r a w sm u c h a t t e n t i o nf r o mc a d c a g dr e s e a r c h e r sa sw e l la sa n i m a t i o nd e s i g n e r s t h i st h e s i s a i m so f f t h er e s e a r c ho fd e v e l o p i n gn e wm o d e l i n g m e t h o d s , e s p e c i a l l y t h e 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 so nt h et r i a n g u l a rm e s h , t om a k es u b d i v i s i o na d a p t t ov a r i o u sa p p l i c a t i o n s i ti sk n o w nt h a tt h e r ei sac b s er e l a t i o nb e t w e e nt h ee f f i c i e n c y a n dt h es i z eo ft h em a s ko ft h es u b d i v i s i o na l g o r i t h m t h ep r e s e n tw o r ks e e k st o r e d u c et h es i z eo ft h em a s ka n dt h e ni n t r o d u c e saf a s t1 - 4s p l i t t i n gs u b d i v i s i o n a l g o r i t h mm o r e o v e r , i nv i e w o f t h ed i s a d v a n t a g e so f t h eb u t t e r f l ys c h e m e ，t h ep r e s e n t t h e s i sr e d e s i g nt h eg e o m e t r i cr u l e sa n de x t e n dt h en e wr e g u l a rr u l e st oa r b i t r a r y t o p o l o g y b e s i d e s ，a1 - 9s p l i t t i n go p e r a t o ri si n t r o d u c e dt oc o n s t r u c tan e ws u b d i v i s i o n p a r a d i g m ac 2 - e o n t i n u o a ss u b d i v i s i o nc a r v e s ，t e r n a r ys u b d i v i s i o nc u r v e s ，a r eu s e dt o d e r i v ei t sg e o m e t r i cr u l e s b a s e do nt h e1 - 9s p l i t t i n go p e r a t o r , t h en u m b e ro ff a c e s i n c r e a s e se x p o n e n t i a l l yb yp o w e ro f9i ne a c hs t e po fr e f i n e m e n t i no r d e rt or e d u c e 基于移动终端的网格简化算法 a b s t i a c t t h ei n c r e a s e s p e e do ff a c e s ，a na d a p t i v e s u b d i v i s i o na l g o r i t h mi s d e v e l o p e df o r e f f i c i e n ta p p l i c a t i o n s w i t ht h eh e l po ft h eo p e n g l ，t h ee x p e r i m e n tr e s u l t sa l e p r e s e n t e di n t h et h e s i st oi l l u s t r a t et h ev i s u a lq u a l i t yo ft h e s en e w l yd e s i g n e d a l g o d t h r n s k e y w o r d s ：s u b d i v i s i o ns u r f a c e s ，i n t e r p o l a t o r ys u r f a c e s ，t r i a n g u l a rm e s h e s ， 1 - 4s p l i t t i n g , 1 - 9s p l i t t i n g i l l 插值细分曲面设计与分析 第1 章细分曲面概述 第1 章细分曲面概述 细分作为一种有效的曲线、曲面造型方法出现至今已有数十年。但在之前较 长的一段时间里，细分方法的发展十分缓慢。只有在最近十年，细分理论才真正 进入高速发展阶段。新的理论方法不断被提出，新的细分模式也迅速地加入到该 领域当中。可以说细分的研究已经成为当今图形学的一个热点问题。 1 1 研究背景及对象 细分的思想最早可以追溯到5 0 年代qd er h a m 的通过对折线角点进行切割 来生成光滑曲线，但曲面细分模式发展较慢，直到7 0 年代，c a t m u l l 和c l a r k 才 提出了著名的c a t m u l l c l a r k 细分模式口l ，标志着细分方法正式成为曲面建模手 段。8 0 年代末到9 0 年代初，产生了一些著名的细分方法哺，9 ，2 5 1 ，但此时各种模 式之间仍然缺乏联系，缺乏一般的理论指导。9 0 年代中期至今是细分理论的高 速发展期，这得益于u r e i f 在c o m p u t e r a i d e dg e o m e t r yd e s i g n 上发表的一篇论 文【3 2 1 ，系统地阐述了细分曲面的连续性问题，从而为细分理论的快速发展打下坚 实的基础。随后z o r i n 在1 9 9 6 年提出b u t t e r f l y 细分曲面的改进方法 4 4 1 把经典 的b u t t e r f l y 曲面 9 1 推广到任意拓扑网格上。在这段时期还涌现了大量的细分模式 以适应不同的应用需求：3 细分【，插值3 细分【1 8 1 、4 2 细分 2 0 l 、插值2 细分【悖i 、k o b b e l t 细分【1 6 i 、四边形网格三段细分 2 2 1 等等。更为重要的是，在这一 时期，细分方法得到了广泛应用，尤其是复杂网格曲面的多分辨率分析取得了大 量研究成果。 细分曲面一般可以分为逼近曲面和插值曲面两种。对于逼近模式，其生成的 曲面不经过初始控制网格。对于插值模式则不同，初始网格的每一个控制顶点都 存在于生成曲面当中。因此曲面造型应用中，插值曲面具有容易控制生成曲面外 形的特点。插值细分曲面应用最广的算法包括：运用于三角形网格上的b u t t e r f l y 细分【9 2 3 , 4 4 1 和运用于四边形网格上的k o b b e l t 细分【1 6 2 1 1 。 插值细分曲面设计与分析第1 章细分曲面概述 一般来说。逼近细分曲面可以看成是b o x 样条的推广，对于正则区域的网 格，逼近曲面都能达到和b o x 样条同样的连续阶，因而逼近细分容易得到高阶 连续的曲面。但是对于插值细分，就目前已经应用到实际c a d 应用中的方法而 言，只能达到c 7 连续。其中的困难部分来自于构造和分析插值细分曲面上的理 论仍未完善。因为插值细分曲面往往不能归结到己知的参数曲面上，所以给进一 步研究带来了很大的理论障碍。最近h a s s a n 于2 0 0 2 年提出了曲线的三段插值细 分方法【1 2 i ，第一次生成了具有连续的细分蓝线。受到该细分模式的启发，李 桂清提出了四边形网格三段插值细分【2 ”。其方法突破点在于在正则区域上它能够 达到连续，这是插值细分曲面的第一次能够生成高于c 。连续的曲面。但是目 前对于高阶连续的插值曲面，无论是构造还是连续性分析理论还有待完善，因而 成熟的高阶连续的插值细分曲面仍非常少见。 尽管细分还存在着许多未解决的问题，但是就实际应用来说，细分经过几十 年的发展，细分方法已经成为图形学的一个标准造型技术。不但被学术界所理解 同时也被工业界所接受。例如像3 d sm a x 、w a v e f r o n t 、m a y a 、s o f t i m a g e 等一 些著名的3 d 造型系统都加入了支持细分造型的功能。因而对于细分的研究的不 仅仅局限于理论意义上，对我们工业生产、计算机图形学的发展都有着非常重要 的影响。 由于细分曲面包含了非常宽广的研究内容，细分曲面不仅区分为逼近和插值 两种，细分曲面还可以区分为静态1 和动态细分【3 6 1 ，最近还出现了半静态细【5 i j ， 三角形网格细分【2 3 i 、四边形网格细分【t 6 1 ，混合网格细分口7 1 等。同时细分领域在 网格的多分辨率表示【4 5 1 、动态细分策科1 1 、局部细化方法【1 4 i 等都有着大量的研究 题材。 本文的研究内容将专注于三角形网格的静态插值细分理论，主要研究集中在 三个问题上：研究如何在三角形网格上生成一种快速细分方法；如何改进现有的 b u t t e r f l y 细分效果；如何把c 2 连续细分曲线推广到任意拓扑的三角形网格上。 在设计新的细分曲面的同时，也从数学上分析了这些细分曲面的特性。 插值细分曲面设计与分析 第l 章细分曲面概述 1 2 细分曲面相关基本概念 由于细分曲面是作用在多边形网格上的一组规则，但并非任意网格都能适用 于细分进行细化，因而需要给能够细分的网格做一个限定。由于我们只专注于三 维空间的模型处理理论，因此在下文讨论的概念如果没有特别说明，都是属于 空间中的概念。 多边形网格( p o l y g o n a lm e s h 以下简称网格) 简单地说是一个由顶点、边、 面片组成的集合。其中边由顶点间的拓扑关系所决定，相连接的两个顶点决定一 条边。面片由依次连接且组成一个封闭环的边所构成，并且面片中的任意一个顶 点应满足只与面片中的两条边相连接，这样保证了面片中不再包含子面片。能够 细分的多边形网格应满足如下约束：( 1 ) 每个面片都一定属于此网格，每条边都 一定属于某个面片，每个顶点都一定属于某条边。也就说没有孤立的面片、边或 顶点。( 2 ) 每条边最多属于两个面片，两个面片最多共有一条边。若一条边只属 于一个面片，则称这条边为边界边( b o u n d a r ye d g e ) ；若一个顶点属于边界边， 则称此顶点为边界顶点( b o u n d a r yv e r t e x ) ；至少包含一个边界顶点的面称为边 界面片( b o u n d a r yf a c e ) 。非边界的顶点、边和面分别称为内部顶点( i n t e r n a l v e r t e x ) 、内部边( i n t e r n a le d g e ) 和内部面片( i n t e r n a lf a c e ) 。 若一个网格中的所有面片都是三角形面片，那么称此网格为三角形网格 ( t r i a n g u l a rm e s h ) 。网格中与某一顶点相连接的边的数目称为该顶点的度数 ( v a l e n c e ) 。在三角形网格中，若一个内部顶点的度数为6 ，那么称此内部顶点 为正则点( r e g u l a rv e r t e x ) ，否则称为奇异点( e x t r a o r d i n a r yv e r t e x ) 。网格中所 有顶点都为正则点的称为正则网格( r e g u l a r m e s h ) ，包含至少一个奇异点的网格 称为非正则网格( i r r e g u l a rm e s h ) 。 有了以上对于网格及其相关概念的基本定义后，下面讨论细分曲面的定义。 细分曲面( s u b d i v i s i o ns u r f a c e ) 是通过一组拓扑规则和几何规则来对控制网格进 行细化，得到新的密集网格，不断以新生成的下一层密集网格作为新的控制网格 再次进行细化，无限重复此步骤得到一个收敛于固定连续曲面的过程。我们称这 个极限曲面为细分极限曲面( s u b d i v i s i o nl i m i ts u r f a c e ) 。细分的过程一般可以表 插值细分曲面设计与分析第1 章细分曲面概述 示为如下： m 、m t 专一mn 畸mn 呻m 。 其中m 0 为初始网格，膨为m 0 细分一次后得到的下一层网格， 厶为 厶一，层网 格再进行一次细分得到的网格， 厶为细分极限细分曲面。 拓扑规则( t o p o l o g i c a lr u l e ) 主要控制新顶点的生成个数以及新顶点和旧顶 点间的连接关系；几何规则( g e o m e t r i cr o l e ) 主要负责计算新生成的顶点和旧顶 点在下一层网格中的具体位置。其中几何规则又因处理对象的不同分为正则规则 ( r e g u l a rr u l e ) 和非正则规则( i r r e g u l a rr u l e ) 两种。正则规则只处理正则网格 中新顶点在下一层网格中的位置问题，非正则网格则由非正则规则处理。对于曲 面插值细分，由于新顶点生成位置的不同，可以区分为面点和边点两种。面点 ( f a c e v e r t e x ) 的生成依赖于某面片在网格中的拓扑及位置关系，而边点( e d g e v e r t e x ) 则依赖于某边在网格间的拓扑及位置关系。可以粗略地认为面点是生成 在面片上的，而边点是产生在边上的。为了计算新顶点的位置，几何规则需要收 集网格中的一定数量的顶点，这些收集到的顶点及其连接关系称为模板或面具 ( s t e n c i l ) 。赋予模板中的顶点一定权值，新顶点的位置即为模板中顶点的加权 平均。我们称顶点具有权值的模板为掩膜( m a s k ) 。掩膜的权值也称系数，下文 将不区分掩膜中的权值和系数两个概念。 1 3 细分曲面连续性分析理论 d y n 在文献【1 0 l 中推导出了细分模式矿连续的充分条件。d y n 把复杂的细分 曲面连续性问题归结到探讨差分细分模式( d i f f e r e n c es u b d i v i s i o ns c h e m e ) 的收 敛性上。通过研究细分模式及差分细分模式对应的l a u r e n t 多项式，她推导出了 一组十分简洁的连续性证明充分条件。由于证明步骤的简洁，此证明方法被多次 运用到不同的细分模式连续性证明上【1 2 ，2 2 ，3 9 1 。在d y n 的方法基础上，k o b b e l t 在 文献【”1 又推导出了一个更为普遍的证明手段，使复杂的细分模式也能通过研究差 分细分模式的收敛性问题来证明原细分模式的连续度。同样k o b b e l t 给出的也是 一个充分条件。但是他们的方法都存在着一个非常重要的不足，就是只能证明正 插值细分曲面设计与分析 第1 章细分曲面概述 则网格的连续性问题，对于非正则网格的连续性证明，则无能为力。 突破性的工作来源于r d f 于1 9 9 5 年在c a g d 上的论文 3 2 1 。这篇论文给出 了细分曲面连续的充分必要条件：当且仅当细分矩阵对应的特征映射为单射 ( i n j e c t i v i t y ) 和正则( r e g u l a r i t y ) 时，细分矩阵满足c ，连续。同时r c i f 也指 出了一个验证细分曲面连续的简单的必要条件：若细分模式为连续，则该 细分矩阵的模最大的4 个特征值满足如下结构： 1 = 1 1 忙0 如i - i 也6 i l k , 0 ( 1 2 ) 在连续的基础上，若要使细分曲面拥有曲率有界的性质，那么其6 个模 最大的特征值应进一步满足如下结构，l o o p 把此结构称为b o u n d e dc u r v a t u r e s p c t r u m 撕1 ： l ，a ，五，矛，矛( 1 3 ) 无论是r e i f 的理论还是l o o p 的进一步探讨，此套理论体系都只能数值地证 明细分曲面的连续性问题。若已知一个曲面中心是一个度数为1 1 的顶点，那么 r e i f 他们的理论能够验证此细分极限曲面c o 连续性以及曲率有界问题。但无法 一般地证明所有度数的情况都能满足c o 连续和曲率有界条件，只能分别地验证 单个度数的连续性。不过般来说，验证度数1 0 0 以下的连续性已经能够满足工 业及计算机动画需求。 z o r i n 在1 9 9 8 年提出了能够分析任意网格的矿连续性理论嗍。z o r i n 的突出 贡献在于成功地解决了分析奇异点的高次连续性问题。z o 抽的分析理论主要基 于细分矩阵、特征基函数( e i g e nb a s i sf u n c t i o n ) 和参数映射( p a r a m e t r i cm a p ) 。 但是该方法的推导和应用都十分复杂繁琐，鲜见于用其作为细分模式的分析手段 的文献。 东京大学的k a w a h a r a d a 最近提出了一种新的连续性分析理论【1 鲥。细分曲面 特别是插值细分曲面，对曲面进行参数化分析是一件非常困难的工作。为了避免 直接分析细分曲面本身，k a w a h a r a d a 分析细分模式的面片法向量细分模式 插值细分曲面设计与分析 第l 章细分曲面概述 ( n o r m a ls u b d i v i s i o ns c h e m e ) 来决定细分曲面的连续性。基于法向量细分模式， 他推导出了曲面连续的充分必要条件。该方法在证明步骤上比z o f i n 的方法简 洁许多，应该会在将来的细分证明工作中扮演重要的角色。他推导的方法虽然能 够适用于任意拓扑的网格，但是也如r e i f 的方法一般，只能从数值上证明单个 度数的奇异点网格的连续性问题，无法证明整个方法的任意度数都满足某阶的连 续性，是为该方法的一个不足。 1 4 细分曲面模式构造方法 细分曲面模式的构造主要有两个部分组成：( 1 ) 正则规则的构造，使细分模 式能够适用正则网格，对正则网格进行细化：( 2 ) 非正则规则的构造，细分模式 比传统c a d 方法的主要优势就在于对于任意拓扑网格的处理能力，因而非正则 模式的构造对于整个细分有着非常重要的意义。 1 4 1 细分曲线到曲面的推广 表i 1主要细分模式及其来源 貉用对象：。：渤凳模式，善旷。风格类型： ；褥性鼻；，黪，i 黧来源。：塌 b 样条曲线逼近b 样条 曲线四点法曲线插值 l a g r a n g e 插值 割角法曲线 逼近 b 样条 l o o p 三角形逼近b o x 样条 b u t t e r f l y三角形插值 l a g r a n g e 插值 曲面c c四边形逼近 b 样条 3 三角形逼近 l a g r a n g e 插值 2四边形逼近 l a g r a n g e 插值 对于插值细分曲面，正则规则构造的灵感通常来自于细分曲线的进步。d y n 于1 9 8 7 年提出了四点法曲线细分模式【8 1 ，受到该方法的启发，d y n 于1 9 9 0 年又 提出了b u t t e r f l y 曲面细分模式【9 】。当一个正则三角形网格沿着三角形任意一条边 的方向压缩为一条曲线的时候，b u t t e r f l y 方法和四点法是等价的，因而可以把 b u t t e r f l y 方法看成是四点法在三角形网格上的推广。同样来源于四点法，k o b b e l t 也提出了基于四边形网格的细分模式【1 6 1 。插值、，3 细分【1 8 】、2 细分【1 9 1 同理也可 一6 一 插值细分曲面设计与分析第1 章细分曲面概述 以看成是四点法在相应类型网格的拓展。 下面以b u t t e r f l y 细分为例，介绍曲线到曲面的推广法则。这里提前涉及了细 分模式的细节，关于四点法的具体细分模式可以参考2 2 节，b u t t e r f l y 细分模式 可以参考3 2 节。 图1 1 b u t t e r f l y 细分与四点法细分之间的推广关系 从2 2 节中我们已知四点法的掩膜中四个顶点的系数分别为a o 、a na 2 、毋， 那么图l l 中描述的b u t t e r f l y 掩膜若要成为四点法在曲面上的推广，则b u t t e d f y 掩膜中的系数应满足如下约束： 2 ， o l = p + a + yf o = 2 y + p 口2 = f l + a + r i i = 撕 码2 ， ( 1 4 ) 这样当正则网格沿着图l l ( a ) 中虚线方向压缩时，新顶点生成的位置和 四点法是一致的；当正则网格沿着图l l ( b ) 中虚线的方向压缩时，新顶点的 生成不影响曲线( 一个压缩成曲线的曲面) 原有的形状。 1 4 2 傅立叶分析在非正则规则构造中的应用 对于插值细分而言，由于非正则规则构造的困难，直到1 9 9 6 年才真正出现 了第一个能处理任意拓扑三角形网格的插值细分模式 4 4 1 ，此方法是b u t t e r f l y 方 法的一次重要改进。若一个细分模式要对c a d 产生真正的作用，无论对于正则 还是非正则网格而言，其生成的曲面至少应该是一连续，但是对于如何使奇异 ，一 插值细分曲面设计与分析第1 章细分曲面概述 点附近曲面达到c 连续一直是一个难题。我们知道检验一个曲面是否为c 7 连续 的一个非常重要的必要条件是其细分矩阵的特征值的结构1 3 2 。因而研究何保持细 分矩阵的特征值结构，使其满足公式( 1 1 ) 中的结构特征是设计非正则规则的 一个可行研究方向。 一般而言，我们的得到的细分矩阵都能转化为循环矩阵的形式。而傅立叶分 析在循环矩阵的一个重要的应用就是可以在保证循环矩阵特征值结构不变的情 况下，拓展矩阵的循环块数目。若一个正则的细分矩阵由6 个循环块所组成，那 么运用傅立叶分析到这个细分矩阵上，我们可以构造出一个新的循环矩阵，这个 新矩阵可以由任意n 个循环块所组成，这个新的矩阵和原矩阵有着同样的特征值 结构。因而新构造出的细分矩阵也能保证满足c 2 连续的必要条件。只要再验证 细分矩阵的特征映射是否满足单射和正则，则可知新构造的细分矩阵是否具有 连续的属性。此方法已经被运用到了许多细分模式的构造上【1 9 ，2 1 , 2 3 ，州。 1 5 论文的主要内容 我们注意到b u t t e r f l y 细分模式是一种非常流行的细分模式，对该细分的任意 一点改进都能快速地运用到实际应用程序和生产当中。因而在第二章中，我们设 计了一种快速的l 一4 分裂插值细分模式，此细分模式能够与原有的b u t t e r f l y 模 式兼容。虽然曲面的质量稍微劣于原b u t t e r f l y 曲面，但是快速的曲面生成是其优 点，该方法能够运用到对曲面质量要求不高，但对运算速度敏感的应用场景上去。 在第三章中，注意到了原有b u t t e r f l y 细分曲面在某些网格情况下，生成的细 分曲面质量存在一定问题，因而我们重新设计了b u t t e r f l y 细分掩膜中各顶点的权 重，包括正则几何规则和非正则几何规则都进行了优化。实验证明细分曲面的质 量要优于原b u t t e r f l y 细分曲面。 h a s s a n 近年提出了一种新的，连续的细分曲线【1 2 1 ，d o d g s o n 把该细分曲线 推广到了正则三角形网格上们。但是d o d g s o n 的方法不足以应用到实际当中，因 为该方法无法适用于任意拓扑的网格。我们在第四章中，把d o d g s o n 的方法推导 到任意拓扑的网格上，同时证明了该细分模式的连续性。 插值细分曲面设计与分析第1 章细分曲面概述 最后是论文的总结及将来工作的展望。细分曲面相对于传统c a d 方法是一 个新生事物，在工业设计中的运用还不十分普遍。其中主要问题是多方面的，一 方面是因为细分出现的时间较晚，许多系统已经用传统的方法成熟地完成了目前 的任务，没有必要用新方法重新设计整个系统；另一方面因为细分方法的确存在 着一些不如人意的问题，限制了应用的推广。我们将在这一章中探讨插值细分曲 面仍未解决的问题以及如何把本文工作进一步深入研究下去。相信细分曲面以其 高效率、适用任意拓扑网格、可局部控制等优点继续会高速发展，成为无论是工 业c a d ，还是计算机动画方面都不可以忽略的重要技术领域。 - - 9 - - 插值细分曲面设计与分析第2 章l - 4 分裂快速插值细分 第2 章1 - 4 分裂快速插值细分 本章将研究一种与现有b u t t e r f l y 细分兼容的算法，在不牺牲过多曲面质量的 前提下，达到快速细分的目的。由于该方法与b u t t e r f l y 算法兼容，拓扑规则将仍 采用l 一4 分裂。本方法专注于几何规则的优化，从而加快算法运算速度。 2 1 引言 本章提出一种基于l 一4 分裂的插值型三角形网格细分方法。拓扑分裂规则 与l o o p 方法、b u t t e r f l y 方法类似，区别在于几何更新规则上。l o o p 方法是一种 逼近型的细分方法，每次细分过程，不但要把新的顶点增加到原来的网格中，还 要对网格原顶点位置进行调整。而本文提出的方法是一种插值型的方法，一个新 的顶点加入了网格后，在后来的细分步骤中都不会再被移动。与同属插值型细分 的b u t t e r f l y 方法相比，本文方法的优点在于每次细分的计算量更少，这得益于本 文提出的方法在生成每个边点时的参考点数量较b u t t e r f l y 方法少，因而本方法较 传统的b u t t e r f l y 细分方法在执行速度上拥有优势。 由于本方法与b u t t e r f l y 方法相似，因而本方法与现有的b u t t e r f l y 方法拥有 很高的兼容性。现有的运用b u t t e r f l y 方法的程序模块都能轻易替换成使用本细 分方法的模块，替换过程不需要对程序进行大规模改动。 2 2 四点法插值细分曲线 四点法【8 1 是首先由d y n 推导出来的一种曲线插值细分方法。该细分方法实际 上是l a g r a n g e 三次插值曲线的细分表示形式。我们用公式( 2 1 ) 表示l a g r a n g e 插值曲线的基函数： 厶一( f ) = 矗巧t - j j , o j 。j ，( f = 峨3 ) i j ( 2 1 ) 插值细分曲面设计与分析第2 章t - 4 分裂快速插值细分 图2 - l 四点法插值曲线细分掩膜 那么插值四个顶点的三次l a g r a n g e 多项式为： c ( t ) = p o l 4 ，o ( f ) + p l 厶，2 ( f ) + p 2 l 4 2 0 ) + p 3 l 4 ，3 0 ) 当插值一个顶点在f = ；位置的时候，我们得到： c ( 主) = 一面1p 。+ 话9n + 而9p ：一话1 p ， ( 2 2 ) ( 2 3 ) 公式( 2 3 ) 中的系数为四点法最常见的形式。可以看到，四点法其实相当于 用三次l a g r a n g e 样条曲线插值四个顶点，在中间生成一个新顶点的过程。当然 四点法的系数并不是完全固定的，公式( 2 3 ) 只是四点法的一个特例。通过d y n 的生成函数证明【1 0 j ，四点法的系数只要符合公式( 2 4 ) 就能保证c 7 连续。 口0 = 一缈 l 口i 2 + 国，其中。i 国i s 击 口2 = 三+ m 码= 一口 2 31 - 4 分裂快速插值细分曲面 2 3 1 网格分裂拓扑规则 ( 2 4 ) 细分方法的拓扑分裂规则：对于网格中的每一个三角形面片，算法对面片的 三条边各生成一个新的边点，然后利用新生成的三个边点和三角形面片的原来三 个顶点，按照图2 2 的规则把原三角形分裂成4 个小三角形。此规则一般称为 插值细分曲面设计与分析 第2 章1 4 分裂快速插值细分 l 一4 分裂。b u t t e r f l y 细分【9 】、l o o p 细分【2 5 1 均采用此拓扑规则。 4 么 图2 - 2细分拓扑分裂规则左为原始网格拓扑结构；右为分裂后得到的拓扑结构 2 3 2 正则几何规则 多数的三角形网格都是由大量的正则点和极少数的奇异点所组成。当一个三 角形网格中奇异点太多而导致算法运行结果不理想时，可以通过对网格的预处 理，使网格符合要求，一般可以采取重网格化的方法来进行预处理。 p 力 图2 - 3新边点的计算掩模 由于多数的网格中都是正则点占绝对多数，而且一般情况下，网格内部点也 远远多于边界上的点，所以对一个细分算法来说，内部的正则点处理是非常重要 的。本节中，将只讨论正则情形下的内部点细分几何规则，奇异点以及边界处理 将在后面的章节中论述。而前- d , 节讨论的拓扑分裂规则是对于正则情形和非正 则情形都是一致的。 图2 - 3 给出了三角形三个新边点计算所用到的掩模。q ，、q 2 “、g y 是根 据掩模上的点武o = 1 , 2 ，9 ) 计算出来的点 插值细分曲面设计与分析第2 章l - 4 分裂快速插值细分 对于细分后的生成的新网格，本文提出的方法将采取下面的几何规则： q 卜等( p ：+ p 沪嚣( p ：+ p ；) q ：k + l = 百8 + 0 ( p ；+ p ；) 一嚣( p ：+ p ；) q 卜百8 + c 0 ( p ；+ p ：) 一嚣( p ；+ p ；) p = p p ；“= p ： p ，= p ： ( 2 5 ) 几何规则( 2 5 ) 中的珊一股情况可以取i 。这个规则由6 个算式组成，其中 前三个是计算新生成边点的方法，后面三个表明了本章提出的方法是插值型方 法。网格中原来的点将会保持到细分新生成的网格中。在使用上面的方法计算三 角形三个边点时，三角形还必须满足两个条件：第一、对于将要进行边点计算的 三角形的三个顶点都必须是正则点：第二、三角形的三个顶点不能出现在网格的 边界上，这个条件同时表明了三角形的三条边不能是网格的边界。 可以看到，边点g “是根据边p ? p ；所在的曲线，采取4 点四点细分模式得 到的顶点，对于q ，口；“也是如此。 2 3 3 非正则几何规则 对于一个封闭三角形网格，其中的顶点都不可能全部是正则点，开放的网格 也常常有少量的奇异点，因而在细分规则中引入对奇异点的处理是必要的。 当算法需要生成一个边点时，边点所在的边有三种情况：( a ) 边的两个顶点 都是内部正则点，这种情况已经讨论；( b ) 边的一个顶点是内部奇异点，一个顶 点是内部正则点；( c ) 边的两个顶点都是内部奇异点。这节讨论后两种情况的处 理规则。 当边的一个顶点是内部正则点，一个顶点是奇异点时，算法用奇异点本身与 插值细分曲面设计与分析第2 章l - 4 分裂快速插值细分 奇异点周围一环的顶点作为计算边点的掩模，算法为掩模中每个顶点分配不同的 权重，然后组合这些点生成边点，图2 4 为这种情况的掩模。 当奇异点的度数h 2s ( n 6 ) 时，掩模中每个点a o = 0 , 1 ，2 ，万一1 ) 的对应权 重啦= o , 1 ，2 ，甩一1 ) 计算规n 如- f ： 一= i 1 i 1 + c o s ( 竿) + j 1 ( 半) ) ( 2 6 ) 当疗= 3 时，取w o = 5 1 2 ，w i = - v 1 2 ，m = - v 1 2 ；当一= 4 时，取w o = 3 g ， m = o ，w 2 = - v s ，w 3 = 0 。对于奇异点矿，其权重的计算规则如下； = 1 - - z i 于是得到生成新边点鼋“1 的计算规则： n - i q m = k 矿+ ( 峨p ：) ，0 ( 2 7 ) ( 2 8 ) 当一条边的两个顶点都是内部奇异点时，算法分别对两个奇异点运用图2 - - 4 的掩模和公式( 2 8 ) 计算出两个边点的位置，然后取两个边点位置的平均值为 新边点。 这种取平均值的方法也许会产生细小的误差，而影响曲面的光顺性，但由于 本文提出的拓扑分裂规则使得新生成的点都是正则点，所以这种边两个顶点都是 内部奇异点的情况只会出现在初始网格中，逐级细分得到的中闻网格不会有这种 情况出现。因而，由于取平均值而影响的曲面光顺性的问题将会在多次细分后逐 渐弱化。 插值细分曲面设计与分析第2 章卜4 分裂快速插值细分 2 3 4 边界处理规则 图2 - 4处理奇异点的掩模 增添边界处理的新几何规则。对于有两个顶点在边界上的三角形，如图2 5 ，要生边界上边的边点口y ，算法仍然可以从网格中找到计算这个边点掩模所 需要的4 个顶点p ：、p ；、p ；、p ；。但是算法要生成边点q ”，只能从原网格 中找到钟、p ；、，；，对于四点法来说，还缺少一个顶点的值，同样生成边点g y ， 也只能找到p ：、p ；、p ：。 砖p ： ，：秘 图2 - 5 三角形有两个顶点在边界上 采用镜像点方法可以虚构出掩模中所缺少的点。这样就可以继续使用四点法 来计算边点。在图2 - - 5 中，筋、霹是镜像点，戤与p ；关于p ? 对称，菇与p ； 关于p ；对称通过对称关系，算法得到： 插值细分曲面设计与分析第2 章l - 4 分裂快速插值细分 那么对于几何规则( 2 5 ) 中的g y ，g 的几何规则也改成： 譬= 等。；+ p ；卜嚣( 露+ 露) ( 2 ，9 ) ( 2 1 0 ) 从图2 - - 5 中还可以看到，对于边界上每一条边的边点，其生成掩模的4 个 顶点都是边界上的点，也就是说边界上边点的生成只与边界本身相关，与网格内 部的顶点无关。这个特性对于细分网格的c o 拼接是有用的，当两个网格的边界 原本是重合的，分别对两个网格进行细分，那么细分后得到的新网格的边界也是 重合的。 嚣 对 弋夕 砖 砖 图2 6三角形有一个顶点在边界上 同样原理，对于三角形有一个顶点在边界上的情形，算法也是通过镜像点的 方法虚构出掩模中所缺少的点用于计算。如图2 - - 6 ，露、菇是镜像点，霹与p ； 关于露对称，菇与露关于露对称，通过对称关系，算法得到： ( 2 1 1 ) i 2 i 2 p p 一 一 i i 3 一p + + 1 0 t ， p p = 篁 i i 9p p ，lj、fl ，i 2蟊p 一 一 i ，i 3p + + 露砖 = i i 菇露 ，ti(1l 插值细分曲面设计与分析 第2 章1 - 4 分裂快速插值细分 那么对于几何规则( 2 5 ) 中的q ；“、q ，的几何规则也改成： 2 k + l 百8 + 0 9 【p ：+ p ；) 一面0 9 ( p ：+ 砝) 叮卜等( 硝+ p 沪嚣( p ；+ 敲) ( 2 1 2 ) 图2 一l o 是一个开放的猫模型，模型底部是没有闭合的，从图中可以清晰地 看到边界的细分效果。 2 4 细分曲面连续性分析 由于细分算法本身的复杂性，想通过把细分曲面归结到某类己知的参数曲面 往往是十分困难的，而且这样的参数曲面也不一定存在。这里通过推导出细分模 式的矩阵，然后计算矩阵的特征值的方法来证明矩阵的收敛性。 图2 - 7左图为一个正则点以及其周围2 环的点；中图为上图深色部分局部放大图；右图为 左图细分一次后的结果。 图2 7 为掩模中的每个点都做了标记，设定把掩模的中心点周围l 一环上 的点标记为p ：( f = 0 , 1 ，2 ，3 ，4 ，5 ) ，把2 一环上面的点标记为p 左o = o ，l ，2 ，3 ，4 ，5 ) 与 p ：( f = o ，l ，2 ，3 ，4 ，5 ) ，掩模的中心标记为的p 二( f = o ，l ，2 ，3 ，4 ，5 ) ，这6 个p 名表示的都 是同一个点，为了方便细分矩阵的表示，这里把一个中心点写成六种表示形式。 记钟= ( p 名，p ：，p 二，以) 和b = ( 既，b i ，b ：，马，风，昆) 7 。如果用s 来表示算法的 细分矩阵，那么 插值细分曲面设计与分析 第2 章1 4 分裂快速插值细分 口“= s b ( 2 1 3 ) 根据几何规则(