（计算机应用技术专业论文）反向工程中三维模型重建研究.pdf

中文摘要 计算机辅助设计中的反向工程，是根据实物模型和样件测量数据，建立数 学模型，然后将这些模型和表征用于产品分析、制造和加工的先进方法。它是快 速原形制造、快速模具制造的重要组成部分，它在工业仿制、航天、军事等诸多 方面都有广阔的应用前景。 论文有重点的展开了对反向工程三维重建的讨论与研究，综述了反向工程的 基本理论。讨论了模型重建方法：基于规则数据的等值面抽取算法m c ( 移动立 方体) 算法；基于散乱数据的径向基函数三维重建算法。 在讨论了模型重建算法的基础上指出，当前反向工程的主要问题是模型重建 产生的网格模型的数据量过大造成显示和交互操作困难，论文详细讨论了重建后 的网格模型的简化方法。提出一种改进的累进网格简化方法，引入了新的误差控 制手段，加入特征边判定并优化了简化流程，在保证视觉效果的前提下，提高了 简化速度。 关键词：反向工程、网格模型简化、三维重建、m c 算法、径向基函数 a b s t r a c t r e v e r s ee n g i n e e r i n gt e c h n o l o g yi nc a d i saa d v a n c e dm a n u f a c t u r i n gt e c h n o l o g y a n dw h i c hf o u n dm a t hm o d e l sb a s e do ns a m p l et h er e a lm a t e r i a lt o ，a n dp r o d u c t i o n a n df a s tl l s et h e s em o d e l sg u i d ep r o d u c t i o na n a l y s e ，p r o d u c t i o nm a n u f a c t u r i n ga n d p r o d u c t i o np r o c e s n n g r e v e r s ee n g i n e e r i n g i st h em o s ti m p o r t a n tp a r to ff a s tp r o t o t y p e m o d e lm a n u f a c t u r i n ga n df a s tm o d e lm a n u f a c t u r i n gt e c h n o l o g y ，i ti sw i d e l yu s e di n i n d u s t r ys t r y p p e d d o w n ，s p a c e f l i g h ta n dm i l i t a r ye t c d i s s e r t a t i o nm a i n l yf o c u so nr e c o n s t r u c t3 dm o d e lf r o ms a m p l es e t sa n dm e s h m o d e ls i m p l i f i c a t i o n 。d i s c u s st h eb a s i cc o n c e p t i o no fr e v e r s ee n g i n e e r i n ga n di t s a p p l i c a t i o n a n a l y s e s t h ec o r e t e c h n o l o g y i n r e v e r s e e n g i n e e r i n g d i s c u s s m c ( m a r c h i n gc u b e s ) a l g o r i t h mt o d e a lw i t ht h ef o r m a ls a m p l ed a t as e t ，w h i c hi sa c l a s s i c a la l g o r i t h mt oe x t r a c ti s o s u r f a c ef r o mr e g u l a rv o l u m ed a t a d i s c u s sh o wt o u s er a d i a lb a s i sf u n c t i o no n3 dm o d e lr e c o n s t r u c t i o ns u r f a c em o d e lf r o ms c a t t e r s a m p l ed a t a s e t b a s e do nr e s e a r c h i n gt h em o d e lr e c o n s t r u c t i o na l g o r i t h m ，p o i n to u tt h a tt h e m a j o rp r o b l e mi nr e v e r s ee n g i n e e r i n gr e c e n t l yi st h ed a t as e tc o m i n gf r o mt h em o d e l r e c o n s t r u c t i o np r o c e s si st o ol a r g ei ns c a l e ，s oi t sh a r dt ob ed i s p l a y e da n d d i s p o s e d t o o v e r c o m et h eb o t t l en e c ko ft h ed i s p l a ya n dt r a n s m i tm e s hm o d e l d i s c u s sm e s h m o d e ls i m p l i f i c a t i o n ，m e n dap r o g r e s s i v em e s h m o d e ls i m p l i f i c a t i o nm e t h o d ，w h i c h i m p o r tn e w e t r o rc o n t r o lm e t h o da n dw e i 曲o fs u r f a c ec h a r a c t e r ，a n do p t i m i z et h e m o d e ls i m p l i c a t i o n p r o c e s s ，t oa c c e l e r a t et h ep r o c e s so f m e s hm o d e ls i m p l i f i c a t i o na n d m a i n t a i ns u r f a c e ra p p e a r a n c eo ft h em o d e l k e yw o r d s ：r e v e r s ee n g i n e e r i n g ，m e s hm o d e l s i m p l i f i c 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 ，m ca l g o r i t h m ，r a d i a lb a s i sf u n c t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位黻作者签名：似呀签字蹶- 中年，月，p 臼 学位论文版权使用授权书 本学位论文作者完全了解鑫鲞盘鲎有关保留、使用学位论文的规定。 特授权鑫洼盘茎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名 编绛 u 导师签名：寻午棵丧 签字日期： p 妒年 r 月妒日签字日期： 。午年1 月c o 日 天津大学硕士学位论文 第一章绪论 1 1 背景和研究意义 第一章绪论 随着计算机技术的普及和进步，计算机辅助设计与制造技术( c a d c a m ) 也 得到了迅猛的发展，自由曲面造型技术在现代工业产品的设计和制造中有着广泛 的应用。然而在许多情况下，产品制造的流程是先产生产品模型和实物模型，而 后构建产品的c a d 模型，并为在原模型的基础上迸行优化，最后得到产品设计的 最终c a d 模型。这样，需要将这些样件和实物转化为c a d 模型。这种根据实物 模型和样件测量数据，建立数学模型，得到其设计思想，从而进一步修改原有设 计，然后将这些模型和表征用于产品分析、制造和加工。这种把实物转化为c a d 模型的技术称为反向工程或反求工程( r e v e r s e e n g i n e e r i n g 1 ， 2 】) 。随着数控 测量技术的发展，反向工程技术已被广泛应用于航空、航天、造船、汽车和模具 等现代制造业的各个领域。 现代先进制造技术的基础是产品模型，而产品模型又是脱胎于几何模型。所 以，研究产品的几何模型在先进制造技术中占有重要的地位。几何模型的用途一 种是由c a d 造型系统建立产品的几何模型，二是由已有的物理模型直接生成产品 的c a d 模型，即通过反向工程的途径建立产品的几何模型。反向工程，是近年来 才发展起来的一系列先进的分析方法的组合，其主要的目的是为了尽快的改善技 术水平，提高竞争力。反向工程具有广阔的应用范围，它是快速原形制造、快速 模具制造的重要组成部分，是产品快速开发的支柱，它在医学、工业仿制、航天、 军事、地形测绘、交通建筑、结构仿生和工艺美术等诸多方面都有巨大的应用前 景。在现在世界中，各国所发展的技术和产品大多数来自国外，尽快的从国外产 品中汲取经验，利用反向工程来消化吸收先进的技术经验能够极大的节约成本， 缩短产品的研发周期，所以研究反向工程技术，对国民经济的发展和科学技术水 平的提高很有帮助。 天津大学硕十学位论文 第一章绪论 1 2 反向工程综述 反向工程技术是随着计算机技术的发展和成熟以及数据测量技术的进步而 迅速发展起来的一门新兴学科与技术。它的出现，改变了原来c a d 系统中从图 纸到实物的设计模式，为产品的快速丌发以及快速原型化设计提供了一条新的途 径。 反向工程技术在许多工业领域中有着广泛的应用。例如在仿造设计中，需要 克隆某个产品，然而通常却没有该产品的原始设计草案或文档；又如在零件的修 改与改良设计中，需要从现存的产品出发，构造出他的几何模型，从而可以利用 现有的c a d 系统进行进一步的分析与优化，从而开发出新的产品；在汽车工业 等领域，车体外壳的美学设计显得尤其重要，对于众多设计师而言，他们更喜欢 的是在真实的雕刻或油泥模型上进行设计，实物模型相对于计算机二维屏幕而言 更能真实的反映物体的形状，更有利于设计师阐释他的设计思想；另外，在特制 的服装、鞋帽等产品定制领域，由于每个人的面部，身体结构不同，统一的尺码 并不一定适合客户的要求，又由于批量小，甚至可能就只生产一件产品，用传统 的设计方法，冗长费时，在经济上来说也是不合适的。 传统的产品开发流程是种预定的顺序模式，即从市场需求出发，抽象出 产品的功能描述，然后进行概念设计，在此基础上进行总体设计和详细的零部件 设计，制定工艺流程，设计工具央具，完成加工及装配，通过检验及性能测试， 这种开发模式的前提是已经完成了产品的蓝图设计或c a d 模型。而反向工程技 术则是从一存在物理或实物模型，通过对它进行数据采集，三维重建，从而得到 它的几何模型和设计思想的过程。所谓反向实际上是相对于传统的c a d c a m 系统工作流程而言的。 天泮人学硕士学位论文第一章绪论 臣兰h ! 兰 反向工程设计过程 图1 1 反向t 程与传统设计工程流程差别 反向工程中的两个主要方向：数字化技术和三维重建技术。 1 2 1 数字化技术 反向工程的首要任务是采集包含实物几何特征的三维坐标信息，只有获得了 这些信息，才能实现复杂曲面的建模。因而，近十几年来人们开发了多种的数据 采集系统，以实现对实物三维信息的高效、高精度的采集。数字化技术就是利用 测量装置采集实物三维数据，根据采集工具的采集方式可分为接触式和非接触式 方法两大类，接触式主要包括基于力一变形原理的触发式和连续式数据采集，非 接触式主要基于光学原理进行数据采集，典型方法有激光三角法、激光测距法等 方法，其特点式测量装置不与样件接触，这两者各有优缺点前者因为与被测物体 接触所以速度较慢，而且不能测量软物体；而后者速度较快，能够测量软物体， 但是精度比前者差。另外基于激光扫描设备不能采集具有复杂内部结构的材质的 特点，人们发展了工业c t 和断层扫描仪，它不损伤实物，但是测量精度较低，成 本较高。 近十年来，随着激光扫描设备的发展，包含被测物体更多细节的海量数据获 耿成为可能，并且成为高精细测量建模的发展方向。但对于形状相对复杂的物体， 如具有孔洞、内腔、手柄等构型特点时，一次测量并不能保证数据的完整性。通 常需要对物体进行多次测量，并对测量点集进行合并，因而并不能保证整个点集 的拓扑构型。另外，在某些三维重建的应用中，数据来源于c t 扫描，数据是分 天津大学硕士学位论文 第一章绪论 层组织的。由于数据来源的不同造成数据组织形式的不一致，多数三维重建算法 都是将数据点作为散乱点，提出了基于散乱数据点的三维重建方法。 根据采集设备的不同，采集的数据主要分为两种类型； 1 规则数据 规则数据主要来自于c t 断层扫描技术等实体信息采集技术，其特点是，保存 了被测物体表面和内部的信息。获得的采样数据的位置参数是有序的，均匀的， 采样点之间的相邻信息可以被利用。由于其测量中逐层扫描的特点，可以从获得 的图像中抽取一系列轮廓线，在有些三维重建算法中使用了这些特性。 2 散乱数据 散乱数据顾名思义，就是通过激光扫描技术等三维坐标采集技术获得的被测 物体的三维信息中，采样点之间的位最关系是不确定的，数据分布没有任何规律， 其测量点之间的相邻信息不可利用。 1 2 2 三维重建 三维重建就是从表示物体三维属性的采样数据集中构建出合理的三维自由 曲面。三维重建是反向工程中最重要的问题，也是当前反向工程研究中的热点。 三维重建是要为已存在的曲面建立模型。它有两个方面的含义。第一意味着已有 的曲面是三维重建的根据，可以根据需要在该曲面上采集各种数据以进行三维重 建；第二意味着已有曲面是衡量重建所得的曲面模型质量好坏的标准，要求建立 的模型能忠实地恢复已有曲面的形状。这两点正是三维重建与自由曲面表示的区 别所在。 根据重建曲面和采样点集之间的关系可将三维重建分为两大类：插值法和逼 近法。前者得到的重建曲面完全通过原始数据点，而后者则是用分片线性曲面或 其它形式的曲面来逼近原始数据点，从而使得得到的重建曲面是采样点集的一个 逼近。而根据重建曲面的表现形式不同又可以将它分为以下几种：参数重建、隐 式重建、变形重建、网格重建和细分重建。反向工程的最终目标是能够从原始物 体出发，自动地构造出该物体几何模型与设计思想，以便于运用现有的c a d 造 型工具对其进行再设计，或者利于快速成型机实现物体的快速仿制 3 。 1 参数重建 天津大学硕士学位论文 第一章绪沧 长期以来，参数衄线曲面一直是描述几何形状的主要工具，它起源于飞机、 船舶的外形放样工艺，由c o o n s 、b 6 z i e r 等大师于上世纪6 0 年代奠定其理论基 础。c o o n s 曲面、8 6 z i e r 曲面、n u r s s 曲面等不仅成为几何设计的主要工具， n u r b s 曲面已被作为工业产品数据交换的s t e p 标准，也作为描述工业产品几何 形状的唯一数学方法。 1 9 9 5 年b a d 给出了一种稠密、规则采样数据的三维重建方法 4 。它首先 构造一个c l 连续的分片代数曲面作为定义域曲面，计算出它的有向距离场函数， 利用得到该定义域曲面的分片线性逼近，并在此定义域曲面上重建出连续的 b e r n s t e i nb e z i e r 曲面片作为重建曲面。1 9 9 6 年e e k 等人提出了用b 样条曲 面对任意给定拓扑网格进行重建的方法 5 。同年，h a ls t e a d 等提出了利用b 样 条曲面构造高精度地逼近需要重建的曲面法向的方法。虽然该方法还不能重建有 尖点和棱角的曲面，但是它以b 样条为工具，为包括b e z i e r 在内的各种参数曲 面参与三维重建的工作开辟了道路。 1 9 9 7 年6 u o 提出了一种具有任意拓扑形状的参数三维重建方法 6 ，他首先 利用形构造出一简单曲面矿使之反映出原曲面的拓扑结构，然后在此基础上 重建出一曲率连续的参数曲面作为重建瞌面。 同年，l e e 等人在文 7 中给出了一种用多阶b 样条三维重建算法。它可以 对重建曲面进行多阶表示，以利于重建曲面的多分布率分析与表示。1 9 9 9 年y a n g 提出了一种基于边数据分割的二次参数三维重建方法 8 。它首先根据各点及其 邻域内各点的分布计算出该点的法向、曲率等微分信息，从而判断该点是否位于 曲面的边界上，对数据点集进行分割处理，最后对于每块数据分别用二次参数 曲面逼近。2 0 0 0 年p i e g l 和t i l l e t 在 9 中提出了用b 样条曲面逼近离散采样 点的方法。他们假设经过数掘预处理后，采样数据点是组具有矩形分布形式的 点鳊，i = l ，门，j = 1 ，m 从而可以构造出一张c ( - i q - o 连续的曲面作为 重建越面。f l o a t e r 在 1 0 中提出一种新的b 一样条曲面三维重建的方法。它通 过将原始数据点投影到平面参数域上进行参数化后，用b 一样条曲面对原始数据 点进行最小平方逼近，所得到的曲面就是重建曲面。作为描述几何形状的主要工 具，参数三维重建也是最常见的三维重建方法。 2 隐式重建 天洋大学硕士学位论文第一章绪论 在数学和计算科学中，通常也用隐式曲面来定义几何物体，不等式 f ( x ，y ，z ) 0 描述了空间中的半空间，等式f ( x ，y ，z ) = 0 可定义该半空间的边界， 这种曲面表示方法在几何造型和图形学中也得到了诸多的应用。参数化表示具有 许多优点，如计算曲线曲面的几何量简单，曲线曲面的显示方便，具有离散等优 良性质等。然而，在另外的一些几何操作，如判断一个点是否在曲线或曲面上以 及在哪一侧时，参数表示曲面极为不便，与之相反，隐式化表示给这些操作带来 了极大的方便，同时，隐式化表示在曲线曲面求交方面也有极其重要的应用。因 此，在三维重建中，也越来越多地使用曲线曲面地隐式化表示。 m u r a k i 在1 9 9 1 年进行的人头三维重建中，借助势函数的概念，提出用网 格隐式曲面作为工具进行三维重建的方法 1 1 。1 9 9 2 年，b a j a j 等给出了插值 给定网格的网格曲线片的构造方法 1 2 1 3 。1 9 9 5 年，s a p i d i s 等人在 1 4 中提出了一基于区域增长的多项式三维重建方法，用数目尽量少的具有 f ( x ，y ，z ) 表示形式的函数曲面片来逼近三维采样数据点。z b a o 等人在 1 5 一文 中提出了一类基于极小曲面模型( m i n i m a l s u r f a c e l i k em o d e ) 和p d e ( p a r t i a l d i f f e r e n t i a le q u a t i o n ) 方法的隐式三维重建方法。以原始数据点集的距离场的 某等势面作为初始曲面，沿一给定的能量方程的梯度流方向连续变化，最终得到 的曲面就是重建曲面。2 0 0 1 年，c a r r 等人在 1 6 一文中提出了用多项式径向基 函数( r b f ，r a d i a lb a s i sf u n c t i o n ) 重建曲面的方法。z h o u 等人提出了一种用带 指数函数的超二次曲面进行三维重建的方法 1 7 。 3 变形重建 许多复杂曲面都是由多张曲面拼接构成，无法用一张参数曲面或隐式曲面的 将其重建出来，也有的曲面形状特别奇特，用参数曲面或隐式l 虫面来表示则显得 格外复杂，近年来有人提出了一种变形三维重建技术，这种方法先定义一封闭曲 面，然后对其进行变形，使其逐步与数据集吻合，即在内力( 各种平滑条件、曲 率约束) 、外力( 数据分布) 作用下，使能量达到最小。先将种小模型放入需 要重建的闭曲面内部，然后让其膨胀变形，同时以要重建的曲面上的采样点作为 对膨胀变形的约束条件。当几何模型的变形达到某一平衡点时，就得到该曲面的 数学模型。也可以通过赋予曲面一定的物理属性，例如，质量、刚度等，曲面的 变形通过模拟曲面的受力情况来定义。曲面的物理属性和外力的综合作用，使得 天津大学硕十学位论文 第一章绪论 曲面最终变形为所求的重建曲面。 t u r k 在文 1 8 提出了一类利用二维物体隐式形变技术对切片数据进行三维 重建的方法。它的数据点来源于医学图像的c t 切片，通过建立各切片问的过渡 曲面来实现整张曲面的重建。b r e e n 将l e v e ls e t 方法引入三维重建当中，提 出了一类基于l e v e ls e t 模型的曲线重建方法 1 9 。 4 网格重建 由于计算机技术的发展，计算机的存储技术的进步，使得计算机能够处理更 多的数据。同时，许多c a d 造型系统和快速原型制造系统的数据输入输出也逐 步采用多边形表示模型，以d f x 和s t l 格式文件来进行，另一方面，网格曲面 也更加有利于曲面的计算机显示。因此，在三维重建中，越来越多的人提出了网 格曲面方法。网格曲面由h o p p e 于1 9 9 2 年在文 2 0 中提出。该文通过各采样点 的局部信息自动计算各点处的法向信息，用切平面线性逼近待重建曲面的局部模 型，建立离散点集的距离场函数，然后利用实现等值面抽取的m c ( m a r c h i n gc u b e ， 移动立方体) 算法得到它的三角面片逼近曲面，并以此曲面作为所需的重建曲面。 a m e n t a 等提出了一种基于v o r o n o i 图的网格三维重建算法 2 1 。它通过构造采 样点集的三维v o r o n o i 图，利用d e l a u n a y 三角化的方法来重建曲面。通过该方 法得到的重建曲面精确的通过每一个原始采样点。b r a d l e y 提出了一种依赖种子 点增长的网格三维重建算法 2 2 ，它从选定的种子点开始，通过候选点与当前网 格的可见关系来判断该点是否在网格上以及确定它的连接关系，最终获得一张或 多张网格曲面作为所求的重建曲面。f l o a t e r 提出了无网格参数化的三维重建算 法 2 3 ，它首先将原始数据点集投影到平面上，并运用平面d e l a u n e y 三角化的 方法将投影点集分割为一个个三角形，从而得到各点集的连接关系。最后根据投 影点集的连接关系确定各原始数据点间的拓扑连接，所得到的三角网格曲面即为 重建曲面。网格曲面作为一种曲面表示形式由于具有简单、统一的优点，已成为 一种重要的曲面表示方法。用网格曲面进行三维重建也得到了众多研究着的关 注。 5 细分重建 为了解决具有复杂拓扑形状的三维重建问题，人们提出并发展了细分重建方 法。细分曲面是类采用组成曲面的多边形网格的点、线、面及拓扑信息完整地 天泮大学硕士学位论文第一章绪论 描述地曲面。它从初始多面体网格开始，按照某种规则，递归地计算新网格上的 每个顶点，这些顶点都是原网格上相邻的几个顶点的加权平均。随着细分的不断 进行，控制网格被逐渐磨光，在一定的细分规则下，细分无穷多次之后多边形网 格将收敛到一张光滑曲面。细分曲面的最大优点就是算法简单，并且几乎可以描 述任意复杂的曲面，基于细分曲面的重建方法在特征动画设计和复杂的雕塑三维 重建中得到了高度的应用。h o p p e 等人在文 2 4 中提出了用细分曲面进行三维重 建的方法。该方法分为三个步骤，首先，构造一由大量三角面片构成的三角网格 作为原始点集的逼近，然后，对该三角网格进行优化，减少网格顶点，提高拟合 精度，最终，通过调整控制网格的顶点数目、位置与连接关系，从而得到最终的 重建曲面。该方法对于重建带有尖锐特征边以及具有任意拓扑形状的曲面可获得 满意的效果。由于计算机技术的进步和人们对细分曲面研究的进展，细分技术获 得了长足的进步，越来越多的研究者讨论了如何用细分曲面拟合或插值散乱点， 进行三维重建的问题。 1 3 反向工程的研究进展 基于反向工程快速，直接的特点，它在工业设计中的利用优势早已被人们发 现，而国内由于起步较晚，现在还处于研究阶段，理论基础较薄而且产品也不能 达到精度要求，有待于进一步的研究和开发。 早在6 0 年代，国外就已经起步进行这方面的研究，现在技术已发展得相当 成熟。九十年代以来，反向工程的需求和技术得到了美国、日本、欧洲各国等学 者的高度重视，国际著名刊物c o m p u t e ra i d e dd e s i g n 、c o m p u t e rg r a p h i c s 等 对反向工程研究的报道明显增多 反向工程中用于数据采集的坐标测量硬件设备发展十分迅速，基于机械接 触、光学观测、声学探测和磁学扫描的各种测量机现在基本上达到了商品化的程 度。尤其近年激光扫描仪和工业c t 技术的发展，使三维集合外形数据的自动采 集无论在效率上、精度一h 还是在价格上都可以被广泛接受。 基于测量数据的三维重建技术也获得了较大的发展，现在已经有了一些反向 天津人学硕士学位论文第一章绪论 工程的软件系统，比如说意大利d e a 为自己的坐标测量仪开发的的s u p f e r 系统， 德国c m m 厂家z e i s s 的h o l o s 系统，比利时的k r u t h 丌发的s h a p i d 系统，美国 i m a g e w a r e 公司的s u r f a c e 系统，英国d e l c a m 公司的c o p y c a d 等系统。还有许 多通用的c a d c a m 系统，如u g i i ，p r o e 等也增加了测量造型模块。在国内也有 浙江大学的和山东大学等学校开发的一些造型系统。 近年来，反向工程方面的研究和应用已有很大进展，但也存在不少有待进 步研究的问题。其中数据获取技术、快速成型技术的发展已趋成熟，但通过测量 数据建构实物数学模型技术相对滞后，从而严重影响着反向工程的实用化程度。 因此反向工程领域今后的研究侧重于三维重建技术方面。以下问题将仍是反向工 程中值得研究的方面： 高质量、高速度的三维重建和显示技术的研究； 模型的简化及多分辨率显示； 模型精度优化与表面光顺； 1 4 论文工作 本文研究了基于计算机辅助设计的反向工程，在研究吸收了国内外相关资料 的基础上，进行了对反向工程三维模型重建的讨论，主要着眼点在三维模型的建 立和简化上。主要工作分为三个部分： 第一部分讨论了反向工程的基本内容，重点指出了反向工程的核心技术是数 据采集，三维模型重建和模型简化三个方面。从而引出对三维模型重建方法和模 型简化方法的讨论。 第二部分分为两章，针对反向工程中采样数据的不同讨论了两种经典的模型 重建方法。 对于使用断层扫描等方法获得的规则采样数据集，讨论了传统的等值面抽取 算法m c ( m a r c h i n gc u b e s ) 算法。为了提高等值面抽取的速度，减少冗余计算 和对于数据网格点的冗余访问，探讨了基于八叉树划分区块的加速方法和基于等 值面区域增长的加速方法。 基于通常获得的采集数掘都是散乱数据这个事实，讨论了基于径向基函数 的隐式三维重建技术。 天津大学硕十学位论文 第一章绪论 第三部分，针对当前的反向工程中获得的多边形网格模型规模巨大，不方便 显示和操作的缺点，我们重点研究了重建后的网格模型的简化。在一种传统的累 进网格简化算法的基础上引入新的简化代价计算方法，同时引入特征权值，在保 证模型的简化效果的同时加速简化的速度。从试验结果看出，改进算法在对模型 进行高度简化后仍然能够较好的反映原模型的几何特征，同时加快了简化的速 度，试验证明了方法的有效性。 最后我们对做过的工作进行了总结，对未来的研究指明了方向。 天津人学硕士学位论文 第二章规则数据的重建方法 第二章规则数据的重建方法 通过平面断层扫描或者逐层照相方式采集得到的数据的是一个规则的三维 数据集。对于这种规则的三维数据集的三维重建方法被称为等值面提取。其方法 是在提取的区域中，根据给定阈值，构建出需要的等值面。因为不同的物质具有 不同的物理属性，因此可以选定适当的值来定义等值面，该等值面表示不同物质 的交界。也就是说，一个适当值定义的等值面可以代表某种物质的表面。 m a r c h i n gc u b e s 算法( 简称m c 算法) 是三维规则数据集等值面生成的经典算 法，科学计算可视化的很多工作都以该算法为基础完成，并且有大量研究工作对 m c 算法本身进行了有效的探讨，来对该算法进行完善和提高它的运算效率。 m c 算法不仅仅是可视化领域的经典算法，也在其它图形学的其它领域中广为应用， 因而也是图形学的基础算法之一。 在本章中，首先简要介绍等值面的定义，讨论m c 算法原理及实现方法，然 后分析m c 算法在连接方式上二义性的产生和消除，及m c 算法的加速改进。 2 1m c 算法的基本原理 m c 算法脱胎于立方块法( c u b e r i l l e ) ，它是用边界体素的六个面拟合等值面， 即把边界体素中相互重合的面去掉，只把不重合的面连接起来近似表示等值面 2 5 。这种方法的特点是算法简单易行，便于并行处理，该方法的主要问题是出 现严重的走样，显示图象给人一种“块状”感觉，尤其在物体边界处锯齿形走样 特别醒目。l o r e n s e n 等人于1 9 8 7 年提出的移动立方体法( m a r c h i n gc u b e s ) 2 6 ，修正类立方体法的缺陷，是最有影响的等值面构造方法，一直沿用至今。 它假定原始数据是规则的三维空间数据，c t 断层图像属于这一类数据。 最初的m c 算法不能保证三角面片所构成的等值面的拓扑一致性，会造成等 值面上出现空洞。m j d u r s t 首先提出了m c 算法中的二义性 2 7 ，后来许多人 在l o r e n s e n 方法的基础上做了许多改进。 2 1 1 基本概念 1 体元 查堂叁堂堡主堂垡笙茎 笙三至塑型塑塑竺至鍪苎堕 在三维空间的菜个区域内进行采样，若采样点在z y x 三个方向上的分布 是均匀的，采样恻距分别为呔，缈，a z ，则可以用三维数字矩阵来表示一个空间 中的体数据，表示为f ( i ，工七) 。每八个相邻的采样点所定义的立方体区域就构成 了个体元，而这八个采样点称为该体元的角点，它们的坐标分别为 ( f ，j ，后) ，( j + 1 ，) ，( i ，j + l ，后) ，( f ，j ，七+ 1 ) ， ( f + 1 ，f 十l ，盂x ( f + 1 ，j ，k + 1 ) ，( 1 ，+ 1 ，k + 1 ) ，( + 1 ，+ 1 ，k 十1 ) 对于体元内的任一点，其值只能从体元的八个角点的采样值来估算。常用线 性插值方法来实现。如同公式2 1 所述。( 式中a ，a ，为常数) f ( x ，y ，= ) = a o + a i x + a 2 y + a 3 z + a 4 妙+ 口5 弦+ a 6 蟊+ a 7 x y z ( 2 1 ) 2 等值面 等值面是空间中具有某个相同值的所有点的集合。公式表示如公式2 2 所 玎i ： ( 五y ，2 ) f f ( x ，弘z ) = c ，c 为常数 ( 2 2 ) 3 边界体元 当体元的八个角点都大于c 或者都小于c 时，其内不存在等值面。只有那些 既有大于c 的角点又有小于c 的角点的体元才含有等值面，我们称这样的体元为 边界体元。 等值面在一个边界体元内的部分称该体元内的等值面片。等值面与边界体元 面的交线是一条双曲线且这条双曲线仅由该面上的四个角点决定。这些等值面片 可以构成连续的无孔的曲面。因为对于任何两个共面的边界体元，如果等值面与 它们的公共面有交线，则该交线就是这两个边界体元中等值面片与公共面的交 线，也就是说这两个等值面片完全吻合。所以，可以认为等值面是由许多个等值 面片组成的连续曲面。 由于等值面是三次代数曲面，构造等值面的计算复杂，也不便于显示，而多 边形的显示则非常方便，所以，等值面的三角面片拟合是常用的手段。我们本章 论述的m c 算法就是是在边界体元中生成三角面片，以三角面片逼近等值面。 2 1 2 m c 算法 m c 算法的基本思想是把三维图象相邻层上的各四个象素组成立方体的八个顶 点，逐个处理三维图象中的立方体，分类出与等值面相交的立方体，采用插值计 算出等值面与立方体边的交点。根据立方体每一顶点与等值面的相对位置，将等 值面与立方体的边的交点按一定方式连接生成等值面，作为等值面在该立方体内 的个逼近表示。 天沣人学硕士学位论文 第二章规则数据的重建方法 假设沿着体元的棱边采样数据为线性变化。也就是说，如果一条棱边的两个 顶点的采样数据值分别大于和小于等值面的值，则该条边上有且仅有一点是等值 面与该边的交点。确定等值面在体元内的分布是该算法的基础。 2 ，1 2 1 等值面与体元的相交方式 对体元的8 个顶判定该顶点是位于等值面内还是等值面外。再根据8 个顶点 的状态，确定等值面在体元内部的连接方式。 假定等值面的值为c 。则顶点分类规则为 1 如果体元顶点的数据值大于等于c ，则定义该顶点位于等值面之外，标记 + 号： 2 如果体元顶点的数据值小于c ，则定义该顶点位于等值面之内，标记号 如图2 1 所示： 幽2 1 顶点标记 由于每一体元共有8 个顶点，每个顶点有2 种状态，因此共有2 5 6 种绍 合状态。但是体元有下述两种对称性： 1 顶点状态互换，此时三角面片的拓扑结构不变。也就是说，大于等值面顶点 和小于等值面的顶点是可以相互替换的，根据互补对称性，即体元的顶点标记置 反( o 变为l ，1 变为0 ) ，不影响该体元内三角面片的拓扑结构，这样2 5 6 种构 型可以简化成1 2 8 种。 图2 2 顶点互换 2 旋转相似性，经过多种旋转，有许多状态是一致的，根据旋转列称性，可将 - 1 3 一 天津大学硕士学位论文 第二章规则数据的重建方法 这1 2 8 种组合进一步简化成1 5 种。 图2 3 旋转相似性 每一个体元可以按以下索引值进行索引： i n d e x = v ov 1v 2v 3v 4v 5v 6v 7 其中v i ( i - 0 ，1 ，7 ) ，是体元的8 个顶点的状态值( 标号为+ 状态值为1 ， 标号为一状态值为o ) ，根据该值对应到其经过经过旋转、互换后的连接方式上 去，获得等值面的逼近面片的形状。 2 1 2 2 等值面与体元交点 图2 4 体元的1 5 种等值面连接 在确定等值面的连接方式后，就要计算三角面片顶点位置。根据m c 算法的基 本假设，当三维离散数据集的密度较高时，即当体元很小时，可以假定函数值沿 体元边界呈线性变化，可以直接用线性插值计算等值面与体元棱边的交点。对于 天津大学硕十学位论文 第二章规则数据的重建方法 某条棱边，如果它的两个端点”1 ，”z 标记不同，那么等值面一定与该边相交。 以点( i ，j ，) 和( f + l ，j ，k ) 这两点的连线为例，交点( x ，j ，k ) 的坐标由下式可得： x = i + 【c f ( v ，) 】 厂( v z ) 一f ( v ，) f 23 、 在其它的情况下方法类似。求出了等值面与体元棱边的交点后，根据索引表 确定交点的连接方式，得到该体元内的等值面的拟合三角面片。 2 1 2 3 三角面片的法向计算 为了利用图形硬件显示等值面图象，必须给出形成等值面的各三角面片的法 向，选择适当的光照模型进行光照计算，生成真实感图形。对于等值面上的每一 点，其沿等值面的切线方向的梯度分量应该是零，该点的梯度矢量的方向也就代 表了等值面在该点的法向。 g ( x ，y ，2 ) = v f 0 ，y ，= )( 2 4 ) 直接计算三角面片的法向是费时的。而且，为了消除各三角面片之间明暗度 的不连续变化，在m c 算法中，只要给出三角面片各顶点处的法向并采用p h o n g 或 者g o u r a u d 光照模型绘制各三角面片就行了。 体元各角点处的梯度可以采用中心差分计算，然后再一次通过体元棱边两个 端点处梯度的线性插值求出三角面片各顶点的梯度，也就是各项点处的法向，从 而实现等值面的绘制。体元角点的中心差分公式如下： g ：f ( x i + l yf ，z k 一f ( x i - iyf ，z g j ：地，y j + l ，z k 一f ( x i y - 、，z 。：厂( t ，y j ，z k + 1 ) 一厂( z ，y j ，卸一 其中越，n 止为体元的边长。 2 1 2 4m c 算法抽取等值面的算法流程 佗5 1 m c 算法求等值面的步骤： 1 将三维离散规则数据集分层读入； 2 扫描两层数据，逐个构造体元： 3 将体元每个顶点的函数值与给定的等值面值c 做比较，根据比较结果 确定体元内等值面的形状； 4 计算出体元棱边与等值面的交点，求出三角面片各顶点处的法向； 勉勉 天津火学硕士学位论文 第二章规则数据的重建方法 5 根据各三角面片各顶点的坐标及法向量绘制等值面。 2 2m c 算法存在的二义性问题及其解决方法 m c 方法存在着连接上的二义性问题。在该方法提出来不久后，由m j d u r s t 提出来了。在m c 算法中，如果在体元的一个面上，如果标号为+ 和标号为一的 角点分别位于对角线的两端，那么就会有两种可能的解释方式，因而存在着二义 性，这样的面称为二义性面，包含至少1 个二义性面的体元为具有二义性的体元， 其等值面连接方式存在着二义性。如果这个问题不解决，就会引起最后生成的等 值面可能出现拓扑不一致，出现空洞，从而不能保证曲面的封闭性。 膂溜豫馐颦睦黪 ( a ) 二维情况f 的二义性( b ) 三维情况下的二义性 幽2 5 等值面连接二义性 有很多种方法来解决m c 算法中存在的连接二义性： 1 将体元划分为四面体的组合，彻底消除了二义性闷题。但是该方法 生成更多的三角形，并且要选择切分四面体时的切分方向，并可能 导致等值面的跳跃 2 8 1 。 2 用渐近线方法判别和消除二义性。由于假定规则数据体元棱边呈线 性变化，等值面与体元的一个边界面所在平面的交线是双曲线。可 以插值出出双曲线的两条渐近线的交点的数据值，并按照它与等值 面函数值c 的关系标以+ 号或一号。则它应与标有相同符号的角点 落在同一区域，凭此就可以唯一确定等值面的连接方式。 团圈 图2 6 交点之间的连接准则 天泮大学硕士学位论文第二章规则数据的重建方法 3 增加互补情况时的连接方法 2 8 】。这是一种简单有效的解决方法，在 原来的1 5 种连接方式增加了6 种连接方式，这些连接方式用来与相邻 体元进行正确连接，不会在等值面上产生空洞。 2 3 减少冗余访问 由于m c 需要检测所有的体元，而在大多数情况下有效体元( 即与等值面相 交的体元) 所占的西分比是很少的，少于1 0 左右。算法执行中3 0 至7 0 的 时间花在空体元的检测上，因此m c 的加速改进关键在于减少对空体元的检测。 下面介绍两类m c 的加速算法：基于八叉树的加速算法和等值面跟踪技术 2 9 。 2 3 1 使用八叉树分块减少空体元访问 从采用合适的空涮数据结构及其搜索算法的角度出发，在规则采样数据集中 最常见的结构是长方体，空间八叉树 3 0 1 比较适合于这种数据结构。 八叉树是一种空间分割的层次数据结构，可以看成是四叉树在三维空蒯的一 种扩展，空间被递归地分成8 个单元，其根表示了整个物体，8 个单元用o 一7 表示，写成8 进制是z y x 形式，即o o o 一1 1 1 ，分割是在每一个方向上进行等分。 八叉树的表示是一个较活跃的研究方向，为了节省存储空间，学者们提出过 不少压缩方法，线性八叉树是较好的表示，它改进了使用指针的表示方法，每一 结点被赋以一个下标键表示从根到该结点的一条路径，边界体元上的外部结点不 分配任何空间，内部节点的键值保存在一个排过序的数组中。 为了加快遍历，尽量较少与等值面无交点的体元的检测，在每一结点上，除 了保存它的儿子的信息外，还保留了两个值：其中包括的采样数据集的最大和最 小值。这样，在遍历时如该结点的最大值小于等值面的值，或最小值大于等值面 的值，则其所有子结点中都不包含等值面，也就无需再遍历其子结点，可直接转 到其兄弟结点再检测。这样大大加快了m c 算法的遍历过程。 天津大学硕十学位论文 第二二章枷m u 数据的重建方法 2 3 2 基于区域增长的边界体元搜索 在上一节中，我们知道要提高m c 方法的可以使用八叉树对数据集进行分块 减少对冗余的体元进行防问。这里介绍另一类方法，这种方法利用曲面的封闭性 和m c 算法巾相邻体元的性质来达到每次遍历到非空体元上。 考虑到曲面的封闭性，可以利用某个与等值面相交的边界体元作为种子，来 对整个等值面进行跟踪，它们的相邻体元中是否有等值面与它们相交可咀根掘曲 面的封闭性来推知。每一个体元自上下前后左右六个面，也就有相应的六个相邻 的体兀，在这六个面中，与存在交线的面相邻的体元中爿可能存在等值而，从而 确定某个体元是否是非空的体元，减少对空体元的遍历如果用一个字节来表示一 个体元的相邻体元的遍历情况，一个方向的相邻体元用一位来表示，l 表示该方 向的相邻体元是边界体元，0 则表示该方向