1 /* Last non-groff version: hgraph.c 1.14 (Berkeley) 84/11/27
3 * This file contains the graphics routines for converting gremlin pictures
11 #ifdef NEED_DECLARATION_HYPOT
13 double hypot(double, double);
15 #endif /* NEED_DECLARATION_HYPOT */
20 #define PointsPerInterval 64
21 #define pi 3.14159265358979324
22 #define twopi (2.0 * pi)
23 #define len(a, b) hypot((double)(b.x-a.x), (double)(b.y-a.y))
26 extern int dotshifter; /* for the length of dotted curves */
28 extern int style[]; /* line and character styles */
29 extern double thick[];
32 extern int stipple_index[]; /* stipple font index for stipples 0 - 16 */
33 extern char *stipple; /* stipple type (cf or ug) */
36 extern double troffscale; /* imports from main.c */
37 extern double linethickness;
56 void HGSetFont(int font, int size);
57 void HGPutText(int justify, POINT pnt, register char *string);
58 void HGSetBrush(int mode);
59 void tmove2(int px, int py);
60 void doarc(POINT cp, POINT sp, int angle);
61 void tmove(POINT * ptr);
63 void drawwig(POINT * ptr, int type);
64 void HGtline(int x1, int y1);
67 void HGArc(register int cx, register int cy, int px, int py, int angle);
68 void picurve(register int *x, register int *y, int npts);
69 void HGCurve(int *x, int *y, int numpoints);
70 void Paramaterize(int x[], int y[], float h[], int n);
71 void PeriodicSpline(float h[], int z[],
72 float dz[], float d2z[], float d3z[],
74 void NaturalEndSpline(float h[], int z[],
75 float dz[], float d2z[], float d3z[],
80 /*----------------------------------------------------------------------------*
81 | Routine: HGPrintElt (element_pointer, baseline)
83 | Results: Examines a picture element and calls the appropriate
84 | routine(s) to print them according to their type. After the
85 | picture is drawn, current position is (lastx, lasty).
86 *----------------------------------------------------------------------------*/
89 HGPrintElt(ELT *element,
95 register int graylevel;
97 if (!DBNullelt(element) && !Nullpoint((p1 = element->ptlist))) {
98 /* p1 always has first point */
99 if (TEXT(element->type)) {
100 HGSetFont(element->brushf, element->size);
101 switch (element->size) {
117 HGPutText(element->type, *p1, element->textpt);
119 if (element->brushf) /* if there is a brush, the */
120 HGSetBrush(element->brushf); /* graphics need it set */
122 switch (element->type) {
125 p2 = PTNextPoint(p1);
127 doarc(*p1, *p2, element->size);
132 length = 0; /* keep track of line length */
138 length = 0; /* keep track of line length */
139 drawwig(p1, BSPLINE);
144 length = 0; /* keep track of line length so */
145 tmove(p1); /* single lines don't get long */
146 while (!Nullpoint((p1 = PTNextPoint(p1)))) {
147 HGtline((int) (p1->x * troffscale),
148 (int) (p1->y * troffscale));
149 if (length++ > LINELENGTH) {
159 /* brushf = style of outline; size = color of fill:
160 * on first pass (polyfill=FILL), do the interior using 'P'
162 * on second pass (polyfill=OUTLINE), do the outline using a series
163 * of vectors. It might make more sense to use \D'p ...',
164 * but there is no uniform way to specify a 'fill character'
165 * that prints as 'no fill' on all output devices (and
167 * If polyfill=BOTH, just use the \D'p ...' command.
169 float firstx = p1->x;
170 float firsty = p1->y;
172 length = 0; /* keep track of line length so */
173 /* single lines don't get long */
175 if (polyfill == FILL || polyfill == BOTH) {
176 /* do the interior */
177 char command = (polyfill == BOTH && element->brushf) ? 'p' : 'P';
179 /* include outline, if there is one and */
180 /* the -p flag was set */
182 /* switch based on what gremlin gives */
183 switch (element->size) {
208 default: /* who's giving something else? */
209 graylevel = NSTIPPLES;
212 /* int graylevel = element->size; */
216 if (graylevel > NSTIPPLES)
217 graylevel = NSTIPPLES;
218 printf("\\h'-%du'\\D'f %du'",
219 stipple_index[graylevel],
220 stipple_index[graylevel]);
223 printf("\\D'%c", command);
225 while (!Nullpoint((PTNextPoint(p1)))) {
226 p1 = PTNextPoint(p1);
229 if (length++ > LINELENGTH) {
235 /* close polygon if not done so by user */
236 if ((firstx != p1->x) || (firsty != p1->y)) {
244 /* else polyfill == OUTLINE; only draw the outline */
245 if (!(element->brushf))
247 length = 0; /* keep track of line length */
250 while (!Nullpoint((PTNextPoint(p1)))) {
251 p1 = PTNextPoint(p1);
252 HGtline((int) (p1->x * troffscale),
253 (int) (p1->y * troffscale));
254 if (length++ > LINELENGTH) {
260 /* close polygon if not done so by user */
261 if ((firstx != p1->x) || (firsty != p1->y)) {
262 HGtline((int) (firstx * troffscale),
263 (int) (firsty * troffscale));
267 } /* end case POLYGON */
269 } /* end else Text */
274 /*----------------------------------------------------------------------------*
275 | Routine: HGPutText (justification, position_point, string)
277 | Results: Given the justification, a point to position with, and a
278 | string to put, HGPutText first sends the string into a
279 | diversion, moves to the positioning point, then outputs
280 | local vertical and horizontal motions as needed to justify
281 | the text. After all motions are done, the diversion is
283 *----------------------------------------------------------------------------*/
286 HGPutText(int justify,
288 register char *string)
290 int savelasty = lasty; /* vertical motion for text is to be */
291 /* ignored. Save current y here */
293 printf(".nr g8 \\n(.d\n"); /* save current vertical position. */
294 printf(".ds g9 \""); /* define string containing the text. */
295 while (*string) { /* put out the string */
296 if (*string == '\\' &&
297 *(string + 1) == '\\') { /* one character at a */
298 printf("\\\\\\"); /* time replacing // */
299 string++; /* by //// to prevent */
300 } /* interpretation at */
301 printf("%c", *(string++)); /* printout time */
305 tmove(&pnt); /* move to positioning point */
308 /* local vertical motions */
309 /* (the numbers here are used to be somewhat compatible with gprint) */
313 printf("\\v'0.85n'"); /* down half */
319 printf("\\v'1.7n'"); /* down whole */
323 /* local horizontal motions */
327 printf("\\h'-\\w'\\*(g9'u/2u'"); /* back half */
333 printf("\\h'-\\w'\\*(g9'u'"); /* back whole */
336 printf("\\&\\*(g9\n"); /* now print the text. */
337 printf(".sp |\\n(g8u\n"); /* restore vertical position */
338 lasty = savelasty; /* vertical position restored to where it */
339 lastx = xleft; /* was before text, also horizontal is at */
341 } /* end HGPutText */
344 /*----------------------------------------------------------------------------*
345 | Routine: doarc (center_point, start_point, angle)
347 | Results: Produces either drawarc command or a drawcircle command
348 | depending on the angle needed to draw through.
349 *----------------------------------------------------------------------------*/
356 if (angle) /* arc with angle */
357 HGArc((int) (cp.x * troffscale), (int) (cp.y * troffscale),
358 (int) (sp.x * troffscale), (int) (sp.y * troffscale), angle);
359 else /* a full circle (angle == 0) */
360 HGArc((int) (cp.x * troffscale), (int) (cp.y * troffscale),
361 (int) (sp.x * troffscale), (int) (sp.y * troffscale), 0);
365 /*----------------------------------------------------------------------------*
366 | Routine: HGSetFont (font_number, Point_size)
368 | Results: ALWAYS outputs a .ft and .ps directive to troff. This is
369 | done because someone may change stuff inside a text string.
370 | Changes thickness back to default thickness. Default
371 | thickness depends on font and pointsize.
372 *----------------------------------------------------------------------------*/
379 ".ps %d\n", tfont[font - 1], tsize[size - 1]);
380 linethickness = DEFTHICK;
384 /*----------------------------------------------------------------------------*
385 | Routine: HGSetBrush (line_mode)
387 | Results: Generates the troff commands to set up the line width and
388 | style of subsequent lines. Does nothing if no change is
391 | Side Efct: Sets `linmode' and `linethicknes'.
392 *----------------------------------------------------------------------------*/
397 register int printed = 0;
399 if (linmod != style[--mode]) {
400 /* Groff doesn't understand \Ds, so we take it out */
401 /* printf ("\\D's %du'", linmod = style[mode]); */
402 linmod = style[mode];
405 if (linethickness != thick[mode]) {
406 linethickness = thick[mode];
407 printf("\\h'-%.2fp'\\D't %.2fp'", linethickness, linethickness);
415 /*----------------------------------------------------------------------------*
416 | Routine: dx (x_destination)
418 | Results: Scales and outputs a number for delta x (with a leading
419 | space) given `lastx' and x_destination.
421 | Side Efct: Resets `lastx' to x_destination.
422 *----------------------------------------------------------------------------*/
427 register int ix = (int) (x * troffscale);
429 printf(" %du", ix - lastx);
434 /*----------------------------------------------------------------------------*
435 | Routine: dy (y_destination)
437 | Results: Scales and outputs a number for delta y (with a leading
438 | space) given `lastyline' and y_destination.
440 | Side Efct: Resets `lastyline' to y_destination. Since `line' vertical
441 | motions don't affect `page' ones, `lasty' isn't updated.
442 *----------------------------------------------------------------------------*/
447 register int iy = (int) (y * troffscale);
449 printf(" %du", iy - lastyline);
454 /*----------------------------------------------------------------------------*
455 | Routine: tmove2 (px, py)
457 | Results: Produces horizontal and vertical moves for troff given the
458 | pair of points to move to and knowing the current position.
459 | Also puts out a horizontal move to start the line. This is
460 | a variation without the .sp command.
461 *----------------------------------------------------------------------------*/
470 if ((dy = py - lasty)) {
471 printf("\\v'%du'", dy);
473 lastyline = lasty = py; /* lasty is always set to current */
474 if ((dx = px - lastx)) {
475 printf("\\h'%du'", dx);
481 /*----------------------------------------------------------------------------*
482 | Routine: tmove (point_pointer)
484 | Results: Produces horizontal and vertical moves for troff given the
485 | pointer of a point to move to and knowing the current
486 | position. Also puts out a horizontal move to start the
488 *----------------------------------------------------------------------------*/
493 register int ix = (int) (ptr->x * troffscale);
494 register int iy = (int) (ptr->y * troffscale);
498 if ((dy = iy - lasty)) {
499 printf(".sp %du\n", dy);
501 lastyline = lasty = iy; /* lasty is always set to current */
502 if ((dx = ix - lastx)) {
503 printf("\\h'%du'", dx);
509 /*----------------------------------------------------------------------------*
512 | Results: Ends off an input line. `.sp -1' is also added to counteract
513 | the vertical move done at the end of text lines.
515 | Side Efct: Sets `lastx' to `xleft' for troff's return to left margin.
516 *----------------------------------------------------------------------------*/
521 printf("\n.sp -1\n");
526 /*----------------------------------------------------------------------------*
529 | Results: Draws a single solid line to (x,y).
530 *----------------------------------------------------------------------------*/
537 printf(" %du", px - lastx);
538 printf(" %du'", py - lastyline);
540 lastyline = lasty = py;
544 /*----------------------------------------------------------------------------
545 | Routine: drawwig (ptr, type)
547 | Results: The point sequence found in the structure pointed by ptr is
548 | placed in integer arrays for further manipulation by the
549 | existing routing. With the corresponding type parameter,
550 | either picurve or HGCurve are called.
551 *----------------------------------------------------------------------------*/
557 register int npts; /* point list index */
558 int x[MAXPOINTS], y[MAXPOINTS]; /* point list */
560 for (npts = 1; !Nullpoint(ptr); ptr = PTNextPoint(ptr), npts++) {
561 x[npts] = (int) (ptr->x * troffscale);
562 y[npts] = (int) (ptr->y * troffscale);
565 if (type == CURVE) /* Use the 2 different types of curves */
566 HGCurve(&x[0], &y[0], npts);
568 picurve(&x[0], &y[0], npts);
573 /*----------------------------------------------------------------------------
574 | Routine: HGArc (xcenter, ycenter, xstart, ystart, angle)
576 | Results: This routine plots an arc centered about (cx, cy) counter
577 | clockwise starting from the point (px, py) through `angle'
578 | degrees. If angle is 0, a full circle is drawn. It does so
579 | by creating a draw-path around the arc whose density of
580 | points depends on the size of the arc.
581 *----------------------------------------------------------------------------*/
584 HGArc(register int cx,
590 double xs, ys, resolution, fullcircle;
597 register double epsilon;
604 resolution = (1.0 + hypot(xs, ys) / res) * PointsPerInterval;
605 /* mask = (1 << (int) log10(resolution + 1.0)) - 1; */
606 (void) frexp(resolution, &m); /* A bit more elegant than log10 */
607 for (mask = 1; mask < m; mask = mask << 1);
610 epsilon = 1.0 / resolution;
611 fullcircle = (2.0 * pi) * resolution;
613 extent = (int) fullcircle;
615 extent = (int) (angle * fullcircle / 360.0);
618 while (--extent >= 0) {
620 nx = cx + (int) (xs + 0.5);
622 ny = cy + (int) (ys + 0.5);
623 if (!(extent & mask)) {
624 HGtline(nx, ny); /* put out a point on circle */
625 if (length++ > LINELENGTH) {
634 /*----------------------------------------------------------------------------
635 | Routine: picurve (xpoints, ypoints, num_of_points)
637 | Results: Draws a curve delimited by (not through) the line segments
638 | traced by (xpoints, ypoints) point list. This is the `Pic'
640 *----------------------------------------------------------------------------*/
643 picurve(register int *x,
647 register int nseg; /* effective resolution for each curve */
648 register int xp; /* current point (and temporary) */
650 int pxp, pyp; /* previous point (to make lines from) */
651 int i; /* inner curve segment traverser */
653 double w; /* position factor */
654 double t1, t2, t3; /* calculation temps */
656 if (x[1] == x[npts] && y[1] == y[npts]) {
657 x[0] = x[npts - 1]; /* if the lines' ends meet, make */
658 y[0] = y[npts - 1]; /* sure the curve meets */
661 } else { /* otherwise, make the ends of the */
662 x[0] = x[1]; /* curve touch the ending points of */
663 y[0] = y[1]; /* the line segments */
664 x[npts + 1] = x[npts];
665 y[npts + 1] = y[npts];
668 pxp = (x[0] + x[1]) / 2; /* make the last point pointers */
669 pyp = (y[0] + y[1]) / 2; /* point to the start of the 1st line */
672 for (; npts--; x++, y++) { /* traverse the line segments */
675 nseg = (int) hypot((double) xp, (double) yp);
678 /* `nseg' is the number of line */
679 /* segments that will be drawn for */
680 /* each curve segment. */
681 nseg = (int) ((double) (nseg + (int) hypot((double) xp, (double) yp)) /
682 res * PointsPerInterval);
684 for (i = 1; i < nseg; i++) {
685 w = (double) i / (double) nseg;
687 t3 = t1 + 1.0 - (w + w);
688 t2 = 2.0 - (t3 + t1);
689 xp = (((int) (t1 * x[2] + t2 * x[1] + t3 * x[0])) + 1) / 2;
690 yp = (((int) (t1 * y[2] + t2 * y[1] + t3 * y[0])) + 1) / 2;
693 if (length++ > LINELENGTH) {
702 /*----------------------------------------------------------------------------
703 | Routine: HGCurve(xpoints, ypoints, num_points)
705 | Results: This routine generates a smooth curve through a set of
706 | points. The method used is the parametric spline curve on
707 | unit knot mesh described in `Spline Curve Techniques' by
708 | Patrick Baudelaire, Robert Flegal, and Robert Sproull --
710 *----------------------------------------------------------------------------*/
717 float h[MAXPOINTS], dx[MAXPOINTS], dy[MAXPOINTS];
718 float d2x[MAXPOINTS], d2y[MAXPOINTS], d3x[MAXPOINTS], d3y[MAXPOINTS];
732 * Solve for derivatives of the curve at each point separately for x and y
735 Paramaterize(x, y, h, numpoints);
738 if ((x[1] == x[numpoints]) && (y[1] == y[numpoints])) {
739 PeriodicSpline(h, x, dx, d2x, d3x, numpoints);
740 PeriodicSpline(h, y, dy, d2y, d3y, numpoints);
742 NaturalEndSpline(h, x, dx, d2x, d3x, numpoints);
743 NaturalEndSpline(h, y, dy, d2y, d3y, numpoints);
747 * generate the curve using the above information and PointsPerInterval
748 * vectors between each specified knot.
751 for (j = 1; j < numpoints; ++j) {
752 if ((x[j] == x[j + 1]) && (y[j] == y[j + 1]))
754 for (k = 0; k <= PointsPerInterval; ++k) {
755 t = (float) k *h[j] / (float) PointsPerInterval;
758 nx = x[j] + (int) (t * dx[j] + t2 * d2x[j] / 2 + t3 * d3x[j] / 6);
759 ny = y[j] + (int) (t * dy[j] + t2 * d2y[j] / 2 + t3 * d3y[j] / 6);
761 if (length++ > LINELENGTH) {
770 /*----------------------------------------------------------------------------
771 | Routine: Paramaterize (xpoints, ypoints, hparams, num_points)
773 | Results: This routine calculates parameteric values for use in
774 | calculating curves. The parametric values are returned
775 | in the array h. The values are an approximation of
776 | cumulative arc lengths of the curve (uses cord length).
777 | For additional information, see paper cited below.
778 *----------------------------------------------------------------------------*/
781 Paramaterize(int x[],
792 for (i = 1; i <= n; ++i) {
794 for (j = 1; j < i; j++) {
795 dx = x[j + 1] - x[j];
796 dy = y[j + 1] - y[j];
797 /* Here was overflowing, so I changed it. */
798 /* u[i] += sqrt ((double) (dx * dx + dy * dy)); */
799 u[i] += hypot((double) dx, (double) dy);
802 for (i = 1; i < n; ++i)
803 h[i] = u[i + 1] - u[i];
804 } /* end Paramaterize */
807 /*----------------------------------------------------------------------------
808 | Routine: PeriodicSpline (h, z, dz, d2z, d3z, npoints)
810 | Results: This routine solves for the cubic polynomial to fit a spline
811 | curve to the the points specified by the list of values.
812 | The Curve generated is periodic. The algorithms for this
813 | curve are from the `Spline Curve Techniques' paper cited
815 *----------------------------------------------------------------------------*/
818 PeriodicSpline(float h[], /* paramaterization */
819 int z[], /* point list */
820 float dz[], /* to return the 1st derivative */
821 float d2z[], /* 2nd derivative */
822 float d3z[], /* 3rd derivative */
823 int npoints) /* number of valid points */
826 float deltaz[MAXPOINTS], a[MAXPOINTS], b[MAXPOINTS];
827 float c[MAXPOINTS], r[MAXPOINTS], s[MAXPOINTS];
831 for (i = 1; i < npoints; ++i) {
832 deltaz[i] = h[i] ? ((double) (z[i + 1] - z[i])) / h[i] : 0;
834 h[0] = h[npoints - 1];
835 deltaz[0] = deltaz[npoints - 1];
838 for (i = 1; i < npoints - 1; ++i) {
839 d[i] = deltaz[i + 1] - deltaz[i];
841 d[0] = deltaz[1] - deltaz[0];
844 a[1] = 2 * (h[0] + h[1]);
847 for (i = 2; i < npoints - 1; ++i) {
848 a[i] = 2 * (h[i - 1] + h[i]) -
849 pow((double) h[i - 1], (double) 2.0) / a[i - 1];
850 b[i] = d[i - 1] - h[i - 1] * b[i - 1] / a[i - 1];
851 c[i] = -h[i - 1] * c[i - 1] / a[i - 1];
857 for (i = npoints - 2; i > 0; --i) {
858 r[i] = -(h[i] * r[i + 1] + c[i]) / a[i];
859 s[i] = (6 * b[i] - h[i] * s[i + 1]) / a[i];
863 d2z[npoints - 1] = (6 * d[npoints - 2] - h[0] * s[1]
864 - h[npoints - 1] * s[npoints - 2])
865 / (h[0] * r[1] + h[npoints - 1] * r[npoints - 2]
866 + 2 * (h[npoints - 2] + h[0]));
867 for (i = 1; i < npoints - 1; ++i) {
868 d2z[i] = r[i] * d2z[npoints - 1] + s[i];
870 d2z[npoints] = d2z[1];
873 for (i = 1; i < npoints; ++i) {
874 dz[i] = deltaz[i] - h[i] * (2 * d2z[i] + d2z[i + 1]) / 6;
875 d3z[i] = h[i] ? (d2z[i + 1] - d2z[i]) / h[i] : 0;
877 } /* end PeriodicSpline */
880 /*----------------------------------------------------------------------------
881 | Routine: NaturalEndSpline (h, z, dz, d2z, d3z, npoints)
883 | Results: This routine solves for the cubic polynomial to fit a spline
884 | curve the the points specified by the list of values. The
885 | alogrithms for this curve are from the `Spline Curve
886 | Techniques' paper cited above.
887 *----------------------------------------------------------------------------*/
890 NaturalEndSpline(float h[], /* parameterization */
891 int z[], /* Point list */
892 float dz[], /* to return the 1st derivative */
893 float d2z[], /* 2nd derivative */
894 float d3z[], /* 3rd derivative */
895 int npoints) /* number of valid points */
898 float deltaz[MAXPOINTS], a[MAXPOINTS], b[MAXPOINTS];
902 for (i = 1; i < npoints; ++i) {
903 deltaz[i] = h[i] ? ((double) (z[i + 1] - z[i])) / h[i] : 0;
905 deltaz[0] = deltaz[npoints - 1];
908 for (i = 1; i < npoints - 1; ++i) {
909 d[i] = deltaz[i + 1] - deltaz[i];
911 d[0] = deltaz[1] - deltaz[0];
914 a[0] = 2 * (h[2] + h[1]);
916 for (i = 1; i < npoints - 2; ++i) {
917 a[i] = 2 * (h[i + 1] + h[i + 2]) -
918 pow((double) h[i + 1], (double) 2.0) / a[i - 1];
919 b[i] = d[i + 1] - h[i + 1] * b[i - 1] / a[i - 1];
923 d2z[npoints] = d2z[1] = 0;
924 for (i = npoints - 1; i > 1; --i) {
925 d2z[i] = (6 * b[i - 2] - h[i] * d2z[i + 1]) / a[i - 2];
929 for (i = 1; i < npoints; ++i) {
930 dz[i] = deltaz[i] - h[i] * (2 * d2z[i] + d2z[i + 1]) / 6;
931 d3z[i] = h[i] ? (d2z[i + 1] - d2z[i]) / h[i] : 0;
933 } /* end NaturalEndSpline */
936 /*----------------------------------------------------------------------------*
937 | Routine: change (x_position, y_position, visible_flag)
939 | Results: As HGtline passes from the invisible to visible (or vice
940 | versa) portion of a line, change is called to either draw
941 | the line, or initialize the beginning of the next one.
942 | Change calls line to draw segments if visible_flag is set
943 | (which means we're leaving a visible area).
944 *----------------------------------------------------------------------------*/
947 change(register int x,
951 static int length = 0;
953 if (vis) { /* leaving a visible area, draw it. */
955 if (length++ > LINELENGTH) {
959 } else { /* otherwise, we're entering one, remember */
966 /*----------------------------------------------------------------------------
967 | Routine: HGtline (xstart, ystart, xend, yend)
969 | Results: Draws a line from current position to (x1,y1) using line(x1,
970 | y1) to place individual segments of dotted or dashed lines.
971 *----------------------------------------------------------------------------*/
977 register int x0 = lastx;
978 register int y0 = lasty;
981 register int oldcoord;
983 register int visible;
987 register int dotcounter;
989 if (linmod == SOLID) {
994 /* for handling different resolutions */
995 dotcounter = linmod << dotshifter;
999 if ((dx = x1 - x0) < 0) {
1003 if ((dy = y1 - y0) < 0) {
1013 if ((x0 & dotcounter) && !visible) {
1016 } else if (visible && !(x0 & dotcounter)) {
1017 change(x0 - xinc, oldcoord, 1);
1032 if ((y0 & dotcounter) && !visible) {
1035 } else if (visible && !(y0 & dotcounter)) {
1036 change(oldcoord, y0 - yinc, 1);