Time of intersection between moving 2D segments

Here are some algorithm that are in my mind right now...

Make one of the lines static by calculating the relative velocities between those lines. Make a polygon out of the "dynamic" line. It might be a concave polygon too if you use rotation. Then check if those objects intersect and calculate the time of collision using the intersection points.

OR

Do a binary search using a simple static line vs static line intersection test (you still should make one of the lines static) - move the "dynamic" line to time t=0.5 (start being 0.0 and end - 1.0 here). If it collides, subtract a half of the time, if it doesn't add a half of the time between currently used time and previous time (for the first iteration - 0.0). Use as many iterations as you need.

OR

Make the lines "fatter" and use a moving polygon-polygon intersection test.


There might be some more algorithms but these are the most basic that come in my mind right now.

Quote:

Original post by snake5 Here are some algorithm that are in my mind right now... Make one of the lines static by calculating the relative velocities between those lines. Make a polygon out of the "dynamic" line. It might be a concave polygon too if you use rotation. Then check if those objects intersect and calculate the time of collision using the intersection points.

I thought about it, but it won't work on fast rotating segments.

Quote:

OR Do a binary search using a simple static line vs static line intersection test (you still should make one of the lines static) - move the "dynamic" line to time t=0.5 (start being 0.0 and end - 1.0 here). If it collides, subtract a half of the time, if it doesn't add a half of the time between currently used time and previous time (for the first iteration - 0.0). Use as many iterations as you need.

Sounds nice, but it won't work on very fast moving segments, that can be on one frame in one side of a polygon and on the next frame on the other side.

Quote:

OR Make the lines "fatter" and use a moving polygon-polygon intersection test.

Now, that sounds interesting. Can anyone elaborate more about that "moving polygon-polygon intersection test"?

http://gpwiki.org/index.php/Polygon_Collision - Collision Prediction

Thanks! I'll look into it later.

O.K., I'm stuck. The problem is that both my polygons are moving and rotating(I asked about segments because I thought it'll simplify things, but what I really want to check if for polygon intersection).

Anyways, I've tried that separating axis thingie, but I got stuck at this equation:


That I need to apply for each point in one polygon, and each segment in the other polygon, to check when will the point touch the segment(if at all).

h is the height of segment that is used as axis, from the center of it's polygon.
alpha is the angle of that segment.
C is the center of the polygon that contains the point.
v is the relative velocity between the polygon that contains the point and the polygon that contains the segment.
p is the position of the point, relative to the center of it's polygon.
omega is the rotation speed(in radians) of the polygon containing the segment.
delta omega is the relative rotation speed(also in radians) between the polygon containing the point and the polygon containing the segment.
And, ofcourse, t is the time.

All values, except time, are parameters. I need to find the time. With such a complex equation, is it even possible?

I can't find it right now, but there should be a thread on these forums concerning moving point vs moving lineseg; the gist is that you consider the point to be static and find the time when it intersects the line containing the two lineseg endpoints (solve a quadratic), and then you determine if at this time the point is between the endpoints (i.e within the lineseg) or not.

With a moving-point-vs-moving-lineseg, you can handle moving-seg-vs-moving-seg by testing each endpoint vs the other lineseg. Of course, this linearizes the movement (i.e the linesegs change length, since the movement of the ends are represented as vectors rather than arcs) so for high rotation it might not be a good approximation.

Yea... rotation is my main problem here. Two rotations, actually...

From what I found out when I wrote similar equations a long time ago is that it's analytically impossible to find the time of collision between two rotating and translating line-segments. There are unlimited possible intersection points so a numerical method is your best bet. Treating one of the line-segments as stationary is what you have to do. You can treat line-segment A as stationary and then give B a velocity of B.Velocity - A.Velocity. For the rotation you'll have B rotating around A :P That part is fun. I have a demo if you want to see it with the equations.

Also why are you doing this? If you're trying to use this for a priori collision detection system it won't work well at all for anything real-time. (Solving the first collision stepping forward and solving the next anyway). You'll run into floating point issues along with the fact you can't reasonably handle stacked objects since collisions will be happening in an epsilon amount of time coupled with the fact that you can't solve the response for an N-body collision problem perfectly resulting in more floating point inaccuracies.

Actually the wikipedia article sums it up best:

Quote:

However, in all but the simplest cases, the problem of determining ahead of time when two bodies will collide (given some initial data) has no closed form solution -- a numerical root finder is usually involved.

It's not for the faint of heart. I started writing an article that covers Priori methods of collision detection and the whole purpose of the article is to warn people of the problems with this method. (I should finish it sometime). I spent a good few months tackling the math and writing some a somewhat decent system for it. It lagged badly in the end. I know a math major that had done the same thing with the exact same results. We both kind of figure there might be a hybrid method between using an SAT based system along with priori stuff for continuous collision detection.

Thanks... I guess I should just use old method of checking the penetration depth...

The problem is easy to conceptualize: imagine a point on one segment. You want to trace out the path it follows through space. Such a path is defined by something like r(t) := ballistic motion + rotation motion.

Ballistic motion is a quadratic, so it's a nice closed form to work with. The rotation motion, though, is trigonometric. And trigonometric functions don't have a closed form. ie: imagine something like f(t) := 5 * t + sin(t) + 1, and g(t) := 7*t + cos(t) + 2. Finding the intersection of these two functions gives: f(t) - g(t) = 0 = -2 * t + sin(t) - cos(t) + 3.

The only way to solve that equation is with numerical methods (in case you're wondering, cosf, acosf, etc. are numerical methods under the hood).

Also, there is a way to approach this problem that's been thought of and is used in practice. Take a look at Mirtich's thesis, Chapter 2 ("Collision Detection"). You find a lower bound on the distance between the bodies, and an upper bound on the max velocity of a point on either bodies, and use that to "conservatively advance" by some value to a new time where the bodies are either just touching or entirely disjoint. Then you go again and recompute a "conservative" estimate for a new time in the future. Eventually you reach some epsilon value and call it good enough.

The nice thing here is that if you can describe the motion of the center of mass of either body over time (say, because they follow a ballistic path) you can treat the two bodies in isolation and calculate indefinitely into the future (possibly several seconds or more). You then put the tentative collision pair into a "collision heap" (again, Chapter 2). If a collision "lower" (sooner) in the heap causes either body to change motion, you find any collision pairs in the heap which might be affected (directly or indirectly) and recalculate them. It causes a sort of "cascade" update, so if two bodies are in isolation somewhere in the simulation you don't have to conservatively advance the entire world.

Some insights I've had myself after reading Mirtich's thesis:

You can also bound the times of impact by doing bounding sphere - bounding sphere collision detection on the path of the center of mass. Since the path of the center of mass is invariant to any rotations, you can entirely drop the rotation term and get a "window" for collision when the bounding spheres overlap by doing something as simple as finding the roots of a quartic (assuming ballistic motion), for which there is a closed form solution. If you assume only linear motion, you just have to solve a quadratic, which likewise has a closed form solution. This window represents bounds during which a collision "might" occur. I haven't done any tests but I imagine this is a far tighter bound than conservative advancement would give. So if the two objects might collide during the window [5 seconds, 5.5 seconds], you can start conservative advancement at 5 seconds and save yourself from doing several GJK steps.

Likewise if you do an "inner" bounding sphere (bounding the region inside the shape that is entirely filled by the shape. For instance, a square's inner bounding sphere would be the inscribed circle centered on the center of mass) you can construct another window which represents a time period when the two objects must be in intersection.

Using the outer and inner bounding spheres' windows of collision, I'm thinking you can use some more aggressive root finding methods, but I'm not sure what they would be just yet.

Oh I almost forgot to say the most important problem. Try doing joint kinematics using your equations :P They can get rather interesting.

That linked thesis is cool, I lost the link to that when I deleted my bookmarks a while back.

[Edited by - Sirisian on October 5, 2009 6:19:56 PM]

Yeah, any IK is a whole other can of worms since it means bodies won't have a nice ballistic path. That said, if you take the multibody formed by the smaller bodies and their joints, you can still conservatively advance it to find time of impact against other multibodies or terrain. And you can still do the bounding sphere trick I mentioned if you use the center of mass of the multibody as a whole, since you can ignore any torque terms and take any forces the body uses to move arms, etc. as operating only on the center of mass. Usually you'll want the linear terms to all cancel out, which means they won't affect the motion of the center of mass for the multibody anyway, so you can ignore them (eg: a flailing man in space can't change the motion of his center of mass).

Quote:

Original post by Sirisian There are unlimited possible intersection points so a numerical method is your best bet.

Hmm, I saw this bit coming.

Quote:

Original post by Sirisian Also why are you doing this? If you're trying to use this for a priori collision detection system it won't work well at all for anything real-time. (Solving the first collision stepping forward and solving the next anyway). You'll run into floating point issues along with the fact you can't reasonably handle stacked objects since collisions will be happening in an epsilon amount of time coupled with the fact that you can't solve the response for an N-body collision problem perfectly resulting in more floating point inaccuracies.

This is what I've been working on recently, mainly because I can rarely just be told that something does/doesn't work - I have to go through and convince myself first-hand. >_>

I've had a formula working for a point and a moving line sans-rotation, though I haven't transplanted it into a game yet; and I've been running an a priori solution for collisions between moving circles and fixed lines/points in a project I'm working on. The latter bleeds data - up the timestep and there are minor variants in the direction the system takes (so much for determinism) - but the circles could be moving at any speed you like, for any period of time, and never find their way out of their enclosure.

I guess my other problem is that I'm over-dramaticizing the task of dealing with inaccuracy, resolving intersecting bodies only to cause another intersection, etc. I'm obviously pretty new at this stuff.

Quote:

Original post by Numsgil The only way to solve that equation is with numerical methods

I'm guessing...



...?

Quote:

Original post by Fenrisulvur Quote: Original post by Numsgil The only way to solve that equation is with numerical methods I'm guessing... ...?

Not sure what you're trying to say exactly. You could approximate the trig functions with some sort of polynomial or linear function using its taylor expansion, and arrive at an answer that way, if that's your point. But it's always an approximation so you'd still have to do some sort of iterative convergence.

Quote:

Original post by Numsgil Not sure what you're trying to say exactly. You could approximate the trig functions with some sort of polynomial or linear function using its taylor expansion, and arrive at an answer that way, if that's your point. But it's always an approximation so you'd still have to do some sort of iterative convergence.

First part: yes, that's my point. Secondly, like I said before, I'm pretty new at this stuff. You've lost me on iterative convergence - at least as far as it applies to collision detection. I can see I've got a lot of research to do.

Quote:

Original post by Fenrisulvur This is what I've been working on recently, mainly because I can rarely just be told that something does/doesn't work - I have to go through and convince myself first-hand. >_>

Yep that's why I did it too. It's a fun challenge.

I actually tried the taylor series approach. It's not as easy as it first seems. Also it doesn't help to solve the problems I discussed earlier. Even if you have the exact times of every collision you still end up in situations where the collision response graph you're solving is insane.

Quote:

Original post by Numsgil You then put the tentative collision pair into a "collision heap" (again, Chapter 2). If a collision "lower" (sooner) in the heap causes either body to change motion, you find any collision pairs in the heap which might be affected (directly or indirectly) and recalculate them. It causes a sort of "cascade" update, so if two bodies are in isolation somewhere in the simulation you don't have to conservatively advance the entire world.

I haven't read Mirtich's thesis yet(I'll do it later), but that was my basic idea. Great minds think alike, I guess...

Quote:

Using the outer and inner bounding spheres' windows of collision, I'm thinking you can use some more aggressive root finding methods, but I'm not sure what they would be just yet.

That's brilliant, Numsgil! At his first reply, snake5 suggested I do a binary-search-like algorithm to find the time of intersection, but I didn't like it, because if, lets say, a bullet is supposed to move 10m. at a certain frame, and it is distanced 5 meters from a 2 meter wide wall, they won't intersect neither at the beginning nor the end of the frame. However, if I use the outer bounding circle time and the inner bounding circle time(or the time when they are closest, if they don't collide) as the search frame, this idea might work!

snake5 and Numsgil, thank you very much! I'm gonna try that later.

Quote:

Original post by Fenrisulvur Quote: Original post by Numsgil Not sure what you're trying to say exactly. You could approximate the trig functions with some sort of polynomial or linear function using its taylor expansion, and arrive at an answer that way, if that's your point. But it's always an approximation so you'd still have to do some sort of iterative convergence. First part: yes, that's my point. Secondly, like I said before, I'm pretty new at this stuff. You've lost me on iterative convergence - at least as far as it applies to collision detection. I can see I've got a lot of research to do.

The language is harder than the idea, if you know what I mean. :)

Assuming you know what a Taylor expansion is, no matter how many terms you add you will always have an error term. Plus, on computers with floating point, higher order polynomials are extremely fussy, to the point of being borderline unusable. (eg: Wilkinson's polynomial.)

So you have to choose a reasonable level (say, quadratic or linear) to approximate the trig function at, if that's the way you want to approach it. There will be some given error for that approximation. If it's within your acceptable error (say, machine epsilon), then you're done. But it probably won't be. So you'll need to do a new approximation using your old approximation as a starting point. You iterate like this until the difference between two successive answers is within some threshold.

This is the basis for Numerical Analysis, which is a suite of tools for solving problems that can't be solved with direct methods. Often the iterative methods are actually better (faster to run the algorithms) than direct methods, especially if you have a tight bounds on where the answer should live.

As far as collision detection, you can approach it in two ways that I'm aware of if you want to find the exact time of impact:

1. Construct some sort of equation representing the distance between the bodies, and solve for when this distance is 0 (ie: find the roots). Since anything much more complex than rotation free ballistic motion with drag can't be solved analytically, you have to delve into numerical methods, which are inherently iterative.

2. Using an algorithm to conservatively find the distance between any two shapes (ie: GJK), and a liberal estimate of the speed of any point on the body, advance the simulation forward by distance/speed. Again here, you have to iterate since you're using estimations at each point.