Point line collision reaction

Question

I am trying to program point line segment collision detection and reaction. I am doing this for fun and to learn.

The point moves (it has a velocity, and can be controlled by the user), whilst the lines are strait and stationary. The lines are not axis aligned. Everything is in 2D.

It is quite straight forward to work out if a collision has occurred. For each frame, the point moves from A to B. AB is a line, and if it crosses the line segment, a collision has occurred (or will occur) and I am able to work out the point of intersection (poi).

The problem I am having is with the reaction. Ideally I would like the point to be prevented from moving across the line. In one frame, I can move the point back to the poi (or only alow it to move as far as the poi), and alter the velocity. The problem I am having with this approach (I think) is that, next frame the user may try to cross the line again.

Although the point is on the poi, the point may not be exactly on the line. Since it is not axis aligned, I think there is always some subtle rounding issue (A float representation of a point on a line might be rounded to a point that is slightly on one side or the other). Because of this, next frame the path might not intersect the line (because it can start on the other side and move away from it) and the point is effectively allowed to cross the line.

Firstly, does the analysis sound correct?

Having accepted (maybe) that I cannot always exactly position the point on the line, I tried to move the point away from the line slightly (either along the normal to the line, or along the path vector). I then get a problem at edges. Attempting to fix one collision by moving the point away from the line (even slightly) can cause it to cross another line (one shape I am dealing with is a star, with sharp corners). This can mean that the solution to one collision inadvertently creates another collision, which is ignored.

Again, does this sound correct?

Anyway, whatever I try, I am having difficulty with edges, and the point is occasionally able to penetrate the polygons and cross lines, which is undesirable. Whilst I can find a lot of information about collision detection on the web (and on this site) I can find precious little information on collision reaction.

Does any one know of any good point line collision reaction tutorials? Or is my approach too flawed/over complicated?

Answer 1

Well first off I'm assuming you're doing a kind of "trace" like described here: http://www.realtimerendering.com/intersections.html

So for a given frame you have a certain amount of velocity you want to account for. For the sake of argument let's say you want to slide along surfaces instead of bouncing off of them.

So let's say the user is pushing their point (or circle, if you want to give yourself a little more wiggle room with penetration testing) along a surface. You might have a certain amount of movement until you hit the wall. So place the object at the earliest intersection point you detect (but slightly offset in the opposite direction to avoid the floating point errors you mentioned). Then in the same frame figure out the desired velocity (in our case we'd do a sliding effect by taking the remaining component of the velocity vector that's parallel to the hit surface). In the same frame you'd attempt to move the user's point along this updated velocity vector, doing collision detections along the way. Iterating the collisions, if you will. You'll probably have to set some maximum number of per-frame collisions so that you don't get into some kind of near-infinite-loop situation. This number is usually pretty small, like 5 or so.

Answer 2

The first part seems reasonable, and your solution also seems reasonable. The second part can be avoided by finding the closest line that intersects the path. You can't create a new collision if there is nothing closer that will collide.

Answer 3

I found this tutorial to be very revealing on the subject.

Metanet Collision Detection & Reaction

Quote from one of the first lines of the tutorial:

"Before thinking about how to detect collisions, we should first think about what should happen to two objects which collide."