（应用数学专业论文）细分、优化方法在cagd中的应用.pdf

中文摘要 用细分与最优化相结合来处理模型数据的方法是近几年计算机辅助几何设 计( c a g d ) 领域研究的热点问题，在逆向工程、数据传输等方面有着广阔的应 用前景。 细分方法是c a g d 中用于曲面造型的一种非常有效的方法，其主要思想是根 据细分规则由初始控制网格递归构造新的顶点，新顶点由某些原控制网格点加权 平均生成，随着细分的不断进行，控制网格点逐渐逼近一条光滑的曲线或一张光 滑的自由曲面。这种方法不仅显著地压缩了设计和建立一个原始模型的时间，提 高了计算效率，还允许原始模型局部的精细化；更重要的是，细分方法可以处理 任意拓扑结构的曲面，解决了传统的连续性参数曲面造型方法的拼接问题。因此， 细分方法在计算机图形学领域有着广泛的应用。 最优化方法也是一个备受关注的研究领域，其主要工作是求一组约束条件下 的目标函数的最优解，这通常化为一个无约束极值求解问题。在实际应用中，其 简洁的表述形式与精确的表示能力对研究者和工程技术人员有着巨大的吸引力。 随着计算机技术的发展，其计算精度和计算效率都有了大幅度地提高。现在，它 已经成为一个解决工程问题的强大的数学工具。在c a g d 中，几何模型通常都能 够用一个模型表达式与一组几何限制表示，这就建立了c a g d 中的模型与最优化 方法模型之间的联系。因此，最优几何模型的求解问题最终能够化为一个最优化 问题。 本文总结和研究了细分方法与最优化方法的基本概念和理论、模型构建方法 及经典计算方法。并且，为了解决细分方法产生的大量数据不利于细分模型传输 的问题，本文结合细分方法与最优化方法的优点，采用发送端对模型采样，减少 数据传输量，接收端使用细分、优化技术从采样点中将模型重构的方法，有效地 减少了数据量，提高了数据传输的效率。另外，本文还将细分与最优化相结合的 方法推广到了曲线逼近的应用中。数值实验表明，该方法简单、快速、有效。 关键词：逆向工程细分造型最优几何模型模型重构 a bs t r a c t t h em e t h o do fc o m b i n i n gs u b d i v i s i o nw i t ho p t i m i z a t i o ni nc a g di sar e s e a r c h f o c u sd u r i n gt h e s ey e a r s ，w h i c hh a saw i d ep e r s p e c t i v ei nr e v e r s ee n g i n e e r i n g ，d a t a t r a n s m i s s i o na n ds oo n t h em a i ni d e ao fs u b d i v i s i o nm o d e l i n gi sr e f i n i n gt h ec o n t r o lm e s hr e c u r s i v e l y u s i n gs u b d i v i s i o nr u l e s ，t h en e w v e r t e x e sa r ec o m p u t e db yt h ea v e r a g ew e i g h t e ds u m o ft h e i rn e i g h b o r sf r o mt h eo l dc o n t r o ln e t t h el i m i to ft h ec o n t r o ln e ti se i t h e r s m o o t hc u r v e so rc o n v e r g e n ta n ds m o o t hs u r f a c e s t h ee f f i c i e n c yo fs u b d i v i s i o n a l g o r i t h m s ，w h i c hr e d u c et h ec o s to fm o d e l i n g ，t h e i rf l e x i b i l i t ya n ds i m p l i c i t y ， e s p e c i a l l y t h ea d a p t a b i l i t yo fa r b i t a r yt o p o l o g ym a k et h e ms u i t a b l ef o rm a n y i n t e r a c t i v ec o m p u t e rg r a p h i c sa p p l i c a t i o n s o p t i m i z a t i o ni sa n o t h e rf o c u s e da r e aw h o s e m a i nw o r ki st of i n dt h eb e s tr e s u l to f at a r g e tf u n c t i o nw i t hc o n t r a i n s t h i sp r o b l e mi so f t e nc o n v e n e dt of m d i n gt h e e x t r e m u mo fat a r g e tf u n c t i o nw i t h o u tc o n s t r a i n s i nt h er e a lw o r l d ，m a n yr e s e a r c h e r s a n de n g i n e e r si sa b s o r b e db yi t ss i m p l ee x p r e s s i o na n de x a c tm o d e lr e f l e c t i o na b i l i t y w i t ht h ep r o g r e s so fc o m p u t e rt e c h n i q u e s ，i t sc o m p u t a t i o np r e c i s i o na n de f f i c i e n c yi s p r o m o t e dl a r g e l y b yn o w , i th a sb e c o m eap o w e r f u lm a t h e m a t i c a lt o o l t os o l v e p r o j e c t i o n s i nc a g d ，ag e o m e t r i cm o d e l i n gp r o b l e mc a nb ep o s e da s as e to f g e o m e t r i cm o d e l i n gc o n s t r a i n t s ，i nw h i c hi t h a sf o u n d e dt h ec o n n e c t i o nb e t w e e n c a g da n do p t i m i z a t i o n t h u s ，t h ep r o b l e mo ff i n d i n gt h eo p t i m i z e dg e m o t r i cm o d e l c a l lb es o l v e da sa l lo p t i m i z a t i o np r o b l e m t h i si s s u es u m m a r i z e sa n ds t u d i e st h eb a s i cc o n c e p t i o n sa n dt h e o r i e s ，m o d e l i n g m e t h o d sa n dc l a s s i cc o m p u t a t i o nm e t h o d so fs u b d i v i s i o na n do p t i m i z a t i o n b e s i d e s ， i no r d e rt or e d u c et h ed a t ag e n e r a t e db ys u b d i v i s i o n ，am e t h o dc o m b i n i n gs u b d i v i s i o n w i t ho p t i m i z a t i o nw h i c hs a m p l et h em o d e li nt h ed i s p a t c h e ra n dr e c o n s t r u c ti ti nt h e r e c e i v e ri sp r o p o s e dh e r e t h ee f f i c i e n c yo fd a t at r a n s m i s s i o ni sp r o m o t e d a n di t i s a l s oe x t e n d e di n t oc u i w ea p p r o x i m a t i o n n u m e r i c a le x p e r i m e n t sa r ea l s og i v e nt o s h o wt h a tt h ea l g o r i t h mi ss i m p l e ，f a s ta n de f f i c i e n t k e yw o r d s ：r e v e r s ee n g i n e e r i n g ，s u b d i v i s i o n m o d e l i n g ，o p t i m i z e d g e o m e t r i cm o d e l ，m o d e lr e c o n s t r u c t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得玉鲞苤鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：褪，淆签字日期：劢咕 年f 1 月弓口日 学位论文版权使用授权书 本学位论文作者完全了解垂盗盘堂有关保留、使用学位论文的规定。 特授权盘盗盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：名冬堕蒲 签字日期：z 台年f 月弓d 同 导师签名：汐毒彳牛岸乞 签字同期：上d 口厂年f2 月多矽日 第一章综述 第一章综述 本章前两节简要介绍细分、优化方法的背景及发展历史。后两节则是本文工 作及后续章节安排的介绍。 1 1 细分、优化的背景 细分与优化都是有着很长历史的学科，现在，它们各自都己形成了一套比较 成熟的体系，在现代化工业设计和生产中发挥着重要的作用。 1 1 1 细分方法背景 细分方法是c a g d 中用于曲面造型的一种方法，其思想早在上世纪5 0 年代 就已被提出。自诞生之日起，其简洁的表达形式和良好的设计效果就受到了研究 人员的青睐。经过几十年的发展，细分方法的理论体系已基本建立，应用软件 也比较丰富，现在，它已经成为c a g d 中继参数方法后又一个主要的曲面造型 方法。这主要是由以下几个方面决定的： 一方面，细分曲面( s u b d i v i s i o ns u r f a c e s ) 是一个网格序列的极限，其网格序列 则是通过采用一组规则( 一般是加权平均) 在给定初始网格中插入新顶点并不断 重复此过程而获得。这种方法克服了传统的参数曲面处理任意拓扑网格( a r b i t r a r y t o p o l o g ym e s h e s ) 时存在的困难。因为，在不规则拓扑处只须采用特殊的细分规则 就可以了，不存在拼接的问题。 另一方面，由于三维扫描仪( 3 ds c a n n e r ) 、测距仪( r a n g ef i n d e r ) 和c t 等三维 数据获取设备的日益完善，为几何形状不能或难于用分析曲面表示的对象建模提 供了有力的工具，例如医学的人体器官建模、考古学中的古代器件和艺术领域的 雕塑作品三维重构等等。离散曲面逐渐成为一种重要的几何表示方法。细分方法 作为从给定规则产生离散曲面的方法统一了传统的参数曲面与多边形两种实体 表面的表示。 另外，由于实验获取的三维数据量一般都非常大，多分辨率分析 ( m u l t i r e s o l u t i o na n a l y s i s ) 成为有效地处理这类数据的重要手段。细分方法与多分 辨率分析、小波变换( w a v e l e tt r a n s f o r m a t i o n ) 之间的深刻联系也是目前细分方法受 到关注的一个重要原因。 第章综述 1 1 2 优化方法背景 优化方法，即最优化方法，是一门应用相当广泛的学科，是讨论问题的最佳 选择和寻求最优解的计算方法。它产生于二次世界大战末期，以其简单的表示形 式和对问题的准确描述博得了学术界的重视。在接下来的几十年中，伴随着计算 机的高速发展和计算方法的进步，优化方法的优越性得到了越来越多的体现，因 此也越来越受到人们的重视。现在，它已渗透到生产、管理、商业、军事、决策 等各个领域，成为科学研究和生产设计不可或缺的工具。 1 2 细分、优化的发展历程 任何体系的建立都不是一蹴而就的，都需要经过方法提出、理论发展再到体 系成熟这样一个过程，细分和优化也不例外，下面将简单介绍细分方法和最优化 方法的发展历程。 1 2 1 细分方法的发展历程 细分方法可以追溯到5 0 年代gr h a m 的通过对折线角点进行切害l l ( c o m e rc u t ) 来生成光滑曲线的思想。7 0 年代中期，c h a i k i n 提出的生成曲线的细分方法【i 】正 是这种角切割思想的具体实现。稍后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 】，标志着细分方法正式成为曲面建模的手段。当矩形网格没有奇异顶 点( 见2 1 节的定义) 时，c a t m u l l c l a r k 方法生成三次b 样条曲面：对于有奇异顶 点的网格，生成的曲面除有限个点外，具有二阶光滑性，可以说是一张“几乎处 处 的张量积双三次b 样条曲面。与此同时，d o o 和s a b i n 采用离散f o u r i e r 变 换的方法【3 j ，对c a t m u l l c l a r k 方法的收敛性进行了分析，开创了细分方法收敛性 矩阵特征分析的先河。细分方法的发展历史大致可以分成如下三个阶段： 1 ) 7 0 年代后期是细分方法的萌芽期。c a t m u l l c l a r k 细分方法以及d o o s a b i n 关于奇异点处行为的分析理论标志着细分方法正式成为曲线曲面造型的 一种手段。 2 ) 8 0 年代末到9 0 年代初是细分方法的形成期。在这一阶段，提出了很多 著名的细分方法，对旧方法也有许多改进以适应不同要求。规则情形的 收敛性和连续分析理论也逐渐完善，例如给出了单变元细分方法任意阶 光滑的充要条件【4 5 】。不过，各种方法之间仍然缺乏联系，般情形的收 敛性分析方法也是“随身定作”，缺乏一般的理论指导。 3 ) 9 0 年代中期到现在是细分方法的发展期。这一时期开始建立系统的收敛 第一章综述 性理论，提出了多变元方法任意拓扑情形下收敛性分析的理论框架【6 - 8 】。 这些理论反过来指导细分方法的构造，尤其是二阶以上连续曲面的构造。 此外，各种细分方法的内在联系也逐渐被揭示出来，例如z o r i n 和 s c l a r 6 d e r 为主( p r i m a l ) 四边形网格细分方法和对偶( d u a l ) l 四边形网格细分 方法建立了统一的框架睁】。更为重要的是，在这一时期，细分方法得到 了广泛应用，尤其是复杂网格曲面的多分辨率分析的研究取得了大量成 果。 1 2 2 优化方法的发展历程 正如第一节所说，最优化方法产生于上世纪4 0 年代，最初是作为战略决策 工具为军方服务的。二次大战以后，它的研究和应用由军方扩展到了民间，理论 体系也因此得以不断完善。 5 0 年代以后，随着电子计算机技术的迅速发展，最优化方法领域中的许多子 集，如线性规划、动态规划等由于能够更加方便地求解而被进一步应用于实际操 作中。至5 0 年代末，美国已有约半数的大公司在自己的经营管理中应用了最优 化方法，主要用于生产计划、物资存储、资源分配、设备更薪等方面的管理决策。 6 0 年代中期，造船厂的研究人员在光顺轮船外壳曲线时引用了最小二乘拟合 法，并取得了良好的效果，这是优化模型第一次被引入c a g d 领域。1 9 6 9 年， h o s a k a 在最t j 、- - - 乘拟合的基础上运用最小能量法给出了光顺轮船外壳曲线的方 法1 1 0 】，迸一步巩固了最优化方法在 c a g d 领域的地位。 8 0 年代，由于计算机技术的突飞猛进，计算机图形学也空前繁荣起来，各种 新的图形图像处理技术不断被提出。其中，最优化方法也扮演了重要角色，以 m u m f o r d s h a h 模型为工具把流体力学中的l e v e ls e t 方法引入图像处理领域，从 而提出运用活动边界( a c t i v ec o u n t e r ) 来进行图像分割的方法就是一个重要的例 - - 7 ：ul 1 3 】 oo 现在，最优化方法作为一个强大的数学工具，已经成为c a g d 领域中的重 要成员，在相当多的图像处理和模型设计方法中都能看到它的身影，而在当今发 展最为迅速的逆向工程【1 4 】中，晟优化方法更是成为模型重构必不可少的工具。 1 ；3 本文的主要工作 本文首先按照实际发展的顺序详细研究了几种典型的细分方法和最优化方 法，并指出其在计算机辅助几何设计( c a g d ) 中的应用，进而针对细分生成的 模型数据最大，不利于网络传输，在窄带宽环境下传输模型数据更为困难的特点， 第一章综述 提出了在模型数据传输过程中，发送端离散采样，接收端使用细分、优化技术将 采样点重构，从而减少模型传输过程中的数据量，提高传输的速度和效率的方法， 在本文最后，该方法还被推广到了曲线逼近的应用中。经实践证明，该方法简单， 快速，有效。 1 4 本文内容组织 第一章也就是本章介绍了本文的背景及主要工作； 第二章是细分方法的详细研究，主要内容包括几种典型细分技术规则、性质 的讨论及应用、细分方法的现状和算例； 第三章是最优化方法的研究，主要内容包括最优化方法的基本模型，无约束 优化的计算方法，并在最后举例说明了最优化方法在c a g d 中的应用； 第四章是本文的主要章节，在前两章的基础上说明在模型传输中提出细分、 优化方法的必要性，并给出算法主要的理论推导和算例说明。 第五章是本文的总结及对未来工作的展望 第二章细分技术研究及应用 第二章细分技术研究及应用 本章全面描述细分方法的研究状况，包括细分曲面的特点、分类、性质、计 算及应用，并详细研究了几种基本的细分方法，包括c a t m u l l c l a r k - 细分、d o o s a b i n 细分、l 0 叩细分、i e b u t t e r f l y 细t、；细分等。在本章最后演示了运用 c a t m u l l - c l a r k 方法、d o o - s a b i n 方法及l o o p 方法的实例。 2 1 细分造型基础 2 1 i 基本概念 由于细分处理的主要对象是插值网格中的控制顶点，因此需要对多边形网格 的相关概念作出详细规定。如图2 1 ，一个网格n ( v 玉，f ) ，由一系列控制顶点 v 按一定拓扑关系构成，顶点之间的拓扑关系由边e 和面f 定义。 图2 一l 一个控制网格 每条边定义了相邻的两个顶点连接关系，面是由一系列顶点顺序连接而成， 其中每对相邻的点都有一条边相连。 点的度数( 价) 是网格中以该点为端点的网格边的个数或是与该点相连接的 相邻点的个数，也可以看成是以该点为一个顶点的网格面的个数。这些共点的网 格边和网格面分别称为点的相邻边和相邻面。 面的度数是该面含有的顶点( 或边) 的个数。如果一条边只属于一个面，称 为边界边，如果一个项点属于边界边，则称之为边界顶点。至少包含一个边界顶 点的面被称为边界面，非边界的边、顶点、面分别称为内部点、内部边、内部面。 第二章细分技术研究及应用 如果一个网格没有边界的话，我们称之为闭的，否则称为开的。一个闭合的三角 网格，如果它的每个顶点的度数都是6 ，我们称它是规则的，否则称为奇异的。 相应的，一个闭合的四边形网格，如果它的每个顶点的度数都是4 ，我们称它是 规则的，否则称为奇异的。 对于我们讨论的细分网格来讲，需要满足如下的条件： 1 ) 每个项点至少属于两条边； 2 ) 每条边至少属于一个面，至多属于两个面； 3 ) 每个面至少含有三条边，两个面至多有一条公共边； 4 ) 每个边界顶点至多属于两条边界边。 2 1 2 细分方法的分类 前面已经介绍过，细分造型是由细分规则作用在初始网格得到的。细分规则 可以分为两个部分：一是拓扑分裂规则，用来描述网格每次细分后所有顶点之间 的连接关系，该过程称为分裂；另一个是几何规则，用来计算新顶点的几何位置 信息，这一过程称为平均。 e f 咖 v 瞄 图2 2 顶点分裂( a ) 与面分裂( b ) 示意图 通常有两种最基本的分裂方法：顶点分裂和面分裂。顶点分裂是对于给定度 数为，? 的顶点f ，将其分裂成门个新顶点，每个顶点对应着它的一个邻面，使用 该方式的细分方法称为对偶型。如果i 为内部顶点，则把这些复制顶点依次相连 第二章细分技术研究及应用 形成一个以边形，称此以边形称为新网格的v 一面：对于内部边两个端点分裂构成 的新网格称为e 一面，旧网格多边形每个顶点分裂构成的新网格面与原来的网格 具有相同的拓扑结构，称之为f 一面。图2 - 2 ( a ) 为顶点分裂的示意图。面分裂 是在网格边和面上插入新的顶点，然后对每个面进行剖分，从而得到新的网格， 如图2 2 ( b ) 使用此方式的细分方法称为基本型。根据新生成的面的数量分裂也 可以有不同种类的划分。 除此之外，根据不同的角度，细分方法还有很多种不同的分类方式。根据几 何规则和细分层次之间的关系，若几何规则在不同的分层之间采取相同的系数， 称之为静态细分方法，否则称之为动态细分方法。根据控制网格的类型，可以分 为四边形网格细分和三角形网格细分。根据细分极限曲面与初始控制网格的关 系，又可分为插值细分和逼近细分，其主要区别在于前者v 一顶点的位置在细分 后保持不变。根据表述细分规则的方程类型，又可分为隐式细分方法和显式细分 方法。另外，细分方法还有局部、全局，均匀、非均匀等之分。 2 1 3 细分方法的特点 同传统的参数样条曲面相比，细分方法具有如下特点： 1 ) 拓扑结构的任意性：传统的曲面造型方法很难处理任意拓扑结构的网格， 对于利用张量积方法构造的参数曲面来讲，拼接或裁剪的难度是显而易 见的。而细分方法以其本身为参数空间，在控制拓扑结构的同时又不失 高效性，这正是它最显著的特点。 2 ) 在进行局部特征调控的同时，能够保证曲面整体的光滑性。虽然样条曲 面也具有同样的功能，但细分曲面对局部细节的控制要比它更加的灵活 和方便，同时运算量也要节省很多。 3 ) 高效性：细分方法方法实现简单，数值稳定，由于新点的计算是线性且 局部的，所以相对隐式曲面等来讲计算的效率很高。 细分造型是联系连续模型和离散表示的桥梁，它通过对离散的控制网格不断 应用细分规则而得到连续的极限曲面。 2 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 方法、；方法等。 第二章细分技术研究及应用 2 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 方法是u t a h 大学的c a t m u l l 和c l a r k 于1 9 7 8 年提出【2 】的，这是最早 的细分曲面方法，当时还缺乏比较严格的理论支持，直至u d o o 和s a b i n 利用矩阵的 f o u r i c r 分析技术【3 】对该方法进行收敛性分析之后，才得到广泛的应用和认可。基 于四边形网格的细分方法研究中，很多工作都是在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 _ 4 四边形分裂算子生 成新网格的拓扑，其计算新顶点的几何规则如图2 3 中a - e 所示，具体如下： 1 ) f 顶点( 新面点) ：对应面上所有顶点的平均。设面的四个顶点为 v 1 ，v ，v 1 ，k ，则相应的卜顶点的位置取为 咋= 三( v l + 屹+ b + 屹) 2 ) e 顶点( 新边点) ：对应边两端点与相邻两个面顶点的平均。设内部边 的端点为r o y , ，共享此边的两个四边形面分别为v o v , v 2 v 3v o v l v 4 v ；，那么 与此内部边相对应的e 一顶点为 r 吾( y 0 + v 1 ) + 去( v 2 + 坞+ 屹圳 3 ) v 顶点( 新顶点) ：对应顶点与周围相邻顶点的平均。若内部顶点v 的 卜环的边界顶点依次为r o y , v 2 ，v 2 州，偶数下标的顶点为邻点，奇数下 标的顶点为其四边形面上的对角顶点，相应的v 一顶点为 w = + 争茗+ 鲁善。 c a t m u l l 和c l a r k 取其中的权值为尾= 3 ( 2 n ) ，以= l ( 4 n ) ，= l 一屈一以 4 ) 边界边( v o v l ) 上的e - 顶点为 1 ，、 v e2 互( v o + v 1 ) 5 ) 边界顶点y 在边界上的两个相邻顶点为q ，则v 的v - 顶点为 w = 吉( v o + h ) + 三， 建立c a t m u l l c l a r k 细分新的拓扑网格的规则是连接每一个新面点，连接每一 个新顶点与周围的新边点，具体的细分过程如图2 - 4 所示。可以看出经过次细 第二章细分技术研究及应用 分后，网格中所有的面均为四边形面，奇异点的个数始终保持不变，为初始网格 中非四边形面的个数和奇异点个数之和。 当初始网格为规则网格时，c a t m u l l c l a r k 方法将生成张量积双三次b 样条曲 面，因此可将其看作是双三次b 样条曲面的推广。对于v 顶点权值，口和口可 1 以有多种选择，只要保证聆= 4 时孱= 丢，以= 即可，这个条件使得初始控制 6j o 网格为规则网格时c a t m u l l c l a r k 方法总生成张量积双三次b 样条曲面。j 6 r g p e t e r s 和u l r i c hr e i f 证明尾，儿满足下面的条件时极限曲面是光滑的： 2 卜l 、 ( 4 a n - 1 ) z + 8 f t - 4 s 等+ 5 + ( c o s - 等+ 9 ) ( c o s 2 z r + 1 ) j 二田： ( a ) i t _ 顶点( b ) e - 顶点( c ) 、顶点 卜- _ _ _ 卜_ _ _ _ 1 , 2 1 。： ，( d 越界e 顶点 打卜一_ 1卜。卜。叫 1 ：8 3 ，418 ( e ) 边界v 顶点 图2 3c a t m u l l c l a r k 方法几何规则( a - e 分别对应了几何规则1 ) 5 ) ) 图2 - 4c a t m u l l c l a r k 细分过程 2 2 2d o o - - s a b i n 细分方法 类似于c a t m u l l c l a r k 方法，d o o s a b i n 方法【3 】是基于二次b 样条的离散生成方 法，这是一种逼近型的点分裂方法。在规则网格情况下，细分曲面是均匀双二次 b 样条曲面。 对于顶点为尸( 江l ，2 ，胛) 的初始 卒制多边形p ，c h a i k i n 最早在1 9 7 4 年提 出了一种通过重复割角得到光滑曲线的方法【“，经过一次细分后得到多边形p 件1 ， 其递推公式按照二次b 样条分界点插入为： 第二章细分技术研究及应用 耻缸+ 扣 p = 扣扭 其效果如图2 5 所示。 一。i 一 、1 d 图2 5c h a i k i n 细分过程 d o o s a b i n 细分曲面方法是将c h a i k i n 曲线细分方法推广到b 样条曲面的情 况，对于任意拓扑结构的网格p f ，细分一次后得到新网格p i “，其顶点由p 顶点 的线性组合得到。设f 是p 的一个面，顶点为g ( i = l ，2 ，刀) ，则有几何规则： 在该面内对应只的新顶点q f 取为： q i - - z w p j f ( 刀+ 5 ) 驴霉2 c o s 警n 3 + 二= 型 l咔 i2 j i j 图2 - 6d o o s a b i n 细分生成的三种新面( 实线为原网格，虚线为细分后的网格) 其顶点连接的拓扑规则如图2 - 6 所示，一次细分后将分成三种新面。经过一 次细分后所有的网格顶点度数均为4 ，且非四边形的个数在后面的细分过程中将 保持不变，极限曲面是c 1 连续的，且插值于初始网格面的重心【1 5 】，这个性质是 n a s r i 利用d o o s a b i n 方法解决点集和曲线插值问题的基础。图2 7 是d o o s a b i n 方法具体的细分过程。 图2 7d o o s a b i n 细分过程 、，r 、 ， 一、 ， 一t i i l 十 一 一t 一 第二章细分技术研究及应用 2 2 3l o o p 细分方法 c a t m u l l c l a r k 方法和d o o - s a b i n 方法主要是针对四边形网格的细分，对于三 角形网格的细分，最早是l o o p 提出的基于逼近的l - 4 三角形面分裂方法【1 6 】，它 基于三向箱样条( t h r e ed i r e c t i o n a lb o xs p l i n e ) ，在规则网格上可以生成c 2 连续 的曲面，对于任意的三角形网格，极限曲面除奇异点外是c 2 连续的，在奇异点 处c 1 连续。分裂后新顶点的生成方法如下： 1 ) v 点：若内部顶点v 的相邻点为m ，v 2 ，v ，则相应的v 顶点为 v v = ( 1 - n f l ) v + 砭v f j = l 其中系数可以是由l o o p 【1 6 】给出： = j 1 ( 虿5 一唁3 + 4 c 0 s 争2 ) 阵t w a r r e n 5 】给出： = 3 ，、 而【甩2 3 ) 一3 ( 玎 3 ) 8 n 、 2 ) e - 顶点：设内部边的两个顶点为v o v l ，共享此边的两个三角形面为m v 2 和 v ov i 屹，则e 顶点为 吃= 詈( v i + v 1 ) 十吉( ，吃+ b ) 3 ) 边界顶点处理方法与c a t m u l l c l a r k 方法一致。 ：妻雩二j ：多 ir j 蟛 ， 图2 - 8l o o p 细 拓扑和几何规则 ；八一! 第二章细分技术研究厦应用 图2 - 8 是l 0 0 p 方法的细分规则其拓扑规则与上面的方法类似，连接新的v - 顶点与周围的e 一顶点，并两两连接相邻的e - 边点，具体可见圈2 8 。m 2 9 是l o o p 细分曲面的例子。 对于规则网格，l o o p 方法生成盒式样条( b o xs p l m e ) t 因此是c 2 连续的。对 于不规则网格，需要修改以边界点为端点的内部边的权值，当危满足 ；o - c o s 争t 峨t “。1 c o s 2 一。_ * 时，l 。o p 曲面是一阶光滑的。 2 2 4 蝶形细分方法 图2 - 9l o o p 细分过程 前面的几种方法都是逼近型的细分方 去，1 9 9 0 年d 州t t 等提出了一种三角 形网格上的插值的面分裂型细分方法由于其插值顶点的形状了类似于蝴蝶如 图2 一1 0 ，因此称为蝶形( b u t l e r f l y ) 细分。观察图2 - 1 0 ，新的e - 点q “。由如下方 法得到 9 “= ；( 且+ n ) + 2 ( n + 且) 一叫b + r + 见+ 岛 一般取= 1 1 6 。由于该方法是插值型的且分裂太快，在奇异点光顺性很差， 所以效果不是根理想。 这种方法的缺点在于规则网格上生成的曲面是c 1 连续的，但在奇异顶点处只 能达到c 。连续，如图2 - 1 l 。对此z o r i n 提出了修正的b u t t e r f l y 方法踟能够存 任意三角形网格上生成c 连续的曲面。该方法细分的拓扑规则与l o o p 细分规则 相同几何规则如下： 第二章细分技术研究及应用 图2 1 0 蝶形细分方法 淬：茵 图2 - 1 1 蝶形方法示例 9 1 6 9 1 6 l l 上j s o 1 ：1 6 一 1 jt 6 ( a ) 端点度数等于6 ( b ) 端点度数不等于6( c ) 边界e - 顶点 图2 1 2 修正的b u t t e r f l y 方法 e - 顶点有三类，一类是内部边且两个端点的度数均为6 ，第二类是内部边且 至少有一个端点度数不等于6 ，第三种是边界边的e 顶点，分别如图2 - 1 2 中a - e 所 示。边界e 顶点使s d y n 等人的4 点插值格式。 对第二类e 顶点，设对应边的其中一个端点的价为甩，那么此e 顶点将e b 奇异点本身及其相邻顶点线性组合而成，如图2 1 2 b 表示，其中权值取值为： ，如果赫，则有s = 吉( 丢+ c o s 等+ 扣争 2 ) 如果玎= 4 ，则有& = 吾，是= 一吉，墨= 是= 0 3 ) 如果疗= 3 ，则有s o = 吾，s = 最= 一吉 图2 1 3 左侧为初始三角插值网格，中间为使用蝶形方法细分插值形成的网格， 效果并不理想，右侧是用修正b u t t e r f l y 方法生成的网格，在奇异点不仅满足c 1 连 续，而且没有尖点生成。 。i 麓。黪 7， 一，z，_ 一，： 一 m，；o；上。 ， _ ， ， ，_ v ， 二 ，jjojjv、j一 第二章细分技术研究及应用 ：i ：7 、i f j ；箩：o 沁、 繁三笏 ”k 、， 图2 1 3 插值初始网格的蝶形方法及其修正方法 2 2 5 抠细分方法 3 细分方法是k o b b e l t t l 9 】于2 0 0 0 年提出的另一种c 2 连续的三角网格细分方 法，该方法采用一种全新的顶点插入和分裂方式，如图2 1 4 所示，每次细分时， 对每个三角形面插入一个新顶点，新顶点与三角形的三个顶点以及相邻的三角形 的新顶点相连，最后去掉原三角形的内部边。非边界面的新顶点的度数都是6 ， 旧项点的度数不变，每次细分都使三角形面的个数增加3 倍，两次增加9 倍，面 片的增长速度小于其他细分方法。其中f 顶点和v 顶点的计算规则如下： 1 ) f 顶点：设三角形的三个顶点为v o v j v 2 ，新插入的f 顶点，。由下式计算 v ，= 吾( v o + m + v 2 ) 2 ) v - 顶点：设顶点1 ，的相邻顶点为v 1 一l ，则v - 顶点坳由下式计算 其中 吲训v + 鲁霎u 口* 。 4 2 c o s 塾 9 3 ) 边界上的细分方法可由三次样条方法生成： 纵k + l ，= 击( 1 0 p 幺- 1 6 + p 二。) 硝1 = 寺( 4 蘸。+ 1 9 + 4 t 。) 巧k 川+ l = 击( 硅。+ 1 6 + l o 或。) 第二章细分技术研究及应用 2 2 64 8 细分方法 图2 1 4 ；细分方法示意图 2 0 0 1 年v e l h o 和z o r i n 2 0 】提出了4 8 细分方法，它是每次分类成两段的新的细分 方法，更慢的分裂速度可以更好的加强对细分网格的控制。该方法有很高的连续 性，除了奇异点是c 1 连续外，其他点几乎处处c 4 连续。 对于规则禾8 网格，如图2 1 5 ，每次分裂采用如下拓扑规则： 1 ) 对于所有内部面片，插入新的分裂顶点： 2 ) 通过连接新的分裂顶点与其所在面片的两个相对的顶点，构成新的内部 边： 3 ) 将未连接的原顶点与新的分裂顶点相连，删除原内部边； 这样经过两次细分过程之后，面片的数量变成原来的2 倍，因此可以视其为 一种2 细分方法。其几何规则如图2 1 6 所示。 、 八 、 ， ， 、 、 j 、 q 、 、 尹 皇 ， 图2 1 54 8 方法细分拓扑示意图 第二章细分技术研究及应用 0 o o 图2 1 64 _ 8 细分方法几何规则 2 3 细分方法的连续性和收敛- 陛分析 ， 、 、 1 y 由于细分方法采用迭代格式，没有解析形式，连续性和光滑性的分析非常重 要。早在上世纪七十年代末，d o o 和s a b i n t 3 】利用离散f o u r i e r 变换和细分矩阵特 征分析，开创了细分方法收敛性矩阵特征分析的先河。之后的研究在这一思路指 引下，不断取得成果。1 9 9 5 年，r i e f t 2 1 】在细分曲面c 1 连续性研究方面取得重要 成果，给出了连续性必要条件并提出了特征映射的概念，为细分收敛性研究提供 了有力的工具。从这一时期开始，系统的收敛性理论开始建立，不同形式细分的 连续性准则不断被提出。对于曲面( 双变元) 细分方法，控制网格为正则情形时 连续性分析相对也比较容易。一般地，只需要研究奇异顶点处的极限行为。对于 线性的静态细分方法，从迭代关系得到的局部细分矩阵可用来对极限行为进行分 析。大多数情况下得到的矩阵具有循环矩阵的一些特点，离散f o u r i e r 变换可以 简化矩阵特征根的求解。从而揭示迭代过程的收敛性。p r a u t z s c h 更给出了细分造 型g 连续的充分条件。 2 3 1 线性细分方法的矩阵表示 对于初始的控制网格p ot 设其顶点序列为只( f = 1 ，2 ，胛) ，经过第七次细分 后控制网格为p ，设其顶点序列为( i - - l ，2 ，刀) ，对于线性细分方法，p 卅的 顶点是p 顶点的线性组合，可以用矩阵表达为 ”= s 幸p 矩阵s 。称为细分矩阵或迭代矩阵。若p + 和分别包含了各自网格的全部 顶点则称之为全局细分，否则为局部细分；若s ( 足= l ，2 ) 为固定的常数矩阵， 则称之为静态细分，否则为动态细分。 第二章细分技术研究及应用 对于网格来说，全局矩阵的结构将会很复杂，且对不同的网格就会有不同的 矩阵，要以此对细分方法进行分析是很困难的。事实上这也是不必要的，因为网 格的规则部分的极限行为较容易分析，关键在于研究奇异顶点处的局部极限性 态。以3 细分方法为例，由于它在每个面上生成新的插值顶点，考虑以p 为顶 点，只( f - 0 ，1 ，1 ) 为相邻顶点的伞状网格，如图2 1 7 所示，根据细分规则，p 点细分后生成的新顶点s 为 s ( p ) = ( 1 一吒) 尸+ 只 扭l 相邻的各面上细分生成的新顶点为 将其写成细分矩阵为 s ：1 3 “v 1l 1o 10 1l vv 1o 11 00 l0 2 3 2f o u r i e r 分析 v o 0 q ：i ( p + 霉+ 最。) _ 图2 1 7 ；细分伞状网格 观察前面的细分矩阵s ，下面的部分具有循环性质，在作变换之后可以对其 进行f o u r i e r 分析。引入f o u r i e r 变换的目的是把问题转换n f o u r i e r 系数空间，由于 细分矩阵一般具有一定的循环特性，作f o u r i e r 变换后块状循环矩阵会变成块状对 角阵，从而可以简化细分矩阵的特征分析。 对于序列a = ( a 0 ，口l ，巳) ，其f o u r i e r 变换定义为： 其中，国：p 勘口 色= 熹喜巳2 鬲缶q 第二章细分技术研究及应用 显然，q 2 i 1 万姜句国，这就是f 0 u r i e r 逆变换。把上式代入下述循环矩阵 s = 口。巳 q口。 巳巳一1 口l a 2 口。 得s = u d u 7 ， 其中u 是关于c t j 的v a n d e r m o n d e 行列式 u = 丽1 nv十l 1 l 1国 1 国” 1 缈” 6 0 2 沪是u 的共轭转置。由于u 痧r = i ，即s 与d 是相似矩阵，它们有相同的特征 根。上述分析对珥为块状方阵时也成立，只需把1 ，换成相应的方阵厶c u 根口可。 利用f o u r i e r 分析对细分矩阵进行特征分析的关键是构造块状循环矩阵。针 对具体情况，需要用到一些简单的几何技巧。d o o 和s a b i n 3 】以及b a l l 和s t o r r y 2 2 】 的工作是这方面的典型例子。p e