Sign in to follow this  
Chocoboko

Plotting pixels of a filled ellipse

Recommended Posts

Hi, I am trying to draw a filled ellipse on a 2D screen (using SDL). Would you happen to have any idea on how to develop an algorithm draw a filled ellipse? As in, what would I need to calculate in order to draw the ellipse.

Share this post


Link to post
Share on other sites
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 circle
x := 0;
y := r;

plot8(x, y);
// plot the first eighth of the circle
while (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. :)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
I tried it. For the most part, it works. Though, as you said, some sides do not draw. I'll have to try that loop you described. But for the most part, it works. How can I optimize this now? Thank you.

Share this post


Link to post
Share on other sites
search for bresenham ellipse (you don't even need a multiplications! )

Let xr,yr it's x radius and y radius.
a*x2+b*y2=c
it's equation of aligned ellipse.
Where
a=1/(xr*xr);
b=1/(yr*yr);
c=1;
Note that if we multiply both sides of equation by
xr*xr*yr*yr
we get

a=yr*yr;
b=xr*xr;
c=xr*xr*yr*yr;

Then, note that we can calculate square(like in ) without doing multiplication, if we know previous square:
(y+1)2=y2+2*y+1 .
a*(y+1)2=a*y2+2*a*y+a

Share this post


Link to post
Share on other sites
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 ellipse
x := 0;
y := r;
v1 := (r^2 - r) * a^2; // = x^2 * b^2 + (y - 0.5)^2 * a^2 - 0.25

plot4(x, y);
// plot the first eighth of the ellipse
while (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 ellipse
x := 0;
y := r;
v1 := (r^2 - r) * a^2; // = x^2 * b^2 + (y - 0.5)^2 * a^2 - 0.25
v2 := a^2;
v3 := b^2;
v4 := v2 * v3;

plot4(x, y);
// plot the first eighth of the ellipse
while (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 ellipse
x := 0;
y := r;
v1 := (r^2 - r) * a^2; // = x^2 * b^2 + (y - 0.5)^2 * a^2 - 0.25
v2 := a^2;
v3 := b^2;
v4 := v2 * v3;
v5 := v3;
v6 := (2 - 2 * r) * v2;

plot4(x, y);
// plot the first eighth of the ellipse
while (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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this