Facet-JFA: Faster computation of discrete Voronoi diagrams.
Talha Bin Masood, Hari Krishna Malladi and Vijay Natarajan.ICVGIP 2014: Proc. Indian Conference on Computer Vision, Graphics and Image Processing, 2014, 20:1-20:8.
Abstract
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.[PDF]
Supplementary Material:
- Facet-JFA: Faster computation of discrete Voronoi diagrams - Supplementary material. (Download)