Implementation-friendly Geometric Algorithms for Provable Surface and Volume Meshing

用于可证明表面和体积网格划分的易于实施的几何算法

• 批准号: 0430735
• 负责人: Tamal Dey
• 金额: --
• 依托单位: Ohio State University Research Foundation -DO NOT USE
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-01 至 2008-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0430735&HistoricalAwards=false
• 关键词: Implementation; friendly; Geometric; Algorithms; Provable

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.

知识分子的优点：科学和工程中的许多应用都需要将表面或体积用于三角剖分。 这个问题出现在分子建模的微观层次和汽车设计中的宏观水平，在自然现象的科学研究以及人造机床和家具的工程中。随着应用程序的各种方式，其输入的类型也是如此。 对于许多这些输入域而言，几乎不存在可证明的算法。结果，许多商业产品满足了巨大的优质网格需求，这取决于通常会产生较差网格的启发式方法。这项研究将填补对各种输入域的质量网格的需求与可以保证正确的算法和软件之间的差异。为此，这项研究将认为输入与隐式，参数，点采样，多面体，分段平滑表面以及它们所包含的体积一样多样。这些输入中的每一个都构成了同类独特的困难。 该项目将重点介绍基于这些输入域的可证明的网格划分算法和软件系统的设计和分析。BRODERIMPACT：该项目中开发的工具将使网格划分复杂的几何形状具有保证，并使用它们增强进一步的分析。这将影响科学和工程领域的各个领域，包括物理学，生物学，环境科学，计算机辅助设计，制造，医疗保健，娱乐等。发展将影响计算几何，计算拓扑，几何学建模，计算机图形和可视化领域的研究。课程注释，通过该项目开发的研讨会和软件系统将使教育工作者和学生能够在正式环境中以确保正确性来攻击网络问题。