Bezier curves of grade n

Question

I made a function which creates Bezier curves of grade n. What do you think?

float interpolate(float n1, float n2, float prec)
{
    return n1 + ((n2-n1) * prec);
}

std::vector<Vector2f> make_bezier(const std::vector<Vector2f>& anchors, double accuracy=10000.0)
{
    if(anchors.size()<=2)
        return anchors;

    std::vector<Vector2f> end;
    end.push_back(anchors[0]);

    for(float i=0.f; i<1.f; i+=1.f/accuracy)
    {
        std::vector<Vector2f> temp;
        for(unsigned int j=1; j<anchors.size(); ++j)
            temp.push_back(Vector2f(interpolate(anchors[j-1].x, anchors[j].x, i),
                                    interpolate(anchors[j-1].y, anchors[j].y, i)));

        while(temp.size()>1)
        {
            std::vector<Vector2f> temp2;

            for(unsigned int j=1; j<temp.size(); ++j)
                temp2.push_back(Vector2f(interpolate(temp[j-1].x, temp[j].x, i),
                                         interpolate(temp[j-1].y, temp[j].y, i)));
            temp = temp2;
        }
        end.push_back(temp[0]);
    }

    return end;
}

Answer 1

Just a few comments:

std::vector<Vector2f> make_bezier(const std::vector<Vector2f>& anchors, double accuracy=10000.0)

You're using float for all your other floating point variables. Unless there's some really good reason to use double here (for accuracy) I'd consider changing it to a float as well.

std::vector<Vector2f> end;
end.push_back(anchors[0]);

for(float i=0.f; i<1.f; i+=1.f/accuracy)

I'd write this a bit differently. As it stands, i can accumulate rounding errors from one iteration of the loop to the next. I'd prefer to do something like:

for (int j=0; j<accuracy; j++) {
    float i = 1.0f/j;
    // ...

This way, each value of i is computed independently, and rounding from one iteration doesn't affect its value in the next.

    std::vector<Vector2f> temp;
    for(unsigned int j=1; j<anchors.size(); ++j)
        temp.push_back(Vector2f(interpolate(anchors[j-1].x, anchors[j].x, i),
                                interpolate(anchors[j-1].y, anchors[j].y, i)));

Literally all your calls to interolate (at least in this code) happen in pairs. That being the case, I think I'd rewrite it a bit to take a couple of vector2fs as parameters, and return a vector2f containing the interpolation on both the x and y components of the inputs. It also uses i as a third input. My immediate reaction would be to define interpolate as a lambda that captured i, and took the other two parameters as inputs.

vector2f interpolate(vector2f in1, vector2f const &in2) { 
    in1.x = /* ... */;
    in1.y = /* ... */;
    return in1;
}

With that in place, the loop above can be reduced to a fairly simple application of std::transform, something like this:

 std::transform(anchors.begin(), anchors.end(), 
                anchors.begin()+1, 
                std::back_inserter(temp));

Of course, pretty much the same would happen here:

        for(unsigned int j=1; j<temp.size(); ++j)
            temp2.push_back(Vector2f(interpolate(temp[j-1].x, temp[j].x, i),
                                     interpolate(temp[j-1].y, temp[j].y, i)));

...as well.

Answer 2

Just a few notes:

• You could improve readability by adding whitespace between operators.

  For instance, in the for loop statement:

  for (float i = 0.f; i < 1.f; i += 1.f/accuracy) {}
  

  For this as well, I would have a constant in place of the 1.f/accuracy to avoid performing the division operation each time (it's slow). Instead, you'll only be performing addition each time.

  Consider something like this:

  const float stepsize = 1.f / accuracy;
  
  for (float i = 0.f; i < 1.f; i += stepsize) {}
  

• With an std::vector, you can use front() to get the reference to the first element instead of using the index 0:

  end.push_back(anchors.front());
  

• Prefer to use std::size_type when incrementing through an STL container. This guarantees that you can access every element of any container size, whereas an unsigned int or another integer type may not be large enough.

  Due to its length, this can be declared before the loop.

  std::vector<Vector2f>::size_type j;
  
  for (j = 1; j != temp.size(); ++j) {}
  

Answer 3

Apart from the things which already have been noted:

You duplicate the interpolation loop in your body which violates DRY. The easy fix for that is to copy anchors into temp.

Also rather than assigning temp2 to temp which copies the vector you could use vector::swap which swaps the contents of the two vectors in constant time.

So your main body can be written as:

for (float k = 0.f; k < accuracy; ++k)
{
    float i = k / accuracy;

    std::vector<Vector2f> temp(anchors);

    while (temp.size() > 1)
    {
        std::vector<Vector2f> temp2;

        for (unsigned int j = 1; j < temp.size(); ++j)
            temp2.push_back(Vector2f(interpolate(temp[j-1].x, temp[j].x, i),
                                     interpolate(temp[j-1].y, temp[j].y, i)));
        temp.swap(temp2);
    }
    end.push_back(temp.front());
}

Answer 4

The algorithm you are using works, but it will exhibit very poor performance as you increase the order of your Bézier curve. Let's say that you want to render m points and that you have n anchors, you are computing n-1 + n-2 + ... + 1 interpolations for every rendered point. So we are talking about an O(n²m) algorithm.

If performance matters, you'll have to consider using the general formula with the binomial coefficients. The binomial coefficients can be precomputed so we can consider that they are given for free. Then for each rendered point you only need to traverse the list of anchors once, yielding an O(nm) algorithm.