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.