A Mesh Generation Perspective on Robust Mappings

Abstract

Mapping a shape to some parametric domain is a fundamental tool in graphics and scientific computing. In practice, a map between two shapes is commonly represented by two meshes with same connectivity and different embedding. The standard approach is to input a mesh embedded in one domain plus a set of prescribed positions for its boundary vertices in the other domain, and compute the position of the interior points in the mesh. For the 2d case, there are numerous robust tools that follow this scheme. However, theoretical issues prevent them to scale to 3d domains, thus the robust generation of volumetric maps remains an important open scientific problem. Inspired by basic principles in mesh generation, in this paper we present the reader a novel point of view on mesh parameterization. We consider connectivity as an additional unknown, and assume that our inputs are just two boundaries that enclose the domains we want to connect. We compute the map by simultaneously growing the same mesh inside both shapes in an advancing front fashion. This change in perspective allows us to recast the parameterization problem as a mesh generation problem, granting access to a wide set of mature tools that are typically not used in this setting. Our practical outcome is a provably robust yet trivial to implement algorithm that maps non convex planar shapes to convex ones. Perhaps more interestingly, we speculate on possible extensions to planar maps between non convex domains, and to volumetric maps as well, listing the major challenges that arise. Differently from prior methods, our analysis leaves us reasonable hope that an extension to volumes is possible.