QuadriFlow: A Scalable and Robust Method for Quadrangulation
QuadriFlow: A Scalable and Robust Method for Quadrangulation
复制标题
DOI：
10.1111/cgf.13498
复制
发表时间：
2018-08-01
影响因子：
2.5
通讯作者：
Guibas, Leonidas J.
中科院分区：
文献类型：
--
作者：
Huang, Jingwei;Zhou, Yichao;Guibas, Leonidas J.
QuadriFlow是一种可扩展的算法，用于基于雅各布等人（ACM图形学汇刊34(6):189, 2015）提出的即时场对齐网格生成四边形表面网格。我们对原始算法进行了修改，使其能高效生成奇点数量大幅减少的网格。四边形网格中的奇点会给包括参数化以及使用Catmull - Clark细分曲面进行渲染在内的诸多应用带来问题。奇点极少能被完全消除，但可以将其数量控制在较低水平。局部优化算法通常会生成带有大量奇点的网格，而最优算法往往需要非局部优化，因此速度较慢。我们提出一种通过将即时网格目标与线性和二次约束系统相结合来最小化奇点的高效方法。这些约束通过求解全局最小成本网络流问题和局部布尔可满足性问题来实施。我们在ShapeNet的一个子集中验证了该方法的稳健性和效率，该子集包含17791个自然状态下的三维物体。我们的评估表明，我们方法生成的四边形网格质量即便不比其他方法生成的更好，也与之相当，奇点数量比即时网格减少约四倍。其他能产生类似少量奇点的算法速度要慢得多；我们处理每个模型所需时间不到十秒。我们的源代码已公开。
QuadriFlow 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.