CS 3 (Spring 2022) Project 06: Collision Resolution

In this project, you will add collision resolution to last week’s collision detection and modify your space invaders game into a breakout game.

Last Physics Engine Project

This is the last physics engine project. Your game design document will be due Wednesday @ 11:30pm this week. You can find a specification for the design document here.

Code Correctness

Deliverables

This week’s demo is effectively an extension of last week’s with some minor changes. The two tasks this week are:

Demos

The main demo this week is a simple version of Breakout.

Your game demo must have the following features (but feel free to play around and implement anything you want otherwise):

Additionally, we have provided you with a “pegs” demo which must work correctly with your code.

Collision Resolution

Last week, you implemented find_collision() to detect collisions between two convex polygons. This week, you will implement collision resolution, which changes the velocities of the bodies based on the physics of the collision. There are two main components to implement:

Finding the collision axis

When two bodies collide in 3D space, there is a contact plane tangent to both bodies at the point of collision. The collision creates a “normal force” perpendicular to the contact plane. In 2D space, there is an analogous contact line tangent to the bodies. Just as in 3D physics, the applied force is perpendicular to the contact line. We refer to the unit vector perpendicular to the contact line as the “collision axis.” (There are actually two perpendicular directions; we will choose the one that points from the first body towards the second.) In the example below, the black line is the contact line and the red vector is the collision axis (from the green body towards the blue body).

collision

When bodies are polygons rather than continuous shapes, there is no longer a tangent line, but we can approximate a collision axis.

If you implemented the Separating Axis method last week, the collision axis is simply the axis onto which the shapes’ projections have the least overlap.

If you implemented the Vertex Containment method last week, computing the collision axis is a bit harder. The idea is compute a vector pointing outwards from each contained vertex. The vector pointing outwards should have an angle halfway between the angles of its neighboring edges. This can be done by adding unit vectors along both edges. For example, the red vertex below is contained in the blue shape, so adding unit vectors along the edges produces the dashed outwards vector.

vertex containment outwards vector

We perform this “outwards vector” calculation on each vertex of each polygon that is contained inside the other. The sum of outwards vectors from the first polygon minus the sum of outwards vectors from the second polygon gives the direction of the collision axis. Below, three vertices are contained in the opposite polygon. To find the collision axis pointing from the green shape towards the blue shape, we compute an outwards vector at each vertex and subtract the blue vectors from the green vector:

vertex containment multiple outwards vectors

vertex containment superimposed outwards vector

vertex containment outwards vector sum

Note that the sum of outwards vectors needs to be normalized since the collision axis is expected to be a unit vector.

Computing the impulse

You may remember from Ph 1a that when bodies collide, momentum is conserved. However, kinetic energy is only conserved when the bodies collide elastically (like billiard balls). You will implement collisions with variable amounts of elasticity, controlled by a parameter double elasticity. If elasticity is 1, the collision is elastic. If elasticity is 0, the collision is completely inelastic; if the bodies are moving along a line, they stick together when they collide. Values of elasticity between 0 and 1 correspond to partially elastic collisions. If elasticity is greater than 1, the collision is “super-elastic”: kinetic energy increases in the collision.

There is a simple formula for the impulse due to a collision with a certain elasticity, so we will apply impulses instead of forces to resolve the collision. The formula can be found on Wikipedia, but here’s an explanation:

Given that

The impulse applied to each body is parallel to the collision axis. The parallel component of the impulse applied to the first body is:

impulse

To conserve momentum, an equal and opposite impulse is applied to the second body.

Notes

Because bodies with mass INFINITY are not affected by forces or impulses, it is natural to use them as “walls” in a collision. For example, you could have implemented the bounce demo in project01 by making the star collide elastically with an infinite-mass wall on each side of the scene. This requires a minor change to the formula for computing the impulse: if one of the masses is INFINITY, the reduced mass (m_a * m_b / (m_a + m_b)) in the formula becomes the mass of the other body.

If two bodies collide in a tick and an impulse is applied to resolve the collision, they may still be colliding in the next tick. In this case, you should not apply a second impulse to the bodies in the next tick. Only resolve a collision between two bodies if they were not colliding in the previous tick.

Grading

The grading this week will be based on: