Detecting the time of collision between a rotating line and a moving sphere?

Game Mechanics
#1

This is for a pinball game, and the rotating lines are the flippers. It’s 2d.

The ball can move very very fast, so I can’t simply check for an intersection and respond then. If I translate the rotation of the line into additional motion in the ball, the ball gets really really strange non-linear paths that I have no idea how to work with, and they get worse the higher the rotation of the line is (obviously).
I’ve been trying to figure this out for five days now, and it’s slowly driving me insane. Help!

#2

That’s going to be difficult to solve exactly. Were I to face the same problem, I reckon I’d detect if the ball is passing through the arc that the flipper can swing through, and then just take timeslices and check for intersection as normal. If you find a collision, you can do a binary search over time to find a more exact solution. Calculate the size of the timeslices taking account of the speed of the ball and the speed of the tip of the flipper so there’s no chance you miss the collision.

Alternatively, instead of adding the flipper’s motion onto the ball, have you tried adding the ball’s motion onto the flipper? You’ll avoid having to deal with the curved paths, but you’ll still have to worry about the rotation. Something to think about anyway.

#3

Yeah, I tried that, but then I got a MOVING rotating line. :open_mouth:

Time slicing is not the most attractive option, as this has to run really, really fast, both in the verification code in java, and in actionscript for the actual client.
And besides, there’s no good way of knowing if the ball will hit after some random timeslice, or if it has done so before. Consider the extreme case of a line spinning 360*2 degrees in a single timestep, crossing a ball twice, ending up in the original position.

#4

damn, actionscript! and I half-expected this to be his next 4K game…

#5

Had a bit of a think about this, and you might be able to reduce it down to a one-dimensional problem by looking at the angles.

Assuming that your ball is moving in a straight line, and your flipper is rotating at a fixed speed ( or at least they can be approximated as such over a single timestep ), and taking everything with the pivot of the flipper as the origin:

Calculate the point on the circumference of the ball that is closest to the flipper at the start and end of the timestep. We’ll approximate the likely point of impact on the ball as being linearly interpolated between these points over the course of the timestep. Take the angles of these points so that you have an equation parameterised on time for the angle at which a collision can occur.
You also have a parametric equation for the angle of the flipper given the time
-> Solve to get the time where one equation equals the other. If there’s two or more solutions, as in your crazy-whirly-bonkers pinball pathological example, take the earliest.

I can see some problems arising where the ball’s center is moving into or out of the flipper’s range, but it might be worth a shot.

There’s some assumptions and approximations in there that you might be comfortable with, but I’m crap at maths so it’s the best I could come up with :-\

You could also try asking on the Maths & Physics section on Gamedev. They’ve got some fairly smart cookies there and you can avoid the flood of dilettantes if you’re specific enough in your question and make it clear your looking for an exact mathematical solution.

#6

hm, ok I will try that (tomorrow, at work).

Thanks. =)

#7

Isn’t this problem reducible to the intersection to two lines- the flipper line and the velocity ray of the ball, emanating from the ball? If you have an intersection of the lines, you will also have a collision if the distance sq between the point of intersection & the ball center will be <= the radius sq of the ball, and the collision normal is easy enough to find.

If we are thinking of the same problem, then the time of collision is (dist_from_description_above / speed_of_ball)*frame_time_slice

#8

No, imagine a line that rotates a full 360 degrees, and it’s obvious why at least one of the lines isn’t straight. Unfortunately. :-\

#9

I don’t see how that changes anything.

#10

You can’t have two straight lines (in 2d). It doesn’t seem to have any simple projection from 3d into 2d either (ie using line/plane intersection).
Possibly 4d, but now it’s getting complicated.

Aaanyway, I ended up replacing the flippers with a series of spheres. Moving spheres are no problem, as they don’t actually rotate, and since the flippers don’t move more than some 5 degrees or something per tick, the minor loss of accuracy from the linear interpolation isn’t noticeable.
It’s not perfect, and it’s a huge hack, but I need to finish this project sometime this year. :wink:

#11

?

Isn’t y=x or even y=0 a straight line?

But if you have a solution, then so be it. I guess you won’t need this http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm

#12

Probably for the best. Any performant solution was going to be an approximation anyway, so it may as well be a simple one.

#13

er, I think I forgot to finish the sentence. ;D

I meant “you can’t have a straight line represent a rotation”. An object that rotates 360 degrees ends up in the same position as it started, and it’s really hard to represent that as a straight line.

#14

Do you mean the paddle rotates in 360 degrees?

#15

yes, for example.

Of course, this will never happen, but it’s proof of why a straight line doesn’t work.

#16

Assuming that the paddle hinge is the origin, then the paddle can be represented as the line from the origin to the point at (cos(theta)*len, sin(theta)*len), unless I’m missing something important.

#17

The sphere is also moving.

You can’t project 2 moving/rotating lines in eachother.

Imagine we have the path for the ball in this timestep defined by a line, and the paddle as a rotating line. Figuring out where the lines will intersect doesn’t give you much information, as in that case you’re basicly checking for line vs. capped-cilinder, not a moving sphere, so you’d be able to determine if the shapes collide, not when (and in which direction to bounce), as relative to the rotating paddle, the (projected) movement of the sphere is not a line.

#18

That’s if the system is continuous, but what I’m talking about is discrete. After finding the position of the second paddle point, it’s just a line. Ok, the paddle is a line. check. Now at an instant in time, the sphere is not moving. The sphere is just an origin point and a velocity. Translate the origin point along the velocity vector by the radius to put the origin at the edge of the sphere. Given the new origin point and the terminal point of the sphere velocity, the sphere trajectory is a line. check. Ok, so now we have two lines in a Cartesian plane. If they intersect, we know that the will collide in the next timestep. We know where, we can find at what angle, and therefore the ricochet vector, and we can translate angular velocity for the paddle into linear velocity and add it to the ricochet.

However, this may all be wrong, as it does seem like this is too simplistic a solution when I write it out. :-[

#19

http://www.songprojector.com/temp/sphere_paddle.png

#20

Wow. You’re right, that’s phenomenally complex. But, I don’t see where the exact time matters, only that the simulation is believable (i.e., if a collision occurs within the time step, which is usually pretty small, react). So let’s cut out the idea of sub-steps. Let’s look at each of the first row of cells as if each is a full time step. Assuming a time step <1/30 sec, I think that would be sufficiently close to “exact”. Now it’s simply as I said, the intersection of two lines. This method also ignores “contacts” where the paddle is technically within the sphere, but the sphere is moving away from the paddle (assuming you move the sphere line segment to the edge of the sphere. This is similar to what bleb was saying, with some simplification