## Green : Our method yields a fair Morse function b with the….

1 Introduction Morse theory connects the differential geometry of a surface with its algebraic topology.

Given a real function over some shape, it describes the connectedness of the shape from the conﬁguration of the points where the function’s gradient vanishes, its so-called critical points (eg minima, maxima, saddles).

Morse theory has been used in graphics and visualization to analyze different real functions.

Terrain data, eg, is deﬁned by an altitude function on the plane, and Morse theory can identify topographical features, control their simpliﬁcation [Bajaj and Schikore 1998], and organize them into a multiresolution hierarchy [Bremer et al. 2003].

The zeroset of a real function over 3-space deﬁnes an isosurface, and Morse theory can determine its topology for more accurate polygonization [Stander and Hart 1997].

When given only a shape, the critical points of almost all real functions on its surface can be used to interrogate its topology, but some functions are much better choices than others.

The Euler characteristic χ reveals the genus of a closed connected manifold mesh by the formula χ = vertices − edges + faces = 2 − 2g. (1) (a) (b) Figure 1: An altitude function (a) yields a complicated arrangement of 3,605 critical points on the genus-6 Buddha.

Our method yields a fair Morse function (b) with the least number of critical points, in this case one blue minimum, one red maximum and twelve green saddles.

Cutting along the indicated path separates the mesh into a shape topologically a disk suitable for planar parameterization. The Euler characteristic can also be calculated from the critical points χ = minima − saddles + maxima. (2) By combining these two equations we see that the smallest number of critical points possible on a genus g closed oriented manifold is one minimum, one maximum and 2g saddles.

However, an arbitrarily chosen Morse function like altitude can yield many more critical points, satisfying the Euler characteristic with any number of additional extrema (minima or maxima) matched by the same number of additional saddles.

For example, the altitude function on the genus-6 Buddha model, Fig. 1(a), yields 3,605 critical points.

A better choice of function (b) yields the minimum number of 14 Morse critical points for this shape.

This paper describes how to ﬁnd such a function and how to use it to solve various problems in meshed geometry processing.

These extra critical points are caused by the altitude function’s sensitivity to surface undulation.

A vertical wrinkle in the surface, no matter how small, creates a pair of critical points.

These undu- lations could be removed by smoothing the surface, but it is easier and less destructive to smooth the function.

We leave the surface unchanged, and instead apply Laplacian smoothing to the function to remove its “wrinkles” until it converges to a smooth, in fact harmonic, result that yields the least number of critical points.

Because we are removing unwanted function variation over the surface, we call this process Morse fairing and the resulting function a fair Morse function.

Given a fair Morse function, one can trace gradient-descent ﬂowlines down the edges of the mesh from the saddle points to the minimum.

These ﬂowlines form a seam that allows the mesh to be cut into a shape topologically equivalent to a disk.

Most other methods used in graphics to cut a surface into a disk are based on a regiongrowing Dijkstra’s algorithm.

Sec. 2 reveals that Dijkstra’s algorithm is in fact an arbitrarily chosen Morse function which leads to extraneous topological events that must be identiﬁed and removed.

Sec. 3 reviews Morse theory and the state of the art in its application to meshes.

This section offers new solutions that make Morse theory work more robustly on meshes, including managing high-multiplicity saddles, the application of Conley index theory to resolve degenerate “ﬂat” regions, and “teﬂon” saddles that avoid a degenerate Morse structure.

Sec. 4 describes the Morse fairing process, based on solving a constrained Laplacian over the mesh.

A theorem in this section leads to a new “intermediate value propagation” multigrid solver that performs Morse fairing in provably linear time, allowing it to be applied in-core to any size mesh, and outruns an irregular-mesh multigrid Laplacian solver.

Morse fairing can also produce a real function with a userspeciﬁed number of critical points, and can place its extrema in user speciﬁed positions.

Sec. 3 reviews how the gradient-descent paths of this function embed a graph, called the Morse complex, in the meshed surface that contains a vertex for each minimum, a face containing each maximum and the exact arrangement of edges needed to ensure it matches the topology of the mesh.

Section 5 describes applications of the faired Morse complex for cutting a surface into a disk, constructing a feature-sensitive topology-correct base domain, clustering faces toward developable charts and visualizing the topology of a complex surface.

Sec. 6 concludes with a discussion of the limitations of Morse fairing and directions for further research. Front propagation generates a real function over the mesh, when the mesh is sufﬁciently subdivided, the collisions of these fronts form Morse critical points [Axen and Edelsbrunner 1998].

The choice of distance-to-base-point as the Morse function is arbitrary with respect to the surface topology which makes it unecessarily expensive and prone to generating more critical points than necessary.

Morse fairing provides a less expensive real function that generates the same topological information as front propagation, but avoids the maintenance of an prioriry-queued equidistant front and the expense of collision detection.

Morse Theory on Meshes.

Morse theory was originally devised for smooth functions on manifolds [Milnor 1963], though it extends elegantly to piecewise linear functions on triangle meshes [Banchoff 1970].

Edelsbrunner et al. [2002] further reﬁned the application of Morse theory to meshes.

They ﬁrst deﬁne persistence as the difference in value between a pair of critical points that would cancel each other after the appropriate perturbation.

Persistence prioritizes the cancellation of critical points, which allows one to control the simpliﬁcation of features in terrain data and general 2-manifolds [Edelsbrunner et al. 2003b; Bremer et al. 2003].

These methods can remove all unnecessary critical points, but do so in order of increasing persistence.

Morse fairing leapfrogs this persistence organization and removes unwanted critical points in a single step.

The Reeb graph has also been used in graphics to represent shape topology, eg [Shinagawa et al. 1991; Hilaga et al. 2001].

The Reeb graph uses graph topology to represent solid topology (eg a Reeb graph cycle represents a torus hole).

Similar to us, Steiner & Fischer [2001] also used a mesh Laplacian to simplify topology, but instead generated a simpliﬁed Reeb graph that lacked extraneous details from non-topological features.

The Morse complex represents topology in a surface embeddable structure, and so makes it more amendable to the application of surface processing.

Laplacian Smoothing.

Bajaj et al. [1998] observed that smoothing a Morse function with a Gaussian ﬁlter cancelled many pairs of unnecessary critical points, which simpliﬁed the critical point structure to aid in the visualization of scientiﬁc data.

Bremer et al. [2003] perform iterative Laplacian smoothing steps to cancel critical points in its multiresolution topology hierarchy (and to smooth the jagged 1-cells of the Morse-Smale complex).

Ray & Levy [2003] devise a multigrid Laplacian solver similar to ours to ﬁnd a least-squares optimal conformal parameterization of a surface triangle mesh.

The solution needed for Morse fairing need not be an exact Laplacian, and Sec. 4.3 capitalizes on this property to simplify the multigrid implementation. 2 Previous Work Cutting a Surface into a Disk.

The problem of cutting a closed genus-g mesh of n vertices into a single ﬂattenable component has been investigated as the polygonal schema problem in computational topology [Vegter 1997; Dey et al. 1999a].

Finding optimal cuts is NP-hard, but cuts within O(log2 g) of optimal can be found in O(g2 n log n) time [Erickson and Har-Peled 2002], and paths through a common base point can be optimized in polynomial time [de Verdi` ere and Lazarus 2002].

Arbitrary cuts can be found in O(gn) time [Lazarus et al. 2001].

Morse fairing ﬁnds the least number of non-optimal cuts through a base point in time linear in the number of vertices, but with an approach that is signiﬁcantly easier to implement.

Mesh topology methods in computer graphics, including topological noise removal [Guskov and Wood 2001], geometry images [Gu et al. 2002], and feature detection [Zhang et al. 2003], ﬁnd mesh cuts primarily with region growing [Dey and Schipper 1995].

In a closed manifold, a front expanding from a base point will self intersect, and these self intersections ﬂag the presence of a handle.

Front propagation is robust and works well even on meshes with boundaries, and Dijkstra’s algorithm can be used when the length of cuts is important. — A theorem of smooth Morse theory states that M is homotopic to a cell complex that contains a λ -cell corresponding to each critical point of index λ [Milnor 1963].

If f is Morse-Smale [Edelsbrunner et al. 2002] then this 2-complex can be instantiated geometrically as a graph embedded in M .

This graph contains a vertex (0-cell) at each Morse saddle v, decompose Lk− (v) into its two disjoint connected components A and B, and let vA = argmin(A) and likewise for vB .

The 1-cell corresponding to saddle v is then the union of ﬂow(vA ), vA , v , v, vB and ﬂow(vB ) and its ends (minima) are attached to the corresponding 0-cells.

The remaining 2-cells, the connected components of M − X 1 , will each contain a single maximum. F x Figure 6: A ﬂat region of vertices can be treated as a single vertex.

Each of the vertices in the ﬂat region appears to be regular when ignoring ﬂat edges, but contraction of the ﬂat region to a single vertex reveals it to be a saddle. Figure 5: The Morse complex of the x-coordinate of a closedmanifold version of the Utah teapot (the handle-to-spout axis).

All critical points lie in the xy-plane: blue = minimum, green = saddle and red = maximum.

We can extend the Morse complex to handle saddles of multiplicity m > 1 though it requires the rather inelegant addition of 0-cells at these saddles2 .

First place a 0-cell at each saddle v of multiplicity m.

Then decompose Lk− (v) into its m + 1 connected components {Ai } and let vi = argmin(Ai ).

For each of these, embed a 1-cell in M corresponding to the ﬂow path ﬂow(vi ), attaching one end to the 0-cell at v and the other to the 0-cell at the ﬂow path’s terminating minimum.

The two ﬂow paths visiting vertices (v1 , v2 , . . . , vn ) and (v1 , v2 , . . . , vn ) can merge (vi = v j for some minimal i < n and j < n ).

These merged paths invalidate the embedding, as it becomes two-to-one on the pair of corresponding 1-cells, and manyto-one on the 2-cell between.

We can repair this degeneracy of the resulting complex by inserting a 0-cell at the merge vertex vi and representing the two merged ﬂow paths by a single 1-cell attached to vi and the terminating minimum.

Since we have added a 0-cell and a 1-cell, the Euler characteristic remains unchanged, though the resulting cell complex contains additional 0-cells that do not correspond to any critical point. this case is the set of vertices not in F one edge away from a vertex in F, and the cycle of edges connecting them. (Alternatively a ﬂat edge can be processed as a single vertex by an edge collape, and simply-connected ﬂat regions can be converted to a single vertex by a sequence of ﬂat edge collapses.) Thus the lower link can be evaluated and the ﬂat region classiﬁed.

Since a ﬂat region will have more edges incident on it than would a single vertex, they are more likely to be saddles of high multiplicity, which we can process directly as previously described.

The altitude of the Buddha model in Fig. 1(a) contains several ﬂat regions that were removed by ﬂat edge collapse.

Perturbation of these edges would have resulted in 18 additional critical points.

One may encounter a multiply-connected ﬂat region, especially in models designed or reconstructed by sampling a rectilinear grid.

For example the altitude of the Utah teapot from a triangle mesh derived from its control points contains numerous ﬂat edge cycles.

Even the x-coordinate function used in Fig. 5 contains a single ﬂat edge cycle at its girth.

Such cases require more sophisticated methods from Conley index theory that deserve a separate and more indepth treatment than possible here.

Such cases can nevertheless be overcome by perturbation techniques at the risk of additional lowpersistence critical points, and the teapot in Fig. 5 has been rotated slightly.

Such multiply-connected ﬂat regions are far less common in Morse-faired functions. 3.4 Boundaries 3.3 Flat Regions The ﬂat edge limitation: v1 , v2 ∈ M → f (v1 ) = f (v2 ), can be overcome by perturbation, but perturbation can introduce numerous low-persistence additional critical points.

A better solution for ﬂat edges can be drawn from Conley index theory [Mischaikow 1995; Mischaikow and Mrozek 2002].

The Conley index simpliﬁes the classiﬁcation of a complicated critical region in a vector ﬁeld (more general than the gradient ﬁeld studied in this paper) by analyzing the vector ﬁeld along the boundary of a neighborhood of the critical region, which effectively contracts the critical region to a single point.

Let F be a simply connected maximal collection of equal-valued vertices, as demonstrated in Fig. 6.

Then the boundary of this neighborhood is Lk F, where the link is the boundary of the star and in 2 These additional 0-cells do not affect the Euler characteristic because they separate a single 1-cell passing through the saddle into 2 1-cells extending from the saddle. We can also extend Morse theory to meshed manifolds with boundary.

Such manifolds contain one or more boundaries each represented by a simple closed loop of edges.

In preparation for Morse function processing, we sew up each boundary loop by inserting a temporary vertex and creating a face between it and each edge of the boundary loop.

The location of the temporary vertex is irrelevant for topological processing, but for geometric concerns can be placed at the centroid of the boundary loop vertices.

Likewise the new faces may not generate a valid embedding, but they are only used for combinatorial processing and will be removed once a Morse function has been found.

This is similar to the scaffolding triangles of [Zhang et al. 2003] which were used on the much different application of individual patch layout and parameterization.

We will assign an extremal function value to each temporary vertex.

If the temporary vertex is not constrained to a global minimum or maximum, then one runs the risk of it becoming a saddle.

When the temporary vertex and its face neighborhood are removed, the mesh will be missing a key piece of its critical point structure.

For cutting the surface into a disk, we make the vertex a minimum, which will connect at least one gradient descent ﬂow to the boundary.

When the temporary vertex and its star are removed, any ﬂows to it will terminate at, and include, the boundary loop.

Alternatively, assigning a maximum value to the temporary vertices

Read more about *Green : Our method yields a fair Morse function b with the….*:

Equestrian Products – Guardian Horse Bedding, Equiderma Skin Products, Equilinn Sports Bra