oPossum 1,083 Posted July 10, 2011 Share Posted July 10, 2011 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. RobG, xpg and SugarAddict 3 Quote Link to post Share on other sites

bluehash 1,581 Posted July 10, 2011 Share Posted July 10, 2011 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. Quote Link to post Share on other sites

## Recommended Posts

## Join the conversation

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