1 绪论
1.1 研究背景及意
科学计算是一门通用学科, 是指通过计算机预测、模拟和发现自然世界的客观规律和发展过程[1], 最常见的特点是需要较大的存储量和计算量。在电子计算机出现之前, 各种科学研究和工业设计领域通过反复试验得出数据, 效率较低、成本高昂。自计算机出现后, 历经几十年时间迅猛发展, 各类复杂计算成为了可能, 通过计算机可以模拟自然界现象, 发现物理规律, 探索新的理论。科学计算实验会产生大量数据, 科学家高效地获取科学计算数据中蕴含的有用信息是一个重要的研究领域。
科学可视化(Scientific Visualization), 也称为科学计算可视化, 是通过图形和图像的形式描述原始科学计算数据的过程, 帮助科学家和研究员更好地理解数据本身、从数据中获取有用信息[1-5]。科学可视化以视觉形式展现复杂的数据, 可以提供清晰直观的大数据处理分析方法, 并且通过人类熟悉的视觉隐喻增强理解。科学数据的可视化过程可以分为二维科学可视化和三维科学可视化, 广泛使用各个领域, 比如图像处理、计算机动画、计算机视觉、信号处理、计算机图形学、人机交互和计算机辅助设计等[6]。
随着计算机硬件技术发展, 各种模拟和仿真实验产生的数据呈爆炸式增长, 高效地从数据中获取有用信息并得出结论是亟待解决的问题。单台计算机的计算能力难以满足现实需求, 基于多核和众核架构的并行计算为大规模科学计算数据可视化提供了可能。因此, 大规模科学计算数据高效并行可视化是一个重要的研究领域, 具有广泛应用前景。
........................
1.2 体可视化研究现状
1.2.1 体绘制
体可视化[6-9]是使用可交互的图形和图像从体数据中获取有用信息的技术, 与体数据的表示、渲染和操作密切相关, 是科学可视化领域最重要的研究课题之一。研究员早期通过几何图元(点、线、面)表示的方法[10]间接可视化体数据, 因此也称为间接体绘制, 或者面绘制, 如图 1-1a 所示; 但是, 这种方法对于三维的体数据本身会造成一个维度的缺失, 很多数据内部结构和特殊信息无法获取。随着体可视化技术的发展, 直接将三维体数据映射为二维图片的算法被提出, 也称为直接体绘制[11], 或者简称为体绘制, 如图 1-1b 所示。体绘制广泛应用于多个领域, 例如, 通过 MRI、CT、fM RI 或 PET 等技术获取的一个二维切片序列, 使用三维重建技术生成体数据模型, 然后使用体绘制帮助医生诊断病情并给出治疗和手术意见; 工业中的 CT 技术用于无损检测机械零件和复合材料。在计算领域, 比如计算流体力学(CFD), 模拟结果通常运行在超级计算机上, 并且通过体可视化对结果进行分析和验证。此外, 多个传统计算机几何图形学应用领域也在利用体绘制技术优势, 比如飞行器模拟过程中使用体绘制技术让流场更加真实[6]。相对于面绘制而言, 体绘制技术虽然可以向科学家传递更多的信息, 但是却增加了算法的复杂度, 因此绘制时间也随之增加。为了提升算法效率和交互体验, 大量基于软件优化和硬件加速的体绘制算法被提出。
图 1-1 飓风数据可视化: (a)面绘制; (b)体绘制
2 大规模标量场数据体可视化基础
2.1 体可视化理论基础
2.1.1 体数据
体数据是三维的, 一个典型的体数据是一个(x, y, z, v)的采样点集合, 采样点也称为体素, v 是三维空间(x, y, z)处的数据属性[6]。v 可能有多值的, 包含多个可测量属性, 比如, 颜色、密度、温度和压力等标量属性; 也可能为速度等矢量。其中, 数据属性为标量和矢量分别对应三维标量场数据和矢量场数据, 其中, 三维标量场数据体可视化是本文的重点研究内容, 矢量场数据通常也可以计算矢量模长, 用三维标量场数据可视化的方法处理。体数据也可能是时变的, 此时, 数据集会增加一个时步维度, 可看做是一个(x, y, z, t, v)的采样点集合, 其中, t 表示时步信息。
一般来讲, 体数据采样点分布在空间中的随机位置, 但是, 大多数情况下, 体数据集具有各向同性, 即采样点沿着三个正交坐标轴均匀间隔, 如图 2-1a 所示。因此, 这类体数据被定义为均匀网格, 用一个三维数组 A 存储, 其中, 数组元素的位置表示网格中采样点的位置, 即 A[x, y, z]表示空间(x, y, z)处的采样值。此外, 线性网格(图 2-1b)、曲面网格(图 2-1c)、不规则网格(图 2-1d)也常用于描述三维数据场。在线性网格中, 网格单元沿坐标轴对齐, 但是沿着坐标轴的网格单元间隔是任意的。当线性网格保留拓扑结构进行非线性转换会变成曲面网格, 通常, 定义线性网格的空间称为计算空间, 定义曲面网格的空间称为物理空间[6]。不规则网格是一系列单元的集合, 单元之间的连接关系显式指定, 其中, 网格单元形状可以是任意的, 比如四面体、六面体、棱柱等。不规则网格数据体绘制算法是本文研究重点。
(a) 均匀网格 (b) 线性网格
2.2 大规模标量场数据并行体可视化理论基础
2.2.1 并行计算
随着计算机硬件和存储技术发展, 大量并行计算机和系统开始出现。同时,各种计算模拟和仿真实验的规模和精度要求提高, 传统单机串行处理难以满足需求, 因此, 并行计算[23-27]开始广泛应用。并行计算是指大量的计算任务和处理器指令同时执行, 大规模问题被分解为可以同时执行的小问题。
并行计算在高性能计算领域长期使用, 但是物理因素限制了频率缩放, 因此,引起了研究者广泛关注。并行计算已经成为计算机体系架构中的重要范例, 主要是以多核处理器的形式出现。并行计算与并发计算紧密相关, 尽管两者截然不同, 容易混淆, 但是经常一起使用。在并行计算中, 一个计算任务通常被划分为多个相似的子任务, 这些子任务可以独立处理, 并且在计算完成后将结果合并; 相反, 在并发计算中, 不同的进程通常不解决类似的问题, 当它们这样做时, 单独的任务可能具有变化的性质, 并且在执行过程中需要进程之间通信。
并行计算机可以根据硬件支持并行性的级别进行分类, 其中, 多核和多处理器计算机在单台计算机上具有多个处理元素; 而集群、MPP 和网格使用多台计算机完成同一个任务; 专用并行计算体系架构有时与传统处理器混用, 以加速特定的计算任务[26-27]。
并行计算可以分为: 按位级、指令级、数据/任务级并行[23]。按位级并行是指增加处理器字长的并行计算形式; 指令级并行是计算机处理器可以同时处理多条指令; 数据/任务级并行是并行程序的特征, 即可以对相同或不同的数据执行完全不同的计算。其中, 按位级和指令集并行对程序员是透明的, 但是, 显示的并行算法(尤其是使用并发的并行算法)比串行的算法更难设计, 因此并发引入了几种新的软件漏洞类型, 其中竞争条件最为常见。
............................
3 基于线程并行的体绘制算法研究.....................25
3.1 并行可见性排序算法.....................25
3.2 并行四面体投影分类与拆分算法.....................25
4 基于进程并行的体绘制算法设计与实现.....................30
4.1 并行数据分割算法实现.....................30
4.1.1 KD 树理论基础.....................30
4.1.2 并行 KD 树体数据分割算法.....................30
5 松耦合的 C/S 并行体可视化系统设计与实现.....................45
5.1 系统需求分析....................45
5.1.1 背景及用途....................45
5.1.2 功能需求....................45
5 松耦合的 C/S 并行体可视化系统设计与实现
5.1 系统需求分析
5.1.1 背景及用途
体绘制是标量场数据可视化的重要方法, 用户通过体绘制结果可以观察数据体内部结构, 并从中获取有用信息。随着各种科学计算和仿真实验精度要求越来越高, 产生的体数据规模呈指数级增长。因此, 高效获取海量体数据中有用信息, 帮助科研人员更好地了解数据规律是亟待解决的问题。 此外, 由于体数据规模过于庞大, 单个处理器计算能力有限, 不能满足大规模数据体可视化需求。因此, 基于多处理器的高效并行体可视化系统设计与实现在科学计算与仿真研究领域具有广阔的应用前景。
5.1.2 功能需求
体绘制算法通过传递函数, 将标量场数据中的物理属性映射为可见的颜色和透明度。对于一个友好的体可视化系统, 支持体绘制结果交互(旋转、平移和缩放)的同时, 还需要提供传递函数修改的接口, 用户可以动态改变传递函数映射, 并及时获得反馈结果。
5.1.3 性能需求
体绘制是非常耗时的算法, 以及系统面向大规模标量场数据体可视化, 对于性能要求非常高。本文系统高效可视化大规模标量场数据的同时, 还要求对体绘制结果可以实时交互, 因此, 需要对系统性能进行多方面优化工作, 提供良好的用户体验效果。
............................
6 总结与展望
(1) 本文总结
三维标量场数据体可视化一直是科学可视化领域的重点研究内容, 在计算流体力学、医学影像、气象气候学等领域有广泛的应用前景。随着科技发展, 各种科学计算与仿真实验产生的体数据规模越来越大, 给体绘制领域发展带来了新的挑战。本文重点研究了大规模标量场并行体可视化技术, 首先, 研究并实现了基于 OpenMP 线程并行的投影四面体算法, 用于非结构网格体绘制, 充分利用了多核处理器的计算资源; 然后, 设计并实现了基于MPI 进程并行的体绘制算法, 解决大规模标量场数据体绘制问题; 最后, 设计并实现了松耦合的 C/S 并行体可视化系统, 支持体绘制交互和传递函数修改。此外, 还使用图片压缩技术降低了C/S 通信开销, 以及传递函数延时更新方法和两层 LOD 模型提升交互体验
(2) 展望
本文在大规模标量场数据体可视化技术上展开研究, 取得了部分成果, 但还有值得优化的地方, 主要体现在如下四个方面：
在基于线程并行的投影四面体算法设计方面。首先, 所有四面体网格处理完毕后再一次性载入显存光栅化, 当网格量较大, 顶点数据将会极大占用CPU/GPU 内存, 下阶段应研究分批将顶点数据载入显存, 减少内存占用; 然后, 线程并行投影多边形分类/拆分算法中构造了额外的顶点填充顶点数组, 虽然这些顶点不会影响最终可视化结果, 但是会增加 CPU/GPU 内存和数据传输开销, 下阶段研究中应确保正确绘制结果的前提下移除这些顶点数据; 最后, 本文根据深度信息计算四面体单元可见性顺序, 这是一种近似的排序, 未来应该研究更加高效和精确的并行可见性排序算法, 进一步提升算法效率和准确度。
参考文献（略）