Graph-based surface reconstruction using structures in scattered point sets

The authors present an algorithm for the reconstruction of a surface from an unorganized set of points in space. The point data may be obtained from a laser range scanner or any other digitizing tool to describe the shape of the object(s). The basic idea of the algorithm is to construct some kind of wire frame for the surface, the so-called surface description graph. This is performed by applying several steps. In the final part of the algorithm this wire frame is then filled with triangles. Each step uses rules for the reconstruction which are based on human knowledge in geometric structures. These rules are designed to allow the reconstruction of artificial objects as well as natural objects and are extendable in many aspects for ongoing research. As a result of this approach, the algorithm is able to reconstruct surfaces in data sites with changing point density as well as high curvature of the surface. In addition, it automatically recognizes the number of objects covered in the point set. Several examples are given to demonstrate its features.