Supplementary Material for SIGGRAPH 2013 paper: An Efficient Computation of Handle and Tunnel Loops via Reeb Graphs

p q Specifically, note that the pre-image of Arc(pq) is the evolution of a single contour till it either splits, merges with another one, or is destroyed. We call this the topological component C(pq) corresponding to Arc(pq). See the right figure for an illustration, where the shaded region in M is C(pq). We can obtain C(pq) by computing the contours passing through p and q and cutting and refining any triangle intersecting these contours. We then compute any path in C(pq) from p to q by a depth first search on the edges in C(pq), and use this path as π(p, q). Note that some edges in π(p, q) may be the refined edges along the contours. For each Reeb graph arc Arc(pq), the computation of C(pq) as well as of a pre-image path π(p, q) takes O(n) time. Since there are O(n) number or arcs in the Reeb graph, it takes O(n2) time to compute a path in the pre-image for every Reeb graph arc. Given a Reeb graph loop ce, we compute a loop γi in M by simply assembling the pre-image paths for all arcs in ce. This step takes O(ng) time for all g Reeb graph loops. We remark that the loops in γis may contain edges produced by locally cutting a triangle with a contour. However, later in Section 3.2, we map these edges to the original mesh edges in M before we perform tightening of handle / tunnel loops. Hence, the final loops output by our algorithm consist of only edges from input mesh.