Year 1, Term 3, 2024
Physics Programming
Continuous collision detection solved with a quadratic discriminant, on a vector type written from scratch.
- GXPEngine
- C#
- Solo
- One term
What it was, and what I owned
A physics playground built on GXPEngine, a bare 2D framework with no physics of its own. Everything below is mine, including the vector type, because the engine does not ship one.
That work did not come out of one clean pass. I failed the assignment on my first attempt, then rebuilt the vector and collision code while carrying a full team-built game in term 4, Cog in the Machine. The two projects share a byte-identical Vec2.cs, and the code on this page is the improved version, refined against a real team project rather than a grading rubric, that passed the redo after the game was done.
The core problem is tunnelling. If you move a ball by its velocity each frame and then check for overlaps, a fast ball passes straight through a thin wall between two frames and the collision never happens. The fix is to stop asking 'do these overlap now' and start asking 'when, between now and the end of this frame, do they first touch'.
For ball-versus-ball that reduces to a quadratic in time, solved with the discriminant: no real root means they never meet this frame, and the smaller root is the first contact. For ball-versus-line-segment it is a projection onto the segment normal. Every mover computes its earliest collision across all candidates, the simulation advances to that moment, resolves the impulse, and repeats with the remaining slice of the frame until the frame is used up.
Gravity, drag, mass and bounciness integrate per frame against delta time, so the behaviour does not change with frame rate.
The code that makes the claim checkable
float CalculateTOIBall(Vec2 a, Vec2 b, Vec2 c)
{
if (a.x != 0)
{
float D = b.Dot(b) - 4 * a.Dot(c);
if (D >= 0)
{
float TOI = (b.Dot(new Vec2(-1, -1)) - Mathf.Sqrt(D)) / a.Dot(new Vec2(2, 2));
if (0 <= TOI && TOI < 1)
{
return TOI;
}
}
}
return 0;
}Time of impact for two moving circles. D is the discriminant: negative means no contact this frame, and the smaller root is the first moment they touch. The 0 <= TOI < 1 guard keeps the hit inside this frame's slice.
public void Reflect(Vec2 normal, float bounciness)
{
Vec2 velocityOut = new Vec2((1 + bounciness) * Dot(normal) * normal.x, (1 + bounciness) * Dot(normal) * normal.y);
x -= velocityOut.x;
y -= velocityOut.y;
}Reflection about a surface normal, scaled by bounciness. GXPEngine has no vector type, so Vec2 is written from scratch: Normalize, Dot, Normal, rotation by degrees and radians, rotate-around-point, and this.
Systems deep-dive
Discrete collision detection asks whether two shapes overlap right now. That question has a wrong answer for anything moving faster than its own radius per frame, which in a physics playground is most things.
Continuous detection asks when they first touch. Set up the positions as functions of time across the frame, require the distance between the two centres to equal the sum of the radii, and the result is a quadratic in t. The discriminant tells you whether a real contact exists: negative and they miss entirely this frame. If it exists, the smaller root is the first contact, and it is only useful if it falls inside [0, 1), the normalized span of the current frame.
Line segments are simpler: project the movement onto the segment's normal and solve for the moment that projection equals the radius.
Resolution runs as an earliest-collision loop. Find the soonest contact among all candidates, advance every body to exactly that instant, resolve that one collision, then repeat for whatever remains of the frame. Handling collisions in time order rather than list order is what stops a three-body pileup from resolving into geometry.