DSeal@acorn.co.uk (10/16/89)
A fairly fast way to do arbitrarily aligned ellipses is to regard them as sheared axis-aligned ellipses. Suppose you want an ellipse centred at (0,0). Assuming your scan lines are parallel to the X-axis, use a shear parallel to the X-axis. If the top-most point of the ellipse is (xtop,ytop) and the positive intersect of the ellipse with the X axis is (xside,0), then your ellipse is the result of shearing the axis-aligned ellipse with semi-X-axis xside and semi-Y-axis ytop, using the shear given by (x',y') = (x + y*xtop/ytop, y). [Formulae for xtop, ytop and xside in terms of the semi-major axis M, the semi-minor axis m and the angle a of the major axis are: ytop = SQR( (M*SIN(a))^2 + (m*COS(a))^2 ) xtop = (M^2-m^2)*SIN(a)*COS(a)/ytop xside = M*m/ytop Fortunately, these calculations only have to be done once per ellipse! ] To implement this for a filled ellipse, run an axis-aligned ellipse algorithm for semi-X-axis xside and semi-Y-axis ytop and a line algorithm running from (0,0) to (xtop,ytop) in parallel. (Both algorithms can be Bresenham-type algorithms and thus involve only a few easy arithmetic operations per iteration.) On each scan line, you get an intercept (xline,y) with the line and two intercepts (-xell,y) and (xell,y) with the axis-aligned ellipse. Fill the scan line segment from (xline-xell,y) to (xline+xell,y). To do an ellipse outline, do the same thing, except that you end up by comparing the calculated scan line segment with the one calculated on the adjacent scan lines: from this you can determine which pixels are boundary pixels of the solid ellipse and so should be plotted. One defect of this technique is that you can get aliasing effects between the line algorithm and the axis-aligned ellipse algorithm. To reduce these, keep the X co-ordinates to higher than pixel resolution. We first used this technique at Acorn in 1984 to do general ellipses on the BBC Master (a 6502-based machine). It has since also been used on the Archimedes, which is ARM-based. Typical plotting times for a large filled ellipse (about 200 pixels high by 280 pixels wide, with xtop=ytop=xside=100) are: 6502: (filled) 0.565 seconds (outline) 0.515 seconds ARM: (filled) 0.017 seconds (outline) 0.022 seconds [The change in the relative timing between processors reflects the ARM's ability to fill scan line segments very quickly using multiple-register store instructions.] This technique is not claimed to be mathematically perfect in any way, but it produces reasonable results and is reasonably fast. David Seal Acorn Computers Ltd., Fulbourn Road, Cambridge CB1 4JN, U.K. <insert standard disclaimers>