Spatial hashing

Spatial hashing is a simple technique that is used in databases, physical and graphics engine, particle simulation and everywhere, where you need to quickly find something. In short, the point is that we divide the space into cells with objects and adds them to the objects. Then, instead of looking for value very quickly looking for hash.

Suppose that you have several objects and you want to know whether the collision between them. The simplest solution is to calculate the distance from each object to all other objects. However, this approach increases the amount of computation required is too fast. If a dozen objects have to do a hundred checks, then hundreds of objects has been published for tens of thousands of checks. This is the infamous quadratic complexity of the algorithm.

Here and below we use the pseudo code suspiciously very similar to C #, but it is only an illusion.

// Each object
foreach (var obj in objects)
{
    if (Distance(this.position, obj.position) < t)
    {
        // Found one neighbor
    }
}

You can improve the situation, if you break the space with the help of the grid. Then each object gets into some cell of the grid and will be fairly easy to find the adjacent cells to test their occupancy. For example, we can be sure that two objects don't collide when they are separated by at least one cell.

Grid is already good, but there is a problem with the update of the grid. Permanent screening coordinate the cells can work well in two dimensions, but in three starts to slow down already. We can take a step further and bring a multidimensional search space is one-dimensional, hashing. Hashing will allow us to quickly fill cells and search for them. How does it work?

Hashing is the process of converting large amounts of data to a fixed, with little difference in the source data results in a large difference in the fixed. In fact it is a lossy compression. We can assign each cell of your ID, and when we compress the coordinates of objects, drawing an analogy with pictures, to lower their permission, then automatically obtain the coordinates of the desired cell. Thus filling all the cells, then we can easily get the objects in the vicinity of any origin. We just hash the coordinates and get a cell identifier objects.

It may look a hash function for a two-dimensional grid of fixed size? For example as follows:

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

We divide the X coordinate of the size of the cell and cut off the fractional part, then do the same with the Y coordinate and multiply 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 by simplifying calculations. True, they are simplified due to the appearance of conflicts when the hash is very distant object coordinates may coincide with the hash coordinates close. Therefore important to choose a hash function with good distribution and acceptable frequency of collisions. Read more at Wikipedia. I better show you how to realize in practice the three-dimensional spatial hash.

a little about hashes
What is faster calculate 2 * 2 * 3.14 or 3,1415926535897932384626433832795028841971 ...? Of course the first thing. We get less accurate result, but who cares? Likewise, hashes. We simplify the calculations lose their accuracy but most likely still get the result that we want. This feature hashes and the source of their power.

Let's start with the most important - a hash function for three-dimensional coordinates. In the article on the site Nvidia offer the following options:

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

Take the coordinate of each axis is divided by the size of a cell, use the bitwise shift and OR results with each other. The authors did not specify what the value should be a shift to the same bit math is not exactly "for the little ones." There is a function a little easier, as described in this this publication. If you translate it into code, we get something like that:

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

Find the coordinates of the cell for each axis, multiplied by a large prime number, and XOR. Honestly not much easier, but at least without unknown changes.

To work with a spatial hash convenient to have two containers, one for storing objects in cells other storage location numbers of objects. As the main container fastest hash table work, they are also dictionaries, they also heshmapy or as they are called in your favorite language. In one of them we get keyed-hash stored object in another object by key-cell number. Together, these two containers allow you to quickly find and check neighbors filled cells.

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

How did look to work with these containers? We insert objects using two parameters: the coordinates and the actual object.

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;
}

Hashing position, check the presence of a key in the dictionary, we push on the key object and the object key. When we need to update the coordinates, we remove the object from the old box and insert the new one.

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

If the object is updated at a time too many, it is easier to clean all the 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 all full class code is shown below. It uses a Vector3 of engine Unity, but the code can easily be adapted for the XNA framework or another.

using System.Linq;
using UnityEngine;
using System.Collections.Generic;

public class SpatialHash<T>
{
    private Dictionary<int, List<T>> dict;
    private Dictionary<T, int> objects;
    private int cellSize;

    public SpatialHash(int cellSize)
    {
        this.cellSize = cellSize;
        dict = new Dictionary<int, List<T>>();
        objects = new Dictionary<T, int>();
    }

    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;
    }

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

    public List<T> QueryPosition(Vector3 vector)
    {
        var key = Key(vector);
        return dict.ContainsKey(key) ? dict[key] : new List<T>();
    }

    public bool ContainsKey(Vector3 vector)
    {
        return dict.ContainsKey(Key(vector));
    }

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

    public void Reset()
    {
        dict.Clear();
        objects.Clear();
    }

    private const int BIG_ENOUGH_INT = 16 * 1024;
    private const double BIG_ENOUGH_FLOOR = BIG_ENOUGH_INT + 0.0000;

    private static int FastFloor(float f)
    {
        return (int)(f + BIG_ENOUGH_FLOOR) - BIG_ENOUGH_INT;
    }

    private int Key(Vector3 v)
    {
        return ((FastFloor(v.x / cellSize) * 73856093) ^
                (FastFloor(v.y / cellSize) * 19349663) ^
                (FastFloor(v.z / cellSize) * 83492791));
    }
}

 

All data posted on the site represents accessible information that can be browsed and downloaded for free from the web.

http://habrahabr.ru/post/182998/

 

User replies

No replies yet