Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!wuarchive!gem.mps.ohio-state.edu!uakari.primate.wisc.edu!ames!uhccux!munnari.oz.au!bruce!dbrmelb!davidp
From: davidp@dbrmelb.dbrhi.oz (David Paterson)
Newsgroups: comp.graphics
Subject: Re: Tilted ellipse.
Summary: Two alternative fast methods
Message-ID: <634@dbrmelb.dbrhi.oz>
Date: 16 Oct 89 04:14:42 GMT
References: <4821@druco.ATT.COM>
Organization: CSIRO, Div. Building Constr. and Eng'ing, Melb., Australia
Lines: 55

>>	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