A Beautiful and Relatively Old Algorithm for Surface Reconstruction

Title: A Beautiful and Relatively Old Algorithm for Surface Reconstruction

Abstract: This research article discusses a "wrapping" algorithm by Edelsbrunner for surface reconstruction. The algorithm reconstructs a unique surface from a given set of points without making assumptions about sample density or requiring adjustment of heuristic parameters. It relies on continuous mathematics and discrete methods, specifically the Delaunay complex. The algorithm works by finding a "wrapping" surface W, a connected simplicial subcomplex in Del S, by removing simplices from Del S one by one, following an acyclic partial ordering. This ordering is defined using a continuous function g(x) that assigns a value to every point x in R3, and a vector field ∇g derived from it. The flow curves of ∇g are used to define an acyclic relation on all the simplices of Del S and ø, ensuring that the relation is always acyclic. The algorithm starts with ø and methodically "collapses" its flow predecessors until no more collapses are possible, yielding the complex X.

Main Research Question: How can we develop an algorithm for surface reconstruction that reconstructs a unique surface without making assumptions about sample density or requiring adjustment of heuristic parameters?

Methodology: The methodology involves using continuous mathematics and discrete methods to develop an algorithm that reconstructs a unique surface from a given set of points. The algorithm relies on the Delaunay complex, a "proper" gluing together of simplicies, and the Voronoi diagram of S. The algorithm starts with the Delaunay complex and removes simplices one by one, following an acyclic partial ordering defined by a continuous function g(x) and a vector field ∇g derived from it. The flow curves of ∇g are used to define an acyclic relation on all the simplices of Del S and ø, ensuring that the relation is always acyclic.

Results: The results show that the algorithm successfully reconstructs a unique surface from a given set of points without making assumptions about sample density or requiring adjustment of heuristic parameters. The algorithm is able to find a "wrapping" surface W, a connected simplicial subcomplex in Del S, by removing simplices from Del S one by one, following an acyclic partial ordering.

Implications: The implications of this research are significant for the field of computational geometry. The algorithm provides a new and improved method for surface reconstruction that is more reliable and accurate than previous methods. It also offers insights into the development of algorithms for other geometric problems by demonstrating how continuous mathematics and discrete methods can be combined to solve complex problems.

Link to Article: https://arxiv.org/abs/0405034v1 Authors: arXiv ID: 0405034v1