Introduction

The Contour Tree of a scalar field is the graph obtained by contracting all the connected components of the level sets of the field into points.

This is a powerful abstraction for representing the structure of the field with explicit description of the topological changes of its level sets. It has proven effective as a data-structure for fast extraction of isosurfaces and its application has been advocated as a user interface component guiding interactive data exploration sessions.


Evolution of level sets and its contour tree

In practice, this use has been very limited due the problem of presenting a graph that may be overwhelming in size and in which a planar embedding may be confusing due to self-intersections.

Topological simplification techniques have helped in relieving this problem since they allow reducing the size of the graph. Simplification schemes are best suited for computation of high quality approximations but tend too be inappropriate for computing real-time adaptive refinement for interactive data exploration.




In this case we have the additional problem of needing to compute the layout for the graph, which may be very expensive when done with an external tool not designed for real-time interaction.

Consequently the layout is either poorly distributed at a coarse level, since it was optimized for a fine level of detail, or it is recomputed after simplification, which may change completely its layout loosing the correlation among different levels of resolution with a confusing effect for the user.
We present a multi-resolution data-structure for representing contour trees and an algorithm for its construction. Moreover, we provide a hierarchical layout that allows coarse-to-fine rendering of the tree in a progressive user interface.

We have tested the approach using topological persistence (that is the difference in function value between a pair of critical points that are simplified) as the main metric for constructing the topological hierarchy, and using geometric position (containment in a bounding box) as a secondary metric for adaptive refinement.

The main three contributions of this project are:

  1. we provide a multi-resolution representation for the Contour Tree with algorithms for uniform and adaptive refinement on the basis of precomputed metrics;

  2. we provide an algorithm for computing a multi-resolution Contour Tree directly from join and split trees and guarantee that atomic simplification steps of the tree correspond to atomic collapses of proper pairs of critical points (the minimal topological simplification possible);

  3. we provide a simple scheme for laying out the tree in a way that highlights the hierarchical relationships among the critical points and that can be rendered progressively for real-time user interaction.



Multi-resolution Contour Trees

Single resolution algorithms for computing a contour tree can be found in Computing Contour Trees in All Dimensions" (Hamish Carr and Jack Snoeyink and Ulrike Axen) and in "Efficient Computation of the Topology of the Level Sets" (Valerio Pascucci and Kree Cole-McLaughlin")

In both cases one needs to make two passes through the data to compute the Join Tree and the Split Tree. These trees are then merged to construct the Contour Tree.

Here we use a similar approach but build directly a hierarchical decomposition of the Contour Tree. To do so we store all our trees as branch decompositions and modify the algorithm that merges the join and split trees.

A branch is defined as a monotone path in the graph traversing a sequence of nodes with non-decreasing (or non-increasing) value of f. The first and last nodes in the sequence are called the endpoints of the branch.


All other nodes are said to be interior to the branch. A set of branches is called a branch decomposition of a graph if every arc the graph appears in exactly one branch of the set.

We construct a hierarchical decomposition of a contour tree such that the endpoints of each branch (except the root) represent a saddle-extremum pair that form an atomic topological cancellation (critical points can be canceled only in pairs).

The tree can be simplified by removing a branch that does not disconnect the tree. This corresponds to the cancellation of two critical points in the scalar filed. This simplification process defines a hierarchy of cancellations where a branch B1 is said to be the parent of branch B3 if one endpoint of B3B1.
Example
The general idea is illustrated in the following pratical example (see "Where and When to Look in Time-varying Volume Visualization" by Jack Snoeyink and Jarek Rossignac for the sample example in the standard/single resolution way).

The large nodes are the endpoints of the branches (initially all).At each stage the branches candidate for transfer into the Contour Tree are pointed by a gray arrow. The one effectively selected (by some measure of priority) is drawn with a bold and is the moved into the Contour Tree at the next stage.


After the branch (10-6) has been moved to the Contour Tree, the Join Tree has a branch with endpoints 9 and 4 and middle node 6. The red arrow that points to the branch (1-3-4), which is not a candidate for removal since the node 4 is properly paired with node 9 and not with node 1:



At the fifth step the Join and Merge tree have been reduced to the branch (7-5-4-3-1),s which becomes the root branch of the Contour Tree:



Layout, Traversal and Visualization

In a user interface that includes the Contour Tree as a tool for interactive exploration of topology, it is often desirable to use a tree layout that highlights naturally:
  1. the separation among branches (either by movement or by minimization of self-intersections);
  2. the function value of the critical points (e.g. mapping it to the vertical direction in the layout);
  3. the scale of the topological features (e.g. level of persistence);
  4. hierarchical parent-child relations among topological features.
  5. remain stable during the interactive navigation with changing adaptive refinement, and
  6. the information should be spread as uniformly as possible to optimize the use of the screen space.

As often happens, such objectives are often in conflict. For example a 2D layout using one axis to represent the function value of the critical points does not allow to guarantee a layout without self intersections. Because of this problem we develop a three-dimensional embedding of the contour tree, which is inspired to the orrery metaphor:


We draw a graph where the root is a vertical line. All the other branches are L-shapes that connect to their extremum (red for minimum, blue for maximum) to its paired saddle along the parent (white circle). We map the field value to the elevation along the z-coordinate so that the vertical span of each branch equals its persistence.


The main idea of the layout algorithm is to define a sequence of consecutive disks, D1, D2,D3..., with radii r_1 < r_2 < r_3 < .... Then we compute an angular wedge at each node such that the subtree rooted at that node is contain entirely within the angular wedge. The root node is positioned at the origin and the nodes of depth k are arranged on the boundary of the disk D_k. Thus the projection of the tree in the xy plane is arranged with a circular layout that has no self intersections.

The branch decomposition representation of the Contour Tree allows for uniform or adaptive refinement of the tree. Uniform simplification is achieved by interrupting the drawing process when the first branch with persistence less than a specified value is reached. Adaptive simplification is almost as easy: before each branch is visualized it is tested to see if it satisfies the adaptive criterion.

Gallery

Electron density distribution
Contour Tree at three levels of resolution for the electron density distribution rho computed with an ab initio simulation for water molecules at high pressure.

At the coarse scale (top) the tree has only one maximum (blue sphere) per water molecule. At medium scale (middle) the topology reconstructs one dipole per molecule with one maximum and one minimum (red sphere). At fine scale (bottom) only the noise is removed and three extrema per molecule reconstruct each atom in the simulation.

Adaptive refinement in the area marked with a rectangle (middle) can be used to refine the topology for two particular molecules. This as shown on the right at coarse, medium and fine scale both for the Contour Tree and for the embedding (shown side by side)



Triangulated models
Here we show some examples of the computation of contour treees for triangular meshes. In the first column we show the original model. In the second column the Complete Contour Trees are drawn with their critical points in their original position (the Morse function f is the height in the vertical direction). In the third column the full topology is shown only in the bounding box containing the head (using the adaptive refinement of our multiresolution representation).



Neghip dataset
Neghip dataset representing the spatial probability distribution of the electrons in a high potential protein molecule. You see in sequence: level sets for different isovalues; Contour Tree of the full topology; Contour Tree of the coarse resolution topology; critical points of the coarse scale topology, displayed together with a semi transparent level set.





Silicium grid
Topology of the electron density distribution in a simulation of a silicium grid. The topology can be presented incrementally from coarse to fine:






Files and demos

You can donwload the PDF file Multi-Resolution computation and presentation of Contour Trees which study in deep all the arguments here presented.


Demos for Windows. Click here