# Adding vector from another moving object...

## Recommended Posts

Aw crud, it's me again. [grin] Here's an easy one...
              ------    .
|      |  .
|Moving| .
----->    | Box  |.  <-- Circle collides here
Box's travel |      | .
direction    |      |  o
------
Let's say in the above example that the 'Moving Box' is moving along vector (1, 0) at a speed of 300. Let's also say that the 'Circle' is moving along the vector (-0.707, 0.707) at a speed of 400. If I perform a standard reflection against the Moving Box, the Circle's new vector will be (0.707, 0.707) which would make its X speed roughly 282... The problem with that is the Moving Box will overtake the circle, since it's traveling along the X at 300. I want to keep the Circle's speed at 400... How do I change the vector of the Circle so that it just outruns the Moving Box? Thanks in advance for the help!

##### Share on other sites
Find a vector for the circle whose X component is greater than or equal to the X component of the box's movement vector. (Note that I find it a tad easier to treat the vectors as full velocity vectors rather than unit vectors multiplied by velocity).

So if vx2 + vy2 = v2, vx = 300, and v = 400, solve for vy and get sqrt(70000), or ~265. So the velocity vector for the circle should be <300,-265>, which you can convert to a unit vector if you like.

Hope that helps,
Twilight Dragon

##### Share on other sites
You could try looking for the equations needed to implement a more physically accurate collision.

In this particular case, the velocity of the object the ball is bouncing off of should be considered. If the reflection is done relative to the moving box's frame of reference, it should have the proper effect. The x velocity relative to the box is -0.707 - 1 = -1.707. Reflecting this gives a velocity of 1.707.

The equations for collisions provide a more general solution than this that works for any collision direction and with objects that both have mass. I think when one object has infinite mass, the equations reduce to something like a reflection.

##### Share on other sites
Note to the AP: You're right, but also keep in mind that the OP was using unit vectors for the direction and specifying the velocity separately, so the numbers you gave weren't entirely accurate.

##### Share on other sites
let have two objects A and B, with velocity vector 'va' and mass 'ma', and B with velocity vector 'vb' and mass 'mb'.

Also have the collision normal 'nab', the collision normal of A impacting on B.

also, have a coefficient of restitution 'cor', or how hard the collision will be (very hard collision, cor = 1.0f, very soft, cor = 0.0f).

from the conservation of momentum, you can derive the collision impulse

let vab = (va - vb), or the relative velocity of object A from object B's point of view.

if(vab . nab > 0.0f), the objects are moving away from each other, so return;

the collision impulse will be
j = -(1 + cor) * (vab . nab) / (1/ma + 1/mb);

then

va += (j * nab) / ma;
vb -= (j * nab) / mb;

in short

bool Bounce(Vector va, float ma, Vector vb, float mb, Vector nab, float cor){    Vector vab = (va - vb);    float  vn  = vab.DotProduct(nab);    if (vn > 0.0f) return false;    float j = -((1.0f + cor) * vn) / (1/ma + 1/mb);    va += (j * nab) / ma;    vb -= (j * nab) / mb;    return true;}

##### Share on other sites
Oh oops...well the x velocity of the ball relative to the box is -282.8 - 400 = -682.8, so reflecting that gives a velocity of 682.8. Also it is easier to just use a velocity vector than a direction vector and a speed.

##### Share on other sites
Cool, thanks again!

So if I change the code a bit to work for my own application, it should be as follows:

bool Bounce(float* va, float ma, float* vb, float mb, float* nab, float cor){    float vab[2], vn, j;    vab[0] = (va[0] - vb[0]);    vab[1] = (va[1] - vb[1]);    vn = vab[0]*nab[0] + vab[1]*nab[1];    if (vn > 0.0f) return false;    j = -((1.0f + cor) * vn) / (1/ma + 1/mb);    va[0] += (j * nab[0]) / ma;    va[1] += (j * nab[1]) / ma;    vb[0] -= (j * nab[0]) / mb;    vb[1] -= (j * nab[1]) / mb;    return true;}

I'd send the function the objects' vectors stored in the floats 'va[2]' and 'vb[2], and the collision normal 'nab[2]'. I'd also send it the floats 'ma' (mass of A) and 'mb' (mass of B), as well as the float 'cor' (hardness of collision). Would you proof-read the above and make sure I have it correct? Thanks! [smile]

I'm presuming vectors 'va' and 'vb' are scaled to include the speed of the objects, which means their velocities are going to change after the collision takes place. I'll have to experiment with this to see if I can get it to work with my Breakout-style game, where I want the ball's velocity to remain constant even after colliding with a moving block (only the ball's travel vector should change to avoid being overrun by the block, not its velocity), and I don't want the block's velocity or trajectory to change at all.

Thanks again for the info, oliii! If I can't get this to work with my breakout game, I'll definitely be able to use this for a platform game I have planned in the near future.

##### Share on other sites
that system should work as it is.

To keep the ball speed relatively unchanged, you'll need a high value for cor (0.99), and a high mass for the paddle (100.0), and a low mass (1.0) for the ball, so most of the energy from the collision is transfered from the paddle towards the ball.

I'd also advocate an artificial system to keep the ball velocity constant, like add a little bit of velocity to the ball every frame if it's too low, because there is always some FP innacuracies over time, and making inifnite or 0 mass will cause you problems, and the system, as it is, will still loose energy (mass not infinite, but you can't and should not do that anyway).

Also, be careful with the ball moving too fast, as well as the paddle, and make sure you nudge the ball away from the paddle in case of an intersection (using the MTD), and then apply the collision response like above (using the normalised MTD).

##### Share on other sites
Sorry it took a while to respond, I was trying to get oliii's idea along with my rather finite knowledge of vector math to work together in my game. [wink]

And ya know what? It works Great! Thanks oliii, for helping me to get that collision detection to work in my game! I was using two separate routines (one for right-oriented blocks and one for angled blocks), and that wasn't working well because sometimes a collsion would be prematurely detected for a block that was buried behind another block. Heh, you'd probably cringe if you saw the code for my game.

I only have one question about that collision detection scheme... If the ball is moving along and it clips the corner of a block, sometimes it will detect the collision and then process the 'bounce' routine but the ball's vector won't change.

 ------       .| Block|     .  <== Ball's Trajectory before collision|      |    .|    --|---|   |  |   | ------    |    | Ball |     ------    .   .  <== Ball's Trajectory after collision  .

This only happens very occasionally, and it doesn't seem to matter how fast the ball is travelling or whether or not the block is a moving block. It only seems to happen if the very tip of the corner of the ball quad and the tip of the corner of a block quad collide (very small collision; "glancing blow"), not when there's a 'major' collision (ball smacks into the side of the block). Hard to explain, so I'm hoping you've seen this issue in action. If you have seen this in action, do you know how to make this work every time? Like I said, it happens very rarely but it's distracting when you're playing a fast and furious game and the ball doesn't ricochet like you'd expect.

Thanks again for all the help, I really appreciate it!

##### Share on other sites
I have a theory...

Are you calculating the amount of intersection and multiplying that to the final vector? then maybe the intersection is to low in the above case...?

You could cheat, and do a simple "if collision is detected, and resulting vector is lower than a certain reflective angle, set it to that angle"...
In this type of game, I think most people would think it's ok. :D

##### Share on other sites
it would happen if the ball was clipping the box at a very shallow angle. In that case, the MTD vector might be not pointing down, but pointing to the right, as the amount of intersection on the X axis is actually lower than the amount of intersection in the Y axis. This is one of the major drawback of doing a SAT in static.

To get back to the example, the ball will be moving to the right, and the normal of collision vector will be pointing to the right. Since the ball velocity and the normal of collision are going in the same direction (dot product will be > 0), there will be no bounce.

                +------------+            /              y overlap = 5 pixel wide   /                |  v         |          /                | ........+------------+               |  |      |  |        /|               |  |     >|--|< x overlap = 3 pixel wide               |  |      |  |      /  |               +---------|--+     /   |                  ^      |       /    |                         |      /     |                         |     /      |                         |    /       |                         +---/--------+                            /                            / ////  x = 3//  y = 5//  => x < y, so MTD will point towards the right (x axis)//  => but velocity if going mostly up, so expect a downward collision normal//  => bummer//

If you *do* apply the response, the ball will bounce back towards the wall, and over several frames will appear to be stuck to the wall. Hence why I cut short the response code in that case, and the lack of collision response. YOu can try that by yourself.

several solutions.

1) split the trajectory of the ball into smaller timesteps to find a good MTD, like in your example where it will be aligned with the bottom wall. Although there will be genuine cases where this case will be perfectly valid and will not return any meaningful results.

2) do the SAT test in dynamics. But that's more complicated, and will stretch your vector maths a bit further. I've got several examples and docs around explaining the swept SAT.

3) Some form of hacks.

in any case, your collision detection and physics will have to be upgraded, and work on a swept basis (factor velocities in the collison detection tests, collision loop, where you have to find the first collision, apply response at each step, then find other collisions until the time left in search is exhausted). That would be the next step, but it depends how much time you want to spend on that thing.

##### Share on other sites
Well crud. I think I'm starting to run into the limitations that you're talking about, oliii. Methinks I'm gonna have to try your second suggestion:

Quote:
 2) do the SAT test in dynamics. But that's more complicated, and will stretch your vector maths a bit further. I've got several examples and docs around explaining the swept SAT.

Would you point me in the direction of those examples? Thanks!

##### Share on other sites
here, here, and here.

the first one has a doc explaining the algorithm (done in 3D). It also has a number of demos (press F1 to F7 if I remember corectly. all mouse controls and keys awsd). please, do the effort to read the doc, and dont rip out the code straight away. make sure you get it in your head first.

The second example is the 2D version. It's more what you'd like to achieve. It also has sphere-polygon collision (based on Raigan Burn's tutorial).

The third is an example, with added physics and contact point calculations.

##### Share on other sites
Thanks again for the info, oliii. I just wish I could bang it all into my head and understand it! I don't want to simply rip somebody else's code and tailor it for my game, because I don't learn anything that way. But since I code using generic C, I don't have a whole lot of experience in writing and understanding classes, and that makes it tough to understand some of the sample code. And it's REALLY hard to find websites that contain 'workable' code that goes along with their tutorials. The only useful sites and tuts have been the ones you've sent my way, and I really appreciate it!

Anyhoo, I'll get back to reading and see if I can figure out any of this stuff. Maybe I just need to take it in a little at a time... Wish me luck!

Thanks again!

##### Share on other sites
as I said in the docs, you start off with a ray-box intersection test. If you understand the principle, and since you know the SAT, you're basically 90% of the way there.

##### Share on other sites
OK, I think I'm starting to understand this...

But I'm having a problem understanding 'swept' and time-based collision detections. I'm really starting to understand 'static' collision detections though, so I guess I'm getting somewhere [smile]. Here's a pic of what I'm doing right now:

You can see the game object (ball) is traveling down and to the right. OldLoc[2] is the ball's x/y coordinates at the last frame, and NewLoc[2] is the ball's x/y coordinates on this frame. You can also see how the ball at NewLoc is colliding with the blue object; where it's at will cause an incorrect calculation of MTD when the SAT function is applied and push the ball down rather than the correct direction of left. I've been trying to understand 'swept' and time-based collisions, and this is all I understand:

If I can extrapolate the point where the ball actually comes in contact with the blue object, I can then nudge and bounce it the correct way. However, I can't figure how to get that extrapolated position. And I still don't really understand 'swept' collision detections at all... Can one of you guys point me to a tutorial or explanation on how I can learn how to do this? Since I'm working on a 2D game, if you could point me to a 2D tutorial or explanation then that would be AWESOME!

Thanks in advance for the help!

##### Share on other sites
You highlighted in your above post one of the pitfalls of static tests: even if tunneling is avoided, the results can still be less than satisfactory.

If you're looking for a quick fix, you could subdivide your step into small enough substeps that each would be small relative to the box dimensions. Although this probably wouldn't be a good approach where many objects are involved, in a simple setting I think it would be adequate.

However, as you note, swept tests may be a better answer. I think a good starting place would be this gamasutra article (free membership required) which is linked from the gdnet articles section. Among other things it covers swept AABBs in 3d, which can easily be adapted to 2d by dropping a dimension and would be (I think) exactly what you're looking for.

IMO, swept tests with SAT can be a little hard to get a handle on conceptually (again, IMO). Starting with axis-aligned boxes in 2d is a good way to get comfortable with it before moving to 3d and having to deal with cross-product axes and so on. It also may help to draw some pictures or create some diagrams such as the ones in your post.

If you've got the static SAT test down, you understand that an object can be projected onto an axis to yield an interval with a minimum and maximum value. Now imagine that the object is moving; it stands to reason then that the interval would be moving as well. How much and in what direction depends on the relationship between the object's velocity vector and the axis. For example, for an object moving perpendicular to the axis, the projected interval would be stationary (draw it if you're not sure).

Now imagine the interval associated with your moving box moving along the axis, and also a stationary interval which is the projection of an obstacle you wish to test against. With some algebra you can determine a) when the intervals will first intersect, and b) when they will stop intersecting.

Well, for such a simple test it actually gets a little complicated to explain, so I'll cut to the chase. In order for the objects to intersect over the time step, there must be some time interval during which they are overlapping on all potential separating axes. There are different ways you can keep track of this, but it all boils down to pretty much the same thing. The beginning of the time interval of possible intersection is the greatest of all the first times of intersection collected from the axes. The intuition is that the objects cannot possibly intersect until they have begun to overlap along all potential separating axes. The end of the time interval of possible intersection is the least of all last times of intersection collected from the axes. The intuition is that the objects cannot possibly intersect after they have stopped overlapping along any potential separating axis. If the time interval of possible intersection ends up being negative, i.e. min > max, they didn't intersect. Otherwise, min is the first time of intersection.

Ok, that post was too long. 'Hope some of it will be helpful, though.

##### Share on other sites
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]

##### Share on other sites
OK, moving on :)

first off, I'd like to rw-write some of the logic.

bool PointSlabCollision(float slabmin, float slabmax, float point, float displacement, float& tfirst, float& tlast){    if (fabs(displacement) < 1.0E-8f)    {        return (point > slabmin && point < slabmax);    }    float tslabmin = (slabmin - point) / (displacement);    float tslabmax = (slabmax - point) / (displacement);    float tslabenter;    float tslabexit;    if(tslabmin < tslabmax)    {        tslabenter = tslabmin;        tslabexit  = tslabmax;    }    else    {        tslabenter = tslabmax;        tslabexit  = tslabmin;    }    tfirst = max(tfirst, tslabenter);    tlast  = min(tlast , tslabexit);    if (tfirst < tlast)        return false;    return true;}bool PointBoxCollision(Vector BoxMin, Vector BoxMax, Vector Point, Vector displacement, float& tfirst, float& tlast){    // calculate intervals for both slabs    if (!PointSlabCollision(BoxMin.x, BoxMax.x, Point.x, Displacement.x, tfirst, tlast))         return false;    if (!PointSlabCollision(BoxMin.y, BoxMax.y, Point.y, Displacement.y, tfirst, tlast))        return false;    return true;}bool BoxBoxCollision(Vector Amin, Vector Amax, Vector Bmin, Vector Bmax, Vector BDisplacement, float& tfirst, float& tlast){    tfirst = 0.0f;    tlast  = 1.0f;    Vector Bextent = (Bmax - Bmin) * 0.5f;    Vector Bcentre = (Bmax + Bmin) * 0.5f;    Amin += Bextent;    Amax -= Bextent;       return PointBoxCollision(Amin, Amax, BCentre, BDisplacement, tfirst, tlast);}

OK, now that the logic is sorted, we can think of adding collision normals.

this part really, is traight forward. There is little change to the code required.

bool PointSlabCollision(float slabmin, float slabmax, float point, float displacement, const Vector& SlabNormal, float& tfirst, Vector& Nfirst, float& tlast, Vector& Nlast){	if (fabs(displacement) < 1.0E-8f)	{		return (point > slabmin && point < slabmax);	}	float tslabmin = (slabmin - point) / (displacement);	float tslabmax = (slabmax - point) / (displacement);	float tslabenter;	float tslabexit;	float sign;	if(tslabmin < tslabmax)	{		tslabenter = tslabmin;		tslabexit  = tslabmax;		sign = -1.0f;	}	else	{		tslabenter = tslabmax;		tslabexit  = tslabmin;		sign = 1.0f;	}	if (tslabenter > tfirst)	{		tfirst = tslabenter;		Nfirst = SlabNormal * sign;	}	if (tslabexit < tlast)	{		tlast  = tslabexit;		Nlast  = SlabNormal * -sign;	}	if (tlast < tfirst)		return false;	return true;}bool PointBoxCollision(const Vector& BoxMin, const Vector& BoxMax, const Vector& Point, const Vector& Displacement, float& tfirst, Vector& Nfirst, float& tlast, Vector& Nlast){	// calculate intervals for both slabs	if (!PointSlabCollision(BoxMin.x, BoxMax.x, Point.x, Displacement.x, Vector(1, 0), tfirst, Nfirst, tlast, Nlast)) 		return false;	if (!PointSlabCollision(BoxMin.y, BoxMax.y, Point.y, Displacement.y, Vector(0, 1), tfirst, Nfirst, tlast, Nlast))		return false;	return true;}bool BoxBoxCollision(const Vector& Amin, const Vector& Amax, const Vector& Bmin, const Vector& Bmax, const Vector& Displacement, float& tfirst, Vector& Nfirst, float& tlast, Vector& Nlast){	tfirst = 0.0f;	tlast  = 1.0f;	Nfirst = Vector(0, 0);	Nlast = Vector(0, 0);	Vector Bextent = (Bmax - Bmin) * 0.5f;	Vector Bcentre = (Bmax + Bmin) * 0.5f;	return PointBoxCollision(Amin - Bextent, Amax + Bextent, Bcentre, Displacement, tfirst, Nfirst, tlast, Nlast);}

BoxBoxCollision2.cpp

OK, now I'll get back to the static test, and calculating the MTD vector for two intersecting rectangles.

first of, to detect if two boxes intersect, it is quite straight forward.

bool BoxBoxIntersect(Vector Amin, Vector Amax, Vector Bmin, Vector Bmax){     if (Amin.x > Bmax.x || Bmin.x > Amax.x)         return false;     if (Amin.y > Bmax.y || Bmin.y > Amax.y)         return false;    return true;}

BoxBoxCollision2.cpp

Nothing can be simpler. :)

Now, usually, when we have an intersection, we'd like to make the intersection dissappear, by moving one or both box away from each other. Thus, we need to find which direction and by what amount we need to push the boxes appart.

From the first picture, it is quite obvious that we'd like to move the green the box upwards until the boxes only touch. Moving the box to the left, right or down, would require a much bigger translation, which would most likely be pushing in the wrong direction.

So, we'd like to calculate that MTD vector, or aka the Minimum Translation Distance, or distance of minimum translation to make the box stop intersecting.

Calculating the MTD in case of two boxes is quite simple, and basically falls down to find the minimum amount of overlap between intervals of the boxes, along the X and Y axis.

Again, I will simplify the problem by converting a BoxBox Intersection by a PointBoxIntersection. Following the same logic as the swept test, you shrink a box to a point, while expand the other box by the same amount. Then the problem becomes finding the side of the box the closest to the point.

bool PointSlabsIntersect(float slabmin, float slabmax, float point, const Vector& SlabNormal, Vector& MTD, float& mtdsquared){    	float dist_min = slabmin - point;	float dist_max = slabmax - point;	// point outside the slab	if (dist_min > 0.0f || dist_max < 0.0f)		return false;	// the vector we use to push the point outside the slab	float slabmtd  = (fabs(dist_min) < fabs(dist_max))? dist_min : dist_max;	Vector SlabMTD = SlabNormal * slabmtd;	float slabmtdsquared = SlabMTD * SlabMTD;	// Check if that push vector is smaller than our curent push vector	if (slabmtdsquared < mtdsquared || mtdsquared < 0.0f)	{		MTD = SlabMTD;		mtdsquared = slabmtdsquared;	}	return true;}bool PointBoxIntersect(const Vector& Min, const Vector& Max, const Vector& Point, Vector& MTD){	float mtdsquared = -1.0f;	// Test X axis	if (!PointSlabsIntersect(Min.x, Max.x, Point.x, Vector(1, 0), MTD, mtdsquared))		return false; 	// Test Y axis	if (!PointSlabsIntersect(Min.y, Max.y, Point.y, Vector(0, 1), MTD, mtdsquared))		return false;	return true;}bool BoxBoxIntersect(const Vector& Amin, const Vector& Amax, const Vector& Bmin, const Vector& Bmax, Vector& MTD){	// clear MTD	MTD = Vector(0, 0);		// convert Box-Box problem into point box problem	Vector Bextents = (Bmax - Bmin) * 0.5f;	Vector Bcentre  = (Bmax + Bmin) * 0.5f;	return PointBoxIntersect(Amin - Bextents, Amax + Bextents, Bcentre, MTD);}

BoxBoxMTD.cpp

PointSlabIntersect might feel a bit winded, but it is a necessary evil for later on.

When we work on a slab, we first find if the point is inside the slab or not. If not, the point cannont be inside the box.

If the point is inside the slab, we need to find the minimum distance from the point to the slab planes, and push the point there. This is where SlabMTD comes from, and tells us which slab side is the closest to the point.

Now, we also neem to make sure that that SlabMTD is indeed the smallest vector we can find to push the point outside the box.

Instead of comparing vector length, I simply compare vector length squared.

Ultimately, we will end up with a MTD vector, that we can use to push the virtual point outside the large box, which in turn, can be used to push the two intersecting boxes apart.

I choose to use that representation so now, we can plug it into the swept test as a fallback procedure in case the swept boxes intersecting, or if the boxes are static.

[Edited by - oliii on October 13, 2005 5:02:40 PM]

##### Share on other sites
OK, now to finish it. We can combine both the time-based movement, and the intersection test, in one single algorithm.

bool PointSlabCollision(float slabmin, float slabmax, float point, float displacement, const Vector& SlabNormal, float& tfirst, Vector& Nfirst, float& tlast, Vector& Nlast, Vector& MTD, float& mtdsquared, bool& bCollision){	float dist_min = slabmin - point;	float dist_max = slabmax - point;	// point inside the slab	bool bIntersect = (dist_min < 0.0f && dist_max > 0.0f);	if (bIntersect)	{		// the vector we use to push the point outside the slab		float slabmtd  = (fabs(dist_min) < fabs(dist_max))? dist_min : dist_max;		Vector SlabMTD = SlabNormal * slabmtd;		float slabmtdsquared = SlabMTD * SlabMTD;		// Check if that push vector is smaller than our curent push vector		if (slabmtdsquared < mtdsquared || mtdsquared < 0.0f)		{			MTD = SlabMTD;			mtdsquared = slabmtdsquared;		}	}	// if not moving, can only collide	// through intersections	if (fabs(displacement) < 1.0E-8f)		return bIntersect;			float tslabmin = (slabmin - point) / (displacement);	float tslabmax = (slabmax - point) / (displacement);	float tslabenter;	float tslabexit;	float sign;	if(tslabmin < tslabmax)	{		tslabenter = tslabmin;		tslabexit  = tslabmax;		sign = -1.0f;	}	else	{		tslabenter = tslabmax;		tslabexit  = tslabmin;		sign = 1.0f;	}	if (tslabenter > tfirst)	{		tfirst = tslabenter;		Nfirst = SlabNormal * sign;		bCollision = true;	}	if (tslabexit < tlast)	{		tlast  = tslabexit;		Nlast  = SlabNormal * -sign;	}	if (tlast < tfirst)		return false;	return true;}bool PointBoxCollision(const Vector& BoxMin, const Vector& BoxMax, const Vector& Point, const Vector& Displacement, float& tfirst, Vector& Nfirst, float& tlast, Vector& Nlast, Vector& MTD, float& mtdsquared, bool& bCollision){	// calculate intervals for both slabs	if (!PointSlabCollision(BoxMin.x, BoxMax.x, Point.x, Displacement.x, Vector(1, 0), tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision)) 		return false;	if (!PointSlabCollision(BoxMin.y, BoxMax.y, Point.y, Displacement.y, Vector(0, 1), tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision))		return false;	return true;}bool BoxBoxCollision(const Vector& Amin, const Vector& Amax, const Vector& Bmin, const Vector& Bmax, const Vector& Displacement, float& tfirst, Vector& Nfirst, Vector& MTD){	const float tolerance = 1.0E-8f;	bool bCollision = false;	float mtdsquared = -1.0f;	MTD = Vector(0, 0);	tfirst = 0.0f - tolerance;	Nfirst = Vector(0, 0);		float tlast  = 1.0f + tolerance;	Vector Nlast = Vector(0, 0);	Vector Bextent = (Bmax - Bmin) * 0.5f;	Vector Bcentre = (Bmax + Bmin) * 0.5f;	bool bCollisionOrIntersection = (PointBoxCollision(Amin - Bextent, Amax + Bextent, Bcentre, Displacement, tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared));	if(!bCollisionOrIntersection)	{		return false;	}	if (bCollision)	{		// check if we found a valid time of collision		if(tfirst < 0.0f || tfirst > 1.0f)			return false;		MTD = Vector(0, 0);	}	else	{		tfirst = 0.0f;		Nfirst = MTD;		Nfirst.Normalise();	}	return true;}

BoxBoxCollisionAndMTD.cpp

This combines both the static and time-based test in one function. There is nothing really particular about it, except for what decides if we have a collision, or an intersection. Quite simply, if the first time of collision is <= 0 (well, tfirst *will* be 0), then we are already intersecting, and the result reverts to returning the MTD. The collision normal is also set to be the MTD direction, as this will be the case in 99.99% of the times.

This algorithm can easily be extended to 3D boxes, but also 2D oriented boxes, 2D polygons, 3D polygons, 3D triangles, triangles against boxes, convex hulls, ... All you need is use the same basic underlying principles of the SAT, and apply the time-based modifications.

[Edited by - oliii on November 14, 2005 2:35:54 AM]

##### Share on other sites
Woof, looks like I'm gonna need a couple of Advil before I try to draw this out on paper... [grin]

Thanks a bazillion for the explanation, oliii, I don't think there would be any way I'd begin to understand this if it weren't for you. You ROCK! I'll read up on what you've posted and see if I can figure why this works, and then I can better apply this new knowledge to my future games. I may pick your brain a little later on getting this to work with "line-rotated box" collisions, but I'd better try to learn how to do it with simple boxes first. Time to start reading... Wish me luck!

Thanks again, I REALLY appreciate it!

##### Share on other sites
it's not just for you, you know :) I intend to get that thread stickified (maybe slightly modified), so it's done once and for all. Any comments appreciated, then I can edit my posts as you try to decipher the algo, add a couple of pics...

##### Share on other sites
Now onto oriented boxes.

If you've been reading stuff on the SAT, you would know that the algorithms basically gets decomposed into a number of 1D interval intersection tests, where each object get 'projected' on a given axis.

The axes of projection, for 2D polygons, are basically the vectors perpendicular to edges. For an oriented box, since the 4 edges are either perpendicular or parallel, the number of axes per boxes is only 2. For 2 oriented boxes, we will have to test 4 separation axes in all.

so now, we need a way to find the projection interval of a box along an arbotrary axis, for example, the projection interval of box A when projected on one axis of box B.

for boxes, it is

void CalculateBoxIntervalOnAxis(const Vector& Axis, const Vector& Pos, const Vector& Ext, const Vector* Dir, float& min, float& max){	// projected centre on axis	float p = Pos * Axis;	// projected box extents on axis	float r = fabs(Dir[0] * Axis) * Ext.x + fabs(Dir[1] * Axis) * Ext.y;	// min and max of the box	min = p - r;	max = p + r;}

Now that we have both min and max for both boxes along an arbitrary axis, we can pass it to the PointSlabCollision() function. Here, I do away with the concept of point-box representation, and use the two boxes' intervals directly. It just a juggling of scalar values anyway.

//===========================================================================//// COLLISION CODE////===========================================================================void CalculateBoxIntervalOnAxis(const Vector& Axis, const Vector& Pos, const Vector& Ext, const Vector* Dir, float& min, float& max){	float p = Pos * Axis;	float r = fabs(Dir[0] * Axis) * Ext.x + fabs(Dir[1] * Axis) * Ext.y;	min = p - r;	max = p + r;}	bool PointSlabCollision(float slabamin, float slabamax, float slabbmin, float slabbmax, float displacement, const Vector& SlabNormal, float& tfirst, Vector& Nfirst, float& tlast, Vector& Nlast, Vector& MTD, float& mtdsquared, bool& bCollision){	float dist_0 = slabamin - slabbmax;	float dist_1 = slabamax - slabbmin;	// point inside the slab	bool bIntersect = (dist_0 < 0.0f && dist_1 > 0.0f);	if (bIntersect)	{		// the vector we use to push the point outside the slab		float slabmtd  = (fabs(dist_0) < fabs(dist_1))? dist_0 : dist_1;		Vector SlabMTD = SlabNormal * slabmtd;		float slabmtdsquared = SlabMTD * SlabMTD;		// Check if that push vector is smaller than our curent push vector		if (slabmtdsquared < mtdsquared || mtdsquared < 0.0f)		{			MTD = SlabMTD;			mtdsquared = slabmtdsquared;		}	}	// if not moving, then we can only 	// collide through intersections	if (fabs(displacement) < 1.0E-8f)		return bIntersect;		float tslab0 = (dist_0) / (displacement);	float tslab1 = (dist_1) / (displacement);	float tslabenter;	float tslabexit;	float sign;	if(tslab0 < tslab1)	{		tslabenter = tslab0;		tslabexit  = tslab1;		sign = -1.0f;	}	else	{		tslabenter = tslab1;		tslabexit  = tslab0;		sign = 1.0f;	}	if (tslabenter > tfirst)	{		tfirst = tslabenter;		Nfirst = SlabNormal * sign;		bCollision = true;	}	if (tslabexit < tlast)	{		tlast  = tslabexit;		Nlast  = SlabNormal * -sign;	}	if (tlast < tfirst)		return false;	return true;}bool IntervalColllision(const Vector& Apos, const Vector& Aext, const Vector* Adir, 						const Vector& Bpos, const Vector& Bext, const Vector* Bdir, 						const Vector& Axis, const Vector& Displacement,						float& tfirst, Vector& Nfirst, float& tlast, Vector& Nlast, Vector& MTD, float& mtdsquared, bool& bCollision){	float amin, amax;	float bmin, bmax;	CalculateBoxIntervalOnAxis(Axis, Apos, Aext, Adir, amin, amax);	CalculateBoxIntervalOnAxis(Axis, Bpos, Bext, Bdir, bmin, bmax);	float disp  = Displacement * Axis;		return PointSlabCollision(	amin, amax, 								bmin, bmax, disp, 								Axis, 								tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision);}bool BoxBoxCollision(const Vector& Apos, const Vector& Aext, const Vector* Adir, 					 const Vector& Bpos, const Vector& Bext, const Vector* Bdir, 					 const Vector& Displacement, 					 float& tfirst, Vector& Nfirst, Vector& MTD){	const float tolerance = 1.0E-8f;	bool bCollision = false;	float mtdsquared = -1.0f;	MTD = Vector(0, 0);	tfirst = 0.0f - tolerance;	Nfirst = Vector(0, 0);		float tlast  = 1.0f + tolerance;	Vector Nlast = Vector(0, 0);	if (!IntervalColllision(Apos, Aext, Adir, 							Bpos, Bext, Bdir, 							Adir[0], Displacement, 							tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision))	{		return false;	}	if (!IntervalColllision(Apos, Aext, Adir, 							Bpos, Bext, Bdir, 							Adir[1], Displacement, 							tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision))	{		return false;	}	if (!IntervalColllision(Apos, Aext, Adir, 							Bpos, Bext, Bdir, 							Bdir[0], Displacement, 							tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision))	{		return false;	}	if (!IntervalColllision(Apos, Aext, Adir, 							Bpos, Bext, Bdir, 							Bdir[1], Displacement, 							tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision))	{		return false;	}		if (bCollision)	{		// check if we found a valid time of collision		if(tfirst < 0.0f || tfirst > 1.0f)			return false;		MTD = Vector(0, 0);	}	else	{		tfirst = 0.0f;		Nfirst = MTD;		Nfirst.Normalise();	}	return true;}

OrientatedBoxesCollision.cpp

As a side note, AABBoxes have another added property, where the boxes also share the same axes of projections, that reduces the tests between two boxes to only 2 (along the X and Y axis).

From the code I presented, you can see that PointSlabCollision() is effectively testing two interval along any arbitrary axis.

This can be used for arbitrary convex polygons as well. Like axis-aligned boxes and oriented boxes, convex polygons are also the result of the intersection of slabs.

from there, it's quite easy to see what to do next. Form the picture, you can see that slabs are basically following edges of the polygons. so in general, there are as many slabs to test as there are edges for each polygons (disregarding parallel edges, like in the first picture). Second, each slab will be parallel to edges, so the intervals we need will have to be projected on the perpendicular axis of the slab, that is, the vector perpendicular to the edge corresponding to the slab.

so the main loop function will simply be

bool PolygonPolygonCollision(const Vector* Averts, int Anumverts, 							 const Vector* Bverts, int Bnumverts, 							 const Vector& Displacement, 							 float& tfirst, Vector& Nfirst, Vector& MTD){	const float tolerance = 1.0E-8f;	bool bCollision = false;	float mtdsquared = -1.0f;	MTD = Vector(0, 0);	tfirst = 0.0f - tolerance;	Nfirst = Vector(0, 0);		float tlast  = 1.0f + tolerance;	Vector Nlast = Vector(0, 0);	int j = Anumverts-1;	for(int i = 0; i < Anumverts; j = i, i ++)	{		Vector Edge = Averts[i] - Averts[j];		Vector Axis(-Edge.y, Edge.x); // direction perpendicular to edge		if (!IntervalColllision(Averts, Anumverts,								Bverts, Bnumverts,								Axis, Displacement, 								tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision))		{			return false;		}	}	j = Bnumverts-1;	for(int i = 0; i < Bnumverts; j = i, i ++)	{		Vector Edge = Bverts[i] - Bverts[j];		Vector Axis(-Edge.y, Edge.x); // direction perpendicular to edge		if (!IntervalColllision(Averts, Anumverts,								Bverts, Bnumverts,								Axis, Displacement, 								tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision))		{			return false;		}	}	if (bCollision)	{		// check if we found a valid time of collision		if(tfirst < 0.0f || tfirst > 1.0f)			return false;		MTD = Vector(0, 0);	}	else	{		tfirst = 0.0f;		Nfirst = MTD;		Nfirst.Normalise();	}	return true;}

And now, what we need is a way for calculating the interval for a polygon. A simple min-max expansion should do.

void CalculatePolygonIntervalOnAxis(const Vector& Axis, const Vector* Vertices, int inumverts, float& min, float& max){	min = max = Vertices[0] * Axis;	for(int i = 1; i < inumverts; i ++)	{		float p = Vertices[i] * Axis;		if (p < min) min = p;		else if (p > max) max = p;	}}

One last thing peculiar to using non-normalised arbitrary axes.

First of all, in case of collision, becasue all interval calculations, and various dot products, everything is scaled by the axis length. This is fine, as in the end, when you calculate the time of collision, you dived quantites which are both scaled by axis length. In essence, it cancels out, and all is good.

In case of an intersection, you have to factor in the axis length in the equations, to get a proper MTD vector. When calculating the mtd, quantities are in fact scaled but the SQUARED length of the axis. Which is grand, since all we have to do is divide the quantities by the square length, which is easy and inexpensive to calculate.

	float dist_0 = slabamin - slabbmax; // value scaled by axis length	float dist_1 = slabamax - slabbmin; // value scaled by axis length		// point inside the slab	bool bIntersect = (dist_0 < 0.0f && dist_1 > 0.0f);	if (bIntersect)	{		// the vector we use to push the point outside the slab		float slabmtd			= (fabs(dist_0) < fabs(dist_1))? dist_0 : dist_1;		float slabnormalsquared = SlabNormal * SlabNormal; // Slab Normal isn't garanteed to be normalised		Vector SlabMTD			= SlabNormal * (slabmtd / slabnormalsquared);		float slabmtdsquared	= SlabMTD * SlabMTD;		// Check if that push vector is smaller than our curent push vector		if (slabmtdsquared < mtdsquared || mtdsquared < 0.0f)		{			MTD = SlabMTD;			mtdsquared = slabmtdsquared;		}	}

ConvexPolygonCollision.cpp

[Edited by - oliii on November 14, 2005 2:22:45 AM]

##### Share on other sites
for 3D, there is only a little more work to do. I've you've experimented with the SAT in 3D, you'll know that the separation axes are made of the surface normals, and the cross product of edges between surfaces on both objects.

and example. Take two triangles (A0, A1, A2) and (B0, B1, B2). Each are made of one surface, and three edges. the separation axes to test will be

(A2 - A1) x (A1 - A0) // triangle normal
(B2 - B1) x (B1 - B0) // triangle normal

(A1 - A0) x (B1 - B0) // first of of A cross first edge of B
(A1 - A0) x (B2 - B1) // first of of A cross second edge of B
(A1 - A0) x (B0 - B2) // first of of A cross third edge of B

(A2 - A1) x (B1 - B0) // second of of A cross first edge of B
(A2 - A1) x (B2 - B1) // second of of A cross second edge of B
(A2 - A1) x (B0 - B2) // second of of A cross third edge of B

(A0 - A2) x (B1 - B0) // second of of A cross first edge of B
(A0 - A2) x (B2 - B1) // second of of A cross second edge of B
(A0 - A2) x (B0 - B2) // second of of A cross third edge of B

You also need to implement the inteerval calculation function. Again, we can use the same min-max calculations as for 2D.

void CalculateIntervalOnAxis(const Vector& Axis, const Vector* Vertices, int inumverts, float& min, float& max){	min = max = Vertices[0] * Axis;	for(int i = 1; i < inumverts; i ++)	{		float p = Vertices[i] * Axis;		if (p < min) min = p;		else if (p > max) max = p;	}}

all in all, you get
bool 3DPolygonPolygonCollision(	const Vector* Averts, int Anumverts, 								const Vector* Bverts, int Bnumverts, 								const Vector& Displacement, 								float& tfirst, Vector& Nfirst, Vector& MTD){	const float tolerance = 1.0E-8f;	bool bCollision = false;	float mtdsquared = -1.0f;	MTD = Vector(0, 0, 0);	tfirst = 0.0f - tolerance;	Nfirst = Vector(0, 0, 0);		float tlast  = 1.0f + tolerance;	Vector Nlast = Vector(0, 0, 0);	Vector Axis;		Axis = (Averts[2] - Averts[1]) ^ (Averts[1] - Averts[0]); // Polygon A normal	if (!IntervalColllision(Averts, Anumverts,							Bverts, Bnumverts,							Axis, Displacement, 							tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision))	{		return false;	}	Axis = (Bverts[2] - Bverts[1]) ^ (Bverts[1] - Bverts[0]); // Polygon B normal	if (!IntervalColllision(Averts, Anumverts,							Bverts, Bnumverts,							Axis, Displacement, 							tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision))	{		return false;	}	int j = Anumverts-1;	for(int i = 0; i < Anumverts; j = i, i ++)	{		Vector EdgeA = Averts[i] - Averts[j];			k = Bnumverts-1;		for(int l = 0; l < Bnumverts; k = l, l ++)		{			Vector EdgeB = Bverts[l] - Bverts[k];			Axis = EdgeA ^ EdgeB; // cross product of edges			// degenerate axis. 			if (Axis * Axis < 1.0E-4f)				continue;			if (!IntervalColllision(Averts, Anumverts,									Bverts, Bnumverts,									Axis, Displacement, 									tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision))			{				return false;			}		}	}	if (bCollision)	{		// check if we found a valid time of collision		if(tfirst < 0.0f || tfirst > 1.0f)			return false;		MTD = Vector(0, 0);	}	else	{		tfirst = 0.0f;		Nfirst = MTD;		Nfirst.Normalise();	}	return true;}

One thing you have to watch out though, for 2 coplanar polygons. In that case, you should revert back to the 2D type of algorithm (where you use vectors perpendicular to the edges, and also to the polygon plane now). The algo above will most likely fail.

bool 3DCoplanarPolygonPolygonCollision(  const Vector* Averts, int Anumverts, 										 const Vector* Bverts, int Bnumverts, 										 const Vector& Displacement, 										 float& tfirst, Vector& Nfirst, Vector& MTD){	const float tolerance = 1.0E-8f;	bool bCollision = false;	float mtdsquared = -1.0f;	MTD = Vector(0, 0, 0);	tfirst = 0.0f - tolerance;	Nfirst = Vector(0, 0, 0);		float tlast  = 1.0f + tolerance;	Vector Nlast = Vector(0, 0, 0);	Vector PolyNormal = (Averts[2] - Averts[1]) ^ (Averts[1] - Averts[0]);		if (!IntervalColllision(Averts, Anumverts,							Bverts, Bnumverts,							PolyNormal, Displacement, 							tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision))	{		return false;	}	int j = Anumverts-1;	for(int i = 0; i < Anumverts; j = i, i ++)	{		Vector Edge = Averts[i] - Averts[j];		Vector Axis =Edge ^ PolyNormal; 		if (!IntervalColllision(Averts, Anumverts,								Bverts, Bnumverts,								Axis, Displacement, 								tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision))		{			return false;		}	}	j = Bnumverts-1;	for(int i = 0; i < Bnumverts; j = i, i ++)	{		Vector Edge = Bverts[i] - Bverts[j];		Vector Axis =Edge ^ PolyNormal; 		if (!IntervalColllision(Averts, Anumverts,								Bverts, Bnumverts,								Axis, Displacement, 								tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision))		{			return false;		}	}		if (bCollision)	{		// check if we found a valid time of collision		if(tfirst < 0.0f || tfirst > 1.0f)			return false;		MTD = Vector(0, 0);	}	else	{		tfirst = 0.0f;		Nfirst = MTD;		Nfirst.Normalise();	}	return true;}

all the other functions do not have to be modified. Except that you are using 3D vectors, of course :)

for oriented boxes, the algorithm is similar to 2D boxes. you have now 15 axes.

Bdir[0]
Bdir[1]
Bdir[2]

and the interval function is now

void CalculateBoxIntervalOnAxis(const Vector& Axis, const Vector& Pos, const Vector& Ext, const Vector* Dir, float& min, float& max){	float p = Pos * Axis;	float r = fabs(Dir[0] * Axis) * Ext.x + fabs(Dir[1] * Axis) * Ext.y + fabs(Dir[2] * Axis) * Ext.z;	min = p - r;	max = p + r;}

so there. That should cover everything for 2D and 3D polygonal collisions.

3DBoxPolygonCollision.cpp
DXInputs.cpp
DXInputs.h

[Edited by - oliii on November 14, 2005 2:32:56 AM]

##### Share on other sites
that is one of the most heroic posts i have ever seen....

for another quick reference and explaination of linear interpolation, i found this site helpful:
http://gpwiki.org/index.php/Linear_Interpolation

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628312
• Total Posts
2981999

• 9
• 9
• 13
• 11
• 13