（航空宇航制造工程专业论文）结构件反求建模中的数据处理技术.pdf

南京航空航天火学硕十学位论文 摘要 逆向工程是近年来c a d c a m 技术中发展很快的一个分支，而结构件的重构研究 莉：航窄工业、汽车 ：业等领域有着非常重要的应用。本文在基于草图重建结构件的思 路f ，针列结构件反求中的数据点简化、平整处理和草图平丽、草图兀索生成算法进 行了研究。主要工作如下： 研究了建立在数据点空问k 一邻域划分基础上的测量点按法向距离简化的方法，该 算法具有点的简化密度对曲面曲率大小的自适应能力。借鉴一些成熟的网格光顺 方法，本文实现了引入拉普拉斯算子的高斯滤波平整数据点的方法，具有时间复 杂度小，有效防止模型“收缩”等优点。 户结构件是出特征组成，特征在设计时一般是以一个或多个草图为基础，然后进行 拉伸、旋转、扫掠等操作而得到。按照在草图基础上反求结构件的思路，本文研 究了草图平面与草图元素的生成算法，包括平面、直线、圆弧的最小二乘拟合和 基于设计意图的样条线生成算法。实现了在给定拟合精度下自动优化顶点数目的 b 样条曲线拟合算法并提出借鉴草图元素生成算法和b 样条曲线拟合算法，构 造截面轮廓线和特征线来实现自由曲面反求的方法。 ，简要介绍了c a t i a 的二次开发平台c a a ，以及算法实现中用到的主要c a a 框 架和a p i 。在c a a 平台上对本文研究的相关算法进行了编程实现。 关键字：逆向工程，结构件，数据点简化，数据崽光顺，b 样条，最小二乘法 草图平面，草图元素tc a t i a - - 次开发 、 、 堕塑笪垦鲞蕉堡主堕墼塑竺堡丝查 a b s t r a c t r e v e r s ee n g i n e e r i n gi so n eb r a n c hd e v e l o p i n gr a p i d l yi nc a d c a mr e s e a r c hf i e l d a n di n s t a n c e so fr e c o n s t r u c t i o no fs t r u c t u r a lp a r tm o d e l sa r t s ei nn u m e r o u ss c i e n t i f i ca n d e n g i n e e r i n ga p p l i c a t i o n s s u c ha sa i r c r a f t i n d u s t r y , a u t o m o b i l ei n d u s 订y a n ds oo i l a c c o r d i n gt ot h ei d e ao f s t r u c t u r a lp a r tr e c o n s t r u c t i o nf r o ms k e t c h e s ，t h i st h e s i sa d d r e s s e s t h ed a t ap o i n t ss i m p l i f i c a t i o n ，d a t ap o i n t sf a i r i n g ，s k e t c h p l a n ef i t t i n ga n ds k e t c h p r o f i l e c r e a t i n gi n s t r u c t u r a lp a r tr e c o n s t r u c t i n g t h em a i nc o n t e n t so ft h i st h e s i sa r el i s t e da s f o l l o w s ： 户b a s e do nt h ek - n e t g h b o rs t r u c t u r eo fd a t ap o i n t s ，t h i st h e s i sp r e s e n t sa na l g o r i t h mo f d a t ap o i n ts i m p l i f i c a t i o na c c o r d i n gt on o r m a le r r o r s ，w h i c hi sa d a p t i v et ot h ec u r v a t u r e v a r i a t i o no fs u r f a c e s b yr e f e r r i n gt os o m e c l a s s i c a la p p r o a c h e so f m e s h f a i r i n g ，an e w a l g o r i t h mo fd a t ap o i n td e n o i s i n gi sd e s i g n e do nt h eb a s i so fg a u s s i a nf i l t e rw h i c h i n t r o d u c e sac o m b i n a t i o no fl a p l a c i a na n dt h es e c o n dl a p l a c i a n t h ea l g o r i t h mi s c h a r a c t e r i s t i co fs h o r tt i m e c o n s u m p t i o na n d a n t i s h r i n k a g eo f m o d e l s s t r u c t u r a lp a r t sa r em a d eu pw i t hf e a t u r e s ，w h i c ha r eu s u a l l yo b t a i n e db ye x t r u d i n g ， r o t a t i n ga n ds w e e p i n go f o n eo rs e v e r a ls k e t c h e s a c c o r d i n gt ot h ei d e ao fs t r u c t u r a l p a r t r e c o n s t r u c t i o nf r o m s k e t c h e s ，t h ea l g o r i t h m s o f s k e t c h - p l a n ef i t t i n g a n d s k e t c h p r o f i l ec r e a t i n ga r es t u d i e di n t h i st h e s i s ，i n c l u d i n gt h el e a s t - s q u a r ef i t t i n g a l g o r i t h m so fp l a n e ，l i n e ，c i r c l ea n ds p l i n eb a s e do nd e s i g ni n t e n t t h i st h e s i s a l s o r e a l i z e sa nb s p l i n e f i t t i n ga l g o r i t h mw i t ho p t i m i z e dc o n t r o l v e r t i c e su n d e rg i v e n t o l e r a n c e s ，a n dp u t sf o r w a r d a na p p r o a c h o f r e c o n s t r u c t i n gf r e e s t y l es u r f a c e sf r o m t h e c u r v e so np l a n a rs e c t i o n sa n dc h a r a c t e r i s t i cc u r v e su s i n gt h es k e t c h e l e m e n tc r e a t i n g a n d b s p l i n ef i t t i n ga l g o r i t h m sf o r r e f e r e n c e t h i st h e s i sg i v e sab r i e fi n t r o d u c t i o nt oc a t i a d e v e l o p i n gp l a t f o r m ( c a n ) ，t h em a i n f r a m e w o r ka n da p ii nt h ei m p l e m e n t a t i o no ft h ea b o v em e n t i o n e da l g o r i t h m s a l lt h e p r o p o s e da l g o r i t h m sh a v e b e e ni m p l e m e n t e dw i t hc a a a p ia n dc + + a p i k e y w o r d s ：r e v e r s ee n g i n e e r i n g ，s t r u c t u r a lp a r t s ，d a t ap o i n ts i m p l i f i c a t i o n ，d a t ap o i n t f a i r i n g ，b s p l i n e ，l e a s t s q u a r e ，s k e t c hp l a n e ，s k e t c he l e m e n t ，s e c o n dd e v e l o p i n gp l a t f o r m f o r c a t 认 南京航空航大人学硕l 学位论文 第一章绪论 i i 逆向工程技术及其应用 逆盯：程( r e v e r s ee n g i n e e r i n g ) 是数字化与快速响应制造大趋势下的一项承要 技术，足c a d 领域中一个相对独立的范畴。目前逆向工程研究主要针对实物模型几何 嘭状的反求，它的般过程是根据已有实物或模型的测量数据，重新构造其计算机模 型，然后利用c a d c a m c a e 等计算机辅助技术进行分析、再设计、数控编程等操 图1 1 逆向工程原理不意图 作，然后进行加工【1 11 ，图l 一1 是逆向工程的工作原理图。通过实物模型产生的数字 化模型，可以充分利用数字化的优势，提高设计、制造、分析的质量和效率，并适应 t 煽化、集成化、并行化、网络化的产品设计制造过程中的信息存储与交换。实施逆 l 。挫”j 以充分发挥先进坐标测量设备的优越性，使其既可以作为产品设计所需要的 | 1 i j 竹输入：妓霄，又可作为c a d c a m 系统处理后模型的误差评估装罱。逆向工程技 术t t j 以与快速原型制造( r p m ) 技术相结合，提高工业产品的设计、制造自动化程度， 缩短产讯的研制周期，降低生产成本。 逆阳1 二程在各个领域有着广泛的应用，逆向工程所研究的实物模型可以是机械 “趴人体、动植物、艺术品、地形地貌等等。在模具设计中，常常需要根据样件或 m 、”- 5 川。进行模具设计，如果利用了逆向工程技术，将使设计自动化程度大大提高。 们忖，需硬通过c a e 软件对样件进行有限元分析，也可以用逆向工程建立样件的数 ，化校j 峨在产品作局部改型的情况下，如果没有产品的数字化模型，也可以借助逆 向i 程建由数字化模型，提高新产品的市场响应速度。 逆阳r 程的另一个重要应用是对外形美学要求很高的零部件的设计。例如在汽 1f 、h 外形设汁师经常需要先制作全尺寸的木质或黏土模型，因为要存一：维的仆 结构1 ， ：反求建模中的数据处理技术 钟机屏幕上完成三维复杂外形的设汁是很困难的。当实物模型制作好以后，就需要把 它转化为c a d c a m 能够处理的计算机模型，再借助计算机完成后续的设计步骤。 冗外，在g i s ( 地理信息化系统) 领域中，我们需要对各种地貌特征的航拍数据 进行处删，建立地容地貌的计算机模型；还有，在个性化产品设计和产品定制中，例 埘j ，每个人体都不同，借助先进的测量设备快速建立人体的数字化模型，就可以完成 1 1 如头躲、服装等各种随身物品设备的设计，体现产品的个性化和对每个客户的适应 ，。 1 2 结构件模型重构以及测量规划 几何模型是由几何信息和拓扑结构两部分组成，通常可以分为线框( w i r e f r a m e ) 、 挺嘶( s u r f a c e ) 、实体( s o l i d ) 和参数化特征模型【3 5 】四种模型形式。其中表面模型是 史体校b 绷q 重要组成部分，一般需要先构造出表面模型，再演算出实体模型。参数化 的特自l ：模型使用约束来定义和修改几何模型，将尺寸用变量表示，作为设计的几何参 数，以建立通用的几何模型，参数化特征模型可以方便地进行动态修改。 结构件的反求有两种不同的思路，分别对应于不同的测量规划。第一种方法是 采用f | h | l l j 面反求建模的通用方法，借助激光扫描测量设备，测量得到模型的海量数 捌“点i i ”，然后采用通用的曲面重建方法重建。例如，先生成三角化网格模型，进 行心边界域的划分，然后构造基于四边界区域划分的分片b 样条曲面来完成实体模 刑的重建【3 】【“。又如，先把“点云”用包围盒树来加以划分，每个包围盒中的点拟合 t f 成一个最小二乘平面，根据这个平面来重新定位包围盒方向，每个包围盒递归划分 为更小的包围盒，调整它的方向：根据每个包围盒和其中的数据点生成最小二乘二次 | f f i f 丽；把这些二次曲面升阶到双三次曲面，然后按照一定法则“混合”这些胁而片产 乍 系列逼近测量点的b 样条曲面f 5 l o 第二种方法是针对结构件特征较明显的特点， 巴逆阻i ：程和正向设计结合起来，按特征对数据点进行分块，分别萋建这些特征。按 照 j 殳计思路，提取出结构件上一系列草图平面，然后构造出草图元素。在草图的 i l ；础 ：ir j 以通过拉伸、旋转、倒角、扫掠、放样等后续处理，生成曲面、实体，再结 合裁剪、过渡等操作，得到最终重构实体。后者可以是激光扫描仪测得的海量数据点， 也】以足通过接触式的三坐标测量仪，有选择地测量得到的反映结构什特征的数据 r i 。仆本沦文小，我们针对结构件特点，按照第二种方法对结构件逆向建模中的数据 处瑚技术进行研究。 通常把三维空间中的密集测量点称为“点云”( p o i n tc l o u d ) ，离密度的“点云” h 能达剁卜百力数据点，甚至更多。根据“点云”中点的分布特性将“点云”分为： 1 ) 敞。e l “点云” 测f 硅，_ 没有明显的几何分和特性，c m m ( 坐标测量机) 随机扫描方式f 和激光扫 w n 数7 手照相法多次测量厉拼合得到的数据是散乱“点云”。 2 南京航空航天人学硕十学位论文 2 ) 描线( s c a n ) “点云” 数拥点位 ：系列扫描线内，每条扫描线上的点位于一个扫描平面内。c m m 直 线 l 捕干线结构光扫批的数据呈现扫描线特性。 3 ) 栅格化( g r i d ) “点云” “点云”中的所有点与参数域中的一个均匀网格的顶点对应。栅格化“点云”一 般足将j i 它形式“点云”进行网格化插值后得到的。 逆mr ：程的不断深入发展，对各种坐标测量设备在精度和速度上提出了更高的要 求。近 i ：来，各种坐标测量设备发展得很快，测量速度和精度都得到了很大的提高， 例如德凼g o m 公司的a t o s 的光学测量机，英国3 ds c a 咂s 公司的r e v e r s a 激光 删头等等。对于结构件，先根据结构件的构造特征对其分类( 如梁、框、肋、接头等) ， 然后，按子类结构件的几何特征分别进行测量数据规划。对于数据点的测量，采用光 学洲0 量方法可以快速得到海量的数据点；也可以采用c m m 来测得低密度“点云”或 水足够反映结构件细节特征的特征点、线、面上的数据点，只要保证数据点能提供重 掬i i , l 所需要的足够几何信息。 1 3 论文选题依据及研究内容 b 机数字化设计制造技术是2 0 世纪8 0 年代后期以来，随着c a d ，c a m 技术、 计算机信息技术、网络技术的发展，以美国为首的西方发达国家开始研究并首先采用 的项新技术。这项技术以全面采用数字化产品定义、数字化预装配、产品数据管理、 j _ j ：j 程和虚拟制造技术为主要标志，从根本上改变了飞机传统的设计与制造方式， 人i 幅度提高了设讨帝0 造技术水平。例如，美国波音公司b 7 7 7 型飞机的研制，由于全 i f | i 采用该项新技术，使设计更改和返工率减少了5 0 以上，装配时出现的问题减少 j 5 0 8 0 1 3 6 j ，成为数字化设计制造技术在飞机研制中应用的标志和毋程碑。 我旧的航空工业对逆向工程技术有迫切的需求。我国的很多航空企业引进了一些 先进f | j 数宁化设汁制造手段，也初步具有了数字化设计制造的能力，但匙以i m 的年进 l | 的些产品并没有建立起“全机数字化模型”，这就成为了实现飞机数字化制造的 帆颈。例如，我国从俄罗斯引进了某重点型号飞机，该飞机的制造体系属“模线样板 ，】：准样件工作法”，这对于零件制造和装配协调会产生很大隐患，因为工装是要经常 按”什进行修币的，二 装一经修正，所带来的修改是一连串的，并会给零件制造增加 定的i 作量。采用先进的数字化设计制造技术，可以缩短引进飞机国产化及改型设 汁制造周期，提高制造质量，因此，建立这些飞机的数字化模型势在必行。飞机结构 | ：j 数模必须采用逆向：【程技术来建立，在飞机的上百万个零部件中，很多是结构 什。与其它的自由型面零件相比，结构件具有特征比较明显，曲面形状不复杂的特点， 叱仃确：多关键技术亟待解决。例如，如何保持原有工装继续使用的前提下，建立结构 什的数7 化模型的问题。 3 结构件反求建模中的数据处理技术 外的p r o e 、u g 、c a t i a 等已相继推出各自的反求工程模块，现有的商品化反 求i j 程的软件，如通用的逆向工程软件c o p y c a d 、1 - d e a s f r e e f o r mm o d e l e r 、g e o m a g i c 钟卜要钊剥曲面模型重建，但是这些反求工程软件都不专门应用于飞机结构件模型的 - n 建。h | ：j ，c a t i a 在航空业中有着广泛的应用，我们希望开发针对飞机结构件反 求的j j j t l 。模块集成在c a t i a 中，因此，本课题选择在c a t i a 上作结构件反求模块的 ：次j 1 发。 本文研究得到高等学校优秀青年教师教学科研奖励计划、航空科学基金 ( o l h 5 2 0 5 1 ) 、江苏省自然科学基金( b k 2 0 0 1 4 0 8 ) 支持。针对飞机结构件反求中数据点 预处理( 数据简化、滤波平整) ，草图平面的拟合和草图元素的生成等问题进行了深 入的研究，并在c a t i a 二次开发平台c a a 上，结合v i s u a lc + + 6 0 集成开发环境， 刈算法进行了实现。 本文研究的内容如下： 第章绪论，综述逆向工程技术及其应用领域，介绍结构件的重构以及测量肌划 题，斤据此引出本文的选题依据及研究内容。 笫二章研究了数据点简化、平整滤波预处理方法。提出并实现了按法向距离简化 的数据简化方法，采用一种对“点云”形状保持比较好的高斯低通滤波算子，对高频 噪菏数据进行平滑处理。 第章研究了基于测量点的草图平面与草图轮廓生成算法。介绍了草图- 甲而的生 成算法，以及数掘点向草图平面投影后，如何进行直线、圆弧、多项式曲线的拟合， 硼f 究了躯于设计意图的样条曲线的生成，空间b 样条曲线拟合等一系列相关算法。 筇叫带介绍了c a t i a 二次丌发平台c a a 和c o m ( 组件对象模型) ，包括 ( a a r a d e 丌发环境介绍。c a a 应用的框架和生成c a a 应用的基本流程。介绍本 文i 一 t 论的算法用到的主要a p i 以及算法在c a t i a 中的具体软件实现。 筇f i 章是对本文工作的总结以及对今后工作的展望。 南京航空航天火学硕士! 学位论文 2 1 引言 第二章海量散乱点的简化与平滑处理技术 逆盯r 程中，首先要得到实物的测量数据点，以前采用接触式的坐标测最机，为 了提高蕊构模型精度，通常需要人为规划，使得在曲面上曲率变化大的地方分布更多 n j 测最点，曲率变化小的地方测量点分布少一些，而且接触式测量速度受到很大约束。 随着各利，非接触测量方法的不断发展，测量精度大大提高，以前成为非接触测量瓶颈 的测豉精度问题现在不复存在，目前激光扫描测量机和其它光学测量设备可以在很短 的时洲内得到上百万个点。通常，用非接触方法得到的测量点是与曲面上的曲率大小 无关的“均匀”采样点。 测茕点数据可以分为有序数掘点和无序数据点。对于特征比较明显的结构件，可 能j 需蛭测得特征点、线上的有序点就行，但对于复杂的包含自由曲面的零件，更一 般的方法是采用激光扫描或者三维照相的方法得到海量数据“点云”，以保留全面的 儿何倩息。“点云”数据量很大，而且测量过程不可避免地会引入噪声点，考虑到重 构速度干重构模型的精度，海量数据一般不能直接用来进行三角化、曲面拟合。而且 埘j 二形状比较复杂的物体，需要从多个方向上采集物体表面上的点，这些点在不同的 一p 标系f ，因此，需要对数据进行多视数据拼合、数据简化、数据去噪、数据分块等 预处理【( ”。可以说数据预处理的质量直接关系到生成的曲面品质。 术一拳提出的数据点简化与平滑算法，是建立在散乱点的空间邻接关系建立的基础 _ l ，称为点的邻域关系。在此基础上，实现了适应曲率大小而自动选择简化后该区域 点密度大小的按法向距离简化算法；通过选择适当的拉普拉斯算子和权因子，实现了 i j i 入“体积补偿”的商斯滤波平滑算法，在平滑数据的同时，很好保持了“点云”数 就- j 的原始模型的形状。 2 2 海量散乱数据点邻域关系的建立 考察敞乱“点云”数据中某个测量点附近区域在模型中所呈现的一些几何形状特 。m - - 以只考察与这个点邻近的若干点，然后利用这个点和邻近点来近似考察点附近 k 域订：整个模型中所表现出来的一些几何特性。这样就可以把计算限制在这个点周围 的若一n j l 当中，简化计算。例如考察点的法矢方向，曲率大小等等。 定义2 1 设“点云”中的测量点集合为x x i , x 2 ，x 3 ，x 。) ，则在集合x 中，与 x 距离最近的k 个点，称为x i 的k 一邻域点，表示为n e i g h b o u r ( x i ) 。 定义22 作一个包含“点云”中测量点集合x x i , x 2 ，x 3 ，x 。) 的体积最小的长 结构件反求建模中的数据处理技术 方体，f - 1 这个长方体的两两垂直的三条边分别与笛卡儿坐标系的三个坐标轴平行，则 称这个k 方体为测量点集合x 的沿坐标轴的最小矩形包围盒，简称为最小矩形包围 盒( b o u n d i n g b o x ) 。 为了求出每个测量点的k 矗b 域点，就需要求出“点云”中与当前考察点x i 最近的 k 个点，如果在所有的数据点中进行搜索，由于“点云”中数据量太大，效率非常低。 所以，本文提出了对“点云”作空间划分的思路。 首，t ，把测量数据点集合x 读进来，把坐标值存储在一个顺序表中，同时求出点 云数据的沿坐标轴的最小矩形包围盒。设矩形包围盒的最小坐标为： l o wb o xx ，l o w 。矩形包围盒的最大坐标为：_ b o xy , l o wb o xz u p p e r b o x _ x ，u p p e r b o x y , u p p e r b o x _ z ，把这个包围盒在x 、y 、z 方向按边长相等的 原则进行等间距分割，设立方体栅格的边长为：g r i d _ s i z e ，则包围盒被分为m x n x l 个小立方体栅格，其中： m = ( i n t ) ( u p p e r _ b o x _ _ x - l o wb o x x ) g r i d _ s i z e ： n = ( i n t ) ( u p p e rb o x _ y l o w _ b o x y ) g r i d _ s i z e ：( 2 - 1 ) l = ( i n o ( u p p e r b o x _ z l o w _ b o x _ z ) g r i d - s i z e ； 栅格的大小选择要适当，如果栅格太大，对减小邻域搜索范围效果不明显，本文 墩栅格的数目与点的数目保持大致相同，尽量保证平均每个栅格中有一到两个点。 栅格划分完成后，计算每个测量点所在的橱格。设当前点的坐标为： c u r _ x ，c u r _ y , c u rz ，则当前点所在栅格的索引为： g r i d j = ( i n o ( c u r _ _ x l o w _ b o x _ x ) g r i d _ s i z e ： g r i dj = ( i n o ( c u r _ _ y - l o w _ b o x _ y ) g r i d _ s i z e ：( 2 - 2 ) g r i d 。j ( = ( i n t ) ( c u r z l o w _ b o x _ z ) g r i ds i z e ： g r i d i ，g r i dj ，g r i d _ k 是当前测量点在x ，y ，z 轴方向上对应的橱格索引号。为 每个栅格设计了一个栅格链表，把每个测量点加入对应的一个播格链表中去，栅格链 表的头结构和结点数据结构如下所示： t y p e d e f s t r u c ti n d e x p o i n t t a g 存放栅格链袭的结点结构 f l o a t x ；点的x 坐标 f l o a t y ；点的y 坐标 f l o a tz ；点的z 坐标 i n ti n d e x ；点数据在顺序表中的索引位置 ) l n d e x p o i n t ； t y p e d e f s t r u c tg r i d t a g 存放栅格链表的头结构 l i n k e d l i s t h e a d e r ； ) g r i d h e a d ； 壹壅塾窒堕鲞盔堂婴堂垡笙苎一 建立好栅格链表以后，在点x 所在栅格的周围2 7 个删格中( 包括x i 所在的栅格) 搜索距离最近的k 个点，按与x i 距离由小到大建立k - 邻域链表，k 值取太大使 n e i g h b o u r ( x 。) 不够局部化，把对影响较小的点也加入到对x i 计算考虑中，不能很好 地反映局部几何信息，影响算法效率；k 值取太小又不能足够反映测量点局部范围内 的几何特性，本文中，取k 值为1 0 ，建立每个测量点的1 0 一邻域链表。邻域链表的头 结构和结点数据结构如下： t y p e d e f s t r u c tn e i g h b o u r t a g 存放邻域链表的头结构 l i n k e d l i s t h e a d e r ；指向链表的头指针 f l o a tn o m a l d i s t a n c e 当前测点与最小二乘平面的法向距离 ) n e i g h b o u r h e a d ； t y p e d e f s t r u e tn e i g h b o u r b o d y t a g 邻域链表的结点结构 f l o a td i s t ；与当前测点的距离 i n ti n d e x ；点数据在顺序表中的索引 n e i g h b o u r b o d y ； z y 削2 + 1 “点云”数据的空i 可栅格划分 在当前考察点所在栅格周围2 7 个相邻栅格中搜索所有点，然后把这些点加入一 个临时链表，其伪码算法如算法2 1 所示。然后，把这个邻域链表的前k o r - l o ) 个点 加入x 的邻域链表。 算法2 1 f o r ( i = g r i d _ i 1 ；i 一鲥d - i + 1 ；i + + ) i 是搜索中当前栅格x 方向索引 i f ( ( i = g r i d _ r n ) ) c o n t i n u e ；，到达边界，退出本次循环 f o r o = g r i d j 一1 ； = g r i d a + 1 0 + + ) j 是当前栅格y 方向索引 结构件反求建模中的数据处理技术 i 坟( i = g r i d j ) ) c o n t i n u e ；到达边界，退出本次循环 f o r ( k = g r i d _ k 一1 ；k = g r i d _ k + 1 ；k + + ) k 是当前栅格z 方向索引 i f ( ( k = g r i d _ 1 ) ) c o n t i n u e ：到达边冕，退出本次循环 t m p _ g r i d = g r i d _ n + g r i d _ l + i 十鲥dl * j + k ；棚 格链表偏移量 遍历栅格，把所有点按与x i 的距离由d , n 大加入l 临时链表； ) 建立好散乱数据“点云”的k 邻域结构，就可以对数据点处的原始几何性质进行 估计，这是本章设计和实现散乱数据点的简化算法和滤波光顺算法的基础。 2 3 数据点简化的方法及实现 海量散乱数据点的简化算法，通常有以下几种。( 1 ) 邻城内均匀采样法，就是在 每个点的k 邻域内去除n 个( n _ k ) 与当前点最近的点，即按照本章前面所介绍的 方法建立邻域链表的前i 3 个点。( 2 ) 按测量点之间距离简化。简单遍历每个测量点的 邻域链表，去除每个点的邻域中所有距离小于一个给定阙值( t h r e s h o l d ) 的点。( 3 ) 按给定点个数简化，每一次遍历需要遍历所有点的邻域链表，且一次只能去除“点云” 中距离最近的两个点中的一个，直到达到用户指定的数目，由于遍历次数较多，算法 时间复杂度高【7 1 。( 4 ) 随机采样法，针对海量数据点的测量方法是一次测量得到一个区 域的点数据，和数据点存储是随机存储的特点，对顺序读入数据文件的点进行随机的 去除，这种方法不用建立散乱点的邻域结构，所以实现是很快的，但算法稳定性显然 与测量方法和测量点的存储方法有关，稳定性不够好。前面的几种以测量点之间距离 为依据的算法和随机简化算法都是以一种比较均匀的方式减小“点云”密度。在实际 应用中，我们希望简化后在曲面上曲率大的“尖锐”的地方保留更多的点。防止丢失 一些细小特征信息，而在曲率小的“平坦”的地方去豫更多的点。因此，在本文中， 采用了一种与曲率大小相关的简化算法按法向距离简化。 按法向距离简化的思想是：以当前考察点x i 去除后引起的法向误差来判定当前考 幽2 - 2 点的法向误差估计示意图 察点是否应该去除。由于待构曲面是未知的， 所以去掉x i 后的在此处的曲面形状也是未知 的，本文采用的是x i 的邻域n e i g h b o u r ( x i ) 内的 点拟合最小二乘平面p i 来近似待构曲面在去掉 点x i 后在这个地方的形状。最d , - 乘拟合问题 研究的文献很多，本文采用的是把最小二乘平 面拟合问题转换为求矩阵的特征值和特征向量 8 壹星塾窒堕鲞盔堂堡主堂焦笙壅 一 问题的厅法。 波址小二乘平而为p ，可以用、f 面上一点c e n t r o i d _ i 和平面的节位法矢n i 来表示， 填i i ，c e l l t r o i di 为n e i g h b o u r ( x i ) 的形心，这样去除点x 引起的法向误差可以用点x i 与 最小乘甲面p 的距离d i 来表示，如图2 2 所示，可以认为d l 越大，曲面在x i 处的 阳牢越火。给定一个法向误差的闽值t h r e h o l d d i s t a n e e ，如果d i 小于t h r e h o l d d i s t a n c e ， 则删除x ，反之，则保留这个点。 c e n t r o i d i = o ( = 1 0 ) ( 2 3 ) j j e 脚啪幻w ( 。f ) 设沁录初始数据点坐标的顺序表是i n f i l e p o i n t a r r a y n ，与每个点对应的一个记录 邻域链表头结构的顺序表n e i g h b o u r h e a d e r n 】，记录点是否被删除的标志 l n f i l e p o i n t f l a g n ，法向距离的阐值t h r e h o l d d i s t a n e e ，则按法向距离简化算法的步骤 表示如下： 算法2 2 ( 1 ) 初始化参数。对l n f i l e p o i n t f l a g n 】全部髯初始值0 ，对法向距离闽值 t h r e h o l d d i s t a n e e 赋值。 ( 2 ) 从顺序表n e i g h b o u r h e a d e r i 取出邻域链表头指针h e a d e r ，由链表头指针 h e a d e r 遍历它的邻域链表，用n e i g h b o u “x i ) 中的点拟合一个最d , - 乘平面p i 。 ( 3 ) 计算点x i 与p i 的法向距离d j ，如果d i t b _ r e h o l d d i s t a n e e ，则鼍删除标志，令 l n f i l e p o i n t f l a g i 】= l 。 ( 4 ) 如果i 0 ，u 一 ，贝0 11 k m = + 二 0 ( 2 - 1 1 ) ； 、 厂、 b 。 f 一10 ( a ) | 玺l2 _ 4 和u 选择不当导致厂” ) 定义域内不再具有低通特性 南京航空航天人学硕士学位论文 _ ，( o ) = 1 ， 牙u 取值总的原则是要保证在k t h k 2 之间l s ( k 】 1 ，同时希望让旯( 0 , 1 ) 取 1 ：| ：f 尽特人，以减少叠代次数，但 和p 的取值并不是独立的，如果 取得太大，则会 使( k ) l l h 线在 k 1 ，因此f “( k ) 的函数曲线不 f q 呈现低通特性，如图2 - 4 所示。可以按照如下的步骤确定各个参数： 1 ) 先定k 1 ，可以根据光顺效果加以调整，本文的研究结果表明k l h 在o 1 左右可 以得到比较好的效果。 2 ) 根据公式( 2 1 1 ) 确定 和u 。为了保证较少的迭代次数得到较好低通特性，就 要保证在k t h k 2 区间上s ( k ) f j 的前提下， 取值尽可能大，定下 后再确 定u 。 2 数据点集的形状保持 诒：应用某种方法对“点云”数据进行平整时，如何对数据点的形状进行控制，防 l l ：闲过度光顺而使数据点不能正确反映初始模型的几何形状，也是一个重要的值得关 汁的问题。例如，用加权的一阶拉普拉斯算子( 2 。7 ) 来决定顶点的调整方向和大小x ， 饵个数据点都有向每个点的邻域所包围空间内部移动的趋势。在顶点调整后，就可能 使“点夏”所反映的初始几何模型体积收缩。为了防止因收缩引起的形状失真，不同 的措施被采用，通常有如下两种方法：体积不变法【1 0 】和顶点距离控制法。 体移 不变法的思想是保持迭代前后几何体体积不变。对于“点云”数据的体积可 以先求数