Spatial hashing for the smallest

Spatial hashing is a simple technique that is used in databases, physical and graphic engines, particle simulations and, in general, everywhere where you need to quickly find something. If in short, the point is that we divide the space with objects into cells and add objects into them. Then, instead of searching by value, we very quickly search by hash.

Suppose you have several objects and you need to know if there are any collisions between them. The simplest solution is to calculate the distance from each object to all other objects. However, with this approach, the number of required calculations grows too fast. If you have to do hundreds of checks on a dozen of objects, then already tens of thousands of checks go on a hundred of objects. This is the infamous quadratic complexity of the algorithm.

Hereinafter, pseudocode is used, suspiciously very similar to C #, but this is only an illusion. This code is given at the end of the article.

//    foreach (var obj in objects) { if (Distance(this.position, obj.position) < t) { //    } } 

You can improve the situation by dividing the space with a grid. Then each object will fall into some grid cell and it will be quite easy to find the neighboring cells to check their fullness. For example, we can be sure that two objects do not collide if at least one cell separates them.
')


The grid is already good, but there is a problem with updating the grid. Permanent sifting of coordinates into cells can work well in two dimensions, but in three it is already starting to slow down. We can step further and reduce the multidimensional search space to one-dimensional by using hashing. Hashing will allow us to fill cells faster and search them. How does this work?

Hashing is the process of converting a large amount of data to a fixed one, with a slight difference in the original data resulting in a big difference in the fixed one. In essence, this is lossy compression. We can assign each cell its own identifier, and when we compress the coordinates of the objects, drawing an analogy with the pictures, lower their resolution, we automatically obtain the coordinates of the desired cell. Having filled all the cells in this way, we can then easily reach objects in the vicinity of any coordinates. We simply hash the coordinates and get the ID of the cell with the objects.

What might a hash function look like for a two-dimensional fixed-size grid? For example as follows:

 hashId = (Math.Floor(position.x / ellSize)) + (Math.Floor(position.y / ellSize)) * width; 

We divide the x coordinate by the cell size and cut off the fractional part, then do the same with the coordinate of the game and multiply it by the width of the grid. It turns out one-dimensional array as in the picture below.



In fact, we have the same grid as before, but the search is faster due to simplified computations. True, they are simplified due to the appearance of collisions, when the hash of the coordinates of a very distant object can coincide with the hash of the coordinates of the close one. Therefore, it is important to choose a hash function with a good distribution and an acceptable collision rate. Read more in Wikipedia. I'd better show you how to implement a three-dimensional spatial hash in practice.

I will add a little about hashes
What is faster to calculate 2 * 3.14 or 2 * 3.1415926535897932384626433832795028841971 ...? Of course the first. We will get a less accurate result, but who cares? Similarly with hashes. We simplify the calculations, lose accuracy, but with high probability we still get the result that suits us. This hash chip and the source of their power.

Let's start with the most important thing - hash functions for three-dimensional coordinates. In a very rich article on the site Nvidia offer the following option:

 GLuint hash = ((GLuint)(pos.x / CELLSIZE) << XSHIFT) | ((GLuint)(pos.y / CELLSIZE) << YSHIFT) | ((GLuint)(pos.z / CELLSIZE) << ZSHIFT); 

We take the coordinate along each axis, divide by the cell size, apply the bitwise shift, and OR'im the results between each other. The authors of the article do not specify what value the shift should be, moreover, bit math is not quite “for the smallest”. There is a little simpler function described in this publication . If you translate it into code, you get something like this:

 hash = (Floor(pos.x / cellSize) * 73856093) ^ (Floor(pos.y / cellSize) * 19349663) ^ (Floor(pos.z / cellSize) * 83492791); 

Find the coordinates of the cell on each axis, multiply by a large prime number and XOR'im. To be honest, it is not much easier, but at least without any unknown changes.

To work with a spatial hash, it is convenient to have two containers: one for storing objects in cells, the other for storing numbers of object cells. The main containers are the fastest working hash tables, they are dictionaries, they are also hashmaps or as they are called in your favorite language. In one of them, we obtain a stored object by the key-hash, in the other, by the object-key, the cell number. Together, these two containers allow you to quickly find neighbors and check the fullness of the cells.

 private Dictionary<int, List<T>> dict; private Dictionary<T, int> objects; 

What does working with these containers look like? We insert objects using two parameters: the coordinates and the object itself.

 public void Insert(Vector3 vector, T obj) { var key = Key(vector); if (dict.ContainsKey(key)) { dict[key].Add(obj); } else { dict[key] = new List<T> { obj }; } objects[obj] = key; } 

Hash the coordinates, check the presence of the key in the dictionary, push the object by the key and the key by the object. When we need to update the coordinates, we delete the object from the old cell and insert it into the new one.

 public void UpdatePosition(Vector3 vector, T obj) { if (objects.ContainsKey(obj)) { dict[objects[obj]].Remove(obj); } Insert(vector, obj); } 

If too many objects are updated at once, it is easier to clear all dictionaries and refill each time.

 public void Clear() { var keys = dict.Keys.ToArray(); for (var i = 0; i < keys.Length; i++) dict[keys[i]].Clear(); objects.Clear(); } 

That's it, the full class code is presented below. It uses Vector3 from the Unity engine, but the code can easily be adapted for XNA or another framework. The hash function uses some kind of “fast rounding”, I cannot vouch for its work.


In the interactive demonstration of this link you can see how the hash space is distributed. The coordinates of the yellow ball are hashed by a timer, after which it moves to a random point inside the sphere. Yellow cubes denote coordinates that fall into the same cell. The keys that have already been created are marked in blue so that you can look at the process of filling the memory. Mouse can be rotated.

Sources on GitHub | Online version for owners of Unity Web Player

Interesting related links

http://www.cs.ucf.edu/~jmesit/publications/scsc%202005.pdf
http://www.beosil.com/download/CollisionDetectionHashing_VMV03.pdf
http://http.developer.nvidia.com/GPUGems3/gpugems3_ch32.html