Research On Parallel Algorithm Of Voronoi Diagram In Surface Reconstruction

How to compute a piecewise linear approximation to a surface from a set of sampling points abstracted from the surface, which is called surface reconstruction terminologically, is a topic covers so many fields such as reverse engineering, medicine image processing.Consequently, many research on surface reconstruction have being made and many algorithms on it are also proposed, among which the reconstruction algorithm based on Voronoi diagram is widely used. However, with the rapid development of measure equipment, the point set people can obtain is so large that both construction speed of Voronoi diagram and surface reconstruction of those point set are slowing. Consequently, this paper mainly research parallel construction of Voronoi diagram.Firstly, four algorithms named Intersection, Increment, Plane Sweep and Divide-Conquer are systematicly studied, their parallel ability are analyzed. Especially, the parallel ability of Divide-Conquer algorithm is excavated, the merge algorithm which is a part of Divide-Conquer is improved. Then, a compare on the four algorithms'parallel ability is made by four aspects of whether or not paralleled, granularity, parallel degree and memory type.Secondly, base on above analysis on parallel ability, combine with the extensive use of dual-core compute, base on Plane Sweep algorithm,a parallel algorithm which is adaptive to dual-core compute is proposed. It can not only improves construction speed of Voronoi diagram but also assures load balance of dual-core by using parallel opposite sweep idea.Finally, base on Divide-Conquer algorithm, combine with the extensive of cluster system, a parallel algorithm which is adaptive to it is proposed. For solving the problem of complex merging in the parallel algorithm, a method named short wait is proposed, a dynamic list of nodes'state is designed, which can maintain correct implemented of the parallel algorithm and achieve dynamic merging.