An ellipse rasterizer

40fd50c8665e5b5f4233e4c0587a9d47
2
17_Gen_r 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

Please log in or register to post a reply.

Fd80f81596aa1cf809ceb1c2077e190b
0
rouncer 103 Aug 11, 2013 at 08:32

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

B5262118b588a5a420230bfbef4a2cdf
0
Stainless 151 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.

40fd50c8665e5b5f4233e4c0587a9d47
0
17_Gen_r 105 Aug 11, 2013 at 09:11

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