Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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);
    }
share|improve this question
    
okay what should I do ? delete the question ? –  Aybe May 28 '12 at 0:11
1  
(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 ;) –  Laurent Couvidou May 28 '12 at 1:02
    
Yes you're right :) –  Aybe May 28 '12 at 3:40
    
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. –  Patrick Hughes May 28 '12 at 15:31
    
Definitely ! ^_^ –  Aybe May 29 '12 at 20:24

1 Answer 1

up vote 1 down vote accepted

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 ).

share|improve this answer
    
+1 for exhuming this question, thanks :D –  Aybe Oct 31 at 22:24
    
@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. –  Zehelvion Nov 1 at 6:56
    
Alright, thank you ! –  Aybe Nov 1 at 16:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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