1 #include "lib9.h"
2 #include "draw.h"
3 #include "memdraw.h"
4 #include "memlayer.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*
newstate(State * s,int a,int b)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
step(State * s)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
memellipse(Memimage * dst,Point c,int a,int b,int t,Memimage * src,Point sp,int op)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
bellipse(int y,State * s,Param * p)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
erect(int x0,int y0,int x1,int y1,Param * p)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
epoint(int x,int y,Param * p)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
eline(int x0,int y0,int x1,int y1,Param * p)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 }
248