（计算数学专业论文）反向工程中曲面重构与简化问题研究.pdf

反向工程中曲面重构与简化问题研究 摘要 反向工程，就是从实物样件获取产品数学模型描述的相关技术，它已经发展成为 c a d c a m 中的一个相对独立的领域。反向工程有两个主要的研究内容：一是实物模型表 面数据获取技术：二是曲面重构技术。数据获取和整合技术的发展为我们处理复杂物理 模型提供了可能，曲面重构技术就是根据获取的“点云”来恢复原始曲面的几何模型。 根据重构曲面的形式，曲面重构可分为光滑曲面重构和离散型曲面重构。 本文主要的工作包括对反向工程中复杂曲面重构的个简要介绍，以及主要的几种 点云简化和网格简化方法的详细讨论，然后综合简化方法和细分方法来尝试用细分曲面 来重构做了一些自己的工作。 非规则采样点云数据是现在常见的三维物体数据的表示方式，也近乎成为标准的数 据格式，随着现在测量技术的发展，对于曲面数据的获取，使用3 d 扫描仪，可以很容 易的得到数百万的数据点。这就对这些数据的处理，例如传输，储存，显示等提出了很 大的挑战。因此，为后续可视算法的处理做准备，对这些数据进行简化处理，已经成为 一个重要的发展研究方向。而细分曲面具有所需存储空间少，适于多尺度分析，生成曲 面速度快等优点。也是现在反向工程中的重要研究领域。 关键词；计算机辅助几何设计；反恕工程；曲面重构；细分曲面；点云简化； 反向工程中艘面重构与简化问题研究 a b s t r a c t s u r f a c er e v e r s ee n g i n e e r i n gi sa p r o c e s s t h a tc r e a t e st h eg e o m e t r ym o d e l sb a s e do nt h ed a t a o f r e a lo b j e c t sa n dt h er e s e a r c ho n r e v e r s e 既画m 期证g h a sb e c o m ea ni n d e p e n d e n la n dh o tf i e l d r e c e n t l y r e v e r s ee n 百n e e r i n g c a nb ed i v i d e di n t ot w os u bf i e l d s ；o n ei si n v o l v e di ns a m p l ed a t a o b t a i n i n gt e c h n o l o g y , a n o t l 脚i si n v o l v e d i ns u r f a c er e c o n s t r u c t i o nt e c h n o l o g y d a t a0 b 蛐 t e c m o o 科i s c o n c e r n e d a b o u t h o w t o g e t t h e p o i n t s d a t a f r o m t h e o b j e c t s u r f a c e s ，w h i c h p r o v i d e t h ep m b a b 姆o f d e a l i n gw i t ht h ec o m p l i c a t e ds u r f a c e s s u r f a c er e c o n s w 碰o ni e c h n o l o g yi s c o n c g m e da b o u th o wt ob u i l dt h eg e o m e t r yn l c h d db a s e do r t h e1 l r l o l g a n i z 耐3 dd a t a s u r f a c e r e c o n s t r u c t i o nm e t h o d si n c l u d e 瑶c l m 塔删o nw i t hs n a o o t hs u r f a c e sa n dr e c o n s w a e t i o nw i t h d i s c r e t es u r f a c e s t h ec o n t e r ao ft h i st h e s i sk n c l u d et h ei n l r e d u a i o no ft h el e v e s e e n g i n e e re s p e c i a l j yi 1 1 剐慨r e c o n s t r u c t i o n 越p e c t h em e t h o d so f p o i n tc l o u ds i m ；i l i f i c a f i o n , a n dt h er e c o n s t a u c t i o n o f s u b d i v i s i o ns u r f a c e i r r e # 盯3 dp o i n tc l o u dd i n , w h i c hn o w i se x t e n s i v eu s e di nc o m p u t e r - a ：i d e dg e o m e t r i c d e s i g n , h a st h es u c hf e a t u r et h a th u g es c a l e r i ot o p o l o g ye t c f o rs u r f a c ed a l aa c q u i s i t i o n , m o d e m3 d s c a n m n g d e v i c e sa r ec a p a b l e o f p r o d u c i n gp o i n t s e t st h a te o n t 出m i l l i o r l s o f s a m p l e p o i n t s r e d u c i n g t h ee o n 印l e x i t yo f s u c hd a t as e t si so n eo f t h ek e y p r e p m c e s s i n gt e c h n i q u e s f o r s u b s e q u e n tp r o c e s s i n g i t c a nm a k es t o r a g e , t r a n s m i s s i o n , c o m p u t a t i o n , a n dd i s p l a ym o r e e f f i d 锄t ，a n di i o ws u b d m s i o n 翱舭a i | e 寥瞳窀m o r ea 蛐f i o r l sf o ri t sf e a t so f l e s ss t | 蝣 s p a c e ，f a s ts p e e do f g e n e r a t i n gl e v e t o f d e t a i l s u r f a c e ，s u i t a b l ef o r h i e r a c h i c a ld e s i g ne t c k e y - w o r d s ：c o m p u t e ra i d e dg e o m e t r yd 姆( c a g d ) ，r e v e r s e , e n g i n e e r , s u b d i v i s i o n s u r f a c e s r e c o n s t r u c t i o n , p o m t c l o u d s i m p l i f i c a t i o n 3 反向工程中曲面重构与简化问题研究 月| j 菁 从9 0 年代初开始，特别是h o p p e 在其博士论文0 1 中给出了从任意拓扑的三维散乱点 到细分曲面的重构方怯，建立了反向工程这卜研究够蜮。在短短的十年间，反向工程已 经有了非常大的发展，发展方向包括散乱点的网格生成，复杂曲面的n u r b s 逼近，n u p d 3 s 片的光滑拼接。以及与多分辨分析，细分方法结合在工业制造，动画制作，c t 图像重构 方面的应用。在这些应用中间，由于曲面的几何复杂往，曲面的加工就变得比较困难， 参数化方法正是在这一要求下被发展起来的。 曲面参数化就是一种碟形三维曲面到平面多边形的一一映射的方法，通常该曲面用 三角形网格来表示或者逼近。由于其一一映射的性质和二维平面的易操作性，对于三维 曲面，特别是三维网格上很难实现的方法，可以先将三维网格映射到平面，在平面上进 行相应的操作，然后再逆映射到三维网格，就自得到不错的结果，例如对网格上一条折 线拉直，但是不能和边界相交，直接的方法是很难实现的，一般的方法是先参数化网格 到平面，然后在平面上找到连接折线的两个端点，连接两个端点的线段，求出该线段的 逆映射，得到折线拉直后的结果。 参数化方法在最近发展的很迅速，从1 9 9 5 年d e r o s e 的调和映射方法开始，到f l o a t e r 的局部保形参数化，以及后来的m i p s 方法，保角映自十等等，方法从线性方法发展到非 线性方法，虽然参数化效果越来越好，但是算法的复杂隆电在不断加大。同时，以前的 参数化方法都要求先设定边界的参数值，般都将边界点映射到凸多边形或者正方形上， 但是m i p s ，保角映射等参数化方法并不要求先确定边界点，会自动选择最优的边界点参 数值，使得了参数化效果进一步提高。 参数化方法在很多方面得以应用，例如重新n 格化( r e m e s h i n g ) ，般重新网格化的 3 5 - 法是将三维空间的三角形网格映射到多边形上，对多边形进行规则的三角剖分，然后 将这些平面上整齐的三角形网格逆映射到网格上，就得到了规则的三维空间的三角形网 格。对于材质贴图( t e x t u r em a p p i n g ) ，也是将三角形网格映射到材质平面上，网格的边界 和材质的边界对应，然后再将材质逆映射回网格就得到了材质贴图，当然在贴国时 可能会有一些特殊的要求，比如材质的点必须和网格的某个点对应，如果三角形网格不 是碟形区域需要对其进行区域剖分等等。 本文的主要的贡献是将参数化方法应用于几何性质复杂的曲面区域的插值点选取 中，获得的不错的结果。本文第一章介绍了反向工程的现状：第二章对的曲面参数化问 题进行了综述性的介绍；第三章介绍作者基于特定的问题利用改进的参数化方法所做的 应用。 反向工程中曲面重构与简化问题研究 1 反向工程简介 1 1 曲面造型的趋势和发展方向 曲面造型( s u r f a c em o d e l i n g ) 是计算机辅助几何设计和计算机图形学的项重要内容。 主要研究在计算机环境系统下对曲面的设计，显示，表示和分析。他起源于汽车、飞机、 船舶、叶轮等外形放样工艺，由c o o 蕊目杨豇等 于二十世纪六十年代奠定了理论基础。 如今，曲面造型已形成了以有理b 样条曲面限a 曲1 1 a l b - s p l i n t s 敝圮) 参数化特征设计和 隐式代数曲面o m p l i e i t a l g e b r a i cs u r f a c e ) 表示这两类方法为主体，以插值、拟合、逼近这 三种手段为骨架的几何理论体系。 近年来，随着计算机图形显示的真实性、实时性和交互性要求的日益从增强，随着 集合设计对象多样性、特殊性和拓扑结构复杂性趋势的日益明显，随着图形工业和制造 工女垃迈匈一体化、集成化和网络化步伐的日益加快和激光测距扫描等数据采样技术和硬 件设备的不断完善，曲面造型技术得到了长足的发展，已从传统的研究曲面表示、曲面 求交和曲面拼接，扩充到曲面变形，曲面重建，曲面倘化，曲面转换和曲面等讵性等方 面。 1 2 反向工程简介及其应用介绍 反向工程，就是从实物样件获取产品数学模型描述的相关技术，它已经发展成为 c a d c a m 中的个相对独立的领域。反向工程有两个主要的研究内容：一是实物模型表 面数据获取技术；二是曲面重构技术。数据获取和整合技术的发展为我们处理复杂物理 模型提供了可能，曲面重构技术就是根据获取的“点云”来陕复原始曲面的n 何模型。 根据重构曲面的形式，曲面重构可分为光滑曲面重构和离散型曲面重构。离散型曲面重 构的常用方法是建立离散点集的平面片逼近模型，得到是个任意拓扑的、稠密的、无 缝的多边形网格。与离散型曲面重构方法对应的两个重要的研究领域是网格简化 ( s i m d l i f i c a t i o n ) 和网格多分辨率分析( m u l t i r e s o l u t i o na n a l y s i s ) 。网格简化基本思 想是从三维重建后的离散曲面或造型软件的输出结果( 主要是三角网络) 中去除冗余信息 而又保证模型的准确度，以利于图形显示的实时性、数据存储的经济| 生和数据传输的快 速性。网格简化辅之以一定的细分( s u b d i v i s i o n ) 规则就构成了网格多分辨率分析的主要 研究内容，包括建立曲面的层次逼近模型，进行曲面的分层显示、传输和编辑等。这些 技术在动画模拟、l o d ( l e v e l - o f - d e t a i l ) 和网络数据传输中有很广阔的应用前景。 反向工程是现代测量技术、数控技术、c a d 技术、加工技术发展和综合应用的产物 对现代制造业起到了巨大的推动作用其意义在于： a ) 更好地满足企业产品开发和生产发展的需要，大大缩短了产品开发的周期，提高 了企业产品开发的能力和市场竞争力。 b ) 使设计思想发生了深刻的变革。更多的设计开发是在现有的产品基础上，从” 反求”入手进行改型设计，以加快本品的开发周期。与此同时，产品设计更多地 6 反向工程中曲面重构与简化问题研究 是从三维设计入手以取代过去从二级图纸设计入手的设计方法。 c ) 生产设备的选择需要重新认识。三坐标狈0 量机成为重要的测量检钡4 设备，特别 是在自动化生对过程中，是不可缺少的电子数据的来源。 d ) 使传统的仿形加工( 靠模加工) 向数控技形加工转变，提高了产品加工的速度 和精度。 e ) 反向工程的研究还为快速产品设计、快速源型制造绍现代先进制造技术提供了 关键的技术支持。 f ) 随着对反向工程研究的深入，其内涵不仅仅停留在对本品几何形状的反求而且 将扩展到工艺反求。材料反求等诸多方面。目前，大多数反向工程的研究都集 中在几何形状，即重建产品实物的c a d 模型方面( 本文所指的“反向工程”即 局限于这一概念) 。 1 3 反向工程的数据获取 反向工程的关键技术生要包括两方面。是样件表面的数据获取技术即数字化技术； 二是计算机反向建模技术，即曲面重构技术。数字化技术是指通过一定的测量设备和测 量方过去获取实物表面离散点的n ，何坐标信息。曲面重构技术是指利用测量数据进行曲 面和实体造型，以获得最接近于实物原型的c a d 模型。近十年来随着传感技术、控制 技术等相关技术的发展，出现了各种各样的样件表面数字化方法。如图1 1 所示数据的 采集方式主要分为接触式数据采集和非接触式数据采集两种。 非接触式数据采集，其测头不接触持测物体的表面，传递介质有激光、声波、电磁 场等，常见的是以激光为媒介的激光三角形法和激光成像法。它的特点是测量速度陕， 因而可以相当密集地对产品表面进行测量，形成所谓的“点云”数据。工业中常用的非 接触式数字化设各有激光扫描仪( l a s e rs c m n e r ) 、激光三角测量仪、工业c t ( c o m p u w d t o m o g r a p h y ，计算机断层摄像) 和自动切层扫描仪等。激光扫描仪和激光三角测量仪在 国外被厂泛采用。它们的侧整速度快、不损伤物体表面、数据点密集，特别适合于测量 图i - i 获取数据的方法 f i 毋n i - if 1 1 e m e f l a o d so f d l g i t l z a t l o n 7 反向工程中曲面重构与简化问题研究 尺寸较大的曲面。利用激光三角测量仅能对一些松软材质进行数据采集。并能很好地测 量到变面尖角、凹位等复杂轮廓数据，所采集的数据是物体表面的实际数据，无需测头 补偿，但缺点是价格较贵，且只适于测量外轮廓表面，测量精度不高，易引起“阴影效 应”，造成较大的失真。工业c t 和切层扫描主要用于有复杂内轮廓的实物测量。工业 c t 不损伤实物，是测量没有备件和复制品的实物刻唯一方法，但测量精度较低、成本 很高。自动切层扫描仪以极小的切削厚度逐层切刚实物，并对每一断面进行照相，这种 测量方法精度较高。但属破坏性测量。 接触式测量有点位触发式数据采集和连续式数据采集两种、触发式数据采集的原理 是，当用压每沛捧怫4 成的探头接触被钡b 物体表面时尚 针会受力产生个微小的变形触发 采样头中的开关产生个电信号，6 而记录下探针( 测球中心点) 的坐标值，它的采集速 度较低，般只适于零件表面的形状检测或需要数据较少的场合。连续或数据采集采用 模拟里开关采样头。它的原理是利用磁力感应器来检测轨过匕触头的位置和方向，它的 测量速度比点位触发式采洋测头快很多倍，采样精度也较高，可用于采集较大规模的数 据，但只能用于非金属村料的物体表面测量。接触式测量中常用的数字化设备是三坐标 测量机 如 厶，其相应的特征向量为v ，v ：，v ，我们选择玎，为v ，或 - - v ，其选择由切平面的方向决定。这样我们就得到了每个点切平面。接下来我们来为 这些切平面的法向定向。 假设x ，工，x 是几何上相邻，理想情况下，当数据点较密时，表面是光滑的，则 1 0 反向工程中曲面重构与简化问题研究 相应的切平面硒0 。) 。( d ，行，) ，t p ( x j ) = ( d ，疗，) 应该几乎平行，否则该平面 将会出现尖点，即( n ，- n j ) z l ，如果该表面有致的方向的话，则( 栉，n j ) = 1 ，但困 难的是找出该表面一致的方向，使得( 胛，”) = 1 。 我们可以建立一个图来解决这个问题，该图中每一个节点m 代表一个切平面 t p ( x ，) ，虫果v p ( x ，) 和劢( ) 地中心o ，0 ，相隔足够近的话( “足够近”就是个点 在另外个点的k - 邻集里) 。边( i ，j ) 的权重用( 啊n ，) 来表示，这样选择致方向 的问题，就转化为求该图的最大权重问题了。该问题是个n p 问题。为了有效的解决 该问题，我们应该求助于新的近似算法。 在描述我们使用的新的算法之前，我们必须减少图中边的对数，由于该表面认为单 连通分支，我们可以认为该图是单连通图，由于嘣李通图可以通过广度遍历和深度遍历 来连接所有的点。但显然生成衬的边太少，有可能导致错误的定向，我们再次给出以下 的算法，如果0 ，是d ，的瞄口集，或者o ，是0 ，的k - 集，则加入边( i ，j ) ，产生的图是 一个黎曼图。 相对简单的算法是任意找个有向平面，然后将该方向应用于相应的邻集，在实践 中，我们发现传播该法向的方向是很重要的，如果沿着非法的方向传播生成的表面，会 产生错误的拓扑结构，显然我们应该选择两平面的法向量最接近平行的方向作为正确的 传播方向，这可以通过计算1 一j 来确麒方向，因此我f 门可以通过建立该黎曼图 的最小生成树来完成该过程，这个方法是可以达到正确的方向的，根据最小生成树的原 理我们可以知道，该法向的传播会朝着低曲率的方向传播，这就使得我们在处理尖点处 的法向时，不会出现难以确定法向的情况。 反向工程中曲面重构与简化问题研究 划彤纭 吨h h f+ 事， 锄觚萨 图l - 2 原始点集图1 t 3 致的法向 f i g u r e1 - 2 酣西脚d a t a s e t f i g u r e1 - 3 c o n s i s t e n t n o r m a l v e c t o r 为了确定初始平面的法向量，我们选择切平面中中心o ，的z 坐标最大的点的法向量 的z 坐标大于零，然后生成最小生成树，我们用采用深度遍历的方法，使得每个节点的 法向同他的父接点一致，这就是说，如果他们的法向的乘积小于零的话，该切平面的法 向月= 一该算法应用于我们所有的例子中，都产生了正确的一致法向量。相应的法向 量图示见图1 - 2 。 得到了一致的法向后，就可以得到点到切平面的有向距离了( 图1 4 ) 。点p 到已知平 面的有向距离，( p ) 是点p 到m 中的点的最短距离再乘以土1 ，实际匕我们不知道原始 曲面，但我们可以用以下给出切平面模拟这一生程。首先我们找个其中心d j 离该点最 近的切平面印0 ，) ，该切平面是未知平面的局部近似平面，因此我 f 认为该点到未知平 面的距离用该点到印( x j ) 的距离来代替，即： f ( p ) = d i s t ( p ) = ( p d ) h 1 2 反向工程中曲面重构与简化问题研究 图1 4 点p 到最近的切平面的有向距离 l 时g t r e1 - 4 t h e d i r e c i e d l e n g t h o f p o i n t p t o t h e n e a r e s t t a n g e n t p l a r m 如果m 是无边界的，这种度量方法是正确的，但如果该切平面有边界，则该度量方 法还需要改进。捌f f 段设集合x = z ，_ 。 5 t i p 一密度，6 一误差的样点，我们可以推出 设一点z ，当d ( z ，z ) p 时，点z 不可能在面m 上因为面m 提取的样点是p 一密度，肯 定不能留下一个半径大于p 的洞，同理如果样点有6 一误差时，我们可以推出如果 d ( z ，z ) p + 6 时，则z 不可能是m 上的点此时我们取f ( p ) 为u n d e f i n e d , u n d e f i n e d 就 是我们在轮廓算法中识别边界的值。如e 所述，我们定义有向函数为： 设i 为切平面中心到点p 最近的切平面下标 计算点p 在r p ( x ，) 上的投影z ： z = p 一( ( p 一0 1 ) 聍，) n f i f ( d ( z ，) p + 6 ) t h e n 厂( p ) ；( p d ，) n ， e l s e f ( p ) = u n d e f i n e d e n d i f 上面提到这一简单的方法建立了一个局部线性近似的z ( f ) ，但含有一些不连绕这主要 是由于把空间分割成简单的切平面。 由上面所讲就可以得到空间中一点到曲面的有向距离，这样就可以利用一些轮廓生 成算法来生成三角形网格，如m a m h i n g c u b e 算法。 m a r c h i n gc u b e 是种建立轮廓的方法，该方法针对等值面的三角剖分或者本文所需 要的知道了近似切平面和法方向要求三角剖分的情况。下面我们以等值面为基础说明一 垦旦三堡! 些耍里塑量堡垡囹丝至塞 下三角形网格的生成方法，设等值面所对应的函数为，( 石，y ，2 ) = 0 ，该方法主要分成以 下两步，第一步，将曲面所对应空间区域分成一系列的小立方体。然后遍历所有的小立方 体，判断是否和相应的立方体是否相交，判断是否相交的条件就是对于立方体c j 的每个 顶点k ( 靠，y m ，靠) ，七= 1 , 2 ，8 ，判断，( ，y m ，) 是否异号，如果异号则表示相交， 反之表示不相交。 第二步，对于和曲面相交的立方体，相对应的8 个顶点的值分别为正或负就有2 5 6 种情况，除掉两种都为正和都为负的情况还有2 5 4 种，但是多种隋况由于其对称性本质 上是一样的，本质上可以归纳成1 4 种，如图1 5 ，黑色的小球表示魑廊该顶点取正 值。对于每种相交的情况，都对应于下面的种隋况，根据下面的图，我们就可以生成 相应的三角形片。所有的三角形片的集合形成了我们所求的三角形网格。另外，三角形 图1 - 5 曲面和m a r c h i n g c u b e s 相交的各种情况 蛳l - 5 啊田刚捌m 蛐c 慨 片在立方体边的位置选取可以通过坪嘣萄在边的两个顶点的值通过线性插值来获得。 将m a m h i n gc u l m 算法用在我们的应用中，我们假设所求的三角形网格是个在一 个等筐面上，那么判断黼面和立方体相交的判定方法还可以通过瞻定立方体的所_ 茸 顶点到该等值面的有向距离来判断，如果所有顶点的有向距离都同向则不相交，否则就 相交，有向距离的求法参见上面的算法，这样我们就可以通过m a 曲j n gc u b e 来生成三 角片了。 1 4 1 2 c r u s t 算法 c m s f 算法是山n e 眨腿出的种三维散乱点的重构方法，该方法在平面d i e l a l 1 y 三 角剖分原理的基础e ，提出个凸壳的概念，改方法的优点是第一次对三维重构的拓扑 正确上做了理论上证明，这样就保证了方法的理论正确性，而其他方法都是实践性的， 不能对重构的正确性在某种条件下作出保证，也不能作出个很好的评价。第二个优点 是对散乱点并不要求密度均匀，而只要求在表现细节的地方需要点云密集，而在稀疏的 反向工程中曲面重构与简化问题研究 地方散乱点可以分布稀疏一些。下面大概介绍他的算法。 c r u s t 算法并不要求散乱点的密度均匀，而是要求所谓的r - s a m p l e 标准，即如果样点 是从曲面f 上提取的，那么如果能正确的重构出来f 的要求是任意f 上的点到最近样点 的距离与到最近曲面中轴点的距离之比小于等于r ( r 肛输出的是一组双三次 b 样条曲面( 与初始网格的四边形面片对应) 。b 样条曲面是标准的插值形式，即“和v 节点向量的两端都是四重节点( 节点0 和扣2 的重数为4 ) ，每个节点向量有两个二重节 点( 在1 和虹1 处) ，其余节点重数都是l 。例如 0 ，o , o ，o , 1 ，l ，2 ，3 ，4 , 5 6 7 ，7 ，8 ，8 ，8 ，8 ) 。b 样条曲 面的控制顶点q ，。( f ) 可由输入的网格顶点只。( f ) 分两步计算得到。 图1 1 8 控制顶点的分类 f i g u 1 - 1 8t h ec i a 镐i 6 吐( 仉o f e o n 扫o lp o i n t s a 节点插九对每个四边形，定义c a ：h 1 1 u 1 1 c l a r k 细分网格的个子网格，其中包 括此四边形的所有子面片( 锄b 丘皑b 和与这些子面片至少共有个结点的那些子面片。如 图1 1 6 中双线右上方的那部分网格就是定义的子网格。 将四边形f 的两族互相垂直的网格线看作是三次b 样条曲面的控制网，其中b 样条 曲面的节点向量u 和v 是均匀的，目p - 4 ，3 矗，- 1 0 ，1 ，2 ，) ，不是标准的插值形式。p e t e r s 先分别将脚和u = k 插入三次，然后在v = o 和v 锹处实施类似的操作，这样最终的b 样条曲面就插值于四边形f 的四条边界。图1 1 9 说明了对一条u 线在u = o 处的标准节 点插入操作。 f i g u r e1 - 1 9 n o d 一 m s e m o n 图l 1 9 节点插入 反向工程中曲面重构与简化问题研究 这样控制顶点q 就可由e 得出 q o = ( j ，_ 3 十4 p o 十e x ) l e ，q 1 = ( 2 两4 - 焉) 3 对至少具有个非正则网格点的边，插入第二个节点，在u = o 附近，将1 插入节点 向量( 在u = kp f , f 近，将肛j 插，： q 2 = ( j 】b 十2 马) 南 q 4 = ( 2 飓十玮) 1 3 剩余的q ，j = b ，( f 0 ，o ) ，对岛o ( 1 ) 一- g k ( ”) ，有 q o , o ( 1 卜一咄州= 型巡篇掣 b 角点处的光滑处理如果只进行a 中的操作，则在角点周围b 样条曲面仅仅是c o 连续的，尽管在其它地方都是c 2 的。为了得到g 1 连续，p e t e r s 修正了非正则角点附近 的控制顶点。记力为非正则角点的度， 7 , 定义两个门力矩阵4 和e 如下： 厶( ，) = 等一( 等a 一州 默认n 一1 驯卜 ：= ：；圳叫。：鬻 啦叫= m a d ( n 十i 一 帕 例如，魂( 3 ，3 ) = - 1 。对心”：刀且u v e o o ，1 0 ，2 0 ，4 0 ) ，将由节点插入得到的控 制顶点q ，( f ) 月3 组合在起，形成彘( f ) 五“3 。只有当刀为偶数目大于4 时，才计 算r = ：，( 一1 ) 磊。( i ) n ；如果r o ，对每个，将曩= 一( 一1 ) r 依次加到 反向工程中曲面重构与简化问题研究 图1 - 2 0 角点的光滑5 z b 理 f i g u r e1 - 2 0 t h e p r o c e s s o f c o m e r p o i n t ss m o o 出e n i n g 9 4 。( f ) = g o ( f 一1 ) ， q 4 ，( f ) 和9 1 。( f 一1 ) 上，使得：，( 一1 ) 。q 4 。( f ) = o 并且 q 4 。( f ) = ( q 4 。( f ) + q l 。( f 一1 ) ) 2 。否则，除了下面几个外，所有的系数都保持不变， q 加= 孑+ 。q l o ， 0 = ( 1 巩。十6 q l o 一2 q o o ) 5 ， 口u = b ( q l o + 掣( q 一锄) ) 对j ”；1 7 , 当v l ，2 ，4 ) 复制q 。q + d = q 0 ，( 叭并且将q 2 0 ( f ) 一磊。( f ) 加到q ，( f ) 和 q j ：( f 一1 ) 上。 p e t e r s 证明了，输出的每片b 样条曲面在内部是c 2 的，除了在非正则点周围穿过 边界” o ，1 ) ，v 【0 , 1 】和v o ，1 ，u o ，1 】时曲面是切平面连续外，在其它地方曲面之 间也是c 2 的。 本节以b 样条曲面间的g 1 光滑连接为重点，回顾了任意拓扑区域上的g 1 曲面拟合中 连续性处理的方法。 1 5 总结 本章主要对反向工程中和复杂曲面自动重构相关的各个方面给出了一个简要的介 绍，让我们对反向工程所要作的工作有个大致的轮廓。 反向工程中曲面重构与简化问题研究 2 简化方法综述 2 1 简化方法介绍 反向工程的第部分要做的工作就是得到物体的数字化信息，一般的标准数据格式 为点云数据或者网格数据，然后对数据进行分析，处理，重建，得到最终重建的曲面。 一般隋况f ，得至0 的数据越是详细，最后重构的曲面的质量就会越与真实曲面相近。随 着现在测量技术的发展，比如激光3 d 扫描仪的使用，使得可以很容易的得到上百万数量 级的数据，这样对于曲面的重建，可以提供更多的信息，使得重构的曲面质量更好，但 同时也因为数据的数量级臣大，也剥数据的后继处理，比如存储，传输，显示每黻出了 很大的挑战，所以对数据进行简化处理正变得越来越重要。简化的目的就是要用最少的 数据信息来达到最大的原始曲面的特征的保留。 2 2 网格简化方法 多边形模型现在在互动三维计算机图形学领域占有统治地位。这主要是因为他们的 数学简化方法允许对多边形数据集的快速显示渲染，也因此大力推进了很多支持多边形 渲染的硬件的发展。而且，多边形模型表示现在可以作为一种计算机模型表示的最通用 方法，因为几乎其他的模型表示( 样条( s p l i n e ) ，隐式曲面表示( i m p l i c i t s u r f a c e ) ， 体素表示( v o l u m e t r i c ) 等等) 都可以被 专化为任意精度的多边形网格表示。基于这些原 因，多边形模型现在已经是在医学领域，科学计算领域和c a d 领域得到最广泛应用的一 种数据集的可视化表示方法。 高精度的扫描测绘手段为复杂物体基于多边形网格表示的三维几阿建模提供了新的 高效手段，但由于采样精度高，由此建立起的三维模型的复杂程度远远超过了当前计算 机实时的图形处理能力。如何降低这些模型的复杂度，减少图形系统需处理的多边形数 目，实现实时交互，已经成为计算机图形学研究中的个重大课题。为此人们提出了各 种方法，细节层次l o d ( 1 e v e lo fd e t a i l ) 便是其中种非常有效的控制场景复杂度的方 法。 所谓l o d 技术，就是在实时显示系统中所采用的细节省略( d e t a i le l i s i o n ) 技术。 这项技术首先由c l a r k 3 4 于1 9 7 6 年提出，基本思想是：如果用具有多层次结构的物体 集合描述一个场景，即场景中的物体具有多个模型，其模型间的区另u 在于细节的腾述程 度，那么实时显示时，细节较简单的物体模型就可以用来提高显示速度。实时显示时， 模型的选择取决于物体的重要程度，而物体的重要程度由物体在图象空间所占面积等多 种因素确定。在计算机图形学中，场景中的物体通常是用多边形网格描述的，因此l o d 模型的自动生成就转化为三维多边形网格的简化问题。 反向工程中曲面重构与简化问题研究 l o d 模型的缺点是所需存储量大。当使用l o d 模型进行绘制时，有时需要在不同的 l o d 模型间进行切换，这样就需要生成多个l o d 模型。此外，离散l o d 模型无法支持模 型间的连续过渡。为此，人们开始研究多分辨率模型。 严格地讲，多分辨率模型是指一彳孛紧凑的模型表示方法，撕这个表示中可以生成任 意多个不同分辨率的模型，个典型的代表是m i c r o s o f t 公司的h o p p e 2 1 提出的累进 网格。不过，由于有些网格简化方法能够生成连续的l o d 模型，因而在些文献中，也 把这类模型统称为多分辨率造型。 为了生成l o d 模型，近几年来研究人员提出了多种多边形网格简化算法。网格简化 的目的是将个用多边形网格表示的模型表示为个近似模型，近似模型基本保持了原 模型的可视特征，但顶点数目少于原始网格的顶点数目。通常的做法是把些不重要的 图元( 顶点、边或三角形) 从多边形网格中移去。 目前主要有两类多边形网格简化方法：基于n 何特征识别j 蝴基于小波变换的方 法。小波变换是八十年代后期发展起来的数学分支，在计算机图形学中具有广阔的应用 前景，其中多尺度分析姒( m u l t i r e s o l u t i o na n a l y s i s ) 是一个重要方面。基于m p a 的简化网格是对原始网格的简单近似，被省略的细节可以通过一系列的小波基重构出来。 尽管小波计算的复杂性影响了这类方法的应用，但这类方法具有明显的优势，利用经过 处理的小波基序歹日，只需要很少的面片就可以逼近原始网格，在构造多分辨率模型、三 维几何数据压缩、模型的甜级传输和l o d 控伟情瘟用中有着无可e 匕拟的实用价值，因此 逐渐成为模型简化的研究热点。 基于凡f 嘴钲识别嬲简化方法根据对原始模型的逼近精度要求，识别并保留模 型中的几何特征信息、消除r 涂信息，从而达至删简化目的。有了快速、可靠的模型 简化方法，只要给出不同的逼近精度要求，即可构造出层次化模型。各种基于几何特征 的模型简化算法都会采用如下四种多边形简化方法的变形形式或者组合形式。这四种方 法是彩 4 ( s a m p l i n g ) ，自适应细分( a d a p t i v es u b d i v i s i o n ) ，迭代消除( d e c i m a t i o n ) ，顶 点聚合( v e r t e xm e r g i n g ) ； 1 采样( s a l r i p l i n 亩 采样方法开始于采样厕恻的几何屠息。这些采样点可以是悖型中2 - d 流形曲面 上的点或者是3 - d 网格层次鲫中的体素点。算法的下一步就试着去建立们旨近原始 模型的多边形简化模型。选择不同的采样点数目可以得到不同精度的简化模型。 2 自适应细分( a d a p t i v es u b d i v i s i o n ) 自适应细分方法会得到一个很简单的原始模型的多边形逼近模型，称作为基模型 ( b a s em o d e l ) ，这个基模型的般m - - 角形网格或者四边形网格构成，还有一定的细分 规则。这个细分的规则持续应用到基网格上，一直到结果模型和原始模型的误差缩小到 用户定义的误差范围之内。概念上很简单，但是这种方法也有两个要解决的问题。第一， 建立基网格就i l 吸到简化问题的各个方面，所以细分的方法在地形显示领域育着j 艮好的 应用，因为地形研究领域的基网格出饺容易计算。第二，由基网格迭代生成的细分曲面 反向工程中曲面重构与简化问题研究 一般不能很好的抓住原始模型的几何特征，特别是在网格的尖角或者转折处( s h a r p c o r n e r sa n d ”e r e & s e s ”) 。 3 迭代消除法( d e c i 豫t i o n ) 选代消除( d e c i m a t i o r 】) 方崮卷代的移除网格模型中的顶点或者面片，然后重新三角 化产生的孔洞区域。这个力谨硷直持续进行下去直到满足用户定义的要求。因为很多 的d e c i m a t i o n 方法一般会很小心的选择要消去的点或者面片，尽量的保持原始模型的拓 扑结构，所以最终的结果模型不会得到很大的简化率。 4 顶点聚厶( v e r t e xm e r g i n g ) 这种方法持续的把两个或者更多的顶点聚合为一个顶点。受到影响的三角形会i 屋化 或者被消除，这样就减少的总共的多边形面片数目。顶点聚合的方法不需要知道原始模 型的拓扑结构。尽管有些方法会隐含的假设拓扑结构。这些算法的爪j 腻就是边消除 算法，在这个算法中只有一条边的两个端点才会被消除，聚合为个顶点。 对于网格简化的分类，还可以考虑其他的方面。如视点相关、拓扑结构及误差分析 等。 视点棍老睦 把算法分为两大类，即与视点无关的模型简化算法和与视点有关的模型简化方法。 早期的算法都与视点无关，近两年出现了一些与视点相关的方法，这是个重要的发展 趋势。 拓扑结构： 在多边形简化领域，拓扑结构指的是2 固流形或者网格的连接结构。一个面，边或 者顶点的局部拓扑指的是它与周围的邻域几何关系。个保持局部拓扑结构的简化算法 将不会改变这个n 何结构，它会保 寺i 塞个简化曲面的种类( g e 叫s ) 。全局拓扑结构指的是 整个曲面的几何结构。个算法如果保持局部拓扑结构，而且不生成自交的 ( s e l f - i n t e r s e c t i o n s ) 部分，那么它就会保持全局的拓扑结构。许多真实世界的c a d 模 型包含有违反局部拓扑规则或者全局拓扑规则的对象。因为c a d 模型数据的互动可视化 是多变性简化的个主要应用。所以对于这些模型数据，不同算法得到的结果也是个 重要的分类方式，拓扑结构保持算法和非拓扑结构保持算法。拓扑结构保持算淄顷向于 得到更好的逼真程度。因为他们保持了简化的模型的原来的灼4 ( g e n u s ) ，在简化过程中， 原始数据中的孔洞部分( h o l e ) 不会得到消除。然而这一点对保持拓扑结构的算法也是一 种限制，因为不进行闭合孔洞的操作，个含有较蔚中类的( h i 曲g e n u s ) 网格数据不能 被简化到所需要的简单程度。而且，保持拓卦结构的算法的初始输入数据需要是个具 有正确拓扑结构的网格。s c h r o e d e r 9 2 的算法会忽略具有非法拓扑结构的区域，不对它 进行简化，而另外的些算法可能就会出错而不能正确执 亍下去。不保持拓扑结构的算 法将不认为保持局部或者全局结构为准则。因l 比在简化的过程中，它会闭合些原来的 反向工程中曲面重构与简化问题研究 孔洞部分，相对于保持拓扑结构的算法而言，它可以达到更好的简化程度。但这种更大 程度的简化所带来的还有就是较差的保真度。一些不保持拓扑结构的算法的初始网格输 入不需要一定具有正确的拓扑结构，这一点可以在现实的c a d 应用中得到很好的使用。 还有一些不保持拓扑结构的算法可能会试图调整拓扑结构的变化，4 e _ j e 大多数的算法是 拓扑无关的( t o p o l o g y i n s e n s i t i v e ) ，他们不在乎初始网格的原始连接结构。误差可控 性：有两层含义，一是用户对整个模型的近似误差是否可以控制( 全局) ：二是指用户对 局部误差是否可以控制。进一步讲，用户可以有选择地对模型的不同部分使用不同的误 差度量。 误差度量( e r r o rm e t r i c ) ： 基于保真度的简化技术允许用户以某种形式确定建华所需要的逼真程度，然后在 满足逼真程度的条件下最小化所需要的多边形面数。不同的方法会有不同的逼近程度的 定义。个般的定义是简化曲面和原始曲面之间的最大距离。自适应的细分算法可以 很好的与这种误差度量相搭配，它可以简单的持续的细分基网格知道满足逼近程度的条 件。基于多边形面数的简化度量系统以一个给定的多边形面数为目标，试图在不超过度 量限制的情况下，最大化简化网格的逼近程度。这种方法和d e c i m a t i o n 的方法搭配得比 较自然，因为它的方法是持续的消除顶点或者面片，直到到达指定的面片数而终止简化 算法。如上面所提到的，拓扑结构的限制常常会使得d e c i m a t i o n 算法达不到所需要的简 化程度。理想的说，最好的简化方法既需要支持基于保真度的操作，又要支持基于多边 形面数的操作。对于生成精确图像的方法来说，基于保真的方法是重要的，同时对于时 间限制，