Research And Implementation Of Limited Voronoi Diagram Generation Based On Multi-Core Environment

As a basic data structure element of discrete space division, Voronoi mesh is an important research direction in the field of computational geometry. Because of the characteristic of perpendicular bisector, Voronoi mesh especially suitable for solving some physical problems related to conservation nature by the method of finite volume, such as fluid flow, heat conduction and so on. However, in these application areas, the generation of the Voronoi diagram has a special qualification, take the example of reservoir simulation, the Voronoi mesh can not cross some physical barriers, like the border and faults. For some particular points, such as horizontal well and vertical well must be the center of the Voronoi mesh. Consider the requirement of constructing limited Voronoi mesh in some practical applications and the problem of constructing high-quality Voronoi mesh under the complex constrained conditions through large-scale data processing, research and implementation of limited Voronoi mesh generation and its parallel algorithms is necessary.Under the computing ability of single-core, using large-scale data to generate limited Voronoi mesh is low efficiency and its calculation time can not be accepted, however, using the large-scale parallel processor for data processing needs high cost, and it's not convenient to operation. With the rapid development of hardware and processor, heterogeneous multi-core has become the main trend of high performance computing. In this paper, we present a available and efficient Voronoi mesh generation parallel algorithm by using MPI parallel programming language under the environment of multi-core, the specific research and content as the follows:(1) Implementation the algorithm of Constructing Voronoi mesh by the indirect method, which is high-quality but low efficiency.(2) Consider the parallel algorithm, we use the optimal algorithm of divide and conquer to achieve limited Voronoi mesh generation. According to the two qualifications (the principles of limited point and limited line), we make analysis and processing on each limited situation, which is prepare for constructing high-quality mesh generation latter. (3) Constructing limited Voronoi mesh of large-scale point set by optimal algorithm-Divide and Conquer alrgorithm, we also design and modify the parallel data structure-doubly-connected edge list, which is easy to conform parallel processing and complex features of complex limited boundary.(4) Using MPI and C programming language, according to the gradually merge in the whole parallel program, we do the parallel processing of reasonable distribution of point and constructing limited Voronoi mesh generation. We run the program under the environment of on the HP large-scale parallel machine and heterogeneous multi-core machine, and get its experimental results.(5) Achieve the Voronoi diagram transform to its dual diagram-Delaunay diagram, and realize real-time graphics display by ultimate data processing.Based on the content of this paper, we can apply our research results on the fields of fluid flow simulation, modeling drawing and so on. Combined with multi-core processors and the rapid development of parallel computing, we can use this parallel algorithm to solve many problems of real-time computing related to simulation. Finally, the future research direction of Voronoi diagram is presented.