{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,12]],"date-time":"2026-01-12T20:17:56Z","timestamp":1768249076861,"version":"3.49.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2006,7,1]],"date-time":"2006-07-01T00:00:00Z","timestamp":1151712000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2006,7]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/1141911.1141926","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"579-588","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":110,"title":["Perfect spatial hashing"],"prefix":"10.1145","volume":"25","author":[{"given":"Sylvain","family":"Lefebvre","sequence":"first","affiliation":[{"name":"Microsoft Research"}]},{"given":"Hugues","family":"Hoppe","sequence":"additional","affiliation":[{"name":"Microsoft Research"}]}],"member":"320","published-online":{"date-parts":[[2006,7]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/566570.566652"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1179352.1141947"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4379(90)90001-6"},{"key":"e_1_2_2_4_1","unstructured":"Cantlay I. 2005. Mipmap-level measurement. GPU Gems II 437--449.]]  Cantlay I. 2005. Mipmap-level measurement. GPU Gems II 437--449.]]"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00146-6"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/566570.566649"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/129617.129623"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/280277.280279"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1077534.1077538"},{"key":"e_1_2_2_11_1","unstructured":"Ho Y. 1994. Application of minimal perfect hashing in main memory indexing. Masters Thesis MIT.]]  Ho Y. 1994. Application of minimal perfect hashing in main memory indexing. Masters Thesis MIT.]]"},{"key":"e_1_2_2_12_1","unstructured":"Kraus M. and Ertl T. 2002. Adaptive texture maps. Graphics Hardware 7--15.]]   Kraus M. and Ertl T. 2002. Adaptive texture maps. Graphics Hardware 7--15.]]"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/641480.641518"},{"key":"e_1_2_2_14_1","unstructured":"Lefebvre S. Hornus S. and Neyret F. 2005. Octree textures on the GPU. In GPU Gems II 595--613.]]  Lefebvre S. Hornus S. and Neyret F. 2005. Octree textures on the GPU. In GPU Gems II 595--613.]]"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1122501.1122505"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186822.1073303"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.80"},{"key":"e_1_2_2_18_1","unstructured":"Mirtich B. 1996. Impulse-based dynamic simulation of rigid body systems. PhD Thesis UC Berkeley.]]   Mirtich B. 1996. Impulse-based dynamic simulation of rigid body systems. PhD Thesis UC Berkeley.]]"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780633"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111411.1111433"},{"key":"e_1_2_2_21_1","volume-title":"Eurographics Symposium on Rendering, 65--73","author":"Ramanarayanan G."},{"key":"e_1_2_2_22_1","unstructured":"Ray N. Cavin X. and L\u00e9vy B. 2005. Vector texture maps on the GPU. Technical Report ALICE-TR-05-003.]]  Ray N. Cavin X. and L\u00e9vy B. 2005. Vector texture maps on the GPU. Technical Report ALICE-TR-05-003.]]"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3532.3538"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219054"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1201775.882301"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1058129.1058139"},{"key":"e_1_2_2_27_1","volume-title":"Eurographics Conference, 557--568","author":"Tarini M."},{"key":"e_1_2_2_28_1","volume-title":"Proc. VMV, 47--54","author":"Teschner M."},{"key":"e_1_2_2_29_1","volume-title":"Symposium on Rendering, 186--194","author":"Tumblin J."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02017345"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1141911.1141926","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1141911.1141926","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:14:23Z","timestamp":1750259663000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1141911.1141926"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,7]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,7]]}},"alternative-id":["10.1145\/1141911.1141926"],"URL":"https:\/\/doi.org\/10.1145\/1141911.1141926","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,7]]},"assertion":[{"value":"2006-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}