A Practical Approach to Morse-Smale Complex Computation: Scalability and Generality
A Practical Approach to Morse-Smale Complex Computation: Scalability and Generality
复制标题
DOI：
10.1109/tvcg.2008.110
复制
发表时间：
2008-11-01
影响因子：
5.2
通讯作者：
Pascucci, Valerio
中科院分区：
文献类型：
--
作者：
Gyulassy, Attila;Bremer, Peer-Timo;Pascucci, Valerio
Morse-Smale (MS) 复合体已被证明是从标量值数据中提取和可视化特征的有用工具。然而，大规模数据的 MS 复合体的高效计算仍然是一个具有挑战性的问题。我们描述了一种新算法和易于扩展的框架，用于计算任何维度的大规模数据的 MS 复合体，其中标量值在闭包有限和弱拓扑 (CW) 复合体的顶点给出，因此可以在各种网格上进行计算，例如规则网格、单纯网格和自适应多分辨率 (AMR) 网格。新的分而治之策略允许对 MS 复合体进行内存高效的计算，并进行即时简化以控制输出的大小。除了能够处理各种数据格式之外，该框架还支持特定于实现的优化，例如针对常规数据的优化。我们展示了所有维度上临界点抵消的完整特征。该技术可以在现成的计算机上对大数据进行基于拓扑的分析。特别是，我们展示了在具有 2Gb 内存的笔记本电脑上对 10 亿/1024(3) 节点网格的 MS 复合体的首次完整计算。
The Morse-Smale (MS) complex has proven to be a useful tool in extracting and visualizing features from scalar-valued data. However, efficient computation of the MS complex for large scale data remains a challenging problem. We describe a new algorithm and easily extensible framework for computing MS complexes for large scale data of any dimension where scalar values are given at the vertices of a closure-finite and weak topology (CW) complex, therefore enabling computation on a wide variety of meshes such as regular grids, simplicial meshes, and adaptive multiresolution (AMR) meshes. A new divide-and-conquer strategy allows for memory-efficient computation of the MS complex and simplification on-the-fly to control the size of the output. In addition to being able to handle various data formats, the framework supports implementation-specific optimizations, for example, for regular data. We present the complete characterization of critical point cancellations in all dimensions. This technique enables the topology based analysis of large data on off-the-shelf computers. In particular we demonstrate the first full computation of the MS complex for a 1 billion/1024(3) node grid on a laptop computer with 2Gb memory.