Curve reconstruction from unstructured points in a plane is a fundamental problem with many applications that has generated research interest for decades. Involved aspects like handling open, sharp, multiple, and non-manifold outlines, runtime, and provability as well as its extension to 3D for surface reconstruction have led to many different algorithms. The presented algorithms spans the range from improved interpolation of manifold curves over fitting noisy points with better accuracy, requiring fewer points for successful reconstruction to proving the lower limit of required samples with regard to local feature size, or provable statistical accuracy for noise-infected samples. A new sampling condition is introduced that can be expressed as a simple function of the long-standing epsilon-sampling, and permits to reconstruct curves with even fewer samples. As a side product, an algorithm for sampling curves is designed as well. A survey paper compares this body of work with all related work in this now mature field and includes an open source benchmark that allows to easily evaluate competing algorithms in multiple aspects and highlights their relative strengths. For selected 2D algorithms, extensions to 3D are given, as well as offering many novel perspectives for 3D reconstruction, where important open problems remain. As a different topic, when visualizing point clouds, occlusion can be inferred for almost free by exploiting the fact that point clouds representing surfaces are inherently 2D and squashing them in a view-based 2D data structure. This permits novel real-time methods on large point clouds such as collision detection, surface processing like cutting or editing, and efficient exploration.
en
Research Areas:
Visual Computing and Human-Centered Technology: 100%
