There is an efficient algorithm for drawing an ellipse, which can be easily modified to draw a filled ellipse. The ellipse may be stretched horizontally and vertically as you like, but not in other directions (this is rarely wanted).

However, I'll first show you an algorithm for drawing a circle, which is simpler. It is called the 'mid-point' algorithm. If you understand, I'll take you through the modifications you'll need for a filled ellipse. There are also some significant optimizations I'll show you later if you're still interested. Here is the basic algorithm for a circle of radius r, centred on (cx, cy):

// begin at the 'top' of the circlex := 0;y := r;plot8(x, y);// plot the first eighth of the circlewhile (x <= y){ // move across a single pixel x := x + 1; // decide whether or not we need to move down a pixel as well, // by looking at whether or not (x, y - 0.5) is within the // radius of the circle. if (x^2 + (y - 0.5)^2 > r^2) {  // if (x, y - 0.5) is outside, then the circle is closer to  // (x, y - 1) than (x, y), so move down one pixel.  y := y - 1;  // we never need to go down by more than one pixel, since we  // stop an eighth of the way around, so the gradient is  // always under 45 degrees. } plot8(x, y);}

The key to drawing the whole circle is the plot8 function, which actually plots 8 pixels:
(cx + x, cy + y)
(cx - x, cy + y)
(cx + x, cy - y)
(cx - x, cy - y)
(cx + y, cy + x)
(cx - y, cy + x)
(cx + y, cy - x)
(cx - y, cy - x)

Hopefully I haven't made any mistakes there. :)

Is it axis aligned or in general position ?

Whatever, the general algo uses the fact that it's convex. You just need to write horizontal lines (spans). For any convex the general algo simply looks like this :

for(y=ymin; y<=ymax; y++) span(xmin(y), xmax(y))

The difficulty is only in defining and implementing the xmin(y) and xmax(y) functions efficiently. Normally it requires a square root, today it's cheap.

Also care should be taken with the discretization, so that only the centers of pixels inside the ellipse are rendered. Google search. Anti-aliasing also makes things quite more difficult.

Note the pixel8 trick is only useful because of the circle symetries. Anyway it's not hardware (cache, write-burst, etc...) friendly. A video memory is always organized by rows.

Quote:Original post by Charles B

Whatever, the general algo uses the fact that it's convex. You just need to write horizontal lines (spans). For any convex the general algo simply looks like this :

for(y=ymin; y<=ymax; y++) span(xmin(y), xmax(y))

Yes, that's how you produce a filled ellipse from an unfilled ellipse algorithm. The ellipse algorithm's job is to produce the min / max values for each row.

Quote:The difficulty is only in defining and implementing the xmin(y) and xmax(y) functions efficiently. Normally it requires a square root, today it's cheap.

No, it doesn't require a square root. The most conceptually simple algorithms might do, but the one I posted above only uses multiplication - and I can show you how to reduce it to only addition / subtraction / comparison inside the loop.

Quote:Anti-aliasing also makes things quite more difficult.

Yes, it would make things a bit harder. I'm not sure what the best anti-aliased method would be, but I bet it can be done without a square root. [smile]

Quote:Note the pixel8 trick is only useful because of the circle symetries.

An ellipse still has four-way symmetry though. You can loop through two eighths of the ellipse instead of one.

Quote:Anyway it's not hardware (cache, write-burst, etc...) friendly. A video memory is always organized by rows.

Yes it is. After you've run the midpoint algorithm, you plot the actual pixels in rows in the manner you suggested.

To draw the first section of an ellipse, a few things need to be changed:

1) the test:

if (x^2 + (y - 0.5)^2 > r^2)

can be rewritten (divide both sides by r^2):

if (x^2/r^2 + (y - 0.5)^2/r^2 > 1)

It's then possible to use a different radius in the x and y directions, lets call them 'a' and 'b' respectively:

if (x^2/a^2 + (y - 0.5)^2/b^2 > 1)

Which can be rewritten back without the division (multiply both sides by a^2 * b^2):

if (x^2 * b^2 + (y - 0.5)^2 * a^2 > a^2 * b^2)

2) the loop guard (x <= y) must be changed because that equation no longer identifies the region of less than 45 degree slope. If I've done my differentiation correctly, (x.b^2 <= y.a^2) will do instead.

3) plot only four pixels, because there is only four-way symmetry:
(cx + x, cy + y)
(cx - x, cy + y)
(cx + x, cy - y)
(cx - x, cy - y)

This should work, except that parts of the ellipse are missing. I think you can draw the remaining parts with another loop, identical to the first except that the pairs (x, y), (cx, cy) and (a, b) are swapped in every occurrence.
edit: except when you plot pixels!

There are some major optimizations, which are actually pretty simple to implement. However, before we confuse things I'd like you to get an implementation working. I've only done circles before, and I'd like reassuring that I've got it right so far.

Most of the optimizations have to do with storing the values of various equations and updating them each iteration, instead of recalculating them. To begin with, we can add a variable v1, with invariant:

v1 = x^2 * b^2 + (y - 0.5)^2 * a^2 - 0.25

i.e. whenever we change x or y, we'll change v1 so that this formula remains true. With this new variable, we don't have to recalculate the formula at each step (the -0.25 part is only there so that it is always integer - you don't need a float; it never affects the outcome of any of the comparisons):

// begin at the 'top' of the ellipsex := 0;y := r;v1 := (r^2 - r) * a^2; // = x^2 * b^2 + (y - 0.5)^2 * a^2 - 0.25plot4(x, y);// plot the first eighth of the ellipsewhile (x * b^2 <= y * a^2){ // move across a single pixel (update x and v1) v1 := v1 + (2x + 1) * b^2; x := x + 1; // decide whether or not we need to move down a pixel as well, // by looking at whether or not (x, y - 0.5) is within the // radius of the circle. if (v1 > a^2 * b^2) {  // if (x, y - 0.5) is outside, then the circle is closer to  // (x, y - 1) than (x, y), so move down one pixel.  v1 := v1 + (2 - 2 * y) * a^2; y := y - 1;  // we never need to go down by more than one pixel, since we  // stop an eighth of the way around, so the gradient is  // always under 45 degrees. } plot4(x, y);}

You can trivially pre-calculate:
v2 = a^2
v3 = b^2
v4 = a^2 * b^2
as follows:

// begin at the 'top' of the ellipsex := 0;y := r;v1 := (r^2 - r) * a^2; // = x^2 * b^2 + (y - 0.5)^2 * a^2 - 0.25v2 := a^2;v3 := b^2;v4 := v2 * v3;plot4(x, y);// plot the first eighth of the ellipsewhile (x * v3 <= y * v2){ // move across a single pixel (update x and v1) v1 := v1 + (2x + 1) * v3; x := x + 1; // decide whether or not we need to move down a pixel as well, // by looking at whether or not (x, y - 0.5) is within the // radius of the circle. if (v1 > v4) {  // if (x, y - 0.5) is outside, then the circle is closer to  // (x, y - 1) than (x, y), so move down one pixel.  v1 := v1 + (2 - 2 * y) * v2; y := y - 1;  // we never need to go down by more than one pixel, since we  // stop an eighth of the way around, so the gradient is  // always under 45 degrees. } plot4(x, y);}

Next up:
v5 = (2x + 1) * v3
v6 = (2 - 2 * y) * v2
(v6 is usually a negative number)
Like v1, these need updating as x and y change:

// begin at the 'top' of the ellipsex := 0;y := r;v1 := (r^2 - r) * a^2; // = x^2 * b^2 + (y - 0.5)^2 * a^2 - 0.25v2 := a^2;v3 := b^2;v4 := v2 * v3;v5 := v3;v6 := (2 - 2 * r) * v2;plot4(x, y);// plot the first eighth of the ellipsewhile (x * v3 <= y * v2){ // move across a single pixel (update x and v1) v1 := v1 + v5; v5 := v5 + 2 * v3; x := x + 1; // decide whether or not we need to move down a pixel as well, // by looking at whether or not (x, y - 0.5) is within the // radius of the circle. if (v1 > v4) {  // if (x, y - 0.5) is outside, then the circle is closer to  // (x, y - 1) than (x, y), so move down one pixel.  v1 := v1 + v6;  v6 := v6 + 2 * v2;  y := y - 1;  // we never need to go down by more than one pixel, since we  // stop an eighth of the way around, so the gradient is  // always under 45 degrees. } plot4(x, y);}

Finally, you can pre-calculate 2 * v2 and 2 * v3, and add variables for x * v3 and y * v2. After that, you should only have addition, subtraction and comparison inside the loop.