CODEWITHSUNDEEP
c++bezier
danijar
danijar

Reputation: 34185

Why is my bezier curve implementation biased?

I want to render bezier curves in C++, so I started implementing it myself. For now, it doesn't have to be very efficient. My code somehow produces a near result, but those curves aren't accurate. (dvec2 is a vector of two double values.)

list<dvec2> bezier(list<dvec2> const &points, int resolution)
{
    list<dvec2> samples;
    double step = 1.0 / resolution;
    for (double time = 0.0; time <= 1.0; time += step) {
        list<dvec2> sliders = points;
        while (sliders.size() > 1)
            sliders = slide(sliders, time);
        samples.push_back(sliders.front());
    }
    return samples;
}

list<dvec2> slide(list<dvec2> const &points, double time)
{
    list<dvec2> result;
    auto current = points.begin();
    dvec2 last = *current;
    for (++current; current != points.end(); ++current)
        result.push_back(last * time + *current * (1.0 - time));
    return result;
}

Currently, I create n-1 points from a curve by interpolating the first with the second, the second with the third, and so on, based on time t. Then, I reduce this new set of points again by the same algorithm, until I'm left with one point that I can draw. I think the approach should work.

On rendered image, you can see the algorithms outcome on several rendered curves.

rendering looks similar to bezier curves

For example, in the bottom left of the image, the two opposing curves should by symmetrical I think. Mine are biased by the direction. Moreover, those fully enclosed curves should at least draw a point in the center for t=0.5. What is causing this?

Upvotes: 3

Views: 369

Answers (1)

leemes
leemes

Reputation: 45675

Your approach should work. You made a little oversight: Within slide(), you don't update last in your loop.

Try:

for (++current; current != points.end(); ++current) {
    result.push_back(last * time + *current * (1.0 - time));
    last = *current; // <--
}

Note that a different interpretation of bezier curves can be given by taking the sum of these products:

(Source: wikipedia)

Some terminology is associated with these parametric curves. We have

\mathbf{B}(t) = \sum_{i=0}^n b_{i, n}(t)\mathbf{P}_i,\quad t \in [0, 1]

where the polynomials

b_{i,n}(t) = {n\choose i} t^i (1 - t)^{n - i},\quad i = 0, \ldots, n

are known as Bernstein basis polynomials of degree n.

Here, you need (precomputed) binomial coefficients, and by using the std::pow function you end up with a single loop instead of two nested ones (considering n to be limited by a constant in practice, to make precomputation possible).

Upvotes: 4

Related Questions