Simple algorithm for drawing filled ellipse in C/C++

Question

On SO, found the following simple algorithm for drawing filled circles:

for(int y=-radius; y<=radius; y++)
    for(int x=-radius; x<=radius; x++)
        if(x*x+y*y <= radius*radius)
            setpixel(origin.x+x, origin.y+y);

Is there an equally simple algorithm for drawing filled ellipses?

Solution 1

Simpler, with no double and no division (but be careful of integer overflow):

for(int y=-height; y<=height; y++) {
    for(int x=-width; x<=width; x++) {
        if(x*x*height*height+y*y*width*width <= height*height*width*width)
            setpixel(origin.x+x, origin.y+y);
    }
}

We can take advantage of two facts to optimize this significantly:

• Ellipses have vertical and horizontal symmetry;
• As you progress away from an axis, the contour of the ellipse slopes more and more.

The first fact saves three-quarters of the work (almost); the second fact tremendously reduces the number of tests (we test only along the edge of the ellipse, and even there we don't have to test every point).

int hh = height * height;
int ww = width * width;
int hhww = hh * ww;
int x0 = width;
int dx = 0;

// do the horizontal diameter
for (int x = -width; x <= width; x++)
    setpixel(origin.x + x, origin.y);

// now do both halves at the same time, away from the diameter
for (int y = 1; y <= height; y++)
{
    int x1 = x0 - (dx - 1);  // try slopes of dx - 1 or more
    for ( ; x1 > 0; x1--)
        if (x1*x1*hh + y*y*ww <= hhww)
            break;
    dx = x0 - x1;  // current approximation of the slope
    x0 = x1;

    for (int x = -x0; x <= x0; x++)
    {
        setpixel(origin.x + x, origin.y - y);
        setpixel(origin.x + x, origin.y + y);
    }
}

This works because each scan line is shorter than the previous one, by at least as much as that one was shorter than the one before it. Because of rounding to integer pixel coordinates, that's not perfectly accurate -- the line can be shorter by one pixel less that that.

In other words, starting from the longest scan line (the horizontal diameter), the amount by which each line is shorter than the previous one, denoted dx in the code, decreases by at most one, stays the same, or increases. The first inner for finds the exact amount by which the current scan line is shorter than the previous one, starting at dx - 1 and up, until we land just inside the ellipse.

                       |         x1 dx x0
                       |######    |<-->|
 current scan line --> |###########    |<>|previous dx
previous scan line --> |################  |
two scan lines ago --> |###################
                       |##################### 
                       |###################### 
                       |######################
                       +------------------------

To compare the number of inside-ellipse tests, each asterisk is one pair of coordinates tested in the naive version:

 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************

... and in the improved version:

                        *
                             **
                                  ****
                                       ***
                                          ***
                                            ***
                                             **
                                             **

Solution 2

An ellipse (about the origin) is a circle that has been linearly stretched along the x or y axes. So you can modify your loop like this:

for(int y=-height; y<=height; y++) {
    for(int x=-width; x<=width; x++) {
        double dx = (double)x / (double)width;
        double dy = (double)y / (double)height;
        if(dx*dx+dy*dy <= 1)
            setpixel(origin.x+x, origin.y+y);
    }
}

You can see that if width == height == radius, then this is equivalent to your code for drawing a circle.

Solution 3

Replace

x*x+y*y <= radius*radius

with

Axx*x*x + 2*Axy*x*y + Ayy*y*y < radius*radius

where you have three constants, Axx, Axy, Ayy. When Axy=0, the ellipse will have its axes straight horizontal and vertical. Axx=Ayy=1 makes a circle. The bigger Axx, the smaller the width. Similar for Ayy and height. For an arbitrary ellipse tilted at any given angle, it takes a bit of algebra to figure out the constants.

Mathematically Axx, Axy, Ayy are a "tensor" but perhaps you don't want to get into that stuff.

UPDATE - detailed math. I don't think S.O. can make nice math like Math S.E. so this will look crude. You want to draw (or do whatever) with an ellipse in x,y coordinates. The ellipse is tilted. We create an alternative coordinate system x',y' aligned with the ellipse. Clearly, points on the ellipse satisfy

(x'/a)^2 + (y'/b)^2 = 1  

By contemplating some well-chosen random points we see that

x' =  C*x + S*y
y' = -S*x + C*y

where S, C are sin(θ) and cos(θ), θ being the angle of the x' axis w.r.t. the x axis. We can shorten this with notation x = (x,y) and similar for primed, and R a 2x2 matrix involving C and S:

x' = R x

The ellipse equation can be written

T(x') A'' x' = 1

where 'T' to indicates transpose and, dropping '^' to avoid poking everyone in the eyes, so that "a2" really means a^2,

A'' =

1/a2     0  
 0     1/b2

Using x' = Rx we find

T(Rx) A'' Rx = 1

T(x) T(R) A'' R x =1

T(x) A x = 1

where A, the thing you need to know to make your tilted drawing scan line algorithm work, is

A = T(R) A'' R =

C2/a2+S2/b2     SC(1/a2-1/b2)
SC/(1/a2-1/b2)  S2/a2 + C2/b2    

Multiply these by x and y according to T(x)Ax and you've got it.

Solution 4

A fast Bresenham type algorithm, as proposed by this paper, works really well. Here's an OpenGL implementation that I wrote for the same.

The basic premise is that you plot the curve on one quadrant, which we can mirror on to the other three quadrants. These vertices are computed using an error function, similar to what you use in the midpoint circle algorithm for circles. The paper I have linked above has a pretty nifty proof for the equation, and the algorithm distills down to just checking if a given vertex is within an ellipse or not, just by substituting its values in the error function. The algorithm also tracks the tangent line slope of the curve we are drawing in the first quadrant, and increments x or y depending on the slope value - which contributes further to the performance of the algorithm. Here's an image that shows what's going on:

As for filling the ellipse, once we know the vertices in each quadrant (which is essentially mirror reflections across x and y axes), we get 4 vertices for every vertex that we compute - which is sufficient to draw a quad (in OpenGL anyway). Once we draw quads for all such vertices, we get a filled ellipse. The implementation I have given employs VBO for performance reasons, but you don't strictly need it.

The implementation also shows you how to achieve a filled ellipse using triangles and lines instead of drawing quads - the quads are clearly better though, as it is a primitive and we only draw one quad for 4 vertices, as opposed to one triangle per vertex in the triangle implementation.

View more solutions

Comments

[Greg Hewgill]

With the setpixel() in the inner loop, the whole algorithm isn't likely to be efficient anyway. Also, any optimising compiler will lift the dy calculation out of the x loop.

[Mark Ransom]

If you multiply all terms by width*height you can make it integer arithmetic. It simplifies to x*height*x*height+y*width*y*width <= width*height*width*height.

[Roger Dahl]

Thank you for this improvement. Could you fix the code by changing dx and dy to x and y?

[Mr Lister]

Oh, if it's performance you want, you can just run y from 0 to height, and do two setpixels in the inner loop, one for origin.y+y and one for origin.y-y.

[cvoinescu]

If it's performance you want, then you use a different algorithm. You do away with the inner loop. For each y, the algorithm finds the x of the leftmost and rightmost pixels that belong to the ellipse; then you simply draw horizontal lines. The finding of the line ends is very simple if you're allowed to take a square root, but, with a little effort, can be modified to integer-only (a little like Bresenham's algorithm).

[Roger Dahl]

Thank you for this. Any chance you can add a reply with a complete algorithm that also takes an angle?

[crashmstr]

Links are great, links with relevant quotes and examples, better. How to Answer

[Prathap]

@crashmstr Apologies - have provided a better explanation

[picmate 涅]

Thanks for the links to the papers and your answer. Works well.