（计算数学专业论文）细分曲线参数化与累加弦长参数化的数值比较.pdf

大连理工大学硕士学位论文 摘要 曲线曲面造型( c u r v e s u r f a c em o d e l i n g ) 是计算机辅助几何设计( c a g d ) 和计算机图 形学( c g ) 的一项重要内容，主要研究在计算机图像系统的环境下对曲线曲面的表示、设 计、显示和分析。曲线曲面造型中的一项重要技术就是细分造型方法，所谓细分方法是 指对初始多边形或网格依据一定的规则通过不断细化产生光滑极限曲线或者曲面。细分 方法是人们在寻求用样条方法解决任意拓扑造型问题过程中提出的一种新的造型方法， 它最大的优点是能够很好的控制任意给定的拓扑结构，同时又不失高效性。因此细分曲 线曲面造型技术已成为一种强大的、应用比较广泛的曲线曲面造型工具。 曲线曲面的参数化在散乱数据拟合、纹理映射、样条曲面逼近、计算机动画、多分 辨分析等方面起着重要的作用，已成为c a g d 中广为关注的课题。不同的参数化方法将导 致不同的逼近结果。 本文对文献i t 中的细分曲线参数化方法进行了深入研究。细分曲线参数化方法首 先要确定一个初始控制多边形 只o k ，然后选用某二种细分方法来进行k 次细分，得到 逼近曲线段c 的细分极限曲线，然后在此细分极限曲线上搜索距离被参数化的点最近的 点，细分极限曲线上该点的参数就是所求的参数值。 为了更深入地理解该方法，本文先是对细分方法的产生背景、发展概况、优点及其 应用做了综合评述，并扼要介绍了目前常用的几种经典的细分方法及其细分规则。接着 介绍了曲线曲面的参数化表示，重点介绍了曲线的参数化、常用的曲线参数化方法以及 二阶参数连续( c 2 ) 的参数三次样条曲线。最后本文选取了六例典型的平面和空间曲线把 细分曲线参数化跟一直被认为是最佳参数化方法的累加弦长参数化做了全面的数值比 较。 比较 关键词：细分方法；细分曲线参数化；累加弦长参数化；参数三次样条曲线；数值 细分曲线参数化与累加弦长参数化的数值比较 n u m e r i c a lc o m p a r i s o nb e t w e e ns u b d i v i s i o nc u r v ep a r a m e t r i z a t i o na n d c h o r d a lp a r a m e t r i z a t i o n a b s t r a c t c u r v ea n ds u r f a c em o d e l i n gi so n eo ft h ei m p o r t a n tp a r t si nb o t hc o m p u t e ra i d e d g e o m e t r i cd e s i g na n dc o m p u t e rg r a p h i c s ，i tm a i l ys t u d i e so nt h er e p r e s e n t i n g ，d e s i g n i n g ， s h o w i n ga n da n a l y z i n go fc u r v e s u r f a c ei nac o m p u t e r 佃均g i i l gs y s t e m a so n eo ft h e i m p o r t a n tt e c h n o l o g i e si nc u r v e s u r f a c em o d e l i n g , s u b d i v i s i o ns c h e m ei sr e f e r st ot h ei n i t i a l p o l y g o no rm e s h e sb a s e so nc e r t a i nr u l eb e c o m et h es m o o t hl i m i tc u r v eo rt h es u r f a c et h r o u g h t h eu n c e a s i n gr e f i n e m e n t i ti so n en e wm o d e l l i n gs c h e m ew h i c hp r o p o s e db yt h ep e o p l ew h o s e e k ss p l i n em e t h o & t os o l v e r a n d o mt o p o l o g i c a lm o d e l l i n gq u e s t i o n , t h eb i g g e s tm e r i to f s u b d i v i s i o ns c h e m ei st h a ti tc a nc o n t r o la d m i r a b l yt h et o p o l o g yw h i c ha s s i g n e dw i l l f u l l y ，a n d a tt h es a m et i m ei th a sh i g he f f e c t i v e s ot h es u b d i v i s i o nm o d e l i n gt e c h n o l o g yh a sb e c o m ea c u r v es u r f a c em o d e l i n gt o o lw h i c hi ss t r o n ga n d w i d c l yu s e d m c u r v ea n ds u r f a c e sp a r a m e t r i z a t i o np l a y sai m p o r t a n tr o l ei ns c a t t e r e dd a t af i t t i n g ， t e x t u r e m a p p i n g ，s p l i n e s u r f a c e a p p r o x i m a t i o n , c o m p u t e ra n i m a t i o n , a n d s oo n m u l t i - r e s o l u t i o na n a l y s i s ，i th a sb e c o m et h et o p i cw h i c hi nc a g d p a y sa t t e n t i o nw i d e l y t h e d i f f e r e mp a r a m e t r i z a t i o nm e t h o dw i l lc a u s et oa p p r o a c ht h ed i f f e r e n tr e s u l t t i l i st h e s i sh a sc o n d u c t e dd e e pr e s e a r c ht ot h es u b d i v i s i o nc u r v ep a r a m e t r i z a t i o ns c h e m e o ft h el i t e r a t u r e i ，n l es u b d i v i s i o nc u r v ep a r a m e t r i z a t i o ns c h e m ef i r s tn e e d st od e t e r m i n e t h a tai n i t i a lc o n t r o lp o l y g o n p , o 7 - o ，t h e ns e l e c t ss o m es u b d i v i s i o ns c h e m et o c a r r yo nk t i m e ss u b d i v i s i o n , a n do b t a i n st h es u b d i v i s i o nl i m i t i n gc u r v ew h i c ha p p r o x i m a t i n gc u r v ea r c s e g m e n tc t h e ns e a r c h e s 也en e a r e s tv e r t e xw h i c hi sa w a yf r o mp a r a m e t e r e dv e r t e xo nt h i s s u b d i v i s i o nl i m i t i n gc u r v e ，t h i sp a r a m e t e ro ft h en e a r e s tv e r t e xo nt h es u b d i v i s i o nl i m i t i n g c u r v ei st h er e q u i r e dp a r a m e t e rv a l u e t ou n d e r s t a n ds u b d i v i s i o nc u r v ep a r a m e t r i z a t i o ns c h e m et h o r o u g h l y ，t h i st h e s i s c o m p l e t e l ya p p r a i s e st h ep r o d u c t i o nb a c k g r o u n d , t h ed e v e l o p m e n ts u r v e y ，t h em e r i ta n dt h e a p p l i c a t i o no ft h i ss c h e m ea tf i r s t , a n ds u c c i n c t l yi n t r o d u c e ss e v e r a lc l a s s i c a ls u b d i v i s i o n s c h e m e si nc o m m o nu s e t h e n i n t r o d u c e st h et h er e p r e s e n t i n go fc u r v ea n ds u r f a c e s p a r a m e t r i z a t i o n , a n di n t r o d u c e st h ec u r v ep a r a m e t r i z a t i o n , t h ec , o m m o l l l yu s e de l r y e p a r a m e t r i z a t i o nm e t h o da sw e l la st h es e c o n d - o r d e rp a r a m e t e rc o n t i n u o u s l y ( c z ) p a r a m e t e r t h r e es p l i n ec u r v e s 、析n le m p h a s i s f i n a l l yt h i st h e s i ss e l e c t e ss i xe x a m p l e so f p l a n ea n ds p a c e c u r v e st om a k eac o m p r e h e n s i v en u m e r i c a lc o m p a r i s o nb e t w e e nt h es u b d i v i s i o nc b i v e p a r a m e l r i z a t i o na n dt h ec h o r d a lp a r a m e t r i z a t i o nw h i c hh a sb e e nc o n s i d e r e dt h eb e s t - i i - 大连理工大学硕士学位论文 p a r a m e t r i z a t i o nm e t h o d k e yw o r d s ：s u b d i v i s i o ns c h e m e ；s u b d i v i s i o nc u r v ep a r a m e t r i z a t i o n ；c h o r d a l p a r a m e t r i z a t i o n ；p a r a m e t r i cc u b i cs p l i n ec u r v e s ；n u m e r i c a lc o m p a r i s o n i i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：鱼边! 盏童垫! 垦查鲨垒：逢益垒壑丝立塑丝丝塑： 作者签名：雌q 一慨粤年上月丛日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 壶丞望堕歪亟! 兰苎显塑尘盐墨塑! 兰兰整匝丝丛 作者签名 导师签名 日期：迦2 年z - 月竺日 e l 期：竺聋年二l 月j 立e t 大连理工大学硕士学位论文 1 绪论 本章将首先简要介绍细分方法的产生背景、发展概况、细分方法与其它方法相比的 优势以及细分方法的主要应用，然后再扼要介绍一下曲线与曲面的参数表示和采用参数 表示与其它形式相比的优点，最后给出了本文的主要研究内容和内容组织。 1 1 细分方法产生的背景 在计算机辅助几何设计( c a g d ) 和计算机图形学( c g ) 中，曲线曲面造型 ( c u r v e s u r f a c em o d e l i n g ) 是其中的的一项重要内容，主要研究在计算机图象系统的 环境下对曲线曲面的表示、设计、显示和分析。它起源于飞机、船舶的外形放样工艺， 由c o o n s 、b 6 z i e r 等大师于六十年代奠定理论基础。经四十多年发展，现在它已经形成 了以。b 6 z i e r 和b 样条方法为代表的参数化特征设计和隐式代数曲面表示这两类方法为 主体，以插值( i n t e r p o l a t i o n ) 、拟合f l i t t i n g ) 、逼近( a p p r o x i m a t i o n ) 这三种手段为骨架 的几何理论体系。曲面造型技术研究的领域包括曲面表示、曲面求交、曲面拼接、曲 面重建、曲面简化、曲面转化、曲面位差等等【2 】。 曲线曲面造型在6 0 年代初期就已经诞生，是一个有着较长历史的领域。1 9 6 3 年美 国波音飞机公司的f e r g u s o n 首先提出将曲线曲面表示为参数的矢函数方法，并引入参 数三次曲线，在此之前曲线曲面都是采用普通的函数表示形式或它们的隐式方程的表示 形式。1 9 6 4 年美国麻省理工学院的c o o n s 发表一种具有一般性的曲面描述方法，给定围 成封闭曲线的四条边界就可定义一块曲面。但这种方法存在形状控制与连接问题。同年， s c h o e n b e r g 提出的样条函数提供了解决连接问题的一种技术f 3 1 。用于形状描述的样条方 法是它的参数形式，即参数样条曲线曲面。 1 9 7 1 年法国雷诺( r e n a u l t ) 汽车公司的b g z i e r 提出一种由控制多边形设计曲线的 新方法，设计人员可以通过移动控制顶点达到控制曲线形状的目的，并可以预测曲线的 变化趋势。这种方法不仅简单易用，而且很好地解决了整体形状控制问题，把曲线曲面 的设计向前推进了一大步，为曲面造型的进一步发展奠定了坚实的基础。但b e z i e r 方 法仍存在连接问题和局部修改问题。到1 9 7 2 年，d e - b o o r 和c o x 分别独立给出了关于b 样条的一套标准算法：d e - b 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 提出了b 样条曲线曲面并发展了b 样条曲线曲面的理论和算法。这种方法继承了b 6 z i e r 方法的 一切优点，克服了b 6 z i e r 方法存在的缺点，较成功地解决了局部控制问题，又在参数 连续性基础上解决了连接问题，从而使自由型曲线曲面形状的描述问题得到较好解决。 但是上述各种方法用于圆锥截线和球面椭球面等初等解析曲面表示时仅是近似的 细分曲线参数化与累加弦长参数化的数值比较 不能适应大多数机械产品设计的要求。为此在1 9 7 5 年v e r s p d l l e 提出了有理b 样条方法。 后来由于p i e g l 和t i l l e r 等人的功绩，终于在8 0 年代后期发展起来非均匀有理b 样条 ( n o n - u n i f o - i t i ir a t i o n a lb s p l i n e s ，以下简称n u r b s ) 的一整套方法，把有理和非有理b 6 五e r 曲线和b 样条曲线曲面及圆锥曲线和初等解析曲面统一在一种表示之中。因此，国 际标准化组织( i s o ) 于1 9 9 1 年颁布了关于工业产品数据交换的s t e p 国际标准，将n u r b s 方法作为定义工业产品几何形状的唯一数学描述方法，从而使n u r b s 方法成为几何造型 技术发展趋势中最重要的基础。 尽管n u r b s 方法在造型方面有许多优势，但也存在一定的缺陷。其优点、缺点如下： n u r b s 方法的主要优点是h ： 1 ) 可以精确地表示二次规则曲线曲面，从而能用统一的数学形式表示规则曲面与自 由曲面，而其它非有理方法无法做到这一点； 2 ) 有可影响曲线曲面形状的权因子，使形状更宜于控制和实现，n u r b s 方法是非有 理b 样条方法在四维空间的直接推广，多数非有理b 样条曲线曲面的性质及其相应算法 也适用于n u r b s 曲线曲面，便于继承和发展。 n u r b s 方法的主要缺点是： 1 ) 采用参数曲面表达复杂物体表面时，需要对参数曲面片进行裁剪、缝合等处理， 手续繁琐复杂且容易产生误差。单一的n u r b s 曲面与其他参数曲面一样，不能表示任意 拓扑结构的曲面。 2 ) 另外3 d 表面上的数据往往以任意拓扑网格形式出现，用参数曲面对这些数据存 储、修改、传输以至加工都有一定局限性。为了表达特征动画中更复杂的形状，如人的 头、手或服饰，用常用的复杂光滑曲面的造型方法，例如对n u r b s 的修剪来解决往往会 遇到：有数值误差、修剪昂贵、并且由于模型是活动的，要在曲面的接缝处保持光滑， 即使是近似的光滑也是有一定难度。 正是n u r b s 曲面在表示复杂拓扑物体方面存在困难，无法满足这一要求，而细分方 法却能够很好地产生拓扑结构复杂的曲面，因此，成为近年来曲线曲面造型技术研究的 一个热点。 细分方法就是根据给定初始多边形( 网格) ，计算一个细化的多边形( 网格) 序列，此 序列收敛到一张极限曲线( 曲面) 。通过插入新点，并按一定的规则与已有的多边形( 网 格) 点相连，得到一个新的细化多边形( 网格) 。新点的位置由上一层多边形( 网格) 点按 一定的几何规则计算得到。细分曲面( 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 e s ) 大连理工大学硕士学位论文 存在的困难。因为，在不规则拓扑处只须采用特殊的细分规则就可以了，不存在拼接的 问题。 与传统的方法相比，细分方法有着明显优势： 由于细分过程中新点的计算是线性的，因而计算效率高。新点的计算只涉及少数的 老点，与样条造型相似，但比隐式、变分方法效率高得多。而且它符合计算机从离散到 离散的造型特点，可以大幅提高曲线曲面的计算机计算、生成显示的速度。 细分方法是人们在寻求用样条方法解决任意拓扑造型问题过程中提出的一种新造 型方法，它可以很好的控制任意给定的拓扑结构，同时又不失高效性。 利用以往的造型方法要么计算量庞大( 如样条方法) ，要么难以控制( 如隐式曲面) ， 而通过改变细分规则的系数即可达到特殊效果。并且可以控制边界曲线的变化。 细分方法作为曲线曲面造型的重要方法得到图形学界的一致公认始于1 9 9 9 年，当 年a c ms i g g r a p h 的成就奖授予t o n yd e r o s e 的一个重要原因是为表彰他把细分方法 创造性地应用于解决图形学中的实际问题所做的贡献。 1 2 细分方法的起源和发展 细分方法可以追溯到5 0 年代g r h a r n 的通过对折线角点进行切害l j ( c o m e rc u t ) 来生成 光滑曲线的思想。当时d er h a m 就已经使用对多边形割角( c o m e rc u t ) 的方式来描述一条 光滑的曲线1 5 j ，但这并没有引起人们的注意。在1 9 7 4 年美国u t a h 大学举行的c a g d 国际会议上，图形艺术家c h a i k i n 提出的一种与众不同的曲线的快速生成方法【6 j 。它以 直观的几何构造为基础，由一个闭合的2 d 多边形开始，通过重复的割角操作，来得到 一条光滑的极限曲线。事实上这种快速生成曲线的细分方法正是这种角切割思想的具体 实现。1 9 7 8 年，c a t m u u 和c l a r k 提出了著名的c a t m u l c l a r k 细分模式，标志着细分方法 正式成为曲面建模的手段。与此同时，d o o 和s a b i n 采用离散f u o r i e r 变换的方法，对 c a t m u l l c l a r k 模式的收敛性进行了分析，从此细分模式收敛性分析有了矩阵特征分析和 离散f u o r i e r 变换这样理论分析很好的工具。 8 0 年代末到9 0 年代初的工作主要是对已有方法的改进和新方法的提出。1 9 8 7 年 l o o p 在其硕士论文中提出的一种基于三角网格的逼近细分方法，该方法是在箱样条的 基础上提出的。d n y 等人提出了四点插值细分模式，并在此基础上给出基于三角形网格 的插值细分方法，生成所谓蝶形( b u t t e r f l y ) 曲面。 9 0 年代中期到现在已有的细分方法得到进一步的改进、完善。z o r i n 提出改进的蝶 形细分算法，解决了原方法不能适用于任意曲面的问题，同时k o b b e l t 提出基于四点方 法的张量积曲面插值细分模式。p e t e r s 和r i e f , h a b i b 和w a r r e n 分别给出细分算法，将 细分曲线参数化与累加弦长参数化的数值比较 二次四向箱样条推广到任意四边形网格上。1 9 9 8 年q i n 7 1 等人将动态模型应用到 c a t m u l l c l a r k 曲面上，后来又应用到b u r e f l y 曲面上。k o b b e l t 提出新的基于三角形网格 的细分方法，称之为细分方法。h a s s a n 提出一种三重插值细分方法使细分生成的极限曲 线能够达到c 2 阶光滑度，而在此之前的细分方法一般是二重的，并且插值细分方法一 般很难达到较高阶的光滑度。在这个时期还开始建立了细分模式的系统的连续性分析理 论，提出了任意拓扑情形下收敛性分析的理论框架。这些理论又反过来指导了细分模式 的构造。此外，各种细分模式的内在联系也逐渐被揭示出来，例如z o r i n 和s o h r s d e r 为 基本四边形网格细分模式和对偶四边形网格细分模式建立了统一的框架。更为重要的 是，在这一时期，细分方法得到了广泛应用。同时细分方法与多分辨分析小波变换之间 的本质联系也被揭示出来并得到进一步拓展，出现了细分小波。这时细分也由曲线、曲 面细分过渡到了三维立体细分。 按照细分极限曲面( 曲线) 与控制网格的关系，细分可以分为插值型和逼近型两种。 以b 样条细分为代表的逼近型细分是“砍角 型的，常常具有收缩现象，而以d y n 的 四点插值细分为代表的插值型细分则是“堆积 型的。细分曲线一般趋于扩张，为改善 这种状况，张丽梅博士综合“砍角与“堆积方法的优点，构造了一种四点逼近的细 分模式隅】，其思想来源于美术中的素描。为了达到更高的光滑度，文献【9 】在抛开系数的 对称性的条件下得到了改进的四点逼近细分模式，该方法产生c 3 阶光滑曲线。以上两 种方法属于对偶型细分，在推广到曲面细分时要求每个顶点的度( v a l e n c e ) 均为4 。为弥 补这一不足，文献 1 0 】构造了一种基本型的四点逼近细分方法，该方法在松弛参数取特 定值时为三次b 样条细分模式。为了加快控制多边形的收敛速度，有些学者提出了三重 的细分格式，文献【1 1 】提出了一种逼近型的四点三重的细分格式，极限曲线可达到c 1 光滑。较之与已有的细分方法，这四种四点逼近细分产生的极限曲线能够更加贴近初始控 制多边形。 伴随着细分方法不断被提出，为适应不同的目的各种修改的细分模式也不断涌现。 如d y n 等人提出的保凸插值细分【1 2 】，能满足局部插值约束的逼近型细分方法f 1 3 】和组合 细分【1 4 】，以及n u r s s 细分【1 5 】和动态细分阴等。为产生特殊的细分效果，尖锐特征的生 成也受到了广泛的关注，即在细分曲面上生成折痕( c r e a s e ) 、角点( c o m e r ) 和尖刺( d a r t ) 等不光滑的特征。 1 3 细分方法的主要应用 细分方法在很多领域都有重要应用。其中一个重要方面就是多分辨率分析，例如曲 面网格的多分辨率分析、医学数据的多分辨分析等，此外在计算机动画、科学计算可视 大连理工大学硕士学位论文 化、数值计算以及医学图象处理中都有应用1 1 6 1 。 首先，在计算机图形学、几何造型及逆向工程等应用领域，往往采用大规模甚至超 大规模的多边形网格来表示复杂对象的表面形状。从数据的获取、处理到传输都面临巨 大的挑战，多分辨率模型( m u l i t r c s o l u t i o nm o d e l i n g ) 正是为了解决这样的问题而提出的。 其次，细分曲面造型方法在生动逼真的特征动画和雕塑曲面的设计加工中如鱼得水，得 到了高度的运用。1 9 9 9 年a c ms i g g r a p h 的成就奖授予t o n yd e r o s e ，原因之一是为 表彰他把细分方法创造性地应用于解决图形学中的实际问题所做的贡献。再次，细分方 法在医学图象处理中应用主要是用于医学图象重构，直接得到等值面的具有细分连通性 的三角网格。这方面比较典型的工作是q i n ，m a n d a l 和v c m u i r 等人的基于细分曲面动 态造型方法，他们通过建立作用于新顶点的力学模型来确定新顶点的位置。 1 3 1多分辨率分析 在计算机图形学、几何造型及逆向工程等应用领域，往往采用大规模甚至超大规模 的多边形网格来表示复杂对象的表面形状。从数据的获取、处理到传输都面临巨大的挑 战。多分辨率模型( m u l t i r e s o l u t i o nm o d e l i n g ) 正是为了解决这样的问题而提出的。所 谓多分辨率模型是一种曲面表示方法，这种表示可以支持物体表面从粗糙到细致的各个 层次的重构。按照这一定义，层次细节模型、累进网格表示都属于多分辨模型。层次细 节模型需要保存多个版本的数据，占用比原始数据大得多的存储空间，而且在不同细节 模型间转换时会出现跳跃现象。为此h o p p e 提出累进网格模型( p r o g r e s s i v em e s h e s ) 把 任意拓扑网格表示为一种高效、无损且具有连续分辨率的编码。该编码由一个粗糙的基 网格和一系列细化变换组成。累进网格模型支持基于几何变形( g e o m o r p h ) 的平滑视觉过 渡、累进传输、网格压缩和适应性细化。接着h o p p e 又提出了依赖于视点的累进网格模 型，使得重构过程可以根据视点位置只对视锥内的部分进行细化，对于视锥外的部分则 保持粗网格。后来，p o p o v i c 和h o p p e 利用更一般的细化技术构造累进网格，从而可以 处理任意的三角剖分模型( 如任意维数、无向、非流形、非正则模型) ，而且基网格总 是一个顶点，他们把这称之为累进单纯复形( p r o g r e s s i v es i m p l i c i a lc o m p l e x e s ) 。 k h o d a k o v s k y 等人则把累进网格的思想应用到网格几何压缩( g e o m e t r yc o m p r e s s i o n ) 。 上面的表示大型网格数据的方法都是基于点、边或三角形面删除的三角网格简化算 法，难于事先估计误差界，表示也不够紧凑，而且不能支持多尺度编辑，因此人们转向 研究基于小波的多分辨率分析和细分曲面的表示方法。细分模式与多分辨率分析、小波 分析有着紧密的联系，这也是细分曲面备受关注的重要原因之一。 细分曲线参数化与累加弦长参数化的数值比较 1 3 2 动画中的应用 d e r o s e 1 7 】等人把细分曲面应用于动画人物造型获得了极大的成功。用n u r b s 等参 数曲面表示人物时需要由多片曲面拼成，因此需要求解复杂的相容关系，当人物运动时 原来的相容条件被破坏，需要重新求解相容条件或者采用大量的手工操作以消除片之间 的缝隙。另外，为了拼接方便还经常需要对曲面片进行剪裁( t r i m m i n g ) ，剪裁操作代价 相当高而且易导致数值误差。而对细分曲面来说，不存在这样的问题。由于细分曲面定 义在任意拓扑网格上，不需要剪裁，曲面的光滑性也由细分模式的极限性质自动保证。 不过，虽然细分曲面表示克服了曲面拼接的相容性问题，但由于没有适当的参数化，基 于物理方法的运动模型建立、碰撞检测、纹理映射等问题都需要重新考虑。 1 3 3 医学图像重构 细分方法在医学图象处理中应用主要是用于医学图象重构，直接得到等值面的具有 细分连通性的三角网格。这方面比较典型的工作是q i n ，m a n d a l 和v e m u r i 等人的基于 细分曲面动态造型方法。他们通过建立作用于新顶点的力学模型来确定新顶点的位置。 1 4 曲线与曲面的参数表示 在1 9 6 3 年，美国波音( b o e i n g ) 飞机公司的弗格森( f e r g u s o n ) 首先提出了将曲线曲面 表示为参数的矢函数方法。他最早引入参数三次曲线，构造了组合曲线和由四角点的位 置矢量及两个方向的切矢定义的弗格森双三次曲面片。在这之前，曲线的描述一直是采 用显式的标量函数y - - t ( x ) 或隐方程f ( x ，y ) = o 的形式，曲面的描述相应采用z - - - f ( x ，y ) 或 f ( x ，y ，z ) = o 的形式。弗格森所采用的曲线曲面的参数形式从此成为形状数学描述的标准形 式。 所以曲线和曲面均有参数表示和非参数表示之分，在非参数表示中又分为显示表示 和隐式表示。不同的表示方法在实际工程中都有其相应的应用领域。 1 显式表示 显式的非参数方程一般式是：y - - f ( x ) 或z = 暇x ，y ) 。每一个x 或( x ，”值只对应一个y 或z 值，所以用显式方程不能表示封闭或多值曲线，例如不能用显式方程表示一个圆。 在实际应用中，加工设备最终处理的仍是显示表示下的曲线离散坐标，因此无论是用隐 式方法还是参数方法最终仍然要转化nx , - - 9 咒的形式。 2 隐式表示 用隐式的非参数方程不受上述限制，其一般形式为：f ( x ，y 户0 或f ( x ，y ，z ) = o 。它描述 了变量之间的关系。例如，函数坟冯y ) 一x 2 + y 2 4 - - o 表示半径为2 的一个圆。 大连理工大学硕士学位论文 但是所有的非参数方程( 无论显式还是隐式) 都是： ( 1 ) 与坐标轴相关的； ( 2 ) 会出现斜率为无穷大的情况； ( 3 ) 对于非平面曲线、曲面难以用常系数的非参数化函数表示； ( 4 ) 不便于计算和编程。 为了解决这些问题，可考虑用参数方程表示曲线和曲面。 3 参数表示 曲线与曲面的参数表示，就是指曲线或曲面上任一点的坐标均表示成给定参数的函 数。假定用t 表示参数，平面曲线上任一点p 可表示为：p ( t ) = x ( t ) ，y ( t ) 】； 空间曲线上任一三维点p 可表示为：p ( t ) = 【x ( t ) ，y ( t ) ，z ( t ) 】。 曲面的参数化是曲线的推广，设u v 表示参数，则一张定义在矩形域上的参数曲面 可类似表示为：p ( u ，v ) = 【x 沁v ) ，y 沁v ) ，z 沁v ) 】。 相应地，在c a g d 里，曲面大都采用基表示的一种特殊矢函数形式： p ( u ，v ) = a ，妒。( u ) 9 _ ，( v ) i f f i 0 i f 0 其中，妒。( u ) ( i = 0 ，1 ，2 , - - , m ) 为以参数u 为变量的一组基函数，9 ，( v ) 0 = 0 ，1 ，2 ，n ) 为 以参数v 为变量的一组基函数，两者都是用于定义曲线的。各取其一组成的乘积，就得 到用于定义曲面的以参数u 与v 为双变量的一组基函数，( u ) 9 ，( v ) ( i = 0 ，1 ，2 ，l i l ； j = o ，1 ，2 ，n ) ，a 玎为系数矢量。 参数曲线曲面中的参数可由数据点的位置关系获得，所以通常情况下，参数往往具 有某种几何意义。例如x o y 平面上第一象限里的圆心位于原点的四分之一单位圆： c = c o s ( 0 ) ，s i n ( 0 ) ，0 0 万2 其中0 就具有明确的几何意义，它表示从圆心到圆上一点的半径矢量对于x 轴正向 的夹角。当然参数也可能没有意义，如参数二次多项式c = a 。+ a 2 + a 2 u 2 中的参数就没 有任何几何意义。这样的参数被称为一般参数。 1 5曲线曲面参数表示的优点 与非参数表示相比，曲线曲面采用基表示的特殊参数矢函数形式就具有如下一系列 优点【1 8 1 ，因而能较好地满足形状数学描述的要求： 1 总是能够选取那些具有几何不变性的曲线曲面基表示形式，且能通过某种变换 处理使那些不具有几何不变性的形式变换成具有几何不变性的形式，从而满足几何不变 细分曲线参数化与累加弦长参数化的数值比较 性要求。 2 易于规定曲线曲面的范围。 3 易于表示空间曲线。 4 仿射变换( 一个一般的仿射变换由一个比例、旋转或剪切等线性变换加上一个平 移变换) 和投影变换容易执行。 5 易于计算曲线、曲面上的点及其他信息。采用隐方程表示时，计算曲线或曲面 上一点需要求解一个非线性方程组，远不及采用参数方程方便。此外，求导、等距计算 等也能较容易地进行。 6 易于处理多值问题。 7 易于处理无穷大斜率。 8 便于曲线、曲面的分段、分片描述。 1 6 本文的主要工作 本文主要对文献 1 】中的细分曲线参数化方法进行深入研究。为了更深入地理解该方 法，本文首先要将细分方法的产生背景、发展概况、优点及其应用进行综合评述，并扼 要介绍目前常用的几种经典的细分方法及其细分规则。然后再重点介绍一下曲线的参数 化、常用的曲线参数化方法以及二阶参数连续( c 2 ) 的参数三次样条曲线。最后，为适应 在实践中的不同应用，本文安排了有针对性的实验方案，并选取了六例典型的平面和空 间曲线，把细分曲线参数化跟一直被认为是最佳参数化方法的累加弦长参数化进行全面 的数值比较。 1 7 论文的组织结构 本文深入研究了文献 1 中的细分曲线参数化方法，一共包含四章内容。 第一章，首先回顾了细分方法的产生背景、发展概况、优点及其应用，并简要介绍 了曲线曲面的参数化表示及使用参数表示的优点，最后介绍了本文的主要内容及论文的 组织结构。 第二章，介绍了目前常用的几种经典的细分方法及其细分规则。 第三章，重点介绍了曲线的参数化、常用的曲线参数化方法以及二阶参数连续( c 2 ) 的参数三次样条曲线。 第四章，安排了有针对性的实验方案，并选取了六例典型的平面和空间曲线，把细 分曲线参数化跟一直被认为是最佳参数化方法的累加弦长参数化进行全面的数值比较。 最后，全文总结。 大连理工大学硕士学位论文 2 细分方法综述 本章主要介绍了细分方法的分类、特点，并给出其常见的术语，然后扼要介绍几种 典型的细分方法，包括c h a i k i n 算法、c a t m u l l c l a r k 细分方法、d o o s a b i n 细分方法、 l o o p 细分方法、四点插值细分方法、改进的b u t t e r f l y 细分方法、3 细分方法以及四点 逼近细分方法。 2 1 细分方法的分类 在细分曲面的发展历史中，出现了各种不同的细分方法，它们都有各自的应用范围。 在本章节中，将从不同的角度对已有的细分方法进行概括分类l l w 。 细分规则通常由两部分组成：一是拓扑分裂规则( t o p o l o g i c a ls p l i t r u l e ) ，用于描述网 格细分一次后的所有顶点之间的连接关系；另一个是几何规贝1 ( g e o m e t d cr u l e ) ，用于计 算细分后产生的新点的几何位置信息。 可以把细分方法如下进行分类： ( 1 ) 根据网格类型分类。已有的细分方法多是由应用于规则网格上的传统样条方法 推广而来，如b 样条和箱样条。b 样条用于由四边形组成的网格，箱样条用于由三角形 组成的网格。因此，细分方法还可根据其拓扑规则分为基于四边形网格和三角形网格的 细分。还有一种网格是由六边形组成的，但并不常在实际中应用。 ( 2 ) 根据几何规则与细分层次的关系分类。如果几何规则在整个细分过程中保持不 变，就称之为是静态细分，否则称为非静态细分或动态细分。 ( 3 ) 根据拓扑分裂的类型分类。生成细化后网格的拓扑分裂主要有两种类型：面分 裂和点分裂，用前者方法生成细分叫基本型，后者为对偶型。对第一种情形，每个三角 形或四边形网格被分成四部分，旧顶点的拓扑位置不变，新顶点插在边上，对于四边形 还需要在每一个面上插入一个顶点。对第二种情形，对应每一个旧顶点有几个新顶点产 生，每个点对应临近旧点的网格面，在旧网格面的拓扑位置保持的同时对应每一条边产 生一个新网格面，同时对应每一个旧顶点产生一个新网格面。 ( 4 ) 根据细分极限曲面与初始控制网格的位置关系划分可分为插值细分和逼近细 分。在细分过程中，如果上一层网格的顶点总是下一层网格的顶点，因而初始网格上的 控制顶点总在细分极限曲面上，就称这种细分为插值的，否则称为逼近的。 ( 5 ) 从细分生成的极限曲面的光滑度分，又可分为c 1 、c 2 、p 等等。 从细分过程的几何变化特点划分可以分为切割磨光法和堆积法。设计师在绘图时， 总是先用折线打轮廓，然后用更密的折线逐步割去多边形的尖角，最后得到被磨光的曲 细分曲线参数化与累加弦长参数化的数值比较 线。雕塑家在创造雕像时，也往往先用油泥、石块、木头或金属的多面体打轮廓，然后 用铲子或凿子的平面逐步切割多面体的棱边或尖角，最后得到被磨光的曲面 2 1 。例如b 样条、b d 五e r 曲线就是对初始控制多边形进行切割磨光的例子，切割磨光法通常是属于 逼近类的细分。 另外一类细分方法可以形象地成为堆积法，一般属于插值型的细分，与逼近型细分 所不同的是上一层顶点总是生成的光滑衄线上的点。这种方法可以形象地看作在凸的初 始控制多边形的轮廓向外堆积新顶点并与旧顶点构成新的控制多边形，这是从初始多边 形向外逐步堆积形成保持其轮廓的光滑曲线的细化过程，四点插值法以及k o b b e l t 和 b u t t t e d l y 给出的方法都属于此类。插值细分方法通常达到的光滑度较低。 点数成二倍增长时称为二重细分，大部分细分属于此类细分，近年来出现了三重细 分，即点数成三倍增长的细分模式，如h a s s a n 细分。 表2 1 是现有细分方法的分类表。 表2 i 细分方法的分类 t a b 2 1c l a s s i f i c a t i o no fs u b d i v i s i o ns c h e m e s 静态 细分 面分裂( 基本型) 点分裂( 对偶型) 逼近型细分 插值型细分 四c a t 姒1 1 1 - c l a r k 细分( e 2 ) x o b b e l t 插僵细分 d o o - s a b i 湖分( c 1 ) 边 基本型的四点逼近细分 敲d p o i n t 细分 t e r n 醐分 四点逼近细分 形 修改的四点逼近细分 l o o p 细分( e 2 ) b u t te r f l y 细分 d y n - l e v i a - l i u 细分 角插值再细分 形 再细分 改进的b u t t e r f l y 崮1 分 非静态细分或动态细分 非静态四点插值细分，变分细分， i 瞰r s s ,动态c a t m u l l - c l a r k 细分 旋转面细分，半静态回插细分 大连理工大学硕士学位论文 2 2 细分方法的特点 细分方法与参数表示、隐函数表示等连续函数所描述的曲面在方法和数据结构上有 着本质的区别。它能更有效地处理传统方法难以解决的问题