# Cloth Self Collisions | XPBD

Handling self collisions in cloth simulations will make a simulation much more real. This week, we'll study a few tips that Matthias from Ten Minute Physics suggests we use to help us implement this in our own simulations.

Keywords: graphics, tutorial, cloth simulation, leetcode, self collisions

Self collisions in a cloth simulation are collisions that occur between two particles in a piece of cloth.

Until now, we have been developing a cloth simulation that lives in GitHub.

The handling of self collisions in our simulation makes the difference between a simulation that seems real and one that is not really impressive…

By following this article, we will have a simulation capable of handling self collisions like this:

## What is a self collision?

A self collision is when two internal particles within an object collide.

In terms of a piece of fabric, a self-collision occurs when, for example, two threads collide and do not intersect, as in the image below:

The two threads on the left cross each other, which is not possible in real life because the threads obey the laws of physics. The two threads on the right exhibit correct behavior because they do not cross.

## Tips for implementing self collisions

To implement self collisions into a cloth simulation, I will explain in detail five ideas recommended by Matthias from Ten Minute Physics.

### Tip 1: Use a spatial hash table

With a spatial hash table, we can detect and correct collisions while looping the XPBD simulation.

We’ll see the code for such an implementation in the next article.

#### Use uniform particles

That said, to facilitate the use of a spatial hash table, it is recommended to use simple and uniform particles.

Let’s take the following image below as an example:

The uniform particles are located in a spatial hash table (which is represented by the grid in the image).

With this approach, we can simplify all calculations to detect collisions between particles.

Let’s see the opposite case where the particles are non-uniform:

By using non-uniform particles, we may have to perform more complex calculations to detect and correct for collisions.

### Tip 2: Avoid jerky simulation

In order to have a visually pleasing cloth simulation that takes into account self collisions, we need to consider the values of the following two parameters carefully :

• Rest length between particles
• Spacing between cells within a spatial hash table

Why consider both?

If these are misconfigured, it may be impossible to reach a stable cloth simulation. Basically, these two settings are linked.

Before seeing why this is the case, let’s review each parameter.

#### Rest length between particles

Recall that during an XPBD cloth simulation, we define a rest length between the particles:

In the image above, the variable $d$ is the rest length between each particle in a cloth model.

In XPBD simulation terms, the rest length, $d$, between two particles acts as a distance constraint, which will constrain the movement of the particles during a simulation in order to satisfy the constraint itself.

#### Spatial hash table spacing

The spacing is the size of each cell, or “square”, of the imaginary grid which is represented as a spatial hash table in the image below:

This parameter acts as the minimum distance needed between two particles to not be considered a collision, $d_{coll}$.

#### The instability problem

Let’s imagine that I would like to create a simulation with only two particles. I first define the initial position and the radius, $r_p = 0.5$, of the particles.

Next, I define our two parameters of interest:

• The rest length : $d_{rest} = 2.0$
• Spacing : Twice the radius of a particle, $d_{coll} = 2r_p = 1.0$.

In this case, there is no problem, because the rest length is long enough that $d_{coll} < d_{rest}$. This means that the distance constraint and the self collision constraint will not fight each other while they attempt to resolve themselves.

However, if I had set $d_{rest} = 0.5$… it will cause problems:

In such a simulation, the distance constraint will attempt to resolve itself by bringing the particles together.

However, the self collision constraint will try to resolve itself by acting against this movement.

This will cause a very jerky simulation!

#### The solution

To avoid a jerky simulation, we must define $d_{coll}$ like so:

$d_{coll} = \text{min}(2r_{p}, d_{rest})$

By setting $d_{coll}$ like this, the distance constraint and the collision constraint will no longer fight each other in order to resolve themselves.

That said, during a cloth simulation, I suggest defining $d_{coll} = 2r_{p}$ and $d_{rest} > 2r_p$

### Tip 3: Use sub-steps

We already learned about implementing substeps to increase the stability of an XPBD simulation a few months ago. We can also use it to better detect and correct collisions between particles:

Recall that to implement this, we simply need to divide the time step, $\Delta t$, by the number of desired sub-steps, $n$.

Next, we will follow the XPBD simulation as follows:

∆𝑡ₛ ← ∆𝑡/𝑛 (substep) for all vertices i initialize xᵢ = xᵢ_₀, vᵢ = vᵢ_₀, wᵢ = 1/mᵢ while simulating createHash() for 𝑛 sub-steps for all particles 𝑖 (pre-solve) 𝐯ᵢ ← 𝐯ᵢ + ∆𝑡ₛ*wᵢfₑₓₜ(𝐱ᵢ) 𝐩ᵢ ← 𝐱ᵢ 𝐱ᵢ ← 𝐱ᵢ + ∆𝑡ₛ*𝐯ᵢ for solverIterationCount for all constraints 𝐶 (solve) solve(𝐶, ∆𝑡ₛ) (solve for 𝐱ᵢ) for all particles 𝑖 (post-solve) 𝐯ᵢ ← (𝐱ᵢ − 𝐩ᵢ)/∆tₛ render()

This feature in our simulation allows us to avoid a more complex collision detection system like Continuous Collision Detection (CCD). To learn more, take a look at this resource!

### Tip 4: Limit the velocity

So far, we have a lot of ways to ensure a good simulation. A problem that remains however is the case where the particles in the simulation are moving too fast, which may actualize a phenomenon called tunneling:

In the image, we see two particles which were to collide during this time step…

However, they instead went through each other!

A lever we can pull to avoid such behavior is to limit the maximum speed of each particle.

Matthias from Ten Minute Physics recommends that we use this equation to find the maximum permitted speed:

$\mathbf{v}_{max} = \frac{r * n_{substeps}}{\Delta t}$

where $r$ is the radius of a particle.

We can see with this equation that the more sub-steps, $n$, that we use, the more the maximum allowed speed increases!

Let’s take an example where I have a piece of cloth containing particles with radii of size $\text{10cm}$. Our simulation runs with a time step $\Delta t = \frac{1}{60}$ and substeps $n = 20$:

$\mathbf{v}_{max} = \frac{\text{10cm} * 20}{\frac{1}{60}}\\[6px] \mathbf{v}_{max} = 120\frac{\text{m}}{\text{s}}$

Using the equation from above, we calculate a maximum permitted velocity of $120\frac{\text{m}}{\text{s}}$… which is very fast! In a cloth simulation, we’ll probably never come close to surpassing such a high velocity.

Let’s see another example with less substeps and a larger time step: $n = 1$ and $\Delta t = \frac{1}{30}$:

$\mathbf{v}_{max} = \frac{\text{10cm} * 1}{\frac{1}{30}}\\[6px] \mathbf{v}_{max} = 3\frac{\text{m}}{\text{s}}$

We calculated a maximum speed of $3\frac{\text{m}}{\text{s}}$, which is the speed of a human walking!

We can realistically believe that the particles of a cloth simulation could move faster than this.

So, to avoid any potential issues with tunneling, we should cap the velocity of the particles to not surpass this maximum velocity threshold.

### Tip 5: Introduce friction

Finally, it is recommended by Matthias to introduce friction during our calculations in order to better stabilize the simulation during a collision.

We should introduce it during the constraint solver loop, more precisely by following the calculation and the positional correction of a particle which has just collided with another particle.

#### How to calculate the friction correction

Imagine that we have just calculated the new positions $x_1, x_2$ of two particles which have just collided with each other. The next step is to calculate the velocity of each particle by using Verlet integration.

$\mathbf{v_1} = (\mathbf{x_1} - \mathbf{p_1}) / h \\[6pt] \mathbf{v_2} = (\mathbf{x_2} - \mathbf{p_2}) / h \\[6pt]$

Next, we calculate the average velocity.

$\mathbf{v_{avg}} = (\mathbf{v_1} - \mathbf{v_2}) / 2 \\[6pt]$

Then we find the difference between $\mathbf{v_{avg}}$ and each already calculated velocity $\mathbf{v_{2}}, \mathbf{v_{1}}$:

$\Delta {\mathbf{v}_1} = \mathbf{v_{avg}} - \mathbf{v_{1}}\\[6pt] \Delta {\mathbf{v}_2} = \mathbf{v_{avg}} - \mathbf{v_{2}}\\[6pt]$

Finally, the positions are updated by adding $\Delta \mathbf{v}_i * d$ where $d$ is a damping factor which is between $0$ and  \$1:

$\mathbf{x_1} \leftarrow \mathbf{x_1} + (d * \Delta {\mathbf{v}_1}) * h \\[6pt] \mathbf{x_2} \leftarrow \mathbf{x_2} + (d * \Delta {\mathbf{v}_2}) * h \\[6pt]$

I genuinely do not really understand the reasoning behind using average velocity during these steps… so if you know please contact me!

## Comments for Cloth Self Collisions | XPBD

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