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