1 76193d7c 2003-09-30 devnull #include <u.h>
2 76193d7c 2003-09-30 devnull #include <libc.h>
3 76193d7c 2003-09-30 devnull #include <draw.h>
4 76193d7c 2003-09-30 devnull #include <memdraw.h>
7 76193d7c 2003-09-30 devnull * ellipse(dst, c, a, b, t, src, sp)
8 76193d7c 2003-09-30 devnull * draws an ellipse centered at c with semiaxes a,b>=0
9 76193d7c 2003-09-30 devnull * and semithickness t>=0, or filled if t<0. point sp
10 76193d7c 2003-09-30 devnull * in src maps to c in dst
12 76193d7c 2003-09-30 devnull * very thick skinny ellipses are brushed with circles (slow)
13 76193d7c 2003-09-30 devnull * others are approximated by filling between 2 ellipses
14 76193d7c 2003-09-30 devnull * criterion for very thick when b<a: t/b > 0.5*x/(1-x)
15 76193d7c 2003-09-30 devnull * where x = b/a
18 76193d7c 2003-09-30 devnull typedef struct Param Param;
19 76193d7c 2003-09-30 devnull typedef struct State State;
21 76193d7c 2003-09-30 devnull static void bellipse(int, State*, Param*);
22 76193d7c 2003-09-30 devnull static void erect(int, int, int, int, Param*);
23 76193d7c 2003-09-30 devnull static void eline(int, int, int, int, Param*);
25 76193d7c 2003-09-30 devnull struct Param {
26 76193d7c 2003-09-30 devnull Memimage *dst;
27 76193d7c 2003-09-30 devnull Memimage *src;
30 76193d7c 2003-09-30 devnull Point sp;
31 76193d7c 2003-09-30 devnull Memimage *disc;
36 76193d7c 2003-09-30 devnull * denote residual error by e(x,y) = b^2*x^2 + a^2*y^2 - a^2*b^2
37 76193d7c 2003-09-30 devnull * e(x,y) = 0 on ellipse, e(x,y) < 0 inside, e(x,y) > 0 outside
40 76193d7c 2003-09-30 devnull struct State {
43 76193d7c 2003-09-30 devnull vlong a2; /* a^2 */
44 76193d7c 2003-09-30 devnull vlong b2; /* b^2 */
45 76193d7c 2003-09-30 devnull vlong b2x; /* b^2 * x */
46 76193d7c 2003-09-30 devnull vlong a2y; /* a^2 * y */
47 76193d7c 2003-09-30 devnull vlong c1;
48 76193d7c 2003-09-30 devnull vlong c2; /* test criteria */
49 76193d7c 2003-09-30 devnull vlong ee; /* ee = e(x+1/2,y-1/2) - (a^2+b^2)/4 */
50 76193d7c 2003-09-30 devnull vlong dxe;
51 76193d7c 2003-09-30 devnull vlong dye;
52 76193d7c 2003-09-30 devnull vlong d2xe;
53 76193d7c 2003-09-30 devnull vlong d2ye;
58 76193d7c 2003-09-30 devnull newstate(State *s, int a, int b)
60 76193d7c 2003-09-30 devnull s->x = 0;
61 76193d7c 2003-09-30 devnull s->a = a;
62 76193d7c 2003-09-30 devnull s->a2 = (vlong)(a*a);
63 76193d7c 2003-09-30 devnull s->b2 = (vlong)(b*b);
64 76193d7c 2003-09-30 devnull s->b2x = (vlong)0;
65 76193d7c 2003-09-30 devnull s->a2y = s->a2*(vlong)b;
66 76193d7c 2003-09-30 devnull s->c1 = -((s->a2>>2) + (vlong)(a&1) + s->b2);
67 76193d7c 2003-09-30 devnull s->c2 = -((s->b2>>2) + (vlong)(b&1));
68 76193d7c 2003-09-30 devnull s->ee = -s->a2y;
69 76193d7c 2003-09-30 devnull s->dxe = (vlong)0;
70 76193d7c 2003-09-30 devnull s->dye = s->ee<<1;
71 76193d7c 2003-09-30 devnull s->d2xe = s->b2<<1;
72 76193d7c 2003-09-30 devnull s->d2ye = s->a2<<1;
73 76193d7c 2003-09-30 devnull return s;
77 76193d7c 2003-09-30 devnull * return x coord of rightmost pixel on next scan line
81 76193d7c 2003-09-30 devnull step(State *s)
83 76193d7c 2003-09-30 devnull while(s->x < s->a) {
84 76193d7c 2003-09-30 devnull if(s->ee+s->b2x <= s->c1 || /* e(x+1,y-1/2) <= 0 */
85 76193d7c 2003-09-30 devnull s->ee+s->a2y <= s->c2) { /* e(x+1/2,y) <= 0 (rare) */
86 76193d7c 2003-09-30 devnull s->dxe += s->d2xe;
87 76193d7c 2003-09-30 devnull s->ee += s->dxe;
88 76193d7c 2003-09-30 devnull s->b2x += s->b2;
90 76193d7c 2003-09-30 devnull continue;
92 76193d7c 2003-09-30 devnull s->dye += s->d2ye;
93 76193d7c 2003-09-30 devnull s->ee += s->dye;
94 76193d7c 2003-09-30 devnull s->a2y -= s->a2;
95 76193d7c 2003-09-30 devnull if(s->ee-s->a2y <= s->c2) { /* e(x+1/2,y-1) <= 0 */
96 76193d7c 2003-09-30 devnull s->dxe += s->d2xe;
97 76193d7c 2003-09-30 devnull s->ee += s->dxe;
98 76193d7c 2003-09-30 devnull s->b2x += s->b2;
99 76193d7c 2003-09-30 devnull return s->x++;
103 76193d7c 2003-09-30 devnull return s->x;
107 76193d7c 2003-09-30 devnull memellipse(Memimage *dst, Point c, int a, int b, int t, Memimage *src, Point sp, int op)
109 76193d7c 2003-09-30 devnull State in, out;
110 76193d7c 2003-09-30 devnull int y, inb, inx, outx, u;
111 76193d7c 2003-09-30 devnull Param p;
113 76193d7c 2003-09-30 devnull if(a < 0)
115 76193d7c 2003-09-30 devnull if(b < 0)
117 76193d7c 2003-09-30 devnull p.dst = dst;
118 76193d7c 2003-09-30 devnull p.src = src;
119 76193d7c 2003-09-30 devnull p.c = c;
120 76193d7c 2003-09-30 devnull p.t = t;
121 76193d7c 2003-09-30 devnull p.sp = subpt(sp, c);
122 76193d7c 2003-09-30 devnull p.disc = nil;
123 76193d7c 2003-09-30 devnull p.op = op;
125 76193d7c 2003-09-30 devnull u = (t<<1)*(a-b);
126 76193d7c 2003-09-30 devnull if(b<a && u>b*b || a<b && -u>a*a) {
127 76193d7c 2003-09-30 devnull /* if(b<a&&(t<<1)>b*b/a || a<b&&(t<<1)>a*a/b) # very thick */
128 76193d7c 2003-09-30 devnull bellipse(b, newstate(&in, a, b), &p);
132 76193d7c 2003-09-30 devnull if(t < 0) {
133 76193d7c 2003-09-30 devnull inb = -1;
134 76193d7c 2003-09-30 devnull newstate(&out, a, y = b);
135 76193d7c 2003-09-30 devnull } else {
136 76193d7c 2003-09-30 devnull inb = b - t;
137 76193d7c 2003-09-30 devnull newstate(&out, a+t, y = b+t);
139 76193d7c 2003-09-30 devnull if(t > 0)
140 76193d7c 2003-09-30 devnull newstate(&in, a-t, inb);
141 76193d7c 2003-09-30 devnull inx = 0;
142 76193d7c 2003-09-30 devnull for( ; y>=0; y--) {
143 76193d7c 2003-09-30 devnull outx = step(&out);
144 76193d7c 2003-09-30 devnull if(y > inb) {
145 76193d7c 2003-09-30 devnull erect(-outx, y, outx, y, &p);
146 76193d7c 2003-09-30 devnull if(y != 0)
147 76193d7c 2003-09-30 devnull erect(-outx, -y, outx, -y, &p);
148 76193d7c 2003-09-30 devnull continue;
150 76193d7c 2003-09-30 devnull if(t > 0) {
151 76193d7c 2003-09-30 devnull inx = step(&in);
152 76193d7c 2003-09-30 devnull if(y == inb)
153 76193d7c 2003-09-30 devnull inx = 0;
154 76193d7c 2003-09-30 devnull } else if(inx > outx)
155 76193d7c 2003-09-30 devnull inx = outx;
156 76193d7c 2003-09-30 devnull erect(inx, y, outx, y, &p);
157 76193d7c 2003-09-30 devnull if(y != 0)
158 76193d7c 2003-09-30 devnull erect(inx, -y, outx, -y, &p);
159 76193d7c 2003-09-30 devnull erect(-outx, y, -inx, y, &p);
160 76193d7c 2003-09-30 devnull if(y != 0)
161 76193d7c 2003-09-30 devnull erect(-outx, -y, -inx, -y, &p);
162 76193d7c 2003-09-30 devnull inx = outx + 1;
166 76193d7c 2003-09-30 devnull static Point p00 = {0, 0};
169 76193d7c 2003-09-30 devnull * a brushed ellipse
173 76193d7c 2003-09-30 devnull bellipse(int y, State *s, Param *p)
175 76193d7c 2003-09-30 devnull int t, ox, oy, x, nx;
177 76193d7c 2003-09-30 devnull t = p->t;
178 76193d7c 2003-09-30 devnull p->disc = allocmemimage(Rect(-t,-t,t+1,t+1), GREY1);
179 76193d7c 2003-09-30 devnull if(p->disc == nil)
181 76193d7c 2003-09-30 devnull memfillcolor(p->disc, DTransparent);
182 76193d7c 2003-09-30 devnull memellipse(p->disc, p00, t, t, -1, memopaque, p00, p->op);
185 76193d7c 2003-09-30 devnull nx = x = step(s);
187 76193d7c 2003-09-30 devnull while(nx==x && y-->0)
188 76193d7c 2003-09-30 devnull nx = step(s);
190 76193d7c 2003-09-30 devnull eline(-x,-oy,-ox, -y, p);
191 76193d7c 2003-09-30 devnull eline(ox,-oy, x, -y, p);
192 76193d7c 2003-09-30 devnull eline(-x, y,-ox, oy, p);
193 76193d7c 2003-09-30 devnull eline(ox, y, x, oy, p);
194 76193d7c 2003-09-30 devnull ox = x+1;
198 76193d7c 2003-09-30 devnull } while(oy > 0);
202 76193d7c 2003-09-30 devnull * a rectangle with closed (not half-open) coordinates expressed
203 76193d7c 2003-09-30 devnull * relative to the center of the ellipse
207 76193d7c 2003-09-30 devnull erect(int x0, int y0, int x1, int y1, Param *p)
209 76193d7c 2003-09-30 devnull Rectangle r;
211 76193d7c 2003-09-30 devnull /* print("R %d,%d %d,%d\n", x0, y0, x1, y1); */
212 76193d7c 2003-09-30 devnull r = Rect(p->c.x+x0, p->c.y+y0, p->c.x+x1+1, p->c.y+y1+1);
213 76193d7c 2003-09-30 devnull memdraw(p->dst, r, p->src, addpt(p->sp, r.min), memopaque, p00, p->op);
217 76193d7c 2003-09-30 devnull * a brushed point similarly specified
221 76193d7c 2003-09-30 devnull epoint(int x, int y, Param *p)
223 76193d7c 2003-09-30 devnull Point p0;
224 76193d7c 2003-09-30 devnull Rectangle r;
226 76193d7c 2003-09-30 devnull /* print("P%d %d,%d\n", p->t, x, y); */
227 76193d7c 2003-09-30 devnull p0 = Pt(p->c.x+x, p->c.y+y);
228 76193d7c 2003-09-30 devnull r = Rpt(addpt(p0, p->disc->r.min), addpt(p0, p->disc->r.max));
229 76193d7c 2003-09-30 devnull memdraw(p->dst, r, p->src, addpt(p->sp, r.min), p->disc, p->disc->r.min, p->op);
233 76193d7c 2003-09-30 devnull * a brushed horizontal or vertical line similarly specified
237 76193d7c 2003-09-30 devnull eline(int x0, int y0, int x1, int y1, Param *p)
239 76193d7c 2003-09-30 devnull /* print("L%d %d,%d %d,%d\n", p->t, x0, y0, x1, y1); */
240 76193d7c 2003-09-30 devnull if(x1 > x0+1)
241 76193d7c 2003-09-30 devnull erect(x0+1, y0-p->t, x1-1, y1+p->t, p);
242 76193d7c 2003-09-30 devnull else if(y1 > y0+1)
243 76193d7c 2003-09-30 devnull erect(x0-p->t, y0+1, x1+p->t, y1-1, p);
244 76193d7c 2003-09-30 devnull epoint(x0, y0, p);
245 76193d7c 2003-09-30 devnull if(x1-x0 || y1-y0)
246 76193d7c 2003-09-30 devnull epoint(x1, y1, p);
