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.
