Facet-JFA: Faster computation of discrete Voronoi diagrams
Facet-JFA: Faster computation of discrete Voronoi diagrams
复制标题
Facet-JFA：更快地计算离散 Voronoi 图
DOI：
10.1145/2683483.2683503
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
V. Natarajan
中科院分区：
文献类型：
--
作者：
Talha Bin Masood;Haritha Malladi;V. Natarajan
跳跃泛洪是一种从不同种子跨给定平面传播标签的方法。它已被用于计算给定平面的离散Voronoi细分。我们介绍了JFA的一个版本，它通过只计算Voronoi细分的面来优化处理的像素数。不处理Voronoi区域内部的像素，从而产生2D中的Voronoi细分的1骨架表示和3D中的2骨架表示。我们描述了该算法在使用CUDA的GPU上的实现，并展示了它在多个数据集上的性能优势。作为该算法的应用，我们提出了一种基于GPU的生物分子通道中心线提取方法。利用离散Voronoi图的快速计算来实时提取分子动力学模拟轨迹中的通道，从而支持对静态和动态通道结构的交互式可视化分析。
Jump Flooding is a method for propagating labels across a given plane from different seeds. It has been used to compute the discrete Voronoi tessellation of a given plane efficiently. We introduce a version of JFA, which optimizes the number of pixels processed by computing only the faces of the Voronoi tessellation. The pixels in the interior of the Voronoi regions are not processed resulting in a 1-skeleton representation of the Voronoi tessellation in 2D and a 2-skeleton representation in 3D. We describe an implementation of this algorithm on a GPU using CUDA and demonstrate its performance benefits on multiple data sets. As an application of the proposed algorithm, we present a GPU based method for extraction of channel centerlines in biomolecules. The fast computation of the discrete Voronoi diagram is exploited to extract channels in molecular dynamics simulation trajectories on-the-fly, thereby supporting the interactive visual analysis of static and dynamic channel structures.