6
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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:

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ "Note that lines, ... can be described by an implicit equation with integer coefficients." Do you mean that it is possible to write Bresenham's algorithm as a Diophantine equation? $\endgroup$ – Alexey Popkov Oct 5 '15 at 10:14
  • 1
    $\begingroup$ @AlexeyPopkov: in a way. In the first quadrant, the line equation is 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$ – Yves Daoust Oct 5 '15 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.