i once found this cool collision detection for moving spheres (circles) that found the exact moment they collided, not just whether they did or did not - this was cool to detect against two circles who might be moving too fast they''d move past each other, never being in a collided state. (if i remember they took the distance between two circles as a graph/formula, and tested for any places it crossed the x-axis -aka- anytime the two collided -aka- anytime the formula was zero. hope that helps) i want to expand this to include lines. however, lines are more complex than simple circles. im looking for some advice on how to go about doing this. not whether two lines intersect or not, for that is explained online already, but whether between one frame and the next two lines ever intersected, and if so, when and where. ex: imagine two parellel lines traveling closer to each other. the odds of them simply passing through each other and not landing on top of each other during a frame is high. ex2: lines can be any length, and also be rotating as well as moving. there are instances where two lines would pass through each other, or their ends would rotate past each other - and in actuality intersect but on screen never be in a collided state. as ive stated before, im not looking for any simple IS/ISNT collision scheme, but rather an expansion of the DID/DIDNT from the circle example that includes lines as well (circle/line and line/line detection). - jeremiah http://inlovewithGod.com

Well, that is a nasty problem. At a minimum you are going to have to use linear algebra. Matrix equations are the only thing that would make it anywhere near a managable problem. It should be possible to setup a matrix equation such that you have P(u,t) where u varis from 0 to 1 and t is the time generates the points on one line segment at a given time. Then you will need to solve P1(u,t)=p2(v,t) for u, v and t. Within 3D that is three equations of three unknowns so it is possible at least in theory. It seems like it should still be possible in 2D. Personally I would expect actually solving it to take more linear algebra than I know. Specifically I don''t know how you solve A^t=B where A and B are matrices of constants and t is a scalar variable. If your matrix equation is an equation of matrices of constants then I''m pretty sure those matrices are going to be raised to a power of the time.

That at least gives you a direction to go if you really want to do this.

quote:

---

and also be rotating as well as moving

---

hehe... good luck. I gave up on this. Sorry not to be more helpful but the more you look at it the more you will see its far from a trivial problem... In fact the only hints I could get from people who knew more about it than me were like ''we never tried to do that''.

yeah, its not that simple i know. :-/

i went and looked at a circle-circle DID/DIDNT collision scheme and i realized a bit more that the rotation of the lines causes lots of headache. if they didnt rotate, i can imagine a plausible solution - but the rotating just messes things up...

if the lines dont move or rotate, then its trivial - if they move but dont rotate, i can see some potential ways - but if they''re doing both, im a little light on ideas on even how to go about setting it up...

id be more than willing to throw around ideas though and see if we cant try and come up with a solution...

- jeremiah

inlovewithGod.com

One problem with intersecting moving lines is that over the course of a frame, the two positions for a given line may not lie in the same plane. So if you want to compute their collision using swept-lines, then you''re going to be intersecting two curved surfaces. You could, of course, tesselate each surface into two triangles----making an assumption about which diagonal to use. After that, triangle-triangle intersection is covered in the literature.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

http://www.jopte.com/bastillion/jjc/collision/3d_collide.html

Here are the goods :-) Non trivial but this method is a nice and simple solution.


-Meto

im not sure if i mentioned this before, but my game is only 2D, so that helps simplify any planar issues.

after reading some posts, it got me thinking. i thought that if you created a 4-sided polygon from the moving/rotating lines - where one side was the line in frame 1, and the opposite side was the line from frame 2 - you could then test whether these polygons overlapped to see if a collision occured or not. however, its still flawed as the issue of time isnt addressed properly.

heres an example of it failing...


any further thoughts on this?

- jeremiah

Jeremiah-
The problem you are having is that the paths of the lines cross, but not at the same time. Its the same problem that plagues students when they are first exposed to parametric equations, graph the objects moving, see the lines they make cross, and come to the false conclusion that the two objects intersect. You need to look for the time at which the two lines would intersect. The test you have right now sounds good for determining whether or not this is a possibility, but I don''t think there is going to be a shortcut around finding the time when the two intersect, and then from there you should be able to find the point of intersection. Let me think about it and I will get back to you later tonight hopefully.
Brendan

If I''ve solved similar really messy systems of parametric equations, you can solve this one! It''s nothing a pencil, paper, a calculator, and some 9th-grade maths cant solve. It''s time consuming and error prone, but you can do it.

Here''s a set of cartesian equations that describe a line in 3d:

y = ax + b
z = cx + d

a is dy/dx and c is dz/dx. Write equations for them in terms of known points and t, and substitute that back into the above equations. Do this for both lines, and set them equal. You end up with 4 equations (2 per line * 2 lines) and 4 variables (x, y, and z coordinates of point of intersection, and t). That means you can solve it.

It''s ugly, but you can do it.

I''m not of a mathematician, so take this with a a grain of salt.

Going by the groovy pic above, instead of creating the first quad from the line1 + vector1, Create the quad using the difference between the two vectors.

ie. line1 + (vector1 - vector2) = quad1;
(If they both have the same vector magnitude and direction, quad1 will be = to line1.)
Leave line2 unchanged, but test to see if it intersects quad1.
Then to determine the exact point of intesection, get the distance between Line1''s final position and Line2. Get the ration between the two lines velocities, and then use that to calculate teh exact point of collision.

If this doesn''t make sence I can try to explain more carefully.
Let me know.