（计算机软件与理论专业论文）参数曲线数据点参数化方法的研究.pdf

山东大学硕士学位论文 皇曼皇i z m 1 1 罡曼皇曼曼曼曼曼曼曼皇皇曼皇曼曼曼曼曼 摘要 在计算机图形学和计算机辅助几何设计领域，参数插值曲线的应用非常广 泛。通常情况下，要求所构造的参数插值曲线必须是光顺的。为了达到这个要求， 不仅需要有好的插值方法，还要有好的确定节点参数的方法。同一组数据点，即 使采用同样的插值方法，若数据点的参数化方法不同，也会获得不同的插值曲线， 对数据点的参数化，应尽可能反映被插值( 逼近) 曲线或设计员想要用数据点所 构造的曲线的性质。 一般而言，曲线参数化都会努力使之接近于弧长参数化，这是因为弧长参数 化是比较理想的参数化方法，它可以使参数域中均匀分布的点对应于参数曲线上 均匀分布的点，对于实际应用具有重要意义，现在的参数化方法，都努力向弧长 参数化靠拢，但与真正意义上的弧长参数化还存在很大距离，而且，衡量这种距 离也需要有一个标准，所以，弧长参数化是很困难的。 迄今为止，虽然已经有多种数据点的参数化方法在实际中使用，但是如何获 得一个满意的参数化结果这个问题仍然没有得到圆满的解决。 在确定数据点的参数的方法中，比较常用的有，均匀参数化法，累加弦长参 数化法，向心参数化法，修整弦长参数化法以及z c l 参数化法。 均匀参数化方法是最简单的方法，它认为各点的参数是均匀递增的，而事实 上数据点的分布在一般情况下都不均匀，所以采用这种方法构造出的曲线效果较 差。累加弦长法是现在被广泛采用和接受的参数化方法，在该方法中，弦长被看 作是弧长的近似，通过迭代，累加弦长参数化方法就成为弧长参数化方法，但是， 只有参数曲线是直线的时候，参数曲线根据弧长插值才最合适。 近年来，基于最优化技术确定节点参数的方法得到了广泛的发展，实验表明， 这些参数化方法所构造的曲线效果较好，但是实现起来比较困难。 向心参数化方法，由美国波音公司的李( l e e ，1 9 8 9 ) 提出，它利用累加弦 长的平方根来计算节点参数，将数据点相邻弦线的折拐情况考虑在内，据他介绍， 在他所作的所有非均匀分布数据点的实验中，该方法都给出了优于前两种方法的 结果。 山东大学硕士学位论文 福利提出了修整弦长参数化方法，该方法除了考虑相邻两点间的弦长，还对 该弦的两个紧邻弦长以及该弦与这两个紧邻弦的夹角进行了考虑，获得的参数化 结果也较好。 张彩明教授提出了z c m 参数化方法，该方法是一种整体性方法，其数据点参 数化的结果具有二次精度的优点，实验表明，通常情况下利用它所构造的参数插 值曲线效果要好于向心参数化或修正弦长参数化方法。 本文提出了一种基于能量极小模型的参数化方法，该方法基于双抛物线能量 极小，通过对局部曲线进行能量极小优化约束来确定节点参数，使得构造出的样 条插值曲线比较光顺，在一些数据点分布情况下可以获得比其它参数化方法好的 结果。 本文选取部分有代表性的数据使用经典的参数化方法和能量模型参数化法 分别做了试验，根据试验结果，提出了下一步改进的方向。 关键词：参数曲线；数据点参数化；能量模型 a b s t r a c t i nt h ef i e l d so fc o m p u t e rg r a p h i c sa n dc 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 ， t h e r ea r eal o to fm e t h o d st od e f i n ea n de x p r e s sac u r v e o n eo fw h i c h ，p a r a m e t e r s p l i n e c u r v ei s w i d e l yu s e d u s u a l l yt h ep a r a m e t e r so ft h er e q u e s t s t r u c t u r e i n t e r p o l a t i o nc h iv em u s tb es m o o t h i no r d e rt om e e tt h i sr e q u i r e m e n t , n o to n l yi t n e e d sg o o di n t e r p o l a t i o nm e t h o d s ，b u ta l s on e e d sg o o dm e t h o d st od e t e r m i n e p a r a m e t e r so ft h ed a t an o d e s t h es a m es e to fd a t ap o i n t s ，e v e nu s i n gt h es a m e i n t e r p o l a t i o nm e t h o d , i fu s i n gd i f f e r e n tp a r a m e t e r sm e t h o d s ，w i l lr e c e i v ed i f f e r e n t i n t e r p o l a t i o nc u i w e s ot h ep a r a m e t e r so ft h ed a t ap o i n t ss h o u l dr e f l e c tt h en a t u r eo f t h ei n t e r p o l a t i o nc u r v ew h i c hd e s i g n e r sw a n tt ob e g e n e r a l l ys p e a k i n g ，t h ec u r v ep a r a m e t e r i z a t i o nw i l lm a k ei t c l o s e rt ot h ea r c l e n g t hp a r a m e t e r i z a t i o n ，t h i si s b e c a u s ea r cl e n g t hp a r a m e t e r i z a t i o na r ei d e a l p a r a m e t e r i z e dm e t h o d , w h i c he n a b l e sp a r a m e t e r su n i f o r m l yd i s t r i b u t e dp o i n t so nt h e c u l v e c o r r e s p o n d st o t h ep a r a m e t e r so fu n i f o r md i s t r i b u t i o n ，f o rt h ep r a c t i c a l a p p l i c a t i o no fg r e a ts i g n i f i c a n c e ，a n dn o w t h ep a r a m e t e r so fm e t h o d s ，a r em a k i n ga n e f f o r tt om o v ec l o s e rt ot h ea r cl e n g t hp a r a m e t e r i z a t i o n ，b u tt h et r u es e n s eo ft h e a r c l e n g t hp a r a m e t e r i z a t i o ni sa l s oa 嘶d eg a pb e t w e e nt h ei d e a l ，b u ta l s om e a s u r i n g t h ed i s t a n c eh a sas t a n d a r d ，t h e r e f o r e ，a r c - l e n g t hp a r a m e t e r i z a t i o ni sv e r yd i f f i c u l t s of a r , a l t h o u g ht h e r ea r es e v e r a ld a t ap o i n t so ft h ep a r a m e t r i cm e t h o d su s e di n p r a c t i c e ，h o wt oo b t a i nas a t i s f a c t o r yo u t c o m e o ft h ep a r a m e t e r so ft h i sp r o b l e mh a s s t i l ln o tb e e ns o l v e ds a t i s f a c t o r i l y a tp r e s e n t , t h e r ea r es u c hp a r a m e t e r so ft h em e t h o d s ，c o m m o n l yu s e dn o w , u n i f o r mp a r a m e t e r i z a t i o nm e t h o d , a c c u m u l a t e dc h o r dl e n g t hp a r a m e t e r i z a t i o nm e t h o d , t h ec e n t r i p e t a lp a r a m e t e r i z a t i o n ，a d a p t i n gc h o r dl e n g t hp a r a m e t e r i z a t i o nm e t h o da n d t h ez c mm e t h o d u n i f o r mp a r a m e t e r i z a t i o nm e t h o di st h es i m p l e s tm e t h o d , w h i c hc o r j s i d e r sa l lt h e p a r a m e t e r sa r eu n i f o r m l yi n c r e a s e d b u ti nf a c tt h ed i s t r i b u t i o n so fd a t ap o i n t su n d e r n o r m a lc i r c u m s t a n c e sa r eu n e v e n ，s ot h eu s eo ft h i sm e t h o do fc u r v ec o n s t r u c t e dl e s s i i i e f f e c t i v e a c c u m u l a t i v ec h o r dl e n g t hm e t h o da r en o ww i d e l yu s e da n da c c e p t e d m e t h o dp a r a m e t e r s ，i nt h i s m e t h o d , t h ec h o r dl e n g t hw a ss e e n 嬲t h ea p p r o x i m a t e l e n g t h ，t h r o u 曲t h ei t e r a t i v e ，a c c u m u l a t i v ec h o r dl e n g t hp a r a m e t e r i z a t i o nm e t h o dh a s b e c o m et h em e t h o do fa r c l e n g t hp a r a m e t e r i z a t i o n ，h o w e v e r ，o n l yp a r a m e t r i cc b r v ei s as t r a i e g a tl i n e ，t h ep a r a m e t r i cc u r v ei n t e r p o l a t i o ni na c c o r d a n c e 、i mo n l yt h em o s t s u i t a b l ea r cl e n g t h i nr e c e n ty e a r s ，t e c h n i q u eb a s e do no p t i m i z a t i o nt od e t e r m i n et h en o d e p a r a m e t e r sh a sb e e nw i d e l yd e v e l o p e d , e x p e r i m e n t ss h o wt h a tt h e s ep a r a m e t e r so ft h e m e t h o do fc u r v ec o n s t r u c t e da r eb e t t e r ，b u tm o r ed i m c u l tt oa c h i e v e c e n t r i p e t a lp a r a m e t e r i z a t i o n ，b yl e e ( l e e ，19 8 9 ) f r o mb o e i n gc o m p a n y p r o p o s e d , w h i c hu s e sa c c u m u l a t i v ec h o r dl e n g t ht oc a l c u l a t et h es q u a r er o o to f t h e n o d ep a r a m e t e r s a c c o r d i n gt oh i si n t r o d u c t i o n ，a ta l ln o n u n i f o r md i s t r i b u t i o no f e x p e r i m e n t a ld a t ap o i n t s ，t h em e t h o dg i v e sab e t t e rp a r a m e t e r i z a t i o nt h a nt h er e s u l t s o ft h ef i r s tt w om e t h o d s f o l e yd e v e l o p e da na d a p t i n gc h o r dl e n g t hp a r a m e t e r i z a t i o nm e t h o d , w h i c h c o n s i d e r sd i s t a n c ea p a r tf r o mt h ea d ja c e n tc h o r dl e n g t hb e t w e e nt w op o i n t s ，b u ta l s o t h el e n g t ho ft w oa d j a c e n tc h o r dl e n g t ho ft h ea n g l eb e t w e e nt w oa d j a c e n ta n g l e s ，t o o b t a i ng o o dp a r a m e t e r sr e s u l t s p r o f e s s o rc a i m i n gz h a n gp r o p o s e dz c mp a r a m e t e r i z a t i o nm e t h o d , t h em e t h o d i sah o l i s t i ca p p r o a c h ，t h ed a t ap o i n t st h ep a r a m e t e r so ft h er e s u l t so ft h ea c c u r a c yo f t h em e r i t so ft h es e c o n de x p e r i m e n ts h o w e dt h a tu n d e rn o r m a lc i r c u m s t a n c e st h eu s e o fi t ss t r u c t u r a lp a r a m e t e r si n t e r p o l a t i o nc u r v eb e t t e rt h a nt h ee f f e c to fp a r a m e t e r st o t h eh e a r to ra m e n d m e n tc h o r dl e n g t hp a r a m e t e r i z a t i o n t h i sa r t i c l ep r e s e n t sap a r a m e t e r i z a t i o nm e t h o db a s e do i lm i n i m a le n e r g yw i t h t h eq u a d r a t i ca c c u r a c y ；t h em e t h o du s e sl o c a lo p t i m i z a t i o no fm i n i m u me n e r g yc u r v e s b o u n dt od e t e r m i n et h en o d ep a r a m e t e r s ，s ot h es t r u c t u r eo ft h es p l i n ec u r v ei s s m o o t h i n g i ns o m ec a s e so fd i s t r i b u t i o no fd a t ap o i n t s ，t h i sm e t h o dc a ng e tm e b e s t r e s u l t s a tl a s tis e l e c ts o m er e p r e s e n t a t i v es a m p l e so fd a t a ，a n dt h e nu s et h ec l a s s i c a l p a r a m e t e r i z a t i o nm e t h o d sa n de n e r g ym o d e lm e t h o dt od oe x p e n m e n t ss e p a r a t e l y 二_ _ - _ - 一- - - _ _ _ - _ - _ _ _ - - ，_ - - _ - - _ - - - - - _ _ i _ _ - - _ - - - _ - _ _ 。_ _ _ _ _ _ _ 。_ - _ _ _ - _ _ _ _ - 一 a c c o r d i n gt oe x p e r i m e n tr e s u l t s ，ip r o p o s e dt h ed i r e c t i o no fi m p r o v e m e n t f o rt h en e x t k e y w o r d s ：p a r a m e t r i cc u r v e ；p a r a m e t e r i z a t i o nm e t h o d ；e n e r g ym o d e l v 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：盛 日期2 0 0 尹f 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名： 【i f 东大学硕士学位论文 1 1 研究背景 第一章绪论 计算机辅助几何设计( 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 ) 是由巴恩希尔 ( b a r n h i l l ) 与里森费尔德( r i e s e n f e l d ) 于1 9 7 4 年在美国犹他( u t a h ) 大学的一次 国际会议上提出，以描述计算机辅助设计( c o m p u t e ra i d e dd e s i g n ) 的更多的数 学方面，因此加上“几何修饰词。在当时，其含义包括曲线、曲面和实体的表 示及其在实时显示条件下的设计，也扩展到某些方面，例如四维曲面的表示与显 示。自此以后，计算机辅助几何设计开始以一门独立的学科出现。 c a g d 是随着航空、汽车等现代工业发展与计算机的出现而产生与发展起来 的一门新兴学科。它主要研究计算机图像系统环境下曲面信息的表示、逼近、分 析和综合，其研究核心为几何建模。c a g d 主要处理自由形式的曲线和曲面的构 造与表示，即自由曲线和自由曲面建模。所谓自由曲线和自由曲面，就是通过采 样得到的一系列型值点构成的离散曲线和离散曲面，它们没有数学模型，需要通 过曲线和曲面重建，来建立自由曲线和自由曲面的数学模型。 1 9 6 3 年美国波音( b o e i n g ) 飞机公司的弗格森( f e r g u s o n ) 首先提出了将曲线 曲面表示为参数的矢函数方法。弗格森所采用的曲线曲面的参数形式是形状数学 描述的标准形式。 1 9 6 4 年，美国麻省理工学院( m i t ) 的孔斯( c o o n s ) 发表了一个具有一般性的 曲面描述方法，给定围成封闭曲线的四条边界就可定义一块曲面片。1 9 6 7 年， 孔斯进一步推广了他的这一思想。在c a g d 实践中应用广泛的只是它的特殊形式 孔斯双三次曲面片。它与弗格森双三次曲面片的区别，仅在于将角点扭矢量 改为非零矢量。两者都存在形状控制与连接问题。 舍恩伯格( s c h o e n b e r g ) 于1 9 6 2 年提出的样条函数提供了解决连接问题的一 种技术。用于形状描述的样条方法是它的参数形式，即参数样条曲线、曲面。样 条方法用于解决插值问题，在构造整体达到某种参数连续阶( 指可微性) 的插值曲 线、曲面时是很方便的，但不存在局部形状调整的自由度，样条曲线和曲面的形 状难以预测。 山东大学硕士学位论文 法国雷诺( r e n a u l t ) 汽车公司的贝塞尔( b e z i e r ) 于1 9 1 7 年发表了一种由控 制多边形定义曲线的方法。设计员只要移动控制顶点就可方便地修改曲线的形 状，而且形状的变化完全在预料之中。贝塞尔方法简单实用，又漂亮地解决了整 体形状控制问题，在c a g d 中占有重要的地位，为c a g d 的进一步发展奠定了坚实 基础。贝塞尔方法仍存在连接问题，还有局部修改问题。 德布尔( d eb o o r ) 1 9 2 7 年给出了关于b 样条的一套标准算法。美国通用汽车 公司的戈登( g o r d o n ) 和里森费尔德( r i e s e n f e l d ) 在1 9 7 4 年将b 样条理论应用于 形状描述，给出了b 样条曲线曲面。 综上所述，2 0 世纪6 0 年代，法国汽车业的工程师借助计算机工具，通过使 用参数曲面表示汽车零部件实现了汽车的几何模型表示，开创了c a g d 学科。这 一时代的c o o n s 、b e z i e r 等人分别提出以c o o n s 曲面和b e z i e r 曲线为代表的 c o o n s 技术和b e z i e r 技术，建立了c a g d 的理论基础。从此以后，c a g d 发展十分 迅速，7 0 年代建立了b 样条技术，8 0 年代发展为有理b 样条技术，现在，曲面 表示和造型已经形成了以非均匀有理b 样条( n u r b s ：n o n - u n i f o r mr a t i o n a l b - s p l i n e ) 参数化特征设计( p a r a m e t e r i z e da n dc h a r a c t e r i s t i cd e s i g n ) 和隐式 代数曲面表示i m p l i c i ta l g e b r a i cs u r f a c er e p r e s e n t a t i o n ) 这两类方法为主 体，以插值( i n t e r p o l a t i o n ) 、逼近( a p p r o x i m a t i o n ) 、拟合( f i t t i n g ) 这三种手 段为骨架的几何理论体系。 目前，参数插值曲线的应用非常广泛。通常情况下，要求所构造的参数插值 曲线必须是光顺的。为了达到这个要求，不仅需要有好的插值方法，还要有好的 确定节点参数的方法。同一组数据点，即使采用同样的插值方法，若数据点的参 数化方法不同，也会获得不同的插值曲线，对数据点的参数化，应尽可能反映被 插值( 逼近) 曲线或设计员想要用数据点所构造的曲线的性质。 一般而言，曲线参数化都会努力使之接近于弧长参数化，这是因为弧长参数 化是比较理想的参数化方法，它可以使参数域中均匀分布的点对应于参数曲线上 均匀分布的点，对于实际应用具有重要意义，现在的参数化方法，都努力向弧长 参数化靠拢，但与真正意义上的弧长参数化还存在很大距离，而且，衡量这种距 离也需要有一个标准，所以，弧长参数化是很困难的。 2 山东大学硕士学位论文 1 2 研究现状 目前，在确定数据点的参数的方法中，比较常用的有，均匀参数化法，累加 弦长参数化法，向心参数化法，修整弦长参数化法以及z c m 参数化法。 均匀参数化方法是最简单的方法，它认为各点的参数是均匀递增的，这种方 法仅适用于数据点多边形各边接近相等的场合，否则，在相邻段弦长相差悬殊的 情况下，生成插值曲线后弦长较长的那段曲线显得较扁平，弦长较短的那段则膨 胀的厉害，甚至出现尖点或打圈自交情况，出现上述问题，从物理上可解释如下： 把参数t 看作时间，质点p 随着时间变化在空间扫出一条一次经过给定位置的曲 线p ( t ) ，采用均匀参数化就意味这在任一两邻点间花费同样多的时间，而不管 它们间的距离如何，所以采用这种方法构造出的曲线效果较差。 累加弦长法是现在被广泛采用和接受的参数化方法，在该方法中，弦长被看 作是弧长的近似，通过迭代，累加弦长参数化方法就成为弧长参数化方法，这 种参数化方法反映了数据点按弦长的分布情况，一直被认为是最佳参数化法。它 克服了数据点按弦长分布不均匀情况下采用均匀参数化所出现的问题，但是，文 献 i 已经证明，只有参数曲线是直线的时候，参数曲线根据弧长插值才最合适。 向心参数化方法嘲，由美国波音公司的李( l e e ，1 9 8 9 ) 提出，他从累加弦 长参数化法并不总能保证生成光顺的插值曲线出发，认为问题在于未考虑数据点 相邻弦线的折拐情况。由此他假设在一段曲线弧上的向心力与曲线切矢从该弧段 始端至末端的转角成正比，利用累加弦长的平方根来计算节点参数，将数据点相 邻弦线的折拐情况考虑在内，据他介绍，在他所作的所有非均匀分布数据点的实 验中，该方法都给出了优于前两种方法的结果。 福利在文献 3 里提出了修正弦长参数化方法，这种参数化方法引入了修正 系数，对实际弦长偏短的情况做到了修正作用。修正弦长就较接近实际弦长。另 方面，不同于向心参数化使向心加速度平稳的变化，修正弦长法增大了花费在 这一曲线段上运动地“时间间隔挣，使“切向速度减缓下来，修正弦长参数化 法生成的插值曲线显现较好的光顺性。 通常意义上，弧长参数化法是最理想的参数化方法，尽管上面提到的参数化 方法都努力向弧长参数化靠拢，但毕竟与真正意义上的弧长参数化还有相当的距 离，事实上，弧长参数化往往是非常困难的，甚至是不可能的，因此，近年来的 山东大学硕士学位论文 研究，大多集中于寻找一种近似弧长参数化方法来代替弧长参数化法。而近似弧 长参数化需要一个衡量近似程度的标准。为使这种状况有所改善，f a r o u k i 提出 了最优参数化的标准璐1 ，f a r o u k i 将b e z i e r 曲线重新参数化为有理参数曲线，曲 线重新参数化后，其形状和参数域保持不变，描述曲线的参数方程发生了变化， 参数速度相应改变。改变重新参数化因子，得到描述同一条曲线的不同的参数方 程。利用重新参数化因子，f a r o u k i 求出了b e z i e r 曲线的最优参数化，即参数 速度最逼近单位速度的曲线参数方程。 郭风华副教授在f a r o u k i 最优参数化理论的基础上，讨论了一种新的重新参 数化变换函数哺1 ，比常用的有理线性参数变换计算简单，通用性强。这种方法可 以求出b e z i e r 曲线的最优参数化方程，在她的文章中，给出了求解b e z i e r 曲线 最优参数化方程的新算法，新算法具有单一自由度，最优值通过求解个二次方 程的根得到，算法简单可靠。 然而，不论是上述的参数化方法，还是对参数化的优化方法都不能对参数化 的质量，也就是所采用的参数化与弧长参数化之间的差异进行人为的控制。由于 这个原因，文献 7 给出了改善b e z i e r 曲线参数化效果的算法，以便对参数化的 效果进行控制，但是这种算法仅适合于b e zi e r 曲线。 以上提到的参数化方法主要是根据数据点的分布及其几何性质预先确定各 数据点的参数值，由于数据点的分布与插值曲线几何性质之间的关系非常复杂， 因此还未得到很好的研究，潘日晶教授提出从相对简单的二次b 样条曲线入手跚， 基于插值曲线本身的几何性质来进行参数化，以使插值曲线具有预期的几何性 质，不同于以往的参数化方法，该方法不是预先选定数据点的参数值，而是在构 造插值曲线的过程中根据b 样条曲线预期的几何约束条件，递推的确定各数据点 的参数值，因此称之为动态参数化法，她的实验结果表明这种方法非常有效。 张彩明教授提出了z c m 参数化方法h 3 ，该方法是一种整体性方法，假设数据 点取自一条二次曲线，以此作为插值曲线的几何约束，其数据点参数化的结果具 有二次精度的优点，实验表明，通常情况下利用它所构造的参数插值曲线效果要 好于向心参数化或修正弦长参数化方法。 4 l il 东大学硕士学位论文 _ i曼i mi iiiim l ! 皇曼舅! 曼曼曼 1 3 论文主要研究成果 本文对计算机辅助几何设计领域中插值曲线的参数化方法进行了深入的学 习和研究，对现有的经典参数化方法如均匀参数化法，累加弦长参数化法，向心 参数化法，修正弦长参数化法，z c m 参数化法的理论基础和算法实现进行了系统 的总结。 在此基础上，根据曲线能量的理论，提出了一种基于能量模型的参数化方法。 这种方法通过分步依次取出四点构造两条朗格郎日插值二次曲线，然后旋转坐标 轴使之成为两条抛物线，再对两条抛物线进行能量极小约束，通过数值解方程的 方法得到局部参数值，最后将局部参数值转换成为全局参数值的方式完成参数化 过程。该方法通过对局部曲线进行能量极小优化约束来确定节点参数，使得构造 出的样条插值曲线在理论上比较光顺。 论文使用经典的参数化方法和新的能量模型参数化方法，对具有代表性的数 据点进行了参数化实验，并根据参数化结果，过数据点构造三次样条插值曲线， 对插值出来的曲线形状进行了对比，并求得插值曲线与原曲线的误差，对各种参 数化方法产生的误差进行了比较。实验表明，在一些常见的经典数据分布情况下， 本文介绍的能量模型参数化，可以获得比经典参数化方法更准确的结果和更好的 形状。 最后，根据实验结果，论文总结了新的能量模型参数化的不足，提出了比较 可行的改进方案，给出了下一步研究的方向。 1 4 论文章节安排 全文共分五章，具体内容安排如下： 第一章，介绍计算机辅助几何设计、数据点参数化方法的产生背景和发展现 状。首先介绍了在计算机辅助几何设计理论的提出，及其在三十多年的发展过程 中的基本理论和代表人物。然后，介绍了计算机辅助几何设计的现状和数据点参 数化理论的出现和发展情况，最后简单介绍论文的研究成果。 第二章，介绍参数插值曲线的基础知识。参数曲线是计算机辅助几何设计领 域的基本理论，也是目前研究热点的基础问题，本章介绍了参数插值曲线的基本 山东大学硕士学位论文 ! _ _ - - - 一 一- 一- _- 曼曼曼曼曼曼曼曼! ! ! 詈詈曼曼鼍! 量暑置鼍詈詈暑暑 概念，包括曲线的表示形式、曲线弧长的定义和计算公式以及曲线能量的定义和 计算公式。 第三章，介绍数据点参数化方法中比较常用的几种方法的理论基础和算法实 现。数据点参数化方法经历数十年发展，目前被广为接受的主要有均匀参数化 法，累加弦长参数化法，向心参数化法，修正弦长参数法以及z c m 参数化法，本 章对这几种经典的参数化方法进行了介绍和部分推导。 第四章，提出了一种通过旋转构造两条抛物线并使之能量之和极小的参数化 方法。包括理论基础，推导以及实验。基于曲线能量的概念和物理意义，本章提 出了一种基于能量极小模型的参数化法，该方法采取分步构造两条二次曲线，旋 转坐标轴成为两条抛物线，然后对其进行能量极小约束，求得局部参数值，并最 终转换为全局参数化值的参数化方法。本章的最后使用这种参数化方法进行了实 验，并与几种经典参数化方法进行了对比。 第五章，总结和展望，总结本文的内容，并对下一步的研究进行了计划。总 结全文的内容，对论文提出的基于能量极小参数化方法也进行了总结，并针对这 种方法的不足提出了新的研究方法。 6 山东大学硕士学位论文 ii - 第二章参数插值曲线的基础知识 在几何造型中，对曲线的描述一般有两种形式，即参数方程形式和隐式方程 形式与非参数形式相比，参数曲线以其构造简单直观、易于显示等特点流行于 世这种曲线表示方法脱离了对坐标系的依赖，给许多应用带来了极大的方便 本章将介绍参数曲线的有关基础知识，例如：曲线的参数表示、弧长、能量问题， 为后续研究打好基础。 2 1 曲线的参数表示 在空间解析几何里，空间曲线常采用参数表示，即把空间曲线上一点p 的三 个坐标写成某个参数u 的标量函数 x - - - - x ( u ) ，y = y ( u ) ，z = z ( u ) 在微分几何里，它们被合写在一起，列矢量转置成行矢量，左端就是该点的 位置矢量p = x ，y ，z ，右端p ( u ) = x ( u ) ，y ( u ) ，z ( u ) 表示它是参数u 的矢函数 于是，就有微分几何里表示曲线的一般的矢函数形式 p = p ( u ) ( 2 1 ) 明显地，上式方程右端的p ( u ) 指3 个标量函数x ( u ) ，y ( u ) ，z ( u ) 合写在一起 构成的矢函数这种矢量表示等价于笛卡尔分量表示 p ( u ) = x ( u ) i + y ( u ) j + z ( u ) k 其中，i ，j ，k 分别为沿x 轴，y 轴，z 轴正向的3 个单位矢量，它与前面的参 数表示也是等价的 在几何造型里，曲线大都采用称为基表示的一种特殊的矢函数形式， p ( u ) = i = 0 咖) ( 2 2 ) 其中， 仍 ) ( i ：0 ，1 ，n ) 称为基函数，它决定了曲线的整体性 质，口j ( i = 0 ，1 ，n ) 称为系数矢量，当基函数给定后，系数矢量也就决定了所 表示曲线的形状。 7 山东大学硕士学位论文 鼍曼曼皇曼皇皇曼曼曼曼曼曼曼曼皇鼍曼量皇a _ = -l a i 苎 描述形状的参数曲线，例如式( 2 2 ) ，总是有界的参数益线的范围可以方便 的用参数区间却定义域5 “蚝或“陬，u 2 来表示，也可以称它为曲线的参数 域。参数曲线中的参数可能具有某种几何意义例如：o x y 平面上第一个象限内圆 心位于原点的四分之一单位圆： p = 【c o s 0 ，s i n t g ，0 0 n 1 2 其中，参数9 就具有明确的几何意义，它表示从圆心到圆上一点的半径矢量对于 x 轴方向的夹角参数也可能没有任何几何意义例如，参数三次多项式 p = a 0 + a l u + a z u 2 + a 3 u 3 中的参数。没有任何几何意义这样的参数称之为一般参数或任意参数 同一条曲线可以有不同的参数方程，给定一个具体的单参数的矢函数，即给 定一个具体的参数曲线方程它既决定了所表示曲线的形状，也决定了该曲线上 的点与其参数域内的点( 即参数值) 之间的一种对应关系。 在形状确定后，这种对应关系指的是曲线上点p ( u ) 沿曲线弧长的分布情况 与点的参数值u 在参数域内的分布情况之间的对应一般地，当曲线取任意参数 时，参数域内线段长度之比既不等于曲线上对应曲线段弧长之比，也不等于对应 曲线段的弦长之比仅在曲线取自身弧长或弧长的线性函数为参数时，参数域线 段长度之比才等于曲线上对应曲线段弧长之比，但一般的仍不等于对应衄线段的 弦长之比可见，这种对应关系与参数选取有关。 2 2 弧长 对于正则曲线p ：p ( t ) ( 1 尸7 ( f ) i o ) ，从点p ( o ) 到点p ( t ) 的弧长定义为 f s ( f ) = j ( f ) 防 0 t 其中i p ( f ) i 是切矢量p ( f ) 的长度，式s ( f ) = j 1 p 7 ( f ) 防可看作式曲线从p ( t ) 到p ( t ) 的折线长度的极限。记p ( o ) 为b ，p ( t ) 为只，在曲线从最到只之间沿着t 递增的 方向，取n 一1 个点置，昱，乞- l ，把相邻点用直线段连接起来，得到曲线的折线， 8 山东大学硕士学f 7 = 论文 它的长度为( 刀) = 1 只一，只l ，当以j 时，l ( 玎) 专s ( f ) 。 i = 1 如果以弧长为参数，曲线在任意点的切矢量为单位矢量，设s 表示p ( t ) 到 p o + “) 的弧长，由上面讨论知，弧长l a pl 和弧长s 的极限相同，即 豳l 卯i 斫。衍 所以 丁：1 1 1 1 1 竺：坚 j 一 一= 一 “娟氏sd s t 称为p ( t ) 处切线方向的单位矢量。 2 3 能量 曲线段两点间，转过的角度和弧线段长的比值，伍，s ，用极限的观点定义到 曲线的某一点上，就是曲线在该点的曲率，曲率的几何意义为曲线的单位切矢对 于弧长的转动率。对于平面曲线p = p ( u ) = 【x ) ，y ) 】，一阶、二阶导矢分别为 p = 【碧( 甜) ，少( z f ) 】，矽= 碧( z f ) ，夕( 甜) 】 曲率可按如下公式计算： 拈意劳( 贾2 + 夕2 ) 7 2 曲线的能量定义为对该曲线弧上曲率平方的积分，即 e _ - f k 2 d $ ( s 为弧长，k 为该曲线弧上的曲率) 9 【i f 东大学硕士学位论文 第三章参数化方法 设给定挖+ 1 个数据点只，j 0 , i ，刀。如果我们把给定的刀+ 1 个数据点看作 是某一参数曲线上的点p ( ) ，那么对只，i = 0 , 1 ，刀插值，就是要求出参数曲线 p ( t ) ，使得p ( t ) = 只。要唯一地决定一条插值于肛+ 1 个点只，i = 0 , 1 ，行的参数 插值曲线或逼近曲线必须先给数据点只指定相应的参数值，使其形成一个严格 递增的序列司，：t o f l 乙，称为关于参数t 的一个分割( p a r t i t i o n ) 。其中 每个参数值称为节点( k n o t ) 或断点( b r e a k p o i n t ) 。对于插值曲线而言，它决 定了位于曲线上的这些数据点与其参数域t t o ，乙】内的相应点之间的一种对应 关系。对组有序数据点决定一个参数分割称之为对这组数据点实行参数化。 把插值曲线看作质点顺序通过的一些空间位置( 即数据点) 的运动轨迹，参 数t 看作时间，那么对数据点的参数化，就等于规定了质点依次到达这些空间位 置的时间。它们是人为给定的。同一组数据点，即使采用同样的插值法，若数据 点的参数化不同，将可能获得不同的插值曲线。我们希望，对数据点的参数化， 应尽可能反映被插( 逼) 曲线或设计员想要用数据点所构造的曲线的性质。对数 据点实行参数化主要有如下方法： 3 1 均匀参数化法 使每个节点区间长度( 用向前差分表示) a ，= + 。一f f = 正的常数， f = o ，1 ，刀一l ，即节点在参数轴上呈等距分布，为处理方便起见，常取成整数 序列 f i = i ， i = o ，l ，刀 这种参数化法仅适合于数据点多边形各边( 或称弦) 接近相等的场合。否则， 在多边形相邻段弦长相差悬殊的情况下，生成插值曲线后弦长较长的那段曲线显 得较扁平，弦长较短的那段曲线则膨胀得厉害，甚至出现尖点或打圈自交的情况。 l o 【l 东大学硕士学位论文 _ ! - - _,l iih - - 出现上述问题，从物理上可解释如下：把参数t 看作时间，质点尸随着时间 变化在空间扫出一条依次经过给定位置( 即数据点) 的曲线p ( f ) 。采用均匀参数 化就意味着在任意两邻点间花费同样多的时间，而不管它们间的距离如何。如果 汽车沿着这样条插值曲线行驶时，数据点成了站点，当两邻站点间距离大时， 就必须高速前进。如果接下来的两相邻站点间距离很小时，由于不能把速度突然 减下来，就会发生过冲问题。 3 2 积累弦长参数化法 t i = 一1 + i 纰一1 l ， i = 1 ,