Jump to content
43oh

Bezier Curves


Recommended Posts

Does anyone know of a pixel-by-pixel method using integer math to draw Bezier curves? I used the Google and found this interesting idea, but don't have time to study the math and try to implement it. Most of the info I found was just the math.

 

Since I couldn't find the ideal algorithm, I just did a piecewise Bernstein polynomial with fixed point 16.16 integer math. It seems to work properly and is reasonably efficient.

 

Any suggestions about how to improve this, or do it another way are most welcome. This is part of a MSP430 graphics library I am working on.

 

Drawing code

void bezier_quad(int x0, int y0, int x1, int y1, int x2, int y2, unsigned m)
{
   register unsigned long t, t2;
   int x, y;
   const int a1 = x0 - (x1 << 1) + x2;
   const int b1 = (x1 - x0) << 1;
   const int a2 = y0 - (y1 << 1) + y2;
   const int b2 = (y1 - y0) << 1;
   register const long xx = ((long)x0 << 16) + 0x8000;
   register const long yy = ((long)y0 << 16) + 0x8000;
   const unsigned inc = 2048; 
   int px = x0, py = y0; 

   for(t = inc; t < 65536; t += inc) {
       t2 = (t * t) >> 16;
       x = ((a1 * t2) + (b1 * t) + xx) >> 16;
       y = ((a2 * t2) + (b2 * t) + yy) >> 16;
       line(px, py, x, y, m);
       px = x; py = y; 
   }
   line(px, py, x2, y2, m);
}

void bezier_cubic(int x0, int y0, int x1, int y1, int x2, int y2, int x3, int y3, unsigned m)
{
   register unsigned long t, t2, t3;
   int x, y;
   const int a1 = ((x1 - x2) * 3) - x0 + x3; 
   const int b1 = (x0 - (x1 << 1) + x2) * 3;
   const int c1 = (x1 - x0) * 3; 
   const int a2 = ((y1 - y2) * 3) - y0 + y3;
   const int b2 = (y0 - (y1 << 1) + y2) * 3;
   const int c2 = (y1 - y0) * 3;
   register const long xx = ((long)x0 << 16) + 0x8000;
   register const long yy = ((long)y0 << 16) + 0x8000;
   const unsigned inc = 2048;
   int px = x0, py = y0; 

   for(t = inc; t < 65536; t += inc) {
       t2 = t * t;
       t3 = ((t2 & 0xFFFF) * t) >> 16;
       t2 >>= 16;
       t3 += (t2 * t);
       t3 >>= 16;
       x = ((a1 * t3) + (b1 * t2) + (c1 * t) + xx) >> 16;
       y = ((a2 * t3) + (b2 * t2) + (c2 * t) + yy) >> 16;
       line(px, py, x, y, m);
       px = x; py = y; 
   }
   line(px, py, x3, y3, m);
}

Test code

void bez_demo(void)
{
   int dx0, dy0, dx1, dy1, dx2, dy2, dx3, dy3;
   int x0, y0, x1, y1, x2, y2, x3, y3;
   x0 = y0 = x1 = y1 = 0;
   x2 = y2 = x3 = y3 = 0;
   dx0 = 2;
   dx1 = 3;
   dx2 = 4;
   dx3 = 5;
   dy0 = 3;
   dy1 = 2;
   dy2 = 5;
   dy3 = 4;
   for(; {
       x0 += dx0; if(x0 < 0 || x0 > 255) dx0 = -dx0, x0 += dx0; 
       y0 += dy0; if(y0 < 0 || y0 > 191) dy0 = -dy0, y0 += dy0; 
       x1 += dx1; if(x1 < 0 || x1 > 255) dx1 = -dx1, x1 += dx1; 
       y1 += dy1; if(y1 < 0 || y1 > 191) dy1 = -dy1, y1 += dy1;
       x2 += dx2; if(x2 < 0 || x2 > 255) dx2 = -dx2, x2 += dx2; 
       y2 += dy2; if(y2 < 0 || y2 > 191) dy2 = -dy2, y2 += dy2; 
       x3 += dx3; if(x3 < 0 || x3 > 255) dx3 = -dx3, x3 += dx3; 
       y3 += dy3; if(y3 < 0 || y3 > 191) dy3 = -dy3, y3 += dy3;
       #if 0
       set_pix(x1, y1);
       bezier_quad(x0, y0, x1, y1, x2, y2, 0);
       wait(1);
       bezier_quad(x0, y0, x1, y1, x2, y2, 1);
       clr_pix(x1, y1);
       #else
       set_pix(x1, y1); set_pix(x2, y2);
       bezier_cubic(x0, y0, x1, y1, x2, y2, x3, y3, 0);
       wait(1);
       bezier_cubic(x0, y0, x1, y1, x2, y2, x3, y3, 1);
       clr_pix(x1, y1); clr_pix(x2, y2);
       #endif
   }
}

 

http://www.youtube.com/watch?v=dZPk5OPafk8

 

The camera added a lot of motion blur. It really looks much better.

Link to post
Share on other sites

Opossum, what did you display this on?

 

Also, I have had a little experience in Bezier trajectories. It was a part of my thesis to make to robots follow each other. You can view it here. See pdf.

 

Youtube link:

 

As far as I can remember it was in float math. So cannot help you much there. Pg 38 shows you how to calculate the co-efficients.

 

Hope this helps.

Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...