Efficient computation of the topology of level sets
Efficient computation of the topology of level sets
复制标题
DOI：
10.1109/visual.2002.1183774
复制
发表时间：
2002-10
期刊：
影响因子：
--
通讯作者：
Valerio Pascucci;K. Cole-McLaughlin
中科院分区：
文献类型：
--
作者：
Valerio Pascucci;K. Cole-McLaughlin
本文介绍了两种计算三维标量场等值线树的有效算法/SPL Fscr/及其用每个等值面的Betti数进行扩展的算法。等高线树是科学可视化中的一种基本数据结构，用于对区域网格进行预处理，从而以最小的开销存储空间进行等值面的优化计算。等高线树还可用于构建报告标量字段的完整拓扑特征的用户界面。本文第一部分提出了一种用线性时间内各等值线的Betti数来扩充等值线树的新方案。我们展示了如何在不增加其复杂性的情况下用Betti数计算来扩展该方案。因此，我们将以前的方法的时间复杂度从O(Mlogm)提高到O(nlogn+m)，其中m是四面体的个数，n是/SPL Fscr/区域中的顶点个数。论文的第二部分介绍了一种新的计算增广等值线树的分治算法，提高了计算效率。该方案的中心部分通过合并两棵中间轮廓树来计算输出轮廓树，并且与插值法无关。通过这种方式，我们将关于特定内插的任何知识限制在计算单个单元格的树的先知上。我们已经为三线性插值法实现了这个预言，并计划在需要时用高阶插值法取代它。该方案的复杂度为O(n+tlogn)，其中t为/SPL Fscr/的临界点个数。当t=O(n/sup 1-/spl EPSi//)时，我们第一次可以在许多实际情况下在线性时间内计算轮廓树。最后，我们报告了我们的算法的并行实现的运行时间，显示了良好的可扩展性与处理器的数量。
This paper introduces two efficient algorithms that compute the Contour Tree of a 3D scalar field /spl Fscr/ and its augmented version with the Betti numbers of each isosurface. The Contour Tree is a fundamental data structure in scientific visualization that is used to preprocess the domain mesh to allow optimal computation of isosurfaces with minimal overhead storage. The Contour Tree can also be used to build user interfaces reporting the complete topological characterization of a scalar field. The first part of the paper presents a new scheme that augments the Contour Tree with the Betti numbers of each isocontour in linear time. We show how to extend the scheme with the Betti number computation without increasing its complexity. Thus, we improve on the time complexity from our previous approach from O(m log m) to O(n log n+m), where m is the number of tetrahedra and n is the number of vertices in the domain of /spl Fscr/. The second part of the paper introduces a new divide-and-conquer algorithm that computes the Augmented Contour Tree with improved efficiency. The central part of the scheme computes the output Contour Tree by merging two intermediate Contour Trees and is independent of the interpolant. In this way we confine any knowledge regarding a specific interpolant to an oracle that computes the tree for a single cell. We have implemented this oracle for the trilinear interpolant and plan to replace it with higher order interpolants when needed. The complexity of the scheme is O(n+t log n), where t is the number of critical points of /spl Fscr/. For the first time we can compute the Contour Tree in linear time in many practical cases when t=O(n/sup 1-/spl epsi//). Lastly, we report the running times for a parallel implementation of our algorithm, showing good scalability with the number of processors.