3
\$\begingroup\$

Is it possible to get a constant speed movement over a Bézier curve when its points are not kept symmetrical ?

Here white square (almost) moves at constant speed. (red and green squares are control points) enter image description here

Here travel time is much longer in the green part than in the red part. (control points moved) enter image description here

Curve generation and white square movement is defined as follows :

    public void Update(...)
    {
        // White square movement        
        _timeline += 0.01f;
        if (_timeline >= 1.0f)
        {
            _timeline = 0.01f;
        }
        _timelineVector2 = GetBezierPoint(_timeline, _p0, _p1, _p2, _p3);
    }

    // Also used for generating curve
    public static Vector2 GetBezierPoint(float t, Vector2 p0, Vector2 p1, Vector2 p2, Vector2 p3)
    {
        float cx = 3 * (p1.X - p0.X);
        float cy = 3 * (p1.Y - p0.Y);

        float bx = 3 * (p2.X - p1.X) - cx;
        float by = 3 * (p2.Y - p1.Y) - cy;

        float ax = p3.X - p0.X - cx - bx;
        float ay = p3.Y - p0.Y - cy - @by;

        float Cube = t * t * t;
        float Square = t * t;

        float resX = (ax * Cube) + (bx * Square) + (cx * t) + p0.X;
        float resY = (ay * Cube) + (@by * Square) + (cy * t) + p0.Y;

        return new Vector2(resX, resY);
    }
\$\endgroup\$
5
  • \$\begingroup\$ okay what should I do ? delete the question ? \$\endgroup\$
    – aybe
    Commented May 28, 2012 at 0:11
  • 1
    \$\begingroup\$ (Dunno how my previous comment disappeared, this is possibly a duplicate of that). I flagged your question for moderators' attention, if they agrees they'll close it in a while; so you don't have to do anything. Anyways, very good question, it's a very common trap in gameplay programming. Next time, just search a bit before posting ;) \$\endgroup\$ Commented May 28, 2012 at 1:02
  • \$\begingroup\$ Yes you're right :) \$\endgroup\$
    – aybe
    Commented May 28, 2012 at 3:40
  • \$\begingroup\$ Should close soon. The white rabbit says "arc length parametrization" and that leads you down the rabbit hole, if you want to read up on the math later. \$\endgroup\$ Commented May 28, 2012 at 15:31
  • \$\begingroup\$ Definitely ! ^_^ \$\endgroup\$
    – aybe
    Commented May 29, 2012 at 20:24

1 Answer 1

0
\$\begingroup\$

There is a simple approximation you could apply here. Lets say the movement pace you want is 1.0 units per frame. You start with t = 0 and a stepSize = 1.0

Lets say the function getBezierPoint(t) returns a position on the bezier, now you do a binary search like approximation:

desiredStepSize = 1.0; // How much we move each frame / second ... some other time unit
acceptableError = desiredStepSize / 20.0; // How much can we deviate from the desired speed

currentT = 0.0; // Where do we start on the bezier (t = 0)
tStepSize = 0.01; // How much we guess the change in t needs to be

actualStepSize = 0; // The distance between the current position and the next one

  function compute_t_step_size_from_guess()
  // Make tStepSize big enough if needed

  actualStepSize = distance(getBezierPoint(currentT),
                              getBezierPoint(currentT + tStepSize));
  while (actualStepSize < desiredStepSize);
  {
    tStepSize *= 2.0;
    actualStepSize = distance(getBezierPoint(currentT),
                              getBezierPoint(currentT + tStepSize));
  } 


  deltaT = 0.5 * tStepSize;
  // Fine tune with binary search
  while ((actualStepSize < desiredStepSize - acceptableError 
          ||
          actualStepSize > desiredStepSize + acceptableError )
  {
    if (actualStepSize < desiredStepSize) tStepSize += deltaT;
    else tStepSize -= deltaT;

    deltaT *= 0.5;  
  }
}

This runs very fast and gets really accurate results. You can use it to compute the next position for nearly perfect linear velocity (it doesn't take the arc into account). You can vastly improve the speed by fine tuning some things, for instance, increasing the size during the growth phase by * (1 + acceptableError / desiredStepSize ), then binary searching between the the current approximation and 1 / (1 + acceptableError / desiredStepSize ).

\$\endgroup\$
3
  • \$\begingroup\$ @Aybe You"re welcome, I've faced the same issue a while back when I was working on an in-house tweening library. I used very similar code, basically binary searching for the next ideal position. You can also use the Newtonian approach... ie changing the tStep by the ration between the current distance and the desired distance. \$\endgroup\$
    – AturSams
    Commented Nov 1, 2014 at 6:56
  • \$\begingroup\$ This algorithm will not give accurate results for a curve with sharp bends, because it measures direct distance rather than distance along the curve. The 'binary search' will get stuck in an infinite loop because the parameters actualStepSize and desiredStepSize do not change within the loop. \$\endgroup\$
    – Kevin
    Commented Nov 23, 2023 at 2:32
  • \$\begingroup\$ @Kevin Share a fix. \$\endgroup\$
    – AturSams
    Commented Nov 26, 2023 at 12:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .