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.

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