Dookie, you've got it spot on there :)
ok, now, for the extrapolated (really, it's interpolated, but anyway) position. Since you know vectors, I'll start off with a basic collision test, a segment against a plane. Sorry, but you have to start there to understand time-based system. [grin]
have segment [OldLoc, NewLoc].
have a plane [O, N], where O (Origin) is an arbitrary point on a plane.
In your example, let the plane be with normal N(-1, 0), and with Origin being the top-left corner of the blue box (point (xmin, ymax) of the box).
A P point is on the plane [O, N] if it satisfies the equation
(P - O) . N = 0
P is on segment [OldPos, NewPos] if it satisfied the equation
P = OldPos + t * (NewPos - OldPos), and 0 <= t <= 1.
so, if the segment intersects the plane at point P, P will satisfy both equations.
combined the equaitons, and you have
((OldPos - O) + t * (NewPos - OldPos)) . N = 0
therefore, t = [(O - OldPos) . N] / [(NewPos - OldPos) . N]
now that you have a value for t, if t < 0, the segment is therefore 'behind' the plane. if t > 1, the segment is 'in front' of the plane. if 0 <= t <= 1, the segment crosses the plane, and the point P = OldPos + t * (NewPos - OldPos).
bingo, you have segment / plane intersection, with an arbitrary plane.
in this example, the normal is N(-1, 0), and Origin O is (xmin, ymax).
decompose the equation to find t with the dot products, and you get...
t = [OldPos.x - xmin] / [OldPos.x - NewPos.x].
Now, a box is basically an intersection of two slabs (in 2D).
So, you process the intersection for each slab. You will have an enter and exit point (both at time tenter, and texit) where the segments crosses the planes. Of course tenter is always < texit.
for example, consider the [xmin, xmax] slabs.
as explained above,
txmin = [OldPos.x - xmin] / [OldPos.x - NewPos.x]
txmax = [xmax - OldPos.x] / [NewPos.x - OldPos.x]
ok, re-arrange txmin, so it looks nice
txmin = [xmin - OldPos.x] / [NewPos.x - OldPos.x]
txmax = [xmax - OldPos.x] / [NewPos.x - OldPos.x]
here, txmin < txmax, so we have txenter = txmin, txexit = txmax
you do the same for the Y-slab
tymin = [ymin - OldPos.y] / [NewPos.y - OldPos.y]
tymax = [ymax - OldPos.y] / [NewPos.y - OldPos.y]
here however, tymax will be < tymin. so we have tyenter = tymax, tyexit = tymin.
ok, so now, how to tell of the segment intersected the box? It's quite simple. The segment will intersect the box if the intervals [txenter, tyexit] and [tyenter, tyexit] overlap.
rings a bell? It loosely connected to the SAT. It's again a matter of 1D interval intersections. Here is a picture worth 100 words.
first picture, you can see that intervals [txenter, txexit] and [tyenter, tyexit] do not overlap (txexit < tyenter). The segment misses the box entirely.
second picture, the intervals overlap. the segment does indeed intersects the box. and you can see that it will intersect the box at point t = txenter, and exit the box at point t = txexit.
OK, .. so now, we have a basic algo to find if a segment intersects a box or not.
in code, it's quite simple. What we are interested in, is the time of entering the box, and also, exiting (why not, hey :)). lets call then tfirst, tlast.
There is also another interval to consider, the segment range itself, [0.0f, 1.0f]. the segment will intersect the box if obviously the found interval [tfirst, tlast] intersects the interval [0.0f, 1.0f].
I've also added a safety checks, in case the segment is parallel to an axis. If that's the case, you make sure the segment is inside the slab it is parallel with.
bool SegmentSlabIntersect(float slabmin, float slabmax, float oldpos, float newpos, float& tenter, float& texit){ float displacement = (newpos - oldpos); if (fabs(displacement) < 1.0E-8f) { return (oldpos >= slabmin && oldpos <= slabmax); } float tslabmin = (slabmin - oldpos) / (newpos - oldpos); float tslabmax = (slabmax - oldpos) / (newpos - oldpos); if(tslabmin < tslabmax) { tenter = tslabmin; texit = tslabmax; } else { tenter = tslabmax; texit = tslabmin; } return true;}bool SegmentBoxIntersect(Vector BoxMin, Vector BoxMax, Vector OldPos, Vector NewPos, float& tfirst, float& tlast){ // calculate intervals for both slabs float txenter, txexit; float tyenter, tyexit; if (!SegmentSlabIntersect(BoxMin.x, BoxMax.x, OldPos.x, NewPos.x, txenter, txexit)) return false; if (!SegmentSlabIntersect(BoxMin.y, BoxMax.y, OldPos.y, NewPos.y, tyenter, tyexit)) return false; // slab intervals dont overlap if (txenter > tyexit || tyenter > txexit) return false; // get the intersection between the intervals tfirst = max(txenter, tyenter); tlast = min(txexit, tyexit); // now check it's within the segment if (tfirst > 1.0f || tlast < 0.0f) return false; tfirst = max(tfirst, 0.0f); tlast = min(tlast , 1.0f); return true;}
so there you go, you know when a segment intersects a box.
Now, how does that translates to a box-box collision.
well, you can imagine the segment as a travelling point, and the times of intersections as the times the point hits box and exits, like a bullet. Easy enough.
Now, you can also consider the point as a box of size 0, and the first example of a point hitting a plane.
if you inflate the point to a box of extents (1, 1) (from the centre point, the sides will be at distance 1), and at the same time, push the plane back by the same amount, the time the small box will hit pushed-plane will be the same as the time when the point hit plane. Because effectively, the distance box-pushedplane, and the distance point-plane remain the same.
Now, thinking the other way around, by shrinking a box to a point, and expanding the other box by the same amount, we end up doing a segment-large box intersection test.
it is *that* simple.
in code again. There is a slight change in terminology, using 'dispalcement', instead of 'oldpos-newpos', which I think you'll understand. And I use 'collision' instead of 'intersection' since it's a bit more representative.
bool PointSlabCollision(float slabmin, float slabmax, float point, float displacement, float& tenter, float& texit){ if (fabs(displacement) < 1.0E-8f) { return (point > slabmin && point < slabmax); } float tslabmin = (slabmin - point) / (displacement); float tslabmax = (slabmax - point) / (displacement); if(tslabmin < tslabmax) { tenter = tslabmin; texit = tslabmax; } else { tenter = tslabmax; texit = tslabmin; } return true;}bool PointBoxCollision(Vector BoxMin, Vector BoxMax, Vector Point, Vector Displacement, float& tfirst, float& tlast){ // calculate intervals for both slabs float txenter, txexit; float tyenter, tyexit; if (!PointSlabCollision(BoxMin.x, BoxMax.x, Point.x, Displacement.x, txenter, txexit)) return false; if (!PointSlabCollision(BoxMin.y, BoxMax.y, Point.y, Displacement.y, tyenter, tyexit)) return false; // slab intervals dont overlap if (txenter > tyexit || tyenter > txexit) return false; // get the intersection between the intervals tfirst = max(txenter, tyenter); tlast = min(txexit, tyexit); // now check it's within the segment if (tfirst > 1.0f || tlast < 0.0f) return false; tfirst = max(tfirst, 0.0f); tlast = min(tlast , 1.0f); return true;}bool BoxBoxCollision(Vector Amin, Vector Amax, Vector Bmin, Vector Bmax, Vector BDisplacement, float& tfirst, float& tlast){ Vector Bextent = (Bmax - Bmin) * 0.5f; Vector Bcentre = (Bmax + Bmin) * 0.5f; Amin += Bextent; Amax -= Bextent; return PointBoxCollision(Amin, Amax, BCentre, BDisplacement, tfirst, tlast);}
So there you go. If the boxes originally intersect, BCentre will be inside [Amin, Amax], and then tfirst will become 0.0f.
If that happens, you can fall back to a static collision test.
Also, I haven't discussed the problems of normals at times of collision. But I'll discuss that later, once you've digested all that.
NOTE : The gfx are from Word6, you need a non-black background to see the text annotations (it's written in black with transparent background :/).
[Edited by - oliii on November 14, 2005 2:52:31 AM]
