Time of intersection between moving 2D segments
Author
Howdy everybody!
I have two 2D segments. Each segment has a velocity and a rotation speed. The segments are represented by two vectors - one for each end - the velocity by a vector, and the rotation speed by an angle/time scalar and a vector for the axis - but I can change the representations to whatever needed.
Anyways, what I need to know is when(if at all) those segments are going to intersect, if they continue at their current velocity and rotational speed. I tried to calculate it myself, but my math skills are not strong enough... is it even possible? Is there a formula or algorithm or something?
Thanks in advance!
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.
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.
Author
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"?
Author
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?
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.
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.
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:
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.
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.
Author
Thanks... I guess I should just use old method of checking the penetration depth...
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
