（计算机软件与理论专业论文）细分表面建模—插值细分表面技术.pdf

摘要 摘要 本文研究细分方法在图形学中的应用，细分方法近年来已成为图形学领域的一项重 要研究内容。但是，要进一步拓广细分方法的应用范围( 尤其在c a d 领域) ，还有很多工 作要做。本文先简单地列举了一些常用的表面建模方案，指出细分方案作为一种新颖的 表面建模技术其存在的历史背景和理由，然后，给出了细分技术作为表面建模的数学基 础，即讨论了她是基于b 一样条技术的一般扩展，分析了两个经典的细分方案的连续性， 由于细分作为一个新的表面建模工具，在随后章节中，我们提出了两个改进的细分方案， 分别是基于顶点的插值细分方案和基于曲线插值的细分方案。 构造可调的顶点插值任意拓扑结构的光滑表面在计算机图形学领域是一项重要的 课题。本文改进了插值的d o o s a b i n 细分表面的初始控制网格，在第一次细分的同时加 入了表面调节参数。该方案具有以下特征：首先满足插值所有顶点或某些顶点的同时可 以由参数调节极限表面；增加了对极限表面的调节自由度。其次整个的计算复杂度为 0 ( k ) ，其中k 是顶点的数量。在第三章的最后也对结果表面的形状处理进行了讨论。 在可调表面上完成曲线插值的工作在图形学应用领域中也是一项重要的任务。本文 提出了一个带有多特征的曲线插值可调表面的算法。首先引入形状相似性参数，拓扑地 修改初始控制网格。这样使得在满足曲线插值的同时，结果表面与初始控制网格有不同 的相似性；引入双边控制调节参数，更新插值曲线两边位置，调节插值曲线的弯曲程度； 形成求解满足控制曲率公式。结果表明此算法使得曲线插值可调表面可行，能够表现出 多样性。 关键词：表面细分；顶点插值；极限表面调节；形状控制；曲线插值；曲率控制 a b s t r a c t a b s t r a c t t h i st h e s i ss t u d i e sm o d e l i n ga n da p p l i c a t i o no fs u b d i v i s i o ns u r f a c e s s u b d i v i s i o nm e t h o d h a sb e c o m ea ni m p o r t a n tt o o li nc o m p u t e rg r a p h i c sr e c e n t l y t oe x t e n da p p l i c a t i o na r e a s ( e s p e c i a l l yi nt h ea r e ao fc a d ) m o r ew i d e l y , h o w e v e r , m a n yp r o b l e m sh a v et ob es o l v e d w b l i s ts o m ec o m m o ns c h e m e st h a tm o d e l i n gs u r f a c e s ，a n dw ep o i n tt oi t sh i s t o r yb a c k g r o u n d a n de x i s tr e a s o n s ，a tt h e1 a s t , w es h o wt h ef o u n d a t i o no fm a t h e m a t i co fs u b d i v i s i o n t e c h n o l o g yw h i c hw eh a v ed i s c u s s e di ti sag e n e r a l i z eo fb - s p l i n e ，a n dw eh a v ea n a l y s i s c o n t i n u i t yo ft w os c h e m e s s i n c et h es u b d i v i s i o nt e c h n o l o g yi sn e w t o o lf o rm o d e l i n gs u r f a c e ， f o l l o w i n gc h a p t e r s ，w eh a v ep o s t e dt w os c h e m e st h a ti n t e r p o l a t i n gs u r f a c e si nt h i sp a p e r t h ec o n s t r u c t i o no fa na d j u s t a b l es m o o t hs u r f a c ei n t e r p o l a t i n gam e s ho fa r b i t r a r y t o p o l o g i c a lt y p ei sa ni m p o r t a n tp r o b l e mi nm a n yg r a p h i c sa p p l i c a t i o n s t h ep a p e rp r e s e n t sa m o d i f i c a t i o no ft h ec o n t r o lm e s ha n das u b s e q u e n td o o s a b i ns u b d i v i s i o n t h em e t h o dh a s t h ef o l l o w i n gf e a t u r e s ：f i r s ti tc a na d j u s te x t r e m e l ys u r f a c ea c c o r d i n gt oas c a l a ra n dc a n i n t e r p o l a t es o m eo ra l lv e r t i c e so fam e s hw i t ha r b i t r a r yt o p o l o g y , t h u sm a k et h en e wm e t h o d i t s e l fs u i t a b l ef o ri n t e r a c t i v ef r e e - f o r ms h a p ed e s i g n s e c o n dt h ew h o l ec o m p l e x i t yi so ( k ) ， w h e r eki st h en u m b e ro ft h ev e r t i c e s a tt h ee n do ft h i sc h a p t e rw eh a v ed i s c u s s e ds h a p e a d j u s tw h i c hi sd i f f e r e n ts u b d i v i s i o ns u r f a c e t h ec o n s t r u c t i o no fa na d j u s t a b l es u r f a c e sc u r v ei n t e r o o i a t i n gi sa ni m p o r t a n tt a s ki n m a n yg r a p h i c sa p p l i c a t i o n s a na l g o r i t h mw i t hm u l t i - f e a t u r e sf o rc u r v e si n t e r p o l a t i n go nt h e a d j u s t a b l es u r f a c ew a sp r o p o s e d t h ep a r a m e t e r so ft h es a m e n e s so ft h er e s u l ts u r f a c e sw e r e i n t r o d u c e d a n dt h ec u r v e sw e r ed e f n e d t h ec o n t r 0 1m e s hw a sm o d i f i e dt o p o l o g i c a l l y , a n d t h em e s ht ob ei n t e r p o l a t e d u n d e rt h ec o n d i t i o no fs a t i s f y i n gc u r v e si n t e r p o l a t i n g ，s o m e s i m i l a r i t i e sb e t w e e nr e s u l ts u r f a c ea n dc o n t r o lm e s hh a db e e nm a d ea n dt w o s i d ea d j u s t a b l e p a r a m e t e r sw e r eu p d a t e d i tu s e dt h ep r e d e f i n e dc u r v a t u r et oa d j u s tt h eb e n d e dd e g r e eo ft h e c u r v e sa n dc r e a t e dt h ec u r v a t u r ec o n t r o lf o r m u l a t h er e s u l ts h o w si ti sa v a i l a b l et ot h ec u r v e i n t e r p o l a t i n ga d j u s t a b l es u r f a c e sa n dt h ee x t r e m e l ys u r f a c e sa r ed i v e r s e k e y w o r d s ：s u r f a c e ss u b d i v i s i o n ；v e r t e xi n t e r p o l a t i n g ；e x t r e m es u r f a c ea d j u s t a b l e ； s h a p ec o n t r o l ；c u r v ei n t e r p o l a t i n g ；c u r v a t u r ec o n t r o l i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签 名 趣煎罐日 期： 塑堡：笪：! 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规 定：江南大学有权保留并向国家有关部门或机构送交论文的复印件扣 磁盘，允许论文被查阅争借阅，可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致 保密的学位论文在解密后也遵守此规定 签 名：瓤铬伟 导师签名：期： 。6 艿， 。l 第一章绪论 第一章绪论 这一章里，先介绍表面建模的大致概况， 细分技术的背景，然后给出本文的主要内容， 1 1 引言 包括由来、分类、传统表面建模的不足， 最后安排后续章节。 曲面建模是c a d 和计算机图形学中最活跃、最关键的学科分支之一，是c a d 系统 的一个重要组成部分，也是c a g d 中的一项重要研究内容，主要研究在计算机图象系 统的环境下对曲面的表示、设计、显示和分析。c a d c a m 、计算机图形学、计算机艺 术、动画片、模拟仿真、计算机视觉、机器人等领域都把曲线曲面建模作为基础。 1 1 1 曲面建模 曲面建模是一个有着较长历史的领域，6 0 年代初期就已经诞生。它起源于汽车、飞 机、船舶、叶轮等的外形放样工艺，由c o o n s 、b e z i e r 等大师于二十世纪六十年代奠定 其理论基础。现在曲面建模技术已经形成了以插值( 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 1 2 曲面建模的表示方法 在曲面的表示上，曲面建模的表示方法大致包括以下几类u 1 。 1 、参数曲面建模技术：参数曲线曲面表示一直是描述几何形状的主要工具，由 c o o n s ，b 6 z i e r 等人在6 0 年代奠定其理论基础。s c h o e n b e r g d l 在1 9 4 6 年提出的样条函 数多年后被发现可解决曲线曲面的连接问题，同时还可以用来解决顶点插值问题。 1 9 7 1 年，法国雷诺( r e n a u l t ) 汽车公司的b 6 z i e r h l 发表了一种用控制多边形定义曲线 的方法，设计人员可以通过移动控制顶点达到控制曲线整体形状的目的，并且可以预测 曲线形状变化趋势，具有良好的交互性。后来f o r r e s t 悔。，g o r d o n 和r i e s e n f e l d 1 等对b e z i e r 方法作了深入研究，将b e z i e r 基表示形式改写为现在广泛使用的b e m s t e i n 基表示形式。 在应用过程中，b e z i e r 曲线曲面暴露出曲线段或曲面片间需要进行细致费时的连续 拼接以及不能进行局部形状修改等问题。1 9 7 2 年，b o o r n l 和c o x 俑1 分别独立地给出了b 样条计算的标准算法_ d eb o o r - c o x 递推公式，应用递推公式使计算简便稳定，且为新 工具的产生作了理论准备。1 9 7 4 年，美国通用汽车公司的g o r d o n 和r i e s e n f e l d 旧3 将b 样 条理论用于形状描述，提出了b 样条曲线曲面。b 样条方法兼具了b 6 z i e r 方法的切优 点，较成功地解决了局部控制问题，并在参数连续性基础上解决了连续拼接问题。 上述方法较成功地解决了自由型曲线曲面建模方面的问题，然而它却不能精确地表 示除抛物线和抛物面外的二次曲线曲面，只能给出近似表示。1 9 7 5 年，美国s y r a c u s e 大学的v e r s p r i l l 在他的博士论文中首先提出有理b 样条方法u 们，克服了以上缺陷。以后， 经过众多学者的深入研究，至8 0 年代后期，p i e g l 和 f i l l e r 。将有理b 样条发展成非均匀 有理b 样条( n o n u n i f o r mr a t i o n a lb s p l i n e ) 方法，即n u r b s ，至今已成为描述自由曲 线和曲面的最广为流行的技术。由于n u r b s 在外形表示方面的强大功能与潜力，它被 江南大学硕士学位论文 作为工业产品数据交换的s t e p 国际标准n 副，也成了定义工业产品几何形状的首要数学 方法。 尽管n u r b s 成为了现行的工业标准，各种曲面都是定义在矩形参数域上，即矩形曲 面片，无法有效地表示任意拓扑形状的曲面。通常采用逐片构造方法来表示复杂物体表 面，这时候需要对曲面片进行剪裁( t r i m m i n g ) 或直接在非规则的四边形网格上构造曲面 片，无论哪种情况都要考虑片与片之间的光滑连接。这是一个相当困难的工作，后来， 人们提出了细分建模技术u 副。 2 、隐式曲面建模技术：在c a g d 中，形状的数学描述的另一个重要工具就是隐式 曲面。参数曲面构造简单、计算容易。且一般来说，参数曲面比较容易绘制、分割及定 界。然而参数曲面的不足是其代数次数很高，且由于参数曲面对于曲面的等距及求交等 操作的不封闭性，使得基于参数曲面的几何建模系统的发展受到了阻碍，因此，近年来 对隐式曲面的研究正在不断加强n 劓。与参数曲面相比，隐式曲面具有更多的自由度。在 构造复杂曲面的时候，能够得到更高光滑度，提供更多的形状控制手段。隐式曲面表达 形式紧凑，而且具有几何运算下的封闭性m 3 。任何参数或隐式曲面之间如求交、等距操 作等几何运算的结果均可表示成隐式形式u 刮。 3 、变形曲面建模技术：为了更方便、直观地构造和编辑三维形体，b a r r n 刀率先将变 形思想引入到几何建模领域。它模拟了力学中常见的几种变形，如拉伸、均匀张缩、扭 转和弯曲等，并给出了这些变形的数学表示。应用b a n 的方法，可以生成许多类型的三 维几何形状。由于该方法仅能用于特定的几何形体，一般称其为非自由型变形。 4 、基于形状混合的曲面建模技术：形状混合技术( s h a p eb l e n d i n g ) 又称形状插值 ( s h a p ei n t e r p o l a t i o n ) 、形状平均( s h a p ea v e r a g i n g ) 、形状过渡( s h a p et r a n s i t i o n ) 、形状 演化( s h a p ee v o l v i n g ) 、变形( m o r p h i n g m e t a m o r p h o s i s ) 等n 副，是指由给定的两个物体( 这 里的物体可以是平面曲线定义的形状、平面数字图象、三维曲面、三维形体等) 产生一 系列逐渐改变形状的中间状态的物体，来完成已知的两个物体之间的形状过渡；这里新 产生的中间状态的物体同时具有原来两个物体的形状特征u 引。 5 、细分曲面建模技术：由于参数曲面建模技术不足，细分曲面( s u b d i v i s i o ns u r f a c e s ) 受到越来越多的关注，是本文研究的对象。其主要原因在于细分方法可从任意拓扑网格 出发构造出光滑曲面而无需考虑几何连通性。由于计算机图形学、计算机动画等领域对 任意拓扑结构的光滑曲面建模的需求变得日益迫切，n u r b s 曲面在表示复杂拓扑物体 方面存在着许多困难，无法满足这一要求，而细分方法由于能够很好地产生拓扑结构复 杂的曲面，因此，成为近年来曲面建模技术研究的一个热点。给定一个初始网格( 或初 始控制网格或输入网格，在不至于混淆主题的情况下，本文将同时使用这两个说法) ， 细分过程就是要计算一个细化的网格序列，此序列收敛于一张极限曲面。通过插入新点， 并按一定的规则与已有的网格点相连，得到一个新的细化网格。新点的位置由上一层网 格点按一定的几何规则计算得到。 曲面建模还有其他方法，我们这里不一一赘述，更详细的讨论可参考口仉2 。由于细 分技术是用于解决曲面建模而引入的，所以，本章对曲面建模的分类做了大概介绍，关 2 第一章绪论 于细分的进一步叙述，将在下一个章节中进行。 1 2 本文内容 本文研究的主要内容是构造可变的插值表面，包括可调表面的顶点插值和可调表面 的曲线插值，并对结果表面进行相应的处理。完成的工作包括基于d o o - s a b i n 细分方案 啪1 的可调节表面的顶点插值；基于c a t m u l l - c l a r k 细分方案3 的的可调节表面的曲线插 值；在每个细分方案后面，我们给出它们实现的结果图；在对已经存在的各种插值表面 的进行了仔细的对比和较深入的研究的基础上，尝试构造一些行之有效的表面建模方法 以进一步提高使用细分方法的建模曲面能力。 1 3 本文结构 第1 章，引言，即本章，引入本文研究的主题、背景以及本文的主要工作，并交代 后续章节的安排。 第2 章，细分方法的综述，讨论了细分在国内外的研究概况及基本概念和基本数学 基础( 关于对细分方案详细的数学分析可以参考文后的参考文献) ；最后探讨了细分技 术的两个分类：即逼近和插值。 第3 章和第4 章，本文的主要工作。第3 章描述了一个基于控制网格拓扑修改的可 调d o o s a b i n 细分曲面的顶点插值建模方法。第4 章讨论了基于可调c a t m u l l c l a r k 细分 曲面的曲线插值方法，在保持曲线插值的同时，此方法还引入了曲线插值参数，更灵活 地调节结果表面。 第5 章，实现，讨论了实现本文提出的两个插值方案的数据结构和实现算法以及实 现平台。第6 章，总结了本文的主要工作，并对下一步的工作提出了一些设想。 江南大学硕士学位论文 第二章细分曲面技术概述 2 1 引言 在计算机辅助几何设计中，即c a g d ，自由曲线曲面往往由离散数据通过指定的调 配函数表示成连续的参数形式。但这种连续的信息一旦用于实际，如在计算机屏幕上或 在绘图仪上绘制出来，或用数控机床进行加工，还需要将连续的模型离散化，这是一个 “离散一连续一离散”的过程。然而，以连续表示作为中间媒介有时并非必要，而且还增 加麻烦，降低效率。相反，放弃连续模型，直接用离散数据表示、操作曲线曲面更适合 于显示、加工和求交计算等，也更适合于外形设计。直接从离散到离散的建模方法与传 统的方法不同，它通常没有显示表示形式，仅提供一个算法描述过程，用以产生加密的 离散点列或点阵来表达曲线曲面的信息，细分技术便是这种建模的典型代表盈劓。另外， 由于计算机图形学、计算机动画等领域对任意拓扑结构的光滑曲面造型的需求变得日益 迫切。n u r b s 曲面在表示复杂拓扑结构的物体方面至少会遇到以下困难1 ：修剪是昂 贵的，而且有数值误差；要在曲面的接缝处保持光滑，即便近似光滑也很困难，因为模 型是活动的。而细分方法有潜力克服以上两个困难，她无须修剪，活动模型的平滑度被 自动地保证。由于细分方法能够很好地产生拓扑结构复杂的曲面，无须修剪，活动模型 的平滑度被自动地保证，算法简单直观晒1 ，因此，成为近年来曲面造型技术研究的一个 热点。许多商业图形动画软件，如a l i a s l w a v e f r o n t 公司的m a y a ，p i x a r 公司的r e n d e r m a n ， n i c h i m a n 公司的m i r a i ，以及m i c r o p a c e 公司的l i g h t w a v e3 d 等都将细分作为一种曲面 表示方法。1 9 9 9 年a c ms i g g r a p h 成就奖授予t o n yd e p o s e m 。，原因就是表彰他把细 分方法应用于解决图形学中的实际问题所做的贡献( 在1 9 9 8 年的电影作品中，美国p i x a r 动画电影“g e r i sg a m e 荣获奥斯卡奖，t o n yd e r o s e 使用c a t m u l l c l a r k 细分方法建模 了电影中的g c r i 人物) 。这标志着在c a g d 和计算机图形学中，将细分技术作为重要的 曲面建模方法之一，得到了图形学界的一致公认。细分方案用给定规则产生离散曲面的 方法统一了传统参数曲面和多边形曲面这两种表面的表示。另外，由于实验获取的三维 数据量一般都非常大，多分辨率分析( 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 ) 之间的深刻 联系也是目前细分方案受到关注的一个重要原因3 之一。 本章将对细分技术做一简单描述，阐述细分技术的国内外研究概况包括细分技术的 基本概念，基本数学基础，讨论细分技术的两个分类：逼近和插值。 2 2 国内外研究概况 细分( s u b d i v i s i o n ) 方法可以被简单地解释如下：将光滑曲线或曲面定义为连续细 化过程的极限汹1 。细分曲面( 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 yt o p o l o g ym e s h ) 时存 4 第二章细分曲面技术概述 在的困难。因为，在不规则拓扑地方只须采用特殊的细分规则就可以了，不存在拼接问 题。 细分的基本思想可以追溯到上个世纪四十年代晚期和五十年代早期。其创始人可以 追溯到5 0 年代的d er h a m 啪一利，当时d er h a m 就已经使用对多边形割角( c o r n e rc u t ) 的 方式来描述一条光滑的曲线。但最初引起c a g d 领域注意的是在1 9 7 4 年美国u t a h 大学 举行的c a g d 国际会议上，图形艺术家c h a i k i n 硷鲫提出了一种与众不同的曲线的快速生 成方法，它以直观的几何构造为基础，从一个闭合的2 d 多边形开始，通过重复的割角 操作，得到一条光滑的极限曲线，随后r i e s e n f e l d 乜钔和f o r r e s t m 们从理论上证明了这种极 限曲线其数学本质即是均匀二次b 样条曲线。1 9 7 8 年，c a t m u l l 和c l a r k 心纠，d o o 和s a b i n 啪1 则分别提出了将双三次和双二次b 样条曲面推广到任意拓扑网格上的细分算法，将对曲 线的细分推广到了曲面，也意味着细分技术应用于曲面建模的开始。从此对曲面的建模 也有了新的起点，不再将初始输入网格局限于矩形网格了，即使用b 一样条张量积表面。 这也使得细分可以将带有“奇异点 和“奇异面 的初始网格作为输入网格成为可能。 所谓“奇异点 是指在一个点不被四个面共用；“奇异面是指一个面不是由4 个边组 成。同时，在1 9 7 8 年，d d o o m l 对双二次细分曲面做了连续性分析，提出了一个分析细 分技术在“奇异顶点处的行为。对细分的递归行为，使用了矩阵乘积和矩阵特征根分 析技术曙u 。关于这个方面的工作，b a l l 和s t o r r y 在1 9 8 4 年继续进行这项研究口幻，他们 改善了c a t m u l l c l a r k 细分方案中的“奇异顶点 处周围顶点的系数。s t o r r y 口3 1 在他的博 士论文中提到，“奇异顶点的极限表现是其相邻顶点分布的仿射变换，这种仿射变换 可以被细分矩阵的特征向量完全确定，并把这个特点叫做细分的“本质结构 ( n a t u r a l c o n f i g u r a t i o n ) 。 1 9 8 7 年，l o o p 婚钊在其硕士论文中提出了一种基于三角网格的逼近细分方法。该方 法是在b o e h m 曙5 1 和p r a u t z s c h 婚副的盒样条( b o xs p l i n e ) 细分算法的基础上提出的，将四次 三方向盒样条( q u a r t i c 3 d i r e c r i o nb o xs p l i n e ) 推广到任意的三角网格上。该方法不仅确定 了细分网格的新的定义域一三角形域，而且使用特征根分析的方法来确定一个细分方案 在“奇异顶点 处周围顶点系数的选择。随着l o o p m 3 提出基于三角形的细分方法后， 人们又找到了新的分析细分技术的方法，如提出了使用z 一变换和傅立叶变换分析方法。 1 9 9 5 年，r e i f 3 提出了使用“特征映射( c h a r a c t e r i s t i cm a p ) 技术，推导出结果表面c 1 连 续的充分条件。而d y n ，l e v i n 和g r e g o r y 刚等人则提出了一种四点插值的曲线细分规则， 他们的方法在两个方面体现了与其他方法不同：一是，他们的方法不是逼近的而是插值 的，即结果曲面能够插值初始控制网格和细分过程中所产生的所有顶点；另一个是，极 限曲线不是由分段参数多项式表示的，除此之外，他们方法的连续性和可微性分析还有 待于使用新的工具。1 9 9 0 年，d y n 和l e v i n 等口吼删又据此给出了基于三角网格的插值型 细分方法，生成所谓的蝶形曲面( b u t t e r f l ys u r f a c e ) ，提出了新的分析这类细分方案的技 术。另外，这种细分方案要求初始网格是正则的三角网格，即每个顶点的共点三角形数 均为6 ，如此才能保证极限细分曲面是c 1 连续的。以上四种基本的细分方案是细分方法 发展早期阶段的重要研究成果，为后来新的细分方法提供了可借鉴的构造途径，并且也 江南大学硕士学位论文 在实际应用中，发挥着重要作用。 由于b u t t e r f l y 方法对初始控制网格的限制，使其不能应用于任意拓扑网格。1 9 9 6 年，z o r i n 等h u 提出了改进的b u t t e r f l y 算法，该方法可以在任意拓扑网格上生成c 1 的细 分曲面。基于变分的细分方法是由k o b b e l t m 4 钉提出的，细分网格不再由静态的规则决定， 而是通过使某些能量函数最小化来生成新网格。对于规则网格，该方法即为四点法的张 量积形式。细分过程中，新顶点的位置是通过求解一个优化问题确定的，即使某种能量 函数最小化。因而这种细分方法是整体性的，即每个新点的位置依赖于上一层网格中 的所有顶点。p e t e r s 和r e i f 划，h a b i b 和w a r r e n 心5 1 分别提出了一类简单的细分方法，将 二次四方向盒样条( q u a d r a t i c4 d i r e c t i o n b o xs p l i n e ) 推广到任意的四边网格上。他们使用 的细分模板比d o o s a b i n 方法的模板更小；对于规则点，只需用到三个控制点。1 9 9 8 年， q i n 和m a n d a l 等h 町将动态模型引入到c a t m u l l c l a r k 曲面中。这种动态曲面模型使得对 几何形状的操作更为直接。后来他们又将这种方法推广到了b u t t e r f l y 曲面。1 9 9 8 年 s i g g r a p h 会议上，s e d e r b e r g 和我国学者z h e n g j i a n m i nm 1 提出了广义的c a t m u l l c l a r k 细分方案和d o o s a b i n 细分方案：在细分过程中引入了节点距，提出了不同节点距的 d 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 和非均匀 c a t m u l l c l a r k 细分表面的特征根进行了分析，使得n u r b s 成为它们的一个子集。2 0 0 0 c 年，k o b b e l t h 明提出了一种新的用于三角形网格细分的方法，称为3 细分，其拓扑分裂 规则与以往的基于三角形网格的细分方法不同，剖分三角形并不是一分为四，而是一分 为三。除奇异顶点外。极限曲面达到c 连续，在奇异顶点处可达到c 1 连续。l a b s i k 口们 c 提出了一种基于三角形网格的插值型细分方法，称为插值v - j 细分，其拓扑分裂规则与 c k o b b e l t 的j 细分规则相同；几何规则则与b u t t e r f l y 细分类似，细分过程中只计算新 产生点的位置，而老点则保持不变( 这是插值方案的本质) 。v e l h o m 5 2 1 提出了一种拟静 态细分方法，4 - 8 细分方案，用于对四方向网格( f o u r - d i r e c t i o n a lm e s h e s ) 的细分。2 0 0 1 年，我国学者z h a n gh o n g x i n ，w a n gg u o j i n 嵋3 1 提出了蜂窝细分，他们是基于六边形网格 rr 的细分。2 0 0 3 年，李桂清畸钉在他的博士后出站论文中提出了、，2 细分，同时也讨论了2 插值细分模式。 基于各种经典的细分方案，研究人员提出了各种各样的或基于顶点或基于曲线的插 值方案。1 9 9 1 年到1 9 9 7 年，n a s r i 曾提出了一系列的基于曲线插值方案嘞删。2 0 0 2 年， n a s r i 和a b b a s 哺u 提出了基于c a t m u l l c l a r k 细分方案的曲线插值方案。2 0 0 3 年，张 景峤和王国瑾旧1 从对称区域的角度，提出了一种基于c a t m u l l c l a r k 的曲线插值方案。 2 0 0 5 年和2 0 0 6 年，z h e n gj i a n m i n 和c a iy i y u 哺3 朋1 提出了一种新颖的基于d o o s a b i n 和 c a t m u l l c l a r k 的顶点插值方案；他们在逼近细分方案的基础上，提出了满足带有插值约 束的细分方案，使产生的结果表面拥有更多的灵活性。2 0 0 2 年，秦洪等删使用有限元 方法，提出了各种细分的框架。 目前，细分曲面( s u b d i v i s i o ns u r f a c e ) 建模技术得到了广泛的研究一l 删，文献嘲1 给出的三个大概的归类，这里我们将其简单扩充：( 1 ) 基于各种细分规则的构造：l o o p b 叼 6 第二章细分曲面技术概述 的基于三角形的细分技术。p e t e r s 和r e i f ( 训提出的最简单的细分构造。q i n m j 7 1 等将动态 模型加入到c a t m u l l - c i a r k 曲面中去，这些方案都是逼近的构造。同时，d y n ，l e v i n 和 g r e g o r y 船钔提出的著名的“b u t t e r yf l y 插值细分算法。随后z o r i n 等人h 等改进了这一 算法以取的得更好的光滑性质。这两个插值细分方案是基于三角形结构的拓扑网格。 k o b b e l t 3 则提出了适合四边形网格的插值算法。l e v i n 鹋1 设计了细分规则用于网格曲 线插值。n a s r i m 7 1 1 将基本的细分算法应用到各种造型要求中去，比如多面体细分和自由 曲线的产生等。其它的细分方法还包括基于变分原理的规则m 7 2 瑚1 ，这些细分方法是在 细分的过程中，规则是可改变的。文献m 1 是基于n u r b s 推广的细分规则。文献n 们是具有 某些特殊性质的细分规则等。( 2 ) 基于细分的实用有效的算法研究：h a l s t e a d 口朝等发现 了精确计算细分曲面上点的位置和法向的公式，从而建立了光滑函数用来构造光滑的插 值曲面。s t a m m 3 进一步分析了精确计算和表示细分曲面的问题。h o p p e t 7 7 3 等修改规则用 于产生具有尖点、尖边等特征的细分曲面。d e r o s e 晗副和l e e 等h 鲫是属于研究应用细分曲 面到某些具体问题中去的。( 3 ) 对细分曲面连续性的数学分析：最早d o o 和s a b i n 噙_ 叮 应用f o u r i e r 技术和特征根分析的方法来讨论细分曲面的连续性。随后b a l l 和s t o r y 7 9 删 及s a b i n l 8 1 3 给出了进一步的分析，并由此导出一组优化的细分规则。此外，r e i f 和p e t e r s 3 7 闺1 提出了特征映射的概念，更严格地分析了连续性和光滑性。l e v i n 1 于2 0 0 6 年提出了进 一步修改细分某些，在局部区域可以达到c 连续，但是他也没有解决整体的不规则顶 点处的c 2 连续。 大部分已有的细分方法都是用于构造流形曲面( m a n i f o l ds u r f a c e ) ，但有一些生物组 织结构模型以及一些人工艺术建模需要用到非流形曲面( n o n m a n i f o l ds u r f a c e ) 。因此， 2 0 0 1 年，y i n g 和z o r i n 8 盯提出了一种可以用于构造非流形曲面的细分方法。 1 9 9 6 年，m a c c r a c k e n 和j o y 嘶1 将c a t m u l l - c l a r k 细分方法推广用于体网格( v o l u m e m e s h ) 的细分，但由于其细分规则的复杂性，曲面的光滑性还是个未知数。2 0 0 1 年，b a j a j 等阻6 1 提出了一种细分方法，可用于六面体网格的细分。 细分方法的优点可总结如下啪1 ： 任意拓扑：细分技术将经典的样条面片推广到能够处理任意拓扑结构的控制网格， 这意味着不需要处理难以对付的面片修剪工作。 稳定性：由于递归结构，细分很好地可以满足层次细节( l e v e lo f d e t a i l ) 绘制的需 要。在一定的误差范围内，可以自适应调整到一个近似结果曲面，算法更好地利用有限 的硬件资源，使细分技术可以在低端p c 上实现。在进行局部特征调控的同时，能够保 证曲面整体的光滑性。 均匀一致的表现形式：大部分传统的曲面建模要么使用多边形网格，要么使用样条 片作为建模输入模型。细分技术则是联系两者的桥梁，她的结果表面即可以表现得象样 条面片拼接的结果，也可以表现的象许多小的多边形组合的结果。 数值的稳定性：使用细分技术产生的结果表面有许多良好的满足有限元解的属性， 细分技术对数值仿真任务表现出了很高的稳定性，这对于工程和计算机动画都有重要的 意义。 7 江南大学硕士学位论文 执行代码的简单性：另外，隐藏在细分思想背后的基本观点使得细分被实现起来非 常简单。尽管在分析她的数学性质可能比较棘手，但是这丝毫不影响她在工程上的使用， 即算法实现非常简单。 除此之外，细分还有诸如高效性：可以在一般的终端上使用；局部定义性：极限曲 面上的点不需要原始网格上更多的顶点来确定；仿射性：在实时性动画表现非常有意义； 连续性：可以支持高分辨率绘制；紧凑性：对局部顶点的修改影响的区域非常小，对于 交互性编辑非常重要。 细分曲面的重要特点是思想简洁、适用于任意拓扑网格且具有多分辨率结构。当前 国际上，从2 0 0 0 年到2 0 0 7 年，几乎每年的p r o c e e d i n g so fg e o m e t r i cm o d e l i n ga n d p r o c e s s i n g 、i n t e r n a t i o n a lc o n f e r e n c eo nc o m p u t e ra i d e dd e s i g na n dc o m p u t e rg r a p h i c s 和 p a c i f i cc o n f e r e n c eo nc o m p u t e rg r a p h i c sa n da p p l i c a t i o n s 的国际会议上都有与细分有关 的论文。另外，每年举行的a c ms i g g r a p h ( 计算机图形学和交互技术特别兴趣小组) ， a c mt r a n s c a t i o n so ng r a p h i c s ( a c m 图形学的专刊) ，c o m p u t e r a i d e dg e o m e t r i cd e s i g n ， c o m p u t e rg e o m e t r i cd e s i g n ，i e e et r a n s a c t i o n so nv i s u a l i z a t i o na n dc o m p u t e rg r a p h i c s ， w w w g r a p h i c s s t a n f o r d e d u ，斯坦福大学图形学研究实验室。这些会议、期刊和实验室基 本上反映了当前计算机辅助几何设计领域的最新研究成果和进展。 当然，尽管有许多的研究机构、期刊、兴趣小组，他们解决了细分方案中遇到的一 些问题。但是，关于细分方案在工业化方面的使用仍然没有完成陋钉。对于常见的一些细 分曲面，人们已经有了一个较好的认识。但是，要进一步拓宽细分方法的应用范围( 尤 其是在c a d 领域的应用) 还有很多工作要做啪1 ：例如，高阶连续细分方案的构造，目 前大部分使用的细分方案还没有整体达到c 连续( 在奇异顶点处只有c 1 连续) ；细分方 法与解析方法的溶合；细分曲面的光滑；细分曲面间的逻辑运算，比如使用细分方案建 模时，各个实体间的求交运算；数学分析工具的改善( 目前使用傅立叶变换和有限元分 析) ；动态细分；大规模数据拟合；以及满足各种应用要求的新方案的发展等等。这里 高阶连续细分方案是指生成的极限曲面整体连续次数都大于或等于2 的方案。对于复杂 的细分曲面，连续性仍然是一个未解决的问题旧1 。 有关细分方法较全面的讨论，可参看啪2 5 7 驯。本章简要阐述细分方案的构造和细 分技术中插值曲面的相关工作，并介绍一些基本概念，其中的一些内容在呻7 1 中有较详细 的论述。 8 第二章细分曲面技术概述 l 墨一 二氐l 么讼 图卜1 几个经典细分方法的比较 f ig 卜1t h ec o p m ar is i o no f $ e v e r a lc l ass ! c a ls u b d l v is i o ns c h e m e s 2 3 基本概念 我们将。o 的2 2 节和”的2l 节讨论的细分概念做一总结，细分曲面( s u b d i v i s i o n s u r f a c e s ) ，也称子分曲面或剖分曲面。利用。组拓扑规则( t o p o l o g i cr u l e s ) 和几何规则 ( g e o m e t r i cr u l e s ) 对初始多边形网格进行细分，生成业细密的新网格。假设初始输入的 控制网格为m 。，对其作用一次一缰拓扑规则和几何规则。其中，几何规则用来计算新 列格顶点的位置，拓扑规则用柬确定新网格的顶点插入方式及连接关系。从而构成新的 控制网格m ，将这个新的网格m 作为下一