03-29-08 - 2

cubic maxaccel maths

I figure I should write up the maths for the record since I've described it previously but haven't been totally clear. There's an implementation in testdd you can look at.

The goal is to make a curve that goes from initial position & velocity {X0,V0} to final position & velocity {X1,V1}. Position and velocity are N-d vectors. Traveling this curve, you should at no point exceed the maximum acceleration "m". m is a scalar. I'll use caps for vectors and lower case for scalars.

The lowest order polynomial curve that fits these condition is a cubic. A parametric cubic has 4 vector coefficients which can be used to fit the end position & velocities. It also has a free scalar - the time to travel the parametric interval from 0 to 1. This duration can be fit to "m" the max acceleration.

Using the Bezier form we have :

B(s) = B0 *(1-s)^3 + B1 *3*(1-s)^2*s + B2 *3*(1-s)*s^2 + B3 *s^3

s = (t / d) is parametric time
t = real time
d = duration of curve
And fitting to the end conditions :
B0 = X0
B1 = X0 + V0*(d/3)
B2 = X1 - V1*(d/3) 
B3 = X1
Now, the velocity of a cubic curve is quadratic, the acceleration is linear. The means the highest acceleration on the interval [0,1] is either at 0 or 1. So we have to just check the acceleration of the two end points :
A(0) = 6*(B0 + B2 - 2B1)/d^2
A(1) = 6*(B3 + B1 - 2B2)/d^2
Now you have to solve both end points and use the shorter of the two durations. You may want to early out to handle the trivial case, if you can use a tiny value for "d" and not exceed maximum acceleration at either end point, then just return. In fact "tiny value" could be the duration of the frame - if you can step the whole curve in one frame then just do that.

If we just consider A(0) for now we have to solve :

|A(0)| = m
m = max accel parameter


A(0)*A(0) = m^2
(B0 + B2 - 2B1)^2 = m^2 * d^4/36
( (X1-X0) - d*(2V0 + V1)/3 )^2 = (m^2/36) * d^4
You can expand out the dot product and you are left with a quartic polynomial in the duration "d". Solve this polynomial. There are in general 4 complex roots of a quartic. You must choose the lowest magnitude positive real root. There should always be a positive real root because all the coefficients are real.

Note that the quartic arose because A was a vector - if we want to just solve the 1d problem it's much easier, because the equation in d is just quadratic. Note that you can not just solve the 1d problem and run it indepedently on each dimension of a vector, because that allows maxaccel in each dimension seperately and gives you curves that are obviously axis-aligned (it breaks rotational invariance of your space).

Once you have solved for the shortest duration "d" which gives you a curve that doesn't exceed maxaccel, you can now simply step along the curve. Note that we are not simply applying a force, but taking an exact step along the curve, you evaluate the position and velocity from the curve at the end of your current time step. This is equivalent to doing an exact integration with a force that is changing.

NOTE : we are not solving this curve once and hanging on to it; our system has zero state. A new curve is solved each frame using the current position and velocity. Because the cubic is exactly constrained, if the external conditions are not changing, then solving each frame will produce exactly the same path as just following the original solution the whole way. If the external conditions are changing, then the path changes smoothly.

ADDENDUM : talked to Drew about this, he made me aware of two issues. One thing I should state clearly : when you are changing the duration of the cubic, you are not just changing how long you take to follow the same curve. Obviously changing the rate of change of the parameter would change the acceleration, but that would also change the start & end velocity. In the math we did here previously, we are scaling the duration of the curve while keeping the real-time start & end velocity constant, which means that we are changing the parametric velocity of the ends of the curve. That means the curve actually has a different shape as you scale the duration.

The other note is that it might be possible to have seperate accel/decel parameters by using a different "max accel" parameter for A(0) and A(1), since you are generally at max accel at the start and decelerating at the end. That's not necessarilly true if the start & end velocities are not zero so maybe a bit more thought is needed, but in general the idea of using different maxaccel to get a control over accel & decel seems possible.

BTW you can also acheive the same purpose using a piecewise quadratic. To use a piecewise quadratic you have 3 phases of travel :

phase 1 : accelerate up to max velocity
phase 2 : travel linearly at max velocity
phase 3 : decelerate to hit target
So in phase 1 you are fitting the end points {X0,V0} and ending max velocity. The maths for piecewise quadratic are slightly simpler, but the logic is quite a bit more complex because you have to figure out what phase to use and also handle the degenerate cases where phase 2 is not needed because you're close enough to the target.

I find the cubic is more appealing because you can just do the math and get an answer. There is one advantage of the piecewise solution, which is that you can have seperate max accel parameters for the acceleration and deceleration parts of the curve, which can give you non-time-symmetric curves.

No comments:

old rants