How to Query Spatial Hash Maps for XPBD Self Collisions

Let's continue to take a look into spatial hash tables, and how to query them. This will be needed in order to implement self collisions in our XPBD Cloth Simulation.

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

By Carmen Cincotti  

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.

Folding cloths

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.

Self collisions 1

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 55:

Grid showing maxDist

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 55 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 44 is returned to us :

Indexing into cellCount, but finding nothing

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

nparticles=cellCount[i+1]cellCount[i] n_\text{particles} = \text{cellCount[i+1]} - \text{cellCount[i]}

where ii is the index that we just calculated.

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

nparticles=cellCount[5]cellCount[4]nparticles=11=0 n_\text{particles} = \text{cellCount[5]} - \text{cellCount[4]} \\[6pt] n_\text{particles} = 1 - 1 = 0

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

Check square where there are particles

By hashing squareCoordinate, we get the index 55. With this index, we query the cellCount array for particles as before:

nparticles=cellCount[6]cellCount[5]nparticles=21=1 n_\text{particles} = \text{cellCount[6]} - \text{cellCount[5]} \\[6pt] n_\text{particles} = 2 - 1 = 1

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 11.

Therefore, by indexing into particleMap with the index 11, we are able to see that particle 44 is within the square of interest.

To finish up, we add the particle 44 in an array called queryIds to use it later in the application:

Array holding query Ids

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 55:

Particle 4 falls within maxDist

We see in the image above that the particle 44 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:

Δp=pipjd=Δpx2+Δpy2 \Delta p = \text{p}_i - \text{p}_j\\[6pt] d = \sqrt{\Delta{p}_x^2 + \Delta{p}_y^2}

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

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

Particle 4 and 5 do not intersect

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(n2)O(n^2). However, during a simulation, such complexity is not acceptable.


Comments for How to Query 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


Interested in contributing to Carmen's Graphics Blog? Click here for details!