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 */ 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 */ 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 */ 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 */ 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