Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (538)
Games in Android Showcase (132)
games submitted by our members
Games in WIP (600)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1] 2
  ignore  |  Print  
  Detecting the time of collision between a rotating line and a moving sphere?  (Read 6727 times)
0 Members and 1 Guest are viewing this topic.
Offline Markus_Persson

JGO Wizard


Medals: 16
Projects: 19


Mojang Specifications


« Posted 2007-01-14 11:37:26 »

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!

Play Minecraft!
Offline ryanm

Senior Devvie


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #1 - Posted 2007-01-14 11:57:45 »

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.
Offline Markus_Persson

JGO Wizard


Medals: 16
Projects: 19


Mojang Specifications


« Reply #2 - Posted 2007-01-14 12:54:44 »

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

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.

Play Minecraft!
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline woogley
« Reply #3 - Posted 2007-01-14 13:24:20 »

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

Senior Devvie


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #4 - Posted 2007-01-14 14:24:50 »

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.

<mind-dump>
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.
</mind-dump>

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 Undecided

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.
Offline Markus_Persson

JGO Wizard


Medals: 16
Projects: 19


Mojang Specifications


« Reply #5 - Posted 2007-01-14 15:15:46 »

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

Thanks. =)

Play Minecraft!
Offline biggeruniverse

Senior Newbie




That's just peanuts to space.


« Reply #6 - Posted 2007-01-14 15:32:29 »

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
Offline Markus_Persson

JGO Wizard


Medals: 16
Projects: 19


Mojang Specifications


« Reply #7 - Posted 2007-01-14 15:52:26 »

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. Undecided


Play Minecraft!
Offline biggeruniverse

Senior Newbie




That's just peanuts to space.


« Reply #8 - Posted 2007-01-14 16:08:13 »

I don't see how that changes anything.
Offline Markus_Persson

JGO Wizard


Medals: 16
Projects: 19


Mojang Specifications


« Reply #9 - Posted 2007-01-14 19:25:17 »

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

Play Minecraft!
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline biggeruniverse

Senior Newbie




That's just peanuts to space.


« Reply #10 - Posted 2007-01-14 20:11:25 »

You can't have two straight lines (in 2d).

[size=20pt]?[/size]

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
Offline ryanm

Senior Devvie


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #11 - Posted 2007-01-14 20:36:15 »

Aaanyway, I ended up replacing the flippers with a series of spheres.

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

JGO Wizard


Medals: 16
Projects: 19


Mojang Specifications


« Reply #12 - Posted 2007-01-14 21:26:33 »

[size=20pt]?[/size]

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

er, I think I forgot to finish the sentence. Grin

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.

Play Minecraft!
Offline biggeruniverse

Senior Newbie




That's just peanuts to space.


« Reply #13 - Posted 2007-01-14 21:49:30 »

Do you mean the paddle rotates in 360 degrees?
Offline Markus_Persson

JGO Wizard


Medals: 16
Projects: 19


Mojang Specifications


« Reply #14 - Posted 2007-01-15 08:41:04 »

yes, for example.

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

Play Minecraft!
Offline biggeruniverse

Senior Newbie




That's just peanuts to space.


« Reply #15 - Posted 2007-01-16 11:34:50 »

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.
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 840
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #16 - Posted 2007-01-16 12:16:54 »

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.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Offline biggeruniverse

Senior Newbie




That's just peanuts to space.


« Reply #17 - Posted 2007-01-16 13:21:28 »

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.

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.   Embarrassed
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 840
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #18 - Posted 2007-01-16 15:29:18 »


Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Offline biggeruniverse

Senior Newbie




That's just peanuts to space.


« Reply #19 - Posted 2007-01-16 16:26:21 »

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
Offline Markus_Persson

JGO Wizard


Medals: 16
Projects: 19


Mojang Specifications


« Reply #20 - Posted 2007-01-17 08:14:05 »

simply pretending the lines are straight and intersecting does not work. The ball flies straight through the paddle in several instances.

Play Minecraft!
Offline oNyx

JGO Coder


Medals: 2


pixels! :x


« Reply #21 - Posted 2007-01-17 09:26:25 »

>But, I don't see where the *exact* time matters[...]

http://en.wikipedia.org/wiki/Collision_detection#A_posteriori_versus_a_priori

Imo priori is amazingly accurate and robust (but it's also horribly complicated).

---

Hm. Well, a rotating line segment won't really do the trick, because those edges of the flippers are offsetted from the rotating point.

Man... my head hurts.

Well, you can always use multi sampling if the ball gets into that area... and if you find a collision you go back/forward stepsize/=2 until you reach some (abs) threshold distance, at which point you resolve the collision.

弾幕 ☆ @mahonnaiseblog
Offline Markus_Persson

JGO Wizard


Medals: 16
Projects: 19


Mojang Specifications


« Reply #22 - Posted 2007-01-17 09:36:42 »

hm, so if the ball is going very fast, I find out what timespan of the total tick time the ball spends in the vincinity of the flipper, then do checks only for that distance.

It might end up using too many cycles, but it's probably better than my solution of replacing the rotating line with 20 moving spheres, all overlapping each other. Wink

Play Minecraft!
Offline oNyx

JGO Coder


Medals: 2


pixels! :x


« Reply #23 - Posted 2007-01-17 11:14:28 »

Shouldn't be that bad... I think. The speed of the tip of the flipper and the speed of the ball give you the minimum step size (if it's bigger it might warp through).

And then you either step all the way through that area and no collision happens. Or you step a few times and you get a collision... in which case you go back half the step size, then forward or back depending on the penetration depth (stepsize halved again) etc.

As soon as you found a time where the distance is <1px you can stop. Resolve the collision and advance the simulation by the remaining time (if you drop this little bit of remaining time, it will feel slower and less real/solid - it's a very subtle thing, but it does make a bit difference).

Well, for the most part there should be only like a dozen passes at most, which should be even fast enough with action script. (Unless there is multiball it's the only thing happening this frame... so it should be alright, I think.)

弾幕 ☆ @mahonnaiseblog
Offline cylab

JGO Ninja


Medals: 55



« Reply #24 - Posted 2007-01-17 12:35:07 »

I am at work now, so I can't check this and I am not much of a mathematician at all, so bear with me, but shouldn't you be able to calculate the intersection by using the balls velocity ray, an assumed intersection point (projecting a rectangular line l from the velocity ray through the origin of your rotating line) and solving t in
1  
t*vb=tan(va*(t-t0))/l

where vb is the balls velocity, va the angle velocity of your rotating line and t0 is the time the rotating line needs from rotating from it's start point to the assumed intersection.


Mathias - I Know What [you] Did Last Summer!
Offline biggeruniverse

Senior Newbie




That's just peanuts to space.


« Reply #25 - Posted 2007-01-17 13:14:40 »

If you weren't at work I would kiss you.

EDIT:
@Markus_Persson: I know the ball flies through. That's why you use the lines and not the ball itself. Given oNyx' wikipedia reference, I've been describing an a priori method whereby you see if a collision will occur in the time step, and where it will occur. Then you place the ball at the position of line intersection (not quite of course, since the intersection is the on the edge of the ball) and give it a new velocity which is the mirror of the current velocity around the perpendicular to the paddle line.

steps:

1. (time step begins) calculate line that represents paddle, given current paddle orientation
2. fire ball velocity ray, get list of collisions, take the first one
3. if it intersects the paddle line (or any line technically, but the paddle line is special)
    place the ball at the intersection point, set new velocity, add paddle angular velocity to ball linear velocity
4. else update ball position by ball velocity
5. (time step ends)

And what do you mean pretending won't work? The entire thing is about pretending! Tongue
Offline cylab

JGO Ninja


Medals: 55



« Reply #26 - Posted 2007-01-17 14:01:28 »

If you weren't at work I would kiss you.
Be careful teasering me *blink*  Wink

Mathias - I Know What [you] Did Last Summer!
Offline Markus_Persson

JGO Wizard


Medals: 16
Projects: 19


Mojang Specifications


« Reply #27 - Posted 2007-01-17 14:12:21 »

I don't get it.. could you elaborate?

 Cheesy

Play Minecraft!
Offline jojoh

JGO Knight


Medals: 5
Projects: 7


games4j.com


« Reply #28 - Posted 2007-01-17 15:18:58 »

Interesting topic. Can't say that I have completely understood everything that has been written so far... I assume that you are just trying to detect collision and not necessarily at what exact time between two frame updates, right? I don't think a player will detect a 1/50th of a sec error Smiley

If so, couldn't you represent the flipper as one sphere at the pivoting axle, and one smaller sphere at the tip (if you want a rounded end of the flipper) and then two line segments connecting the tangents of the spheres.
Calculate a ball movement line segment from balls previous position to balls new position.
Then you can just do:
an intersection test between the ball and the flipper line segments (in case it currently is colliding)
intersections test between ball movement line segment and flipper line segments (in case it is "moving through" the flipper)
intersection test between flipper spheres (one at a time) and the ball movement line segment, but add ball radius to the flipper sphere. (in case it hits one of the ends)

You probably have to move flipper, do tests, move ball, do tests, to be sure to not miss any collisions.

You will naturally have to move the ball out of the flipper and then bounce ball and add the speed generated by the flipper. If you don't add the speed generated by the flipper, then you might get multiple collisions with one flipper press, and that would give very weird bouncing as result.

Hmmm really difficult to explain it without writing it on paper  Tongue  But it is a quite straight forward.

Let us know how you solve it in the end, and get the game ready soon. Getting eager to test it now Smiley

Offline cylab

JGO Ninja


Medals: 55



« Reply #29 - Posted 2007-01-17 15:54:09 »

This is hard without a drawing (so my first post was actually wrong, but it might be the right direction), so recall the previous image of the process:


Let's start with the rightmost figure and assume the angle between the projected ray (in the direction of the balls movement) and paddle is rectangular. You can find the intersection point between the ray and the paddle by using some vector math (I have no book at hand, so...) regarding rectangular aligned vector equations.

Now the ball needs some time to travel (at it's known speed) to this intersection point. Also the paddle needs some time to rotate (at it's known angle speed) to it's position rectangular to the ray. In an ideal situation this times are equal, meaning that the ball hits the paddle while it is rectangular to the balls directional vector (the ray).

Unfortunately this might be the less likely situation, so the other figures come into play. At any given time (exept the ideal above) there is a distance between the ball and the projected intersection. This distance is minimized by the ball moving towards the paddle and the paddle rotating towards the ball. If you take our assumed rectangular intersection as a subsidiary line you can form a rectangular triangle between this line and the paddle. Now you can use the trigonometrical function
1  
tan(angle)=o/a (a:adjacent/o:opposite leg)

You know the angle speed (va) the paddle is rotating, you can use this like
1  
tan(va*t)=o/a

Since you need to know the distance the projected intersection point "travels" on the balls ray, you need to calculate the opposite leg o, which is
1  
o=tan(va*t)*a

So we have one part of the equation. Remember: a is the distance between the assumed rectangular intersection and the origin.

The other part of the equation is the distance the ball is travelling in a given time, which is easy:
1  
d=vb*t (vb is the speed of the ball)


To determine where the ball and the paddle meet, you have to calculate the distance between the ball and the projected paddle line at time 0 (using vector math); lets call it d0. Now this distance has to be equal to the distance travelled by the intersection point on the paddle and the distance travelled by the ball:
1  
d0-(tan(va*t)*a)-vb*t=0


You have to solve this to t Tongue, which should be the time, when the ball and the paddle meet. Afterwards you can use t inserted in vb*t to get the accurate intersection point.

Keep in mind, that I may have made errors and that it assumes a paddle of infinite length (you have to test if the intersection point is on the finite paddle afterwards). Also you might need some case differentiation, since tan is not a continious function.

Mathias - I Know What [you] Did Last Summer!
Pages: [1] 2
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

rwatson462 (28 views)
2014-12-15 09:26:44

Mr.CodeIt (19 views)
2014-12-14 19:50:38

BurntPizza (35 views)
2014-12-09 22:41:13

BurntPizza (70 views)
2014-12-08 04:46:31

JscottyBieshaar (32 views)
2014-12-05 12:39:02

SHC (44 views)
2014-12-03 16:27:13

CopyableCougar4 (40 views)
2014-11-29 21:32:03

toopeicgaming1999 (108 views)
2014-11-26 15:22:04

toopeicgaming1999 (94 views)
2014-11-26 15:20:36

toopeicgaming1999 (29 views)
2014-11-26 15:20:08
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!