Practical Computation of the Cut Locus on Discrete Surfaces

We present a novel method to compute the cut locus of a distance function encoded on a polygonal mesh. Our method exploits theoretical findings about the cut locus and – with a combination of analytic, geometric and topological tools – it is able to compute a topologically correct and geometrically accurate approximation of it. Our result can be either restricted to the mesh edges, or aligned with the real cut locus. Both outputs may be useful for practical applications. We also provide a convenient tool to optionally prune the weak branches of the cut locus, simplifying its structure. Our approach supersedes prior art, in that it is easier to use and also orders of magnitude faster. In fact, it depends on just one parameter, and it flawlessly operates on meshes with high genus and very high element count at interactive rates. We experiment with different datasets and methods for geodesic distance estimation. We also present applications to local and global surface parameterization.