Shape reconstruction from unorganized points using Voronoi diagrams

Abstract

Given only a set of points, without any geometric information such as the adjacency among the points, the scanning order or the scanning direction, it is a difficult problem to reconstruct a surface model corresponding to the original shape. For the reconstruction of open shapes, many effective approaches have been proposed. It is, however, hard to find a robust and effective method for the reconstruction of closed shapes. In this paper, an algorithm is proposed to reconstruct a three-dimensional closed shape from a set of good sample points using the properties of Delaunay triangulation and Voronoi diagrams. The proposed method consists of three steps; (1) constructing a convex hull consisting of mutually exclusive tetrahedra by 3D Delaunay triangulation of input points, (2) generating a Voronoi diagram of input points by utilising the properties of Delaunay triangulation, and (3) extracting the triangles on the shape boundary, defined by input points, after selecting the tetrahedra which are contained inside the shape using the properties of Voronoi diagrams. The proposed method in this paper has some advantages compared to the previous approaches. First, the distance parameter, such as a in the a-shape approach, is not required in the proposed approach. The determination of a proper parameter by trial and error is not appropriate, especially in the automation of shape reconstruction. Secondly, the time complexity of the proposed approach is 0(n) since, in a single pass, this algorithm determines whether each tetrahedron is located inside or outside the shape boundary.