科研之友
微信
新浪微博
Facebook
分享链接
摘要
power图(加权Voronoi图)的计算是计算机图形学和计算几何等领域的一项基础任务.针对求解三维power图的传统串行方法所需的时间成本较高,且现有并行算法所得结果为近似解,提出一种新颖的GPU并行计算方法.首先给出power图与高一维受限Voronoi图的等价构造方法,将Voronoi图的无网格方法直接推广到power图的计算.因此,给定的加权种子点被置于更高一维空间中的一组方格内,据此快速搜索每个种子点的邻居关系,进而使用各个种子点与其若干个邻居的中垂面对各自的power胞元进行并行裁剪,以快速地获取三维空间中的精确power图.对比不同求解域下和5万个种子点的计算耗时,比现有方法具有超过3倍的加速比.
-
单位南昌大学软件学院
