Jump flooding algorithm

From HandWiki
Short description: Class of algorithms used for computing distance-related functions

The jump flooding algorithm (JFA) is a flooding algorithm used in the construction of Voronoi diagrams and distance transforms. The JFA was introduced at an ACM symposium in 2006.[1]

The JFA has desirable attributes in GPU computation, notably constant-time performance. However, it does not always compute the correct result for every pixel, although in practice errors are few and the magnitude of errors is generally small.[1]

Implementation

The JFA original formulation is simple to implement.

Take an [math]\displaystyle{ N \times N }[/math] grid of pixels[2] (like an image or texture). All pixels will start with an "undefined" color unless it is a uniquely-colored "seed" pixel. As the JFA progresses, each undefined pixel will be filled with a color corresponding to that of a seed pixel.

For each step size [math]\displaystyle{ k \in \{\frac N 2, \frac N 4, \dots, 1\} }[/math], run one iteration of the JFA:

Iterate over every pixel [math]\displaystyle{ p }[/math] at [math]\displaystyle{ (x, y) }[/math].
For each neighbor [math]\displaystyle{ q }[/math] at [math]\displaystyle{ (x+i, y+j) }[/math] where [math]\displaystyle{ i,j \in \{-k, 0, k\} }[/math]:
if [math]\displaystyle{ p }[/math] is undefined and [math]\displaystyle{ q }[/math] is colored, change [math]\displaystyle{ p }[/math]'s color to [math]\displaystyle{ q }[/math]'s
if [math]\displaystyle{ p }[/math] is colored and [math]\displaystyle{ q }[/math] is colored, if [math]\displaystyle{ dist(p, s) \gt dist(p, s') }[/math] where [math]\displaystyle{ s }[/math] and [math]\displaystyle{ s' }[/math] are the seed pixels for [math]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math], respectively, then change [math]\displaystyle{ p }[/math]'s color to [math]\displaystyle{ q }[/math]'s.

Note that pixels may change color more than once in each step, and that the JFA does not specify a method for resolving cases where distances are equal, therefore the last-checked pixel's color is used above.

The JFA finishes after evaluating the last pixel in the last step size. Regardless of the content of the initial data, the innermost loop runs a total of [math]\displaystyle{ 9 \log_2(N) }[/math] times over each pixel, for an overall computational complexity of [math]\displaystyle{ O(N^2 \log_2(N)) }[/math].

Variants

Some variants of JFA are presented in [1] and [3]:

  • Additional pass at the end: JFA+1 has one additional pass with step size of 1, i.e. the step sizes are N/2, N/4, ..., 1, 1; JFA+2 has two additional passes with step sizes of 2 and 1, i.e. the step sizes are N/2, N/4, ..., 1, 2, 1; JFA[math]\displaystyle{ ^2 }[/math] has [math]\displaystyle{ \log_2(N) }[/math] additional passes, i.e. the step sizes are N/2, N/4, ..., 1, N/2, N/4, ..., 1. JFA+1 has much less errors than JFA, and JFA+2 has even less errors.
  • Additional pass at the beginning: 1+JFA has one additional pass with step size of 1, i.e. the step sizes are 1, N/2, N/4, ..., 1. 1+JFA has very low error rate (similar to JFA+2) and the same performance as JFA+1.
  • Half resolution: This variant runs normal JFA at a half resolution, and enlarge the result into the original resolution and run one additional pass with step size of 1. Because most of the passes has only half resolution, the speed of this variant is much faster than the full resolution JFA.

Uses

The jump flooding algorithm and its variants may be used for calculating Voronoi maps[1][3] and centroidal Voronoi tessellations (CVT),[4] generating distance fields,[5] point-cloud rendering,[6] feature matching,[7] the computation of power diagrams,[8] and soft shadow rendering.[9] The grand strategy game developer Paradox Interactive uses the JFA to render borders between countries and provinces.[10]

Further developments

The JFA has inspired the development of numerous similar algorithms. Some have well-defined error properties which make them useful for scientific computing.[11]

In the computer vision domain, the JFA has inspired new belief propagation algorithms to accelerate the solution of a variety of problems.[12][13]

References

  1. ↑ 1.0 1.1 1.2 Rong, Guodong; Tan, Tiow-Seng (2006-03-14). "Jump flooding in GPU with applications to Voronoi diagram and distance transform". Proceedings of the 2006 Symposium on Interactive 3D Graphics and Games. I3D '06 (Redwood City, California: Association for Computing Machinery): 109–116. doi:10.1145/1111411.1111431. ISBN 978-1-59593-295-2. https://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf. 
  2. ↑ The original paper uses the optimal case, a square grid, as an example, but a grid of any size works. Albeit with reduced efficiency. See this StackOverflow question for more.
  3. ↑ Rong, Guodong; Tan, Tiow-Seng (July 2007). "Variants of Jump Flooding Algorithm for Computing Discrete Voronoi Diagrams". 4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007): 176–181. doi:10.1109/ISVD.2007.41. ISBN 978-0-7695-2869-4. https://ieeexplore.ieee.org/document/4276119. 
  4. ↑ Guodong Rong; Yang Liu; Wenping Wang; Xiaotian Yin; Gu, X D; Xiaohu Guo (2011-03-25). "GPU-Assisted Computation of Centroidal Voronoi Tessellation". IEEE Transactions on Visualization and Computer Graphics 17 (3): 345–356. doi:10.1109/TVCG.2010.53. ISSN 1077-2626. http://ieeexplore.ieee.org/document/5438988/. 
  5. ↑ Golus, Ben (2021-04-01). "The Quest for Very Wide Outlines" (in en). https://bgolus.medium.com/the-quest-for-very-wide-outlines-ba82ed442cd9. 
  6. ↑ Farias, Renato (2014). "POINT CLOUD RENDERING USING JUMP FLOODING". https://www.lcg.ufrj.br/thesis/renato-farias-MSc.pdf. 
  7. ↑ Yu, Pei; Yang, Xiaokang; Chen, Li (2012). Zhang, Wenjun; Yang, Xiaokang; Xu, Zhixiang et al.. eds. "Parallel-Friendly Patch Match Based on Jump Flooding" (in en). Advances on Digital Television and Wireless Multimedia Communications. Communications in Computer and Information Science (Berlin, Heidelberg: Springer) 331: 15–21. doi:10.1007/978-3-642-34595-1_3. ISBN 978-3-642-34595-1. https://link.springer.com/chapter/10.1007/978-3-642-34595-1_3. 
  8. ↑ Zheng, Liping (2019-05-01). "GPU-based efficient computation of power diagram" (in en). Computers & Graphics 80: 29–36. doi:10.1016/j.cag.2019.03.011. ISSN 0097-8493. https://www.sciencedirect.com/science/article/abs/pii/S0097849319300342. 
  9. ↑ Rong, Guodong; Tan, Tiow-Seng (2006-11-01). "Utilizing jump flooding in image-based soft shadows". Proceedings of the ACM Symposium on Virtual Reality Software and Technology. VRST '06 (Limassol, Cyprus: Association for Computing Machinery): 173–180. doi:10.1145/1180495.1180531. ISBN 978-1-59593-321-8. https://doi.org/10.1145/1180495.1180531. 
  10. ↑ Boczula, Bartosz; Eriksson, Daniel (2020). "Optimized Gradient Border Rendering in Imperator: Rome" (in en). https://www.intel.com/content/www/us/en/develop/articles/optimized-gradient-border-rendering-in-imperator-rome.html. 
  11. ↑ Schneider, Jens; Kraus, Martin; Westermann, Rüdiger (2010). Ranchordas, AlpeshKumar; Pereira, João Madeiras; Araújo, Hélder J. et al.. eds. "GPU-Based Euclidean Distance Transforms and Their Application to Volume Rendering" (in en). Computer Vision, Imaging and Computer Graphics. Theory and Applications. Communications in Computer and Information Science (Berlin, Heidelberg: Springer) 68: 215–228. doi:10.1007/978-3-642-11840-1_16. ISBN 978-3-642-11840-1. https://link.springer.com/chapter/10.1007/978-3-642-11840-1_16. 
  12. ↑ Alchatzidis, Stavros; Sotiras, Aristeidis; Paragios, Nikos (2011-11-06). "Efficient parallel message computation for MAP inference". 2011 International Conference on Computer Vision: 1379–1386. doi:10.1109/ICCV.2011.6126392. https://ieeexplore.ieee.org/document/6126392/. 
  13. ↑ Choi, Jungwook; Rutenbar, Rob A. (2016-08-29). "Configurable and scalable belief propagation accelerator for computer vision". 2016 26th International Conference on Field Programmable Logic and Applications (FPL): 1–4. doi:10.1109/FPL.2016.7577316. https://ieeexplore.ieee.org/document/7577316/. 

As of this edit, this article uses content from "Is Jump Flood Algorithm Separable?", authored by alan-wolfe, trichoplax at Stack Exchange, which is licensed in a way that permits reuse under the Creative Commons Attribution-ShareAlike 3.0 Unported License, but not under the GFDL. All relevant terms must be followed.




Retrieved from "https://handwiki.org/wiki/index.php?title=Jump_flooding_algorithm&oldid=2639504"