Car Physics
This week, once again, I have been iterating on my physics engine hoping I could fix some of its bugs. But since bugfixing newsletters can get boring, I'll walk you through how my physics engine works and we will fix the bug along the way!
How the Physics engine works
Overview
The very core idea of my car physics is the following:
- a car is a solid compound of ellipsoids (3D ellipses), this gives enough collision details while keeping math manageable
- the world is composed of sided triangles
- every physic update, each ellipsoid finds the deepest penetrating triangle
- each of those triangles push back according to a dampened spring model with friction
I think this last part is the most interesting and explains how my physics reaches decently looking collisions so let me detail with an example:
In first frame, imagine an ellipsoid with a downward velocity (in yellow) that has just penetrated the triangle (represented by the horizontal line). Let's imagine this system is a compressed suspension modelled by the classic dampened spring formula F = -k·x -c·vn where x is the pentration distance and vn the relative velocity of our ellipsoid at point of contact along the triangle's normal. Since the ellipsoid is not rotating, the velocity at point of contact (in green) is the same as the ellipsoid center's velocity. This also means there is no lateral velocity at point of contact, so no friction to account for this frame. Applying this force (in red) will push the ellipsoid back vertically and induce a rotation based on the lever arm from point of contact to center.
On frame two, after applying previous frame's forces, the ellipsoid is now falling a little bit less (it was pushed upward) and rotating (in blue). Relative velocity at point of contact is now slightly offset to the left by this rotating motion. We must then also apply a friction force such as F = -f.vt where vt is velocity of ellipsoid at point of contact projected on triangle's plane. The total of those forces will push the ellipsoid back up a bit more and slightly to the right (how much depends also on friction factor f of both the surface and the ellipsoid).
After a few more frames/steps, ellipsoid has bounced back (this depends on damping coefficient c seen above, the greater it is the less ellipsoid bounces back) and now has a lateral momentum. Try picturing a rubber rugby ball falling on the ground to convince yourself this is a model that can yield believable results. Here is an older video of mine showing what it can look like with a simple ellipsoid:
Applying forces
So we just saw how a collision can be modelled like a dampened spring with friction. But what type of spring and dampener? A constraint I gave myself was to limit duration of collisions to a few milliseconds (period during which ellipsoid is penetrating triangle) and their amplitude to a few centimetres (so that it wouldn't look too odd seeing the car inside a fence). By fixing expected max velocity at impact to a few hundreds of meters per second and mass to about a ton, this gives elasticity values in the 10's of millions. Needless to say that I would need to be careful when applying forces!
The classic way is to apply Euler's method; every frame we update physics state based on current state and a fixed deltatime:
- Xn+1 = Xn + dt · Vn
- Vn+1 = Vn + dt · Fn
- Fn = forces discussed above based on current state of physics
This method is off course highly dependent on chosen deltatime since Fn is assumed constant for the duration of the iteration. However, for the type of extreme oscillating forces I am dealing with, this assumption makes the physics unstable: the same collision at same speed would sometimes bounce a lot and sometimes less depending on when iterations occurred during penetration. Off course I could decrease my deltatime from an already-low 1/1000th of a second, but this comes at a cost (evaluating the collision function is not trivial since it needs to find in the world what surfaces the car collides with). Here is an example of this Euler's drift for a simple Harmonic Oscillator (un-dampened spring):
The alternative? Runge-Kutta. The idea of this method is to evaluate the costly collision detection function 4 times per iteration, at specific sub-steps and in a way that produces much less error than if we had divided deltatime by 4 (about a thousand times more accurate than Euler for my deltatime). In short (please just watch this phanimation's video on RK4 for an actual good explanation), we compute restitution forces at T, T+dt/2, T+dt/2, T+dt each time learning from previous step then combining the results appropriately. Here is an older video of mine showing the type of results it is capable of achieving:
A Single Triangle
Some point I skimmed through is how I only consider 1 triangle per car's ellipsoid and per iteration. You may think I should consider all collided geometry to apply restitution forces as it is usually the case in physics engine. However, the later usually do volume-to-volume collision detection/resolution which can be restrictive in how the environment is done (I really wanted to consider my static world like a huge collection of triangles to offer a lot of freedom in the type of geometry supported). It also means that when a wall is formed of two pieces (left & right), there can be an edge case if the car was to hit in between making bounces unpredictable.
Only accounting for the 1 triangle means that as the car drives over a surface (which may be one or multiple triangles, see image below), there is always 1 point of contact. Off course this comes at the expense that the physics may take more frame to resolve collisions if a same ellipsoid collides at the same time with multiple surfaces (e.g. the ground and a wall) but this is fairly rare.
Off course, the key is now to chose which triangle to consider, but I will explain this later.
Finding The Deepest Triangle
The Bug
Above we just saw how physics relies on finding, for every ellipsoid composing a car, the triangle it is penetrating the most. Finding the deepest triangle means finding the triangle penetrating ellipsoid that we would have to "push" the furthest to remove the intersection. When an ellipsoid is intersecting the inside of a triangle, we probably want to push straight along the normal of the triangle (see green line last image in above section). So in the general and easy case, we just find the correct of the 2 ellipsoid points that have a normal parallel to the triangle's normal (I'll save you the details but trust me it's the easy part) and we project that point back onto the triangle to get the ellipsoid-triangle penetration vector.
Off course, devil is in the detail! As the ellipsoid (think a wheel) is moving on the triangle's surface, it will inevitably encounter its edge (or even worse two of them at once). We want the algorithm to remain consistent whether another triangle comes after or not (for instance it could be two triangles forming a flat quad OR the edge of a cube). Here is an example of collision normal what we would expect for a cube:
The idea I had to achieve this was to (see image below for reference) project the ellipsoid point E0 (found with above method) back onto the triangle's plane (T0), then project it onto the triangle (T), and finally find closest ellipsoid point from there.
However, as I was testing my engine last week, I noticed that this algorithm was flawed. I drove slowly through the backface of a triangle, and here is what my physics interpreted:
Indeed, under the right -but annoying- circumstances, it is possible that the point found by aforementioned algorithm ends up on the wrong side of the triangle (I assume they only collide on one side). This obviously messes up the computation of restitution forces and projects the car fast in the air. Here is a simplified view of what is happening:
The Solution
So I decided to rethink the problem: if ellipsoid point nearest to deepest triangle point is not always where to "push back from", what point is it? And how do I compute it? In above example we can see how pushing from that top point would actually make ellipsoid collide even more with the triangle! Not only is it on the wrong side of the plane, it is also on the wrong side of that triangle's edge (above it is represented by the red dot).
If a good solution is found, it means that locally, other nearby ellipsoid point are further from targeted triangle point (again, the red dot). This means we are looking for a point P on ellipsoid such that the normal at this point aims towards the triangle's point T:
> Px²/Rx² + Py²/Ry² + Pz²/Rz² = 1
> Px/Rx² + Py/Ry² + Pz/Rz² = w·(P-T)By manipulating these equations we can find a function in w which is equal to 0 for the solution of our problem. We then just have to find the zeroes of this function (this is somewhat tedious but doable) to fianlly retrieve up to 6 candidate points (4 in 2D) that satisfy our problem:
Finally we discard candidate points that are either above the triangle's plane or on the wrong side of appropriate edges. Above, this would remove all points but the bottom one, which is indeed where to push ellipsoid from towards triangle point to resolve the collision the quickest. Here is a cool debug view I implemented (very enjoyable to finally see correct contact normals after a week spent on this tricky math problem) followed by some driving through obstacles:
Bloopers
If you read until here, you deserve some bloopers:
1. A strange bug where every other triangle would push my wheels in somewhat random directions
2. Nyan cat after a collision went wrong?
3. Collisions going wrong