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.