A robust combinatorial approach to reduce singularities in quadrilateral meshes. (April 2017)

• Record Type: Journal Article
• Authors: Verma, Chaman Singh; Suresh, Krishnan
• Is Part Of: Computer aided design. Volume 85(2017)
• Page Start: 99
• Page End: 110
• Publication Date: 2017-04
• Subjects: Quadrilateral mesh generation -- Singularities -- Quad templates; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2016.07.008
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: There are many automatic quadrilateral mesh generators that can produce a 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 a 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 can be transformed into a patch that 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 interval 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. Besides improving the topological quality of an existing quad mesh, we describe two additional algorithms that exploit the above MST operations to (1) generate an ab-initio high-quality quadrilateral mesh in a complex domain, and (2) convert a quad-dominant mesh to a pure quadrilateral mesh. Highlights: We provideMinimum Singularity Templates which reduce singularities in a quad-mesh. Our approach is inexpensive, deterministic, efficient, and simple. Singularity reduction is supported by a theory. We extend it to generate a high-quality quad mesh and convert a quad dominant mesh to a pure quad-mesh.