HOMEO: Higher-Order Mesh Optimization with Guarantees

• Applicant: Professor Dr. Marcel Campen
• Subject Area: Image and Language Processing, Computer Graphics and Visualisation, Human Computer Interaction, Ubiquitous and Wearable Computing
• Term: since 2021
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 451286978

Partitioning complex 2D or 3D objects into simple elements (such as triangles or tetrahedra) is at the heart of computational tasks in simulation, analysis, design, fabrication, animation, and computer graphics. Based on meshes of such elements, function spaces can be defined that these computational tasks can rigorously build on. The demand for such meshes has led to major research efforts in the field of algorithmic mesh generation over the past decades. The general task is: given a description of a 2D or 3D object’s boundary, automatically construct a mesh representation of its interior, meeting application-dependent quality requirements. The main focus has been on linear meshes, with straight edges. In the common case that an object’s boundary is not piecewise straight or planar, however, they can only approximately represent the object; the mesh is not conforming with the boundary. Accurate conformance, however, is an important ingredient in demanding applications, e.g., in numerical analysis and physical simulation. An exact, error-free representation is enabled by the use of more general nonlinear elements. In particular, higher-order polynomial or rational curved elements are able to exactly conform to industry standard curved object boundary representations. The potential of methods built on such higher-order meshes has been demonstrated manifoldly. Recent developments have made possible the reliable automatic generation of such nonlinear curved meshes, with strong guarantees regarding their validity. A mesh is considered valid if it, as desired, conforms with the given boundary and is free of defects like degeneracies or inversions – an important prerequisite, e.g., in the finite element method and related techniques. Unfortunately, methods that guarantee mesh validity, do so by largely ignoring mesh quality. In other words, while the resulting meshes are technically fit to be used, meeting all the hard requirements, additional soft desiderata that may not be crucial for correctness but highly relevant for, e.g., efficiency and accuracy, thus practicality, are not respected well. In this project reliable algorithms for the generation of nonlinear meshes that are both, valid and of high quality, are targeted. It revolves around the idea of building upon the above mentioned guaranteeing methods, exploiting their output meshes as valid starting points for systematic optimization. In this process mesh quality is improved, using novel strategies and operators to efficiently and effectively address both, the problem’s continuous and its discrete or combinatorial degrees of freedom – while ensuring that the so carefully established validity is preserved. Multiple types of quality objectives, from parsimony to notions of element distortion, are targeted. The project’s results thereby ultimately enable advancing the utility and applicability of higher-order mesh based methods.

• DFG Programme: Research Grants