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