（航空宇航制造工程专业论文）逆向工程中基于散乱数据点的曲面重构方法研究.pdf

南京航空航天大学硕士学位论文 摘要 逆向工程已成为当今c a d c a m 领域内研究的热点之一。曲面重构是逆向工程 的关键部分，它在机械产品测量造型、计算机视觉、根据切片数据的医学图象重建 等领域有重要应用。本文对基于散乱数据点的曲面重构技术进行了研究，主要工作 如下： 研究了抽取等值面的步进立方体( m c ) 算法，解决了算法中出现的二义性问 题。 提出了一种基于散乱数据点的曲面重构算法。该算法以物体表面上不附加任 何几何和拓扑信息( 包括边界信息) 的散乱数据点集为处理对象，自动生成 物体表面的三角化网格模型。 给出了曲面重构算法的数据结构、具体实现步骤，并在a c i s 平台上采用 v c + + 6 0 加以实现。 提出了一种对大量密集数据点集进行空间划分的算法，提高了海量数据的处 理效率。 关键词：逆向工程曲面重构几何建模 逆向工程中基于散乱数据点的曲面重构方法的研究 a b s t r a c t r e v e r s e e n g i n e e r i n gh a sb e c o m ea f o c u si nc a d c a mr e s e a r c hf i e l d a sac r i t i c a l p a r to fr e v e r s ee 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 ni so fg r e a ti m p o r t a n c ei nav a r i e t yo f s i t u a t i o n ss u c ha sr e v e r s ee n g i n e e n n gf o ram e c h a n i c a lp r o d u c t ，c o m p u t e rv i s i o na n d r e c o v e r yo fb i o l o g i c a ls h a p e sf r o mt w o - d i m e n s i o n a lc o n t o u r s ，s u r f a c er e c o n s t r u c t i o no f s c a t t e r e dp o i n t sh a sb e e nd e e p l yi n v e s t i g a t e di nt h i st h e s i s t h ef o l l o w i n ga r et h ep r i m a r y c o n t e n t s ： o nt h eb a s i so fs t u d i e so ft h em a r c h i n gc u b e s a l g o r i t h mi nd e t a i l s t h ea m b i g u i t y p r o b l e m i ss o l v e d t h et h e s i s p r e s e n t s a l l a l g o r i t h m t o a u t o m a t i c a l l y r e c o n s t r u c t t r i a n g u l a r r e p r e s e n t a t i o no fs u r f a c ef r o ms c a t t e r e dp o i n t s t h es o u r c ed a t as h o u l di n c l u d e n e i t h e rt o p o l o g yn o r g e o m e t r yi n f o r m a t i o no f t h es u r f a c et ob er e c o n s t r u c t e d t h et h e s i s p r o v i d e s t h ed a t as t r u c t u r ea n de n t i r e p r o c e d u r e o ft h es u r f a c e r e c o n s t r u c t i o na l o g r i t h m t h ea l o g r i t h mh a sb e e ni m p l e m e n t e dw i t hv c + + 6 0o n t h ep l a t f o r mo f a c i s t h es p a t i a l p a r t i t i o n i n g s c h e m ep u tf o r w a r di nt h et h e s i s g r e a t l yi m p r o v e st h e e f f i c i e n c yo f t h es u r f a c er e c o n s t r u c t i o na l o g r i t h m k e y w o r d s r e v e r s ee n g i n e e r i n gs u r f a c er e c o n s t r u c t i o n g e o m e t r i cm o d e l i n g i i 南京航空航天大学硕士学位论文 1 1 逆向工程及其应用 第一章绪论 逆向工程是指根据实物测量的数据重新构造实物的计算机模型，然后利用 c a d c a e c a m 等计算机辅助技术进行分析、再设计、数控编程等操作，而后进行 加工【1 】。逆向工程现已发展为c a d c a m 中一个相对独立的范畴。通过实物模型产 生c a d 模型，可以使产品设计充分利用c a d 技术的优势，并适应智能化、集成化 的产品设计制造过程中的信息交换。实施逆向工程可以充分发挥先进的测量设备的 优越性，使其既可作为c a d c a m 系统所需要的三维输入装置，又可作为c a d c a m 系统处理后的误差检测评估装置，从而提高工业产品的设计、制造自动化程度，缩 短产品的试制开发周期，降低生产成本。 大多数有关逆向工程问题的研究都集中在几何形状，即重建产品实物的c a d 模型方面口】。在这一意义下，逆向工程可定义为：逆向工程是与将实物转变为c a d 模型相关的数字化技术和几何模型重建技术的总称f 3 1 4 1 。 逆向工程是相对于传统的c a d c a m 技术而言的。传统的c a d c a m 的工作流 程为1 ) 概念设计，2 ) c a d 建模，3 ) 数控编程，4 ) 数控加工。在逆向工程中首先 有产品的样件，经过对产品的表面数据采集，得到产品的型面数据，然后对这些数 据进行处理，反求出产品的c a d 模型。图1 1 是逆向工程的工作原理简图。 介 田蓝 图1 - 1 逆向工程工作原理简图 逆向工程应用领域十分广泛。例如，模具制造商经常要根据客户提供的样件进 行模具设计，如果能够利用逆向工程技术，将使设计自动化程度大大提高。有时， 在没有样件图形文档的情况下，需要对样件进行有限元分析、备件加工等，或者需 要对样件进行修改，考察个性后的样件与其它零件间的装配协调性等等。 逆向工程中基于散乱数据点的曲面重构方法研究 逆向工程的另一类重要应用是对外形美学要求较高的零部件的设计。例如在汽 车工业，外形设计师仍然要制作全尺寸的木质或黏土模型，因为要在小小的计算机 屏幕上完成这样高要求的复杂外形设计是非常困难的。而当实物模型制作好后，就 需要输入到计算机辅助设计统中，以便进行后续的各种操作。 另外，逆向工程在产品定制生产中也可以发挥其独到的作用。例如，每一个人 体都是不同的，采用先进的扫描设备和先进的模型重建软件，可以快速建立人体的 数字化模型，从而可以设计制造诸如头盔、手柄、座椅、假肢、假发套、服装等产 品，并使这些产品完全适合每一个不同的客户。目前，这方面的研究和应用仍处于 初级阶段，但在当今这个追求完美与个性化的时代，可以预见此项研究将极具发展 前景。 除此之外，逆向工程在自然景物描述方面也有应用价值，如通过对大地遥测数 据的特征识别和建模，快速生成导弹目标的自适应跟踪轨迹等。 1 2 曲面重构技术的发展与应用【5 i 州i 1 几何模型是由几何信息和拓扑结构两部分组成，通常可分为线框( w i r e f r a m e ) 、 表面( s u r f a c e ) 和实体( s o l i d ) 三种模型形式。近年来，还发展了特征模型、产品 模型以及仿生模型等。 对于复杂曲面产品来说，表面模型是实体模型的一个重要组成部分，是实体模 型精确表示复杂曲面产品的基础。自由曲面是表面模型中的一种重要形式，它是描 述复杂型面的强有力的工具，是计算机辅助几何设计( c a g d ) 中最为活跃、最为 关键的分支之一，它随着c a d c a m 技术的发展而不断发展并日趋完善。 复杂曲面的c a d 模型重建是逆向工程模型重建研究的重点。对于复杂曲面产 品来说，其实体模型可由自由曲面模型经一定的计算演变而来。在建立其实体模型 之前必须先得到表面模型。因而，表面模型是复杂曲面产品逆向工程几何建模的重 点。由测量所得的三维表面数据获得产品表面模型的过程即为曲面重构。 曲面重构中三维表面数据获取是逆向工程中的一个关键部分。随着科学技术的 不断发展，测量技术也随着新的物理原理、新的技术成就的不断引入而获得长足发 展，光波干涉技术特别是激光技术的实用化使得测量精度提高了1 - 2 个数量级；数 字显示技术在测量上得到了充分的应用，提高了读数精度和可靠性；光电摄像技术 与计算技术的结合，使得对复杂零件的测量无论是精度上还是在效率上都得到了极 大的提高。曲面重构获取数据的方法很多，市场上主要有三类数字化点测量仪器。 1 激光测量仪 由激光扫描实物，同时由摄像机录下光束与实物接触部位。如果接触 南京航空航天大学硕士学位论文 部分为点状，称之为点激光测量仪，如果接触部分为线状，则称之为面 激光测量仪。 2 光学测量仪 由结构光源照射实物，利用干涉条纹技术测出实物的形状。 3 机械式测量仪 通过测量仪与实物的接触测出其形状。这类机械接触测量仪，以前都 用于仿形加工。 除此之外，还有声纳测量仪，g p s 测量仪等测量设备。机械接触测量技术已非 常成熟，但这种方法要求必须与实物接触，因而不适合柔软实物的测量，测量速度 也比较慢，另外还存在接触球半径补偿问题。激光与光学测量仪技术比较新，测量 效率高，但价格比较贵。 益面重构技术的主要难点在于：( 1 ) 数据量极大；( 2 ) 有时曲面数据点散乱， 不可能由数据点用常规方法直接构造；( 3 ) 所需构造的曲面极为复杂，由多张曲面 拼接而成。 就目前而言，常规的曲面重构手段是通过拟合型值点的方法生成零件的参数曲 面。尽管这种方法较容易实现，但在许多情况下并不适用。因为一般说来，拟合一 张曲面往往要经过所有的离散数据点，在数据点非常密集的情况下，计算量与占用 的内存空间都是相当大的。这是因为通常分片描述的参数曲面的曲面片的数量几乎 等同于型值点的数量。 1 3 论文选题依据及研究内容 近年来，逆向工程中涉及的硬件设备发展十分迅速，基于光学、声学、磁学和 机械接触的各种测量机现在基本达到了成熟的商品化程度。尤其是近些年激光扫描 仪的发展，使三维几何外形数据的自动采集无论是在效率上、精度上还是在价格上 都可以被广泛接受，而相应的软件却落后于硬件的发展。有关逆向工程的软件，如 美国的s u r f a c e r 、v e r i s u r f 、r e v e n g ，英国的d e s a u l t ，法国c i s i g r a p h 公司的s t r m l0 0 软件的d g m 程序包，英国d e l c a m 公司的d v c t 5 系统的d v c t d i g i t i z e 模块等， 目前在功能覆盖域、自动化程度、稳定性、可靠性、与其它c a d 系统的兼容性等方 面还不够成熟，不同程度地存在各种各样的问题。正如逆向工程研究权威t a m a s v h r a d y t “1 指出的那样：“跟扫描仪配套提供的软件功能十分有限，这些简单的软件包 只允许对测量数据进行简单的操作，而且一次只能用用户交互选择的数据集拟合一 张简单曲面。即使是目前最好的商品化软件所能构造的完整模型也仅限于三角化模 型或很少见到的一点非常简单的边界模型。” 逆向工程技术在我国也有定的研究和应用。成都飞机工业公司汽车模具中心 逆向工程中基于散乱数据点的曲面重构方法研究 于1 9 8 8 年用逆向工程制造出依维柯汽车主模型，该中心1 9 9 0 年与北京工业大学 c a d c a m 中心合作开发了通过实物测量加工凸凹模的软件r e s u r f 。长春第一汽 车制造厂也利用逆向工程技术进行新车型的研制。另外，中国航空精密仪器研究所、 浙江大学等单位也对逆向工程技术进行了研究，在一些特定的应用中取得了较好的 成果。但由于受到当时测量设备硬件发展水平的限制，而且计算机辅助几何设计、 计算机图形学等学科也还没有发展到今天的水平，因而这些研究和应用的范围受到 了一定的限制。随着测量设备的发展，包含被测物体更多细节的海量数据获取成为 可能，并且成为高精细测量建模的发展方向。 本文研究课题来源于国家8 6 3 高科技发展计划自动化领域基础研究项目“逆向 工程中曲面自动重建的多元解决策略”。本课题对基于散乱数据点的曲面重构技术进 行了研究，提出了一种基于散乱数据点的曲面重构算法，实现了散乱数据点的三角 网格模型重构，并在国际著名的几何开发平台a c i s 上用v c + + 6 0 语言加以实现。 本文还提出了一个对大量密集点集进行空间划分的算法，给出了相应的数据结构， 提高了海量数据的处理效率。 本文主要研究内容如下： 第一章是绪论，综述逆向工程及应用以及曲面重构相关技术，并据此引出本文 的选题依据及研究内容。 第二章给出了基于散乱数据点的曲面重构算法的基本思想，重点研究了三角网 格模型输出的步进立方体算法( m c 算法) 。 第三章详细研究了基于散乱数据点的三角网格模型重建问题，给出了算法实现 的具体步骤，并提出了一种对海量数据进行空间划分的算法，从而大大提高了数据 的处理效率。 第四章给出衄面重构算法的软件实现方法。 第五章是对本文工作的总结以及对后续工作的一些展望。 4 南京航空航天大学硕士学位论文 第二章基于散乱数据点的曲面重构技术 曲面重构是逆向工程中最关键的部分1 。它所要解决的问题就是：给定一组散 乱数据点x ，这些点位于未知的曲面u 上，要求一个新曲面s ，能最好地逼近原曲 面u t l ”。 曲面重构技术应用十分广泛，主要体现在以下几个方面： 逆向工程：许多企业都有很多过去的零部件，这些零部件往往不是用计算机设 计出来的，甚至没有设计图纸。当需要再利用这些零部件时，应用逆向工程技术可 以很方便的将这些零件输入计算机进行再设计等。另外，在进行一些对外形美学要 求较高的零部件的设计时，例如汽车工业，外形设计师仍然要制作全尺寸的木质或 黏土模型，因为要在小小的计算机屏幕上完成这样高要求的复杂外形设计是非常困 难的。而当实物模型制作好后，就需要应用逆向工程技术输入到计算机辅助设计统 中，以便进行后续的各种操作。 三维传真：国外的科技人员提出了一种三维传真的新概念i ”j 。他们将曲面重构 技术与快速原型技术( r p t ) 结合在一起，使得一个三维物体能够方便、可靠地被 “读入”、“传输”，并在另一个地方重新生成。 医用图像处理：在药理研究中，一般的做法是用切片机将病理样本切成薄片， 得到每一层薄片的轮廓信息，再由轮廓信息得到样本的整体形状。另外，在超声波 检测、c t 检测中也存在由散乱数据重构轮廓形状的问题。 除此之外，曲面重构在计算机图形学、电影、三维动画制作等方面也有应用价 值。正是由于曲面重构技术具有广泛的应用前景，同时也具有相当的难度和复杂性， 对这一问题的研究得到了国内外学者的高度重视。九十年代以来，国外许多著名刊 物，如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 、i e e ep a m i 等对逆向工程曲面 重构技术的报道明显增多。 b g u o i ”】、c l b a j a j t ”3 首先用三维q 一形建立结构的拓扑关系，再建立多面体逼 近模型，但是三维。一形的计算复杂性高，对于n 个点的数据集为o ( , 2 ) ，而且 不易做简化处理。c h e n ”1 直接判定三点形成的三角形的最小内角，应用最小内角最 大原则建立测量点的三角化模型。这种方法首先要将三维数据点投影到二维平面 上，然后再进行判定。这导致对封闭表面或近似封闭的表面处理困难，而且对大量 的密集点集，也存在效率问题。p g u t “j 提出利用神经网络的学习机制重建自由曲面， 但还限于较为简单的应用。另外一类基于散乱点的曲面重建采用变形曲面的方法， 如d r u p r e c h te ”i 、a w i t k i n t ”】提出的方法。变形曲面方法通常要赋予曲面一定的物 逆向工程中基于散乱数据点的曲面重构方法研究 理属性，例如，质量、刚度等，变形通过模拟一定外力作用来定义，但物理属性和 外力大小是较难给定的，而且变形方法一般要事先给定物体的拓扑结构，如球形拓 扑、盘形拓扑等。 b o l l e 和v e m u r i t ”l ，b r i n k l e y 【2 “，s c h m i t t 等【2 1 1 ，黄雪梅等f 2 2 l 采用的是参数表示法。 该方法将三维数据映射n - - 维参数域上，在二维上进行曲面重构，然后将重构结果 映射回三维空间。这种方法只能处理具有简单拓扑形状的数据，如平面，球面，柱 面等。但实际应用中的数据往往都具有较为复杂的拓扑形状，对于这种复杂数据， 参数表示法就受到了限制。 s c l a r o f f 和p e n t l a n d 【”l ，b a r n h i l l 等 2 4 】，n i e l s o n 等叫1 提出了函数拟合法。该方法 对任意点集x ，试图找到函数f ，使得f ( x 。，y ；) 一z ，。同参数法一样，函数拟合法 也只能处理拓扑形状较为简单的数据。 p r a t t 【2 6 】，h o p p e ”1 提出了隐函数表示法。该方法设法找到未知曲面的隐函数表示， 再通过m a r c h i n gc u b e s t 2 7 l 算法得到网格模型。由于该方法对初始数据无特殊要求， 也无须其他附加信息，且可处理具有较为复杂拓扑形状的数据，因而得到了越来越 广泛地应用。 此外，m i l l “2 8 l 提出了一种利用法式附加信息进行曲面重构的算法。柯映林f 9 l 、 c h e n t ”l 应用最小角最大原则建立散乱点的网格模型。但对于大量数据存在效率问题。 潘志庚【2 9 1 提出了一种基于图的三角剖分算法。 作者在研究了国内外的文献后，在h o p p e t ”1 等人工作的基础上，提出了一种由 散乱点集重构三角网格模型的算法。同以上算法相比，本文提出的算法具有以下的 优点： ( 1 ) ：对于每一个点来说，仅仅需要其空间坐标( x ，y ，z ) ，而不需要其它附加 信息，如法矢等。 ( 2 ) ：待重构的模型可以具有复杂的拓扑形状。 ( 3 ) ：不必输入待重构的模型的拓扑形状。 。 本文算法的基本思想是：给定一组空间散乱数据点x ( x ，x ：，x 。) ，对于 每一个点x ，找出一个切平面，并以此切平面代替x 附近的真实曲面，最后用步进 立方体m a r c h i n gc u b e s 法输出三角网格模型。算法步骤如下： ( t ) ：建立点集的拓扑关系 ( 2 ) ：切平面的生成 ( 3 ) ：切平面方向的调整 ( 4 ) ：有向距离函数的推导 ( 4 ) ：三角网格生成 南京航空航天大学硕士学位论文 2 2 曲面重构算法描述 2 2 1 相关定义 定义2 1 ：设u 为待重构曲面，给定一组空间散乱数据点集x ( x ，k ) ， 这些散乱数据点可以用下式表示： x 3y ，+ e ( 2 - 1 ) 其中： y 。是曲面u 上的点；e 。是误差向量； 如果对于所有的i ，都有j | e 。f l 6 ，则称点集x 是6 一误差的。如果以曲面u 上 的任意一点o 为圆心，p 为半径作球，至少有一个y ，在此球内，则称点集x 是p 一 密度的。 定义2 2 ：给定r “中一个点；和一组点y ，y = 瓦，i ，瓦) ，则；到y 的距 离为： d ( x ，j ，) 2 孵d ( x ，y )( 2 2 ) y ， 、一一 其中：d ( x ，y ) 为点x 到y 的欧氏距离。 定义2 3 ：给定r n 中两组点x = i ，i ，i ) ，y = 瓦，页，巧 ，则x 到 y 的单向h a u s d o r f f 距离定义为： d e ( 爿，y ) - s u p d ( x ，y ) ( 2 3 ) j 一般来讲，如( x ，】，) d z ( y ，) 。例如，考虑图2 - 1 的情况： e a 图2 - 1 单向h a u s d o r f f 距离 g c 逆向工程中基于散乱数据点的曲面重构方法研究 取x 为单位正方体a b c d e f g h 的顶点集，y 为四面体d a c h 的顶点集。则： d f ( x ，y ) = 4 2 ；d ( 】，) = o ； 定义2 4 ：给定r “中两组点x = 一x o ，i ，i ) ，y = 元，i ，z ，则x 到 y 的对称h a u s d o r f f 距离定义为： d h ( x ，r ) = m a x ( d e ( x ，y ) ，d f ( y ，j ) ) ( 2 4 ) 显然，d 。( x ，y ) = d 。( y ，工) 。 定义2 5 ：将切平面作为待重建曲面u 的局部线性逼近，可以构造空间一点p 到 m 的有符号距离函数) ( 2 5 ) ( p ) = ( p x ，) r 月。 其中x 。为所有测点中与p 最近的点，n 为相应的切平面法矢。 对于具有p 一密度和6 一噪声的测量点集x ，为了能够实现带边界曲面的重建， 本文参照文献 1 】的方法将式( 2 5 ) 表达为下面的形式 z p 一( ( p x 0 n 3 n ，计算p 点到最近切平面的投影z i f d ( z ，x ) p + 6 t h e n a v ) 一( p x ) 。n 。 e l s e a p ) 一u n d e f i n e 其中a ( z ，x ) 表示z 与测量点集x 中最近点间的距离。 2 2 2 算法基本思想 本算法首先在密集的散乱点集中寻找每一个测量点的k 一近邻( 即距离该点最近 的k 个邻近点) ，利用k 个邻近点近似算出待重建曲面在该测点处的法矢量，根据 测点及其法矢量就得到了重建曲面在该测点处的切平面。虽然还没有重建曲面的整 体形状信息，但可以用测点处的有向切平面作为重建曲面在各测点处的线性逼近。 由于用k 个邻近点算出的法矢量可以有正负两个方向，为了保证切平面方向的协调 一致( 指向曲面的同一侧) ，算法需要对法矢的方向做自动调整。法矢方向调整采用 如下方法：首先建立切平面法矢的最小生成树( m s t ) ，然后深度优先遍历该生成树， 法矢即可调整完毕。算法的下一步是建立空间点p 到重建曲面的有向距离函数f ( p ) ， 其中重建曲面是由各测点处的有向切平面来表示的，因而f ( p ) 是一个非连续的标量 场函数。最后，用等值面抽取的步迸立方体算法( m c ) 输出f ( p ) 的零集z ( f ) 。 r 南京航空航天大学硕士学位论文 算法步骤如下： ( 1 ) ：建立点集的拓扑关系 ( 1 ) ：切平面的生成 ( 2 ) ：切平面方向的调整 ( 3 ) ：距离函数的推导 ( 4 ) ：三角网格生成 2 3 曲面重构输出算法 曲面重构输出采用了步进立方体步进算法( m c ) ，由于该算法涉及内容较多 因此单独列出本小节阐述了m c 算法的基本原理及其存在的问题和改进方法。 2 - 3 1 步进立方体( m c ) 算法原理f 2 7 】 m c 算法是三维数据场等值面生成的经典算法，是体素单元内等值面抽取技术 的代表。在m c 算法中，体素是一逻辑上的立方体，由相邻层上的各四个象素组成 立方体上的八个顶点，如图2 2 所示。算法以扫描线方式逐个处理数据场中每一立 方体体素，求出每一体素内包含的等值面。 ( i 彳1 ，k + 1 ) ( i + i ，】+ 垆1 ) 象豪 乜。 图2 2 步进立方体 用m c 算法可分为两个基本步骤： 1 根据用户定义的数据来对等值面进行定位，并创建三角平面片： 2 计算每个三角平面片的每个顶点的法矢，以保证高质量地生成等值面图象。 m c 算法以一种分而治之的方法来计算每一个逻辑立方体中的等值面。 一三角平面片的生成 m c 算法首先确定所需生成的等值面如何与立方体相交。对于立方体的八个顶 逆向工程中基于散乱数据点的曲面重构方法研究 点来说，若某顶点的闽值大于等于该等值面的值，则将该顶点设置为1 ：否则设置 为0 。换言之，被设置为l 的顶点在曲面之外或在曲面之上，而被设置为0 的顶点 在曲面之内。根据以上假设，便可确定曲面与该立方体的拓扑关系，并进一步找出 二者的相交部分。 由于每个立方体有八个顶点，每个顶点有两种状态，因此等值面与立方体的 的相交方式共有2 8 = 2 5 6 种。通过枚举2 5 6 种方式，可以创建一张等值面与立方体相 交方式的索引表。通过这张索引表，便可以知道等值面与立方体中的每一条边是如 何相交的。 通过给全部2 5 6 种方式逐一列出其三角平面片表示来完成整个等值面的三角化 表示是可行的，但相当繁琐且容易出错。由分析可知立方体有两种对称性： 1 如顶点状态反转，等值三角平面片的拓扑结构不变，即，大于等值面的点与 小于等值面的点是可以互相替换的，如图2 。3 所示； 2 旋转对称性，经过适当旋转，有许多状态是一致的，如图2 4 所示。 画画 图2 3 互补性 研。画。屈 跹 图2 - 4 旋转对称性 南京航空航天大学硕士学位论文 利用以上两种对称性可将2 5 6 种情况减少到1 5 种，如图2 - 5 所示。其中方式0 最为简单，立方体的所有顶点与等值面无交点，因此不产生三角平面片。在方式1 中，等值面将一个顶点与其它7 个顶点分开，有三个交点，产生一个三角平面片。 其它方式分别产生1 4 个三角平面片。 画画画画画 s 画画回国囱 回l 画画1 固1 囵 图2 - 5 等值面与立方体1 5 种相交方式 利用每个顶点的不同状态，可创建一个索引表。顶点编号方式见图2 - 6 。另外， 可再创建一个边表，在边表中给出等值面与不同状态的立方体的边相交的情况。而 每个立方体的索引可作为指向边表的指针。 困习困丑亚砸 图2 - 6 立方体顶点状态索引编号 逆向工程中基于散乱数据点的曲面重构方法研究 根据索引表及边表，可用插值的方法求出等值面与立方体的交点。由于高阶插 值的方法并不能显著改善曲面质量，且较为费时，因此一般采用线性插值的方法。 得到所有交点后，可根据图2 5 得到所需的三角平面片。 二三角平面片顶点法矢的计算 步进立方体算法的最后一步是计算每个三角平面片的三个顶点的单位法矢。绘 制算法将用这些法矢来生成明暗处理图象。等值面沿切矢方向的梯度为0 ，因此梯 度矢量g 的方向垂直于该等值面，若该梯度矢量的模不为0 的话，则可以通过它确 定等值面的曲面法矢。 ( 1 ) 估算立方体顶点处的梯度 立方体顶点( f ，七) 处的梯度用沿着三个坐标轴的中心差估算可得： g ：( j 七) ：丛生盟盟；型塑 x g ，( f ，i ) ：堕盟生盟坐业 y g = ( j 七) ：巫丝卫生；坠业 n z 其中，d ( i ，j ，k ) 为数据集o ( i ，j ，k ) 点的值，血a y a z 分别是立方体的三个方向 的边长。 ( 2 ) 计算三角平面片顶点处单位法矢 由两个顶点的梯度进行线性插值求出交点( 三角平面片的顶点) 梯度，再将求 出的三角平面片的顶点梯度除以它的模就得到了每个顶点的单位法矢。 三m c 算法流程 m c 算法在执行时，每次扫描其中两片断层，构造这两层之间的立方体。首先 对立方体顶点进行分类。由分类顶点建立该立方体在检索分类表中的索引号，检索 分类表中对应的等值面分布模式，由线性插值计算出三角平面片顶点位置及其梯度 值，将立方体边上的交点按等值面片连接模式连接成三角形。 m c 算法的基本流程如下： f o r k = lt o m 一1d o 读入缸，tk + t 和k + 2 四层数据点值 f o r j 2 lt o m ld o f o r - 1 t o 毽一ld o 由( f ，j ，助，( i , j ，句，( i , j ，( i , j ，翰，( f ，j ，幼，( i , j ，功，( f ，工句，( f ，j ，翰组 南京航空航天大学硕士学位论文 成当前立方体的八个顶点巧，k ，判定巧，与等值面的相对位 置( 内或外) ，并由此决定当前立方体的索引号i n d e x ； 由i n d e x 取出构造索引表中的等值面片的连接方式p ； 由线性插值计算出立方体边上等值面交点的位置p 和相应单位法 矢； 由p 确定的次序构造等值面的三角平面片并放入输出的等值面几何 表示中： e n df o r e n df o r e n df o r 图2 7 立方体的连续性 2 3 1 m c 算法存在的问题及解决方法 尽管利用m c 基本算法可以生成质量很高的图象，但其图象生成的效率、生成 的三角平面片的个数及其在三角平面片划分过程中的二义性等问题，使得其适用范 围受到很大的限制。因此，许多研究人员花费了大量的精力，针对上述问题提出了 许多改进的方法。 一效率 在m c 算法的基本流程中，每个立方体都需进行等值面与各边交点及各三角平 面片顶点单位法矢的计算。显然，大多数边、点将重复计算四次，使得效率大降低。 望旦三堡! 苎王墼塾墼塑皇竺些亘重塑查鲨堑塞 由于m c 算法是按i ，j ，k 从小到大的顺序依次处理每个立方体，所以可利用 立方体的连续性来提高m c 基本算法的效率。例如，对于内部的立方体来说，只有 三条边需进行插值计算，而其它的九条边与等值面的相交情况可从先前已计算过的 立方体获得。如图2 7 所示，图中所示立方体仅需计算e 6 、e 7 、e 1 2 。同样，在图2 6 中，只需计算v 7 的梯度。 据研究，真正与等值面相交的立方体至多只有1 0 左右，算法执行中3 0 7 0 的时间用在空立方体的检测上。w i l h e l m s l ”1 提出一种按需分叉的八叉树结构对体数 据集进行分割，仅对与等值面相交的立方体进行计算，这样就大大加快了运算速度。 二二义性 m c 算法中所提出的1 5 种立方体内等值面的连接方式中存在着二义性的问题。 如图2 8 所示，在立方体的一个面上，如果这个面上的四条边都存在交点，即位于等 值面外的顶点分别分布在对角线的两端，那么就有两种可能的连接方式，因而存在 二义性，这样的面称之为二义性面。 ( a ) 图2 - 8 二义性面 在图2 - 5 中的1 5 种连接方式中，方式3 、6 、7 、1 0 、1 2 、1 3 都包含有二义世面。 包含有一个以上二义性面的立方体称之为二义性立方体。要能正确地构造等值，必 须鼹决好二义性立方体内的等值面连接方式。例如，若两个相邻的立方体的公共面 是二义性面，则有可能在等值面上产生“洞”，见图2 - 9 。 南京航空航天大学硕士学位论文 2 - 9 等值面上“洞”的出现 解决二义性面的方法有：双曲线法和小特征处理法】。 1 双曲线法 该方法利用双曲线渐近线的交点来判定二义性面。根据m c 基本算法的假 设，通过线性插值可以求得立方体边与等值面的交点，而对立方体内的点则是 通过三维线性插值求得的。 d 1 2 d 2 1 图2 - 1 0 三维线性插值 如图2 - 1 0 所示，设p 点坐标为( x ，y ，z ) ，则由三维线性插值可得 f ( x , y , z ( p 2 ) + 赣耵胛2 ) ) ( 2 _ 6 ) 其中p 。，p ：两点可由p p 。2 和p ：。，p ：插值决定。这样，p 点可由八个顶点的 三维线性插值求得，具体展开成 f ( x ，y ，三) = 日o + a l x + a 2 y + a 3 z + 口4 叫+ d s 弦+ a 6 z 了+ a 7 x y z ( 2 7 ) 逆向工程中基于散乱数据点的曲面重构方法研究 其中8 个系数由v ，v 。这8 个顶点决定。 厂( z ，y ，：) = c o 在立方体内值为c 。的等值面方程可表示为 等值面与立方体某一外表面的交线，即是方程式( 2 6 ) 与立方体表面的交。不 失一般性，可设为z = z n 平面，代入方程式( 2 7 ) ： 得到 其中 f f ( x ，y ，z ) = c 。 i z 2z 0 b o + b l x + b 2 x + 6 2 y + 6 3 x y = c o ( 2 8 ) ( 2 9 ) ( 2 1 0 ) ( 2 1 1 ) 显然，上述方程是一双曲线，也就是等值面与立方体某一面的交线是一组双曲 线或其中的一支，具体可写成 ( 2 1 2 ) 如图2 1 1 所示，当两支双曲线均与立方体平面相交时，就会出现二义性( 图 2 1 1 中的( a ) ( b ) 具有二义性) 。 1 6 口十 吼 l i 白 口+ 吒 1 i 扫 一 弧 叫一 4 + 叩弘 + + 为 写一一 也 可 二 式 一 r 一 一 1，j 蛐 m f b b l p j 1 l 一 一 s d 一 1 i 00 8 南京航空航天大学硕士学位论文 ( a ) 图2 1 1 等值面与立方体表面交线的其中四种情况 在出现二义性的情况中，二支双曲线将二义性面分成三个区域，双曲线渐近线 的交点总是和其中一对交点落在同一个区域内。 根据式( 2 1 1 ) ，渐近线方程可写为 工：一丝：一丝亟鱼 如口4 + 口7 ：o ( 2 1 3 ) 。：一旦：一堡丝鱼 7 6 3d 4 + a t z o 如玳_ ) i 砂2 g ，则数值大于c 。的一对顶点与渐近线交点落入同一区域，如图2 - 1 2 ( a ) 所示，可连接m ，m ：和m ，m 。，否则数值小于c o 的一对顶点与渐近线交点 ( a ) 图2 1 2 二义性等值面的判定 落入同一区域，如图2 - 1 2 ( b ) 所示，可连接m m ，和m ：m 。方式3 和方式6 各有一 个二义性面，分别可以获得两种连接方式；方式7 有三个二义性面，可以获得8 逆向工程中基于散乱数据点的曲面重构方法研究 种连接方式；方式1 0 和方式1 2 各有两个二义性面，可以获得4 种连接方式；方式 1 3 有六个二义性面，因此存在2 6 = 6 4 种连接方式。图2 1 3 给出了方式3 及方式6 的 两种连接方式。根据等价性原理，可以减少一些方式。有些= 义性面的出现几率较 小，如方式1 3 就很少出现。 厦 方式3 固 方式6 图2 1 3 方式3 、6 的两种连接方式 2 ，j 、特征处理法i ” 在m c 算法中之所以会产生“洞”是由于利用互补、对称方法将2 5 6 种等值面 与立方体的连接方式简化为1 5 种最基本的方式，然而互补方式并不适用于二义立方 体的情况。对于互补方式是将大于等于闽值所有顶点与所有小于阈值的顶点相互交 换，这种互补情况被认为是对等的，在图2 5 中方式1 0 ，1 2 ，1 3 中是不存在互补情 况的，这是由于这三种情况中仅有4 个大于阈值的顶点，只有方式3 ，6 ，7 包含这 种情况。 实际上，解决“洞”的问题的方法是很简单。只要将剩余的三种方式3 ，6 ，7 的互补情况分别用另外三种新的方式代替。这6 种方式见图2 1 4 。 南京航空航天大学硕士学位论文 3 6 图2 1 4 六种新方式替代了m c 中原三种方式 本文采用的这种方法考虑了1 8 种立方体的连接方式，而不是原来的1 5 种方式。 由图2 - 9 中二义面造成的“洞”的问题己得到解决。在这种新方法中，所有的二义 面都用图2 - 8 ( b ) 的方法连线。因此，再也不会产生“洞”问题。例如，图2 - 9 中的 “洞”问题可以通过用图2 1 4 中的3 b 替代图2 - 9 中右边的立方体，如图2 1 5 所示。 6 a3 b 圆彭 图2 1 5 解决“洞”的方法举例 圆留团圆虱曰 k 沁 a 逆向工程中基于散乱数据点的曲面重构方法研究 三三角平面片的个数 m c 基本算法的另一个问题是生成的三角平面片过多。尤其是对于医学图这类 较复杂的图象一般都要生成几十万个三角平面片，以至于用户无法对用三角平面片 绘制出来的图象进行旋转、平移、缩放等实时交互，因此有必要减少生成的三角平 面片，以提高交互绘制速度。 压缩原始数据可以减少输出的三角平面片个数，例如采用均值化的方法将一层 中的四个数据点作为一个数据点来处理，这样可以提高算法的效率，并使图象更为 平滑，但这以丢失图象细节为代价( 见图2 1 6 ) 。 数据压缩 图2 1 6 数据压缩导致等值面图象信息丢失示意图 用户往往需要观察图象的局部细节，因此，有必要找到一种用较少的面片表示 较精细的结构的方法。s c h r o e d e r 提出的d e c i m a t i o n ”1 算法可以在不影响图形质量的 情况下，通过对原等值面三角形网格重排结点，生成最优化意义下的d e l a u n a y 三角 化网格，该算法能够大量减少三角形的个数。但该算法是个最优化过程，执行时间 很长；另外，为了建立边表结构，该算法需要很大的内存开销。 自适应m c 算法p 琊4 1 与m b 算法都能大量减少三角平面片的个数。 自适应m c 算法( a d a p t i v em c ，a m c ) 的基本思想是根据等值面的形态来决 定三角平面片的大小，即等值面比较平滑时，可以用比较大的三角平面片来拟合它， 否则用较小的三角平面片来拟合。其基本方法是：先将体数据集分割成一些较大的 立方体单元，然后分别在这些立方体单元中进行m c 计算，若产生的三角平面片能 够较好地拟合等值面，则对该立方体单元的计算结束：否则继续将这些立方体单元 分割成较小的单元并重复以上步骤，直到三角平面片能够较好地拟合等值面或立方 体单元而不用继续分割为止。 m b 算法是对m c 算法的优化，减少直接由m c 输出的三角平面片，而不是依 赖后续处理来优化。与压缩数据方法不同的是，m b 算法按一定的规则将m c 算法 产生的面片加以归并来实现减少三角平面片的目的，它试图在减少三角平面片与保 留图象细节之间达到某种平衡。m b 是一个递归算法，它把m c 算法中的立方体概 念加以拓广为b o x 。b o x 由若干个立方体构成的空间六面体区域。m b 算法把原始 2 n 南京航空航天大学硕士学位论文 体数据看作一个b o x ，从这个b o x 开始进行以下操作： ( 1 ) 把b o x 分成b o x l 和b o x 2 ； ( 2 ) 对b o x l 和b o x 2 分别用m c 算法抽取出其中的等值面c f i 和c f 2 ： ( 3 ) 判断c f i 和c f 2 能否用b o x 中的等值面c f 代替：如果c f l + c f 2 = c f 就以c f 代替c f l 和c f 2 ，实现归并； ( 4 ) 对b o x l 和b o x 2 递归进行上述步骤，直至不能归并为止； ( 5 ) 输出达到最大归并程度的b o x 中的等值面。 逆向工程中基于散乱数据点的曲面重构方法研究 第三章基于散乱数据点曲面重构实现步骤 3 1 建立数据点拓扑关系 本算法以没有任何拓扑信息的散乱点集为处理对象，因而首先就需要建立点的 拓扑邻接关系。如果在整个点集中寻找每个测点的k 一近邻，在测点数较多时效率是 非常低下的。为此，本文提出一个空间划分策略，以提高算法的效率。首先读入测 量点集，在读入三维坐标点的同时，得到测量点集的x 坐标，y 坐标，z 坐标的最小、 最大值，从而形成一个与坐标轴平行的长方体包围盒，包围所有的测量点集，并将 长方体包围盒划分成m x n x l 个小立方体栅格，如图3 - 1 。 0 卜_ 旦l 叫 f “ 匕一x 图3 1 空间化分 将所有测量得到的三维数据点存入一个一维数组，判断每个数据点所在的立方 体栅格，并将数据点的序号追加到该立方体栅格对应的线性链表中，用哈希表结构 存放各个小立方体栅格中所包含的数据点，哈希表通过立方体栅格在x 、y 、z 三个 方向的索引号直接定址。 南京航空航天大学硕士学位论文 设空间长方体包围盒的最小坐标为：c e l l _ o r g i n _ x ，c e l l _ o r g i ny ， 立方体栅格的长度为c e l l s i z e 当前点的三维坐标值为：p x ，p y ，p z 小立方体栅格的哈希函数是： r r f ( i n t ) ( p x c e l l _ o r i g i n _ x ) c e l lj s i z e ； n = ( i n t ) ( p y - c e l l _ o r i g i n _ y ) c e l i s i z e ； c e l l o r i g i n z ， 则求该点所在 ( 3 1 ) 1 2 ( i n t ) ( p z c e l l _ o f f g i n7 ) c