Integer-Grid Maps for Reliable Quad Meshing

Abstract : Quadrilateral remeshing approaches based on global parametrization enable many desirable mesh properties. Two of the most important ones are (1) high regularity due to explicit control over irregular vertices and (2) smooth distribution of distortion achieved by convex variational formulations. Apart from these strengths, state-of-the-art techniques suffer from limited reliability on real-world input data, i.e. the determined map might have degeneracies like (local) non-injectivities and consequently often cannot be used directly to generate a quadrilateral mesh. In this paper we propose a novel convex Mixed-Integer Quadratic Programming (MIQP) formulation which ensures by construction that the resulting map is within the class of so called Integer-Grid Maps that are guaranteed to imply a quad mesh. In order to overcome the NP-hardness of MIQP and to be able to remesh typical input geometries in acceptable time we propose two additional problem specific optimizations: a complexity reduction algorithm and singularity separating conditions. While the former decouples the dimension of the MIQP search space from the input complexity of the triangle mesh and thus is able to dramatically speed up the computation without inducing inaccuracies, the latter improves the continuous relaxation, which is crucial for the success of modern MIQP optimizers. Our experiments show that the reliability of the resulting algorithm does not only annihilate the main drawback of parametrization based quad-remeshing but moreover enables the global search for high-quality coarse quad layouts - a difficult task solely tackled by greedy methodologies before.
Type de document :
Article dans une revue
ACM Transactions on Graphics, Association for Computing Machinery, 2013, 32 (4)
Liste complète des métadonnées

Littérature citée [38 références]  Voir  Masquer  Télécharger


https://hal.inria.fr/hal-00862648
Contributeur : David Bommes <>
Soumis le : mardi 17 septembre 2013 - 11:12:51
Dernière modification le : jeudi 8 février 2018 - 16:20:02
Document(s) archivé(s) le : jeudi 6 avril 2017 - 21:20:28

Fichiers

IGM.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00862648, version 1

Collections

Citation

David Bommes, Marcel Campen, Hans-Christian Ebke, Pierre Alliez, Leif Kobbelt. Integer-Grid Maps for Reliable Quad Meshing. ACM Transactions on Graphics, Association for Computing Machinery, 2013, 32 (4). 〈hal-00862648〉

Partager

Métriques

Consultations de la notice

589

Téléchargements de fichiers

4692