Lecture 2: Collision Detection

26 Aug 2024

Notes Physically Based Modelling Lecture 2: Collision Detection

§ Collisions

Collisions do not usually occur at time step boundaries, so we must detect whether a collision has occurred, determine the exact time that it happened, and compute its response.

Specifically, this lecture goes over continuous collision detection (CCD) for the basic case of a ball and a plane.

While planes are used as an intuitive example in this discussion, it is actually a specific case of using a surface described by a signed-distance function (SDF).

§ Detection

Detection

Suppose we are given positions $\mathbf{x}^{(n)}$ and $\mathbf{x}^{(n + 1)}$ with distances $z_n$ and $z_{n}$ , respectively, and let the surface be defined as a level-set $z_c$ .

If $\mathrm{sgn}(z_n - z_c) \stackrel{?}{\neq} \mathrm{sgn}(z_{n + 1} - z_c)$ , then an object travelling from $\mathbf{x}^{(n)}$ to $\mathbf{x}^{(n + 1)}$ will collide with the level-set surface.

Detection doesn't tell us when or where a collision happened, just that it did happen.

Typically we use a zero level-set surface (i.e. let $z_c = 0$ ).

§ Determination

Determination

In determining a collision, we want to determine the time and point of contact.

Again, suppose we are given positions $\mathbf{x}^{(n)}$ and $\mathbf{x}^{(n + 1)}$ with distances $z_n$ and $z_{n}$ , respectively, and let the surface be defined as a level-set $z_c$ .

Let $f$ denote the fraction of a time step $h$ at which the collision occurred,

f = \frac{z_c - z_n}{z_{n + 1} - z_n}.

We can find the velocity and position at the time of contact by integrating with the fractional time step $fh$ instead of $h$ ,

\begin{align*} \vec{v}_c &= \vec{v}^{(n)} + fh\vec{a}\\ \vec{x}_c &= \vec{x}^{(n)} + fh\vec{v}^{(n)}. \end{align*}

In our case, we've only talked about explicit Euler integration; for other integration techniques we also find $\vec{v}_c$ and $\vec{x}_c$ by integrating $\vec{v}$ and $\vec{x}$ over $fh$ instead of $h$ .

Note that it is difficult to compute the exact time and point of contact.

Here, we used a linear interpolation to compute the fractional time step; for small enough time steps, this is a good enough approximation.

§ Response

Response

Given $\mathbf{v}_c$ and $\mathbf{x}_c$ , we want to find the collision response $\mathbf{v}_c'$ and $\mathbf{x}_c'$ based on the material properties of the colliding objects.

Typically collisions are not perfectly elastic, meaning that they lose some energy -- this could be from a myriad of forms, such as the sound of the impact, friction, object deformation, etc.

The most common responses: restitution and friction, have physical models based solely on the tangential and normal components of the velocity, respectively.

Suppose we have determined a collision with velocity $\mathbf{v}_c$ and position $\mathbf{x}_c$ .

Next, we can get the collision normal by computing the surface normal of the object we are colliding with at the point of collision.

We can imagine a separating plane between the two colliding objects defined by the point of contact and the surface normal.

Normal velocity $\mathbf{v}_\perp$ by doing a vector projection of $\mathbf{v}$ onto the collision normal $\hat{\mathbf{n}},$

\mathbf{v}_\perp = \|\mathbf{v}\|\hat{\mathbf{n}}.

And the tangent velocity $\mathbf{v}_\parallel$ by taking the difference between the velocity and its projection onto $\hat{\mathbf{n}},$

\mathbf{v}_\parallel = \mathbf{v} - \|\mathbf{v}\|\hat{\mathbf{n}} = \mathbf{v} - \mathbf{v}_\perp.

§ Resitution

An example of a normal response is restitution; i.e. how bouncy something is.

Restitution

Restitution is a measure of the elasticity of a collision, and its response is computed as

\|\mathbf{v}_\perp'\| = -\varepsilon \|\mathbf{v}_\perp\|,\quad 0 \leq \varepsilon \leq 1

where $\varepsilon$ is the coefficient of restitution.

In this case $\varepsilon = 0$ is a perfectly inelastic collision, and $\varepsilon = 1$ is perfectly elastic.

§ Friction

A common tangential response is friction.

A very simple, and very wrong, model of friction that some people might've learned in high-school is

\|\mathbf{v}_\parallel'\| = (1 - c_f) \|\mathbf{v}_\parallel\|,

where $c_f$ is the coefficient of friction.

A not much more complicated model, and the one that I was taught by the best high-school physics teachers, is the Coulomb model.

Coulomb Friction

In the Coulomb model, the force of friction is proportional to the normal force.

\mathbf{v}_\parallel' = \mathbf{v}_\parallel - \min(\mu \|\mathbf{v}_\parallel\|, \|\mathbf{v}_\parallel\|) \hat{\mathbf{v}_\parallel}

Friction can completely stop, but not reverse, motion; hence the $\min$ .