（计算数学专业论文）参数曲线、曲面的区间隐式化及代数曲线的区间参数化.pdf

摘要 本文主要讨论了区间算法在曲线、曲面隐式化和参数化中的应 用具体来说，我们对有理参数曲线、曲面进行区间隐式化，以及 对代数曲线进行区间参数化对于这些问题的研究结果，在计算机 图形学和c a d 系统中具有重要的理论意义和应用价值 在第一章中，首先回顾了计算机辅助几何设计与制造系统中几 何造型的发展简史，说明了稳定性在物体造型中的重要性为了达 到稳定性的要求，引入了区间算法和舍入区间算法，以及介绍了区 间代数曲线、曲面和区间b e l i e r 曲线 在第二章中，提出了区间曲线隐式化的概念用一个低次的区 间代数曲线去隐式化个高次的有理参数曲线并且研究了细分参 数曲线后对区间隐式化的影响 在第三章中，对第二章中区间益线隐式化进行了推广，研究了 区间曲面隐式化我们用一个低次的区间代数曲面去隐式化一个高 次的有理参数曲面 在第四章中，对代数曲线进行了区间参数化的研究主要是对 一个三角区域内的代数曲线段进行三次区间参数化，并且要求保持 在端点的一阶几何连续，同时考虑了细分代数曲线后对区间参数化 的影响 关键词：区间算法，舍入区间算法，区间代数曲线，区间代数曲线 段，区间代数曲面，区间代数曲面片，区间隐式化，区间b e l i e r 曲 线，区间参数化 a b s t r a c t t h i s p a p e rd i s c u s s e s s o m ea p p l i c a t i o n so fi n t e r v a l a r i t h e m e t i c i ni m d l i c i t i z a t i o na n dp a r a m e t r i z a t i o no fc u r v e sa n ds u r f a c e s m o r e d e t a i l s w ed os o m ew o r ka b o u ti n t e r v a li m p l i c i t i z a t i o no fr a t i o n a l c u r v e s ( s u r f a c e s ) ，a n di n t e r v a lp a r a m e t r i z a t i o n o f a l g e b r a i c c u r v e s t h e s e p r o b l e m sh a v et h e o r e t i c a la n dp r a c t i c a li m p o r t a n c ei nc o m p u t e rg r a p h - i c sa n dg e o m e t r i cm o d e l i n g i nc h a p t e ro n e ，a f t e rab r i e fr e v i e wo ft h er o l eo fs o l i dm o l d e l l e r s i nc a da n dc a m ，w ee x p l a i nt h ei m p o r t a n c eo fr o b u s t n e s sf o rc u r v e d o rs u r f a c e ds o l i dm o d e l s f o rs t a b i l i t y , i n t e r v a la r i t h e m e t i ca n dr o u n d e d i n t e r v a la r i t h e m e t i ca r ei n t r o d u c e d a tt h es a m et i m e ，w ei n t r o d u c e s o m e c o n c e p t sa b o u t i n t e r v a la l g e b r a i cc u r v e ( s u r f a c e ) a n di n t e r v a lb e l i e r c u r v e i nc h a p t e rt w o ，w ep r o p o s ean e w c o n c e p tc a l l e di n t e r v a li m p l i c i t i 。 z a t i o no lr a t i o n a lc t i r v e s t h a ti s ，w ef i n da ni n t e r v a la l g e b r a i cc u r v ew i t h l o w e rd e g r e et ob o u n dag i v e np a r a m e t r i cr a t i o n a lc u r v ew i t hh i g h e rd e - g r e e f u r t h e r m o r e ，w es u b d i v e r a t i o n a lc u r v e sa n dt h e nt om a k ei n t e r v a l i m p l i c i t i z a t i o no ft h e s ec u r v e sr e s p e c t i v e l y i nc h a p t e rt h r e e ，w ee x t e n di n t e r v a li m p l i c i t i z a t i o no fc u r v e st o s u r f a c e sc a s e w ef i n da ni n t e r v a la l g e b r a i cs u r f a c ew i t hl o w e rd e g r e e t ob o u n dag i v e np a r a m e t r i cr a t i o n a ls u r f a c ew i t hh i g h e rd e g r e e w e m a i n l yf o c u so nr e c t a n g l eb e l i e rs u r f a c ep a t c h i nt h el a s tc h a p t e r ，w ed os o m er e s e a r c ha b o u ti n t e r v a lp a r a m e t r i z a - t i o no fa l g e b r a i cc u r v e s w em a i n l yb o u n dag i v e na l g e b r a i cc u r v es e g - m e r i tw i t hac u b i ci n t e r v a lb e l i e rc u r v e w er e q u i r et h eg i v e na l g e b r a i c c u r v es e g m e n ta n dt h ei n t e r v a lb 芭i e rc u r v et oh o l dg 1a tt h et w oe n d p o i n t s f o r t h e r m o r e ，w es u b d i v i d ea l g e b r a i cc u l w e 8a n d t h e nt od oi n - t e r v a lp a r a m e t r i z a t i o no ft h e s ec u r v e sr e s p e c t i v e l y k e yw o r d s ：i n t e r v a la r i t h m e t i c ，r o u n d e di n t e r v a la r i t h m e t i c ，i n t e r v a l a l g e b r a i cc u r v e ，i n t e r v a la l g e b r a i cs e g m e n t ，i n t e r v a la l g e b r a i cs u r f a c e ， i n t e r v a la l g e b r a i cs u r f a c ep a t c h ，i n t e r v a li m p l i c i t i z a t i o n ，i n t e r v a lb e l i e r c u r v e ，i n t e r v a lp a r a m e t r i z a t i o n 致谢 花开花落，三易寒暑，我的硕士生活也即将结束，作此文以做总结本文 是在导师冯玉瑜教授和陈发来教授的悉心指导下完成的，从选题到定稿，两位 导师都给予了许多无私的关怀和帮助，付出了大量的心血三年的研究生生活 中他们渊博的知识，严谨的治学，谦逊的为人，诚实的作风一直都深深的影响 着我在此我向他们表示崇高的敬意和衷心的感谢! 我还要感谢科学计算与计算机图形学实验室的师兄弟们，无论是在完成 论文期间，还是平常的研究生学习过程中，他们都给予了我许多无私的帮助 另外，数学系的许多老师和师兄弟们在日常学习生活中给我提供了许多方便， 在此一并感谢 最后我要感谢我的父母和家人这么多年来在物质和精神上对我的全力支 持，使我能够安心学业，并顺利的完成毕业论文 谨将此文献给所有曾经关心过我的人 第一章绪论 1 1 引言 曲线( 曲面) 的参数化表示和隐式化表示是c a g d 中几何物体的两种基本 表示方法这两种表示方法各有其优点和缺点，例如，我们很容易从曲线( 曲 面) 的参数表达式得到曲线( 曲面) 上的点，这样就很容易通过算法在计算机 上描绘出曲线( 曲面) 的形状；另外一方面，我们很容易通过曲线( 曲面) 的 隐式表示来判断任意一个点是在曲线( 曲面) 的内部，表面或者外部从而， 同时得到曲线( 曲面) 的两种表达形式是非常有意义的 到目前为止，大量的工作都集中在寻找参数曲线( 曲面) 的精确隐式表示 以及代数曲线( 曲面) 的精确参数化表示 1 ，2 ，3 然而，精确表示的物体只 是理想的数学体，只有很少的一部分理想数学体能够在计算机中精确表示出 来在计算机中，所有的运算都是通过浮点算法进行的通过浮点算法得到的 数只是近似的所以，严格的说，一个以浮点数表示的几何体是不精确的，这 个不精确性是因为浮点数的有限精度产生的这样，一个连续的几何体，计算 机中只能用离散的点来近似表示，这种不精确表示的结果是： ( 1 ) 在几何计算上的不可靠性例如，边界求值 ( 2 ) 几何实体的几何与拓扑表示之间的不一致性 例如曲线( 曲面) 的求交问题中涉及到对非线性多项式方程组的求解，而 多数的非线性方程组的求解在当前的c a d c a m 系统中都是按照浮点算法进 行计算由于浮点数的误差，一些根可能会丢失一个典型的例子就是坏条件 下的求交问题( 相切交和莺叠交) 这样的坏条件问题对初值和计算误差是很 敏感的，对初值的一个很小的扰动，就可能极大地改变计算结果虽然增加数 值精度可能会改善求根过程，但是还不能完全解决这个问题实际上，即使在 现今的双精度浮点计算机上，在物体造型时还不时地发生丢失交点( 如密切 点) 的情况，这些问题有时候可能会导致系统瘫痪，降低系统的效率 例1 ：设有一个四阶平面b e i i e r 曲线，如图1 1 所示，其控制顶点为 ( 一0 5 ，0 0 6 2 5 ) ，( 一0 2 5 ，一0 , 0 6 2 5 ) ，( 0 ，0 0 6 2 6 ) ，( o 2 5 ，- 0 0 6 2 5 ) ，( 0 5 ，0 0 6 2 5 ) ( 1 1 1 ) 这条b e g i e r 曲线等价于显式曲线y = x 4 ( - o 5 z 0 5 ) ，显然曲线与x 轴 在( z ，y ) = ( 0 ，0 ) 处相切，然而，若把曲线沿y 轴方向移1 个单位，再往回分三 次各移- 1 3 ，如果在计算机中以浮点运算( f p a ) 来做，则得到的曲线一般与 原曲线不同 2 0 0 2 年中国科学技术大学硕士学位论文 第一章绪论 第2 页 1 1 引亩 心声 - o 4 _ o 2 v - 00 2 _ 0 ” v - - 0 0 6 图1 1y 4 和y = 0 在原点密切交 例如，设计一个数字计算机有四位尾数，误差是四舍五入不是截尾，则有 理数- 1 3 在计算机中是以一0 3 3 3 3x1 0 0 存入在进行了四次移动之后，这个 曲线的新的控制顶点就变为： ( 一0 5 ，0 0 6 3 1 ) ，( 一0 2 5 ，一0 0 6 2 4 ) ，( 0 ，0 0 6 3 1 ) ，( 0 2 5 ，- 0 0 6 2 4 ) ，( 0 5 ，o 0 6 3 1 ) 若计算曲线在参数t = 0 5 的值，则可得到( o ，0 0 0 0 3 5 ) 而不是( 0 ，o ) ，该 数值误差可能导致几何方程和拓扑结构不相容，假如，用这些新的控制点来求 曲线与x 轴的交点，若误差界比0 0 0 0 3 5 小的话，将会无交点，上面问题说明 了通过变量的代数变换会增加误差 下面的例子指出，即使原始数据是准确的，在解的过程中也会产生误差 1 4 j 例2 ：求一个三次显示方程y = 扛一o 1 ) 一o 6 ) 一o 7 ) ( os x s1 ) 与x 轴的交 首先将该曲线转化为b e r n s t e i n 基形式表示( 用有理算法) ，以浮点算法运 算，基于b e r n s t e i n 分割算法( 如b e l i e r 剪裁 5 5 方法或射影多面体算法 5 ) ， 最后得到的结果是丢失了0 7 这个根，详细可见【4 】 在物体造型中缺乏稳定性的问题自8 0 年代就已经被提出并且一直是一个 活跃的研究课题，有大量的文章在讨论如何进行稳定的几何表示及算法详见 6 ，7 j 等文献 2 0 0 2 生 第一章绪论 中国科学技术大学硕士学位论文 第3 页 12 区间算法和舍入区间算法 例如，像在上面例l ，例2 的丢根问题可以用舍入区间算法代替浮点算法 来克服，舍入区间算法可保证数值计算的稳定性与可靠性 区间运算早在6 0 年代就由m o o r e 引入进稳定性的数值分析计算，但直到 近几年才被h u 【8 ，9 等人引入几何造型领域，s e d e r b e r g 1 0 】引入区间b e l i e r 曲 线来逼近一般曲线，h u 1 l ，1 2 等人将区间运算应用于曲线，曲面求交及几何 形体的表示之中，给出了几何形体的可靠的表示方法及几何运算算法此外， 区间运算还能被应用于计算机图形学的许多其它领域，如碰撞检测，可视化 等 用区间表示物体通常可以避免浮点算法中的数值扰动导致的拓扑冲突见 1 0 】对物体用区间几何表示，且基于舍入区间算法，有效地解决了当前基于 浮点算法的边界表示的物体造型中的稳定性问题 1 2区间算法和舍人区间算法 一个区间【o ，q 是指个实数集合： f a ，6 j = x l a z 6 )( 1 2 1 ) 若n = b 则称区间h6 】为一个退化区间，两个区间 n ，6 】， c ，司相等指的是 a = c ，b = d 当两个区间的交为空时，当且仅当o d 或者c b 一般的有 陋，6 u c ，d 】= m i n ( a ，c ) ，m a x ( b ，d ) i a ，6 1f 3 c ，d 】= i r n a x ( a ，c ) ，m i n ( b ，d ) ( 1 2 2 ) 【o ，6 】 ( c ，d i 6 c 区间【o ，6 】的宽度定义为：”( k 胡) = b o ，区间1 0 i6 1 的中点定义为： c ( 【。，6 】) = ( b + n ) 2 假设a = a ，b 】以及b = 【c d 是两个区间，而o ( + ，一，) 是一个运算符号，那么ao b 定义为： 具体的说即为 a o b = ( x o y l x a ，g b ) f a ，6 j + i c ，d = f 0 + c ，b + d 然臻篙i n ( a c 警a db c ，b d ) ，l n a , x ( a c a db ch a ) ， q 。 陋，6 】 c ，d = m ， 】 、1 肛，b f c ，d j = 陋，6 】f l d , l c 】，0 9 f e ，司 2 0 0 2 正 第一章绪论 中国科学技术大学硕士学位论文第4 页 1 3 区间b e l i e r 曲线 很容易证明，加法和乘法的交换率是成立的，但是分配率不成立一般的 说来，对于分配率有 a ( b + c ) a b + a c 其中，a ，b ，c 是三个区间如果a 是一个常数，那么将变成等号 实际上，用上面的式子进行浮点运算，是不能保证边界的舍入数据能够完 全落在区间之内的浮点数在计算机中是具有固定的长度的，表示浮点数的字 节数依赖于变量的精度例如，采用i e e e 标准，一个双精度的数有6 4 位，8 个字节长，以二进制存储为( 士) m 2 e z p ，其中m 为尾数( 0 5 m s l ) ，e x p 为 指数如果x 和x 。是连续的正的双精度数，他们的差s 称为u l p ( u n i t i n t h e l a s t p l a c e ) ，= 2 5 3 2 v x p = 2 e x p 一5 3 加入舍入误差后，运算的结果可以保证一定会落在最后的区间中，舍入区 间算法( r o u n d e di n t e r v a la r i t h m e t i c ) 具体表达为： a ，6 + c ，d 】= a + c 一岛b + d + e 】 【o ，6 】一 c ，d = a d e ，b c + g 】 ， 9 趴 陋，6 】e ，胡= m i n ( a c ，a d ，b c ，b d ) 一s ，m a x ( a e ，a d ，b c ，b d ) + 】 、 a ，b c ，d = m i n ( a e ，a d ，b c ，b d ) 一，m a 2 9 ( a c ，a d ，b e ，b i d ) + 】 在上面的公式中，e 在二进制中表示2 e x p _ 5 3 ，其中e x p 为每个参加运算 的数的上界或下界在十进制中，它表示l o 一1 0 e x p ，其中k 表示采用的精 度位数 1 3 区间b e l i e r 曲线 定义1 3 1 区间b e c , i e r 曲线 区间b e l i e r 曲线【p l ( t ) 是由区间控制点 最1 定义的： n p | ( f ) = ( p k l b ? ( t ) ( o t 1 ) ( 1 3 i ) k = o n 为曲线的阶数 黜) = ( 抄( r 女= o l ，n 为b e r n s t e i n 多项式基陬】为一个向量区间 对于平面曲线来说： l 昆】= 【a k ，h 】 c k ，d t 】= ( 七，y ) f x a k ，6 t 】，y e k ，d 七】) ( 1 3 2 ) ( 1 3 3 ) 2 0 0 2 芷 第一章绪论 中国科学技术大学硕士学位论文 第5 页 14 区间代数曲线和曲面 图1 2 区间b e l i e r 曲线示例 对于三维空间曲线， 鼠 = a k ，b k 】【c k ，d k 【e k ，a = ( z ，y ，z ) i $ a k ，b k ，y ，d k ，z e k ， 】) ( 1 3 4 ) 曲线用区间曲线来表示，它与经典的b e l i e r 曲线的区别在于原来的实数 控制顶点由区间来代替，所以，经典的控制点向量由长方形来代替一般的， 已知曲线的控制顶点都是以单个浮点数给出的，可以认为是零宽度的区间， 随着运算的进行，区间的宽度逐渐增大，使得区间总是包含原来的精确值 区间b e l i e r 曲线描述了一个管道，如图1 , 2 所示它包含所有的其控制顶 点满足p k 【p k ( k = 0 ，1 ，棚) 的b e i i e r 曲线也就是包含了沿着参数从0 到 1 的连续区间的包络 1 4区间代数曲线和曲面 1 4 1 区间代数曲线 定义1 4 1 区间代数曲线 区间代数曲线是一个以区间为系数的代数曲线，其具有如下形式： 【， ( 。，v ) ：= 嘲矿= 【0 】 ( 1 4 1 ) 其中，嗡j 是区间，并且 o j 表示含零区间 2 0 0 2 年中国科学技术大学硕士学位论文 第6 页 第一章绪论 14 区问代数曲线和曲面 一个区间代数曲线可以表示为如下的一个点集： i a c ：= ) i g i j x y j = o ，g i j 嗡】) ( 1 4 2 ) 0 s i h m 对于一个非零的常数，容易证明 【向y = 0 o 蔓t + j m 和 f i a x 矿= o 0 1 l 卅m 代表同一个区间代数瞌线因此，我们可以对区间代数曲线的系数进行标准化 处理对于一个标准的区间代数曲线，我们要求 o s m 。却a x 。圳l 21 这里c ( 【南】) 表示区间【岛】的中点 定义1 4 2 区间代数曲线的宽度 定义区间代数曲线的宽度为 ”( 州) ：= 2 ( 【向】) ( ( m + 1 ) ( m + 2 ) ) 定义1 4 3 区间代数曲线段 一个区间代数曲线段是一段定义在一个三角区域内的区间代数曲线，区 间代数曲线段的b e r n s t e i n b e l i e r 表示形式如下： ，】( “，”，”) ：= 【岛d b 瓢( u ，”，”) = 【o 】 ( 1 4 5 ) “0 h - k = r n 这里 鼢( 叩，”) = 盎山彬，州+ k = m 是b e r n s t e i n 基函数，( u ，”，”) 表示三角形t = 噩乃码区域内的一个点相对 于三角形的面积坐标， 图1 3 给出了一个三次区间代数曲线段的示例 3 4 4 4 q q 2 0 0 2 年中国科学技术大学硕士学位论文 第7 页 篁三兰堑篁 ! ! 兰垦堡垡墼塑竺塑些塑 t 3 。 a 2 n 1 ， v 图1 3 三次区间代数曲线段的示例 为了标准化区间代数曲线段，类似于区间代数曲线，要求 + j m + a 胁x l 。( 】) l = 1 定义1 4 4 区间代数曲线段的宽度 定义区间代数曲线段的宽度为 t 3 ( 1 4 6 ) ”( ，】) ：= 2 ( 向 ) ( ( m + 1 ) ( m + 2 ) )( 1 4 7 ) + j + = m 1 4 2 区间代数曲面 类似于区间代数曲线，我们给出区间代数曲面的一些基本定义 定义1 4 5 区间代数曲面 一个区间代数曲面是一个以区间为系数的代数曲面，其具有如下形式 【， ( 刚，z ) ：= 向矿z = 【o 】 ( 1 4 8 ) o i + j + 女兰m 对于一个非零的常数k ，同样有 【岛女矿= 0 o i + i + s ” 2 0 0 2 年中国科学技术大学硕士学位论文 第8 页 篁三塞竺丝 ! ! 兰垦堡垡墼堕塑塑些里 代表同一个区间代数曲面同样可以对区间代数曲面的系数进行标准化处理 对于一个标准的区间代数曲面，我们要求 。s 州m a + x mc ( 嘲) l = 1 ( 1 删 定义1 4 6 区间代数曲面的宽度 定义区间代数曲线的宽度为 t ( 【，】) ：= 6 t l ( 【，t j k 】) ( ( m + 1 ) ( r h + 2 ) ( m + 3 ) ) ( 1 ，4 1 0 ) o i + j + k m 定义1 4 7 区间代数曲面片 一个区间代数曲面片是一片定义在一个四面体区域内的区间代数曲面， 区间代数曲面片的b e r n s t e i n b e l i e r 表示形式如下： 【， ( u ，”，w ，g ) ：= 【岛i b 承f ( u ，”， ，g ) = o ( 1 4 1 1 ) i + j + k + l = m 这里 一 鼢l ( 刚， ，g ) = 淼“口i ， + j + + f _ m 是b e r n s t e i n 基函数，( “，”，w ，q ) 表示四面体t = n 乃码乃区域内的一个点相 对于四面体的体积坐标 图1 4 给出了一个三次区间代数曲面片的示例，其表示的区间代数曲面片 为图中上下两个曲面片以及两个曲面片中间所夹区域 为了标准化区间代数曲面片，要求： i 州+ m 川a x ：。i c ( 嗡删= 1 ( 1 4 1 2 ) 定义1 4 8 区间代数曲面片的宽度 区间代数曲面片的宽度由如下式子决定： ”( ， ) ：= 6”( 岛 f 】) ( ( m + 1 ) ( m + 2 ) ( m + 3 ) )( 1 4 1 3 ) i + j + k + l = m 0 = 少 矿 z 向 m 一 忡呸 和 2 0 0 2 年中国科学技术大学硕4 - 学位论文 第9 页 篁三兰篁堡 ! ! 兰奎兰竺三堡 图1 4 三次区间代数曲面的示例 1 5 本文的工作 在第一章里，首先说明了区间算法在物体造型中的重要性，同时给出了一 些基本的区间曲线曲面的定义 在第二章里，首次提出了有理参数曲线的区间隐式化的概念对三角形区 域内的任一n 次的有理参数曲线，用一个低次的m ( m n ) 阶的区问代数曲线 段去包含有理参数曲线，并且使这种包含达到某种最优性，同时讨论了对有理 曲线进行细分后逼近的效果 在第三章里，把第二章的曲线的情况推广到了曲面的情况在一个四面体 里，用一个低次的区间代数曲面片去包含高次的有理曲面，并且使这种包含达 到某种最优性 在第四章里，对于在三角形区域内的代数曲线，给出了一个三次的区间 b e l i e r 曲线逼近，使得此区间b e i i e r 曲线包含给定的代数曲线，并且保持在两 端端点的插值以及一阶几何连续，同时考虑了细分代数曲线后逼近的效果 第二章有理曲线的区间隐式化 由于在实际的应用中，高次有理曲线( 曲面) 的精确隐式化表示具有极 其复杂的表达式，所以给应用带来了一些困难，从而，寻找有理曲线( 曲面) 的近似隐式表达式变得非常实际在 1 3 中，陈发来提出了一个有效的算法 去计算有理曲线的近似隐式化表达后来，t w s e d e r b e r g 等讨论了有理曲 面的近似隐式化问题 1 7 在本章里，我们采用几何体的区间表达，并且提 出了区间隐式化( i n t e r v a li m p l i c i t i z a t i o n ) 的概念，也就是找到一个低次的区 间代数曲线去包含一个给定的高次有理参数曲线，并且使得包得尽可能的紧 设p ( t ) 是一个平面的n 次的有理b e g i e r 曲线，其齐次形式为 p ( t ) = ( z ( t ) ，秽( t ) ， ( t ) ) = 。b b ? ( t ) ，0 st l( 20 1 ) i = 0 这里只= ( y ，1 ) 和w t ，i = 0 ，1 ，n 是控制顶点和每个顶点相应的权值 霹( ) = ( ? ) t i ( 1 一t ) n 一4 是b e r n s t e i n 基函数有理曲线p ( t ) 的区间隐式化问题 可以陈述如下： 找一个m 次( m n ) 区间代数曲线使得这个区间代数曲线包含p ( t ) ( 或者说，p ( t ) 在这个区间代数曲线的内部) ，并且使得包含p ( t ) 的区间代 数曲线的宽度达到极小 为了达到包含上的精确性，必须找到区间代数瞌线包含有理参数曲线的 条件，以及使得这种包含达到某种最优性的标准 2 1有理曲线的包含条件 对任一个给定的三角形t = 蜀乃乃，有理b e l i e r 曲线( 2 0 1 ) 能够重新写 成三角形t 上如下的b e r n s t e i n b e l i e r 的形式： p ( t ) = ( u ( t ) ，y ( t ) ，w 7 ( ) ) ，0 t 1( 2 1 _ 1 ) 这里( u ( t ) ，y ( t ) ，( t ) ) 是点p ( t ) 相对于三角形t 的面积坐标如果有理参数曲 线p ( t ) 全部落在三角形t 的内部，那么对任意的t 0 ，1 】有( 矿( t ) ，y ( t ) ，( ) ) 的每个分量均为非负数 我们可以对有理曲线的b e r n s t e i n - b e l i e r 形式和有理曲线的齐次形式进行 转换，其转换由如下的变换来决定： 1 0 2 0 0 2 年中国科学技术大学硕士学位论文 第1 1 页 篁三塞童堡些竺竺垦望堕苎些 ! ! ；! 童堡苎丝竺堡! ! ! 丝 y ( ) = ( c 2 1 。( t ) + c 2 2 可 ) + c 2 3 训( t ) ) 伽( t ) ( 2 l - 2 ) 【w ( t ) = ( c 3 1 z ( ) + c a 2 y ( t ) + c 3 3 w ( t ) ) w ( t ) 畦引车x i 2 汀 ， ( 蜀，y d ，i = 1 ，2 ，3 分别是三角形t 的三个顶点t i ，i = l ，2 ，3 的直角坐标系中的 现在令 ， ( u ，”，w ) = 0 是一个次数为m ( m n ) 的区间代数曲线段( 见定 ， ( u ( ) ，y ( ) ，w 7 ( ) ) = f i j , ：l b 嚣j k ( u ( t ) ，y o ) ，矿( t ) ) = o ( 2 1 4 ) t + j + k = m 现在，我们假设 那么有 【岛k = 【路女，嚣女 ，i + j + k = m 坞女z 强( 矿( ) ，y ( t ) ，- 矿( f ) ) s 0 i + j + k f i ； b i j m k ( u ( t ) ，y ( t ) ，( t ) ) 0 i + j + k 利用式子( 2 1 2 ) ，经过运算后可以得到 这里 s 嚣j k ( u ( t ) ，y ( t ) ，( ) ) = ：掣“( t ) ( t ) ” ( 2 15 ) i + j + k r = 0 m n 塌 b 承( 矿o ) ，y ( t ) ，仰7 ( t ) ) = ，u 。，r n “( t ) ”( ) “ ( 2 1 6 ) h 与喝t 鸡* l + + k = m 像 ( 2 1 7 ) i + j + k = m 2 0 0 2 年中国科学技术大学硕士学位论文 第1 2 页 篁三塞查堡些竺竺垦塑堕苎丝 ! ! 兰垦堡垡墼塑竺竺壅壅 r = 0 ，1 ，m n ，以及c i j k , i + j + k = m 为常数由以上运算及式( 2 14 ) ，我 们得到了如下定理： 定理2 1 包含定理 一个区间代数曲线段包含一个有理参数曲线的充分条件为 辟= c b t 岛e 0 i + j + = m 2 2区间代数曲线的宽度 接下来的问题就是要让包含有理参数曲线的区间代数曲线段的宽度”( ， ) ( 定义1 4 4 ) 尽可能的小很容易看出，如果包含有理参数曲线的区间代数 曲线段的宽度越小，那么这种包含也就越好特别是，当包含的宽度w ( ， ) = 0 的话，那么区间代数曲线段【， ( u ，”，w ) = 0 就退化为一个普通的代数曲线段 ，( “，。，w ) = 0 这个时候，( u ，v ，w ) = 0 就是有理参数曲线的完全精确的隐式 化表达式从这个意义上来说，如此求得的区间代数曲线段就具有某种最优性 了 得 2 3区间代数曲线的求解 现在，有理参数曲线的区间隐式化问题可以陈述如下： 给定一个有理参数b e l i e r 曲线口0 u ，找一个区间代数曲线段亿4 印使 j ：条件f 2 1 8 ) 成立 2 ：条件f j 4 6 j 成立 3 7 区间代数曲线段的宽度4 刁达到最小 也就是说，区间隐式化问题转变成为了如下的一个优化问题 r a i n ( 强一) i + j + k = m s t 岛岛k 0 ，岛 ，嚣女0 ， r = 0 ，l ， l + j + 女= mi + j + k = m 蟛女岛k ， + j + k = m i n 忙a x 。j 塌k + 缘2 2 2 0 0 2 年中国科学技术大学硕士学位论文 第1 3 页 篁三童童堡堕竺竺垦堡堕苎些 ! ! 耋垦墼垡墼塑矍墼查矍 如上的这个优化问题是一个具有( m + 1 ) ( m + 2 ) 个变量的线性优化问题 为了更为有效的解决这个优化问题，接下来，把这一个优化问题转变为两个小 的线性优化问题，使得每一个小的优化问题具有( m + 1 ) ( m + 2 ) 1 2 个变量 我们按照如下的步骤进行，首先找到一个逼近给定有理参数曲线p ( t ) 的 近似代数曲线9 ( “，”，w ) = 0 。假设： 9 ( u ，”，t i ，) = 9 i j k b i j r n k ( u ， ，”) ( 2 3 2 ) i + j + k ：m 然后，重新给定区间代数战线的表达形式如下： 沁协一e b ，g i j k 十s 驯啄( “，”，w ) i a - j + k = m 这里s l j k , e 是非负实数 自然，包含条件( 2 1 8 ) 转变为 c o e s b ， 颤一b ，r = 0 1 ，m n ( 2 3 4 ) l + j + 女= m件j + k = m 这里“= f + 什 ：。吻9 巧女是常数 现在，我们用解两个线性优化问题来代替解一个线性规划问题( 2 3 1 ) 也就是以解决如下两个小的线性优化问题： 和 r a i n e z + j + 女= m s t 啄- 6 ， r = 0 ，l ，m n ( 2 3 5 ) i + j + k = m 嚣0 ， i + j 十k = m s o t i + j + k = m 南e b r ， r = 0 1 ，m n ( 2 3 6 ) “0 + k = n t ：j 0 ， 如上的两个规划问题能够很容易的被一些数学软件解决，像m a t l a b ，m a t h e - m a t i c a 都有专门用来解决线性规划问题的函数同样，对于式子( 2 3 3 ) ，我 们同样要求标准化其系数接下来的一个问题就是逼近有理曲线p ( t ) 的代数 曲线g ( “，”，w ) = 0 的寻找 2 0 0 2 年中国科学技术大学硕- 4 - 学位论文 第1 4 页 篁塞壁堕竺竺垦堡堕苎丝 塑璧些堡竺型墼些 2 4 有理曲线的近似隐式化 在解决线性优化问题( 2 35 ) ，( 2 36 ) 之前，首先得找到找到有理参数曲线 p ( ) 的一条近似隐式化曲线9 ( “，”，”) = 0 现在借用文献f 1 3 的思想来解决 这个问题。 假设有理参数曲线p ( ) 和近似隐式化方程分别由式子( 21 1 ) 和( 23 2 ) 给 出对隐式化方程的系数做标准化处理有： 9 = 1 ( 我们也可以用其它的模来标准化隐式化方程g 的系数) 定义近似隐式化的 逼近误差为： 一 fr l ( g ，p ) 2 上【g ( u ( 。) ，y ( ) ，( 晰出 ( 2 叫 也就是说，对于一个给定的有理参数曲线p ( t ) ，必须找到一个隐式化方程g 使得逼近误差a ( g ，p ) 达到最小 令 z = ( g m , o ，0 ，g m - 1 ，1 ，o ，g m - l ，o ，l ，g o ，m ，0 ，g o ，o ，m ) 以及 ( 亡) = ( u 0 ) m ，m u ( ) m - i y ( t ) 1 ，m v ( t ) m - - 1 ( t ) 1 ，y 0 ) m ，( ) m ) 这两个向量的维数均为f = ( m + 1 ) ( m 十2 ) 2 令x i 是向量。的第i 个分量 h i ( t ) 是向量 ( t ) 的第i 个分量，则有： g ( u ( t ) ，y ( t ) ，( t ) ) = 。俐= x i h i ( t ) t = l 从而可得 ( 9 ，p ) 2 = x a x t 这里a = ( a i j ) l 。! 是一个矩阵，其分量表达式为： 。：，= h i ( t ) h j ( t ) d t ，i ，j = l ，2 ，l 现在，近似隐式化问题简化为： r a s 圳i nx z a l | x t ：1 ( 2 删 s t 蚓1 = 1 。 2 0 0 2 年中国科学技术大学硕士学位论文 第二章有理曲线的区间隐式化 第1 5 页 5 25 一些例子 这里恻l 。= ：= ，z ；。 上面的优化问题的解就是矩阵a 的最小特征值所对应的特征向量解得 z 后，对。进行标准化处理，使得1 1 1 a , x 1 1 。! i 蚓= 1 ，然后将z 作为近似隐式 化曲线g ( u ，”，w ) = 0 的系数。 2 5 一些例子 在这一部分，给出一些例子用来说明有理参数曲线的区间隐式化的算法 例1 ：给定一个有理五次b e l i e r 曲线，其控制点和权重如下： 忙o ，g o ，w o ) = ( o ，0 ，1 ) ，扛1 ，玑，”1 ) = ( 1 ，l ，l ) ，( z 2 ，y 2 ， 2 ) = ( 3 ，2 ，4 ) ， ( x 3 ，y 3 ，w 3 ) = ( 4 ，3 ，2 ) ，( x 4 ，y 4 ，w 4 ) = ( 6 ，2 ，2 ) ，( x 5 ，y 5 ，w 5 ) = ( 8 ，0 ，1 ) 给定的三角形a t l t 2 t 3 为噩= ( 一0 5 ，o ) ，乃= ( 5 ，5 ) ，乃= ( 8 5 ，0 ) ，现用一个两 次的区间代数曲线段去包含有理参数曲线通过将参数曲线改写为面积坐标 的形式以后，首先得到了接近隐式化方程9 ( u w ) = 0 的系数，其系数为： z = ( 一0 1 1 6 6 ，一o 1 3 3 0 ，1 0 0 0 ，- 02 1 0 6 ，- 0 2 7 1 9 ，- 0 1 0 5 7 ) 通过计算优化问题( 2 3 5 ) ，( 2 3 6 ) ，得到 ，】( u ， ， ) = 一0 1 1 7 2 ，一0 0 9 9 7 1 b ；o o + - o 2 2 9 9 ，一0 0 5 1 9 6 b l o + 1 0 0 0 ，1 0 0 0 b 0 1 + 【_ 0 2 1 0 6 ，一o 2 1 0 6 1 b 如o + 一0 2 9 6 8 ，一0 2 4 4 8 1 b ；1 1 + 一o 1 1 7 2 ，一o 1 0 5 7 1 8 3 0 2 = 0 】 图片2 1 给出了这个例子的图象 区间代数曲线段的宽度为： ( ， ) = o 0 4 3 1 7 中间的那条曲线表示有理参数曲线，而阴影部分则表示包含此有理参数 曲线的区间代数曲线段 现在，将有理b e l i e r 曲线从中点分为两段，每一段代表一个新的有理参 数曲线分别寻找两条二次的区间代数曲线段去包含这两条新的有理参数曲 线用l e f t w ( f ) 来表示包含左半部分有理参数的区间代数曲线段的宽度， 用r i g h t w ( f ) 表示包含右半部分有理参数曲线的区间代数曲线段的宽度包 2 0 0 2 年中国科学技术大学硕士学位论文 第1 6 页 兰三童重望堕垡竺垦塑堕苎些 ! ! 兰三竺型三 图21 用二次的区间代数曲线段 含左半部分曲线的三角形t 1 t 2 t 3 由t l = ( 一0 5 ，一0 5 ) ，t 2 = ( 2 5 ，3 ) ， 码= ( 4 ，2 ) ，给出，而包含右半部分曲线的三角形由n = ( 3 ，2 , 2 ) ，马= ( 5 5 ，3 ) ， 乃= ( 8 5 ，一0 5 ) ，给出通过计算，可得包含前半部分参数曲线的区间代数曲 线为 卅( “， ，w ) = f o 0 4 5 9 6 ，0 0 8 9 7 7 b 刍o + - 0 1 6 7 5 ，一o 1 6 7 5 b 1 0 4 - 0 2 8 4 1 ，0 2 9 9 3 b 0 14 - 一1 0 0 0 ，一1 o o o 醯o + 0 2 0 4 1