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