article

Perfect spatial hashing

Authors:

Sylvain Lefebvre,

Hugues HoppeAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 25, Issue 3

Pages 579 - 588

https://doi.org/10.1145/1141911.1141926

Published: 01 July 2006 Publication History

Abstract

We explore using hashing to pack sparse data into a compact table while retaining efficient random access. Specifically, we design a perfect multidimensional hash function -- one that is precomputed on static data to have no hash collisions. Because our hash function makes a single reference to a small offset table, queries always involve exactly two memory accesses and are thus ideally suited for parallel SIMD evaluation on graphics hardware. Whereas prior hashing work strives for pseudorandom mappings, we instead design the hash function to preserve spatial coherence and thereby improve runtime locality of reference. We demonstrate numerous graphics applications including vector images, texture sprites, alpha channel compression, 3D-parameterized textures, 3D painting, simulation, and collision detection.

Supplementary Material

JPG File (p579-lefebvre-high.jpg)

Download
14.71 KB

JPG File (p579-lefebvre-low.jpg)

Download
11.95 KB

High Resolution (p579-lefebvre-high.mov)

Download
59.39 MB

Low Resolution (p579-lefebvre-low.mov)

Download
21.94 MB

References

[1]

Benson, D., and Davis, J. 2002. Octree textures. ACM SIGGRAPH, 785--790.]]

Digital Library

[2]

Blythe, D. 2006. The Direct 3D 10 system. ACM SIGGRAPH.]]

Digital Library

[3]

Brain, M., and Tharp, A. 1990. Perfect hashing using sparse matrix packing. Information Systems, 15(3), 281--290.]]

Digital Library

[4]

Cantlay, I. 2005. Mipmap-level measurement. GPU Gems II, 437--449.]]

[5]

Czech, Z., Havas, G., and Majewski, B. 1997. Perfect hashing. Theoretical Computer Science 182, 1--143.]]

Digital Library

[6]

Debry, D., Gibbs, J., Petty, D., and Robins, N. 2002. Painting and rendering on unparameterized models. ACM SIGGRAPH, 763--768.]]

Digital Library

[7]

Fox, E., Heath, L., Chen, Q., and Daoud, A. 1992. Practical minimal perfect hash functions for large databases. CACM 33(1), 105--121.]]

Digital Library

[8]

Fredman, M., Komlós, J., and Szemerédi, E. 1984. Storing a sparse table with O(1) worst case access time. JACM31(3), 538--544.]]

Digital Library

[9]

Gaede, V., and Günther, O. 1998. Multidimensional access methods. ACM Computing Surveys 30(2), 170--231.]]

Digital Library

[10]

Govindaraju, N., Lin, M., and Manocha, D. 2004. Fast and reliable collision culling using graphics hardware. Proc. of VRST, 2--9.]]

Digital Library

[11]

Ho, Y. 1994. Application of minimal perfect hashing in main memory indexing. Masters Thesis, MIT.]]

[12]

Kraus, M., and Ertl, T. 2002. Adaptive texture maps. Graphics Hardware, 7--15.]]

Digital Library

[13]

Lefebvre, S., and Neyret, F. 2003. Pattern based procedural textures. Symposium on Interactive 3D Graphics, 203--212.]]

Digital Library

[14]

Lefebvre, S., Hornus, S., and Neyret, F. 2005. Octree textures on the GPU. In GPU Gems II, 595--613.]]

[15]

Lefohn, A., Kniss, J., Strzodka, R., Sengupta, S., and Owens, J. 2006. Glift: Generic, efficient, random-access GPU data structures. ACM TOG 25(1).]]

Digital Library

[16]

Loop, C., and Blinn, J. 2005. Resolution-independent curve rendering using programmable graphics hardware. SIGGRAPH, 1000--1009.]]

Digital Library

[17]

Mehlhorn, K. 1982. On the program size of perfect and universal hash functions. Symposium on Foundations of Computer Science, 170--175.]]

Digital Library

[18]

Mirtich, B. 1996. Impulse-based dynamic simulation of rigid body systems. PhD Thesis, UC Berkeley.]]

Digital Library

[19]

Östlin, A., and Pagh, R. 2003. Uniform hashing in constant time and linear space. ACM STOC, 622--628.]]

Digital Library

[20]

Qin, Z., McCool, M., and Kaplan, C. 2006. Real-time texture-mapped textured glyphs. Symposium on Interactive 3D Graphics and Games.]]

Digital Library

[21]

Ramanarayanan, G., Bala, K., and Walter, B. 2004. Feature-based textures. Eurographics Symposium on Rendering, 65--73.]]

[22]

Ray, N., Cavin, X., and Lévy, B. 2005. Vector texture maps on the GPU. Technical Report ALICE-TR-05-003.]]

[23]

Sager, T. 1985. A polynomial time generator for minimal perfect hash functions. CACM 28(5), 523--532.]]

Digital Library

[24]

Schmidt, J., and Siegel, A. 1990. The spatial complexity of oblivious k-probe hash functions, SIAM Journal on Computing, 19(5), 775--786.]]

Digital Library

[25]

Sen, P., Cammarano, M., and Hanrahan, P. 2003. Shadow silhouette maps. ACM SIGGRAPH, 521--526.]]

Digital Library

[26]

Sen, P. 2004. Silhouette maps for improved texture magnification. Graphics Hardware Symposium, 65--73.]]

Digital Library

[27]

Tarini, M., and Cignoni, P. 2005. Pinchmaps: Textures with customizable discontinuities. Eurographics Conference, 557--568.]]

[28]

Teschner, M., Heidelberger, B., Müller, M., Pomeranets, D., and Gross, M. 2003. Optimized spatial hashing for collision detection of deformable objects. Proc. VMV, 47--54.]]

[29]

Tumblin, J., and Choudhury, P. 2004. Bixels: Picture samples with sharp embedded boundaries. Symposium on Rendering, 186--194.]]

[30]

Winters, V. 1990. Minimal perfect hashing in polynomial time, BIT 30(2), 235--244.]]

Digital Library

Cited By

Azad FCandan KKapkiç ALi MLiu HMandal PSheth PArslan BChowell-Puente GSabo JMuenich RRedondo Anton JSapino M(2024)(Vision Paper) A Vision for Spatio-Causal Situation Awareness, Forecasting, and PlanningACM Transactions on Spatial Algorithms and Systems10.1145/367255610:2(1-42)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1145/3672556
Reiser CGarbin SSrinivasan PVerbin DSzeliski RMildenhall BBarron JHedman PGeiger A(2024)Binary Opacity Grids: Capturing Fine Geometric Detail for Mesh-Based View SynthesisACM Transactions on Graphics10.1145/365813043:4(1-14)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658130
Dong BWu KByna S(2024)The Art of Sparsity: Mastering High-Dimensional Tensor Storage2024 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)10.1109/IPDPSW63119.2024.00094(439-446)Online publication date: 27-May-2024
https://doi.org/10.1109/IPDPSW63119.2024.00094
Show More Cited By

Index Terms

Perfect spatial hashing
1. Computing methodologies
  1. Computer graphics
  2. Parallel computing methodologies
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Perfect spatial hashing
SIGGRAPH '06: ACM SIGGRAPH 2006 Papers

We explore using hashing to pack sparse data into a compact table while retaining efficient random access. Specifically, we design a perfect multidimensional hash function -- one that is precomputed on static data to have no hash collisions. Because our ...
Minimal perfect hashing: A competitive method for indexing internal memory

A perfect hash function (PHF) is an injective function that maps keys from a set S to unique values. Since no collisions occur, each key can be retrieved from a hash table with a single probe. A minimal perfect hash function (MPHF) is a PHF with the ...
Perfect hashing schemes for mining traversal patterns

Hashing schemes are a common technique to improve the performance in mining not only association rules but also sequential patterns or traversal patterns. However, the collision problem in hash schemes may result in severe performance degradation. In ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 25, Issue 3

July 2006

742 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/1141911

Issue’s Table of Contents

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2006

Published in TOG Volume 25, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

106
Total Citations
View Citations
2,845
Total Downloads

Downloads (Last 12 months)72
Downloads (Last 6 weeks)15

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Azad FCandan KKapkiç ALi MLiu HMandal PSheth PArslan BChowell-Puente GSabo JMuenich RRedondo Anton JSapino M(2024)(Vision Paper) A Vision for Spatio-Causal Situation Awareness, Forecasting, and PlanningACM Transactions on Spatial Algorithms and Systems10.1145/367255610:2(1-42)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1145/3672556
Reiser CGarbin SSrinivasan PVerbin DSzeliski RMildenhall BBarron JHedman PGeiger A(2024)Binary Opacity Grids: Capturing Fine Geometric Detail for Mesh-Based View SynthesisACM Transactions on Graphics10.1145/365813043:4(1-14)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658130
Dong BWu KByna S(2024)The Art of Sparsity: Mastering High-Dimensional Tensor Storage2024 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)10.1109/IPDPSW63119.2024.00094(439-446)Online publication date: 27-May-2024
https://doi.org/10.1109/IPDPSW63119.2024.00094
Guo YCao YWang CHe YShan YZhang S(2023)VMesh: Hybrid Volume-Mesh Representation for Efficient View SynthesisSIGGRAPH Asia 2023 Conference Papers10.1145/3610548.3618161(1-11)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.1145/3610548.3618161
Lyu CBai KWu YDesbrun MZheng CLiu X(2023)Building a Virtual Weakly-Compressible Wind Tunnel Testing FacilityACM Transactions on Graphics10.1145/359239442:4(1-20)Online publication date: 26-Jul-2023
https://dl.acm.org/doi/10.1145/3592394
Molenaar MEisemann E(2023)Editing Compressed High‐resolution Voxel Scenes with AttributesComputer Graphics Forum10.1111/cgf.1475742:2(235-243)Online publication date: 23-May-2023
https://doi.org/10.1111/cgf.14757
Chen WWei YWang ZZhou SLin BZhou Z(2023)Federated Visualization: A Privacy-Preserving Strategy for Aggregated Visual QueryIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.326193829:6(2901-2913)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.1109/TVCG.2023.3261938
Gutow GChoset H(2023)Fast Point to Mesh Distance by Domain Voxelization2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)10.1109/IROS55552.2023.10341468(3264-3269)Online publication date: 1-Oct-2023
https://doi.org/10.1109/IROS55552.2023.10341468
Sabek IVaidya KHorn DKipf AMitzenmacher MKraska T(2022)Can Learned Models Replace Hash Functions?Proceedings of the VLDB Endowment10.14778/3570690.357070216:3(532-545)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.14778/3570690.3570702
Mallett ISeiler LYuksel C(2022)Patch Textures: Hardware Support for Mesh ColorsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2020.303977728:7(2710-2721)Online publication date: 1-Jul-2022
https://doi.org/10.1109/TVCG.2020.3039777
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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents