ΑMST: A robust unified algorithm for quadrilateral mesh adaptation in 2D and 3D. (October 2018)

• Record Type: Journal Article
• Authors: Verma, Chaman Singh; Suresh, Krishnan
• Is Part Of: Computer aided design. Volume 103(2018)
• Page Start: 47
• Page End: 60
• Publication Date: 2018-10
• 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.2017.11.003
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: Mesh adaptation plays a critical role in balancing computational efficiency and numerical accuracy. Three types of mesh adaptation techniques exist today, namely, mesh improvement, mesh refinement and mesh simplification, and, for each of these, several algorithms have been proposed. Current mesh adaptation algorithms yield acceptable geometric mesh quality, but provide limited control over topological quality. In this paper, we introduce a unified algorithm for all three types of mesh adaptation, specifically for quadrilateral meshes. The algorithm builds upon the Minimum Singularity Templates (MST) proposed by the authors for improving the topological quality of a quadrilateral mesh. The MST is extended here to define the concept of an α MST where a single parameter α controls mesh adaptation: α = 1 for mesh improvement, α > 1 for mesh refinement, and α < 1 for mesh simplification. The proposed algorithm generates a mesh that is adapted to user requirements of high geometric and topological qualities. Further, it is non-hierarchical and stateless, and yet it provides an arbitrary level of mesh adaptation. Finally, since cyclic chords can play an important role in quadrilateral mesh adaptation, we provide a simple constructive algorithm to insert such chords using α MST. The proposed α MST templates can also be used to improve surface quadrilateral meshes using conformal mapping of surface charts. Furthermore, rotating the templates in the direction of cross-fields allows mesh edges to align along curvature lines. The proposed 3D generalization is fast, scalable, and inexpensive while improving alignment, shape, size, and sparsely placing the singularities. Several examples (both in 2D/3D) are presented that demonstrate the robustness, efficiency, and versatility of the proposed concept and algorithm. Highlights: We introduce a unified algorithm for all three types of mesh adaptation, specifically for quadrilateral meshes. The algorithm builds upon the Minimum Singularity Templates (MST) proposed by the authors for improving the topological quality of a quadrilateral mesh. The MST is extended here to define the concept of an α MST where a single parameter controls mesh adaptation: α = 1 for mesh improvement, α > 1 for mesh refinement, and α < 1 for mesh simplification. The proposed algorithm generates and adapt a mesh per user requirements, with high geometric and topological qualities. It is non-hierarchical and stateless, and yet it provides an arbitrary level of mesh adaptation. Since cyclic chords can play an important role in quadrilateral mesh adaptation, we provide a simple constructive algorithm to insert such chords using α MST. The proposed α MST templates can also be used to improve surface quadrilateral meshes using conformal mapping of surface charts. Furthermore, rotating the templates in the direction of cross-fields allows mesh edges to align along curvature lines. The proposed 3D generalization is fast, scalable, and inexpensive while improving alignment, shape, size, and sparsely placing the singularities.