1绪论

1.1引言

日常生活中，可视化技术的应用亦随处可见，如气象图、三维模型等。那么何谓可视化？ 1987年，首届“科学计算中的可视化”研讨会(Visualizationin Scientific Computing，Vise)给出了完整描述[2]?该报告指出，可视化是一种计算方法，能够将数据转化为用户能够直观观察、自然交互的几何模型。可视化提供了一种展示数据隐含逻辑的手段，丰富了科学研究的方法，有助于人们深入理解数据。通俗一点、-来讲，可视化就是利用计算机创建视觉图像，将枯燥、晦湿的数据或者信息转化为简单明了的图像或者3D模型的方法。在许多领域，它已经改变了科研人员的科研方式。可视化的目标就是在充分利用现有科研方法的基础上，提供一种新的科研视角科学计算可视化是一个跨学科研究领域，是集计算机图形学、计算机辅助设计、数理统计、计算机视觉、美学等计算机及其他领域知识于一体的新兴学科。可视化技术在帮助人们感知真实世界、仿真自然现象、抽象大规模数据等方面具有显著的意义。正因如此，可视化技术广泛应用于医学图像处理、大气模拟、地球和空间科学、流体仿真等领经过近三十年的快速发展，可视化已经成为了举世公认的一门学科。从1990年开始，美国IEEE计算机学会计算机图形学技术委员会每年都会举办可视化国际学术会议。为了引导领域内的科研力量、方便同行学者交流，Chris、Christopher等人分别归纳总结了可视化研宄的主要议题。其中，Christopher将可视化的主要议题归结为基本可视化算法、标量场的等值面算法、标量场的体绘制算法、向量场的可视化、张量场的可视化、几何建模、虚拟环境、大规模数据的可视化、可视化框架、可视化中的人为因素、信息可视化等几个方面[3]。

……….

1.2课题背景

近年来可视化技术的研究取得了重大发展并得到了广泛应用。在医学领域中的应用医学图像可视化是数据可视化的重要应用之一。由于物体不同材质部分对物理射线的吸收率也不同，从而能够在乳脂胶片上成像。英国科学家Hounsfield和美国科学家Cormack成功实现了CT技术的临床应用，因而分别荣获诺贝尔医学和生理学奖。由于计算机断层扫描（computer tomography，简称CT)、磁共振（magnetic resonance imaging.简称MRI)、超声成像、正电子辖射断层成像（positron emission computed tomography，简称PET)等非损伤性扫描设备的出现及发展，医生可以很容易地获取患者病灶部位的扫描图像序列。但是，扫描所得的是二维图像，观察者很可能因受视力和知识水平的限制而人为忽略二维图像上的很多特征。另外，二维图像序列不是三维对象，观察者无法对其进行选择、缩放、错切等操作，因而难以进一步的了解被扫描物体。可视化技术中的三维重建技术打破了二维扫描序列到三维物体的限制，有效协助医生制定术前规划、实时掌握手术进度例如，三维重建技术可在脑部肿瘤放射治疗中降低对患者正常组织的伤害。因为人脑结构复杂、组织脆弱，在不幵颇的情况下，医生既无法制定最佳手术方案，也无法实时掌控手术进展，而幵顿又会对患者造成额外的伤害。在这种情况下，三维重建技术能投通过重建人脑内部结构辅助医生选择、确定最佳的顿骨穿孔位置、同位素置入通道、安放位置，从而降低手术风险。再比如，在少年儿童旳體关节矫形手术中，通过重建髓关节模型可以预先了解矫形位置，通过对髓关节模型的切割、移位、固定等操作的演练，可以縮短手术时间、提高矫形质量。

…………

2移动立方体算法与移动四面体算法的对比与评估

2.1研究目标与思路

等值面提取在标量场体数据可视化和隐函数曲面显示中具有重要应用，经典算法包括移动立方体算法和移动四面体算法，其核心是在立方体或四面体体素单元中用线性的三角面片逼近原始曲面。文中以可计算的代数曲面为例，对上述2种等值面提取算法的逼近精度、时间和空间效率等方面进行了详细的对比，为各种应用中等值面提取算法的选取提供了参考依据。对于三维标量场体数据或者隐函数，等值面是指其标量值或函数值为某一常数的点的集合。通过选择不同的标量值或者函数值，可以得到不同的等值面，从而有助于可视化和分析相关的体数据和隐函数曲面。因此，等值面提取是三维标量场数据可视化、隐函数曲面显示、三维曲面重建等应用中的基础问题。等值面提取算法的主要思想是：对于三维标量场体数据，通常是由离散体素单元集合描述；对隐函数进行空间釆样，生成基本体素单元；然后在基本体素单元内用线性三角面片逼近等值面。在科学与工程中的有限元计算，四面体和立方体是最为常用的体素单元；在各种三维医学成像设备中，如CT、MRI、PET等，通过对成像算法得到的体数据进行空间均勾立方体重采样，可以得到立方体体素数据；而在隐函数曲面显示与绘制算法中，用户可以自由选择四面体或者立方体体素单元，对隐函数所在空间进行采样。因此，根据体素单元不同，常用的等值面提取算法主要有：基于立方体的移动立方体(marching cubes，简称MC)算法和基于四面体的移动四面体算法。

…….

2.2相关工作

1986年，WyviU等首次提出了隐函数曲面旳多边形化方法，即隐函数的等值面提取算法。1987年，Lorensen等提出了经典的移动立方体方法，即移动立方体算法。该算法不仅适用于隐函数曲面的等值面提取，更适合于离散标量体数据的等值面提取。移动立方体算法根据每个立方体八个角点的标量值，在具有28个条目的查找表中进行匹配，实现立方体中的等值面的三角形逼近表示。算法实现简单，且容易改造以适应大规模并行计算。但是，在某些情况下，移动立方体算法中三角片的连接方式存在二义性Nielson等提出了移动立方体算法中二义情况下的判定方法，防止了”洞"的出现。Natarajan和Cignoni等综合考虑邻接立方体的状态，通过引入了面鞍点与体鞍点的方式，有效处理了等值面的二义性。与移动立方体算法相比，移动四面体算法实现更简单，它的査找表只对应24个状态，而且不存在二义性。传统的MT方法中，通过对立方体的进行单形剖分，获得四面体体素单元。但是，不同的单形剖分方式对于等值面结果在精度、面片数目和效率上有较大的影响此外，这种单形剖分是建立在立方体体素数据基础上的，文献没有给出在相同的釆样条件下，移动立方体算法和移动四面体算法在逼近精度和时空效率对比。

……….

3异质物体的2-流形边界面提取 ......... 31

3.1 引言.........31

3.2相关工作.........  32

3.3 BSHO 算法......... 34

3.4试验结果与讨论......... 42

3.5本章小结及研究展望 ......... 45

4基于GPU加速的2-流形异质物体边界面提取算法......... 47

4.1引言......... 47

4.2相关工作 .........47

4.3基于GPU的BSH0算法  .........49

4.4 实验结果 ......... 55

4.5本章小结及研究展望 .........57

5基于三棱柱的高效异质物体边界面重建......... 59

5.1引言.........59

5.2相关工作 ......... 60

5.3层次边界面数据结构.........  61

5.4 DA算法......... 62

5.5 实现与结果 ......... 74

5.6本章小结 ......... 80

5基于三棱柱的高效异质物体边界面重建

5.1引言

在现实世界中，异质物体随处可见。异质物体就是由多个同质部分组成的物体[118]。重建异质物体的几何表示是许多与几何相关应用技术的前提例如，各个部分清晰分隔且支持交互显示的数字肝脏模型是术前规划的基础，是手术成功的重要保证。我们在本章提出了基于三棱柱剖分的异质物体边界面重建算法。目前，重建异质物体边界面的研究工作较少。现有的算法解决重建问题时要么基于立方体体素[85]，要么基于四面体体素[]18]。但是，以上两种类型的算法都在理论上或者实际应用中存在缺陷。我们通过细分立方体生成三棱柱体素，然后从三棱柱体素中提取边界面。文中，我们提出了新的编码方法用于枚举异质三棱柱类型，通过检验每种情况下算法的重建结果来验证重建算法的有效性。按维度攀升的方式重建边界面因三棱柱的使用而成为可能。在重建过程中，算法首先生成体素边上的点，其次将点连成线，然后生成分隔三角面，最后通过精心组织这些分隔三角面得到分界面和边界面。算法因此被命名为维度攀升算法，简称Da。

……….

结论

可视化是一种以图像、表格或者动画等手段揭示数据隐含知识、逻辑的手段，是人们理解自然、认识世界的新方法。三维数据场重建是可视化技术的重要分支，是计算机图形学在工程数据可视化领域的重要应用，具有近三十年的发展历史。以等值面提取为核心的三维数据场重建技术迅猛发展，创造了巨大的经济与社会效益。例如，在逆向工程中，三维数据场重建技术可在缺少产品原始设计文档与模型参数的情况下构建几何模型，供设计师后续改良或重用；又例如在整型或者假肢外科手术规划中，三维数据场重建技术可快速建立人体组织模型，供医师估计手术方案风险。近年来，由于异质零件开始广泛应用等原因，三维数据场重建技遇到了新的挑战。与传统重建技术不同，在异质物体重建中，拓扑与材质信息相关。为了清晰地展示物体的外表与内部结构，异质物体重建不仅要求重建物体的外表面，还要求重建构成异质物体的各部分之间的分界面，并保证分界面的拓扑一致性。本文首先详细介绍了重建技术的发展、应用与现状，提出了在现今条件下重建技术存在的问题；其次提出了定量测量等值面提取精度的算法；随后，针对重建技术的不足提出了一种新的异质物体的重建算法，解决了法向计算、流形性保持等问题；接着，针对前一算法存在的效率不高、结果面片数量巨大等问题，分别提出了基于GPU的异质物体重建加速算法和基于三棱柱的异质物体重建算法；最后，对本文的工作做了总结，并提示了今后工作的方向。

…………

参考文献（略）