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 } 524