Nonlinear Curved Simplicial Meshing 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 structurally 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 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, physical simulation, relevant for accuracy and efficiency. 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.An ideal method for the generation of such nonlinear meshes can be expected to yield elements that are 1) boundary-conforming and 2) regular. A higher-order element is regular if it is defined through a polynomial or rational map of that order that is injective – an important prerequisite, e.g., in the finite element method and related techniques. Common higher-order meshing approaches, however, reliably achieve only one of these two important properties in general, not both. A recent result from the PI’s research group is a novel strategy that explicitly and systematically guarantees both properties by construction. It concerns nonlinear triangle meshes for 2D domains with curved boundary, and can be viewed as this project’s point of departure.In this project reliable algorithms for the generation of valid meshes of provably regular and conforming nonlinear elements are targeted. While the preliminary result is restricted to the special case of 2D piecewise polynomial boundaries, the goal is to support the general regime of practically relevant cases: 2D and 3D domains, polynomial and rational boundaries, C0 and higher-order continuity. This will fill a gap in the set of techniques required to further advance the utility and applicability of higher-order mesh based methods. It can relieve applications from the robustness issues still prevalent in the nonlinear mesh generation stage today – which are particularly pressing in increasingly common scenarios that require a fully automatic handling of large collections of objects or object variations.

• DFG Programme: Research Grants