Haskcode for three-dimensional integer coordinates with high spatial coherence

Question

this is my first question on these forums :)

I am writing a coordinate class in Java for a spatial octave voxel system. These coordinates are not floating point coordinates, they are 4D integer indices in octree (3 normal sizes X, Y, Z and fourth for depth in the tree). The first 3 values ​​are all shorts, the last dimension is byte. In fact, only the first 11 bits of shorts and only 3 bits of bytes are currently used, but this can be changed.

Now I am trying to write a "good" hash function for this class. The problem I'm struggling with is that coordinates will often be used in highly spatial connected situations (I hope that I use the correct terminology there). I mean that often the time when a coordinate will be hashed along with its neighboring neighbors and other neighboring coordinates.

Is there a good practice to make these coordinates “next to each other” create significantly different hash codes?

Answer 1

You are in luck: there is a way to get decent coordinating encodings with high spatial connectivity using something called a Z-order curve .

The trick is to alternate the bits of different coordinate components. Therefore, if you have 3 8-bit coordinates, for example:

[XXXXXXXX, YYYYYYYY, ZZZZZZZZ] 

Then the encoded value of the z-curve will be the only 24-bit value:

 XYZXYZXYZXYZXYZXYZXYZXYZ 

You can extend to more bits or coordinates as needed.

This encoding works because coordinates that are close in space will have differences, mainly in lower order bits. Thus, alternating the coordinates, you get the differences focused in the least significant bits of the encoded value.

An additional interesting property is that the least significant bits describe the coordinates in cubes of space. Thus, the lowest 3-bit address position with 2x2x2 cubes, the smallest 6-bit address position within 4 * 4 * 4 cubes, the lowest 9-bit position within 8 * 8 * 8 cubes, etc. Thus, it is actually a fairly ideal system for accessing co-constraints within the octa.

Answer 2

“Significantly different” really depends on what you do with the hash code afterwards. In some cases, it will cycle through the bucket, taking hash % size , where size is the size of the hash map used, for example. Obviously, this will change over time. I would usually use something like:

 int hash = 23; hash = hash * 31 + x; hash = hash * 31 + y; hash = hash * 31 + z; hash = hash * 31 + depth; return hash; 

(basically it is cut from Effective Java ). Obviously, this means that (x1, y1, z1) and (x1 + 1, y1 - 31, z1) will have the same hash code, but if you are more concerned about very close neighbors, this should not be a problem.

EDIT: mikera's answer will most likely work better, but it will be harder to code. First I'll try this very simple approach and see if this is enough for your actual use cases. Use gradually more effective but sophisticated approaches until you find good enough.