Ellipse routine

[Krice]

I have great difficulties finding a working bresenham type ("perfect") ellipse routine for C++ from the internet. Can someone help? Since I don't know anything about math I don't know how to implement one.

[Xecutor]

like this:

Code: [Select]

#include <stdio.h>

char map[100][101]={0,};

void mySetPixel(int x,int y)
{
  if(x<0 || y<0 || x>=100 || y>=100)return;
  map[y][x]='#';
}

void drawEllipse(int x0,int y0,int a,int b )
{
  if (a == 0 || b == 0) return;
  int a2 = 2*a * a;
  int b2 = 2*b * b;
  int error = a*a*b;
  int x = 0;
  int y = b;
  int stopy = 0;
  int stopx = a2 * b ;
  while (stopy <= stopx)
  {
    mySetPixel(x0 + x, y0 + y);
    mySetPixel(x0 - x, y0 + y);
    mySetPixel(x0 - x, y0 - y);
    mySetPixel(x0 + x, y0 - y);
    ++x;
    error -= b2 * (x - 1);
    stopy += b2;
    if (error <= 0)
    {
      error += a2 * (y - 1);
      --y;
      stopx -= a2;
    }
  }

  error = b*b*a;
  x = a;
  y = 0;
  stopy = b2*a;
  stopx = 0;
  while (stopy >= stopx)
  {
    mySetPixel(x0 + x, y0 + y);
    mySetPixel(x0 - x, y0 + y);
    mySetPixel(x0 - x, y0 - y);
    mySetPixel(x0 + x, y0 - y);
    ++y;
    error -= a2 * (y - 1);
    stopx += a2;
    if (error < 0)
    {
      error += b2 * (x - 1);
      --x;
      stopy -= b2;
    }
  }
}


int main()
{
  for(int y=0;y<100;y++)
  {
    for(int x=0;x<100;x++)
    {
      map[y][x]=' ';
    }
  }
  drawEllipse(50,50,35,15);

  for(int i=0;i<100;i++)
  {
    printf("%s\n",map[i]);
  }
  return 0;
}


[Kalantir]

Just curious, why do you need an ellipse as opposed to a regular circle?  I don't know much about using an ellipse, but a circle is rather trivial to implement since you can just use Pythagorean Theorem to determine if any given point is within the circle's radius.

Code: [Select]

yDistance = abs(Y - y);   // The distance between y and the player
xDistance = abs(X - x);   // The distance between x and the player

 if(sqrt((float)((yDistance * yDistance) + (xDistance * xDistance))) <= ((float)Radius))
   Explored[y][x] = true;
Basically, if the square root of yDistance squared plus xDistance squared is  less then Radius , you know its in the circle.

Although, you'll find that most fonts dont use perfect squares for their characters, so this "circle algorithm"  Will produce more of an oval which is taller then it is wide... To fix that, you can multiply yDistance squared by another number.  I've found that values between 2 and 3 tend to do well.  The larger you make this number, the more oval-like it will eventually become.  You could make it more oval-like in the other direction by doing the same thing to xDistance squared

eg.

Code: [Select]

// An approximate circle with the font I'm using
if(sqrt((float)((yDistance * yDistance * 3.0f) + (xDistance * xDistance))) <= ((float)Radius))
   Explored[y][x] = true;

// An approximate wide oval with the font I'm using
if(sqrt((float)((yDistance * yDistance * 6.0f) + (xDistance * xDistance))) <= ((float)Radius))
   Explored[y][x] = true;

Anyways, I'm curious as to what uses you've found for an ellipse.  Good luck with the project!

[Krice]

Just curious, why do you need an ellipse as opposed to a regular circle?

It's for Brick Atelier, the tile editor I've been programming. I'm going to try that Xecutor's code later (monday at work).. I think it looks like based on that pdf I saw. There is also an interesting version in wikipedia which creates dots that can be then connected with lines. It doesn't make a symmetrical ellipse, but that could be fixed by mirroring.

[Z]

Surprisingly, there was a thread about this before.

if(sqrt((float)((yDistance * yDistance) + (xDistance * xDistance))) <= ((float)Radius))

This one is better: if(yDistance*yDistance+xDistance*xDistance <= Radius*Radius). No roots, no floats, and shorter.

Although, you'll find that most fonts dont use perfect squares for their characters, so this "circle algorithm"  Will produce more of an oval which is taller then it is wide...

I think that roguelikes usually use (e.g. for field of vision) "logical circles", which have the same width and height from the view of game mechanics, not things that look like circles on screen. (Actually, it would be more logical to use squares for FOV, but it looks ugly.)

[Darren Grey]

For ellipses you only need to work out one quarter and then reflect/rotate for the remaining three quarters if you want to keep it all symmetrical.  (For circles it's even easier - you only need 1/8th calculated.)

[Kalantir]

This one is better: if(yDistance*yDistance+xDistance*xDistance <= Radius*Radius). No roots, no floats, and shorter.

I'll admit that I do like that better, although floats are usefull as they allow you to determine which portion of the tile any given lines pass through.

[Krice]

For ellipses you only need to work out one quarter and then reflect/rotate for the remaining three quarters

About that I noticed that I don't know how to mirror the quarters... and that Xecutor's code doesn't handle zero size ellipses (draws a line). The current routine I have can handle vertical, but not horizontal zero condition. I can't figure out why.

[Kalantir]

I dont know how the algorithm you're using works, but if its set up so that you feed it a new Y value and it gives you a corresponding X value, try doing it the other way around and see if it works for horizontal.

Again, I don't really know much about how that works, but for mirroring, as long as you know the current point and the point its going to be mirrored across it should be fairly straightforward.  If you are drawing at a point over here, find the point you're mirroring across and it'll be the same distance on the other side.  You should be drawing 4 points per loop iteration if I'm understanding this correctly.

Code: [Select]

Draw(NewY, NewX);
Draw(NewY, CenterX-NewX);
Draw(CenterY-NewY, NewX);
Draw(CenterY-NewY, CenterX-NewX);
Or something to that effect...
Correct me if I'm foolishly talking about things which are not relevant

[Xecutor]

IMO it's better to handle zero radius as separate case.

[Bear]

All of these routines only make a special case of ellipse though.  If you want ellipses that can be at any angle, you have to do something just a little bit more complex, like this.

if (rad*2 >
    (sqrt (double)((testpt.x - f1.x)*(testpt.x - f1.x) + (testpt.y - f1.y)*(testpt.y - f1.y))+
     sqrt (double)((testpt.x - f2.x)*(testpt.x - f2.x) + (testpt.y - f2.y)*(testpt.y - f2.y)))

This code checks a point named testpt for membership in an ellipse with foci at f1 and f2 and average radius rad.  With this, the foci don't have to be in the same row, nor the same column. 

So, if you want a spell to have an "ellipse" area effect that's stretched along the line from the caster to the target, you can do that even if the caster is firing at a funny angle. 

Bear

[Krice]

If you want ellipses that can be at any angle

I don't want.

So, if you want a spell to have an "ellipse" area effect

Not using for spells or even a roguelike.

Here is the current, strange kind of routine. I just copied it somewhere. The second part is actually drawing a diamond which is confusing, but together it seems to create nice ellipses. The result is better than any of routines in this thread. If you look at other routines, they create rectangles (or other way poor looking ellipses) with small values!

Code: [Select]

void Matrix::Draw_Ellipse_Part(int sx, int sy, int x, int y, int b)
{
int dx=sx+x, dy=sy+y, dx2=sx-x, dy2=sy-y, t;

for (t=dy2; t<=dy; t++)
{
//fill right side of the ellipse
Put(dx, t, b);
//fill left side
Put(dx2, t, b);
}
}

void Matrix::Draw_Ellipse(int xc, int yc, int radius_x, int radius_y, int tile)
{
radius_x=abs(radius_x);
radius_y=abs(radius_y);

int a_square_rad=(radius_x*radius_x);
int b_square_rad=(radius_y*radius_y);
int aa2=(a_square_rad*2);
int bb2=(b_square_rad*2);

int x=0, y=radius_y;
int fx=0, fy=(aa2*radius_y);

double p=(b_square_rad-(a_square_rad*radius_y)+(0.25f*a_square_rad)+0.5f);

Draw_Ellipse_Part(xc, yc, x, y, tile);

while(fx<fy)
{
x++;
fx+=bb2;

if (p<0) p+=(b_square_rad+fx);
else { y--; fy-=aa2; p+=(fx+b_square_rad-fy); }

Draw_Ellipse_Part(xc, yc, x, y, tile);
}

p=((b_square_rad*(x+0.5f)*(x+0.5f))+(a_square_rad*(y-1)*(y-1))-(a_square_rad*b_square_rad)+0.5f);

while(y>0)
{
y--;
fy-=aa2;

if (p>=0) p+=(a_square_rad-fy);
else { x++; fx+=bb2; p+=(fx+a_square_rad-fy); }

Draw_Ellipse_Part(xc, yc, x, y, tile);
}
}

The only problem with this routine is (as mentioned earlier) that it draws only the center tile when the ellipse is flat in horizontal direction.

[Krice]

I noticed that input values for x and y radius are not the same for a perfect circle so that could explain something, but I don't know why y=0 radius doesn't work.

[kipar]

Checking if yradius=0 and drawing the line in that case will be a nice addition to this strange procedure.

[Krice]

Checking if yradius=0 and drawing the line in that case will be a nice addition to this strange procedure.

That indeed works, but I noticed a new artifact when yradius is one (three pixels height ellipse) and xradius is over some value like 7 or 8, then the ellipse width is actually one smaller than it should be. I wish there was a way to fix the routine to produce exact results.