Jump flooding algorithm

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

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.^[1]

^ ^a ^b Rong, Guodong; Tan, Tiow-Seng (2006-03-14). "Jump flooding in GPU with applications to Voronoi diagram and distance transform" (PDF). Proceedings of the 2006 symposium on Interactive 3D graphics and games - SI3D '06. Redwood City, California: Association for Computing Machinery. pp. 109–116. doi:10.1145/1111411.1111431. ISBN 978-1-59593-295-2. S2CID 7282879.

[Rong2006-1] Rong, Guodong; Tan, Tiow-Seng (2006-03-14). "Jump flooding in GPU with applications to Voronoi diagram and distance transform" (PDF). Proceedings of the 2006 symposium on Interactive 3D graphics and games - SI3D '06. Redwood City, California: Association for Computing Machinery. pp. 109–116. doi:10.1145/1111411.1111431. ISBN 978-1-59593-295-2. S2CID 7282879.

[1]