ios - How to achieve uniform speed of movement on a bezier curve?

I'm trying to move an image along Bezier curve. This is how I do it:

- (void)startFly
{    
 [self runAction:[CCSequence actions:
             [CCBezierBy actionWithDuration:timeFlying bezier:[self getPathWithDirection:currentDirection]],
             [CCCallFuncN actionWithTarget:self selector:@selector(endFly)],
             nil]];

}

My issue is that the image moves not uniformly. In the beginning it's moving slowly and then it accelerates gradually and at the end it's moving really fast. What should I do to get rid of this acceleration?

Answer

It is possible to approximate a solution to this problem for most parametric trajectories. The idea is the following: if you zoom deep enough on a curve, you cannot tell the curve itself from its tangent at that point.

By making this assumption, there is no need to precompute anything more than two vectors (three for cubic Bezier curves, etc.).

So for a curve \$M(t)\$ we compute its tangent vector \$\frac{dM}{dt}\$ at point \$t\$. The norm of this vector is \$\lVert \frac{dM}{dT} \rVert\$ and thus the distance traveled for a duration \$\Delta t\$ can be approximated as \$\lVert \frac{dM}{dT} \rVert \Delta t \$. It follows that a distance \$L\$ is traveled for a duration \$L \div \lVert \frac{dM}{dT} \rVert\$.

Application: quadratic Bezier curve

If the control points of the Bezier curve are \$A\$, \$B\$ and \$C\$, the trajectory can be expressed as:

$$ \begin{align} M(t) &= (1-t)^2A + 2t(1-t)B + t^2C \\ &= t^2(A - 2B + C) + t(-2A + 2B) + A \end{align} $$

So the derivative is:

$$ \frac{dM}{dt} = t(2A - 4B + 2C) + (-2A + 2B) $$

You just need to store vectors \$\vec v_1 = 2A - 4B + 2C\$ and \$\vec v_2 = -2A + 2B\$ somewhere. Then, for a given \$t\$, if you want to advance of a length \$L\$, you do:

$$ t = t + {L \over length(t \cdot \vec v_1 + \vec v_2)} $$

Cubic Bezier curves

The same reasoning applies to a curve with four control points \$A\$, \$B\$, \$C\$ and \$D\$:

$$ \begin{align} M(t) &= (1-t)^3A + 3t(1-t)^2B + 3t^2(1-t)C + t^3D \\ &= t^3(-A + 3B - 3C + D) + t^2(3A - 6B + 3C) + t(-3A + 3B) + A \end{align} $$

The derivative is:

$$ \frac{dM}{dt} = t^2(-3A + 9B - 9C + 3D) + t(6A - 12B + 6C) + (-3A + 3B) $$

We precompute the three vectors:

$$ \begin{align} \vec v_1 &= -3A + 9B - 9C + 3D \\ \vec v_2 &= 6A - 12B + 6C \\ \vec v_3 &= -3A + 3B \end{align} $$

and the final formula is:

$$ t = t + {L \over length(t^2 \cdot \vec v_1 + t \cdot \vec v_2 + \vec v_3)} $$

Accuracy issues

If you are running at a reasonable framerate, \$L\$ (which should be computed according to the frame duration) will be sufficiently small for the approximation to work.

However, you may experience inaccuracies in extreme cases. If \$L\$ is too large, you can do the computation piecewise, for instance using 10 parts:

for (int i = 0; i < 10; i++)
    t = t + (L / 10) / length(t * v1 + v2);