Efficient computation of the topology of level sets

This paper introduces two efficient algorithms that compute the Contour Tree of a 3D scalar field ℱ 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 ℱ. 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 ℱ. For the first time we can compute the Contour Tree in linear time in many practical cases when t=O(n^1-ε). Lastly, we report the running times for a parallel implementation of our algorithm, showing good scalability with the number of processors.