Volume 43, Issue 6, June 2011, Pages 639-650
doi:10.1016/j.cad.2011.02.012 | How to Cite or Link Using DOI
Permissions & Reprints
A new mesh-growing algorithm for fast surface reconstruction
a, a, aLuca Di Angelo, Paolo Di Stefanoand Luigi Giaccari
a Università degli Studi de L‘Aquila, Italy
Received 7 September 2010;
accepted 22 February 2011.
Available online 1 March 2011.
This paper presents a new high-performance method for triangular mesh generation based on a mesh-growing approach. Starting from a seed triangle, the algorithm grows the triangular mesh by selecting a new point based on the Gabriel 2—Simplex criterion. This criterion can be considered to be a good approximation of the 2D Delaunay if the point cloud is well-sampled and not too rough. The performance of the proposed method is compared with that of the Cocone family and that of Ball Pivoting
as regards the tessellation rate and the quality of the surface being generated from some benchmark point clouds and artificially noised test cases. The results are analysed and critically discussed. Highlights
? A new surface reconstruction method based on a mesh growing approach is presented. ? Surface reconstruction is carried out by using the Gabriel two—Simplex Criterion. ? For well-sampled and not
rough point clouds it is similar to the 2D Delaunay approach. ? The proposed method is competitive for
tessellation rate, quality and defectiveness.
Keywords: Surface reconstruction; Triangular meshes; Reverse engineering
2.1. The implicit methods
2.2. The explicit methods
2.2.1. Voronoi/Delaunay-based methods
2.2.2. Mesh-growing methods
Gabriel 2—Simplex criterion
4.1. Selection of the seed triangle
5.1. Typical benchmarks
5.2. Noisy point clouds
The process of constructing a triangular mesh from a point cloud which has been acquired from a 3D real object is known as a surface tessellation or reconstruction. The applications of the triangular meshing of 3D point clouds are wide-ranging and include Reverse Engineering, Collaborative Design, Inspection, Computer Vision, Dissemination of Museum artefacts, Medicine, Special Effects, Games and Virtual Worlds. For many of the already-mentioned applications, robustness, reliability and triangulation speed are important factors that are required in any tessellation method. Equally critical is the capability to tessellate according to the nature of the surface which is to be reconstructed.
Over the last few years 3D scanning systems have been offering high resolutions with a measuring accuracy as high as 10 μm, which, on the one hand, makes it possible to capture the smallest surface features but, on the other hand, generates very large data sets. The typical triangulation speed of the methods presented in literature may not be enough for the tessellation of a cloud with over one million
points. Furthermore, in analysing the peak memory usage of these algorithms, it becomes clear that most of them cannot be run on personal computers.
In order to overcome these limitations, this paper proposes a new algorithm. It is based on the concept of the Gabriel 2—Simplex (G2S). This concept allows us to extend 2D tessellation approaches to 3D triangulations. As long as point clouds are locally flat, the method being proposed guarantees a correct triangulation. Unlike some other methods presented in literature, the one being put forth does not require that the surface defined by the point cloud should enclose a volume or have a strictly uniform sampling. This method is tested for the tessellation of some benchmark point clouds and artificially noised test cases. The results derived from those experiments are critically discussed further down. 2. Related works
Numerous algorithms to tessellate point clouds are presented in literature. The more recent exhaustive overviews of 3D surface reconstruction methods are presented in  and . Surface reconstruction
algorithms are generally divided into two categories: implicit and explicit.
2.1. The implicit methods
Implicit methods seek to reconstruct an implicit function , where is either the whole point cloud or only a part of it. The final triangulation is obtained by extracting the iso-surface for . The most common methods define the implicit function as:
– the sum of radial basis functions (RBF) centred at the points
– a set of constraints that force the function to assume given values at the sample points and also force its upward gradient to match the assigned normal at the sample points (Moving Least Squares)  and
– a Poisson problem
These implicit methods carry out a watertight surface reconstruction also in the case of sparse and noisy data. However, these methods may generally require many computations and, sometimes, they may even need the surface normal at each data point. Moreover, the triangles of the final surface may not pass through all the points, and this in turn may imply the loss of some details of the shape of the original model. The more points we use to compute the implicit function, the higher will be the fitting accuracy and the longer will be the computation time.
2.2. The explicit methods
Explicit methods attempt to triangulate the points directly. In contrast with the implicit methods, they are less robust against noise although they are generally faster. The most common explicit methods can be classified into two main groups: Voronoi/Delaunay-based and mesh-growing approaches. 2.2.1. Voronoi/Delaunay-based methods
This first group includes algorithms that compute a volume tetrahedralisation by means of a 3D Delaunay triangulation of the sample points. The most important methods presented in the related literature (, , , , ,  and ) essentially differ in the way they remove the tetrahedra and build the external triangular mesh. In the Crust method, proposed by Amenta et al. in , the set of
candidate triangles (called Crust) are those having three vertices which are not poles. Since the Crust
is still not a manifold, in order to extract a topologically correct surface, a walking strategy is employed
2in candidate triangles. The worst time complexity of the Crust algorithm is Θ(m), where m is the
number of points and poles. In order to reduce running time and memory consumption, while still providing the same theoretical guarantees, Amenta et al. in  proposed an improvement of the Crust
algorithm, which they called Cocone. The candidate triangles are those triangles inside the Cocone
region that is the complement of a double cone which has its apex at the point under analysis () and an assigned opening angle and whose axis is the normal at . The Cocone’s worst time complexity is
2Θ(n), where n is the number of points. As pointed out by Chang et al. in , the theoretical guarantee
of obtaining a correct reconstruction with the Crust and Cocone methods is only possible as long as the
point cloud is well sampled. Dey and Goswami proposed other Cocone versions, one suited to provide
a watertight closed surface reconstruction, which they called Tight Cocone  and one suited for
noisy data called Robust Cocone . Dey et al. in  proposed the Super Cocone algorithm so as to
manage large amounts of data. In that method, the entire set of sample points is partitioned into smaller clusters using an octree subdivision, and the Cocone algorithm is applied to each cluster
separately. A further evolution of the Crust is the Power Crust proposed by Amenta et al. in . This
algorithm can generate a watertight mesh for any point cloud which is sampled enough but it could be non-manifold. Furthermore, sharp edges or noisy data can result in defectiveness. Gopi et al. in 
proposed a different approach which, for each sample point, provides the projection of the neighbouring points onto the approximating tangent plane and the tessellation of the projections by
means of a 2-D Delaunay triangulation. The 2D edges obtained are then applied to 3D space. With a view to enhancing the performance of the Delaunay-based methods, Cohen-Steiner and Da in 
proposed the Greedy algorithm, which selects the triangles sequentially. The selection of candidate
triangles is carried out by the plausibility grade, which is an empirical function of the circumradius and
the dihedral angle between adjacent triangles. As stated by Cazals and Giesen in , this method
―may fail to interpolate all points or to provide a closed surface essentially due to the presence of slivers‖.
2.2.2. Mesh-growing methods
Mesh-growing approaches generate the tessellated surface from a seed triangle and grow the meshed area pushing the fronts ahead by using some criteria. Over the last few years a number of algorithms have been presented. Bernardini et al.  introduced the Ball Pivoting algorithm, by which the front
grows as a ball of user-defined radius pivots around the front edge. When the ball touches three points, a new triangle is formed. Generally speaking, this method affords a correct triangulation for any uniform data point, which is also noisy, but which does not have any concave sharp features. Huang and Menq in  proposed an algorithm which, for each front edge, projects the k-nearest points of two endpoints onto the plane that is defined by the triangle adjacent to the front edge. Any point generating triangles whose edges intersect edges of already-existing triangles is discarded. Of the points which are