（计算数学专业论文）catmullclark曲面与loop曲面控制网格的收敛性质.pdf

厦门大学学位论文原创性声明 兹呈交的学位论文是本人在导师指导下独立完成的研究成果本人在 论文写作中参考的其它个人或集体的研究成果，均在文中以明确方式标明 本人依法享有和承担由此论文而产生的权利和责任 声明人( 签名) l 阵旭 z 7 年s 月f f 日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定厦门大学有权 保留并向国家主管部门或其指定机构送交论文的纸质版和电子版，有权将学 位论文用于菲赢利目的的少量复制并允许论文进入学校图书馆被查阅。有权 将学位论文的内容编入有关数据库进行检索。有权将学位论文的标题和摘要 汇编出版保密的学位论文在解密后适用本规定 本学位论文属于 1 ，保密() ，在 年解密后适用本授权书 2 ，不保密() ( 请在以上相应括号内打- 。) 日期。z 啪年岁月日 噍呻月r 日 摘要 本文共分为三章，其内容如下。 第一章首先简要叙述了本文的相关研究背景，并简要介绍了本 文的主要内容 第二章首先简要介绍了c a t m u l l - c l a r k 曲面及相关的一些结论， 然后引入了一种新的方法，并通过这种新方法得到了更精确的误差 估计公式 第三章首先简要介绍了l o o p 曲面及相关的一些结论，然后引入 了与上一章类似的方法，并通过这种新方法得到了更精确的误差估 计公式 关键词t c a t m u l l - c l a r k 曲面；l o o p 曲面；误差估计 4 a b s t r a c t t h i sp a p e ri so r g a n i z e da sf o l l o w i n g ： i nc h a p t e r lw eg i v eab r i e fr e c o u n tf o rt h e c o r r e s p o n d i n gr e - s e a r c hb a c k g r o u n do fc a g da n di n t r o d u c et h em a i nc o n t e n t so f t h i sp a p e r i nc h a p t e r 2w ef i r s ti n t r o d u c et h ec a t m u l l - c l a r ks u b d i v i s i o n s u r f a c ea n ds o m ec o r r e s p o n d i n gc o n c l u s i o n t h e nw ei n t r o d u c ea n e wa l g o r i t h m t od r a wa s s i s t a n c ef r o mt h i sn e w a l g o r i t h mw eo k t a i nam o r ep r e c i s ee s t i m a t eo fc o n v e r g e n c er a t eo fc o n t r o lm e s h e s o fc 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 sa n dg i v eab e t t e rf o r m u l a f o re r r o re s t i m a t e i nc h a p t e r 3w ef i r s ti n t r o d u c et h el o o ps u b d i v i s i o ns u r f a c e a n ds o m ec o r r e s p o n d i n gc o n c l u s i o n t h e nw ei n t r o d u c ean e wa l - g o r i t h m t od r a wa s s i s t a n c ef r o mt h i sn e wa l g o r i t h mw eo b t a i n am o r ep r e c i s ee s t i m a t eo fc o n v e r g e n c er a t eo fc o n t r o lm e s h e s o fl q b ps u b d i s u r f a c e sa n d 百v e b e ：formul|fo：oil o o ps u b d i v i s i o ns u r f a c e sa n dab e t t e rf o r m u l af o re r r o r口、伧 e s t i m a t e k e yw o r d s ：c a t m u l l - c l a r ks u r f a c e s ；l o o ps u r f a c e s ；e r r o r 一 一 e s t i m a t e 5 第一章绪论 第一章绪论 1 1 研究背景 8 计算机辅助几何设计( 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 ，简 称c a g d ) ，是以_ 计算几何簟为理论基础的新兴学科，应用计算 几何建立产品外形的数学模型，通过计算机对产品外形进行描述、 修改和控制，并依靠计算机图形学的图形显示技术实现曲线、曲面 的计算机辅助设计，从而使计算机成为设计人员的得力助手由此 可见，c a g d 不仅依据计算几何的理论，而且还涉及到计算机图 形学的图形处理和显示技术计算几何侧重于学科，而c a g d 则侧 重于工程应用，与计算机图形学有密切关系它研究的内容可归纳 为。 ( 1 ) 几何形体外形信息的定义及在计算机内的表示、描述， 数学模型输入计算机并通过运算求出能够描述该模型的足够多的信 息( 外形数据、结构参数等，并将这些数据参数转化成一连串的数 值信息) ，并存贮于计算机的相应数据库内 ( 2 ) 几何形体外形信息的分析和综合在上述的基础上进行 分析、综合，如有限元分析计算、振动分析、力的分析等，为绘图、 数控加工等提供形状所必要的信息 ( 3 ) 几何形体外形的形状控制和显示设计中需要对形体的 外形进行有效地控制和修改，借助人机交互手段反复进行修改直至 满意，产生适时的图形，利用图形显示设备和显示技术准确地显示 出来 第一章绪论 9 目前最活跃的研究课题是。曲线、曲面的构造和满足一定连续条 件的拼接；曲面造型与立体造型的结合；散乱数据三角化及三角域 插值和几何复杂性等如同一切科学技术的发展使各门学科之间相 互渗透、相互沟通一样，c a g d 与计算机图形学、图形处理、模式 识别、计算几何的学科界线变得越来越模糊起来目前，曲线、曲面 的数学表示及立体造型技术不仅是c g ( c o m p u t e rg r a p h i c s 。即 计算机图形学) 研究的重要基础和组成部分，而且也是c a g d 研 究的重要基础和组成部分同时，自由曲线、曲面的计算机辅助设 计的最终实现与c g 所研究的图形显示的原理和方法又是不可分离 的尤其是在图形学的重要应用领域c a d c a m ( 计算机辅助设 计计算机辅助制造) 中曲面造型和立体造型，可以说也是c a g d 与c g 的综合运用、相互弥补、相互沟通、相互渗透的典型c a d 技术的应用大大缩短了设计周期，提高了设计精度，易于修改，并 可节约大量模型试制材料，而且提高了市场竞争能力c a g d 在 c a d c a m 中有着十分重要、不可忽视的作用，是现代工业革命和 技术革新的一个重要手段 c a g d 是在早期作为样条函数和逼近论等实际应用而发展起来 的早在4 0 年代中期美国数学家i j s c h o e n b e r g 提出了样条函数的 概念，尽管当时未引起人们的广泛重视，但对近代样条函数理论和 应用的发展有着重大意义他的研究工作无疑是样条函数发展史上 一项奠基工作随着科学技术的发展和计算机的广泛应用，人们采 用了低次分段插值的方法，克服了高次多项式计算不稳定的敝端，并 建立了相应的理论，奠定了样条函数插值发展的基础1 9 6 2 年，法 第一章绪论 l o 国雷诺汽车公司的工程师b d z i e r 开始构造以_ 逼近- 为基础的参数 曲线、曲面表示法，并以此为基础建立了一种自由曲线、监面的设计 系统u n i s u r f ，1 9 7 2 年在雷诺汽车公司正式投入使用，使用之后 并不断扩展功能b d z i e r 方法简单方便。形象直观，对使用者又不 要求有多么高的数学基础，而且易予对外形设计进行控制。b d z i e r 方法是将函数逼近论同几何表示相结合到如此简单而直观的地步， 样条用于c a g d 最初的手段是样条插值和参数样条插值，这无疑 是对参数样条曲线用于c a g d 的一种改进，是对c a g d 发展的重 大贡献。1 9 6 4 年，美国麻省理工学院机械工程系教授s a c o o n s 为设计海军舰艇外形提出了用小块曲面片组合起来表示自由曲面， 使曲面片边界连接处可达到任意阶连续的方法，得到了学术界和工 业界的极大推崇，称之为c o o n s 曲面其主要思想是把一张复杂的 曲面用一定数量的曲面片来表示，适当选择曲面片的数学表达式， 然后通过曲面片之间接一定的连续条件拼接，设计过程又能方便地 进行修改，增添控制条件以便修改原始曲面，当把附加条件输入计 算机时会自动产生新的曲面，直至充分反映设计者意图为止这种 由小曲面片拼接成复杂形状曲面，并可交互设计、修改，达到一定 需要精度的交互设计思想是c o o n s 曲面最早体现出来的曲面设计 方法显然c o o n s 曲面法无论是对c a g d 还是对c g 的发展都是 重要的贡献，是一项开创性的工作 2 1 本文主要内容 第一章绪论 1 l c a t m u l l - c l a x k 细分曲面是自由曲面造型的强有力的工具，作为 对双三次样条曲面节点嵌入算法的推广，它可以定义在任意拓朴网 格上，基于这个性质，细分曲面可以广泛应用于具有任意拓朴结构 的复杂形体的造型，例如图形建模，计算机动画设计及医学图象处 理等从1 9 7 8 年c a t m u l - c l a r k 细分曲面产生至今，经历过二十多 年的发展，细分衄面方法在理论研究方面已取得不少成果关于估 计细分控制网格与精确的极限细分曲面之间的距离，以及近似程度 如何，需要经过多少次细分步骤才能达到满足一定程度的误差要求 这个问题，文献【4 】给出了一个答案在这个基础上，本文第一部 分给出了一个新的方法，并应用这个方法得到了更好的误差估计公 式 同样的方法也被应用在l o o p 细分曲面上，本文第二部分在文献 【8 】的基础上用这个方法得到了更好的误差估计公式 第二章c a t m u l l - c l a r k 细分曲面控制网格的收敛性质 1 2 第二章c a t m u l l c l a r k 细分曲面控制网格的收 敛性质 从1 9 7 8 年c a t m u l l - c l a r k 细分曲面产生至今，经历了二十多年 的发展，细分曲面方法在理论研究方面已取得不少成果c a t m u l l - c l a r k 曲面是一种逼近形式的细分曲面框架，因此一个重要的问题 是研究其控制网格的收敛速率以及极限曲面产生过程的误差估计 文献【4 1 利用相邻点的概念和一阶差分给出了这方面研究的初步结 果本章首先介绍c a t m u l l - c l a r k 细分哇珏面的定义及一些记号，然后 在文献【4 】的基础上提出新的算法，并借助此算法得到关于c a t m u l l - c l a r k 细分曲面控制网格的收敛速率的更精确的估计和给出更好的 误差计算公式 2 1c a t m u l l - c l a r k 细分曲面介绍 c a t m u l l - c l a r k 细分曲面是自由曲面造型的强有力的工具作为 对双三次b 样条曲面节点嵌入算法的推广，它可以定义在任意拓朴 网格上，其极限曲面为c 2 连续的三次b 样条曲面对于任意多边 形网格，经过一次c a t m u l l - c l a r k 细分就会变为四边形网格图l 显示了c a t m u l l - c l a r k 细分过程在细分过程中，称由上一层网格 的每个面生成的新顶点为面点( f _ 顶点) 。由每条边生成的新顶点 称为边点( b 顶点) ，由每个顶点得到的新顶点称为顶点( v 顶 点) ，新点的计算公式如下。 ( 1 ) f - 顶点；一个面所有旧顶点的平均； 第二章c a t m u l l - c l a r k 细分曲面控制网格的收敛性质1 3 价概 ( a ) 初始网格( b ) 一次c 扯砌皿- c 姒细分 ( c ) 两次c a t m u l l c l a r k 细分 图hc a t m u l l - c l a r k 细分过程 第二章u a t m u l l - u l a r k 细分曲面控制网格的收敛性质 1 4 均； ( 2 ) b 顶点t 旧边中点和共有这条边的两个面的新面点的平 ( 3 ) v 顶点。按如下公式得到： 垒+ 竺4 - 兰f 堡二望 绍。佗 。 n 其中： , - - - 和旧顶点相关联的所有面的新面点的平均； r = 和旧顶点相关联的所有边的中点的平均； s = 旧顶点； n = 旧顶点的度数，即与旧顶点相关联的边的数量 新点产生后，按如下规则建立拓朴结构- ( 1 ) 连接每一个新面点和对应旧面的边上的新边点 ( 2 ) 连接每一个新顶点和对应旧顶点相关联的边上的新边点 按此规则对控制网格进行操作可以得到加密的控制网格不断 重复这个过程，控制网格将收敛于一张光滑的曲面当控制网格为 四边形网格时，得到的曲面就是双三次b 样条曲面当控制网格为 任意拓朴结构时得到的曲面称为c a t m u l l - c l a r k 细分曲面 由于c a t m u l l - c l a r k 细分曲面可以定义在任意拓朴结构上，这 给实际应用带来了很大方便如图【2 】所示，对控制网格按c a t m u l l - c l a r k 规则细分一次后所有的控制网格都会成为四边形，且在细分 过程中奇异点( 即度数不为4 的点) 的个数将保持不变事实上， c a t m u l l - c l a r k 曲面除了奇异点以外的部分可以达到俨连续，而 在奇异点处至少可以达到切平面连续 第二章c a t m u l l - c l a r k 细分曲面控制网格的收敛性质 1 5 2 2c a t m u l l - c l a r k 细分曲面控制网格的收敛性质 从1 9 7 8 年c a t m u l l - c l a r k 细分曲面产生至今，经历了二十多年 的发展，细分曲面方法在理论研究方面已取得不少成果c a t m u l l - c l a r k 曲面是一种逼近形式的细分曲面框架，因此个重要的闻题 是研究其控制网格的收敛速率以及极限曲面产生过程的误差估计 文献【4 】利用相邻点的概念和一阶差分给出了这方面研究的初步结 果本文在文献这个基础上提出新的算法，并借助此算法得到关于 c a t m u l l - c l a r k 细分曲面控制网格的收敛速率的更精确的估计和给 出更好的误差计算公式 1 、定义和记号 假设控制网格已经过至少两次细分，其奇异点是孤立的记i i ( o ) = p 1 1 i 2 n + 8 为c a t m u l l - c l a r k 曲面片s ( u ，v ) ，0 仳 1 ，0 钐l 的初始控制网格( 假定曲面片按s t a m 2 的方法参数 化) ，如图2 a 所示，其中p 1 是一个度数为n 的奇异点经过一次 细分后，得到一组新的控制顶点，它们构成一个新的控制网格，记 为l - i ( 1 ) = p ：l 1 1 i 2 n + 1 7 ，如图2 b 所示记细分n 次后形 成的控制网格为( n ) = p 1 1 i 2 n + 1 7 下面引入相邻点的概念 定义1 在控制网格i i ( n ) 内，若某个小空间四边形以曩n 为其一 个顶点，则此四边形其它顶点称为碍n 的相邻点 如图【3 a 】，硝o 的相邻点为硅m ，砖0 1 ，础+ 1 第二章c a t m u l l - c l a r k 细分曲面控制网格的收敛性质1 6 定义2 在第订层控制网格i i ( o 中，令( 吣= m a x 删矽一 硌l i ，其中硌是曩n 的相邻点， 其中l i l i 是三维欧氏空间r 3 中的距离范数 在下文中，为方便起见。将掣简写为b ，并将( o ) 简写为 。 ( a ) 细分前的控制网格( b ) 细分后的控制网格 图2 ：c a t m u l l - c l a r k 细分过程 2 、定理及证明 本节给出本章主要结果及其证明注意到按s t a m 2 】关于控制 顶点的排列顺序，每次细分后，图2 b 中左上角的控制子网格( 即由 点只，1 主2 + 1 组成的控制子网格) 具有相同的拓朴结构( 参 见文献【2 】2 ，p 3 9 7 ) 关于这些子网格的关系，本文证得如下结论。 定理1 对于第2 佗层控制网格( 2 川，有如下估计。 ( 加) m ( ) n ， 第二章u a t m u l l o u l a r k 细分曲面控制网格的收敛性质 1 7 这里 删，= 一 n = 3 n = 4 5 证明。含奇异点的子控制网椽( 1 ) = 曩1 ) 1 1 i 2 n + 8 ) 的 顶点组成的向量q 可以由细分矩阵a 乘以细分前控制网椽i i ( o ) ) 的顶点组成的向量岛得到而初始网格( i i ( o ) ) 细分后得到的控 制网格( ( 1 ) ) 的顶点组成的向量( 参见图【3 b ) 两则可以由增 广细分矩阵再乘以h ( o ) 的顶点组成的向量c o 得到： a = a c o ，q = a c o 一一 u o一 一一 v l m u l一 片，b ，p 2 n + s ) q ，曩u ，州p 2 i ) + 8 ) 曩，砭，p 2 2 i ) + 1 7 ) 关于c a t m u l l - c l a r k 细分矩阵a 和它的增广矩阵a 的具体形 式，参见附录a 要证明定理，显然只需证明 ( 2 ) m ( n ) a 根据a = a c o ，显然有q = a 2 c o 直接计算得，当n = 3 时， ( 2 ) 蔫； 当n = 4 时， ( 2 ) 罴； 第二章c a t m u l l - c h r k 细分曲面控制网格的收敛性质 1 8 下面详细考虑当n 5 时，如图2 a 所示，计算可得。 曩2 = 1 6 n 2 i - 溺4 6 ：广n + 4 9 d i + 1 9 刚n ，- 。2 1 p 2 + 8 上n 。- v 。t p 3 , + + 鼍g 产最 + 黼鼢+ l ； 矗2 = 1 9 矿n - 2 1 j f r t ：) i + _ 2 3 匝n 矿2 + 7 2 r d 2 + _ 1 1 狺n 矿2 + 2 4 上r d 3 + 丽n 2 + 9 _ d 4 + 曩n 丽2 + 2 4 d 5 + 丽n 2 + 1 4 4 一d 6 + 赤马+ 赤b + + 赤鼢一t + 赤鼢一3 + 冬磊斋笋只w 一2 + n z 洲2 + v 2 4 p 州,一l + 一n 工。2 。+ v 。9 只2 + 帮只w + l ； 砖2 =丽8 n - - 7 r d l + 訾恳+ 号男铲b + 1 1 丽n 丙2 + 广2 4 r d 4 + 丽n 2 + 4 f d 5 + 百n i 豇+ 矿2 4 一d 6 + 素斋b + 赤r + + 菩萨3 最一2 + 素l 丽只j 一l + 紫恳+ 涨恳+ 1 则有： 6 4 n 3 ( 硝一曩2 ) = ( 3 2 n 3 一口一n b n ) p 1 一( 1 1 n s o ) 恳 一( 6 n 3 6 ) b 一( i i n 3 一a n ) p 4 一( n s h ) 尼 一( 3 一a n ) p 6 + b n p 7 + a n p 8 + + a n p 2 一2 + b p 2 n 一1 一( 3 一口) 恳一( 3 6 ) 恳+ l ， 其中 a n= 1 2 8 n 一1 6 8 ，6 = 2 8 n 一2 8 令6 4 n 3 ( p ；f 射一砖2 ) = h i + 日2 ，其中。 1 - 1 1 = 【8 n 3 一( n 一6 ) a n 一( 一2 ) b n p 1 一( 6 n 3 一b n ) p 3 一( n s 一6 ) 尼 一( 3 6 ) 马+ 1 + b n p 9 + a n p l o + + a n p 2 n 一4 + b n p 2 1 v 一3 ； h 2 = ( 2 4 n 3 6 a n 一2 b n ) p 1 一( 1 l n s 一口) 恳一( 1 l n s a n ) p 4 一( 3 一a n ) 1 6 + 6 b + a n p s + a n p 2 n 一2 + b n 最一l 一( 3 一a n ) p 2 n 则有s 第二章c a t m u l l - c l a r k 细分曲面控制网格的收敛性质 1 9 h i 当 5 - 2 = 当n h 2 其中k ( 6 3 6 ) ( 只一b ) + ( 3 6 ) ( 只一b ) + ( 3 6 ) ( 只一恳+ 1 ) + h ( 局一只) + a ( e l o 一只) + + a n ( p 2 n 一4 一只) + h ( p 2 p t 一3 一只) 【8 3 + ( 一6 ) a n + ( n 一8 ) b n a n 1 0 时，r 和p 2 n 的系数一( 胪一口) 是正数，则有t 一( 3 一口) ( r 一只) 一( 3 一蛳) ( 恳一恳) + ( 1 2 3 2 a v ) ( p 1 一恳) + ( 1 2 n 3 2 口) ( 只一只) + 6 ( 岛一只) + a = ( p 8 一r ) + a n ( 马一2 一只) + 6 ( 鼢一1 一只) ( 2 2 n 3 + 2 b - ) a ； 1 1 时，r 和恳的系数一( 3 一口) 是负数，则有。 ( 1 l n 3 一口) ( r 一恳) + ( 1 l n 3 一a n ) ( p 1 一只) + k ， ( 2 n 3 4 a n 一2 b n ) p 1 一( n 3 8 ) p 6 一( n 3 一c n ) p 2 n + h b + a n p 8 + a n p 2 n 一2 + 6 恳一1 t l ( 2 a n + 2 b n ) a 1 1 n 1 6 i ( 2 3 2 a n ) a n 1 7 则有： 凰 ( 2 2 n 3 + 2 6 ) 1 1 1 6 i ( 2 4 n 3 4 a n ) a n 1 7 于是就有。 0 硝一砖2 l l 由0 研+ 日2 0 一8 n 3 + 3 9 n 1 6 z - 2 3 8 0 n + 2 2 0 一a ， n 5 = l i g ：- 章u a t m u u - u l a r k 细分曲面控制网格的收敛性质 2 0 直接计算可得， 0 曩2 ) 一毫2 i i 0 曩射一砖2 0 同理可得， l l 曩一曩2 i i 8 n a + 3 9 n l 。2 6 - 2 3 8 0 n t 2 2 0 u a ， n 5 ， 这里3 i 2 n + 1 下面再考虑i 碍钠一背i i ，这里2 i 2 n + 8 ，拶是 曩2 的所有相邻点 若硌= 曩鼢，那么同以上的结论一样 若硌曩。则结合文章【4 】中的结论，显然有： o 曩孙一硌i l 剖碍n 一碍8 i 9 63 n 2 + 椰7 n - 4 0 一a e p 证明了当n 5 时， ( 2 ，坐坐掣a 至此，定理证毕 利用定理1 和细分曲面的凸包性质，我们有如下定理： 定理2 设佗为细分次数，v 0 ，要使得第他层控制网格n ( n ) 与极限曲面s ( u ，v ) 的距离如e ，只要。 n t 2 l o g m ( ) 一1 万7 a 证明t 对于第2 n 层控制网格，以矗n ) = 主( 矗住+ 曩n + 砖n + 磁n ) 为球心，以三m ( ) n a 为半径作一个球，则第2 n 层控制网格 完全被包含在这个球内根据细分曲面的凸包性质显然极限曲面 第二章c a t m u l l - c l a r k 细分曲面控制网格的收敛性质 2 l 也在这个球内则第2 佗层控制网格到极限曲面的距离不会超过球的 直径三m ( ) n a 要使得第死层控制网格( n ) 与极限曲面s ( u ，v ) 的距离厶e ，只要丢m ( ) ( 詈) e ，就有。 馆 12 1 。g m ( 胪芸 下面是应用定理2 的个实例图3 分别是n = 3 时的初始网 格、细分一次的网格、细分四次的网格以及极限曲面设对细分两 次后的网格取= l ，要求最大误差不超过o 0 1 则由定理2 的 计算公式得到访= 9 。这时控制网格到极限曲面距离的最大误差不 超过0 0 0 7 3 3 ( a ) 原始的控制网格( b ) 细分一次后的控制网格 ( c ) 细分四次后的控制网格( d ) 极限血面 图3 ：n = 3 的c a t m u l l - c l a r k 细分过程 第三章l o o p 细分曲面控制网格的收敛性质 2 2 第三章l o o p 细分曲面控制网格的收敛性质 l o 叩细分曲面是美国犹他大学的c h a r l e sl o o p 于1 9 8 7 年在 其硕士论文【5 】中提出的一种逼近型三角形面分裂细分曲面，它是 基于b 样条逼近型算法的一种细分策略j s t a m 在【6 】中对l o o p 细分曲面重新参数化文献【8 1 证明了l o o p 细分曲面控制网格以 指数数率收敛于极限曲面，并给出了误差计算公式本章首先介绍 l o o p 细分曲面的定义和一些记号，然后在文献【8 】的基础上延用上 一章提出的方法，并由此得到关于l o o p 细分曲面控制网格的收敛 速率的更精确的估计和给出更好的误差计算公式 3 1l o o p 细分曲面介绍 l o o p 细分曲面是一种基于三角网格的面分裂逼近细分模式。其 生成的极限曲面是箱样条曲面的推广由l o o p 细分规则产生的极 限曲面在正规点处达到伊连续，而在奇异点处达到c l 连续图4 显示了l o o p 的细分过程 如图5 所示，l o o p 按如下规则产生新的点。 ( 1 ) 新边点( 岛) 。设该边的两个顶点为岛，只，共享这条边 的两个三角形为局，最，局和岛，只，恳，则新边点为 忍= 西3 ( 局+ 最) + 丢( 恳+ p 3 ) ； ( 2 ) 新顶点( r ) ：设与原顶点局相邻的顶点为只，恳，r ， 其中n 是局的度数，则新的顶点为： r = ( 1 一n p ) p o + p 只 第三章l o o p 细分曲面控制网格的收敛性质 2 3 ( 曩) 初始网格( b ) 一次脚细分 ( c ) 两次l o o p 细分 图4 ：l o o p 细分过程 9 ( 1 ) 新边点( 忍) 的产生( b ) 新顶点( r ) 的产生 图5 ：l o o p 细分规则 第三章l o o p 细分曲面控制网格的收敛性质 2 4 新点产生后，依次连接每个新边点和原边的两个顶点产生的新 顶点就得到新的控制网格 按此规则对控制网格进行操作可以得到加密的控制网格不断 重复这个过程，控制网格将收敛于一张光滑的曲面l o o p 细分曲 面除了奇异点以外的部分可以达到俨连续，而在奇异点处可以达 到c l 连续 3 2l o o p 细分曲面控制网格的收敛性质 l o o p 细分曲面是美国犹他大学的c h a r l e sl o o p 于1 9 8 7 年在 其硕士论文【5 】中提出的一种逼近型三角形面分裂细分曲面，它是 基于b 样条逼近型算法的一种细分策略j s t a m 在【6 】中对l o o p 细分曲面重新参数化文献【8 】证明了l o o p 细分蓝面控制网格以 指数数率收敛于极限曲面，并给出了误差计算公式本文在这基础 上延用上一章的算法，并由此得到关于l o o p 细分曲面控制网格的 收敛速率的更精确的估计和给出更好的误差计算公式 1 ，定义和记号 记i i ( o ) = p p l l i n + 6 ) 为l o o p 曲面片s ( 缸，钞) ，0 珏 1 ，0 移l t 的初始控制网格( 假定曲面片按s t a r e 6 】的方法参 数化) ，如图6 a 所示，其中p l 是个度数为n 的奇异点按l o o p 细 分规则对它进行一次细分后，得到一组新的控制顶点，它们构成一个 新的控制网格，记为i i ( 1 ) = p ：u 1 1 i n + 1 2 ，如图6 b 所示 记细分n 次后形成的控制网格为( n ) = p ：t 1 ) 1 1 i n + 1 2 下面引入相邻点的概念 第三章l o o p 细分曲面控制网格的收敛性质 2 5 ( 矗) 细分前的控制网格( b ) 细分后的控制网格 图6 ：l o o p 细分过程 定义3 在控制网格i i ( n ) 内，若曩住和曩n 为同一条边的两个顶 点，则称曩n 和巧n 互为相邻点 如图6 a ，硝的相邻点为砭们。巧，艘1 定义4 在第n 层控制网格i i ( n ) 中，令 ( n ) = m a x l l 曩川一硌i i ，其中掣是碍n 的相邻点) ， 其中l l 0 是三维欧氏空间r 3 中的距离范数 在下文中，为方便起见，将碍o 简写为p i ，并将( o ) 简写为 2 定理及证明 本节给出本文主要结果及其证明注意到按s t a r e 6 】关于控制 顶点的排列顺序，每次细分后，图6 b 中左上角的控制子网格( 即由 第三章l o o p 细分曲面控制网格的收敛性质 2 6 点b ，l i n + 6 组成的控制子网格) 具有相同的拓朴结构( 参 见文献【6 】) 关于这些子网格的关系，本文证得如下结论。 定理3 对于第3 死层控制网格n ( 轨) ，有如下估计。 这里 ( 鼽) m ( ) 竹a ， 一 老一1 n = 3 ，4 ，5 ，6 7 1 9 2 0 证明：含奇异点的子控制网格( ( 1 ) = 曩1 ) 1 1 t + 6 ) 的 顶点组成的向量q 可以由细分矩阵a 乘以细分前控制网椽i i ( o ) ) 的顶点组成的向量岛得到而初始网格( i i ( o ) ) 细分后得到的控 制网格( i i ( 1 ) ) 的顶点组成的向量( 参见图6 b ) 一c 1 则可以由增广 细分矩阵趸乘以( o ) 的顶点组成的向量g 得到： q = a 岛，g = a c o 艇一 u 0一 一一 u l一 邝一 u l一 只，忍，p + 6 ) 群，砖，p n ( + 6 ) 曩，巧，p n 1 + 1 2 ) ) 关于l o o p 细分矩阵a 和它的增广矩阵才的具体形式，参见附 录b 要证明定理，显然只需证明 第三章l o o p 细分曲面控制网格的收敛性质 2 7 ( 3 ) m ( n ) a 根据q = a 岛，显然有岛 = a 3 c o 直接计算得，当n = 3 ，4 ，5 ，6 时，( 2 ) 丢a ； 下面详细考虑当n 7 时，如图【6 a 1 所示，计算可得： 碍3 = z s t 2 4 x 2 2 - 6 - 1 2 5 1 3 盯6 z 一+ 9 8 3 0 4 d l 一+ 2 4 p 1 露+ 1 啄5 3 瓦6 z 矿- - 1 6 3 8 4 0 f d 2 一 一z z + 2 4 x 1 2 + 葩1 瓦5 3 面6 z r - 1 6 3 8 4 0 f r l + l ； 曩3 = 3 z 2 + 1 1 9 两2 x 丽+ 一1 2 2 8 8 f d l 一3 , z 2 + 1 9 2 = j - - z ，2 8 8 1 0 y n - 1 2 4 8 0 p 2 , 一3 z 2 t 1 9 2 x 3 - 2 7 1 6 8 9 2 0 n - 1 2 4 8 0 p d 一1322+192x-576n-12480p：4一322+192=-64n-12480_d5一3x2+夏19汤2x霭-矿12480jrrd32768n 3 2 7 6 8 n 56 4 一一面丽蓟r 一6 3 x 2 + d l z 9 ，2 。x 6 - y 1 2 4 8 0 p j i ，一2 一3 z 2 + 1 9 1 2 x 两- 丽6 4 丙n - 1 2 4 8 0 j f r d 一l 一3 z 2 + 1 9 2 琵x - - 丽5 7 酊6 r n - - 1 2 4 8 0 d 一3 z 2 + 1 9 2 x 葡- 丽1 9 圃2 0 r n - 一1 2 4 8 0 j r r r ) n 一+ 1 3 2 7 6 8 。“ 3 2 7 6 8 一一一上 + 其中z = ( 3 + 2 c o s 2 万1 r ) 2 则有t 2 6 2 1 4 4 n ( p ( 一p 2 ( 3 ) ) = n x 3 p 1 + ( y 一2 3 0 4 0 n ) p 2 + ( 秒一1 5 3 6 0 n ) p 3 + ( y 一4 6 0 8 n ) p 4 + ( y 一5 1 2 n ) p s + y p 6 + + y p m 一2 + ( y 一5 1 2 n ) p 一1 + ( y 一4 6 0 8 n ) p n + ( 秒一1 5 3 6 0 n ) p + 1 这里y = - - x 3 + 6 4 0 0 0 ，显然y 0 当7 n 1 1 时，只和p 的系数y 一4 6 0 8 n 0 ，且 1 秒一4 6 0 8 n l i y 一1 5 3 6 0 n i ，则有。 第三章l o o p 细分曲面控制网格的收敛性质 2 8 原式= ( y 一4 6 0 s n ) ( p 4 一恳) + ( y 一4 6 0 s n ) ( p n p + 1 ) + ( - - 2 y + 1 9 9 6 8 n ) ( p 1 一b ) + ( - 2 y + 1 9 9 6 s n ) ( p 1 一p + 1 ) + ( y 一5 1 2 n ) ( p 5 一只) + ( 箩一5 1 2 n ) ( p n 一1 一只) + ( 一暑f + 2 3 0 4 0 n ) ( p 1 一恳) + 秒( 尼一只) + + 秒( p 一2 一只) l l 原式0 【( 一8 ) u + 5 2 7 3 6 n ； 当1 2 n 1 9 时，只和p 的系数y 一4 6 0 8 n f y 一5 1 2 n f ，则有s 原式= ( y 一5 1 2 n ) ( p 5 一只) + ( 可一5 1 2 n ) ( p n l p ) + ( - 2 y + 5 t 2 0 n ) ( p , 一只) + ( - 2 y + 5 1 2 0 n ) ( p l p ) + ( 一秒+ 1 5 3 6 0 n ) ( p , 一b ) + ( 一y + 1 5 3 6 0 n ) ( p , 一p + 1 ) + ( 一+ 2 3 0 4 0 n ) ( p , 一恳) + 秒( r 一只) + + 矽( p 一2 一只) i l 原式i l 【( 一1 2 ) y + 6 2 9 7 6 n a ； 当9 5 n 1 8 9 时，b 和p 一1 的系数秒一5 1 2 n 0 ，且 l y 一5 1 2 n i 2 0 l2 6 2 1 4 | 埘 至此，定理证毕 利用定理3 和k o b b e l t d a u b e r t - s e i d e l 7 中的结论，我们有如 下定理： 定理4 设n 为细分次数，v e 0 ，要使得第n 层控制网格( n ) 与极限曲面s ( u ，v ) 的距离厶e ，只要s n 3 l o 断( ) - 1 詈 证明：根据a 的定义和k o b b e l t d a u b e r t s e i d e l 7 中关于l o o p 细分血面的界的结论。可知厶a ( 川再结合定理3 。就有 d 3 n m ( ) n a v e 0 ，要使厶e ，就有- 礼3 i o g m ( n ) - ti a n7891 01 11 2 1 3 o o g ( ) 3 0 1 9 1o 2 4 40 2 8 6 0 3 1 90 3 4 6 0 3 6 80 3 8 70 6 3 5 m ( n ) 0 1 6 9 0 2 0 10 2 2 5 0 2 4 30 2 5 7 0 2 6 80 2 7 80 4 2 9 附录a c a t m u l l - c l a r k 的细分矩阵为t b 弋s f 历l 、 页盘旺 b nc n o0 0o o0 oo ee o0 其中： deedee a = l 一南，6 = 杀，甜= 而1 ，d = 百3 ，e = 去，= 三 s l l =s 1 2 = 3 1 2 20 毋 、l-、2o & q e o o o； e ， 幻 e 0 0 o ；d ， h o 0 啊 o o ， 幻 e ， 甜 e ， h d 厂鲋d ， 0 o o 0 o c e c o 0 0 e 6 e 厶 o o 0 e c o 0 o c e o 0 0 c e 6 e o 0 0 6 e c o 0 o o c 0 o o o o 0 o o o 0 0 o 0 0 0 c e o 0 0 o 0 厶 d 0 0 0 6 d 口 d e c 0 g d