Efficient algorithm for drawing quadratic bezier curves

[Klakap]

I've recently come to drawing bezier curves. I found this simple algorithm based on quadratic bezier curve formula:

Code: Select all

void draw_quadratic_bezier(dword_t x1, dword_t y1, dword_t x2, dword_t y2, dword_t x3, dword_t y3, float r, dword_t color) {
   float draw_x1 = x1, draw_y1 = y1, draw_x2, draw_y2, a, b, c, z;

   for(float i=0; i<1; i+=r) {
    z = (1-i);
    a = z*z;
    b = z*2*i;
    c = i*i;
    draw_x2 = a*x1 + b*x2 + c*x3;
    draw_y2 = a*y1 + b*y2 + c*y3;
    draw_line(draw_x1, draw_y1, draw_x2, draw_y2, color);
    draw_x1 = draw_x2;
    draw_y1 = draw_y2;
   }
 
   draw_line(draw_x1, draw_y1, x3, y3, color);
}

It works, however, I can not found any informations how to calculate best r value, and also it is not very efficent, because there is multiplication in each cycle. I was searching for something better, but I did not found anything. So I sit down, and recalculate that code above can be rewritten into this:

Code: Select all

void draw_quadratic_bezier(dword_t x1, dword_t y1, dword_t x2, dword_t y2, dword_t x3, dword_t y3, float r, dword_t color) {
   float x1_inc = r*r*x1;
   float x1_step = ((1/r)-1)*x1_inc;
   float x2_base = 0;
   float x2_base_inc = (x2*2)/(1/r);
   float x2_inc = ((r*r*x2)*2);
   float x2_step = 0;
   float x3_inc = r*r*x3;
   float x3_step = 0;
   float y1_inc = r*r*y1;
   float y1_step = ((1/r)-1)*y1_inc;
   float y2_base = 0;
   float y2_base_inc = (y2*2)/(1/r);
   float y2_inc = ((r*r*y2)*2);
   float y2_step = 0;
   float y3_inc = r*r*y3;
   float y3_step = 0;
   float draw_x1 = x1, draw_y1 = y1, draw_x2, draw_y2;
 
   x2 = 0;
   x3 = 0;
   y2 = 0;
   y3 = 0;
 
   for(float i=0; i<1; i+=r) {
    draw_x2 = x1 + (x2_base-x2) + x3;
    draw_y2 = y1 + (y2_base-y2) + y3;
    draw_line(draw_x1, draw_y1, draw_x2, draw_y2, color);
    draw_x1 = draw_x2;
    draw_y1 = draw_y2;
  
    x1 -= (x1_step+x1_step+x1_inc);
    x1_step -= x1_inc;
    x2_base += x2_base_inc;
    x2 += (x2_step+x2_step+x2_inc);
    x2_step += x2_inc;
    x3 += (x3_step+x3_step+x3_inc);
    x3_step += x3_inc;
  
    y1 -= (y1_step+y1_step+y1_inc);
    y1_step -= y1_inc;
    y2_base += y2_base_inc;
    y2 += (y2_step+y2_step+y2_inc);
    y2_step += y2_inc;
    y3 += (y3_step+y3_step+y3_inc);
    y3_step += y3_inc;
   }
}

That's quite fast, but it is still missing best r value computation. After this, I found site https://zingl.github.io/bresenham.html with bresenham algorithm for quadratic beziers. It is faster than my code, but it do not work for all bezier curves. Is there some more efficient algorithm to draw any bezier curve? Or if not, how to calculate best value for r?

[devc1]

I once felt into that problem, and found (invented) a solution that worked perfectly and draws perfect curves with brensenham lines, the solution I taught myself is to use the normal math formula to calculate the width of a straight line from A to B, the results were similar to those of MS Paint unanti-alliased lines so I think that's what everyone does, you will have very close points sometimes that you can just draw a line between them.

To get point A and B, you will need to calculate the X, Y position of the pixel given (for e.g) that t = 0.1 (for point A) and t = 0.2 (for point B).

I can give a more detailled explanation if you want, try this and tell me if it works.

That was my implementation :

Code: Select all

float IncVal = 0.1; // this is "t"
UINT64 XA = BezierCompute(XCordinates, NumCordinates, 0.1 /*t: inc value), YA = BezierCompute(YCordinates, NumCordinates, 0.1);
UINT64 XB = BezierCompute(XCordinates, NumCordinates, 0.2 /* now with t = 0.2*/), YB = BezierCompute(YCordinates, NumCordinate, 0.2);

// calculate the distance using the famous math formula
float Distance = __sqrt(pow(XB - XA, 2) + pow(YB - YA, 2));
If(Distance > 2)
{
    IncValue /= (Distance - 1); // - 1 to link between small points and make clean curves
}

[Klakap]

Sorry, I am not quite sure how your code works. I already have code that draw bezier curve using bresenham lines, but I am looking for faster algorithm, or how to calculate the smallest possible number of lines needed to draw a curve - best t(or r in my code) value.

[devc1]

Are you looking for a faster way to figure out pixels in a bezier curve, or to get the "t" increment value or both ?

You can use SIMD (SSE, AVX/ AVX2/ AVX512) To calculate pixels faster, that's what I've done.

This is the ComputeBezier function

Code: Select all

unsigned long long __fastcall BezierCompute(float* cordinates, unsigned int NumCordinates, float t);

It does something similar to what you do int the loop where you draw the bezier curve, you give the cordinates and "t" and it gives you the position of the pixel to draw.

"float IncValue" is the "r value" that you are looking for, it is so accurate and takes nothing.

To the day, with the best optimizations I can make, my bezier drawing function can draw almost 400000 quadratic bezier curves per second.

[Klakap]

Well, I would say both, I am looking for fast algorithm for drawing pixels, or/and I am looking for how to get best "t" incrementing value for cycle.
I am not exactly sure in what way is BezierCompute() method better than my code in cycle. Can you please provide more detailed explanation of your algorithm?

[Gigasoft]

It is better to recursively subdivide the curve in half, the math then becomes trivial and you can stop at the point where the curve becomes locally flat.

[devc1]

BezierCompute is what returns the location of X and Y in the bezier curve corresponding to "t".

You calculate the gap between two points, A where t = 0.1 and B where t = 0.2.
The cordinates of A and B are generated by ComputeBezier (the thing you do in your for loop).

Then you get the distance using the famous math formula : D = sqrt((xB-xA)^2 + (yB-yA)^2)

Then you divide r "the increment value" by the distance - 1 and you get a correct value

This is faster than subdividing, its a method that I invented and it works.

[Klakap]

thank you for explanation. I also founded that bresenham algorithm works, but you need other half of code than on page I mentioned. It can be founded in famous pdf A Rasterizing Algorithm for Drawing Curves.