From albanycs!leah:rsb584 Sat Jan  9 02:42:36 1988
Received: by albanycs.albany.edu (5.54/4.8)
	id AA08556; Sat, 9 Jan 88 01:49:15 EST
Date: Sat, 9 Jan 88 01:49:12 EST
From: albanycs!leah:rsb584 ( Raymond S Brand)
Received: by leah.Albany.EDU (5.58/1.1)
	id AA04516; Sat, 9 Jan 88 01:49:12 EST
Message-Id: <8801090649.AA04516@leah.Albany.EDU>
To: albanycs:beowulf!rsbx

>From mcdonald@uxe.cso.uiuc.edu Wed Jan  6 12:31:00 1988
Path: leah!uwmcsd1!bbn!oberon!bloom-beacon!gatech!purdue!i.cc.purdue.edu!j.cc.purdue.edu!pur-ee!uiucdcs!uxc.cso.uiuc.edu!uxe.cso.uiuc.edu!mcdonald
From: mcdonald@uxe.cso.uiuc.edu
Newsgroups: comp.graphics
Subject: Re: circles with non-unity aspect ratio
Message-ID: <46900007@uxe.cso.uiuc.edu>
Date: 6 Jan 88 17:31:00 GMT
References: <807@hsi.UUCP>
Lines: 120
Nf-ID: #R:hsi.UUCP:807:uxe.cso.uiuc.edu:46900007:000:3894
Nf-From: uxe.cso.uiuc.edu!mcdonald    Jan  6 11:31:00 1988


>I am trying to draw "good" circles on an AT&T 3b1 (aka, UNIX PC).
>The problem is the aspect ratio - it is nowhere near unity.
>I have gone through McIlroy's paper ("Best Approximate Circles on
>Integer Grids") and Foley & Van Dam.  I see two ways to draw the circle:

>(1) Utilize "user coordinates" (in this case a 4096 by 4096 square)
       Bad idea.

>(2) Utilize "device coordinates" (430 by 288, in this case).
        The correct way.

>Am I missing something simple that would make it easy to draw my
>circles ??  Can anyone point me to another reference that adequately
>covers the drawing of a circle on a screen with a non-unity aspect
>ratio (F & VD mention a few, but before I go digging up the articles,
>does anyone know if these are what I should be looking at) ??

It's not really easy to generate good looking circles on a pixel grid.
After trying lots of different things, I have adopted the following
ellipse drawer. It draws ellipses in pixel space; to get circles you
feed it the proper height and width in pixels. This thine works really
well for circles with a radius greater than 4. For smaller circles,
it pays in terms of looking nice to draw each size as a special case.

The enclosed program uses the standard Bresnahan algorithm for the
best approximation of a curve. It is optimized for speed.

There was a good reference to this an article in Dr. Dobbs Journal in 1987,
but for circles only, not ellipses.

I hope that this can help you.

Doug McDonald
Department of Chemistry
University of Illinois


/* Draw an ellipse with width irx and height iry                         */
/* from a routine by Tim Hogan in Dr. Dobb's Journal May '85 p.40        */
/* Improved by calculating increments incrementally, thus removing all   */
/* multiplies from the loops. These multiplies were very bad since they  */
/* were (long)*(long).                                                   */
/* Written Sept. 7, 1987 by J.D. McDonald (public domain)                */

static long     alpha, beta, alpha2, alpha4, beta2, beta4, d;
static long     ddx, ddy, alphadx, betady;
static int      dy, dx;

extern void     e_start(int, int, int ,int);
extern void     e_xd();	
extern void     e_xdyu();
extern void     e_yu(); 

ellipse(x, y, irx, iry, c)
    int             x, y, irx, iry;
    unsigned        c;
{

    beta = (long) irx *(long) irx;
    alpha = (long) iry *(long) iry;

    if (alpha == 0L)
	alpha = 1L;
    if (beta == 0L)
	beta = 1L;

    dy = 0;
    dx = irx;
    alpha2 = alpha << 1;
    alpha4 = alpha2 << 1;
    beta2 = beta << 1;
    beta4 = beta2 << 1;
    alphadx = alpha * dx;
    betady = 0;
    ddx = alpha4 * (1 - dx);
    ddy = beta2 * 3;

    d = alpha2 * ((long) (dx - 1) * dx) + alpha + beta2 * (1 - alpha);
    e_start(x - dx, x + dx, y, c);
          /* e_start draws left and rightmost pixels on vertical centerline */
          /* e_yu draws a pixel in right top quadrant one up from previous  */
          /* e_xd draws a pixel in right top quadrant one left from previous*/
          /* e_xdyu draws a pixel in right top quadrant up and left from    */
          /* previous. e_yu, e_xd, and e_xdyu also draw the corresponding   */
          /* pixels in the other three quadrants.                           */
          /* c is the color                                                 */
    do {
	if (d >= 0) {
	    d += ddx;
	    dx--;
	    alphadx -= alpha;
	    ddx += alpha4;
	    e_xdyu();
	} else
	    e_yu();
	d += ddy;
	dy++;
	betady += beta;
	ddy += beta4;
    } while (alphadx > betady);

    d = beta2 * ((long) dy * (dy + 1)) + alpha2 * ((long) dx * (dx - 2) + 1) 
	+ beta * (1 - alpha2);
    ddx = alpha2 * (3 - (dx << 1));
    ddy = beta4 * (1 + dy);

    do {
	if (d <= 0) {
	    d += ddy;
	    ddy += beta4;
	    dy++;
	    e_xdyu();
	} else
	    e_xd();
	d += ddx;
	ddx += alpha4;
	dx--;
    } while (dx > 0);
}