xref: /plan9/sys/src/libmemdraw/line.c (revision e5b1f7dde43c88534ab5bb52aa101ce2f496062a)
1 #include <u.h>
2 #include <libc.h>
3 #include <draw.h>
4 #include <memdraw.h>
5 #include <memlayer.h>
6 
7 enum
8 {
9 	Arrow1 = 8,
10 	Arrow2 = 10,
11 	Arrow3 = 3,
12 };
13 
14 static
15 int
lmin(int a,int b)16 lmin(int a, int b)
17 {
18 	if(a < b)
19 		return a;
20 	return b;
21 }
22 
23 static
24 int
lmax(int a,int b)25 lmax(int a, int b)
26 {
27 	if(a > b)
28 		return a;
29 	return b;
30 }
31 
32 #ifdef NOTUSED
33 /*
34  * Rather than line clip, we run the Bresenham loop over the full line,
35  * and clip on each pixel.  This is more expensive but means that
36  * lines look the same regardless of how the windowing has tiled them.
37  * For speed, we check for clipping outside the loop and make the
38  * test easy when possible.
39  */
40 
41 static
42 void
horline1(Memimage * dst,Point p0,Point p1,int srcval,Rectangle clipr)43 horline1(Memimage *dst, Point p0, Point p1, int srcval, Rectangle clipr)
44 {
45 	int x, y, dy, deltay, deltax, maxx;
46 	int dd, easy, e, bpp, m, m0;
47 	uchar *d;
48 
49 	deltax = p1.x - p0.x;
50 	deltay = p1.y - p0.y;
51 	dd = dst->width*sizeof(ulong);
52 	dy = 1;
53 	if(deltay < 0){
54 		dd = -dd;
55 		deltay = -deltay;
56 		dy = -1;
57 	}
58 	maxx = lmin(p1.x, clipr.max.x-1);
59 	bpp = dst->depth;
60 	m0 = 0xFF^(0xFF>>bpp);
61 	m = m0 >> (p0.x&(7/dst->depth))*bpp;
62 	easy = ptinrect(p0, clipr) && ptinrect(p1, clipr);
63 	e = 2*deltay - deltax;
64 	y = p0.y;
65 	d = byteaddr(dst, p0);
66 	deltay *= 2;
67 	deltax = deltay - 2*deltax;
68 	for(x=p0.x; x<=maxx; x++){
69 		if(easy || (clipr.min.x<=x && clipr.min.y<=y && y<clipr.max.y))
70 			*d ^= (*d^srcval) & m;
71 		if(e > 0){
72 			y += dy;
73 			d += dd;
74 			e += deltax;
75 		}else
76 			e += deltay;
77 		d++;
78 		m >>= bpp;
79 		if(m == 0)
80 			m = m0;
81 	}
82 }
83 
84 static
85 void
verline1(Memimage * dst,Point p0,Point p1,int srcval,Rectangle clipr)86 verline1(Memimage *dst, Point p0, Point p1, int srcval, Rectangle clipr)
87 {
88 	int x, y, deltay, deltax, maxy;
89 	int easy, e, bpp, m, m0, dd;
90 	uchar *d;
91 
92 	deltax = p1.x - p0.x;
93 	deltay = p1.y - p0.y;
94 	dd = 1;
95 	if(deltax < 0){
96 		dd = -1;
97 		deltax = -deltax;
98 	}
99 	maxy = lmin(p1.y, clipr.max.y-1);
100 	bpp = dst->depth;
101 	m0 = 0xFF^(0xFF>>bpp);
102 	m = m0 >> (p0.x&(7/dst->depth))*bpp;
103 	easy = ptinrect(p0, clipr) && ptinrect(p1, clipr);
104 	e = 2*deltax - deltay;
105 	x = p0.x;
106 	d = byteaddr(dst, p0);
107 	deltax *= 2;
108 	deltay = deltax - 2*deltay;
109 	for(y=p0.y; y<=maxy; y++){
110 		if(easy || (clipr.min.y<=y && clipr.min.x<=x && x<clipr.max.x))
111 			*d ^= (*d^srcval) & m;
112 		if(e > 0){
113 			x += dd;
114 			d += dd;
115 			e += deltay;
116 		}else
117 			e += deltax;
118 		d += dst->width*sizeof(ulong);
119 		m >>= bpp;
120 		if(m == 0)
121 			m = m0;
122 	}
123 }
124 
125 static
126 void
horliner(Memimage * dst,Point p0,Point p1,Memimage * src,Point dsrc,Rectangle clipr)127 horliner(Memimage *dst, Point p0, Point p1, Memimage *src, Point dsrc, Rectangle clipr)
128 {
129 	int x, y, sx, sy, deltay, deltax, minx, maxx;
130 	int bpp, m, m0;
131 	uchar *d, *s;
132 
133 	deltax = p1.x - p0.x;
134 	deltay = p1.y - p0.y;
135 	sx = drawreplxy(src->r.min.x, src->r.max.x, p0.x+dsrc.x);
136 	minx = lmax(p0.x, clipr.min.x);
137 	maxx = lmin(p1.x, clipr.max.x-1);
138 	bpp = dst->depth;
139 	m0 = 0xFF^(0xFF>>bpp);
140 	m = m0 >> (minx&(7/dst->depth))*bpp;
141 	for(x=minx; x<=maxx; x++){
142 		y = p0.y + (deltay*(x-p0.x)+deltax/2)/deltax;
143 		if(clipr.min.y<=y && y<clipr.max.y){
144 			d = byteaddr(dst, Pt(x, y));
145 			sy = drawreplxy(src->r.min.y, src->r.max.y, y+dsrc.y);
146 			s = byteaddr(src, Pt(sx, sy));
147 			*d ^= (*d^*s) & m;
148 		}
149 		if(++sx >= src->r.max.x)
150 			sx = src->r.min.x;
151 		m >>= bpp;
152 		if(m == 0)
153 			m = m0;
154 	}
155 }
156 
157 static
158 void
verliner(Memimage * dst,Point p0,Point p1,Memimage * src,Point dsrc,Rectangle clipr)159 verliner(Memimage *dst, Point p0, Point p1, Memimage *src, Point dsrc, Rectangle clipr)
160 {
161 	int x, y, sx, sy, deltay, deltax, miny, maxy;
162 	int bpp, m, m0;
163 	uchar *d, *s;
164 
165 	deltax = p1.x - p0.x;
166 	deltay = p1.y - p0.y;
167 	sy = drawreplxy(src->r.min.y, src->r.max.y, p0.y+dsrc.y);
168 	miny = lmax(p0.y, clipr.min.y);
169 	maxy = lmin(p1.y, clipr.max.y-1);
170 	bpp = dst->depth;
171 	m0 = 0xFF^(0xFF>>bpp);
172 	for(y=miny; y<=maxy; y++){
173 		if(deltay == 0)	/* degenerate line */
174 			x = p0.x;
175 		else
176 			x = p0.x + (deltax*(y-p0.y)+deltay/2)/deltay;
177 		if(clipr.min.x<=x && x<clipr.max.x){
178 			m = m0 >> (x&(7/dst->depth))*bpp;
179 			d = byteaddr(dst, Pt(x, y));
180 			sx = drawreplxy(src->r.min.x, src->r.max.x, x+dsrc.x);
181 			s = byteaddr(src, Pt(sx, sy));
182 			*d ^= (*d^*s) & m;
183 		}
184 		if(++sy >= src->r.max.y)
185 			sy = src->r.min.y;
186 	}
187 }
188 
189 static
190 void
horline(Memimage * dst,Point p0,Point p1,Memimage * src,Point dsrc,Rectangle clipr)191 horline(Memimage *dst, Point p0, Point p1, Memimage *src, Point dsrc, Rectangle clipr)
192 {
193 	int x, y, deltay, deltax, minx, maxx;
194 	int bpp, m, m0;
195 	uchar *d, *s;
196 
197 	deltax = p1.x - p0.x;
198 	deltay = p1.y - p0.y;
199 	minx = lmax(p0.x, clipr.min.x);
200 	maxx = lmin(p1.x, clipr.max.x-1);
201 	bpp = dst->depth;
202 	m0 = 0xFF^(0xFF>>bpp);
203 	m = m0 >> (minx&(7/dst->depth))*bpp;
204 	for(x=minx; x<=maxx; x++){
205 		y = p0.y + (deltay*(x-p0.x)+deltay/2)/deltax;
206 		if(clipr.min.y<=y && y<clipr.max.y){
207 			d = byteaddr(dst, Pt(x, y));
208 			s = byteaddr(src, addpt(dsrc, Pt(x, y)));
209 			*d ^= (*d^*s) & m;
210 		}
211 		m >>= bpp;
212 		if(m == 0)
213 			m = m0;
214 	}
215 }
216 
217 static
218 void
verline(Memimage * dst,Point p0,Point p1,Memimage * src,Point dsrc,Rectangle clipr)219 verline(Memimage *dst, Point p0, Point p1, Memimage *src, Point dsrc, Rectangle clipr)
220 {
221 	int x, y, deltay, deltax, miny, maxy;
222 	int bpp, m, m0;
223 	uchar *d, *s;
224 
225 	deltax = p1.x - p0.x;
226 	deltay = p1.y - p0.y;
227 	miny = lmax(p0.y, clipr.min.y);
228 	maxy = lmin(p1.y, clipr.max.y-1);
229 	bpp = dst->depth;
230 	m0 = 0xFF^(0xFF>>bpp);
231 	for(y=miny; y<=maxy; y++){
232 		if(deltay == 0)	/* degenerate line */
233 			x = p0.x;
234 		else
235 			x = p0.x + deltax*(y-p0.y)/deltay;
236 		if(clipr.min.x<=x && x<clipr.max.x){
237 			m = m0 >> (x&(7/dst->depth))*bpp;
238 			d = byteaddr(dst, Pt(x, y));
239 			s = byteaddr(src, addpt(dsrc, Pt(x, y)));
240 			*d ^= (*d^*s) & m;
241 		}
242 	}
243 }
244 #endif /* NOTUSED */
245 
246 static Memimage*
membrush(int radius)247 membrush(int radius)
248 {
249 	static Memimage *brush;
250 	static int brushradius;
251 
252 	if(brush==nil || brushradius!=radius){
253 		freememimage(brush);
254 		brush = allocmemimage(Rect(0, 0, 2*radius+1, 2*radius+1), memopaque->chan);
255 		if(brush != nil){
256 			memfillcolor(brush, DTransparent);	/* zeros */
257 			memellipse(brush, Pt(radius, radius), radius, radius, -1, memopaque, Pt(radius, radius), S);
258 		}
259 		brushradius = radius;
260 	}
261 	return brush;
262 }
263 
264 static
265 void
discend(Point p,int radius,Memimage * dst,Memimage * src,Point dsrc,int op)266 discend(Point p, int radius, Memimage *dst, Memimage *src, Point dsrc, int op)
267 {
268 	Memimage *disc;
269 	Rectangle r;
270 
271 	disc = membrush(radius);
272 	if(disc != nil){
273 		r.min.x = p.x - radius;
274 		r.min.y = p.y - radius;
275 		r.max.x = p.x + radius+1;
276 		r.max.y = p.y + radius+1;
277 		memdraw(dst, r, src, addpt(r.min, dsrc), disc, Pt(0,0), op);
278 	}
279 }
280 
281 static
282 void
arrowend(Point tip,Point * pp,int end,int sin,int cos,int radius)283 arrowend(Point tip, Point *pp, int end, int sin, int cos, int radius)
284 {
285 	int x1, x2, x3;
286 
287 	/* before rotation */
288 	if(end == Endarrow){
289 		x1 = Arrow1;
290 		x2 = Arrow2;
291 		x3 = Arrow3;
292 	}else{
293 		x1 = (end>>5) & 0x1FF;	/* distance along line from end of line to tip */
294 		x2 = (end>>14) & 0x1FF;	/* distance along line from barb to tip */
295 		x3 = (end>>23) & 0x1FF;	/* distance perpendicular from edge of line to barb */
296 	}
297 
298 	/* comments follow track of right-facing arrowhead */
299 	pp->x = tip.x+((2*radius+1)*sin/2-x1*cos);		/* upper side of shaft */
300 	pp->y = tip.y-((2*radius+1)*cos/2+x1*sin);
301 	pp++;
302 	pp->x = tip.x+((2*radius+2*x3+1)*sin/2-x2*cos);		/* upper barb */
303 	pp->y = tip.y-((2*radius+2*x3+1)*cos/2+x2*sin);
304 	pp++;
305 	pp->x = tip.x;
306 	pp->y = tip.y;
307 	pp++;
308 	pp->x = tip.x+(-(2*radius+2*x3+1)*sin/2-x2*cos);	/* lower barb */
309 	pp->y = tip.y-(-(2*radius+2*x3+1)*cos/2+x2*sin);
310 	pp++;
311 	pp->x = tip.x+(-(2*radius+1)*sin/2-x1*cos);		/* lower side of shaft */
312 	pp->y = tip.y+((2*radius+1)*cos/2-x1*sin);
313 }
314 
315 void
_memimageline(Memimage * dst,Point p0,Point p1,int end0,int end1,int radius,Memimage * src,Point sp,Rectangle clipr,int op)316 _memimageline(Memimage *dst, Point p0, Point p1, int end0, int end1, int radius, Memimage *src, Point sp, Rectangle clipr, int op)
317 {
318 	/*
319 	 * BUG: We should really really pick off purely horizontal and purely
320 	 * vertical lines and handle them separately with calls to memimagedraw
321 	 * on rectangles.
322 	 */
323 
324 	int hor;
325 	int sin, cos, dx, dy, t;
326 	Rectangle oclipr, r;
327 	Point q, pts[10], *pp, d;
328 
329 	if(radius < 0)
330 		return;
331 	if(rectclip(&clipr, dst->r) == 0)
332 		return;
333 	if(rectclip(&clipr, dst->clipr) == 0)
334 		return;
335 	d = subpt(sp, p0);
336 	if(rectclip(&clipr, rectsubpt(src->clipr, d)) == 0)
337 		return;
338 	if((src->flags&Frepl)==0 && rectclip(&clipr, rectsubpt(src->r, d))==0)
339 		return;
340 	/* this means that only verline() handles degenerate lines (p0==p1) */
341 	hor = (abs(p1.x-p0.x) > abs(p1.y-p0.y));
342 	/*
343 	 * Clipping is a little peculiar.  We can't use Sutherland-Cohen
344 	 * clipping because lines are wide.  But this is probably just fine:
345 	 * we do all math with the original p0 and p1, but clip when deciding
346 	 * what pixels to draw.  This means the layer code can call this routine,
347 	 * using clipr to define the region being written, and get the same set
348 	 * of pixels regardless of the dicing.
349 	 */
350 	if((hor && p0.x>p1.x) || (!hor && p0.y>p1.y)){
351 		q = p0;
352 		p0 = p1;
353 		p1 = q;
354 		t = end0;
355 		end0 = end1;
356 		end1 = t;
357 	}
358 
359 	if((p0.x == p1.x || p0.y == p1.y) && (end0&0x1F) == Endsquare && (end1&0x1F) == Endsquare){
360 		r.min = p0;
361 		r.max = p1;
362 		if(p0.x == p1.x){
363 			r.min.x -= radius;
364 			r.max.x += radius+1;
365 		}
366 		else{
367 			r.min.y -= radius;
368 			r.max.y += radius+1;
369 		}
370 		oclipr = dst->clipr;
371 		sp = addpt(r.min, d);
372 		dst->clipr = clipr;
373 		memimagedraw(dst, r, src, sp, memopaque, sp, op);
374 		dst->clipr = oclipr;
375 		return;
376 	}
377 
378 /*    Hard: */
379 	/* draw thick line using polygon fill */
380 	icossin2(p1.x-p0.x, p1.y-p0.y, &cos, &sin);
381 	dx = (sin*(2*radius+1))/2;
382 	dy = (cos*(2*radius+1))/2;
383 	pp = pts;
384 	oclipr = dst->clipr;
385 	dst->clipr = clipr;
386 	q.x = ICOSSCALE*p0.x+ICOSSCALE/2-cos/2;
387 	q.y = ICOSSCALE*p0.y+ICOSSCALE/2-sin/2;
388 	switch(end0 & 0x1F){
389 	case Enddisc:
390 		discend(p0, radius, dst, src, d, op);
391 		/* fall through */
392 	case Endsquare:
393 	default:
394 		pp->x = q.x-dx;
395 		pp->y = q.y+dy;
396 		pp++;
397 		pp->x = q.x+dx;
398 		pp->y = q.y-dy;
399 		pp++;
400 		break;
401 	case Endarrow:
402 		arrowend(q, pp, end0, -sin, -cos, radius);
403 		_memfillpolysc(dst, pts, 5, ~0, src, addpt(pts[0], mulpt(d, ICOSSCALE)), 1, 10, 1, op);
404 		pp[1] = pp[4];
405 		pp += 2;
406 	}
407 	q.x = ICOSSCALE*p1.x+ICOSSCALE/2+cos/2;
408 	q.y = ICOSSCALE*p1.y+ICOSSCALE/2+sin/2;
409 	switch(end1 & 0x1F){
410 	case Enddisc:
411 		discend(p1, radius, dst, src, d, op);
412 		/* fall through */
413 	case Endsquare:
414 	default:
415 		pp->x = q.x+dx;
416 		pp->y = q.y-dy;
417 		pp++;
418 		pp->x = q.x-dx;
419 		pp->y = q.y+dy;
420 		pp++;
421 		break;
422 	case Endarrow:
423 		arrowend(q, pp, end1, sin, cos, radius);
424 		_memfillpolysc(dst, pp, 5, ~0, src, addpt(pp[0], mulpt(d, ICOSSCALE)), 1, 10, 1, op);
425 		pp[1] = pp[4];
426 		pp += 2;
427 	}
428 	_memfillpolysc(dst, pts, pp-pts, ~0, src, addpt(pts[0], mulpt(d, ICOSSCALE)), 0, 10, 1, op);
429 	dst->clipr = oclipr;
430 	return;
431 }
432 
433 void
memimageline(Memimage * dst,Point p0,Point p1,int end0,int end1,int radius,Memimage * src,Point sp,int op)434 memimageline(Memimage *dst, Point p0, Point p1, int end0, int end1, int radius, Memimage *src, Point sp, int op)
435 {
436 	_memimageline(dst, p0, p1, end0, end1, radius, src, sp, dst->clipr, op);
437 }
438 
439 /*
440  * Simple-minded conservative code to compute bounding box of line.
441  * Result is probably a little larger than it needs to be.
442  */
443 static
444 void
addbbox(Rectangle * r,Point p)445 addbbox(Rectangle *r, Point p)
446 {
447 	if(r->min.x > p.x)
448 		r->min.x = p.x;
449 	if(r->min.y > p.y)
450 		r->min.y = p.y;
451 	if(r->max.x < p.x+1)
452 		r->max.x = p.x+1;
453 	if(r->max.y < p.y+1)
454 		r->max.y = p.y+1;
455 }
456 
457 int
memlineendsize(int end)458 memlineendsize(int end)
459 {
460 	int x3;
461 
462 	if((end&0x3F) != Endarrow)
463 		return 0;
464 	if(end == Endarrow)
465 		x3 = Arrow3;
466 	else
467 		x3 = (end>>23) & 0x1FF;
468 	return x3;
469 }
470 
471 Rectangle
memlinebbox(Point p0,Point p1,int end0,int end1,int radius)472 memlinebbox(Point p0, Point p1, int end0, int end1, int radius)
473 {
474 	Rectangle r, r1;
475 	int extra;
476 
477 	r.min.x = 10000000;
478 	r.min.y = 10000000;
479 	r.max.x = -10000000;
480 	r.max.y = -10000000;
481 	extra = lmax(memlineendsize(end0), memlineendsize(end1));
482 	r1 = insetrect(canonrect(Rpt(p0, p1)), -(radius+extra));
483 	addbbox(&r, r1.min);
484 	addbbox(&r, r1.max);
485 	return r;
486 }
487