How to draw elliptical sector with Bresenham's algorithm?

Question

How can I draw filled elliptical sector using Bresenham's algorithm and bitmap object with DrawPixel method?

I have written method for drawing ellipse, but this method uses symmetry and passes only first quadrant. This algorithm is not situable for sectors. Of course, I can write 8 cycles, but I think it's not the most elegant solution of the task.

Answer 1

On integer math the usual parametrization is by using limiting lines (in CW or CCW direction) instead of your angles. So if you can convert those angles to such (you need sin,cos for that but just once) then you can use integer math based rendering for this. As I mentioned in the comment bresenham is not a good approach for a sector of ellipse as you would need to compute the internal iterators and counters state for the start point of interpolation and also it will give you just the circumference points instead of filled shape.

There are many approaches out there for this here a simple one:

1. convert ellipse to circle

   simply by rescaling the smaller radius axis

2. loop through bbox of such circle

   simple 2 nested for loops covering the outscribed square to our circle

3. check if point inside circle

   simply check if x^2 + y^2 <= r^2 while the circle is centered by (0,0)

4. check if point lies between edge lines

   so it should be CW with one edge and CCW with the other. You can exploit the cross product for this (its z coordinate polarity will tell you if point is CW or CCW against the tested edge line)

   but this will work only up to 180 deg slices so you need also add some checking for the quadrants to avoid false negatives. But those are just few ifs on top of this.

5. if all conditions are met conver the point back to ellipse and render

Here small C++ example of this:

void elliptic_arc(int x0,int y0,int rx,int ry,int a0,int a1,DWORD c)    
    {
    // variables
    int  x, y, r,
        xx,yy,rr,
        xa,ya,xb,yb,                // a0,a1 edge points with radius r
        mx,my,cx,cy,sx,sy,i,a;
    // my Pixel access (you can ignore it and use your style of gfx access)
    int **Pixels=Main->pyx;         // Pixels[y][x]
    int   xs=Main->xs;              // resolution
    int   ys=Main->ys;
    // init variables
    r=rx; if (r<ry) r=ry; rr=r*r;   // r=max(rx,ry)
    mx=(rx<<10)/r;                  // scale from circle to ellipse (fixed point)
    my=(ry<<10)/r;
    xa=+double(r)*cos(double(a0)*M_PI/180.0);
    ya=+double(r)*sin(double(a0)*M_PI/180.0);
    xb=+double(r)*cos(double(a1)*M_PI/180.0);
    yb=+double(r)*sin(double(a1)*M_PI/180.0);
    // render
    for (y=-r,yy=y*y,cy=(y*my)>>10,sy=y0+cy;y<=+r;y++,yy=y*y,cy=(y*my)>>10,sy=y0+cy) if ((sy>=0)&&(sy<ys))
     for (x=-r,xx=x*x,cx=(x*mx)>>10,sx=x0+cx;x<=+r;x++,xx=x*x,cx=(x*mx)>>10,sx=x0+cx) if ((sx>=0)&&(sx<xs))
      if (xx+yy<=rr)                // inside circle
        {
        if ((cx>=0)&&(cy>=0)) a=  0;// actual quadrant
        if ((cx< 0)&&(cy>=0)) a= 90;
        if ((cx>=0)&&(cy< 0)) a=270;
        if ((cx< 0)&&(cy< 0)) a=180;
        if ((a   >=a0)||((cx*ya)-(cy*xa)<=0))           // x,y is above a0 in clockwise direction
         if ((a+90<=a1)||((cx*yb)-(cy*xb)>=0))
          Pixels[sy][sx]=c;
        }
    }

beware both angles must be in <0,360> range. My screen has y pointing down so if a0<a1 it will be CW direction which matches the routione. If you use a1<a0 then the range will be skipped and the rest of ellipse will be rendered instead.

This approach uses a0,a1 as real angles !!!

To avoid divides inside loop I used 10 bit fixed point scales instead.

You can simply divide this to 4 quadrants to avoid 4 if inside loops to improve performance.

x,y is point in circular scale centered by (0,0)
cx,cy is point in elliptic scale centered by (0,0)
sx,sy is point in elliptic scale translated to ellipse center position

Beware my pixel access is Pixels[y][x] but most apis use Pixels[x][y] so do not forget to change it to your api to avoid access violations or 90deg rotation of the result ...