Jump flooding algorithm - Revision history

OAbot: Open access bot: url-access updated in citation with #oabot.

2025-05-23T23:32:05Z

Open access bot: url-access updated in citation with #oabot.

← Previous revision		Revision as of 23:32, 23 May 2025
Line 29:		Line 29:

	== Uses ==		== Uses ==
	The jump flooding algorithm and its variants may be used for calculating [[Voronoi map\|Voronoi maps]]<ref name=Rong2006/><ref name=Rong2007>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007) \|chapter=Variants of Jump Flooding Algorithm for Computing Discrete Voronoi Diagrams \|date=July 2007\|chapter-url=https://ieeexplore.ieee.org/document/4276119\|pages=176–181\|doi=10.1109/ISVD.2007.41\|isbn=978-0-7695-2869-4\|s2cid=386735}}</ref> and [[centroidal Voronoi tessellation]]s (CVT),<ref>{{Cite journal\|last1=Guodong Rong\|last2=Yang Liu\|last3=Wenping Wang\|last4=Xiaotian Yin\|last5=Gu\|first5=X D\|last6=Xiaohu Guo\|date=2011-03-25\|title=GPU-Assisted Computation of Centroidal Voronoi Tessellation\|url=https://ieeexplore.ieee.org/document/5438988\|journal=IEEE Transactions on Visualization and Computer Graphics\|volume=17\|issue=3\|pages=345–356\|doi=10.1109/TVCG.2010.53\|pmid=21233516 \|s2cid=11970070 \|issn=1077-2626\|hdl=10722/132211\|hdl-access=free}}</ref> generating [[distance field]]s,<ref>{{Cite web\|last=Golus\|first=Ben\|date=2021-04-01\|title=The Quest for Very Wide Outlines\|url=https://bgolus.medium.com/the-quest-for-very-wide-outlines-ba82ed442cd9\|access-date=2021-08-19\|website=Medium\|language=en}}</ref> [[point-cloud]] rendering,<ref>{{Cite web\|last=Farias\|first=Renato\|date=2014\|title=POINT CLOUD RENDERING USING JUMP FLOODING\|url=https://www.lcg.ufrj.br/thesis/renato-farias-MSc.pdf}}</ref> [[feature matching]],<ref>{{Cite book\|last1=Yu\|first1=Pei\|last2=Yang\|first2=Xiaokang\|last3=Chen\|first3=Li\|title=Advances on Digital Television and Wireless Multimedia Communications \|chapter=Parallel-Friendly Patch Match Based on Jump Flooding \|date=2012\|editor-last=Zhang\|editor-first=Wenjun\|editor2-last=Yang\|editor2-first=Xiaokang\|editor3-last=Xu\|editor3-first=Zhixiang\|editor4-last=An\|editor4-first=Ping\|editor5-last=Liu\|editor5-first=Qizhen\|editor6-last=Lu\|editor6-first=Yue\|chapter-url=https://link.springer.com/chapter/10.1007/978-3-642-34595-1_3\|series=Communications in Computer and Information Science\|volume=331\|language=en\|location=Berlin, Heidelberg\|publisher=Springer\|pages=15–21\|doi=10.1007/978-3-642-34595-1_3\|isbn=978-3-642-34595-1}}</ref> the computation of [[power diagram]]s,<ref>{{Cite journal\|last=Zheng\|first=Liping\|date=2019-05-01\|title=GPU-based efficient computation of power diagram\|url=https://www.sciencedirect.com/science/article/abs/pii/S0097849319300342\|journal=Computers & Graphics\|language=en\|volume=80\|pages=29–36\|doi=10.1016/j.cag.2019.03.011\|s2cid=131923624 \|issn=0097-8493}}</ref> and [[Soft shadows\|soft shadow]] rendering.<ref>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=Proceedings of the ACM symposium on Virtual reality software and technology \|chapter=Utilizing jump flooding in image-based soft shadows \|date=2006-11-01\|chapter-url=https://doi.org/10.1145/1180495.1180531\|series=VRST '06\|location=Limassol, Cyprus\|publisher=Association for Computing Machinery\|pages=173–180\|doi=10.1145/1180495.1180531\|isbn=978-1-59593-321-8\|s2cid=15339123}}</ref> The [[Grand strategy wargame\|grand strategy game]] developer [[Paradox Interactive]] uses the JFA to render borders between countries and provinces.<ref>{{Cite web\|last1=Boczula\|first1=Bartosz\|last2=Eriksson\|first2=Daniel\|date=2020\|title=Optimized Gradient Border Rendering in Imperator: Rome\|url=https://www.intel.com/content/www/us/en/develop/articles/optimized-gradient-border-rendering-in-imperator-rome.html\|access-date=2021-03-28\|website=Intel\|language=en}}</ref>		The jump flooding algorithm and its variants may be used for calculating [[Voronoi map\|Voronoi maps]]<ref name=Rong2006/><ref name=Rong2007>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007) \|chapter=Variants of Jump Flooding Algorithm for Computing Discrete Voronoi Diagrams \|date=July 2007\|chapter-url=https://ieeexplore.ieee.org/document/4276119\|pages=176–181\|doi=10.1109/ISVD.2007.41\|isbn=978-0-7695-2869-4\|s2cid=386735}}</ref> and [[centroidal Voronoi tessellation]]s (CVT),<ref>{{Cite journal\|last1=Guodong Rong\|last2=Yang Liu\|last3=Wenping Wang\|last4=Xiaotian Yin\|last5=Gu\|first5=X D\|last6=Xiaohu Guo\|date=2011-03-25\|title=GPU-Assisted Computation of Centroidal Voronoi Tessellation\|url=https://ieeexplore.ieee.org/document/5438988\|journal=IEEE Transactions on Visualization and Computer Graphics\|volume=17\|issue=3\|pages=345–356\|doi=10.1109/TVCG.2010.53\|pmid=21233516 \|s2cid=11970070 \|issn=1077-2626\|hdl=10722/132211\|hdl-access=free}}</ref> generating [[distance field]]s,<ref>{{Cite web\|last=Golus\|first=Ben\|date=2021-04-01\|title=The Quest for Very Wide Outlines\|url=https://bgolus.medium.com/the-quest-for-very-wide-outlines-ba82ed442cd9\|access-date=2021-08-19\|website=Medium\|language=en}}</ref> [[point-cloud]] rendering,<ref>{{Cite web\|last=Farias\|first=Renato\|date=2014\|title=POINT CLOUD RENDERING USING JUMP FLOODING\|url=https://www.lcg.ufrj.br/thesis/renato-farias-MSc.pdf}}</ref> [[feature matching]],<ref>{{Cite book\|last1=Yu\|first1=Pei\|last2=Yang\|first2=Xiaokang\|last3=Chen\|first3=Li\|title=Advances on Digital Television and Wireless Multimedia Communications \|chapter=Parallel-Friendly Patch Match Based on Jump Flooding \|date=2012\|editor-last=Zhang\|editor-first=Wenjun\|editor2-last=Yang\|editor2-first=Xiaokang\|editor3-last=Xu\|editor3-first=Zhixiang\|editor4-last=An\|editor4-first=Ping\|editor5-last=Liu\|editor5-first=Qizhen\|editor6-last=Lu\|editor6-first=Yue\|chapter-url=https://link.springer.com/chapter/10.1007/978-3-642-34595-1_3\|series=Communications in Computer and Information Science\|volume=331\|language=en\|location=Berlin, Heidelberg\|publisher=Springer\|pages=15–21\|doi=10.1007/978-3-642-34595-1_3\|isbn=978-3-642-34595-1}}</ref> the computation of [[power diagram]]s,<ref>{{Cite journal\|last=Zheng\|first=Liping\|date=2019-05-01\|title=GPU-based efficient computation of power diagram\|url=https://www.sciencedirect.com/science/article/abs/pii/S0097849319300342\|journal=Computers & Graphics\|language=en\|volume=80\|pages=29–36\|doi=10.1016/j.cag.2019.03.011\|s2cid=131923624 \|issn=0097-8493\|url-access=subscription}}</ref> and [[Soft shadows\|soft shadow]] rendering.<ref>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=Proceedings of the ACM symposium on Virtual reality software and technology \|chapter=Utilizing jump flooding in image-based soft shadows \|date=2006-11-01\|chapter-url=https://doi.org/10.1145/1180495.1180531\|series=VRST '06\|location=Limassol, Cyprus\|publisher=Association for Computing Machinery\|pages=173–180\|doi=10.1145/1180495.1180531\|isbn=978-1-59593-321-8\|s2cid=15339123}}</ref> The [[Grand strategy wargame\|grand strategy game]] developer [[Paradox Interactive]] uses the JFA to render borders between countries and provinces.<ref>{{Cite web\|last1=Boczula\|first1=Bartosz\|last2=Eriksson\|first2=Daniel\|date=2020\|title=Optimized Gradient Border Rendering in Imperator: Rome\|url=https://www.intel.com/content/www/us/en/develop/articles/optimized-gradient-border-rendering-in-imperator-rome.html\|access-date=2021-03-28\|website=Intel\|language=en}}</ref>

	== Further developments ==		== Further developments ==

LucasVB: /* Implementation */

2025-03-15T12:33:25Z

Implementation

← Previous revision		Revision as of 12:33, 15 March 2025
Line 9:		Line 9:
	Take an <math>N \times N</math> grid of pixels<ref>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 [https://computergraphics.stackexchange.com/questions/2102/is-jump-flood-algorithm-separable this StackOverflow question for more].</ref> (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.		Take an <math>N \times N</math> grid of pixels<ref>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 [https://computergraphics.stackexchange.com/questions/2102/is-jump-flood-algorithm-separable this StackOverflow question for more].</ref> (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>k \in \{\~~frac~~ N 2, \~~frac~~ N 4, \dots, 1\}</math>, run one iteration of the JFA:		For each step size <math>k \in \{\tfrac{N}{2}, \tfrac{N}{4}, \dots, 1\}</math>, run one iteration of the JFA:

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

Oman395: /* top */No other part of the uses section has a how tag. As well, the uses section shouldn't contain implementation details-- perhaps the implementation section could be expanded to include details on usage.

2024-04-15T13:31:37Z

top: No other part of the uses section has a how tag. As well, the uses section shouldn't contain implementation details-- perhaps the implementation section could be expanded to include details on usage.

← Previous revision		Revision as of 13:31, 15 April 2024
Line 29:		Line 29:

	== Uses ==		== Uses ==
	The jump flooding algorithm and its variants may be used for calculating [[Voronoi map\|Voronoi maps]]<ref name=Rong2006/><ref name=Rong2007>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007) \|chapter=Variants of Jump Flooding Algorithm for Computing Discrete Voronoi Diagrams \|date=July 2007\|chapter-url=https://ieeexplore.ieee.org/document/4276119\|pages=176–181\|doi=10.1109/ISVD.2007.41\|isbn=978-0-7695-2869-4\|s2cid=386735}}</ref> and [[centroidal Voronoi tessellation]]s (CVT),<ref>{{Cite journal\|last1=Guodong Rong\|last2=Yang Liu\|last3=Wenping Wang\|last4=Xiaotian Yin\|last5=Gu\|first5=X D\|last6=Xiaohu Guo\|date=2011-03-25\|title=GPU-Assisted Computation of Centroidal Voronoi Tessellation\|url=https://ieeexplore.ieee.org/document/5438988\|journal=IEEE Transactions on Visualization and Computer Graphics\|volume=17\|issue=3\|pages=345–356\|doi=10.1109/TVCG.2010.53\|pmid=21233516 \|s2cid=11970070 \|issn=1077-2626\|hdl=10722/132211\|hdl-access=free}}</ref> generating [[distance field]]s,<ref>{{Cite web\|last=Golus\|first=Ben\|date=2021-04-01\|title=The Quest for Very Wide Outlines\|url=https://bgolus.medium.com/the-quest-for-very-wide-outlines-ba82ed442cd9\|access-date=2021-08-19\|website=Medium\|language=en}}</ref>~~{{How\|date=August 2021}}~~ [[point-cloud]] rendering,<ref>{{Cite web\|last=Farias\|first=Renato\|date=2014\|title=POINT CLOUD RENDERING USING JUMP FLOODING\|url=https://www.lcg.ufrj.br/thesis/renato-farias-MSc.pdf}}</ref> [[feature matching]],<ref>{{Cite book\|last1=Yu\|first1=Pei\|last2=Yang\|first2=Xiaokang\|last3=Chen\|first3=Li\|title=Advances on Digital Television and Wireless Multimedia Communications \|chapter=Parallel-Friendly Patch Match Based on Jump Flooding \|date=2012\|editor-last=Zhang\|editor-first=Wenjun\|editor2-last=Yang\|editor2-first=Xiaokang\|editor3-last=Xu\|editor3-first=Zhixiang\|editor4-last=An\|editor4-first=Ping\|editor5-last=Liu\|editor5-first=Qizhen\|editor6-last=Lu\|editor6-first=Yue\|chapter-url=https://link.springer.com/chapter/10.1007/978-3-642-34595-1_3\|series=Communications in Computer and Information Science\|volume=331\|language=en\|location=Berlin, Heidelberg\|publisher=Springer\|pages=15–21\|doi=10.1007/978-3-642-34595-1_3\|isbn=978-3-642-34595-1}}</ref> the computation of [[power diagram]]s,<ref>{{Cite journal\|last=Zheng\|first=Liping\|date=2019-05-01\|title=GPU-based efficient computation of power diagram\|url=https://www.sciencedirect.com/science/article/abs/pii/S0097849319300342\|journal=Computers & Graphics\|language=en\|volume=80\|pages=29–36\|doi=10.1016/j.cag.2019.03.011\|s2cid=131923624 \|issn=0097-8493}}</ref> and [[Soft shadows\|soft shadow]] rendering.<ref>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=Proceedings of the ACM symposium on Virtual reality software and technology \|chapter=Utilizing jump flooding in image-based soft shadows \|date=2006-11-01\|chapter-url=https://doi.org/10.1145/1180495.1180531\|series=VRST '06\|location=Limassol, Cyprus\|publisher=Association for Computing Machinery\|pages=173–180\|doi=10.1145/1180495.1180531\|isbn=978-1-59593-321-8\|s2cid=15339123}}</ref> The [[Grand strategy wargame\|grand strategy game]] developer [[Paradox Interactive]] uses the JFA to render borders between countries and provinces.<ref>{{Cite web\|last1=Boczula\|first1=Bartosz\|last2=Eriksson\|first2=Daniel\|date=2020\|title=Optimized Gradient Border Rendering in Imperator: Rome\|url=https://www.intel.com/content/www/us/en/develop/articles/optimized-gradient-border-rendering-in-imperator-rome.html\|access-date=2021-03-28\|website=Intel\|language=en}}</ref>		The jump flooding algorithm and its variants may be used for calculating [[Voronoi map\|Voronoi maps]]<ref name=Rong2006/><ref name=Rong2007>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007) \|chapter=Variants of Jump Flooding Algorithm for Computing Discrete Voronoi Diagrams \|date=July 2007\|chapter-url=https://ieeexplore.ieee.org/document/4276119\|pages=176–181\|doi=10.1109/ISVD.2007.41\|isbn=978-0-7695-2869-4\|s2cid=386735}}</ref> and [[centroidal Voronoi tessellation]]s (CVT),<ref>{{Cite journal\|last1=Guodong Rong\|last2=Yang Liu\|last3=Wenping Wang\|last4=Xiaotian Yin\|last5=Gu\|first5=X D\|last6=Xiaohu Guo\|date=2011-03-25\|title=GPU-Assisted Computation of Centroidal Voronoi Tessellation\|url=https://ieeexplore.ieee.org/document/5438988\|journal=IEEE Transactions on Visualization and Computer Graphics\|volume=17\|issue=3\|pages=345–356\|doi=10.1109/TVCG.2010.53\|pmid=21233516 \|s2cid=11970070 \|issn=1077-2626\|hdl=10722/132211\|hdl-access=free}}</ref> generating [[distance field]]s,<ref>{{Cite web\|last=Golus\|first=Ben\|date=2021-04-01\|title=The Quest for Very Wide Outlines\|url=https://bgolus.medium.com/the-quest-for-very-wide-outlines-ba82ed442cd9\|access-date=2021-08-19\|website=Medium\|language=en}}</ref> [[point-cloud]] rendering,<ref>{{Cite web\|last=Farias\|first=Renato\|date=2014\|title=POINT CLOUD RENDERING USING JUMP FLOODING\|url=https://www.lcg.ufrj.br/thesis/renato-farias-MSc.pdf}}</ref> [[feature matching]],<ref>{{Cite book\|last1=Yu\|first1=Pei\|last2=Yang\|first2=Xiaokang\|last3=Chen\|first3=Li\|title=Advances on Digital Television and Wireless Multimedia Communications \|chapter=Parallel-Friendly Patch Match Based on Jump Flooding \|date=2012\|editor-last=Zhang\|editor-first=Wenjun\|editor2-last=Yang\|editor2-first=Xiaokang\|editor3-last=Xu\|editor3-first=Zhixiang\|editor4-last=An\|editor4-first=Ping\|editor5-last=Liu\|editor5-first=Qizhen\|editor6-last=Lu\|editor6-first=Yue\|chapter-url=https://link.springer.com/chapter/10.1007/978-3-642-34595-1_3\|series=Communications in Computer and Information Science\|volume=331\|language=en\|location=Berlin, Heidelberg\|publisher=Springer\|pages=15–21\|doi=10.1007/978-3-642-34595-1_3\|isbn=978-3-642-34595-1}}</ref> the computation of [[power diagram]]s,<ref>{{Cite journal\|last=Zheng\|first=Liping\|date=2019-05-01\|title=GPU-based efficient computation of power diagram\|url=https://www.sciencedirect.com/science/article/abs/pii/S0097849319300342\|journal=Computers & Graphics\|language=en\|volume=80\|pages=29–36\|doi=10.1016/j.cag.2019.03.011\|s2cid=131923624 \|issn=0097-8493}}</ref> and [[Soft shadows\|soft shadow]] rendering.<ref>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=Proceedings of the ACM symposium on Virtual reality software and technology \|chapter=Utilizing jump flooding in image-based soft shadows \|date=2006-11-01\|chapter-url=https://doi.org/10.1145/1180495.1180531\|series=VRST '06\|location=Limassol, Cyprus\|publisher=Association for Computing Machinery\|pages=173–180\|doi=10.1145/1180495.1180531\|isbn=978-1-59593-321-8\|s2cid=15339123}}</ref> The [[Grand strategy wargame\|grand strategy game]] developer [[Paradox Interactive]] uses the JFA to render borders between countries and provinces.<ref>{{Cite web\|last1=Boczula\|first1=Bartosz\|last2=Eriksson\|first2=Daniel\|date=2020\|title=Optimized Gradient Border Rendering in Imperator: Rome\|url=https://www.intel.com/content/www/us/en/develop/articles/optimized-gradient-border-rendering-in-imperator-rome.html\|access-date=2021-03-28\|website=Intel\|language=en}}</ref>

	== Further developments ==		== Further developments ==

Wishdosher: Correct computational complexity (there are N×N pixels)

2024-03-29T00:36:49Z

Correct computational complexity (there are N×N pixels)

← Previous revision		Revision as of 00:36, 29 March 2024
Line 18:		Line 18:
	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.		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>9 \log_2(N)</math> times over each pixel, for an overall computational complexity of <math>O(N \log_2(N))</math>.		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>9 \log_2(N)</math> times over each pixel, for an overall computational complexity of <math>O(N^2 \log_2(N))</math>.

	=== Variants ===		=== Variants ===

104.158.166.216 at 23:12, 28 March 2024

2024-03-28T23:12:46Z

← Previous revision		Revision as of 23:12, 28 March 2024
Line 2:		Line 2:
	The '''jump flooding algorithm''' ('''JFA''') is a [[flooding algorithm]] used in the construction of [[Voronoi diagram]]s and [[Distance transform\|distance transforms]]. The JFA was introduced by Rong Guodong at an [[Association for Computing Machinery\|ACM]] symposium in 2006.<ref name=Rong2006>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=Proceedings of the 2006 symposium on Interactive 3D graphics and games - SI3D '06 \|chapter=Jump flooding in GPU with applications to Voronoi diagram and distance transform \|date=2006-03-14\|chapter-url=https://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf\|location=Redwood City, California\|publisher=Association for Computing Machinery\|pages=109–116\|doi=10.1145/1111411.1111431\|isbn=978-1-59593-295-2\|s2cid=7282879}}</ref>		The '''jump flooding algorithm''' ('''JFA''') is a [[flooding algorithm]] used in the construction of [[Voronoi diagram]]s and [[Distance transform\|distance transforms]]. The JFA was introduced by Rong Guodong at an [[Association for Computing Machinery\|ACM]] symposium in 2006.<ref name=Rong2006>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=Proceedings of the 2006 symposium on Interactive 3D graphics and games - SI3D '06 \|chapter=Jump flooding in GPU with applications to Voronoi diagram and distance transform \|date=2006-03-14\|chapter-url=https://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf\|location=Redwood City, California\|publisher=Association for Computing Machinery\|pages=109–116\|doi=10.1145/1111411.1111431\|isbn=978-1-59593-295-2\|s2cid=7282879}}</ref>

	The JFA has desirable attributes in [[GPU]] computation, notably ~~constant-time~~ performance. However, it is only an approximate algorithm and does not always compute the correct result for every pixel, although in practice errors are few and the magnitude of errors is generally small.<ref name=Rong2006/>		The JFA has desirable attributes in [[GPU]] computation, notably for its efficient performance. However, it is only an approximate algorithm and does not always compute the correct result for every pixel, although in practice errors are few and the magnitude of errors is generally small.<ref name=Rong2006/>

	== Implementation ==		== Implementation ==

OAbot: Open access bot: hdl updated in citation with #oabot.

2024-01-15T09:33:53Z

Open access bot: hdl updated in citation with #oabot.

← Previous revision		Revision as of 09:33, 15 January 2024
Line 29:		Line 29:

	== Uses ==		== Uses ==
	The jump flooding algorithm and its variants may be used for calculating [[Voronoi map\|Voronoi maps]]<ref name=Rong2006/><ref name=Rong2007>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007) \|chapter=Variants of Jump Flooding Algorithm for Computing Discrete Voronoi Diagrams \|date=July 2007\|chapter-url=https://ieeexplore.ieee.org/document/4276119\|pages=176–181\|doi=10.1109/ISVD.2007.41\|isbn=978-0-7695-2869-4\|s2cid=386735}}</ref> and [[centroidal Voronoi tessellation]]s (CVT),<ref>{{Cite journal\|last1=Guodong Rong\|last2=Yang Liu\|last3=Wenping Wang\|last4=Xiaotian Yin\|last5=Gu\|first5=X D\|last6=Xiaohu Guo\|date=2011-03-25\|title=GPU-Assisted Computation of Centroidal Voronoi Tessellation\|url=https://ieeexplore.ieee.org/document/5438988\|journal=IEEE Transactions on Visualization and Computer Graphics\|volume=17\|issue=3\|pages=345–356\|doi=10.1109/TVCG.2010.53\|pmid=21233516 \|s2cid=11970070 \|issn=1077-2626}}</ref> generating [[distance field]]s,<ref>{{Cite web\|last=Golus\|first=Ben\|date=2021-04-01\|title=The Quest for Very Wide Outlines\|url=https://bgolus.medium.com/the-quest-for-very-wide-outlines-ba82ed442cd9\|access-date=2021-08-19\|website=Medium\|language=en}}</ref>{{How\|date=August 2021}} [[point-cloud]] rendering,<ref>{{Cite web\|last=Farias\|first=Renato\|date=2014\|title=POINT CLOUD RENDERING USING JUMP FLOODING\|url=https://www.lcg.ufrj.br/thesis/renato-farias-MSc.pdf}}</ref> [[feature matching]],<ref>{{Cite book\|last1=Yu\|first1=Pei\|last2=Yang\|first2=Xiaokang\|last3=Chen\|first3=Li\|title=Advances on Digital Television and Wireless Multimedia Communications \|chapter=Parallel-Friendly Patch Match Based on Jump Flooding \|date=2012\|editor-last=Zhang\|editor-first=Wenjun\|editor2-last=Yang\|editor2-first=Xiaokang\|editor3-last=Xu\|editor3-first=Zhixiang\|editor4-last=An\|editor4-first=Ping\|editor5-last=Liu\|editor5-first=Qizhen\|editor6-last=Lu\|editor6-first=Yue\|chapter-url=https://link.springer.com/chapter/10.1007/978-3-642-34595-1_3\|series=Communications in Computer and Information Science\|volume=331\|language=en\|location=Berlin, Heidelberg\|publisher=Springer\|pages=15–21\|doi=10.1007/978-3-642-34595-1_3\|isbn=978-3-642-34595-1}}</ref> the computation of [[power diagram]]s,<ref>{{Cite journal\|last=Zheng\|first=Liping\|date=2019-05-01\|title=GPU-based efficient computation of power diagram\|url=https://www.sciencedirect.com/science/article/abs/pii/S0097849319300342\|journal=Computers & Graphics\|language=en\|volume=80\|pages=29–36\|doi=10.1016/j.cag.2019.03.011\|s2cid=131923624 \|issn=0097-8493}}</ref> and [[Soft shadows\|soft shadow]] rendering.<ref>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=Proceedings of the ACM symposium on Virtual reality software and technology \|chapter=Utilizing jump flooding in image-based soft shadows \|date=2006-11-01\|chapter-url=https://doi.org/10.1145/1180495.1180531\|series=VRST '06\|location=Limassol, Cyprus\|publisher=Association for Computing Machinery\|pages=173–180\|doi=10.1145/1180495.1180531\|isbn=978-1-59593-321-8\|s2cid=15339123}}</ref> The [[Grand strategy wargame\|grand strategy game]] developer [[Paradox Interactive]] uses the JFA to render borders between countries and provinces.<ref>{{Cite web\|last1=Boczula\|first1=Bartosz\|last2=Eriksson\|first2=Daniel\|date=2020\|title=Optimized Gradient Border Rendering in Imperator: Rome\|url=https://www.intel.com/content/www/us/en/develop/articles/optimized-gradient-border-rendering-in-imperator-rome.html\|access-date=2021-03-28\|website=Intel\|language=en}}</ref>		The jump flooding algorithm and its variants may be used for calculating [[Voronoi map\|Voronoi maps]]<ref name=Rong2006/><ref name=Rong2007>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007) \|chapter=Variants of Jump Flooding Algorithm for Computing Discrete Voronoi Diagrams \|date=July 2007\|chapter-url=https://ieeexplore.ieee.org/document/4276119\|pages=176–181\|doi=10.1109/ISVD.2007.41\|isbn=978-0-7695-2869-4\|s2cid=386735}}</ref> and [[centroidal Voronoi tessellation]]s (CVT),<ref>{{Cite journal\|last1=Guodong Rong\|last2=Yang Liu\|last3=Wenping Wang\|last4=Xiaotian Yin\|last5=Gu\|first5=X D\|last6=Xiaohu Guo\|date=2011-03-25\|title=GPU-Assisted Computation of Centroidal Voronoi Tessellation\|url=https://ieeexplore.ieee.org/document/5438988\|journal=IEEE Transactions on Visualization and Computer Graphics\|volume=17\|issue=3\|pages=345–356\|doi=10.1109/TVCG.2010.53\|pmid=21233516 \|s2cid=11970070 \|issn=1077-2626\|hdl=10722/132211\|hdl-access=free}}</ref> generating [[distance field]]s,<ref>{{Cite web\|last=Golus\|first=Ben\|date=2021-04-01\|title=The Quest for Very Wide Outlines\|url=https://bgolus.medium.com/the-quest-for-very-wide-outlines-ba82ed442cd9\|access-date=2021-08-19\|website=Medium\|language=en}}</ref>{{How\|date=August 2021}} [[point-cloud]] rendering,<ref>{{Cite web\|last=Farias\|first=Renato\|date=2014\|title=POINT CLOUD RENDERING USING JUMP FLOODING\|url=https://www.lcg.ufrj.br/thesis/renato-farias-MSc.pdf}}</ref> [[feature matching]],<ref>{{Cite book\|last1=Yu\|first1=Pei\|last2=Yang\|first2=Xiaokang\|last3=Chen\|first3=Li\|title=Advances on Digital Television and Wireless Multimedia Communications \|chapter=Parallel-Friendly Patch Match Based on Jump Flooding \|date=2012\|editor-last=Zhang\|editor-first=Wenjun\|editor2-last=Yang\|editor2-first=Xiaokang\|editor3-last=Xu\|editor3-first=Zhixiang\|editor4-last=An\|editor4-first=Ping\|editor5-last=Liu\|editor5-first=Qizhen\|editor6-last=Lu\|editor6-first=Yue\|chapter-url=https://link.springer.com/chapter/10.1007/978-3-642-34595-1_3\|series=Communications in Computer and Information Science\|volume=331\|language=en\|location=Berlin, Heidelberg\|publisher=Springer\|pages=15–21\|doi=10.1007/978-3-642-34595-1_3\|isbn=978-3-642-34595-1}}</ref> the computation of [[power diagram]]s,<ref>{{Cite journal\|last=Zheng\|first=Liping\|date=2019-05-01\|title=GPU-based efficient computation of power diagram\|url=https://www.sciencedirect.com/science/article/abs/pii/S0097849319300342\|journal=Computers & Graphics\|language=en\|volume=80\|pages=29–36\|doi=10.1016/j.cag.2019.03.011\|s2cid=131923624 \|issn=0097-8493}}</ref> and [[Soft shadows\|soft shadow]] rendering.<ref>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=Proceedings of the ACM symposium on Virtual reality software and technology \|chapter=Utilizing jump flooding in image-based soft shadows \|date=2006-11-01\|chapter-url=https://doi.org/10.1145/1180495.1180531\|series=VRST '06\|location=Limassol, Cyprus\|publisher=Association for Computing Machinery\|pages=173–180\|doi=10.1145/1180495.1180531\|isbn=978-1-59593-321-8\|s2cid=15339123}}</ref> The [[Grand strategy wargame\|grand strategy game]] developer [[Paradox Interactive]] uses the JFA to render borders between countries and provinces.<ref>{{Cite web\|last1=Boczula\|first1=Bartosz\|last2=Eriksson\|first2=Daniel\|date=2020\|title=Optimized Gradient Border Rendering in Imperator: Rome\|url=https://www.intel.com/content/www/us/en/develop/articles/optimized-gradient-border-rendering-in-imperator-rome.html\|access-date=2021-03-28\|website=Intel\|language=en}}</ref>

	== Further developments ==		== Further developments ==

135.180.48.179 at 06:55, 28 September 2023

2023-09-28T06:55:49Z

← Previous revision		Revision as of 06:55, 28 September 2023
Line 1:		Line 1:
	{{Short description\|Class of algorithms used for computing distance-related functions}}		{{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 diagram]]s and [[Distance transform\|distance transforms]]. The JFA was introduced at an [[Association for Computing Machinery\|ACM]] symposium in 2006.<ref name=Rong2006>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=Proceedings of the 2006 symposium on Interactive 3D graphics and games - SI3D '06 \|chapter=Jump flooding in GPU with applications to Voronoi diagram and distance transform \|date=2006-03-14\|chapter-url=https://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf\|location=Redwood City, California\|publisher=Association for Computing Machinery\|pages=109–116\|doi=10.1145/1111411.1111431\|isbn=978-1-59593-295-2\|s2cid=7282879}}</ref>		The '''jump flooding algorithm''' ('''JFA''') is a [[flooding algorithm]] used in the construction of [[Voronoi diagram]]s and [[Distance transform\|distance transforms]]. The JFA was introduced by Rong Guodong at an [[Association for Computing Machinery\|ACM]] symposium in 2006.<ref name=Rong2006>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=Proceedings of the 2006 symposium on Interactive 3D graphics and games - SI3D '06 \|chapter=Jump flooding in GPU with applications to Voronoi diagram and distance transform \|date=2006-03-14\|chapter-url=https://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf\|location=Redwood City, California\|publisher=Association for Computing Machinery\|pages=109–116\|doi=10.1145/1111411.1111431\|isbn=978-1-59593-295-2\|s2cid=7282879}}</ref>

	The JFA has desirable attributes in [[GPU]] computation, notably constant-time performance. However, it is only an approximate algorithm and does not always compute the correct result for every pixel, although in practice errors are few and the magnitude of errors is generally small.<ref name=Rong2006/>		The JFA has desirable attributes in [[GPU]] computation, notably constant-time performance. However, it is only an approximate algorithm and does not always compute the correct result for every pixel, although in practice errors are few and the magnitude of errors is generally small.<ref name=Rong2006/>

Citation bot: Removed parameters. | Use this bot. Report bugs. | #UCB_CommandLine

2023-09-27T06:04:08Z

Removed parameters. | Use this bot. Report bugs. | #UCB_CommandLine

← Previous revision		Revision as of 06:04, 27 September 2023
Line 29:		Line 29:

	== Uses ==		== Uses ==
	The jump flooding algorithm and its variants may be used for calculating [[Voronoi map\|Voronoi maps]]<ref name=Rong2006/><ref name=Rong2007>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007) \|chapter=Variants of Jump Flooding Algorithm for Computing Discrete Voronoi Diagrams \|date=July 2007\|chapter-url=https://ieeexplore.ieee.org/document/4276119\|pages=176–181\|doi=10.1109/ISVD.2007.41\|isbn=978-0-7695-2869-4\|s2cid=386735}}</ref> and [[centroidal Voronoi tessellation]]s (CVT),<ref>{{Cite journal\|last1=Guodong Rong\|last2=Yang Liu\|last3=Wenping Wang\|last4=Xiaotian Yin\|last5=Gu\|first5=X D\|last6=Xiaohu Guo\|date=2011-03-25\|title=GPU-Assisted Computation of Centroidal Voronoi Tessellation\|url=https://ieeexplore.ieee.org/document/5438988\|journal=IEEE Transactions on Visualization and Computer Graphics\|volume=17\|issue=3\|pages=345–356\|doi=10.1109/TVCG.2010.53\|pmid=21233516 \|s2cid=11970070 \|issn=1077-2626}}</ref> generating [[distance field]]s,<ref>{{Cite web\|last=Golus\|first=Ben\|date=2021-04-01\|title=The Quest for Very Wide Outlines\|url=https://bgolus.medium.com/the-quest-for-very-wide-outlines-ba82ed442cd9\|access-date=2021-08-19\|website=Medium\|language=en}}</ref>{{How\|date=August 2021}} [[point-cloud]] rendering,<ref>{{Cite web\|last=Farias\|first=Renato\|date=2014\|title=POINT CLOUD RENDERING USING JUMP FLOODING\|url=https://www.lcg.ufrj.br/thesis/renato-farias-MSc.pdf~~\|url-status=live~~}}</ref> [[feature matching]],<ref>{{Cite book\|last1=Yu\|first1=Pei\|last2=Yang\|first2=Xiaokang\|last3=Chen\|first3=Li\|title=Advances on Digital Television and Wireless Multimedia Communications \|chapter=Parallel-Friendly Patch Match Based on Jump Flooding \|date=2012\|editor-last=Zhang\|editor-first=Wenjun\|editor2-last=Yang\|editor2-first=Xiaokang\|editor3-last=Xu\|editor3-first=Zhixiang\|editor4-last=An\|editor4-first=Ping\|editor5-last=Liu\|editor5-first=Qizhen\|editor6-last=Lu\|editor6-first=Yue\|chapter-url=https://link.springer.com/chapter/10.1007/978-3-642-34595-1_3\|series=Communications in Computer and Information Science\|volume=331\|language=en\|location=Berlin, Heidelberg\|publisher=Springer\|pages=15–21\|doi=10.1007/978-3-642-34595-1_3\|isbn=978-3-642-34595-1}}</ref> the computation of [[power diagram]]s,<ref>{{Cite journal\|last=Zheng\|first=Liping\|date=2019-05-01\|title=GPU-based efficient computation of power diagram\|url=https://www.sciencedirect.com/science/article/abs/pii/S0097849319300342\|journal=Computers & Graphics\|language=en\|volume=80\|pages=29–36\|doi=10.1016/j.cag.2019.03.011\|s2cid=131923624 \|issn=0097-8493}}</ref> and [[Soft shadows\|soft shadow]] rendering.<ref>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=Proceedings of the ACM symposium on Virtual reality software and technology \|chapter=Utilizing jump flooding in image-based soft shadows \|date=2006-11-01\|chapter-url=https://doi.org/10.1145/1180495.1180531\|series=VRST '06\|location=Limassol, Cyprus\|publisher=Association for Computing Machinery\|pages=173–180\|doi=10.1145/1180495.1180531\|isbn=978-1-59593-321-8\|s2cid=15339123}}</ref> The [[Grand strategy wargame\|grand strategy game]] developer [[Paradox Interactive]] uses the JFA to render borders between countries and provinces.<ref>{{Cite web\|last1=Boczula\|first1=Bartosz\|last2=Eriksson\|first2=Daniel\|date=2020\|title=Optimized Gradient Border Rendering in Imperator: Rome\|url=https://www.intel.com/content/www/us/en/develop/articles/optimized-gradient-border-rendering-in-imperator-rome.html~~\|url-status=live~~\|access-date=2021-03-28\|website=Intel\|language=en}}</ref>		The jump flooding algorithm and its variants may be used for calculating [[Voronoi map\|Voronoi maps]]<ref name=Rong2006/><ref name=Rong2007>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007) \|chapter=Variants of Jump Flooding Algorithm for Computing Discrete Voronoi Diagrams \|date=July 2007\|chapter-url=https://ieeexplore.ieee.org/document/4276119\|pages=176–181\|doi=10.1109/ISVD.2007.41\|isbn=978-0-7695-2869-4\|s2cid=386735}}</ref> and [[centroidal Voronoi tessellation]]s (CVT),<ref>{{Cite journal\|last1=Guodong Rong\|last2=Yang Liu\|last3=Wenping Wang\|last4=Xiaotian Yin\|last5=Gu\|first5=X D\|last6=Xiaohu Guo\|date=2011-03-25\|title=GPU-Assisted Computation of Centroidal Voronoi Tessellation\|url=https://ieeexplore.ieee.org/document/5438988\|journal=IEEE Transactions on Visualization and Computer Graphics\|volume=17\|issue=3\|pages=345–356\|doi=10.1109/TVCG.2010.53\|pmid=21233516 \|s2cid=11970070 \|issn=1077-2626}}</ref> generating [[distance field]]s,<ref>{{Cite web\|last=Golus\|first=Ben\|date=2021-04-01\|title=The Quest for Very Wide Outlines\|url=https://bgolus.medium.com/the-quest-for-very-wide-outlines-ba82ed442cd9\|access-date=2021-08-19\|website=Medium\|language=en}}</ref>{{How\|date=August 2021}} [[point-cloud]] rendering,<ref>{{Cite web\|last=Farias\|first=Renato\|date=2014\|title=POINT CLOUD RENDERING USING JUMP FLOODING\|url=https://www.lcg.ufrj.br/thesis/renato-farias-MSc.pdf}}</ref> [[feature matching]],<ref>{{Cite book\|last1=Yu\|first1=Pei\|last2=Yang\|first2=Xiaokang\|last3=Chen\|first3=Li\|title=Advances on Digital Television and Wireless Multimedia Communications \|chapter=Parallel-Friendly Patch Match Based on Jump Flooding \|date=2012\|editor-last=Zhang\|editor-first=Wenjun\|editor2-last=Yang\|editor2-first=Xiaokang\|editor3-last=Xu\|editor3-first=Zhixiang\|editor4-last=An\|editor4-first=Ping\|editor5-last=Liu\|editor5-first=Qizhen\|editor6-last=Lu\|editor6-first=Yue\|chapter-url=https://link.springer.com/chapter/10.1007/978-3-642-34595-1_3\|series=Communications in Computer and Information Science\|volume=331\|language=en\|location=Berlin, Heidelberg\|publisher=Springer\|pages=15–21\|doi=10.1007/978-3-642-34595-1_3\|isbn=978-3-642-34595-1}}</ref> the computation of [[power diagram]]s,<ref>{{Cite journal\|last=Zheng\|first=Liping\|date=2019-05-01\|title=GPU-based efficient computation of power diagram\|url=https://www.sciencedirect.com/science/article/abs/pii/S0097849319300342\|journal=Computers & Graphics\|language=en\|volume=80\|pages=29–36\|doi=10.1016/j.cag.2019.03.011\|s2cid=131923624 \|issn=0097-8493}}</ref> and [[Soft shadows\|soft shadow]] rendering.<ref>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=Proceedings of the ACM symposium on Virtual reality software and technology \|chapter=Utilizing jump flooding in image-based soft shadows \|date=2006-11-01\|chapter-url=https://doi.org/10.1145/1180495.1180531\|series=VRST '06\|location=Limassol, Cyprus\|publisher=Association for Computing Machinery\|pages=173–180\|doi=10.1145/1180495.1180531\|isbn=978-1-59593-321-8\|s2cid=15339123}}</ref> The [[Grand strategy wargame\|grand strategy game]] developer [[Paradox Interactive]] uses the JFA to render borders between countries and provinces.<ref>{{Cite web\|last1=Boczula\|first1=Bartosz\|last2=Eriksson\|first2=Daniel\|date=2020\|title=Optimized Gradient Border Rendering in Imperator: Rome\|url=https://www.intel.com/content/www/us/en/develop/articles/optimized-gradient-border-rendering-in-imperator-rome.html\|access-date=2021-03-28\|website=Intel\|language=en}}</ref>

	== Further developments ==		== Further developments ==

24.240.41.171: Fixed incorrect time-complexity

2023-09-16T17:23:28Z

Fixed incorrect time-complexity

← Previous revision		Revision as of 17:23, 16 September 2023
Line 18:		Line 18:
	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.		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>9 \log_2(N)</math> times over each pixel, for an overall computational complexity of <math>O(N^2 \log_2(N))</math>.		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>9 \log_2(N)</math> times over each pixel, for an overall computational complexity of <math>O(N \log_2(N))</math>.

	=== Variants ===		=== Variants ===

Citation bot: Alter: title, template type. Add: chapter-url, chapter. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar

2023-09-04T11:41:01Z

Alter: title, template type. Add: chapter-url, chapter. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar

← Previous revision		Revision as of 11:41, 4 September 2023
Line 1:		Line 1:
	{{Short description\|Class of algorithms used for computing distance-related functions}}		{{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 diagram]]s and [[Distance transform\|distance transforms]]. The JFA was introduced at an [[Association for Computing Machinery\|ACM]] symposium in 2006.<ref name=Rong2006>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=Proceedings of the 2006 symposium on Interactive 3D graphics and games - SI3D '06 \|chapter=Jump flooding in GPU with applications to Voronoi diagram and distance transform \|date=2006-03-14\|chapter-url=https://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf~~\|series=I3D '06~~\|location=Redwood City, California\|publisher=Association for Computing Machinery\|pages=109–116\|doi=10.1145/1111411.1111431\|isbn=978-1-59593-295-2\|s2cid=7282879}}</ref>		The '''jump flooding algorithm''' ('''JFA''') is a [[flooding algorithm]] used in the construction of [[Voronoi diagram]]s and [[Distance transform\|distance transforms]]. The JFA was introduced at an [[Association for Computing Machinery\|ACM]] symposium in 2006.<ref name=Rong2006>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=Proceedings of the 2006 symposium on Interactive 3D graphics and games - SI3D '06 \|chapter=Jump flooding in GPU with applications to Voronoi diagram and distance transform \|date=2006-03-14\|chapter-url=https://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf\|location=Redwood City, California\|publisher=Association for Computing Machinery\|pages=109–116\|doi=10.1145/1111411.1111431\|isbn=978-1-59593-295-2\|s2cid=7282879}}</ref>

	The JFA has desirable attributes in [[GPU]] computation, notably constant-time performance. However, it is only an approximate algorithm and does not always compute the correct result for every pixel, although in practice errors are few and the magnitude of errors is generally small.<ref name=Rong2006/>		The JFA has desirable attributes in [[GPU]] computation, notably constant-time performance. However, it is only an approximate algorithm and does not always compute the correct result for every pixel, although in practice errors are few and the magnitude of errors is generally small.<ref name=Rong2006/>
Line 29:		Line 29:

	== Uses ==		== Uses ==
	The jump flooding algorithm and its variants may be used for calculating [[Voronoi map\|Voronoi maps]]<ref name=Rong2006/><ref name=Rong2007>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007) \|chapter=Variants of Jump Flooding Algorithm for Computing Discrete Voronoi Diagrams \|date=July 2007\|chapter-url=https://ieeexplore.ieee.org/document/4276119\|pages=176–181\|doi=10.1109/ISVD.2007.41\|isbn=978-0-7695-2869-4\|s2cid=386735}}</ref> and [[centroidal Voronoi tessellation]]s (CVT),<ref>{{Cite journal\|last1=Guodong Rong\|last2=Yang Liu\|last3=Wenping Wang\|last4=Xiaotian Yin\|last5=Gu\|first5=X D\|last6=Xiaohu Guo\|date=2011-03-25\|title=GPU-Assisted Computation of Centroidal Voronoi Tessellation\|url=https://ieeexplore.ieee.org/document/5438988\|journal=IEEE Transactions on Visualization and Computer Graphics\|volume=17\|issue=3\|pages=345–356\|doi=10.1109/TVCG.2010.53\|pmid=21233516 \|s2cid=11970070 \|issn=1077-2626}}</ref> generating [[distance field]]s,<ref>{{Cite web\|last=Golus\|first=Ben\|date=2021-04-01\|title=The Quest for Very Wide Outlines\|url=https://bgolus.medium.com/the-quest-for-very-wide-outlines-ba82ed442cd9\|access-date=2021-08-19\|website=Medium\|language=en}}</ref>{{How\|date=August 2021}} [[point-cloud]] rendering,<ref>{{Cite web\|last=Farias\|first=Renato\|date=2014\|title=POINT CLOUD RENDERING USING JUMP FLOODING\|url=https://www.lcg.ufrj.br/thesis/renato-farias-MSc.pdf\|url-status=live}}</ref> [[feature matching]],<ref>{{Cite ~~journal~~\|last1=Yu\|first1=Pei\|last2=Yang\|first2=Xiaokang\|last3=Chen\|first3=Li\|date=2012\|editor-last=Zhang\|editor-first=Wenjun\|editor2-last=Yang\|editor2-first=Xiaokang\|editor3-last=Xu\|editor3-first=Zhixiang\|editor4-last=An\|editor4-first=Ping\|editor5-last=Liu\|editor5-first=Qizhen\|editor6-last=Lu\|editor6-first=Yue\|~~title=Parallel~~-~~Friendly Patch Match Based on Jump Flooding\|~~url=https://link.springer.com/chapter/10.1007/978-3-642-34595-1_3~~\|journal=Advances on Digital Television and Wireless Multimedia Communications~~\|series=Communications in Computer and Information Science\|volume=331\|language=en\|location=Berlin, Heidelberg\|publisher=Springer\|pages=15–21\|doi=10.1007/978-3-642-34595-1_3\|isbn=978-3-642-34595-1}}</ref> the computation of [[power diagram]]s,<ref>{{Cite journal\|last=Zheng\|first=Liping\|date=2019-05-01\|title=GPU-based efficient computation of power diagram\|url=https://www.sciencedirect.com/science/article/abs/pii/S0097849319300342\|journal=Computers & Graphics\|language=en\|volume=80\|pages=29–36\|doi=10.1016/j.cag.2019.03.011\|s2cid=131923624 \|issn=0097-8493}}</ref> and [[Soft shadows\|soft shadow]] rendering.<ref>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=Proceedings of the ACM symposium on Virtual reality software and technology \|chapter=Utilizing jump flooding in image-based soft shadows \|date=2006-11-01\|chapter-url=https://doi.org/10.1145/1180495.1180531\|series=VRST '06\|location=Limassol, Cyprus\|publisher=Association for Computing Machinery\|pages=173–180\|doi=10.1145/1180495.1180531\|isbn=978-1-59593-321-8\|s2cid=15339123}}</ref> The [[Grand strategy wargame\|grand strategy game]] developer [[Paradox Interactive]] uses the JFA to render borders between countries and provinces.<ref>{{Cite web\|last1=Boczula\|first1=Bartosz\|last2=Eriksson\|first2=Daniel\|date=2020\|title=Optimized Gradient Border Rendering in Imperator: Rome\|url=https://www.intel.com/content/www/us/en/develop/articles/optimized-gradient-border-rendering-in-imperator-rome.html\|url-status=live\|access-date=2021-03-28\|website=Intel\|language=en}}</ref>		The jump flooding algorithm and its variants may be used for calculating [[Voronoi map\|Voronoi maps]]<ref name=Rong2006/><ref name=Rong2007>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007) \|chapter=Variants of Jump Flooding Algorithm for Computing Discrete Voronoi Diagrams \|date=July 2007\|chapter-url=https://ieeexplore.ieee.org/document/4276119\|pages=176–181\|doi=10.1109/ISVD.2007.41\|isbn=978-0-7695-2869-4\|s2cid=386735}}</ref> and [[centroidal Voronoi tessellation]]s (CVT),<ref>{{Cite journal\|last1=Guodong Rong\|last2=Yang Liu\|last3=Wenping Wang\|last4=Xiaotian Yin\|last5=Gu\|first5=X D\|last6=Xiaohu Guo\|date=2011-03-25\|title=GPU-Assisted Computation of Centroidal Voronoi Tessellation\|url=https://ieeexplore.ieee.org/document/5438988\|journal=IEEE Transactions on Visualization and Computer Graphics\|volume=17\|issue=3\|pages=345–356\|doi=10.1109/TVCG.2010.53\|pmid=21233516 \|s2cid=11970070 \|issn=1077-2626}}</ref> generating [[distance field]]s,<ref>{{Cite web\|last=Golus\|first=Ben\|date=2021-04-01\|title=The Quest for Very Wide Outlines\|url=https://bgolus.medium.com/the-quest-for-very-wide-outlines-ba82ed442cd9\|access-date=2021-08-19\|website=Medium\|language=en}}</ref>{{How\|date=August 2021}} [[point-cloud]] rendering,<ref>{{Cite web\|last=Farias\|first=Renato\|date=2014\|title=POINT CLOUD RENDERING USING JUMP FLOODING\|url=https://www.lcg.ufrj.br/thesis/renato-farias-MSc.pdf\|url-status=live}}</ref> [[feature matching]],<ref>{{Cite book\|last1=Yu\|first1=Pei\|last2=Yang\|first2=Xiaokang\|last3=Chen\|first3=Li\|title=Advances on Digital Television and Wireless Multimedia Communications \|chapter=Parallel-Friendly Patch Match Based on Jump Flooding \|date=2012\|editor-last=Zhang\|editor-first=Wenjun\|editor2-last=Yang\|editor2-first=Xiaokang\|editor3-last=Xu\|editor3-first=Zhixiang\|editor4-last=An\|editor4-first=Ping\|editor5-last=Liu\|editor5-first=Qizhen\|editor6-last=Lu\|editor6-first=Yue\|chapter-url=https://link.springer.com/chapter/10.1007/978-3-642-34595-1_3\|series=Communications in Computer and Information Science\|volume=331\|language=en\|location=Berlin, Heidelberg\|publisher=Springer\|pages=15–21\|doi=10.1007/978-3-642-34595-1_3\|isbn=978-3-642-34595-1}}</ref> the computation of [[power diagram]]s,<ref>{{Cite journal\|last=Zheng\|first=Liping\|date=2019-05-01\|title=GPU-based efficient computation of power diagram\|url=https://www.sciencedirect.com/science/article/abs/pii/S0097849319300342\|journal=Computers & Graphics\|language=en\|volume=80\|pages=29–36\|doi=10.1016/j.cag.2019.03.011\|s2cid=131923624 \|issn=0097-8493}}</ref> and [[Soft shadows\|soft shadow]] rendering.<ref>{{Cite book\|last1=Rong\|first1=Guodong\|last2=Tan\|first2=Tiow-Seng\|title=Proceedings of the ACM symposium on Virtual reality software and technology \|chapter=Utilizing jump flooding in image-based soft shadows \|date=2006-11-01\|chapter-url=https://doi.org/10.1145/1180495.1180531\|series=VRST '06\|location=Limassol, Cyprus\|publisher=Association for Computing Machinery\|pages=173–180\|doi=10.1145/1180495.1180531\|isbn=978-1-59593-321-8\|s2cid=15339123}}</ref> The [[Grand strategy wargame\|grand strategy game]] developer [[Paradox Interactive]] uses the JFA to render borders between countries and provinces.<ref>{{Cite web\|last1=Boczula\|first1=Bartosz\|last2=Eriksson\|first2=Daniel\|date=2020\|title=Optimized Gradient Border Rendering in Imperator: Rome\|url=https://www.intel.com/content/www/us/en/develop/articles/optimized-gradient-border-rendering-in-imperator-rome.html\|url-status=live\|access-date=2021-03-28\|website=Intel\|language=en}}</ref>

	== Further developments ==		== 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.<ref name=":0">{{Cite ~~journal~~\|last1=Schneider\|first1=Jens\|last2=Kraus\|first2=Martin\|last3=Westermann\|first3=Rüdiger\|date=2010\|editor-last=Ranchordas\|editor-first=AlpeshKumar\|editor2-last=Pereira\|editor2-first=João Madeiras\|editor3-last=Araújo\|editor3-first=Hélder J.\|editor4-last=Tavares\|editor4-first=João Manuel R. S.\|~~title=GPU~~-~~Based Euclidean Distance Transforms and Their Application to Volume Rendering\|~~url=https://link.springer.com/chapter/10.1007/978-3-642-11840-1_16~~\|journal=Computer Vision, Imaging and Computer Graphics. Theory and Applications~~\|series=Communications in Computer and Information Science\|volume=68\|language=en\|location=Berlin, Heidelberg\|publisher=Springer\|pages=215–228\|doi=10.1007/978-3-642-11840-1_16\|isbn=978-3-642-11840-1}}</ref>		The JFA has inspired the development of numerous similar algorithms. Some have well-defined error properties which make them useful for scientific computing.<ref name=":0">{{Cite book\|last1=Schneider\|first1=Jens\|last2=Kraus\|first2=Martin\|last3=Westermann\|first3=Rüdiger\|title=Computer Vision, Imaging and Computer Graphics. Theory and Applications \|chapter=GPU-Based Euclidean Distance Transforms and Their Application to Volume Rendering \|date=2010\|editor-last=Ranchordas\|editor-first=AlpeshKumar\|editor2-last=Pereira\|editor2-first=João Madeiras\|editor3-last=Araújo\|editor3-first=Hélder J.\|editor4-last=Tavares\|editor4-first=João Manuel R. S.\|chapter-url=https://link.springer.com/chapter/10.1007/978-3-642-11840-1_16\|series=Communications in Computer and Information Science\|volume=68\|language=en\|location=Berlin, Heidelberg\|publisher=Springer\|pages=215–228\|doi=10.1007/978-3-642-11840-1_16\|isbn=978-3-642-11840-1}}</ref>

	In the [[computer vision]] domain, the JFA has inspired new [[belief propagation]] algorithms to accelerate the solution of a variety of problems.<ref>{{Cite book\|last1=Alchatzidis\|first1=Stavros\|last2=Sotiras\|first2=Aristeidis\|last3=Paragios\|first3=Nikos\|title=2011 International Conference on Computer Vision \|chapter=Efficient parallel message computation for MAP inference \|date=2011-11-06\|chapter-url=https://ieeexplore.ieee.org/document/6126392\|pages=1379–1386\|doi=10.1109/ICCV.2011.6126392\|isbn=978-1-4577-1102-2 \|s2cid=17554205 \|url=https://hal.archives-ouvertes.fr/hal-00858394/file/PID2005337.pdf }}</ref><ref>{{Cite book\|last1=Choi\|first1=Jungwook\|last2=Rutenbar\|first2=Rob A.\|title=2016 26th International Conference on Field Programmable Logic and Applications (FPL) \|chapter=Configurable and scalable belief propagation accelerator for computer vision \|date=2016-08-29\|chapter-url=https://ieeexplore.ieee.org/document/7577316\|pages=1–4\|doi=10.1109/FPL.2016.7577316\|isbn=978-2-8399-1844-2 \|s2cid=10923625 }}</ref>		In the [[computer vision]] domain, the JFA has inspired new [[belief propagation]] algorithms to accelerate the solution of a variety of problems.<ref>{{Cite book\|last1=Alchatzidis\|first1=Stavros\|last2=Sotiras\|first2=Aristeidis\|last3=Paragios\|first3=Nikos\|title=2011 International Conference on Computer Vision \|chapter=Efficient parallel message computation for MAP inference \|date=2011-11-06\|chapter-url=https://ieeexplore.ieee.org/document/6126392\|pages=1379–1386\|doi=10.1109/ICCV.2011.6126392\|isbn=978-1-4577-1102-2 \|s2cid=17554205 \|url=https://hal.archives-ouvertes.fr/hal-00858394/file/PID2005337.pdf }}</ref><ref>{{Cite book\|last1=Choi\|first1=Jungwook\|last2=Rutenbar\|first2=Rob A.\|title=2016 26th International Conference on Field Programmable Logic and Applications (FPL) \|chapter=Configurable and scalable belief propagation accelerator for computer vision \|date=2016-08-29\|chapter-url=https://ieeexplore.ieee.org/document/7577316\|pages=1–4\|doi=10.1109/FPL.2016.7577316\|isbn=978-2-8399-1844-2 \|s2cid=10923625 }}</ref>