Perfect spatial hashing
ACM Trans. Graphics (SIGGRAPH), 25(3), 2006.
Sparse spatial data packed into a dense table using a simple collision-free map.
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.