From: Psilon AT concentric DOT net (Avery Lee)
Newsgroups: rec.games.programmer,comp.os.msdos.djgpp
Subject: Re: bresenham's circle
Date: Fri, 01 Aug 1997 06:12:55 GMT
Organization: Concentric Internet Services
Lines: 64
Message-ID: <33e27d37.4438718@news.concentric.net>
References: <33DF4527 DOT 671 AT mindspring DOT com> <kn5WwGAfZ$3zEwbB AT jenkinsdavid DOT demon DOT co DOT uk> <33E06240 DOT 3FE7 AT mindspring DOT com> <vMFk6FATSU4zEwx$@jenkinsdavid.demon.co.uk>
NNTP-Posting-Host: ts007d13.sto-ca.concentric.net
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Precedence: bulk

David Jenkins <me AT jenkinsdavid DOT demon DOT co DOT uk> wrote:

>In article <33E06240 DOT 3FE7 AT mindspring DOT com>, Derek Greene
><topcoder AT mindspring DOT com> writes
>>David Jenkins wrote:
>>> Is this Bresenhams circle routine??
>>> Or is it the one where you calculate an eigth of a circle and draw the
>>> full circle from these calcs, never seen that one in action though.
>>
>>according to my info, bresenham's is the one where you calculate the
>>eighth
>
>Is it faster than the routine I posted??
>I did read about it somewhere, I figured that recalculating the eigth to
>the other 7 eigths would take offset the benefits.

No.  The other 7 octants are simply reflections, so you can generate them
by reversing signs or by swapping x and y.  There is no division in the
algorithm, which is very time consuming even on a Pentium.  The drawback to
Bresenham's circle algorithm is that it can only generate circles, so to
get a circle on an output device without a 1:1 aspect ratio, you need to
switch to an ellipse algorithm.

Here is the algorithm I have for the circle, from Ferraro's book:

---------
d = 3 - 2r
x = 0
y = r

while y > x
	plot	xc+x,yc+y
	plot	xc+x,yc-y
	plot	xc-x,yc+y
	plot	xc-x,yc-y
	plot	xc+y,yc+x
	plot	xc+y,yc-x
	plot	xc-y,yc+x
	plot	xc-y,yc-x

	if d >= 0
		d += 4*(x-y)+10
	else
		d += 4*x + 6

--------

One useful optimization to this algorithm is to eliminate the else clause:

	if d >= 0
		d -= 4*y-4

	d += 4*x + 6


-- Avery Lee (Psilon AT concentric DOT net)
Try my freeware junk at http://www.concentric.net/~Psilon
(pages revised 7/30/97 - all programs include source)
* VGAPaint 386 V1.3/1.4b4: 32-bit paint program
* VETools 1.21: 2:1 compression for Watcom executables
* IPXfer5 1.6a: easy file transfers over networks at 450k/s
* Playwav 1.2: PC speaker sound for older computers
* Stellaryx/PC 1.1: Shoot-em-up from the Amiga, ported to the PC
* LMPStat 1.0: Pages of statistics for DOOM ][ .LMP files