OSDev.org

The Place to Start for Operating System Developers
It is currently Thu Mar 28, 2024 4:28 pm

All times are UTC - 6 hours




Post new topic Reply to topic  [ 8 posts ] 
Author Message
 Post subject: Efficient algorithm for drawing quadratic bezier curves
PostPosted: Mon Dec 26, 2022 6:19 am 
Offline
Member
Member

Joined: Sat Mar 10, 2018 10:16 am
Posts: 296
I've recently come to drawing bezier curves. I found this simple algorithm based on quadratic bezier curve formula:
Code:
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:
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?

_________________
https://github.com/VendelinSlezak/BleskOS


Top
 Profile  
 
 Post subject: Re: Efficient algorithm for drawing quadratic bezier curves
PostPosted: Mon Dec 26, 2022 6:53 am 
Offline
Member
Member

Joined: Fri Feb 11, 2022 4:55 am
Posts: 435
Location: behind the keyboard
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:
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
}


Top
 Profile  
 
 Post subject: Re: Efficient algorithm for drawing quadratic bezier curves
PostPosted: Mon Dec 26, 2022 7:13 am 
Offline
Member
Member

Joined: Sat Mar 10, 2018 10:16 am
Posts: 296
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.

_________________
https://github.com/VendelinSlezak/BleskOS


Top
 Profile  
 
 Post subject: Re: Efficient algorithm for drawing quadratic bezier curves
PostPosted: Mon Dec 26, 2022 7:18 am 
Offline
Member
Member

Joined: Fri Feb 11, 2022 4:55 am
Posts: 435
Location: behind the keyboard
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:
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.


Top
 Profile  
 
 Post subject: Re: Efficient algorithm for drawing quadratic bezier curves
PostPosted: Mon Dec 26, 2022 7:27 am 
Offline
Member
Member

Joined: Sat Mar 10, 2018 10:16 am
Posts: 296
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?

_________________
https://github.com/VendelinSlezak/BleskOS


Top
 Profile  
 
 Post subject: Re: Efficient algorithm for drawing quadratic bezier curves
PostPosted: Mon Dec 26, 2022 10:50 am 
Offline
Member
Member

Joined: Sat Nov 21, 2009 5:11 pm
Posts: 852
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.


Top
 Profile  
 
 Post subject: Re: Efficient algorithm for drawing quadratic bezier curves
PostPosted: Mon Dec 26, 2022 11:31 am 
Offline
Member
Member

Joined: Fri Feb 11, 2022 4:55 am
Posts: 435
Location: behind the keyboard
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.


Top
 Profile  
 
 Post subject: Re: Efficient algorithm for drawing quadratic bezier curves
PostPosted: Sat Jan 14, 2023 4:14 pm 
Offline
Member
Member

Joined: Sat Mar 10, 2018 10:16 am
Posts: 296
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.

_________________
https://github.com/VendelinSlezak/BleskOS


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 8 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 38 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group