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.