I would like to continue our conversation about spatial hash tables, which we were started learning about last week.

Spatial hash maps will allow us to implement a very important feature of cloth simulations : **self collisions**.

## What is a cloth self-collision?

**A self-collision** is the interaction that occurs when particles of a piece of fabric collide against one another.

## How to query a spatial hash table

Let’s see together how to make queries to a spatial hash table in order to detect particles close to each other, **while keeping time complexity fast.**

### Step 1: Create the spatial hash table and populate it

We have already seen how to do this in the previous article. I suggest you read it before continuing!

With our two arrays, `cellCount`

and `particleMap`

, we are ready to search for nearby particles.

### Step 2: Query for adjacent squares

Our goal in this step is to find all particles that are in adjacent squares in order to limit the search to nearby particles. **This method is very fast compared to a method that checks each particle to see if they are nearby or not.**

To perform such a query, we define a maximum search distance, `maxDist`

. Let’s imagine that I have already set `maxDist`

equal to the length of a square and I would like to search for particles close to particle $5$:

As you can see, I’ve marked all points that we’ll eventually query as violet.

Now, we’ll loop through all of these violet points in order to see if the squares in which they reside contains particles. We’ll also need to check the square that particle $5$ resides in.

For now, let’s see an example on how to check for particles within a square of interest. I’ll query the top left violet point.

*I’m going to query the purple point at the top left.* We start by calculating the coordinate of the grid, `squareCoordinate`

, in which this point is located. To do this, we use the `intCoord`

function:

```
intCoord(pos: number) {
return Math.floor(pos / spacing);
}
const squareCoordinates = [
intCoord(pos.x),
intCoord(pos.y),
]
```

Using `squareCoordinate`

, we can index into `cellCount`

to see what particles are there…

Recall that we can use the hash function `hashPos`

to compute the hash of a position:

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

Assume that we use a hash function that, by hashing `squareCoordinate`

, the index $4$ is returned to us :

To see if there are particles in this space, we carry out the following calculation:

where $i$ is the index that we just calculated.

Continuing this example, we find that there is nothing in the table at index $4$!:

Now, let’s see an example of a square in which particles reside. Let’s query the coordinate located at the bottom:

By hashing `squareCoordinate`

, we get the index $5$. With this index, we query the `cellCount`

array for particles as before:

This time, we see that one particle does exist within the square of interest! The number at `cellCount[i]`

also acts as the index into `particleMap`

, which in this case is $1$.

Therefore, by indexing into `particleMap`

with the index $1$, we are able to see that particle $4$ is within the square of interest.

To finish up, we add the particle $4$ in an array called `queryIds`

to use it later in the application:

### Step 3: Confirmation of the collision

With our array, `queryIds`

, it’s time to confirm that each particle found in the previous step falls within the maximum search distance, `maxDist`

, from the particle of interest, in this case particle $5$:

We see in the image above that the particle $4$ is indeed within this search radius. In the code, we need to use a distance function to confirm this is the case. We can use a typical distance function, like so:

If $d < \text{maxDist}$, we can consider that the two particles intersect!

If $d > \text{maxDist}$, we would notice that the two particles do not intersect, just like as represented in the image below:

Of course, we can avoid these steps by using two loops to visit all the particles twice in order to determine if two particles intersect. Such an operation would have a time complexity $O(n^2)$. However, **during a simulation, such complexity is not acceptable.**