Ellipse routine research

[Krice]

I found the old thread with google, but it doesn't seem to exist when I tried to search it. However routines that were in that thread did not work as I wanted. In the search of perfect ellipse routine I made something myself:

Code: [Select]

void S_Tile::Draw_Ellipse_Points(int cx, int cy, int x, int y, const S_Pixel &c)
{
Set_Pixel(cx+x, cy+y, c);
Set_Pixel(cx-x, cy+y, c);
Set_Pixel(cx-x, cy-y, c);
Set_Pixel(cx+x, cy-y, c);
}

int S_Tile::Trunc(double f)
{
return (int)(f-0.5);
}

void S_Tile::Ellipse(int ox, int oy, int radius_x, int radius_y, const S_Pixel &c)
{
radius_x=abs(radius_x);
radius_y=abs(radius_y);
if (radius_x<1) radius_x=1;
if (radius_y<1) radius_y=1;

const double pi=3.14159265358979323846;

int q=radius_x;
if (q<radius_y) q=radius_y;
double a=(double)(q*q);
double d=(pi*2)/a;

for (double t=0.0; t<=pi/2; t+=d)
{
int xp=Trunc((radius_x*cos(t)));
int yp=Trunc((radius_y*sin(t)));

Draw_Ellipse_Points(ox, oy, xp, yp, c);
}
}

Edit: solved the square problem with q variable while writing this message... q*q seems to be needed for symmetry, but I'm not sure if pi*2 is right.

It's notable that this ellipse routine creates diamond shaped ellipse with small values which is what I want. Most ellipse routines create roundish or even rectangle forms with small radius.

The problem with this routine are "double pixels". The entire shape should be constructed from 1 pixel wide line through the arc.

It's ridiculously difficult to get this right! Searching internet gives "papers" that "solve" this but when trying those routines they fail especially when the ellipse is flat.

[Xecutor]

Hm.
What about this:

Code: [Select]

void ellipse(int cx,int cy,int rx,int ry)
  int rx2=rx*rx;
  int ry2=ry*ry;
  int r4=rx2*ry2;
  for(int y=0;y<ry;++y)
  {
    for(int x=0;x<rx;++x)
    {
      if(ry2*x*x+rx2*y*y<=r4)
      {
        put(cx+x,cy+y);
        put(cx-x,cy+y);
        put(cx+x,cy-y);
        put(cx-x,cy-y);
      }
    }
  }
}


[Krice]

It's quite ok. 3x3 and 5x5 ellipses are rectangles so it seems to produce more rounder result. Also I need a routine which draws only edges of the ellipse as well as filled version (with separate fill color). I think different routines could be optional, because I guess there is no perfect answer to the aliasing problems.

[Xecutor]

You can play a little with condition.
Like change <= to <, add or subtract something from right side
And yes, I think there is no single ultimate solution.

[reaver]

If you have certain shapes in mind for certain radii, wouldn't it be possible to run a non-linear solver of sorts to get the coefficients for your ellipse shapes?

[Krice]

wouldn't it be possible to run a non-linear solver of sorts to get the coefficients for your ellipse shapes?

I guess everything is possible. I just don't know what non-linear solver and coefficients are.

[Quendus]

I think it would be easier to provide satisfactory suggestions if you gave some examples of what you want filled and unfilled ellipses to look like.

Ellipses are very weird compared to circles, especially when you want to do things with their perimeter.

[Krice]

I think it would be easier to provide satisfactory suggestions if you gave some examples of what you want filled and unfilled ellipses to look like.

I want them to have the same shape of course. Some examples from the current routine:


Red pixels are actually green, produced by the routine but I wanted to show which ones need to be removed. I was thinking of some kind of trimming routine to remove them, but no luck yet. You have to remove them as you draw the shape. I tried a routine checking previous location and almost got it working, but there are strange things in it I don't understand like how the second half of 1/4 circle is handled, but pixels get removed from the outside, not the inside.

[Xecutor]

Then for empty ellipse you need something like this:

Code: [Select]

void DrawEllipse (int x0, int y0, int width, int height)
{
    int a2 = width * width;
    int b2 = height * height;
    int fa2 = 4 * a2, fb2 = 4 * b2;
    int x, y, sigma;

    /* first half */
    for (x = 0, y = height, sigma = 2*b2+a2*(1-2*height); b2*x <= a2*y; x++)
    {
        put (x0 + x, y0 + y);
        put (x0 - x, y0 + y);
        put (x0 + x, y0 - y);
        put (x0 - x, y0 - y);
        if (sigma >= 0)
        {
            sigma += fa2 * (1 - y);
            y--;
        }
        sigma += b2 * ((4 * x) + 6);
    }

    /* second half */
    for (x = width, y = 0, sigma = 2*a2+b2*(1-2*width); a2*y <= b2*x; y++)
    {
        put (x0 + x, y0 + y);
        put (x0 - x, y0 + y);
        put (x0 + x, y0 - y);
        put (x0 - x, y0 - y);
        if (sigma >= 0)
        {
            sigma += fb2 * (1 - x);
            x--;
        }
        sigma += a2 * ((4 * y) + 6);
    }
}

And you can easily fill it...