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
main(argc,argv)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 */
getnumber(fp)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 */
ngetnumber(fp)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
conv(fp)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
setlimit(newup,newdown)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
arcbounds(h,v,h1,v1)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
oflush()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
done()630 done()
631 {
632 oflush();
633 exit(0);
634 }
635
error(f,s,a1,a2,a3,a4,a5,a6,a7)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
t_push()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
t_pop()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
t_page(n)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
startspan(n)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
polygon(member,nvect,x,y,maxy,miny)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