1 /*
2 * @(#)graphics2.c 1.2 01/03/85
3 *
4 * Line drawing and polygon fill routines for the SUN Gremlin
5 * picture editor. Line drawing courtesy of dsun.c and polygon
6 * fill courtesy of dvar.c.
7 *
8 * Mark Opperman (opcode@monet.BERKELEY)
9 *
10 */
11
12 #include <suntool/tool_hs.h>
13 #include "gremlin.h"
14
15 #define point(sun_x, sun_y) pr_put(scratch_pr, (sun_x), (sun_y), 1)
16
17 /* imports from main.c */
18
19 extern struct pixrect *scratch_pr;
20 extern linestyle; /* type of line (1 - 6) */
21 extern linemod; /* line drawing mask (SOLID, DOTTED, ...) */
22 extern linethickness; /* 1, 2, 3 */
23 extern SymbolicLines; /* TRUE if OK to use pr_vector for all lines */
24 extern SUN_XORIGIN; /* database x-coord of upper left screen */
25 extern SUN_YORIGIN; /* database y-coord of upper left screen */
26
27 /* imports from display.c */
28
29 extern minsunx, maxsunx, minsuny, maxsuny;
30
31 /* imports from menu.c */
32
33 extern struct _menu menu[];
34 extern int HiStipple[];
35
36 /* imports from graphics.c */
37
38 extern char stipple_patterns[NSTIPPLES][128];
39 extern rasterlength;
40 extern bytesperline;
41 extern nlines; /* scratch_pr->pr_size.x */
42 extern char *fill; /* zero origin in filling buffer */
43
44 /* imports from C */
45
46 extern char *calloc();
47
48 /* locals */
49
50 static char *stipplebits;
51
52 typedef struct poly {
53 struct poly *next; /* doubly-linked lists of vectors */
54 struct poly *prev;
55 int param; /* bressenham line algorithm parameter */
56 short dy; /* delta-y for calculating line */
57 short dx; /* delta-x for calculating line */
58 short curry; /* current y in this vector */
59 short endx; /* where vector ends */
60 } polyvector;
61
62
63 /*
64 * Vector from (x1, y1) to (x2, y2) using global linemod and linethickness.
65 * Parameters in database coordinates system.
66 * Always write to scratch_pr.
67 * Borrowed from dsun.
68 */
GRVector(dbx1,dby1,dbx2,dby2)69 GRVector(dbx1, dby1, dbx2, dby2)
70 float dbx1, dby1, dbx2, dby2;
71 {
72 register x0; /* starting point and line-walking registers */
73 register y0;
74 register res;
75 register i; /* line-bleeding carrier */
76 int dx; /* parameters in the line calculations */
77 int dy;
78 int xinc;
79 int yinc;
80 int x1; /* end-point of the line */
81 int y1;
82 int radius;
83 int top; /* how much to bleed line in "up" (left) direction */
84 int bottom; /* how much to bleed line in "down" (right) direction */
85 int stop1; /* place to stop making circles at start of line */
86 int stop2; /* place to start making circles at end of line */
87 int halfstop; /* distance tween stop1 and stop3 */
88 int stop3; /* midpoint `tween making circles and lines */
89
90 x0 = dbx_to_win(dbx1); /* convert endpoints to SUN coordinates */
91 y0 = dby_to_win(dby1);
92 x1 = dbx_to_win(dbx2);
93 y1 = dby_to_win(dby2);
94
95 MINMAX(minsunx, maxsunx, x0);
96 MINMAX(minsuny, maxsuny, y0);
97 MINMAX(minsunx, maxsunx, x1);
98 MINMAX(minsuny, maxsuny, y1);
99
100 if ((SymbolicLines) || (linestyle == 5 /* NARROW */)) {
101 pr_vector(scratch_pr, x0, y0, x1, y1, PIX_SRC | PIX_DST, 1);
102 return;
103 }
104
105 xinc = 1;
106 yinc = 1;
107 if ((dx = x1 - x0) < 0) {
108 xinc = -1;
109 dx = -dx;
110 }
111 if ((dy = y1 - y0) < 0) {
112 yinc = -1;
113 dy = -dy;
114 }
115
116 radius = (linethickness - 1) / 2;
117 RoundEnd(x0, y0, radius, TRUE); /* add ends of line */
118 RoundEnd(x1, y1, radius, TRUE); /* (nice and curvy) */
119
120 top = linethickness; /* increase line thickness if at an angle */
121 stop1 = halfstop = 0;
122 if ((i = (int) (sqrt ((double) (dx * dx + dy * dy)) + 0.01)) < 2)
123 return; /* small lines are done with endpoints */
124
125 if (dx >= dy) {
126 top = (linethickness * i) / dx;
127 stop1 = (linethickness * dy) / (i + 1);
128 halfstop = (radius * dy) / i;
129 } else {
130 top = (linethickness * i) / dy;
131 stop1 = (linethickness * dx) / (i + 1);
132 halfstop = (radius * dx) / i;
133 }
134
135 bottom = (top - 1) / 2;
136 top = top / 2;
137
138 if (dx >= dy) {
139 res = (dy >> 1) - (dx >> 1);
140 if (linethickness >= i) {
141 stop1 = stop2 = x0;
142 halfstop = i + 1;
143 } else if (xinc == 1) {
144 stop2 = x1 - stop1;
145 stop1 = x0 + stop1;
146 stop3 = x0 + halfstop;
147 } else {
148 stop2 = x1 + stop1;
149 stop1 = x0 - stop1;
150 stop3 = x0 - halfstop;
151 }
152
153 while (x0 != stop1) {
154 RoundEnd(x0, y0, radius, FALSE);
155 if ((x0 & linemod) && (xinc == 1 ? x0 > stop3 : x0 < stop3)) {
156 for (i=y0-top; i<=y0+bottom; i++)
157 point(x0, i);
158 }
159 if (res >= 0) {
160 res -= dx;
161 y0 += yinc;
162 }
163 res += dy;
164 x0 += xinc;
165 }
166
167 while (x0 != stop2) {
168 if (x0 & linemod) {
169 for (i=y0-top; i<=y0+bottom; i++)
170 point(x0, i);
171 }
172 if (res >= 0) {
173 res -= dx;
174 y0 += yinc;
175 }
176 res += dy;
177 x0 += xinc;
178 }
179
180 stop3 = x1 + (xinc == 1 ? -halfstop : halfstop);
181
182 while (x0 != x1) {
183 RoundEnd(x0, y0, radius, FALSE);
184 if ((x0 &linemod) && (xinc == 1 ? x0 < stop3 : x0 > stop3)) {
185 for (i = y0 - top; i <= y0 + bottom; i++)
186 point(x0, i);
187 }
188 if (res >= 0) {
189 res -= dx;
190 y0 += yinc;
191 }
192 res += dy;
193 x0 += xinc;
194 }
195 } else {
196 res = (dx >> 1) - (dy >> 1);
197
198 if (linethickness >= i) {
199 stop1 = stop2 = y0;
200 halfstop = i + 1;
201 } else if (yinc == 1) {
202 stop2 = y1 - stop1;
203 stop1 = y0 + stop1;
204 stop3 = y0 + halfstop;
205 } else {
206 stop2 = y1 + stop1;
207 stop1 = y0 - stop1;
208 stop3 = y0 - halfstop;
209 }
210
211 while (y0 != stop1) {
212 RoundEnd(x0, y0, radius, FALSE);
213 if ((y0 & linemod) && (yinc == 1 ? y0 > stop3 : y0 < stop3)) {
214 for (i = x0 - top; i <= x0 + bottom; i++)
215 point(i, y0);
216 }
217 if (res >= 0) {
218 res -= dy;
219 x0 += xinc;
220 }
221 res += dx;
222 y0 += yinc;
223 }
224
225 while (y0 != stop2) {
226 if (y0&linemod) {
227 for (i=x0-top; i<=x0+bottom; i++)
228 point(i, y0);
229 }
230 if (res >= 0) {
231 res -= dy;
232 x0 += xinc;
233 }
234 res += dx;
235 y0 += yinc;
236 }
237
238 stop3 = y1 + (yinc == 1 ? -halfstop : halfstop);
239
240 while (y0 != y1) {
241 RoundEnd(x0, y0, radius, FALSE);
242 if ((y0 & linemod) && (yinc == 1 ? y0 < stop3 : y0 > stop3)) {
243 for (i=x0-top; i<=x0+bottom; i++)
244 point(i, y0);
245 }
246 if (res >= 0) {
247 res -= dy;
248 x0 += xinc;
249 }
250 res += dx;
251 y0 += yinc;
252 }
253 }
254 }
255
256
257 /*
258 * Plots a filled (if requested) circle of the specified radius
259 * centered about (x, y).
260 * Coordinates are window relative.
261 * Modified from dsun source.
262 */
RoundEnd(x,y,radius,filled)263 RoundEnd(x, y, radius, filled)
264 register x;
265 register y;
266 int radius, filled;
267 {
268 float xs, ys, epsilon;
269 register j, k;
270
271
272 point(x, y+radius); /* do the starting point of the circle */
273
274 if (radius < 1) /* if circle is tiny, quit now */
275 return;
276
277 point(x, y-radius);
278 if (y-radius < minsuny)
279 minsuny = y-radius;
280
281 /* Calculate trajectory of the circle for 1/4 the circumference
282 (while ys is positive) and mirror to get the other three quadrants. */
283
284 xs = 0.0;
285 ys = (float) radius;
286 epsilon = 1.0 / ys;
287
288 while (ys >= 0) {
289 j = (int) (xs + 0.5);
290 k = (int) (ys + 0.5);
291 if (filled) { /* fill from center */
292 do {
293 point(j+x, k+y);
294 point(j+x, y-k);
295 point(x-j, k+y);
296 point(x-j, y-k);
297 } while (--k >= 0);
298 } else { /* do the perimeter only */
299 point(j+x, k+y);
300 point(j+x, y-k);
301 point(x-j, k+y);
302 point(x-j, y-k);
303 }
304 xs += epsilon * ys; /* generate circumference */
305 ys -= epsilon * xs;
306 }
307 } /* end RoundEnd */;
308
309
310 /*
311 * Set drawing parameters for filling polygons.
312 * Must be called before GRStippleFill().
313 */
GRSetStippleStyle(style)314 GRSetStippleStyle(style)
315 int style;
316 {
317 if ((style <= 0) || (style > NSTIPPLES)) {
318 fprintf(stderr, "GRSetStippleStyle: bad stipple #%d\n", style);
319 return;
320 }
321
322 stipplebits = stipple_patterns[style-1];
323 }
324
325 /* >>> stipple fonts must be 32 x 32 bits <<< */
326 #define MASK 31 /* mask to pick off pixel index into stipple */
327 #define BYTEWIDTH 4 /* glyph width in bytes */
328 #define BYTEMASK 3 /* mask to pick off byte index into stipple */
329
330
331 /*
332 * Fill polygon defined by points in plist using parameters set by
333 * previous call to GRSetStippleStyle().
334 *
335 * This routine was modified from source for the varian driver.
336 * Because the varian rotates everything 90 degrees before printing,
337 * the x and y coordinates from the window are reversed before
338 * computing the region. This is just a kludge to get the code
339 * to work as soon as possible. Better to change this at some point,
340 * but I don't have time now.
341 *
342 * The scan-line algorithm implemented scans from left to right
343 * (low x to high x). It also scans, within a line, from bottom to top
344 * (high y to low y). Stipple patterns MUST be a power of two bytes wide
345 * and square (in fact, they must be 32 x 32 bits).
346 */
GRStippleFill(plist)347 GRStippleFill(plist)
348 POINT *plist;
349 {
350 int nextx; /* x value where next vector starts */
351 int maxx, minx, maxy, miny; /* finds bounds of polygon */
352 polyvector *activehead; /* doing fill, is active edge list */
353 polyvector *waitinghead; /* edges waiting to be active */
354 register polyvector *vectptr; /* random vector */
355 register int i; /* random register */
356
357 char *topstipple; /* beginning of stipple glyph */
358 char *leftstipple; /* beginning of line of stipple */
359 char *bottompage; /* the edge of a raster line */
360
361 int x[MAXPOINTS]; /* algorithm requires this form */
362 int y[MAXPOINTS];
363 int npts;
364 POINT *p1, p2;
365
366 p1 = plist;
367 npts = 0;
368
369 /*
370 * convert coordinates to arrays of integers exchanging x and y,
371 * and making origin upper right.
372 */
373 while (!Nullpoint(p1)) {
374 npts++;
375 x[npts] = dby_to_win(p1->y) - 1;
376 y[npts] = rasterlength - 1 - dbx_to_win(p1->x);
377 p1 = PTNextPoint(p1);
378 }
379
380 topstipple = stipplebits; /* start of stipple pattern */
381
382 /* allocate space for raster-fill algorithm */
383 if ((vectptr = (polyvector *) calloc(sizeof(polyvector), npts + 6)) ==
384 (polyvector *) NULL) {
385 fprintf(stderr, "unable to allocate space for polygon");
386 return;
387 }
388
389 waitinghead = vectptr;
390 minx = maxx = x[1];
391 miny = maxy = y[1];
392 (vectptr++)->prev = (polyvector *) NULL; /* put dummy entry at start */
393 waitinghead->next = vectptr;
394 vectptr->prev = waitinghead;
395
396 i = 1; /* starting point of coords */
397 if (y[1] != y[npts] || x[1] != x[npts]) {
398 y[0] = y[npts]; /* close polygon if it's not */
399 x[0] = x[npts];
400 i = 0;
401 }
402
403 while (i < npts) { /* set up the vectors */
404 register int j; /* indexes to work off of */
405 register int k;
406
407 /* remember limits */
408 MINMAX(miny, maxy, y[i]);
409 MINMAX(minx, maxx, x[i]);
410
411 j = i; /* j points to the higher (lesser) point */
412 k = ++i;
413 if (x[j] == x[k]) /* ignore vertical lines */
414 continue;
415
416 if (x[j] > x[k]) {
417 j++;
418 k--;
419 }
420 vectptr->next = vectptr + 1;
421 vectptr->param = x[j]; /* starting point of vector */
422 vectptr->dy = y[k] - y[j]; /* line-calculating parameters */
423 vectptr->dx = x[k] - x[j];
424 vectptr->curry = y[j]; /* starting point */
425 (vectptr++)->endx = x[k]; /* ending point */
426 vectptr->prev = vectptr - 1;
427 }
428
429 /*
430 * keep polygon within bounds of scratch pixrect
431 * width is checked when actual drawing is done
432 */
433 if (maxx >= scratch_pr->pr_size.y)
434 maxx = scratch_pr->pr_size.y - 1;
435
436 /* set now because we didn't know minx before */
437 leftstipple = topstipple + (minx & MASK) * BYTEWIDTH;
438 bottompage = fill + minx * bytesperline;
439 waitinghead->param = minx - 1;
440
441 /* if no useable vectors, quit */
442 if (vectptr == waitinghead + 1) {
443 free(waitinghead);
444 return;
445 }
446
447 vectptr->param = maxx + 1; /* dummy entry at end, too */
448 vectptr->next = (polyvector *) NULL;
449
450 activehead = ++vectptr; /* two dummy entries for active list */
451 vectptr->curry = maxy + 1; /* head */
452 vectptr->endx = maxx + 1;
453 vectptr->param = vectptr->dx = vectptr->dy = 0;
454 activehead->next = ++vectptr;
455 activehead->prev = vectptr;
456
457 vectptr->prev = activehead; /* tail */
458 vectptr->next = activehead;
459 vectptr->curry = miny - 1;
460 vectptr->endx = maxx + 1;
461 vectptr->param = vectptr->dx = vectptr->dy = 0;
462
463
464 /*
465 * main loop -- gets vectors off the waiting list, then displays spans
466 * while updating the vectors in the active list
467 */
468 while (minx <= maxx) {
469 i = maxx + 1; /* this is the NEXT time to get a new vector */
470 for (vectptr=waitinghead->next; vectptr!=(polyvector *) NULL; ) {
471 if (minx == vectptr->param) {
472 /*
473 * The entry in waiting list (vectptr) is ready to go into
474 * active list. Need to convert some vector stuff and
475 * sort the entry into the list.
476 */
477 register polyvector *p; /* random vector pointers */
478 register polyvector *v;
479
480 /* convert this entry to active */
481 if (vectptr->dy < 0)
482 vectptr->param = (vectptr->dy >> 1) - (vectptr->dx >> 1);
483 else
484 vectptr->param = -((vectptr->dx >> 1) + (vectptr->dy >> 1));
485
486 p = vectptr; /* remove from the */
487 vectptr = vectptr->next; /* waiting list */
488 vectptr->prev = p->prev;
489 p->prev->next = vectptr;
490
491 /*
492 * find where it goes in the active list
493 * (sorted greatest first)
494 */
495 for (v=activehead->next; v->curry>p->curry; v=v->next)
496 ;
497 p->next = v; /* insert into active list */
498 p->prev = v->prev; /* before the one it stopped on */
499 v->prev = p;
500 p->prev->next = p;
501 } else {
502 if (i > vectptr->param) {
503 i = vectptr->param;
504 }
505 vectptr = vectptr->next;
506 }
507 }
508 nextx = i;
509
510 /* print the polygon while there are no more vectors to add */
511 while (minx < nextx) {
512 /* remove any finished vectors */
513 vectptr = activehead->next;
514 do {
515 if (vectptr->endx <= minx) {
516 vectptr->prev->next = vectptr->next;
517 vectptr->next->prev = vectptr->prev;
518 }
519 } while ((vectptr = vectptr->next) != activehead);
520
521 /* draw the span */
522 if (((unsigned) minx) < nlines) {
523 vectptr = activehead->next;
524 while (vectptr->next != activehead) {
525 register int start; /* get the beginning */
526 register int length; /* and the end of span */
527 register char *glyph;
528 register char *raster;
529
530 start = (rasterlength - 1) - vectptr->curry;
531 vectptr = vectptr->next;
532 length = rasterlength - vectptr->curry;
533 vectptr = vectptr->next;
534
535 /* bound the polygon to the page */
536 if (start >= rasterlength)
537 break;
538 if (start < 0)
539 start = 0;
540 if (length > rasterlength)
541 length = rasterlength;
542 length -= start; /* length is in pixels */
543
544 i = start & 7;
545 start = start >> 3; /* start is in bytes */
546 raster = bottompage + start;
547 glyph = leftstipple + (start & BYTEMASK);
548
549 if (i) { /* do any piece of byte */
550 register char data; /* that hangs on the front */
551
552 data = (*(glyph++)) & (0x7f >> --i);
553 length -= 7 - i;
554 if (length < 0) { /* less than one byte wide? */
555 data &= 0xff << -length;
556 length = 0; /* force clean stoppage */
557 }
558 *(raster++) |= data;
559
560 /* update glyph ptr after first byte */
561 if (!(++start & BYTEMASK))
562 glyph = leftstipple;
563 }
564
565 /* fill the line of raster */
566 while ((length -= 8) >= 0) {
567 *(raster++) |= *(glyph++);
568 if (!(++start & BYTEMASK))
569 glyph = leftstipple;
570 }
571
572 /* add any part hanging off the end */
573 if (length & 7) {
574 *raster |= (*glyph) & (0xff << -length);
575 }
576 }
577 }
578
579 /* update the vectors */
580 vectptr = activehead->next;
581 do {
582 if (vectptr->dy > 0) {
583 while (vectptr->param >= 0) {
584 vectptr->param -= vectptr->dx;
585 vectptr->curry++;
586 }
587 vectptr->param += vectptr->dy;
588 } else if (vectptr->dy < 0) {
589 while (vectptr->param >= 0) {
590 vectptr->param -= vectptr->dx;
591 vectptr->curry--;
592 }
593 vectptr->param -= vectptr->dy;
594 }
595
596 /*
597 * must sort the vectors if updates caused them to cross
598 * also move to next vector here
599 */
600 if (vectptr->curry > vectptr->prev->curry) {
601 register polyvector *v; /* vector to move */
602 register polyvector *p; /* vector to put it after */
603
604 v = vectptr;
605 p = v->prev;
606 while (v->curry > p->curry) /* find the */
607 p = p->prev; /* right vector */
608
609 vectptr = vectptr->next; /* remove from spot */
610 vectptr->prev = v->prev;
611 v->prev->next = vectptr;
612
613 v->prev = p; /* put in new spot */
614 v->next = p->next;
615 p->next = v;
616 v->next->prev = v;
617 } else {
618 vectptr = vectptr->next;
619 }
620 } while (vectptr != activehead);
621
622 if (++minx & MASK) {
623 leftstipple += BYTEWIDTH;
624 } else {
625 leftstipple = topstipple;
626 }
627 bottompage += bytesperline;
628 } /* while (minx < nextx) */
629 } /* while (minx <= maxx) */
630
631 free(waitinghead);
632 } /* end GRStippleFill */
633