ellipse.c (4754B)
1 #include "u.h" 2 #include "lib.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 else 143 memset(&in, 0, sizeof in); 144 inx = 0; 145 for( ; y>=0; y--) { 146 outx = step(&out); 147 if(y > inb) { 148 erect(-outx, y, outx, y, &p); 149 if(y != 0) 150 erect(-outx, -y, outx, -y, &p); 151 continue; 152 } 153 if(t > 0) { 154 inx = step(&in); 155 if(y == inb) 156 inx = 0; 157 } else if(inx > outx) 158 inx = outx; 159 erect(inx, y, outx, y, &p); 160 if(y != 0) 161 erect(inx, -y, outx, -y, &p); 162 erect(-outx, y, -inx, y, &p); 163 if(y != 0) 164 erect(-outx, -y, -inx, -y, &p); 165 inx = outx + 1; 166 } 167 } 168 169 static Point p00 = {0, 0}; 170 171 /* 172 * a brushed ellipse 173 */ 174 static 175 void 176 bellipse(int y, State *s, Param *p) 177 { 178 int t, ox, oy, x, nx; 179 180 t = p->t; 181 p->disc = allocmemimage(Rect(-t,-t,t+1,t+1), GREY1); 182 if(p->disc == nil) 183 return; 184 memfillcolor(p->disc, DTransparent); 185 memellipse(p->disc, p00, t, t, -1, memopaque, p00, p->op); 186 oy = y; 187 ox = 0; 188 nx = x = step(s); 189 do { 190 while(nx==x && y-->0) 191 nx = step(s); 192 y++; 193 eline(-x,-oy,-ox, -y, p); 194 eline(ox,-oy, x, -y, p); 195 eline(-x, y,-ox, oy, p); 196 eline(ox, y, x, oy, p); 197 ox = x+1; 198 x = nx; 199 y--; 200 oy = y; 201 } while(oy > 0); 202 } 203 204 /* 205 * a rectangle with closed (not half-open) coordinates expressed 206 * relative to the center of the ellipse 207 */ 208 static 209 void 210 erect(int x0, int y0, int x1, int y1, Param *p) 211 { 212 Rectangle r; 213 214 r = Rect(p->c.x+x0, p->c.y+y0, p->c.x+x1+1, p->c.y+y1+1); 215 memdraw(p->dst, r, p->src, addpt(p->sp, r.min), memopaque, p00, p->op); 216 } 217 218 /* 219 * a brushed point similarly specified 220 */ 221 static 222 void 223 epoint(int x, int y, Param *p) 224 { 225 Point p0; 226 Rectangle r; 227 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 if(x1 > x0+1) 241 erect(x0+1, y0-p->t, x1-1, y1+p->t, p); 242 else if(y1 > y0+1) 243 erect(x0-p->t, y0+1, x1+p->t, y1-1, p); 244 epoint(x0, y0, p); 245 if(x1-x0 || y1-y0) 246 epoint(x1, y1, p); 247 }