Author Topic: Ellipse routine research  (Read 7086 times)

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Ellipse routine research
« on: February 02, 2014, 01:10:59 PM »
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.
« Last Edit: February 02, 2014, 01:18:54 PM by Krice »

Xecutor

  • 7DRL Reviewer
  • Rogueliker
  • *
  • Posts: 263
  • Karma: +0/-0
    • View Profile
Re: Ellipse routine research
« Reply #1 on: February 03, 2014, 04:52:15 AM »
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

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: Ellipse routine research
« Reply #2 on: February 03, 2014, 09:04:37 AM »
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

  • 7DRL Reviewer
  • Rogueliker
  • *
  • Posts: 263
  • Karma: +0/-0
    • View Profile
Re: Ellipse routine research
« Reply #3 on: February 04, 2014, 04:00:30 AM »
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

  • Rogueliker
  • ***
  • Posts: 207
  • Karma: +0/-0
    • View Profile
Re: Ellipse routine research
« Reply #4 on: February 04, 2014, 08:57:17 AM »
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

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: Ellipse routine research
« Reply #5 on: February 04, 2014, 11:59:20 AM »
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

  • Rogueliker
  • ***
  • Posts: 447
  • Karma: +0/-0
  • $@ \in \{1,W\} \times \{1,H\}$
    • View Profile
    • Klein Roguelikes
Re: Ellipse routine research
« Reply #6 on: February 04, 2014, 12:20:54 PM »
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

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: Ellipse routine research
« Reply #7 on: February 04, 2014, 01:07:12 PM »
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

  • 7DRL Reviewer
  • Rogueliker
  • *
  • Posts: 263
  • Karma: +0/-0
    • View Profile
Re: Ellipse routine research
« Reply #8 on: February 05, 2014, 04:36:41 AM »
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...