Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

n-th order Bezier Curves?

I've managed to implement quadratic and cubic Bezier curves.They are pretty straightforward since we have a formula. Now I want to represent an n-th order Bezier curve using the generalization:

enter image description here

Where

enter image description here

and

enter image description here

I'm using a bitmap library to render the output, so here is my code:

// binomialCoef(n, k) = (factorial(n) / (factorial(k) * factorial(n- k)))
unsigned int binomialCoef(unsigned int n, const unsigned int k)
{
    unsigned int r = 1;

    if(k > n)
        return 0;

    for(unsigned int d = 1; d <= k; d++)
    {
        r *= n--;
        r /= d;
    }

    return r;
}

void nBezierCurve(Bitmap* obj, const Point* p, const unsigned int nbPoint, float steps, const unsigned char red, const unsigned char green, const unsigned char blue)
{
    int bx1 = p[0].x;
    int by1 = p[0].y;
    int bx2;
    int by2;

    steps = 1 / steps;

    for(float i = 0; i < 1; i += steps)
    {
        bx2 = by2 = 0;
        for(int j = 0; (unsigned int)j < nbPoint; j++)
        {
            bx2 += (int)(binomialCoef(nbPoint, j) * pow(1 - i, (float)nbPoint - j) * pow(i, j) * p[j].x);
            by2 += (int)(binomialCoef(nbPoint, j) * pow(1 - i, (float)nbPoint - j) * pow(i, j) * p[j].y);
        }

        bresenhamLine(obj, bx1, by1, bx2, by2, red, green, blue);

        bx1 = bx2;
        by1 = by2;
    }

    // curve must end on the last anchor point
    bresenhamLine(obj, bx1, by1, p[nbPoint - 1].x, p[nbPoint - 1].y, red, green, blue);
}

Here's the set of points to render:

Point ncurv[] = {
                    20, 200,
                    70, 300,
                    200, 400,
                    250, 200
                };

and here's the output:

enter image description here

The red curve is a cubic Bezier. The blue one is supposed to be the 4th order Bezier, which is the same as cubic Bezier, but in this case, they are not the same ?!

EDIT : I forgot to note that the bottom left point is (0, 0)

like image 929
Jonas Avatar asked Mar 24 '13 14:03

Jonas


2 Answers

The sum in your formula...

enter image description here

...runs from 0 to n, ie for an n-th order bezier you need n+1 points.

You have 4 points, so you're drawing a 3rd-order bezier.

The error in your code is here:

for(int j = 0; (unsigned int)j < nbPoint; j++)

it should be:

for(int j = 0; (unsigned int)j <= nbPoint; j++)

otherwise you're only iterating from 0 to n-1.

3rd-order bezier

EDIT:

Out of interest, the shape you were getting is the same as if the missing (5th) point was at (0,0), since that's the only point that would contribute nothing to your sum...

4th-order bezier with 5th point at origin

like image 105
Richard Inglis Avatar answered Oct 02 '22 20:10

Richard Inglis


You are trying to construct a 4th-order Bezier curve on only four points. No wonder it's not working.

like image 21
TonyK Avatar answered Oct 02 '22 20:10

TonyK