20
\$\begingroup\$

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?

\$\endgroup\$
26
\$\begingroup\$

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);
\$\endgroup\$
  • 1
    \$\begingroup\$ Hi. I am reading your answer,but I can't understand what is L. What do you mean by "which should be computed according to the frame duration"? \$\endgroup\$ – Michael IV Jan 1 '18 at 1:28
  • \$\begingroup\$ Is L = curve segment length? \$\endgroup\$ – Michael IV May 6 '18 at 9:49
  • \$\begingroup\$ L is the curve length, i.e. the distance you want to travel during the current frame. \$\endgroup\$ – sam hocevar May 10 '18 at 21:48
  • \$\begingroup\$ OK,I see now. And you think this approximation is as good as curve splitting technique from the answer below? \$\endgroup\$ – Michael IV May 11 '18 at 4:16
  • \$\begingroup\$ When L is sufficiently small, this approximation is actually always more accurate than the answer below, yes. It also uses less memory (because it uses the derivative instead of storing all point values). When L starts to grow, you can use the technique I suggest at the end. \$\endgroup\$ – sam hocevar May 13 '18 at 23:30
6
\$\begingroup\$

You need to reparamaterize the curve. The easiest way to do this is to calculate the arc lengths of several segments of the curve and use these to figure out where you should sample from. For example, maybe at t=0.5 (halfway through), you should pass s=0.7 to the curve to get the "halfway" position. You need to store a list of arc lengths of various curve segments to do this.

There are probably better ways, but here's some very simple C# code I wrote to do this in my game. It should be easy to port to Objective C:

public sealed class CurveMap<TCurve> where TCurve : struct, ICurve
{
    private readonly float[] _arcLengths;
    private readonly float _ratio;
    public float length { get; private set; }
    public TCurve curve { get; private set; }
    public bool isSet { get { return !length.isNaN(); } }
    public int resolution { get { return _arcLengths.Length; } }

    public CurveMap(int resolution)
    {
        _arcLengths = new float[resolution];
        _ratio = 1f / resolution;
        length = float.NaN;
    }

    public void set(TCurve c)
    {
        curve = c;
        Vector2 o = c.sample(0);
        float ox = o.X;
        float oy = o.Y;
        float clen = 0;
        int nSamples = _arcLengths.Length;
        for(int i = 0; i < nSamples; i++)
        {
            float t = (i + 1) * _ratio;
            Vector2 p = c.sample(t);
            float dx = ox - p.X;
            float dy = oy - p.Y;
            clen += (dx * dx + dy * dy).sqrt();
            _arcLengths[i] = clen;
            ox = p.X;
            oy = p.Y;
        }
        length = clen;
    }

    public Vector2 sample(float u)
    {
        if(u <= 0) return curve.sample(0);
        if(u >= 1) return curve.sample(1);

        int index = 0;
        int low = 0;
        int high = resolution - 1;
        float target = u * length;
        float found = float.NaN;

        // Binary search to find largest value <= target
        while(low < high)
        {
            index = (low + high) / 2;
            found = _arcLengths[index];
            if (found < target)
                low = index + 1;
            else
                high = index;
        }

        // If the value we found is greater than the target value, retreat
        if (found > target)
            index--;

        if(index < 0) return curve.sample(0);
        if(index >= resolution - 1) return curve.sample(1);

        // Linear interpolation for index
        float min = _arcLengths[index];
        float max = _arcLengths[index + 1];
        Debug.Assert(min <= target && max >= target);
        float interp = (target - min) / (max - min);
        Debug.Assert(interp >= 0 && interp <= 1);
        return curve.sample((index + interp + 1) * _ratio);
    }
}

Edit: It's worth noting that this won't give you the exact arc length, since it's impossible to get the arc length of a cubic curve. All this does is estimate the length of the various segments. Depending on how long the curve is, you may need to increase the resolution to prevent it from changing speeds when it reaches a new segment. I usually use ~100, which I have never had a problem with.

\$\endgroup\$
0
\$\begingroup\$

A very lightweight solution is to approximate the speed rather than approximating the curve. Actually this approach is independent of the curve function and enables you to use any exact curve instead of using derivatives or approximations.

Here is the code for C# Unity 3D:

public float speed; // target linear speed

// determine an initial value by checking where speedFactor converges
float speedFactor = speed / 10; 

float targetStepSize = speed / 60f; // divide by fixedUpdate frame rate
float lastStepSize;

void Update ()
{   
    // Take a note of your previous position.
    Vector3 previousPosition = transform.position;

    // Advance on the curve to the next t;
    transform.position = BezierOrOtherCurveFunction(p0, p1, ..., t);

    // Measure your movement length
    lastStepSize = Vector3.Magnitude(transform.position - previousPosition);

    // Accelerate or decelerate according to your latest step size.
    if (lastStepSize < targetStepSize) 
    {
        speedFactor *= 1.1f;
    }
    else
    {
        speedFactor *= 0.9f;
    }

    t += speedFactor * Time.deltaTime;
}

Although the solution is independent of the curve function, I wanted to note it here as I was also looking for how to achieve constant speed on a Bezier curve, and then I come up with this solution. Considering the popularity of the function this may be helpful here.

\$\endgroup\$
-3
\$\begingroup\$

I don't know anything about cocos2, but a bezier curve is a kind of parametric equation, so you should be able to get your x and y values in terms of time.

\$\endgroup\$
  • 4
    \$\begingroup\$ Add an example + more explanation and this would be a good answer. \$\endgroup\$ – MichaelHouse Apr 9 '12 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.