Bezier Curves

[oPossum 1,083]

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.

[bluehash 1,581]

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.