In the context of computer graphics, 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. This is joint work with Sylvain Lefebvre, who is now at INRIA Sophia-Antipolis.
Speaker Biography
Hugues Hoppe is a principal researcher in the Computer Graphics Group of Microsoft Research. His primary interests lie in the multiresolution representation, parameterization, and synthesis of both geometry and textures. He received the 2004 ACM SIGGRAPH Computer Graphics Achievement Award for pioneering work on surface reconstruction, progressive meshes, geometry texturing, and geometry images. His publications include dozens of SIGGRAPH papers, and he is associate editor for ACM Transactions on Graphics. He obtained a BS summa cum laude in electrical engineering in 1989 and a PhD in computer science in 1994 from the University of Washington.