Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/41901
Title: Jump flooding in GPU with applications to voronoi diagram and distance transform
Authors: Rong, G.
Tan, T.-S. 
Keywords: Digital geometry
Interactive application
Programmable graphics hardware
Issue Date: 2006
Source: Rong, G.,Tan, T.-S. (2006). Jump flooding in GPU with applications to voronoi diagram and distance transform. Proceedings of the Symposium on Interactive 3D Graphics 2006 : 109-116. ScholarBank@NUS Repository.
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. © 2006 ACM.
Source Title: Proceedings of the Symposium on Interactive 3D Graphics
URI: http://scholarbank.nus.edu.sg/handle/10635/41901
ISBN: 159593295X
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

60
checked on Dec 9, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.