cylab


«
Posted
20090316 12:45:35 » 

I am ashamed to have to ask such questions, since all this was covered in my math classes (but 10 years ago) and I hate to have become such a dumb blockhead after multiple years of j2ee development, but... Say there is a train at point p0 travelling at speed v0 (which might be 0!) and has to reach a point p1 in constant time T. How would I compute the minimum needed acceleration ac and deceleration dc to reach p1 in exactly T with the constraints that ac <= dc and min(ac+dc). Any pointers on how to solve such problems (fast)? And for alternative ideas: the real problem is, that I have to smooth abruptly changing input values to produce a smooth 2dcurve y' over t where y is only accessible locally at t (I can't query t+n, but could perhaps cache some tn).

Mathias  I Know What [you] Did Last Summer!



pjt33


«
Reply #1  Posted
20090316 13:24:38 » 

Say there is a train at point p0 travelling at speed v0 (which might be 0!) and has to reach a point p1 in constant time T. How would I compute the minimum needed acceleration ac and deceleration dc to reach p1 in exactly T with the constraints that ac <= dc and min(ac+dc). Any pointers on how to solve such problems (fast)? s = ut + ½at² Did you want an additional constraint that v(T) = 0? And for alternative ideas: the real problem is, that I have to smooth abruptly changing input values to produce a smooth 2dcurve y' over t where y is only accessible locally at t (I can't query t+n, but could perhaps cache some tn). Use a spring model? But that's a rather short description, and I suspect that more detail will be needed to give a good answer. To be precise: given streaming input y(t) and assuming output y'(t), what is the function you're trying to minimise and under what constraints?




CommanderKeith


«
Reply #2  Posted
20090316 13:28:39 » 

Haha, while I was typing pjt33 had the same idea...
s = ut + (1/2)*at^2
Solving for a, your unknown,
a = 2*(s  ut)/t^2




Games published by our own members! Check 'em out!


cylab


«
Reply #3  Posted
20090316 15:49:06 » 

See the attachment for a viusualization what I want to do. The upper curve is the simple case, while the lower represents the case where the input is changing unpredictable. The red curve is the input, the green the desired output. The input is not sampleable (does this word exist? ) for t+n, but I could cache the input for tn (more than one cached sample is undesired but possible). The input is sampled once per frame (so the sample period might be varying due to rendering time). The output of this query should be the smoothed value at sample time.

Mathias  I Know What [you] Did Last Summer!



ryanm


«
Reply #4  Posted
20090316 16:15:35 » 

For the sample smoothing, what you are after is a lowpass filter. That page deals mainly with signal processing electronics guff, but look here for more useful information.




cylab


«
Reply #5  Posted
20090316 16:23:02 » 

OMG I feel so dumb. Thank you!!! Hope nobody noticed that I have a degree in Electrical Engineering

Mathias  I Know What [you] Did Last Summer!



h3ckboy


«
Reply #6  Posted
20090316 16:26:11 » 

OMG I feel so dumb. Thank you!!! Hope nobody noticed that I have a degree in Electrical Engineering know the feeling lol




cylab


«
Reply #7  Posted
20090316 16:34:11 » 

know the feeling lol Thanks

Mathias  I Know What [you] Did Last Summer!



cylab


«
Reply #8  Posted
20090318 13:55:42 » 

For the sample smoothing, what you are after is a lowpass filter. That page deals mainly with signal processing electronics guff, but look here for more useful information. While theoretically the right idea, the result is not what I am looking for (see attachment), so I am back to the acceleration deceleration thingy... Haha, while I was typing pjt33 had the same idea...
s = ut + (1/2)*at^2
Solving for a, your unknown,
a = 2*(s  ut)/t^2
This would not be entirely correct, since this assumes that the acceleration is equal to the deceleration. Should be more lke s = v0 * t0 + a1 * t^2 + a2 * (Tt)^2 I have s, v0, t0 and T. I need a1, a2 and t under the constraints that (Tt) >= 0, a1 >= 0, a2 <= 0, v(T)=0 and min(a1 + a2). The problem is how to solve the min constraint... :/

Mathias  I Know What [you] Did Last Summer!



ryanm


«
Reply #9  Posted
20090318 15:01:44 » 

You can get the transitions you are after by jiggering with the weighting of the average. Try weighting the most and least recent samples lightly, but samples in the middle more heavily. A linear progression in weighting factors will probably work for you. For instance, say you have the 10 most recent samples: a relative weighting factor array like 1
 [ 1, 3, 5, 7, 9, 9, 7, 5, 3, 1 ] 
would give the desired smoothing.




Games published by our own members! Check 'em out!


DzzD


«
Reply #10  Posted
20090318 15:27:14 » 

maybe what you are looking for is a Polynomial => http://en.wikipedia.org/wiki/Polynomial. you can find a polynomial that lie on any set of points (for any number of point, the difference will be the polynomial "order"), for example if you want a polynomial that go trough 2 points 3 points you will use an equation like : y=ax²+bx+c for three four points ax^3+bx²+cx+d etc... you just have to set the equation and solve it, it will become pretty complexe for a lot of point, but the advantage is that you will have an unic and continuous function y=f(x). for a lot of point you will better use a subset of point like the neigbourgs points and interpolate them. one of interpolation such as the following http://freespace.virgin.net/hugo.elias/models/m_perlin.htm, the cubic interpolation is a polynomial but it only use a subset of neighbourg points. cubic one is polynomial with an order 3: EDIT : little error order 2 => 3 point not 2




cylab


«
Reply #11  Posted
20090318 16:43:25 » 

I tried this using a bezier spline with limited success, but the nature of the input sampling seems to make this too complicated. I may give this another try, but I will try the weighted average and the acelleration thingy first.
Thank you so far.

Mathias  I Know What [you] Did Last Summer!



pjt33


«
Reply #12  Posted
20090318 16:49:15 » 

Looking at your example I think all you want is to find a function f(x) with the following properties: f(0) = 0 f(1) = 1 f'(0) = 0 f'(1) = 1 For all 0 < x < 1, f'(x) > 0
Then you could do a linear transform on f for each segment: if you sample y0 at t0 and y1 at t1 then your output in t0 < t <= t1 is y0 + (y1y0) f((tt0)/(t1t0)).
There are various functions you could choose for f, although the simplest is probably f(x) = sin^2(2x / PI).




cylab


«
Reply #13  Posted
20090318 16:57:26 » 

Look at the first attachment I posted. The 01 sequence is just the simplest case. Usually you get unpredictable input values (by a random function or mouse movement or whatever)

Mathias  I Know What [you] Did Last Summer!



pjt33


«
Reply #14  Posted
20090318 17:38:34 » 

Look at the first attachment I posted. The 01 sequence is just the simplest case. Usually you get unpredictable input values (by a random function or mouse movement or whatever)
I did. I'm not sure what your point is.




cylab


«
Reply #15  Posted
20090318 17:53:41 » 

Maybe I didn't understand your post I don't want to interpolate values and my input values are at arbitrary times with arbitrary numbers. I also might not get, if you think that the curve "jumps" are at sample occasions. If so, that's not true. Assume that the square curve in my example has a period of 2s. So each state lasts for 1s. The values are sampled at a rate of 60 per seconds. So I get 60 0 values and 60 1 values. For every sample I want to return a smoothed value instead of the original 0 or 1 value from the input. So correct me if misunderstand your proposal, but it seems, it would only work for interpolating between sampled inputs or if the inputs don't change while the transition is calculated. Another problem might be, if I use a sinusidal transition, I can't lineary "sweep over" samples lying on the interpolation path without getting an ease in and ease out effect.

Mathias  I Know What [you] Did Last Summer!



pjt33


«
Reply #16  Posted
20090318 21:30:57 » 

I also might not get, if you think that the curve "jumps" are at sample occasions. If so, that's not true.
I think this may be the source of confusion. How do you know the value of the curve other than at sample points? Could you redo your diagram showing where samples are taken?




cylab


«
Reply #17  Posted
20090318 23:49:24 » 

Maybe this sentence wasn't clear. See the second post with an attachment. The red dots are the input samples.

Mathias  I Know What [you] Did Last Summer!



pjt33


«
Reply #18  Posted
20090319 01:06:17 » 

Ah, looking at the maths in the post with the second attachment I think I see what you're trying to do.
At time t0 you have velocity v0. You accelerate until t0 + t with acceleration a1. You then accelerate until t0 + T with acceleration a2. At t0 + T the velocity is zero. The distance travelled from t0 to t0 + T is s.
Then s = v0 t + ½ a1 t² + ½ (T  t) (v0 + a1 t) and (T  t) a2 =  (v0 + a1 t)
Since a1 > 0 and a2 < 0, a1 + a2 is a1  a2 = (a1 T + v0) / (T  t). Rearrange the expression for s to get a1 as a function of t  if I'm not mistaken it's a1 = (2 s  3 v0 t + T) / (Tt). Substitute in: the expression you want to minimise is now (2 s  2 v0 t + T) / (Tt  t²) Differentiate with respect to t and set equal to zero and you should have a quadratic in t to solve.




pjt33


«
Reply #19  Posted
20090320 10:39:46 » 

Is the absence of response an indication that the problem is solved or that you didn't notice my last post?




cylab


«
Reply #20  Posted
20090320 12:14:39 » 

Is the absence of response an indication that the problem is solved or that you didn't notice my last post?
I didn't notice your last post. The forums "show unread posts" is notoriously broken... thanks for the input. I'll try it on the weekand and will give some feedback.

Mathias  I Know What [you] Did Last Summer!



Jono


«
Reply #21  Posted
20090321 19:37:03 » 

At time t0 you have velocity v0. You accelerate until t0 + t with acceleration a1. You then accelerate until t0 + T with acceleration a2. At t0 + T the velocity is zero. The distance travelled from t0 to t0 + T is s.
If I've read those graphs correctly, in the second diagram attached the final velocity is not zero. It is equal to the starting velocity of the next segment. Also, A1 > 0 is not necessarily true, since he's shown it moving downward as well =( As it's described there is an infinite number of solutions. Some extra constraints, like t = T/2 (make the acceleration and deceleration times the same) might help, but depending on the number of segments may still have no unique solution. As it stands I'd get all the constraints together and find the least squares solution: en.wikipedia.org/wiki/Least_squaresEdit: Just reread the first post and noticed that you want min(ac+dc). Least squares isn't right here.. this is a linear programming problem.




Eli Delventhal


«
Reply #22  Posted
20090321 20:15:35 » 

I just did this the other day, actually, and needed to spend 20 minutes figuring it out with pencil and paper. However, my case was a little simpler so I just used a summation to find it. d = v + va + v2a + v3a + v4a ... Basically because you're decelerating by a every time then each timestep you velocity will be a multiple of a smaller. That ends up simplifying to d = nv  s(n1)*a Where s(n1) is the summation (sigma) from n1 to 1. Then I could easily solve for the deceleration knowing the distance I wanted, or I could also solve for a depending upon how long I wanted to take to stop by knowing that v = d/t.




Jono


«
Reply #23  Posted
20090322 19:40:39 » 

I just did this the other day, actually, and needed to spend 20 minutes figuring it out with pencil and paper. However, my case was a little simpler so I just used a summation to find it. d = v + va + v2a + v3a + v4a ... Basically because you're decelerating by a every time then each timestep you velocity will be a multiple of a smaller. That ends up simplifying to d = nv  s(n1)*a Where s(n1) is the summation (sigma) from n1 to 1. Then I could easily solve for the deceleration knowing the distance I wanted, or I could also solve for a depending upon how long I wanted to take to stop by knowing that v = d/t. Yeah, that's the discrete (sampled) version of the formula pjt33 posted earlier: s = ut + (1/2)*at^2 The summation s(n1) can be simplified to n(n1)/2, and then the relation between the two equations becomes more obvious.




pjt33


«
Reply #24  Posted
20090323 17:32:04 » 

If I've read those graphs correctly, in the second diagram attached the final velocity is not zero. Yes, indeed. That's why I said "Looking at the maths in the post...", which say "v(T)=0" and are inconsistent with the diagram.




cylab


«
Reply #25  Posted
20090323 18:52:41 » 

The final velocity after T is 0, but only in case there are no more updates til t = T is reached. Otherwise I would take the current velocity as v0 and restart the calculation. I still had no time to have another shot on this, but I will post with the results of the various strategies in this thread, if I get at it again.

Mathias  I Know What [you] Did Last Summer!



Jono


«
Reply #26  Posted
20090323 20:43:28 » 

Yes, indeed. That's why I said "Looking at the maths in the post...", which say "v(T)=0" and are inconsistent with the diagram.
Ah, sorry if I took that out of context. The final velocity after T is 0, but only in case there are no more updates til t = T is reached. Otherwise I would take the current velocity as v0 and restart the calculation. I still had no time to have another shot on this, but I will post with the results of the various strategies in this thread, if I get at it again.
So the second diagram doesn't show a sequence of locations that were known ahead of time.. it's showing the results of a sequence of moves where v(T) was expected to be 0, but were often interrupted by the next move. If that's the case  where you just have to solve it one move at a time  then it looks like pjt33 has pretty much got that sorted. I get the feeling that even when v(0) > 0 the min(A1+A2) is when A1 = A2. If so, the equation will simplify a lot.




Eli Delventhal


«
Reply #27  Posted
20090420 21:18:41 » 

Hm, so what about an equation to compute acceleration needed to go from one velocity to another in a given distance? It seems like you should be able to use the above but I'm having trouble solving for it.
Basically, at t(0) the object has v(0), and after going d it has v(f). Those 4 values are known, but I need to know an a that can get me there. I guess it's all a matter of simplifying v to d/t and a to d/t^2 but I'm still having trouble. Any help?




DzzD


«
Reply #28  Posted
20090420 21:43:55 » 

V=V0+t*A knowing V,V0 and t maybe something like that ? A=(VV0)/t EDIT: forget. I miss something in reading .... ... EDIT2:not sure you can solve it for a distance and a time at the same time, cause acceleration give the velocity and is not related to distance, if you compute acceleration based on distance as an input you will need to use V0 , and so you can compute for a given distance and time but also a given initial velocity: A=(2*(dV0*t))/t² or A=(VV0)/t




Eli Delventhal


«
Reply #29  Posted
20090420 22:35:47 » 

V=V0+t*A knowing V,V0 and t maybe something like that ? A=(VV0)/t EDIT: forget. I miss something in reading .... ... Hm I don't think V = V0 + t*A is correct. It should be V = V0 + A + V0 + 2A + V0 + 3A ... v0 + tA which simplifies to V = t*V0 + ((t * (t+1))/2) * A . Even so that doesn't really help, because d is nowhere in this equation. Like say I have the following values: v(0) = 10 m/s v(f) = 2 m/s d = 51 m When we are at t(0), our position is 0. When we are at t(f), our position is 100. Because I had this precalculated, you can see that with an acceleration of 1 m/s we end up at v(f) when we reach d. Time is nowhere in the equation  we don't care how long it takes. v(0) = 10 d(0) = 0 v(1) = 10 d(1) = 9 v(2) = 8 d(2) = 19 v(3) = 7 d(3) = 27 v(4) = 6 d(4) = 33 v(5) = 5 d(5) = 39 v(6) = 4 d(6) = 44 v(7) = 3 d(7) = 48 v( = 2 d( = 51 Maybe someone else can see some pattern in that? It's easy to figure out d or t, but not a when given a d  at least I'm having trouble with it.




