Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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?

like image 385
Roger Dahl Avatar asked Apr 25 '12 19:04

Roger Dahl


People also ask

How do you draw a filled ellipse?

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.

How do you fill an ellipse in C graphics?

fillellipse() function in C h contains fillellipse() function which draws and fills an ellipse with center at (x, y) and (x_radius, y_radius) as x and y radius of ellipse. Syntax : void fillellipse(int x, int y, int x_radius, int y_radius); where, (x, y) is center of the ellipse.

What is ellipse drawing algorithm?

Midpoint ellipse algorithm is a method for drawing ellipses in computer graphics. This method is modified from Bresenham's algorithm. The advantage of this modified method is that only addition operations are required in the program loops. This leads to simple and fast implementation in all processors.

How ellipse is generated and which algorithm is used for ellipse generation?

Mid-point Ellipse algorithm is used to draw an ellipse in computer graphics. Midpoint ellipse algorithm plots(finds) points of an ellipse on the first quadrant by dividing the quadrant into two regions. Each point(x, y) is then projected into other three quadrants (-x, y), (x, -y), (-x, -y) i.e. it uses 4-way symmetry.


2 Answers

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:

                        *
                             **
                                  ****
                                       ***
                                          ***
                                            ***
                                             **
                                             **
like image 123
cvoinescu Avatar answered Sep 21 '22 12:09

cvoinescu


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.

like image 24
Greg Hewgill Avatar answered Sep 18 '22 12:09

Greg Hewgill