xref: /plan9/sys/src/cmd/unix/drawterm/libmemdraw/ellipse.c (revision 8ccd4a6360d974db7bd7bbd4f37e7018419ea908)
1*8ccd4a63SDavid du Colombier #include <u.h>
2*8ccd4a63SDavid du Colombier #include <libc.h>
3*8ccd4a63SDavid du Colombier #include <draw.h>
4*8ccd4a63SDavid du Colombier #include <memdraw.h>
5*8ccd4a63SDavid du Colombier #include <memlayer.h>
67dd7cddfSDavid du Colombier 
77dd7cddfSDavid du Colombier /*
87dd7cddfSDavid du Colombier  * ellipse(dst, c, a, b, t, src, sp)
97dd7cddfSDavid du Colombier  *   draws an ellipse centered at c with semiaxes a,b>=0
107dd7cddfSDavid du Colombier  *   and semithickness t>=0, or filled if t<0.  point sp
117dd7cddfSDavid du Colombier  *   in src maps to c in dst
127dd7cddfSDavid du Colombier  *
137dd7cddfSDavid du Colombier  *   very thick skinny ellipses are brushed with circles (slow)
147dd7cddfSDavid du Colombier  *   others are approximated by filling between 2 ellipses
157dd7cddfSDavid du Colombier  *   criterion for very thick when b<a: t/b > 0.5*x/(1-x)
167dd7cddfSDavid du Colombier  *   where x = b/a
177dd7cddfSDavid du Colombier  */
187dd7cddfSDavid du Colombier 
197dd7cddfSDavid du Colombier typedef struct Param	Param;
207dd7cddfSDavid du Colombier typedef struct State	State;
217dd7cddfSDavid du Colombier 
227dd7cddfSDavid du Colombier static	void	bellipse(int, State*, Param*);
237dd7cddfSDavid du Colombier static	void	erect(int, int, int, int, Param*);
247dd7cddfSDavid du Colombier static	void	eline(int, int, int, int, Param*);
257dd7cddfSDavid du Colombier 
267dd7cddfSDavid du Colombier struct Param {
277dd7cddfSDavid du Colombier 	Memimage	*dst;
287dd7cddfSDavid du Colombier 	Memimage	*src;
297dd7cddfSDavid du Colombier 	Point			c;
307dd7cddfSDavid du Colombier 	int			t;
317dd7cddfSDavid du Colombier 	Point			sp;
327dd7cddfSDavid du Colombier 	Memimage	*disc;
33*8ccd4a63SDavid du Colombier 	int			op;
347dd7cddfSDavid du Colombier };
357dd7cddfSDavid du Colombier 
367dd7cddfSDavid du Colombier /*
377dd7cddfSDavid du Colombier  * denote residual error by e(x,y) = b^2*x^2 + a^2*y^2 - a^2*b^2
387dd7cddfSDavid du Colombier  * e(x,y) = 0 on ellipse, e(x,y) < 0 inside, e(x,y) > 0 outside
397dd7cddfSDavid du Colombier  */
407dd7cddfSDavid du Colombier 
417dd7cddfSDavid du Colombier struct State {
427dd7cddfSDavid du Colombier 	int	a;
437dd7cddfSDavid du Colombier 	int	x;
447dd7cddfSDavid du Colombier 	vlong	a2;	/* a^2 */
457dd7cddfSDavid du Colombier 	vlong	b2;	/* b^2 */
467dd7cddfSDavid du Colombier 	vlong	b2x;	/* b^2 * x */
477dd7cddfSDavid du Colombier 	vlong	a2y;	/* a^2 * y */
487dd7cddfSDavid du Colombier 	vlong	c1;
497dd7cddfSDavid du Colombier 	vlong	c2;	/* test criteria */
507dd7cddfSDavid du Colombier 	vlong	ee;	/* ee = e(x+1/2,y-1/2) - (a^2+b^2)/4 */
517dd7cddfSDavid du Colombier 	vlong	dxe;
527dd7cddfSDavid du Colombier 	vlong	dye;
537dd7cddfSDavid du Colombier 	vlong	d2xe;
547dd7cddfSDavid du Colombier 	vlong	d2ye;
557dd7cddfSDavid du Colombier };
567dd7cddfSDavid du Colombier 
577dd7cddfSDavid du Colombier static
587dd7cddfSDavid du Colombier State*
newstate(State * s,int a,int b)597dd7cddfSDavid du Colombier newstate(State *s, int a, int b)
607dd7cddfSDavid du Colombier {
617dd7cddfSDavid du Colombier 	s->x = 0;
627dd7cddfSDavid du Colombier 	s->a = a;
637dd7cddfSDavid du Colombier 	s->a2 = (vlong)(a*a);
647dd7cddfSDavid du Colombier 	s->b2 = (vlong)(b*b);
657dd7cddfSDavid du Colombier 	s->b2x = (vlong)0;
667dd7cddfSDavid du Colombier 	s->a2y = s->a2*(vlong)b;
677dd7cddfSDavid du Colombier 	s->c1 = -((s->a2>>2) + (vlong)(a&1) + s->b2);
687dd7cddfSDavid du Colombier 	s->c2 = -((s->b2>>2) + (vlong)(b&1));
697dd7cddfSDavid du Colombier 	s->ee = -s->a2y;
707dd7cddfSDavid du Colombier 	s->dxe = (vlong)0;
717dd7cddfSDavid du Colombier 	s->dye = s->ee<<1;
727dd7cddfSDavid du Colombier 	s->d2xe = s->b2<<1;
737dd7cddfSDavid du Colombier 	s->d2ye = s->a2<<1;
747dd7cddfSDavid du Colombier 	return s;
757dd7cddfSDavid du Colombier }
767dd7cddfSDavid du Colombier 
777dd7cddfSDavid du Colombier /*
787dd7cddfSDavid du Colombier  * return x coord of rightmost pixel on next scan line
797dd7cddfSDavid du Colombier  */
807dd7cddfSDavid du Colombier static
817dd7cddfSDavid du Colombier int
step(State * s)827dd7cddfSDavid du Colombier step(State *s)
837dd7cddfSDavid du Colombier {
847dd7cddfSDavid du Colombier 	while(s->x < s->a) {
857dd7cddfSDavid du Colombier 		if(s->ee+s->b2x <= s->c1 ||	/* e(x+1,y-1/2) <= 0 */
867dd7cddfSDavid du Colombier 		   s->ee+s->a2y <= s->c2) {	/* e(x+1/2,y) <= 0 (rare) */
877dd7cddfSDavid du Colombier 			s->dxe += s->d2xe;
887dd7cddfSDavid du Colombier 			s->ee += s->dxe;
897dd7cddfSDavid du Colombier 			s->b2x += s->b2;
907dd7cddfSDavid du Colombier 			s->x++;
917dd7cddfSDavid du Colombier 			continue;
927dd7cddfSDavid du Colombier 		}
937dd7cddfSDavid du Colombier 		s->dye += s->d2ye;
947dd7cddfSDavid du Colombier 		s->ee += s->dye;
957dd7cddfSDavid du Colombier 		s->a2y -= s->a2;
967dd7cddfSDavid du Colombier 		if(s->ee-s->a2y <= s->c2) {	/* e(x+1/2,y-1) <= 0 */
977dd7cddfSDavid du Colombier 			s->dxe += s->d2xe;
987dd7cddfSDavid du Colombier 			s->ee += s->dxe;
997dd7cddfSDavid du Colombier 			s->b2x += s->b2;
1007dd7cddfSDavid du Colombier 			return s->x++;
1017dd7cddfSDavid du Colombier 		}
1027dd7cddfSDavid du Colombier 		break;
1037dd7cddfSDavid du Colombier 	}
1047dd7cddfSDavid du Colombier 	return s->x;
1057dd7cddfSDavid du Colombier }
1067dd7cddfSDavid du Colombier 
1077dd7cddfSDavid du Colombier void
memellipse(Memimage * dst,Point c,int a,int b,int t,Memimage * src,Point sp,int op)108*8ccd4a63SDavid du Colombier memellipse(Memimage *dst, Point c, int a, int b, int t, Memimage *src, Point sp, int op)
1097dd7cddfSDavid du Colombier {
1107dd7cddfSDavid du Colombier 	State in, out;
1117dd7cddfSDavid du Colombier 	int y, inb, inx, outx, u;
1127dd7cddfSDavid du Colombier 	Param p;
1137dd7cddfSDavid du Colombier 
1147dd7cddfSDavid du Colombier 	if(a < 0)
1157dd7cddfSDavid du Colombier 		a = -a;
1167dd7cddfSDavid du Colombier 	if(b < 0)
1177dd7cddfSDavid du Colombier 		b = -b;
1187dd7cddfSDavid du Colombier 	p.dst = dst;
1197dd7cddfSDavid du Colombier 	p.src = src;
1207dd7cddfSDavid du Colombier 	p.c = c;
1217dd7cddfSDavid du Colombier 	p.t = t;
1227dd7cddfSDavid du Colombier 	p.sp = subpt(sp, c);
1237dd7cddfSDavid du Colombier 	p.disc = nil;
124*8ccd4a63SDavid du Colombier 	p.op = op;
1257dd7cddfSDavid du Colombier 
1267dd7cddfSDavid du Colombier 	u = (t<<1)*(a-b);
1277dd7cddfSDavid du Colombier 	if((b<a && u>b*b) || (a<b && -u>a*a)) {
1287dd7cddfSDavid du Colombier /*	if(b<a&&(t<<1)>b*b/a || a<b&&(t<<1)>a*a/b)	# very thick */
1297dd7cddfSDavid du Colombier 		bellipse(b, newstate(&in, a, b), &p);
1307dd7cddfSDavid du Colombier 		return;
1317dd7cddfSDavid du Colombier 	}
1327dd7cddfSDavid du Colombier 
1337dd7cddfSDavid du Colombier 	if(t < 0) {
1347dd7cddfSDavid du Colombier 		inb = -1;
1357dd7cddfSDavid du Colombier 		newstate(&out, a, y = b);
1367dd7cddfSDavid du Colombier 	} else {
1377dd7cddfSDavid du Colombier 		inb = b - t;
1387dd7cddfSDavid du Colombier 		newstate(&out, a+t, y = b+t);
1397dd7cddfSDavid du Colombier 	}
1407dd7cddfSDavid du Colombier 	if(t > 0)
1417dd7cddfSDavid du Colombier 		newstate(&in, a-t, inb);
1427dd7cddfSDavid du Colombier 	inx = 0;
1437dd7cddfSDavid du Colombier 	for( ; y>=0; y--) {
1447dd7cddfSDavid du Colombier 		outx = step(&out);
1457dd7cddfSDavid du Colombier 		if(y > inb) {
1467dd7cddfSDavid du Colombier 			erect(-outx, y, outx, y, &p);
14759cc4ca5SDavid du Colombier 			if(y != 0)
1487dd7cddfSDavid du Colombier 				erect(-outx, -y, outx, -y, &p);
1497dd7cddfSDavid du Colombier 			continue;
1507dd7cddfSDavid du Colombier 		}
1517dd7cddfSDavid du Colombier 		if(t > 0) {
1527dd7cddfSDavid du Colombier 			inx = step(&in);
1537dd7cddfSDavid du Colombier 			if(y == inb)
1547dd7cddfSDavid du Colombier 				inx = 0;
1557dd7cddfSDavid du Colombier 		} else if(inx > outx)
1567dd7cddfSDavid du Colombier 			inx = outx;
1577dd7cddfSDavid du Colombier 		erect(inx, y, outx, y, &p);
15859cc4ca5SDavid du Colombier 		if(y != 0)
1597dd7cddfSDavid du Colombier 			erect(inx, -y, outx, -y, &p);
1607dd7cddfSDavid du Colombier 		erect(-outx, y, -inx, y, &p);
16159cc4ca5SDavid du Colombier 		if(y != 0)
1627dd7cddfSDavid du Colombier 			erect(-outx, -y, -inx, -y, &p);
1637dd7cddfSDavid du Colombier 		inx = outx + 1;
1647dd7cddfSDavid du Colombier 	}
1657dd7cddfSDavid du Colombier }
1667dd7cddfSDavid du Colombier 
1677dd7cddfSDavid du Colombier static Point p00 = {0, 0};
1687dd7cddfSDavid du Colombier 
1697dd7cddfSDavid du Colombier /*
1707dd7cddfSDavid du Colombier  * a brushed ellipse
1717dd7cddfSDavid du Colombier  */
1727dd7cddfSDavid du Colombier static
1737dd7cddfSDavid du Colombier void
bellipse(int y,State * s,Param * p)1747dd7cddfSDavid du Colombier bellipse(int y, State *s, Param *p)
1757dd7cddfSDavid du Colombier {
1767dd7cddfSDavid du Colombier 	int t, ox, oy, x, nx;
1777dd7cddfSDavid du Colombier 
1787dd7cddfSDavid du Colombier 	t = p->t;
1797dd7cddfSDavid du Colombier 	p->disc = allocmemimage(Rect(-t,-t,t+1,t+1), GREY1);
1807dd7cddfSDavid du Colombier 	if(p->disc == nil)
1817dd7cddfSDavid du Colombier 		return;
1827dd7cddfSDavid du Colombier 	memfillcolor(p->disc, DTransparent);
183*8ccd4a63SDavid du Colombier 	memellipse(p->disc, p00, t, t, -1, memopaque, p00, p->op);
1847dd7cddfSDavid du Colombier 	oy = y;
1857dd7cddfSDavid du Colombier 	ox = 0;
1867dd7cddfSDavid du Colombier 	nx = x = step(s);
1877dd7cddfSDavid du Colombier 	do {
1887dd7cddfSDavid du Colombier 		while(nx==x && y-->0)
1897dd7cddfSDavid du Colombier 			nx = step(s);
1907dd7cddfSDavid du Colombier 		y++;
1917dd7cddfSDavid du Colombier 		eline(-x,-oy,-ox, -y, p);
1927dd7cddfSDavid du Colombier 		eline(ox,-oy,  x, -y, p);
1937dd7cddfSDavid du Colombier 		eline(-x,  y,-ox, oy, p);
1947dd7cddfSDavid du Colombier 		eline(ox,  y,  x, oy, p);
1957dd7cddfSDavid du Colombier 		ox = x+1;
1967dd7cddfSDavid du Colombier 		x = nx;
1977dd7cddfSDavid du Colombier 		y--;
1987dd7cddfSDavid du Colombier 		oy = y;
1997dd7cddfSDavid du Colombier 	} while(oy > 0);
2007dd7cddfSDavid du Colombier }
2017dd7cddfSDavid du Colombier 
2027dd7cddfSDavid du Colombier /*
2037dd7cddfSDavid du Colombier  * a rectangle with closed (not half-open) coordinates expressed
2047dd7cddfSDavid du Colombier  * relative to the center of the ellipse
2057dd7cddfSDavid du Colombier  */
2067dd7cddfSDavid du Colombier static
2077dd7cddfSDavid du Colombier void
erect(int x0,int y0,int x1,int y1,Param * p)2087dd7cddfSDavid du Colombier erect(int x0, int y0, int x1, int y1, Param *p)
2097dd7cddfSDavid du Colombier {
2107dd7cddfSDavid du Colombier 	Rectangle r;
2117dd7cddfSDavid du Colombier 
2127dd7cddfSDavid du Colombier /*	print("R %d,%d %d,%d\n", x0, y0, x1, y1); */
2137dd7cddfSDavid du Colombier 	r = Rect(p->c.x+x0, p->c.y+y0, p->c.x+x1+1, p->c.y+y1+1);
214*8ccd4a63SDavid du Colombier 	memdraw(p->dst, r, p->src, addpt(p->sp, r.min), memopaque, p00, p->op);
2157dd7cddfSDavid du Colombier }
2167dd7cddfSDavid du Colombier 
2177dd7cddfSDavid du Colombier /*
2187dd7cddfSDavid du Colombier  * a brushed point similarly specified
2197dd7cddfSDavid du Colombier  */
2207dd7cddfSDavid du Colombier static
2217dd7cddfSDavid du Colombier void
epoint(int x,int y,Param * p)2227dd7cddfSDavid du Colombier epoint(int x, int y, Param *p)
2237dd7cddfSDavid du Colombier {
2247dd7cddfSDavid du Colombier 	Point p0;
2257dd7cddfSDavid du Colombier 	Rectangle r;
2267dd7cddfSDavid du Colombier 
2277dd7cddfSDavid du Colombier /*	print("P%d %d,%d\n", p->t, x, y);	*/
2287dd7cddfSDavid du Colombier 	p0 = Pt(p->c.x+x, p->c.y+y);
2297dd7cddfSDavid du Colombier 	r = Rpt(addpt(p0, p->disc->r.min), addpt(p0, p->disc->r.max));
230*8ccd4a63SDavid du Colombier 	memdraw(p->dst, r, p->src, addpt(p->sp, r.min), p->disc, p->disc->r.min, p->op);
2317dd7cddfSDavid du Colombier }
2327dd7cddfSDavid du Colombier 
2337dd7cddfSDavid du Colombier /*
2347dd7cddfSDavid du Colombier  * a brushed horizontal or vertical line similarly specified
2357dd7cddfSDavid du Colombier  */
2367dd7cddfSDavid du Colombier static
2377dd7cddfSDavid du Colombier void
eline(int x0,int y0,int x1,int y1,Param * p)2387dd7cddfSDavid du Colombier eline(int x0, int y0, int x1, int y1, Param *p)
2397dd7cddfSDavid du Colombier {
2407dd7cddfSDavid du Colombier /*	print("L%d %d,%d %d,%d\n", p->t, x0, y0, x1, y1); */
2417dd7cddfSDavid du Colombier 	if(x1 > x0+1)
2427dd7cddfSDavid du Colombier 		erect(x0+1, y0-p->t, x1-1, y1+p->t, p);
2437dd7cddfSDavid du Colombier 	else if(y1 > y0+1)
2447dd7cddfSDavid du Colombier 		erect(x0-p->t, y0+1, x1+p->t, y1-1, p);
2457dd7cddfSDavid du Colombier 	epoint(x0, y0, p);
2467dd7cddfSDavid du Colombier 	if(x1-x0 || y1-y0)
2477dd7cddfSDavid du Colombier 		epoint(x1, y1, p);
2487dd7cddfSDavid du Colombier }
249