State Key Lab of CAD&CG, Zhejiang University, Hangzhou 310058, China.
IEEE Trans Vis Comput Graph. 2013 Jun;19(6):941-52. doi: 10.1109/TVCG.2012.301.
Many natural and man-made objects consist of simple primitives, similar components, and various symmetry structures. This paper presents a divide-and-conquer quadrangulation approach that exploits such global structural information. Given a model represented in triangular mesh, we first segment it into a set of submeshes, and compare them with some predefined quad mesh templates. For the submeshes that are similar to a predefined template, we remesh them as the template up to a number of subdivisions. For the others, we adopt the wave-based quadrangulation technique to remesh them with extensions to preserve symmetric structure and generate compatible quad mesh boundary. To ensure that the individually remeshed submeshes can be seamlessly stitched together, we formulate a mixed-integer optimization problem and design a heuristic solver to optimize the subdivision numbers and the size fields on the submesh boundaries. With this divider-and-conquer quadrangulation framework, we are able to process very large models that are very difficult for the previous techniques. Since the submeshes can be remeshed individually in any order, the remeshing procedure can run in parallel. Experimental results showed that the proposed method can preserve the high-level structures, and process large complex surfaces robustly and efficiently.
许多自然和人为物体都由简单的基元、相似的组件和各种对称结构组成。本文提出了一种分而治之的四边形剖分方法，利用这种全局结构信息。对于用三角网格表示的模型，我们首先将其分割成一组子网格，并将它们与一些预定义的四边形网格模板进行比较。对于与预定义模板相似的子网格，我们将其重新划分为模板，最多进行若干细分。对于其他子网格，我们采用基于波的四边形剖分技术进行重新划分，并进行扩展以保持对称结构并生成兼容的四边形网格边界。为了确保单独重新划分的子网格可以无缝拼接在一起，我们制定了一个混合整数优化问题，并设计了一个启发式求解器来优化子网格边界上的细分数量和大小字段。使用这个分而治之的四边形剖分框架，我们能够处理对于以前的技术来说非常困难的非常大的模型。由于子网格可以按任意顺序单独进行重新划分，因此重新划分过程可以并行运行。实验结果表明，该方法能够很好地保持高层结构，并能稳健、高效地处理大型复杂曲面。
