[INFORMATION]
[TITLE]
[AUTHOR]
[SOURCE]
[PRG]
[FILEPATH]
[DELAY]0
[CD TRACK]0
[COMMENT]
[END INFORMATION]
[SUBTITLE]
[COLF]&HFFFFFF,[STYLE]no,[SIZE]8,[FONT]Tahoma
00:00:03.80,00:00:08.47
The Reeb graph of a scalar function represents the evolution of the topology of its level sets.
00:00:09.21,00:00:12.19
There are very few generic algorithms for computing Reeb graphs
00:00:12.19,00:00:15.83
even though there are optimal algorithms for computing contour trees
00:00:16.31,00:00:20.30
In this video we illustrate an easy to implement, near-optimal, output-sensitive
00:00:20.34,00:00:23.33
algorithm for computing the Reeb graph of scalar functions
00:00:23.36,00:00:26.62
defined over manifolds or non-manifolds in any dimension.
00:00:27.38,00:00:30.24
Consider a solid torus. To ease the illustration
00:00:30.28,00:00:33.44
all solid models in this video are rendered transparent.
00:00:34.16,00:00:36.99
Define the function value at every point in the torus
00:00:37.03,00:00:39.10
to be the height of that point above the floor.
00:00:39.97,00:00:44.60
A level set consists of all points where the function attains a given value, called the iso-value.
00:00:46.65,00:00:51.10
Notice that, as we increase the iso-value, the topology of the level sets change.
00:00:52.26,00:00:54.59
Let us now track these level sets.
00:00:54.93,00:00:57.59
A new level set component is created at a minimum.
00:00:58.35,00:01:00.79
It now splits into two components at a saddle.
00:01:02.11,00:01:06.00
Upon reaching the second saddle, the two components merge into one component
00:01:06.03,00:01:08.41
which is finally destroyed at a maximum.
00:01:09.63,00:01:13.81
These four points where the topology of the level sets change are known as critical points.
00:01:14.62,00:01:18.69
The Reeb graph shown on the right expresses this evolution of level sets as a graph.
00:01:19.33,00:01:22.34
Nodes of the Reeb graph correspond to critical points of the function.
00:01:26.13,00:01:29.78
Let us now consider a more complex model with the height function defined on it.
00:01:37.69,00:01:41.91
Notice that each arc of the Reeb graph can be mapped to a cylinder in the input.
00:01:42.44,00:01:45.08
Each cylinder is a collection of level set components
00:01:45.03,00:01:47.33
that are topologically equivalent to each other.
00:01:48.75,00:01:51.81
The level sets at the two critical points defining the arc
00:01:51.36,00:01:53.43
form the boundary of the corresponding cylinder.
00:01:54.31,00:01:56.71
The key idea in our algorithm is to use this mapping
00:01:57.08,00:01:58.90
to obtain the arcs of the Reeb graph.
00:01:59.99,00:02:02.36
Our algorithm takes a triangulated mesh as input.
00:02:03.12,00:02:06.98
The function is sampled at vertices and linearly interpolated within each simplex.
00:02:07.82,00:02:11.19
The algorithm first locates and classifies the critical points of the input.
00:02:12.55,00:02:14.93
Consider a vertex in the mesh along with its neighborhood.
00:02:15.84,00:02:19.57
The link of that vertex consists of the mesh induced by its adjacent vertices.
00:02:20.61,00:02:22.64
The upper link is the mesh induced by adjacent vertices
00:02:22.95,00:02:24.44
having a higher function value
00:02:24.95,00:02:27.36
while the lower link is the mesh induced by adjacent vertices
00:02:27.76,00:02:28.87
having a lower function value.
00:02:32.14,00:02:35.44
A minimum has an empty lower link, while its upper link has one component.
00:02:37.60,00:02:40.18
An index 2 saddle has one component in its lower link
00:02:40.47,00:02:42.08
and two components in its upper link.
00:02:43.95,00:02:46.56
An index 1 saddle has two components in its lower link
00:02:46.83,00:02:48.40
and one component in its upper link.
00:02:49.79,00:02:51.71
The lower link of a maximum has 1 component
00:02:52.31,00:02:53.53
while its upper link is empty.
00:02:56.40,00:03:00.35
For a regular point, both lower and upper links consist of one component.
00:03:03.15,00:03:06.02
We use this characterization to locate all critical points.
00:03:06.37,00:03:09.91
All degeneracies are handled using simulation of simplicity
00:03:10.66,00:03:14.20
Next, we sort them in increasing order of function value.
00:03:16.61,00:03:19.47
The Algorithm next computes the level set for each critical value
00:03:19.78,00:03:20.82
called the critical level set.
00:03:21.75,00:03:24.34
Specifically, we compute only those critical level sets
00:03:24.79,00:03:26.66
that form the upper boundary of each cylinder.
00:03:27.54,00:03:31.72
We march through adjacent triangles starting from a triangle incident on the critical point.
00:03:38.52,00:03:39.96
If a saddle has two lower link components
00:03:40.58,00:03:42.97
the corresponding critical level set has two components.
00:04:07.61,00:04:09.90
The final step of the algorithm computes the arcs
00:04:10.17,00:04:12.49
of the Reeb graph by tracing through each cylinder.
00:04:13.13,00:04:15.20
Starting from a triangle incident on the upper link
00:04:15.41,00:04:16.38
of the smallest critical point
00:04:16.97,00:04:19.43
we march to an adjacent triangle having vertices
00:04:19.87,00:04:21.08
with a higher function value.
00:04:21.55,00:04:23.43
We continue marching until we reach a triangle
00:04:23.94,00:04:26.04
that contains the level set at an iso-value
00:04:26.43,00:04:29.36
equal to the function value of the next non-minimum critical point.
00:04:30.11,00:04:32.62
If the destination triangle belongs to a critical level set
00:04:33.31,00:04:35.95
we insert an arc between the corresponding nodes in the Reeb graph.
00:04:37.11,00:04:40.27
We repeat this process for all critical points in the sorted list.
00:04:45.97,00:04:48.53
If the upper link of the source critical point has two components
00:04:49.15,00:04:52.68
we launch two traversals from that critical point, one for each component.
00:05:08.89,00:05:11.27
Upon reaching the function value of a higher critical point
00:05:11.82,00:05:14.10
if we find that the destination triangle does not belong
00:05:14.71,00:05:15.43
to its critical level set
00:05:16.19,00:05:19.36
we continue our traversal until we reach a higher critical level set.
00:05:26.65,00:05:27.96
When all critical points are processed
00:05:28.40,00:05:30.60
we are done computing the Reeb graph of the input function.
00:05:31.79,00:05:35.62
Tracking the connected components of the level set requires only a 1-skeleton representation
00:05:36.57,00:05:39.32
which can be extracted from the triangles of the input mesh
00:05:40.34,00:05:43.42
In case of non-manifolds, we relax the definition of critical points
00:05:43.99,00:05:47.50
to include all vertices that modify the topology of the level set
00:05:48.34,00:05:51.38
So, the algorithm works directly on the 2-skeleton representation
00:05:51.82,00:05:54.13
of higher dimensional manifolds and non-manifolds
00:05:55.05,00:05:59.68
Our algorithm has a running time of O(n + l + t log t)
00:06:00.13,00:06:02.34
where n is the number of triangles in the input mesh
00:06:02.82,00:06:03.89
t is the number of critical points
00:06:04.38,00:06:06.67
and l is the size of all critical level sets.
00:06:07.57,00:06:10.28
We have noticed that l is usually O(n) in practice.
00:06:11.04,00:06:15.90
So the running time in practice is close to the optimal bound of O(n + t log t).
00:06:16.66,00:06:17.97
As a by-product of our algorithm
00:06:18.31,00:06:20.35
if we trace a path through the triangles traversed
00:06:20.78,00:06:22.59
we get an embedded layout for the Reeb graph.
00:06:23.34,00:06:26.88
This embedding is guaranteed to lie in the interior of the input domain.
00:06:27.51,00:06:29.64
A breadth first search traversal within a cylinder
00:06:29.97,00:06:31.45
instead of traversing a single path
00:06:31.95,00:06:34.78
marches through all triangles that belongs to that cylinder.
00:06:35.63,00:06:38.46
We then specify different transfer functions for each cylinder
00:06:38.92,00:06:40.86
thereby creating a volume rendered image
00:06:41.22,00:06:44.31
that distinctly highlights the user specified areas of the volume.
00:06:45.10,00:06:47.38
For example, consider the Silicium dataset.
00:06:48.14,00:06:50.76
The Reeb graph of the height function is embedded within the volume.
00:06:52.07,00:06:54.91
Two atoms are now highlighted by assigning a different transfer function
00:06:55.46,00:06:57.80
for the cylinders corresponding to a loop in its Reeb graph.
00:06:59.11,00:07:02.33
The Reeb Graph computed by our algorithm also finds applications
00:07:02.65,00:07:04.08
in interactive surface segmentation
00:07:04.59,00:07:07.12
skeleton extraction and topology repair of models.