“Perfect spatial hashing” by Lefebvre and Hoppe

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