基于SpanSpace划分的海量数据等值面提取算法关键技术研究

论文摘要

科学计算可视化技术是分析处理海量科学数据的重要手段,目前针对海量数据的可视化仍然面临诸多难题,如需要更长的预处理时间、难于实施交互绘制等问题,因此目前对海量数据的可视化依然是国际上的研究难点与热点。本文针对目前海量数据处理过程中区间二叉树与BBIO树存在的问题,采用自适应构建四叉树以及构建区间包围盒的方式对两种树形结构进行了改进,进一步完成了相关理论分析与实验,同时完成了海量数据处理相关算法的系统框架实现。本文的主要工作及取得的主要研究成果包括:（1）提出了四叉树自适应划分的区间二叉树节点构造算法。实践发现,对于海量数据集的meta-cell构建区间二叉树时,往往出现胖节点的情况。胖节点将严重影响海量数据预处理效率,使得预处理时间无法控制。针对胖节点问题,提出使用四叉树自适应划分的方法取代原有两次全局排序的方法,在降低了预处理时间开销的同时,保持原有最优搜索活动单元效率。通过实验证明,采用自适应划分算法构造四叉树较传统方法构造时间缩短50%左右,在搜索活动meta-cell方面与最优方法相比相差不到0.2s。（2）提出了基于节点包围盒的BBIO树构造算法。针对传统BBIO树搜索效率低的问题,采用节点内区间分组做包围盒的方式对BBIO树节点进行了重新构建,有效提高了BBIO树节点内搜索活动meta-cell的效率,实验表明改进后的节点包围盒算法比传统BBIO树算法搜索效率提升近20%。（3）设计实现了集成自适应划分区间二叉树和节点包围盒BBIO树的海量数据可视化框架。整合本文所提出的两种海量数据组织改进方法,合并相同的数据读取、meta-cell划分以及等值面提取阶段,将海量数据组织阶段抽象为对象接口,在更高抽象层次上实现了完整的海量数据可视化流程。设计依照现代面向对象软件工程原则,综合考虑系统框架的功能可扩展性、有效性和模块可重用性,设计实现了优秀的易于扩展、易于维护的海量数据可视化框架。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题研究背景
• 1.1.1 科学计算可视化
• 1.1.2 三维体可视化技术
• 1.2 国内外研究现状与发展趋势
• 1.2.1 海量数据组织与划分技术
• 1.2.2 多分辨率显示与遮挡剔除
• 1.2.3 并行绘制与图像合成
• 1.2.4 等值面提取相关技术
• 1.3 论文结构
• 1.4 论文研究成果
• 第二章 海量数据等值面提取相关技术研究
• 2.1 海量数据处理相关技术
• 2.1.1 基本处理方法
• 2.1.2 Span Space 技术
• 2.1.3 并行处理与负载平衡
• 2.2 等值面提取相关方法研究
• 2.2.1 Marching Cubes
• 2.2.2 Marching Tetrahedra
• 2.2.3 基于GPU 的等值面提取方法
• 2.3 本章小结
• 第三章 基于Span Space 自适应划分的区间二叉树构造算法
• 3.1 研究背景
• 3.2 自适应节点划分算法基本思想
• 3.2.1 区间二叉树在海量数据处理中的缺陷
• 3.2.2 自适应Span Space 划分策略
• 3.3 基于Span Space 自适应划分的区间二叉树构造算法
• 3.3.1 算法思想与基本流程
• 3.3.2 算法性能理论分析评价
• 3.4 实验结果与分析
• 3.5 本章小结
• 第四章 基于节点包围盒的BBIO 树构造算法
• 4.1 研究背景
• 4.2 BBIO 树结构的Span Space 表示方法
• 4.3 基于节点包围盒的BBIO 树节点构造算法
• 4.3.1 包围盒结构BBIO 树构造算法
• 4.3.2 包围盒结构BBIO 树搜索算法
• 4.4 实验结果与分析
• 4.5 本章小结
• 第五章 基于Span Space 划分的海量数据处理框架
• 5.1 Span Space 划分方法集成框架
• 5.1.1 Span Space 自适应划分框架结构
• 5.1.2 节点包围盒BBIO 树框架结构
• 5.2 集成框架总体层次结构
• 5.3 模块及框架软件性能评价
• 5.4 本章小结
• 第六章 总结与展望
• 6.1 工作总结
• 6.2 未来展望
• 致谢
• 参考文献
• 作者在学期间取得的学术成果