Perfect multidimensional spatial hashing

• US 7,619,623 B2
• Filed: 04/17/2006
• Issued: 11/17/2009
• Est. Priority Date: 04/17/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lefebvre, Sylvain, Hoppe, Hugues H.
• Primary Examiner(s): Chauhan; Ulka
• Assistant Examiner(s): BROOME, SAID A
• Application Number:
  US11/405,953
• Publication Number:
  US 20070244850A1
• Time in Patent Office: 1,310 Days
• Field of Search: 345/419
• US Class Current: 345/419
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/5862 using texture

Abstract

A multidimensional hash table is created based on a data source having sparse multidimensional data. The sparse source data is mapped into the hash table using a hash function. The hash function can be defined by accessing multidimensional values in an offset table. The offset values in the offset table can be precomputed from the static source data so as to avoid hash collisions, thus creating a perfect hash function. Additionally, the perfect hash function is designed to preserve spatial coherence of accesses, so as to improve locality of memory reference.

Claims

1. A method performed by a computer having a processor and a memory for efficiently accessing sparse spatial data by its position in a multidimensional space, the method comprising:

storing a hash table by the processor in a memory of the computer containing the sparse spatial data in densely packed form;

storing a set of offset values in an offset table by the processor in the memory of the computer, wherein the offset values map the positions of the sparse spatial data in the multidimensional space to a hash index of the densely packed sparse spatial data'"'"'s location in the hash table according to a perfect hash function formed as a sum modulo of a size of the hash table of a first hash function of the positions plus an offset value obtained from the offset table indexed by a second hash function of the positions, where the first hash function and second hash functions are calculated using identity matrix transforms of the positions to provide coherent data access from the positions to the sparse spatial data in the hash table; and

accessing the sparse spatial data by the processor from the hash table in the memory according to the perfect hash function of the sparse spatial data'"'"'s positions within the multidimensional space.

2. The method of claim 1, wherein the sparse multidimensional data comprises sparse two-dimensional data.

3. The method of claim 1, wherein the sparse multidimensional data comprises sparse three-dimensional data.

4. The method of claim 1, wherein storing a hash table comprises creating as compact a hash table as possible to contain the sparse multidimensional data.

5. The method of claim 1, wherein said accessing the sparse spatial data by the processor from the hash table in the memory according to the perfect hash function comprises adapting a heuristic ordering strategy to optimize data coherence.

6. The method of claim 1, wherein said storing a set of offset values in the offset table comprises creating the offset table to be as compact as possible while still permitting application of a perfect hash function.

7. The method of claim 1, wherein said storing a set of offset values in the offset table comprises:

setting the offset table size to an initial size; and

if a hash construction fails, successively increasing the offset table size until construction succeeds.

8. The method of claim 1, wherein said storing a set of offset values in the offset table comprises performing a binary search over the offset table size.

9. The method of claim 1, wherein the offset table comprises a square and the hash table comprises a square.

10. The method of claim 1, wherein the offset table comprises a cube and the hash table comprises a square.

11. The method of claim 1, wherein applying a perfect hash function comprises applying a minimal perfect hash function.

12. A computer system for providing efficient storage and access to sparse spatial data at positions in a multidimensional space, the computer system comprising:

a memory for storing;

a compact hash table having a geometric shape, the compact hash table capable of receiving the sparse spatial data in a packed format; and

a compact offset table having a geometric shape substantially similar to the geometric shape of the compact hash table, the compact offset table containing offset values for mapping the positions to indices of the sparse spatial data in the compact hash table according to a perfect hashing function formed as a sum modulo of a size of the compact hash table of a first hash function of the positions plus an offset value obtained from the offset table indexed by a second hash function of the positions, where the first hash function and second hash functions are calculated using identity matrix transforms of the positions to provide coherent data access from the positions to the offset values in the compact offset table and to the sparse spatial data in the compact hash table; and

a processing unit for accessing the sparse spatial data from the compact hash table in the memory according to the perfect hashing function of the sparse spatial data'"'"'s position in the multidimensional space.

13. One or more computer-readable storage media containing instructions which, when executed by a computer, cause the computer to perform a method of three-dimensional painting, the method comprising:

creating a hashing function on a three-dimensional domain to map three-dimensional data into a hash table using offset values in an offset table, where the hashing function is formed as a sum modulo of a size of the hash table of a first hash function plus an offset value obtained from the offset table indexed by a second hash function, where the first hash function and second hash functions are calculated using identity matrix transforms to provide coherent data access into the offset table and the hash table;

storing a plurality of position tags corresponding to the three-dimensional data mapped into the hash table;

comparing a paintbrush position with one of the plurality of position tags; and

updating the three-dimensional data mapped into the hash table based on the comparing.

14. The one or more computer-readable media of claim 13, wherein the hashing function comprises a perfect hashing function.

15. The one or more computer-readable media of claim 13, wherein the hash table is a two-dimensional hash table.

16. The one or more computer-readable media of claim 13, wherein the comparing and updating comprise performing one or more rasterization passes over the hash table data.

17. The one or more computer-readable media of claim 13, wherein the method further comprises transferring the hash table content to a conventional texture atlas representation.

18. The one or more computer-readable media of claim 13, wherein the method further comprises transferring the two-dimensional texture to a conventional texture atlas.