（应用数学专业论文）基于噪声样本点的曲线、曲面重构.pdf

中文摘要 曲线曲面重构是逆向工程中研究的重要问题之一。某些曲面重构问题，可以 转化为曲线重构问题来研究，如：回转曲面、螺旋曲面、轮廓曲面等。 本文着重研究了一类光滑曲线曲面的重构问题，提出了基于噪声样本点的曲 线、曲面的重构算法。曲线重构算法通过构造加细邻域细化点云，然后对点云进 行排序，从而可借助于曲线拟合方法构造出一条光滑曲线；曲面重构算法，对每 一个噪声样本点找出中心点，在对这些新点修剪，修剪后的新点再用c o c o n e 算 法构造出曲面。若采样点较稀疏，可对其加密插值，从而构造出较光滑的曲面； 若采样点较稠密，将会产生许多密集的微小三角片，一方面，产生信息冗余，另 一方面，在曲率变化大的地方，不能体现出尖角、尖边等特点，针对这种情况， 本文的做法是对生成的密集小三角网格用拓扑学知识进行网格简化。本文还给出 了多个曲线、曲面重构的算例，用以验证上述算法的有效性和正确性。 关键词：逆向工程噪声样本点曲线曲面重构网格优化 a b s t r a c t t h er 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 si so n eo ft h ei m p o r t a n tp r o b l e m si n r e v e r s ee n g i n e e r i n g s o m e t i m e s ，t h er e c o n s t r u c t i o no fs u r f a c ec a l lb ec h a n g e di n t o 8 u r v er e c o n s t r u c t i o n s u c ha s ，s u r f a c e so fr e v o l u t i o n , h e l i c a ls u r f a c e ，p r o f i l es u r f a c e ， a n ds oo n t h i sp a p e rf o c u s e so nc u r v ea n ds u r f a c er e c o n s t r u c t i o nf r o mn o s i ys a m p l i n g sa n d p r o p o s e dt h ea l g o r i t h mt og e tt h e c u r v ea n ds u r f a c e i nt h ea l g o r i t h mo fr e c o n s t r u c t i o n , t h er e f i n e dn e i g h b o u r h o o dc a nb ec o n s t r u c t e ds ot h a tt h ed a t ap o i n ti sm o v e dt oan e w p o s i t i o no nt h i sa p p r o x i m a t e dc u r v e ，s ot h ep o i n tc l o u di st h i n n e rt h a no l dp o i n t c l o u d t h e nt h ep o i n tc l o u dc a nb eo r d e r e d f i n a l l y , as m o o t hc u r v ec a nb e r e c o n s t r u c t e db yu s i n gc u r v ef i t t i n gm e t h o d i ft h es a m p l e sa r es p a r s e ，as m o o t h s u r f a c ei sp r o d u c e db yi n t e r p o l a t i o n w h i l et h es a m p l e sa r ed e n s e ，an u m b e ro fs m a l l t r i a n g l a rm e s h e sw i l lb ep r o d u c e d o no n eh a n d ，i tw i l lp r o d u c er e d u n d a n ti n f o r m a t i o n o nt h eo t h e rh a n d , t h ec h a r a c t e r i s t i c so ft h es h a r pc o m e r sa n ds h a r pe d g e sc a n tb e r e f l u c t e dw h e nt h ec u r v a t u r eh a sab i gc h a n g e i nl i g h to ft h i ss i t u a t i o n ；t h ea p p r o a c h o fm e s ho p t i m i z a t i o ni s g e n e r a t e df o rt h e s m a l lt r i a n g l a rm e s h e sb yt o p o l o g y k n o w l e d g e s o m ee x a m p l e sa leg i v e nh e r et os h o wi t sv a l i d i t ya n de f f e c t i v i t yi n r e c o n s t r u c t i n gc u r v e so rs u r f a c e sw i t hd i f f e r e n ts h a p e s k e yw o r d s ：r e v e r s ee n g i n e e r i n g ，n o i s ys a m p l i n g s ，c u r v ea n ds u r f a c e r e c o n s t r u c t i o n , m e s ho p t i m i z a t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：捐秀荚 签字日期：2 d d g 年6 月2 日 学位论文版权使用授权书 本学位论文作者完全了解丞凄盘鲎有关保留、使用学位论文的规定。 特授权苤凄盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：胡秀荚 导师签名： 咖伸牟磊 签字日期：- 2 嬲年舌。月，2 日 签字日期：2 o o 净彩月z e l 天津大学硕士学位论文 基于噪声样本点的曲线与曲面的重构 1 1 概述 第一章绪论 曲线与曲面重构所研究的问题可描述如下：对未知曲线通过采样得到一组数 据点，曲线重构就是从这组采样数据出发，以尽可能高的精度逼近原始曲线，并 满足某种连续性要求。进行曲线重构，广泛采用的方法是对数据点进行曲线插值 或拟合( 见2 1 节) ，然而曲线拟合要求数据点是有序的，也就是说要求数据点集 中的点沿着原始曲线有一定的先后次序，当采样数据点无序时，比如通过采样得 到的数据是散乱点时，便无法直接对数据点进行曲线拟合。 曲线与曲面重构是逆向工程的形状反求中所研究的重要问题，逆向工程技术 与传统的正向设计存在很大差别。 正向工程是一个“从无到有”的过程。设计人员首先在大脑中构思产品的外 形、性能、大致的技术参数等，然后通过图纸或在c a d 技术的帮助下建立产品 的三维数字化模型，最后将这个模型转入到制造流程中去，完成产品的整个设计 制造周期。对每一组件来说，其正向工程的流程如图1 1 所示。 b i g1 - 1 组件的正向工程开发流程 逆向工程产品设计可以认为是一个“从有到无”的过程。简单地说，逆向工 程产品设计就是根据已经存在的产品模型，反向推出产品设计数据( 包括设计图 纸或数字模型) 的过程。从这个意义上来说，逆向工程这概念在工业设计中已 经使用了很久。早期的船舶工业中常用的船体放样设计就是逆向工程的很好实 例。 一般来说，产品逆向工程包括形状反求、工艺反求和材料反求等几个方面， 在工业领域的实际应用中，主要包括以下几个内容： ( 1 ) 新零件的设计，主要应用于产品的改型或仿型设计； 天津大学硕士学位论文基于噪声样本点的曲线与曲面的重构 ( 2 ) 已有零件的复制，再现原产品的设计意图； ( 3 ) 损坏或磨损零件的还原； ( 4 ) 数字化模型的检测，例如检验产品的变形分析、焊接质量等，以及进模 型的比较。 逆向工程技术为快速设计和制造提供了很好的技术支持，已经成为制造业信 息传递的重要而简洁的途径之一。逆向工程的设计流程图如图1 2 所示 图卜2 逆向工程流程田 近年来，随着计算机辅助几何设计和图形学的发展以及计算机技术的广泛应 用，以曲线、曲面重构为代表的逆向工程技术无论在理论和应用上都取得了巨大 的成功，其应用几乎涉及了自然科学和工程技术的一切领域，包括汽车、飞机、 轮船外形设计与制造等工业领域，化学分子模型构造领域，基于地震勘探数据或 测井数据的地质勘探领域，以及依据大量数据计算和对计算结果进行分析的气象 领域，需要实现形体的网格划分及结果数据显示、优化的有限元分析，以及根据 测量数据建立人体骨骼和器官的计算机模型的医学和定制生产领域等等。 1 2 研究的现状 近年来，随着曲线与曲面重构技术研究的深入，各种各样的重构方法层出不 穷。解决曲线曲面重构问题的关键是：使点云关于点集的密度和形状尽可能细， 将原点集细化成充分细的点云，然后对这些细的点云进行排序。l e e 1 0 用最小 平方移动法细化点云，最小平方移动法的基本思想：对每一个数据点p ，计算一 个简单的回归曲线或曲面c ，用一个加权的回归方案，来局部拟合p 的邻域，然 后p 被移到近似曲线或曲面c 上的一个新的位置。d e d i e u 和f o w a r d i n 1 1 假设 所有的点均在重构的曲线上，给出了对这些数据点进行排序的一种算法。t a u b i n 和r o n f a r d 1 2 对无序数据点用一个隐式的单纯曲线重构平面曲线，他们首先构 建一个覆盖所有样本点的三角网格，然后用一个多角曲线拟合数据点。e d e l s b f u n l l e r 和m u c k e 1 3 给出了曲线重构问题的一个简单方法：通过找多角边界( 比 如口一s h a p e ) 表示点集的形状，然后用中央轴表示多面体点集的轮廓，然而一般 天津大学硕士学位论文基于噪声样本点的曲线与曲面的重构 2 1 插值、拟合 2 1 1 插值 第二章曲线曲面插值的基本理论 什么是插值? 简单的说，就是用给定的未知函数f ( x ) 的若干点的函数值构 造f ( x ) 的近似函数伊( x ) ，称函数伊( x ) 为插值函数。【l 】 在实际问题中，有时只能给出函数厂( x ) 的一些离散点的值( 五，f ( x t ) ) ，i = o ， 1 ，2 ，n ；给不出函数厂( x ) 的具体解析表达式，或者函数f ( x ) 的表达式过于 复杂不利于计算，这时，我们需要构造函数9 ( 曲的近似函数厂( x ) 。例如，在服 装店定做风衣时，选好风衣的样式后，服装师量出并记下你的胸围、衣长和袖长 等几个尺寸，这几个尺寸就是风衣函数的插值函数矽( x ) ，裁剪水平的差别就在 于量准插值点和构造合乎身材的插值函数。 在数学上常用的函数逼近方法有： ( 口) 插值： f b ) - 一致逼近，平方逼近； ( c ) 均方逼近或最d - - 乘法。 定义2 1 1 ：设f ( x ) 为定义在区间 a ，b 】上的函数，x o 五为 a ，b 上n + 1 个 互不相同的点，若函数伊( 功满足：伊( 薯) = 厂( t ) ，i = o ，1 ，2 n 则称伊( x ) 为f ( x ) 关 于节点x o x t 毛的插值函数。这样，对函数f ( x ) 在区间 a ，b 】上的各种计算，就用 对插值函数矽( x ) 的计算取而代之。 可对插值函数矽( x ) 的类型作多种不同函数的选择，由于代数多项式具有简单 和一些良好的特性，例如，多项式是无穷光滑的，容易计算它的导数和积分，故 常选用代数多项式作为插值函数。 2 1 1 1 多项式插值的l a g r a n g e 形式 ( 口) 线性插值 给定函数厂( x ) 在不同点和五的值，用一个线性函数： y = 妒( x ) = a x + b 近似代替( 功，称伊( x ) 为f ( x ) 的线性插值函数。其中，线性函数的系数a , b 通 天津大学硕士学位论文基于噪声样本点的曲线与曲面的重构 过条件 确定。如图2 1 ( a ) 所示 y q ( x 0 1 = y o q , ( x 1 ) = j ，l 图2 1 线性插值和抛物线插值 当x o x i 时，若用两点式表不这条直线，则有 厶( x ) = 羔玉( ) + 兰丑厂( 毛)( 2 1 1 ) x o 一1一x o 称这种形式为l a g r a n g e 插值形式。 记乇( x ) = 旦，( x ) = 旦，称乇( 功，( 功为插值基函数，易见 l j ( x , m = 三曷 ( b ) 抛物线插值 抛物线插值又称二次插值。对三个互异点而，x 2 ，毛，设已知厂( z ) 的函数值为 m ，赐，儿，要求构造一个函数： 9 ( j c ) = a x 2 + b x + c 使尹( x ) 在x i ( i = 1 , 2 ，3 ) 处与f ( x ) 在x i 处的值相等，如图2 1 ( b ) 所示。于是可由条件 c p ( x t ) = 厂( 蕾) = j ，= 1 , 2 ，3 ) 构造线性方程组，求得a ，b ，c ，即构造了尹( 工) 的插 值函数。 二次l a g r a n g e 插值的一般形式为： 厶( x ) = 乇( x ) 厂( ) + ( 五) 厂( 五) + 如( 恐) 厂( 而)【2 1 2 ) 每个基函数f ，( x ) 是一个二次函数。其中 天津大学硕士学位论文基于噪声样本点的曲线与曲面的重构 l o ( x ，2 ：毫糕，厶c 工，2 荨鞘，易c 工，= i 塞粼 插值基函数仍满足 t a x , ) = 岛= 三；i ( c ) n 次插值 给定平面上n + 1 个互不相同的点( 一，厂( 五) ) f = o 1 n 五互不相同，构造一个n 次多项式 ( 石) = a o + q x + + 口。x ” 由线性方程组 只( t ) = 厂( 鼍) ，i = o ，1 ，n 求出a i ，即构造了( x ) 插值函数。 刀次l a g r a n g e 插值多项式的一般形式 厶( x ) = 0 ( x ) 厂( 而)( 2 1 3 ) 其中， 闻 删2 l - i 再x - x j 2 1 1 2 多项式插值的n e w t o n 形式 设而，五，气互不相同，厂( 工) 关于而，五，x k 的k 阶差商定义为 厂，和气】：业琏型止巫删 一吒 带重节点( n + 1 个相同的节点) 的n 阶差商定义为： 九而】：坐掣 ( 口) 线性插值的n e w t o n 形式 i ( 工) = f ( x o ) + 九x o ，五 ( 工一) ( b ) 二次n e w t o n 插值多项式 2 ( 功= f ( x o ) + f i x o ，而 ( x x o ) + 厂 ，x a ，屯】( x x o ) ( x 一鼍) ( c ) n 次n e w t o n 插值函数 m ( 力= 厂( 而) + f i x o ，* ，x , ( x - x o ) ( x - x o ( x - x k 1 ) = 0 ( 2 1 4 ) ( 2 1 5 ) ( 2 1 6 ) 天津大学硕士学位论文 基于噪声样本点的曲线与曲面的重构 2 1 1 3 三次样条插值 在区间 a ，b l _ l ，给定n + 1 个互不相同的节点a = 民 五 0 ，使得厂( x + 2 d ) 厂( x ) ，v 五( o ，艿) ，贝i j 称d 为厂在点x 处的上升方向。【8 】 定义2 5 2 ：假定给定了搜索方向d 。，从x 。出发沿方向d ；进行搜索，要确 定步长以，使得厂( 以+ 。) = f ( x t + 以d ) f ( x 女) ( 1 ) ，记伊( 名) = f ( x 。+ 以d 。) ，则 ( 1 ) 营伊( 以) 0 。 n ( i i ) 检查是否满足终止准则。七- t - 算v f ( x o ) ，若0 耵( ) 0 一 厶 厶 呻0 c c 5 曰 p 。 p rj、1_rjll = = 局 历 天津大学硕士学位论文基于噪声样本点的曲线与曲面的重构 k 。， 。? 0 。 ，一。v p 囊 。： 。0 一。器 - 。一 ， ， ? v j 一一”k f l ? ：i ； t ， f 2 ，+ f。i + j 。， ： 一 。一一 ， ， 图3 4 点云排序 ( i i i ) mb 一样条曲线( 见2 2 节) 逼近有序点集。 3 2 曲线同胚的理论证明 下面证明当采样点n 0 0 时，由本章算法重构出的曲线与原曲线是同胚的的 概率趋于l 。首先证明s 的加细邻域的中心s 与s 距离非常近。 1 引理3 2 1 - 假设万衰，p 5 ，s 是一个样本点，形是加细邻域的宽度，对 j p 充分大的n ，加细邻域的中心j 与：的距离至多是( 1 3 8 8 + 3 ) 形的概率至少是 1 一d n ( h 。7 ，恤) 。 证明：首先假设 2 2 】中的引理3 3 1 ，3 3 2 ，3 3 3 ，3 4 1 ，3 4 2 ，3 4 3 均成 立，所以该引理成立的概率至少是1 0 一f l ( 1 n ，蛳) 假设s 砖，；的法线是竖直的，砖n c o a r s e ( s ) 在菇 c o a r s e ( s ) 的上方， 设屹，吒分别是从s 向下、向上作的射线，该射线与竖直方向所成的角为见， 设x ，y 分别是吒与黠、屹与s 的交点，设z 是屹与菇的交点，s s 二，s 。：s ，不 失一般性，假设矿0 ，如图3 5 所示。 ， 0 。一 天津大学硕士学位论文 基于噪声样本点的曲线与曲面的重构 珏 图3 - 5 引理3 2 1 的证明图例 由三角不等式，得 d ( ) d ( s ，y ) + d ( - s , y ) 0 9 由正弦定理， 郴一