Towards a robust and portable pipeline for quad meshing: Topological initialization of injective integer grid maps

Integer Grid Maps (IGMs) 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. The presence of both discrete and continuous degrees of freedom makes the computation of IGMs extremely challenging. In particular, solving for all degrees of freedom altogether leads to a mixed-integer problem that is known to be NP-Hard. Such a problem can only be solved heuristically, occasionally failing to produce a valid quadrilateral mesh. In this paper we propose a simple topological construction that allows to reduce the problem of computing a valid IGM to the one of mapping a topological disk to a convex domain. This is a much easier problem to deal with, because it completely removes the integer constraints, permitting to obtain a provably injective parameterization that is guaranteed to incorporate all the correct integer transitions with a simple linear solve. Not only the proposed algorithm is easy to implement, but it is also independent from costly numerical solvers that are unavoidable in existing quadmeshing pipelines, preventing their exploitation in open source or low-budget projects. 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.