New triangulation method for surface scattered points

Triangulations for surface scattered points are used in the field of three-dimensional reconstruction widely. In order to reconstruct surface fast and efficiently, a combination triangulation algorithm was proposed. The triangulation method includes three steps: firstly, the scattered points were carved into many regions by the Axis-Aligned Bounding Box algorithm, then searched k-Neighbor points of each scattered points and constructed its tangent plane, transformed 3D triangulation into 2D triangulation. Secondly, direct triangulation were carried out according to the criterion of different side rule; the angle of two normal vectors maximized rule; the threshold distance rule of semisphere and the internal minimal angle maximized rule. Finally, each region were connected or spliced by 3D Delaunay circumsphere rule. Experiment results shows that the combination algorithm can triangulate the scattered points precisely and efficiently.