QEx: Robust Quad Mesh Extraction

Abstract : The most popular and actively researched class of quad remeshing techniques is the family of parametrization based quad meshing methods. They all strive to generate an integer-grid map, i.e. a parametrization of the input surface into R2 such that the canonical grid of integer iso-lines forms a quad mesh when mapped back onto the surface in R3. An essential, albeit broadly neglected aspect of these methods is the quad extraction step, i.e. the materialization of an actual quad mesh from the mere “quad texture”. Quad (mesh) extraction is often believed to be a trivial matter but quite the opposite is true: Numerous special cases, ambiguities induced by numerical inaccuracies and limited solver precision, as well as imperfections in the maps produced by most methods (unless costly countermeasures are taken) pose significant challenges to the quad extractor. We present a method to sanitize a provided parametrization such that it becomes numerically consistent even in a limited precision floating point representation. Based on this we are able to provide a comprehensive and sound description of how to perform quad extraction robustly and without the need for any complex tolerance thresholds or disambiguation rules. On top of that we develop a novel strategy to cope with common local fold-overs in the parametrization. This allows our method, dubbed QEx, to generate all-quadrilateral meshes where otherwise holes, non-quad polygons or no output at all would have been produced. We thus enable the practical use of an entire class of maps that was previously considered defective. Since state of the art quad meshing methods spend a significant share of their run time solely to prevent local fold-overs, using our method it is now possible to obtain quad meshes significantly quicker than before. We also provide libQEx, an open source C++ reference implementation of our method and thus significantly lower the bar to enter the field of quad meshing.
Type de document :
Article dans une revue
ACM Transactions on Graphics, Association for Computing Machinery, 2013, Proceedings of SIGGRAPH Asia, pp.168:1--168:10. 〈10.1145/2508363.2508372〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00815814
Contributeur : David Bommes <>
Soumis le : lundi 8 septembre 2014 - 22:47:39
Dernière modification le : jeudi 11 janvier 2018 - 16:47:36
Document(s) archivé(s) le : vendredi 14 avril 2017 - 12:20:12

Fichier

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

Identifiants

Collections

Citation

Hans-Christian Ebke, David Bommes, Marcel Campen, Leif Kobbelt. QEx: Robust Quad Mesh Extraction. ACM Transactions on Graphics, Association for Computing Machinery, 2013, Proceedings of SIGGRAPH Asia, pp.168:1--168:10. 〈10.1145/2508363.2508372〉. 〈hal-00815814v2〉

Partager

Métriques

Consultations de la notice

431

Téléchargements de fichiers

215