AF: Small: The Fixed Point of the Restricted Delauay Triangulation Operator, with Applications to Manifold Reconstruction and Mesh Generation

研究人员将研究曲面重建和网格生成的相关问题。曲面重建是从仅显示物体形状的数据创建几何模型(通常是曲面三角剖分)的问题。最常见的情况是，曲面重建算法的输入是由激光测距仪、立体摄影、医学图像、视频运动深度算法甚至物理探头从真实对象采样的点组成的点云。表面重建在计算工程中用来执行物理模拟，在计算机图形学中用来获取真实世界的几何图形，放在视频游戏和电影特效等虚拟环境中，以及在测量中用来获取一块土地或一组建筑物的几何图形。网格生成是将具有复杂几何图形的物理域--例如汽车发动机、人体血管或飞机周围的空气--分割成小而简单的小块，如三角形或四面体。网格生成中的一个重要问题是生成嵌入在三维中的曲面网格--具体地说，就是近似曲面的三角形网格。曲面网格在计算机图形学、几何建模和可视化中普遍存在，以往的研究大多是在2维或3维空间中进行的。有一种更高维的曲面重建方法，称为流形重建，通常用于科学数据分析。科学和工程中的许多过程都以高维属性空间中的点的形式产生数据。流形重构是发现约束点(近似)位于低维流形上的属性之间的关系的问题，该研究将流形重构和流形网格生成的算法推广到嵌入在d维环境空间中的k维流形上，其中k从2到可能10，d从3到10，甚至更大。研究人员还将生产并公开发布用于d维流形重建的软件和用于从极大的三维点云进行表面重建的核心外软件，以便科学家、工程师和几何建模人员可以使用这些方法进行数值模拟、计算机图形学和科学数据分析。这项工作将通过培训研究生和本科生在研究和几何算法方面影响加州大学伯克利分校的教育和推广。

The investigators will study the related problems of surface reconstruction and mesh generation. Surface reconstruction is the problem of creating geometric models (usually surface triangulations) from data that merely suggests the form of an object. Most commonly, the input to a surface reconstruction algorithm is a point cloud consisting of points that have been sampled from a real-world object by laser range finders, stereo photography, medical images, video depth-from-motion algorithms, or even physical probes. Surface reconstruction is used in computational engineering to perform physical simulations, in computer graphics to acquire real-world geometry to place in virtual environments such as videogames and movie special effects, and in surveying to acquire the geometry of a plot of land or a collection of buildings.Mesh generation is the problem of dividing a physical domain with a complicated geometry--say, an automobile engine, a human's blood vessels, or the air around an airplane--into small, simple pieces such as triangles or tetrahedra. An important problem within mesh generation is the generation of surface meshes embedded in three dimensions--specifically, triangle meshes that approximate curved surfaces. Surface meshes are ubiquitous in computer graphics, geometric modeling, and visualization.Most prior work on these topics has been set in 2- or 3-dimensional space. There is a higher-dimensional analog of surface reconstruction called manifold reconstruction, commonly used for scientific data analysis. Many processes in science and engineering produce data in the form of points in a high-dimensional space of attributes. Manifold reconstruction is the problem of discovering relationships between the attributes that restrict the points to lie (approximately) on a low-dimensional manifold.This research will generalize algorithms for manifold reconstruction and manifold mesh generation to operate on k-dimensional manifolds embedded in a d-dimensional ambient space, where k ranges from 2 to perhaps 10 and d ranges from 3 to 10,000 or even greater. The investigators will also produce and publicly release software for manifold reconstruction in d dimensions and out-of-core software for surface reconstruction from extremely large three-dimensional point clouds so that scientists, engineers, and geometric modelers can use the methods for numerical simulation, computer graphics, and scientific data analysis. The work will impact education and outreach at U.C. Berkeley by training graduate and undergraduate students in research and geometric algorithms.