（计算机科学与技术专业论文）基于outofcore的海量数据等值面绘制技术研究与实现.pdf

国防科学技术大学研究生院硕士学位论文 摘要 可视化技术是海量数据处理与分析的重要手段。目前海量数据可视化面临许 多困难，存在预处理时间长、绘制速度慢、磁盘消耗大等问题，实现海量数据的 实时、交互可视化仍十分困难，因此该领域是国际上可视化的研究难点与热点。 本文在系统地研究与分析海量数据预处理方法、并行绘制技术及加速显示方 法的基础上，针对存在的问题，结合坐标空间划分、标量空间划分、核外数据调 度及并行绘制显示等方法，对基于数据二维划分的b b i o 树技术、基于跨度空间划 分的压缩索引技术进行了深入研究，并完成了相关算法与系统框架实现。本文的 主要工作及取得的主要研究成果包括： 1 ) 提出了加速b b i o 树节点区间检索过程的四端点算法。针对传统b b i o 树构造 算法易产生病态树形结构的缺陷，四端点算法对b b i o 树节点进行了基于重排 序的组织与管理，有效提高了b b i o 树节点内元单元的搜索效率，保证了实验 规模数据的树形结构检索时间小于0 0 0 1 秒。 2 ) 提出了基于数据二维划分的b b i o 树方法。通过对海量数据集进行坐标空间的 二维划分，使数据集的绘制显示能够适合多通道显示环境的显示需求，从而实 现海量数据高分辨率显示的目的。在绘制阶段使用间隔标记法，元单元等值面 提取时间较传统m a r c h i n gc u b e s 平均减少了2 3 。 3 ) 提出了基于跨度空间划分的压缩索引方法。针对坐标空间划分数据易造成并行 处理负载不均衡的问题，使用跨度空间划分方法分割网格标量空间，并使用并 行归并排序和全互换数据通信完成对数据的分配，有效保证了并行绘制负载均 衡。针对跨度空间划分方式存在索引结构占内存大的问题，采用压缩索引方法 实现了基于压缩结构的b b i o 树索引，与传统b b i o 树组织结构相比，索引数 据所占空问减少了4 0 。 4 ) 提出了基于立方体子元单元的二叉区间树方法。针对间隔标记法存在的性能与 等值面分布相关问题，采用立方体子元单元对元单元进行划分组织，提高了等 值面加速绘制性能。实验结果表明采用新方法绘制速度较传统m a r c h i n gc u b e s 算法平均提高了3 2 。 5 ) 结合基于数据二维划分的b b i o 树方法和基于跨度空间划分的压缩索引方法， 依照现代软件工程的目标和原则，构建了海量数据可视化框架结构，描述了完 整的包图和类结构图，明确了模块的功能，阐明了模块与模块之间的关系。框 架结构具有扩展性好、重用性强等特点。 主题词：海量数据处理，核外计算，数据划分，b b i o 树，元单元，并行绘制 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t v i s u a l i z a t i o nh a sb e e nc o n s i d e r e da sf l l l i m p o r t a n tm e t h o df o ra n a l y z i n ga n d p r o c e s s i n gl a r g e s c a l ed a t a s e t t op r o c e s s i n gl a r g e d a t a s e t ，p e o p l em u s to v e r c o m el o t s o fd i f f i c u l t i e s ，s u c ha sp r e p r o c e s s i n gt i m ei st o ol o n g ，r e n d e r i n gt i m ei st o ol o n go r c o n s u m i n gt o om u c hs p a c e h o wt or e a l i z et h er e a l t i m ea n di n t e r a c t i v ev i s u a l i z a t i o no f l a r g es c a l ed a t a s e th a sb e c o m eah o tt o p i co fs c i e n t i f i cv i s u a l i z a t i o n w ew i l ld i s c u s st h ep r e - p r o c e s s i n gm e t h o d s ，p a r a l l e lr e n d e r i n g t e c h n o l o g ya n d a c c e l e r a t e i n gr e n d e rt e c h n o l o g yi n t h i sp a p e r f o rs o l v i n gt h ep r o b l e m so fl a r g e s c a l e d a t a s e tv i s u a l i z a t i o n w ew i l lc o m b i n em a n yt e c h o n o l o g i e ss u c ha sc o o r d i n a t e s d e v i d i n g ，s c a l a rd e v i d i n g ，o u t - o f - c o r et e c h n o l o g ya n dp a r a l l e lr e n d e ra n ds oo n t h e nw ew i l lp u tf o r w a r db b i ot r e em e t h o db a s e do nc o o r d i n a t e sd e v i d i n ga n d c o m p r e s ss t r a t e g yb a s e do ns p a ns p a c ed e v i d i n gt e c h n o l o g y a tl a s t ，al a r g e s c a l e d a t e s e tv i s u a l i z a t i o nf r a m ew i l lb er e a l i z e di n t e g r a t e i n gt w om e t h o dw ep u tf o r w a r d e d t h ec o n t r i b u t i o n sa n dr e l e v a n tw o r ki nt h ep a p e ra r ea sf o l l o w s f i r s t l y ，af o u re n d - p o i n ta l g o r i t h mi sp r e s e n t e df o ra c c e l e r a t e i n gs e a r c h i n gb b i o t r e en o d e t h et r a d i t i o n a lb b i ot r e ec o n s t r u c t i n gm e t h o du s u a l l yb u i l d si l lt r e ew i t hb a d s t r u c t t h ef o u re n d p o i n ta l g o r i t h mo f f s e tt h ee f f e c to fb a ds t r u c t a n di ti sam e t h o d b a s e do nr e - s o r t i n g o fi n t e r v a l t h em e t h o dh a sr e d u c e dt h et i m eo fs e a r c h i n gt r e eu n d e r 0 0 01 s e c o n d s e c o n d l y b b i ot r e eb a s e do nt w o d i m e n s i o n a l i t yc o o r d i n a t e sd e v i d i n g i s p r e s e n t e dt or e a l i z el a r g e s c a l ed a t a s e tv i s u a l i z a t i o n t h r o u g hd e v i d i n g d a t a s e tb y t w o - d i m e n s i o n a l i t y ，v i s u a l z i t i o ni sf i tt od i s p l a yw i t ht i l e d d i s p l a yw a l l i np h a s eo f r e n d e r i n g i n t e r v a lm a r km e t h o di su s e dt or e d u c ei s o s u r f a c ee x t r a c t i o nt i m e2 3 t h i r d l y ，c o m p r e s si n d e xm e t h o db a s e do ns p a ns p a c ei sp u tf o r w a r dt os o v l et h e p r o b l e mo fw h i c hi sh a r dt ob a l a n c ew o r k l o a di nv i s u a l i z a t i o np r o c e s s i n g t h e l a r g e s c a l ed a t a s e td e v i d e db ys p a ns p a c e a n dt h r o u g hp a r a l l e lm e r g i n ga n da l l t o - a u c o m m u n i c a t i n g t h ew o r k l o a dw i l lb ea s s u r e db a l a n c e ac o m p r e s si n d e xm e t h o di s p r e s e n t e dt oc o m p r e s st h et r e es t r u c t i tw i l lr e d u c et h ei n d e xs t r u c ts p a c ea b o u t4 0 f o r t h l y ，b i n a r yi n t e r v a lt r e eb a s e do ns u b - m e t a c e l li sp r e s e n t e di np h r a s eo f r e n d e r i n g i ti sam e t h o dw h i c hr e l a t e l e s sw i t ht h ei s o - s u r f a c e ，a n dt h er e n d e rt i m ew i l l r e d u c e3 0 c o m p a r e dw i t ht r a d i t i o n a lm a r c h i n gc u b e sm e t h o d f i n a l l y ，t h ep a p e rr e a l i z e do fa l lm e t h o dd i s c u s s i n ga b o v e f o l l o w e db yt h eg o a l s a n dt h ep r i n c i p i ao fm o d e ms o f t w a r ee n g i n e e r i n g ，w eb u i l dal a r g e - s c a l ed a t a s e t v i s u a l i z i n gf r a m e ，a n di ti sas c a l a b l ea n de a s y r e u s e df r a m e s t m c t k e yw o r d s ：l a r g e s c a l ed a t av i s u a l i z a t i o n ，o u t o f - c o r e ，d a t ap a r t i t i o n ， b b i o 。m e t a c e l l ，p a r a l l e lr e n d e r i n g 第i i 页 国防科学技术大学研究生院硕士学位论文 表目录 表3 1 间隔标记法绘制元单元加速状况表( 一) 2 6 表3 2 间隔标记法绘制元单元加速状况表( 二) 2 6 表3 3 数据预处理实验结果统计表2 9 表3 4 使用b b i o 树结构进行等值面提取实验结果( 一) 2 9 表3 5 使用b b i o 树结构进行等值面提取实验结果( 二) 3 0 表3 6 使用b b i o 树结构进行等值面提取实验结果( 三) 3 0 表4 1 二叉区间树方法与传统m c 算法绘制时间表( 一) 4 1 表4 2 二叉区间树方法与传统m c 算法绘制时间表( 二) 4 1 表4 3 基于跨度空间划分的压缩索引方法预处理结果4 3 表4 4 使用压缩索引方法实现等值面绘制实验结果表( 一) 4 3 表4 5 使用压缩索引方法实现等值面绘制实验结果表( 二) 一4 4 表4 6 使用压缩索引方法实现等值面绘制实验结果表( 三) 4 4 第1 i i 页 国防科学技术大学研究生院硕士学位论文 图目录 图2 1 任务并行处理示意刚3 。9 图2 2 均匀网格中的元单元划分1 l 图2 3 数据的二维划分1 2 图2 4 数据并行处理绘制显示1 3 图2 5 数据跨度空间划分【3 6 j 1 4 图2 6 连接方式二义性示意图1 6 图2 7s o r t f i r s t 方法流程图1 3 l 1 7 图2 8s o r t l a s t 方法流程图i 引。18 图3 1 均匀网格空间在x y 平面按6 3 划分结果示意图1 9 图3 2 网格数据划分共享数据点示意图2 0 图3 3 病态的b b i o 树形结构2 1 图3 4 长方体子元单元示意图2 3 图3 5 标记单元与子元单元编号2 4 图3 6 长方体子元单元的分类2 4 图3 7 间隔标记法对各类函数的加速百分比2 7 图3 8 间隔标记法加速百分比与活动单元数关系图2 7 图3 9 间隔标记法部分实验效果图2 7 图3 1 0 相同两平面观察角度不同造成活动元单元的差异2 8 图3 1 1 各类数据占据预处理结果百分比2 9 图3 1 2 基于数据二维划分的b b i o 树方法各处理机活动元单元分布图3 l 图3 13 三角面片数目分布示意图31 图3 1 4 基于数据二维划分的b b i o 树算法绘制效果图3 2 图4 1 二路归并排序过程3 4 图4 2 元单元索引结构3 5 图4 3 全互换通信示意图【4 7 】3 6 图4 4 树节点压缩方式【3 6 】3 7 图4 5 立方体子元单元模型3 8 图4 6 立方体子元单元二叉区问树节点描述结构3 9 图4 7 二叉区间树法对各类函数的加速百分比4 1 图4 8 加速百分比与活动子元单元数目关系图4 2 图4 9 使用二叉区间树算法绘制的部分函数效果图4 2 图4 1 0 各种类型数据占预处理结果百分比一4 3 第l v 页 国防科学技术大学研究生院硕士学位论文 图4 11 跨度空问方法1 8 个处理节点绘制效果图4 5 图4 1 2 跨度空间方法1 8 个处理节点合成效果图4 5 图5 1 海量数据集可视化处理流程图4 6 图5 2 海量数据集可视化处理顶层架构4 7 图5 3 数据读写包类图4 7 图5 4 数据分发包类图4 8 图5 5 元单元处理包类图4 9 图5 6 结构化元单元包类图4 9 图5 7 图像渲染包类图5 0 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目 学位论文作者 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 日期：矽矿年7 月夕日 日期：2 刃厂年z 月歹9 日 国防科学技术大学研究生院硕士学位论文 1 1 1 科学计算可视化 第一章绪论 1 1 课题研究背景 科学计算可视化【1 ( v i s u a l i z a t i o ni ns c i e n t i f i cc o m p u t i n g ) 作为人类研究和发现 自然规律的重要手段，已成为当今研究的热门领域。科学计算可视化是运用计算 机图形学和图像处理技术，将科学计算的输出数据和其它领域通过观察测试生成 的数据转换为图形和图像，最终在屏幕上显示出来并进行交互处理的理论、方法 和技术。 科学计算可视化的概念于2 0 世纪8 0 年代末被提出，在二十多年的发展中， 随着计算机图形学和图像处理技术的不断发展，科学计算可视化由幼稚走向成熟， 可视化算法研究和系统设计方面都有很大的提高，并已广泛应用到许多科学研究 领域。当今，来自超级计算机、地球卫星、航空航天、医学扫描仪以及石油地震 勘探等应用领域的数据与同俱增，使得计算数据的可视化和计算过程的交互干预 同益成为迫切需要解决的问题。 科学数据可视化是一个复杂的过程，从最开始的与图形无关的科学数据到最 终由像素点表示的图形，需要经过一系列的处理过程，主要包括数据的生成、预 处理、映射、绘制和显示等过程。与传统计算机图形绘制技术不同的是，科学计 算可视化技术侧重的是数据绘制的准确性和易理解性。目前应用领域对科学计算 可视化的要求，不仅是显示出数据的结构和关系，还要求能够对数据集进行动态 显示，并允许用户实时交互。 1 1 2 三维数据场可视化 三维数据场可视化是科学计算可视化的核心问题【2 】。下面对三维空问数据场及 其可视化的基础问题作概要介绍。 数据类型 三维数据场可视化的数据类型主要包括标量、矢量、张量。 1 ) 标量：指可以用一个不依赖坐标系的数字表征其性质的量，如密度、温度、 质量等，标量没有方向。 2 ) 矢量：指需要用不依赖于坐标系的数字及方向表征其性质的量，如位移、速 度、加速度等。 3 ) 张量：将矢量按以坐标变换为基础的定义加以推广，即得到张量，张量可用 第1 页 国防科学技术大学研究生院硕士学位论文 于流体力学的计算中，用以表示流体微幽的微观变化。 数据分布及连接关系类型 三维数据场可视化对象主要是科学计算结果。一般情况下，科学计算仅能求 得离散的数值，很难在空间中取得连续的测量数据，所以可视化对象一般为空间 上离散的三维数据。离散数据之间的连接关系类型主要有： 1 ) 结构化数据 结构化数据是指在逻辑上组织成三维数组的空间离散数据，即空间离散数据 的各个元素具有三维数组各元素之间的逻辑关系，每个元素都可以有自己所在的 层号、行号和列号。符合这一条件的三维空间数据都称为结构化数据。结构化数 据如图1 1 ( a ) 、图1 1 ( b ) 、图1 1 ( c ) 、图1 1 ( d ) 所示。 ( a ) 均匀网格 ( b ) 规则网格( c ) 矩形网格 l 袋 ，千、 一 l 朴 ( d ) 结构网格 ( e ) 非结构网格 ( f ) 混合网格 图1 1 数据类型 2 ) 非结构化数据 非结构化数据是由一系列的单元构成的，但不能组织成三维数组，如图1 1 ( e ) 所示。此类数据单元可以是四面体、六面体、三棱柱等。此类数据常出现在有限 元分析和计算流体力学中，数据结构中必须给出每个数据点空间位置及连接关系。 3 ) 结构化和非结构化混合型数据 某些应用中须将结构化与非结构化数据结合使用，从而形成了混合型数据类 型，如图1 1 ( f ) 所示。 两类三维空问数据可视化算法 第一类算法首先由三维空间数据场构造出中间几何图元( 如曲面、平面等) ，然 后再由传统的计算机图形学技术实现画面绘制。常见的中间图元是平面片，并且 可以使用现有的图形硬件进行加速绘制。这类算法是常用的可视化算法，本文对 于海量数据集的可视化就使用此类算法。 第二类算法与第一类完全不同，它不构造中间几何图元，而是直接由三维数 据场产生屏幕上的二维像素，称为体绘制( v o l u m er e n d e r i n g ) 算法，其主要问题是 计算量很大，难于使用传统图形硬件进行绘制，计算时间较长。但近年来针对该 第2 页 国防科学技术大学研究生院硕士学位论文 类算法亦有很多加速技术，这是近年米迅速发展的一种三维数据场可视化方法。 三维数据场可视化技术的应用领域十分广泛，包括医学、气象学和地质勘探 等诸多领域。在医学领域，由核磁共振、c t 扫描等设备产生的人体器官密度场均 为三维空间数据场，对于不同的组织，表现出不同的密度值，通过从多个方面来 表现病变区域，使医生对病灶部位的大小、位置等，都有定性及定量的认识，尤 其是对大脑等复杂区域，可视化所带来的效果尤其明显。借助虚拟现实的手段， 医生可以对病变的部位进行确诊，制定出有效的手术方案，并在手术之前模拟手 术。在临床上也可以应用在放射诊断、制定放射治疗计划等。在气象领域，三维 数据场可视化技术可以将大量的天文气象数据转换为直观的图像，使预报人员能 对未来的天气做出准确的分析和预测。在地质勘探领域，利用模拟人工地震的方 法，可以获得地震岩层信息。通过数据特征的抽取和匹配，可以确定地下的矿藏 资源。由于地震数据的数据量极其庞大，而且分布高度不均匀，因而根本无法从 纸面数据做出分析。利用可视化方法对模拟地震数据进行解释，可以得到矿藏是 否存在、矿藏位置及储量大小等重要信息，大大提高地质勘探的效率和安全性。 综上所述，三维数据场可视化具有重要的研究意义，是科学技术发展的重要研究 方向。 1 1 3 海量数据可视化 随着当今科学技术的进步和计算机处理能力的不断增强，产生的科学数据量 与日俱增，对于海量数据的可视化处理是当今可视化研究的热点与难点问题。 国际上对于海量数据的具体规模尚无精确定义，但通常认为当数据规模满足 以下条件时，数据集即称为海量数据【3 j ： d 1 0 m o 其中d 表示数据集规模大小，m d 表示处理机内存容量的大小。海量数据可视 化处理的难点主要在于：对海量数据进行可视化处理所需时间难于满足需要，难 于对数据集进行实时交互式的渲染。导致这些问题的主要原因可以归结如下： 首先，虽然当今单机处理能力已经有很大发展，但相比于当前所要处理的科 学数据而言，其处理能力还远远不够，处理时间往往难于满足人们需求。其次， 对于海量数据的存储仍然存在难题。由于数据量特别巨大和内存容量的限制，在 可视化处理过程中不可能将数据全部调入内存，只能将少量数据调入内存而将大 量数据留在磁盘等外部存储设备，这样势必导致可视化处理过程中的多次i o 操 作，考虑到当前计算机存储层次体系结构以及i o 操作速度慢的事实，那么对于海 量数据进行实时交互的处理将十分困难。 海量数据一般可分为两类：一类是时变数据剿4 1 ，一类为高分辨率数据集。时 第3 页 国防科学技术大学研究生院硕士学位论文 变数据集“泛出现在各种科学与工程研究中，在生物解剖学中兴奋神经兀模拟、 气象学中的雷暴演化、空气动力学中的不稳定流场飞行器模拟实验以及地质科学 中地震波反射研究中的实验结果均使用时变数据集描述。计算流体动力学 ( c o m p u t a t i o n a lf l u i dd y n a m i c s ，c f d ) 的模拟结果是一类典型的时变数据集，该数据 集包含数百个模拟时间步，每个时间有数百力个数据点值组成，这样一次模拟结 果的数据将很容易达到百个g b 、t b 甚至p b 级规模，目前如此大规模的数据集在 各类科学实验中司空见惯。 随着显示技术的不断发展，高分辨率显示问题已经得到解决，借助多通道显示 墙技术1 5 j ，人们能够得到前所未有的图像显示精度。假设多通道显示墙中一块屏幕 分辨率为1 0 2 4 x 7 6 8 ，对于6 x 3 的多屏显示墙，其分辨率将是1 0 2 4 x 6 x 1 0 2 4 x 3 ，如 此高分辨率的显示能力为更细粒度的网格数据显示提供了条件。当某实验数据结 果网格分辨率为4 0 9 6 x 2 0 4 8 3 0 7 2 ，数据类型采用双精度浮点数时，其数据大小将 达到1 9 2 g b ，该数据规模对于当今的单机处理能力而言仍然是一种挑战。 在工程实践中，两类海量数据集通常混合出现，即时变数据集具有单时间步网 格规模大、分辨率高，模拟时间步骤长的特点。例如美国l l n l ( l a w r e n c el i v e r m o r e n a t i o n a ll a b s ) 实验室的a s c i 小组对r i c h t m y e r - m e s h k o v 不稳定性的模拟实验【6 】共 耗时9 天，使用9 6 0 个c p u 协同工作，产生了2 1 0 t b 的模拟数据。该数据集共包 含2 7 0 0 个时间步，每个时问步网格分辨率为4 0 9 6 4 0 9 6 x 3 8 4 0 ，如此大规模、高分 辨率的数据能够精确描述模拟过程，对r i c h t m y e r - m e s h k o v 不稳定性的研究将更 加精确细致，但2 1 0 t b 的数据规模对于当今科学可视化是一个新的巨大挑战。 目前对海量数据可视化的需求日益迫切，但海量数据可视化方法与技术依然有 限，因此对于海量数据可视化的研究十分必要。 1 2 国内外研究现状 随着高性能计算机能力的不断提高以及物理模型的同益复杂，计算模拟产生 的数据规模规模急剧庞大，海量数据可视化方法研究越来越为国内外所重视，近 年来己涌现出相当多的新技术、新方法用于解决海量数据可视化的难题，下面从 三个方面系统介绍国内外关于海量数据可视化的先进技术与方法。 1 。2 1 海量数据预处理技术 海量数据预处理技术是海量数据可视化的核心和难点，其目的是对海量数据 进行有效组织与管理，实现海量数据的高效访问。海量数据预处理主要包括以下 三个方面： 第4 页 国防科学技术大学研究生院硕士学位论文 数据处理 海量数据处理主要以并行处理方法为主，较为成熟的并行处理方法主要有数 据流方式、任务并行方式、数据并行以及流水线处理方式四种【3 j 。四种方法能够很 好解决绝大多数海量数据处理问题，在海量数据可视化中应用广泛。 数据集结构化 数据集的结构化目前主要分为两类，一类是基于数据坐标空间分布的划分组织 方法，一类是针对数据值空间分布的划分组织方法。基于数据坐标空间的典型方 法主要有以下几种： w i l h e l m s 等提出了空间八叉树【7 j 数据划分方式，对网格空间按空间八叉树进行 组织，提高了数据集合的访问效率。s u t t o n 和h a n s e n 对空间八叉树组织结构进行 了改进，提出了t b o n ( t e m p o r a l b r a n c h o n - n e e do c t r e e ) 幺h 织结构【8 j ，该方法应用 于时变数据场的处理，在数据预处理阶段为每时间步的数据建立一个 b r a n c h o n - n e e do c t r e e 索引结构，优化了数据在磁盘的存储结构，同时使用元单 元技术优化i o 操作，能有效提高时变数据场可视化效率。 s m o o t h 提出了基于实时处理和多分辨显示技术的四叉树【9 】数据组织方法。该 方法能实现实时交互、视点相关优化方法，在3 d 地形显示中得到有效应用，支持 地形数据网格的实时、连续显示。 l e v o y 1 0 1 提出了数据的金字塔分层组织方法，金字塔尖具有最大的数据粒度， 由上至下数据粒度逐渐减小，数据描述逐渐详尽。利用金字塔组织方法能有效加 速活动单元检测过程，且结合视点相关显示技术，能显著加速等值面提取过程。 在核外计算方面，v a l e r i o 与r a n d a l l 提出了一种层次索引结构【1 1 1 ，用于组织 核外数据、加速访问。该方法适用于海量数据集合的处理，能提高o u t o f - c o r e 算 法中i o 效率，加速有效数据在磁盘中的定位。 针对数据值空间分布的划分组织典型方法主要有以下几种： e d e l s b r u n n e r 提出二叉区间树【l2 j 组织方法，该方法将数据值划分为一系列区 间段，对区间断序列进行组织排序，形成二叉树结构，给定等值面的情况下能够 通过二叉树的访问定位区间段，从而加速提取等值面。 b b i o 树形数据组织结构【1 3 】【1 4 1 是二叉区间树方法在核外算法应用中的扩展，其 首先将数据集合划分为元单元并求取各元单元区间值，再形成树形结构。b b i o 树 形结构广泛应用于核外算法当中，是海量数据集合处理的常用方法。 数据集简化 对于海量数据的可视化，除有效进行数据组织外，另一关键技术就是对海量 数据进行有效化简，从而加速可视化过程。较为流行的包括顶点移除【16 1 ，边折叠【17 1 ， 半边折叠【1 引，三角形折叠，顶点对压缩2 0 1 以及顶点聚类【2 1 1 等。这些技术有一个 第5 页 国防科学技术大学研究生院硕十学位论文 主要的共同之处，即将输入网格的顶点集划分为顶点聚类。 简化核心是用一个顶点代替一个顶点聚类。当前基于o u t o f - c o r e 算法的化简 方法有两种：空间聚类( s p a t i a lc l u s t e r i n g ) 和表面分割( s u r f a c es e g m e n t a t i o n ) ， 这两种主要方法又可以细分为一致( u n i f o r m ) 与自适应( a d a p t i v e ) 划分两方面。 空间聚类法的聚类可以基于网孑l 连通性或者网孔的几何形状。l i n d s t o r m | 2 2 提 出了o o c s 方法，该方法扫描整个三角形网孔数据结构，并为每个三角形网孔计 算二次曲面矩阵q 。在l i n d s t o r m 的基础上，s h a f f e r 和g a r l a n d 提出了自适应划分 【2 3 1 。一致性划分法某种程度上对于网格的平移和旋转敏感，并且使用同种方法简 化网格，自适应划分法能根据网格的不同情况调整化简方法，自适应化简方法比 一致性划分法更加灵活，但实现更加复杂。 空间聚类法基于表面所占的空间的划分，而表面分割法则将表面本身划分为 足够小的单元而放入内存处理。h o p p e t 2 4 】首先提出了基于表面分割的核外化简技 术。他的方法主要应用在2 d 空间的子分规则网格地形数据中。b e m a r d i n n i 4 4 1 改进 了h o p p e 的算法策略，采用了单分辨率技术。e r i k s o n 则提出了使用静态离散多分 辨率技术应用于空间层次当中【2 5 j 。 1 2 2 海量数据绘制与显示技术 等值面提取技术研究现状 等值面提取技术在科学计算可视化中应用十分广泛，许多标量场可视化问题 都可归纳为等值面的提取与绘制，如医学图像中的三维重建，有限元分析中的标 量场分析，分子化学中的分子表面显示，地质中矿藏分布的构造等等，近年来， 等值面逼近问题受到广泛的关注并取得许多重要成果。 最为典型的等值面绘制算法是m a r c h i n gc u b e s 算法( 简称m c 算法) 口酬。该算 法使用三角面片作为中问图元的基本表达元素，由于目前显示设备都可对三角面 片进行硬件加速绘制，且m c 算法本身原理简单，容易实现，故得到了广泛应用。 但m c 算法本身亦存在问题，如等值面二义性问题、逼近精度问题、计算效率问 题等，因此新的改进算法不断被提出。 m a r c h i n gt e t r a h e d r a 算法( 简称m t 算法) 口7 j 是在传统m c 算法上发展起来的， 它将立方体剖分为四面体，在各四面体中构造等值面。这种方法不存在m c 算法 中面二义性问题和空洞问题，且构造的等值面逼近精度较高，唯一不足在于m t 算法同样存在空立方体以及不能对相邻立方体之间的共享信息重复利用的问题。 针对密度值较高的数据场而言，c l i n e 和l o r e n s o n 等提出了剖分立方体方法【2 引， 该方法提高了m c 算法和m t 算法在绘制高密度数据场时效率低下的问题，进一 步加速了等值面提取速度。 第6 页 国防科学技术大学研究生院硕士学位论文 并行绘制与显示技术研究现状 针对海量数据集存储困难的问题，p h i l i p 等提出了可视化桌面投递方法1 2 圳，建 立了远程可视化系统平台，实现了可视化服务器与用户的分离，使用户远程使用 可视化服务器以及远程办公成为可能。可视化桌面投递技术又分为原始数据投递、 几何数据投递以及像素投递三种方式，三种方法投递的内容不同，导致对于传输 带宽、传输数据大小等的要求各异，适用于不同的需求。 当前对于海量数据集的可视化大都采用并行处理绘制技术，经典的并行绘制 技术主要有s o r t f i r s t ，s o r t m i d d l e 和s o r t l a s t 方法【3 ，三种方法都基于图形绘制 流水线技术，广泛应用于海量数据集合的绘制与显示过程中。 由于海量数据往往需要进行高分辨率显示，因此国内外通常采用多通道显示 环境实现图像的高分辨率显示【5 j 。多通道显示墙是一种大尺寸、高分辨率、低成本、 高性能的可视化设备，它能将复杂的数据以图形图像的形式在高度沉浸感的显示 环境中实时展现出来，是虚拟实验室和可视化应用环境的重要组成部分。 1 3 论文结构 全文共分六章： 第一章为绪论，主要介绍论文的研究背景与意义，阐述了国内外在海量数 据处理和并行绘制显示等方面的研究现状。最后对论文工作与研究成果进 行了总结。 第二章介绍了有关海量数据处理以及并行绘制方面的关键技术。主要从海 量数据可视化方面详细阐释了o u t o f - c o r e 技术、b b i o 树技术、压缩索引 方法和s o r t f i r s t 、s o r t l a s t 等技术，给出了各项技术的基本原理及相关的 重要理论证明。 第三章对网格数据场的空间划分以及b b i o 树组织结构进行了研究。针对 传统b b i o 树构造算法容易产生病态树形结构的缺陷，提出了一种树节点 改进构造方法一四端点算法，加快了树节点内搜索活动元单元的过程； 最后使用网格数据场的空间二维划分方法做预处理方法，实现了一种海量 数据等值面绘制方法。 第四章对网格数据场跨度空间划分方法以及压缩索引方法进行了研究。提 出了将基于子元单元的二叉区间树与跨度空间划分相结合的方法，实现了 以跨度空间划分为预处理技术、以压缩索引方法为查找元单元技术、以二 叉区间树法为加速绘制技术的海量数据等值面绘制算法。 第五章对第三、第四章提出的海量数据可视化算法进行了分析，提出了一 个集成两种算法的框架结构，系统分析了两种算法的绘制流程，并以现代 第7 页 国防科学技术大学研究生院硕士学位论文 软件工程的目标利设计原则为依据，刈框架结构进行了优化，使陔算法框 架具有良好的功能可扩展性、易修改性和可重用性。 第六章为结束语。总结了论文主要工作，并对未来工作进行了展望。 1 4 论文研究成果 本文完成的主要工作和取得的主要研究成果包括： 提出了加速b b i o 树节点区问检索过程的四端点算法。针对传统b b i o 树 构造算法易产生病态树形结构的缺陷，四端点算法对b b i o 树节点进行了 基于重排序的组织与管理，有效提高了b b i o 树节点内元单元的搜索效率， 保证了实验规模树形结构的检索时间小于0 0 0 1 秒。 提出了基于数据二维划分的b b i o 树方法。通过对海量数据集进行坐标空 间的二维划分，使数据集的绘制显示能够适合多通道显示环境的显示需 求，从而实现海量数据高分辨率显示的目的。在绘制阶段使用间隔标记法， 元单元等值面较传统m a r c h i n gc u b e s 算法提取时间平均减少了2 3 。 提出了基于跨度空间划分的压缩索引方法。针对坐标空间划分数据易造成 并行处理负载不均衡的问题，使用跨度空间划分方法分割网格标量空间， 并使用并行归并排序和全互换数据通信完成对数据的分配，有效保证了并 行绘制负载均衡。针对跨度空间划分方式存在索引结构占内存大的问题， 采用压缩索引方法实现了基于压缩结构的b b i o 树索引，与传统b b i o 树 组织结构相比，索引数据减少了4 0 。 提出了基于立方体子元单元的二叉区间树方法。针对间隔标记法存在的性 能与等值面分布相关问题，采用立方体子元单元对元单元进行划分组织， 提高了等值面加速绘制性能。实验结果表明采用新方法绘制速度较传统 m a r c h i n gc u b e s 算法平均提高了3 2 。 结合基于数据二维划分的b b i o 树方法和基于跨度空间划分的压缩索引方 法，依照现代软件工程的目标和原则，构建了海量数据可视化框架结构， 描述了完整的包图和类结构图，明确了模块的功能，阐明了模块与模块之 间的关系。框架结构具有扩展性好、重用性强等特点。 第8 页 国防科学技术大学研究生院硕士学位论文 第二章海量数据集可视化相关技术研究 本章主要介绍海量数据集可视化的相关技术，包括海量数据预处理方法和海 量数据并行绘制显示技术。 2 1 海量数据集基本预处理方法 2 1 1 数据处理基本方法 目前海量数据的基本处理方法主要以下有四种： 数据流处理方法 该处理方法是最简单通用的方法，对于每个与其它数据不相关的数据集合进 行顺序读取并处理。在多数内存或缓存受限的情况下，数据流处理方法是唯一可 用的方法。该方法的优点在于，无论数据集合规模有多大，方法均能成功处理数 据集。缺点是该方法处理比较耗时，不利于数据的交互式处理，数据i 0 速度是处 理方法最大瓶颈所在，改进数据i 0 调度方法将有效提高数据流处理方法效率。 任务并行处理方法 任务并行处理方法【3 4 】是将处理数据的任务分解为多个相互独立的子任务，并 将多个子任务分配给多个处理机进行处理，如图2 1 所示。 图2 1 任务并行处理示意图【3 1 任务并行处理方法的优点在于能够充分利用多个处理机使之并行工作，从而 加速数据处理。其缺点是要将数据处理任务分解为相互独立的一系列子任务比较 难，并且分解后的子任务规模大小各异，容易造成处理机负载不平衡，降低并行 处理效率。 流水线处理方法 流水线处理方法【3 1 1 需要将整个数据处理过程分解为任务量近似的多个阶段， 上一阶段的输出作为下一阶段的输入，各个阶段始终处于工作状态，对输入的任 务依次处理。该方法的主要优点在于能充分利用当前所有的计算资源( 如c p u 、磁 第9 页 国防科学技术大学研究生院硕士学位论文 盘以及绘制加速硬件等) 。缺点是对于任务处理流水线的各阶段划分较为困难，难 以达到任务规模近似。 数据并行处理方法 数据并行处理【3 2 】过程中，各个处理机执行相同的任务，但所处理的数据不同， 各处理机并行执行任务。该方法需要对数据进行合理划分，使得各个处理机在执 行任务过程中尽量不存在相互依赖关系，从而获得更高的加速比