三维精确power图的GPU并行计算
Parallel Computation of Exact Power Diagrams in 3D Space on GPU
-
摘要: power图 (加权Voronoi图) 在计算机仿真和图形学等领域具有广泛的应用, 其快速且精确的计算是一项基础任务. 然而, 求解三维power图的传统方法所需的时间成本较高. 虽然已经有并行算法被提出, 但其所得的结果为近似power图. 本文提出了一种新颖的GPU并行计算方法, 能够快速获取三维空间中的精确power图. 给定的加权种子点首先被置于更高一维空间中的一组方格内, 据此可快速搜索每个种子点的邻居关系, 进而使用各个种子点与其若干个邻居的中垂面对各自的power胞元进行并行裁剪. 实验结果表明, 本文方法比现有方法具有较高的精度和效率优势.Abstract: Power diagram (weighted Voronoi diagram) has been widely used in various fields including computer graphics and simulations, its fast and exact computation is a fundamental task in many applications. However, the time cost required to compute 3D power diagrams still stays at a high level. Despite some parallel algorithms having been developed, they produce approximating results of power diagrams. We propose a novel parallel computation method with the assistance of GPU, which enables us to efficiently obtain the exact power diagrams in 3D space. The given weighted sites are first placed into a set of grids in the space with one dimension higher, based on which the neighbors of each site can be identified quickly, then the power cells are clipped in parallel by using the bisectors between the corresponding site and the neighbors. Experimental results demonstrate that our method has remarkable advantages in terms of accuracy and efficiency compared with existing methods.