Reconstruction of 2D polygonal curves and 3D triangular surfaces via clustering of Delaunay circles/spheres

A simple and efficient method is presented in this paper to reliably reconstruct 2D polygonal curves and 3D triangular surfaces from discrete points based on the respective clustering of Delaunay circles and spheres. A Delaunay circle is the circumcircle of a Delaunay triangle in the 2D space, and a Delaunay sphere is the circumsphere of a Delaunay tetrahedron in the 3D space. The basic concept of the presented method is that all the incident Delaunay circles/spheres of a point are supposed to be clustered into two groups along the original curve/surface with satisfactory point density. The required point density is considered equivalent to that of meeting the well-documented rr-sampling condition. With the clustering of Delaunay circles/spheres at each point, an initial partial mesh can be generated. An extrapolation heuristic is then applied to reconstructing the remainder mesh, often around sharp corners. This leads to the unique benefit of the presented method that point density around sharp corners does not have to be infinite. Implementation results have shown that the presented method can correctly reconstruct 2D curves and 3D surfaces for known point cloud data sets employed in the literature.

► A unified scheme to process points from both smooth regions and sharp corners.
► Simple implementation without the need of any user-tuned parameters.
► Improved computational efficiency: meshing time is in general only a fraction of the Delaunay triangulation time.