（计算机应用技术专业论文）移动立方体算法的理论及应用的研究.pdf

摘要 摘要 随着计算机图形学的发展，科学计算可视化技术在许多领域得到了广泛的研究和应用， 其中三维物体的表面重建是可视化领域中的经典研究主题。移动立方体( m c ) 算法是表面重 建中最具影响力的算法，其绘制的效果以及效率一直是个很重要的研究内容。本文针对这两 个方面，主要对移动立方体算法中的等值面、三角剖分以及加速方面进行了研究，并改进了 m c 算法。 以方向无关的三线性插值模型生成的等值面为三次曲面，等值面与边界体单元的交线有 两种特殊情况。本文基于这两种特殊情况，根据判别式的值，决定是对体素面元上的双线性 插值还是体素内部的三线性插值，从而得到不同的体素模式，再进行曲面重建，通过实例表 明该方法很好地保持了模型表面的特征，能够更加真实地重建出曲面模型。 本文利用三角剖分技术来改进m c 算法中生成的体素的剖分模式，并对拼接成的网格进行 自适应三角剖分，为了保持模型表面的特征信息，本文利用“交点”作为新点，这样，最终 结果很好地保留了原网格模型的特征信息，但是却降低了绘制的效率。然后从空间数据的遍 历方法和相应的数据表示形式角度出发，本文利用了基于区域增长的边界体素搜索策略，在 一定程度上提高重建的效率。 关键词：曲面重建移动立方体算法等值面三角剖分 江南大学硕士学位论文 a b s t r a c t w i t hi h ed e v e l o p m e n to fc o m p u t e r 孕a p h j c s ，v i s u a l i z a t i o ni ns c i e n t i f j cc o m p u t i n go b t a i n e s e x t e n s i v er e s e a r c h 锄dt h e 印p l i c a t i o ni nm a n yf i e l d s 3 ds u r f h c er e c o n s t n i c t i o ni sa ni m p o n a n t r e s e a r c hf i e l di nt h e s c t h em a r c l l i n gc u b e sa l g o r i t h mi st h em o s ti n f i u e n t i a lm e t h o do f e x t r a c t j n gi s o s u r f a c eo fas p a t i a lf i e l ds of a lt h ei s o s u 血c e ，t h et r i 柚g i l l a t i o n 姐dt h ea c c e l e r a t i o n o ft h em ca 1 9 0 r i t h ma r cs t u d i e d ，t h e nt h em c a l g o r i t h mi si m p m v e d w h e nt a k i n gt h ed j r e c t i o ni i t e l e v a n tt h i el i n e a ri n t e r p o l a t i o nm o d e l ，i s o s u r f a c ei sac u b i c s 曲c e t h ei n t e r s e c t i o no ft h ei s o s u r f a c ea i l dt h eu n i tc u b eh a sm oe x c 印t i o n s b a s e d0 nt h e s e 时oe x c e p t i o n s ，t h eb j l i n e a ri l l t e r p o l a t i o no nt h es u r f a c eo r t h et r i l i n e a ri n t e i p o l a t i o ni nt h ec u b ei s d e c i d e db yt h ev a l u eo ft h ed i s c r i m i n a l l t ，t h u so b t a i n sd i 虢r e n tc u b ep a t t e mb e f o r er e c o n s t m d i o n s o m ei n s t a n c e si n d i c a t et h a t t h i sm e t h o dm a i n t a i n e dt h em o d e ls u r f a o ed h a r a c t e r i s t i cw e u a n d r c a l l yr e c o n s t m c tt h ec u e ds u r f a c em o d e l 1 1 l ep a p e ra l s ou s e st h et r i a n g i i l a t i o nt e c h n o l o g yt oi m p m v el h em ca 1 9 0 r i t h m ，t h e nd o a d 印t i v et r i 柚g l l l a t i o n0 nt h e 鲥d 1 1 l e “i n t e r s e c t i o n ”i sc o n s i d e r e d 勰n e wp o i i l t ，t h e no f i 百n a l 鲥d m o d e lc h a r a c t e r i s t i ci n f o 册a t i o nj sr e t a i n e dw e l l b u tt h er c n d e 血ge 伍d e n c yi sr e d u c e d t 1 l e n b o u n d a r yc i l b es e a r c hs t r a t e g yw h a tb a s e do nt h er e 百o ni n c r e m e n t a li su s e dt oa c c e l e r a t et h e a l g o r i t l l m ，a n dt h ee f e i c i e n c yo ft h er e c o n s t 兀l c t i o ni se n h a n c e di nac e n a i ne x t e n t k e yw o r d s ：s u r f a c er e c o n s t m d i o n ，珂a r c h i n gc i l b ea l g o r i t h m ，i s o - s u 面c e ，t r i a n g i l l a t i o n 1 i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 墨毽垡日期：础年月心日 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规 定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名：墨焦鱼导师签名汐冱牲 日期：沙j 年j 月心日 第一章绪论 1 1 科学计算可视化简介 第一章绪论 科学计算可视化( s u a l j z a t i o ni s c i e n t i 血c o m p u 咖g 摘写为s c ) ( 简称可视化) 是计 算机图形学的一个重要研究方向，是图形科学的新领域。科学计算可视化的基本含义是运用 计算机图形学或者一般图形学的原理和方法，将科学与工程计算等产生的大规模数据转换为 图形、图像，以直观的形式表示出来。它涉及计算机图形学、图像处理、计算机视觉、计算 机辅助设计以及图形用户界面等多个研究领域，已成为当前计算机图形学研究的重要方向。 1 1 1 科学计算可视化的概念 科学计算可视化这一术语是在1 9 8 7 年由b h m c c o 咖i c k 等根据美国国家科学基金会召开 的“科学计算可视化研讨会”的内容撰写的一份报告中正式提出的。会议认为，“将图形和图 像技术应用于科学计算是一个全新的领域”，“科学家们不仅需要分析由计算机得出的计算数 据，而且需要了解在计算过程中数据的变化情况，而这些都需要借助于计算机图形学及图像 处理技术”。会议将这一涉及到多个学科的领域定名为“s u a l i z a t i o ni ns d e n t i f i cc o m p u 血g ”， 简称为“s c i e n t i f i cv i s u a i i z a t i o n ”。 直观地讲，科学计算可视化【1 】是研究如何把科学数据，无论是通过计算还是通过测量获 得的数值，或是从卫星传送回来的图像，或是医学c t ( 计算机层面x 射线照相) 和m r j ( 核” 磁共振成像) 转换成可视的、能帮助科学家理解的信息的计算方法。简言之，科学计算可视 化是把计算机图形学与图像处理技术应用于计算科学的学科，这里所谓的计算科学是指所有 应用计算机从事计算的科学与工程学科。 以上我们更多地谈到的是数据的可视化( d a t av i s u a l i z a t i o n ) 。习惯上，人们讲许多种类 的数据也广义地称为信息或者知识。一般认为，数据( d a t a ) 、信息( m f o m a t i o n ) 和知识 ( k n o w l e d g e ) 还是有区别的。为明确起见，下面的介绍限定于狭义的数据的可视化，即将抽 象的数字或者字符表示转换成图形图像的技术( 信息可视化和知识可视化，被认为是数据可 视化的进一步发展，本文暂不涉及) 。 1 1 2 科学计算可视化的过程 在科学研究领域，研究的主要目的是理解自然的本质。科学家要达到这个目的，要经过 从观察自然现象到模拟自然现象并分析模拟结果的过程。在分析实验结果的过程中，可视化 是一个十分重要的辅助手段。可视化的过程1 2 】可进一步细化为以下四个步骤： ( 1 ) 过滤：对原始数据进行预处理，可以转换数据形式、滤掉噪声、抽取感兴趣的 数据等： ( 2 ) 映射：将过滤得到的数据映射为几何元素，常见的集合元素有：点、线、面图 江南大学硕：l 学位论文 元、三维体图元和更高维的特征图标等； ( 3 ) 绘制：几何元素绘制，得到结果图像； ( 4 ) 反馈：显示图像，并分析得到的可视结果 可视化的上述四个步骤是一个周而复始的循环迭代的过程。 1 1 3 科学计算可视化处理的数据 科学计算可视化技术处理的对象是科学数据，这些科学数据的来源是多种多样的，数据 中包含的科学规律和现象有很多。这些科学数据都是离散的采样数据，他们有很多属性，主 要有：来源、维数、定义域的维数、组织形式、时间特性以及数据量等等；数据的维数表示 标量数据、向量数据及高维的张量数据等；数据定义域的维数分为一维、二维、三维数据等； 数据的组织形式分为有网格数据和无网格散乱数据，有网格数据的组织形式也不一样，图1 1 给出了一些二维网格的组织形式，这些二维网格的处理由易到难。 口口圈陋 1 、均匀网格结构化数据2 、规则网格结构化数据3 、矩形网格结构化数据4 、不规则网格结构化数据 踊圆圈硒 5 、分块结构化数据 6 、非结构化数据7 离散点集8 混和体数据 图1 1 数据场网格分类 1 1 4 科学计算可视化技术的分类 由于可视化是针对数据进行的，因而对可视化技术的分类方法，实质上是对可视化数据 集的一种分类技术。 研究可视化技术分类的方法有好几种【1 】，最先是由b e r g e r s o n 和g r i n s t e i n 提出了基于网 格方式的：分类方法，其中表示了具有n 维数据的k 维网格。网格的维数表示了数据的 阶：零维网格是一无序点集，一维网格是一个以为有序的数据点集，二维网格表示了一个二 维有序的数据点集，这种分类是面向数据的分类。 b m d l i e 将该技术更向前推进了一步，认为数据模型比数据分布方式更为重要，提出了由 标量、矢量、张量等数据类型建立的分类体系。用e 来表示数据元素的类型，它强调了数据 模型是分类的基础，而非数据本身。这两种方法各有特点，前者更强调数据的分布方式，它 能区分随机采样的点数据和网格分布的点数据，但却无法区分一个二维矢量与一对无关的标 量，无法分清独立变量与依赖变量。从可视化技术分类的角度出发，后者更清晰更易理解。 所以本文下面的分类采用b m d l j e 的分类方法。 一2 第一章绪论 b r o d l i e 采用的方法是将数据场当作多变量函数对待，根据数据集中独立变量的个数和依 赖变量的类型建立函数相关性，由此对可视化技术进行分类。采用函数类型为主分类，如标 量场、矢量场、张量场等；将定义域维数作为次分类，如一维标量场、二维标量场等。 1 2 三维表面重建技术 三维表面重建是可视化技术等领域中的经典研究主题，其研究在最近几年形成了热潮 p 】1 4 】。通过各种传感器，计算机可以获取外部世界中物体的某种信息，称之为采样数据。从曲 面上的部分采样信息来恢复原始曲面的几何模型，称为曲面重建。重建的任务就是要从获取 的采样数据中恢复物体的三维物体结构，即物体的原型。重建从本质上说是个逆问题。 在精致的轿车车身设计或人脸一类雕塑曲面的动画制作中，常由油泥制模，再作三维型 值点采样。在医学图像可视化中，也常用c t 切片来得到人体内脏器表面的三维数据点。不 同的领域，所用的传感器不同，所得到的数据种类不同，重建的目标也不一样，因此造成重 建方法的多样化。根据不同的标准，我们可以对重建技术进行相应的分类。 1 2 1 体绘制和面绘制 三维空间规则数据场的可视化算法根据问题的要求和数据的特点大致可分为两类 一类是体绘制【5 】，它直接由三维数据场产生屏幕二维图像。这种算法产生的图像，可以 包括每一个细节，具有图象质量高、便于并行处理等优点，但其计算量大、计算时间长。体 绘制算法的典型代表是光线投射法( r a y 一蕊t i n g ) f 6 】1 7 】和足迹表法( f 0 0 t p r i n g 或s p i a t 廿n g ) 9 1 。 光线投射法和足迹表法的改进就是错切一变形( s h e 小w 叩) 法，该算法由g g c a m e m n 和p i 五c m u t e 等人于1 9 9 2 年提出，原理是将三维数据场的投影变换分解为三维数据场的错 切( s h e a r ) 变换和二维图像的变形( w a r p ) 两步来实现，从而将三维空间的重采样过程转换 为二维平面的重采样过程，大大减少了计算量。这是目前被认为软件实现速度最快的种体 绘制算法i l 。 另一类是面绘制i l ，即在原始三维数据中抽取一个或多个等值面。面绘制适用于有完整、 光滑外表面的体数据的三维重建，但不能反映整个数据场的全貌及细节。面绘制的最大特点 是采用曲面造型技术，生成数据场等值面的曲面表示，再采用面光照模型计算出绘制图像。 从结果图像的质量上讲，体绘制优于面绘制，但是从交互性能和算法效率上讲，至少在 目前的硬件平台上，面绘制还是要优于体绘制的，这是因为面绘制采用的是传统图形学的绘 制方法，现有的交互算法、图形硬件和图形加速板能充分发挥作用，因此面绘制仍发挥着较 大的作用。 江南大学硕士学位论文 1 2 2 体素级和切片级重建算法 从三维体数据中重建三维物体的方法很多，但从重建过程处理的基本元素的级别上来分， 可以把这些方法分成两大类： 体素级重建方法【1 2 j 【1 3 】f 1 4 】：体素级重建方法首先要确定物体表面在每个体素内的小面片， 然后将这些小面片连接起来就构成了物体的表面。 切片级重建方法【1 5 】f 1 6 】：切片级重建方法则是从一组平面轮廓重构通过这些轮廓的曲面。 当原始图像的分辨率很高时，体素级重建方法比切片级重建方法更可靠、更有效；而当 原始图像的分辨率很低时，体素级重建方法的重建精度也很低，这时切片级重建方法能够比 较好地构造出光滑的表面。 总体来说，体素级重建方法相对比较可靠，因为它只需要保证各个小面片之间的拓扑一 致性，不需要考虑总体的拓扑关系，但重建的结果却产生大量的小面片，占用大量的存储空 间，即使对于几何结构非常简单的物体也是如此。而切片级重建方法可以实现大幅度的数据 压缩，但轮廓对应存在着多义性，特别是在出现分叉情况的时候使得轮廓对应问题的不确定 性更加严重。 为了提高等值面生成的精度，体素被认为是由相邻层对应八个采样点组成，针对这种体 素表示，出现了以移动立方体算法( m a r c h i n gc u b e s ，以下简称m c 算法) 为代表的单元内 的等值面抽取方法。m c 算法是最有影响力的体素级重建方法，也是面绘制中的典型代表， 是本文的主要研究内容，将于下面具体介绍。 1 3 移动立方体算法的概念及研究现状 传统的m c 算法的基本思想是逐个处理数据场中的立方体( 体单元) ，分类出与等值面相 交的立方体，采用插值计算出等值面与立方体边的交点。根据立方体每一顶点与等值面的相 对位置，将等值面与立方体边的交点按一定方式连接生成等值面，作为等值面在该立方体内 的一个逼近表示。 在这个算法中首先要给定一个阈值。对于这个值一些体单元被分在等值面的两侧，而另 外一部分则与等值面相交。体单元的8 个顶点中被值面分隔的情况一共有2 “8 即2 5 6 种，由 于立方体单元具有顶点状态翻转对称性( 即大于等值面值的点与小于等值面值的点相互替换， 其等值面的拓扑结构不变) 和旋转对称性( 即旋转后，其等值面的拓扑结构不变) ，根据旋转 对称性和互补对称性，简化为1 5 种【1 7 l 【1 8 1 ，本文将在第二章中详细介绍。最初的m a r c h i n gc u b e s 算法不能保证三角片所构成的等值面的拓扑一致性，会造成等值面上出现孔隙。m j d u r s t 首先提出了m c 算法中的二义性，后来许多人在l o r e n s e n 方法的基础上做了许多改进。 传统的移动立方体算法构造的三角面片是待求等值面的近似表示，在确定立方体内三角 剖分模式后，就要计算三角片顶点位置。当三维离散数据场的密度较高时，即当体单元很小 时，可以假定函数值沿体单元边界呈线性变化，这就是m c 算法的基本假设。因此，根据这 一基本假设，可以直接用线性插值计算等值面与体单元边的交点。l o r e n s e n 曾指出采用高次 第一章绪论 插值并不比线性插值在精度上有所改进。 n i e l s o n 【2 0 】提出了基于沿立方体表面进行双线性插值的渐进线决策法，利用了立方体表面 上的顶点的分离还是连接性，需要将立方体与等值面相交的情况在原先1 5 种基础上增加到 1 9 种。等值面与体单元相交得到一系列的二次曲线，但是遇到二次曲线为一对直线的特殊情 况时，这种方法构造的逼近等值面不连续。 m a t v e y e v 【2 1 l 进一步讨论了内部二义性问题，利用沿体单元对角线的三重线性插值来解决。 n a t a r a j a n 【2 2 j 分析了双重线性插值模型及在体单元内部进行三重线性插值的思想。 对m c 算法的理论研究一直是三维物体表面重建领域中的研究热点，这几年在国际图形学 会议以及i e e e 刊物上有多篇文章对此进行报告。 a d r i a n ol o d e s 和k e nb r o d l i e 【1 8 】改进了三重线性插值模型重建等值面的正确性和精确 性，提高了重建的效率，并且保证了三重线性插值的拓扑性质的正确性。 g r e g o r ym n i e l s o n 通过三重线性插值得到了等值面的逼近三角片，分析了三重线性 插值等值面的特点并对其进行了分类，并改进了移动立方体算法。 g r e g o r ym n i e l s o n 【2 4 】研究了移动立方体算法生成等值面的参数化理论，提出了基于曲 线弦长参数化的等值面参数化算法，并将该算法应用与几何造型和医学图像分析上，通过实 验验证了该算法的有效性。 1 4 本文研究课题 1 4 1 论文范围 本文主要讨论等值面生成算法中的经典算法一移动立方体算法，对该算法的理论及其 应用进行研究。该算法用于三维物体表面重建中等值面生成，本文研究的是三维空间规则数 据场的可视化中的面绘制。本文不讨论如何从实物扫描获取点模型，也不讨论将采样得到的 数据进行匹配等前期处理过程，进行等值面生成时候用到的点模型几何是前期处理过的，并 不是原始扫描获得的数据。 1 4 2 主要工作 本文主要研究工作是建立在前人对三维物体表面重建技术的探讨基础上的，本人所做的 主要工作如下： 分析了当前m c 算法的主要步骤，综合分析其他算法，分析了该算法的优缺点，并给 出了具体的实现过程。 从三重线性插值问题入手，通过分析三重线性插值生成的等值面，得出了等值面的一 些特点，重点讨论了等值面与边界体单元的交线的两种例外情况，并将这两种例外考 虑进入算法的具体实现中。实验验证了算法的有效性及正确性。 就剖分问题进行拓展，讨论了基于三角剖分的改进m c 算法的原理及实现，引入“耳” 江南大学硕士学位论文 和“耳尖”的概念，解决连接上的二义性问题。对于生成的非平面多边形，对三角剖 分进行优化。最后实现基于改进移动立方体算法实现的三维物体表面重建系统，达到 了预期研究目的。 1 4 3 内容组织 各章节内容分布如下： 第一章是绪论，主要介绍了课题的相关背景。我们从概念、过程、处理数据、应用以及 意义这几个角度首先介绍了科学计算可视化技术。然后结合b m d l i e 的可视化分类方法介绍了 三维物体表面重建，同时引出本文所要解决的问题，即研究移动立方体算法中存在的若干问 题。我们列举了近年来在三维物体表面重建中表面拟合算法的研究方面国内、外已有的相关 工作，分析了它们的特点，并初步提出了本文的观点。 第二章分析了等值面生成中经典算法一移动立方体算法。我们首先介绍了等值面生成 的相关概念，介绍了几种典型的基于体素的等值面绘制方法，并介绍了移动立方体算法的实 现原理，分析了该算法的优缺点，并给出了该算法的一些拓展。 第三章研究了移动立方体算法中三重线性插值，对三重线性插值生成的等值面进行了分 析，分析了等值面的一些特点，重点讨论了等值面与边界体单元的交线的两种例外情况，基于 这两种情况，我们给出了改进算法，最后我们通过实验验证了改进算法的可行性。 第四章探讨了移动立方体算法中的交点的连接和多边形的生成以及三角剖分中的具体实 现以及改进，首先分析了该算法中的交点连接问题，引入“耳”和“耳尖”的概念，解决连 接上的二义性问题，从而更好地生成多边形；对于生成的非平面多边形，对三角剖分进行了 优化，以此改进了移动立方体算法，本文实现了此算法，给出了实验结果。 第五章是结论，同时介绍了今后需要进一步完善的工作。 第二章等值面构造m c 算法 第二章等值面构造m c 算法 在三维物体表面重建中，等值面构造是从体数据恢复物体三维几何描述的常用方法之一。 一个适当定义的等值面可以代表某种物体的表面( 在假设“不同物体含有不同物质”成立的 情况下) 。最早的体素级重建方法叫立方体法( c u b e r i l l e ) ，它是用边界体素的六个面拟合等 值面，即把边界体素重相互重合的面去掉，只把不重合的面连接起来近似表示等值面，但效 果不佳。而l o r e n s e n 等人【17 】于1 9 8 7 年提出的移动立方体法( m c ) 是最有影响力的等值面构 造方法，它的提出提供了一种精确地定义体素及其体素内等值面的生成方法，一直沿用至今。 这也是近年来等值面生成算法的主要研究方向。 本章首先简要介绍体素模型以及等值面的相关知识，然后介绍了移动立方体算法的基本 原理以及算法步骤，接着分析了m c 算法的特点以及它的变形，最后结合实例，给出了m c 算 法的具体应用。 2 1 体素模型与等值面定义 2 1 1 体素模型 m c 算法提出后，体素被定义为相邻层之间八个网格点组成的数据单元，每八个相邻的采 样点所定义的立方体区域就构成了一个体素。它提供了一种更一般化的体素定义，由于本文 讨论的是一个体素级重建算法，所以我们首先来介绍一下体素模型。 在图2 1 ，我们介绍两种体素模型：方向无关的三线性插值模型( 图a ) 和方向有关的三 线性插值模型( 图b ) 。 r h f 、 一 6 ，7 8 _ i a 巩 厂 名7 。 、 毋 ，l 。 f ， ， 岛 血 ，7 e 上 名7 厂岛 、 ， a ) 方向无关的三重线性插值模型 b ) 方向有关的三重线性插值模型 图2 1 体素单元模型 在三维空问的某一个区域内进行采样，若采样点在x ，y ，z 三个方向上的分布是均匀的，采 样间距分别为缸，缈，z ，则体数据可以用三维数字矩阵来表示，即5 ( f ，t ) 。 江南大学硕士学位论文 每八个相邻的采样点所定义的立方体区域就构成了一个体素，而这八个采样点称为该体 素的角点，坐标分别为( f ，七) ，o 十1 ，j ，t ) ，( f + 1 ，+ 1 ，七) ，( f + 1 ，f + 1 ，七) ，( f ，t + 1 ) ，( f + 1 ，女+ 1 ) ， ( f ，+ 1 ，七+ 1 ) ( f + 1 ，+ 1 ，七+ 1 ) 。对于体单元内的任一点，其值只能从体单元的八个角点的采样 值来估算。 对于体素内任一点p 。= ，y ，z ) ，其物理坐标可以转换成图像坐标( f 。，。，k ) ，其中 乇= 素，。= 古，七。= 古。 我们采用方向无关的三线性插值作为体素模型时，其值可以表示为 5 p 6 ) = s ( p 4 ) o + 1 一f 6 ) + 5 ( p ；) 。0 6 一f ) ( 2 1 ) 5 ( p 。) = 5 ( p o ) + ( j + 1 一j 6 ) + 5 ( p 3 ) ( j 6 一j )( 2 2 ) s ( p ，) = 5 ( p ，) ( j + 1 一j 。) + 5 ( p 2 ) ( j 。一j ) ( 2 3 ) 而s ( p 。) = 5 ( f ( 甩) ，( 以) ，七) ( 七+ 1 一七。) + s ( f ( 刀) ，( 甩) ，七+ 1 ) - ( 七。一七) ( n = o ，1 ，2 ，3 ) ( 2 4 ) n 皇0 1 n = 2 3 胁芝 s o ，y ，z ) = 扭d ，z + 6 _ 砂+ o 亿+ d 及+ 甜+ 痧+ 肜+ i l 其中口，6 ，c ，d ，p ，g ， 为常数，由体单元的八个角点值唯一决定， 性插值的组合，结果与这三个一维线性插值的顺序无关。 ( 2 5 ) 三重线性插值是一维线 如果我们采用方向有关的三线性插值作为体素模型时，对于体素面上的点，和方向无关 的三线性插值一样，其值由该店所在的面上的四个角点值的双线性插值确定。而对于体素内 的任意一点，经过它沿着某个给定方向所做的直线将与体素的表面交于两点，该点的值就是 关于这两个角点上的值的线性插值l 吲。因此，这两种插值模型在体素的面上是相同的，而在 体素内是不同的。 2 1 2 等值面定义 等值面是空间中所有具有某个相同值的点的集合。以方向无关的三线性插值模型生成的 等值面可以表示成： 昂s o ，_ ) ，z ) j f 0 ，y ，z ) = c ) ， c 是常数( 2 6 ) 当然，并不是每个体素内都有等值面。当体素的八个角点都大于c 或者都小于c 时，它 内部不存在等值面。只有那些既有大于c 的角点又有小于c 的角点的体素才含有等值面，我 一8 - 第二章等值面构造m c 算法 们称这样的体素为边界体素。等值面在一个边界体素内的部分称为该体素内的等值面片。 等值面是个三次曲面，一般意义上，它与边界体素面的交线是一条双曲线，并且这条 双曲线仅由该面上的四个角点决定。但是存在某些特殊情况，我们将在第3 章中详细讨论。 这些等值面片之问具有拓扑一致性，即它们可以构成连续的无孔的无悬浮面的曲面( 除非在 体数据的边界处) 。因为对于任何两个共面的边界体素，如果等值面与它们的公共面有交线， 则该交线就是这两个边界体素中等值面片与公共面的交线，也就是说两个等值面片完全吻合。 所以可以认为等值面是由许多个等值面片组成的连续曲面。 2 2 基于体素的等值面绘制方法 基于体素的等值面绘制方法始见于医学图像的可视化研究中，因为医学图像均由三维正 交的正六面体网格单元组成，我们将每个立方体单元称为体素( 如前所述) ，基于体素的等值 面绘制方法可分为c u b e r i l l e 方法、m a r c h i n gc u b e 【1 7 】方法、d i v i d i i l gc u b e 方法，其中目前最常 用的是m a r c h i n gc u b e 方法，这也是该文的重点介绍部分。 2 2 1c u b e r i l l e 算法 这是最早出现的基于体素的等值面绘制方法，即立方体法。它假设每个体素都是一个等 值立方体，等值面由体素的六个表面面元组成，因此它实现起来非常简单，当某个体素位于 等值面上时，认为它是边界体素，即对它进行绘制。典型的绘制方法有： 1 ) 距离光照算法( d i s t a n c e o i l l ys h a d i n g ) ，该方法只考虑体素到光源的距离； 2 ) 常数光照算法( c o n s t 卸ts h a d i n g ) ，取该体素所在的边界表面的中心点的法向量计算光 亮度； 3 ) 结构光照算法( c o t e x t u a ls h a d i 雎) ，其基本思想为面元上一点的光亮度不仅与该面元 的法向量有关，而且与相邻边界面元上的法向量有关： 4 ) 梯度光照算法( g r a d i e n ts h a d i n g ) ，该方法属图像光照算法，通过计算各象素的梯度得 到表面的法矢量。 如果在具有硬件深度缓存( z b u 疵r ) 功能的计算机上运行立方体法，可以由硬件完成 隐藏而消除的任务。如果以软件方式执行立方体法，在算法中必须考虑多边形的遮挡问题。 借鉴画家算法的思想，我们可以将遍历体素几何与显示合二为一，遍历体素几何相对视点采 用从后至前的次序。发现一个边界体素，就立刻显示它的六个表面面元。后显示到屏幕上去 的多边形将覆盖先显示的多边形，这样就达到消除隐藏面的目的。 立方体法的特点是算法简单易行，便于进行处理，其主要问题是出现严重的走样，显示 图像给人一种“块状”感觉，尤其在物体边界处锯齿形状走样特别醒目，而且显示粗糙，不 能很好的显示物体的细节。 江南大学硕士学位论文 2 2 2d i v i d i n gc u b e 算法 d i v j d i n gc u b e 算法即分解立方体法，该算法与移动立方体算法不同的是，分解立方体法 是以点而不是以三角片作为基本元素来构造等值面。只有当表示等值面的点的密度足够大时， 其显示图像才会呈现“实”的物体，一般要求点的密度不低于显示图像的分辨率。 d i v i d i n gc u b e 算法执行时，采用递归子分的方法，首先判断每个体素是否有等值面穿过， 如果有，则计算该体素在屏幕上的投影，若其投影面积大于一个象素，则将该体素递归分割 成更小的子体素，直到子体素在屏幕上投影区域为一个象素大小，这样就可以将该子体素作 为一个点显示在屏幕上。 对于某个预先选定的值，我们首先在体数据中寻找那些与等值面相交的体素，就是前面 我们所说的边界体素。把每个边界体素沿着三个坐标方向进一步细分成用，m ，m ，个大小相 等的子体素，分解的个数由边界体素的大小mxw 2 屿和显示分辨率r 决定。 豫= h i - 1 ，2 ，3 ( 2 7 ) 新产生的子体素的角点值由原来边界体素的八个角点值的三线性插值计算出来。根据子 体素的角点值，可以判断那些子体素与等值面相交，哪些不与等值面相交。对于那些与等值 面相交的子体素，它们的中心点就作为等值面上的点。 该方法主要用于密集数据场的等值面生成。在密集数据场中，等值面的面片很多，三角 面片面积很小，其在屏幕上的投影接近一个象素大小，由于绘制点的速度比绘制多边形快， 因而d i v j d i n gc u b e 方法可以大大加速密集数据场的等值面生成速度。 d j v i d i n gc u b e 方法的最大缺点是由于等值面是用离散的点表示的，为了保证等值面的显 示精度，必须生成最大分辨率的等值面点集或者根据视点与屏幕的相对位置动态生成等值面 点集。 对于体素的分解方法，还可以采用自适应分解法。在我们的研究工作中，我们也将研究 利用自适应分解法来提高m c 算法的执行效果。 2 2 3m a r c h i n gc u b e 算法 m a f c h i n g c u b e 算法( 移动立方体法) 是目前三维数据场等值面生成中最常用的方法。它 实际上是一个分而治之的方法，把等值面的抽取分布于每个体素中进行。对于每个被处理的 体素，以三角片逼近其内部的等值面片。每个体素是一个小立方体，构造三角片的处理过程 对每个体素都“扫描”一遍，就好像一个处理器在这些体素上移动一样，由此得名移动立方 体算法。 第二章等值面构造m c 算法 2 2 3 1 算法原理 该算法基于下述假设：即等值面穿过体素单元的方式是非常有限的，因此可根据每个体 素顶点的标量值列举出所有可能出现的拓扑情况，对每种情况建立其等值面的连接模式，存 储在索引表中，通过索引即可快速求得该体素内的等值面多边形连接模式。每个体素的等值 面模式决定于该体素八个顶点与等值面的相对位置状态。 当给定个门限值( 阈值) c ，一个边界体素内的等值面片就唯一确定了。对于一个体素， 每个顶点只有两种状态( 或者称为2 种颜色) ，如立方体顶点的数据值等值面的值，则定义 该顶点位于等值面之外，记为“0 ”；如果立方体顶点的数据值 o 臻3 ，6 g f l o 潜等值面模式 坚塑查兰堡兰堂竺堡兰 3 2 3 基于关键点的等值面模式 a d r i a i l ol o p e s 等人1 1 8 j 为了进一步改进m c 算法生成等值面的精度和稳定性，对m c 算法 生成的等值面进行了改进，他们找出了体素单元内部对等值面生成至关重要的“关键点”，这 些关键点数量不多，但是却可以表示可能发生的不同拓扑结构，当产生二义性面的时候，结 合目前最为常用的渐近线判别法，我们就可以利用关键点来决定等值面的模式。 3 2 3 1 体素表面的肩点 在基于对体素单元表面双线性插值的渐进决策法中，这些关键点为面上双曲线的肩点。 如图3 7 所示： 彳、曰为等值面与体素单元表面的两个交点 m 为舳的中点 s 为驻点 r 为双曲线的附加点 图3 7 体素单兀表面上的关键点 在双线性插值的渐进决策法中，f 为双曲线方程： f o ，_ ) ) = 叫+ k + c ) ，+ d( 3 1 1 ) 如图3 7 所示，二次曲线f o ，y ) = o 与体素单元表面的交点为爿：( 0 ，卅c ) 和 曰= ( 一6 ，0 ) 。这样，爿b 的中点m 为( 一拍，一d 2 c ) 。 根据式3 1 1 可得：c = 掣+ 6 ，f v = 甜+ c 得到驻点s = ( c ，而口) ，最终得到肩点r = ( ( 一c ) 口，( c 一6 ) 口) 。 3 2 3 2 体素内部的切点 对于三线性插值模型，利用公式3 6 ，我们可以推导出： f e = 彬+ 砂+ 出+ p 0 = 戤z + 砂+ c z + ， ( 3 1 2 ) j e = 删+ 钞+ 出+ g 当f = c = 0 ，f = 只= o ，f = ，= 0 时， 我们利用：，一工。c = 0 可以得到：哪+ 抄+ g z + = 0 ( 3 1 3 ) 可以得到切点坐标为： z = 一警，y = 一粤老，z = 7 ， 一 第三章m c 算法的等值面研究 y 满足方程 ( e d 一口g ) y2 + ( c e + 彤一匆g 一口 ) y + 0 ，一6 ) = o ( 3 1 4 ) 这样在z 方向上有两个切点。从而在三个方向上，一共有6 个切点。 3 2 4 等值面的特殊情况 以方向无关的三线性插值模型生成的等值面为一个三次曲面，一般情况下，等值面与边 界体单元的交线是一条双曲线且这条双曲线仅由该面上的四个点决定，但有两种情况例外： 1 在双线性插值模型中，双曲抛物面是一个服从双重规则的表面，它与平行于平面的所 有平面和平行于平面的所有平面都相交于一条直线。而在三重线性插值模型中，我们分析平 面x = 弓，y = ，z = ：。假定口一o ，这时，在三个平面上& 都为一条直线，并且这三条 直线两两相交。 如图3 8 所示。 图3 8 平面工= 弓，y = 一詈，z 2 上的s ，的情况 对于平面x 一詈，我们可以得到& 的表达式为： i f ( 一 ，y ，z ) = 盟尘坐鼍旦卫型型= o 同理，对于平面y 一鲁，z 一告，我们可以得到： i i f ( x ，一 ，z ) = 坐卫些巫等等旦生型盟= o m f ( x ，y ，一 ) = 生尘生生型卫生_ 旦丛业= o 这样我们就到了这三条直线。 联立i 、i i 式，由于z 一詈，y 一昔，易得z ；丛生嚣害毫手盟 所以这两条直线交于点n ( 一詈，一吾，坐号笔笔手盟) 江南大学硕= l 学位论文 同理联立i i 、式，这两条直线交于点l ( 堕鳖薏铲，一吾，一鲁) 联立i 、式，这两条直线交于点m ( 一詈，巫坠薏铲，一鲁) 这样我们得到了三条直线两两相交的交点。 在这里，我们必须保证口p 砌鲁0 ，口，一6 c 0 ，昭一c d 0 。 即保证q 0 ，口y o ，口：o z t 我们对s 【f 】的表达式迸仃整理燹形。在这里我们假设“+ c o ，叫+ d o ， + 6 * o 。我们可以得到如3 7 式所述的： i f o ，y ，z ) = ( 黜+ c ) 【( y + 警) g + 等) + 鱼兰丛笔兰第剑堕盟】 f ，y ，z ) = ( 缈+ d ) 【 + 嚣) ( z + 等) + 鱼型巡篆兰严】 f ，_ ) ，z ) = o z + 6 ) 【 + 等) ( y + 等) + 生生如笔兰严】 若使f 只力= 0 ，而在“+ c o 的情况下，则必须保证后面因子为o ， 可得：( y + 警) ( z + 等) + 坐堂苦等巡盟= o 从而当正( 功s 塑型号烹产= o 有解时，前半部分的y = 一篆警与z = 一案等 互相垂直。 对于i i 、i 有同样的性质：当( ) ，) ；鱼型堕老誊笋迎盟= o 有解_ ) ，。时，同样有两条互相 垂直的渐近线z = 一嚣等与z = 一等；当正( z ) s 堕塑譬篆产= o ，有解时，同样 有两条互相垂直的渐近线x = 一琶等与y = 一啬善。 如图3 9 所示。在每幅图中均有六条直线。记g 【f 】_ 以，口，口：，g 旷】的正负不同有不同的 情况。g 旷】c0 时等值面中存在“项链”现象，而g 陋1 o 时则不存在类似情况。 图3 9 第二种特殊情况 第三章m c 算法的等值面研究 由以上分析，我们可以得出等值面与边界体单元面交线的两种例外情况。由于这两种特 殊情况的存在，导致了在用三角形来逼近等值面的时候，在边界处等特殊情况处出现了裂纹 和孔隙。 3 3 涵盖特殊情况的m c 算法 在考虑上述两种情形下，并借鉴g m n i e l s o n 【2 3 1 中判别式对等值面连接方式的影响理论 我们对m c 算法进行了改进。 3 3 1 基本思想 我们算法的输入数据需要包含八个顶点的标量值，输出结果则是逼近这个特定体素单元 等值面的一系列三角片，大体方法与传统m c 算法相同。我们目的是要得出所有可能情形的一 系列典型模式的特征。一个确定的三角形片由每一个不同的模式决定。与传统m c 算法不同 的是，传统m c 算法考虑旋转对称性和互补对称性，我们只考虑旋转对称性而不考虑互补对 称性，使用一个三层方法： 1 对于不存在二义性的构型即d 如c 【f 】= 0 ，我们将其定义为第一层构型。在这里我 们只考虑立方体边界上顶点的连接性； 2 对于存在二义性的构型即肪c 陋】o ，我们需要进行二、三层构型的进一步讨论： 2 1 如果g 旷】：0 ，则不存在第三层构型。第二层是基于面上的双线性插值i ， 决定沿着立方体表面的顶点是否连接； 2 2 如果g 【，】一o ，则存在第三层构型。第三层构型考虑到负顶点在立方体内部 是否相连。如果g 【f 】 0 ，则负顶点在立方体内部相连，否则负顶点在立方 体内部分离。 3 对应负顶点在立方体内部相连还是分离，可以得出不同的等值面曲面； 4 通过三线性插值计算体单元与等值面的交点，此后的处理方法和现有的m c 算法 一致。 下面给出旋转对称性过程的实现： v o i ds w a p c u b e ( i n tc u b e i n d e x ，i n ta ，i n tb ) n o a th o l d 【3 】 0 ) ； f o r ( i m i - 0 ；i 3 ；i + + ) h o l d 【i 】= c i l b e s 【c i l b e h l d e x 】【a 】【i 】；