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