（计算机应用技术专业论文）marching+cubes算法研究现状.pdf

山东大学硕士学位论文 摘要 等值面技术在可视化中应用广泛，许多标量场中的可视化问题都归纳为等值 面的抽取和绘制，m 缸c l l i n gc i l b 嚣方法是目前应用最为广泛的等值面抽取方法之 一。自1 9 8 7 年l o 枷s 等提出该算法以来，就因为其简单高效取得了众多研究 人员的关注，被广泛的应用于医学图像重构，有限元分析，隐式曲面绘制等领域 的研究中，取得了许多重要的成果。但算法也存在一些不足之处。在目前为之， 已经有大量的研究工作对m a r c h i n gc u b e s 算法本身进行了有效的探讨，来对该 算法进行完善和提高它的运算效率。本文按照改进算法对m a r c h i n gc u b 嚣的具 体领域的改进，提出归类方法并进行比较讨论，为在具体的领域中应用和进一步 研究改进算法，有着很好的借鉴意义。 本文首先介绍了算法的研究背景和意义，以及该领域相关的工作和研究现 状，然后阐述了算法的基本原理，讨论了其优缺点和产生这些优缺点的原因。算 法在构造等值面的过程中，太依赖于直观的构造，构建体元状态模型时，对于对 称，旋转等情况的处理缺乏全面考虑，忽视了立方体内部可能存在的环状结构和 存在的临界点( 等值面发生变化的点) ，直接使用求得的边界等值点，根据基本 的体元状态模型，简单连接成三角片构成等值面，导致生成的等值面有在拓扑结 构，表示精度和效率方面，不能满足实际应用中的需求。 文章对算法构造的等值面在拓扑结构方面存在的二义性分面上的二义性和 体上的二义性两个方面进行讨论。首先分析了立方体面上存在二义性的原因，给 出了解决面上二义性的办法；随后，通过分析插值曲面在体元内部可能存在的结 构，引出体二义性，并且根据解决体二义性方法的不同原理，分四个类别对解决 方法进行讨论，根据三线性插值函数等值面的特性和不同体元模型的实验结果， 指出了每一类算法存在的问题和优势所在。 由于m 盯c h i n gc u b 髂算法求逼近等值面的过程中，使用线性插值计算出等值 面与立方体边的交点之后，采用简单连接的方式，形成逼近等值面的边界多边形， 然后进行三角化得到最终的逼近等值面片，所以当算法针对采样稀疏的数据场构 造等值面时，会出现等值面精度不高的问题，无法保证所形成的等值面的表示精 度。增加采样点无疑是提高表示精度的直接方法，但是随着采样点的加入，形成 山东大学硕士学位论文 三角片的增加，所需要的存储空间和处理时间往往超出系统的负荷和实时应用的 要求：另一种方法是渐进式网格抽取算法，算法通过逐渐细化的方法，逐步提高 表示精度，直到达到应用要求为止，这种方法可以在增加计算量不大的情况下提 高精度。 m a r c h i n gc u b e s 算法对每一个立方体单元进行处理，耗费大量的时间，同时， 在采样密度较高的数据场中，也往往生成过多三角面片，导致算法效率大大降低。 本文对这种情况进行分析，总结了提高算法效率的主要方法。然后将这些方法分 成三类：第一类方法通过建立合适的数据结构，跳过不存在等值面的体元，有效 的节省了生成等值面所需要的时间；第二类方法旨在讨论节省存储空间的几种方 法，主要是在保证逼近精度的情况下，通过合并相邻的三角面片进行实现；文章 重点讨论了第三类，即多分辨率方法，该方法兼顾算法时间和空间两个方面的耗 费，有效地解决了交互显示等实际应用问题。 。 文章最后对m a r c h i n gc u b 豁改进算法进行总结，并展望了算法今后的发展方 向，对实践中具体应用算法和对其进一步进行研究，都有很重要的借鉴意义。 关键词：可视化；等值面抽取；拓扑二义性；精度；效率 i i 山东大学硕士学位论文 a b s t r a c t i s o s i i k et e c i l l l o l o 韶i s 谢d e i y 璐e di i lv i s u a l i z a 6 0 n 锄dm a n ys c a l 缸f i e l d 、，i s l l a l i z 撕珊d b l 锄sc 锄b e l v e db yi s o s u r f 赫n g 锄dr d e 血吕m a r 凼n gc u b e s a l g o r i t i l i ni s t l l en d s t 丽d e l yu di s l l 一沁em e 山o dm l wf r o m1 9 8 7w h 吼 l o r e n 湖b r o 心h tf o r w a r dt h i sm e m o d m a n yr 髂e 缸c h e r sh a db e i m e r 嚣t e d i l li tf o f “ss i m p l i d 够锄de m c i 锄盯i ti s 晰d e l yu d mm a n ya r e 嬲，s u c h 鹊m e d i c a li m a g e r e c 吼s 虮l c t i o i l ，觚t ee l 咖e n t 姐a l y s i s ，i n l p l i c i ts u r f 缸er d e r i n ge t c ，t h e f eh a v eb 咖 n u m e r o 璐r e a r c h e so nm a r c h i n gc u b 鼯畦l ln o w t oi n l p f o v e1 h e 桶c i c y 锄dm a l 【e i tw o r kb e t t 既h lt l l i sp a p 也ei m p r o v 锄e n ta l g o r i t l l 】【i l sa r e 、，i e 删锄dc l 舾s i f i e d a c c o 岫n g t o t 量l ea s p e c 协t l l e yh a v e i m p r o v e d t l l ea l 鲥血i nt l l i s w o r k 、】l i i uh a v e a d e 印i m p a c to nt l l ef h r t i l e rr e s e a r c h 趾da p p l i c a l i o n i l lt l l es p e c i 丘ca r e 弱 1 k sp a p e rf i r s ti i l 仃0 d u c 郫t h eb k g r o l | l i d 肌di n l p o r 啪c eo ft l l es t i l 衄s o m e e 菇s t i n gw o r k 孤dm e i i l o d sa b o u tt l l ea l g o r i t l l ma r ei m r o d u c e dt h 百v 嚣o u tm e d e f i n i 6 0 n ，t 1 1 ed i s a d v 锄t a g 鹤锄da d v 锄t a g e so f t i l ea 1 9 0 f i t l l l 砸锄de x p l a i 邺h o wa r e 1 1 1 e p r o b l e m sa r eb r o u g h ta b o l i t h lt 1 1 ep r o c 嚣so fi s i | r f 如i n 吕t h ea l g o r i t h ml k s c o n s i d e r a t i o no f t l l ei n t e r i o rs 咖c t i l i o f t h ev o x e l 锄dt a l 【e1 l l e 伍锄百器i nt h es 协t e 1 1 1 0 d u l e 鹤i s o s u r f 缸e sf o r1 1 1 e r em a yb es o m ec r i 石c a lp o i n 协锄dl o o p sw h e r et h e i s o s u m i c e sm a yc h 锄g ei t ss h 印e ，t 量l ei s o s l | r f 缸豁p r o d u c e di i l 也i sw 锣m 帮h a v e m 锄yp r o b l e m si nt o p o l o g 蜘p r e c i s i o n 锄de m c i c y 锄dc 锄ts a t i s 分m a n y a p p l i c a 吐o l l s t h e r ea r ef 缸e 锄b i 鲥锣锄db o d y 锄b i g i l i t yp r o b l 锄sa b o l i tt 量l ea l g o m h i i lh i t l l i sp a p e r ，t 1 1 en 圯t l l o d st 0s o l v et l l ef 缸e 觚l b i g l l i t ya r ep l l tf o 刑a r d e df i r 瓯龇dl 量l e n d i s c l l s s e s1 l l es o i 砸o n so fb o d ya l l l b i g i l i 锣p r o b l e 脚f 如mf o l | ra s p e c t s t h r o u g h a 1 1 由豳gt h ep d o p e n i e so ft l l e 伍l i i l e a ri i l 僦p o l 撕o nf 血c t i o n 锄dt l l ee 冲耐m 锄t a l r e s l l l t s ，t h ed i f l e r c 鲻锄m n gt i i ec l 船s m c a t i o n sa 旭p u tf 0 确d e d h it 1 1 i sp a p e lt l l ep r o b l e m so fl o wa c c u r a c yi s o s l l r f 缸鹤i ns p a r s e 纰f i e l da r e d i s c 璐s e d1 1 1 em a r c h i n gc u b e sa l g o m mf i r s t l yc o m p u t e st l l ei n t e r s e c t i o np o i n 怊 b e t w e e nt l l ei s o s u r f h e s 锄dv o x e l s ，t l l e nl l s e st h ep o i n t st of o n n 证锄羽鹤w h i c h 黜 山东大学硕士学位论文 忸k e r i 翘l l l ef _ m a la p p r o ) d m a t ei s o s l l r f a c e s h lt h i s 唧，血ea l g o r i t l l mc 猢o tg 哪i i t e e t h e c l l r a c yo ft h ei s o s u r f a c e ad i r e c tn 蚓 h o dt os o l v e1 l l i sp r o b l e mi st oi n c r e a s 锄1 p l i n gp o i n 招，b m 埘1 l lm ei i i c 佗m to ft 量l ep o i n 协，t l l e r em 妙b et o om u c hs p a c e 舭dt i m en e e d e dt 0p r o c e s si i l 锄i n t e r a c 6 v ew a ya n o m e rm e 山o dt oi m p r o v em e 孔c u r a c yi s 1 l l ea d a p 矗v e 鲥dm e l l l o dw i l i c ha b s t r a c st l l e 仃i 锄百eg r a d u a l l yt i l l1 l l e a c c i l r a c yi ss 撕s 丘e da n dm i sm e m o dc a ni m p r o v em ea c c u m c y 、】v i t l l o l i ti l l c r e 舔i n g t 0 0m u c hc o m p u t 撕o n t i l i sp 印盯a l s o 锄a l y z 器1 l i ec i r c m n s t a l l c et l l a tt h ea l g o 疵l i i i lm a yo f t l mp r o d u c e t o om 舡】ym 锄甜嚣i nd d a t af i e l da n dm e np u tf o r 啪r d1 i l em a i l lm e m o d st o i m p f o v et l l e 喊c i 印c y t h e r e 盯et h r e et y p e so fm e m o d s 协l v e1 l l ep r o b l 唧o n e w 帮i s 协a v o i ds w e 印i n gm ev o x e l sw h i c hd o nn o th a v ea n yi s l l 一沁鹤t os a v e 矗m e ； a 1 1 0 t h e rm e t i l o da i m s 协s a v e1 l l es p e s ，锄dt i l e 删i i l l 、唧i s 协c o m b i n es e v e r a l m a n g l e si n t o0 n e ；t h em l | 1 6 - r e l i n i o nm 劬o d i st i l ew i d e l y 懈e do n e 协i m p f o v em e e m c i e n 吼1 1 l i sm e m o d 啪s i d e 培t i 埠幻瑙i i lb o t l ls p a c e 锄d6 m ea n dc 觚s a l i s 匆 1 量1 ep m c t i c a la p p l i c a t i o ns u d h 鹊i m 僦t i v ed i s p l a y a t l a s t ，“sp 印e rs u n 蚰a r i z 髂t l l em e m o d sa n d 百v 铭1 l l ef u t u r er e s e 砌仃锄d s o fm 删n gc u b 韶i n l p r o v 鲫e n tm e t h o d s a i l dt l l i si i l i 曲t h a v ei n 啪n 锄ti m p a c t t l l e 如曲e rr e s e 砌w o f l 【锄dp r a 甜c a la p p l i c 撕o n k e yw o r d s ：s u a l i z a t i 蚰，i s o s u r f a c i n 舀t o p o i o 贸a m b i g u i 锄a c c u r a 铴 e m c i 蛐c y 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：雌日期：2 芈 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手 段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 啤一名：僻 山东大学硕士学位论文 1 1 研究背景和意义 第一章绪论 面绘制是科学计算可视化方法中常用的一种方法，它从原始的三维数据中重 建出中间的几何图元( 一般是以三角面片或者体元组成的曲面) ，然后使用真实感 图形学技术对几何图元进行光照计算和绘制【1 捌。面绘制技术的基本原理是，首 先对整个数据进行等值表面分割和定义，用各种几何元拟合表面，然后绘制出所 有的几何元【3 】。在可视化中常用的几何元有体元级大小的平面多边形、多边形网 格、三角片等。实际上，从数据场中构造的表面就是提取的某一阈值的逼近等值 面。许多标量场中的可视化问题都归纳为等值面的抽取和绘制，如医学图像中的 三维重建；有限元计算中的标量场分析，分子化学中的分子表面显示；地质中矿 藏分布的构造等等。在散乱点的雎面重建h 5 】和关键帧动画1 6 刀中，也常常提取零 等值面作为散乱点数据的重建曲面和中间帧。近年来，等值面逼近问题得到了极 为广泛的关注，并取得了许多重要的成果。m a r c h i n gc u b e s 方法以其简单和高效 的特点，成为应用最广泛的等值面逼近方法。 随着成像设备的不断更新及其性能的提高，断层扫描序列图像的层内与层间 分辨率较以前有显著提高，使得能够在二维水平上更加清楚、直观地看到物体结 构的细微特征，从而获得越来越详实的信息。然而，这些二维影像数据只是表达 某一截面的信息，研究人员只能通过二维图像进行观察，所得到的结果往往带有 研究人员的主观判断和研究经验。地r c h i n gc u b e s 算法的不断完善和发展，使 得提供直观、逼真而且能够包含原始信息中隐含的丰富内容的三维信息成为可 能。通过图形图像技术，可以对影像进行任意放大、缩小、旋转、对比调整、三 维重建等处理，得到便于研究者从多角度、多层次进行观察的三维模型。这对分 析结果的准确性和正确性有深远的意义，并促进了应用领域的飞速发展。 1 2 相关工作和研究现状 在1 9 8 7 年，由w e l o r e n s o n 和h e c l i n e 嘲提出的m a r c h i n gc u b e s ( 以下将 其称为m c ) 是基于体元的一种典型的面绘制方法。m c 算法作为一种构造等值面的 山东大学硕士学位论文 方法，使用三角面片作为中间几何图元的基本表达元素，较好地解决了在任意不 规则、非线性数据场中进行等值面重建的问题。 由于目前的显卡都可以对三角面片进行硬件加速的绘制，并且m c 方法本身原 理简单，容易实现，因此得到了广泛的应用，被认为是目前最流行的面绘制算法， 对面绘制的研究产生了深远的影响。一直到现在为止在可视化领域的著名杂志和 会议上还经常有针对m c 方法的改进算法。然而，m c 方法也存在一定的不足之处。 首先，m c 算法不能保证生成曲面满足c o 连续，即产生的逼近等值面片的拓扑结构 与采样数据场的拓扑结构不一致【1 】；其次，m c 方法直接连接边上插值得到的等 值点组成逼近等值面的多边形，然后三角化得到等值面，当要求的逼近精度较高 时，很难达到逼近精度的要求，对于采样比较稀疏的数据场更是如此协删；最 后，m c 算法用大量的三角片来逼近等值面，对这些三角片的顶点和项点连通关系 进行编码，需要非常大的存储空间和传输带宽，同时，生成和处理大量的三角片 往往会耗费较多的执行时间渺稍1 ，这限制了算法在交互应用中的使用。 最初，众多学者的注意力主要集中在面二义性问题上，目的是提取正确的边 界多边形。然而，边界多边形是等值面与体元边界的交点，不同的三线性插值曲 面与体元相交可产生相同或相似的边界多边形，从而导致体二义性的存在。1 9 9 4 年，bkn a t a r 面“1 9 】发现体二义性的存在，极大的促进了m c 方法的研究和改进， 许多学者开始提出新的疑问：除了bk n a t a 啊孤算法提出的体二义性外，是否还 有其他体元内部存在“管”状曲面? 如果存在，又如何判定“管”状曲面的存在 和提取逼近等值面呢? 由此引起了广泛关注，提出了许多对于m c 方法的改进 【2 9 q 1 1 ，其中很多方法根据不同的数据特征，从一个角度来判定体二义性的存在， 因而没有有效的保证等值面的拓扑正确性和体元模型查找表的完整性。 其次，利用m c 算法求逼近等值面的过程中，使用线性插值计算出等值面与 立方体边的交点之后，采用简单连接的方式，形成逼近等值面的边界多边形，然 后进行三角化得到最终的逼近等值面片。当对目标数据场的采样密度比较大，m c 算法中单位立方体大小相对显示尺度来说很小时，这种简单构造三角片的方式已 经足以满足实际使用的精度要求。但如果要对局部数据放大观察或者采样数据本 身的分辨率很低，就需要对这种简单构造方式进行改进，来达到较高的逼近精度 要求。 2 山东大学硕士学位论文 此外，m c 算法在数据场密度较高的情况下具有较好的绘制效果，但这时往往 生成大量的三角面片，需要较大的存储空间和传输带宽，并且过多三角面片需要 较长的时间进行处理，以至于无法进行实时绘制。这些因素都使m c 算法的应用 受到了限制。因此，需要改进算法来减少对存储空间的需要和对时间的耗费。 一些文献曾综合讨论过部分改进算法，如舢l 、，肌g e l d e 2 i ，2 1 1 等对等值面抽 取过程中产生的拓扑结构问题进行研究，k b r o d h 【7 1 1 曾对体数据可视化的各种 方法进行综述，ph e c k b e n m l 对等值面逼近算法也进行过讨论，但这些文献对于 改进算法或者针对一个方面进行研究，或者没有很好的对各种改进方法进行分类 对比，致使没有形成完整地理论体系，阻碍了m c 和其改进算法在具体的领域中进 行应用。 1 3 论文主要贡献和章节安排 本文主要对等值面逼近算法m c 进行综合分类研究，该方法是应用最广泛的面 绘制方法之一，其基本的实现方法是在等值面上提取有限个等值点并将其三角 化，以得到的三角片组合曲面作为逼近等值面，因而等值点的选择和等值点的三 角化是该方法的关键环节，等值点的位置和三角化的方式决定着体元内部逼近等 值面的拓扑结构和几何形状，逼近等值面片的表示精度以及生成面片的数量和处 理时间。虽然在m c 方法的不断发展过程中，众多学者对拓扑问题，精度问题和效 率优化问题进行了研究，但却缺乏全面的综述讨论，目前为止，没有形成一种公 认的行之有效的方法。 本文总结现有的针对各个领域的改进方法，从拓扑二义性，等值面表示精度 和算法效率三个方面进行综合讨论分析，提出新的分类方法。对每一个方面的改 进方法按照其理论依据不同进行分类，理论依据相同的分类按照发展历程进行讨 论，对每类改进算法，文章对其实验结果进行比较，然后分析对比，指出其优点 和不足之处。对于拓扑二义性的改进方法，文章从面二义性和体二义性两个角度 进行分析，面二义性问题的解决方法相对简单，使用渐近线方法可以很好的进行 解决；体二义性问题的解决相对复杂，文章通过分析三线性插值曲面的性质，按 照解决方法的研究历程，将解决体二义性的方法从四个方面进行分析，由简单到 复杂，从最初提出的鞍点解决方法，到最终的临界点和拓扑结构方法解决体二义 山东大学硕士学位论文 性，逐渐改进了算法中存在的不足之处。关于如何提高逼近等值面表示精度，文 章分两个类别进行讨论，增加采样内部点是很直观的方法，但单纯依赖于增加采 样点的方法显然是不合理的，等值点数目越多，计算量和数据量也就越大，导致 产生大量的冗余数据；渐进式网格方法是较好的处理方法，该方法在处理等值面 的过程中，不断细化，直到满足具体应用的需求，在保证表示精度的同时，能有 效防止冗余数据的产生。文章对算法效率从时间耗费和空间存储效率两个方面进 行讨论，具体分为三个方向：第一类方法通过建立合适的数据结构，跳过不存在 等值面的体元，有效的节省了生成等值面所需要的时间；第二类方法旨在讨论节 省存储空间的几种方法，主要是在保证逼近精度的情况下，通过合并相邻的三角 面片进行实现；文章重点讨论了第三类，即多分辨率方法，该方法兼顾算法时间 和空间两个方面的耗费，有效地解决了交互显示等实际应用问题。 全文共分六章，第一章绪论介绍了科学计算可视化中的等值面抽取算法m c 的研究背景、研究现状和重要意义；第二章阐述了m c 算法的原理，应用领域，并 对算法本身存在的问题进行分析；第三章对m c 方法中存在的拓扑二义性进行研 究，首先介绍了算法中拓扑二义性的存在，然后从面二义性和体二义性的解决两 个方面，讨论改进算法的研究情况；第四章针对m c 算法在构造等值面的过程中达 不到表示精度的问题，综合分析了现有的提高表示精度的方法：第五章提出了提 高m c 算法得时间和空间效率的方法。有些数据场，由于采样密度过大，在等值面 逼近的过程中，形成大量的三角面片，从而需要大量的存储空间和处理时间，无 法达到交互式应用的要求，本章对算法在时间空问效率以及其综合应用方面的改 进进行总结；第六章对全文工作进行了回顾和总结，提出了m c 算法发展的趋势， 并对未来发展进行了展望。 4 山东大学硕士学位论文 第二章m a r c h i n gc u b 鹤算法概述 2 1m a r c h i n gc u b 鹤算法基本原理 m c 嘲方法以数据场中的相邻两层上的各四个像素为顶点组成的立方体为最 小的等值面搜索单元( 也称为体元) 。其基本思想是逐个处理数据场的体元，分 类出与等值面相交的体元，采用线性插值计算出与等值面相交的体元的棱边上的 交点，根据体元8 个顶点与等值面的相对位置，将这些交点按一定方式连接成等 值面，作为等值面在体元内的逼近表示，所有体元中的等值面构成整个数据场的 等值面。等值面中各三角片顶点处的法向量的计算，一般先采用中心差分计算出 体元顶点处的梯度，再用线性插值计算等值点处的梯度值作为该点的法向量。 m c 的基本假设是沿着体元的棱边数据场呈线性变化。也就是说，如果一条棱 边的两个顶点的数据场值分布大于和小于等值面的值，则该条边上有且仅有一点 是等值面与该边的交点。确定立方体体元内部的等值面的分布是该算法的基础。 算法可简单地分为三个主要步骤：1 ) 用线性插值计算体元边与等值面的交点， 以下将这些等值点称为边界等值点；2 ) 将交点按一定方式连接成等值面，通常 多采用三角片组合曲面来逼近等值面，这一过程称为三角化；3 ) 计算等值面中 各三角片顶点处的法向量，为后续的绘制提供依据。 计算等值点的过程比较简单，首先对体元的8 个顶点进行分类，以判定该顶 点是位于等值面内还是等值面外。再根据8 个顶点的状态，确定等值面在体元内 部的连接方式。 假定等值面的值为c 0 。则顶点分类规则为： ( 1 ) 如果体元顶点的数据场值c n ，则定义该顶点位于等值面之外，标记 “+ ”号： 山东大学硕士学位论文 ( 2 ) 如果体元顶点的数据场值 c 0 ，则定义该顶点位于等值面之内，标记 “一”号。 圆 1 0l l 圈2 一l1 4 种基本体元状态模型 每个体元有8 个顶点，每个顶点只有两种状态，显然共有2 8 - 2 5 6 种组合状 态。l o r e n s e n 最早利用顶点状态反转和旋转对称性将2 5 6 种组合状态的所有可能 的情形总结为如图2 1 所示的1 4 种基本模式。其中由边界等值点构成的多边形 称为边界多边形。 需要说明的是，在本文中我们对体元顶点和边的标注仍然沿用l o r e n s 锄的表 示方式，如图2 2 所示，v 1 v 8 分别表示体元的八个顶点，e 1 e 1 2 分别表示体元 的十二条边。 v s e 7 v 7 v 图2 2 体元顶点和边的标注 v 6 在实现时，可按照立方体项点状态构造等值面连接模式的索引表： 6 山东大学硕士学位论文 i i i d e x = 可直接由立方体各项点的状态检索出其中等值面的分布模式，确定该立方体 体元内的等值面三角片连接方式。 为使重构的曲面片之间具有拓扑一致性，即它们可以构成连续的、无孔的、 无悬浮面的曲面( 数据场的边界处除外) ，等值点的三角化过程应遵循以下规则： ( 1 ) 体元内曲面的各三角片之间满足c o 连续；( 2 ) 体元内曲面无自交现象；( 3 ) 不出现“边界面三角片”( 属于体元边界面的一部分的三角片) ；( 4 ) 一条直线 段属于且仅属于两个三角片( 边界体元除外) 。 2 2m 矗r c h i n gc u b 嚣算法的优点和存在问题 m a r c h i n gc u b e s 方法的提出提供了一种精确的定义体元以及体元内等值面 的生成方法，体元定义为由相邻层之间八个网格点组成的数据单元，它提供了一 种更一般化的体元定义，从造型的观点看，所有三维标量场都可以由这种一般意 义下的体元或单元组成，因而标量场中的等值面的生成均可以分别在这些组成标 量场的体元内完成，这为散乱数据场和曲面分布数据场中等值面的构造提供了非 常简单有效的方法。但算法在构造等值面的过程中，太依赖于直观的构造，构建 体元状态模型的过程中，对于对称，旋转等情况的处理缺乏全面考虑，忽视了立 方体内部可能存在的环状结构和存在的临界点( 等值面发生变化的点) ，直接使 用求得的边界等值点，根据简单的体元状态模型，简单连接成三角片，因此，存 在许多缺点。算法白面世之日起就受到极大的关注，该领域研究人员在应用中不 断地发现其中的问题和不足之处并加以改进。 最早d a r s t 例发现二义性的问题。如果在体元的一个边界面上，标号为+ 和 标号为一的角点分别位于对角线的两端，则该表面上存在四个等值点，那么就会 有两种可能的等值线的连接方式，如图2 3 中a ) 和b ) 所示。如果二义性问题不解 决，就会导致最后生成的等值面可能有“孔洞”存在，即不能保证曲面的封闭性， 从而将空间分为“内”和“外”。为与下文的体二义性相区别，我们称这种二义 山东大学硕士学位论文 性为面二义性。 我们来观察图2 3 中的体元状态模型可知，3 、6 中有一个面存在二义性，l o 中有两个面存在二义性7 、1 2 中有三个面存在二义性，而1 3 中的六个面都存在 二义性。 图2 3 二义性面上四个交点的相对位置 随着m c 方法的广泛应用和对其研究的逐步深入，人们又发现了新的问题， n a t a r a ja n 【1 川首先指出体二义性的存在。根据三维线性插值，即使体元的六个表 面都不存在二义性，体元内部的等值面仍然不确定。如图2 - 4 中的体元状态模型 4 ，其内部的等值面可能为两片分离的面片，也可能为一“管”状曲面，也就是 说，m c 算法的体元模型查找表不完整，不能保证逼近等值面的拓扑正确性。 画 图2 4 体二义性和“管”状曲面 m c 算法在求逼近等值面的过程中，使用线性插值计算出等值面与立方体边 的交点( 等值点) 之后，采用简单连接的方式，形成逼近等值面的边界多边形， 然后进行三角化得到最终的逼近等值面片。当对目标数据场的采样密度比较大， 立方体大小相对显示尺度来说很小时，这种简单构造三角片的方式已经足以满足 实际使用的精度要求。但如果要对局部数据放大观察或者采样数据本身的分辨率 很低，这种简单连接方式构造的逼近等值面分辨率较低，远远不能达到实用的要 山东大学硕士学位论文 求。 此外，m c 算法在数据场密度较高的情况下具有较好的绘制效果，但这时往 往生成过多的三角面片，存储这些三角片顶点位置和法向量，需要较大的存储空 间和传输带宽，同时，计算大量三角面片的顶点位置和法向量，需要较长的时间 进行处理，以至于很难进行实时绘制和交互式应用，这些因素都使m c 算法的应 用受到了限制。 9 山东大学硕士学位论文 第三章m a r c h i n gc u b 鹤拓扑二义性解决办法 3 1m a 佗h i n gc u b e s 面二义性问题 第二章中提到，如果位于等值面内和在等值面外的顶点分别分布在对角线的 两端，就会有两种连接方式，当相邻的两个立方体在公共面上采取的连接方式不 相同时，就会出现面二义性，导致孔洞生成。随着面二义性问题的提出，也随之 出现了众多的解决方法”】，其中比较经典的方法是n i e l s o n 提出的渐近线方 法( a s y m p t o t i cd e c i d e r ) 【1 刀和四面体剖分法方法( 移动四面体法妇r c h i n g t e t r a l l e d r a ) 【1 0 ，l 。 3 1 1 基于四面体剖分解决面二义性 使用四面体方法解决二义性时，假设在四面体的边上，数据场呈线性变化， 由于四面体的每个面是三角形，生成的等值面片的连接方式是唯一的，并且对于 每个四面体，等值面模式只有三种情况，如图3 。如果顶点数据全大于或者全小 于等值面值，等值面与单元无交( 图3 1 左) ，如果一个顶点大于另外三个顶点 小于等值面值，则四面体中的等值面是一个三角片( 图3 一l 中) ，如果两个顶点 大于两个小于等值面值，则等值面是一个四边形( 图3 1 右) ，可以由两个三角 形构造。 图3 1 四面体中的等值面 四面体剖分法将立方体剖分为5 个，6 个或2 4 个四面体。然而，5 个或6 个 四面体的剖分是一种不对称的剖分，剖分后形成的四面体不全等，无疑增加了处 理的复杂性。虽然2 4 个四面体的剖分是一种全等四面体的剖分，四面体的插值 计算比较简单，却产生太多的三角片，并且在立方体内的等值面没有二义性时， 山东大学硕士学位论文 立方体也会被剖分处理，这都大大增加了算法的时间耗费。面对庞大的数据，为 达到实时交互的要求，减少计算和存储显得尤为必要，尤其是近年来随着成像设 备物理分辨率的不断提高，对可视化运算速度提出更高的要求。另外，对于一个 立方体来说，四面体剖分方法中等值面的构造跟剖分方式有关，不同的四面体剖 分方式将导致不同的等值面例，如图3 2 所示。这样一来，整个数据场内等值面 的构造与最初一个体元的剖分方式有关，导致形成的逼近等值面可能和真实等值 面有不同的拓扑结构。因而，用四面体剖分法来解决二义性问题很难达到理想的 结果。 图3 2 四面体不同剖分方式形成不同的等值面 3 1 2 基于渐近线方法解决面二义性 渐近线方法是应用最为广泛的判定面二义性的方法。基本原理是：当出现 面二义性时，双曲线的两支将所在平面分成三个区域，双曲线渐近线的交点总是 和其中一对交点落在同一区域，具体为如果渐近线交点的标量值大于等值面的标 量值，则标量值大于等值面标量值的对顶点跟交点落在同一区域，反之，另一 对顶点与渐近线交点落在同一区域，这是渐近线方法判定面二义性的基础。 根据渐近线方法，位于体元某一表面的等值线是一对渐近线分别与体元边相 平行的双曲线，双曲线与体元表面可能交于0 、1 、2 、3 、4 个交点，如图3 - 3 所 示。其中( a ) 、( b ) 和( e ) 三种均为退化情形，为处理简单，我们将( a ) 归并为( c ) ， ( b ) ( e ) 归并为( f ) 。只考虑双曲线与体元表面存在o 、2 和4 个交点的情形，即 山东大学硕士学位论文 图中( c ) 、( d ) 和( f ) 所示的情形。 厂人 _ j 、 ( a ) h i l l 划 ( d ) 厂天 弋 j ( b ) 厂太 弋 j ( e ) 厂 、一 _ j ( c ) 7 ( 1 图3 3 等值面与体元某一表面的相交情况示意图 模式0 ，1 ，2 ，4 ，5 ，8 ，9 和1 1 的等值面是确定的，而根据方法其它体元 内部等值面则为如图3 4 所示。 图3 4 渐近线方法判定面二义性的结果 采用渐近线方法可正确解决二义性面的连接问题，并且不会产生太多的 三角片，因而是解决面二义性的一种较好的方法。 山东大学硕士学位论文 3 2 m a r c h i n gc u b 鹳体二义性问题 n i e l s o n 【”，1 6 1 刀等虽然对立方体面上存在的二义性进行分析，但对三线性插 值函数在立方体内部的形状没有给与足够的重视。n a t a r a j a n 【1 9 】对等值面在立方 体内部的具体形状进行详细研究，进一步发现即使体元中不存在二义性面，体元 内部也可能存在不同拓扑结构的等值面，指出了体二义性存在的可能性，并提供 了最初的解决办法。随后，通过对三线性插值等值面拓扑结构的深入研究，许多 体内拓扑二义性的解决办法也相继被提出。如图3 5 中的体元状态模型4 ，其内 部的等值面可能为两片分离的面片，也可能为一“管”状曲面。 画 图3 5 体二义性和“管”状曲面 bkn a t a r a j a n 的发现，极大的促进了m a r c h i n gc u b e 方法的研究和改进， 许多学者开始提出新的疑问：除了模式4 外，是否还有其他体元内部存在“管” 状瞳面? 如果存在，又如何判定“管”状曲面的存在和提取逼近等值面呢? 由此 引起了众多学者的关注，提出了许多对于m c 方法的改进。 3 2 1 利用鞍点解决体二义性 t a r a j a n 为有效的利用m c 算法抽取拓扑结构正确的等值面，提出逼近等 值面片需要满足的三个条件：一是所得逼近等值面片须是原来等值面的几何逼 近，即在一定误差范围内与原等值面相同；二是要达到拓扑一致性，也就是在体 元中的任意两点，对于逼近的等值面片和等值面，具有相同的位置关系；三是构 造逼近等值面片的复杂度不能太高。在文章中n a t a r a j a n 引入了面鞍点和体鞍点 的概念，并利用这两类鞍点来解决满足以上三个条件的可视化问题。其中面鞍点 为渐近线方法中渐近线的交点，体鞍点为在三维空间中面鞍点的扩展。即根据数 据在体元面上是双线性变化的，可以得到在该面上的双线性函数，对其两个分量 山东大学硕士学位论文 分别求偏导，可以得到面鞍点，同理，对均匀采样的数据场进行三线性插值得到 的三线性函数，通过求该函数在三个方向上的偏导数可以得到体鞍点。 得到面鞍点和体鞍点后，根据以下规则来解决二义性：如果面上的一对对角 线顶点与面鞍点有相同的符号( 同时大于或者同时小于等值面值) ，则这一对顶点 在同一个区域内，否则另外一对定点在同一区域；如果体对角线的一对顶点与体 鞍点有相同的符号，则连通这一对顶点，构成一个管状曲面，否则不连通这对顶 点，形成两个分离的三角片。 v a ng e l d e r 和w i l h e l m s 2 1 1 研究发现，为保证多边形逼近等值面c 0 连续，体 数据内部的逼近多边形的边只能由两个多边形共享，体数据边缘的边只能出现在 一个逼近多边形中。并进一步指出，如果三角片位于立方体的面上，在该立方体 中就会有两个三角形共享同一条边，同时，在相邻的立方体中也会有至少一个三 角形共享这条边，这将导致生成的三角片逼近曲面不连续。虽然n a t a r a j a n 解决 了立方体中存在的拓扑二义性，但由于算法中没有解决三角片落在立方体面上的 问题，因而不能保证生成c 0 连续的三角曲面片，同时，n a t a r a j a n 也没有明确提 出对曲面如何进行三角化。c i g l l o n i 鲫以n a t a r a j a n 的研究为基础，对m c 进行了进 一步的研究，基于面鞍点和体鞍点对m c 的基本体元状态进行进一步分类，构造了 扩展查找表，对各种情况都给出了三角化方法，新建的扩展查找表总共7 9 8 种情 况，进行旋转，映射等操作后，最终得到具有8 8 种情况且各不相同的分类查找 表。对于逼近等值面存在不连续性的问题，特别是当有三角片在立方体面上存在 时，算法通过对立方体对角线顶点插值的方法，来加入一个体对角线上的点，有 效解决了不连续的问题。但由于数据场在体对角线上是三线性变化的，因此，引 入的内部点可能不在原等值面上。此外，对于图3 吨中的体元模型1 3 4 中存在 单个复杂曲面片的情况和1 3 5 1 中存在两个体鞍点的情况，算法都没有很好的 加以解决。 3 2 2 推广渐近线方法解决体二义性 c h e n l y a e v 口5 1 利用渐近线方法解决面上的二义性，对拓扑二义性，提出两 种新方法来加以解决。第一种方法以下面的结论为基础：在立方体上的一个三线 性插值函数在一条平行于边的直线上是线性变化的。算法通过比较有拓扑二义性 1 4 山东大学硕士学位论文 的立方体相对的平面上的渐近线来消除二义性。如图3 5 ，如果两个符号相同的 点在立方体内部是连通的，那么其一个面上的渐近线投影到其相对的另一个面上 时，两段渐近线必然相交，反之，如果两段渐近线的投影不相交，那么这两个顶 点是分离的。 图3 6 体元模型4 的两种情况 第二种方法基于在平行于立方体面的任意平面上，三线性函数都是双线性变 化的。在立方体中如果有两个顶点是在内部连通，但在面上不是连通的，如图 3 7 中的a 。，c 1 ，那么必然存在一个平行于立方体面的平面，平面与立方体的 交点形成的面是一个二义性面，在该二义性面中，符号与立方体中连通的顶点的 符号相同的两个顶点连通( 图3 7a t ，c t ) 。 c l c t c o l a t c t - b j ) t 怠。j ? ，t 。r 图3 7 抛物线方法解决体内二义性 如果a t ，c t 是连通的，根据渐近线条件，可得，a l c t b t d p o 。由于数 据在立方体的边上呈线性变化，可以用a 。，马，c ，d 。和，b o ，c 。，d o 的 线性组合表示a t ，b t ，c t ，d t ，然后代入并验证不等式是否满足，如果满足， 则对应的顶点a 。，c ，在立方体内部是连通的，否则，a 。，c 。是不连通的， 山东大学硕士学位论文 从而有效地将拓扑二义性去除。 画画 国画圆圆 画回国厨圆 圆静画固器 圆圆留 圆 回国 图3 8 细分m c 体元状态模型 c h e r n y a e v 对m c 算法的1 5 种基本情况，首先根据是否含有二义性面进行细 分，对于细分的这些情况中存在内部拓扑二义性的情况，进一步加以细分。最后 明确给出了有3 3 种情况的拓扑分类情况如图3 8 和对应的三角化方法。对于立 方体内部需要加入顶点的情况，算法选择其他顶点的平均值作为新加入的点，这 种方法选择的点不一定位于等值面上，同时，算法也没有解决三角片位于立方体 面上从而导致生成逼近