1 /* vsort.c 1.11 84/05/29 2 * 3 * Sorts and shuffles ditroff output for versatec wide printer. It 4 * puts pages side-by-side on the output, and fits as many as it can 5 * on one horizontal span. The versatec driver sees only pages of 6 * full width, not the individual pages. Output is sorted vertically 7 * and bands are created NLINES pixels high. Any object that has 8 * ANY part of it in a band is put on that band. 9 */ 10 11 12 #include <stdio.h> 13 #include <ctype.h> 14 #include <math.h> 15 16 17 /* #define DEBUGABLE /* compile-time flag for debugging */ 18 #define FATAL 1 19 #define NVLIST 3000 /* size of list of vertical spans */ 20 #define OBUFSIZ 250000 /* size of character buffer before sorting */ 21 #define SLOP 1000 /* extra bit of buffer to allow for passing OBUFSIZ */ 22 #define MAXVECT 200 /* maximum number of points (vectors) in a polygon */ 23 24 #ifndef FONTDIR 25 #define FONTDIR "/usr/lib/font" 26 #endif 27 #define INCH 200 /* assumed resolution of the printer (dots/inch) */ 28 #define POINT 72 /* number of points per inch */ 29 #define WIDTH 7040 /* number of pixels across the page */ 30 #define HALF (INCH/2) 31 #ifndef DEBUGABLE 32 #define BAND 1 /* length of each band (or defined below) */ 33 #endif 34 #define NLINES (int)(BAND * INCH) /* number of pixels in each band */ 35 36 #define hgoto(n) if((hpos = leftmarg + n) > maxh) maxh = hpos 37 #define hmot(n) if((hpos += n) > maxh) maxh = hpos 38 #define vmot(n) vpos += (n) 39 #define vgoto(n) vpos = (n) 40 41 42 #ifdef DEBUGABLE 43 int dbg = 0; /* debug flag != 0 means do debug output */ 44 float BAND = 1.0; 45 #endif 46 47 48 int size = 10; /* current size (points) */ 49 int up = 0; /* number of pixels that the current size pushes up */ 50 int down = 0; /* # of pixels that the current size will hang down */ 51 int font = 1; /* current font */ 52 int stip = 1; /* current stipple */ 53 char * fontdir = FONTDIR; /* place to find DESC.out file */ 54 int thick = 3; /* line thickness */ 55 int style = -1; /* line style bit-mask */ 56 int hpos = 0; /* horizontal position to be at next (left = 0) */ 57 int vpos = 0; /* current vertical position (down positive) */ 58 59 int maxh = 0; /* farthest right we've gone on the current span */ 60 int leftmarg= 0; /* current page offset */ 61 int spanno = 0; /* current span number for driver in 'p#' commands */ 62 int pageno = 0; /* number of pages spread across a physical page */ 63 64 65 struct vlist { 66 unsigned short v; /* vertical position of this spread */ 67 unsigned short h; /* horizontal position */ 68 unsigned short t; /* line thickness */ 69 short st; /* style mask */ 70 unsigned short u; /* upper extent of height */ 71 unsigned short d; /* depth of height */ 72 unsigned short s; /* point size */ 73 unsigned char f; /* font number */ 74 unsigned char l; /* stipple number */ 75 char *p; /* text pointer to this spread */ 76 }; 77 78 struct vlist vlist[NVLIST + 1]; 79 struct vlist *vlp; /* current spread being added to */ 80 int nvlist = 1; /* number of spreads in list */ 81 int obufsiz = OBUFSIZ; 82 char obuf[OBUFSIZ + SLOP]; 83 char *op = obuf; /* pointer to current spot in buffer */ 84 85 86 main(argc, argv) 87 int argc; 88 char *argv[]; 89 { 90 FILE *fp; 91 double atof(); 92 93 94 vlp = &vlist[0]; /* initialize spread pointer */ 95 vlp->p = op; 96 vlp->v = vlp->d = vlp->u = vlp->h = 0; 97 vlp->s = size; 98 vlp->f = font; 99 vlp->l = stip; 100 vlp->st = style; 101 vlp->t = thick; 102 103 while (argc > 1 && **++argv == '-') { 104 switch ((*argv)[1]) { 105 case 'f': 106 fontdir = &(*argv)[2]; 107 break; 108 #ifdef DEBUGABLE 109 case 'B': 110 BAND = atof(&(*argv)[2]); 111 break; 112 case 'd': 113 dbg = atoi(&(*argv)[2]); 114 if (!dbg) dbg = 1; 115 break; 116 117 case 's': 118 if((obufsiz = atoi(&(*argv)[2])) > OBUFSIZ) 119 obufsiz = OBUFSIZ; 120 break; 121 #endif 122 } 123 argc--; 124 } 125 126 if (argc <= 1) 127 conv(stdin); 128 else 129 while (--argc > 0) { 130 if ((fp = fopen(*argv, "r")) == NULL) 131 error(FATAL, "can't open %s", *argv); 132 conv(fp); 133 fclose(fp); 134 } 135 done(); 136 } 137 138 /* read number from input: copy to output */ 139 int getnumber (fp) 140 register FILE *fp; 141 { 142 register int k; 143 register char c; 144 145 while (isspace(c = getc(fp))) 146 ; 147 k = 0; 148 if (c == '-') { 149 c = getc(fp); 150 do { 151 k = 10 * k - ((*op++ = c) - '0'); 152 } while (isdigit(c = getc(fp))); 153 } else { 154 do { 155 k = 10 * k + (*op++ = c) - '0'; 156 } while (isdigit(c = getc(fp))); 157 } 158 ungetc(c, fp); 159 return (k); 160 } 161 162 /* read number from input: do _N_O_T copy to output */ 163 int ngetnumber (fp) 164 register FILE *fp; 165 { 166 register int k; 167 register char c; 168 169 while (isspace(c = getc(fp))) 170 ; 171 k = 0; 172 if (c == '-') { 173 c = getc(fp); 174 do { 175 k = 10 * k - (c - '0'); 176 } while (isdigit(c = getc(fp))); 177 } else { 178 do { 179 k = 10 * k + c - '0'; 180 } while (isdigit(c = getc(fp))); 181 } 182 ungetc(c, fp); 183 return (k); 184 } 185 186 187 conv(fp) 188 register FILE *fp; 189 { 190 register int c; 191 int m, n, m1, n1; 192 193 while ((c = getc(fp)) != EOF) { 194 #ifdef DEBUGABLE 195 if (dbg > 2) fprintf(stderr, "%c i=%d V=%d\n", c, op-obuf, vpos); 196 #endif 197 if (op > obuf + obufsiz) { 198 error(!FATAL, "buffer overflow %d.", op - (obuf + obufsiz)); 199 oflush(); 200 } 201 switch (c) { 202 case '\0': /* filter out noise */ 203 break; 204 case '\n': /* let text input through */ 205 case '\t': 206 case ' ': 207 *op++ = c; 208 break; 209 case '{': /* push down current environment */ 210 *op++ = c; 211 t_push(); 212 break; 213 case '}': /* pop up last environment */ 214 *op++ = c; 215 t_pop(); 216 break; 217 case '0': case '1': case '2': case '3': case '4': 218 case '5': case '6': case '7': case '8': case '9': 219 /* two motion digits plus a character */ 220 setlimit(vpos - up, vpos + down); 221 *op++ = c; 222 hmot((c-'0') * 10 + (*op++ = getc(fp)) - '0'); 223 *op++ = getc(fp); 224 break; 225 case 'c': /* single ascii character */ 226 setlimit(vpos - up, vpos + down); 227 *op++ = c; 228 *op++ = getc(fp); 229 break; 230 case 'C': /* white-space terminated funny character */ 231 setlimit(vpos - up, vpos + down); 232 *op++ = c; 233 do 234 *op++ = c = getc(fp); 235 while (c != EOF && !isspace(c)); 236 break; 237 case 't': /* straight text */ 238 setlimit(vpos - up, vpos + down); 239 *op++ = c; 240 fgets(op, SLOP, fp); 241 op += strlen(op); 242 break; 243 case 'D': /* draw function */ 244 switch (c = getc(fp)) { 245 case 's': /* "style" */ 246 sprintf(op, "Ds "); 247 op += 3; 248 style = getnumber(fp); 249 break; 250 251 case 't': /* thickness */ 252 sprintf(op, "Dt "); 253 op += 3; 254 thick = getnumber(fp); 255 break; 256 257 case 'l': /* draw a line */ 258 n = ngetnumber(fp); 259 m = ngetnumber(fp); 260 if (m < 0) { 261 setlimit(vpos+m-thick/2, vpos+thick/2); 262 } else { 263 setlimit(vpos-(1+thick/2),vpos+1+m+thick/2); 264 } 265 sprintf(op, "Dl %d %d", n, m); 266 op += strlen(op); 267 hmot(n); 268 vmot(m); 269 break; 270 271 case 'e': /* ellipse */ 272 n = ngetnumber(fp); 273 m = ngetnumber(fp); 274 setlimit(vpos-(m+thick)/2, vpos+(m+thick)/2); 275 sprintf(op, "De %d %d", n, m); 276 op += strlen(op); 277 hmot(n); 278 break; 279 280 case 'c': /* circle */ 281 n = ngetnumber(fp); 282 setlimit(vpos-(n+thick)/2, vpos+(n+thick)/2); 283 sprintf(op, "Dc %d", n); 284 op += strlen(op); 285 hmot(n); 286 break; 287 288 case 'a': /* arc */ 289 n = getnumber(fp); 290 m = getnumber(fp); 291 n1 = getnumber(fp); 292 m1 = getnumber(fp); 293 arcbounds(n, m, n1, m1); 294 sprintf(op, "Da %d %d %d %d", n, m, n1, m1); 295 op += strlen(op); 296 hmot(n + n1); 297 vmot(m + m1); 298 break; 299 300 case 'P': 301 case 'p': 302 { 303 register int nvect; 304 int member; 305 int border; 306 int x[MAXVECT]; 307 int y[MAXVECT]; 308 309 310 border = (c == 'p'); /* type of polygon */ 311 member = ngetnumber(fp);/* and member number */ 312 313 nvect = 1; /* starting point for */ 314 x[1] = hpos; /* points on polygon */ 315 y[1] = vpos; 316 m = n = vpos; /* = max/min vertical */ 317 /* position for curve */ 318 { 319 register int h; 320 register int v; 321 322 323 h = hpos; /* calculate max and minimum */ 324 v = vpos; /* vertical position */ 325 /* and get points */ 326 do { 327 h += ngetnumber(fp); 328 v += ngetnumber(fp); 329 330 if (v < n) n = v; 331 else if (v > m) m = v; 332 333 if (nvect < (MAXVECT-1))/* keep the */ 334 nvect++; /* points in */ 335 x[nvect] = h; /* bounds */ 336 y[nvect] = v; /* of arrays */ 337 c = getc(fp); 338 } while (c != '\n' && c != EOF); 339 } 340 if (border) { /* output border as a */ 341 register int *x1; /* bunch of lines */ 342 register int *x2; /* instead of having */ 343 register int *y1; /* the filter do it */ 344 register int *y2; 345 register int extra = thick/2; 346 347 x1 = &(x[0]); /* x1, y1, x2, y2 are */ 348 x2 = &(x[1]); /* for indexing along */ 349 y1 = &(y[0]); /* coordinate arrays */ 350 y2 = &(y[1]); 351 for (border = 0; ++border < nvect; ) { 352 if (*++y1 > *++y2) { 353 setlimit(*y2-extra, vpos+extra); 354 } else { 355 setlimit(vpos-(1+extra),*y2+1+extra); 356 /* the extra 1's are to force */ 357 /* setlimit to know this is a */ 358 /* real entry (making sure it */ 359 /* doesn't get vpos as limit */ 360 } 361 sprintf(op, "Dl %d %d\n", 362 c = *++x2 - *++x1, *y2 - *y1); 363 op += strlen(op); 364 hmot(c); /* update vpos for */ 365 vgoto(*y2); /* the setlimit call */ 366 } 367 } else { 368 register int *x1; /* x1, x2, are for */ 369 register int *x2; /* indexing points */ 370 register int i; /* random int */ 371 372 x1 = &(x[0]); 373 x2 = &(x[1]); 374 for (i = 0; ++i < nvect; ) { 375 hmot(*++x2 - *++x1); 376 } 377 vgoto(y[nvect]); 378 sprintf(op, "H%dV%d", hpos, vpos); 379 op += strlen(op); 380 } 381 if (member) { 382 polygon(member, nvect, x, y, m, n); 383 } 384 } 385 break; 386 387 case '~': /* wiggly line */ 388 case 'g': /* gremlin curve */ 389 startspan(vpos); /* always put curve */ 390 sprintf(op, "D%c ", c); /* on its own span */ 391 op += 3; 392 393 m = n = vpos; /* = max/min vertical */ 394 do { /* position for curve */ 395 hpos += getnumber(fp); 396 *op++ = ' '; 397 vpos += getnumber(fp); 398 *op++ = ' '; 399 400 if (vpos < n) n = vpos; 401 else if (vpos > m) m = vpos; 402 403 c = getc(fp); 404 } while (c != '\n' && c != EOF); 405 406 vlp->u = n < 0 ? 0 : n; 407 vlp->d = m; 408 *op++ = '\n'; 409 startspan(vpos); 410 break; 411 412 default: 413 error(FATAL,"unknown drawing command %c", c); 414 break; 415 } 416 break; 417 case 's': 418 *op++ = c; 419 size = getnumber(fp); 420 up = ((size + 1)*INCH) / POINT; /* ROUGH estimate */ 421 down = up / 3; /* of max up/down */ 422 break; 423 case 'f': 424 *op++ = c; 425 font = getnumber(fp); 426 break; 427 case 'i': 428 *op++ = c; 429 stip = getnumber(fp); 430 break; 431 case 'H': /* absolute horizontal motion */ 432 hgoto(ngetnumber(fp)); 433 sprintf(op, "H%d", hpos); 434 op += strlen(op); /* reposition by page offset */ 435 break; 436 case 'h': /* relative horizontal motion */ 437 *op++ = c; 438 hmot(getnumber(fp)); 439 break; 440 case 'w': /* useless */ 441 break; 442 case 'V': /* absolute vertical motion */ 443 *op++ = c; 444 vgoto(getnumber(fp)); 445 break; 446 case 'v': 447 *op++ = c; 448 vmot(getnumber(fp)); 449 break; 450 case 'p': /* new page */ 451 t_page(ngetnumber(fp)); 452 vpos = 0; 453 break; 454 case 'n': /* end of line */ 455 hpos = leftmarg; 456 *op++ = c; 457 do 458 *op++ = c = getc(fp); 459 while (c != '\n' && c != EOF); 460 break; 461 case '#': /* comment */ 462 do 463 c = getc(fp); 464 while (c != '\n' && c != EOF); 465 break; 466 case 'x': /* device control */ 467 startspan(vpos); 468 *op++ = c; 469 do 470 *op++ = c = getc(fp); 471 while (c != '\n' && c != EOF); 472 break; 473 default: 474 error(!FATAL, "unknown input character %o %c", c, c); 475 done(); 476 } 477 } 478 } 479 480 481 /*----------------------------------------------------------------------------* 482 | Routine: setlimit 483 | 484 | Results: using "newup" and "newdown" decide when to start a new span. 485 | maximum rise and/or fall of a vertical extent are saved. 486 | 487 | Side Efct: may start new span. 488 *----------------------------------------------------------------------------*/ 489 490 #define diffspan(x,y) ((x)/NLINES != (y)/NLINES) 491 492 setlimit(newup, newdown) 493 register int newup; 494 register int newdown; 495 { 496 register int currup = vlp->u; 497 register int currdown = vlp->d; 498 499 if (newup < 0) newup = 0; /* don't go back beyond start of page */ 500 if (newdown < 0) newdown = 0; 501 502 if (diffspan(currup, currdown)) { /* now spans > one band */ 503 if (diffspan(newup, currup) || diffspan(newdown, currdown)) { 504 startspan (vpos); 505 vlp->u = newup; 506 vlp->d = newdown; 507 } else { 508 if (newup < currup) vlp->u = newup; 509 if (newdown > currdown) vlp->d = newdown; 510 } 511 } else { 512 if (newup < currup) { /* goes farther up than before */ 513 if (currup == vlp->v) { /* is new span, just set "up" */ 514 vlp->u = newup; 515 } else { 516 if (diffspan(newup, currup)) { /* goes up farther */ 517 startspan(vpos); /* than previously */ 518 vlp->u = newup; /* AND to a higher */ 519 vlp->d = newdown; /* band. */ 520 return; 521 } else { 522 vlp->u = newup; 523 } 524 } 525 } 526 if (newdown > currdown) { 527 if (currdown == vlp->v) { 528 vlp->d = newdown; 529 return; 530 } else { 531 if (diffspan(newdown, currdown)) { 532 startspan(vpos); 533 vlp->u = newup; 534 vlp->d = newdown; 535 return; 536 } else { 537 vlp->d = newdown; 538 } 539 } 540 } 541 } 542 } 543 544 545 /*----------------------------------------------------------------------------* 546 | Routine: arcbounds (h, v, h1, v1) 547 | 548 | Results: using the horizontal positions of the starting and ending 549 | points relative to the center and vertically relative to 550 | each other, arcbounds calculates the upper and lower extent 551 | of the arc which is one of: starting point, ending point 552 | or center + rad for bottom, and center - rad for top. 553 | 554 | Side Efct: calls setlimit(up, down) to save the extent information. 555 *----------------------------------------------------------------------------*/ 556 557 arcbounds(h, v, h1, v1) 558 int h, v, h1, v1; 559 { 560 register unsigned rad = (int)(sqrt((double)(h*h + v*v)) + 0.5); 561 register int i = ((h >= 0) << 2) | ((h1 < 0) << 1) | ((v + v1) < 0); 562 563 /* i is a set of flags for the points being on the */ 564 /* left of the center point, and which is higher */ 565 566 v1 += vpos + v; /* v1 is vertical position of ending point */ 567 /* test relative positions for maximums */ 568 setlimit( /* and set the up/down of the arc */ 569 ((((i&3)==1) ? v1 : (((i&5)==4) ? vpos : vpos+v-rad)) - thick/2), 570 ((((i&3)==2) ? v1 : (((i&5)==1) ? vpos : vpos+v+rad)) + thick/2)); 571 } 572 573 574 oflush() /* sort, then dump out contents of obuf */ 575 { 576 register struct vlist *vp; 577 register int notdone; 578 register int topv; 579 register int botv; 580 register int i; 581 register char *p; 582 583 #ifdef DEBUGABLE 584 if (dbg) fprintf(stderr, "into oflush, V=%d\n", vpos); 585 #endif 586 if (op == obuf) 587 return; 588 *op = 0; 589 590 topv = 0; 591 botv = NLINES - 1; 592 do { 593 notdone = 0; 594 vp = vlist; 595 #ifdef DEBUGABLE 596 if (dbg) fprintf(stderr, "topv=%d, botv=%d\n", topv, botv); 597 #endif 598 for (i = 0; i < nvlist; i++, vp++) { 599 #ifdef DEBUGABLE 600 if(dbg>1)fprintf(stderr,"u=%d, d=%d,%.60s\n",vp->u,vp->d,vp->p); 601 #endif 602 if (vp->u <= botv && vp->d >= topv) { 603 printf("H%dV%ds%df%d\ni%d\nDs%d\nDt%d\n%s", 604 vp->h,vp->v,vp->s,vp->f,vp->l,vp->st,vp->t,vp->p); 605 } 606 notdone |= vp->d > botv; /* not done if there's still */ 607 } /* something to put lower */ 608 if (notdone) putchar('P'); /* mark the end of the spread */ 609 topv += NLINES; /* unless it's the last one */ 610 botv += NLINES; 611 } while (notdone); 612 613 fflush(stdout); 614 vlp = vlist; 615 vlp->p = op = obuf; 616 vlp->h = hpos; 617 vlp->v = vpos; 618 vlp->u = vpos; 619 vlp->d = vpos; 620 vlp->s = size; 621 vlp->f = font; 622 vlp->l = stip; 623 vlp->st = style; 624 vlp->t = thick; 625 *op = 0; 626 nvlist = 1; 627 } 628 629 630 done() 631 { 632 oflush(); 633 exit(0); 634 } 635 636 error(f, s, a1, a2, a3, a4, a5, a6, a7) { 637 fprintf(stderr, "vsort: "); 638 fprintf(stderr, s, a1, a2, a3, a4, a5, a6, a7); 639 fprintf(stderr, "\n"); 640 if (f) 641 done(); 642 } 643 644 #define MAXSTATE 5 645 646 struct state { 647 int ssize; 648 int sfont; 649 int shpos; 650 int svpos; 651 }; 652 struct state state[MAXSTATE]; 653 struct state *statep = state; 654 655 t_push() /* begin a new block */ 656 { 657 statep->ssize = size; 658 statep->sfont = font; 659 statep->shpos = hpos; 660 statep->svpos = vpos; 661 hpos = vpos = 0; 662 if (statep++ >= state+MAXSTATE) 663 error(FATAL, "{ nested too deep"); 664 hpos = vpos = 0; 665 } 666 667 t_pop() /* pop to previous state */ 668 { 669 if (--statep < state) 670 error(FATAL, "extra }"); 671 size = statep->ssize; 672 font = statep->sfont; 673 hpos = statep->shpos; 674 vpos = statep->svpos; 675 } 676 677 678 /*----------------------------------------------------------------------------* 679 | Routine: t_page 680 | 681 | Results: new Margins are calculated for putting pages side-by-side. 682 | If no more pages can fit across the paper (WIDTH wide) 683 | a real page end is done and the currrent page is output. 684 | 685 | Side Efct: oflush is called on a REAL page boundary. 686 *----------------------------------------------------------------------------*/ 687 688 t_page(n) 689 int n; 690 { 691 static int first = 1; /* flag to catch the 1st time through */ 692 693 /* if we're near the edge, we'll go over on */ 694 if (leftmarg + 2*(pageno ? leftmarg/pageno : 0) > WIDTH /* this page, */ 695 || maxh > WIDTH - INCH || first) { /* or this is the first page */ 696 oflush(); 697 printf("p%d\n", spanno++); /* make it a REAL page-break */ 698 first = pageno = leftmarg = maxh = 0; 699 } else { /* x = last page's width (in half-inches) */ 700 register int x = (maxh - leftmarg + (HALF - 1)) / HALF; 701 702 if (x > 11 && x <= 17) 703 leftmarg += (8 * INCH) + HALF; /* if close to 8.5" */ 704 else /* then make it so */ 705 leftmarg = ((maxh + HALF) / HALF) * HALF; /* else set it to the */ 706 pageno++; /* nearest half-inch */ 707 } 708 } 709 710 711 startspan(n) 712 register int n; 713 { 714 *op++ = 0; 715 if (nvlist >= NVLIST) { 716 #ifdef DEBUGABLE 717 error(!FATAL, "ran out of vlist"); 718 #endif 719 oflush(); 720 } 721 vlp++; 722 vlp->p = op; 723 vlp->v = n; 724 vlp->d = n; 725 vlp->u = n; 726 vlp->h = hpos; 727 vlp->s = size; 728 vlp->f = font; 729 vlp->l = stip; 730 vlp->st = style; 731 vlp->t = thick; 732 nvlist++; 733 } 734 735 736 #define MAXX 0x7fff 737 #define MINX 0x8000 738 739 typedef struct poly { 740 struct poly *next; /* doublely-linked lists of vectors */ 741 struct poly *prev; 742 int param; /* bressenham line algorithm parameter */ 743 short dx; /* delta-x for calculating line */ 744 short dy; /* delta-y for calculating line */ 745 short currx; /* current x in this vector */ 746 short endy; /* where vector ends */ 747 } polyvector; 748 749 750 /*----------------------------------------------------------------------------* 751 | Routine: polygon ( member, num_vectors, x_coor, y_coor, maxy, miny ) 752 | 753 | Results: outputs commands to draw a polygon starting at (x[1], y[1]) 754 | going through each of (x_coordinates, y_coordinates), and 755 | filled with "member" stipple pattern. 756 | 757 | A scan-line algorithm is simulated and pieces of the 758 | polygon are put out that fit on bands of the versatec 759 | output filter. 760 | 761 | The format of the polygons put out are: 762 | 'Dp member num miny maxy [p dx dy curx endy]' 763 | where "num" is the number of [..] entries in that 764 | section of the polygon. 765 *----------------------------------------------------------------------------*/ 766 767 polygon(member, nvect, x, y, maxy, miny) 768 int member; 769 int nvect; 770 int x[]; 771 int y[]; 772 int maxy; 773 int miny; 774 { 775 int nexty; /* at what x value the next vector starts */ 776 register int active; /* number of vectors in active list */ 777 int firsttime; /* force out a polgon the first time through */ 778 polyvector *activehead; /* doing fill, is active edge list */ 779 polyvector *waitinghead; /* edges waiting to be active */ 780 register polyvector *vectptr; /* random vector */ 781 register int i; /* random register */ 782 783 784 /* allocate space for raster-fill algorithm*/ 785 vectptr = (polyvector *) malloc(sizeof(polyvector) * (nvect + 4)); 786 if (vectptr == (polyvector *) NULL) { 787 error(!FATAL, "unable to allocate space for polygon"); 788 return; 789 } 790 791 waitinghead = vectptr; 792 vectptr->param = miny - 1; 793 (vectptr++)->prev = NULL; /* put dummy entry at start */ 794 waitinghead->next = vectptr; 795 vectptr->prev = waitinghead; 796 i = 1; /* starting point of coords */ 797 if (y[1] != y[nvect] || x[1] != x[nvect]) { 798 y[0] = y[nvect]; /* close polygon if it's not */ 799 x[0] = x[nvect]; 800 i = 0; 801 } 802 active = 0; 803 while (i < nvect) { /* set up the vectors */ 804 register int j; /* indexes to work off of */ 805 register int k; 806 807 j = i; /* j "points" to the higher (lesser) point */ 808 k = ++i; 809 if (y[j] == y[k]) /* ignore horizontal lines */ 810 continue; 811 812 if (y[j] > y[k]) { 813 j++; 814 k--; 815 } 816 active++; 817 vectptr->next = vectptr + 1; 818 vectptr->param = y[j]; /* starting point of vector */ 819 vectptr->dx = x[k] - x[j]; /* line-calculating parameters */ 820 vectptr->dy = y[k] - y[j]; 821 vectptr->currx = x[j]; /* starting point */ 822 (vectptr++)->endy = y[k]; /* ending point */ 823 vectptr->prev = vectptr - 1; 824 } 825 /* if no useable vectors, quit */ 826 if (active < 2) 827 goto leavepoly; 828 829 vectptr->param = maxy + 1; /* dummy entry at end, too */ 830 vectptr->next = NULL; 831 832 activehead = ++vectptr; /* two dummy entries for active list */ 833 vectptr->currx = MINX; /* head */ 834 vectptr->endy = maxy + 1; 835 vectptr->param = vectptr->dx = vectptr->dy = 0; 836 activehead->next = ++vectptr; 837 activehead->prev = vectptr; 838 vectptr->prev = activehead; /* tail */ 839 vectptr->next = activehead; 840 vectptr->currx = MAXX; 841 vectptr->endy = maxy + 1; 842 vectptr->param = vectptr->dx = vectptr->dy = 0; 843 844 /* if there's no need to break the */ 845 /* polygon into pieces, don't bother */ 846 if (diffspan(miny, maxy)) { 847 active = 0; /* will keep track of # of vectors */ 848 firsttime = 1; 849 } else { /* in the active list */ 850 startspan(miny); 851 sprintf(op, "Dq %d %d %d %d", member, active, miny, maxy); 852 op += strlen(op); 853 for (vectptr = waitinghead->next; active--; vectptr++) { 854 sprintf(op, " %d %d %d %d %d", 855 vectptr->param, vectptr->dx, vectptr->dy, 856 vectptr->currx, vectptr->endy); 857 op += strlen(op); 858 } 859 *(op++) = '\n'; 860 goto leavepoly; 861 } 862 /* main loop -- gets vectors off the waiting list, */ 863 /* then displays spans while updating the vectors in */ 864 /* the active list */ 865 while (miny <= maxy) { 866 i = maxy + 1; /* this is the NEXT time to get a new vector */ 867 for (vectptr = waitinghead->next; vectptr != NULL; ) { 868 if (miny == vectptr->param) { 869 /* the entry in waiting list (vectptr) is */ 870 /* ready to go into active list. Need to */ 871 /* convert some vector stuff and sort the */ 872 /* entry into the list. */ 873 register polyvector *p; /* random vector pointers */ 874 register polyvector *v; 875 876 /* convert this */ 877 if (vectptr->dx < 0) /* entry to active */ 878 vectptr->param = -((vectptr->dx >> 1) + (vectptr->dy >> 1)); 879 else 880 vectptr->param = (vectptr->dx >> 1) - (vectptr->dy >> 1); 881 882 p = vectptr; /* remove from the */ 883 vectptr = vectptr->next; /* waiting list */ 884 vectptr->prev = p->prev; 885 p->prev->next = vectptr; 886 /* find where it goes */ 887 /* in the active list */ 888 /* (sorted smallest first) */ 889 for (v = activehead->next; v->currx < p->currx; v = v->next) 890 ; 891 p->next = v; /* insert into active list */ 892 p->prev = v->prev; /* before the one it stopped on */ 893 v->prev = p; 894 p->prev->next = p; 895 active++; 896 } else { 897 if (i > vectptr->param) { 898 i = vectptr->param; 899 } 900 vectptr = vectptr->next; 901 } 902 } 903 nexty = i; 904 905 /* print the polygon while there */ 906 /* are no more vectors to add */ 907 while (miny < nexty) { 908 /* remove any finished vectors */ 909 vectptr = activehead->next; 910 do { 911 if (vectptr->endy <= miny) { 912 vectptr->prev->next = vectptr->next; 913 vectptr->next->prev = vectptr->prev; 914 active--; 915 } 916 } while ((vectptr = vectptr->next) != activehead); 917 918 /* output a polygon for this band */ 919 if (firsttime || !(miny % NLINES)) { 920 register int numwait; /* number in the waiting list */ 921 register int newmaxy; /* max for this band (bottom or maxy)*/ 922 923 924 startspan(miny); 925 if ((newmaxy = (miny / NLINES) * NLINES + (NLINES - 1)) > maxy) 926 newmaxy = maxy; 927 928 /* count up those vectors that WILL */ 929 /* become active in this band */ 930 for (numwait = 0, vectptr = waitinghead->next; 931 vectptr != NULL; vectptr = vectptr->next) { 932 if (vectptr->param <= newmaxy) 933 numwait++; 934 } 935 936 sprintf(op,"Dq %d %d %d %d",member,active+numwait,miny,newmaxy); 937 op += strlen(op); 938 for (i = active, vectptr = activehead->next; i--; 939 vectptr = vectptr->next) { 940 sprintf(op, " %d %d %d %d %d", 941 vectptr->param, vectptr->dx, -vectptr->dy, 942 vectptr->currx, vectptr->endy); 943 op += strlen(op); 944 } 945 for (vectptr = waitinghead->next; vectptr != NULL; 946 vectptr = vectptr->next) { 947 if (vectptr->param <= newmaxy) { 948 sprintf(op, " %d %d %d %d %d", 949 vectptr->param, vectptr->dx, vectptr->dy, 950 vectptr->currx, vectptr->endy); 951 op += strlen(op); 952 } 953 } 954 *(op++) = '\n'; 955 firsttime = 0; 956 } 957 958 /* update the vectors */ 959 vectptr = activehead->next; 960 do { 961 if (vectptr->dx > 0) { 962 while (vectptr->param >= 0) { 963 vectptr->param -= vectptr->dy; 964 vectptr->currx++; 965 } 966 vectptr->param += vectptr->dx; 967 } else if (vectptr->dx < 0) { 968 while (vectptr->param >= 0) { 969 vectptr->param -= vectptr->dy; 970 vectptr->currx--; 971 } 972 vectptr->param -= vectptr->dx; 973 } 974 /* must sort the vectors if updates */ 975 /* caused them to cross */ 976 /* also move to next vector here */ 977 if (vectptr->currx < vectptr->prev->currx) { 978 register polyvector *v; /* vector to move */ 979 register polyvector *p; /* vector to put it after */ 980 981 v = vectptr; 982 p = v->prev; 983 while (v->currx < p->currx) /* find the */ 984 p = p->prev; /* right vector */ 985 986 vectptr = vectptr->next; /* remove from spot */ 987 vectptr->prev = v->prev; 988 v->prev->next = vectptr; 989 990 v->prev = p; /* put in new spot */ 991 v->next = p->next; 992 p->next = v; 993 v->next->prev = v; 994 } else { 995 vectptr = vectptr->next; 996 } 997 } while (vectptr != activehead); 998 999 ++miny; 1000 } /* while (miny < nexty) */ 1001 } /* while (miny <= maxy) */ 1002 1003 leavepoly: 1004 startspan(vpos); /* make sure stuff after polygon is at correct vpos */ 1005 free(waitinghead); 1006 } /* polygon function */ 1007