（计算机应用技术专业论文）基于测量点与三角网格构造曲面的算法研究.pdf

浙扛大学硕士学位论文基于测量点与三角网格曲面构造的算法研究 摘要 本文针对散乱点、截面线点和三角网格构造曲面的问题，通过研究解决反求 工程中的图形分割、参数化处理和曲面拼接三个部分的问题，给出了这三种数据 的曲面重构算法。 对截面线点的曲面重构主要分封闭和不封闭的截面线点的处理。本文主要针 对的是不封闭的截面线点，可以通过利用截面线点的特性，直接提取截面线点的 四条边界用c o o n s 方法来构造基曲面，然后将基曲面的网格点参数化投影到截面 线点去，再构造连续的n u r b s 曲面；对封闭的截面线，可以通过利用散乱点的分 块方法进行分块构造出不封闭的截面线点，再分而治之的处理，然后进行曲面片 的拼接即可。 对散乱点的构造方法就是先采用平面分割散乱点方法，通过一个固定的方向 ( x ，y ，z 轴方向) 来生成一系列间距相同的平面，然后通过平移、旋转来得到 最适合的分割位置，再通过曲线投影散乱点的算法得到分块的边界线，采用参数 化方法对每个分块进行曲面片构造，然后对分块曲面进行g o 和g 连续的修改， 从而得到完整的n u r b s 曲面。 对三角网格的构造方法就是利用特征线提取和曲率分类的方法进行网格分 块和边界线的生成，然后对分块网格进行三角网格的曲而构造，同样也是对曲面 片进行g o 和g 1 连续的修改，从而得到完整的n u r b s 曲面。 本文的算法在原型系统中，用了多个模型做了测试，验证了它们的有效性。 关键词：散乱点，截面线点，三角网格，参数化，投影，曲率，特征线，c o o n s g 1 ，n u r b s ，曲线，曲面 第1 页共6 0 页 浙江大学硕士学位论文基于测量点与三角网格曲面构造的算法研究 a b s t r a c t t h i st h e s i sc e n t e r so nt h ei s s u eo fs u r f a c er e c o n s t r u c t i o ni ng r a p hd i v i s i o n ， p a r a m e t e r i z a t i o na n dc o n s t r u c t i o nf r o mu n o r g a n i z e dp o i n t s ，c o n t o u rp o i n t s a n dt r i a n g l e m e s h e s w h e nc o n c e r nw i t ht h ec o n t o u rp o i n t s ，p i c ku pt h ep o i n t so nt h eb o u n d a r i e so f c o n t o u r s ，u s ec o o n sm e t h o dt ob u i l du pb a s es u r f a c ef r o mt h eb o u n d a r yc u r v e s ，s p l i t u pt h eb a s es u r f a c ev e r t i c a l l ya n dh o d z o n t a l l yi n t og r i d sa n dp r o j e c tt h eg r i dp o i n t s o n t oc o n t o u r sb yp o i n t - p r o j e c t i o nm e t h o d ，i n t e r p o l a t et h e s eg r i dp o i n t st oo b t a i n c o n t i n u o u sn u r b ss u r f a c e w h e nc o n c e r nw i t ht h eu n o r g a n i z e dp o i n t s ，d a t ap a r t i t i o na n dd e f i n et h e b o u n d a r yc u r v e sf r o mas e r i a lo fp l a n e s ，u s ec o o n so rs k i n n i n gm e t h o dt oc o n s t r u c t b a s es u r f a c e ，u s et h ep a r a m e t e r i z a t i o nm e t h o da n ds u r f a c er e c o n s t r u c t i o nf o rt h eb a s e s u r f a c e st oo b t a i nas e r i a lo fp a t c h e s ，m o d i f yc o n t r o lp o i n t sf r o mt h ep a t c h e si nt h e n e i g h b o r h o o dt oc o n s t r u c tt h eg e o m e 砸cc o n t i n u o u sn u r b s s u r f a c e w h e nc o n c e r nw i t ht h es u r f a c er e c o n s t r u c t i o nf r o mt r i a n g l em e s h e s u s et h e s h a r pf e a t u r ed e t e c t i o na n dd i s c r e t ec u r v a t u r ee s t i m a t i o nm e t h o dt os e g m e n tt h e t r i a n g l em e s h e sa n dm a k et h eb o u n d a r yc u r v e s ，t h e nu s et h ep a r a m e t e r i z a t i o nm e t h o d t om a k en u r b ss u r f a c ep a t c h e su s et h et r i a n g l em e s h e sa r es e g m e n t e d ，f i n m l y m o d i f yc o n t r o lp o i n t sf r o mt h ep a t c h e si nt h en e i g h b o r h o o dt oc o n s t r u c tt h eg e o m e t r i c c o n t i n u o u sn u r b ss u r f a c e t h ea l g o r i t h m si nt h i sp a p e ra r ep r o v e dp r a c t i c a la n de f f i c i e n ti no u rp r o t o t y p e s y s t e m k e y w o r d ：u n o r g a n i z e dp o i n t s ，c o n t o u rp o i n t s ，t r i a n g l em e s h e s ，p a r a m e t e r i z a t i o n p r o j e c t i o n ，c u r v a t u r e ，s h a r pf e a t u r e ，c o o n s g 1 ，n u r b s ，c u r v e s s u r f a c e s 第2 页共6 0 页 浙江大学硕士学位论文 基于测量点与三角网格曲面构造的算法研究 1 1 概述 第一章绪论 在自动化制造领域中，常常涉及大量的复杂曲面的设计制造与检测。通常情 况下，首先在计算机上应用计算机辅助设计制造( c a d c a m ) 技术进行产品模型 设计，然后生成数控( n c ) 代码进行加工。与传统的加j 二模式相比较，反求工程 表征了一种c a d 模型不存在的产品设计新方法( 1 阁。除了应用于新产品的模型设 计以外，反求工程还引用与其它方面，包括现有产品的修改、破碎零件的重构和 工业检测。 反求工程中，复杂曲面的数字化可以通过接触测量技术或非接触测量技术实 现 3 】。三坐标测量机( c m m ) 是一种典型的接触测量设备，其测量精度和智能化 程度较高，为越来越多的用户所广泛采用，测量对象几乎包括各种机械零件，应 用于产品研制到产品最终检验的各个环节。然而，测量效率问题成为接触测量造 型的关键因素。非接触测量技术把激光束投影在零件曲面上，并通过光学传感器 拾取反射回来的激光束，应用三角形法或成像法快速地计算出数据点的3 维坐 标。随着激光测量技术和计算机技术的飞速发展，先进的产品表面数字化测量设 备得到了推广应用，使反求工程设计技术得到了新的发展。目前，在产品反求工 程设计的初期，可以将一个复杂的产品设计原型表达为大量的离散点，即通常所 说的点云。如何从这种离散的点云信息中快速把握产品外形的关键几何特征，成 为基于点云的反求工程c a d 建模研究的核心。 反求工程技术主要是为了解决无图纸实物的造型加工问题。通过测量扫描以 及各种先进的数据处理手段，快速、准确地建立实体数学模型，从一个模型同时 获得凹凸模。换句话说，反求工程技术就是研究如何以测量数据为依据，将测量 数据处理成表示实体外形的数学模型，并将该模型传入c a m 系统进行加工。其核 心就是测量数据的处理问题。反求工程技术可以提高产品的精度和质量，缩短产 品的试制、开发周期，降低成本，因而具有广泛的应用背景。 在反求工程中，曲面重构有其自身特点： ( 1 ) 曲面型面数据散乱且曲面对象边界和形状有时极其复杂，因而一般不 便直接运用常规的曲面构造方法。 第5 页共6 0 页 浙江大学硕士学位论文 基于测量点与三角网格曲面构造的算法研究 ( 2 ) 曲面对象往往不是简单地出一张曲面构成，而是由多张曲面经过延伸、 过渡、裁减等混合而成，因而要分块构造。 ( 3 ) 由于数字化技术的限制，在反求工程中还存在一个“多视数据”问题。 一般地，为了保证数字化的完整性，各视之间还有一定的重叠，这就引来一个被 称为“多视拼合的问题”。目前，在反求工程中，主要有三种曲面构造的方案： 其一是以b - s p l i n e 或n u r b s 曲面为基础的曲面构造方案；其二是以三角b e z j e r 曲面为基础的曲面构造方案；其三是以多面体方式来描述曲面物体。 1 2 相关知识 n u r b s 是非均匀有理b 样条，在b 样条方法中，n u r b s 最具有一般性。n u r b s 既涵盖了多项式的也涵盖了非均匀的和有理的b 样条方法。本节将讨论n u r b s 曲线、曲面的原理激起应用。 1 。2 。1 町r b s 曲线、曲面的定义 一个n u r b s 曲线是一个分段有理多项式方程组，形式如下 w , p f n , ，( “) c ( “) = 鼍_ 一a “b w j ( “) 其中，h 是所谓的权重，鼻是控制点，n 妇( “) 是p 阶b 样条的基础函数 一视啪，= 1 0 甓l 啪) _ 乏意舢) + 嚣兰- l ( “) 是所谓的节点，他们组成节点向量= u o ，“。 这个阶的大小，节点的数量，控制点的数量都联系着方程m = n + p + 1 。 在不均匀b 样条f i 线中，节点向量表示为 u2 以，口，u ，“。一川，p ，卢 口和夕重复p + 1 次。在大多数的应用中都假v 2 a = o ，芦= 1 。如果n u r b s 第6 页共6 0 页 浙扛大学硕士学位论文 基于测量点与三角网格曲面构造的算法研究 曲线使用了以上公式这样的节点向量就是类似于b e z i e r 曲线。大多数无理曲线 的性质都可以使用于n u r b s 。 一个n u r b s 曲面的数学定义，如下： w u 只，和( “) 抽( v ) c ( “) = 竺# ) _ 一 w i ，n i ，( “) 。( v ) i - - - oj 种 其中，w 。是权重，c ，是控制点网，n 。( “) 和n 。( v ) 是“方向p 阶和v 方 向q 阶b 样条的基础函数，相对的，节点向量就为 u = o 0 。0 , u 。，u ，p _ p l 1 。1 ) v = o ，o ，o y h 一，v s - q - i ，i ，i 一，i 其中首尾的节点分别重复了p + 1 次和g + 1 次。相对的方程分别为 ，= 以+ p + 1 和j = m + p + i 。 1 2 2 i 叮u r b s 曲线和曲面的插值 n u r b s 【l 【线的插值可以表述为：根据给定的型值点q 及其权园子 啊( f _ l ，2 ，n ) ，计算符合该条件的k - 1 阶连续的次n u r b s 曲线，起控制顶点和 权因子分别为弓和( j = o 1 ，m ) 。为此，我们可先在四维空间插值型值点 【吃q ，吩】，再将在四维空间求得的控制顶点【叶弓，】向三维空间映射，最后得到 三维空间内n u r b s 曲线的控制顶点弓= w ，e w 及其权因子w j ( j = o 1 ，m ) 。其 计算步骤如下： ( 1 ) 确定节点向量 节点矢量的选择会影响曲线的几何形态，而后者是在三维空间内考虑的问 题，故可用三维坐标下的累加弦长确定节点矢量。若构造三次n u r b s 曲线，其节 点矢量为u = u o = “l = “2 = “3 = o , ( q 1 q 2 + 0 2 q 3 ) i s ，( q l q ：+ q 2 幺+ 蜴q 4 ) s ， ( q l q 2 + 0 2 0 3 + + 包一3 q 一2 ) s ，b l n + 2 = h m = u n + 4 = h 。h = l 】 第7 贞共6 0 页 浙江大学硕士学位论文 基于钡量点与三角网格曲面构造的算法研究 式叶_ 】q ( f _ l ，2 ，n ) 为型值点，n 为型值点数；s 为弦长的总和a s = q f 瓯 ( 2 ) 建立方程组 与多项式b 样条曲线插值相似，n u r b s 曲线插值的方程组为 n + l 肚( u i + 2 ) w i g = h i q i ，i = 1 ，2 ，埘 j - - o 以上公式中的方程总数为n 个，而未知数为n + 2 个，故尚需补充两个方程，补充 方程可根据给定的边界切失求得。 ( 3 ) 构造补充方程 插值计算所需的边界条件是四维空间内的切矢，而我们只能提供j 维空间 内的切矢。为此，利用三维和四维空间的对应关系： f ( w ( 0 ) q ( o ) ) 7 = w ( o ) q i o ) + w ，( o ) q ( o ) l ( w ( 1 ) q ( 1 ) ) = w ( 1 ) q ( 1 ) 4 - ( 1 ) q ( 1 ) 式中q ( o ) = a ，q ( 1 ) = 幺，w ( 0 ) = j i l 。，w ( 1 ) = h 。；q 7 ( o ) 和q ，( 1 ) 分别为用户给定的首、 末切矢，w 7 ( 0 ) 和w ，( 1 ) 则可由数值微分方法求得。 ( 4 ) 求解方程组 前面两个公式构成了求解四维空间控制顶点的方程组，其系数矩阵呈带状， 带宽不大于3 ，故可用追赶泫求解。 ( 5 ) 计算i 维空间的控制顶点 四维空间的控制顶点除以该顶点的权因子，即可得到三维空间内控制顶点 的坐标。 n u r b s 曲线插值方法可以直接推广应用于n u r b s 曲面的插值。后者包括两个 步骤：1 ) 沿“( 或w ) 向对给定的型值点鳞及其权因子插值，求出相应的控 制顶点及其权因子；2 ) 以求得的控制顶点及其权因子作为新的型值点及其权因 子，沿w ( 或u ) 向做插值计算，得到n u r b s 曲面的控制顶点及其权因子。 第8 页共6 0 页 浙江大学硕士学位论文基于测量点与三角刚格曲面构造的算法研究 1 2 3 用蒙皮算法构造n u r b s 曲面 在n u r b s 曲线的基础上，我们可以根据实际需求用旋转法( r e v o l v i n g ) 、 扫成法( s w e e p i n g ) 或蒙皮算法( s k i n n i n g ) 构造n u r b s 曲面。用蒙皮算法构造 n u r b s 曲面的主要步骤： 1 )构造截面曲线。首先，根据给定的型值点和曲线的几何形状( 如直 线、圆弧或自由曲线) 构造各截面的n u r b s 曲线。当曲线由不同冥 次的曲线构成时，则一冥次最高者为准，将低冥次曲线段升阶，而 后以统一冥次的n u r b s 曲线表示该曲线。 2 ) 统一各截面曲线的冥次。当各截面曲线的冥次不同时，则以冥次最 高的曲线为准，对低冥次曲线升阶，使各截面曲线的冥次相同。 3 ) 统一各截面曲线的节点矢量。对各截面曲线的节点矢量( 设为“ 向) 做并运算，使其具有统一的节点矢量。为保证各截面曲线的形 状不变，常采用插入节点的算法。在统一节点矢量后，再计算各截 面曲线的控制顶点。 4 ) 计算w 向的节点矢量。w 向节点矢量由求得的控制顶点确定，应取 统一数值。为此，可取各截面曲线节点矢量的平均值作为w 向节点 矢量。 5 ) 以步骤3 ) 所求得的控制顶点为型值点，应用步骤4 ) 所求得的w 向节点矢量计算基函数，逐个截面反算w 向的控制点。 6 ) 由步骤5 ) 所求得的控制顶点即为用蒙皮算法构造n u r b s 曲面的控 制顶点。 1 3 曲面重构的一般方法 随着计算机辅助设计与图形学的发展，曲面重构技术得到了广泛的研究和应 用，几乎涉及自然科学与工程技术的一起领域，如汽车、航空、轮船等工业领域 中复杂外形产品的外形设汁，基于测距技术的几何模型自动生成，医学成像数据 的可视化等，该技术的发展有力地促进了造型和可视化技术的高速发展。因此， 研究和开发有效、高速、连续、光滑的曲面重构算法，具有重要意义。 第9 页共6 0 页 浙江大学硕上学位论文 基于测量点与三角网格曲面构造的算法研究 现在，曲面重构一般处理流程如下( 见图1 1 ) ： ( 1 ) 利用激光技术得到大量数据。 ( 2 ) 对采集的数据进行预处理。 ( 3 ) 根据数据对边界进行定义、提取，并使其 封闭，对分块测量数据进行补齐、匀化、散乱数据处 理等一系列处理，生成曲面数据。 ( 4 ) 曲面拟合。 ( 5 ) 曲面拼接。 在反求工程中，坐标采集是反求工程中的第一个 图l l 逆向工程的般过程 环节，是数据处理、模型重构的基础。数据预处理是 紧随数据采集环节之后的一个关键环节，它的结果将直接影响后期曲面重构的质 量。数据预处理的一项重要工作就是对扫描数据点进行编辑处理。由于测量仪器 的种类很多，输出数据的格式和质量相差很大，因此需要通过编辑以获得较高质 量的数据。数据预处理的方法通常包括以下几种：数据格式转换及补偿、噪声点 击除、数据点精化与平滑、数据点增密和数据点排序等。 分块数据补齐，是指测量数据按边界进行分块后，得到分块数据。分块数据 在边界处参差不齐，拟合后生成的曲面形态不好，所以必须将分块数据按边界自 动补齐。对于边界线为平面曲线的情况，该问题转化为分块数据与边界线所在的 平面相交。 匀化，测量数据点的间隔往往疏密不均，尤其是经过补齐后的数据。若仅做 曲线拟合，采用非均匀样条基，仍可获得合乎性能要求的曲线。但若由这些数据 构造网格进行曲面拟合时，数据点的不均匀会给拟合曲面的形态造成很大的影 响，引起局部病态，因此需要进行匀化处理。如对数据点较疏部分增加插值点， 过密部分去掉一些点，或在曲线上按均匀间隔( 一般是弧长均匀) 重新取点，这 样由这些匀化数据构造的网格生成曲面的形态较好。 反求工程中，n u r b s 曲面的拟合一般是根据点云数据点，在满足精度和光滑 性等要求的条件下，反算出n u r b s 曲面控制点及相应权值，从而重构出n u r b s 曲面。拟合算法可以是基本的逼近法，插补法或二者的结合。 曲面拼接，由于对测量数据进行分块处理，生成了多个曲面片，各个曲面片 第1 0 页共6 0 页 浙江大学硕十学位论文摹于测量点与三角嘲格曲面构造的算法研究 之间并不能保证光滑，还须将这些曲面片按一定的连续阶拼接生成光滑的曲面。 采用调整两曲面片，使其在边界处法矢的夹角达到极小，从而达到光滑拼接的目 的。 1 4 相关领域的研究 从点云数据到曲面模型，曲面重构的技术难点主要体现在曲面表示及根据点 云数据拟合的算法和曲面重构方法两个层面。 自由曲面一般用参数曲面表示，如常用的b e z i e r ，b - s p l i b e 和n u r b s ，此外 还有三角面片等离散表示方式t 4 j 。有了有效的曲面表示方法和拟合算法并不意 味着一定能重构出高质量的曲面模型。 下面首先讨论曲面模型应达到的要求，这主要指精度和曲面性能。由于曲面 模型往往是由多张曲面组成的，曲面性能应包含单张曲面的性能以及曲面之间连 续性两方面涵义。单张曲面的性能包括光顺性、可加工性、易操作性及气体动力 学性能等。对自由曲面而言首先应保持良好的光滑性，没有局部的皱折起伏、平 点、不正确的曲率特性等缺陷。曲面间的连续性包括位置连续性、切线连续性和 曲率连续性上的要求。曲面重构必须同时保证单张曲面的性能和曲面之间连续性 才能保证益面模型的整体性能。 在实际应用中，由于未采用合理的重构方法而导致不能全面保证曲面模型整 体性能的情况很多，典型的有以下几种： ( 1 ) 对具有复杂特征的点云数据直接进行拟合。这使n u r b s 曲面表示和拟 合算法处理的难度很大，造成运算时间很长，曲面上不同特征间的结合处误差较 大，且曲面节点过多过密，不易操作。 ( 2 ) 为了追求局部性能，仅对点云关键部位拟合益面，曲面间用m e r g e ， 圆角等方法过渡。由于过渡曲面由原曲面边界处的性质决定，而不是根据点云拟 合，故精度将难以保证，且形状不易控制，容易出现畸变。 ( 3 ) 拟合曲面时不限定边界，拟合后剪裁曲面实现曲面边界。在拟合曲面 时如果不限定边界，确定空间点对应参数域坐标值时就比较灵活，易于保证曲面 在原点云区域内的性质，从而达到较好的单张曲面性能。然而裁减曲面在数学表 示上仅仅是用曲线来限定了原曲面的有效参数域范围，平移、延伸、圆角等很多 第1 i 页共6 0 页 浙江大学硕士学位论丘 基于测量点与三角网格曲面构造的算法研究 操作都受到限制，并且由于边界表示的不一致，曲面间往往有难以避免的小缝隙， 不能直接满足快速原型等应用中对实体模型的要求，需要复杂的特殊处理嘲。另 外，为实现曲面间连续性而对曲面所做的改动也会影响精度和曲面性能。由此可 见，为全面保证曲面模型的整体性能，还必须有合理的曲面重构方法。 很多学者在数据预处理、特征提取、模型重建方面进行了大量的研究。b e n k o ， m a t r i n 和v a r a d y 等人提出了建立边界表达模型( b - r e p ) 完整的反求工程体系嗍。 c h i n g c h i ht a i 等人提出了基于设计思想的点云数据预处理算法 侧。在点云分 块和特征识别方面，针对二次曲面的识别与点云数据区域分害0 的研究较多，其主 要方法可大致分为三种：基于边的方法( e d g e b a s e dm e t h o d ) 、基于面的方法 ( s u r f a c e _ b a s e dm e t h o d ) 和混合法( h y b r i dm e t h o d ) e - 1 1 。在模型重建方面，有 关特征之间的约束识别和约束重建方面的研究较多，b e n k o 和w e r g m 等人给出 了反求工程中的各种约束类型及其数学表达，并对二维截线特征和三维曲面特征 的约束求解和优化进行了研究 1 1 3 】。w e i s s 等人研究了基于点云的曲面逼近技 术，提出了曲面的逼近模型和求解方法【1 妇。 1 5 本文的概述 本文将介绍基于三种数据类型( 截面线点，散乱数据点，三角网格数据) 的 曲面重构方法。 1 5 1 截面线点数据的重构 对于截面线点的曲面重构，传统上的插值方法 1 纠阳可分为三步：1 ) 对每条 截面线插值构造n u r b s 曲线；2 ) 通过升阶和节点插入，使每条曲线的次数和控 制点个数匹配；3 ) 运用n u r b s 曲面扫掠法将这些曲线扫掠构造得到n u r b s 曲面。 这个方法虽然直接简单，但是会产生大量的控制点，因此当数据量庞大时，计算 时间和内存消耗难以承受。即使利用减少控制点的方法刀，可以产生一定的效 果，也远远不能满足实际反求工程和曲面造型系统的需要。但是，如果利用参数 化方法使基曲面动态拟合截面线点，就可以在不影响曲面造型质量的前提下，大 大的提高构造效率。 第1 2 页共6 0 页 浙江大学硕士学位论文基于测量点与三角网格曲面构造的算法研究 对于参数化方法，前人已经做了很多研究，发表了不少的论文 1 8 - 2 1 。对不 规则空间和任意分布的点数据做参数化处理，通常是先建立一个简单的曲面，也 就是基曲面，它可以是平面，圆柱，球面，也可以足由四条曲线边界构成的c o o n s 曲面。然后把基曲面划分成网格，再把网格点投影到截面线中，重新计算基曲面 的参数。具体的做法根据基曲面构造方法的不同，投影方法的不同而不同。本文 所用的是非均匀截面型数据，在构造曲面矩形边界线时可以直接拾取边界点来构 造，再通过c o o n s 算法构造得到基曲面，基曲面效果要比文献口1 】好，因为文献 2 1 坤散乱点的边界线要构造精确难度比较大。文献嘲中也用到了提取截面线方 法，但是构造基曲面时用的是蒙皮算法，会产生大量的控制点并且消耗大量的运 算时间，效率并不是很高。然后对基曲面的网格点进行对截面线的投影，关于投 影方法，本文是直接在截面线点中找到一个离网格点最近或者离网格点投影线最 近的点，然后沿投影方向投影到该点附近，方法直接简单，比文献 嘲中多次叠 代投影的方法效率高。而且从实验数据所得结果可以看出，这个投影方法可以保 证比较高的精确度。 1 5 2 散乱点数据的重构 与处理截面线点的数据相比，在处理散乱点数据的时候，不光要做好参数化 的算法，更重要的是对完全没有拓扑信息的散乱点数据进行边界的提取。n u r b s 曲面是典型的张量积曲面，需要的是矩形拓扑区域，而实际的数据点有时并没有 明显的四条边界，有些复杂的数据点甚至连边界线都很难准确得到，这给实际的 建模操作带来了很多的困难。所以对图形进行分割就非常必要，可以将数量庞大 的散乱点分而治之，也可以将结构复杂的图形分割成便于构造曲面的小块。当然 为了保留分块之间的边界信息，要对分割后的小块投影边界曲线。这些边界线可 以作为构造基曲面的边界线，同时在进行曲面片拼接时，要修改这些边界的参数， 使曲面达到工程需要的g 1 连续。 在图形分割这部分，目前都是以平面分割为主，分割的方法多种多样，可以 用一系列平行平面分割，扇型分布的平面分割等等。这都取决于用户对散乱点图 形的需求。然后利用这些平面的位置，可以很自然得把散乱点分成多个区域。对 散乱点进行分块之后，还需要在平面上投影出与散乱点相交的曲线，并且根据曲 第1 3 页共6 0 页 浙扛大学硕士学位论文 基于测量点与三角网格曲面构造的算 玄研究 线的信息插入一些点，作为分块之后的共同边界点，从而保留了块与块之间的连 接，同时为以后曲面片之间的拼接和构造基曲面都提供了条件。 在点云上投影曲线是一个比较难以解决的问题。在以前的文献中较多的是在 2 d 情况下的解决方案。文献 1 2 】是对比较稀疏的2 d 散乱点或是三角网格进行曲线 的拟合，如果要对比较密集的2 d 散乱点和三角网格进行曲线拟合，通常要先进 行点稀释化的预处理。同样的，文献】中对密集型的2 d 散乱点的处理最主要的 问题，也是通过运用相关的图片处理技术对散乱点或是三角网格进行稀释化的预 处理在拟合曲线的。通过运用对2 d 拟合曲线中的解决问题方法来对3 d 散乱点进 行曲线拟合的思想在文献嘲中得到初步的尝试。在文献 2 | 】中对线投影思想进一 步的改进，主要思想是把要投影的直线离散成多个点，然后把点投影到点云上， 再把投影后的点插值成n u b r s 曲线。但是这种方法比较适用于点密集的数据，而 且也只能在不封闭的单面散乱点上投影，具有一定的局限性。本文的算法对此进 行了改进，先在平面上多个指定方向上投影出几个初始点，然后将这些初始点连 线作为投影线的初始值，然后将这些线再离散成点，进行点投影，如此递归，直 到达到一定的精度。如果是对不封闭的单面点云，那么投影的初始线可为直线： 如果是对封闭的多面点云，就用封闭的曲线作为投影初始线，所以这样的算法同 样能够很好的适应丁封闭或是不封闭的多面点云。 然后是对曲面片的构造，当前的n u r b s 曲面构造方法很多，但基本上倾向于 采用最小二乘拟合算法。在数据点的参数化方法，尚没有一个完全的普适方法， 一般情况下要根据点集的特征做基面参数化。在操作中，经常使用的基面是平面。 柱面及双线性c o o n s 酋面，也可以由一系列平行曲线通过蒙皮算法得到的基曲 面。实际的情况是按照用户的需要，如果线投影已经形成了矩形拓扑边界，那么 用双线性c o o n s 曲面更为合适，如果数据是复杂的卷曲类的数据模型，那么投影 一系列n u r b s 曲面，然后用蒙皮算法得到的基曲面更为合适。在得到一系列曲面 片之后，可以通过升阶和修改参数，控制点来达到曲面片之间的几何连续性。 1 5 3 三角网格数据的重构 对于三角网格数据处理来说，三角b e z i e r 曲面具有对数据拓扑关系要求的 宽松性，目前，以三角b e zj e r 曲面模型作为数字样品，通过对三角b e z i e r 曲面 第1 4 页共6 0 页 浙江大学硕士学位论文 基于测量点与三角网格曲卣构造的算法研究 模型进行合理的划分，分区构造多张四边域的n u r b s 曲面，最终将三角b e z i e r 曲面转换为由多张n u r b s 曲面表达的c a d 模型的反求工程c a d 曲面建模方法，已 经被人们所接受，并在实际工程应用中取得了良好的效果。三角b e z i e r 曲面的 优势主要体现在其对复杂曲面对象的快速、统一表达上，尽管三角b e z i e r 曲面 建模过程隐藏了复杂曲面的一些局部特征，但是这种统一表达的曲面重建效率和 精度很高。 在复杂曲面的线扫描测量中，特征曲线由具有明显曲率特征的点( 特征点) 构成。因此，特征盐线的提取过程，就是通过对扫描数据进行分析计算后得到特 征点并构造成曲线的过程。根据扫描线提取特征点的方法有很多 篮】。对比其他 文献利用特征线提取对网格分块的方法。本文的主要思想是先提取特征线，这里 的特征线和其他文献中的高曲率点集中起来的特征线不同，是指当两个相邻三角 网格的向量夹角达到一定程度时，他们的公共边就是特征线，线上的点就是特征 点。尽管在曲率计算之后，这些特征线也会被赋一个曲率值，但是这个曲率值并 不能真正反映出特征线的特性。所以我不能把特征线和别的高曲率的点同等处 理；它只能当作一条边界而非一个区域来进行处理。然后计算所有网格点的曲率， 对曲率进行分类，把临近的曲率类似的三角网格合并成一个新块，当碰到前面所 检测出来的特征线，那这条线就当作分块的边界，停止合并，到这里就是初步的 分块结束。为了缩小块的数据量，还要进行分块的重组，把曲率相近，或是面积 过小的块合并起来，最后形成用户满意的分块结果。分块，再分块重组的好处在 于，可以根据用户的需求，把曲率相近的但是不在同一单边的三角网格分开归并， 这样可以解决特征不十分明显的三角网格的分块。在分块结束之后，提取块与块 之间的边界，当然对边界要进行一定的处理，删除部分噪音点，使提取的曲线更 为光滑。边界提取之后，再进行曲面片的构造，这时每个曲面片不能保证只有4 个边界，所以要解决构造多边形向四边形的转换问题。然后再利用c o o n s 曲面构 造基曲面，网格点的向量作为法向量进行参数化处理得到一系列n u r b s 曲面片。 最后修改控制点和向量参数，使曲面达到工程需要的g 1 连续。 第1 5 页共6 0 页 浙江大学硕士学位论文 基于测量点与三角| 碉格曲面构造的算法研究 第二章基于截面线点数据的曲面重构算法 2 1 概述 对于截面线点的曲面重构，传统上的插值方法 1 5 - 1 6 可分为三步：1 ) 对每条 截面线插值构造n u r b s 曲线；2 ) 通过升阶和节点插入，使每条曲线的次数和控 制点个数匹配：3 ) 运用n u r b s 曲面扫掠法将这些曲线扫掠构造得到n u r b s 曲面。 这个方法虽然直接简单，但是会产生大量的控制点，因此当数据量庞大时，计算 时间和内存消耗难以承受。即使利用减少控制点的方法【1 7 ，可以产生一定的效 果，也远远不能满足实际反求工程和曲面造型系统的需要。但是，如果利用参数 化方法使基曲面动态拟合截面线点，就可以在不影响曲面造型质量的前提下，大 大的提高构造效率。 对于参数化方法，前人已经做了很多研究，发表了不少的论文 1 8 - 2 1 。对不 规则空间和任意分布的点数据做参数化处理，通常是先建立一个简单的曲面，也 就是基曲面，它可以是平面，圆柱，球面，也可以是由四条曲线边界构成的c o o n s 曲面。然后把基曲面划分成网格，再把网格点投影到截面线中，重新计算基曲面 的参数。具体的做法根据基曲面构造方法的不同，投影方法的不同而不同。本文 所用的是非均匀截面型数据，存构造曲面矩形边界线时可以直接拾取边界点来构 造，再通过c o o n s 算法构造得到基曲面，基曲面效果要比文献乜l 】好，因为文献 盘l 】中散乱点的边界线要构造精确难度比较大。文献嘲中也用到了提取截面线方 法，但是构造基曲面时用的是蒙皮算法，会产生大量的控制点并且消耗大量的运 算时间，效率并不是很高。然后对基曲面的网格点进行对截面线的投影，关于投 影方法，本文是直接在截面线点中找到一个离网格点最近或者离网格点投影线最 近的点，然后沿投影方向投影到该点附近，方法直接简单，比文献 咖中多次叠 代投影的方法效率高。而且从实验数据所得结果可以看出，这个投影方法可以保 证比较高的精确度。 2 2 算法 总的来说，n u r b s 曲面拟合方面的研究主要集中在基面的构造和参数化方法 第1 6 页共6 0 页 塑坚查堂堡主堂垡堕苎 苎王型里盛! 三鱼塑蹩些堕塑堕塑竖堡竺墨 两个方面，旨在提高构造n u r b s 曲面的精度和效率。本文介绍的是一种新的截面 线参数化方法。由于非均匀截面线的数据结构的定义，可以较容易地得到截面线 点的四条边界线：第一条截面线c 0 ( “) ，最后一条截面线c l ( “) ，所有截面线第一 个点组成的曲线c 0 ( v ) ，所有截面线最后一个点组成的曲线c 。( v ) 。截面线点 即= ( z ，y ，z ，) 贸3 ， = 0 ，n 一1 的坐标值和截面线点数在图形分割后 就已确定。因此基面的构造较直接精确。我们研究的主要问题就是如何提供合适 的参数值( ，v 。) 能够最好的表示点在曲面的位置。其中， ( “。，v 。) o ，h x o ，l 】c 吼2 ， = 0 。，n l 。而且算法在处理上万个截面线点 时，能够做到快速准确 本文的主要思想是先构造一个基曲面，把基曲面分成网格，再把每个网格点 在基曲面上的向量作为网格点的投影方向来进行动态的调整，使得这些网格点的 投影误差到达最小，最后插值这些网格点得到最后的n u r b s 曲面。最初的基曲面 是根据c o o n s 方法利用边界线得到。网格是利用基础曲面的参数，纵横得到n 、m 条曲线交叉形成。点的投影方法是依照特定的投影方向，使点投影后，让误差方 程的值最小。 最初的基础曲面 上 计算基础面的网格和网格点的投影方向 j l 投影网格点，使网格点与截面线点的误差方程值最小 上 l 插值曲面 图2 1本文参数化方法的流程图 2 3 构造最初的基础曲面 在n u r b s 曲面拟合中一个最关键的问题就是数据点的参数化。一般来说，在 数据点的参数化时，通常要事先找出点集的四条边界。通过提取点集的四条边界， 进而采用双线性c o o n s 曲面来构造基面。c o o n s 曲面具有计算量较小，易于操作 第1 7 页共6 0 页 浙江大学硕士学位论文基于测量点与三角网格曲面构造的算法研究 等优点，精度较差但能完整反映边界特性，非常适合做基面。在截面型数据点中， 由于四条边界的点可以直接得到，我们可以把“( v ) 方向上两条边界线点数较 小的值作为“( v ) 方向上可删选点的最大值。根据用户的需要来决定u ( v ) 方向边界线取点的数量( 如图2 2 ) ，当然点数量越大基曲面的质量越好，消耗 的时间也越多。经过多组截面线点的实验，原则上，选取1 3 的总点数最为合适。 决定选取点数之后，均匀的按比例隔几个选一个点作为边界线的插值点，然后用 这些选取点插值成四条边界线。之后采用c o o n s 方法构造基曲面。 图2 2决定边界线插值点数 我们假设四条边界为：c a u ) = j ，( “) 只。k = 0 , 1 u e 0 ，1 】 m c f ( v ) = 抽( v ) e ，1 = o ，1 v 【o l 】 边界围成的四个顶点为： s 。，。2 g ：o ( “2 0 ) 2 c 1 = o ( ”2 0 ) s l m = c k 目m = 1 ) = c j ：l ( v = 0 ) 晶，= g = 1 0 = o ) = q ；o ( v = 1 ) s 1 1 = c k 。1 0 = 1 ) = c i ：l ( v = 1 ) 基曲面s ( u ，v ) = r l ( “，v ) + r 2 ( “，v ) 一t ( u ，v ) ，其中“，v o ，1 ，r l 和r 2 是m ，v 方 向上的规则曲面，丁c 地v ，= “， s 黾o 。o 虬s o 。i 习。 第1 8 页共6 0 页 浙江大学硕士学位论文 基于测量点与三角网格曲面构造的算法研究 c o o n s 曲面的表面比较光滑，而且根据四条边界的形状，可以比较粗略地反 映点集的几何特性。对比文献脚 中的蒙皮法构造基曲面，用c o o n s 方法虽然点 集的几何特性的效果要差一点，但是对一个基曲面的要求来说，只要能够正确的 反映边界信息就可以；在速度效率方面，都要比蒙皮方法高很多。 2 4 构造网格并确定网格点的投影方向 有了基曲面，接下来就是对基曲面的参数化工作。假设s = s ( u ，v ) 是基曲面 r i = r ，( v ) = s ( u f ，v ) 是n 条v 参量曲线，( u = u 。 0 ，1 ，“h 0 该点在平面a 的正方向 假设 l e n 。= o 该点在平面a 上 ；平面b 同理。 【z p 儿 0 f - o ，2 m + l 2 o w 1 o 0 【2 w 2 ，o w 2 ，o 0 同样的上，左和右边的边界一样要依次满足下列条件： i2 m m + i h m o i = o ，2 m + 1 2 山+ 1 一w 1 勘 0 l ：2 w 2 m + 1 2 n “一w 2 m 2 n + t 0 2 w o ，j w l ，j 0 扛o 2 n + 1 2 w 0 o w o i 0 1 2 w 雌一w o m 0 第3 2 页共6 0 页 浙江大学硕士学位论文 基于测量点与三角网格曲面构造的算法研究 2 w 2m + 1 一w 2 。，j 0 i = o ，2 ，l + 1 2 w 2 “o w 2 m l 0 2 w 2 m m “一w 2 ，m o 我们假设s 的下边界满足的可连续性的条件。那么，我们可以通过下面章节 的公式修改s ，和s ：的全局控制点和s ：上边界的权重来时两个曲面达到g 1 连续。 3 6 1 曲面s 。和曲面s ：的g 1 连续性修改 s l s 。 图3 8n u r b s 曲面s l 和s 2 的示意图 n t i s ：的参数不变，按照下面的公式只修改s l 下边界的第一条和第二条控 制点保持s 。的其他控制点不变，就能使s 和s ：达到g 连续。 1 ) s 。左下角控制点的修改 “= 等警 茹2 r 一2 o22 w o o w t ，o r - 2 , , = 塾篙篙篇铲 话2 ，一2 。l = 2 ( 2 w o o w 0 ，1 ) 一( 2 w 1 o w 1 1 ) 2 ) s 。和s ：边界上的两行控制点修改 d 2 r 一2 十t o2d t o 茹2 卜2 十o = w to k 地。= 杀竽 茹2 p 2 + i ，l = 2 w 女o w 女，1k 2 1 ，2 ” 第3 3 页共6 0 页 浙江大学硕士学位论文 基于测量点与三角剜格曲面构造的算法研究 3 ) 置有下角控制点的修改 ： 2 w 2 + l , o d 2 m + 1 o w 2 m , o d 2 m o d 2 ( r + m - 1 ) + l , 0 一1 瓦= 二- 谛2 ( m 一”+ 1 ，o = 2 w 2 m + 1 o 一”2 m o 2 ( 2 w 2 m + l , 0 d 2 “o w 2 。+ 1 ，1 d 2 。“1 ) 吼( r + m - i h u2 硒瓦= i = f 面五而 2 w 2 o d 2 m o w 2 。，l d 2 m 1 2 ( 2 w 2 。“o w 2 m + 1 i ) 一( 2 w 2 。o w 2 。1 ) 帚2 ( r + m i ) + 1 1 = 2 ( 2 w 2 m + 1 o w 2 m +