（计算数学专业论文）基于散乱数据的曲面重构技术研究.pdf

阿北工业大学硕十学位论文摘要 摘要 随着现代设计和制造技术以及计算机技术的发展，逆向工程在机械工程领域 获得了越来越广泛的应用。三维散乱数据点的曲面重构技术是逆向工程中非常重 要的研究课题之一。 本文从三维散乱数据曲面重构的实际需要出发，对散乱数据的预处理和曲面 重建技术进行了研究和探讨。一方面针对海量散乱点，提出了一种非均匀的简化 算法，另一方面是对基于d e l a u n a y 三角化的曲面重建算法一c o c o n e 算法提出了 改进。 三维散乱数据的非均匀简化研究，首先将数据集的最小包围盒分割成许多大 小相同的立方体，然后在每个含数据点的立方体内计算其所包含曲面的局部法向 变化量，并根据给定的局部法向变化量阈值将数据集进行非均匀简化。 基于散乱数据的曲面重建方面，在研究了诸多v o r o n o i 图和d e l a u n a y 算法之 后，选择c o c o n e 算法作为我们的理论基础，针对c o c o n e 算法在边界处理方面 的不足，对其提出了自己的一种局部处理的改进方法：用距离条件进行三角形过 滤。该方法能快速得到一张网格，它能较好反映待建曲面的拓扑结构与几何信息。 实验证明，改进后的方法，在检测边界时非常有效，能够很好地过滤到边界上的 那些非约束的d e l a u n a y 三角片。 关键字逆向工程，散乱数据，曲面重建，非均匀简化，d e l a u n a y 三角剖分，c o c o n e 算法 距离条件过滤 塑! ! 三些茎兰堡圭兰些兰壅 竺! ! ! 竺 a b s t r a c t w i t ht h ed e v e l o p m e n to ft h em o d e md e s i g na n dm a n u f a c t u r i n gt e c h n o l o g ya sw e l la st h e c o m p u t e rt e c h n o l o g y , t h er e v e r s ee n g i n e e r i n gh a sb e e nw i d e l yu s e di nt h ef i e l do fm e c h a n i c a l e n g i n e e r i n g s u r f a c er e c o n s t r u c t i o no fu n o r g a n i z e d3 dp o i n t si so n eo ft h em o s ti m p o r t a n t r e s e a r c hp r o b l e m so nr e v e r s ee n g i n e e r i n g t h ep r e s e n tp a p e rt e n d st oe s t a b l i s ha ne f f e c t i v ed e m a n do fs u r f a c er e c o n s t r u c t i o n o f u n o r g a n i z e d3 dp o i n t s ，a n dm a k ea ni n - d e p t he x p l o r a t i o nf o rt h ep r e p r o c e s s i n gt e c h n o l o g yo f u n o r g a n i z e d d i s c r e t e p o i n t s s e ta n dt h e a l g o r i t h m o ft h r e e d i m e n s i o n sm o d e ls u r f a c e r e c o n s t r u c t i o n t h es t u d yi sm a i n l yf o u s e do nt w oa s p e c t s ：o nt h eo n eh a n d ，an o n u n i f o r m s i m p l i f i c a t i o na l g o r i t h mo fm a s s i v eu n o r g a n i z e d3 dp o i n t si sp r e s e n t e d ，a n do nt h ea n o t h e r ，t h i s p a p e rs u g g e s t sa ni m p r o v e dm e t h o do nt h eb a s i so fc o c o n ea l g o r i t h m an o n u n i f o r ms i m p l i f i c a t i o na l g o r i t h mo fu n o r g a n i z e d3 dp o i n t sh a sb e e np r e s e n t e di n d e t a i l s a tf i r s t ，t h em i n m a xb o xo f t h ed a t as e ti sd i v i d e di n t oc u b e sw i t ht h es a m es i z e t h e n f o r e a c hc u b ew i t hs a m p l e dp o i n t si ni t ，t h el o c a ln o r m a lc h a n g ei sc a l c u l a t e da n dt h u st h ec l o u d p o i n t sa r en o n u n i f o r m l ys i m p l i f i e da c c o r d i n gt ot h eu s e r - s p e c i f i e dn o r m a lc h a n g et h r e s h o l d b a s e do nm a i n s t r e a ma l g o r i t h m sb a s e dv o r o n o ld i a g r a ma n dd e l a u n a yt r i a n g u l a t i o n ，t h e c o c o n ea l g o r i t h ms e r v e sa st h et h e o r e t i c a lf r a m e w o r kf o rt h i st h s i s a sf o rt h ew e a k n e s so f h a n d l ei nb o u n d a r y , w eu s ed i s t a n c et op e r c o l a t et r i a n g l e s i nt h i sw a y , w ec a ng e tam e s hf r o mt h e d a t as e t ，a n di nt h ew h i c ht h el o c a lg e o m e t r i ca n dt o p o l o g i c a lp r o p e r t yc a nb ec l e a r l yd e s c r i b e d w i t hi t sa d j a c e n tp o i n t sf o rag i v e np o i n t t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ei m p r o v e dc o c o n e a l g o r i t h mi sa ne f f e c t i v em e t h o df o rh a n d l i n gi nb o u n d a r y k e yw o r d s ：r e v e r s ee n g i n e e r i n g ，u n o r g a n i z e dd i s c r e t ep o i n t s ，s u r f a c er e c o n s t r u c t i o n ，n o n u n i f o r m s i m p l i f i c a t i o n ，d e l a u n a yt r i a n g u l a t i o n ，c o c o n ea l g o r i t h m 西北工业大学硕士学位论文 绪论 第一章绪论 1 1 逆向工程简介及发展现状 在产品的开发与制造过程中，几何造型技术已使用得相当广泛，然而在很 多情况下零件的初始信息状态并不是c a d 模型，而是由泥土、陶瓷等制成的样 件，或者是一个已经做好的缺少c a d 模型的实物零件。如果要在这种条件下对 该零件进行批量复制或改型设计，就必须通过一定的途径将这些实物样件转化 为c a d 模型，以便利用c a d c a m 、r p m 、p d m 及c i m s 等先进技术对其进 行处理或管理。目前，这种从实物样件获取产品数学模型的技术，已发展成为 c a d c a m 中的一个相对独立的范畴，称之为逆向工程( 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 d 模型， 经检验满意后制造出产品来。而产品逆向工程是从已存在的零件或产品实物原 型入手，首先通过测量扫描等先进的数字化处理手段获得产品实物信息( 即用一 个庞大的三维数据点集来表示整个零件) ，然后利用c a d 模型重构技术快速准 确地建立产品数学几何模型，再在工程分析的基础上，数控加工出产品，或加 工出产品面具后制成产品。 为了满足日益增长的计算机图形真实感的需要，增强模型的逼真度，实物 真实感模型反求技术也越来越多地被应用于数字地面模型d t m ( d i g i t a l t e r r a i nm o d e l ) 建立、数字化图形仿真、虚拟环境构建、医学成像数据的可视 化、地质勘探数据处理等方面，推动着虚拟现实技术和可视化技术的发展。 从实物原型到三维实物重构模型的过程，称为实物原型重构。后续过程不 论是进行单纯的产品仿制，还是通过快速原型( r p ) 制成样品对产品进行工程分 析，或是对重构模型进行创新设计，或是虚拟现实系统中的真实感图形显示， 绪论 都要首先进行实物原型重构。因此，可以说实物原型重构是逆向工程技术的核 心和基础。 实物原型重构的过程般描述为如下几个阶段：数据采集，数据预处理， 数据分割及曲面重建。其中最重要且比较困难的问题是数据分割和曲面重建 2 1 。 其中，自由曲面重构具有以下几个特点： 待处理的数据点散乱且曲面对象边界和形状有时及其复杂，因而一般不便 直接运用常规的曲面构造方法，需要消除各种干扰因素，精简样点，采用有效 的数据转换格式，减少数据丢失和失真。 三维测量数据的分割和拟合技术是逆向工程中的重要内容。对于含有自由 曲面的复杂型面，曲面对象往往不是简单地由一张曲面构成，而是由多张曲面 经过延伸、过渡、裁剪等混合而成，因而要分块构造用一张曲面来拟合所有的 数据点是不可行的，一般首先按照原型所具有的特征，将测量数据点分割成不 同的区域，各个区域分别拟合出不同的曲面，然后应用曲面求交或曲面间过渡 的方法将不同的曲面连接起来构成一个形体。这牵涉到有关曲面分割与拟合算 法的有效性、效率以及误差问题。包括样点的特征、数量、密度及来源对曲面 拟合的影响，拟合参数曲面的延伸问题，初等曲面与自由曲面的混合问题和求 交算法，c a d 模型重构的约束条件等问题。 在反求工程中还存在一个“多视数据”问题p 】。使用常用的接触式和非接 触式测量方法时，由于物体的复杂性和测量方法的限制，一次装卡可能不能获 得所需的全部数据，需要调整物体与测量系统的相对位置，从而导致了多次测 量所得数据的坐标系不统一。另外，为了保证数字化的完整性，各视之间还应 有一定的重叠。如何对其进行拼台，是一个重要的问题。 1 2 三维散乱数据曲面重构现状及相关技术 反求工程开始于对已有对象的数字化测量，对象可以是一个简单机械零件 的表面，也可以是一个复杂的模型( 如一只兔子的模型) ，甚至人体内的肿瘤、 组织、骨头等。根据不同应用领域的要求，不能对测量出的数据进行假设，如 要求测出的数据云有规律的，或要求测量出的数据是在x o y 平面上投影为单值 的数据。测量出的数据可以是任意的三维数据，甚至图像信息。如何以这些散 乱数据进行曲面重构是逆向工程的关键。 曲面重构技术是通过大量的测量数据点来重构实物的曲面模型。由于只有 依据测量数据点来进行反向建模，造型的过程是被动的，自由度很小，因此使 得反向建模比正向设计的技术难度要大得多。目前，曲面重构尚未形成成熟的 西北工业大学硕士学 立论文绪论 技术集成到c a d c a m c a e 系统中去。在当前国内外通用的c a b c a m c a e 软件系 统中，如美国e d s 公司的u g i i 、法国m a t r a 公司的e u c l i d 及s t r i m 、美国s d r c 公司的i d e a s 、美国p t c 公司的p r o e n g i n e e r 和日本h z s 公司g r a d e c u b e e c 等，只有u g i i 、p r o e h 和s t r i m l 0 0 软件具有专门的反求模块，但都只能进行 简单曲面的数据拟合，对复杂自由曲面的测量数据点集，直接拟合得到的曲面 光顺性较差甚至失真。u gi i 提供的由测量数据点集直接拟合自由曲面的功能限 制在矩形区域的数据点，对于区域边界不呈矩形，或是曲面形态复杂的数据点 集拟合得到的曲面失真很大。u g i i 还提供一种由点一线一曲面的曲面重构方法， 但测量点顺序、测量精度以及测量点拟合曲面的光顺性等都会直接影响重构曲 面的质量，往往造成重构曲面的光顺性较差，并且不适合空间散乱点数据点集 的曲面重构。美国i m a g e w a r e 公司开发的曲面重构专用软件s u r f a c e r ，反向造 型的方法与u g 2 类似，也具有同样的问题，对空间散乱数据的处理也比较困难。 世界各国的测量设备生产厂家也纷纷开始研制开发与其测量设备配套的实 物原型重构软件，如英国的d e l c a m 公司开发了与其测量设备配套使用的 c o p y c a d 软件，c a m i o 测量设备公司也提供了l kc a m i o 实物测量造型软件，d e a 公司为自己的测量仪开发的基于b e z i e f 曲面模型的系统s u r f e r ，德国c m m ( c o o r d i n a t em e a s u r i n gm a c h i n e ) 生产厂家z e i s s 的h o l o s 同样是基于b e z i e r 曲面，美国的i m a g e w a r e 公司的s u r f a c e r 可以将数据云转换为b - s p l i n e 曲面， 但只能从一些散乱点集拟合出单个b - s p l i n e 曲面。比利时的k r u t h 自行开发的 s h a p i d 系统包括测量、造型、快速原型的一套系统，在曲面造型上虽然支持 b e z i e r ，b - s p l i n e 曲线曲面，但系统采用线框模型，对于曲面间的连续性没有 进一步保证。另外s a k a r 和m e n g 对直接从离散点拟合b - s p l i n e 曲面作了研究， 但他处理的数据是假设投影到x o y 平面上其z 值是单值的情况，另外同样只能 处理单张b - s p l i n e 曲面。国内在此方面起步相对较晚，目前较成功的产品是广 州红地公司开发的“金银花( l o n i c e r a ) ”m d a 9 9 系统，采用三角b e z i e r 曲面 模型的浙江大学的r e s o f t 系统，另外山东工程学院汽车工程系亦已研制成这 类软件，并在汽车外形设计和反求中应用，但三维曲面的光顺问题还没妥善解 决，一般按人为方法去处理，具有一定的误差。 在实际应用中，现有的实物原型重构软件或带有实物原型重构功能模块的 软件系统都还存在着用户交互困难、重构曲面质量难以保证等问题。 作为曲面重构入口的测量数据，对曲面重构的方法具有重要影响。为了重 建方便，目前很多曲面重构的研究工作都对测量数据作了一些假设，只能处理 某些特殊分布的测量数据。 曲面重构过程可以分为三个步骤：对测量数据的预处理，数据和曲面的拓 西北_ 1 = 业大学颂士学位论文 绪论 扑组织，曲面的重建。其中后两个步骤是相互影响、彼此依赖的，拓扑结构的 组织形式决定了曲面的重建方法，去面重建的结果反过来又对拓扑结构的组织 形式提出要求。 1 2 1 散乱数据的预处理技术 ( 1 ) 数据测量 数据测量是指：采用某种测量方法和测量设备测出物体各表面的若干组点 的几何坐标。目前采用的主要测量方法有：坐标测量仪、激光测量仪、光学照 相测量仪、工业c t ( c o m p u t e dt o m o g r a p h y 计算机断层成像) 和逐层切削照相测 量等。坐标测量仪、激光测量仪、光学照相测量仪主要用于对实物原型的外部 形状的测量，而工业c t 和逐层切削照相测量则用于具有复杂内部轮廓的实物 的测量。目前国内各个大、中、小企业所采用的测量设备多为三坐标测量仪和 光学照相测量仪。 ( 2 ) 数据处理 数据处理是逆向工程中的关键环节，它的结果将直接影响后期模型重构的 质量。此过程中经常包括以下几方面的工作1 4 1 ：数据预处理，如噪声处理，多视 拼合等，增强数据的合理性及完备性。数据分块，整体曲面的拟合往往较难实 现，通常采用分片曲面的拼接来形成整块曲面。数据光顺，通常采用局部回弹 法、圆率法、最小二乘法和能量法等来实现。三角化( s t l ) ，直接为p r m 产生 切片数据和为b e z i e r 三角曲面造型奠定基础。数据优化，压缩不必要的战面 片内的数据点，减少后期计算曩。散乱数据处理，对于具有较复杂形状的工件， 测量数据中必然有一部分是无序的，须建立数据点间的拓扑关系。 由于测量工件的不确定性和复杂性，经常会出现散乱的数据点。散乱点三角 形拓扑关系的建立是研究中难点之一。l a w s o n5 j 于1 9 7 7 年提出的方法，成为后 来众多方法的基础。c h o i 提出了直接形成三维空间散乱点的拓扑关系的方法： 先形成结点列表t l i s t 届创成t b l ( t r a n s i e n tb o u n d a r yl i s t ) ，以t l i s t 为初 始，完整三角化。姜寿山等 7 11 9 9 5 年提出了从曲面凸包形的角度进行散乱数据 优化划分的条件。实用价值较大的是p a r d 等人8 1 完成的一种自适应的空间散乱 点的光滑逼近方法，其首先基于内外边界和特征线构造初始三角形网格，对存在 内边界的区域交互地分为几个无内孔的子区域，然后逐步插入最大误差点并递 推进行，直到所有数据点在设冠的误差阈值以内。这种方法将拓扑关系的建立和 模型重构有效地统一起来，优点是实现简单，数据压缩量大而且在加点的过程中 只需对局部曲面片重构。柯映林( 9 实现了c h o i 提出的三维直接三角化的方法， 并将自己提出的平面域内三角化方法【0 1 作为在复杂情况下的补充。f a n g 1 在这 西北工业大学硕士学位论文 绪论 方面做过大量的工作，他从平面散乱点的处理研究开始赢到空间散乱点，他的主 体思路为采用一种被称作包围盒( 空间或者平面) 的技术，将散乱点归入每个盒 子当中，然后利用盒子的相互关系建立拓扑。无论采用哪种方法进行散乱点的拓 扑关系重构，我们主要有下面3 条判断原则来衡量优劣：适应性，即这种方法 是否可以处理各种类型的数据集合，如多连通非凸域、多值数据等：复杂性， 算法实现的难易程度：时问效率性，这点尤为重要，因为反求工程中的数据量 往往是非常大的。 ( 3 ) 边界的提取 曲面复杂的产品，内外边界不好确定，测量时要么边界无法测量、要么是 测量不准确，易造成反求模型的“缩边”，或边界变形等工程问题。必须采用 曲面的离散延伸和空间投影相交技术来避免上述问题。曲面边界的离散延伸技 术的核心思想是构成曲面的特征线进行离散延伸、延伸方向应该注意最边沿测 量的两点矢量方向。延伸步距和延伸点是要根据边界曲线及其邻域的测量数据 来确定，构成曲面的特征曲线的延伸，可以实现曲面的延伸。根据曲面延伸后 得到的空间边界曲线通过投影法投影导x ，y 平面上得到平面边界曲线，将平面 边界曲线进行曲率变化的修改，得到完整的x ，y 平面边界曲线，用同样的方法， 求得x z 或y z 平面上的边界曲线，利用空间投影相交技术来确定空间边界曲线， 再利用空间边界曲线和特征曲线重新修改曲面。 ( 4 ) 孔洞修补 对具有孔洞和凸台的曲面，如将测量的数据直接反求曲面，由于相对完整 的曲面被孔洞和凸台分割成非完整的曲面，在孔洞和凸台处将会产生明显的畸 变，因此，必须对孑l 洞和凸台进行“平滑填补”，即将在该处的铡量数据进行 裁剪后再延伸增加，实现非完整曲面和残缺曲面的整型处理。 1 2 2 数据点网格划分 对象数字化得到的散乱数据云通常没有点的相邻信息，所获取的数据可以 是无序的数据云，必须按照一定规则将这些数据组织起来，建立数据的拓扑关 系，使得每个数据将归属于拓扑结构中的一个曲面。常用的拓扑结构表示有俩 种：基于三角域的表示和基于矩形域参数曲面的表示。 测量数据的曲面重构，最早是采用矩形域参数拟合技术，因此早期数据点 网格划分的研究都集中在矩形网格划分。采甩基于矩形域参数曲面的拓扑结构 重构出的曲面与通用的c a d c a m 系统兼容，可以直接输入到已有的c a d c a m 系 统中，进行二次设计和生产，达到真正意义的反求。不过由于对散乱数据和不 规则曲面，矩形域曲面拟合的效果不佳。相比而言，三角形网格比矩形网格更 西北】：业人学f i = i 十学位论文 绪论 为稳定，更能灵活反映实际皓面复杂的形貌，对复杂边界也能很好地表达，适 应于任意分布的散乱数据点集，因此人们在矩形域曲面拟合中矩形无法很好表 达的部分引入了三角形单元格，并开始探讨三角形1 3 e z i e r 曲拟合，研究三角网 格的划分，在曲面重构中取得了较好的应用。由于用各种测量手段获得的数据 点集往往是散乱无序的，因此对散乱数据进行三角网格划分近来数据点网格划 分的研究热点。 d e l a u n a y 或改进的d e l a u n a y 三角化算法，该类三角化算法是目前最常用 的三角化算法。d e l a u n a y 三角化技术发展到现在，已经出现了大量的不同算法。 一般可以将其分为三大类：( 1 ) 以b o w y e r ”1 和g r e e n 、s i b s o n s 邮1 为代表的计 算v o r o n o i 图方法出现较早，其基本思想是首先计算点集的v o r o n o i 图，最后 再求其几何对偶d t ，后来l e e 和s c h a c h t e r u 4 1 利用分治( d i v i d e a n d - c o n q u a r ) 技术也提出了一种直接计算v o r o n o i 图的方法。( 2 ) 以l a w s o n 5 , 1 6 1 为代表的对 角线交换算法的理论根据是d e l a u n a y 三角化的空外接圆特性。该方法是步进的 ( i n c r e m e n t a l ) ，每引入一新点，立即将其插入三角形中，并恢复d e l a u n a y 特性。( 3 ) w a t s o n 算法 1 7 - 1 9 ，其理论基础同样是基于d e l a u n a y 三角化的空外 接圆特性。虽然d e l a u n a y 三角化方法在二维平面区域问题中取得了相当大的成 功，但在3 d 网格自动生成中却遇到了巨大困难。在2 dd e l a u n a y 三角化中，最 大一最小角判据处处适用。但在3 d 情形，基于最大一最小角判据的对角线交换规 则不再成立，而基于外接圆判据的d e l a u n a y 三角化一般也不再能保证生成的网 格质量。遗憾的是，这是d e l a u n a y 三角化的本质弱点，它贯穿于网格生成全过 程，除非对d e l a u n a y 三角化概念本身予以修改 2 0 - 2 u 。 另外s e h r o e d e r 【“1 ，h o p p e 2 3 - 2 5 1 ，r o s s i g n a c 【“1 ，e c k t 2 7 i ，v e r o n h e 和l e o n ”1 ， 等人在数据的三角化及优化方面作了很有意义的工作。h o p p e 提出用微切平面 逼近三维散乱数据的三角形网格生成算法。该算法基于曲面形状信息反映在三 维散乱点集中，用三维点集中某点的邻域点集构造微切平面来近似表示该点处 的局部形状，所有点的微切平面集合则构成了待构曲面的近似表示。最后通过 欧几里德最小生成树对微切平面法矢方向进行调整使其达到整体一致性。该算 法从线性逼近的方向进行了探索，即用三角形网格来近似表示三维散乱数据所 表示的曲面，但并不要求散乱点为三角形网格中三角片的顶点。g u o 在进行曲 面拟合之前用口一s h a p e s 3 i 1 的理论获得近似多面体的拓扑结构。 可以看出，三角片的方法是一种“自底向上”的方法，如何自动得到三角 片的划分是拓扑结构产生的难点。这种模型首先侧重于对离散点的分割，试图 通过对离散数据的自动组织得到其拓扑结构，具有构造灵活、边界适应性好等 特点，因此一直受到广泛重视，在某些领域具有不可替代的作用。三角片的方 6 西北工业大学坝士学位论文绪论 法也具有一些缺点，例如所产生的三角片的数目巨大、几何连续性差、与通用 c a d c a m 系统接口不兼容等问题。 1 2 3 曲面重构技术 根据拓扑结构的不同，曲面的重构方法也有所区别。目前，在逆向工程中， 主要有三种曲面构造方案：1 ) 以b 样条或n u r b s 曲面为基础的曲面构造方案； 2 ) 以三角b z i e r 曲面为基础的曲面构造方案；3 ) 以多面体方式来逼近曲面物体。 1 2 3 ib 样条及n u r b s 曲面 在逆向工程中，型值点数掘具有规模大和数据散乱的特点，其b 样条曲 面的拟合要求比较严格，因而在b 样条曲面拟合中需要研究的首要问题是单一 矩形参数域内散乱数据点的曲面拟合问题。在众多的研究中，w m aa n d j p k r u t h f ”1 的工作较具有代表性。他们首先根据边界构造一张初始曲面，然 后将型值点投影到该初始曲面上，接着根据投影位置算出其参数分布( 从而解 决散乱数据的参数分配问题) ：根据这一型值点参数分配再拟合出一张新的b 样条曲面；最后，再对型值点参数进行优化，以使拟合曲面离给定型值点误差 最小。 在实际产品中，仅由一张曲面构成的情况并不多见，产品型面往往由多张 曲面混合而成。因而，只用一张曲面去重构其数学模型是很难保证其模型精度 的。于是，人们采用不同的方法来处理数据的分块问题。对于图像型数据( 即 具有行列特点的数据) ，b s a r k a ra n dc h 脚e n g i 3 3 j 运用图像处理技术，获取 曲面的特征线；然后根据这些特征线将曲面划分为不同的块，分别用b 样条曲 面拟合；最终将所有块拼接成一个整体。f s c h m i t 等h 4 1 提出一种四叉树方法， 首先构造一张整体的曲面，若不能满足要求，则将其一分为四，再对每- d , 块 进行处理，直到所有小块均满足要求为止。t v a r a d y 等 5 5 1 提出一种基于曲线网 格的方法，首先估算各型值点处的局部性质，以找出特征线( 如尖角、c 连续 及对称线等) ：然后再将特征线拟合成曲线网格，并用每一网格构造一张曲面， 以使网格内部的点与其对应曲面具有最佳的逼近性；最终对所有曲面片进行光 滑拼接。g b r a d l e y 等f 3 6 1 提出一种俩步方案：首先用函数方法，如s h e p a r d 插 值法构造插值于测量点的曲面数学模型，然后在曲面上构造拓扑矩形网格和交 互定义特征线，利用此矩形网格数据构造曲面。1 9 9 6 年，他们又提出另外种 称为o r t h o g o n a lc r o s ss e c t i o n ( 简称o c s ) 的方法【3 7 】，即首先对每块测量数据 进行三角剖分，并得到几张插值于测量点集的平面三角形网格模型；然后用3 西北工业大学颤士学位论文 绪论 组正交的等间隔平行平面与上述模型求交，求出每条交线的交点就得到o c s 模 型；最后根据曲面网格建立其曲面模型。1 9 9 9 年来新民等 3 8 1 对b r a d l e y 等 3 6 1 提 出的两步方案进行了改进，即在s h e p a r d 插值模型的基础上基于其曲率变化抽 取拓扑矩形网格并实现数据点的压缩，最终在拓扑矩形网格上进行n u r b s 曲面 重构。浙江大学也提出了两步方案，他们是先用插值法构造出三角b e z i e r 曲面， 然后在该模型基础上进行矩形划分以构造n u r b s 曲面。 以b 样条瞌面为基础构造的嘧面，其最终的曲面表达形式较为简洁，能够 与现有的曲面造型系统无缝集成。但建立在两次优化基础上的重构曲面，其光 顺性难以保证、且计算量大；曲线网格的建立、分块等都需要人工交互参与， 很难自动完成；重构曲面的精度也较难控制，在所介绍的算法中，若不能满足 要求，则必须从头开始计算。 1 2 3 2 三角曲面 在逆向工程中，三角曲面由于具有构造灵活、边界适应性强的特点，所以 一直受到重视。在三角曲面的应用研究中，以前的重点主要集中在如何提取特 征线，如何简化三角形网格上。1 9 9 4 年，x c h e na n df s c h m i t t 在研究基于图 像数据的曲面重建时，首先利用型值点估算出曲面的局部几何性质得到曲面的 特征线( 阶跃、尖角及曲率极值) ，并以此特征为基础建立初始的三角形网格； 然后自适应递增、有选择地将型值点插入三角形网格，而把三角剖分过程中未 用到的点都当作冗余数据；最后通过三角b e z i e r 曲面片的构造得到一张光滑的 曲面。1 9 9 5 年，h p a r ka n dk k i m 提出了一种自适应的光滑曲面逼近大规模散 乱数据点的方法，他们用分段三次i 角b e z i e r 代数曲面作为最终输出结果，而 使各三角曲面片之间达到跨边界c 1 连续。该方法从插值于产品的边界点开始， 不断插入最大误差点来逼近误差，直到所有测量点都在规定的误差范围内，曲 面的自适应逼近才结束。若逼近的允许误差为0 ，则曲面插值于所有数据点。 这种方法概念简单，数据压缩量大。在加点的过程中不需要对整个曲面进行重 构，而只改变相关影响领域，因而速度快。但是，在这一方法中采用非参数的 形式，其逼近结果将受到坐标系的影响，并且只能适用于单值曲面。另外，由 于在自适应的网格剖分中没有考虑曲面内点之间的连接关系( 指特征) ，因而， 重构曲面不能很好地重现原有特征( 或者是特征线附近曲面片会很密) 。 三角曲面能够适应复杂的形状及不规则的边界，因而在复杂型面的曲面重 构过程中具有很大的应用潜力。其不足之处在于所构造的曲面模型不符合现有 的产品描述标准，并与通用的c a d c a m 系统通讯困难。此外，有关三角b e z i e r 8 西北工业大学硕士学位论文 绪论 曲面的一些计算方法的研究也还不太成熟( 如三角曲面之间的求交、三角曲面 的裁剪等) 。 1 2 3 3 多面体方法 以多面体方式来重构蓝面是近年来用的比较多的一种方法。1 9 9 4 年华盛顿 大学的hh o p p e 通过研究大规模的散乱测量数据的曲面重构问题完成其学位论 文，并在许多刊物上发表其研究成果，概括起来，他的方法分为三个主要步骤： 1 ) 初始曲面估计【2 4 1 ：首先确定一个函数厂：( r 3 一尺) 来估计测量点到为止 曲厩m 之间的距离：然后采用一种等值线提取( c o n t o u rt r a c i n g ) 抽取算法 ( m a r c h i n g c u b ) 来提取f = 0 的曲面( 实际上是以三角平面片为基础的多面体， 或称之为三角化) 以逼近未知曲面m ，即使得z ( 厂) = p r 3 ：，( p ) = 0 ) 。 2 ) n 格优化】：以第一步的初始网格为起点，该步的目的在于减少三角形 数目，并提高曲面的逼近精度。他们采用能量法来完成这项工作，首先定义一 个能量函数以表示逼近精度与网格中所含节点数目的关系，然后优化这一函数， 使得在满足精度条件下节点数最少( 优化的变量为网格中的点数、点之间的联 接关系及位置) 。 3 ) 分片光滑细分曲面片1 2 5 j ：通过一种分片细分的方法来将曲面的尖角、皱褶 等特征构造出来，然后再分片进行曲面拟合，以提高曲面的逼近精度。其曲面 的表达形式为以三角平面片为基础的多面体。不过，这种方法不能精确地表示 二次规则曲线曲面( 如球形、圆柱等) 。 1 9 8 4 年b o i s s o n a tj - d 【4 2 1 提出了一类新方法，其思想是：先对散乱点进行 d e l a u n a y 三角化，然后用点标记出是曲面内部还是外部的d e l a u a n y 四面体，用 于标记用的点就抽象出采样曲面。a m e n t a n ，c h o ia n dk o l l u r i 【4 q 于2 0 0 1 年提 出了p o w e r c r u s t 算法，它使用曲面网格和一个近似的中间轴来重构曲面，并使 用了p o w e r 图单元来代替d e l a u n a y 四面体。2 0 0 2 年a m e n c an a n dc h o i | 55 】提 出了c o c o n e 算法，其思想是利用极点与c o - c o n e 区域来得到合适的受限 d e l a u n a y 三角片，从而重建曲面。2 0 0 3 年t d e ya n ds g o s w a r n i l 4 6 1 提出了t i g h t c o c o n e 算法，它很好地解决了由于欠采样面引起的孔洞问题。t d e ya n ds g o s w a r n i t “1 于2 0 0 4 年又提出了r o b u s tc o e o n e 算法，它的优点是基于d e l a u n a y 的重构算法可以成功地解决由于测量错误带来的问题，不过它对解决离群值和 欠抽样的效果就不太好了。2 0 0 4 年k o l l u r i ，s h e w c h u ka n db r i e n 【4 q 的e i g e n c r u s t 算法很好地解决前两个算法的问题。它先对样点进行d e l a u n a y 四面体化，并引 入一个光谱图的变量来区分四面体的分类，并进行曲面的重构。它能够忽视离 两北工业大学倾士学位论文绪论 群值，修补孔和欠抽样区域，并克服由于测量错误带来的模糊性。此算法可以 很随意地重构复杂曲面。不过它的缺点是偶然会出现些毛刺，另外不能很好 地重构尖角处。另外，江南大学的顾羡林等 6 8 1 人针对p o w e r c r u s t 算法提出了一 种不均匀降采样技术，得到了一种快速快速曲面重建方法。 1 3 本文的主要内容及安排 1 3 1 本文的主要内容 散乱数据的预处理技术 其中主要研究大规模散乱数据的简化问题。 散乱数据的空间三角化 主要研究复杂曲面散乱数据的空间三角网格剖分算法。 散乱数据的曲面重建算法 主要研究了基于d e l a u n a y 三角化的曲面重建算法c o c o n e 算法，并提出 了改进。 1 3 2 论文章节安排 第一章：绪论。 第二章：散乱数据预处理技术。研究了散乱数据的简化问题，并提出了 一种三维散乱数据的非均匀简化算法。该算法先采用撮小包围盒法将数据集 分割成许多大小相同的立方体，然后在每个含有数据点的立方体内，计算器 所包含的局部法向变化量，并根据用户给定的局部法向变化量阈值将数据集 进行非均匀简化。最后运用计算实例来验证算法的有效性。 第三章：散乱数据的三角化。本章介绍了教乱数据重构所必需的基础 的三角剖分技术。首先介绍了三角剖分的优化准则和它的分类。然后介绍 了一些常用d e l a u n a y 三角剖分的概念和经典的d e l a u n a y 三角剖分算法。 主要说明了d e l a u n a y 三角剖分与一般的三角剖分的关系，并介绍了多种 d e l a u n a y 三角剖分算法的具体实现技术，为后面的曲面重建算法作基础。 西北工业大学硕士学位论文绪论 第四章：基于d e l a u n a y 三角化的曲面重建算法。介绍了一些相关的基 本概念及理论基础。然后说明了c o c o n e 算法的基本原理及算法描述，并 讨论了该算法的优缺点。最后针对c o c o n e 算法在边界处理方面的不足， 提出了对它的改进：用距离条件进行三角形过滤。 第五章：结论与展望。对本文所作的工作进行了总结和提出下一步值 得研究的内容。 西北工业人学硕士学位论文 散乱数据的预处理技术 第二章散乱数据的预处理技术 目前对逆向工程技术的研究主要集中在：模型的数字化技术和曲面重构技术 两个方面上；而对数字型面的预处理技术则研究较少，过外的研究也主要放在噪 声点的处理上，对其它方面几乎没有涉及。本章主要对散乱数据的简化方面进行 了研究。 2 1 引言 随着测量技术的不断提高，各种高效、快速的测量方法和设备的产生，使更 好、更完整地描述被测物体成为可能，于是逆向工程中出现了大数据量的密集点 云。这种密集点云在提供了更加完整的对象零件的几何信息的同时，也提供了大 量的荣誉数据。由于这种数据无法直接进行有效的处理，降低了几何模型重构的 效率，故需要对其进行数据精简。数据精简的目的就是压缩不必要的数据点，在 保证精度的前提下生成适合于后续拟合的结构，故而并不产生新点，只是简单地 对原始“点云”中的点进行删节，并尽可能多地保留原始数据点的形状特征。 对于高密度散乱数据点云，参考文献【7 】提出了3 种数据精简准则：分别以精 简后数据集中点的个数、数据集中点的密度阈值及删除一点引起的法向误差的阂 值作为精简结束的依据。以精简后数据集中点的个数作为精简准则的方法是先用 r i m a n n 图建立散乱点间的邻接关系，然后按给定数据个数进行精简的。精简 的关键是要保证严格按优先队列进行精简；按指定数据点间的临界距离进行精 简，只进行简单遍历，不需要反复遍历寻优，故精简速度比前一个方法要快；第 三种方法则进行r l m a n n 图的最优遍历，并计算数据点的最小二乘拟合平面， 从而近似计算删除一点引起的法向误差，以此为阈值进行精简。该方法精简后的 数据集，在曲面曲率较小的区域分布的点较少。但该方法人工干预较多，适应性 不强。 m a r t i n 等人【4 7 1 利用规则的正交栅格将所有点分离，然后从每栅格中按照 一定规则选取采样点，完成数据精简。选取采样点的依据为：对栅格中的点按z 坐标的大小排序，提取z 坐标为中值的点。精简率由指定的栅格大小决定。栅 格越小，从点云中提取出的点越多，精简的幅度越小；反之，逆之。该方法在忠 实于原始数据的同时，也对噪音点进行了删减。这种方法主要针对被扫描面与光 源方向正交的情况下，用于快速精简具有联系的采样表面的情况。 西北工业大学硕士学位论文 散乱数据的预处理技术 在总结前人经验的基础上，本文针对具有大曲率区域和平坦区域的复杂曲面 提出了一种三维散乱数据的非均匀简化算法，该算法可以实现在大曲率区域保留 较多的数据点，而在平坦区域保留较稀的均匀数据点。 2 2 预备知识 本文首先采用包围合空间分割法对三维散乱数据进行分割处理，并求出k 近邻点和法矢量，然后进行非均匀简化，下面分三个步骤介绍预备知识。 2 2 1 八叉树法分割包围盒 我们采用八叉树空间分割原理对密集散乱点群进行空间分割，建立八又 树拓扑关系，能显著加快任意点的搜寻速度。 现代的测量数据方法，已经使得数据量达到了几兆、几十兆甚至上百兆， 所以说无论用什么方法来处理首先都必须解决如何高效处理庞大的三维点 群数据( 特征点、临男点或边界点的搜索) 。原始的测点数据之间没有相应 的、显式的几何拓扑关系，任何点的搜寻都必须在点群集合的全局范围内进行： 在几兆、几十兆无序测点数据集合中遍历搜寻，是造成三维散乱点群几何建模 速度很慢的主要原因。因此建立测量点群之间的几何拓扑( 空间位置) 关系，是 提高密集散乱点群几何建模速度的关键。三维散乱点群空间划分的拓扑关系 可以采用八叉树建立。 八叉树空间分割在实体几何建模、运动干涉检验等方面得到成功运用 4 9 - 5 0 。下面简单介绍八叉树空间分割原理、密集散乱点群八叉树拓扑关系的 建立。 如图2 - l ( a ) 示，八叉树空间分割模型是用一个立方体序列包围一个曲面 ( 数据云) 占据的空间。其方法是首先构造被测曲面的最小外接正方体，并视它 为八叉树模型的根结点，然后把该最d l - 接正方体分割成大小相同的八个子 立方体，每