QuadriFlow: A Scalable and Robust Method for Quadrangulation

dc.contributor.authorHuang, Jingweien_US
dc.contributor.authorZhou, Yichaoen_US
dc.contributor.authorNiessner, Matthiasen_US
dc.contributor.authorShewchuk, Jonathan Richarden_US
dc.contributor.authorGuibas, Leonidas J.en_US
dc.contributor.editorJu, Tao and Vaxman, Amiren_US
dc.date.accessioned2018-07-27T12:54:57Z
dc.date.available2018-07-27T12:54:57Z
dc.date.issued2018
dc.description.abstractQuadriFlow is a scalable algorithm for generating quadrilateral surface meshes based on the Instant Field-Aligned Meshes of Jakob et al. (ACM Trans. Graph. 34(6):189, 2015). We modify the original algorithm such that it efficiently produces meshes with many fewer singularities. Singularities in quadrilateral meshes cause problems for many applications, including parametrization and rendering with Catmull-Clark subdivision surfaces. Singularities can rarely be entirely eliminated, but it is possible to keep their number small. Local optimization algorithms usually produce meshes with many singularities, whereas the best algorithms tend to require non-local optimization, and therefore are slow. We propose an efficient method to minimize singularities by combining the Instant Meshes objective with a system of linear and quadratic constraints. These constraints are enforced by solving a global minimum-cost network flow problem and local boolean satisfiability problems. We have verified the robustness and efficiency of our method on a subset of ShapeNet comprising 17,791 3D objects in the wild. Our evaluation shows that the quality of the quadrangulations generated by our method is as good as, if not better than, those from other methods, achieving about four times fewer singularities than Instant Meshes. Other algorithms that produce similarly few singularities are much slower; we take less than ten seconds to process each model. Our source code is publicly available.en_US
dc.description.number5
dc.description.sectionheadersMeshing
dc.description.seriesinformationComputer Graphics Forum
dc.description.volume37
dc.identifier.doi10.1111/cgf.13498
dc.identifier.issn1467-8659
dc.identifier.pages147-160
dc.identifier.urihttps://doi.org/10.1111/cgf.13498
dc.identifier.urihttps://diglib.eg.org:443/handle/10.1111/cgf13498
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.subjectI.3.5 [Computer Graphics]
dc.subjectComputational Geometry and Object Modeling
dc.subjectQuadrangulation
dc.titleQuadriFlow: A Scalable and Robust Method for Quadrangulationen_US
Files
Collections