July 1992 | Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, Werner Stuetzle
This paper presents an algorithm for surface reconstruction from unorganized points in 3D space. The algorithm takes as input a set of points on or near an unknown surface and produces a simplicial surface that approximates the surface. The algorithm does not assume any prior knowledge of the surface's topology, boundaries, or geometry, and instead infers these properties automatically from the data. The algorithm is demonstrated on various practical applications such as range scanning, biological shape recovery, and interactive surface sketching.
The algorithm consists of two main stages. In the first stage, a function is defined that estimates the signed geometric distance to the unknown surface. The zero set of this function is used as an estimate of the surface. In the second stage, a contouring algorithm is used to approximate the zero set by a simplicial surface.
The first stage involves estimating tangent planes for each data point. These tangent planes are used to define the signed distance function. The orientation of these tangent planes is determined through a graph optimization process that ensures consistency across the surface.
The second stage involves contouring the signed distance function to produce a simplicial surface. The algorithm uses a variation of the marching cubes algorithm to sample the function and find contour intersections. The resulting surface is then post-processed to improve the aspect ratio of triangles.
The algorithm is tested on various data sets, including points sampled from existing surfaces, ray-traced points, range images, and contour data. The results show that the algorithm can accurately reconstruct surfaces with complex geometries and topologies. The algorithm is capable of automatically inferring the topological type of the surface, including the presence of boundary curves. The algorithm is also capable of reconstructing manifolds of co-dimension one in spaces of arbitrary dimension. Future work includes improving the geometric accuracy of the fit and reducing the space required to store the reconstruction.This paper presents an algorithm for surface reconstruction from unorganized points in 3D space. The algorithm takes as input a set of points on or near an unknown surface and produces a simplicial surface that approximates the surface. The algorithm does not assume any prior knowledge of the surface's topology, boundaries, or geometry, and instead infers these properties automatically from the data. The algorithm is demonstrated on various practical applications such as range scanning, biological shape recovery, and interactive surface sketching.
The algorithm consists of two main stages. In the first stage, a function is defined that estimates the signed geometric distance to the unknown surface. The zero set of this function is used as an estimate of the surface. In the second stage, a contouring algorithm is used to approximate the zero set by a simplicial surface.
The first stage involves estimating tangent planes for each data point. These tangent planes are used to define the signed distance function. The orientation of these tangent planes is determined through a graph optimization process that ensures consistency across the surface.
The second stage involves contouring the signed distance function to produce a simplicial surface. The algorithm uses a variation of the marching cubes algorithm to sample the function and find contour intersections. The resulting surface is then post-processed to improve the aspect ratio of triangles.
The algorithm is tested on various data sets, including points sampled from existing surfaces, ray-traced points, range images, and contour data. The results show that the algorithm can accurately reconstruct surfaces with complex geometries and topologies. The algorithm is capable of automatically inferring the topological type of the surface, including the presence of boundary curves. The algorithm is also capable of reconstructing manifolds of co-dimension one in spaces of arbitrary dimension. Future work includes improving the geometric accuracy of the fit and reducing the space required to store the reconstruction.