Could anybody tell me how to calculate if a point has crossed a 2D line, and how to get the intersection point. Thanks ----------------
Freeride Designs
----------------

hmmmm 2d...

long time ago ;-)

but i think it worked something like that:

equitation of a line

x = x1 + t*g

x.....running variable of the points on the line
x1....1 point on the line
t... parameter
g.....vector of the line

ok, then if u got 2 of thoes equitations
(u got 2 points defined for every line. take 1 point for x1 and for g u take the vector between the 2 points...)

now u put those 2 equitations together:

x1 + t*g = x2 + s*h (diffrent variable for the diffrent lines)

which would resolve in

x1.x + t*g.x = x2.x + s*h.x
x1.y + t*g.y = x2.y + s*h.y

u can solve this equitations because u''ve got only 2 unknown (s,t).If the result is something like 0 = 10 the lines are parallel if it''s something 0 = 0 the lines are ident.

otherwise you should get some values for s and t..

just place them into the equitation above and u get your collision point between the two points...

ok, there''s a problem in solving this on a pc.
u ned an algorythm for solving a equitation with 2 unknown...
i don''t know how to do that either. a friend once tried to explain it to me, but i didn''t get it so he just gave me the formula. sorry i haven''t got it right now ''cause i''m on holiday at my grandparent''s house and all of my older project files are at home...

hope that helped anyway..

cya,

Phil

Thx, but there must be an easier way than going into simultaneous equations.

Anybody???

----------------
Freeride Designs
----------------

As for intersection detection, I remember something like: if you put the line in terms of the equation ax+by=0 and plug in the value of any point to x and y, the resulting sign will tell you which side of the line it is on. Or zero tells you it is on the line. So if the sign is positive, then later negative, the point has crossed the line. I use this for my triangle intersection algorithm.

Then using the last two points, you make a vector and find the intersection of that vector and the line vector, which is expensive, but you only do it one you are sure there is an intersection.

-R

if you have a line defined by p1 and p2 where each point has coords, you need the perpendicular of this line (which has a slope of <-y,x> of the slope of the original line). sorry, you have to look up the math elsewhere, but what you need is the perpendicular to the line dropped from the test point. then you use the dot product with the point and the perpendicular line.

everyone else who knows this trick will say the dot product, too. if you can wait till tonight, i can look up the real implementation.

a2k

Hey thanks guys, once you mentioned the dot product I checked Mr. Gamermaker and read their dot product tutorial, and it had the exact solution I was looking for. So I''ve got it all working great now.

Thx

----------------
Freeride Designs
----------------

good to here it, Freeride Designs.

RotoMuffin: how "expensive" is finding the intersection point? because right now, i''m using euler time integration (if you have ever looked at Chris Hecker''s code, you''d know what i mean) in which, if the next state is penetrating, the time is subdivided, and the calculation is done again. if still penetrating, time is subdivided again until it can find the location of the collision. which is faster?

a2k