Patent ID: 7750905

Claim:
A computer-based method for constructing a triangular mesh surface of a point cloud, the method comprising: (a) inputting point cloud data obtained by a point cloud obtaining device and a tolerance of the triangular mesh surface to be constructed to the computer; (b) determining a cubical figure that confines the point cloud, mapping a grid on the cubical figure to obtain a plurality of grid squares, and putting an ID of each point of the point cloud into a corresponding grid square; (c) acquiring a point that has not constructed any triangle with other points of the point cloud as a first point of a triangle; (d) obtaining grid squares surrounding the first point, and acquiring the point nearest to the first point in the grid squares surrounding the first point as a second point of the triangle; (e) obtaining a midpoint of the first point and the second point, obtaining grid squares surrounding the midpoint, and constructing the triangle by utilizing the first point, the second point and a point in the grid squares surrounding the midpoint; and wherein the step (e) comprises: arranging points in the grid squares surrounding the midpoint; determining whether each arranged point meets a first condition by fitting a circle based on the first point, the second point and the arranged point, wherein the first condition is that a diameter of each circle is greater than the tolerance; making obtuse angle judgment to confirm whether each point satisfying the first condition meets a second condition according to a triangle based on the first point, the second point and the point satisfying the first condition, wherein the second condition is sides of the triangle have not been used to construct any triangle with any other point of the point cloud, or an angle between a triangle constructed by one of the sides and the triangle is obtuse; making circumscribed sphere judgment for each point satisfying the second condition by fitting a circumscribed sphere based on the first point, the second point and the point satisfying the second condition; (f) repeating the steps from (c) to (e) for each point of the point cloud to construct a triangle, and outputting the triangular mesh surface of the point cloud that is constructed by all the triangles.