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.
ACM Copyright Notice
Copyright by the Association for Computing Machinery, Inc. Permission to make digital or
hard copies of part or all 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, to republish, to post on servers, or to
redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications
Dept, ACM Inc., fax +1 (212) 869-0481, or email@example.com. The definitive version of this paper can be
found at ACM's Digital Library http://www.acm.org/dl/.