line.c (11026B)
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 /* 14 static 15 int 16 lmin(int a, int b) 17 { 18 if(a < b) 19 return a; 20 return b; 21 } 22 */ 23 24 static 25 int 26 lmax(int a, int b) 27 { 28 if(a > b) 29 return a; 30 return b; 31 } 32 33 #ifdef NOTUSED 34 /* 35 * Rather than line clip, we run the Bresenham loop over the full line, 36 * and clip on each pixel. This is more expensive but means that 37 * lines look the same regardless of how the windowing has tiled them. 38 * For speed, we check for clipping outside the loop and make the 39 * test easy when possible. 40 */ 41 42 static 43 void 44 horline1(Memimage *dst, Point p0, Point p1, int srcval, Rectangle clipr) 45 { 46 int x, y, dy, deltay, deltax, maxx; 47 int dd, easy, e, bpp, m, m0; 48 uchar *d; 49 50 deltax = p1.x - p0.x; 51 deltay = p1.y - p0.y; 52 dd = dst->width*sizeof(u32int); 53 dy = 1; 54 if(deltay < 0){ 55 dd = -dd; 56 deltay = -deltay; 57 dy = -1; 58 } 59 maxx = lmin(p1.x, clipr.max.x-1); 60 bpp = dst->depth; 61 m0 = 0xFF^(0xFF>>bpp); 62 m = m0 >> (p0.x&(7/dst->depth))*bpp; 63 easy = ptinrect(p0, clipr) && ptinrect(p1, clipr); 64 e = 2*deltay - deltax; 65 y = p0.y; 66 d = byteaddr(dst, p0); 67 deltay *= 2; 68 deltax = deltay - 2*deltax; 69 for(x=p0.x; x<=maxx; x++){ 70 if(easy || (clipr.min.x<=x && clipr.min.y<=y && y<clipr.max.y)) 71 *d ^= (*d^srcval) & m; 72 if(e > 0){ 73 y += dy; 74 d += dd; 75 e += deltax; 76 }else 77 e += deltay; 78 d++; 79 m >>= bpp; 80 if(m == 0) 81 m = m0; 82 } 83 } 84 85 static 86 void 87 verline1(Memimage *dst, Point p0, Point p1, int srcval, Rectangle clipr) 88 { 89 int x, y, deltay, deltax, maxy; 90 int easy, e, bpp, m, m0, dd; 91 uchar *d; 92 93 deltax = p1.x - p0.x; 94 deltay = p1.y - p0.y; 95 dd = 1; 96 if(deltax < 0){ 97 dd = -1; 98 deltax = -deltax; 99 } 100 maxy = lmin(p1.y, clipr.max.y-1); 101 bpp = dst->depth; 102 m0 = 0xFF^(0xFF>>bpp); 103 m = m0 >> (p0.x&(7/dst->depth))*bpp; 104 easy = ptinrect(p0, clipr) && ptinrect(p1, clipr); 105 e = 2*deltax - deltay; 106 x = p0.x; 107 d = byteaddr(dst, p0); 108 deltax *= 2; 109 deltay = deltax - 2*deltay; 110 for(y=p0.y; y<=maxy; y++){ 111 if(easy || (clipr.min.y<=y && clipr.min.x<=x && x<clipr.max.x)) 112 *d ^= (*d^srcval) & m; 113 if(e > 0){ 114 x += dd; 115 d += dd; 116 e += deltay; 117 }else 118 e += deltax; 119 d += dst->width*sizeof(u32int); 120 m >>= bpp; 121 if(m == 0) 122 m = m0; 123 } 124 } 125 126 static 127 void 128 horliner(Memimage *dst, Point p0, Point p1, Memimage *src, Point dsrc, Rectangle clipr) 129 { 130 int x, y, sx, sy, deltay, deltax, minx, maxx; 131 int bpp, m, m0; 132 uchar *d, *s; 133 134 deltax = p1.x - p0.x; 135 deltay = p1.y - p0.y; 136 sx = drawreplxy(src->r.min.x, src->r.max.x, p0.x+dsrc.x); 137 minx = lmax(p0.x, clipr.min.x); 138 maxx = lmin(p1.x, clipr.max.x-1); 139 bpp = dst->depth; 140 m0 = 0xFF^(0xFF>>bpp); 141 m = m0 >> (minx&(7/dst->depth))*bpp; 142 for(x=minx; x<=maxx; x++){ 143 y = p0.y + (deltay*(x-p0.x)+deltax/2)/deltax; 144 if(clipr.min.y<=y && y<clipr.max.y){ 145 d = byteaddr(dst, Pt(x, y)); 146 sy = drawreplxy(src->r.min.y, src->r.max.y, y+dsrc.y); 147 s = byteaddr(src, Pt(sx, sy)); 148 *d ^= (*d^*s) & m; 149 } 150 if(++sx >= src->r.max.x) 151 sx = src->r.min.x; 152 m >>= bpp; 153 if(m == 0) 154 m = m0; 155 } 156 } 157 158 static 159 void 160 verliner(Memimage *dst, Point p0, Point p1, Memimage *src, Point dsrc, Rectangle clipr) 161 { 162 int x, y, sx, sy, deltay, deltax, miny, maxy; 163 int bpp, m, m0; 164 uchar *d, *s; 165 166 deltax = p1.x - p0.x; 167 deltay = p1.y - p0.y; 168 sy = drawreplxy(src->r.min.y, src->r.max.y, p0.y+dsrc.y); 169 miny = lmax(p0.y, clipr.min.y); 170 maxy = lmin(p1.y, clipr.max.y-1); 171 bpp = dst->depth; 172 m0 = 0xFF^(0xFF>>bpp); 173 for(y=miny; y<=maxy; y++){ 174 if(deltay == 0) /* degenerate line */ 175 x = p0.x; 176 else 177 x = p0.x + (deltax*(y-p0.y)+deltay/2)/deltay; 178 if(clipr.min.x<=x && x<clipr.max.x){ 179 m = m0 >> (x&(7/dst->depth))*bpp; 180 d = byteaddr(dst, Pt(x, y)); 181 sx = drawreplxy(src->r.min.x, src->r.max.x, x+dsrc.x); 182 s = byteaddr(src, Pt(sx, sy)); 183 *d ^= (*d^*s) & m; 184 } 185 if(++sy >= src->r.max.y) 186 sy = src->r.min.y; 187 } 188 } 189 190 static 191 void 192 horline(Memimage *dst, Point p0, Point p1, Memimage *src, Point dsrc, Rectangle clipr) 193 { 194 int x, y, deltay, deltax, minx, maxx; 195 int bpp, m, m0; 196 uchar *d, *s; 197 198 deltax = p1.x - p0.x; 199 deltay = p1.y - p0.y; 200 minx = lmax(p0.x, clipr.min.x); 201 maxx = lmin(p1.x, clipr.max.x-1); 202 bpp = dst->depth; 203 m0 = 0xFF^(0xFF>>bpp); 204 m = m0 >> (minx&(7/dst->depth))*bpp; 205 for(x=minx; x<=maxx; x++){ 206 y = p0.y + (deltay*(x-p0.x)+deltay/2)/deltax; 207 if(clipr.min.y<=y && y<clipr.max.y){ 208 d = byteaddr(dst, Pt(x, y)); 209 s = byteaddr(src, addpt(dsrc, Pt(x, y))); 210 *d ^= (*d^*s) & m; 211 } 212 m >>= bpp; 213 if(m == 0) 214 m = m0; 215 } 216 } 217 218 static 219 void 220 verline(Memimage *dst, Point p0, Point p1, Memimage *src, Point dsrc, Rectangle clipr) 221 { 222 int x, y, deltay, deltax, miny, maxy; 223 int bpp, m, m0; 224 uchar *d, *s; 225 226 deltax = p1.x - p0.x; 227 deltay = p1.y - p0.y; 228 miny = lmax(p0.y, clipr.min.y); 229 maxy = lmin(p1.y, clipr.max.y-1); 230 bpp = dst->depth; 231 m0 = 0xFF^(0xFF>>bpp); 232 for(y=miny; y<=maxy; y++){ 233 if(deltay == 0) /* degenerate line */ 234 x = p0.x; 235 else 236 x = p0.x + deltax*(y-p0.y)/deltay; 237 if(clipr.min.x<=x && x<clipr.max.x){ 238 m = m0 >> (x&(7/dst->depth))*bpp; 239 d = byteaddr(dst, Pt(x, y)); 240 s = byteaddr(src, addpt(dsrc, Pt(x, y))); 241 *d ^= (*d^*s) & m; 242 } 243 } 244 } 245 #endif /* NOTUSED */ 246 247 static Memimage* 248 membrush(int radius) 249 { 250 static Memimage *brush; 251 static int brushradius; 252 253 if(brush==nil || brushradius!=radius){ 254 freememimage(brush); 255 brush = allocmemimage(Rect(0, 0, 2*radius+1, 2*radius+1), memopaque->chan); 256 if(brush != nil){ 257 memfillcolor(brush, DTransparent); /* zeros */ 258 memellipse(brush, Pt(radius, radius), radius, radius, -1, memopaque, Pt(radius, radius), S); 259 } 260 brushradius = radius; 261 } 262 return brush; 263 } 264 265 static 266 void 267 discend(Point p, int radius, Memimage *dst, Memimage *src, Point dsrc, int op) 268 { 269 Memimage *disc; 270 Rectangle r; 271 272 disc = membrush(radius); 273 if(disc != nil){ 274 r.min.x = p.x - radius; 275 r.min.y = p.y - radius; 276 r.max.x = p.x + radius+1; 277 r.max.y = p.y + radius+1; 278 memdraw(dst, r, src, addpt(r.min, dsrc), disc, Pt(0,0), op); 279 } 280 } 281 282 static 283 void 284 arrowend(Point tip, Point *pp, int end, int sin, int cos, int radius) 285 { 286 int x1, x2, x3; 287 288 /* before rotation */ 289 if(end == Endarrow){ 290 x1 = Arrow1; 291 x2 = Arrow2; 292 x3 = Arrow3; 293 }else{ 294 x1 = (end>>5) & 0x1FF; /* distance along line from end of line to tip */ 295 x2 = (end>>14) & 0x1FF; /* distance along line from barb to tip */ 296 x3 = (end>>23) & 0x1FF; /* distance perpendicular from edge of line to barb */ 297 } 298 299 /* comments follow track of right-facing arrowhead */ 300 pp->x = tip.x+((2*radius+1)*sin/2-x1*cos); /* upper side of shaft */ 301 pp->y = tip.y-((2*radius+1)*cos/2+x1*sin); 302 pp++; 303 pp->x = tip.x+((2*radius+2*x3+1)*sin/2-x2*cos); /* upper barb */ 304 pp->y = tip.y-((2*radius+2*x3+1)*cos/2+x2*sin); 305 pp++; 306 pp->x = tip.x; 307 pp->y = tip.y; 308 pp++; 309 pp->x = tip.x+(-(2*radius+2*x3+1)*sin/2-x2*cos); /* lower barb */ 310 pp->y = tip.y-(-(2*radius+2*x3+1)*cos/2+x2*sin); 311 pp++; 312 pp->x = tip.x+(-(2*radius+1)*sin/2-x1*cos); /* lower side of shaft */ 313 pp->y = tip.y+((2*radius+1)*cos/2-x1*sin); 314 } 315 316 void 317 _memimageline(Memimage *dst, Point p0, Point p1, int end0, int end1, int radius, Memimage *src, Point sp, Rectangle clipr, int op) 318 { 319 /* 320 * BUG: We should really really pick off purely horizontal and purely 321 * vertical lines and handle them separately with calls to memimagedraw 322 * on rectangles. 323 */ 324 325 int hor; 326 int sin, cos, dx, dy, t; 327 Rectangle oclipr, r; 328 Point q, pts[10], *pp, d; 329 330 if(radius < 0) 331 return; 332 if(rectclip(&clipr, dst->r) == 0) 333 return; 334 if(rectclip(&clipr, dst->clipr) == 0) 335 return; 336 d = subpt(sp, p0); 337 if(rectclip(&clipr, rectsubpt(src->clipr, d)) == 0) 338 return; 339 if((src->flags&Frepl)==0 && rectclip(&clipr, rectsubpt(src->r, d))==0) 340 return; 341 /* this means that only verline() handles degenerate lines (p0==p1) */ 342 hor = (abs(p1.x-p0.x) > abs(p1.y-p0.y)); 343 /* 344 * Clipping is a little peculiar. We can't use Sutherland-Cohen 345 * clipping because lines are wide. But this is probably just fine: 346 * we do all math with the original p0 and p1, but clip when deciding 347 * what pixels to draw. This means the layer code can call this routine, 348 * using clipr to define the region being written, and get the same set 349 * of pixels regardless of the dicing. 350 */ 351 if((hor && p0.x>p1.x) || (!hor && p0.y>p1.y)){ 352 q = p0; 353 p0 = p1; 354 p1 = q; 355 t = end0; 356 end0 = end1; 357 end1 = t; 358 } 359 360 if((p0.x == p1.x || p0.y == p1.y) && (end0&0x1F) == Endsquare && (end1&0x1F) == Endsquare){ 361 r.min = p0; 362 r.max = p1; 363 if(p0.x == p1.x){ 364 r.min.x -= radius; 365 r.max.x += radius+1; 366 } 367 else{ 368 r.min.y -= radius; 369 r.max.y += radius+1; 370 } 371 oclipr = dst->clipr; 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(pts[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 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 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 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 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 }