Scalable Mesh Refinement for Canonical Polygonal Schemas of Extremely High Genus Shapes

Any closed manifold of genus g can be cut open to form a topologicaldisk and then mapped to a regular polygon with 4g sides. This construction iscalled the canonical polygonal schema of the manifold, and is a key ingredient formany applications in graphics and engineering, where a parameterization betweentwo shapes with same topology is often needed. The sides of the 4ggon define onthe manifold a system of loops, which all intersect at a single point and are disjointelsewhere. Computing a shortest system of loops of this kind is NP-hard. Acomputationally tractable alternative consists of computing a set of shortest loopsthat are not fully disjoint in polynomial time using the greedy homotopy basisalgorithm proposed by Erickson and Whittlesey and then detach them in postprocessing via mesh refinement. Despite this operation is conceptually simple,known refinement strategies do not scale well for high genus shapes, triggering amesh growth that may exceed the amount of memory available in moderncomputers, leading to failures. In this article we study various local refinementoperators to detach cycles in a system of loops, and show that there are importantdifferences between them, both in terms of mesh complexity and preservation ofthe original surface. We ultimately propose two novel refinement approaches: theformer greatly reduces the number of new elements in the mesh, possibly at thecost of a deviation from the input geometry. The latter allows to trade meshcomplexity for geometric accuracy, bounding deviation from the input surface. Bothstrategies are trivial to implement, and experiments confirm that they allow torealize canonical polygonal schemas even for extremely high genus shapes whereprevious methods fail.