Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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;
}
share|improve this question

4 Answers 4

up vote 11 down vote accepted

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.

share|improve this answer

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) {}
    
share|improve this answer
1  
Also I would not calculate 1.f/accuracy 10000 times. Maybe a variable float stepsize = 1.f/accuracy should be introduced. –  Marcel Blanck Mar 3 at 10:21
    
@MarcelBlanck: I've missed that as well. Thanks! –  Jamal Mar 3 at 15:13

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());
}
share|improve this answer

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.

share|improve this answer
    
this seems like a good point, I would like to see more code in the review, but I think this fits. –  Malachi Mar 3 at 14:49

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.