Tessellation using Lloyd relaxation on the surface

To generate a triangular mesh from the points cloud of object surface, which is topologically equivalent to the implicit surface and also close in a geometric sense, is important in computer graphics modeling area. This paper presents a Lloyd relaxation based method for generating a tessellation from a set of points sampled from a surface. First by randomly choosing some sample points from the input points cloud, the number of sample points can be specified; then extended Lloyd relaxation is used to move the sample points along the surface; after an even distribution of the sample points on the surface is achieved, an improved "crust" algorithm will be used to generate a triangular mesh from the sample points. To make a triangular mesh geometrically close, we reduce the volume between the mesh and the surface in every loop. The experimental result shows that the method can generate triangle mesh from the points cloud correctly. It can be used in surface reconstruction and mesh simplification.