A new mesh-growing algorithm for fast surface reconstruction

By Randall Freeman,2014-06-23 21:33
13 views 0
A new mesh-growing algorithm for fast surface reconstruction

Computer-Aided Design

    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 2Simplex 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 twoSimplex 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

    Article Outline




    Related works

    2.1. The implicit methods

    2.2. The explicit methods

    2.2.1. Voronoi/Delaunay-based methods

    2.2.2. Mesh-growing methods


    Gabriel 2Simplex criterion


    Algorithm description

    4.1. Selection of the seed triangle

    4.2. Triangulation


    Experimental results

    5.1. Typical benchmarks

    5.2. Noisy point clouds




    1. Introduction

    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 2Simplex (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 [1] and [2]. 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

    [3] and


     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) [5] 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 ([8], [9], [10], [11], [12], [13] and [14]) 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 [8], 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 [9] 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 [2], 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 [10] and one suited for

    noisy data called Robust Cocone [11]. Dey et al. in [12] 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 [13]. 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 [15]

    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 [14]

    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 [16], 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. [17] 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 [18] 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