![]() find all edges e which are neither in T nor are crossed by edges in T *.find a maximum spanning tree T * on the edges of the dual graph which do not cross edges in T.find a tree T of shortest paths from the chosen basepoint.The algorithm for finding a greedy homotopy basis is actually very simple: ![]() Erickson and Whittlesey prove that a shortest homotopy basis at a point on a mesh with n vertices can be computed in O(n log n) time (and subsequently, the shortest basis at any point on the mesh can be computed in O(n 2 log n) time). However, a greedy homotopy basis (described below) will cut the surface into a disk.Ī homotopy basis at x can be thought of as a homology basis where all loops meet at a common vertex x, called the basepoint. Not every homology basis is a cut graph: some homology bases either disconnect the surface or cut it into a punctured sphere. A homology basis consists of one loop from each class. For a closed orientable surface with genus g (i.e., a torus with g handles), there are 2 g classes of homologically independent loops. Intuitively, two loops on a surface are homologous if one can be deformed into the other while always keeping it entirely on the surface. One way to find a cut graph is to find a set of loops, no two of which are homologous, which cut the surface into a disk when removed. For instance, the video linked to above shows a cut graph (in yellow) on a two-handled torus, which gets flattened to a circular disk. This kind of flattening is necessary for texture mapping, remeshing, etc. A common task is to find a collection of edges called a cut graph - cutting along these paths turns the surface into a shape which can be flattened into the plane. These tools often operate on the 1-skeleton of a surface, i.e., the graph of edges embedded in the surface. Several tools from topology are useful for mesh processing.
0 Comments
Leave a Reply. |