Nonlinear Curved Simplicial Meshing with Guarantees

将复杂的2D或3D对象划分为结构简单的元素（如三角形或四面体）是仿真、分析、设计、制造、动画和计算机图形学中计算任务的核心。基于这些元素的网格，可以定义这些计算任务可以严格构建的函数空间。在过去的几十年里，对这种网格的需求导致了算法网格生成领域的主要研究工作。一般任务是：给定2D或3D对象的边界描述，自动构建其内部的网格表示，满足与应用相关的质量要求。主要的焦点是线性网格，有直边。然而，在物体的边界不是分段平面的一般情况下，它们只能近似地表示该物体；网格与边界不一致。然而，准确的一致性在要求苛刻的应用中是一个重要的组成部分，例如在数值分析，物理模拟中，与准确性和效率有关。通过使用更一般的非线性元素，可以实现精确的、无错误的表示。特别是，高阶多项式或有理曲线元素能够完全符合行业标准的曲线对象边界表示。建立在这种高阶网格上的方法的潜力已经得到了多方面的证明。生成这种非线性网格的理想方法可以期望生成1)符合边界和2)规则的单元。一个高阶元素是正则的，如果它是通过该阶的多项式或有理映射定义的，并且是内射的——这是一个重要的先决条件，例如，在有限元方法和相关技术中。然而，常见的高阶网格划分方法通常只能可靠地实现这两个重要属性中的一个，而不是两个。PI研究小组最近的一项成果是一种新颖的策略，通过构建明确而系统地保证了这两种属性。它涉及具有弯曲边界的二维域的非线性三角形网格，可以视为本项目的出发点。本课题主要研究可证明规则和符合非线性单元有效网格生成的可靠算法。虽然初步结果仅限于2D分段多项式边界的特殊情况，但目标是支持实际相关情况的一般制度：2D和3D域，多项式和有理边界，C0和高阶连续性。这将填补进一步提高基于高阶网格的方法的实用性和适用性所需的技术集的空白。它可以减轻应用程序在非线性网格生成阶段仍然普遍存在的鲁棒性问题，这在需要全自动处理大量对象或对象变化的日益常见的场景中尤为紧迫。

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.