A Robust Combinatorial Approach to Reduce Singularities in Quadrilateral Meshes

There are many automatic quadrilateral mesh generators that can produce high quality mesh with low distortion. However, they typically generate a large number of singularities that could be detrimental to downstream applications. This paper introduces Minimum Singularity Templates (MST) to reduce the number of singularities in an existing pure quad mesh. These templates are easy to encode with high-level grammar rules for complete automation, or interactive control. The MST exploits two important properties of quadrilateral meshes: (1) every submesh has even number of quad edges on its boundary, and (2) every submesh with 3, 4 or 5 topological convex corners on its boundary has at most two interior singularities. The MST (1) does not change the boundary edges of the patch, (2) avoids corner picking on a patch and solving NP hard internal matching algorithm to select divisions, (3) is extremely fast with time complexity of O(1) in template creation, and (4) has low memory footprint and is robust. To illustrate the concepts, we consider quadrilateral meshes generated using Abaqus, Gmsh, and Cubit, and reduce the singularities within these meshes.