#include <u.h>
#include <libc.h>
#include <draw.h>
#include <memdraw.h>
#include <memlayer.h>

/*
* ellipse(dst, c, a, b, t, src, sp)
*   draws an ellipse centered at c with semiaxes a,b>=0
*   and semithickness t>=0, or filled if t<0.  point sp
*   in src maps to c in dst
*
*   very thick skinny ellipses are brushed with circles (slow)
*   others are approximated by filling between 2 ellipses
*   criterion for very thick when b<a: t/b > 0.5*x/(1-x)
*   where x = b/a
*/

typedef struct Param    Param;
typedef struct State    State;

static  void    bellipse(int, State*, Param*);
static  void    erect(int, int, int, int, Param*);
static  void    eline(int, int, int, int, Param*);

struct Param {
       Memimage        *dst;
       Memimage        *src;
       Point                   c;
       int                     t;
       Point                   sp;
       Memimage        *disc;
       int                     op;
};

/*
* denote residual error by e(x,y) = b^2*x^2 + a^2*y^2 - a^2*b^2
* e(x,y) = 0 on ellipse, e(x,y) < 0 inside, e(x,y) > 0 outside
*/

struct State {
       int     a;
       int     x;
       vlong   a2;     /* a^2 */
       vlong   b2;     /* b^2 */
       vlong   b2x;    /* b^2 * x */
       vlong   a2y;    /* a^2 * y */
       vlong   c1;
       vlong   c2;     /* test criteria */
       vlong   ee;     /* ee = e(x+1/2,y-1/2) - (a^2+b^2)/4 */
       vlong   dxe;
       vlong   dye;
       vlong   d2xe;
       vlong   d2ye;
};

static
State*
newstate(State *s, int a, int b)
{
       s->x = 0;
       s->a = a;
       s->a2 = (vlong)(a*a);
       s->b2 = (vlong)(b*b);
       s->b2x = (vlong)0;
       s->a2y = s->a2*(vlong)b;
       s->c1 = -((s->a2>>2) + (vlong)(a&1) + s->b2);
       s->c2 = -((s->b2>>2) + (vlong)(b&1));
       s->ee = -s->a2y;
       s->dxe = (vlong)0;
       s->dye = s->ee<<1;
       s->d2xe = s->b2<<1;
       s->d2ye = s->a2<<1;
       return s;
}

/*
* return x coord of rightmost pixel on next scan line
*/
static
int
step(State *s)
{
       while(s->x < s->a) {
               if(s->ee+s->b2x <= s->c1 ||     /* e(x+1,y-1/2) <= 0 */
                  s->ee+s->a2y <= s->c2) {     /* e(x+1/2,y) <= 0 (rare) */
                       s->dxe += s->d2xe;
                       s->ee += s->dxe;
                       s->b2x += s->b2;
                       s->x++;
                       continue;
               }
               s->dye += s->d2ye;
               s->ee += s->dye;
               s->a2y -= s->a2;
               if(s->ee-s->a2y <= s->c2) {     /* e(x+1/2,y-1) <= 0 */
                       s->dxe += s->d2xe;
                       s->ee += s->dxe;
                       s->b2x += s->b2;
                       return s->x++;
               }
               break;
       }
       return s->x;
}

void
memellipse(Memimage *dst, Point c, int a, int b, int t, Memimage *src, Point sp, int op)
{
       State in, out;
       int y, inb, inx, outx, u;
       Param p;

       if(a < 0)
               a = -a;
       if(b < 0)
               b = -b;
       p.dst = dst;
       p.src = src;
       p.c = c;
       p.t = t;
       p.sp = subpt(sp, c);
       p.disc = nil;
       p.op = op;

       u = (t<<1)*(a-b);
       if(b<a && u>b*b || a<b && -u>a*a) {
/*      if(b<a&&(t<<1)>b*b/a || a<b&&(t<<1)>a*a/b)      # very thick */
               bellipse(b, newstate(&in, a, b), &p);
               return;
       }

       if(t < 0) {
               inb = -1;
               newstate(&out, a, y = b);
       } else {
               inb = b - t;
               newstate(&out, a+t, y = b+t);
       }
       if(t > 0)
               newstate(&in, a-t, inb);
       inx = 0;
       for( ; y>=0; y--) {
               outx = step(&out);
               if(y > inb) {
                       erect(-outx, y, outx, y, &p);
                       if(y != 0)
                               erect(-outx, -y, outx, -y, &p);
                       continue;
               }
               if(t > 0) {
                       inx = step(&in);
                       if(y == inb)
                               inx = 0;
               } else if(inx > outx)
                       inx = outx;
               erect(inx, y, outx, y, &p);
               if(y != 0)
                       erect(inx, -y, outx, -y, &p);
               erect(-outx, y, -inx, y, &p);
               if(y != 0)
                       erect(-outx, -y, -inx, -y, &p);
               inx = outx + 1;
       }
}

/*
* a brushed ellipse
*/
static
void
bellipse(int y, State *s, Param *p)
{
       int t, ox, oy, x, nx;

       t = p->t;
       p->disc = allocmemimage(Rect(-t,-t,t+1,t+1), GREY1);
       if(p->disc == nil)
               return;
       memfillcolor(p->disc, DTransparent);
       memellipse(p->disc, ZP, t, t, -1, memopaque, ZP, p->op);
       oy = y;
       ox = 0;
       nx = x = step(s);
       do {
               while(nx==x && y-->0)
                       nx = step(s);
               y++;
               eline(-x,-oy,-ox, -y, p);
               eline(ox,-oy,  x, -y, p);
               eline(-x,  y,-ox, oy, p);
               eline(ox,  y,  x, oy, p);
               ox = x+1;
               x = nx;
               y--;
               oy = y;
       } while(oy > 0);
}

/*
* a rectangle with closed (not half-open) coordinates expressed
* relative to the center of the ellipse
*/
static
void
erect(int x0, int y0, int x1, int y1, Param *p)
{
       Rectangle r;

/*      print("R %d,%d %d,%d\n", x0, y0, x1, y1); /**/
       r = Rect(p->c.x+x0, p->c.y+y0, p->c.x+x1+1, p->c.y+y1+1);
       memdraw(p->dst, r, p->src, addpt(p->sp, r.min), memopaque, ZP, p->op);
}

/*
* a brushed point similarly specified
*/
static
void
epoint(int x, int y, Param *p)
{
       Point p0;
       Rectangle r;

/*      print("P%d %d,%d\n", p->t, x, y);       /**/
       p0 = Pt(p->c.x+x, p->c.y+y);
       r = Rpt(addpt(p0, p->disc->r.min), addpt(p0, p->disc->r.max));
       memdraw(p->dst, r, p->src, addpt(p->sp, r.min), p->disc, p->disc->r.min, p->op);
}

/*
* a brushed horizontal or vertical line similarly specified
*/
static
void
eline(int x0, int y0, int x1, int y1, Param *p)
{
/*      print("L%d %d,%d %d,%d\n", p->t, x0, y0, x1, y1); /**/
       if(x1 > x0+1)
               erect(x0+1, y0-p->t, x1-1, y1+p->t, p);
       else if(y1 > y0+1)
               erect(x0-p->t, y0+1, x1+p->t, y1-1, p);
       epoint(x0, y0, p);
       if(x1-x0 || y1-y0)
               epoint(x1, y1, p);
}

You are viewing proxied material from sdf.org. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.