Implementation-friendly Geometric Algorithms for Provable Surface and Volume Meshing

智力优势：在科学和工程中的许多应用都需要将曲面或体积网格化成三角剖分。这个问题出现在分子建模的微观层面上，出现在汽车设计的宏观层面上，出现在自然现象的科学研究中，出现在人造机床和电器的工程中。由于应用程序多种多样，其输入的类型也是如此。对于这些输入域中的许多，几乎没有可证明的算法。因此，许多迎合高质量啮合的巨大需求的商业产品依赖于启发式算法，而启发式算法往往会产生糟糕的网格。这项研究将填补各种输入域对高质量网格划分的需求与能够在保证正确性的情况下实现该需求的算法和软件之间的差距。为此，本研究将考虑各种输入，如隐式的、参数的、点采样的、多面体的、分段光滑的曲面以及它们所包围的体积。这些投入中的每一项都带来了独一无二的困难。该项目将专注于为这些输入域设计和分析可证明的网格划分算法和基于这些算法的软件系统。广泛的影响：本项目中开发的工具将能够在保证的情况下对复杂的几何图形进行网格划分，并增强使用这些工具的进一步分析。这将影响多个科学和工程领域，包括物理、生物、环境科学、计算机辅助设计、制造、医疗保健、娱乐等，并将影响计算几何、计算拓扑、几何建模、计算机图形学和可视化等领域的研究。通过该项目开发的课程笔记、研讨会和软件系统将使教育工作者和学生能够在正式环境中解决啮合问题，并保证正确性。

Intellectual Merit:Numerous applications in science and engineering require meshing a surface or a volume into a triangulation. The problem arises at the micro-level in molecular modeling and at the macro-level in automotive designs, in the scientific study of natural phenomena and in the engineering of man-made machine tools and appliances. As varied the applications are, so are the types of their inputs. Almost no provable algorithm exists for many of these input domains. As a result, many of the commercial products catering to the huge needs for quality meshing rely on heuristics which often produce poor meshes. This research will fill the gap between the need for quality meshing of a variety of input domains and the algorithm and software that can achieve it with guaranteed correctness. To this end, this research will consider inputs as varied as implicit, parametric, point-sampled, polyhedral, piecewise smooth surfaces as well as volumes enclosed by them. Each of these inputs poses difficulties that are unique to its kind. The project will focus on the design and analysis of the provable meshing algorithms and software systems based on them for these input domains.Broader Impact:The developed tools in this project will enable meshing complicated geometry with guarantees and enhance further analysis using them. This will impact a variety of areas in science and engineering including physics, biology, environmental science, computer aided designs, manufacturing, health care, entertainment and so on.The development will influence the research in the areas of computational geometry, computational topology, geometric modeling, computer graphics and visualization. Course notes, seminars and software systems developed through the project will enable educators and students to attack meshing problems in a formal setting with guaranteed correctness.