# How to Create Spatial Hash Maps for XPBD Self Collisions

Let's take a look into spatial hash tables, and how to construct them. These will be very handy when we implement self collisions in our XPBD cloth simulation.

Keywords: graphics, tutorial, data structures, leetcode, self collisions

A spatial hash table is a special kind of hash table, which is a topic we’ve talked about a lot before in great detail.

Spatial hash maps deal with positions in space.

A spatial hash table is a good tool for detecting collisions between objects and particles, which will prove useful for things such as cloth simulations, video game physics engines, etc.

Let’s see together how such a structure works!

## A review of hash tables

Hey! Before continuing on - if you haven’t already read the previous articles on open addressing and hash tables, I really recommend that you take a look so that you can more easily follow along:

## What is a spatial hash table?

A spatial hash table looks like an ordinary hash table. However, the most striking difference is that a spatial hash table uses locations (2D or 3D) in space as the keys to hash to enter the table.

Let’s check out an example.

### An example

For this example, there is a particle that has settled in space at position $\text{pos}_p = (1, 3, -1)$.

To store this particle in a hash table, we use a hash function which takes as inputs the position of the particle.

The hash function returns an integer which serves as the index into the spatial hash table. The particle is stored at this index.

### How to hash a position

I use this function which comes from Matthias Müller:

 hashCoords(xi: number, yi: number, zi: number) { const hash = (xi * 92837111) ^ (yi * 689287499) ^ (zi * 283923481); return Math.abs(hash); }

The idea is to return a pseudo random integer. Thus, the hash function is less susceptible to returning hashes that cause hash collisions.

## Dense spatial hash table

A dense implementation of a spatial hash table was offered by Ten Minute Physics author Matthias Müller during one of his videos.

The dense implementation offers us a very efficient time and spatial complexity.

Only two arrays are used. :

• Particle Array - It stores references to the particles itself.
• Count Array - It stores the number of particles hashed to a particular bucket, which ultimately act as the index into the Particle Array.

We’ll see how this works in the next part!

## How to populate a dense hash table

To clarify this idea, let’s see step by step how to populate a dense hash table.

### Bounded space

#### Step 1: Create a grid

Let’s imagine that we create a grid overlaid on our particles:

Let’s define some properties of this grid:

• Spacing: the size of each grid square. A good rule of thumb is to define the spacing as two times the radius of a particle, $2r$.
• $(n_x , n_y)$ : the number of squares in each direction (and $n_z$ in the 3D case).

At this point, it’s our job to create a table that represents such a grid. Because this array is going to be designated to keep count of the particles in each square of the grid - we’ll call it cellCount:

Note : We add one more space which will be useful when we make a request - or query - for the particles which are around a location of interest. Ignore this for now, we will revisit this later!

#### Step 2: Fill the count array

Then, we loop through all the particles to fill cellCount. For each particle that belongs to a particular bucket, we increment the counter by $1$.

##### How to calculate the bucket that a particle belongs to

We use a particle’s position. Here is a potential method to calculate the index $i$ that we will use to index into cellCount :

$x_i = \text{Math.floor}(\frac{p_x}{\text{spacing}}) \\[6pt] y_i = \text{Math.floor}(\frac{p_y}{\text{spacing}}) \\[6pt] i = x_i * n_y + y_i \\[6pt]$

… and in 3D:

$z_i = \text{Math.floor}(\frac{p_z}{\text{spacing}}) \\[6pt] i = (x_i * n_y + y_i) * n_z + z_i \\[6pt]$

So having a particle at position $(1.5, 2.3)$ and a table with size of $(n_x, n_y) = (3, 3)$ and with spacing equal to $1$ gives us:

$x_i = \text{Math.floor}(\frac{1.5}{1}) = 1 \\[6pt] y_i = \text{Math.floor}(\frac{2.3}{1}) = 2 \\[6pt] i = 1 * 3 + 2 = 5 \\[6pt]$

The index is equal to $5$.

As you probably have already realized, this example we just saw depends on several variables, like location of the origin. Use this example as a guide and not as a solution.

#### Step 3: Calculate the partial sum

The next step is easy. We need to calculate the partial sum over the cellCount array. We can overwrite it with these new values.

#### Step 4: Fill in the particle array

Finally, we iterate over all the particles to store them in the array particleMap.

Take for example particle $5$:

1. Tout d’abord, on index dans cellCount à l’indice $7$, car la particule $5$ s’y trouve.
2. Then we decrement cellCount at this index which thus changes the integer stored here from $4$ to $3$.
3. This new integer is used as the index in particleMap. We store the particle $5$ at index $3$ in particleMap.

You can of course make this method more efficient by combining a few steps to avoid using extra loops.

### Unbounded space

Please note that in this example, the space is unbounded. The process from the previous section is therefore no longer sufficient!

#### Step 1: Create a grid

In this case, the grid is unbounded:

It is therefore not a good idea to try to represent such a structure with an underlying array of storage of an equal size, because we risk wasting too much memory.

How can we avoid this problem?

The answer: We create an array of fixed size to add all the particles to. This implementation will require resolving hash collisions!

Two parameters must be defined:

• Spacing: the size of each grid square. A good rule of thumb is to define the spacing as two times the radius of a particle, $2r$.
• Table Size: The size (tableSize) of the underlying storage table (cellCount).

In this case - we set tableSize to be equal to 9 plus 1 which makes 10:

#### Step 2: Fill the count array

Then we loop through all the particles to fill cellCount. This time we’re using a hash function to index into cellCount. in order to insert particles.

In order to index in the array, we can use this formula:

$i = \text{hash}(x_i, y_i) \mod \text{tableSize}$

But what is $x_i$ and $y_i$? We could naively define them as the coordinates of the particle itself, but that would mean that particles within the same square could potentially hash to different buckets!

Therefore we have to normalize the coordinates of a particle to instead the position of the square that it resides in.

This is simple - we can use the hashPos function which calls intCoord, which returns a coordinate of a square in the grid :

 intCoord(coord: number) { return Math.floor(coord / spacing); } hashPos() { return hashCoords( intCoord(pos_x), intCoord(pos_y), intCoord(pos_z) ); }

And we already defined our hash function, hashCoords, above.

We can now guarantee that all particles within a certain square in the grid will hash to the same location.

##### How to resolve hash collisions

As you can see, the particles $2$ and $3$ resolve to the same bucket. We just have to increment the count in cellCount at this index. We will see why it works in the following steps.

#### Step 3: Calculate the partial sum

Just like before, we need to calculate the partial sum over the cellCount array. We can overwrite it with these new values.

#### Step 4: Fill in the particle array

Finally, we iterate over all the particles to store them in the array particleMap (the particle table).

Take for example the particle $5$:

1. First, we index into cellCount at index $8$, because particle $5$ is hashed to that location.
2. Next, we decrement cellCount at this index, which changes the integer stored here from $3$ to $2$.
3. This new integer is used as an index in particleMap. Thus, we store the particle $5$ at index $2$ in particleMap.

## Next time…

We will see how query for particles within the spatial hash table, and of course we’ll start coding!

## Comments for How to Create Spatial Hash Maps for XPBD Self Collisions

Written by Carmen Cincotti, computer graphics enthusiast, language learner, and improv actor currently living in San Francisco, CA.  Follow @CarmenCincotti