【作者】 刘强；

【导师】 蔡勋；

【作者基本信息】 国防科学技术大学 ， 计算机技术， 2011， 硕士

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

【Abstract】 Visualization has been played an important role for analyzing and processing large-scale datasets. However, visualizing large-scale datasets still suffers lots of difficulties, such as preprocessing time is too long, rendering time is too long or consuming too much space. How to realize the real-time and interactive visualization of large scale dataset has become a hot topic of visualization.In this paper, we will discuss some large-scale datasets visualization methods. Aiming at the problems of current large-scale datasets visualization, we make use of quad tree based adaptive partition and bounding box based node construction methods to improve traditional binary interval tree and BBIO tree. The theory analysis and experiments show that our approaches are much efficient for large-scale datasets visualization. The contributions and relevant work in the paper are as follows.Firstly, we introduce an adaptive quad tree partition method for binary interval tree. In large-scale datasets visualization process, fat nodes will block the pre-processing efficiency and make visualization time uncontrollable. We use adaptive quad tree partition strategy to reform the construction of binary interval tree, and it not only reduce pre-processing time but also maintain the efficiency of searching active meta-cell. The experiments demonstrate that the adaptive quad tree method is faster than the traditional construction method, and will reduce the pre-processing time almost 50%, the difference between two methods in active meta-cell searching is only less 0.2s;Secondly, we propose a BBIO tree node construction method based on bounding box. We improve the traditional low efficiency of BBIO tree construction, and leverage Span Space bounding box to reform the layout of BBIO tree nodes, the experiments proved that our algorithm is more efficient than the traditional and will achieve 20% speed up for detecting active meta-cell;Finally,for solving the problems of large-scale dataset visualization, we have combined all approaches which is proposed in this paper, and integrated all techniques to a large-scale datasets isosurface extraction framework. We defined all interfaces and model functions well-formed and design a scalable, reusable visualization frame work. At last, we analysis the framework in modern software engineering angle, and in abstract level, we complete all integration work for our framework, and have built an excellent large-scale datasets visualization software framework.更多还原