connors@druco.ATT.COM (ConnorsPA) (10/08/89)
Does anyone have an algorithm, or code, for drawing a TILTED ellipse quickly on a bit-mapped device? How does one do that? ----------------------------- Paul Connors Email: att!druco!connors -----------------------------
mcdonald@uxe.cso.uiuc.edu (10/10/89)
> Does anyone have an algorithm, or code, for drawing > a TILTED ellipse quickly on a bit-mapped device? No, but I too would like one. I have gotten replies to this question before, but they were all too slow. Doug McDonald (mcdonald@uxe.cso.uiuc.edu)
jay@phobos.cis.ksu.edu (Jay Windley) (10/11/89)
>> Does anyone have an algorithm, or code, for drawing >> a TILTED ellipse quickly on a bit-mapped device? >No, but I too would like one. So would I. -- Jay Windley - Dept. of Computer & Information Sciences - Kansas State Univ. Internet: jay@phobos.cis.ksu.edu | Bitnet: JWINDLEY@KSUVM.bitnet | "Incontheivable!" UUCP: can't remember. | -Vizzini, THE PRINCESS BRIDE.
mccaugh@s.cs.uiuc.edu (10/12/89)
connors@druco.ATT.COM (Paul Connors) writes: > Does anyone have an algorithm, or code, for drawing > a TILTED ellipse quickly on a bit-mapped device? Assuming you can plot the pixels of an un-tilted ellipse (horizontal major axis and vertical minor axis) -- say, from: (x-h)^2 (y-k)^2 ---- + ---- = 1, (centered at <h,k>) a^2 b^2 the new coordinates <x',y'> of the point <x,y> on the original ellispe rotated an angle @ about its origin (at <h,k>) are as follows: x' = u + h, where: u = (x-h)*cos(@) - (y-k)*sin(@) and y' = v + k, where: v = (x-h)*sin(@) + (y-k)*cos(@) Scott McCaughrin University of Illinois (mccaugh@s.cs.uiuc.edu)
mcdonald@uxe.cso.uiuc.edu (10/13/89)
/* Written 11:35 pm Oct 10, 1989 by mccaugh@s.cs.uiuc.edu in uxe.cso.uiuc.edu:comp.graphics */ connors@druco.ATT.COM (Paul Connors) writes: > Does anyone have an algorithm, or code, for drawing > a TILTED ellipse quickly on a bit-mapped device? Assuming you can plot the pixels of an un-tilted ellipse (horizontal major axis and vertical minor axis) -- say, from: (x-h)^2 (y-k)^2 ---- + ---- = 1, (centered at <h,k>) a^2 b^2 the new coordinates <x',y'> of the point <x,y> on the original ellispe rotated an angle @ about its origin (at <h,k>) are as follows: x' = u + h, where: u = (x-h)*cos(@) - (y-k)*sin(@) and y' = v + k, where: v = (x-h)*sin(@) + (y-k)*cos(@) Scott McCaughrin University of Illinois (mccaugh@s.cs.uiuc.edu) /* End of text from uxe.cso.uiuc.edu:comp.graphics */ I see that you are also at the U of Ill. Are you a grad or undergrad? If you are an undergrad, did you take freshman English? CAn you read??? The request was for a FAST tilted ellipse drawer. I, and probably most other people, are perfectly aware of rotation matrices. But rotating point by point with a rotation matrix is hardly FAST. In fact it is b...o...g s........l.........o..........w. Even with cos and sin tables. What I am looking for is something that can be stuck in Bresnahan's algorithm. And, please, have some nice way of specifying the ellipse (like major and minor axes and rotation angle, or tangent thereof. Doug McDonald
mima@pattern.flab.fujitsu.co.jp (MIMA T.) (10/13/89)
In article <4821@druco.ATT.COM>, connors@druco.ATT.COM (ConnorsPA) says: > Does anyone have an algorithm, or code, for drawing > a TILTED ellipse quickly on a bit-mapped device? How about Pitteway's method ? M.L.V.Pitteway,`Algorithm for drawing ellipses or hyperbolae with a digital plotter," COMPUTER JOURNAL, vol.10, no.3, pp.282-289, Nov.1967. It's for drawing conic section curve segment, with incremental strategy like Bresenham's DDA. Inner cycle consists of three additions and one test for each move. -- MIMA, Toshiya Fujitsu Laboratories Ltd. Tel: +81 44 777-1111 ext.2-6182 E-mail: mima@flab.fujitsu.co.jp
paquin@kahua.esd.sgi.com (Tom Paquin) (10/14/89)
A fast integer algorithm for tilted ellipses was done by Art Kauffman while he was at IBM and is patented. I have no idea how IBM is treating the patent. Some they enforce, others they don't. Find the patent by author, email me and I'll try to get you the patent #, or look in the AIX "GSL" code if you can get it and find the routines... -Tom ***** Opinions are mine, not SGI's
davidp@dbrmelb.dbrhi.oz (David Paterson) (10/16/89)
>> a TILTED ellipse quickly on a bit-mapped device? > No, but I too would like one. > I have gotten replies to this question before, but they were all too > slow. > > Doug McDonald (mcdonald@uxe.cso.uiuc.edu) Here are two fast algorithms for computing a tilted ellipse. Any such algorithm has four stages. 1) Calculate once for all ellipses 2) Calculate once for each ellipse 3) Calculate points of first ellipse 4) Calculate points of subsequent ellipses You've almost certainly already seen the algorithm based on x = a sin(@) + b cos(@) + c y = d sin(@) + e cos(@) + f The constants a, b, c, d, e, f are fairly easy to calculate when given the major axis, minor axis, centre and slope of the ellipse. They are also fairly easy to calculate when you are looking for an ellipse inside a given parallelogram. They can be found by first looking at a circle in a square and then transforming the square into a parallelogram. This method, given equal increments of @, will put most points where the curvature of the ellipse is greatest and this allows you to minimise the number of points required for given accuracy. In this method sin(@) and cos(@) are calculated once for all ellipses so at step 3 above there are two array accesses, four multiplications and 5 additions at each point. (Don't forget the addition required in incrementing @). A faster algorithm can be made based on x = a sin(@) + b y = c sin(@+d) + e The constants a, b, c, d, e are not so easy to calculate when given the centre, axis lengths and slope of the ellipse. For a low accuracy ellipse the cost of calculations at step 2 above could be significant. However, a, b, c, d, e are easy to calculate based on XMIN, XMAX, YMIN, YMAX and (X at Y=YMAX). In this method sin(@) is calculated once for all ellipses so at step 3 above there are two array accesses, two multiplications and four additions at each point. This could be the fastest possible method for calculating a single sloping ellipse to desired accuracy. It will not be very inefficient for calculating subsequent ellipses in step 4 either. David Paterson, davidp@dbrmelb.dbrhi.oz
davidp@dbrmelb.dbrhi.oz (David Paterson) (11/10/89)
Stephen Johnson of Sun Microsystems, California asks:
$ Maybe someone has a better technique for generating that skewed
$ ellipse at the quickest speed possible.
Here are two related methods. The first method is best if the maximum
speed at given (imperfect) accuracy is required. It is faster than
the second method which gives the maximum speed at perfect accuracy.
By the way, I can't think of any algorithm that works more than twenty
per cent faster for non-tilted ellipses than tilted ones.
Lets suppose that the tilted ellipse is specified by the
major axis, minor axis, x at centre, y at centre and slope.
Call these values MAJOR, MINOR, Xcentre, Ycentre, SLOPE.
The tilted ellipse has points with coordinates:
X = Xcentre + a cos(@) + b sin(@)
Y = Ycentre + c cos(@) + d sin(@)
where:
a = .5 * MAJOR * cos(SLOPE)
b = -.5 * MINOR * sin(SLOPE)
c = .5 * MAJOR * sin(SLOPE)
d = .5 * MINOR * cos(SLOPE)
by redefining the origin of @ this can be converted to:
X = Xcentre + A * sin(@)
Y = Ycentre + B * sin(@ + ANGLE)
where:
A = sqrt(a*a+b*b)
B = sqrt(c*c+d*d)
ANGLE = arcsin(c/B)-arcsin(a/A)
The values A, B and ANGLE are calculated once for each ellipse.
-----
METHOD 1
Precalculate sin(@) once for all ellipses.
Find Xcentre, Ycentre, A, B, and ANGLE once for each ellipse.
Increment @ and find X and Y from
X = Xcentre + A * sin(@)
Y = Ycentre + B * sin(@ + ANGLE)
Join new values of X and Y to old values of X and Y with a straight line.
By adjusting the increment of @ you can adjust the speed and accuracy
of the resulting ellipse.
-----
METHOD 2
Precalculate sin(@) and arcsin(@) once for all ellipses.
Find Xcentre, Ycentre, 1/A, B, and ANGLE once for each ellipse.
Increment X and find Y from
@ = arcsin((X-Xcentre) * (1/A))
Y = Ycentre + B * sin(@ + ANGLE)
Join new value of Y to old value of Y with a vertical line.
Here X is incremented one pixel at a time. Don't forget that
arcsin has two values; one for the top half of the ellipse and
one for the bottom half.
-----
David Paterson,
davidp@dbrmelb.dbrhi.oz
CSIRO Division of B,C & E,
PO Box 56 Highett, Victoria. 3190.