Computing contour trees for 2D piecewise polynomial functions.

Girijanandan Nucha, Georges-Pierre Bonneau, Stefanie Hahmann and Vijay Natarajan. Computer Graphics Forum (EuroVis 2017), 36(3), 2017, 23-33.

Abstract

Contour trees are extensively used in scalar field analysis. The contour tree is
a data structure that tracks the evolution of level set topology in a scalar field.
Scalar fields are typically available as samples at vertices of a mesh and are
linearly interpolated within each cell of the mesh. A more suitable way of
representing scalar fields, especially when a smoother function needs to be
modeled, is via higher order interpolants. We propose an algorithm to compute
the contour tree for such functions. The algorithm computes a local structure
by connecting critical points using a numerically stable monotone path tracing
procedure. Such structures are computed for each cell and are stitched together
to obtain the contour tree of the function. The algorithm is scalable to higher
degree interpolants whereas previous methods were restricted to quadratic or
linear interpolants. The algorithm is intrinsically parallelizable and has
potential applications to isosurface extraction.