It's time to talk about Collision Detection and Resolution.
How do we detect when two (or more) bodies collide, and what happens if we do?
I will (for now) ignore the problems associated with objects that travel very fast, and will concentrate on the typical scenario, where objects cannot pass through each other in a single timestep, ie, we can detect their collision.
Most of the time, we won't see our object nicely kissing each other, we will instead see them penetrating one another. This is known as "interpenetration". In order to resolve this situation, there are two schools of thought.
The most common solution is to try to measure the penetration depth, and use that to determine an appropriate IMPULSE force which would correct the Position of each Body to the "kissing position", which we know is slightly "back in time" , ie , occurs at some moment in the current timestep, then resolve the collision between the bodies conventionally (calculate new forces for the bodies resulting from the impact), and finally, advance the bodies for the remainder of the timestep.
Impulses are forces which are applied immediately.. normally we apply forces to acceleration, and accelerations only alter the position and orientation over time.. impulses can be thought of as accelerations which occur over an infinitely small amount of time, "instantly" changing our position and orientation. This might seem somewhat hacky, and it is.
A more accurate solution is to search for the kissing moment in the current timestep by rewinding our bodies to their initial state, and then subdividing the timestep, and checking for collision, repeating this until we find a penetration depth that is within acceptable tolerance. This scheme can be thought of as a "binary search" of the current timestep. Again, once we find the "kissing point", we can resolve the collision conventionally. It's a lot more expensive, but we can limit the collision check to the bodies involved in THIS collision and its not too bad a tradeoff.

The most common collision we will ever see involves the penetration of a surface by a Point, such as the corner of a cube and a flat floor. As we will see, MANY of our collision tests are based on Point tests.
A flat surface such as a Triangle has a Surface Normal vectir which describes the direction it is facing.
The Surface Normal, along with a fourth value called "PlaneD", when stored as a 4D vector, together describe a PLANE.
Planes are theoretical flat surfaces in 3D which extend to infinity.
The normal vector describes the direction they face, and the PlaneD value describes the shortest possible distance from the World Origin to that unique plane, which just happens to be along that Normal.
Although several triangles may share a single plane (such as the face of a cube made of 2 triangles), every plane is unique , even if it faces the same direction, due to the PlaneD (plane distance) value.
If we wish to test for the intersection of a given Point and Plane, all we need to do is measure the distance between them... negative values indicate that the Point is "behind the plane", while positive values tell us that it is "in front of the plane", and zero would indicate that the point is resting apon the plane.
Since our computer does not have infinite precision and is prone to small numerical errors, we give a little tolerance to give the plane a little "thickness", so we might say if the value is between -.001 and +.001, its resting on the plane, ie, its close enough to zero for me.
A similar logic is used when testing for collision of a Sphere and a Plane, because we can think of a Sphere as being "a Point with some Thickness" where the thickness equals the sphere radius... first we measure the distance from the sphere's origin to the plane, and then we take the sphere's radius into account.
If the distance is more than the radius, the sphere is totally in front of the plane.
If the distance is less than a radius, but not less than -2*radius, we have an intersection.
If the distance is less than -2*radius, the sphere is totally behind the plane.
Testing for collision between two spheres is even easier... we just compare the distance between their origins to the sum of their radii, and determine similarly to the aforementioned sphere/point test.
Using that information, we are now able to perform tests between planes, spheres, and a whole family of "Stuff with flat faces" such as cubes and "arbitrary meshes".
And by extension of this kind of thinking, we can detect for collisions with more difficult geometries such as cylinders and ellipses (egg shapes).

In my next post, we'll look at resolving simple collisions (math ahoy!), followed immediately by a discussion of more complex "multiple, simultaneous" collisions.
Posted on 2008-02-06 22:51:43 by Homer

As an addendum, for the purpose of optimization, using a bounding sphere (a sphere that encloses every vertex in a mesh/object) can be used to cull (avoid useless calculation) the amount of collision detection necessary. If the simpler sphere-to-sphere collision test passes you can move on to the more complex testing and interpolation.

Also, you mentioned ""subdividing the timestep, and checking for collision, repeating this until we find a penetration depth that is within acceptable tolerance."" I've never dealt with the implementation, but I wonder if using the acceleration, velocity and start position vectors and solving for the variable time (when the positions are kissing) would be more efficient (it would certainly be more precise) than subdividing the time-step?

An excellent resource keep at it!
Posted on 2008-02-08 09:54:14 by r22
Nice stuff.  I sadly haven't got time to read most of it, but I'll assume that it's pretty good.  It's at least good that someone's talking about physics stuff, but it looks like it could make use of some SSE.  I've got some electrodynamics using SSE in the screensaver that I'll hopefully be demoing soon.

*sigh* I guess I should get back to work. :sad: I'm way behind, but pretty close now, so it shouldn't be much longer.
Posted on 2008-02-09 23:35:55 by hackulous
I absolutely agree with both of you...

Yes, a hierarchy of collision hulls can be used, and Sphere is certainly the most simply hull, I believe I touched on this already, and certainly mean to cover this in more detail.

Of course SSE would help , where available.
I have deliberately and almost completely avoided the entire concept of optimizing, since this thread is meant to contain the fundamental knowledge required to implement physics on ANY platform.
My example code is meant to remain as readable as possible, not as fast as possible for a specific platform...I could have simply provided formulae and algorithms in pseudocode, but programmers want to see programs, and asmcoders are my audience, so I chose a language which asmcoders might easily understand.

Believe me when I say that I am only putting in text the concepts in my mind, and as such, you are welcome to point out any mistakes that I make.
I am not a physicist, and I am not a mathematician, but I am human, and worse than that, I am mostly self-taught.

Posted on 2008-02-12 00:06:27 by Homer
Just a quick post so you know I am still alive.

We will begin exploring collision detection and resolution via the example of a Mass Particle - a particle that has some mass.
No, I am not going to suggest we make our engine around the concept of mass particles stuck together with stiff springs, like some do, I am going to state:
1) Particles are all linear, theres no rotation stuff

2) For the linear (not angular) side of the question, we can treat the center of mass (COM) of ANY rigid body as a Mass Particle

3) The solution of the angular side of the equation relies on our ability to solve the particle equation for a reference point other than COM.

So I repeat, we will learn how to handle collision detection / resolving for a single point with Mass, then apply what we learned to the geometry of the arbitrary Rigid Body .. we will learn the stuff we need for the linear side of the coin, and then we will learn how to apply that to solve the angular stuff for more complex entities :)
Posted on 2008-02-16 04:07:37 by Homer