[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.