Article

Jump flooding in GPU with applications to Voronoi diagram and distance transform

Authors:

Tiow-Seng TanAuthors Info & Claims

I3D '06: Proceedings of the 2006 symposium on Interactive 3D graphics and games

Pages 109 - 116

https://doi.org/10.1145/1111411.1111431

Published: 14 March 2006 Publication History

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.

References

[1]

Aurenhammer, F. 1991. Voronoi Diagrams-A Survey of a Fundamental Geometric Data Structure. ACM Computing Surveys 23, 3, 345--405.

Digital Library

[2]

Borgefors, G. 1984. Distance Transformations in Arbitrary Dimensions. Computer Vision, Graphics, and Image Processing 27, 321--345.

[3]

Cuisenaire, O. 1999. Distance Transformations: Fast Algorithms and Applications to Medical Image Processing. PhD Thesis, Université catholique de Louvain.

[4]

Danielsson, P.-E. 1980. Euclidean Distance Mapping. Computer Graphics and Image Processing 14, 227--248.

[5]

Denny, M. O. 2003. Algorithmic Geometry via Graphics Hardware. PhD Thesis. Universität des Saarlandes.

[6]

Donnelly, W. 2005. Per-Pixel Displacement Mapping with Distance Functions. GPU Gems 2: Programming Techniques for High Performance Graphics and General-Purpose Computation. Edited by M. Pharr and R. Fernando, Addison-Wesley, 123--136.

[7]

Eggers, H. 1998. Two Fast Euclidean Distance Transformations in Z2 Based on Sufficient Propagation. Computer Vision and Image Understanding 69, 1, 106--116.

Digital Library

[8]

Embrechts, H. and Roose, D. 1996. A Parallel Euclidean Distance Transformation Algorithm. Computer Vision and Image Understanding 63, 1, 15--26.

Digital Library

[9]

Harris, M. J. 2003. Real-time Cloud Simulation and Rendering. PhD Thesis. University of North Carolina at Chapel Hill.

Digital Library

[10]

Hoff, K. E., Keyser, J., Lin, M., Manocha, D. and Culver, T. 1999. Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware. In Proceedings of ACM SIGGRAPH 1999, ACM Press / ACM SIGGRAPH, New York. Computer Graphics Proceedings, Annual Conference Series, ACM, 277--286.

Digital Library

[11]

Huang, C. T. and Mitchell, O. R. 1994. A Euclidean Distance Transform Using Grayscale Morphology Decomposition. IEEE Transaction on Pattern Analysis and Machine Intelligence 16, 4, 443--448.

Digital Library

[12]

Montanari, U. 1968. A Method for Obtaining Skeletons Using a Quasi-Euclidean Distance. Journal of the Association for Computing Machinery 15, 4, 600--624.

Digital Library

[13]

Mullikin, J. C. 1992. The Vector Distance Transform in Two and Three Dimensions. Graphical Models and Image Processing 54, 6, 526--535.

Digital Library

[14]

Okabe, A., Boots, B., Sugihara, K. and Chiu, S. N. 1999. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. John Wiley & Sons Ltd.

Digital Library

[15]

Owens, J. D., Luebke, D., Govindaraju, N., Harris, M., Kröger, J., Lefohn, A. E. and Purcell, T. J. 2005. A Survey of General-Purpose Computation on Graphics Hardware. Eurographics 2005, 21--51.

[16]

Ragnemalm, I. 1992a. Fast Erosion and Dilation by Contour Processing and Thresholding of Distance Maps. Pattern Recognition Letters 13, 3, 161--166.

Digital Library

[17]

Ragnemalm, I. 1992b. Neighborhoods for Distance Transformations Using Ordered Propagation. CVGIP: Image Understanding 56, 3, 399--409.

Digital Library

[18]

Rosenfeld, A. and Pfaltz, J. L. 1966. Sequential Operations in Digital Picture Processing. Journal of the Association for Computing Machinery 13, 4, 471--494.

Digital Library

[19]

Shih, F. Y.-C. and Mitchell, O. R. 1992. A Mathematical Morphology Approach to Euclidean Distance Transformation. IEEE Transaction on Image Processing 1, 2, 197--204.

Digital Library

[20]

Strzodka, R. and Telea, A. 2004. Generalized Distance Transforms and Skeletons in Graphics Hardware. Proceedings of EG/IEEE TCVG Symposium on Visualization, 221--230.

Digital Library

[21]

Wang, L., Wang, X., Tong, X., Lin, S., Hu, S., Guo, B. and Shum, H. Y. 2003. View-dependent Displacement Mapping. ACM Transactions on Graphics 22, 3, 334--339.

Digital Library

[22]

Yamada, H. 1984. Complete Euclidean Distance Transformation by Parallel Operation. 7th International Conference on Pattern Recognition, Montreal, Canada, 336--338.

Cited By

Yoshizawa SMichikawa TYokota H(2024)Topological Delaunay Graph for Efficient 3D Binary Image AnalysisInternational Journal of Automation Technology10.20965/ijat.2024.p063218:5(632-650)Online publication date: 5-Sep-2024
https://doi.org/10.20965/ijat.2024.p0632
Allen BMaejima AAnjyo K(2024)Fast Leak-Resistant Segmentation for Anime Line ArtSIGGRAPH Asia 2024 Technical Communications10.1145/3681758.3698003(1-4)Online publication date: 3-Dec-2024
https://dl.acm.org/doi/10.1145/3681758.3698003
Erel YKozlovsky-Mordenfeld OIwai DSato KBermano A(2024)Casper DPM: Cascaded Perceptual Dynamic Projection Mapping onto HandsSIGGRAPH Asia 2024 Conference Papers10.1145/3680528.3687624(1-10)Online publication date: 3-Dec-2024
https://dl.acm.org/doi/10.1145/3680528.3687624
Show More Cited By

Index Terms

Jump flooding in GPU with applications to Voronoi diagram and distance transform
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Image and video acquisition
        Epipolar geometry
  2. Computer graphics
    1. Graphics systems and interfaces
      1. Graphics processors
    2. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Utilizing jump flooding in image-based soft shadows
VRST '06: Proceedings of the ACM symposium on Virtual reality software and technology

This paper studies the usage of the GPU as a collection of groups of related processing units, where each group communicates in some way to complete a computation efficiently and effectively. In particular, we use the GPU to perform jump flooding to ...
Use of hardware Z-buffered rasterization to accelerate ray tracing
SAC '07: Proceedings of the 2007 ACM symposium on Applied computing

Ray tracing is a rendering technique for producing realistic 3D computer graphics. Compared to traditional scan-line rendering which is generally adopted by graphics pipeline, ray tracing can simulate more realistic global illumination, however, with ...
A Generic and Scalable Pipeline for GPU Tetrahedral Grid Rendering

Recent advances in algorithms and graphics hardware have opened the possibility to render tetrahedral grids at interactive rates on commodity PCs. This paper extends on this work in that it presents a direct volume rendering method for such grids which ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

I3D '06: Proceedings of the 2006 symposium on Interactive 3D graphics and games

March 2006

231 pages

ISBN:159593295X

DOI:10.1145/1111411

Program Chairs:
Marc Olano,
Carlo Séquin

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 March 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 148 of 485 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

149
Total Citations
View Citations
1,337
Total Downloads

Downloads (Last 12 months)74
Downloads (Last 6 weeks)10

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yoshizawa SMichikawa TYokota H(2024)Topological Delaunay Graph for Efficient 3D Binary Image AnalysisInternational Journal of Automation Technology10.20965/ijat.2024.p063218:5(632-650)Online publication date: 5-Sep-2024
https://doi.org/10.20965/ijat.2024.p0632
Allen BMaejima AAnjyo K(2024)Fast Leak-Resistant Segmentation for Anime Line ArtSIGGRAPH Asia 2024 Technical Communications10.1145/3681758.3698003(1-4)Online publication date: 3-Dec-2024
https://dl.acm.org/doi/10.1145/3681758.3698003
Erel YKozlovsky-Mordenfeld OIwai DSato KBermano A(2024)Casper DPM: Cascaded Perceptual Dynamic Projection Mapping onto HandsSIGGRAPH Asia 2024 Conference Papers10.1145/3680528.3687624(1-10)Online publication date: 3-Dec-2024
https://dl.acm.org/doi/10.1145/3680528.3687624
Taniguchi D(2024)GaussMR: Interactive Gaussian Splatting Sandbox with GPU Particles and Signed Distance FieldsACM SIGGRAPH 2024 Immersive Pavilion10.1145/3641521.3664405(1-2)Online publication date: 27-Jul-2024
https://dl.acm.org/doi/10.1145/3641521.3664405
Klamer LDettling TDietsche DTrefftz CDeVries B(2024)Language Timing for Computing Voronoi Diagrams2024 IEEE International Conference on Electro Information Technology (eIT)10.1109/eIT60633.2024.10609940(1-5)Online publication date: 30-May-2024
https://doi.org/10.1109/eIT60633.2024.10609940
Dietsche DDettling TTrefftz CDeVries B(2024)Comparing Data Structures Used in Divide-and-Conquer Three-Dimensional Voronoi Diagrams2024 IEEE International Conference on Electro Information Technology (eIT)10.1109/eIT60633.2024.10609892(1-5)Online publication date: 30-May-2024
https://doi.org/10.1109/eIT60633.2024.10609892
Saikia MDhar SPal S(2024)Discrete Voronoi Diagram Construction Using Digital Geometric Approach2024 2nd International Conference on Computer Graphics and Image Processing (CGIP)10.1109/CGIP62525.2024.00017(48-53)Online publication date: 12-Jan-2024
https://doi.org/10.1109/CGIP62525.2024.00017
Dhar SPal S(2024)A Fast and Efficient Algorithm for Construction of Discrete Voronoi DiagramComputer Vision and Image Processing10.1007/978-3-031-58535-7_25(296-308)Online publication date: 3-Jul-2024
https://doi.org/10.1007/978-3-031-58535-7_25
Dhar SPal SBhattacharjee GPandey A(2024)A digital geometric approach for discrete Voronoi diagram construction using GPUConcurrency and Computation: Practice and Experience10.1002/cpe.801836:11Online publication date: 16-Jan-2024
https://doi.org/10.1002/cpe.8018
Zeng ZXu ZWang LWu LYan L(2023)Ray‐aligned Occupancy Map Array for Fast Approximate Ray TracingComputer Graphics Forum10.1111/cgf.1488242:4Online publication date: 26-Jul-2023
https://doi.org/10.1111/cgf.14882
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents