1819

Perfect spatial hashing

Sylvain Lefebvre, Hugues Hoppe
Microsoft Research
In SIGGRAPH ’06: ACM SIGGRAPH 2006 Papers (2006), pp. 579-588

@article{lefebvre2006perfect,

   title={Perfect spatial hashing},

   author={Lefebvre, S. and Hoppe, H.},

   journal={ACM Transactions on Graphics (TOG)},

   volume={25},

   number={3},

   pages={579–588},

   issn={0730-0301},

   year={2006},

   publisher={ACM}

}

Download Download (PDF)   View View   Source Source   

880

views

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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: