3D-power图的快速生成方法

桂志强，姚裕友，张高峰，徐本柱，郑利平

（合肥工业大学 计算机与信息学院，安徽合肥230009）

0 引 言

Voronoi图在日常生活和自然界中普遍存在，因其优良的几何特性，被广泛应用于可视化、几何建模、建造设计等领域。power图是Voronoi图的扩展，即对Voronoi图站点引入权重概念，并重新定义距离。对power图的区域施加容量限制，得到容量限制power图（capacity constrained power diagram，CCPD）。进一步对CCPD站点施加质心限制，得到质心容量限制 power图（centroidal capacity constrained power diagram，CCCPD）。

Power图因其优良的特性被广泛应用于2D平面中的采样和点画［1］、蓝噪声［2-4］、计算机动画［5］、3D空间流体仿真［6-8］等。

AURENHAMMER［9-10］提出power图的概念，并对power图的性质、应用进行了总结，提出用分治法构建power图；BALZER等提出用“试位法”优化 容 量 约 束，给 出 有 限 区 域［11］和 连 续 区 域［12］的CCPD算法，但时间复杂度较高，且收敛性差；GOES等［2］提 出 用 牛 顿 法 优 化 权 重，并 结 合MULLEN等［13］提出的自适应步长梯度下降法优化质心位置，二者交替迭代，生成CCCPD，但优化过程中存在相互干扰，收敛速度较慢；XIN等［14］提出一种超线性收敛算法，将L-BFGS与牛顿法相结合，生成CCCPD。

相对2D领域，3D-power图的生成复杂性大幅提升，目前大部分研究聚焦于3D-Voronoi图［15-16］，并未将其推广至power图领域，其可能性和适应性也未得到充分证明；YAN等［17］提出了一种以计算几何算法库（computational geometry algorithms library，CGAL）［18］为基础，用边界剪裁方法计算3DVoronoi图 的 算 法；RAY等［19］提 出 了 无 网 格3DVoronoi图的图形处理器（graphics processing unit，GPU）算法；LIU等［20］在YAN等［17］的基础上提出了基于GPU的3D-Voronoi图计算算法。

GOES等［6］实现了基于VORO++［21］的线程安全的并行power图构造算法，计算效率得到较大提高；ZHAI等［8］根 据VORO++提 出 了 一 种 基 于GPU的裁切并行算法。这些算法适用于站点分布较为均匀的情况，如流体仿真的power图，对随机分布的站点表现不佳。……