views:

322

answers:

2

Hi, I'm trying to write a method that interpolates from 0 to x (position of an object in one dimension) over time using acceleration at the beginning and deceleration at the end (ease out / ease in) with the only constraints that the total time is provided, as well as the duration of the acceleration and deceleration. the motion should replicate the inertia effect and I'm considering a Hermite curve for the non-linear portions.

double Interpolate(
    double timeToAccel, double timeCruising, double timeToDecel,
    double finalPosition,
    double currentTime)
{
    //...
}

Can someone point me out to a portion of code that does that? I don't know how to integrate the Hermite curve, hence don't know how much I'll move in the accelerating portion or in the decelerating portion, and in turn I can't figure out what will be the speed in the linear portion.

Thanks.

Some reference to illustrate my question.

Edit:

  • start and end speeds are null, and the current time is also part of the parameters in the method, I've updated the signature.
  • basically the idea is to imagine a move at constant speed on a distance d, this gives a total duration. Then we add the acceleration and deceleration phases, while maintaining the same duration, hence we have an unknown new cruise speed to determinate (because we move less in the Hermite phases than in the linear phases they have replaced). Maybe the amount of move lost in the Hermite phases, compared to a linear move of the same duration is the ratio between the top and bottom area in the curves, just an idea from a non expert.

Edit: Roman and Bob10 have provided full working solutions. I implemented the code from Roman. Thanks to you both, guys! I appreciate your perfect support and your detailed solutions, you saved me long searches and trials.

+2  A: 

First, let's make a cubic hermite spline function:

/*
  t  - in interval <0..1>
  p0 - Start position
  p1 - End position
  m0 - Start tangent
  m1 - End tangent
*/
double CubicHermite(double t, double p0, double p1, double m0, double m1) {
   t2 = t*t;
   t3 = t2*t;
   return (2*t3 - 3*t2 + 1)*p0 + (t3-2*t2+t)*m0 + (-2*t3+3*t2)*p1 + (t3-t2)*m1;
}

Now your task is to calculate the p0, p1, m0 and m1 for both ease-in and ease-out portions. Let us add a few variables to make the math a bit easier to write:

double Interpolate(
    double timeToAccel, double timeCruising, double timeToDecel,
    double finalPosition,
    double currentTime) {

    double t1 = timeToAccel;
    double t2 = timeCruising;
    double t3 = timeToDecel;
    double x = finalPosition;
    double t = currentTime;

We need to specify where should the object be when it stops accelerating and starts decelerating. You can specify these however you please and still produce a smooth movement, however, we would like a somewhat "natural" solution.

Let's assume that the cruising speed is v. During crusing, the object travels distance x2 = v * t2. Now, when the object accelerates from 0 to speed v, it travels distance x1 = v * t1 / 2. Same for deceleration x3 = v * t3 / 2. Put all together:

x1 + x2 + x3 = x

v * t1 / 2 + v * t2 + v * t3 / 2 = x

From that we can calculate our speed and the distances:

    double v = x / (t1/2 + t2 + t3/2);
    double x1 = v * t1 / 2;
    double x2 = v * t2;
    double x3 = v * t3 / 2;

And now that we know everything, we just feed it into our cubic hermite spline interpolator

    if(t <= t1) {
       // Acceleration
       return CubicHermite(t/t1, 0, x1, 0, x2/t2*t1);
    } else if(t <= t1+t2) {
       // Cruising
       return x1 + x2 * (t-t1) / t2;
    } else {
       // Deceleration
       return CubicHermite((t-t1-t2)/t3, x1+x2, x, x2/t2*t3, 0);
    }
}

I tested this in Excel, here's the equivalent VBA code to play with. There are some divisions by zero for boundary conditions, I leave fix to this as an excercise to the reader


Public Function CubicHermite(t As Double, p0 As Double, p1 As Double, _
m0 As Double, m1 As Double) As Double
   t2 = t * t
   t3 = t2 * t
   CubicHermite = (2 * t3 - 3 * t2 + 1) * p0 + _
(t3 - 2 * t2 + t) * m0 + (-2 * t3 + 3 * t2) * p1 + (t3 - t2) * m1
End Function

Public Function Interpolate(t1 As Double, t2 As Double, t3 As Double, _
x As Double, t As Double) As Double
    Dim x1 As Double, x2 As Double, x3 As Double

    v = x / (t1 / 2 + t2 + t3 / 2)
    x1 = v * t1 / 2
    x2 = v * t2
    x3 = v * t3 / 2

    If (t <= t1) Then
       Interpolate = CubicHermite(t / t1, 0, x1, 0, x2 / t2 * t1)
    ElseIf t <= t1 + t2 Then
       Interpolate = x1 + x2 * (t - t1) / t2
    Else
       Interpolate = CubicHermite((t-t1-t2)/t3, x1+x2, x, x2/t2*t3, 0)
    End If
End Function
Roman Zenka
Roman, thanks. Correct, the problem is how to determine the amount of move in the linear portion, to obtain the cruise speed, and in turn we are back to the accel phase and its final speed (the reciprocal for the decel phase). All seems to be interlocked. My guess is that we need to integrate the curves and then solve an equation where the result is the whole time of the move. But I'm far from being a mathematician, so I may be wrong. I searched hard on the net, but so far no lead to pursue.
742
@Roman, I think you may have an error here. You used x = v*t/2, but this is usually used for constant acceleration, and you're using a cubic equation which doesn't match this criterion. I would be interested to see whether the result of this program is consistent with the input assumptions.
tom10
Thanks you very much again. I don't understand how to determinate the tangents for the curve in the Interpolate function. I read a piece of difficult to understand (for me) theory where I can see m0 = c and m1 = 3a+2b+c, but can't figure out what is the visual interpretation of tangents parameters. Is that the slope at start and end points? I was expecting both slopes equal to 0 (horizontal). Or are they horiz, and the value is rather the length of the vectors? I need this to manage tangent values in case one or two of the phases (accel, cruise, decel) are not used (duration = 0). Thks.
742
@tom10, I plotted the first and second derivative for my solution and to my surprise the acceleration (second derivative) is constant! This is because the tangent is exactly double the end point position, so the linear terms just cancel each other out. This solution is therefore IDENTICAL to Tom's. I think it has something to do with the fact that for given first derivatives and endpoints, there is only a single third order multinomial that satisfies the boundary conditions. So we were meant to find the same solution. :)
Roman Zenka
@742: Yes. It is the slope of start and end points. Keep in mind that the end point of the acceleration part follows by the cruise part, which is sloped (see the picture by tom10 below). You are plotting position x against time t.
Roman Zenka
@ Roman. Ok I fixed small issues in my implementation and this works now perfectly based on your code and your explanations. I'm truly grateful to you and Tom. I'd like to include with your permission your name in the credit page of the application. Let me know if you're ok, the text could be something like "Roman Zenka -- http://stackoverflow.com/users/204984/roman-zenka -- for the smooth interpolation algorithm" or something more appropriate of your choice.
742
@742 Sure, that's fine. I'm glad you found it useful! BTW, if performance is ever an issue, I am sure the code could be optimized quite a bit (inlining the CubicHermite and removing the terms where you multiply by zero).
Roman Zenka
+3  A: 

This is straightforward using normal constant acceleration. Then the question becomes what velocity (v) do you need to accelerate to in order to complete the trip in the right amount of time, and this will tell you the acceleration you need to get to that velocity.

If the total time is t_t and the time of acceleration is t_a, then you have the distance traveled as the two accelerating and decelerating parts, and the constant velocity part:

x = 2*(a*t_a*t_a/2) + v*(t_t-2*t_a)

This can be solved for the acceleration by subbing in v=a*t_a, to find

a = x/(t_a*(t_t - t_a))

Here's some Python code that uses and plots the result of these equations, that shows both how to use the equations and what the result looks like:

from pylab import *

t_a, t_t, D = 3., 10., 1.  # input values

a = D/(t_a*(t_t - t_a))
segments = (t_a, a), (t_t-2*t_a, 0.), (t_a, -a)  # durations and accelerations for each segment

t0, x0, v0 = 0.0, 0.0, 0.0  #initial values for the segment
tdata, xdata = [], []
for t_segment, a in segments: # loop over the three segments
    times = arange(0, t_segment, .01)
    x = x0 + v0*times + .5*a*times*times
    xdata.append(x)
    tdata.append(times+t0)
    x0 = x[-1] # the last x calculated in the segment above
    v0 += a*t_segment
    t0 += t_segment

plot(tdata[0], xdata[0], 'r', tdata[1], xdata[1], 'r', tdata[2], xdata[2], 'r')
xlabel("time")
ylabel("position")
show()

alt text

tom10
Hi Tom, thanks a lot. If I got the idea correctly the acceleration of the accelerating and decelerating curves is assumed to be a constant, and because this is a constant, all is going to be solved by determining it (and in turn v) However I'm not sure Hermite curve are part of the set of curves with constant second derivative. Seems to me this would be ok only for a parabola (again: I've very limited skills). If I'm wrong, and Hermite are actually part of such curves, then could you kindly tell me how to convert the acceleration computed above into Hermite parameters? Thanks.
742
Correct, this is smooth ease in, ease out, but not a Hermite curve. Generally with polynomial solutions, it's best to pick the lowest order curve that solves the problem. I can imagine a reason one might want other curves, but your problem is underspecified for a Hermite curve, so I assumed you didn't really want one.
tom10
I would think the movement might be smoother if you used higher-order multinomials. What you propose would lead to a curve with discontinuous second order derivative.
Roman Zenka
A curve that has continuous first derivatives and discontinuous second derivatives still looks smooth. Both splines and bezier curves use this to make interesting yet smooth curves. If the trajectory were a car and you were in it, you could feel the discontinuous second derivative as a change of force, but the trajectory would be smooth. I'm not saying this will solve your problem, but it will look smooth. If it doesn't solve your problem you need to further specify the problem because as stated there aren't enough parameters.
tom10
Guys, thanks for your time in discussing the matter, I appreciate. My need is to simulate a camera move along a line segment, changing linearly both the position and the orientation, My current solution does that exactly by a linear interpolation of the six parameters individually (x,y,z and 3 Euler angles). My current request is related to adding the ease out / ease in feature. I picked the Hermite curve idea by looking at related discussion and also at the definition of what seems to be a well-known animal in the area, the Smoothstep function (http://en.wikipedia.org/wiki/Smoothstep)...
742
... Does my problem needs a Hermine curve or a simpler one, I don't know. Tom what you provided is a parabola, and I can try that first. Is it correct to use x = k*a*currentTime with 'k' being some constant, and 'a' the acceleration computed as you described? What would be you suggestion for the type of curve in my case? I've read that with Hermine you can tied up two linear move (two segments) with a continuity by selecting curve parameters ensuring you have the same inbound speed on the first curve than the outbound speed on the second, but this is not part yet of my project requirements.
742
@742: Do not interpolate camera movement using x, y, z and three euler angles. Do quaternion interpolation, solves gimbal lock problem.
Roman Zenka
@742 - I've added some code that demonstrates how to use the equation and what the result looks like.
tom10
@ Roman: In my case the user doesn't manipulate directly angles, they are only used for describing and storing the orientation in "human" form. I've a custom trackball to change orientation, it is based on two orthogonal vectors (look direction and up direction), the vectors are maintained orthogonal while rotated by the user, and then converted back into Euler angles. I don't experience gimbal lock effects, even when pitch is +/- 90°. I've had GL issues at the beginning with a previous version of the trackball manipulating directly Euler angles, so I change the logic of the trackball.
742
@Tom: Thanks a lot. I'm starting with Roman's cspline, and will let you know both the result. I reimplemented his code in the context of my use, but I've some trouble to determine the curve parameters. Will keep everybody posted.
742
@Tom, this is very elegant and simple solution, my only problem with it is that you calculate the position X by adding small deltas, so you would gather imprecisions along the way. Your solution also forces you to iterate through the movement, while I can calculate the desired position directly. I am however quite sure that it would be easy to convert your solution to do direct calculation as well.
Roman Zenka
@Roman, If this is your only issue with my solution you will like it well indeed, since it's NOT the case that I'm adding small deltas. I only calculate along the curve so I can plot along the curve; the loop in my code only loops three times, one for each section, since each has different parameters, the dt is the time for each segment, and the += is to set v and t to the new values after completing an entire segment. That is, I'm calculating everything directly for each of the three segments and not integrating up small deltas.
tom10
@Tom, I am not familiar with language of your choice, I just saw the v0 += a*dt which looked like you are integrating. I think that if I optimized the cubic hermite spline, many terms would go away and I would arrive at identical equations to yours.
Roman Zenka
@Roman, Yes, it was probably a bad choice of symbols on my part, and I see how it might look like an Euler integration. I'll edit my code to fix this. I wonder if you arrivee at identical equations because of the assumption that x = v*t/2 (which is the result for a constant acceleration and not a general cubic)?
tom10
@Tom: the code from Roman works for me and I selected his answer as the solution. . However I know your solution is similar and you helped; I'm frustrated to have only only "good answer" possibility. As I mention in a comment to Roman, I'll include with your permission a reference to you in my credits page. Just give me a name / an url you would like to appear, for example "Tom -- http://stackoverflow.com/users/102302/tom10" or something else suitable. Thanks
742
@742. It's thoughtful of you to mention me in your credits, thanks. My SO address seems like a good choice. Good luck with it.
tom10