（计算数学专业论文）逆向工程中关于散乱点曲面重构问题的研究.pdf

两北t 业大学倾二j ：学位论文 摘要 在逆向工程中，三维表面重构技术具有广泛的应用前景，通用高效的三维 表面重构算法的研究是当今十分重要的课题之一，特别是对采集的数据点是散 乱的更为迫切需要研究。 本论文主要从两方面来进行三维表面重构算法的研究，一种是基于三角网 格的形式的划分方法为基础，提出来的“基于散乱数据三维表面重构算法的研 究”，另一种是基于矩形域上而提出来的“拟均匀细分曲面方法进行曲面重构”。 在“基于散乱数据三维表面算法的研究”这一章中，首先通过八叉树的数 据结构的算法对三维散乱数据进行处理，然后再确定邻点和微切平面，最后用 三角网格化的方法完成三维物体表面重构。通过实例表明该算法大大加快了散 乱数据点群的重构速度，而且能够较为真实的重构出曲面模型。 我们在充分利用均匀c a t m u l l c l a r k 细分曲面方法与非均匀c a t m u l l - c l a r k 细分曲面方法优点的基础上提出“拟均匀细分曲面方法进行曲面重构”方法， 并且提出了最小内角之和最大的原则，作为非均匀细分到均匀细分的过渡的判 定准则。通过对曲面参数化的分析、计算，得到了特征点附近的任意子面片的 参数化格式。该方法在计算时不需要递归的细分控制网格，所以可以有效、快 捷和精确的计算整个子面片。另外，得到的参数化格式可以计算曲面在除( 0 ，0 ) 点外的任意参数处的任意阶导数的精确值。 关键词：逆向工程，三角划分，曲面重构，c a t m u l l c l a r k 细分 西北工业大学颂士学位论文 a bs t r a c t i nr e v e r s ee n g i n e e r i n g t h r e e d i m e n s i o n sm o d e is u r f a c er e c o n s t r u c t i o nh a s w i d ea p p l i c a t i o np r o s p e c t ，s ot h er e s e a r c h0 1 1t h ea l g o r i t h mo fu n i v e r s a la n de f f i c i e n t 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 em o s ti m p o r t a n tp r o b l e m st o d a y , e s p e c i a l l y , o n s t u d y i n gs c a t t e r e d d a t a p o i n t s t h i sp a p e rm a i n l ys t u d i e st h ea l g o r i t h mo 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 nf r o mt w oa s p e c t s ，o n eo fw h i c hi st h em e t h o d r e s e a r c ho n a l g o r i t h mo f t h r e em m e n s i o n sm o d e ls z t r f a c er e c o n s t r u c t i o nb a s e do ns c a t t e rd a t a p o i n t s b a s e do nt r i a n g u l a t i o n ，t h eo t h e rm e t h o d - - u s i n gt h ei m i t a t e u n i y o r m i t y s u b d i v i s i o nm e t h o d t o f i n i s hs h r f a c gr e c o n s t r u c t i o nb a s e d o nt h er e g i o n o f r e c t a n g l e w cc o n s t r u c tt h ea l g o r i t h mo f t h r e e - d i m e n s i o n sm o d e ls u r f a c er e c o n s t r u c t i o ni n t h r e es t a g e s ：f i r s t ，w eu s e0 c t - t r e et od e s c r i b es c a t t e rd a t ap o i n t si ns p a c e s e c o n d f i n da d j a c e n tp o i n t sa n d t a n g e n tp l a n ea n d u s et h et r i a n g u l a t i o nm e t h o d t or e a l i z e3 d s u r f a c er e c o n s t r u c t i o ni nt h ee n d ，i nr e s e a r c ho na l g o r i t h mo ft h r e ed i m e n s i o n s m o d e z s u r f a c er e c o n s t r u c t i o nb a s e d o ns c a t t e rd a t a p o i n t s s o m ei n s t a n c e si n d i c a t e t h a tt h i sa l g o r i t h mh a sg r e a t l yp r o m o t e dt h es p e e do fu s i n gs c a t t e rd a t ap o i n t st o f i n i s hs u r f a c er e c o n s t r u c t i o n ，a n dr e a l l yr e c o n s t r u c t e ds u r f a c em o d e l w eh a v ea d v a n c e dt h ep r i n c i p l et h a tt h es u mo ft h es m a l l e s ti n t e m a la n g l e si s t h em a x i m u mi nt h ep a r to fu s i n gt h ei m i t a t e du n i f o r m i t ys u b d i v i s i o nm e t h o dt o f i n i s hs u r f a c er e c o n s t r u c t i o n 、t a k ef u l l a d v a n t a g eo fu n i f o r i l lc a t m u l l c l a r k s u b d i v i s i o ns u r f a c em e t h o da n dn o n u n i f o r n lc a t m u l l c l a r ks u b d i v i s i o ns u r f a c e m e t h o d ，i nt h ec h a p t e ru s i n gt h ei m i t a t eu n 如r m i t ys u b d i v i s i o nm e t h o dt of i n i s h s t i r f a c er e c o n s t r u c t i o n t h r o u g ha n a l y s i n ga n dc o m p u t i n gt h es u r f a c ep a r a m e t e r ， w eh a v eo b t a i n e da r b i t r a r i n e s ss u b s u r f a c e p a r a m e t e r i s e d f o r m n e a r b y t h e e x t r a o r d i n a r yp o i n t s ，w h i c hc a nq u i c k l ye f f i c i e n t l ya n dp r e c i s e l yc o m p u t ea l lt h e s u b - s u r f a c e s i na d d i t i o n p a r a m e t e r i s e df o r ma l l o w su st o c o m p u t et h ep r e c i s e p a r a m e t e r i z e d s u r f a c e sd e r i v a t i v e ，e x c e p tt h ep o i n t ( 0 ，o ) k e y w o r d ：r e v e r s e e n g i n e e r i n g ，t r i a n g u l a t i o n ，s u r f a c e r e c o n s t r u c t i o n ， c a t m u l l c l a r ks u b d i v i s i o n 两北丁业大学硕 j 学位论_ ：【= 第一章引言 1 1 逆向工程与曲面重构技术 1 1 1 逆向工程简介 当今的时代已经是信息时代，全球统一市场逐渐形成，这样加剧了世界前 场的竞争使得市场对产品的价格和性自e 更为敏感，产品的生命周期变得越来 越短，产品的更新换代频繁，生产批量减小。如何低成本高效率地开发出新产 品，己成为赢得市场竞争的首要因素。传统的产品开发方式已难以满足新的市 场竞争的需要，而产品反求工程技术则以其在快速产品开发中的独特优势，得 到了广泛重视和迅速发展。 逆向工程( r e v e r s ee n g i n e e r i n 曲，又称反向工程或反求工程，是将已有产品 模型或实物模型转化为工程设计模型或概念模型。按其应用方向的不同，逆向 工程可分为产品反求和实物真实感模型反求。 逆向工程的设计过程与传统的设计过程是完全不同的。传统的正向设计过 程是在市场调研的基础上，根据功能和用途来设计产品，得到图纸或c a d 模 型，经检验满意后制造出产品来。而产品逆向工程是从已存在的零件或产品实 物原型入手，首先通过测量扫描等先进的数字化处理手段获得产品实物信息( 即 用个庞大的三维数据点集来表示整个零件) ，然后利用c a d 模型重构技术快 速准确地建立产品数学几何模型，再在工程分析的基础上，数控加工出产品， 或加工出产品模具后制成产品。 为了满足日益增长的计算机图形真实感的需要增强模型的逼真度，实物 真实感模型反求技术也越来越多地被应用于数字地面模型d t m ( d i g i t a lt e r r a i n m o d e l ) 建立、数字化图形仿真、虚拟环境构建、医学成像数摄的可视化、地质 勘探数据处理等方面。推动着虚拟现实技术和可视化技术的发展。 从实物原型到三维实物重构模型的过程，称为实物原型重构。后续过程刁j 论是进行雎纯的产品仿制，还是通过快速原型( r p ) 制成样品对产品进行工程，) 析，或匙剥重构模型进行创新设计或是虚拟现实系统中的真实感图形显示， 堕苎三些查兰堡! ：鲎堡笙兰 都要阿先进行实物原型重构。因此，可以说实物原型重构是逆向工程技术的核 心和撼础。 1 1 2 1 t 1 1 而重构技术的发展现状 曲诼重构技术是通过大量的测量数据点来重构实物的曲面模型。由于只有 依据测量数据点来进行反向建模，造型的过程是被动的，自由度很小，因此使 得反问建模比正向设计的技术难度要大得多。目前，曲面重构尚未形成成熟的 技术集成到c a d c a m c a e 系统中去。在当前国内外通用的c a d c a m ，c a e 软件系统r h 如美国的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 i 认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 g i i 提供的由测量数据点集直接拟 合自由i l l l 面的功能限制在矩形区域的数据点，对于区域边界不呈矩形，或是曲 而形态复杂的数据点集拟合得到的曲面失真很大。u g i i 还提供利t 由点线一 简面的l | _ | 】面重构方法，但测量点顺序、测量精度以及测量点拟合曲面的光顺性 等都会直接影响重构曲面的质量，往往造成重构曲面的光顺性较差，并且不适 合空洲散乱点数据点集的曲面重构。美国i m a g e w a r e 公司开发的曲面重构专用 软件s u r f a c e r ，反向造型的方法与u g1 i 类似，也具有同样的问题，对空间散乱 数据的处i 唑也比较困难。 世界各l j 弱的测量设备生产厂家也纷纷开始研制开发与其测量设备配套的实 物原型瞳构软件，如英国的d e l c a m 公司开发了与其测量设备配套使用的 c o p y c a d 软件，c a m o 测量设备公司也提供了l kc a m i o 实物测量造型软 件。 在实际应用中，现有的实物原型重构软件或带有实物原型重构功能模块的 软件系统都还存裆：着_ i j ，交互困难、重构曲而质量难以保证等问题。 1 2f h j 面反求相关技术及国内外研究现状 堕：坚三些叁兰丝! 兰些堡兰 由测量数据点反求曲面模型，可以通过两个途径来实现：( 1 ) 由测量数掘 点拟台得到曲线进行曲面建模，出二f 大部分酒i 量数据是散乱点集，甩这神方法 很难得到光顺曲线，同时难以保证由多条曲线拟合得到光顺曲面，曲面重构惰 度低：( 2 ) 通过测量数据点直接进行曲面拟合，首先根据数据点建立拓扑网格， 然后根据网格拟合得到测量曲面的三维数学模型，与前一种方法比较，这种方 法更为智能、自动用户交互少，重构曲面精度高。因此曲面重构路线常采用 第二种途径。 1 2 1 数锯测量 数据测量是指：采用某种测量方法和测量设备测出物体各表面的若干组点 的几俺坐标。琶前采用的主要测量方法有：坐标测量仪、激光溅量 史、光学照 相测量仪、工业c t ( c o m p u t e dt o m o g r a p h y 计算机断层成像) 和逐层切削照相测 量等。坐标测量仪、激光测量仪、光学照相测量仪主要用于对实物原型的外部 形状的测量，而工业c t 和逐层切削照相测量则用于具有复杂内部轮廓的实物 的测量。目前国内各个大、中、小企业所采用的测量设备多为三坐标测量仪和 光学照相测量仪。 1 2 1 1 数据处理 数据处理是逆向工程中的关键环节，它的结果将直接影响后期模型重构的 质量。此过程中经常包括以下凡方面的工作“：数据预处理瓤噪声处理，多视 拼合等，增强数据的合理性及完备性。数据分块整体曲面的拟合往往较难实 现，通常采用分片曲殛的拼接来形成蜓块曲页。数据光顺，通常采甩局部回弹 法、圆率法、最小二乘法和能量法等来实现。三角化( s t l ) ，踅接为p r m 产 生切片数掘和为b e z i e r 三角曲面造型奠定基础。数据优化。压缩不必要f i 勺i 曲 面片内的数掘点，减少后期计算量。散乱数据处理，列于具有较复杂形状的工 件。测量数据中必然有一部分是无序的须建立数掘点她j 的拓扑关系。 于测肇工件的不确定性和复杂性，经常会出现散乱的数扼点。敞乱点三角 形掘扑关系的建立是研究中难点之。l a w s o n 2 】予1 9 7 7 年提出方法，这是后来 众多方法的越础。c h o i j 提出了直接j ! ；成三维空川敝乱点的拓扑关系的方法：，t 西北工业入学 l ! ；! 士学位论_ ! ：c = 形成结点列表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 为初始，完 整三角化。姜寿山等”1 1 9 9 5 年提出了从曲面凸保形的角度进行散乱数据优化划 分的条件。实用价值较大的是p a r d 等人”1 完成的一种自适应的空间散乱点的光 滑逼近方法，其首先基于内外边界和特征线构造初始三角形网格，对存在内边界 的区域交互地分为几个无内孔的子区域，然后逐步插入最大误差点并递推进彳于， 直到所有数据点在设置的误差阈值以内。这种方法将拓扑关系的建立和模型重 构有效地统一起来，优点是实现简单，数据压缩量大而且在加点的过程中只需对 局部啦面片重构。柯映林“1 实现了c h o i 提出的三维直接三角化的方法，并将自 己提出的平面域内三角化方法作为在复杂情况下的补充。f a n g t 8 j 在这方面做过 大量的工作，他从平面散乱点的处理研究开始直到空间散乱点，他的主体思路为 采用一种被称作包围盒( 空间或者平面) 的技术，将散乱点归入每个盒子当中。然 后利用盒子的相互关系建立拓扑。无论采用哪种方法进行散乱点的拓扑关系重 构，我们主要有下面3 条判断原则来衡量优劣：适应性，即这种方法是否可认 处理各种类型的数据集合，如多连通非凸域、多值数据等：复杂性，算法实现的 难易程度：时间效率性，这点尤为重要。因为反求工程中的数据量往往是非常 大的。 1 2 1 2 边界的处理方法 曲面复杂的产品，内外边界不好确定，测量时要么边界无法测量、要么是 测量不准确，易造成反求模型的“缩边”，或“边界变形”等工程问题。必须 采用曲面的离散延伸和空问投影相交技术来避免上述问题。曲面边界的离散延 伸技术的核心思想是构成曲面的特征线进行离散延伸、延伸方向应该注意最边 沿测量的弱点矢量方向。延仲步距和延伸点是要根据边界曲线及其邻域的测量 数据来确定，构成曲面的特征曲线的延伸，可以实现曲面的延伸。根据曲面延 仲后得到的空间边界曲线通过投影法投影导x ，y 平面上得到平面边界曲线，将 平而边界曲线进t ? i t t l 率变化的修改，得到完整的x ，y 平面边界曲线，用同样的 方法求得x z 或y z 平面上的边界曲线，利用空间投影相交技术来确定空问j 边界i i | j 线，雨利用空问边界曲线和特征曲线重新修改曲面。 1 2 1 3 孔洞和凸台处理方法 西北工业夫学颅上学位论殳 对具有孔洞和凸台的监面，如烽泓量的数据直接反求盘露，出于棍对完整 的曲面被j l 洞和凸台分割成非完整的曲面，在孔洞和凸台处将会产生明显的畸 变，因此，必须对孔洞和凸台进行“平滑填补”。即将在该处的测量数据进行 裁剪后再延伸增加，实现非完整曲面和残缺曲顶的整型处理。 1 2 2 数据点网格划分 测量数据的曲面重构，最早是采用四边域参数拟合技术，因此早期数据点 网格划分的研究都集中在四边形网格划分。由于对散乱数据和不规则曲面，四 边域曲面拟合的效果不佳。相比而言，三角形网格比四边形网格更为稳定，更 能灵话反殴实际逝面复杂酶形貌，对复杂边界也能很好地表达，适应于任意分 布的散乱数据点集，因此人们在四边域曲面拟合中四边形无法很好表达的部分 引入了三角形单元格，并开始探讨三角形b 6 z i e r 曲面拟合，研究三角网格的划 分，在曲面重构中取得了较好的应用。 由于用各种测量手段获得的数据点集往往是敏乱无序的，因此对散乱数据 进行三角网格划分近来是数据点网格划分的研究热点。 1 2 z 1 网格划分的基本原则 经典有限元划分理论认为，网格划分应该满足以下要求： ( 1 ) 蕈元之间不能枢互重叠，要与原物体的占有空f 司相容，鄙单元格不能落 在原区域之外。也不能使原区域边界内出现空洞； ( 2 ) 单元应精确逼近原物体： ( 3 ) 单元的形状合理，每令单元应尽量趋近正多边形； ( 4 ) 网格的密度分布合理； ( 5 ) 相邻单元的边界相容，不能从一个单元的边或面的内部产生另个啦元 的顶点。 1 2 2 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 三角划分是将空间测量数据点投影到平面来实现的二维划分方 法。设空间测量点集p o l ，p 0 2 ，p o s 在平面上的投影为p i ，p 2 ，p n ，对每个投影 点r 划定一个区域v 。l i s n ，v i 区域内任何一点距p 。的距离比距其他任投 影点p i ( t ，蔓n ，f f ) 的距离都要小，即 一= x ：a ( x p ，) ( a ( x p j ) ，i ) v 是一个凸多边形，这种区域分割称为 d i r i c h l e tt e s s e l l a t i o n ，又称v o r o n o i 图( 蓝 色) ，如图( 卜1 ) 所示。由上面的定义可 知，v 区域内的边界是由结点p 与相邻结 点连线的中垂线所构成。每个v o r o n o i 多 边形内只包含一个结点。v o r o n o i 多边形 的集合( k 。“也称作d i r c h l e t 图。连接两 相邻v o r o n o i 多边形中的结点可以形成三 角网格，这就是d e l a u n a y 三角网格( 黑 色) 。 对于d e l a u n a y 三角划分算法，后人又进行了相当多的应用、研究和改进。1 d e l a u n a y 三角划分虽然可以获得给定数据点集的最优解，但它的划分结果是一 个三角形单元集合的凸包，对于有复杂凹面边界的实物数据点集，若不做专门 的处理，划分结果中会有大量的冗余三角形，必须在划分完成后删除。 m a r c v i g o i o l 等人在他们的d t 算法中引入了约束边，使得d t 算法可以处理有 凹边界和内7 l 的曲面数据：j o e 】采用的方法是将带有凹边界和内i l 的区域转化 为若干个凸域，先进行标准的d e l a u n a y 三角划分，爵将划分结果合并；还有 s a p i d s l l 川、f l o r i a n i 3 i 也进行了相应的f i j f 究和改进工作。 两北t 业人学坎i 一学位论义 国内南京航空航天大学的应维云“”、浙江大学的徐永安”、清华大学的闻 卫东等人“也对二维裁剪曲面和复杂边界曲面散乱数据点的d e l a u n a y 三角划 分算法进行了研究，以实现带约束的d e l a u n a y 三角划分。 处理凹域和7 l 域的三角划分是三角划分的研究c p 一直需要解决的问题之 一。 三角划分仍需要解决的另一个问题是：如何进行有重叠投影的散乱数据点 的三角划分。现有的三角划分方法都只能解决三维测量数据点与二维投影点一 一对应的情况，对于单向投影有重叠的数据点集，都是通过分片向合适的方向 投影，分别处理后进行拼接的方法来实现。这种方式往往需要大量的人工干预， 降低了三角划分算法的效率“”， 1 2 2 3 三角网格优化的准则 三角网格优化是指通过对原始网格m o 进行调整，使得到的网格m 中出现 尽量少的尖锐三角形，即在整个网格中所有三角形最小内角之和最大，并使得 网格形状变化最合理。除了d e l a u n a y 三角划分能保证划分得到的三角网格形状 最优化以外，通过其他划分方法得到的网格都需要根据优化准则进行优化。目 前三角网格优化有五种准则：最小内角最大准则、圆准则、球面准则、a b n 准 则和光顺准则。 ( 1 )最小内角最大准则 对一个严格凸的四边形进行三角化时，有两种对角线连接方式选择不同 的联系方式得到不同的三角划分。最小内角最大准则就是要保证对角线连接后 所得到的两个三角形的最小内角最大，此时是三角网格划分为最优。 ( 2 )圆准则和球面准则 严格凸四边形中的三个顶点确定一圆，如果第四个顶点落在圆内，则将第 四个顶点与其相对的顶点相连，否则将另外的两个顶点相连，称为圆准则，如 图( 示) 球面准则可以表述为：对于两共面体a 和b ，若a 的不属于b 的顺 点位rb 的外接球内则需对蕊四面体的拓扑关系进行变换；若位于b 的外接 球，则两四面体不作变换，保持其 ；f i i 扑关系不变。 ( 3 )a b n 准r ) ! l j ( a n g l e sb e t w e e nn o r m a l s 两北t 业人学埘! 1 学位论_ ：盘 ( 4 )光顺准则 对一个严格凸的四边形三角化时，有两种选择。设这两种对角线连接分别 为e 和e ，c ( e ) 为连接对角线e 时。四边形四条边上三角形对的夹角中的最小 值，c ( e ) 为连接对角线e 时，四边形四条边上三角形对的夹角中的最小值。光 顺准则就是要选择c ( e ) 和c ( e ) 中数值较小的一种三角化。 1 2 4 曲面的拟合 以往的三角曲面拟合方法研究大多集中在曲面插值。曲面插值的思想是： ( i ) 将散乱的数据点向二维平面上投影井在二维平面上进行三角网格划分和网 格优化，( 2 ) 估算三角曲丽片顶点处的偏导矢，( 3 ) 出三角曲面片顶点的位置矢 量和偏导矢插值边界曲线，( 4 ) 由边界曲线的控制顶点估算曲面片的内部控制顶 点”3 。 曲面插值的优点是计算速度快，但仍存在以下问题：( 1 ) 只能处理单值非封 闭曲面“。对于单向投影有重叠的多值曲面，就需簧进行大量而复杂的分片。 每。片分别处理后再拼接；( 2 ) 由于假定偏导矢在区域边界上呈线形分布”，恧 曲面重构依赖于估算出的偏导矢，因而得到的重构曲面精度和光顺性不够理想。 鉴于曲面插值算法的不足，那么可以用三角b 6 z i e r 曲面片逼近的方法进行 曲面拟合，可以得到精度和光顺性较好的重构曲面。 与四边域b 6 z i e r 曲面片类似，三角b 6 z i e r 曲面片也是一个基函数联系一 个控制顶点。一张n 次三边b 6 z i e r 曲面片是由构成三角行阵列的( n + 1 ) ( n + 2 ) 2 个控制顶点b 。f ，j ，k 20 、t + ，+ k = 月定义。因此。三角b 6 z i e l 曲面片的方程 可定义如下： s ( u ，v ，w ) = 6 冲b 量( “，v ，w ) ，0 “，v ，s l ，且“+ v + w = l ( t - i ) h j + k = n 式( 卜1 ) 。扣。b ”卅( “，v ，w ) = - 考击“v w 。0 蔓“，v ，w 1 。且”+ v + w = l 惩定义掘：王角域l 的双变量1 1 次b e r n s t e i n 基函数。 ! 角b e z i e r 曲而片逼近方法通过离散点的参数化、曲面片逼近和拼接，得 到重构瀚面。 ( 1 ) 离教点的参数化 ：三角划分的结果是j ：h 系列平面三角形逼近散乱数据点集。给定的离散点 集- f l 仪柯少数用作三角形的顶点，而相当多的数据点对曲诬插值来说是栩对多 s 龋北1 业大学唢卜学位浍义 三角b 6 z i e r 曲面片逼近方法通过离敞点的参数化、曲面片逼近和拼接，得 到重构曲丽。 ( 1 ) 离散点的参数化 三角划分的结果是用一系列平面三角形逼近散乱数据点集。给定的离散点 集中仅有少数用作三角形的顶点，而相当多的数据点对曲面插值来巍是相对多 余的【2 “。而曲面逼近方法充分利用了测量得到的所有数据，将这些未被选作顶 点的数据点向每一个三角形所在的平萄投影，如果莱数据点投影在某三角形肉 ( 如下图l - - 2 a ) 说明该点是这一三角曲面片内部的点。根据投影点p 和三角形 的顶点i 、疋和疋就可以用式( 1 - 2 ) 计算其重心坐标( “，v ，w ) ，也就是点p 在这 一三角曲面片中的参数。显然，参数“20 、v 0 、w 三0 。“4 - v + w = l 。 舻黜，v = 黜，w = 黜( 1 嘲 ( 2 ) 曲丽片的逼近 假定某个平面三角网格的内部点为tj = o ，1 ，2 ，玎，那么可以改三角网 格顶点为三个已知控制顶点邵b o 。氏。和瓦。的三角b e z i e r 曲面片应该满足下列 方程： b 盎( k ，v 一_ ) = ，j = o ，1 ，2 ，m 0 - 3 ) f + + 2 n 将式( 1 3 ) 中含有顶点b o 。，b 。和6 。的三项穆到等号的右边印构成含有 【” 1 ) ( h 十2 ) 2 - 3 个未知控制顶点的m 个矢量方程纽。于是，问题就转化为求 解一个矛厢方程组的最小二乘问题。至此改三角b 6 z i e r 曲而片也就唯一确定。 ( 3 ) i l l 丽片的拼接 q 塑垄三兰竺查兰堡! 兰竺笙苎 将上述曲面片在结点( 1 3 ，l ，3 ，1 3 ) 处细分，使其成为三张n 次三角b 6 z i e r 子 曲面片，如图l - - 3 b 。对具有公共边界的两张子曲面片t 和进行拼接，具俸 过程为： a )将曲面e 升阶即由n 次升为n + 1 次，记为f 。； b )将n 次的r 与n + 1 次的，；进行拼接； c 、将r 升阶为n + 1 次。 1 2 5 重构曲面的再设计 曲面再设计问题的提出，是产品反求中进行产品创新，使企业适应市场激 烈竞争的要求。在机械制造领域应用多年的仿制技术。是产品反求技术发展的 基础。但近年来产品反球技术已经有了更深的内涵。在现代企业中，产品创新 能力是市场竞争能力的核心之一。首创式刨新虽然在市场占有和知识资产方面 的回报很高。但试验与肃场开发的投入大时间长，风险大，而模仿式创新则 是利用首创的基本概念与原型技术，和首刨企业已经开发或正在开发的市场， 在其基础上再创新出奇，相对减少投入与风险，取得后发制人的优势。日本和 中国的一些成功企业的经验已经证实了这一点。中国作为发展中国家，在工业 创新的模式上利用模仿式创新的优势。可在产品创新的先期研究试验与市场丌 发方面节省大量时间与投资。 重构曲面的再设计实际上就是通过调整曲面形状获得新的设计方案，实现 模仿式创新。多年来，人们一直试图通过对曲面模型的控制顶点的谪节进行曲 而变形，佃都无法使越砸达到预定的彤状。自1 9 8 4 年b a r r 提出自由变形 ( f r e e t b r m d e i b r m a t i o n ) 的懋想后，国内外榴继开展了这方面白勺研究。【l j 予自由 变形仍是通过凋节曲丽控制顶点求实现的，因而曲面形：状很难控制，尤其是 要达到顶定的形状。 塑兰兰三些查兰塑主兰笙堡兰 鉴于自山变形的不足t e r z o p o u l o s 6 9 1 于1 9 8 8 年提出了物理造型方法，其 基本的思想是茬盥面造型时程曲面看成薄皈或弹性薄嫒。并嘏疆这个模型建立 区面的控制方程，然后通过引入一定的物理参数，如作用力、弹性系数等来调 节衄面的形状。按其求鳃方程的方法可以分为有限元法、有限差分法和变分法 三手中，至于有些文献中所涎的偏微分方程法和数学规= ! l 法或能量法仅仅是分类 方法的不同，实际都可以! j 三i 到其中。浚方法的最初出发点是通过物理参数来给 用户提供种易于操纵曲面变形的手段。但在实际使用中用户很难给出合适的 物理参数和控制曲面的最终形状。因此要使这一方法实用化还需进一步的 研究探索。 彭群生【列等人提出了种基于任意网格骨架的隐式曲面造型方法，为任意 网格骨架构造距离场，然后利用隐函数光滑过渡技术和c s g ( c o n s t r u c t i v es o l i d g e o m e t r y ) 表示技术将所构造的隐式自由益面两两稻合成一张光淆曲面，直观对 复杂自由曲面进行交互式设计。 虽然前人在曲面变形方面取得的研究成果己为重构曲面再设计奠定了一定 的基础，但如饵结合重拘趣蕊的鲁曳特点毂斑甩需求，开发出适合子重构秘蔼 再设计的曲面造型方面，是需要进一步考虑和研究的问题。 1 3 曲砸重构与简化的基本概念 描述物体表面形状的数学表达式称为物体的几何模型，也称为曲面的数学 模型。曲面的数学模型非常重要，它是对物体进行分析、计算和绘制的根据 是研究曲面性质的工具， 曲面是具有某种牲质的点的集合。从理论上讲，每张曲面都有它自己的数 学模型。但是曲面的数学模型的存在是一回事，人们对它的掌握是另一回事， 有很多复杂豹热面，其模型苯为入镪所掌握，锣；虹入筑头颀、动杨鹄骨头、雅 塑、工艺品等和野外地形等等；她有很多复杂的曲面有数学模型，但是未掌握 在需要者的手里，例如复杂叶片、复杂机械零件和某些出土文物器皿的外表面 等等。为了利用计算机对这类物体和其外表曲而避行分析、处理，酋要的征务 是为其建立数学模型。引这种数学模型没有被人们掌握的曲面，或数学模型虽 有但没有掌握在需要者m 手垦的曲而重新建立数学模型的过程称为曲丽的重构 ( 或讯建) ( s a t f a c er e c q n s t r u c c i o l l ) 。 壁些! 些垒兰竺! ! 兰望竺苎 曲面重构是根据已有的曲面去构造反映其心中的数学模型，正好与根据数 学模型生成符合其要求的曲面制造的过程相反。所以工程上又称曲面重构为逆 向工程( r e v e r s ee n g i n e e r i n 曲。 需要重构的曲面，其形状都很复杂。曲面重构工作需要采集大量的数据并 进行大量的计算，以前只能纸上淡兵，只有在近十年来出现了大容量、高速度 的计算机和各种先进的采样设备后，才为开展曲面重构工作提供了必要的工具， 使得进行曲面重构成为可能。 曲面重构的基本要求是准确易行。准确：要求建立起来的数学模型比较准 确地反映原来的曲面形状，或者说较好地逼近原来的曲面：易行：要求对所建的 数学模型易于迸行各种操作或者说较方便地适用于计算机进行曲面的存储、 分析、计算和绘制等。 实现以上基本要求的主要方法是分而治之，化繁为简。分而治之是指把复 杂约曲面分割成一块块小曲面片；化繁为简是指把每块小曲面片都用筋化的方 法来表示。其中代表性的做法有以下五种： 分片线形方法h o p p e 【2 2 1 于1 9 9 2 年提出，在曲面上裁剪大量型值点的位置 信息以后，先构造拟合采样点的分片隐式曲面，再用三角片逼近隐式曲面，最 终以三角片曲面逼近需要重建的曲面。 细分曲面方法h o p p e 2 3 1 于1 9 9 4 年提出，通过反求控制顶点的方法，为需 要重建的曲面建立控制网格，然后运用一系列的细分算子，对控制网格进行细 分，生成细分曲面，来逼近需要重构的曲面。现在较为常用的方法是( 非) 均 匀c a l m u l l c l a r k 细分方法， ( 非) 均匀d o - - s a b i n 细分曲面的方法 隐式曲面方法m u r a k i l 2 4 在1 9 9 1 年进行的人头曲面重建中，借助于势函数 的概念，用分片隐式曲萄作为硅l 厦重构的工具。 参数曲面方法e c k 2 h 等于1 9 9 6 年提出用b 样条曲面对任意的给定的拓扑 网格进行重构的方法。h a l s t e a d 2 6 1 等人同年提出了利用b 样条曲面构造高精度 地逼近需要重构的曲面法向的方法。虽然这种方法还不能重建有尖点和棱角的 曲面，但是它以b 样条为工具，就为包括b 6 z i e r 曲面在内的各种参数曲面参与 l i i l 丽羹构的工作7 r 牌了道踏。 变形模型方法m i l l e r 刚等在1 9 9 1 年提：b 了一种几何变形模型进行闭i l l | i 丽 覆构。叩先将种小艇嬲放入需爱重f = 的闭曲面的内爵| j ，然后d 其膨胀变j 髟。 西北工业大学顺l 学位论义 同时以要重构的曲面上的采样点作为对膨胀变形的约束条件。当模型的变形达 到某一平衡点时，就可以得到需要的数学模型。 以上方法在曲面重构中发挥了很大的作用。 曲面重构需要采集大量的数据，建成的模型一般都很复杂。这样大量的数 据给图形的实时显示、数据的存储与传输都带来麻烦和困难。为此，需要对重 构得到的复杂的数学模型进行简化，以减少数据量、减少数据模型的复杂程度。 一般称此工作为曲面简化( s u r f a c es i n p l i f i c a t i o n ) 。其代表住的方法有一下五种。 去点法这种方法按一定的准则删除一些不必要的点，达到减少数据量的 目的。s c h o e d e r p - g l 在1 9 9 2 年提出平面准则即在局部范围内拟合一张平面，删 除该平面的距离小于指定精度的点，并对保留的点重新三角化。 去边法该方法按一定的准贝l 删酴由曲面重构方法建立起来的网格中的 一条边，其做法是将要删除的边的两个端点合并为个点，同时保持原来的网 格点之间连接关系不变。 优化法t u r k t 2 9 1 在1 9 9 2 年提出，在由曲面重构方法建立起来的网格面上 重新采样，并根据某种优化的准则，使采样点在网格面分布均匀，逼近误差小。 最后对新的采样点进行三角化以形成简化的数学模型。 最大多边形祛k a | v i r t o 。l 于1 9 9 6 年提出，在由重构方法建立起来的网格面 上，将在指定的精度范围内可以近似地认为共面的相邻的三角形( 或多边形) 拼接起来，形成一个最大的多边形，用每个最大的多边形构成曲面的数学模型。 多分辨率方法该方法也可以称为多层次方法，它在逻辑上可以认为是替 要重构的曲面建立了一令从简单到复杂的数学模型的序列，人们可以根据需要 选用序列中的某一个元蒙表示的模型作为曲面的数学模型进行分析显示。模型 序列中的各元素之间具有递推关系。 1 4 本文中我所作的主要工作 第一章对l 韩 丽重构的研究现状、主流、趋辨等作了总的概述，充分的分析了当 今世，界l 的在逆向工程中的曲面重构的范围内主要的研究成果、方法及 其在l i | i 而重构方丽的不足进行了较为详细的叙述，阐明了本沦史的t 婴 f i j 充戏聚。 第2 - 嚣本职在参数化造型的壤础i i 辑重对般乱数据重构方丽进行了1 ) i f 究，其巾 ! ! ! ! 三兰竺墨兰丝! ：兰竺堡苎 对曲面重构的主要方法( b s p l i n e 、n u r b s 、三角b z i e r 曲面、微 切平面法、秭经确络、特征提取秘戴面变形方法) 进行较系统的余鳐。 同时指出关于一般离散点的曲面重构算法中存在的问题。 第三章本章首先通过八叉树的数据结构的算法对三维散乱数据进行处理，然 后再确定邻点和微切平面，最后用三角网格化的方法完成三维物体襄 面重构。丽提出了一个基于散乱数据三维襄蔼重构的整体算法。计露 实例表明本文的算法大大加快了散乱点群的重构速度，而且能够较为 理想的重构出曲面模型。 第四章提出了拟均匀细分曲面算法对空间散乱点进行曲面重构，充分利用均匀 c a t m u l l ，c l a r k 缀分曲面方法与菲均匀c a t m u t l - c l a r k 细分趋面方法的忧 点而提出来的拟均匀细分曲面方法，用户可以通过调节细分步距来对 重构曲面进行相对有效的形状控铋，通过对曲面参数化的分析计算 得到了特异点附近的任意予面片的参数化格式，它在计算时不需要递 归的绍分控制风格，所以可以非常有效、a 乍常快捷地精确计算整个子 面片，得到的参数化格式冗许计算曲面在陈，点外蛇任意参数处的 任意阶导数的精确值。 第五章论文工作总结及进一步研究工作展望。 1 5 本文中我的主要工作成果 1 在“基于散乱数据三维表面算法的研究”中，首先通过八叉树的数据结 掏的冀法对三维散乱数据进行处理，提出了一个基于散乱数据三维裹面重车句的 整体算法，通过实例表明陔算法比传统的方法在处理散乱数掘点群的重构速度 方面有了较大的提商，而且能够较为理想的重构出曲面模型。 2 在拟均匀细分曲面方法进行曲面重构”中。充分利用均匀c a t m u l l c l a r k 细分曲面方法与非均匀c a t m u l l c l a r k 细分曲面方法的优点而提出来的拟均匀 细分曲面方法其中主要的创新点是： ( 1 ) 用户可以通过调节细分步距柬对重构曲面进行相对有效的形状控制。试 验证i ! j ；j 该方法是有效的，比均匀c a t m u l l c l a r k 细分方法有较好的曲面形状的可 控性。 ( 2 ) 通过对曲两参数化的分析计箕，得刘了特舞点附近的任意予强片的参数 化格式，它在计算时不需要递归的细分控制刚格，所以可以非常有效、非常队 毖的精确计算憋个子两片。 ( 3 ) j5 外，得到的参数化洛式允即计算曲i 嘶存除( 0 ，0 ) 点外的任意参数处m 仟惑阶导讯的销疏缎。 西北t 业人学坝j j 学位论立 第二章曲面重构方法简介 曲面重构的方法在总体上可分为代数法和参数法。由于代数法在描述复 杂曲面形体时有较大的局限性，所以我们不做研究。参数曲面在跨界连续性、 曲面的约束及局部控制方面的良好表现而被普遍应用。常用的有b s p l i n e 、 n u r b s 、 三角b z i e r 曲面、微切平面法、神经网络和特征提取等方法，这 些隐面拟合方法已经成为曲面研究重点。参数化曲面造型中常用先对离散数 据点参数化，可以根据数据块的边界构造初始曲面。对应数据点在曲面上的 相对位置，从而计算出其各自的参数( “，v ) 分布，使数据点成为曲面片真正的 节点，然后对整个节点进行顺序排列。包括节点次序、节点编号和节点参数 化值。在这些基础上进行下步处理。 在参数化造型中数据的