up to Schedule & Notes

Collisions

To handle collision, we need to do two things:

We'll assume that collisions are instantaneous. This isn't correct, but is adequate for a simulation in which the only output is visual.

Time of collision

Let's suppose that we have a boolean predicate,

objectsIntersect( obj1, obj2 )

During the simulation, we apply that predicate to all pairs of objects. If at time $t$ there is no intersection, but at the next time step, $t + \Delta t$, these is an intersection, then there is an intersection in the in time interval $[t, t+ \Delta t]$.

We can use binary search on $[t,t+\Delta t]$ to find a time, $t^*$, of collision that is at most some $\epsilon$ away from the true time. Just search until the width of the current interval is less than $\epsilon$.

Efficient collision detection is much more difficult that what was described above, and usually uses data structures (such as Voronoi subdivisions) that maintain information about object/object adjacency and do not test for intersection between objects that are distant.

Once the time, $t^*$, of collision is found we have to

  1. Update the velocities at time $t^*$.
  2. Simulate the remainder of the interval, $[t^*,t+\Delta t]$. Of course, there might be more collisions in this remaining interval.

Velocity update upon collision

We'll assume a point-to-point contact at the collision point.

Then there is a plane of contact that is tangent to both objects at the point of contact. This is shown below with the plane normal $n$ that points from object 2 to object 1.

Case 1: no friction, one object fixed

We will assume that there is no friction during the contact. That means that the moving object (object 1 below) does not experience any force parallel to the plane of contact:

Let $v = v^\perp + v^\parallel$ be the object's velocity, where $v^\perp$ is perpendicular to the plane of contact and $v^\parallel$ is parallel. Then there is no change to $v^\parallel$ during the collision because there is no force parallel to the plane of contact.

A simple model of contact has $$v^\perp_\textrm{after} = k\ v^\perp_\textrm{before}$$ $$v^\parallel_\textrm{after} = v^\parallel_\textrm{before}$$

where $k$ is the coefficient of restitution and is in $[-1,0]$. So $$v_\textrm{after} = k\ v^\perp_\textrm{before} + v^\parallel_\textrm{before}$$

Case 2: no friction, no fixed object

Now let's have both objects free to move.

At the point of collision, an impulse acts to change the velocity of each object. An impulse is a force acting over a period of time and can cause a change in velocity: $$\begin{array}{rcll} P &=& \displaystyle \int_{\Delta t} F(t)\ dt \\ &=& \displaystyle F \int_{\Delta t} dt & \textrm{ if force is constant} \\ &=& \displaystyle F\ \Delta t \\ &=& \displaystyle (m\ \ddot{x})\ \Delta t \\ &=& \displaystyle m\ \Delta v \end{array}$$

The impulse, $P$, acts perpendicularly to the plane of contact. It acts positively on one object (let's say object 1) and negatively on the other (let's say object 2).

NOTE: The following derivation for $P$ differs from the video, which is incorrect. Below is the correct derivation.

What is $P$, which acts positively on object 1 and negatively on object 2?

The $v_1$ and $v_2$ below are in the perpendicular direction only. Since there's no friction, the speeds in the parallel direction do not change. $$\begin{array}{rcll} P &=& m_1\ \Delta v_1 \\ &=& m_1\ (v_{1,\textrm{after}} - v_{1,\textrm{before}}) \\ \end{array}$$

Similary on object 2: $$-P = m_2\ (v_{2,\textrm{after}} - v_{2,\textrm{before}})$$

And we'll constrain the relative speeds in the perpendicular direction using the coefficient of restitution, as in Case 1 above: $$v_{1,\textrm{after}} - v_{2,\textrm{after}} = k \;\; (v_{1,\textrm{before}} - v_{ 2,\textrm{before}})$$

The equations above form three scalar equations and three scalar unknowns (since this is only in the perpendicular direction), so $$ \left[ \begin{array}{ccc} m_1 & 0 & -1 \\ 0 & m_2 & 1 \\ 1 & -1 & 0 \end{array} \right] \;\; \left[ \begin{array}{c} v_{1,\textrm{after}} \\ v_{2,\textrm{after}} \\ P \end{array} \right] \;\; = \;\; \left[ \begin{array}{c} m_1 v_{1,\textrm{before}} \\ m_2 v_{2,\textrm{before}} \\ k \; (m_1 v_{1,\textrm{before}} - m_1 v_{2,\textrm{before}}) \end{array} \right] $$

Which can be solved to get $$P = {m_1 m_2 \over m_1 + m_2} (k-1) \; (v_{1,\textrm{before}} - v_{2,\textrm{before}})$$

(We can also get $v_{1,\textrm{after}}$ and $v_{2,\textrm{after}}$, but we'll do the extra computation below, instead.)

How does $P$ affect $\Delta v$ and $\Delta \omega$? From above $$\Delta v = {1 \over m}\ P$$

and the rotational part is $$\begin{array}{rcll} \Delta \omega &=& \displaystyle \int \dot\omega\ dt \\ &=& \displaystyle \int I^{-1}\ \tau\ dt & \textrm{since } \tau = I\ \dot\omega \\ &=& \displaystyle I^{-1}\ \int (r \times F)\ dt & \textrm{where } r \textrm{ is the point of contact} \\ &=& \displaystyle I^{-1}\ r \times \int F\ dt \\ &=& \displaystyle I^{-1}\ r \times P \end{array}$$

$P$ acts positively on object 1: $$\Delta v_1 = {1 \over m_1} P$$ $$\Delta \omega_1 = I_1^{-1}\ (r_1 \times P)$$

and negatively on object 2: $$\Delta v_2 = {1 \over m_2} (-P)$$ $$\Delta \omega_2 = I_2^{-1}\ (r_2 \times (-P))$$

The velocity and angular velocity of each object are be updated by $\Delta v_1, \Delta \omega_1, \Delta v_2, \Delta \omega_2$ after the collision.

Different effects are achieved by varying the coefficient of restitation, $k$.

Case 3: Friction

Incorporating friction into the collision is more involved and will not be discussed here.

up to Schedule & Notes $$\begin{array}{rcl} \end{array}$$