Abstract: In surface reconstruction of underwater terrain,the commonly used method is to project point cloud data to two-dimensional plane,and use Delaunay triangulation algorithm to generate triangular grid,then combine the depth elevation value in order to restore to three-dimensional space.However,the efficiency of this method is low,and the depth elevation value is abandoned during projection,so it's easy to generate long and narrow triangles in three-dimensional space,which is not conducive to the display effect.Based on the point by point insertion method,the location of the insertion point and the local optimization procedure are improved respectively.The specific performance is as follows:a fusion location algorithm is proposed to find the search direction and locate after calculating the triangle vector area,so as to ensure the uniqueness of the location path and improve the efficiency.At the same time,the depth elevation value is introduced to the local optimization procedure.The standard deviation of triangle angle in three-dimensional space is calculated and used as the standard to measure the similarity to normal triangle.The criterion of empty circumscribed circle is replaced to make the gird more uniform in three-dimensional space.The experimental results show that this method is superior to the traditional Delaunay triangulation algorithm in terms of model quality and construction efficiency.

Key words: Delaunay triangulation, Local optimization, minimum standard deviation, point by point insertion, Underwater terrain