sys/src/libmemdraw/fillpoly.c

   1 #include <u.h>
   2 #include <libc.h>
   3 #include <draw.h>
   4 #include <memdraw.h>
   5 #include <memlayer.h>
   6
   7 typedef struct Seg      Seg;
   8
   9 struct Seg
  10 {
  11         Point   p0;
  12         Point   p1;
  13         long    num;
  14         long    den;
  15         long    dz;
  16         long    dzrem;
  17         long    z;
  18         long    zerr;
  19         long    d;
  20 };
  21
  22 static  void    zsort(Seg **seg, Seg **ep);
  23 static  int     ycompare(void*, void*);
  24 static  int     xcompare(void*, void*);
  25 static  int     zcompare(void*, void*);
  26 static  void    xscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int, int, int, int);
  27 static  void    yscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int, int);
  28
  29 static void
  30 fillcolor(Memimage *dst, int left, int right, int y, Memimage *src, Point p)
  31 {
  32         int srcval;
  33
  34         USED(src);
  35         srcval = p.x;
  36         p.x = left;
  37         p.y = y;
  38         memset(byteaddr(dst, p), srcval, right-left);
  39 }
  40
  41 static void
  42 fillline(Memimage *dst, int left, int right, int y, Memimage *src, Point p, int op)
  43 {
  44         Rectangle r;
  45
  46         r.min.x = left;
  47         r.min.y = y;
  48         r.max.x = right;
  49         r.max.y = y+1;
  50         p.x += left;
  51         p.y += y;
  52         memdraw(dst, r, src, p, memopaque, p, op);
  53 }
  54
  55 static void
  56 fillpoint(Memimage *dst, int x, int y, Memimage *src, Point p, int op)
  57 {
  58         Rectangle r;
  59
  60         r.min.x = x;
  61         r.min.y = y;
  62         r.max.x = x+1;
  63         r.max.y = y+1;
  64         p.x += x;
  65         p.y += y;
  66         memdraw(dst, r, src, p, memopaque, p, op);
  67 }
  68
  69 void
  70 memfillpoly(Memimage *dst, Point *vert, int nvert, int w, Memimage *src, Point sp, int op)
  71 {
  72         _memfillpolysc(dst, vert, nvert, w, src, sp, 0, 0, 0, op);
  73 }
  74
  75 void
  76 _memfillpolysc(Memimage *dst, Point *vert, int nvert, int w, Memimage *src, Point sp, int detail, int fixshift, int clipped, int op)
  77 {
  78         Seg **seg, *segtab;
  79         Point p0;
  80         int i;
  81
  82         if(nvert <= 0)
  83                 return;
  84
  85         seg = malloc((nvert+2)*sizeof(Seg*));
  86         if(seg == nil)
  87                 return;
  88         segtab = malloc((nvert+1)*sizeof(Seg));
  89         if(segtab == nil) {
  90                 free(seg);
  91                 return;
  92         }
  93
  94         sp.x = (sp.x - vert[0].x) >> fixshift;
  95         sp.y = (sp.y - vert[0].y) >> fixshift;
  96         p0 = vert[nvert-1];
  97         if(!fixshift) {
  98                 p0.x <<= 1;
  99                 p0.y <<= 1;
 100         }
 101         for(i = 0; i < nvert; i++) {
 102                 segtab[i].p0 = p0;
 103                 p0 = vert[i];
 104                 if(!fixshift) {
 105                         p0.x <<= 1;
 106                         p0.y <<= 1;
 107                 }
 108                 segtab[i].p1 = p0;
 109                 segtab[i].d = 1;
 110         }
 111         if(!fixshift)
 112                 fixshift = 1;
 113
 114         xscan(dst, seg, segtab, nvert, w, src, sp, detail, fixshift, clipped, op);
 115         if(detail)
 116                 yscan(dst, seg, segtab, nvert, w, src, sp, fixshift, op);
 117
 118         free(seg);
 119         free(segtab);
 120 }
 121
 122 static long
 123 mod(long x, long y)
 124 {
 125         long z;
 126
 127         z = x%y;
 128         if((long)(((ulong)z)^((ulong)y)) > 0 || z == 0)
 129                 return z;
 130         return z + y;
 131 }
 132
 133 static long
 134 sdiv(long x, long y)
 135 {
 136         if((long)(((ulong)x)^((ulong)y)) >= 0 || x == 0)
 137                 return x/y;
 138
 139         return (x+((y>>30)|1))/y-1;
 140 }
 141
 142 static long
 143 smuldivmod(long x, long y, long z, long *mod)
 144 {
 145         vlong vx;
 146
 147         if(x == 0 || y == 0){
 148                 *mod = 0;
 149                 return 0;
 150         }
 151         vx = x;
 152         vx *= y;
 153         *mod = vx % z;
 154         if(*mod < 0)
 155                 *mod += z;      /* z is always >0 */
 156         if((vx < 0) == (z < 0))
 157                 return vx/z;
 158         return -((-vx)/z);
 159 }
 160
 161 static void
 162 xscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int detail, int fixshift, int clipped, int op)
 163 {
 164         long y, maxy, x, x2, xerr, xden, onehalf;
 165         Seg **ep, **next, **p, **q, *s;
 166         long n, i, iy, cnt, ix, ix2, minx, maxx;
 167         Point pt;
 168         void    (*fill)(Memimage*, int, int, int, Memimage*, Point, int);
 169
 170         fill = fillline;
 171 /*
 172  * This can only work on 8-bit destinations, since fillcolor is
 173  * just using memset on sp.x.
 174  *
 175  * I'd rather not even enable it then, since then if the general
 176  * code is too slow, someone will come up with a better improvement
 177  * than this sleazy hack.       -rsc
 178  *
 179         if(clipped && (src->flags&Frepl) && src->depth==8 && Dx(src->r)==1 && Dy(src->r)==1) {
 180                 fill = fillcolor;
 181                 sp.x = membyteval(src);
 182         }
 183  *
 184  */
 185         USED(clipped);
 186
 187
 188         for(i=0, s=segtab, p=seg; i<nseg; i++, s++) {
 189                 *p = s;
 190                 if(s->p0.y == s->p1.y)
 191                         continue;
 192                 if(s->p0.y > s->p1.y) {
 193                         pt = s->p0;
 194                         s->p0 = s->p1;
 195                         s->p1 = pt;
 196                         s->d = -s->d;
 197                 }
 198                 s->num = s->p1.x - s->p0.x;
 199                 s->den = s->p1.y - s->p0.y;
 200                 s->dz = sdiv(s->num, s->den) << fixshift;
 201                 s->dzrem = mod(s->num, s->den) << fixshift;
 202                 s->dz += sdiv(s->dzrem, s->den);
 203                 s->dzrem = mod(s->dzrem, s->den);
 204                 p++;
 205         }
 206         n = p-seg;
 207         if(n == 0)
 208                 return;
 209         *p = 0;
 210         qsort(seg, p-seg , sizeof(Seg*), ycompare);
 211
 212         onehalf = 0;
 213         if(fixshift)
 214                 onehalf = 1 << (fixshift-1);
 215
 216         minx = dst->clipr.min.x;
 217         maxx = dst->clipr.max.x;
 218
 219         y = seg[0]->p0.y;
 220         if(y < (dst->clipr.min.y << fixshift))
 221                 y = dst->clipr.min.y << fixshift;
 222         iy = (y + onehalf) >> fixshift;
 223         y = (iy << fixshift) + onehalf;
 224         maxy = dst->clipr.max.y << fixshift;
 225
 226         ep = next = seg;
 227
 228         while(y<maxy) {
 229                 for(q = p = seg; p < ep; p++) {
 230                         s = *p;
 231                         if(s->p1.y < y)
 232                                 continue;
 233                         s->z += s->dz;
 234                         s->zerr += s->dzrem;
 235                         if(s->zerr >= s->den) {
 236                                 s->z++;
 237                                 s->zerr -= s->den;
 238                                 if(s->zerr < 0 || s->zerr >= s->den)
 239                                         print("bad ratzerr1: %ld den %ld dzrem %ld\n", s->zerr, s->den, s->dzrem);
 240                         }
 241                         *q++ = s;
 242                 }
 243
 244                 for(p = next; *p; p++) {
 245                         s = *p;
 246                         if(s->p0.y >= y)
 247                                 break;
 248                         if(s->p1.y < y)
 249                                 continue;
 250                         s->z = s->p0.x;
 251                         s->z += smuldivmod(y - s->p0.y, s->num, s->den, &s->zerr);
 252                         if(s->zerr < 0 || s->zerr >= s->den)
 253                                 print("bad ratzerr2: %ld den %ld ratdzrem %ld\n", s->zerr, s->den, s->dzrem);
 254                         *q++ = s;
 255                 }
 256                 ep = q;
 257                 next = p;
 258
 259                 if(ep == seg) {
 260                         if(*next == 0)
 261                                 break;
 262                         iy = (next[0]->p0.y + onehalf) >> fixshift;
 263                         y = (iy << fixshift) + onehalf;
 264                         continue;
 265                 }
 266
 267                 zsort(seg, ep);
 268
 269                 for(p = seg; p < ep; p++) {
 270                         cnt = 0;
 271                         x = p[0]->z;
 272                         xerr = p[0]->zerr;
 273                         xden = p[0]->den;
 274                         ix = (x + onehalf) >> fixshift;
 275                         if(ix >= maxx)
 276                                 break;
 277                         if(ix < minx)
 278                                 ix = minx;
 279                         cnt += p[0]->d;
 280                         p++;
 281                         for(;;) {
 282                                 if(p == ep) {
 283                                         print("xscan: fill to infinity");
 284                                         return;
 285                                 }
 286                                 cnt += p[0]->d;
 287                                 if((cnt&wind) == 0)
 288                                         break;
 289                                 p++;
 290                         }
 291                         x2 = p[0]->z;
 292                         ix2 = (x2 + onehalf) >> fixshift;
 293                         if(ix2 <= minx)
 294                                 continue;
 295                         if(ix2 > maxx)
 296                                 ix2 = maxx;
 297                         if(ix == ix2 && detail) {
 298                                 if(xerr*p[0]->den + p[0]->zerr*xden > p[0]->den*xden)
 299                                         x++;
 300                                 ix = (x + x2) >> (fixshift+1);
 301                                 ix2 = ix+1;
 302                         }
 303                         (*fill)(dst, ix, ix2, iy, src, sp, op);
 304                 }
 305                 y += (1<<fixshift);
 306                 iy++;
 307         }
 308 }
 309
 310 static void
 311 yscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int fixshift, int op)
 312 {
 313         long x, maxx, y, y2, yerr, yden, onehalf;
 314         Seg **ep, **next, **p, **q, *s;
 315         int n, i, ix, cnt, iy, iy2, miny, maxy;
 316         Point pt;
 317
 318         for(i=0, s=segtab, p=seg; i<nseg; i++, s++) {
 319                 *p = s;
 320                 if(s->p0.x == s->p1.x)
 321                         continue;
 322                 if(s->p0.x > s->p1.x) {
 323                         pt = s->p0;
 324                         s->p0 = s->p1;
 325                         s->p1 = pt;
 326                         s->d = -s->d;
 327                 }
 328                 s->num = s->p1.y - s->p0.y;
 329                 s->den = s->p1.x - s->p0.x;
 330                 s->dz = sdiv(s->num, s->den) << fixshift;
 331                 s->dzrem = mod(s->num, s->den) << fixshift;
 332                 s->dz += sdiv(s->dzrem, s->den);
 333                 s->dzrem = mod(s->dzrem, s->den);
 334                 p++;
 335         }
 336         n = p-seg;
 337         if(n == 0)
 338                 return;
 339         *p = 0;
 340         qsort(seg, n , sizeof(Seg*), xcompare);
 341
 342         onehalf = 0;
 343         if(fixshift)
 344                 onehalf = 1 << (fixshift-1);
 345
 346         miny = dst->clipr.min.y;
 347         maxy = dst->clipr.max.y;
 348
 349         x = seg[0]->p0.x;
 350         if(x < (dst->clipr.min.x << fixshift))
 351                 x = dst->clipr.min.x << fixshift;
 352         ix = (x + onehalf) >> fixshift;
 353         x = (ix << fixshift) + onehalf;
 354         maxx = dst->clipr.max.x << fixshift;
 355
 356         ep = next = seg;
 357
 358         while(x<maxx) {
 359                 for(q = p = seg; p < ep; p++) {
 360                         s = *p;
 361                         if(s->p1.x < x)
 362                                 continue;
 363                         s->z += s->dz;
 364                         s->zerr += s->dzrem;
 365                         if(s->zerr >= s->den) {
 366                                 s->z++;
 367                                 s->zerr -= s->den;
 368                                 if(s->zerr < 0 || s->zerr >= s->den)
 369                                         print("bad ratzerr1: %ld den %ld ratdzrem %ld\n", s->zerr, s->den, s->dzrem);
 370                         }
 371                         *q++ = s;
 372                 }
 373
 374                 for(p = next; *p; p++) {
 375                         s = *p;
 376                         if(s->p0.x >= x)
 377                                 break;
 378                         if(s->p1.x < x)
 379                                 continue;
 380                         s->z = s->p0.y;
 381                         s->z += smuldivmod(x - s->p0.x, s->num, s->den, &s->zerr);
 382                         if(s->zerr < 0 || s->zerr >= s->den)
 383                                 print("bad ratzerr2: %ld den %ld ratdzrem %ld\n", s->zerr, s->den, s->dzrem);
 384                         *q++ = s;
 385                 }
 386                 ep = q;
 387                 next = p;
 388
 389                 if(ep == seg) {
 390                         if(*next == 0)
 391                                 break;
 392                         ix = (next[0]->p0.x + onehalf) >> fixshift;
 393                         x = (ix << fixshift) + onehalf;
 394                         continue;
 395                 }
 396
 397                 zsort(seg, ep);
 398
 399                 for(p = seg; p < ep; p++) {
 400                         cnt = 0;
 401                         y = p[0]->z;
 402                         yerr = p[0]->zerr;
 403                         yden = p[0]->den;
 404                         iy = (y + onehalf) >> fixshift;
 405                         if(iy >= maxy)
 406                                 break;
 407                         if(iy < miny)
 408                                 iy = miny;
 409                         cnt += p[0]->d;
 410                         p++;
 411                         for(;;) {
 412                                 if(p == ep) {
 413                                         print("yscan: fill to infinity");
 414                                         return;
 415                                 }
 416                                 cnt += p[0]->d;
 417                                 if((cnt&wind) == 0)
 418                                         break;
 419                                 p++;
 420                         }
 421                         y2 = p[0]->z;
 422                         iy2 = (y2 + onehalf) >> fixshift;
 423                         if(iy2 <= miny)
 424                                 continue;
 425                         if(iy2 > maxy)
 426                                 iy2 = maxy;
 427                         if(iy == iy2) {
 428                                 if(yerr*p[0]->den + p[0]->zerr*yden > p[0]->den*yden)
 429                                         y++;
 430                                 iy = (y + y2) >> (fixshift+1);
 431                                 fillpoint(dst, ix, iy, src, sp, op);
 432                         }
 433                 }
 434                 x += (1<<fixshift);
 435                 ix++;
 436         }
 437 }
 438
 439 static void
 440 zsort(Seg **seg, Seg **ep)
 441 {
 442         int done;
 443         Seg **q, **p, *s;
 444
 445         if(ep-seg < 20) {
 446                 /* bubble sort by z - they should be almost sorted already */
 447                 q = ep;
 448                 do {
 449                         done = 1;
 450                         q--;
 451                         for(p = seg; p < q; p++) {
 452                                 if(p[0]->z > p[1]->z) {
 453                                         s = p[0];
 454                                         p[0] = p[1];
 455                                         p[1] = s;
 456                                         done = 0;
 457                                 }
 458                         }
 459                 } while(!done);
 460         } else {
 461                 q = ep-1;
 462                 for(p = seg; p < q; p++) {
 463                         if(p[0]->z > p[1]->z) {
 464                                 qsort(seg, ep-seg, sizeof(Seg*), zcompare);
 465                                 break;
 466                         }
 467                 }
 468         }
 469 }
 470
 471 static int
 472 ycompare(void *a, void *b)
 473 {
 474         Seg **s0, **s1;
 475         long y0, y1;
 476
 477         s0 = a;
 478         s1 = b;
 479         y0 = (*s0)->p0.y;
 480         y1 = (*s1)->p0.y;
 481
 482         if(y0 < y1)
 483                 return -1;
 484         if(y0 == y1)
 485                 return 0;
 486         return 1;
 487 }
 488
 489 static int
 490 xcompare(void *a, void *b)
 491 {
 492         Seg **s0, **s1;
 493         long x0, x1;
 494
 495         s0 = a;
 496         s1 = b;
 497         x0 = (*s0)->p0.x;
 498         x1 = (*s1)->p0.x;
 499
 500         if(x0 < x1)
 501                 return -1;
 502         if(x0 == x1)
 503                 return 0;
 504         return 1;
 505 }
 506
 507 static int
 508 zcompare(void *a, void *b)
 509 {
 510         Seg **s0, **s1;
 511         long z0, z1;
 512
 513         s0 = a;
 514         s1 = b;
 515         z0 = (*s0)->z;
 516         z1 = (*s1)->z;
 517
 518         if(z0 < z1)
 519                 return -1;
 520         if(z0 == z1)
 521                 return 0;
 522         return 1;
 523 }