stevens@hsi.UUCP (Richard Stevens) (01/05/88)
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)
in which case I can use the algorithms as-is, however for each
point on the 4096x4096 grid that I want to plot, I have to
convert the point to device coordinates (430 by 288 for a
square area on the 3b1). However, I'd guess that this will
lead to a "messy" circle (i.e., not meeting McIlroy's
"thinness" or "connectivity" criteria). Perhaps in this case,
since I'd be going from a bigger coordinate space to a smaller
one, there won't be any holes in the circle, but in general,
I'd think a transformation like this could destroy some of
the properties that the algorithm tries to preserve.
Furthermore, this technique will take more time, since I'm
calculating all the points on a 4096x4096 grid, when I'm really
plotting on a much smaller area. Each step of the loop will
also require a transformation of the x and y coordinates,
which will take more time.
(2) Utilize "device coordinates" (430 by 288, in this case).
Here I need convert the circle parameters only once, instead
of each time through the loop, however what I'm really drawing
is an ellipse of pixels (that will appear as a circle on the
screen). The two references that I've looked at don't go into
this case.
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) ??
Richard Stevens
Health Systems International, New Haven, CT
{ uunet | ihnp4 } ! hsi ! stevensmcdonald@uxe.cso.uiuc.edu (01/07/88)
>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); }
jackm@devvax.JPL.NASA.GOV (Jack Morrison) (01/09/88)
A few requests for ellipses have prompted me to include this code. It
draws ellipses (including circles, of course) of varying line width
on a SUN bitmap display. (It's part of a paint-type program). I don't
know how this compares to the earlier posting of an ellipse algorithm,
but it's fairly fast.
Enjoy or flame....
=====================================================================
/***********************************************/
/* gred_ellipse.c - draw ellipses *
/* algorithm from IEEE CG&A Sept 1984 p.24 *
/***********************************************/
#include <stdio.h>
#include <sunwindow/window_hs.h>
gred_ellipse (cx, cy, radius_x, radius_y, line_width, pw, pattern_pr)
int cx, cy;
int radius_x, radius_y;
int line_width;
struct pixwin *pw;
struct pixrect *pattern_pr;
{
struct pixrect *pr;
int inner_radius_x;
int inner_radius_y;
int outer_radius_x;
int outer_radius_y;
/*******************************************************************/
/* Calculate the inner, outer radiuses of the ellipse */
/*******************************************************************/
/* if one pixel wide, radiuses are same */
if (line_width < 2)
{
inner_radius_x = outer_radius_x = radius_x;
inner_radius_y = outer_radius_y = radius_y;
}
else
{
outer_radius_x = radius_x + (line_width >> 1);
outer_radius_y = radius_y + (line_width >> 1);
inner_radius_x = outer_radius_x - line_width + 1;
inner_radius_y = outer_radius_y - line_width + 1;
}
/*******************************************************************/
/* Create a pixrect to build the ellipse in. */
/*******************************************************************/
pr = mem_create ((outer_radius_x << 1) + 1, (outer_radius_y << 1) + 1, 1);
/* now clear it */
pr_rop (pr, 0, 0, pr -> pr_size.x, pr -> pr_size.y,
PIX_CLR, (struct pixrect *) 0, 0, 0);
/*******************************************************************/
/* If the inner_radius > 0 then outline the inner edge. */
/* Then if the outer radius of the ellipse is > than the inner */
/* radius, call the fill ellipse routine with the outer radius. */
/*******************************************************************/
if ((inner_radius_x > 0)
&& (inner_radius_y > 0))
outline_ellipse (pr, outer_radius_x, outer_radius_y,
inner_radius_x, inner_radius_y);
if (line_width >= 2)
fill_ellipse(pr, outer_radius_x, outer_radius_y,
outer_radius_x, outer_radius_y);
/*******************************************************************/
/* Now write the ellipse out to the window. */
/*******************************************************************/
inner_radius_x = inner_radius_y = 0; /* normal source offset */
if ((cx -= outer_radius_x) < 0) /* ellipse extends beyond left edge? */
{
inner_radius_x = -cx;
cx = 0;
}
if ((cy -= outer_radius_y) < 0) /* above top edge? */
{
inner_radius_y = -cy;
cy = 0;
}
if (pattern_pr == NULL)
pw_write (pw, cx, cy, pr->pr_size.x-inner_radius_x, pr->pr_size.y-inner_radius_y,
PIX_SRC ^ PIX_DST, pr, inner_radius_x, inner_radius_y);
else
pw_stencil (pw, cx, cy, pr -> pr_size.x, pr -> pr_size.y,
PIX_SRC, pr, inner_radius_x, inner_radius_y, pattern_pr, 0, 0);
pr_destroy (pr);
}
/* draw ellipse incrementally */
static outline_ellipse (pr, center_x, center_y, rx, ry)
struct pixrect *pr;
int center_x, center_y;
int rx, ry;
{
/* intermediate terms to speed up loop */
long t1 = rx*rx, t2 = t1<<1, t3 = t2<<1;
long t4 = ry*ry, t5 = t4<<1, t6 = t5<<1;
long t7 = rx*t5, t8 = t7<<1, t9 = 0L;
long d1 = t2 - t7 + (t4>>1); /* error terms */
long d2 = (t1>>1) - t8 + t5;
register int x = rx, y = 0; /* ellipse points */
while (d2 < 0) /* til slope = -1 */
{
/* draw 4 points using symmetry */
pr_put (pr, center_x + x, center_y + y, 1);
pr_put (pr, center_x + x, center_y - y, 1);
pr_put (pr, center_x - x, center_y + y, 1);
pr_put (pr, center_x - x, center_y - y, 1);
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 /* rest of top right quadrant */
{
/* draw 4 points using symmetry */
pr_put (pr, center_x + x, center_y + y, 1);
pr_put (pr, center_x + x, center_y - y, 1);
pr_put (pr, center_x - x, center_y + y, 1);
pr_put (pr, center_x - x, center_y - y, 1);
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);
}
static fill_ellipse (pr, center_x, center_y, rx, ry)
struct pixrect *pr;
int center_x, center_y;
int rx, ry;
{
long t1 = rx*rx, t2 = t1<<1, t3 = t2<<1;
long t4 = ry*ry, t5 = t4<<1, t6 = t5<<1;
long t7 = rx*t5, t8 = t7<<1, t9 = 0;
long d1 = t2 - t7 + (t4>>1); /* error terms */
long d2 = (t1>>1) - t8 + t5;
register int x = rx, y = 0; /* ellipse points */
register int t; /* used in fill operation */
int wid; /* width of fill */
while (d2 < 0) /* til slope = -1 */
{
/* fill in leftward to inner ellipse */
for (t=x; (!pr_get(pr, center_x+t, center_y+y)) && t; t--);
wid = x - t + 1;
pr_rop (pr, center_x+t, center_y+y, wid, 1,
PIX_SET | PIX_DONTCLIP, NULL, 0, 0);
pr_rop (pr, center_x-x, center_y+y, wid, 1,
PIX_SET | PIX_DONTCLIP, NULL, 0, 0);
pr_rop (pr, center_x+t, center_y-y, wid, 1,
PIX_SET | PIX_DONTCLIP, NULL, 0, 0);
pr_rop (pr, center_x-x, center_y-y, wid, 1,
PIX_SET | PIX_DONTCLIP, NULL, 0, 0);
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 /* rest of top right quadrant */
{
/* fill in downward to inner ellipse */
for (t=y; (!pr_get(pr, center_x+x, center_y+t)) && t; t--);
wid = y - t + 1;
pr_rop (pr, center_x+x, center_y+t, 1, wid,
PIX_SET | PIX_DONTCLIP, NULL, 0, 0);
pr_rop (pr, center_x+x, center_y-y, 1, wid,
PIX_SET | PIX_DONTCLIP, NULL, 0, 0);
pr_rop (pr, center_x-x, center_y+t, 1, wid,
PIX_SET | PIX_DONTCLIP, NULL, 0, 0);
pr_rop (pr, center_x-x, center_y-y, 1, wid,
PIX_SET | PIX_DONTCLIP, NULL, 0, 0);
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);
}
--
Jack C. Morrison Jet Propulsion Laboratory
(818)354-1463 jackm@jpl-devvax.jpl.nasa.gov
"The paycheck is part government property, but the opinions are all mine."