Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!hplabs!hpfcdc!hpldola!paul
From: paul@hpldola.HP.COM (Paul Bame)
Newsgroups: comp.graphics
Subject: Re: looking for a fast ellipse algorithm
Message-ID: <11390017@hpldola.HP.COM>
Date: 15 Feb 89 19:55:02 GMT
References: <399@peritek.UUCP>
Organization: HP Elec. Design Div. -ColoSpgs
Lines: 105

ddot(x, y) is the routine for drawing a dot on my display.  When I'm not
running a windowing system, I use a macro which diddles the frame buffer
directly and this algorithm is FAST!!.  It's possible that more clever
use of symmetry relating to the ddot() macro could make this even faster.

Please read the article or contact the author for restrictions of use
of this algorithm.

	-Paul Bame

ellipse(xc, yc, a, b)
register int     xc,
        yc;
int     a,
        b;
/*
 *	Algorithm is presented without comment as was taken from:
 *
 *	"An Efficient Ellipse-Drawing Algorithm"
 *	Jerry R. Van Aken (Texas Instruments, Inc)
 *	IEEE CG&A - September 1984
 *	Translated from PASCAL in figure 7 page 30
 *
 *	Extended from the one-quadrant solution to the multiple
 *	quadrant solution by symmetry.
 */
{
    register int     x,
            y;
    int     t1,
            t2,
            t3,
            t4,
            t5,
            t6,
            t7,
            t8,
            t9;
    register int     d1,
            d2;

    x = a;
    y = 0;
    t1 = a * a;
    t2 = t1 << 1;
    t3 = t2 << 1;
    t4 = b * b;
    t5 = t4 << 1;
    t6 = t5 << 1;
    t7 = a * t5;
    t8 = t7 << 1;
    t9 = 0;

    d1 = (t2 - t7 + t4) >> 1;
    d2 = (t1 >> 1) - t8 + t5;

    ddot(xc + x, yc + 0);
    ddot(xc - x, yc + 0);
    while (d2 < 0)
    {
	ddot(xc + x, yc + y);
	ddot(xc - x, yc + y);
	ddot(xc - x, yc - y);
	ddot(xc + x, yc - y);

	y++;
	t9 += t3;
	if (d1 < 0)
	{
	    d1 += t9 + t2;
	    d2 += t9;
	}
	else
	{
	    x--;
	    t8 -= t6;
	    d1 += -t8 + t9 + t2;
	    d2 += -t8 + t5 + t9;
	}
    }

    do
    {
	ddot(xc + x, yc + y);
	ddot(xc - x, yc + y);
	ddot(xc - x, yc - y);
	ddot(xc + x, yc - y);
	x--;
	t8 -= t6;

	if (d2 < 0)
	{
	    y++;
	    t9 += t3;
	    d2 += -t8 + t5 + t9;
	}
	else
	{
	    d2 += -t8 + t5;
	}
    } while (x >= 0);

    ddot(xc + 0, yc + y);
    ddot(xc + 0, yc - y);
}