How do I implement a Bézier curve in C++?

Question

I'd like to implement a Bézier curve. How should I go about creating a quadratic curve?

void printQuadCurve(float delta, Vector2f p0, Vector2f p1, Vector2f p2);

Clearly we'd need to use linear interpolation, but does this exist in the standard math library? If not, where can I find it?

I'm using Linux.

Sevigny

Answer 1

Recently I ran across the same question and wanted to implemented it on my own. This image from Wikipedia helped me:

The following code shows how to compute a quadratic bezier.

int interpolate( int from , int to , float percent )
{
    int difference = to - from;
    return from + ( difference * percent );
}    

for( float i = 0 ; i < 1 ; i += 0.01 )
{
    // The Green Line
    xa = interpolate( x1 , x2 , i );
    ya = interpolate( y1 , y2 , i );
    xb = interpolate( x2 , x3 , i );
    yb = interpolate( y2 , y3 , i );

    // The Black Dot
    x = interpolate( xa , xb , i );
    y = interpolate( ya , yb , i );
    
    drawPixel( x , y , COLOR_RED );
}

With (x1|y1), (x2|y2) and (x3|y3) being P0, P1 and P2 in the image. Just for showing the basic idea...

For the ones who ask for the cubic bezier, it just works analogue (also from Wikipedia):

This answer provides Code for it.

Shir

Great Reply, but this technically a DeCasteljau representation. Which is easier to understand, but usually less optimal. – Meggs

Thanks! You're totally right. What I needed at the time was a vivid understanding of berzier curves (that people feel a similar desire is probably the reason this answer was upvoted that many times). Most other algorithms are (often necessary) optimizations of the DeCasteljau, so it seems to be a really good foundation upon which knowledge can easily build upon. – Shir

@EnderDoe DeCasteljau method is numerically stable. – Vasoconstrictor

Answer 2

Here is a general implementation for a curve with any number of points.

vec2 getBezierPoint( vec2* points, int numPoints, float t ) {
    vec2* tmp = new vec2[numPoints];
    memcpy(tmp, points, numPoints * sizeof(vec2));
    int i = numPoints - 1;
    while (i > 0) {
        for (int k = 0; k < i; k++)
            tmp[k] = tmp[k] + t * ( tmp[k+1] - tmp[k] );
        i--;
    }
    vec2 answer = tmp[0];
    delete[] tmp;
    return answer;
}

Note that it uses heap memory for a temporary array which is not all that efficient. If you only need to deal with a fixed number of points you could hard-code the numPoints value and use stack memory instead.

Of course, the above assumes you have a vec2 structure and operators for it like this:

struct vec2 {
    float x, y;
    vec2(float x, float y) : x(x), y(y) {}
};

vec2 operator + (vec2 a, vec2 b) {
    return vec2(a.x + b.x, a.y + b.y);
}

vec2 operator - (vec2 a, vec2 b) {
    return vec2(a.x - b.x, a.y - b.y);
}

vec2 operator * (float s, vec2 a) {
    return vec2(s * a.x, s * a.y);
}

Sunlit

@ifroce2d which type of curve is that? – Robins

?? It's bezier as per the question and the function name "getBezierPoint" – Sunlit

@ifroce2d The basic Idea shall be the same for Vector3 right ? – Budding

Answer 3

You have a choice between de Casteljau's method, which is to recursively split the control path until you arrive at the point using a linear interpolation, as explained above, or Bezier's method which is to blend the control points.

Bezier's method is

 p = (1-t)^3 *P0 + 3*t*(1-t)^2*P1 + 3*t^2*(1-t)*P2 + t^3*P3 

for cubics and

 p = (1-t)^2 *P0 + 2*(1-t)*t*P1 + t*t*P2

for quadratics.

t is usually on 0-1 but that's not an essential - in fact the curves extend to infinity. P0, P1, etc are the control points. The curve goes through the two end points but not usually through the other points.

Lillielilliputian

Answer 4

Did you use a C# library earlier?

In C++, no standard library function for Bezier curves is available (yet). You can of course roll your own (CodeProject sample) or look for a math library.

This blogpost explains the idea nicely but in Actionscript. Translation should not be much of a problem.

Selfsupport

Just an FYI. The link to the blog post shows an empty page. – Natashianatassia

@RSahu Thanks for flagging; I found an archived copy in Wayback Machine and edited the answer. – Emaemaciate

Answer 5

To get an individual point (x, y) along a cubic curve at a given percent of travel (t), with given control points (x1, y1), (x2, y2), (x3, y3), and (x4, y4) I expanded De Casteljau’s algorithm and rearranged the equation to minimize exponents:

//Generalized code, not C++
variables passed to function:   t,  x1, y1, x2, y2, x3, y3, x4, y4
variables declared in function: t2, t3, x,  y
t2 = t * t
t3 = t * t * t
x = t3*x4 + (3*t2 - 3*t3)*x3 + (3*t3 - 6*t2 + 3*t)*x2 + (3*t2 - t3 - 3*t + 1)*x1
y = t3*y4 + (3*t2 - 3*t3)*y3 + (3*t3 - 6*t2 + 3*t)*y2 + (3*t2 - t3 - 3*t + 1)*y1

(t) is a decimal value between 0 and 1 (0 <= t <= 1) that represents percent of travel along the curve.

The formula is the same for x and y, and you can write a function that takes a generic set of 4 control points or group the coefficients together:

t2 = t * t
t3 = t * t * t

A = (3*t2 - 3*t3)
B = (3*t3 - 6*t2 + 3*t)
C = (3*t2 - t3 - 3*t + 1)

x = t3*x4 + A*x3 + B*x2 + C*x1
y = t3*y4 + A*y3 + B*y2 + C*y1

For quadratic functions, a similar approach yields:

t2 = t * t

A = (2*t - 2*t2)
B = (t2 - 2*t + 1)

x = t2*x3 + A*x2 + B*x1
y = t2*y3 + A*y2 + B*y1

Mercie

Answer 6

• If you just want to display a Bezier curve, you can use something like PolyBezier for Windows.

• If you want to implement the routine yourself, you can find linear interpolation code all over the Intarnetz.

• I believe the Boost libraries have support for this. Linear interpolation, not Beziers specifically. Don't quote me on this, however.

Jugate

Excellent! I think that code project example will do nicely :) – Sevigny

Whilst this may theoretically answer the question, it would be preferable to include the essential parts of the answer here, and provide the link for reference. – Traps

Answer 7

I made an implementation based on this example https://mcmap.net/q/224938/-how-do-i-implement-a-b-233-zier-curve-in-c but for any amount of path points

void bezier(int [] arr, int size, int amount) {
  int a[] = new int[size * 2];    
  for (int i = 0; i < amount; i++) {
    for (int j = 0; j < size * 2; j++) a[j] = arr[j];
    for (int j = (size - 1) * 2 - 1; j > 0; j -= 2) 
      for (int k = 0; k <= j; k++) 
        a[k] = a[k] + ((a[k+2] - a[k]) * i) / amount;
    circle(a[0], a[1], 3);  // draw a circle, in Processing
  }
}

Where arr is array of points {x1, y1, x2, y2, x3, y3... xn, yn}, size is amount of points (twice smaller than array size), and amount is number of output points.

For optimal calculations you can use 2^n amount and bit shift:

void bezier(int [] arr, int size, int dense) {
  int a[] = new int[size * 2];    
  for (int i = 0; i < (1 << dense); i++) {
    for (int j = 0; j < size * 2; j++) a[j] = arr[j];
    for (int j = (size - 1) * 2 - 1; j > 0; j -= 2) 
      for (int k = 0; k <= j; k++) 
        a[k] = a[k] + (((a[k+2] - a[k]) * i) >> dense);
    circle(a[0], a[1], 3);  // draw a circle, in Processing
  }
}

Priester

Answer 8

This implementation on github shows how to calculate a simple cubic bezier, with normal and tangent values for values of 't' from 0->1. It is a direct transposition of the formulas at wikipedia.

Backhanded