Computing Morse-Smale Complexes with Accurate Geometry
Computing Morse-Smale Complexes with Accurate Geometry
复制标题
计算具有精确几何形状的 Morse-Smale 复数
DOI：
--
复制
发表时间：
2012
影响因子：
5.2
通讯作者：
Valerio Pascucci
中科院分区：
文献类型：
--
作者：
A. Gyulassy;P. Bremer;Valerio Pascucci
拓扑技术在分析和可视化科学数据方面已经证明是非常成功的。因此，人们已经做出了巨大的努力来尽可能鲁棒和有效地计算像Morse-Smale复形这样的结构。然而，由此产生的算法，而拓扑一致，往往产生不正确的连接以及穷人的几何。这些问题可能会危及甚至使任何后续分析无效。此外，即使域网格的分辨率增加，这种技术也可能无法改进，从而即使对于高分辨率函数也可能产生不正确的结果。为了解决这些问题，我们引入了两个新的算法：（i）一个随机化的算法来计算离散梯度的标量场收敛下细化;和（ii）一个确定性的变体，直接计算精确的几何形状，从而正确的MS复杂的连接。第一种算法收敛的意义上说，平均而言，它产生正确的结果，其标准偏差接近零，增加网格分辨率。第二个算法使用两个有序遍历的功能，以整合的概率，第一个提取正确的（接近最佳）的几何形状和连接。我们提出了一个广泛的实证研究，使用合成和真实世界的数据，并证明了我们的算法的优势，与几种流行的方法相比。
Topological techniques have proven highly successful in analyzing and visualizing scientific data. As a result, significant efforts have been made to compute structures like the Morse-Smale complex as robustly and efficiently as possible. However, the resulting algorithms, while topologically consistent, often produce incorrect connectivity as well as poor geometry. These problems may compromise or even invalidate any subsequent analysis. Moreover, such techniques may fail to improve even when the resolution of the domain mesh is increased, thus producing potentially incorrect results even for highly resolved functions. To address these problems we introduce two new algorithms: (i) a randomized algorithm to compute the discrete gradient of a scalar field that converges under refinement; and (ii) a deterministic variant which directly computes accurate geometry and thus correct connectivity of the MS complex. The first algorithm converges in the sense that on average it produces the correct result and its standard deviation approaches zero with increasing mesh resolution. The second algorithm uses two ordered traversals of the function to integrate the probabilities of the first to extract correct (near optimal) geometry and connectivity. We present an extensive empirical study using both synthetic and real-world data and demonstrates the advantages of our algorithms in comparison with several popular approaches.