Premium
Perfect Matching Quad Layouts for Manifold Meshes
Author(s) -
Razafindrazaka Faniry H.,
Reitebuch Ulrich,
Polthier Konrad
Publication year - 2015
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/cgf.12710
Subject(s) - quadrilateral , polygon mesh , computation , graph , computer science , manifold (fluid mechanics) , algorithm , matching (statistics) , mathematics , singularity , topology (electrical circuits) , mathematical optimization , theoretical computer science , geometry , finite element method , combinatorics , mechanical engineering , statistics , physics , engineering , thermodynamics
Abstract This paper introduces a new approach to automatically generate pure quadrilateral patch layouts on manifold meshes. The algorithm is based on a careful construction of a singularity graph of a given input frame field or a given periodic global parameterization. A pure quadrilateral patch layout is then derived as a constrained minimum weight perfect matching of that graph. The resulting layout is optimal relative to a balance between coarseness and geometric feature alignment. We formulate the problem of finding pure quadrilateral patch layouts as a global optimization problem related to a well‐known concept in graph theory. The main advantage of the new method is its simplicity and its computation speed. Patch layouts generated by the present algorithm are high quality and are very competitive compared to current state of the art.