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
}
}
```

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

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.

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.

Join the conversation

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

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

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

×
×
• Blog

• Activity

×
• Create New...