50 Jahre Uni Lübeck

Institut für Theoretische Informatik


Curve and Surface Reconstruction

Curve and surface reconstruction from a set of sample points is a problem occurring in many domains, e.g., reverse engineering, CAD, and data interpretation. Given a finite set S of sample points from an unknown curve or surface γ, reconstruct the curve or surface. In the case of a curve this means to connect two sample points if and only if they are adjacent on γ and in the case of a surface this means to construct a triangulated surface with vertices in S homeomorphic to γ. The figures below show sample sets and the reconstructed curve or surface, respectively.

The problems are well-studied since the early 80s and a number of effective heuristics were developed in the 80s and 90s. In the past 10 years, the research shifted to algorithms which come with a guarantee, i.e., which provably solve the problem for a certain class of curves or surfaces and for samples satisfying a certain sampling condition. 

The first algorithms worked for smooth closed curves. This was then extended to collections of open and closed smoothed curves, and finally to non-smooth curves (the example on the left illustrates such a reconstruction). In the case of surfaces, the case of smooth surfaces is solved. Current work investigates generalizations to non-smooth surfaces.