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