DSeal@acorn.co.uk (03/02/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, you want to use a shear parallel to the X-axis. So calculate the top-most point of the ellipse (xtop,ytop) and the positive intersect of the ellipse with the X axis (xside,0). This ellipse is the result of shearing the axis-aligned ellipse with semi-X-axis xside and semi-Y-axis ytop, with 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 few arithmetic operations.) 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. You want to 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 previous scan line: 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 used this technique at Acorn to do general ellipses on the BBC Master (a 6502-based machine) and the Archimedes (ARM-based). Typical plotting times for a large filled axis-aligned 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