（机械制造及其自动化专业论文）基于cmm测量数据的曲面重构关键技术研究与实现.pdf

京理工大学博上学位论文基于c m m 测量数据的曲面霞构关键技术研究与实现 摘要 作为近年来先进制造领域的研究热点，逆向工程已发展为c a d c a m 系统中一 个相对独立的研究分支，其相关领域包括几何测量、图像处理、计算机视觉、几何造 型和数字化制造等。 曲面重构是逆向工程的关键技术之一。本文对逆向工程中曲面重构的关键技术进 行了详细而深入的研究，研究了数据处理技术、n u r b s 曲面重构技术和三角割分算 法，目的是为武器产品技术吸收、消化及创新开发提供更加完善的手段和方法，为歼 发实用的逆向工程软件奠定基础。 本文首先研究了坐标变换、坐标归一化和数据滤波的数据预处理技术。以此为前 提，提出了基于分层维的数据排序方法，针对c m m 扫描线数据，定义了分层维，并 进行了数据分层和数据排序，完成了数据拓扑关系的建立。以数据拓扑结构的建立为 基础，研究了距离阈值法和向量角度法相结合的数据精简算法。重点研究了基于分层 维的特征提取技术，完成了各类不连续点( 跳跃点、尖点、折痕点以及曲率极大值点 等) 的特征提取。研究了基于特征线框的数据分块技术。 。 以基于分层维的数据处理技术研究为基础，本文提出了一种利用数据点特征的非 均匀有理b 样条( n u r b s ) 曲面重构方法。针对数据点的分布不均匀性，通过累积弦 长法构造非均匀节点矢量，保证了曲面的插值精度。研究并优化了b 样条求值的快 速算法，通过符号运算将b 样条基函数描述为分段多项式的形式，通过分层维的设 定来确定最小初始化数组，利用一个临时多项式存储中间计算结果，最终在大规模计 算时，进行的是多项式的求值。这样不仅大大加快了b 样条求值的运算速度，而且 通过最小初始化数组的确定以及多项式数组的重复迭代覆盖，使计算获得较高的空间 利用率。 根据逆向工程中散乱数据点规模越来越大的趋势，为缩小剖分时搜寻和遍历数据 点的空间范围，为提高算法效率，本文研究了大规模散乱数据的空间划分方法及相应 的数据结构和编码方案。在分析典型平面及空间散乱数据三角剖分算法思想的基础之 上，提出并实现了基于微元网格扩张的三维散乱数据点的空间直接三角剖分算法，首 次提出了外连剖分和内连剖分的概念。该算法能在线性时间内完成三角剖分计算，其 总体计算复杂度为d ( ) ，有效地降低了三角剖分算法的时间复杂度，提高了削分后 网格的质量。 在上述研究的基础上，分析了逆向工程系统的开发方法和包含的软件模块，开发 了软件原型系统。以施密特望远镜关键零件一主镜室和底支撑的反求设计为例说明了 立i _ 巳一 望主堡苎 一 软件在军用产品方面的应用。本文根据工程需求制定了从数据采集到c a d 的反求方案，根据反求方案对主镜室和底支撑进行了反求没计制造。反求结 证了数据处理和曲面重构算法的准确性，而且验证了反求方案的有效性。 逆向工程，c m m ，数据处理，n l r r b s ，三角剖分，曲面重构 堡墨堡三查兰堡! 兰堡堡苎 兰三旦竖型里鍪塑塑些耍蔓塑茎壁茎查竺塑皇塞墨 、 一a b s t r a c t a so n eo ft h eh o ts p o t so ft h ea d v a n c e dm a n u f a c t u r i n gf i e l d ，r e v e r s ee n g i n e e r i n gh a s r e c e n t l yb e e nar e l a t i v e l yi n d e p e n d e n tr e s e a r c hb r a n c hi nc a d c a ms y s t e m s i t sc o r r e l a t e a r e a ；n c l u d e sg e o m e t r i cm e a s u r i n g , i m a g ep r o c e s s i n g ，c o m p u t e rv i s i o n ，g e o m e t r i c m o d e l i n ga n dd i g i t a l i z a t i o nm a n u f a c t u r i n ge t e s u r f a c er e c o n s t r u c t i o ni so n eo ft h ek e yt e c h n o l o g i e si nr e v e r s ee n g i n e e r i n g t h ek e y t e c h n o l o g yi ss t u d i e di nd e t a i li nt h i sp a p e r t h et e c h n o l o g i e so fd a t ap r o c e s s i n g ，n u r b s s u r f a c er e c o n s t r u c t i o na n dt h et r i a n g u l a t i o na l g o r i t h mf e a t u r ea r er e s e a r c h e di no r d e rt o s u p p l yt h ep e r f e c tw a y sa n dm e a n sf o rt h et e c h n i q u ea b s o r p t i o n , d i g e s t i o na n di n n o v a t i o n o fw e a p o n sp r o d u c t sa n db u i l du pf o u n d a t i o no f d e v e l o p i n gt h ep r a c t i c a lr e v e r s e e n g i n e e r i n gs o f t w a r e f i r s t l yt h ed a t ap r e - p r o c e s s i n gt e c h n o l o g i e sa r er e s e a r c h e d ，w h i c hi n c l u d ec o o r d i n a t e t r a n s f o r m , c o o r d i n a t ef u s i o n , d a mf i l t e r i n g u n d e rt h i sp r e m i z e ，t h em e t h o do fd a t as o r t i n g b a s e do nl a y e r i n gd i m e n s i o ni sp u tf o r w a r d w i t ht h ec m m s c a n n i n gd a t ap o i n t s ，t h el a y e r d i m e n s i o ni sd e f i n e d ，d a t al a y e r i n ga n dd a t as o r t i n ga r ep e r f o r m e d t h e t o p o l o g yr e l a t i o ni s e s t a b l i s h e d o nt h eb a s i so fd a t at o p o l o g y , t h ea l g o r i t h mo fd a t ar e d u c i n gw h i c hc o m b i n e s d i s t a n c et h r e s h o l d 、耐t l lv e l t o ra n g l ei sr e s e a r c h e d t h et e c h n o l o g yo ff e a t u r ee x t r a c t i o n b a s e do nl a y e r i n gd i m e n s i o ni sa l s os t u d i e 针对扫描线数据，定义了分层维，并以此为依据进行了数据分层，然后，采 用首尾判断法进行层内点的排序，完成了数据拓扑关系的建立。 以数据拓扑结构的建立为基础，研究了距离阈值法和向量角度法相结合的数 据精简算法。 重点研究了特征提取技术： 研究了面向单值曲面边界提取的经纬线扫描算法和基于扫描线数据的边界修 改算法； 提出了基于分层维的特征提取方法，完成了各类不连续点的提取； 研究了基于微元网格扩张的三角剖分算法的任意非封闭曲面边界提取和曲面 尖锐棱线的自动提取； 研究了交互式数据分块和基于特征线框的区域分块技术。 其次，在基于分层维的数据处理技术研究的基础上，针对c m m 测量数据的分布 不均匀性，采用累积弦长法构造非均匀节点矢量，保证曲面的插值精度。 研究实现n u r b s 求值优化算法，通过符号运算将b 样条基函数描述为分段多项 式的形式，通过分层维的设定来确定最小初始化数组，利用一个临时多项式存储中间 计算结果，最终在大规模计算时，进行的是多项式的求值，大大加快运算速度。 再次，根据逆向工程中散乱数据点规模越来越大的趋势，为缩d , n 分时搜寻和遍 历数据点的空间范围，为提高算法效率，研究大规模散乱数据的空间划分方法及相应 的数据结构和编码方案。在分析典型平面及空自j 散乱数据三角剖分算法思想的基础之 上，研究基于微元网格扩张的三维散乱数据点的空间直接三角剖分算法，提高刮分后 网格的质量。 最后，开发逆向工程软件原型系统，介绍系统开发方法和包含的主要模块。以空 间碎片望远镜关键零件一主镜室和底支撑的反求设计为例，根据工程需求制定从数据 采集到c a d 模型建立的反求方案，由反求方案对关键零件进行了反求设计制造，用 以说明逆向工程软件在军用产品方面的应用。 1 6 本文章节安排 本文的章节安排如下： 第l 章绪论 本章介绍了逆向工程的意义及应用，分析了国内外的研究现状，阐述了逆向工程 南京理t 人学博i 学位论艾基f c m m 铡量数据的曲面雪构关键技术研究与实现 包含的关键技术，最后给出了本文的选题意义、主要研究内容和章节安排。 第2 章基于分层维的数据处理技术研究 针对c m m 测量的大量无序数据，本章在分析研究坐标变换、坐标归一化和数据 滤波的数据预处理技术的基础上，提出了基于分层维的数据排序技术，建立了数据的 拓扑结构；研究了距离阂值法和向量角度法相结合的数据精简算法；研究了单值曲面 边界的提取算法，提出了一种基于扫描线数据的边界修改法，重点研究并实现了基于 分层维的特征提取算法。最后，采用基于边的数据分块方法，研究了基于特征线框的 区域分块技术和交互式数据分块技术。 第3 章基于n u r b s 求值优化算法的曲面重构技术研究 本章采用累积弦长法构造非均匀节点矢量，研究实现了非均匀b 样条插值算法。 对n u r b s 求值算法进行了优化，通过符号运算将b 样条基函数描述为分段多项式的 形式，通过分层维的设定来确定最小初始化数组，不仅提高了n u r b s 求值的效率， 而且使计算获得很高的空间利用率。最后，用实例验证了n u r b s 曲面重构算法的可 行性和准确性。 第4 章基于微元网格扩张的三角剖分算法研究 本章首先介绍了散乱数据空间直接三角剖分的算法思想，然后提出了一种大规模 散乱数据的空自j 划分方法，详细研究了散乱数据空间直接三角剖分所要解决的关键问 题，在此基础上给出了基于微元网格扩张的散乱数据空自j 直接三角剖分的算法过程， 分析了算法复杂度，并用实例验证了算法的可行性。 第5 章逆向工程造型系统的开发与应用 本章主要介绍了逆向工程造型系统的开发方法和包含的主要模块，给出了系统的 部分界面。以空间碎片望远镜关键零件主镜室和底支撑的反求设计为例，根据工程 需求制定了从数据采集到c a d 模型建立的反求方案，由反求方案对关键零件进行了 反求设计制造，用以说明逆向工程软件在军用产品方面的应用。 第6 章总结与展望 本章对全文的工作进行了总结，对今后的工作做了展望。 全文各章节研究内容之间的关系如图1 6 1 所示。 1 9 ! 堕堡 堕：! ：堡苎 2 0 图1 6 1 论文结构图 厂= 二二二= 堕塞堡 根据测量数据的不同来源，逆向工程中原始数据的组织和处理形式也各不相同。 无论采用何种数据获取的方式，都会不可避免地引入数据误差，尤其是实体尖锐边和 边界附近的测量数据。数据处理是逆向工程的关键环节，是对获取数据进行处理，如 数据滤波、数据精简、特征提取等等。处理结果直接影响后期曲面重构的质量。本文 针对c m m 测量的大量无序数据，首先对坐标变换、坐标归一化和数据滤波的数据预 处理技术进行了分析和研究，然后提出了基于分层维的数据排序技术、数据精简技术、 特征提取技术，最后研究了基于特征线框的数据分块技术。 2 1 数据预处理技术 2 1 1 坐标变换和坐标归一化技术 在c m m 测量过程中，有时会出现如下情况： a 被测物体的尺寸过大，超出了测量机的行程； b 由于实物几何形状的干涉阻碍，测头无法测量物体的反面； c 被测物体有定位或夹紧要求，一次测量无法同时获得定位面及央紧面的测量 数据，需引入二次测量。 这些情况下，测量数据非一次完成。有时被测数据被分成多块，基准不同，为了 完整地反映被测物体的形状，必须进行坐标变换和坐标归一化的处理【1 1 2 s 4 3 1 。 ( 1 ) 坐标变换 坐标变换的理论依据是计算机图形学。在计算机图形学中，将线性代数与投影几 何相结合，使用了齐次坐标的概念，从而使变换处理能够更一般的进行。三维空问内 的一点( x ，y ，z ) 写成齐次坐标( x ，y ，z ，1 ) 的形式。以下所讨论的坐标变换都 参照原点进行。 坐标变换公式为： p s = p 耳( 2 1 ) 耳= 瓦乃( 2 2 ) 其中：p 。为变换前的坐标表示，p 口为变换后的坐标表示，乙为变换矩阵； 为旋转变换矩阵，珐为比例变换矩阵，为平移变换矩阵。 2 l 2 摹于分层维的数据处理技术研究 博1 ：论文 本文研究采用面向对象技术，把坐标变换封装成一个类，并提供类的接口。类的 定义包含矩阵的表示、矩阵变换、矩阵的求逆和矩阵的相乘等。类的成员函数定义中， 采用一维数组定义矩阵。类的接口还包含专门的数据输入和数据输出函数。 坐标变换类的功能有： 坐标的平移； 分别绕x 、y 、z 轴的旋转； 坐标绕任意轴的旋转； 坐标的缩放。 坐标类的类图如图2 1 1 1 所示。 c o o r d i n a t et r a n s l a t e ，p o i n t ：s t r u c t p o i n t p o i n tv a l u e ：d o u b l e + 一n e wx 。n e wv ，b e wz ：d o u b l e p o i n t _ x , p o i n ty ，p o i n t _ z ：d o u b l e d i r e c t i o nx ，d i r e c t i o nv ，d i r e c t i o nz ：d o u b l e - r o t a t ea n g l e ：d o u b l e s c a l e ：d o u b l e + s e t s t r u e t p o i n t ( d o u b l e + 1 + m a t r i xm u l t i ( d o u b l e ，d o u b l e + 1 + t r a n s l a t e ( d o u b l e ，d o u b l e ，d o u b l e ) + r o t a t ex ( d o u b l e ) + r o t a t e _ y ( d o u b l e ) + r o t a t ez f d o u b l e ) + r o t a t e ( d o u b l e ，d o u b l e 。d o u b l e ，d o u b l e + r o t a t e ( d o u b l e ，d o u b l e ) ：7 个d o u b l e + s c a l e t r a n s f o r m ( d o u b l e ) + g e t p o i n t v a l u e o 图2 1 1 i 坐标变换类图 ( 2 ) 坐标归一化技术 多视数据由多面片数据组成，可通过物坐标系一一进行描述。假设测量时物体任 意摆放，则无法获得面片与物坐标系问的联系。只有在测量时指定一些点或特征，通 过这些特定的基准点或特征的测量数据，来确定变换矩阵。通过变换矩阵，建立多视 数据间的联系，最终将多视数据坐标归一化。 本文研究采用基于三个基准点的数据坐标归一化方法，通过对齐测量时指定的三 个基准点，实现多视数据的匹配。分块测量时，首先在公共测量表面建立三个基准点。 通过对齐三个基准点，求出坐标旋转变换和平移变换矩阵，实现三维测量数据的对齐， 实际上是将坐标归一化问题转换为坐标变换问题。 南京理t 人学博 学位论文堆于c m m 测量数据的曲面重构关毽垫垄型塑! 塞堡 图2 i 1 2 已设置基准点的多视测量 考虑图2 1 1 2 中的情况，测量表面被分为两块s ，s 。在公共测量表面中确定 的三个基准点为a ，b ，c 。基准点的布置原则是：基准点必须是在两次测量中都 可以测到的点；指定的基准点既可以人工设定，也可以为测量对象固有，但必须 是测量数据点集中能准确识别、匹配和定位的点；a 、b 、c 三点不能共线，应避 免鲋b c 成为狭长三角形，其包围面积应尽可能大，以减少测量误差对变换的影响。 在两次测量中分别记基准点a 、b 、c 为p 卜p 2 、p 3 和只。，忍、b 。对于数据 块s ，其测量坐标系为 x y z ；数据块中，测量坐标系为扛夕，z 0 ，如图2 1 i 2 所 示。通过对齐a 、b 、c 三个基准点，求出平移矩阵和旋转变换，实现坐标系的统一。 将s 。固定，通过对s 内的点集进行相同的变换，即可实现两块测量数据的坐标归一化。 上述研究是基于将三维几何物体视为刚体，通过求取刚体相对运动的平移和旋转 矩阵来实现数据坐标归一化的。主要问题是由于测量误差的存在，两次测量得到的基 准点a 、b ，c 的相对位置不可能完全相同，所得到的变换将引起物体的变形，下面 引入最小二乘法来解决该问题。 由于测量误差的存在，坐标变换的过程应表示为： 只= 耳尼+ 4 ( 2 3 ) 式中p 。：变换后的三维数据点；t ：变换矩阵： p l ：变换前的三维数据点；声：测量误差。 万的最小二乘目标函数为： ( 2 4 ) 式中p ：空间中的三维数据点。 满足式( 2 3 ) 的最小二乘解为耳，令岛= 昂p ，易知此时p ，与b4 的重心相 同。即： 2 p耳 一 p ，硝 f i f 2 基于分层维的数据处理技术研究 博卜论文 记： o = c 其中：铲- ( p , + p 2 + p s ) = ；孝动 则式( 2 4 ) 可转化为： c ，= ；o ，。协却，。) c ，= j 1 0 ，+ p ：+ 办) d | = p | 一c ” d i = p t _ c 一 采用矩阵的奇异值分解法即可确定i ，至此，就得到了坐标变换矩阵。 2 1 2 数据滤波技术 ( 2 5 ) ( 2 6 ) ( 2 7 ) ( 2 8 ) ( 2 9 ) ( 2 1 0 ) ( 2 1 1 ) 测量数据中的噪音不仅直接影响测量的质量，还增加了后续处理的难度，延长后 续处理的时间。因此要采取措施减少噪音对测量数据的影响，措施有两种： ( 1 ) 确定测量中噪音的来源，针对不同来源采取不同的措施，从源头上控制噪音； ( 2 ) 对包含噪音的数据在预处理中进行光顺和除噪，减少噪音影响。 在实际测量中采取预防措施可以减少噪音的产生，但并不能完全做到消灭噪音， 因此对测量数据的光顺和除噪的研究是十分必要的。根据测量数据的组织形式，光顺 和除噪的对象主要有点云数据和三角网格数据两大类。因为三角网格数据中包含有明 确的拓扑关系，所以在光顺中可以快速的获取相邻的样本点，便于光顺。因此对三角 网格数据光顺、除噪的研究相对较多。三角网格光顺和除噪的方法有三种：最小能量 法【1 4 1 、信号处理澍1 1 5 1 1 7 1 和曲率均匀法【1 1 蚰。 本文中实物外形数据是通过三坐标测量机来获取的大量数据“点云”。为降低或 消除噪音点对后续重构的影响，有必要对测量数据进行滤波。本文研究采用人机交互 式滤波方法对明显的噪音点进行剔除，采用二次取中法对重复测量产生的批量噪音点 进行滤波，分别描述如下： ( 1 ) 人机交互式滤波 人机交互式滤波是逆向工程中最简单的剔除噪音点的方法。该方法简单易于操 作，明显直观，主观性很强，不适用于高密度“点云”。对于高密度“点云”，常采用 程序判别滤波：现阶段的通常采用标准高斯、n 点平均滤波、中值滤波以及自适应滤 2 4 以 一 忱 ， j j f 南泉理t 夫学博i ：学位论文基f c m m 铡量教姑的1 f i 面蕈构关键技术研究与实现 波法等。 本文研究在交互式滤波方法中，采用了空间点的坐标变换技术，如2 1 1 节所述。 该模块的具体思路是：首先，通过t x t 或i g e s 读写接口将原始数据导入程序中， 借助w i n d o w s 系统自带的o p e n g l 图形库函数显示所有数据点；然后，对所有点实 施统一的坐标变换，进行多角度地观察，判断出明显的噪音点，通过鼠标和快捷键将 它们标识并删除；最后，明显的噪音点都判断完毕后，用1 x t 写接口将真实、有效 的数据写入t x t 文档。 人机交互式滤波效果图如图2 1 2 1 所示。 mi i i ii i i i m 1 l l luj 目嗣 一 -， 噪音点 ( a ) 滤波前的枪拖数据 | 、 善j - | 、 ( b ) 滤波后的枪拖数据 图2 1 2 i 枪拖数据滤波效果圈 ( 2 ) 二次取中法滤波 对于明显的不符合曲面变化趋势的少量数据点，可以采用人机交互的方式剔除。 2 s 2 摹于分层维的数据处理技术研究 博t 论文 而对于由于重复测量而引起的批量噪音点的情况，人机交互的方式则不适合。 图2 1 2 2 显示因重复测量而得到的一组噪音点，图2 1 2 3 显示以该组噪音点构 造的控制多边形。可以清楚的看到噪音点对控制多边形的影响：它使控制多边形出现 不稳定性。这将严重影响重构曲面的质量，同时重构曲面的光顺性也得不到保证。 图2 1 2 2 重复测量造成的噪音点 图2 1 2 3 由包含噪音点的数据反算得到的控制点多边形 针对由于重复测量而引起的批量噪音点的情况，本文研究采用二次取中法，实现 对该类噪音点的平滑处理。二次取中法的原理如图2 1 2 4 所示。当三点a 、b 、c 组 成的三角形顶角- - a b c 为锐角时，从顶点引出一条三角形的中线，并选取中线的中 点作为新的顶点。 因为i a c l 2 = i a b l 2 + b c i l 2 a b i b c i e o s z a b c ，所以本文采用式( 2 1 2 ) 作为判断 z a b c 是否为锐角的依据。 图2 i 2 4 二次取中法 ( 2 1 2 ) 1j1 、 妻皇墨二叁芏整主兰堡垦塞羹至堡坚丛塑鐾墼萋盟些堕重塑羞壁塾墨缝塞蔓塞墨 2 2 基于分层维的数据排序技术 将原始测量“点云”按一定的规则摊廖，使之在存德上具有方向性，这种瓣序规 则被赋予了特定的几何或拓扑意义。 1 9 7 7 年，l a w s o n ”1 9 j 提出了基于结点的拓扑关系建立方法，这是后来众多方法的 基础。随后，c h o i 等【l 训提出了踅接形成三维空间散乱点的拓抒关系的方法；先形成 结点列表t l i s t 盾刨戏t b l ( t r m m j e | n tb o u n d a r yl i 鳓。阻t l i s t 为初始完整三角 化。1 9 9 5 年，姜寿山等b i l l 提出了从曲颤凸包形的角度进行散乱数搀优化划分的条件。 实用价值较大的是p a r k 等人f m l 完成的一种自适应的空问散乱点的光滑适近方法，葜 首先基于内鲫边界和特征线构遗初始三角形网格，对存在内边界的区域交互地分为凡 个无内孔的子区域，然后逐步插入最大误差点并递推进行，直到所有数据点在设置的 误差阀值以内。这种方法将拓扑关系的建立和模型重构有效地统一起来，优点是实现 楚单，数据征缩量大而且在加点的过程中其需对局部曲面片茧构。柯映林l ”崾现了 c h o i 提出的三维直接三角化的方法，并将自己提出的平面域内兰角化方法【1 0 】作为在 复杂情况下的补充。f a n g “ 在这方面做过大量的工作，他扶平面敞乱点的处理研究 开始直至空间散乱点，他的主体慝路为采用种被称作包围盒督空剐或营平蟊) 的技 术，将散乱点归入每个盒子当中，然后利用盒子的相互关系建立拓扑。八叉树空间分 割在实体几何建模、运动干涉检验等方葫得到成功运用，可以在三维散乱点云空间划 分拓扑关系中采用。 本文实验吊数据是通过c m m 测量的。测量数据时探头沿某乎氲移动。故在实 体上测得一条处于该平面内的扫描线数据，予是，一个曲基片的测量数据包含大量的 扫描线信息。通常情况下，它们以点集的形式存赭，且誉完全按照扫攒线的顺序排列， 零节的研究内容是通过数据分屡和数据捧序来建立数据闾的拓辂关系。丈觑横敖乱点 的空间划分方法及相应的数据结均和编码方案将在第4 章详细研究。 2 2 1 数据分层 由- t - c m m 攒4 量数据具有层状分布的规律，且每一层片数据几乎( 在测量误差范 固内) 都在一个乎颟内，所以可班通过设定分层维量，来t 鞋g 属子犀一条扫描线的点， 实现数撂分层。 定义五i ：分屡维是将c m m 测量数据中属于相i 司规律的点划分为同一层数据的 依据。本文中的分层维量主要指固定轴( x 、y 葳z 轴) 的a v e r a g e 值和分层困角度0 ， 如闰2 2 1 ，1 所示。 2 堆f 分层维的数据处理技术研究博 论文 固定轴 万j 一壬 扫描线 图2 2 1 1 分层维昔示意图 固定轴的识别可以通过交互的方式，也可进行自动识别。自动识别是根据坐标值 的集中程度来决定的，具体过程是：取数据点总数量的1 0 ，分别统计各个点坐标值 集中的程度，坐标值最集中的一个坐标轴就可以判断为固定轴。计算原理为：采用随 机发生器，进行次数为点集数量总和的1 0 的采集点操作，把采集到的点与其后一点 进行比较，将得到的值进行累加，判断x 、y 、z 三个方向中累加值最小的方向，即 为固定轴方向。其般棼描述为： 胁h ( ( t - - x j ) ，( m j ，) ，( 4 一z 川) ) ( 2 1 3 ) - if - i ，；1 分层维设定后，进行数据分层。层片类c l a y e r 中的点列记录了一个相同值a v e r a g e 和分层圆角度0 ，利用此分层维作为分层依据，判断点集是否属于同一条扫描线，实 现数据分层。因为测量数据往往存在误差，因此需限定一个阈值，如图2 4 1 1 中的占 或庐，使得误差范围内的点分配在同一层。 2 2 2 数据排序 经过数据分层，我们得到了单层的数据点列p o i n t l i s t ，但是，点列内数据仍然缺 乏拓扑顺序，因此，必须进一步进行拓扑排序，重现数据点的真实顺序。 数据排序的基础是以数据点之阳j 的距离作为判断准则，以对应当前点的距离最小 作为判断下一点的标准。然而，由于每一层片的数据是无拓扑信息的，所以在考虑层 片数据的顺序化时，必须考虑起始点是从中间开始的情况，当点列的顺序化进行到边 界点时，如果以距离最小的原则寻找下一点，会出现将中间点作为边界点的下一点的 情况，这就打乱了点列真实的拓扑顺序，如图2 2 2 i 所示。如果以该点集进行重构 将会构造出完全不同于真实曲面的模型。 1jlilv1 南京理t 大学博f 学位论空甚于c m m j 舅j 蕈循据的| 1 1 1 由章均关键技求研兜0 实现 图2 2 2 1 点列排序问韪 为解决上述问题，本文研究采用了首尾判断法：在层片数据顺序建立的过程中， 每次加入一个新点p 之前，比较顺序表中最后一个元素与p 之间的距离d 0 和顺序表 的开始元素与p 之间的距离f i r s t d i s 的大小，如果f i r s t d i s d o ，直接将p 加入顺序表 的，作为当前顺序表的最后一个元素；如果f i r s t d i s c l a y e r l i s t 类存储所有的层； c p o i n t l i s t 类存储点列表 c p o i n t 类为点类； c l a y e r 类为单层类； c r a n g e b o x 类为最小包围盒类。 c p o i m s t o r e ，存储了所有数据的点，是一个列表类，它包含有c p o i n t l i s t 类、 e l a y e r l i s t 类的成员变量以及一个数据包围盒类e r a n g e b o x t c l a y e r 类，存储单个层内的数据点列c p o i n t l i s t 类l ， c l a y e r l i s t 类和c p o i n t l i s t 类是从系统的t l i s t 类继承下来的新类。 本文扩充了每个类的接口，使数据点的操作更方便、合理；同时，通过类封装的 方式，减小了后续丌发的难度。 c p o i n t s t o r e # p o i n t l i s t ：c p o i n t l i g + # l a y e r l i s t ：c l a y o r l i s t # r a n g e b o x ：e r a n g c b o x # f i x e d a x i s ：c h a r # d h ：d o u b l e + s t a t u s ：i t i t + p e r i o d i c ：b o o i # a x i s s e a r c h o # c r e a t e r a n g e b o x 0 # s a m e d i r e e t i o n o # l a y e r f i h c r o + g e t l a y e t f m t l + g e t p o i n t c o u n t ( ) + g e t p o i n t a r r a y 0 + g e t b o x o h g e c l a y e t c o u n t ( ) + a d d f c p o i n t ) + d e i e t 印o i n “c p o i m ) + l o a d f r o m l g e s ( t s t r i n g s ) + l o a d f r o m t x t ( t s t r i n g s + ) + c r e a t c l a y e r l i s t o + m o d i f y b o u n d a r y 0 e l a y 盯 # p o i m l i s t ：c p o i n t l i s t # f i x e d a x i s ：c h a r + a v e r a g e ：d o u b l e + d e r i o d i o ：b o o l # p r 0 i e c t o # s e a r c b m a x d i s 0 + s o r t ( d o u b l e 。i n t ) + a d d ( c p o i n t ) + f i l t e r 0 + t u r n d o w n ( ) + p o i m d e l e t e ( i n 0 十g e t f i r s t p o i n t o 十g e t l a s t p o i n t ( 1 + g e t p o i n t ( 1 u ti n d e x ) + g e t c o u 叫1 t l i 靠 c l a y e r l i s t + g e “i n t ) c p o i n t l i s t - 8 3 “i n t ) + t o p ：c p o i n t + b o r o m ：c p o i n t c r a n g e b o x ( c p o i n t , e p o i n t ) c p o i r l t - x ：d o u h i e + y ：d o u b k + z ：d o u b l e + d i s t a n c e ( o p o i o t ) + s l e n g t h o 图2 2 3 i 建立糕体数据拓扑关系的类层次图 南京理t 人学博i 学位论文幕f c m m 耐量致妊的曲面重构关键技术峒f 究与实现 2 3 数据精简技术 密集点云在提供了更加完整的对象零件的几何信息的同时，也提供了大量的冗余 数据。由于这种数据无法直接进行有效的处理，降低了几何模型重构的效率，故需要 对其进行数据精简。 数据精简的目的就是压缩不必要的数据点，在保证精度的前提下生成适合于后续 操作的结构，并不产生新点，只是简单地对原始“点云”中的点进行删节，并尽可能 多地保留原始数据点的形状特征。 对于高密度散乱点云，参考文献”1 1 提出了三种数据精简准则：分别以精简后数 据集中点的个数、数据集中点的密度阅值及删除一点引起的法向误差的闻值作为精简 结束的依据。 m a r t i n 等【”5 l 利用规则的正交栅格将所有点分离，然后从每一栅格中按照一定规 则选取采样点，完成数据精简。选取采样点的依据为：对栅格中的点按z 坐杯的大小 排序，提取z 坐标为中值的点。精简率由指定的栅格大小决定。这种方法主要针对被 扫描面与光源方向正交的情况，用于快速精简连续的采样表面。 针对扫描线数据的特点，本文研究并实现了距离阈值法和向量角度法相结合的数 据精简算法，此算法既具有距离阈值法的简单易实现的优点，又能够避免将特征点错 误地删除。而对于散乱点云，本文研究了八叉树栅格法数据精简法。 2 3 1 基于分层维的扫描线数据精简算法 最小距离阙值法是最简单的数据精简方法。该方法数据压缩量大，编程容易实现。 基本思路是计算层内数据相邻点之侧的距离，与设定闽值比较，当小于阈值时，将后 一点删除，并继续判断。该方法适合扫描线数据点十分密集，且整体数据曲率变化较 缓慢的曲面，可以快速滤除冗余数据，精简效果很好。 最小距离闺值原理示意图如图2 31 1 所示。 bc o ： e d f l a b i m i n d d e i m i n d m i n d 为最小距离 删除b 、e 点 图2 3 i 1 最小距离法的精简原理图 但是，如果层内数据点的曲率变动较大，简单删除定会影响曲面造型的精度。本 3 1 2 肇于分居维的数据处理技术研究博士论文 文提出了距离阈值和向量角度闽值结合的方法，其实质是在最小距离法的基础上，增 加相邻三点之削夹角的阈值。因为最小距离法可能会精简掉数据中的特征点，增加夹 角闽值后，对于特征点处的数据来说，其夹角较其它处相邻三点的央角大。因此，该 方法可有效避免特征点的错误精简。 距离闻值和向量角度阈值相结合法的原理如图2 3 1 2 所示。 0 a b c m i n d 为最小距离 m a x a n g l c 为最大向量央角 i a b i m i n d ea b c m a x a n g l e 删除b 点 i d ep m a x a n g i e保留e 点 图2 3 i 2 最小距离和向鼙夹角法的精简原理图 扫描线有序数据的精简过程说明如下：首先，对散乱数据创建其空间拓扑结构； 接着。考虑同一条扫描线上的连续三点( a ，b ，c ) ，计算两个向量v l i b a 和v 2 = c b 。 判断两向量的夹角曰是否小于角度阕值以，同时考查点b 到静一保留点a 的距离 ( d = i 爿一b 1 ) 是否大于给定的距离阙值d r ，如果如下： i f6 i 研且d b 且d 以且d d f 。保留b 。 若b 点删除，则以( a ，c ，d ) 考查c 点；若b 点保留，则以( b ，c ，d ) 考 查c 点，方法同上，遍历所有点至扫描线尾。 不论采用何种方法，对扫描线有序数据进行精简时，必须保留反映重构实体边界 信息的扫描线边界点。 本文用实例进行了验证，精简前后效果图如图2 3 1 3 所示。 。 一 长 南京理丁人学博卜学位论文摹于c m m 测量数据的曲向量构关键技术司f 究与实现 ( a ) 精简前的坐垫数据 警氅警受冀等l - 嘲嘲喇嘲黼嘲蝴嬲黜 l ，l鹃 ! ! 圈1 九j j 爿一一。一 缸，。、 王i - x # ：0 ： 一o oj ：。? ：j 。：一j ：- 。彳 。一7 ：o i 4 r 。i ：! ：二。7 ( b ) 精简后的坐垫数据 图2 3 1 3 坐垫数据精简前后效果图 2 3 2 散乱数据精简算法 对于散乱数据，c h e n 等 1 2 6 1 提出了一种减少三角网格数目从而删除部分数据点 的方法。本文研究采用八叉树栅格法进行数据精简。精简时，要计算每一数据点的法 矢，通过对每一栅格内点集的法向偏离情况来决定是否再进行栅格细化，栅格细分采 用八叉树分割法。当栅格划分结束后，提取每一栅格内的中值点，实现数据的精简。 八叉树栅格法进行数据精简的过程，是依据对栅格内点集的法向一致性的要求， 不断细化栅格，使栅格划分与曲面的复杂程度一致，越复杂的曲面栅格划分越细。其 3 3 2 基于分层维的数据址理技术研究 博k 论立 划分流程如图2 3 2 1 所示。初始栅格的大小由系统给定，如果精简率高，初始栅格 可设定的大些；当每_ 栅格的法向一致性都满足要求或栅格大小达到了设定的最小面 积，栅格划分结束。栅格最4 、面积视零件表面的复杂程度而定。 幽2 3 2 1 栅格精简算法流挫幽 散乱数据点的法向估计可以通过对点云进行三角化后，由其临近的三角形的法矢 来获得。对于图2 3 2 2 中每一三角面片，其法矢可由式( 2 1 4 ) 确定，对于图2 3 2 3 中 的点p ，其法矢的计算用到了它的i 临近六个三角形，设它们的法矢分别为i l l ，n 2 ， n 6 则p 点的法矢可以由式( 2 1 5 ) 来进行估计。 一o p v ，) 疗，- - _ 7 胪两砑2 1 4 ) o p x o q li 、 ( 2 i s ) 筠蔫鬻 轧 南京理t 太学博i 学位论文 綦fc m m 测蛊数据的l i i f 面董构关键控术研究与实现 2 4 特征提取技术 o p 图2 3 2 2 三角面片的单位法矢确定 n 幽2 3 2 3 散乱点的单位法欠估计 现在市场上的很多三维c a d 软件，都是基于特征的造型软件。由此可见，几何 特征是计算机几何造型的关键因素。同样在逆向工程中，几何特征对于曲面构造和 重建模型精度的提高具有极为重要的作用。 曲面重构是根据反求对象模型的点云，重建其几何和拓扑信息，并再现特征的过 程。特征是指对曲面建模有关键影响的符合一定规律的局部曲面或曲线。习惯上把二 次曲面以及曲面之间的过渡曲面称为特征曲面，而把局部曲面之间的交线和局部曲面 的边界称为特征线。特征提取就是从测量数据中提取线特征和面特征，其中线特征是 数据分块的依据，面特征是造型的基础i ”1 。这些特征对重构模型的品质有着举足轻 重的作用。 2 4 1 几何特征组成 特征包括形状几何特征、尺寸公差特征和技术特征。在逆向工程曲面重构中，我 们仅考虑与造型相关的形状几何特钳“1 ，而且主要是构成产品模型的低层几何体素及 其构造特征，如点、线、面等。 2 堆于分层维的数据处理技术研究博i 。论文 在c a d 模型表示中，产品的几何外形组成如表2 4 1 1 所示。 表2 4 1 i 产品几何磐【成 产品几何外形 主要几何次要几何 简单曲面规则的扫略曲面自由曲面 平面移动扫略 四边拓扑边混合 二次曲面 旋转扫略不规则拓扑 顶点混合 圆环 尽管工业产品具有不同的几何形状，但多数都是同一些规则的几何特征组成的， 表2 4 1 2 给出了几何特征的类型。 表2 4 1 2 几何特征类型 点 线 面 测量点( 基准点)一一轮廓线一平面( 基准面) 顶点表面棱线二次曲面 圆心点 中心线自由曲面 抛物面的焦点等 2 4 2 边界线自动提取 现在对于特征提取的研究，多是针对实体建模中简单几何形体的提取识别，或是 基于投影二维图形的特征识别。基于点云的特征定义与分类、特征表达、特征映射、 特征数据库等领域都存在很多有待研究的问题f 1 2 钔。 利用“点云”数据进行曲面的几何模型构造，一般要求先知道曲面的边界；对于 散乱的测量数据，构造边界曲线的方式很多，对于凸区域，散乱点的最小凸包是一种 较好的边界，但对于凹区域，最小凸包离区域数据的距离可能较远，因而，不能算是 最好的区域边界描述。为此，工程上常采用单独测量边界线或与计算机交互的方式来 定义曲面的边界线。显然，这些方法或者精度不高，或者比较费时，或者对操作者要 求较高。 2 4 2 1 单值曲面边界提取 假设被测曲面是单值曲面，即在某平面上具有一对一的单值投影为识别单值曲