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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-00815814
Contributor : David Bommes <>
Submitted on : Monday, September 8, 2014 - 10:47:39 PM
Last modification on : Thursday, September 19, 2019 - 1:18:54 AM
Long-term archiving on : Friday, April 14, 2017 - 12:20:12 PM

File

ebck2013_1.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

779

Files downloads

459