CAREER: Algorithms and Data Structures for Robust 3D Geometry Processing via Intrinsic Triangulations

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

This project develops methods that make it possible for users of geometric software to take advantage of a much larger fraction of available three-dimensional geometric data. We are currently witnessing an explosion in the availability of geometric data, driven by increasingly affordable and accessible technologies for 3D acquisition and digital manufacturing. Yet this data remains under-utilized across science, engineering, and medicine, since development of geometric software still demands sophisticated understanding of difficult low-level technical concepts (mesh generation, finite element methods, etc.). This research instead provides a reliable "black box" interface to geometric data, enabling non-expert users to focus their energy on higher-level application goals. The algorithms developed in this project will be applicable to a broad range of tasks ranging from structural engineering, to autonomous vehicle navigation, to development of virtual 3D environments, to analysis of medical data. The project will develop free and open source software that makes these algorithms immediately and broadly accessible. The project will also engage with both industry and the local "maker" community to evaluate the effectiveness of the new technology and to facilitate transfer to a diverse set of real-world users. Materials developed in this project will help to illuminate connections between discrete computational algorithms and differential geometry, offering rich opportunities for pedagogy and training of a diverse STEM workforce. The basic technical approach is to replace the standard notion of a surface or volume mesh with a so-called intrinsic triangulation. Such a triangulation can connect any two vertices of a polyhedral surface by an edge, whether or not they are connected via a straight line through space. Algorithms based on intrinsic triangulations are far less prone to failure, since they can freely adjust the triangulation to accommodate the demands of a given algorithm. A good analogy from numerical linear algebra is the use of matrix reordering to improve the numerical stability of linear solvers. In the same way, intrinsic triangulations improve the numerical stability of geometric algorithms. From a system-level point of view, intrinsic triangulations provide a valuable "bridge" between a large class of existing algorithms and challenging geometric data, enabling for instance 1) algorithms that were not originally designed to be numerically robust to be successfully run on extremely low-quality meshes; 2) algorithms that were originally formulated only for the flat plane to be applied to curved surfaces; and 3) algorithms designed for homogeneous, isotropic problems to be applied in more general inhomogeneous, anisotropic settings. The intrinsic approach also side-steps some fundamental, traditionally unavoidable challenges in geometric computing, such as the need to juggle the quality of geometric approximation with the quality of individual mesh elements. The project will specifically develop new data structures for both surface and volume meshes, and algorithms for geometric upsampling/downsampling, retriangulation, computing geodesic paths, solving anisotropic partial differential equations, processing tangent vector fields, and processing volumetric data. Methods developed in the project will be evaluated via large-scale data sets arising from industrial applications. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.