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.
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
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:
we provide a multi-resolution representation for the Contour Tree with
algorithms for uniform and adaptive refinement on the basis of
- 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);
- 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.
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:
- the separation among branches (either by movement or by minimization of self-intersections);
- the function value of the critical points (e.g. mapping it to the vertical direction in the layout);
- the scale of the topological features (e.g. level of persistence);
- hierarchical parent-child relations among topological features.
- remain stable during the interactive navigation with changing adaptive refinement, and
- 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
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.
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
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)
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 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.
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