（应用数学专业论文）cad中曲线曲面的插值与重建的研究.pdf

摘要 摘要 曲线曲面的插值与重建是计算机辅助设计和图形学中的重要课题本文针对四 次和五次p h 曲线的几何特征及h e r m i t e 插值问题与曲线曲面重建中的若干问题进 行了系统研究p h 曲线的应用十分广泛，如机械零件的设计、公路与铁路的设计以 及机器人运动轨迹生成等曲线曲面重建则是近几年来随着三维数据采集技术的飞 速发展而出现在计算机辅助设计、计算机图形学、医学领域的一个热点问题曲线曲 面重建的技术被广泛地应用于计算机图形建模，医学成像和逆向工程等领域本文 的主要研究成果如下 首先围绕b 6 z i e r 形式的平面p h 曲线的几何特征及h e r m i t e 插值问题，本文主 要贡献有： ( 一) 给出了平面四次b 6 z i e r 曲线为p h 曲线时其控制多边形满足的充分必要条件 本文从平面p h 曲线的定义出发，利用平面参数曲线的复数表示方法得到平面曲线 为p h 曲线的充分必要条件，并通过引入一些辅助顶点得到了控制多边形的几何特 征；讨论了g 1 的h e r m i t e 插值的几何构造方法给定两点两切向，首先构造控制顶 点p 2 的轨迹曲线段，在选定p 2 后，控制顶点 ，p 3 即被确定，从而得到要求的p h 曲线 ( 二) 平面五次p h 曲线可以分为两类：本原的和非本原的已有的研究工作主要针对 本原的五次p h 曲线，本文则主要讨论了非本原的五次p h 曲线与四次曲线类似， 推导了五次b 6 z i e r 曲线为非本原的p h 曲线时其控制多边形满足的充分必要条件， 进一步讨论了c 1 的h e r m i t e 插值的几何构造方法给定h e r m i t e 插值条件，文中给 出了一个关于控制多边形其中一条辅助边的一元四次方程，通过数值求解该方程和 几何约束条件求得控制多边形，并得到插值曲线 接下来围绕从点云重建曲线曲面的问题，本文提出了两个不同的算法： ( 一) 针对噪声较少且定向的法向信息可以由仪器或估计得到的点云，本文给出了一 个基于径向基函数的算法由于径向基函数的插值方法在处理重建曲面问题时会耗 费大量存储空间，因此在目前的p c 上往往只能处理很少数据的点云本文方法将点 浙江大学博士学位论文 云分割，对每一块分割得到的点云都用径向基函数方法拟合得到一个隐式函数，再 用函数混合的方法得到最终的拟合所有数据点的隐式函数利用m a r c h i n gc u b e s 方 法提取等值面得到三角网格曲面每个方块内点云的重建过程可以并行实现，因此 该方法适用于对重建速度要求较高的场合 ( 二) 当点云中含有较大的噪声时，法向不易估算，许多依赖法向进行重建的算法因 而失效，因此本文提出了一种基于d e l a u n a y 三角剖分的点云形状的定义，利用这个 概念进一步给出了一种曲线曲面重建算法通过细化点集的d e l a u n a y 三角剖分，使 得在点云中的点周围形成空间上的局部均匀采样；基于集合论中的基本概念定义点 云中的内点、外点和边界点，并且明确地定义了点云的形状，根据d e l a u n a y 三角剖 分细化时参数的选择可以得到不同层次的点云的形状；选择合适的参数得到形状 后，再通过薄化过程得到具有流形结构的曲线曲面 关键词：计算机辅助设计计算机图形学 多边形h e r m i t e 插值b 6 z i e r 曲线点云 d e l a u n a y 三角剖分v o r o n o i 图形状 p y t h a g o r e a n - h o d o g r a p h 曲线控制 曲线重建曲面重建径向基函数 a b s t r a c t a b s t r a c t i n t e r p o l a t i o na n dr e c o n s t r u c t i o no fc u r v e sa n ds u r f a c e sa r ei m p o r t a n tt o p i c si nt h e c a df i e l d s i nt h i sp a p e rw ep r o f o u n d l yr e s e a r c ho ni n t e r p o l a t i o no fp hc u r v e sa n ds u r - f a c er e c o n s t r u c t i o n p hc u r v e sa r ew i d e l yu s e ds u c ha sd e s i g n a t i o no fm e c h a n i s mp a r t ， h i g h w a ya n dr a i l w a y , r o b o t ，e t c s u r f a c er e c o n s t r u c t i o ni si n c r e a s i n gi m p o r t a n ti ng e o m e t r i cm o d e l i n gf o rg e n e r a t i n gs u r f a c e sf r o mc l o u dp o i n t sc a p t u r e df r o mr e a lo b j e c t s ，o f t e n b yl a s e rr a n g es c a n n e r sb u ta l s ob yh a n d h e l dd i g i t i z e r s ，c o m p u t e rv i s i o nt e c h n i q u e s ，e d g e d e t e c t i o nf r o mm e d i c a li m a g e s ，o ro t h e rt e c h n o l o g i e s t h em a i nc o n t r i b u t i o n sa lel i s t e da s f o l l o w s f i r s t l y , t h em a i na t t e n t i o ni sp a i do ng e o m e t r i cc h a r a c t e r i z a t i o na n di n t e r p o l a t i o no f p l a n a rp hc u r v e s w ep r e s e n tt h eg e o m e t r i cc h a r a c t e r i z a t i o no fc o n t r o lp o l y g o n sf o ra p l a n a rq u a r t i cb r z i e rc u r v et ob eap hc u r v e b a s e do nt h ed e f i n i t i o no fp hc u r v ea n d c o m p l e xr e p r e s e n t a t i o no fp l a n a rc u r v e ，w ed e d u c eg e o m e t r i cc o n d i t i o n si nt e r m so ft h e l e g so ft h ec o n t r o lp o l y g o nw h i c hg u a r a n t e et h ep hp r o p e r t y w ea l s od i s c u s st h ep r o b l e m o fg 1h e r m i t ei n t e r p o l a t i o nb yp l a n a rp hq u a r t i c s g i v e nt w o e n dp o i n t sw i t ha s s o c i a t e d t a n g e n td i r e c t i o n s ，w ef i r s tc h o o s et h em i d d l ec o n t r o lp o i n to ns o m ec u r v es e g m e n t s ，a n d t h e nf i n da n o t h e rc o n t r o lp o i n t sw h i c hs a t i s f yt h ed e d u c e dc o n d i t i o n s f o rp hq u i n t i c s ，a s t h e r ea r et w om a i nc l a s s e so f c u r v e s ：p r i m i t i v ea n dn o n - p r i m i t i v e t h ef i r s tc l a s si ss t u d i e d w i t hd e t a i lb yl o t so fr e s e a r c h e r s ，b u tf e ww o r kh a v eb e e nf o c u so nt h el a t t e rc a s e i nt h i s p a p e r , w ed e d u c et h eg e o m e t r i cc h a r a c t e r i z a t i o no fp l a n a rn o n - p r i m i t i v ep hq u i n t i c si nt h e s a m ew a ya sq u a r t i cc a s e a l s o ，w ed i s c u s st h ep r o b l e mo fc 1h e r m i t ei n t e r p o l a t i o nb y n o n - p r i m i t i v ep hq u i n t i c s ，g i v e nh e r m i t ed a t a ，b yn u m e r i c a l l ys o l v i n gaq u a r t i ce q u a t i o n w i t hr e s p e c tt os o m ea u x i l i a r ye d g e sw eh a v et h ec o n t r o lp o l y g o no f t h ep h q u i n t i c s e c o n d l y , t h em a i na t t e n t i o ni sp a i do nr e c o n s t r u c t i n gc u r v e sa n ds u r f a c e sf r o mu n o r - g a n i z e dp o i n tc l o u d s w ei n t r o d u c et w oa l g o r i t h m s f o rp o i n tc l o u d sw i t ho r i e n t e dn o r m a l s a n df e wn o i s e ，w ep r e s e n tar a d i a lb a s i sf u n c t i o nb a s e da l g o r i t h m a sd a t ai n t e r p o l a t i o nu s v 浙江大学博士学位论文 i n gr a d i a lb a s i sf u n c t i o na l w a y sp r o d u c el a r g ed e n s em a t r i xw h i c hs e e m st ob eb e y o n d t h ec a p a b i l i t i e so fm o s tp r e s e n tp c s a f t e rt h eb o u n d i n gb o xo ft h ep o i n tc l o u dw a sp a r t i t i o n e di n t op i e c e s ，r a d i a lb a s i sf u n c t i o n sw e r ei n t e r p o l a t e df o rp o i n t sf o re v e r yp i e c e ，a n d a ni m p l i c i tf u n c t i o nc a nb eg o tb ys u m m i n ga l lt h ef u n c t i o n sr e s t r i c t e db yw i n d o wf u n c t i o n s m a r c h i n gc u b e si st h e nu s e dt og e ts i m p l i c i a lm e s h t h em e t h o di sv e r ys u i t a b l e t ob ea p p l i e dt of a s tr e c o n s t r u c t i n gs y s t e mb e c a u s ei tc a nb ei m p l e m e n t e di np a r a l l e l f o r p o i n tc l o u d sw i t hm u c hn o i s ew h i c hc a nh a r d l yg e to r i e n t e dn o r m a l s ，w ei n t r o d u c ean e w d e l a u n a y - b a s e ds h a p ed e f i n i t i o na n da ne f f i c i e n ts u r f a c er e c o n s t r u c t i o na l g o r i t h m d e l a u n a yt r i a n g u l a t i o no fp o i n tc l o u d si sc o n s t r u c t e da n dr e f i n e ds u c ht h a ti t i su n i f o r m l ys a m p i e di nt h en e i g h b o r h o o do fe v e r yp o i n t i n n e rp o i n t s ，o u t e rp o i n t sa n db o u n d a r yp o i n t sa r e d e f i n e df r o mt h eb a s i cc o n c e p to fs e tt h e o r y , a n dd i f f e r e n tl e v e ls h a p e so fp o i n tc l o u d sa r e a l s ow e l l - d e f i n e dd e p e n d i n go nt h ec h o i c e so fp a r a m e t e rs e t t i n g t h ef i n a lr e c o n s t r u c t e d c u r v e so rs u r f a c e si so b t a i n e db yt h i n n i n gt h es h a p ew i t ha p p r o p r i a t ep a r a m e t e r k e y w o r d s ：c o m p u t e ra i d e dd e s i g n ，c o m p u t e rg r a p h i c s ，p y t h a g o r e a n - h o d o g r a p h ， c o n t r o lp o l y g o n ，h e r m i t ei n t e r p o l a t i o n ，b 6 z i e rc u r v e ，p o i n tc l o u d ，c u r v er e c o n - s t r u c t i o n ，s u r f a c er e c o n s t r u c t i o n ，r a d i a lb a s i sf u n c t i o n ，d e l a u n a yt r i a n g u l a t i o n ， v o r o n o id i a g r a m ，s h a p e v l 图目录 图日录 1 1 等距线应用实例 3 1 2 三维扫描过程及扫描得到的点云 5 1 3 旋转曲面重建【l 】 6 1 4 隐式曲面重建方法， 7 1 5 基于d e l a u n a y 三角剖分的曲面重建方法 9 1 6 参数化曲面重建方法1 0 2 1 三次p h 曲线及其控制多边形1 7 2 2 不含奇异点的平面四次b 6 z i e r 曲线的控制多边形2 l 2 3 三次p h 曲线升阶成四次p h 曲线2 3 2 4 含有奇异点的平面四次b 6 z i e r 曲线的控制多边形2 4 2 5 不含奇异点的p h 曲线的控制多边形2 7 2 6 不含奇异点的四次p h 曲线的g 1h e r m i t e 插值2 7 2 7 包含奇异点的p h 曲线的控制多边形，其中石d o 隹r 2 8 2 8 包含奇异点的四次p h 曲线的g 1h e r m i t e 插值，其中d 以。萑r 2 9 2 9 包含奇异点的p h 曲线的控制多边形，其中安r 3 0 2 1 0 包含奇异点的四次p h 曲线的g 1h e r m i t e 插值，其中五d o r 3 0 3 1 本原的平面五次p h 曲线的控制多边形3 7 3 2 退化的本原五次p h 曲线的控制多边形示意3 9 3 3 不合奇异点的平面五次p h 曲线的控制多边形4 2 3 4 仅包含一个奇异点的平面五次p h 曲线的控制多边形4 5 3 5不合奇异点的非本原p h 曲线的h e r m i t e 插值，其中0 萼4 6 3 6 不含奇异点的非本原p h 曲线的h e r m i t e 插值，其中p = 萼4 7 4 1 隐式函数表示的曲面5 l i x 浙江人学博士学位论文 x 4 2不同的径向基函数比较5 2 4 3 利用与不利用附加约束条件结果比较豳5 4 4 4 法向估计【3 1 5 4 4 5 重建过程示意5 7 4 6f o o t 模型5 8 4 7v e n u sh e a d 模型5 9 4 8 d i n o s a u r 模型6 0 4 9 b u n n y 模型6 0 4 1 0r o c k e ra r m 模型6 0 5 1 几何独立6 2 5 2 三维空间中的单形6 2 5 3 v o r o n o i 图和d e l a u n a y 三角剖分6 3 5 4 点云的形状构造示意图6 5 5 5 曲线重建过程示意图6 6 5 6 对原先标记的边界点的处理6 7 5 7 删除引起非流形结构的边界点( c 点) 6 8 5 8 不同的参数下的口形与本章定义的形状的比较6 9 5 9 闭曲线上采样得到的点云的形状及曲线重建6 9 5 1 0 开曲线上采样得到的点云的形状及曲线重建7 0 5 1 l “t ”字形的点云的形状及重建的曲线7 0 5 1 2 自交的点云的形状及重建的曲线7 l 5 1 3 不同的参数下的口形与本章定义的形状的比较7 l 5 1 4 三维点云的形状及重建的曲面7 2 5 1 5 三维曲面的重建7 2 表目录 表目录 4 1 各模型重建时间5 9 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得浙江大学或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名：签字日期：年月日 学位论文版权使用授权书 本学位论文作者完全了解浙江大学有权保留并向国家有关部门或机构送交 本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权浙江大学可以将学位 论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：导师签名： 签字h 期：年月日签字日期：年月 日 致谢 致谢 衷心感谢我的导师汪国昭教授在攻读博士学位期间，汪老师一直在学习和研 究方面给我精心的指导和莫大的帮助，使我在专业知识上有了更多的积累，在科研 能力上有了很大的提高，将使我终身受益特别感谢数学系的黄兆镇老师在论文写 作过程中给予的指导和帮助，黄老师对学生耐心且无私的指导使我受益良多，更为 我树立了良好的榜样 在论文的撰写过程中，曾得到许多老师和同学的帮助特别感谢课题组的王国 瑾教授、刘利刚副教授和杨勋年副教授等老师在各方面所给予的指导和帮助 感谢李亚娟、方美娥、邓重阳、辛士庆、沈莞蔷、徐岗、陆利正、曾兰玲、武丹、 舒振宇、胡倩倩、计忠平、赵宏艳、徐惠霞、柯大观等师兄师姐对我的帮助和鼓励； 感谢胡建伟、曹娟、朱平、陈中贵、张磊、周红光、陈军、周联、张冬梅等各位同学 对我的关心和帮助，同时感谢课题组讨论班的每位成员，大家共同学习，互相帮助， 度过了许多美好时光感谢卢福军、金方其、陈平、叶杨斌、曾九孙等同学在我研究 生期间在学习生活上对我的关心和帮助 特别感谢我的爷爷奶奶、爸爸妈妈、妹妹以及其他亲友一直以来对我的关怀爱 护，你们总是给予我充分的理解、支持与鼓励，使我能够克服困难、不断进取、完成 学业 谨向所有关心我学业的师长、同学和亲友表示衷心的感谢! 方林聪 2 0 0 9 年l o 月于求是园 绪论 第一章绪论 计算机辅助设计( c o m p u t e ra i d e dd e s i g n ，c a d ) 技术兴起于2 0 世纪5 0 年代， 彻底改变了传统的从手工绘图，凭图纸组织整个生产过程的技术管理方式；形成了 在图形工作站上交互设计、用数据文件存储与交换产品的定义、在统一的数字化模 型下进行产品的设计、分析计算、工艺计划到最后数控加工的一揽子解决方案问经 过几十年的发展，c a d 技术作为成熟的普及技术已在企业中广泛应用，几乎覆盖各 个行业，机械、建筑、服装等行业应用得更加明显和突出，并已成为企业的现实生产 力 逆向工程( r e v e r s ee n g i n e e r i n g ，r e ) 是随计算机技术的发展和成熟及数据测量 技术的进步而迅速发展起来的它是在无设计图纸或图纸不完整以及无c a d 模型 的情况下，从现有物理模型或实物零件，利用数字化及c a d 技术重新构造c a d 模 型的过程【5 】它改变了c a d 系统从图纸到实物的传统设计模式，为产品的快速开 发及原型化设计提供了一条新途径，并广泛应用于机械、航空、汽车等领域随着 c a d r c a m 技术的广泛应用，相比之下，在如何准确、有效地从实物样件上采集复杂 三维表面数据，进而能快速地转变成高质量的计算机软件中的三维数学模型一这 一应用上仍然存在很大的障碍 1 1 c a d 中曲线曲面的表示方法 给定一组有序的点 p f j ，构造顺序通过这些数据点的曲线或者曲面，称为对 这些数据点的插值( 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 r i n g ) 传统的数据拟合要求首先对数据点进行参数化，然后通过 反求一些待定系数来确定多项式曲线曲面，若参数化方法不同，即使利用相同的拟 合方法也会得到不同的曲线曲面比较经典的参数化方法有：均匀参数化、累加弦长 参数化、向心参数化等由于采用的基函数不同，不同的多项式插值方法会得到不同 浙江大学博士学位论文 表示形式的曲线h e r m i t e 插值是最常见的多项式插值法之一，它不仅对数据点进行 插值，同时还在其导矢信息之间插值通常h e r m i t e 插值不是对玎+ 1 个点而是在两 个数据点及其导矢之间进行插值数据的拟合是曲线曲面造型的一个重要技术 在目前的c a d 系统中广为应用的是参数多项式表示的曲线和曲面将曲线 曲面表示为参数的矢函数方法最早是于1 9 6 3 年由美国波音( b o e i n g ) 飞机公司的 f e r g u s o n 提出来的，该方法引入三次参数曲线定义了双三次的曲面片1 9 6 4 年，美 国麻省理工学院( m a s s a c h u e s e t t si n s t i t u t eo ft e c h n o l o g y ，m i t ) 的c o o n s 提出了具有 一般性的曲面描述方法，并于1 9 6 7 年进一步推广，即为c o o n s 双三次曲面片同时， 于1 9 6 4 年由s c h o e n b e r g 提出的样条函数理论提供了解决曲面片之间连接问题的方 法法国雷诺( r e n a u l t ) 汽车公司的b 6 z i e r 于1 9 7 1 年提出了由控制多边形定义曲线 的方法b 6 z i e r 曲线，曲线的形状便于控制且简单易用1 9 7 2 年，d eb o o r 给出了关 于b 样条的一套标准算法两年后，美国通用( g e n e r a lm o t o r s ) 汽车公司的g o r d o n 和r i e s e n f e l d 提出的b 样条曲线曲面，由于具有许多的优良性质，在c a d 造型系 统中得到了广泛的应用2 0 世纪8 0 后期，非均匀有理b 样条( n o n u n i f o r mr a t i o n a l b s p l i n e ，n u r b s ) 方法开始成为了c a d 系统中标准形式 2 0 世纪9 0 年代开始，随着数据采集技术的飞速发展，c a d 应用中对传统的数 据拟合方法提出了巨大的挑战由于三维扫描仪等数据采集设备可以在短时间内大 量采集数据点，而且这些数据点是无序的，很难直接利用传统的参数曲线曲面来拟 合于是，如何从散乱的点集自动地生成它们的几何模型并进行处理成为了一个研 究热点，这个过程即为反向工程或逆向工程同时，随着计算机存储与渲染技术的发 展，曲面的离散表示也受到越来越多的关注，即用点云或者多边形网格来表示曲面， 并形成了数字几何处理( d i g i t a lg e o m e t r yp r o c e s s i n g ) 这一新学科网格曲面由于具 有表现能力丰富、便于进行几何操作、易于在硬件上实现等许多优点而得到越来越 多的应用，直接构造网格曲面来拟合散乱点集的技术也得到了快速的发展，成为了 新兴的曲线曲面造型技术进入2 l 世纪，点云渲染技术的兴起跟使得点云模型也越 来越多的被关注，点云曲面抛弃了网格曲面中的拓扑连接关系，表达形式自由、简 单且不受连续性约束，今后将会得到更多的发展 1 2p h 曲线综连 a ) 帆m 靖 桥f b ) 镘镕 ( 0 h m n 图1 1 等距线应用实例 在c a d 的很多领域涉及到曲线弧长和等距线的计算问题，如机械零件昀设 计、公路与铁路的设计以及机器人运动轨迹生成等( 如田l1 ) 一般情况下，多项 武曲线的弧长和等距线不具备有理形式为此，f a r o u k i 等 6 1 引入7 毕选哥拉斯速端 ( h t h a g o r e a nh o d o g m p h ，p h ) 曲线，即该曲线的弧长和菩距线的表达武中分母根号 内为完全平方曲一类参数曲线，它是一类具有优良特性的多项式曲线，可用于解决 许多实际应用问题，尤其是在计算机散字控制( c o m p u t c r n u m e r i c a l c o n t r o l ，c n c l 机器方面例如，曲线弧长和等距线的精确计算问题” 此后，f a r o u k i 又把平面p h 曲线推广到空间p h 曲线与曲面，并给出了具有有 理等距面的可晨曲面的显示表达与此同时，他对p h 曲线儆7 进一步的理论与 应用研究p ”l ，并把其弧长函数是朦参数多项式函数这一优点成功地应用于数控加 工和r 业机器人中1p o r m a n n i ”依据投影对偶表示和包络技术，用p h 思想推宰 出t 有理曲线曲面的等距面具有精确有理表示的条件m a r t i n 等l 研究7 扫掠体 浙江大学博i ：学位论文 的等距曲面，并给出了自交检测方法f a r o u k i 等 1 4 】对凸多面体、旋转体和简单轮 廓线的拉伸体这三种简单实体的表面均给出了等距面的精确表示m a r t i n 1 5 1q , 正明了 d u p i n 曲面( 即曲率线为圆弧的曲面) 的等距曲面也是d u p i n 曲面p e t e r n e l 等【1 6 】利用 l a g u e r r e 几何模型间的几何变换，给出了构造任意有理曲面的p h 曲面的几何方法 另一方面，由于p h 曲线的一系列优点，实际应用中需要对已知数据点构造 h e r m i t e 插值的p h 曲线借助于巧妙的代数运算一平面参数曲线的复变模型【1 0 1 和 空间参数曲线的四元数模型【1 7 _ 2 0 1 ，p h 曲线的理论与应用研究得到进一步的发展 一般三次参数曲线的h e r m i t e 插值为d e b o o r 2 1 】所研究m e e k 等 2 2 1 给出了平面 分段三次p h 曲线的g 1 插值算法1 9 9 5 年f a r o u k i 等【2 3 】利用复分析的方法，求解出 五次p h 曲线在h e r m i t e 插值条件下的曲线形式，并通过“旋转数”的计算来选择四 个可行解的最优解；此后，f a r o u k i 2 4 1 又提出了通过“弯曲能量”的方法来衡量四个 可行解的形状性质m o o n 等【2 5 】则构造出一种新的特殊形式的曲线，用于计算五次 p h 曲线在h e r m i t e 插值条件下的可行解，并通过研究这种形式下曲线参数的符号选 择与可行解的性质特性之间的关系，找到了一种不需要对形状特征进行附加计算的 方法，选择最优的可行解c h o i 等 2 6 1 研究了衡量插值数据点得到的三次和五次p h 曲线的相似度后，进一步提出了用曲线的拓扑结构作为衡量标准来选择最优解的 方法【2 7 1 j i i t t l e r 2 8 】讨论了七次p h 曲线的h e r m i t e 插值k o n g 等 2 9 1 研究了c 1 连续的 p h 曲线的h e r m i t e 插值问题p e l o s i 等 3 0 1 提出了通过指定控制多边形和节点序列来 构造c 2 连续的平面五次p h 样条曲线的方法 f a r o u k i 等 s , 3 1 , 3 2 、p e r w a s s 等1 3 3 和p e l o s i 等【3 4 】对空间p h 曲线的h e r m i t e 插值问 题也进行了深入研究同时，f a r o u k i 等 3 5 1 提出了空间五次p h 曲线的h e r m i t e 插值 问题的最优解的三种选择标准，并讨论了三种标准在实际曲线设计中的不同应用 p h 曲线也被用来构造一些特殊类型的曲线h a b i b 等 3 6 , 3 7 】研究了用五次p h 曲 线光滑地连接两个曲线段的方法w a l t o n 等 3 8 , 3 9 1 提出了用平面五次p h 曲线来构造 螺线的方法a i t h a d d o u 等t 4 0 19 用平面有理p h 曲线来构造椭圆和卵形曲线等特殊 曲线w a l t o n 等 4 q 给出了一种连接两段五次p h 螺线的g 2 连续的方法i r 等 4 2 1 则 比较了圆弧样条和五次p h 曲线用来逼近曲线的等距线的方法 针对从中轴变换( m e d i a la x i st r a n s f o r m ，m a t ) 重建边界曲线问题，m o o n 4 3 1 在 4 论 m i n k o w s k i 度量下定义7 m i n k o w s k i p y t h a g o r e a n h o d o g m p h ( m p h ) 曲线k i m 等讨 论了c 。连续条件的四次m p h 曲线的h e r m l t e 插值州趣k o s i n k a 等m 】研究7 连 续的三次m p h 曲线的h e r m i t e 插值问题打等1 提出7 通过给定一条平面三次曲 线和某点处韧向条件下构造p h 曲线和m p h 曲线的方法 c h o i 等1 4 7 1 证明7p h 曲线的“w e i e r s t m s s 逼近定理”，即对于任意一条二维、 三维欧式空闻或三维m i n k o w s k i 空间中的c 1 连续的曲线，都存在相应空间中的一 条p h 曲线一致地逼近该曲线f a r o u k i h 8 删对p h 曲线的研究现状作了很好的总结 1 3 曲线重建技术 f 盔 圈、：冬，：， 围i2 三维扫描过程及扫描得到的点云 曲线曲面重建是近几年来出现在计算机辅助设计，计算机图形学，医学成像等 领域中的一个热点问题其目的在于寻找某种数学描述或模型，精确、简洁地表示所 输入的点云数据( 通过澈光扫描仪，或者医学图像的特征检测获得，如图l2 ) ，并以 此为基础对点云数据所在的曲线曲面进行分析，修改和绘制曲面重建的技术有着 广泛的应用，其中逆向工程是其中的一个重要的应用领域曲线重建技术常常被用 来作为曲面重建的基础工作l 姐”1 ( 如图i3 ) 蒯拶耘 圈13 旋转曲面重建 到目前为止，现有的曲线重建工作大致可分为两类一类是先建立曲线模型， 再通过求解这个模型得到重建曲线如f a n g 等”1 用弹力模型，把已知数据点作为 约束条件，直接求解曲线参数，得到重建曲线；l i u 等【5 ”用切向流使得种子参数曲 线生长 导到重建曲线，w a n g 等f 5 4 ) 用s d m ( s q t l a l - e d i s t a n c e m i n i m i z a t i o n ) 方法选 代求解优化问题得到重建曲线又如t a u b i n 等利用隐式单纯模型重建出一条简 单曲线，y a n g 等阿1 利用动态隐武b 样枭曲线模型，得到重建的b 样杂曲线，钟纲 等哪j 利用点云构造势函数，使得初始曲线模型沿势函数的梯度方向运动以得到重建 曲线模型熏建万洼一般需要优化或迭代求解，对于大量散据或者噪音过多的点集， 教果币太理想，而且大多需要人工指定初始曲线，因此所得的结果依赖于初始曲线 的选取另一粪方法是先列点云进行预处理，再用已有的有序点到的曲线拟台万浩 重建曲墁如l e e 等川用移动最小：乘( m o v i n gl e a s ts q u a r e ，m l s ) 方法”】细化点 云- 这种万， 需要对每个点进行两次的局部最小二乘运算，计算量非常大p o t t m a n n 等1 5 0 ) 将点云投影到。f 面剥格，咀生成t 值图像，g o s h t a s b y 等叫利用点云构造势函 鼓并生成图像，他们再用图像处理的方法细化点云并重建曲线；钟纲等i 将点云投 影在平面网榕上，然后选取初始点，运步确定跟踪方向以跟踪重建曲线这些方法获 得的重建曲线并不能很好地反映点云的形状，并且重建曲线的准确性甚至正确性受 到网格分辨率的髟响 1 4 曲面重建技术 从重建的结果束分，曲面重建技术可以分为几何重建与拓扑重建几何重建技 术是随着基于点的渲染【蝴l 和几何处理技术m 。州的发展而产生的，他们将点作为 基本图形单元对模型进行处理本质上来说，几何重建也可以理解为点云的击噪方 浩，如参考文献 7 , - 7 e 1 拓扑重建是指从扫描得到的点云得到乡边形网格曲面模型的 过程，本文后面所讨论的曲面重建即指拓扑重建方法 曲面重建技术的研究工作已经有2 0 来年的历史，目前的主要方法大致可以归 为以下几类：基于隐式曲面的重建方洁、基于计革几何的重建方法、参数化曲面重 建方法等国内的王静等1 7 ；1 、武剑洁等，钟纲i 州和董辰世【删等，国外的s c h a a l l 等1 8 ”，d 叫等阱1 先后对点云的曲面重建方法作7 比较全面的总结 4 1 晦武曲面重建方法 ( a ) 孽i t i( c ) 重建目i 圈14 睥武曲面重建方法 晦式函数表示曲面的方法由于使得许多复杂的几何操作变成简单的代数运算而 广受欢迎”1 用隐面散来重琏曲面的最大优点在于它们的数据修复能力，印曲面补 萝-色歹 浙江大学博r j ：学位论文 洞( 如图1 4 ) 而且用隐式方法重建曲面对带噪点云和拓扑较复杂的曲面比基于计算 几何的方法更加鲁棒 大多数隐式曲面重建的方法都是源于b l i n n 钳】混合一些基本隐式函数的想法 m u r a k i s s _ ；f r 用高斯函数的线性组合从点云拟合得到隐式曲面h o p p e 等【8 6 】利用到最 近点的切平面的距离来局部地估计有向距离函数l i m 等【8 7 】首先借助d e l a u n a y 四面 体剖分得到所有的球的初始大小以构造球函数，然后求解一个非线性的优化系统得 到隐式曲面s a v c h e n k o 等【8 8 】、c a r r 等【2 1 、d i n h 等【8 9 】、t u r k 等 9 0 1 利用全局的径向基 函数( r a d i a lb a s i sf u n c t i o n ，r b f ) ，而m o r s e 等 9 11 、k o j e k i n e 等【9 2 】和o h t a k e 等1 9 3 则 利用紧支集的径向基函数来重建隐式曲面这些方法在选择径向基本函数的中心时 一般选择点云中的点，而s a m o z i n o 等【蚓则选取点集的v o r o n o i 顶点作为基本函数 的中心，得到了很好的效果，且利用一些点聚合的方法是得重建的速度得到了很大 的提高 水平集方法【9 5 】是另外一种可以有效地重建出有向距离函数的选择，然而，当重 建精度的要求较高时，这个方法在时间和空间复杂度上均不具有优势基于m l s 的 方法 7 4 , 9 6 9 8 1 的优点在于它们是局部的，与数据点数量无关，而且可以直接计算曲面 上的每一个点的位置但是由于这个方法需要求解非线性的移动最小二乘问题，使 得一些实际操作变得十分地耗费资源m p u ( m u l t i 1 e v e lp a r t i t i o no f u n i t y ) 方法【叫首 先构造八叉树，然后利用二次函数对数据进行局部拟合，最后利用权函数将所有函 数混合得到隐式曲面童伟华等f l o o 】先借助八叉树及其细分过程，从无结构散乱点数 据集构造t 网格，利用曲面拟合模型将曲面重构问题转化为最优化问题；然后基于 隐式t 样条曲面将最优化问题通过矩阵形式表述，依据最优化原理将该问题转化成 线性方程组，通过求解线性方程组解决曲面