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