（计算数学专业论文）非均匀控制点重构二次曲线的细分方法.pdf

大连理工大学硕士学位论文 摘要 近二十年来，随着计算机技术的普及和应用的日益广泛，细分曲线曲面造型 方法已经成为计算机辅助几何设计( a 崛d ) 和计算机图形学( c g ) 领域中的一 个国际性研究热点。 在本文中，作者首先回顾了细分发展的概况与发展历史，然后对细分的特点 与分类进行了评述。之后对已有曲线细分格式以及曲面细分格式的研究要点以及 通常涉及的理论进行了描述，并介绍了诸如d o o - s a b i n 、c a t m u l l - c l m k 、l o o p 等人 的经典细分算法。 。 本文致力于考虑的问题是，对于曲线细分，给定某一类曲线上的初始控制点 列，构造一种细分方法，使其可以重构这一类曲线。文献 2 h 给出的细分格式可 以对于均匀的初始控制点列重构原二次曲线，但对于非均匀情形则无法完成重 构。本文应用“分片”的思想，构造了一种用于局部过渡的、在初始控制点附近 重构原二次曲线的三点插值细分方法，把控制点列分段均匀化，从而在每段均匀 化以后的控制点附近可以应用 2 1 中的细分方法。结合两种细分方法，可以以较 一般情形的非均匀初始控制点列重构原二次曲线。 本文不仅证明了所构造的局部细分方法的收敛性，也证明了该方法在初始控 制点附近重构原二次曲线的性质，即从理论上证明了方法的可行性。另外从大量 的数值试验也看到了该方法的简单易行及其较好的实际效果。 另外，文献【2 3 】中提出了一种可局部控制极限曲线形状的细分格式，文中利 用细分格式渐进相等的理论证明了该细分格式的c - 0 连续性，并猜想该细分格式 是e 1 的。本文应用文献【2 4 】中变参数四点法的收敛性定理给出了一种证明。 关键词：插值细分；二次曲线；重构 非均匀控制点重构二次曲线的细分方法 as u b d i v i s i o nm e t h o dr e p r o d u c i n gc o n i c sw i t hn o n u n i o r md a t a ht h er e c e n tt w e n t yy e a r s w i t ht h ep r e v a l e n c ea n dp r o g r e s s i v e l yb r o a da p p l i c a t i o n o fc o m p o t e xl e c b n 0 1 0 9 y ，s u b d i v i s i o nm e t h o dh a sb g c o l n e 丑f o c u so fs t u d yh ic o m p u t e r a i d e dg e o m e t r i cd e s i g 丑a n dc o m p u t e rg r a p h i c si nt h ew o r l d a f t e rr e v i e w i n gt h eg e n e r a ls i t u a t i o na n dh i s t o r yo fs u b d i v i s i o n , w c 印l p | 缸t h e c h a r a c t e ra n dt h ec l a s s i f i c a t i o no fs u b d i v i s i o n t h v at h ea u t h o ri n t r o d u c e st h ei m p o r t a n t o u t l i n e so fe x i s t e n ts c h e m e so fc 犍r v ea n d 斌j c ca n dt h et h e o r yi n v o l v e di nt h cs t u d yo f s u b d i v i s i o n a tt h e8 a l n e 血e 。t h ea u t h o ri n t r o d u c e sd o o - s a b i ns c h e m e ，c a t m u l l - c l a r k s k i l l l o o pm e t h o d e t c a se x a m p l e so fs u b d i v i s i o nt e m p l e t s a st oc 1 1 r v es u b d i v i s i o n , 咖t h ei n i t i a lc o n t r o lp o i n t si nac l a s so fc l i i v 船，i t sa m 啪i n 酉u 1w o r kt o 删；m l c tas u b d i v i s i o ns c h e m et o 把p r o d u c e t h i sc a t e g o r yo fc u l v c s t h es c h e m eg i v e ni n 2 1 】c 趾r e p r o d u c ec o n i c sf l o r at h eu l o r mi n i t i a lc o n a o lp o i n t s o i lt h ec o n i c s h o w e v e r , i td o c s n tw o r kf o rt h en o n - u n i f o r mc a s c f o rt h et h o u g h to f p i c c e w i s c ”t h e o 础呱w ep r e s e n tat h r e e - p o i n ti 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 w h i c h c a n b e u s e d t or e p r o d u c e t h e c o n i c s a t t h e v i c i n i t y o f t h e i n i d a l c o n t r o l p o i n t s f o r t h e n o n - u n i f o r mc a s e a n dw ec a l lr e p r o d u c et h eg o n i c 8f r o mt h en o n - u n i f o r md a t ac o m b i n i n g t h e s et w os c h e m e s i nt h i st h e s i s 位a m h o rn o to a l yp r e s e n t st h ep r o o fo ft h ec o n v e r g e n c eo ft h ep r e s e a t e ds c h e m e 。b u ta l s ot h en a t u r eo fr e p r o d u c i n g9 a 9 1 】i c sa lt h ev i c i n i t yo ft h ei n i t i a l c o n t r o lp o i n t s a n dt h en u m e r i c a l e x p e r i m e n ta l s og i v ei j $ t b ef e a s i b i l i t yo f o u rm e t h o d b e s i d e s ，u s i n gt h et h e o r e m sa b o u tt h ec o n v e r g e n c yo fv a r i o u sp a r a m e t e rf o u r - p o i n t 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 w eg i v ea p r o o f o f t h ec o n j e c l m eo f t h e 伊c o n t i n u i t y o f t h el o c a lc o n t r o ls u b d i v i s i o ns c h e m ep r e s e n t e di nt h ep a p e r 2 3 】 k e yw o r d s ：i n t e r p o l a t i n gs u b d i v i s i o n ；c o n i c s ；r e p r o d u c e 一一 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研 究工作及取得研究成果尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含 为获得大连理工大学或者其他单位的学位或证书所使用过的材料与 我一同工作的同志对本研究所做的贡献均已在论文中做了明确的说明 并表示了谢意 作者签名醴麟半 天垤理二一7 i 学可士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版 权使用规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的 复印件和电子舨，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等 复制手段保存和汇编学位论文。 作者签名：留芗闻u作者签名：! 逢! ：= 导师签名 丑年上月三互日 一3 7 一 ，1j疗 大连理工大学硕士学位论文 l 绪论 j 1 细分方法豹起源和发展 髓着计算机技术韵发展和普及，计算机辅助设计与制造技术( c m ) ，c n w i 3 、 计算机图形学g ) 得到迅猛的发展。丽作为c k i ) c & 蝇和中的重要理论基础 之一韵计算机辅助几何设计( c a g d ) 也虢之迅速发展并显得越来越重要。作为 门独立的学科，c a g d 研究构是计算机表示以及用计算机控制有关形状信息韵伺 冠，其中项重要内容就是曲线曲面造型技术，密主要研究在计算朝周形图像系 统的环境下对抽线锄面韵表示、设计、显示和分析。 曲线抽面造型中的一项重要技术就是细分造型方法。所谓细分是指对初始网 格l ；萄居一定的觌贝4 通过不断细化产生光滑豹极限抽线或畦日面。 细分方法作为曲线曲面造型豹重要方法得到图形学界韵一致公认始 于1 9 9 9 年，当年- a c t as i o 隘t a 蹭豹成就奖授予t o n yd z x o s e 的一个重要原因 就是为了表彰他把细分方法创造性地应用于解挟图形学中的实际问题所做的贡 献。 细分方法的产生可以追溯到上世纪5 0 年代，g r h a m 通过对折钱 的角点进行切割生成光滑曲线。但这在当时并未引起人们的关 注。1 9 7 4 年c h a i k i n 提出韵生成曲线韵细分方法【l 】正是这种角切割思想的具体 实现。1 9 1 8 年c a m m l l 和c 物澍2 】，d o o 和s a b i n 3 的文章发表在同一期的c a d 杂 志上，分别提出了双三次和双二次b 样条曲面推广到任意拓扑网格上的细分算 法，这是细分方法开始成为曲面造型手段的标志。d o o 和s a b i n 采用离散f o u r i e r 变换的方法，对c a t m u l l - c l a r k 格式的收敛性进行了分析，从此细分格式收敛性分 析有了矩阵特征分析和离散f o u r i e r 变换这样很好的用于理论分析的工具。 8 0 年代末到9 0 年代初的工作主要是对已有方法的改进和新方法的提 出。1 9 87 年l o o p 在其硕士论文中提出的一种基于三角网格的逼近型细分格 式 4 】是在箱样条的基础上提出的。d y n 等人提出了四点插值型细分格式【5 】，并在 此基础上给出基于三角形网格的插值型细分方法，即蝶形( b 嘣硎y ) 细分格式 6 。 9 0 年代中期到现在已有的细分方法得到了进一步的改进、完善。z o r i n 7 提 出改进的蝶形细分算法，解决了原方法不能适用于任意曲面的问 题。同时k o b b e l t 提出基于四点插值方法的张量积插值型曲面细分格 式 8 】。p e t e r s 和础啦9 】，h a b i b 和w a r r e n 1 0 】分别给出细分算法，将二次四向箱 样条推广到任意四边形网格上。1 9 9 8 年q i n o l 】等人将动态模型应用到c a t m u l l 非均匀控制点重构二次曲线的细分方法 a 越k 格式中，后来又应用到蝶形格式中。k o b b e l t 提出新的基于三角形网格的细 分方法，称之为娟细分方法【1 2 】。h a s s a n 1 3 提出一种三重插值型细分方法使细 分生成的极艰曲线能够达到俨骱光精度，而在此之前豹细分方法一般是二重的， 并且插值型细分方法一般很难达到较高阶的光滑度。在这个对期还开始建立了细 分格式的系统构连续性分析理论，蘧出了任意拓扑情形下收敛牲分析钓理论框 架 1 4 - 1 6 ，这些理论反过来又指导了细分格式的构造。此外，各种细分格式韵 内在联系也逐渐被揭示出来，例如互妞而和s c h r 砸盯为基本四边形网格细分格式和 对猖四边形网播细分格式建立了统一的框架【l 刀。同时细分方法与多分辨分析， 小波变换之间的本质联系也被揭示出来并得到进一步拓展，出现了细分小波。同 耐细分也由曲线，瑚面细分过渡到了三维立体细分。 _ 】2 细分方法豹特点 细分方法的处理过程为：从初始的控制网格开始，按照某种规则，递归地产 生新点逐渐加密控制网格。这些新顶点都是原网格上相邻的几个顶点的加权平 均。髓着细分的不断进行，控制网格被逐渐磨光，最终生成离散点插值或逼近的 光滑的曲线或曲面。 细分方法与传统的参数表示和隐式表示等连续函数所描述的曲面在方法和数 据结构上有着本质的区别，能有效地处理传统方法难以解决的问题。这里列出文 献 1 8 】所述的细分方法的主要特点： ( 1 ) 任意拓扑：传统曲面造型方法遇到复杂物体造型时往往束手无策，因为 其控制顶点往往具有复杂的网格拓扑，这对于利用张量积方法构造的参数曲面而 言，拼接或剪裁的困难是显而易见的。但是细分方法不存在这样的闯题，一个重 要原因是它的参数空间为初始网格本身。 ( 2 ) 可伸缩性：由于细分曲面逐层递归生成，是一个不断细化的过程，其多分 辨率分析有坚实的数学基础，特别适合于层次细节技术，从而可充分利用有限的 硬件资源。 ( 3 ) 表示的一致性：这里所说的一致性是指细分法把曲面片与多面体表示统一 起来，使得造型系统有了统一处理曲面和多面体表示的手段。 ( 4 ) 数值稳定性：线性细分方法是一个迭代过程，有很好的数值稳定性。 ( 5 ) 简单性：细分方法在计算新点时仅用邻域中的几个少量的点，而且细分规 则通常比较简单，因而易于实现，计算效率也很高。 1 3 细分方法分类 在细分曲面的发展历史中，出现了多种不同的细分方法，它们都有各自的应 一2 一 大连理工大学硕士学位论文 用范围。在本章节中，将从不同的角度对已有的细分方法进行概括分类。 细分规则通常由两部分组成。一是拓扑分裂规则( t o p o l o g i c a l s p l i t r i d e ) ， 用于描述碉格细分一次后的所有顶点之伺的连接关系；另一个是，l 锕觌则 ( 窘煳嘲c 卸眙) ，用于计算细分后产生拍新点舶几何位置信息。 根据拓扑分裂类型分类。生成细化后网格的拓扑分裂主要有两种方式，一种 是面分裂( f 】a c e s l a i t ) ，另一种是煮分裂囟喇瓤s p l i t ) 。使用第一种方式的细分 方法称为基本型( p r i m a l ) ，使用第二种的称对媚型( d u a l ) 。对于第一种类型， 在细分过程中，组成网格的每一个面被分裂为四个，j 日点拓扑位置保持不变，自 每条网格边上插入一个新点，对四边形弼格，每一个翻格面中也要插入一个新 点。对于第二种类垂l 对应于每个l 丑点，有多个新点产生，每个点对应一个与这 个旧点相邻韵网格面；对应于每一条网格边，生成一个新面；旧的网格面保持不 变( 图1 1 ) 鞲一瓣辅谰 穰垃辩孵格盼瓣分囊舞竣黪一嵇暂点分麓 蒸一鬻 童期蟛一格麴埘分袋 图1 1不同的细分规则 f i 9 1 1 d i f f e m n t s u b d i v i s i o n r u l e s 根据几何规则与细分层次的关系分类。若几何规则在细分过程中保持不 变，则称为静态细分方法( s t a t i o n a r ys u b d i v i s i o n ) ；反之，称为动态细分方法 ( d y n a m i cs u b d i v i s i o n ) ，或非静态细分方法。 根据细分极限曲面与初始控制网格的位置关系分类。已有的细分方法可分 为逼近型细分方法( a p p r o x i m a t i n gs u b d i v i s i o n ) 和插值型细分方法( i n m p o l a t o r y s u b d i v i s i o n ) 。面分裂类型可以是插值的，也可以是逼近的。对于初始网格中的 任一个控制顶点，在不同的细分层次上均有一个控制点与其对应。如果这些点均 相同，则这种细分方法称为插值型的，否则称为逼近型的。对于插值型细分方 法，定义曲面的初始控制点也是极限曲面上的点，这使得我们可以更加直观的控 一3 一 非均匀控制点重构一次曲线的细分方疰 制曲面。但是这类曲面的光顺度不如逼近型细分的极限曲面，收敛速度也比逼近 型细分方法慢。 根据网格类型分类。已有的细分方法多是由应用于规则网格上的传统样条方 法推广而来，如b 样条和b o x 样条。b 样条用于由四边形组成的网格，b o x 样条 用于由三角形组成的网格。因此，细分方法还可根据其拓扑规则分为基于四边形 髑格和三角形网格的细分。还有一种网格是由六边形组成的，但在实际中并不常 用。 根据规则_ 网格情形下极限曲面的连续性分类。如g 1 连续，俨连续等。 点数成二倍增长时称为二重( b i n a r y ) 细分，大部分细分属于此类细分，近年 来出现了三重细分，即点数成三倍增长的细分模式，如h 勰s 缸细分1 1 9 。 表1 1 给出了基本细分格式的分类情况。 表1 1 基本细分格式分类 t 曲1 1c l a s s i f i c a t i o no f 血cb a s i cs u b d i v i s i o ns c h e m e s 曲线细分相应的曲面细分 说明 二次均匀b 样条曲线细分d o o s a b i n 细分( 四边形网)逼近、对偶型 三次均匀b 样条曲线细分c a u n u l l c l a r k 细分( 四边形网)逼近、基本型 l o o p 细分( 三角形网) 基于二次b o x 样条的 逼近、基本型 怕细分( 三角形网)基于b o x 样条的三倍 节点的逼近、基本型 插值怕细分( 三角形网)插值、基本型 四点插值细分改进的蝶形算法( 三角形网)插值、基本型 1 4 本文的工作 本文应用“分片”的思想，在文献 2 1 1 的基础上构造了一种以较一般情形的 非均匀初始控制点列重构原二次曲线的细分方法。 2 1 】中给出的细分格式每一个 薪点表示为上一层四个旧点的线性组合，而且要求上一层相关的控制点均匀分 布。我们构造了一种用于局部过渡的、在初始控制点附近重构原二次曲线的三点 插值型细分格式，把初始控制点列分段均匀化，结合两种细分格式，可以以较一 般情形的非均匀初始控制点列重构原二次曲线。本文不仅证明了所构造的局部细 分方法的收敛性，也证明了该方法在初始控制点附近重构原二次曲线的性质，即 从理论上证明了方法的可行性。另外从大量的数值试验也看到了该方法的简单易 行及其较好的实际效果。 一d 一 盔垄型三丕兰塑兰丝丝奎 另外本文还在文献【刎中的收敛性定理的基础之上稍加分析，给出了文 献【2 3 】中的一个猜想的证明，即证明了其中所给出的可局部控制极限曲线形状的 细分格式的 i a l l i a 2 l i a 3 f2 l k 一1 i ，由线性仿射不 变性，必有k = 1 ，则收敛到的极限位置可以直接计算： 令o , o = 0 ，用埘去除式( 2 4 ) 的两端，得： k p k = a l x l + e 薹吼c 扣 当尼一0 0 时，对应a 1 的控制点向量占主导位置，即极限点沿着向量0 1 排 列，这是曲线中心点的切向量。如果a 1 = a 2 ，则当一0 0 时，由( 2 5 ) 可知，极 限将为0 1 、n 2 的线性组合，在中心点无切向量，因此导致切向量存在的必要条件 为细分矩阵的所有特征向量除k = 1 外均应小于入1 。 2 1 4 细分格式的收敛性 有很多讨论函数列收敛的方法，可以选择不同的范数或不同的收敛性。这里 介绍的是最常用的收敛性：一致收敛性。 定义2 1 ：【1 4 我们称区间【讪 上的函数列 ( t ) ) 一致收敛到，( t ) 是指：如果对任 意的 0 ，存在勘 0 ，使得当礼 n o 时有 龇m a x 洲) 一厶( ) i 芝0 ，存在常数c o 和教缩因子1 鞴足o 1 1 使得i i _ 矿0 c 丫七，则p ) 收敛到连续函数。 定理勉中常数c 依赖于初始点列p 0 韵选取，下面将研究差分向量序 列矿之间钓细分关系。暇定考虑韵是二重的细分格式，设细分矩阵d 满足 因为矿+ 1 = s 矿，代入上式得 扩1 = 耐 s p = d z x p k 由( 2 6 ) 和( 2 7 ) 易得g 和d 所对应的生成多项式s ( z ) 和d ( z ) 有如下关系： s ( z ) = ( 1 + z ) d ( z ) ( 2 聊 ( 2 7 ) 于是可以由d 给出p ( t ) 收敛和极限函数连续的条件： 定理2 3 ：【1 4 】如果o i i 有界，存在m21 使得l l 扩l i o 和0 ，y 1 ，使得对任意的k 有 对 对 我们也可以用下面定理直接判断静态细分格式是否为c 暗连续的。 定理2 - 4 ：【1 4 1 如果s ( z ) 定义的细分格式生成连续的极限曲线，则( 半) s ( z ) 定义 的格式生成的曲线伊连续。 设s ( 名) 定义的静态细分格式生成伊连续的极限曲线，记a ( z ) 为s ) 的生 成多项式，d 为a ) 的各单项式系数从低到高排列成的向量，即细分格式s 的模 板。毗1 为相应的第i 次差分，记扩为第k 次细分矩阵为铲( z ) 的非静态细分格式 的模板，昧】为相应的第1 次差分，在螺) 垒熙礁；d ( m ) 的前提下，若有 0 0 l i d 一d ( 。) o + 。， 脚 一i l 非均匀控制点重构二次曲线的细分方法 则依据 2 6 】中的关于细分格式渐进相等( a s y m p t o t i c a l l ye q u i v a l e n t ) 的定理知，该非静 态细分格式也生成c ”连续的极限曲线。 2 1 5 四点插值细分方法 一、经典四点插值细分法 在实际的应用中，往往需要插值一些特殊的点来表现一定的效果。虽然 一般来说逼近型细分有更好的光顺性，但是插值细分却往往更具有实用价 值。1 9 8 7 年n d y n 等人提出了一种带参数的四点插值格式【5 】，该方法每个新点由 上一层的四个相邻的旧点计算得到，每一步细分都采用相同的权值。细分格式如 下： ff 势1 = 砰，一1 i 2 n + 1 ， lp , k + l = ( 百1 + u ) ( 砖+ 只1 1 ) 一u ( 簟1 + 碴2 ) ， 一1 t 2 k n ， 其几何意义如图所示 喹； 唆， 图2 2 d y n 四点插值细分格式 f i 9 2 2d y n sf o u r - p o i n ts u b d i v i s i o ns c h e m e 其中e = ( 辟- 4 - 璐，) 一；( 肇t + 硌：) ，t f ，为形状控制参数。n d y n 等在文中指 出，当1 训 时，细分格式收敛到一条连续的极限曲线，当0 i 1 时，极限 曲线还是c 1 的。 二、变参数四点法 1 9 9 5 年蔡志杰把n d y n 等的四点法推广到了变参数情形，即变参数四点插 值细分格式( 2 4 。文中对此新算法的性质进行了较为深入的分析。其细分格式如 一1 2 大连理工大学硕士学位论文 下： i d p j 。k g - 1 二荟+ 三善；耋0 ；味。+ ，一1 i 2 i 。斛。= g + u ：) ( 砰+ 璐1 ) 一u 七( - + p ) ，一1 i 2 文c 2 4 中证明了对任何l l 巫( 其中k 是与i ，蠢无关的正常数) ， 细分格式收敛到一条连续的极限曲线；如果还存在良使得0 n 讲s 口 ，则还有极限曲线是俨韵。本文下一章中对该细分格式韵收敛性定理作更深入 的分析，并由此证明文献【2 3 】中舶个猜想。 三、几何控制四点插值格式 2 0 0 4 年m 潮：面加d v n d 弛d 1 删i n 给出了一种细分格式【2 5 】，格式的表达形 式与( 2 8 ) 相同，而其中参数钟韵选取依赖于相关韵几个初始控制点的几何位置， 以此来避免凸性交化及视觉上非光 清等情况的发生。 2 1 6 生戒耩确圆周韵细分格式 旋转曲面和圆周都是几何造型中重要对象，然而生成旋转曲面最终 f 密1 - # 去障1 + ( 2 + 蚓辟+ 】， ( 2 9 ) l 端= ；( 尊+ 磺。) 其中鲰，20 ) 可以由以下递推公式得到： 瓯2 v 了一， 如果给定的初始控制多边形为正m 边形，取定a o = 伽警，则依据细分格 式( 2 9 ) 生成的极限曲线为精确圆周。图2 3 为当m = 4 时依格式得到圆周的例子。 另外还有三重( t g m a r y ) 的细分格式，是英国剑桥大学计算机实验室首先 提出的。i - - l a s s a l l 等在2 0 0 1 年给出了一种三点单变量三重细分格式【1 9 】，该格式 生成伊的光滑极限曲线，i - i a s $ a n 又于2 0 0 2 年给出了一种四点插值型三重细分格 式，该格式生成伊光滑极限曲线【1 3 】。 m o r i n 等人于2 0 0 0 年给出p o i s m n 曲线与曲面的细分格式【3 1 】。d e c a s t e l j a u 求 值法应用于有限控制点列形成b 6 z i e r 曲线，这种求值过程也产生了一种细分算 一1 3 非均匀控制点重构二次曲线的细丹万法 图2 3生成圆周的细分格式 f i 9 2 3 s u b d i v i s i o ns c h e m e l m ，d u c i n gc i r c l e o 法，细分过程产生的极限无限就是b e z i e r 曲线本身，推广d e c 纽碾j 舭求值法到无 限控制点序列就定义了一类的新的曲线。文章中的静态非均匀细分过程产生的极 限相当于以初始数据点为控制顶点、以p o i s s o n 分布为b l e n d i n g 函数的曲线。文章 也研究了从该细分格式通过张量积形式生成曲面的问题。 2 2 曲面细分简介 2 2 1 曲面细分常用术语 曲面细分是初始控制多边形网格按照一定的规则逐步细化得到新的控制多边 形网格，细化控制多边形网格的极限为光滑曲面。研究曲面细分需要掌握网格的 拓扑结构以及细分的拓扑规则和几何规则，为此先进行一些必要的准备。 多边形网格或多面体的表面是由点、边、面构成的集合。称之为单纯复 形( s i m # i c i a lc o m p l e x e s ) ，将曲面细分视为定义在二维单纯复形上的函数。 一个二维单纯复形k 是指一个包含顶点、边、三角形( 或四边形) 的集 合。使得其中任何三角形( 或四边形) 的边属于k ，任何边的顶点属于k ， 也就是没有孤立的顶点或边。复形k 的子集如果也是复形就称之为k 的予复 形( s u b c o m p l c x ) 。复形k 中顶点v 的1 一邻域( 1 - n e i g h b o r h o o d ) 是指以v 作顶点的 所有三角形( 或四边形) 构成的子复形，进而顶点v 的m 一邻域由v 的( m 1 ) 一 邻域的所有顶点的1 一邻域构成。顶点v 的邻接( l i m k ) 是指v 的l 一邻域中不 含v 的所有边的集合。通常顶点的邻接形成开或闭的简单的多边形线，如果 顶点的邻接是开的多边形线，称这个顶点是边界顶点( b o u n d a r yv e r t e x ) ，否则 是内顶点( i n t c m a lv e r t e x ) 。一条边只属于一个面，称这条边为边界边( b o u n d a r y c d g e ) ，否则称为内部边( i n t e r n a le d g e ) 。至少包含一个边界顶点的面称为边界 面( b o u n d a r y f a c e ) ，否则称为内部面( i l i t e r n a l f a c e ) 。 细分是在多边形网格序列上进行的。多边形网格( g r i d ) 是指m = o l d ) ，其 一1 4 一 u 大连理工大学硕士学位论文 中k 是单纯复形，d 是顶点到砂( 通常指r 3 ) 空间的单射。通常对k 的顶点、 边、面与m 的顶点、边、面不加以区分。顶点的价( v a l e n c e ) 是指网格中以该点为 顶点的网格边数或网格面数。通常定义在三角形( 四边形) 网格上韵内部顶点的 价为6 ( 4 ) ，边界顶点的价为4 或2 或( 3 或2 ) ，称这样的顶点为正则顼点承皇卿孤 他疵x ) ，否则删奇异项点西垃趵删m 巧嘲) 。 下面简要介绍在上述网格拓扑定义下的几种细分格式。 c a m m u 和c l a r t ：于t 9 7 8 年提出的c m m u l t - c 1 a r k 细分格式标志着曲面细分的开 始。之后d o o 和s 曲i n 利用矩砗分析的技术对q 岫删c l 破细分格式的收敛性进 行分析，标志着细分方法开始成为曲面造型的一种工具。基于四边形网格的细分 方法研究中，很多工作是在c m m m u - c l m i 格式上展开的。 c m m u - c l a r k 格式的初始控制网格为四边形网，采用四边形面分裂拓扑规则 算子生成新网格的拓扑，计算新顶点的几何规则如下： ( 1 ) 新面点( f - v 髓 t e x ) ：记该面的四个顶点为k ，k ，则相应的新面点 的位置如下确定： v = ( v o + + k + k ) 4 ( 2 1 0 ) ( 2 ) 新边点( e - v e r t e x ) ：设内部边的端点为，k j 共享此边的两个四边形 分别面分别为( k ，k ) 和( ，k ，k ) ，那么与此内部边相对应的e 一顶点 为： 卫1 v r 2 i ( + ) + 盍( k + k + k + k ) ，( 2 1 1 ) 即对应边的两个端点与共享该边的两个面的新面点的平均。 ( 3 ) 新顶点( v - v e r t e x ) ：着内部顶点y 的1 一邻域的边界顶点依次 为，m ，一l ，其中n 是y 的价，偶数下标的顶点为邻点，奇数下标的顶 点为其四边形面上的对角顶点，相应的v - - 顶点为： 2 v + 鲁善n - - l 玩+ 鲁若n - x n - 1 1 玩扎q t 动 一 c 锄l | 1 1 和a a f k 取其中的权值为风= 嘉，= 去，= 1 一风一 对于具有边界的开网格，在边界上通常使用三次b 样条曲面的节点插入系数 得到的结果，即由规则( 4 ) 和( 5 ) 所描述。 一】5 一 非均匀控制点重构- 次血线的细分方法 ( 4 ) 边界边( v 0 ，k ) 上的e 一顶点： = i ( + m ) ( 2 1 3 ) ( 5 ) 边界顶点在边界上的两个相邻顶点为k ，则v 的v 一顶点为： w = ；( k + ) + - v , ( 2 1 4 ) 式( 2 1 0 ) - ( 2 1 4 ) 中顶点的权值分别由图2 4 ( a ) - ( e ) 的m a s k s 表示。当初始网格为 正规网格时，c a t m t d l c l a r k 格式生成三次b 样条衄面。上面给出的v 一顶点的权 值中，和风可以有多种选择。j 魄p e t e r su l r i c h 础e f 证明o z 。和风满足如下 条件时极限曲面是光滑的： 2 1 4 一1 士撕面i 1 f 丙硒i 3 时反= - l 。 ( 3 ) 边界顶点的处理与c a u n u l l - c l a r k 格式相同。 图2 8 ( a ) - ( d ) 是l o o p 格式各类顶点的细分模板。 一1 8 一 k “御 风+ y 风 礼 一 q i j 大连理工大学硕士学位论文 对于正则网格，l o o p 格式生成b 0 x 样条，因此是伊连续的。同样，对开网 格，为使曲面在边界处光滑，需要修改以边界点为端点的内部边新边点细分 模板的权值。如图2 8 铆所示，其串m = i ，蚀= 或m = 三一。2 c o 一2 。r 他= ；+ ；c 0 8 ；鲁。另外，风满足 扣毒， 0 和t = i s s 0 ，其基础解系分别 为 1 ，。，2 2 ，) ， 1 ，。，“，e - s z ) 和 0 ，则细分格式( 3 1 ) 分别重构这两个双曲函数。类 似地，如果给定三角函数c d 8 缸) 和s i n 缸) 上的数据点0 u ，霹) ，j z ，若选取参 数口o = c 0 8 ( 8 u ) ，s ，u 0 ，则细分格式( 3 1 ) 分别重构这两个三角函数。 一2 l 一 非均匀控制点重构二次曲线的细舒万j 云 图3 1 是一些具体的实例，其中虚线表示初始控制多边形，实线表示极限曲线。 。一厂。，：； 图3 1重构双曲函数和三角函数：c o s h ( x ) s i n h ( x ) ，c o s ( x ) ，s i n ( x ) f i 9 3 1 u n i f o r md a t a p r o d u c i n g f u n c t i o n s ：c a s h ( x ) ，s i n h ( x ) ，c o s ( x ) ，s m ( x ) 这样，如果分别沿两个坐标轴方向重构函数a c o s h ( x ) 和b s i n h ( x ) ，或 者a c o s ( x ) 和b s i n ( x ) ，就可以分别实现双曲线和椭圆曲线的重构。而对于抛物 线的情形显然就是重构二次多项式函数。图3 2 是初始控制点均匀分布时按细分格 式( 3 1 ) 重构原二次曲线的例子。 图3 2重构二次曲线：双曲线，椭圆，抛物线 f i 9 3 2 u n i f o r md a t ar e p r o d u c i n gc o n i o $ ：h y p e r b o l a , e n i v s e ，p a r a b o l a 可以看到，对于给定的按参数均匀分布在二次曲线上的初始控制点列，细 分格式( 3 1 ) 可以很好地重构原二次曲线。但是对于初始控制点列非均匀分布的情 形，则无法得到原二次曲线。 3 2 非均匀控制点处细分格式的构造 针对上一节末的问题，即为了完成非均匀控制点情形的二次曲线细分重构， 又考虑到非均匀情形的复杂性，我们在本节中给出了一种三点二重的用于局部过 渡的细分格式，用来将非均匀的初始控制点列分段均匀化。由于这种格式不适合 应用于整条控制多边形线，即对于一般分布的并非落在一条二次曲线上的初始控 制点，不能生成光滑的极限曲线，我们称之为局部细分格式。最终结合细分格 一2 2 大连理工大学硕十学位论文 式( 3 】) 和我们构造的局部细分格式即可以由较一般的非均匀点列细分重构原二次 曲线。 我们从微分方程工) 3 一t 2 d = 0 的解出发给出细分方法的构造过程。容易 看到：当t = 0 ，t = s 0 和t = 饵s 0 时，该微分方程的基础解系分别 为 l ，霸舻) ， 1 ，e - - s x ) 和 l ，严，e 缸) 。对于后面两种情况，我们可以统一 地将插值函数记为 ，0 ) = a o + 0 1 e “+ o a e 一“ ( 3 ，2 ) 考虑第七层的插值点2 一，0 ，2 一m ，其中m 表示相邻两参数区间的长度之 比，而对应的函数值分别为尊t ，才，臻1 ，于是我们可以得到如下的方程组： 托 一刍) = 尊。， o ) = 劈， 罢) = 臻， f 只i l = a o + a l e 一壶+ 以e 舌， 才= n o + n l + o 2 ， ( 3 3 ) 【硌l = n o 十d 1 e 雾+ 啦e n 02 瓦玎晒疋可万万三：厂一 扩+ 1 ( 扩一1 ) p 是】一0 仇( a m + 1 - 4 - 1 ) 砰+ a m ( a 一1 ) 硪】 0 1 。吉j 丽矿1 而而芒面一， a ( a ”一1 ) j 唆1 一o ( m + 1 + 1 ) 钟+ a m ( a 一1 ) 臻1 0 22 韦= 丽万j 而南了旷一 然后分别在昭顶点考的两边各插入一个新顶点础2 ，+ - - 1 i = ，( 一i 2 k + 1 ) 和；p 幻2 k + + l 。= f ( m 2 k + 1 ) ，并将其表示成上一层控制点的线性组合，称之为以点劈为中心的细 分。局部细分格式可表示为： ( 3 4 ) 麓 赣 砖 砖 + + 警 学 睦 睦 + + 扎蜉略罅一 f f = | | 端秽啭 非均匀控制点重构二次曲线的细分万法 由简单计算即可得到这些系数如下 砖= 譬箐辫， 崦= 焉等鬻， a ；= 两专等墨两 ( 3 6 ) 命题3 2 ：局部细分格式( 3 4 ) 中的系数满足关系：砖+ 砖+ 罐= 1 ，曹+ 砖+ 砖= 1 ， 即满足细分格式仿射不变性的要求。 由各系数的表达式经简单计算即可验证命题3 2 的正确性。 这些系数的表达形式看起来很复杂，然而对于不同的系数t 我们可以分别给 出简单的表示。分别记 = ；( o + 口- 1 ) ，谚= ( 扩+ 旷“) ，砖= ( 扩+ 1 + 口一”- 1 ) ， 注意这里n ：e 毒，所以有 对t = s 0 ，我们有 嘭“= k 0 ，j = 1 ，2 ，3 忙丽昔1 蔫而12 、( u p l ) 2 一 ( 碚+ 1 ) 2 一 砖：堡：骘： 2 、( u + 1 ) 2 1 ，、( ”尹1 ) 2 1 6 ；：11 三驾 2 ( 谚“) 2 1 、( 落+ 1 ) 2 1 2 4 一 叼一一一一 一一一一一一一 一两两藤瓣 大连理工大学碗十学位论文 而对t = 妇，s 0 ，有 c 2 丽雨i i - - u 丽2 + 1 ， 畦：1 些1 二筚一， 2 、( 口 + 1 ) 2 1 、( “) 2 1 扣丽昔蔫丽2 、( 谚+ 1 ) 2 1 、( 落“) 2 1 。 ：，竺二窆二， 2 1 一( + 1 ) 2 1 一( 舻1 ) 2 磅：1 竺鐾亨一， 2 、l 一( 。 + 1 ) 2 1 一( 舻1 ) 2 牡矿蔫赤丽， c 2 平菰雨v 2 + 1 了- 1i 孬， 乒矿蔫昔丽， 舡矿煮等丽+ 注1 ：由谚的定义知，落可以用u 和谚来表示，因此我们只要根据初始控制多边 形各参数区间的长度来给出每个初始顶点处合适的参数口 和递a p r 。 注2 ：对于二次多项式情形，也有( 3 4 ) 的形式，此时系数容易求得，有 雾2 m + 1 东享2 m + 1 c ；蕃；，c = 志，奄= 竿，谚= 端 。“ 事实上，可以验证，( 3 7 ) 中各值正是在式( 3 5 ) ，( 3 6 ) 中令一o o 时对应的各系 数的极限值。 一2 5 非均匀控制点重构二次曲线的细分万法 对于局部细分格式( 3 4 ) ，我们有如下的收敛性定t i ： 定理3 1 ：记m 为任意相邻两参数区间长度之比，那么当m ( 丽2 ，墨乎) 时， 结合细分格式( 3 1 ) 和局部细分格式( 3 4 ) 生成的极限曲线是连续的。 证明：格式( 3 1 ) 的收敛性在【2 1 】中已给出，所以这里只需证明应用局部细分格式 处的连续性。 记僻) 2 ，k + 一l ，为按细分格式( 3 4 ) 得到的第七步的各参数值， 劈) ；誊为对应的 各函数值。令，为插值l ，1 e f kj t 2 忙k + 一l l 的分段线性函数，考虑以学为局部细分格式 中心点的细分