（机械制造及其自动化专业论文）反求工程中基于点云的特征挖掘技术研究.pdf

摘孽 摘要 以点云为源，以特征为本的参数化反求建模技术现已成为反求工程领域的一 个研究热点。近年来，非接触式测量设备的飞速发展使点云的数据规模急剧增加， 点云和特征间的关系日趋复杂，在这种情况下，为了能够快速、准确地理解点云 所蕴含的特征信息，本文提出并系统研究了基于点云的特征挖掘技术。 在反求工程的背景下，首先给出了特征的定义和分类，而后在此基础上结合 数据挖掘思想定义了特征挖掘技术。对特征挖掘的研究内容、体系结构和应用领 域进行了系统的分析和论述，指出了包括数据预处理、区域分割和曲面误差评价 在内的论文研究方向。 点云数据的引入一方面使反求建模系统的形状描述能力明显提高；另一方面 使系统的数据分析、处理模块不堪重负。为了提高系统的数据处理效率，本文首 次提出了基于三参数s h e p a r d 曲面的噪声过滤和曲率计算方法。提出的噪声过滤 算法以三参数s h e p a r d 曲面为潜在的流形表面，实现了保特征的异面数据虑除。 提出的点云曲率估算方法通过s h e p a r d 曲面插值点的简单线性组合计算曲率，避 免了大量的曲面逼近运算，具有效率高，复杂度低，实用性强的特点。 提出一种基于微分几何量统计分析的区域自动分割算法。该方法将点云划入 规则分布的三维栅格，通过法曲率映射、高斯映射分析每个栅格的几何属性，利 用假设检验法判断栅格的特征类别并基于栅格的拓扑关系、映射点的聚类性质和 分布拟合的结果分割相应区域。该算法具有阈值少，效率高，抗噪能力强的特点。 提出点云到曲面距离的快速算法。该方法通过曲面采样和最近点搜索获得点 云中每个测量点对应的投影点初值，基于此初值迭代求取精确投影点并计算此点 和对应测量点的距离。文中首次从理论上定量分析了曲面离散密度对计算精度的 影响，这使得本文算法实现了距离估算误差的先验性控制。算法中使用的均匀采 样准则和六面体栅格结构使得其速度明显优于同类算法。 研究了上述特征挖掘算法在r f ，s o f t 系统中的高效代码实现方案。基于两 个建模实例说明了这些特征挖掘算法是快速、稳定和可靠的。本文最后对未来的 研究工作进行了展望。 关键词：反求工程，点云，栅格结构，数据预处理，曲率计算，噪声过滤，区域 分割，假设检验，误差分析，点投影。 、0：fi i j 、 - a b s t r a c t p a r a m e t r i cr e v e r s em o d e l i n gt e c h n o l o g yi st h ef o c u si nt h ef i e l do fr e v e r s e e n g i n e e r i n g i nr e c e n ty e a r s , l a r g ea m o u n to fp o i n t s ，a c q u i r e db yn o n - c o n t a c t m e a s u r i n gm a c h i n e , m a k et h er e v e 船m o d e l i n gb e c o m ea ni n e f f i c i e n tp r o c e d u r e t o s o l v et h ep r o b l e m , f e a t u r em i n i n gt e c h n o l o g yi sp r o p o s e da n dd e e pr e s e a r c h e di nt h e t h e s i s t h eb a s i ct h e o r i e si n c l u d i n gt h ed e f i n i t i o n , c l a s s i f i c a t i o na n dr e p r e s e n t a t i o no f g e o m e t r i cf e a t u r ea r ep r e s e n t e df i r s t l y b a s e d0 nt h ek n o w l e d g eo ff e a t u r e f e a t u r e m i n i n gt e c h n o l o g yi sd e f i n e d b yr e s e a r c h i n gt h em e t h o do f m i n i n gf e a t u r e ，t h r e ek e y s t e p s ：d a t ap r e p r o c e s s ，s e g m e n t a t i o na n df e a t u r ea n a l y s i sa r et a k e na st h em a i n r e s e a r c hs u b j e c t s p o i n tc l o u d , c o m p o s e db yd e n s ea n de r r o r - f i l l e dm e a s u r e dp o i n t s ，a f f e c t st h e e f f i c i e n c ya n dq u a l i t yo fc a dm o d e lr e c o n s t r u c t i o n t os o l v et h ep r o b l e m s , an e w t h r e ep a r a m e t e r ss h e p a r ds u l f a c ei sp r o p o s e d t h es u 触c a nb eb u i l tf r o mp o i n t c l o u dw i t h o u tc o m p l i c a t e dp r o c e d u r es u c ha sb o u n d a r yd e f i n i t i o n ，p a r a m e t r i z a t i o n , s u r f a c ea p p r o x i m a t i o na n de r e b a s e do nt h es u r f a c e ，m e a s u r e dp o i n t sc a nb ec l e a n e d a n da n a l y z e de f f e c t i v e l y f o re x a m p l e ，o u t l i e r si np o i n tc l o u dc a nb er e m o v e dw h i l e p r e s e r v i n gt h ef e a t u r e ；c u r v a t u r eo fe a c hm e a s u r e dp o i n t sc a nb ee f f e c t i v ee s t i m a t e d w i t h o u tc o n s t r u c t i n gt h o u s a n d so f l o c a ls u r f a c ep a t c h e s a na u t o m a t i cs e g m e n t a t i o na l g o r i t h mb a s e do ng e o m e t r i ca t t r i b u t ea n a l y s i si s p r o p o s e d t h ea l g o r i t h ms u b d i v i d e sp o i n tc l o u di n t oc u b i c 鲥d sa n dt h e nm a p st h e g e o m e t r i ca t t r i b u t ev a l u eo f p o i n t si ne a c hg r i dt on o r m a lc u r v a t u r ec o o r d i n a t es y s t e m a n dg a u s s i a ns p h e r e b yt e s t i n gh y p o t h e s i s ，t h ep a t t e r n so ft h en o r m a le t t r v a t o r e i m a g ea n dt h eg a u s s i a ni m a g ea r er e c o g n i z e d b a s e do ng r i ds t r u c t u r e ，t h ei m a g e p o i n t sc l u s t e r i n g ，a n dg o o d n e s s - o f - f i tt e s t i n g ，p o i n tc l o u di ss e g m e n t e di n t o s e v e r a l r e g i o n sa n dc h a r a c t e r i z e d 骶n a t u r a lq u a d r i c s , e x t r u d e ds u r f a c e so rr u l e ds u r f a c e s r e s p e c t i v e l y a p p l i c a t i o n ss h o wt h a tt h ep r o p o s e da l g o r i t h md e a l sw i t hl a r g ea m o u n t o fm e a s u r e dp o i n t ss t a b l ya n de f f e c t i v e l y i tc a nb ea p p l i e dt om a n yo t h e rf i e l d s i n c l u d i n gv i s u a lr e a l i t ya n dc o m p u t e rv i s i o n d e v i a t i o ne s t i m a t i o nb e t w e e np o i n tc l o u da n dg i v e nc a dm o d e lp l a y sa n i m p o r t a n tr o l ei nt h er e v e i s ee n g i n e e r i n g i nt h i sp a p e r , af a s te s t i m a t i o nm e t h o di s p r o p o s e d t h em e t h o ds a m p l e ss u r f a c e so ft h em o d e lf i r s t l y ；b a s e do nt h es a m p l e d p o i n t s ，ap r o j e c t i o no fe a c hm e a s u r e dp o i n ti sc o m p u t e d ；u s i n gt h ep r o j e c t i o n s ， d i s t a n c ef r o mp o i n t st os u r f a c e si sc a l c u l a t e d e r r o ro f t h ed i s t a n c ec a nb ek e p tw i t h i n h 浙江大学幛t 学位论交 g i v e nt o l e r a n c eb ys e t t i n gt h es t e pl e n g t ho fs a m p l i n g 1 1 1 ep r o p o s e dm e t h o di sm o r e e f f e c t i v et h a no t h e r sb ys a m p l i n gt h ep a r a m e t r i cd o m a i no fs u r f a c ea n ds e a r c h i n gt h e n e a r e s tn e i g h b o rb a s e do nc u b i cg r i ds t n l c | n l r e s e v e r a le x a m p l e sa r eg i v e nt os h o wi t s e f f i c a c y t h ei m p l e m e n t a t i o nm e t h o do fa b o v em i n i n ga l g o r i t h m si sr e s e a r c h e d t h eg r e a t v a l u eo f t h e s ea l g o r i t h m si sp r o v e db yt w oa p p l i c a t i o ne x a m p l e s f i n a l l y , s o m et o p i c s f o rf u t u r ew o r ka r cd i s c u s s e d k e yw o r d s ：r e v e r s ee n g i n e e r i n g , p o i n tc l o u d ，g r i d , d a t ap r e p r o c e s s ，c u r v a t u r e ， e s t i m a t i o n , n o i s ef i l t e r i n g ，r e g i o ns e g m e n t a t i o n , h y p o t h e s i st e s t i n g ，e r r o ra n a l y s i s ， ， p o m p r o j e c t i o ni i i i ! ； 第一章绪论 第一章绪论 i 内容提要】阐述点造璎的概念、理论和方法，指出点造型技术在产品设计，尤其是产品特 征细节精确表达方面的缺陷。论述了产品反求工程设计中由大规模点云数据提取产品几何特 征信息的重要性以及呵临的技术挑战。阐述了参数化反求工程c a d 建模的理论和具体方法 以及建模过程中存在的主要问题。最后系统地给出了博士论文的主要内容和基本框架。 1 1 点造型技术 在过去的很长段时间里，基于多边形网格的几何表示与图形绘制方法一直 在c a d 、c g 领域中受到高度重视。近年来，随着非接触式测量方法的广泛使用， 测量数据的信息量急剧增加，基于大规模的测量数据已经难以高效地构建多边形 网格；同时，针对大量网格的系统管理和图形绘制也存在技术瓶颈【l 】。在这种情 况下，以点模型取代网格模型，以点取代三角面片作为几何表示和图形绘制的基 元就逐渐成为c a d 、c g 领域的一个新的趋势。 点模型通常又被称为点云曲面( p o i n ts e ts u r f a c e s ) 或点几何( p o i n ts a m p i e d g e o m e t r y ) 2 - 4 1 。它是基于点云数据对三维几何体的完整、离散的边界表示方式。 与传统的多边形网格模型相比，其特点在于：1 ) 丢掉了对绘制无用的拓扑连接 关系，有利于模型的快速运算和绘制；2 ) 不受模型拓扑结构的限制，只要漫定 足够的采样密度，甚至能够表达不规则的自然界物体；3 ) 无需花费时间和空间 构建并维护网格结构，系统占用量相对减少。可以l ；皂，点模型的提出和应用明显 提高了计算机对3 d 物体的表达能力。 图形学界围绕点模型展 开的一系列研究被称为基于 点的计算机图形学。其特点 是在计算机中以点的形式存 储、编辑、传输和绘制三维 物体( 图1 1 ) 。它主要包括 3 个部分：点获取、点造型 和点绘制。其中，点造型技 术足近年来国内外学者研究 的热点问题之一【5 1 。 图i 1 点造型流程 1 1 1 点造型概念及其内涵 点造型技术通过操纵离散点改变点模型的整体形状和外观。其最大特点就是 1 浙江大学博士学位论文 无需维护模型的拓扑一致性，系统资源利用；筝高。该技术涵盖了点云的几何表达、 处理和编辑三部分内容1 6 l 。 点几何表达的目标是用连续曲面表达离散的点云数据。h o p p e 将此问题表述 为：在给定的阈值( 误差，采样密度) 范围内通过插值或逼近采样点集p 构造 流形表面m m 。点几何表达一方面为点模型的处理、编辑提供了基本的曲面结构， 另一方面使计算机能够绘制出具有连续效果的点模型。 点处理和编辑负责分析、修改和优化点模型所蕴涵的表面信息【5 l 。点处理通 过几何属性分析、光顺去噪、重采样、压缩、形状匹配和特征提取等一系列算法， 降低样件在数据采集( 测量) 过程中所受随机因素的影响，得到精确、符合期望 采样规律并能比较全面地反映几何体形状的离散数据点集。点编辑通过布尔操 作、变形、喷绘、纹理映射和雕刻等工具，修正点模型的形状和表面材质以使其 符合设计者的意图。 1 1 2 点造型的国内外研究现状 点几何表达是点造型和渲染显示的基础，目前常用的几何表示方式包括 s p l a t s 表示和m o v i n gl e a s ts q u a r e ( m l s ) 表示【1 1 s p l a t s 是带颜色、法矢和形 状因子的点元。s p l a t s 技术将每个点扩展为有一定半径的圆盘，通过放缩圆盘的 半径填补测量点之间的空隙从而形成连续的表面。应用s p l a t s 的初衷是用来加速 真实感图形绘制，最近的研究表明，s p l a t s 也可以作为造型的基本体素1 9 1 。s p l a t s 表示法快速简便但连续性较低，精度有限，因此，该方法很难应用于精确零件或 产品造型系统。m l s 表示技术【l m1 1 1 通过加权最d , - - 乘法逼近给定邻域内的测量 点构造局部曲面，连接每个点对应的局部曲面形成连续的表面模型。该技术基于 高斯核函数实现加权拟合，高斯核函数的连续阶次即决定了最终m l s 曲面的连 续阶次【s l 。利用这个特点，只要选用一种高阶的核函数 s l ，m l s 法就很容易表达 高阶曲面；同时，m l s 法也存在一定的缺陷，因为缺少高效的采样算法，绘制 m l s 曲面需要大量的投影运算，效率较低。由此可见，s p l a t s 和m l s 在绘制和 造型上各具优势，如果将它们结合起来，基于s p l a t s 实现点绘制，基于m l s 实 现点造型是一种比较现实可行的方法。 点处理是点造型的主要研究内容之一，几何属性分析、光顺去噪、压缩和特 征提取是目前研究较为集中的几种点处理技术嘲。 要实现点模型的有效处理，通常需要估算法矢、曲率等微分几何量。这个问 题也是目前c a g d 领域的一个研究热点。估算法矢的最常用方法是基于k 邻域 的切平面拟合法川和二次参数曲面拟合法【1 2 1 。为减少局部采样密度对法矢精度的 影响，o uy a n g 【l 习基于给定测量点的v o r o n o i 邻域按一定规则拟合多条二次曲线， 利用二次曲线在该点的切矢和法矢垂直的特性，通过最小二乘法求解该点的法矢 2 第一章绪论 向量。在法矢的基础上，m e r n e s t l l 4 1 进一步通过局部抛物面拟合法计算曲率。 p a u l y l 7 】利用邻域内测量点的相互位置关系构建协方差矩阵，通过分析处理矩阵的 特征值和特征向量获取该点对应的法矢和曲率值。ym i a o 1 5 】提出使用密切球逼 近邻域测量点集，利用一维能量泛函评价密切球对邻域点集的逼近程度，通过计 算密切球的半径来确定测量点的曲率。考虑到上述算法的收敛性和精度等级都没 有得到理论上的证明，f c a z a l s l l 6 l 提出了一种基于泰勒展开式的新方法，该方法 通过插值或逼近截断的泰勒函数计算微分几何量。根据函数的截断阶次不同该方 法可以计算一阶量( 法矢) ，二阶量( 主曲率、主方向) 甚至高阶微分量。f c a z a l s 进一步利用泰勒展开式的性质证明了该方法的收敛率和在特定情况下的微分量 误差等级。总的来说，上述方法对点云中的测量点进行逐点计算，这虽然能够在 一定程度上保持整体的估算精度，但考虑到通常情况下点云中的大部分测量点位 于平坦区域，测量点本身具有相似的几何属性，若一概而论地采用逐点计算的模 式，就会浪费大量系统资源。因此，需要进一步研究能够适应点云分布特征的高 效计算模式。 噪声是影响点处理稳定性的一个主要因素，针对测量数据中存在的随机噪 声，cl a i l g e 【2 l 提出一种基于几何平均曲率流的点模型各向异性光顺算法。该方 法在给定测量点的l 【邻域内计算其方向曲率并利用w e i n g a r t e n 映射计算该点的 主曲率和主方向，根据方向曲率和主曲率计算截断函数，将函数值带入各向异性 的拉普拉斯算子计算该点的位移增量，通过增量修正每个点的位置使点模型的表 面更光滑。胡国飞1 1 7 1 提出利用m e a n s h i f t 方法自适应地构建邻域，利用邻域的曲 率信息对点模型进行三边滤波，以获得一个保持特征的光顺模型。上述光顺去噪 方法能够在一定程度上减小点云中振荡幅度较小的随机噪声，但难以有效处理偏 离样件表面较远的脉冲噪声或异面采样数据。 点模型压缩是控制测量数据规模的一种主要手段i l s 1 9 1 。p a u l y1 1 8 1 首次将以下 三种网格压缩算法推广到散乱的点云数据上。 ( 1 ) 聚类法脚l ：增量聚类法随机选定一系列数据点作为种子点，通过不断 搜索其最近点扩展当前邻域，当邻域体积或曲率变化达到给定公差时停止生长， 选择邻域内部点集中最靠近重心的测量点代替其它点即完成了压缩过程。层次聚 类法首先将点云中的所有测量点作为一个聚类，如果这个聚类的规模及统计方差 大于给定的阈值，就将聚类用主平面一分为二，通过不断细分和选择聚类中心达 到点云压缩的目的。 ( 2 ) 迭代简化法【2 l l ：此方法与适用于三角网格的边收缩算法( e d g ec o l l a p s e ) 类似，其基本原理是迭代地、选择性地将点云中的两个点收缩为个点，以达到 点云简化的目的。通过估算压缩后点云和初始m l s 曲面的距离能得到压缩误差， 3 浙江大学博十学位论文 判定压缩的有效性。 ( 3 ) 粒子系统模拟法1 2 2 ：p a u l y 首先从原始点云中抽取部分离散数据点作为 粒子，而后基于粒子的相对位置计算激振力，以激振力驱动粒子在空间运动并定 位于新的平衡位置。将粒子向最近测量点的切平面投影，将获得的投影点组合起 来即为压缩后的点云。该方法可以得到分布合理的离散点集，但压缩效率不高， 难以处理大规模点云。 点模型的特征主要包括特征线、凹凸结构和边晃等【i 刀。目前的点模型特征技 术主要指特征线提取及运算。特征提取过程可分为两步，首先根据形状变化的剧 烈程度从模型中抽取特征点，而后将特征点按模型的拓扑结构连接形成特征线。 g u m h o l d 等田l 基于测量点邻域构建协方差矩阵，通过分析该矩阵获取相应的法 矢和曲率信息，基于曲率的变化提取特征点，利用最小路径理论连接特征点构造 特征曲线。在上述算法中，邻域大小会直接影响曲率计算的结果，通过动态的改 变邻域范围，p a u l y t 2 4 1 实现了多尺度的特征线提取算法。该算法的抗噪声能力更 强而且能够提取从尖锐到平缓的不同形态的过渡特征。胡国飞【1 - q 首先基于平均曲 率把点模型分为平滑区域，凹区域和凸区域，而后利用主曲率和主方向，抽取凹 凸区域的脊点和谷点为特征点。这些特征提取方法关注的是点模型蕴涵的特征点 和特征线，难以对特征曲面的进行有效的识别和提取。 上述方法是一些空间域的处理方法，pa _ l l l y l 4 1 开创性地提出点云的频谱分析技 术。该技术将模型的点集曲面自动地映射到经过多个规则重采样后的基平面上， 计算每个投影域内的f o u r i e r 变换得到模型的局部频谱分量，通过直接分析和操 纵这些频谱系数实现过滤、重采样、高频分析及局部误差控制与修复。该算法易 于硬件实现，为点集曲面的信号分析处理提供了新的思路。但是这种方法也存在 一些不足：1 ) 在预处理过程中耗费的时间较长；2 ) f o u r i e r 变换过程可能损失 几何信号； 3 ) 频谱分析过程中的几何误差控制困难。 1 1 3 点造型系统及应用 目前，国内外有多个高校开发出以点模型为对象的造型系统。其中具有代表 性的有苏黎世联邦工学院的p o i n t s h o p 3 d ，浙江大学c a d & c g 国家重点实验室 的数字几何处理系统。 p o i m s h o p 3 d 是一个基于组件技术设计的点模型编辑系统【2 5 1 。它为点模型 的读入、储存、修改和渲染提供了一整套功能。系统由基本工具和高级插件两部 分组成。基本工具包括系统中一些常用的几何处理功能：光顺去噪，参数化和表 面绘制等。插件中包含高级的附加功能：模型间的布尔运算，多尺度分解等。系 统内嵌了各具特色的点绘制引擎：基于软件的s p l a t s 引擎绘制精度较高但效率较 低，主要用于绘制高清晰度的静态点模型；基于图形处理器的o p e n g l 高效引擎 4 用于绘制处于运动状态( 旋转、缩放) 的点模型。可以说p o i n t s h o p 3 d 足以变形， 布尔运算，纹理映射等模型编辑操作为主的点造型系统。 与p o i n t s h o p 3 d 相比，浙江大学c a d & c g 国家重点实验室的数字几何处理 系统更注重于点模型的构建和处理。系统具有两条主线：一是对每个顶点进行局 部几何重建，采用合适的曲面来拟合局部点集，估计顶点法向量和曲面在该点的 曲率值，最后基于曲率信息对点模型进行特征检测、去噪和光顺，以及对模型进 行保特征的简化，建立点模型的层次多分辨率表示。另一条是基于平面或球面对 点模型进行参数化，在参数域上进行均匀采样，通过参数域和空间域的映射关系 建立点模型的多分辨率表示，亦可进行纹理映射，变形以及各种几何信号处理。 该系统设计并实现了曲率计算、特征线检测、点模型光顺去噪、参数化等一系列 基础算法，是一个功能丰富的数字几何处理平刽”l 。 点造型系统具备强大的形状表现力、高效的显示机制和快速、便捷的交互方 法，能广泛应用于虚拟现实、人体模特设计、娱乐广告等一系列领域。但另一方 面，目前的点造型系统在系统兼容性、特征细节精确表达等方面还存在一定缺陷， 这严重限制了其在制造业的应用。 1 1 4 点造型存在的问题 点模型的处理和编辑通常需要满足一个假设条件：点云数据来源于一个潜在 的流形表面s 。在理论上，有待处理的点云应满足该条件，但实际应用中，比如 反求工程中，受被测样件本身结构和测量环境的影响，测量数据很可能来源于不 同的流形表面。对于工程实际中这类常见数据，很难直接应用点造型技术予以处 理，这是点造型技术在实用性方面存在的一个问题。 点模型是点造型系统的核心，而目前通用的c a d c a m 系统都构建于n u r b s 曲面模型之上，缺乏对点模型直接、有效的支持。以e d s 公司的u g 系统为例， 该系统将点作为一个独立的体素，至多只能接收2 万左右的数据点，而这对表达 一个点模型来说通常是不够的。没有通用c a d c a m 系统的支撑意味着还很难 将现有的模拟装配、加工轨迹计算等技术应用于点模型上，这在很大程度上限制 了点模型在制造业中的应用。 在点造型过程中，特征被简单视为具有曲率突变性的特征线、凹凸形状或边 界。而在制造业领域，特征是由实体体素构成的能够被固定的方法加工成型的特 定型体，如孔、槽和法兰等。点模型来源于原始的测量数据，受测量环境和设备 的影响，测量数据通常包含一定幅度的随机噪声，这使得点模型只能近似地表达 加工特征的形状，而无法精确的描述特征细节更不能使特征间满足原始的几何约 束关系。另一方面，点模型也缺乏对特征简洁、有效的参数表达。这都会给后续 产品的加工和再设计带来很大困难。以底部为平面的槽特征为例，平面的简洁解 5 浙江大学博十学位论文 析表达式可使糟的加工轨迹计算非常方便，而且效率和精度都非常高。同时，通 过修改平面的参数还可以很方便的获取不同深度的槽特征。但对于点模型来说， 由于缺乏“平面”信息，该表面的加工质量难以保证，而且上述简单的参数化设 计功能也很难实现。由此可见，点造型技术在制造业中的应用仍然受精度、效率 等因素的制约。 1 2 基于点云和特征的反求工程c a d 建模技术 反求工程的目标在于利用计算机辅助技术、数字化测量技术和几何模型重建 技术，由产品实物原型构建c a d 模型，进而支持产品的进一步创新设计。正如， 前文所述，基于点表达的产品模型在系统兼容性、特征细节精确表达和参数化创 。 新设计方面还存在一定的缺陷，因此直接应用点造型技术还难以构造符合工业应 用需求的产品模型。基于这样的背景，国内外许多学者采用基于点云的曲面造型 技术。 1 2 1 基于点云的反求工程c a d 建模技术 在反求工程中，使用的曲面模型主要包括三角平面片模型、三角b 6 z i e r 曲 面模型和矩形域曲面模型。曲面模型不同，基于点云的建模方法也不同。 三角平面片模型 基于敏乱点云数据构建三角网格( 三角平面片) 模型，是c a d 领域的一个经 典问题。h o p p e 及其合作者进行了卓有成效的开创性工作。他们的方法首先自动 计算法矢信息，然后用切平面线性逼近待重建曲面的局部形状，最后利用 m a r c h i n gc u b e 算法构造三角网格模型【”。随后许多学者就反求工程领域内散乱 数据点集的三角剖分、网格优化、网格简化等问题进行了研究 2 6 - 2 9 。 随着测量技术的发展，点云的形体表现力不断增加，同时，点云密度也越来 一 越大。测量点问的距离相对于n c 加工精度而言已足够密集( 大多数情况下比 n c 加工步长还要小) 。在这种情况下，基于点云构建的三角网格模型一方面可 以直接用于n c 加工，反求建模软件c o p y c a d 就提供这样的功能；另一方面还 可以将其作为s t l 模型进行快速原型制造【3 0 1 ，这使得网格模型具有较强的产品 外形复制能力。 综上所述，与点模型相比，网格模型在加工和制造方面具有一定优势；但同 时应该注意到：网格模型并没有从本质上弥补点模型的缺陷。首先，仅具有位置 连续性的网格模型也难以精确表达特征细节。其次，网格模型缺乏特征的几何参 数信息，并不能完整地表达原始设计的意图，也难以实现参数化设计。再次，目 前，散乱测量点的三角化还不存在公认的最优解，这使模型中难免引入一些人为 的因素，这在定程度上限制了反求建模向自动化、智能化方向的发展。 6 第一章绪论 三角b 6 z i e r 曲面模型 d ec a s t e l j a u 早在上世纪5 0 年代末就提出了三角b 6 z i e r 曲面，但是其应用 直到1 9 7 5 年才被b o e h m 发现1 3 1 1 。三角b 6 z i e r 曲面的特点在于构造灵活、边界适 应性好、能插值于任意拓扑结构的散乱数据点集。f a r i n 证明了三角b z i e r 曲 面间c 1 拼接的不满足性，给出了c - t 分割算法，并将曲面间的连续性条件由c l 改为g 1 ，解决了约束矛盾，完成了复合三角l 琵z i e r 曲面的整体g 1 构造 3 2 - 3 4 1 。c - t 分割思想已使用了十多年，目前在散乱点插值领域仍被广泛使用p ”。 在国内，浙江大学是研究散乱数据三角曲面插值理论并将该理论用于解决反 求工程c a d 建模问题较早的单位之一。柯映林博士【3 6 l 在其博士论文中系统研究了 三角8 6 z i e r 曲面造型，并提出了将三角b z i e r 曲面模型应用于反求工程的设想， 其合作者进一步研究了基于三角b 6 z i e r 曲面的反求工程c a d 建模印j 、高级几何 计算1 3 8 3 9 1 、加工及与r p 的集成1 4 0 , 4 1 1 、特征提取与处理等 4 2 1 ，成功架构了基于三 角b 6 z i e r 曲面的反求工程c a d 建模体系。 与三角平面片模型相比，三角b 6 z i e r 曲面模型能达到整体g 1 连续，模型的 表面品质有明显的提高；但同时，这种模型也只能近似表达产品的几何外形而不 能准确、完整表达产品的局部特征细节，而且，与点模型类似，三角b 6 z i e r 曲 面也很难为通用c a d ，c a m 系统所接受或相容，因此也就无法利用成熟c a d 系统 的模型管理、模型处理和分析技术。这些因素促使研究人员进一步探索更好的曲 面模型，以便满足反求工程c a d 建模的应用需求。 矩形域曲面模型 常用的矩形域曲面有b 6 z i e r 曲面、c o o n s 曲面、n u r b s 曲面等，其中，n u r b s 曲面因为具有统一表达自然二次曲面和自由曲面能力、具有局部调整性、几何不 变性、仿射不变性和计算稳定等重要几何特征，成为工业界事实上的曲面表达标 准【3 1 1 。 国内外许多著名学者利用n u r b s 曲面的简化形式，即b 样条曲面实现了产 品模型重构1 4 3 4 5 1 。其基本思路是：首先将点云划分为一系列互不重叠的数据集， 而后通过逼近每个集合中的数据点分片构建b 样条曲面，最后将多张b 样条曲 面缝合组成样件的b r c p 模型。上述构造过程的关键和难点在于点云的区域划分。 可以说，划分结果在很大程度上决定了后续建模的难度和模型的精度及品质。 e e k 4 6 1 等人首先将点云三角化，在三角网格模型中随机选择一些种子网格，基于 多源最短路径原理，通过从每个种子网格向外生长的方法将三角网格划分为多个 区域。一些软件已经基于这种方法构建了自动化程度较高的区域分割工具；但需 要注意的是，在这种方法中种子网格的选择依然非常困难，原始的随机选择方法 显然不能满足要求，纯粹基于拓扑学理论选择种子网格【4 7 】又会导致区域划分结果 7 浙玎大学博十学倚论叟 过于细碎。换句话说，e c k 的方法只是将一个难题转化为男一个难题，并没有从 根本上提供一种公认的最优化准则来指导分割的过程。可以说，目前，要构造高 质量的矩形域曲面模型，必须依靠建模人员的经验和智慧进行区域划分。这种过 于依赖用户技能的反求工程c a d 建模方法会使实际建模过程繁杂，难于控制和 把握最终模型的精度和品质。 与其它两种模型相比，b 样条曲面模型在连续性和系统兼容性方面都具备一 定的优势。但是，从工业产品的设计流程可以知道，包括平面、球面、柱面和锥 面在内的二次曲面特征才是产品参数信息的主要载体。b 样条曲面模型在本质上 并不能理想表达原型实物的隐含设计理念。 综上所述，在参数化设计思想大放异彩的今天，以构建三角平面片模型、三 角b 6 z i e r 曲面模型和b 样条曲面模型为目标的纯几何反求建模方法已经难以满 足实际工程的需要。为提高重构模型的工程应用价值，目前，越来越多的学者试 图将“特征”融入到反求建模过程中。 1 2 2 特征在反求工程c a d 中的地位和作用 特征作为产品参数的主要载体，是参数化模型的一个基本组成部分。在反求 工程中，特征的作用主要体现在以下四个方面。 提高反求建模的效率和自动化程度 决定反求建模效率和重构模型质量的关键是建模策略。通过分析反求建模策 略，我们可以明确了解应该采用何种手段、需要哪些数据、经过什么步骤来完成 零件的三维建模。在传统的反求工程中，建模策略只能完全依靠造型人员根据样 件实物的形状来制订。若样件的拓扑结构复杂或建模人员的造型经验不足，则很 可能制订出不合理的建模策略，从而使建模过程事倍功半。相反，基于特征进行 建模，则可采用一种统一的建模思路，首先，基于点云的微分几何信息，将其分 解为特征单一、互不重叠的数据集合；而后，针对每个数据集分别提取特征参数、 重构特征曲面；最后，通过特征曲面间的几何与拓扑运算构造样件的c a d 模型。 在这样一个清晰的建模策略的指导下，一方面，建模人员能在很大程度上避免错 误或多余的建模操作从而节省大量的建模时间，另一方面，建模过程中的人为因 素明显减少，建模的自动化程度明显提高。 提高重构曲面的精度 传统的反求建模方法通过插值或逼近测量点构建b 样条曲面、三角网格或三 角b 6 z i e r 曲面：而工业产品中大量使用的足包含平面、柱面、球面、锥面在内的 二次曲面，两者在表达方式上的本质差异和测量数据中存在的随机噪声决定了传 统的建模方法难以精确表达二次曲面。利用特征技术，则可以在一定程度上解决 8 第一覃绪论 这个问题。特征技术首先识别点云中的二次曲面特征，而后利用特征提取技术获 取特征参数，最后重新设计特征曲面。通过这种方法构造的特征曲面其表达方式 和几何参数符合产品的设计意图，精度也更高。 有利于和c a e c a m c a p p 等技术进行集成 特征并不是一个只适用于反求工程的概念，在不同领域中应用的特征其定义 也有所区别。常用的特征有加工特征和装配特征等等。这些特征虽然附着的工业 信息各不相同但都是以特定的几何形状为基础的【4 羽。从这个角度来说，只要组合 反求工程中提取的特征曲面元就能构建很大一部分符合设计、加工、制造、质量 分析等要求的特征，从而为c a e c a m c a p p 等技术的集成奠定坚实的基础。这也 正是传统的基于自由曲面的反求建模技术所欠缺的。 有利于产品的创新设计 反求工程的任务是基于已有设计的再设计。传统的反求建模技术更多关注从 实物原型或零件中获取较低层次的几何和拓扑信息；所构建的模型只是对产品外 部形状进行的一种逼近，很少涉及影响产品气动性能和制造工艺的特征信息；这 给模型的后续修改设计造成不便。基于特征构建的参数化模型，就可以实现尺寸 参数驱动的修形设计，进一步缩短新产品研究与开发周期。 总的来说，特征在反求建模、系统集成和参数化设计方面都具有明显的优势； 发挥这种优势需要强大的特征识别、分析和处理工具；为此，一种基于特征的参 数化反求工程c a d 建模技术逐渐成为反求工程领域的一个热点问题。 1 2 3 基于特征的反求工程c a d 建模技术 产品三维c a d 模型的参数化重建过程可视为对参数化曲面特征单元、约束 关系和拓扑关系图的组建过程。构建参数化模型的流程( 图1 2 ) 基本由数据预 处理、区域分割、特征提取与重构、约束优化和曲面编辑、曲面分析评价等6 个 主要步骤。数据预处理包括噪声去除，数据压缩、数据匀化、局部数据补全等一 系列的操作运算，以降低测量过程中由于人为和随机因素的影响，得到精确、符 合期望采样规律并能比较全面地反映产品对象特征的离散数据点集。基于几何微 分量估算和误差评价，数据分块将测量数据分割为属于不同曲面片的数据子集， 并探求蕴含其中的设计理念、功能需求、工程约束、力学性能以及美学原理，同 时获取其外延形式特征属性。曲面重构主要根据数据分块过程中所获取的特征曲 面属性，分析、理解曲面的设计意图和造型规律并进一步重构特征曲面。约束优 化指在各种约束条件( 平行、垂直、重合、相切等) 和误差控制下，优化曲面形 状，使曲面满足产品原始的几何约束关系。优化后的曲面将输入编辑器，通过曲 面间的一系列求交，裁减和过渡等编辑操作构造b r e p 模型。最后，以原始点云 9 浙江大学博十学位论义 为蓝图，对重构参数化模型的保形性、光顺性、约束的完备性进行全面的评估。 特征是参数化反求建模的核心，国内外学者围绕这个核心，分别从点、线、 面等不同层次研究了参数化三维c a d 模型重建的关键技术。在参数化建模过程中 与特征关系最紧密的是区域分割、特征提取和约束优化，本章将针对这几个问题 进行综述。 图i 2 参数化反求建梗流程 区域分割：基于点云重构产品的参数化特征模型，首先需要从点云中分离出 与各特征面对应的数据区域。目前的分割算法可以分为三种：基于边的方法 4 9 l 、 基于面的方法 5 0 , s l 】以及混合方法。 基于边的方法首先提取边界点，而后连接这些点构造连续边界。1 9 9 6 年美国 俄亥俄州立大学h u a n g 博士利用三角网格的边界曲率识 3 f j n 域边界【4 9 1 。2 0 0 2 年， 南朝鲜光州科技研究所w o o 提出了基于八叉树的三维栅格细分法【5 4 。算法首先 对包含网格数据的包围盒进行八叉树细分，直至包含在栅格内的点的估算法矢标 准偏差小于用户输入的最小值。最后合并边长小于某一定值的栅格并从中识别点 云的棱边，进而基于区域生长法实现扫描数据区域分割。 基于面的方法首先选取一系列的种子点，而后基于给定的相容闽值，从种子 点向外生长得到相关的区域。根据方法不同又可细分为基于曲面法矢、曲率相似 性的方法1 5 3 - 5 5 1 和拟合误差控制的方法1 5 6 1 ，基于面的方法受噪声的影响更小，但是 它对闽值过于敏感。 为了综合上述两种方法的优势，近年来提出了多种混合分割方法p m 9 1 。其中 b e n k 6 特别提出了一种常用工业零件测量数据的分割方法1 5 9 1 。该方法通过一系列 不同等级的测试算子实现特征的动态分割。分割过程中每个算子依次作用于嘲格 模型之上，对网格中包含的过渡面、二次曲面、线性拉伸面等特征进行逐层的分 割和剥离。这种方法思想简单，鲁棒性也比较强，不足之处在于需要首先基于测 量数据构建三角网格的拓扑结构，而且算法需要设置多个阈值来控制分割过程， l o 这给使用者带来很多不便。 特征提取与重构：在工业产品中，平面、球面、柱面、锥面等二次曲面特征 出现的频率最高，针对这类特征曲面提取技术的研究也较为集中。l u k f i c s l 6 0 1 和 m a r s h a l l 6 1 l 基于最小二乘逼近法提取平面、球面、柱面、锥面等二次曲面。c h e n l 6 2 1 首先基于逼近方法得到一般的曲面表达式，而后应用遗传算法( g e n e t i c a l g o r i t h m s ，g a ) 中的交叉与突变算子迭代