ellipse.c - vx32 - Local 9vx git repository for patches.
(HTM) git clone git://r-36.net/vx32
(DIR) Log
(DIR) Files
(DIR) Refs
---
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 }