Tip:
Highlight text to annotate it
X
The Reeb graph of a scalar function represents the evolution of the topology of its level sets.
There are very few generic algorithms for computing Reeb graphs
even though there are optimal algorithms for computing contour trees
In this video we illustrate an easy to implement, near-optimal, output-sensitive
algorithm for computing the Reeb graph of scalar functions
defined over manifolds or non-manifolds in any dimension.
Consider a solid torus. To ease the illustration
all solid models in this video are rendered transparent.
Define the function value at every point in the torus
to be the height of that point above the floor.
A level set consists of all points where the function attains a given value, called the iso-value.
Notice that, as we increase the iso-value, the topology of the level sets change.
Let us now track these level sets.
A new level set component is created at a minimum.
It now splits into two components at a saddle.
Upon reaching the second saddle, the two components merge into one component
which is finally destroyed at a maximum.
These four points where the topology of the level sets change are known as critical points.
The Reeb graph shown on the right expresses this evolution of level sets as a graph.
Nodes of the Reeb graph correspond to critical points of the function.
Let us now consider a more complex model with the height function defined on it.
Notice that each arc of the Reeb graph can be mapped to a cylinder in the input.
Each cylinder is a collection of level set components
that are topologically equivalent to each other.
The level sets at the two critical points defining the arc
form the boundary of the corresponding cylinder.
The key idea in our algorithm is to use this mapping
to obtain the arcs of the Reeb graph.
Our algorithm takes a triangulated mesh as input.
The function is sampled at vertices and linearly interpolated within each simplex.
The algorithm first locates and classifies the critical points of the input.
Consider a vertex in the mesh along with its neighborhood.
The link of that vertex consists of the mesh induced by its adjacent vertices.
The upper link is the mesh induced by adjacent vertices
having a higher function value
while the lower link is the mesh induced by adjacent vertices
having a lower function value.
A minimum has an empty lower link, while its upper link has one component.
An index 2 saddle has one component in its lower link
and two components in its upper link.
An index 1 saddle has two components in its lower link
and one component in its upper link.
The lower link of a maximum has 1 component
while its upper link is empty.
For a regular point, both lower and upper links consist of one component.
We use this characterization to locate all critical points.
All degeneracies are handled using simulation of simplicity
Next, we sort them in increasing order of function value.
The Algorithm next computes the level set for each critical value
called the critical level set.
Specifically, we compute only those critical level sets
that form the upper boundary of each cylinder.
We march through adjacent triangles starting from a triangle incident on the critical point.
If a saddle has two lower link components
the corresponding critical level set has two components.
The final step of the algorithm computes the arcs
of the Reeb graph by tracing through each cylinder.
Starting from a triangle incident on the upper link
of the smallest critical point
we march to an adjacent triangle having vertices
with a higher function value.
We continue marching until we reach a triangle
that contains the level set at an iso-value
equal to the function value of the next non-minimum critical point.
If the destination triangle belongs to a critical level set
we insert an arc between the corresponding nodes in the Reeb graph.
We repeat this process for all critical points in the sorted list.
If the upper link of the source critical point has two components
we launch two traversals from that critical point, one for each component.
Upon reaching the function value of a higher critical point
if we find that the destination triangle does not belong
to its critical level set
we continue our traversal until we reach a higher critical level set.
When all critical points are processed
we are done computing the Reeb graph of the input function.
Tracking the connected components of the level set requires only a 1-skeleton representation
which can be extracted from the triangles of the input mesh
In case of non-manifolds, we relax the definition of critical points
to include all vertices that modify the topology of the level set
So, the algorithm works directly on the 2-skeleton representation
of higher dimensional manifolds and non-manifolds
Our algorithm has a running time of O(n + l + t log t)
where n is the number of triangles in the input mesh
t is the number of critical points
and l is the size of all critical level sets.
We have noticed that l is usually O(n) in practice.
So the running time in practice is close to the optimal bound of O(n + t log t).
As a by-product of our algorithm
if we trace a path through the triangles traversed
we get an embedded layout for the Reeb graph.
This embedding is guaranteed to lie in the interior of the input domain.
A breadth first search traversal within a cylinder
instead of traversing a single path
marches through all triangles that belong to that cylinder.
We then specify different transfer functions for each cylinder
thereby creating a volume rendered image
that distinctly highlights the user specified areas of the volume.
For example, consider the Silicium dataset.
The Reeb graph of the height function is embedded within the volume.
Two atoms are now highlighted by assigning a different transfer function
for the cylinders corresponding to a loop in its Reeb graph.
The Reeb Graph computed by our algorithm also finds applications
in interactive surface segmentation
skeleton extraction and topology repair of models.