Sign in to follow this  
Bucket_Head

Real-Time Collision Detection Between Line Segments With Linearly Moving Endpoints

Recommended Posts

Hey everybody, I'm struggling with a real-time collision detection problem - and I'm hoping somebody here might have considered this or a similar problem before, and might be able to help me solve it (or even determine a better problem to solve). I have a tendency to get a little bit thick in math-talk when describing a problem, but it's the way I think, and I hope it helps clarify the exact definition of the problem. I'm trying to make everything as clear as possible -- please let me know if something is confusing and I will try to explain it better. Right now I'm taking on 2D real-time physics, and because I want to detect bullet-through-paper sort of situations (with arbitrarily quickly moving anything), I mean to precisely solve for all exact moments and points of collision. I've been employing a Verlet integration w/ constraints sort of approach, with bodies made up of line segments, the endpoints being the particles in the system. After mulling this over for quite a while, I have come to the conclusion that all collision detection tests boil down to a single question -- if and when do two of these moving line segments collide? As for the exact nature of their movement, for any line segment, the endpoints are moving linearly over time from their respective positions at the beginning and the end of any given frame (any given iteration/update of the physics engine). The length of the line segment is the same at the beginning and the end of the frame, but inbetween it could contract, depending on how the individual endpoints move. There are several variables involved, and some are known. I know the times at the beginning and end of the frame. I know the positions of each of the endpoints at the beginning and end of the frame, so I can represent the position of each as a well-known function of time. Since a line segment is the locus of points in a linear progression from one endpoint to the other (lets call the endpoints A and B), I figured I can define some variable for the linear progression (let's call it x), restrict it to the range between 0 and 1 inclusive, and say that any particular point along the segment can be identified by this x, where in 2d-space this point would be at (B-A)x + A. (See, if x=0, then (B-A)x = 0 so the point is just A, whereas if x=1, (B-A) + A = B, so the point is at B -- and it's a linear progression for anything inbetween.) So basically here I'm defining a function (I can naturally invert it, so it's a nice two-way relation) so I can go between a unique point along the segment and where it is in space. This is all for a given moment of time (call it t), so if I had each of the positions as a function of time, this would look more like (B(t)-A(t))x + A(t). So that's the function for any given spot along the segment at any particular time. Basically, I need to determine when some spot on one segment and some spot on another segment are at the same place, and what spots those are. That means I need to solve for three variables -- the time of collision (t), a number representing where on one line segment the collision happened (since we defined the mapping above going from a single real number to a point in space and vice versa, a single real number is sufficient to represent this -- again, let's call this x), and likewise a number representing where on the other line segment the collision happened (let's call this y). So that's three variables to solve for, and as best I can determine, only one equation! Eep! Again, that equation is between two functions, for the point-of-collision on one segment and the point-of-collision on the other, both functions of time (t) and where-along-the-segment (x and y for the two segments, respectively). If we let the two endpoints of the second line segment be C and D, then algebraically it looks like: (B(t)-A(t))x + A(t) = (D(t)-C(t))y + C(t) After thinking about this some more, I came to the realization (and I really think I'm right about this, but please let me know if I am mistaken -- and remember we're in 2D with this, not 3D) that the only way two line segments can collide is if for at least one of the two, the point of collision is at an endpoint. This means that I can pull out one of the variables (let's take out y) and just attempt to solve the equation four times, once for each endpoint. This gets it down to two variables and one equation, but that's still theoretically unsolvable, unless there's something else I'm missing, or we can somehow get it down further... Another complication I should mention, of course, is that we aren't necessarily colliding for only one moment in time here. It's possible that the line segments could be dragging across each other for some time span, so there would be an infinite number of collision times, though there would be a definite beginning and end point. In this case our points of collision would be a range between an endpoint on one and an endpoint on the other...Still, that's a trickier situation to handle. The only nice thing about all this is that if it does get solved, it handles pretty much all collision and contact problems in one nice bundle. Maybe that's a problem with it though, maybe I'm trying to do too much with one thing and it isn't quite possible, I'm not sure. If you think I should make some other sort of simplification, please let me know. One more thing. I did try looking at this from another angle, simplifying the line segments to pure lines (stretching on forever) and considering a line-line distance equation as a function of time and trying to solve for whenever t=0, and then for those times trying to determine where along the lines the collisions were and if the points were between the segment boundaries, and for that it looked like I actually had a single variable and a single equation, but the math started getting really complicated on paper and it looked like I'd need to solve a third-order polynomial (I forget, is that solvable necessarily? It might have been fourth and beyond that's not, and maybe third is just expensive) which is naturally a doozy... But yeah, an interesting problem. Please let me know if anyone out there has any ideas, or any questions to help clarify the situation. Thanks very much for your time.

Share this post


Link to post
Share on other sites
Your problem is indeed going to boil down to four static-point-against-moving-segment tests. Here's why:

You were right in supposing a contact can only happen at one of the endpoints. So we'll consider each endpoint separately. If A is such an endpoint, we can assume A is static simply by transferring the movement A would have had to the endpoints of the other segment (C and D, for instance).

The movement of C and D is still linear (you only added the component from A's movement), so you need to perform a static-point-against-moving-segment to see the time of collision.

Now, two cases. If C and D move in the same direction, you can find if there will be an intersection (if A is between the "lines" formed by C and D during their movement) and the time of intersection by using Thales.

If C and D do not move in the same direction, their velocity vectors are base of the plane, inside which you could express the coordinates of A. This might be useful.

Share this post


Link to post
Share on other sites
ToohrVyk, I wanted to thank you for your help. I hadn't quite made the jump to realize that this could be simplified to a static pt vs moving line segment problem -- as you showed me it indeed can -- and it turns out that one of my local friends who also does some physics programming happens to have solved this very problem! So we should be able to put our heads together and figure out the more complex cases of the moving-line-segment vs moving-line-segment problem.

The complex cases, of course, are those of contact - where the two line segments slide perfectly along each other, meaning there is some infinite set of moments of time (that's bounded above and below, though) when the segments are in contact.

So there's still those crazy contact cases to work out, and then comes collision response...But we'll cross that bridge when we come to it, ne?

Cheers, and thanks again for your help!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
it sounds to me that you do have your two equations, since you're in 2D, so A(t)=(Ax(t),Ay(t)), so you expand your vectorial equation to 2 scalar equations ...

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this