Numsgil: New page: This page covers the math behind collision response, especially in the case of multiple bodies forming a chain of direct and indirect collisions, such as a stack of bodies. This is called...

2009-05-16T09:53:56Z

New page: This page covers the math behind collision response, especially in the case of multiple bodies forming a chain of direct and indirect collisions, such as a stack of bodies. This is called...

New page

This page covers the math behind collision response, especially in the case of multiple bodies forming a chain of direct and indirect collisions, such as a stack of bodies. This is called an '''island'''.

== Basic concepts ==

=== Forces' linear affects ===
Any force acting on a body, at any point on a body, applies the same change in acceleration to the body's center of mass. Consider the diagram below:
__________
| |
| |
| X | <--- <math>\vec{Force_1}</math>
| |
|________| <--- <math>\vec{Force_2}</math>

''' Diagram 1 '''

Where X is the center of mass for the body. <math>\vec{Force_1}</math> is exactly centered, so it produces no torque. The change in acceleration of the body's center of mass is given by <math>\Delta \vec{a} = \frac{\vec{Force_1}}{Mass}</math>.

Let <math>\vec{Force_2}</math> have the same magnitude and direction as <math>\vec{Force_1}</math>. However it's applying its force at a different point on the body, and will produce torque. Even though it's off center, the change in acceleration for the body's center of mass is still <math>\Delta \vec{a} = \frac{\vec{Force_1}}{Mass}</math>.

=== Forces' angular affects ===
Consider Diagram 1 again. <math>\vec{Force_1}</math> will not produce any change in angular acceleration for the body, because it is centered. <math>\vec{Force_2}</math> ''will'' produce change in angular acceleration, because it is off center. In general, the '''torque''' (<math>\tau</math>) produced by a force is given by:

:<math>\tau = \vec{F} \cdot \vec{r_{\perp}^{P}}</math>

And the change in angular acceleration is given by:

:<math>\Delta \alpha = \frac{\tau}{I}</math>

Where:
* <math>\tau</math> is the scalar torque term.
* <math>\vec{F}</math> is the vector Force term.
* <math>\vec{r_{\perp}^{P}}</math> is the vector perpendicular to the vector from the body's origin to the place <math>\vec{F}</math> is acting on the body.
* <math>\alpha</math> is the scalar angular acceleration
* <math>I</math> is the body's scalar moment of inertertia.

== Simple collision ==

__________ __
| | / |
| | ___/ |
| X |P___ Y |
| | \ |
|________| \__|

''' Diagram 2 '''

Consider a collision between two bodies: body X and body Y. They collide at point P. We assume that the collision takes 0 time. That is, the bodies "instantly" resolve their collision.

The change in angular and linear velocity for body X is given by:

: <math>\Delta\vec{v} = \frac{j_0 \cdot \vec{n}}{m_X}</math>
: <math>\Delta\omega = j_0 * \frac{\vec{r_{\perp}^{XP}} \cdot \vec{n}}{I_X}</math>

where:
* <math>\Delta\vec{v}</math> is the change in linear velocity.
* <math>\Delta\omega</math> is the change in angular velocity.
* <math>j_0</math> is the scalar impulse term applied to the body at point P to correct its velocity from the collision.
* <math>m_X</math> is the scalar mass for the body.
* <math>I_X</math> is the scalar moment of inertia for the body.
* <math>n</math> is a vector representing the "normal" to the colision. In the case of the vertex-on-edge collision in Diagram 2, n would probably be <math><1, 0></math>
* <math>\vec{r_{\perp}^{XP}}</math> is the vector perpendicular to the vector from the center of mass of body X to the collision point P.

Body Y likewise, but the changes are opposite in sign (equal and opposite reaction).

We can define a relationship between the velocities before and after the collision using the [http://en.wikipedia.org/wiki/Coefficient_of_restitution coefficient of restitution]. Which is basically a fractional scalar value between 0 (for inelastic collisions) and 1 (for perfectly elastic collisions).

: <math>v_{XPf} - v_{YPf} = -(1 + \epsilon) * (v_{XPi} - v_{YPi})</math>

where:
* <math>v_{XPf}, v_{YPf}</math> are the final velocities of bodies X and Y at point P.
* <math>\epsilon</math> is the coefficient of restitution for the equation
* <math>v_{XPi}, v_{YPi}</math> are the initial velocities of bodies X and Y at point P.

To find the velocity of a body at a given point, use the formula:

: <math>v_P = v + \omega * r^P_\perp</math>

where:
* <math>v_P</math> is the velocity at a certain point on the body.
* <math>\omega</math> is the body's angular velocity.
* <math>r^P_\perp</math> is the vector perpindicular to the vector from the body's center of mass to point P.

Using all of the equations above, we can find <math>j_0</math> by the following algorithm:

suppose we are supplied with:
a contact point '''P'''
a collision normal '''n'''
two bodies in collision, '''bodyX''' and '''bodyY'''
a coefficient of restitution '''e'''

Vector VelocityAtPoint(Body body, Vector point)
{
return body.Velocity + body.AngularVelocity * (point - body.Position);
}

Scalar ResistanceFromBody(Body body, Vector point, Vector n)
{
Vector rPerp = (point - body.Position).Perp();
Scalar a = n.LengthSquared() * body.InverseMass; // The resistance to linear acceleration
Scalar q = Squared(rPerp.DotProduct(n)) * body.InverseMomentOfInertia; // The resistance to angular acceleration

return a + q;
}

Scalar vXP = VelocityAtPoint(bodyX, P);
Scalar vYP = VelocityAtPoint(bodyY, P);

Scalar b = -(1 + e) * (vXP - vYP).DotProduct(n);

Vector rXPNorm = (point - bodyX.Position).Perp();
Vector rYPNorm = (point - bodyY.Position).Perp();

Scalar resistanceX = ResistanceFromBody(bodyX, P, n);
Scalar resistanceY = -ResistanceFromBody(bodyY, P, n); //equal but opposite

Scalar j0 = b / (resistanceX - resistanceY);

return j0;

== Multiple collisions ==
Consider the case of collisions between '''N''' bodies simultaneously. We can expand from the last section to handle N contact points. The change in linear and angular velocity of a body is described by the equation:

: <math>\Delta\vec{v} = \Large{\frac{\sum_{i=0}^{N-1} j_i \cdot \vec{n}}{m}}</math>

: <math>\Delta\omega = \Large{\frac{\sum_{i=0}^{N-1} j_i \cdot \vec{r_{\perp}^{Pi}} \cdot \vec{n}}{I}}</math>

where:
* <math>j_i</math> is 0 if that contact point isn't part of that body's collision.

We can now form N equations (one for each collision), and solve for N unknowns (each collision impulse <math>j_i</math>).

The equation for collision <math>i</math> is given by:

: <math>\large{V_{BPi} + V_{APi} = b_i}</math>

: <math>\large{V_{XPi} = \sum_{k=0}^{k=N-1} (aX_k + qX_k)} \cdot j_k</math>

: <math>\large{aX_k = \frac{\vec{n_i} \cdot \vec{n_k}}{m_X}}</math>

: <math>\large{qX_k = \frac{ (\vec{r^{XPi}_\perp} \cdot \vec{n_i}) \cdot (\vec{r^{XPk}_\perp} \cdot \vec{n_k})}{I_X}}</math>

: <math>\large{b_i = -(1 + \epsilon) ((V_{BP} - V_{AP}) \cdot n_i)}</math>

: <math>\large{V_{XP} = V_X + \omega_X \cdot r^{XP}_\perp}</math>

All terms in the above quantities are known at the beginning of the collision except for <math>j_i</math>. So we can represent the system of equation as:

:<math>\large{\mathbf{A} \mathbf{j} = \mathbf{b} }</math>

For an example, suppose that there are 4 collisions. One between body A and body B (collision 0), two between body B and body C (collision 1 and 2), and one between body C and body D (collision 3). If we take the equation for <math>V_{XPi}</math> above, are replace <math>j_k</math> with commas, we can form the system of equations into a matrix:

: <math> \large{
\begin{bmatrix}
V_{BP0} - V_{AP0} \\
V_{CP1} - V_{BP1} \\
V_{CP2} - V_{BP2} \\
V_{DP3} - V_{CP3} \\
\end{bmatrix} \begin{bmatrix}
j_0 \\
j_1 \\
j_2 \\
j_3 \\
\end{bmatrix} = \begin{bmatrix}
b_0 \\
b_1 \\
b_2 \\
b_3 \\
\end{bmatrix} }</math>

Which can then be solved in <math>O(N^3)</math>.

Darwinbots3/Physics/Response - Revision history

Numsgil: New page: This page covers the math behind collision response, especially in the case of multiple bodies forming a chain of direct and indirect collisions, such as a stack of bodies. This is called...