2
105 Aug 11, 2013 at 07:39 rasterization

Multiplication-free ellipse rasterizer, about 8 points per iteration.

void ellipse(int x, int y, int a, int B)
{
int z, e, t, u, i, j, k, l;
t = z = k = 0;
e = u = a;
i = b;
l = j = a + 1 >> 1;
for (;;) {
point(x + t, y + i);
point(x + t, y - i);
point(x - t, y + i);
point(x - t, y - i);
point(x + u, y + k);
point(x + u, y - k);
point(x - u, y + k);
point(x - u, y - k);
if (t >= u)
return;
t++;
e += (z << 1) + 1;
z++;
if (e >= u << 1) {
e -= u << 1;
u--;
j += b;
if (j > a) {
j -= a;
i--;
}
}
l += b;
if (l > a) {
l -= a;
k++;
}
}
}


It’s a synthesis of

void circle(int x, int y, int r)
{
int z, e, t;
t = z = 0;
e = r;
for (;;) {
point(x + t, y + r);
point(x + t, y - r);
point(x - t, y + r);
point(x - t, y - r);
point(x + r, y + t);
point(x + r, y - t);
point(x - r, y + t);
point(x - r, y - t);
if (t >= r)
return;
t++;
e += (z << 1) + 1;
z++;
if (e >= r << 1) {
e -= r << 1;
r--;
}
}
}

void line(int x0, int y0, int x1, int y1)
{
int a, z;
a = x1 + 1 >> 1;
z = x1 - x0;
y1 -= y0;
for (;;) {
point(x0, y0);
if (x0 == x1)
return;
x0++;
a += y1;
if (z <= a) {
a -= z;
y0++;
}
}
}


#### 3 Replies

0
104 Aug 11, 2013 at 08:32

very clever!!! :) Especially good for some flying saucer game where you see the ufos from an angle!

0
145 Aug 11, 2013 at 08:38

I did the same algorithm in 68000 in 1987.

Except I used self modifying code to do the actual pixel plot, the Atari ST had a strange colour format that made it faster to use smc than anything else.

0
105 Aug 11, 2013 at 09:11

Thanks for the feedback. Note that this rasterizer does overdraw (hence the “about 8 points per iteration”).