Topological Initialization of Injective Integer Grid Maps

Integer Grid Maps (IGM) are a class of mappings characterized by integer isolines that align up to unit translations and rotations of multiples of 90 degrees. They are widely used in the context of remeshing, to lay a quadrilateral grid onto the mapped surface. Computing an IGM is notoriously a challenging task, because it requires to solve a numerical problem with mixed discrete and continuous variables which is known to be NP-Hard. As a result, state of the art methods rely on heuristics that may occasionally fail to produce a valid quadrilateral mesh. Existing pipelines incorporate a final sanitization step which attempts to fix such defects, but no guaranteees can be given in this regard. In this paper we propose a simple topological construction that allows to reduce the problem of computing an IGM to the one of mapping a topological disk to a convex domain. This is a much easier problem to deal with, because it does not endow integer translational and rotational constraints, permitting to obtain a parameterization that is guaranteed to incorporate all the correct integer transitions and to not contain degenerate or inverted elements. Despite provably correct, the so generated maps contain a considerable amount of geometric distortion and a poor quad connectivity, making this technique more suitable for a robust initialization rather than for the computation of an application-ready IGM. In the article we present the details of our construction, also analyzing its geometric and topological properties.