Meshing a 3D Point cloud of an elevation surface based on 2D Delaunay Triangulation

Abstract

Geometric modeling is one of the most important methods to represent an object in multi-dimensional space. It’s widely used in many technical fields such as image processing 3D simulation, auto design, architecture, etc. Several techniques are used to obtain the data of point clouds such as 3D scanners that provides a huge amount of unorganized 3D point sets. The 3D Point clouds are used as input data in several applications such as reverse engineering, CAD modeling and animation technology and so on. Various methods are available for generating a triangular mesh from a 2D or 3D point cloud. They can be applied on both open and close surfaces. The main goal of this thesis is to the study some algorithms for meshing a surface of 3D point clouds. In this thesis, we first presented an algorithm proposed by Sinh N.V [1] that generates a triangular mesh from 3D point clouds. We then also proposed and implemented an addition work to reconstruct the surface by filling the holes of triangular mesh. The input data are 3D point clouds structured in a sparse 3D volume. The algorithm describes a triangulation of this surface based on Delaunay triangulation. Delaunay triangulation is one of the most popular methods used to generate a triangular mesh. In fact, we base on the advantage of 3D point structured in grid 3D and proposed a fast search algorithm [1] to obtain higher performance. We start by projecting the 3D point clouds onto a 2D grid in the x, y plane. Then, we triangulate the surface (actually, we compute a Delaunay triangulation of the 2D point cloud taking advantage of its regular structure). The new contribution of the proposed method is that the neighboring points of an edge ei are searched in a rectangle supported by the edge ei under consideration. This interesting algorithm has been implemented, the result obtained shows that the processing time is very fast, the initial shape of the surface is well preserved, and the topology of the output triangular mesh approximates the original input surface.