Back in the day when you often had to write your own low level rendering algorithms we all used to learn the Bresenham algorithms for lines and circles.
It was almost trivially easy to extend the Bresenham circle algorithm to cover ellipses whose axes were parallel to the X and Y axes.
But it always eluded me if there was some Bresenham-style way to render an arbitrary ellipse whose axes were at some arbitrary angle.
Does such a scanline method for rotated ellipses exist?
The classic book Computer Graphics: Principles and Practice (second edition) by Foley, van Dam, et al. describes such an algorithm in section 19.2.
The explanation in the book seems to come from an MSc thesis, Raster Algorithms for 2D Primitives by Dilip Da Silva.
See also these papers:
Curve-drawing algorithms for raster displays by Van Aken and Novak (ACM TOG, 1985).
A tracking algorithm for implicitly defined curves by Chandler (IEEE Computer Graphics and Applications, 1988).
All conics (including rotated ellipses) can be described by an implicit equation of the form
H(x, y) = A x² + B xy + C y² + D x + E y + F = 0
The basic principle of the incremental line tracing algorithms (I wouldn't call them scanline) is to follow the pixels that fulfill the equation as much as possible.
Depending on the local slope of the line, you progress more in the x or y direction, following either a lateral or diagonal move. This decision is made so that you minimize the absolute value of H(x, y).
In the case of a straight line, the slope is a constant so that lateral and diagonal moves are always in the same direction.
In the case of a circular arc, the slope varies and one can distinguish 8 cases corresponding to 8 octants of the curve (there are four possible lateral moves and for each two diagonal moves).
For the ellipse and other conics, you can generalize the octant decomposition. This leads to a rather tedious discussion.
You can avoid the octant discussion and modify the algorithm to look at all neighbors of the current pixel. This leads to a general contour tracing algorithm like Moore's neighborhood, where you will follow the outline of the area H(x, y) >= 0.
Note that lines, circles and axis-aligned ellipses can be described by an implicit equation with integer coefficients. This is no more possible with general conics and you will need to resort to floating-point, or good rational approximations.
Lastly, note that incremental computation saves work when evaluating H, on the line of
H(x+1, y) = H(x, y) + A.(2x+1) + B.y + D = H(x, y) + (2A).x + (A + B.y + D)
A true scanline solution is also possible. Let y vary incrementally, and solve the H equation for x:
H(x, y) = A x² + (B y + D) x + (C y² + E y + F) = 0
This will yield two x values for each y. The resulting curve will be much less pleasant as it will always count two pixels per row, which will leave holes when the slope is below 1. You can cope by filling the stretch of pixels between the roots on the successive rows.
Y-Y_0=(X-X0)(Y1-Y0)/(X1-X0), which gives rational Y's. Setting Z=Y(X1-X0), the equation becomes Z-Z0=(X-X0)(Y1-Y0), of the form Z=aX+b.
$\endgroup$
H is wrong in general. Instead, the sign of H at a midpoint should be checked. A counter example is p=(0, 3) vs q=(1, 3) for an ellipse, H = 16 x^2 + y^2 - 16, where |H(p)| = 7, |H(q)| = 9, but you should choose q.
$\endgroup$