Paper Info
Title
Jump flooding in GPU with applications to Voronoi diagram and distance transform
Abstract
This paper studies jump flooding as an algorithmic paradigm in the general purpose computation with GPU. As an example application of jump flooding, the paper discusses a constant time algorithm on GPU to compute an approximation to the Voronoi diagram of a given set of seeds in a 2D grid. The errors due to the differences between the approximation and the actual Voronoi diagram are hardly noticeable to the naked eye in all our experiments. The same approach can also compute in constant time an approximation to the distance transform of a set of seeds in a 2D grid. In practice, such constant time algorithm is useful to many interactive applications involving, for example, rendering and image processing. Besides the experimental evidences, this paper also confirms quantitatively the effectiveness of jump flooding by analyzing the occurrences of errors. The analysis is a showcase of insights to the jump flooding paradigm, and may be of independent interests to other applications of jump flooding.
Year
DOI
Venue
2006
10.1145/1111411.1111431
SI3D
Keywords
Field
DocType
jump flooding,actual voronoi diagram,experimental evidence,example application,paper study,jump flooding paradigm,algorithmic paradigm,constant time,voronoi diagram,constant time algorithm,distance transform,digital geometry,image processing
Computer graphics (images),Computer science,Image processing,Distance transform,Voronoi diagram,Rendering (computer graphics),Jump,Digital geometry,Grid,Computation
Conference
ISBN
Citations 
PageRank 
1-59593-295-X
88
3.65
References 
Authors
14
2
Name
Order
Citations
PageRank
Guodong Rong121310.09
Tiow-Seng Tan239827.99