surface tessellation
The process of generating a triangular mesh from a point cloud is denoted as surface tessellation or reconstruction. The applications of the triangular meshing obtained from scanned point clouds include:
For all these applications, the meshes obtained must:
- Reverse Engineering;
- Collaborative Design;
- Inspection;
- Computer Vision;
- Dissemination of Museum artefacts;
- Medicine;
- Movie Special Effects;
- Games and Virtual Worlds.
Those objectives are hard to be achieved since scanned point clouds are noisy, badly sampled in some areas and non-uniformly sampled. Even the methods, which are considered to be very robust, can generate defectiveness in the mesh such as:
- match the original data set in terms of geometric and topological criteria;
- preserve the natural adjacency between points on the object surface;
- reconstruct also the smallest surface features reconstruction.
- twisted surfaces: this problem arises in correspondence of noisy or under sampled areas ;
- non-manifold vertices: vertices for which the incident triangles form more than one fan as in the cases depicted in the following figure;
- non-manifold edges: edges having more than two incident triangles;
- holes: unmeshed areas;
Furthermore it is required that an algorithm for triangular mesh generation must be robust, reliable and speedy so that very large data sets can be triangulated. Most of the methods presented in literature are not enough speed for the tessellation of a cloud with over one million points and, due to the computing capability required, cannot be run on personal computers. Our research group is developing a new and high-performance mesh-growing algorithm for triangular mesh generation based on the Gabriel 2 - Simplex criterion. This method, 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) show to be advantageous even in the case of very noised point clouds. Unlike the Cocone family and Ball Pivoting methods, our method is preserves manifoldness and also little geometric details of the point cloud are adequately meshed.
In the following figures (click to enlarge) renderings of three test cases generated and illustrative video of the proposed method are reported:
Details of our method are reported in:
Di Angelo L., Di Stefano P., Giaccari L., "A new mesh-growing
algorithm for fast surface reconstruction". Computer - Aided Design,
vol. 43 (6), 2011, p. 639-650, ISSN: 0010-4485.-
Di Angelo L., Di Stefano P., Giaccari L., "A fast algorithm for
manifold reconstruction of surfaces".In Proceedings of IMProVe -
International conference on Innovative Methods in Product Design,
June 15 - 17 2011, San Servolo, Venice, Italy, ISBN:
978-88-7784-328-9.
Di Angelo L., Di Stefano P.,
Giaccari L., “A Fast Mesh-Growing Algorithm For Manifold Surface
Reconstruction”. Computer – Aided Design and Applications, vol. 10
(2), 2013, p. 197-220, ISSN: 1686-4360.