（计算机软件与理论专业论文）几何造型中参数化与拟合技术的研究.pdf

山东大学博士学位论文 摘要 几何造型研究三维几何信息如何在计算机内表示、分析和综合。几何造型是 c a d c a m 内在的理论基础和关键技术，是随着航空、汽车等现代工业发展与计算 机的出现而产生与发展起来的一门学科几何造型作为信息技术的一个重要组成 部分，将计算机高速、海量数据存储及处理和挖掘能力与人的综合分析及创造性 思维能力结合起来，对加速产品开发、缩短设计制造周期、提高质量、降低成本、 增强企业市场竞争能力与创新能力发挥着重要作用不论是军事工业和民用工 业，建筑行业和制造加工业，机械、电子、轻纺产品，还是文体、影视广告制作 都离不开几何造型技术 曲线曲面造型是几何造型的核心之一曲线曲面造型研究在计算机内如何描 述曲线曲面，如何对它的形状进行交互式的显示与控制传统的数学方法虽然提 供了平面、圆柱面、圆锥面、球面等一类规则形状的曲面，但很难用以表达飞机、 轮船、汽车等现实生活中千姿百态的自由曲线曲面形状早期，在飞机和船舶的 制造工厂里，传统的设计方法要求设计与制造人员必须具备丰富的设计经验，付 出繁重的体力劳动，设计制造周期长，制造精度低，互换协调性差，不能适应现 代工业的发展曲线曲面造型就是应现代工业发展的要求而产生与发展起来的， 又对现代工业的发展起着巨大推动作用 曲线曲面造型的核心问题是计算机表示，即要找到既适合计算机处理且有效 地满足形状表示与几何设计要求，又便于形状信息传递和产品数据交换的形状描 述的数学方法在曲线曲面造型中，参数曲线曲面以其构造简单直观、易于显示 等特点而流行于世这种曲线曲面表示方法脱离了对坐标系的依赖，给许多应用 带来了极大的方便与非参数表示相比，参数曲线曲面能较好的满足形状数学描 述的要求长期以来，参数曲线曲面一直是描述几何形状的主要工具，早在2 0 世 纪6 0 年代初被美国波音公司的弗格森所采用，由c o o n s 、b s z i e r 等大师奠定其理 论基础c o o n s 皓面、b 6 z i e r 曲面、n u r b s ( n o n - u n i f o r mr a t i o n a lb - s p l i n e ) 瞌 面等不仅成为几何设计的主要工具，已被作为工业产品数据交换的 s t e p ( s t a n d a r df o rt h ee x c h a n g eo fp r o d u c tm o d e ld a t a ) 标准，也作为描述 山东大学博士学位论文 工业产品几何形状的唯一数学方法 参数曲线曲面造型按用户提供的初始信息不同可分为两类：一类是自由设计 方法，它只要求设计者根据构思给出一些控制点和控制参数来定义曲线和曲面， 然后在设计过程中允许改变这些控制点和参数来调整曲线和曲面的形状，直至它 们符合设计要求为止另一类是插值或逼近法( 工程上统称为拟合法) ，其特点是 给定一组离散点，要求生成的曲线或曲面要么通过所有这些点( 成为插值曲线或 曲面) ，要么以一定的精度贴近这些点( 称为逼近曲线和曲面) 这两类方法生 成的曲线曲面的形状都受参数化的影响参数化既决定了所表示曲线曲面的形 状，也决定了该曲线曲面上的点与其参数域内的点( 即参数值) 之间的一种对应 关系由此可见，参数化和插值与逼近技术是曲线曲面造型的基础问题，具有重 要的理论价值和实际意义围绕这两个问题，本文研究了参数曲线的最优多边形 逼近、参数曲线的最优参数化和高密度的海量数据点拟合等一类关键问题 本文的主要研究工作如下： 1 研究了参数曲线的最优多边形逼近 对传统的逼近算法参数逼近算法和几何逼近算法进行了讨论，找出了传 统算法的不足，并在几何逼近算法的基础上提出了多边形逼近新算法该算法采 用贪心技术，从端点开始，逐步定位逼近点除最后一段外，参数曲线与逼近线 段的最大偏移量总是等于给定的逼近精度，而传统算法不能确保这一点，导致传 统算法得到的逼近线段数目偏多对于凸参数曲线，给定逼近精度，证明了该算法 得到逼近线段的数目最少如果以生成的逼近线段的数目越少则算法越优为标 准，则该算法是最优的算法包含求解一个非线性方程对于b 6 z i e r 曲线，提出 了一种技术把算法涉及的非线性方程的次数降低两次，使得算法能够精确处理二 次曲线 文中用三个实例来对比该算法与传统子分算法的效果，验证了在同一逼近 公差下，该算法所需的逼近多边形的顶点最少算法直观可行，具有一定的实用 价值该算法的不足之处在于，对于非凸参数曲线，不能保证得到最优解，不过 得到逼近线段的数目与最优逼近的差额，不超过该曲线中拐点的数目，由于生产 实践中，常用的参数曲线含有拐点的数目有限，该算法能够得到近似最优解 1 i 山东大学博士学位论文 2 研究了参数曲线的最优参数化问题 讨论了参数曲线的弧长参数化，分析了有理重新参数化对参数曲线产生的影 响研究了利用有理重新参数化的自由度，求解参数曲线最优逼近弧长参数化的 问题提出了一种新的度量曲线的参数速度与弧长参数化接近程度的方法，基于 该方法求出了参数曲线的最优参数化最优参数化的参数速度偏离单位速度的最 大值达到最小与国外著名学者f a r o u k i 的算法相比，该算法取得的最优参数化的 参数速度偏离单位速度的最大值较小本文用三个实例来对比该算法与f a r o u k i 算法的效果，实例表明该算法比f a r o u k i 的算法效果好 该算法的不足之处在于，由于有理重新参数化调整参数速度的能力有限，对 于参数速度存在多次波动的曲线，最优参数化的参数速度不能保证处处逼近单位 速度 3 。研究了数据点的曲线重建问题 对曲线重建进行了讨论，研究了有序数据点的曲线重建问题对样条插值曲 线进行了分析，找出了样条插值曲线拟合高密度数据点的不足基于二次样条函 数，给出了一个拟合高密度的海量数据点的算法对于给定的一组有序数据点， 算法利用多边形逼近，将该组数据点分成一个个子集，在误差允许的范围内，每个 子集内的数据点近似在一条直线上由一段二次曲线拟合每个子集的数据点，全 部数据点由在连接处c - 连续的分段二次样条曲线拟合该算法保持了样条函数 结构简单，易于计算的优点，并在保持逼近精度的前提下，大大减少了插值曲线 的段数，提高了效率文中给出实例来对比该算法与传统样条插值算法的效果， 验证了该算法所需的插值曲线的段数远远少于传统算法 论文的主要创新点如下： 1 ) 提出了多边形逼近参数曲线的新算法对于凸参数曲线，在同样的逼近精 度下，该算法逼近得到逼近线段的数目最少，因而逼近满足最优条件： 除了最后一条边以外，多边形的每一条边到被逼近曲线的最大距离都恰 好等于给定的逼近误差，而传统算法不能确保这一点，导致传统算法得 到的逼近线段较多：当被逼近曲线为b e z i e r 曲线时，有一种技术来降低 本算法的计算复杂度，使得对2 次b e z i e r 曲线的逼近有精确解 i i i 山东大学博士学位论文 2 ) 对于有理重新参数化，提出了一种度量曲线的参数速度与弧长参数化接 近程度的方法基于该方法求出了参数曲线的最优参数化最优参数化的 参数速度偏离单位速度的最大值达到最小 3 ) 基于二次样条函数，给出了一个拟合海量数据点算法算法保持了样条函 数结构简单，易于计算的优点，并在保持逼近精度的前提下，大大减少 了插值曲线的段数，提高了效率 本文的主要贡献在于为解决几何造型中的上述关键问题，提供了新的方法 所提出的参数曲线的最佳多边形逼近算法，大大提高了计算机数控的工作效率； 所提出的最优逼近弧长参数化的方法，对于参数曲线的理论研究和生产实践都有 较好的意义；所提出的有序数据点的曲线重建，减少了组合曲线的段数，获得了 较好的效果 关键词： 参数速度：弧长参数化：单位速度；有理重新参数化；插值：逼近： 拟合 山东大学博士学位论文 a b s t r a c t g e o m e t r i cm o d e l i n gs t u d i e sh o wt od e s c r i b e ，a n a l y s i sa n dp r o c e s s i n g3 dd a t au s i n g c o m p u t e r s i ti n t e g r a t e st h eh i g hs p e e d , m a s s i v ed a t ap r o c e s s i n gc a p a b i l i t , yo f c o m p u t e ra n dt h ec r e a t i v ea b i l i t yo fh u m a nt o g e t h e r i tp l a y sa ni m p o r t a n tr o l ei n s p e e d i n gu pp r o d u c td e v e l o p m e n t ，s h o r t e n i n gt h ed e s i g nc y c l e ，i m p r o v i n gq u a l i t y , d e c r e a s i n gc o s ta n de n h a n c i n ge n t e r p r i s e sa b i l i t yo f m a r k e tc o m p e t i t i o n 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 ek e r n e lt e c h n o l o g i e so fg e o m e t r i c m o d e l i n g i ts t u d i e sh o w t od e s c r i b et h eg e o m e t r i cs h a p e so ff r e ec u r v e sa n ds u r f a c e s u s i n gc o m p u t e r s ， t h ek e r n e lp r o b l e mo fc n r v ea n ds u r f a c em o d e l i n gi sh o wt or e p r e s e n tf r e ef o r m c u r v e sa n ds u r f a c e sw i t hc o m p m e r s ，i e ，t of i n d 趾e f f e c t i v em e t h o dt os a t i s f yt h e g e o m e t r i cd e s i g ng o a l sa n dr e p r e s e n tg e o m e t r i cs h a p e sc o n v e n i e n t l y c o m p a r e d 、访n l n o n - p a r a m e t r i cr e p r e s e n t a t i o n ，t h ep a r a m e t r i cr s p r e s e l l t a t i o nh a sm a n ya d v a n t a g e s f o ral o n gt i m e , p a r a m e t r i ce u l w e sa n ds u l 茁a c e sh a v eb e e nt h ep r i m a r yt o o l si n g e o m e t r i cm o d e l i n ga n dh a v eb e c o m et h es t a n d a r do fs t e p ( s t a n d a r df o r1 1 1 e e x c h a n g eo f p r o d u c tm o d e ld a t a ) a c c o r d i n gt h ei n i t i a li n f o r m a t i o n , c l l l l v e sa n ds u r f a c e sm o d e l i n gc a nb ed i v i d e di n t o t w om e t h o d s o n ei sf r e ef o r md e s i g n i n g , b a s e do nc o n t r o lp o i n t sa n dp a r a m e t e r s ， d e s i g n e r sc a l ld e f i n ec b r v e sa n ds u r f a c e sa n dm o d i f yi n t e r a c t i v e l yu n t i lt h es h a p e s s a t i s f yt h ed e s i g ng o a l t h eo t h e ri st h et e c h n o l o g yo f i n t e r p o l a t i o na n da p p r o x i m a t i o n c u r v e sa n ds u r f a c e sr e c o n s t r u c t e df r o mt h eg i v e np o i n t sb yi n t e r p o l a t i o na r ec a l l e da s i n t e r p o l a t i o nc n l v e sa n ds u r f a c e so rb ya p p r o x i m a t i o nc a l l e da sa p p r o x i m a t i o nc u r v e s a n ds l r f a c e $ t h e s et w om e t h o d sa r ea 1 1i n f l u e n c e db yp a r a m e t e r i z a t i o n s oc u r v 髂 a n ds u r f a c e sp a r a m e t e r i z a t i o na n dt h et e c h n o l o g i e so fi n t e r p o l a t i o na n d a p p r o x i m a t i o na r et h ef o u n d a t i o no fg e o m e t r i cm o d e l i n g i nt h i sd i s s e r t a t i o nw eh a v e m a d eas y s t e m i ct h e o r e t i cr e s e a r c ho nc b l 、，e sa n ds u r f a c e sp a r a m e t e r i z a t i o na n dt h e t e c h n o l o g i e so fi n t e r p o l a t i o na n da p p r o x i m a t i o na n dh a v eo b t a i n e ds o m en e wi d e a s o nt h ef o l l o w i n gt h r e ea s p e c t s ： 1 t h eo p t i r e a lp o l y g o n a la p p r o x i m a t i o no f p a r a m e t r i cc u r v e si ss t u d i e d v 山东大学博士学位论文 t h et r a d i t i o n a la p p r o x i m a t i o na l g o r i t h m si n c l u d i n gp a r a m e t r i ca l g o r i t h ma n d g e o m e t r i ca l g o r i t h mi sd i s c u s s e d c o m p a r e dw i t hp a r a m e t r i ca l g o r i t h m , t h eg e o m e t r i c a l g o r i t h mc a l la c h i e v ef e w e ra p p r o x i m a t i o np o i n t s b a s e do nt h et r a d i t i o n a lg e o m e t r i c a p p r o x i m a t i o na l g o r i t h m , t h i s d i s s e r t a t i o n p r e s e n t s a n o p t i m a lp o l y g o n a l a p p r o x i m a t i o na l g o r i t h m f o rt h ec o n v e xp a r a m e t r i cc u r v e ，t h ea l g o r i t h mp r o v i d e sa p o l y g o nw i t ht h em i n i m a ln u m b e ro ft h ep o i n t st oa p p r o x i m a t et h ep a r a m e t r i cc u r v e w i t hag i v e nt o l e r a n c e f o re a c hl i n es e g m e n te x c e p tt h el a s to n eo nt h ep o l y g o n ，t h e m a x i m a ld i s t a n c et ot h ec u l w ei se q u a lt ot h eg i v e nt o l e r a n c e ，w h i l et h eu a d i t i o n a l g e o m e t r i ca l g o r i t h mc a l l tg u a r a n t e et h i s b e g i n n i n gf r o mt h ef i r s te n d p o i n to ft h e c u r v eo rt h el a s to n e ，t h ea l g o r i t h mm a yg e td i f f e r e n ta p p r o x i m a t i o np o l y g o n ，b u tt h e s a m en u m b e ro ft h ep o i n t s w i t ht h ep r o p e r t i e so fb d z i e rc u r v e , at e c h n i q u ef o r r e d u c i n gt h ec o m p u t i n gc o m p l e x i t yo ft h ea l g o r i t h mi sp r e s e m e d ，w h i c hm a k e st h e a l g o r i t h mh a s t h ep r e c i s es o l u t i o nf o ra p p r o x i m a t i n gt h eb 6 z i e rc u r v eo fd e g r e e t w o i nt h ed i s s e r t a t i o n ，t h r e ec o m p u t i n gi n s t a n c e sa r eg i v e nt oc o m p a r en e w a l g o r i t h m a n dt r a d i t i o n a la l g o r i t h m ，v e r i f y i n gt h a tn e wa l g o r i t h ma c q m r e st h el e a s tn u m b e ro f a p p r o x i m a t i o np o i n t sw i t h i nt h es a m eg i v e nt o l e r a n c e t h ea l g o r i t h m sd i s a d v a n t a g ei st h a t , t oc o n c a v ep a r a m e t r i cc u l n e s , t h ea l g o r i t h m c a l l tg u a r a n t e et h eo p t i m a lr e s u l t b u tt h ed i f f e r e n c eb e t w e e no u ra l g o r i t h ma n d o p t i m a lr e s u l ti m to v e rt h en u m b e ro fi n f l e c t i o np o i n t s a st h e r ea r el i m i ti n f l e c t i o n p o i n t so fac u l w ei np r a c t i c e ，s oo u ra l g o r i t h mc a l la c h i e v et h ea l m o s to p t i m a lr e s u l t 2t h eo p t i m a lp a r a m e t e r i z a t i o no f p a r a m e t r i cc u r v e si ss t u d i e d t h i sd i s s e r t a t i o ne x e r c i s e st h ef r e e d o m so f r e - p a r a m e t e r i z a t i o no f p o l y n o m i a lc u l v e s e g m e n t st oa c h i e v ea p a r a m e t r i cf l o w c l o s e n e s s t o u n i t - s p e e d o ra r c l e n g t h r e p r e s e n t a t i o nr a t i o n a lr e - p a r a m e t e r i z a t i o n so f ap o l y n o m i a lc b r v et h a tp r e s e r v et h e c l l r v ed e g r e ea n dp a r a m e t e rd o m a i na r ec h a r a c t e r i z e db yas i n g l ed e g r e eo ff r e e d o m t h eo p t i m a lr e - p a r a m e t e r i z a t i o ni n t h i sf a m i l yc a l lb ei d e n t i f i e db u tt h ep r e s e n t m e t h o dm a ye x h i b i tt o om u c hr e s i d u a lp a r a m e t r i cs p e e dv a r i a t i o nf o rm o t i o nc o n t r o l a n do t h e ra p p l i c a t i o n s i nt h i sd i s s e r t a t i o n ，ar e p a r a m e t e r i z a t i o nm e t h o dt oo p t i m a l 山东大学博士学位论文 p a r a m e t e r i z a f i o ni sp r e s e n t e da n dt h eo p t i m a lp a r a m e t e r i z a t i o ni nt h i sf a m i l ys a t i s f i e s t h a tt h em a x i m u md e v i a t i o nf r o mu n i t - s p e e di st h em i n i m u m 硼l i sa l g o r i t h m sd i s a d v a n t a g ei st h a tf o rah i g h e r - o r d e rc b r v et h a th a ss e v e r a l u n d u l a t i o n so fi t ss p e e da b o v ea n db d o wu n i t y , t h es c o p ef o r d a m p i n g t h e s e v a r i a t i o n sb yr e - p a r a m e t e r i z a t i o ni sr a t h e rl i m i t e d , o u rm e t h o dc a n tg u a r a n t e et h e p a r a m e t r i cs p e e do f t h eo p t i m a lp a r a m e t e r i z a t i o ni sc l o s et ou n i ts p e e de v e r y w h e r e 3 c u r v ef i t t i n gi ss t u d i e d s p l i n ef u n c t i o ni sw i d e l yu s e da n dh a sb e c o m et h ei m p o r t a n tm e t h o do f c o n s t r u c t i o nc u _ r v e sf i t t i n gh i 曲i n t e n s i t yd a t ap o i n t sw i t ht r a d i t i o n a ls p l i n ef u n c t i o n c a u s a st o om a n yc t f f v es e g m e n t sa n dh i 【曲c o s t s i nt h i sd i s s e r t a t i o n ，b a s e do n q u a d r a t i cs p l i n e , a na l g o r i t h mi sg i v e nt of i t t i n gh i g hi n t e n s i t yd a t ap o i n t s f i r s t , t h e a l g o r i t h ma p p r o x i m a t e sas e to fo r d e r e dp l a n a rp o i n t sw i map o l y g o na n dd i v i d e s t h e s ed a t ap o i n t si n t os u b s e t s t h ed a t ap o i n t si nas u b s e tl i eo nas a m el i n ew i t h i nt h e g i v e nt o l e r a n c e ，f i t t e db yaq u a d r a t i cc b i v es e g m e n ta n da l ld a t ap o i n t sa r ef i t t e db ya c q u a d r a t i cs p l i n ec u r v e t h ea l g o r i t h mp r e s e r v e ss p l i n ef u n c t i o n ss i m p l e c o m p u t i n gd e c r e a s e st h en u m b e ro fi n t e r p o l a t i o nc u r v es e g m e n t sa n dh o l d st h e a p p r o x i m a t i n ga c c u r a c y i tc a l lb eu s e di nf i t t i n gh i g hi n t e n s i t yd a t ap o i n t s t h ep r i m a r yc o n t r i b u t i o n so f t h i sd i s s e r t a t i o na r es u m m a r i z e da sb e l o w ： ( 1 ) t h ea p p r o x i m a t i o no f n u r b s c u i v e s 、) v i t i ll i n es e g m e n t si ss t u d i e d a no p t i m a l p o l y g o n a la p p r o x i m a t i o na l g o r i t h mi sp r e s e n t e d f o rt h ec o l i v ap a r a m e t r i ce l l l w e ，t h e a l g o r i t h mp r o v i d e sap o l y g o nw i t l lt h em i n i m a ln u m b e ro ft h ep o i n t st oa p p r o x i m a t e t h ep a r a m e t r i cc u r v e sw i t hag i v e nt o l e r a n c e f o re a c hl i n es e g m e n te x c e p tt h el a s t o n eo nt h ep o l y g o n , t h em a x i m a ld i s t a n c et ot h ec u r v ei se q u a lt ot h eg i v e nt o l e r a n c e ， w h i l et h et r a d i t i o n a la l g o r i t h mc a n tg u a r a n t e et h i s w i t ht h ep r o p e r t i e so fb 6 z i e r c u r v e , at e c h n i q u ef o rr e d u c i n gt h ec o m p u t i n gc o m p l e x i t yo ft h ea l g o r i t h mi s p r e s e n t e d , w h i c hm a k e st h ea l g o r i t h mh a st h ep r e c i s es o l u t i o nf o ra p p r o x i m a t i n gt h e b & , i e rc u l v eo f d e g r e et w o ( 2 ) t h i sd i s s e r t a t i o ne x e r c i s e st h ef r e e d o m so fr e - p a r a m e t e r i z a t i o no fp o l y n o m i a l i 山东大学博士学位论文 c u r v es e g m e n t st oa c h i e v ea “p a r a m e t r i cf l o w c l o s e n e s st ou n i t s p e e do ra r c l e n g m r e p r e s e n t a t i o n ar e p a r a m e t e r i z a t i o nm e t h o dt oa c h i e v et h eo p t i m a lp a r a m e t e r i z a t i o n o fp o l y n o m i a lb 6 z i e rc b i v e si sp r e s e n t e d t h eo p t i m a lp a r a m e t e r i z a f i o ni nt h i sf a n 币l y s a t i s f i e st h a tt h em a x i m u md e v i a t i o nf r o mu n i t - s p e e di st h em i n i m u m ( 3 ) b a s e do nq u a d r a t i cs p l i n e ，a l la l g o r i t h mi sg i v e nt of i t t i n gh i g hi n t e n s i t yd a t a p o i n t s t h ea l g o r i t h mp r e s e r v e ss i m p l ec o m p u t i n go fs p l i n ef u n c t i o n , d e c r e a s e st h e n u m b e ro fi n t e r p o l a t i o nc u r v es e g m e n t sa n dh o l d st h ea p p r o x i m a t i n ga c c u r a c y i tc a l l b eu s e di nf i t t i n gh i g hi n t e n s i t yd a t ap o i n t s t h i sd i s s e r t a t i o np r o v i d e sn e wm e t h o d st ot h e s ea b o v ek e yp r o b l e m si ng e o m e t r i c m o d e l i n g t h ea l g o r i t h mo fo p t i m a lp o l y g o n a la p p r o x i m a t i o no fp a r a m e t r i c c b r v e s w i l li m p r o v ew o r k i n ge f f i c i e n c yi nc n c ；t h eo p t i m a lp a r a m e t e r i z a t i o na l g o r i t h mi s v a l u a b l et ot h es t u d yo fp a r a m e t r i ct h e o r ya n dc a mp r a c t i c e ；t h ef i t t i n ga l g o r i t h m o b t m n sag o o dr e s u l t k e yw o r d s ：p a r a m e t r i cs p e e d ；a r c - l e n g t hp a r a m e t e r i z a t i o n ；u n i ts p e e d ；静 p a r a m e t e r i z 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 晷 i 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的科研成果对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明本声明的法律责任由本人承担 论文作者签名：聋盈翌 日期： 空! 墼 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文 ( 保密论文在解密后应遵守此规定) 论文作者签名：鸯斗导师签名： 日期：眩甚 山东大学博士学位论文 第一章绪论 几何造型是应现代工业发展的要求，以计算机的出现和发展为条件，又对现 代工业的快速发展起着巨大推动作用的一门学科几何造型中一种新的造型方法 一经出现，往往很快地反映到c a d c a m 系统中因此，几何造型在一个国家的发 展水平往往与该国工业发展水平紧密相关 s h i 2 0 0 1 本章首先综述几何造型的研究背景及目前的研究状况，然后阐述本文的主要 工作、刨新点与论文组织结构 1 1 几何造型的研究背景及研究状况 几何造型这个术语首先是在7 0 年代初期，随着计算机图形学、计算机铺助 设计和制造技术( c a d c a m ) 的迅速发展开始使用的它是几何学与计算机的完美 结合 几何造型包括两个分支第一个分支研究在计算机内如何描述一张曲面，如 何对它的形状进行交互式的显示与控制，即曲面造型第二个分支发展较晚，它 着重研究如何在计算机内定义、示一个三维物体，即所谓实体造型曲面造型与 实体造型是互相支持、互相补充的光有曲面造型，我们的目光就会停留在组成 物体的一张张表面上，无法去计算和分析物体的许多整体性质，如物体的体积、 表面积、重心等，也不能将这个物体作为一个整体去考察它与其它物体相互关联 的性质( 如两个物体是否相交? 如不相交，它们之间的最短距离是多少? ) 反之， 如果光有实体造型而无曲面造型，我们将无法准确地描述和控制物体的外部形 状 在历史上，曲面造型和实体造型是互相独立、平行发展的，彼此之间几乎没 有影响关于实体造型的理论的发展落后于曲线曲面，虽然近几年已经取得了很 大进展并进入实际应用，但仍不及曲线曲面理论那样成熟本文主要研究了曲线 曲面造型，因此我们先对实体造型研究背景及研究现状进行概述，然后较详细地 综述曲线曲面造型的研究背景及研究现状 1 1 1 实体造型 实体造型技术是基于计算机辅助设计与制造的需要而发展起来的。早在2 0 山东大学博士学位论文 世纪5 0 年代，美国麻省理工学院研制成功第一台数控加工机床后，人们就研制 a p t 零件编程语言，以描述被加工零件的外形，自动生成数控加工程序6 0 年代 以来，随着计算机图形学的发展，出现了各种绘图软件包，用计算机绘制各种工 程图纸，以减轻产品设计中手工绘图的繁重负担这些早期的绘图软件大都采用 线框式图形数据结构，即只存储所画图形的顶点以及各顶点间的连接关系它特 别适合于对图形进行各种几何变换和交互显示例如平移某一图形时，只需将这 一图形上各顶点的坐标作相应平移即可按线框结构中各顶点间原有的连接关系 生成新的图形然而随着c a d 技术的发展，当需要在计算机内完整地定义三维物 体时，这种线框数据结构很快暴露出它的弱点首先，由于该数据结构包含的信 息有限，无法实现图形的自动消隐其次，同一数据结构可能对应多个物体，产 生不定性第三，这种数据结构无法处理曲面物体的侧影轮廓线曲面物体的侧影 轮廓线与视线方向有关，它不应包含在物体的数据结构中然而它却是构成一幅 完整图形不可缺少的一部分第四，在生成复杂物体的图形时，采用线框式的数 据结构要求输入大量的初等效据数据愈多，不仅会加重用户的负担，更重要的 是很难保证这些数据的有效性和统一性，甚至可能导致“莫须有”的物体因此， 7 0 年代以来，人们开始致力于研究和发展实体造型技术 实体造型最初考虑如何将一些形状较简单、规则的物体如立方体、圆锥等体 经并、差、交等集合运算组成较为复杂的物体这类研究开始于6 0 年代末期从 1 9 7 3 年起，相继出现了英国剑桥大学c a d 小组中的i c b r a i d 的b u i l d 系统， 美国罗彻斯特大学h b v o e l c k e r 等人主持研究的p a d l 一1 系统，日本北海道大 学n o k i n o 主持研究的t i p s - i 系统，其基本体素是半空间不久，西德、法国、 瑞士等国也发展了类似功能的实体造型系统所有这些系统存在一个很重要的共 同特点：他们都在计算机内提供了对物体的完整的几何定义，因而可以随时提取 所需要的信息，支持c a d c a m 过程的任何一个方面，如计算机绘图、应力分析、 热流计算，数控加工等等实体造型系统的另一个重要特点是允许设计人员直接 在三维空间进行产品的设计、修改、观察，从而使设计活动变得直观、简单、高 效 如今经过二十多年的研究探索，实体造型的理论方法已经成熟，以实体造型 为核心的商品化c a d 软件被工业界广泛应用目前国际上著名的商品化c a d 系统 山东大学博士学位论文 如p r o - e ，u g ，c a t i a ，i - d e a s ，s o l i d w o r k s 等都是以实体造型为核心 t a n 9 2 0 0 0 1 1 2 曲线曲面造型 由已知曲线或曲面的数学方程生成的曲线曲面称为规则曲线曲面，例如圆 柱、圆锥、球面等，常用