sys/src/libmemdraw/ellipse.c

   1 #include <u.h>
   2 #include <libc.h>
   3 #include <draw.h>
   4 #include <memdraw.h>
   5 #include <memlayer.h>
   6
   7 /*
   8  * ellipse(dst, c, a, b, t, src, sp)
   9  *   draws an ellipse centered at c with semiaxes a,b>=0
  10  *   and semithickness t>=0, or filled if t<0.  point sp
  11  *   in src maps to c in dst
  12  *
  13  *   very thick skinny ellipses are brushed with circles (slow)
  14  *   others are approximated by filling between 2 ellipses
  15  *   criterion for very thick when b<a: t/b > 0.5*x/(1-x)
  16  *   where x = b/a
  17  */
  18
  19 typedef struct Param    Param;
  20 typedef struct State    State;
  21
  22 static  void    bellipse(int, State*, Param*);
  23 static  void    erect(int, int, int, int, Param*);
  24 static  void    eline(int, int, int, int, Param*);
  25
  26 struct Param {
  27         Memimage        *dst;
  28         Memimage        *src;
  29         Point                   c;
  30         int                     t;
  31         Point                   sp;
  32         Memimage        *disc;
  33         int                     op;
  34 };
  35
  36 /*
  37  * denote residual error by e(x,y) = b^2*x^2 + a^2*y^2 - a^2*b^2
  38  * e(x,y) = 0 on ellipse, e(x,y) < 0 inside, e(x,y) > 0 outside
  39  */
  40
  41 struct State {
  42         int     a;
  43         int     x;
  44         vlong   a2;     /* a^2 */
  45         vlong   b2;     /* b^2 */
  46         vlong   b2x;    /* b^2 * x */
  47         vlong   a2y;    /* a^2 * y */
  48         vlong   c1;
  49         vlong   c2;     /* test criteria */
  50         vlong   ee;     /* ee = e(x+1/2,y-1/2) - (a^2+b^2)/4 */
  51         vlong   dxe;
  52         vlong   dye;
  53         vlong   d2xe;
  54         vlong   d2ye;
  55 };
  56
  57 static
  58 State*
  59 newstate(State *s, int a, int b)
  60 {
  61         s->x = 0;
  62         s->a = a;
  63         s->a2 = (vlong)(a*a);
  64         s->b2 = (vlong)(b*b);
  65         s->b2x = (vlong)0;
  66         s->a2y = s->a2*(vlong)b;
  67         s->c1 = -((s->a2>>2) + (vlong)(a&1) + s->b2);
  68         s->c2 = -((s->b2>>2) + (vlong)(b&1));
  69         s->ee = -s->a2y;
  70         s->dxe = (vlong)0;
  71         s->dye = s->ee<<1;
  72         s->d2xe = s->b2<<1;
  73         s->d2ye = s->a2<<1;
  74         return s;
  75 }
  76
  77 /*
  78  * return x coord of rightmost pixel on next scan line
  79  */
  80 static
  81 int
  82 step(State *s)
  83 {
  84         while(s->x < s->a) {
  85                 if(s->ee+s->b2x <= s->c1 ||     /* e(x+1,y-1/2) <= 0 */
  86                    s->ee+s->a2y <= s->c2) {     /* e(x+1/2,y) <= 0 (rare) */
  87                         s->dxe += s->d2xe;
  88                         s->ee += s->dxe;
  89                         s->b2x += s->b2;
  90                         s->x++;
  91                         continue;
  92                 }
  93                 s->dye += s->d2ye;
  94                 s->ee += s->dye;
  95                 s->a2y -= s->a2;
  96                 if(s->ee-s->a2y <= s->c2) {     /* e(x+1/2,y-1) <= 0 */
  97                         s->dxe += s->d2xe;
  98                         s->ee += s->dxe;
  99                         s->b2x += s->b2;
 100                         return s->x++;
 101                 }
 102                 break;
 103         }
 104         return s->x;
 105 }
 106
 107 void
 108 memellipse(Memimage *dst, Point c, int a, int b, int t, Memimage *src, Point sp, int op)
 109 {
 110         State in, out;
 111         int y, inb, inx, outx, u;
 112         Param p;
 113
 114         if(a < 0)
 115                 a = -a;
 116         if(b < 0)
 117                 b = -b;
 118         p.dst = dst;
 119         p.src = src;
 120         p.c = c;
 121         p.t = t;
 122         p.sp = subpt(sp, c);
 123         p.disc = nil;
 124         p.op = op;
 125
 126         u = (t<<1)*(a-b);
 127         if(b<a && u>b*b || a<b && -u>a*a) {
 128 /*      if(b<a&&(t<<1)>b*b/a || a<b&&(t<<1)>a*a/b)      # very thick */
 129                 bellipse(b, newstate(&in, a, b), &p);
 130                 return;
 131         }
 132
 133         if(t < 0) {
 134                 inb = -1;
 135                 newstate(&out, a, y = b);
 136         } else {
 137                 inb = b - t;
 138                 newstate(&out, a+t, y = b+t);
 139         }
 140         if(t > 0)
 141                 newstate(&in, a-t, inb);
 142         inx = 0;
 143         for( ; y>=0; y--) {
 144                 outx = step(&out);
 145                 if(y > inb) {
 146                         erect(-outx, y, outx, y, &p);
 147                         if(y != 0)
 148                                 erect(-outx, -y, outx, -y, &p);
 149                         continue;
 150                 }
 151                 if(t > 0) {
 152                         inx = step(&in);
 153                         if(y == inb)
 154                                 inx = 0;
 155                 } else if(inx > outx)
 156                         inx = outx;
 157                 erect(inx, y, outx, y, &p);
 158                 if(y != 0)
 159                         erect(inx, -y, outx, -y, &p);
 160                 erect(-outx, y, -inx, y, &p);
 161                 if(y != 0)
 162                         erect(-outx, -y, -inx, -y, &p);
 163                 inx = outx + 1;
 164         }
 165 }
 166
 167 static Point p00 = {0, 0};
 168
 169 /*
 170  * a brushed ellipse
 171  */
 172 static
 173 void
 174 bellipse(int y, State *s, Param *p)
 175 {
 176         int t, ox, oy, x, nx;
 177
 178         t = p->t;
 179         p->disc = allocmemimage(Rect(-t,-t,t+1,t+1), GREY1);
 180         if(p->disc == nil)
 181                 return;
 182         memfillcolor(p->disc, DTransparent);
 183         memellipse(p->disc, p00, t, t, -1, memopaque, p00, p->op);
 184         oy = y;
 185         ox = 0;
 186         nx = x = step(s);
 187         do {
 188                 while(nx==x && y-->0)
 189                         nx = step(s);
 190                 y++;
 191                 eline(-x,-oy,-ox, -y, p);
 192                 eline(ox,-oy,  x, -y, p);
 193                 eline(-x,  y,-ox, oy, p);
 194                 eline(ox,  y,  x, oy, p);
 195                 ox = x+1;
 196                 x = nx;
 197                 y--;
 198                 oy = y;
 199         } while(oy > 0);
 200 }
 201
 202 /*
 203  * a rectangle with closed (not half-open) coordinates expressed
 204  * relative to the center of the ellipse
 205  */
 206 static
 207 void
 208 erect(int x0, int y0, int x1, int y1, Param *p)
 209 {
 210         Rectangle r;
 211
 212 /*      print("R %d,%d %d,%d\n", x0, y0, x1, y1); /**/
 213         r = Rect(p->c.x+x0, p->c.y+y0, p->c.x+x1+1, p->c.y+y1+1);
 214         memdraw(p->dst, r, p->src, addpt(p->sp, r.min), memopaque, p00, p->op);
 215 }
 216
 217 /*
 218  * a brushed point similarly specified
 219  */
 220 static
 221 void
 222 epoint(int x, int y, Param *p)
 223 {
 224         Point p0;
 225         Rectangle r;
 226
 227 /*      print("P%d %d,%d\n", p->t, x, y);       /**/
 228         p0 = Pt(p->c.x+x, p->c.y+y);
 229         r = Rpt(addpt(p0, p->disc->r.min), addpt(p0, p->disc->r.max));
 230         memdraw(p->dst, r, p->src, addpt(p->sp, r.min), p->disc, p->disc->r.min, p->op);
 231 }
 232
 233 /*
 234  * a brushed horizontal or vertical line similarly specified
 235  */
 236 static
 237 void
 238 eline(int x0, int y0, int x1, int y1, Param *p)
 239 {
 240 /*      print("L%d %d,%d %d,%d\n", p->t, x0, y0, x1, y1); /**/
 241         if(x1 > x0+1)
 242                 erect(x0+1, y0-p->t, x1-1, y1+p->t, p);
 243         else if(y1 > y0+1)
 244                 erect(x0-p->t, y0+1, x1+p->t, y1-1, p);
 245         epoint(x0, y0, p);
 246         if(x1-x0 || y1-y0)
 247                 epoint(x1, y1, p);
 248 }