Xref: utzoo comp.graphics:4505 sci.math:5723 comp.sources.wanted:6402
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!leah!itsgw!steinmetz!uunet!hsi!stevens
From: stevens@hsi.UUCP (Richard Stevens)
Newsgroups: comp.graphics,sci.math,comp.sources.wanted
Subject: Re: looking for a fast ellipse algorithm
Summary: here is a fast ellipse algorithm
Keywords: ellipse, graphics, circle
Message-ID: <301@hsi86.hsi.UUCP>
Date: 16 Feb 89 19:28:28 GMT
References: <399@peritek.UUCP> <1311@ndmath.UUCP> <1403@mtunb.ATT.COM>
Organization: Health Systems Intl., New Haven, CT
Lines: 71

/*
 * Draw an ellipse.
 *
 * The algorithm is from "An Efficient Ellipse-Drawing Algorithm" by
 * Jerry R. Van Aken, IEEE CG&A, September 1984, pp. 24-35,
 * specifically, Figure 10 on page 32.
 */

#include	"plot.h"	/* need definition of PLOT() */

ellipse(centerx, centery, a, b)
int    centerx, centery;	/* center of ellipse, in device coordinates */
int    a, b;			/* a = "radius" in x, b = "radius" in y */
{
	register long	d1, d2;
	register short	x, y;
	register long	t1, t2, t3, t4, t5, t6, t7, t8, t9;

	/* intermediate terms to speed up loop */
	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 = 0L;

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

	x = a;
	y = 0;

	while (d2 < 0) {		/* region 1 of ellipse */
		/* draw 4 points using symmetry */
	    	PLOT(centerx + x, centery + y);
	    	PLOT(centerx + x, centery - y);
	    	PLOT(centerx - x, centery + y);
	    	PLOT(centerx - x, centery - y);

		y++;		/* always move up here */
		t9 += t3;	
		if (d1 < 0) {		/* move straight up */
			d1 += t9 + t2;
			d2 += t9;
		} else {		/* move up and left */
			x--;
			t8 -= t6;
			d1 += t9 + t2 - t8;
			d2 += t9 + t5 - t8;
		}
	}

	do {				/* region 2 of ellipse */
		/* draw 4 points using symmetry */
	    	PLOT(centerx + x, centery + y);
	    	PLOT(centerx + x, centery - y);
	    	PLOT(centerx - x, centery + y);
	    	PLOT(centerx - x, centery - y);

		x--;		/* always move left here */
		t8 -= t6;	
		if (d2 < 0) {	/* move up and left */
			y++;
			t9 += t3;
			d2 += t9 + t5 - t8;
		} else		/* move straight left */
			d2 += t5 - t8;
	} while (x >= 0);
}
-------------------------------------------------------------
	Richard Stevens
	Health Systems International, New Haven, CT
	   stevens@hsi.com
           ... { uunet | yale } ! hsi ! stevens