•      Sign In
• Create Account

# Adding vector from another moving object...

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

39 replies to this topic

### #1Dookie  Members   -  Reputation: 290

Like
0Likes
Like

Posted 22 September 2005 - 02:06 AM

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!

Sponsor:

### #2TDragon  Members   -  Reputation: 679

Like
0Likes
Like

Posted 22 September 2005 - 02:20 AM

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

### #3 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

0Likes

Posted 22 September 2005 - 02:31 AM

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.

### #4TDragon  Members   -  Reputation: 679

Like
0Likes
Like

Posted 22 September 2005 - 02:36 AM

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.

### #5papalazaru  Crossbones+   -  Reputation: 1854

Like
0Likes
Like

Posted 22 September 2005 - 03:05 AM

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;}

### #6 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

0Likes

Posted 22 September 2005 - 03:22 AM

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.

### #7Dookie  Members   -  Reputation: 290

Like
0Likes
Like

Posted 22 September 2005 - 05:26 AM

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.

### #8papalazaru  Crossbones+   -  Reputation: 1854

Like
0Likes
Like

Posted 22 September 2005 - 05:37 AM

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).

### #9Dookie  Members   -  Reputation: 290

Like
0Likes
Like

Posted 26 September 2005 - 02:23 AM

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!

### #10Rasmadrak  Members   -  Reputation: 196

Like
0Likes
Like

Posted 26 September 2005 - 02:51 AM

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

### #11papalazaru  Crossbones+   -  Reputation: 1854

Like
0Likes
Like

Posted 26 September 2005 - 07:25 AM

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.

### #12Dookie  Members   -  Reputation: 290

Like
0Likes
Like

Posted 05 October 2005 - 12:19 PM

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!

### #13papalazaru  Crossbones+   -  Reputation: 1854

Like
0Likes
Like

Posted 05 October 2005 - 12:55 PM

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.

### #14Dookie  Members   -  Reputation: 290

Like
0Likes
Like

Posted 06 October 2005 - 06:04 AM

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!

### #15papalazaru  Crossbones+   -  Reputation: 1854

Like
0Likes
Like

Posted 06 October 2005 - 12:28 PM

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.

### #16Dookie  Members   -  Reputation: 290

Like
0Likes
Like

Posted 12 October 2005 - 10:18 AM

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!

### #17scgames  Members   -  Reputation: 1961

Like
0Likes
Like

Posted 12 October 2005 - 10:50 AM

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.

### #18papalazaru  Crossbones+   -  Reputation: 1854

Like
0Likes
Like

Posted 12 October 2005 - 12:52 PM

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]

### #19papalazaru  Crossbones+   -  Reputation: 1854

Like
0Likes
Like

Posted 13 October 2005 - 07:02 AM

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]

### #20papalazaru  Crossbones+   -  Reputation: 1854

Like
0Likes
Like

Posted 13 October 2005 - 11:35 AM

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]

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS