2d Vector Collision Detection

[hessiess]

Say I have a vector[V1], which over one frame moves to the point[V2]. Slap bang
in the middle of the two points is a triangle, defined by the points P1, P2 and
P3, The problem is that V1 is moving so fast it completely skips over the
triangle.

The solution that I have come up with is to take the triangle and discard all
of the back faces, then project rays through the remaining vertices to
infinity([P1pro][P2pro]). This would form one or more quadrilaterals(shown by
the greeney-yellow
aria of the image). Then the next frame of vector[V1] would be simulated, and
tested to see if it was within any of the quadrilaterals, the collision
point[CP] calculated and V2 moved to slide along the surface/bounced off ETC.

Image to visualise this:

This is all well and good, but I don't know how to calculate if the V2 vector
is within the aria defined by the quadrilateral ([P1][P2][P1pro][P2pro]), or how to calculate the collision
point[CP],

 

[dekutree64]

Seems a little overcomplicated. What about just doing 3 line segment intersections so you don't have to worry about skipping over the triangle? This looks like a good explanation of line intersections http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/

If you're worried about speed, you could do line segment versus bounding circle first. But much better would be to use some sort of space partitioning to avoid checking anything but the immediate surroundings in the first place. An easy style is just a regular grid, with each cell storing a list of objects that are overlapping it.

 

[benjymous]

Box2D is great at that sort of thing, although as it's heavily float based internally there's a bit of a debate on how well it'll perform on the Pandora "out of the box"

Hopefully someone will produce an optimised version soon enough, though

 

[hessiess]

Seems a little overcomplicated. What about just doing 3 line segment intersections so you don't have to worry about skipping over the triangle? This looks like a good explanation of line intersections http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/

If you're worried about speed, you could do line segment versus bounding circle first. But much better would be to use some sort of space partitioning to avoid checking anything but the immediate surroundings in the first place. An easy style is just a regular grid, with each cell storing a list of objects that are overlapping it.



Thanks for the tip, currently im more interested in macking it work, speed optimisations can be done later.

 

[PokeParadox]

Box2D is great at that sort of thing, although as it's heavily float based internally there's a bit of a debate on how well it'll perform on the Pandora "out of the box"

Hopefully someone will produce an optimised version soon enough, though

It's already been ported to the DS, so that version is already fixed point friendly, etc.

 

[sinoth]

Gonna +1 the Box2D suggestions. I'm sorry I can't give a mathematical answer, but here is an article on how Box2D handles it: http://www.box2d.org/wiki/index.php?title=CCD

Basically, if you know something is going to be moving fast, you can turn on CCD (continuous collision detection) for that object. It is more expensive than normal collision detection but avoids the issue of passing through stuff.

 

[TrevorBradley]

This is relatively easy, and while you've defined the question correctly, trying to get the computer to work with quadrilaterals is making things complicated.

Step 1: Check to see if V2 is in the right direction.

There are four new vectors created on your map, with V1 as their origin:

V2-V1
P1-V1
P2-V1
P3-V1

If it helps draw arrow heads pointing at each of V2, P1, P2 and P3 coming from V1.

Each of these vectors has an angular direction that can be determined using the arctan function. You get an angle in radians for each one. If the V2-V1 angle is BETWEEN two of the other angles, you know that a collision is possible. If not, there's no collision.

In the case of your diagram V2-V1 looks to be about 6*PI/4 radians, while P1-V1 is about 7*PI/4 radians, and P2-V1 is about 5*PI/4 radians. Remember that in the computer world, Y is down the axis, so zero radians is still to the right, but the angle goes CLOCKWISE instead of anticlockwise, going down and then to the left.

Step 2: Check to see if V2 passes P1<->P2.

OK, so you know that V2 is in the right direction, but you don't know if it's passed the line made by P1 and P2. What you do now is use P1 (one of the two points in the intersecting face of the triangle) as the origin of a new set of four vectors. Start by determining the angle of P2-P1. Add PI to that angle and you get a range. (Looks like PI/4 to 5*PI/4 on your diagram). You're almost there. Take angles for V1-P1 and V2-P1. If they're on opposite sides of the range (that is, opposite sides of the P1/P2 line), you have a collision. If they're on the same side, then V2 hasn't yet hit the triangle. Again you'll have to use arctan to convert a delta vector (like P2-P1) into an angle.

Basically I've just reworded your quadrilateral imagery and just went with an angular wedge, and a line. Step 1 was "Is the angle of V2 between P1pro and P2Pro?" and Step 2 was "Is V2 on the same side of the P1<>P2 line as V1?"

Just a nasty bit of grade school trigonometry. I took a third year comp sci course in university on 3D graphics, and it was amazing how much the students there struggled with trigonometry.

here... I did these up visually so they'd make more sense (though not as pretty as your diagrams)

Step 1: Is Theta (V2-V1) between Theta (P1-V1) and Theta(P2-V1)? (If so, proceed to step 2, else no collison)

Step 2: Is Phi(P3-P1) between Phi(P2-P1) and Phi(P2-P1)+PI? Is Phi(V1-P1) between Phi(P2-P1) and Phi(P2-P1)+PI? (if one is true, and the other false, the vectors are on opposite sides of the P2-P1 line and you have a collision)

(ignore my weird cruft at the bottom left, I had it at the top left and it was getting in the way)

Edit: just a note here... One messy bit about trig is that you need to define "less than" in a meaningful context for radians. So 2*PI-0.001 is less than 0. Here's a bit of code I wrote up for that very purpose in my latest program...

CODE
// is angle1 between angle2 and angle3 (angle2 left of angle3)
bool Coords::angleBetween(float angle1, float angle2, float angle3) {
while (angle1<0)
angle1+=2.0*PI;
while (angle2<0)
angle2+=2.0*PI;
while (angle3<0)
angle3+=2.0*PI;
while (angle1>2.0*PI)
angle1-=2.0*PI;
while (angle3<angle2)
angle3+=2.0*PI;
while (angle1<angle2)
angle1+=2.0*PI;
if ((angle1>=angle2)&&(angle1<=angle3))
return true;
return false;
}


The code assumes sane angles in the -2*PI to +4*PI range, the kind you'd get by running arctan and then adding or subtracting some offset to it.

EDIT2: CP Collision point by the way is simple algebra. Determine the linear equation for the two lines of V1-V2 and P2-P1 (i.e. determine a,b for y=ax+b ), and put the two together like so:

y=a1*x+b1
y=a2*x+b2
a1*x+b1 = a2*x+b2
(a1-a2)*x = b2-b1
x = (b2-b1)/(a1-a2)

gives you x.. put that back into either of the first two equations to get y.
y=a1*[(b2-b1)/(a1-a2)]+b1

The slope a is just (v2-v1).y/(v2-v1).x... no need to use arctan again. b can be worked out by y=ax+b, using the a we just worked out, and x and y from V1 or V2.

This is all pseudocode, poor text description and badly modified diagrams, but I hope this helps you get in the right direction... Good luck!

 

[White Flame]

EDIT2: CP Collision point by the way is simple algebra. Determine the linear equation for the two lines of V1-V2 and P2-P1 (i.e. determine a,b for y=ax+b ), and put the two together like so:

You really don't want to do y=mx+b style functions in free coordinate space, because it will die on vertical lines. It's best to stick with pure vector math. I'll see if I can blat together my version of it.

EDIT:

Okay, to determine whether V2 is in the infinite "triangle" defined by P1pro and P2pro takes 2 cross products.

The sign of the cross product of (V1-P1)x(V2-P1) will tell you if it's inside P1pro, the cross product of (V1-P2)x(V2-P2) will tell you if it's inside P2pro. Regardless of how the signedness with the flipped screen Y axis and whether Z goes into the screen or not, if the Z signs differ between the two, it's inside the infinite triangle.

Now, to see if it's behind the P1-P2 line, take the cross product of (P2-P1)x(V2-P1). If the sign is the same as the first cross product above, then it has passed through the wall.

z1 = sgn( (V1-P1)x(V2-P1) )
if (z1 != sgn (V1-P2)x(V2-P2)) &&
(z1 == sgn (P2-P1)x(V2-P1)) then it's inside the colored region.

You might get 0 for some of the cross products if V2 is exactly on P1pro or P2pro, so don't actually use sgn, just do <0 binary comparisons or something, depending on how you want your edge condition to work.

and here is the equation to figure out the intersection of 2 line segments from a vector standpoint. Depending on what you need, that one formula can tell you everything you need to know:

ua in [0..1] corresponds to the time of the frame where the moving object hits the _plane_ of the wall.
ub in [0..1] corresponds to where on the wall it hit.

If ua is out of bounds, that means that the collision won't occur during the time that this frame represents, if ub is out of bounds, that means it missed the wall segment.

 

[benjymous]

Having a quick search on the Box2D DS port, I found this post that points out that this is already built in to Box2D v2, you just need to flip a "fixed floats" define, so that makes me feel much happier that my game will run at a decent framerate on the Pandora Hardware (that and the massive graphical optimisation I sorted out last night )

 

[GernotFrisch]

It's just a simple line-line intersection test, no?

 

[JayFoxRox]

Either I don't get the what you are trying to do or a simple ray / triangle intersection is all you need:

http://letmegooglethatforyou.com/?q=triangle+intersection

 

[ledow]

I just have to add that I would highly recommend the book "Physics for Game Developers" which deals with this and many other similar problems both in 2D and 3D, with examples and code on a CD/Download.

I "get" Mathematics and managed to get a degree in it but I still don't "get" physics even though it was part of my courses (I nearly failed all the physics-related courses). That book was very helpful to me and deals with the issues around collision detection in 3D, including this exact problem I believe. You might even be able to find the relevant chapters online because it was an O'Reilly book IIRC.

 

[hessiess]

Thanks greatly for all of the explanations, helped a lot

About Box2D, I may use it in the long term, but I would also like to learn how to implement collision/physics myself as well.