Ok, lets visit the update loop for the physics engine I describe in my angry birds tutorials:


public function Update(dt:Number):void
{
//
// add gravity and generate motion bounds
//

for ( var i:int=1; i<m_rigidBodies.m_Num; i++ )
{
var p:RigidBody = m_rigidBodies.Get(i);

// apply gravity
p.m_vel.MulAddScalarTo( kGravity, dt );

// generate new motion bounds for collision
p.GenerateMotionBounds( dt );
}

//
// collision detection
//

for ( i=1; i<m_rigidBodies.m_Num-1; i++ )
{
var rbi:RigidBody=m_rigidBodies.Get(i);

for ( var j:int=i+1; j<m_rigidBodies.m_Num; j++ )
{
var rbj:RigidBody=m_rigidBodies.Get(j);

//
// simple broad-phase
//

var overlap:Boolean = AABB.Overlap( rbi.m_MotionBounds, rbj.m_MotionBounds );

if ( overlap )
{
//
// narrow phase
//

...
}
}
}

//
// solve all constraints
//

if (m_contactPool.m_Num > 0 || m_joints.m_Num > 0)
{
Solver.Solve(m_contactPool, m_joints, dt, Constants.kNumIterations);
}

//
// integrate forward in time
//

for ( i=1; i<m_rigidBodies.m_Num; i++ )
{
p=m_rigidBodies.Get(i);

p.Integrate( dt );
}
}


I have simplified this down to make it more readable. This is only the physics part, so you'd do your rendering afterwards.

Note the call to GenerateMotionBounds() in the first loop where I'm applying gravity. Looking at the code I am actually transforming all the points to generate the AABB for the predicted next frame and then combining the current frame's AABB with next frames to generate the motion bounds. However, you might just be able to get away with transforming the AABB verts and then generating a new AABB from that and the current frame. It wasn't a performance concern for me, so I never attempted that.

As you can see, the broad-phase is just AABB vs AABB intersection, which is very simple.

If you have a lot of objects, you absolutely need something more intelligent than a simple nested for loop - I've used Sort & Sweep in the past and hash-grid. Hash-grid is great if your objects are similar sizes. AABB trees are the latest kid on the block in that regard, although I've never used them. The goal is to only consider objects which have moved - objects which are stationary should do little to no work.

[color="#1c2837"]for object A to have passed through object B, object A must move to opposite sides of object B on all three world-coordinate axes (X, Y, Z)

[color="#1c2837"]Is that true? What about if object A is moving in only one axis?
[color="#1c2837"]I'm not a big fan of complex maths either - luckily collision detection is all geometry which I can get my head around quite nicely

[color="#1c2837"]Cheers, Paul.
[/quote]
[font="Book Antiqua"]I don't see any significant difference, so I guess all we're talking about is the original topic... namely how to find the time [and position] of first contact (or as it seems to be called, "TOI").

Yes, my engine needs to support lots and lots of objects, because it is designed to support a wide variety of applications, including very sophisticated and compute-intensive ones. My vertex transformation routines automatically create AABB for every object with only 6 assembly-language instructions (and only 3 instructions once 64-bit mode is working), so comparing AABBs is indeed extremely efficient.

My current "broad-phase" collision detection is a modified (optimized) "sweep and pune". At least, I think that's what they call it. Each frame it sorts the "beginning" and "end" markers for each object (in world-coordinates). My tests indicated that the usual way of doing this (sorting on all 3 axes) is a waste of time. Instead, I sort on the most efficient axis (almost always the x-axis), then perform two simple comparisons on the y-axis and z-axis to determine "object-pair overlap"... or not. This is much faster because no processing time is consumed on the other two axes for the vast majority of objects because they do not overlap on the sort axis. I then follow up with a blazing fast implemenation of GJK on the list of potentially colliding object pairs.

Unlike other engines, I also have an "ANY" collision detection routine that performs exactly correct collision-detection on arbitrarily irregular "concave" objects. But that routine is 2x to 20x (or more) slower than GJK, so it is only executed when GJK says the convex hulls are in collision AND the object is not convex (or not known to be convex). I'm working on speeding this more general collision detection routine up, but my GJK is so damn fast (thanks to shane), that I'm sure the concave routine will never be as fast.

As you mentioned, my engine doesn't bother to test object-pairs when neither has been modified since the previous frame (moved/rotated/etc).

Yes, the test I mention to avoid "bullet through paper" works fine. Actually, it is pretty much equivalent to an AABB test. Think about it this way.

if ((objectA.maxx < objectB.minx) || (objectB.maxx < objectA.minx)) for both last frame and this frame, there was no collision or "bullet through paper".

if ((objectA.maxy < objectB.miny) || (objectB.maxy < objectA.miny)) for both last frame and this frame, there was no collision or "bullet through paper".

if ((objectA.maxz < objectB.minz) || (objectB.maxz < objectA.minz)) for both last frame and this frame, there was no collision or "bullet through paper".

That should be pretty obvious. If an object is always "above", "below", "leftward", "rightward", "nearer" or "further" than another, it cannot collide.

The way I stated it is equivalent. For any "bullet" to pass through any "paper", it must pass from "above to below" AND "leftward to rightward" AND "nearer to further". Otherwise it is always on one side or other of the other object.

Unfortunately, you omitted half the original sentence, which might be confusing you. It said that overlapping on any axis constitutes "passing through" from "above to below" or "leftward to rightward" or "nearer to further". In other words, the tests are not > or <, then are >= or <=.

Therefore, to take your case, objectA stays at 0,0,0 on both frames, and objectB moves from -1,0,0 to +1,0,0 (moves only on one axis). That is counted as a possible collision because the objects overlapped in y and z (on both frames, in fact, though overlap on only one frame is sufficient). I hope that clears that up. And if you look, it is indeed equivalent to testing AABBs (even in the number of operations to perform, it appears).

I still need to look harder at that rotating minkowski sum technique, and wrap my brain around it somehow... hopefully. Either that, or hire you to code this part of my engine! :-) As if I could afford to.[/font]