Jump Flooding in GPU with Applications to Voronoi Diagram and Distance Transform

Guodong Rong and Tiow-Seng Tan

{ rongguod | tants }@comp.nus.edu.sg

National University of Singapore

School of Computing

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.

CR Categories: I.3.1 [Computer Graphics]: Hardware Architecture – Graphics Processors; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling – Geometric algorithms, languages, and systems; I.4.1 [Image Processing and Computer Vision]: Digitization and Image Capture – Image Geometry.

Keywords: Digital geometry, Interactive application, Programmable graphics hardware.

Paper in The Proceedings of ACM Symposium on Interactive 3D Graphics and Games (i3D 2006), March 14-17, 2006, Redwood City, CA, USA, pp. 109--116, pp. 228.

Video: click here to download the video clip (44M).

Related Projects: JFA Variants, Soft Shadow with JFA, Shadows for XBOX

See also: ShaderX5 - Advanced Rendering Techniques (Section 3.3), PhD Thesis (2.3M), Presentation (61M)

Dated: 22 December 2005, 12 April 2006, 15 May 2007, 26 June 2007, 13 March 2008

A total of 688 different hosts have accessed this document in the last 148 days; your host, 18.189.182.160, has accessed it 1 times.

If you're interested, complete statistics for this document are also available, including breakdowns by top-level domain, host name, and date.