sys/src/libmemdraw/line.c

   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
  16 lmin(int a, int b)
  17 {
  18         if(a < b)
  19                 return a;
  20         return b;
  21 }
  22
  23 static
  24 int
  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
  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
  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
 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
 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
 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
 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*
 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
 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
 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
 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
 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 }