“Perfect spatial hashing” by Lefebvre and Hoppe

  • ©Sylvain Lefebvre and Hugues Hoppe




    Perfect spatial hashing



    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.


    1. Benson, D., and Davis, J. 2002. Octree textures. ACM SIGGRAPH, 785–790.]] Google ScholarDigital Library
    2. Blythe, D. 2006. The Direct 3D 10 system. ACM SIGGRAPH.]] Google ScholarDigital Library
    3. Brain, M., and Tharp, A. 1990. Perfect hashing using sparse matrix packing. Information Systems, 15(3), 281–290.]] Google ScholarDigital Library
    4. Cantlay, I. 2005. Mipmap-level measurement. GPU Gems II, 437–449.]]Google Scholar
    5. Czech, Z., Havas, G., and Majewski, B. 1997. Perfect hashing. Theoretical Computer Science 182, 1–143.]] Google ScholarDigital Library
    6. Debry, D., Gibbs, J., Petty, D., and Robins, N. 2002. Painting and rendering on unparameterized models. ACM SIGGRAPH, 763–768.]] Google ScholarDigital 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.]] Google ScholarDigital 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.]] Google ScholarDigital Library
    9. Gaede, V., and Günther, O. 1998. Multidimensional access methods. ACM Computing Surveys 30(2), 170–231.]] Google ScholarDigital Library
    10. Govindaraju, N., Lin, M., and Manocha, D. 2004. Fast and reliable collision culling using graphics hardware. Proc. of VRST, 2–9.]] Google ScholarDigital Library
    11. Ho, Y. 1994. Application of minimal perfect hashing in main memory indexing. Masters Thesis, MIT.]]Google Scholar
    12. Kraus, M., and Ertl, T. 2002. Adaptive texture maps. Graphics Hardware, 7–15.]] Google ScholarDigital Library
    13. Lefebvre, S., and Neyret, F. 2003. Pattern based procedural textures. Symposium on Interactive 3D Graphics, 203–212.]] Google ScholarDigital Library
    14. Lefebvre, S., Hornus, S., and Neyret, F. 2005. Octree textures on the GPU. In GPU Gems II, 595–613.]]Google Scholar
    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).]] Google ScholarDigital Library
    16. Loop, C., and Blinn, J. 2005. Resolution-independent curve rendering using programmable graphics hardware. SIGGRAPH, 1000–1009.]] Google ScholarDigital Library
    17. Mehlhorn, K. 1982. On the program size of perfect and universal hash functions. Symposium on Foundations of Computer Science, 170–175.]]Google ScholarDigital Library
    18. Mirtich, B. 1996. Impulse-based dynamic simulation of rigid body systems. PhD Thesis, UC Berkeley.]] Google ScholarDigital Library
    19. Östlin, A., and Pagh, R. 2003. Uniform hashing in constant time and linear space. ACM STOC, 622–628.]] Google ScholarDigital Library
    20. Qin, Z., McCool, M., and Kaplan, C. 2006. Real-time texture-mapped textured glyphs. Symposium on Interactive 3D Graphics and Games.]] Google ScholarDigital Library
    21. Ramanarayanan, G., Bala, K., and Walter, B. 2004. Feature-based textures. Eurographics Symposium on Rendering, 65–73.]]Google Scholar
    22. Ray, N., Cavin, X., and Lévy, B. 2005. Vector texture maps on the GPU. Technical Report ALICE-TR-05-003.]]Google Scholar
    23. Sager, T. 1985. A polynomial time generator for minimal perfect hash functions. CACM 28(5), 523–532.]] Google ScholarDigital 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.]] Google ScholarDigital Library
    25. Sen, P., Cammarano, M., and Hanrahan, P. 2003. Shadow silhouette maps. ACM SIGGRAPH, 521–526.]] Google ScholarDigital Library
    26. Sen, P. 2004. Silhouette maps for improved texture magnification. Graphics Hardware Symposium, 65–73.]] Google ScholarDigital Library
    27. Tarini, M., and Cignoni, P. 2005. Pinchmaps: Textures with customizable discontinuities. Eurographics Conference, 557–568.]]Google Scholar
    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.]]Google Scholar
    29. Tumblin, J., and Choudhury, P. 2004. Bixels: Picture samples with sharp embedded boundaries. Symposium on Rendering, 186–194.]]Google Scholar
    30. Winters, V. 1990. Minimal perfect hashing in polynomial time, BIT 30(2), 235–244.]] Google ScholarDigital Library

ACM Digital Library Publication: