Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!uunet!munnari.oz.au!bruce!dbrmelb!davidp
From: davidp@dbrmelb.dbrhi.oz (David Paterson)
Newsgroups: comp.graphics
Subject: Re: Tilted Ellipse
Message-ID: <649@dbrmelb.dbrhi.oz>
Date: 10 Nov 89 00:46:19 GMT
Organization: CSIRO, Div. Building Constr. and Eng'ing, Melb., Australia
Lines: 77


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.