home *** CD-ROM | disk | FTP | other *** search
/ Amiga Elysian Archive / AmigaElysianArchive.iso / prog / c / post17s.lha / postgraph.c < prev    next >
C/C++ Source or Header  |  1992-03-08  |  54KB  |  1,718 lines
  1. /* PostScript interpreter file "postgraph.c" - graphics routines
  2.  * (C) Adrian Aylward 1989, 1992
  3.  * V1.6 First source release
  4.  * V1.7 Fix stroking lines of zero length
  5.  */
  6.  
  7. # include "post.h"
  8.  
  9. /* Routines */
  10.  
  11. extern void checkclipsize(int size, int end);
  12. extern void setlinesize(int len);
  13. extern void flattencurve(struct point *ppoint, int depth);
  14. extern void strokesub(int pt1, int pt2);
  15. extern void strokeparm(struct point *ppoint1, struct point *ppoint2,
  16.                        float *len);
  17. extern void strokeinit(void);
  18. extern void strokeline(struct point *ppoint1, struct point *ppoint2,
  19.                        int bjoin, int ejoin);
  20. extern void strokecap(int type, int cap);
  21. extern void clipline(struct clip *pclip);
  22. extern void clipswap(struct clip *pclip);
  23. extern void swappath(int beg, int end);
  24.  
  25. /* Initialise the graphics state */
  26.  
  27. void initgstate(void)
  28. {   struct object token, *aptr;
  29.     vmref aref;
  30.     if (page.xsize > 30000 || page.ysize > 30000 || page.yheight > 30000)
  31.         error(errlimitcheck);
  32.     gstate.dev = page;
  33.     pathsize = linesize = clipsize = 0;
  34.     halfbeg = memhbeg;
  35.     halfsize = memhlen;
  36.     halfok = gstacksize + 1;
  37.     screenok = 0;
  38.     token.type = 0;
  39.     token.flags = 0;
  40.     token.length = 0;
  41.     token.value.ival = 0;
  42.     gstate.font = token;
  43.     gstate.clipbeg = 0;
  44.     aref = arrayalloc(9);
  45.     aptr = vmaptr(aref);
  46.     nametoken(&aptr[0], "dup", -1, flagexec);
  47.     nametoken(&aptr[1], "mul", -1, flagexec);
  48.     nametoken(&aptr[2], "exch", -1, flagexec);
  49.     aptr[3] = aptr[0];
  50.     aptr[4] = aptr[1];
  51.     nametoken(&aptr[5], "add", -1, flagexec);
  52.     token.type = typereal;
  53.     token.flags = 0;
  54.     token.length = 0;
  55.     token.value.rval = 1.0;
  56.     aptr[6] = token;
  57.     aptr[7] = aptr[2];
  58.     nametoken(&aptr[8], "sub", -1, flagexec);
  59.     token.type = typearray;
  60.     token.flags = flagexec;
  61.     token.length = 9;
  62.     token.value.vref = aref;
  63.     bind(&token, 0);
  64.     if (gstate.dev.depth == 4)
  65.     {   gstate.screendepth = 4;
  66.         gstate.screenangle[0] = 105.0;
  67.         gstate.screenangle[1] =  75.0;
  68.         gstate.screenangle[2] =  95.0;
  69.         gstate.screenangle[3] =  45.0;
  70.         gstate.screenfreq[0] = gstate.screenfreq[1] =
  71.             gstate.screenfreq[2] = gstate.screenfreq[3] = 60.0;
  72.         gstate.screenfunc[0] = gstate.screenfunc[1]  =
  73.             gstate.screenfunc[2] = gstate.screenfunc[3] = token;
  74.     }
  75.     else
  76.     {   gstate.screendepth = 1;
  77.         gstate.screenangle[0] = 45.0;
  78.         gstate.screenfreq[0] = 60.0;
  79.         gstate.screenfunc[0] = token;
  80.     }
  81.     gstate.transdepth = 1;
  82.     token.length = 0;
  83.     gstate.transfer[0] = token;
  84.     gstate.ucr = token;
  85.     gstate.gcr = token;
  86.     gstate.flatness = 1.0;
  87.     gstate.cacheflag = 0;
  88.     gstate.nullflag = 0;
  89.     gnest = 0;
  90.     gstack = vmallocv(sizeof (struct gstate) * (gstacksize + 1));
  91.     setuphalf();
  92.     initgraphics();
  93.     gsave();
  94.     vmstack[0].gnest = 1;
  95. }
  96.  
  97. /* Initialise the graphics */
  98.  
  99. void initgraphics(void)
  100. {   struct object token;
  101.     initctm(gstate.ctm);
  102.     gstate.pathbeg = gstate.pathend = gstate.clipbeg;
  103.     cliplength(0);
  104.     gstate.clipflag = 0;
  105.     gstate.linewidth = 1.0;
  106.     gstate.linecap = 0;
  107.     gstate.linejoin = 0;
  108.     gstate.mitrelimit = 10.0;
  109.     gstate.mitresin = 0.198997;
  110.     gstate.dashoffset = 0.0;
  111.     token.type = typearray;
  112.     token.flags = 0;
  113.     token.length = 0;
  114.     token.value.vref = 0;
  115.     gstate.dasharray = token;
  116.     gstate.gray = 0.0;
  117.     gstate.rgb[0] = gstate.rgb[1] = gstate.rgb[2] = 0.0;
  118.     gstate.rgbw[0] = gstate.rgbw[1] =
  119.         gstate.rgbw[2] = gstate.rgbw[3] = 0.0;
  120.     gstate.shadeok = 0;
  121. }
  122.  
  123. /* Initialise a matrix to the default ctm */
  124.  
  125. void initctm(float newctm[])
  126. {   newctm[0] = gstate.dev.xden / 72.0;
  127.     newctm[1] = 0.0;
  128.     newctm[2] = 0.0;
  129.     newctm[3] = gstate.dev.yden / 72.0;
  130.     newctm[4] = -gstate.dev.xoff;
  131.     newctm[5] = -gstate.dev.yoff;
  132.     if (gstate.dev.ydir < 0)
  133.     {   newctm[3] = -newctm[3];
  134.         newctm[5] = (gstate.dev.yheight + gstate.dev.yoff);
  135.     }
  136. }
  137.  
  138. /* Change device page */
  139.  
  140. void setdevice(struct device *ppage)
  141. {   struct gstate *pgstate;
  142.     int i;
  143.  
  144.     /* Check whether the densities or depth have changed; install the page */
  145.  
  146.     if (ppage->depth != page.depth ||
  147.         ppage->xden != page.xden ||
  148.         ppage->yden != page.yden ||
  149.         ppage->ydir != page.ydir)
  150.     {   halfok = gstacksize + 1;
  151.         screenok = 0;
  152.     }
  153.     page = *ppage;
  154.  
  155.     /* Update all the page devices on the gstate stack */
  156.  
  157.     i = gnest;
  158.     pgstate = &gstack[0];
  159.     for (;;)
  160.     {   if (i == 0) pgstate = &gstate;
  161.         if (!pgstate->cacheflag && !pgstate->nullflag)
  162.         {   if (page.depth != pgstate->dev.depth) pgstate->shadeok = 0;
  163.             pgstate->dev = page;
  164.         }
  165.         if (i == 0) break;
  166.         i--;
  167.         pgstate++;
  168.     }
  169.  
  170.     /* Reinitialise the CTM of the bottommost graphics state */
  171.  
  172.     initctm(gstack[0].ctm);
  173. }
  174.  
  175. /* Check the image memory size */
  176.  
  177. void checkimagesize(int len)
  178. {   if (len > memilen)
  179.     {   memfree(memibeg, memilen);
  180.         memilen = 0;
  181.         memibeg = memalloc(len);
  182.         if (memibeg == NULL) error(errmemoryallocation);
  183.         memilen = len;
  184.     }
  185. }
  186.  
  187. /* Check the line array size */
  188.  
  189. void checklinesize(int size)
  190. {   int len, segs;
  191.     if (size > linesize)
  192.     {   len = (sizeof (struct line) +
  193.                sizeof (struct line *) +
  194.                sizeof (struct lineseg) * 2) * size;
  195.         segs = (len + memlmin - 1) / memlmin;
  196.         if (segs > memlsegmax) error(errlimitcheck);
  197.         setlinesize(memlmin * segs);
  198.     }
  199. }
  200.  
  201. /* Check the clip array size, relocating the clip pointers */
  202.  
  203. void checkclipsize(int size, int end)
  204. {   struct clip *pclip, **pcptr;
  205.     int len, segs, oldsize;
  206.     if (size > clipsize)
  207.     {   oldsize = clipsize;
  208.         len = (sizeof (struct clip) +
  209.                sizeof (struct clip *)) * size;
  210.         segs = (len + memlmin - 1) / memlmin;
  211.         if (segs > memlsegmax) error(errlimitcheck);
  212.         pclip = cliparray;
  213.         setlinesize(memlmin * segs);
  214.         pcptr = (void *) (cliparray + oldsize);
  215.         while (end--)
  216.             clipptr[end] = cliparray + (pcptr[end] - pclip);
  217.     }
  218. }
  219.  
  220. /* Set the line and clip array memory size */
  221.  
  222. void setlinesize(int len)
  223. {   void *beg;
  224.     beg = memalloc(len);
  225.     if (beg == NULL) error(errmemoryallocation);
  226.     memcpy((char *) beg, (char *) memlbeg, memllen);
  227.     memfree(memlbeg, memllen);
  228.     memlbeg = beg;
  229.     memllen = len;
  230.     linesize = memllen / (sizeof (struct line) +
  231.                           sizeof (struct line *) +
  232.                           sizeof (struct lineseg) * 2);
  233.     linearray = memlbeg;
  234.     lineptr = (void *) (linearray + linesize);
  235.     linesegarray = (void *) (lineptr + linesize);
  236.     clipsize = memllen / (sizeof (struct clip) +
  237.                           sizeof (struct clip *));
  238.     cliparray = memlbeg;
  239.     clipptr = (void *) (cliparray + clipsize);
  240. }
  241.  
  242. /* Check the path array size */
  243.  
  244. void checkpathsize(int size)
  245. {   void *beg;
  246.     int len, segs;
  247.     if (size > pathsize)
  248.     {   len = sizeof (struct point) * size;
  249.         segs = (len + mempmin - 1) / mempmin;
  250.         if (segs > mempsegmax) error(errlimitcheck);
  251.         len = mempmin * segs;
  252.         beg = memalloc(len);
  253.         if (beg == NULL) error(errmemoryallocation);
  254.         memcpy((char *) beg, (char *) mempbeg, memplen);
  255.         memfree(mempbeg, memplen);
  256.         mempbeg = beg;
  257.         memplen = len;
  258.         pathsize = len / sizeof (struct point);
  259.         patharray = mempbeg;
  260.     }
  261. }
  262.  
  263. /* Shuffle the path up or down to change the clip path length */
  264.  
  265. void cliplength(int cliplen)
  266. {   struct point *ppoint1, *ppoint2;
  267.     int pathlen, len;
  268.     len = pathlen = gstate.pathend - gstate.pathbeg;
  269.     checkpathsize(gstate.clipbeg + cliplen + pathlen);
  270.     ppoint1 = &patharray[gstate.clipbeg + cliplen];
  271.     ppoint2 = &patharray[gstate.pathbeg];
  272.     if      (ppoint1 > ppoint2)
  273.     {   ppoint1 += pathlen;
  274.         ppoint2 += pathlen;
  275.         while (len--) *--ppoint1 = *--ppoint2;
  276.     }
  277.     else if (ppoint1 < ppoint2)
  278.         while (len--) *ppoint1++ = *ppoint2++;
  279.     gstate.pathbeg = gstate.clipbeg + cliplen;
  280.     gstate.pathend = gstate.pathbeg + pathlen;
  281. }
  282.  
  283. /* Get the clipping path */
  284.  
  285. void clippath(void)
  286. {   struct point point, *ppoint1, *ppoint2;
  287.     int len, l;
  288.     if (gstate.clipflag)
  289.         len = gstate.pathbeg - gstate.clipbeg;
  290.     else
  291.         len = 5;
  292.     checkpathsize(gstate.pathbeg + len);
  293.     ppoint1 = &patharray[gstate.pathbeg];
  294.     if (gstate.clipflag)
  295.     {   ppoint2 = &patharray[gstate.clipbeg];
  296.         l = len;
  297.         while (l--) *ppoint1++ = *ppoint2++;
  298.     }
  299.     else
  300.     {   point.type = ptmove;
  301.         point.x = 0.0;
  302.         point.y = 0.0;
  303.         ppoint1[0] = point;
  304.         point.type = ptclosex;
  305.         ppoint1[4] = point;
  306.         point.type = ptline;
  307.         point.x = gstate.dev.xsize;
  308.         ppoint1[1] = point;
  309.         point.y = gstate.dev.yheight;
  310.         ppoint1[2] = point;
  311.         point.x = 0.0;
  312.         ppoint1[3] = point;
  313.     }
  314.     gstate.pathend = gstate.pathbeg + len;
  315. }
  316.  
  317. /* Save the graphics state */
  318.  
  319. void gsave(void)
  320. {   struct point *ppoint1, *ppoint2;
  321.     int i;
  322.     if (istate.flags & intgraph) error(errundefined);
  323.     if (gnest == gstacksize) error(errlimitcheck);
  324.     i = gstate.pathend - gstate.clipbeg;
  325.     checkpathsize(gstate.pathend + i);
  326.     gstack[gnest++] = gstate;
  327.     if (i != 0)
  328.     {   ppoint1 = &patharray[gstate.clipbeg];
  329.         ppoint2 = &patharray[gstate.pathend];
  330.         gstate.clipbeg += i;
  331.         gstate.pathbeg += i;
  332.         gstate.pathend += i;
  333.         while (i--) *ppoint2++ = *ppoint1++;
  334.     }
  335. }
  336.  
  337. /* Restore the graphics state */
  338.  
  339. void grest(void)
  340. {   if (istate.flags & intgraph) error(errundefined);
  341.     if (gnest > istate.gbase &&
  342.         gnest > vmstack[vmnest].gnest)
  343.     {   gstate = gstack[--gnest];
  344.         if (gnest <= halfok)
  345.         {   halfok = gstacksize + 1;
  346.             setuphalf();
  347.         }
  348.     }
  349.     screenok = 0;
  350. }
  351.  
  352. /* Restore the graphics state to the previous save */
  353.  
  354. void grestall(void)
  355. {   int nest;
  356.     if (istate.flags & intgraph) error(errundefined);
  357.     nest = vmstack[vmnest].gnest;
  358.     if (nest > istate.gbase)
  359.     {   gnest = nest;
  360.         gstate = gstack[--gnest];
  361.         gsave();
  362.         if (gnest <= halfok)
  363.         {   halfok = gstacksize + 1;
  364.             setuphalf();
  365.         }
  366.         screenok = 0;
  367.     }
  368. }
  369.  
  370. /* Get a matrix */
  371.  
  372. void getmatrix(vmref aref, float *matrix)
  373. {   struct object *aptr;
  374.     int i;
  375.     i = 6;
  376.     aptr = vmaptr(aref);
  377.     while (i--)
  378.     {   if      (aptr->type == typeint)
  379.             *matrix = aptr->value.ival;
  380.         else if (aptr->type == typereal)
  381.             *matrix = aptr->value.rval;
  382.         else
  383.             error(errtypecheck);
  384.         aptr++;
  385.         matrix++;
  386.     }
  387. }
  388.  
  389. /* Put a matrix */
  390.  
  391. void putmatrix(vmref aref, float *matrix)
  392. {   struct object token, *aptr;
  393.     int i;
  394.     token.type = typereal;
  395.     token.flags = 0;
  396.     token.length = 0;
  397.     i = 6;
  398.     aptr = vmaptr(aref);
  399.     while (i--)
  400.     {   token.value.rval = *matrix++;
  401.         *aptr++ = token;
  402.     }
  403. }
  404.  
  405. /* Multiply two matrices */
  406.  
  407. void multiplymatrix(float *mat1, float *mat2, float *mat3)
  408. {   mat1[0] = mat2[0] * mat3[0] + mat2[1] * mat3[2];
  409.     mat1[1] = mat2[0] * mat3[1] + mat2[1] * mat3[3];
  410.     mat1[2] = mat2[2] * mat3[0] + mat2[3] * mat3[2];
  411.     mat1[3] = mat2[2] * mat3[1] + mat2[3] * mat3[3];
  412.     mat1[4] = mat2[4] * mat3[0] + mat2[5] * mat3[2] + mat3[4];
  413.     mat1[5] = mat2[4] * mat3[1] + mat2[5] * mat3[3] + mat3[5];
  414. }
  415.  
  416. /* Invert a matrix */
  417.  
  418. void invertmatrix(float *mat1, float *mat2)
  419. {   float d = mat2[0] * mat2[3] - mat2[1] * mat2[2];
  420.     mat1[0] =  mat2[3] / d;
  421.     mat1[1] = -mat2[1] / d;
  422.     mat1[2] = -mat2[2] / d;
  423.     mat1[3] =  mat2[0] / d;
  424.     mat1[4] = (mat2[2] * mat2[5] - mat2[3] * mat2[4]) / d;
  425.     mat1[5] = (mat2[1] * mat2[4] - mat2[0] * mat2[5]) / d;
  426. }
  427.  
  428. /* Transform a point by a matrix */
  429.  
  430. void transform(struct point *ppoint, float *matrix)
  431. {   float x, y;
  432.     x = ppoint->x;
  433.     y = ppoint->y;
  434.     ppoint->x = x * matrix[0] + y * matrix[2] + matrix[4];
  435.     ppoint->y = x * matrix[1] + y * matrix[3] + matrix[5];
  436. }
  437.  
  438. /* Delta transform a point by a matrix */
  439.  
  440. void dtransform(struct point *ppoint, float *matrix)
  441. {   float x, y;
  442.     x = ppoint->x;
  443.     y = ppoint->y;
  444.     ppoint->x = x * matrix[0] + y * matrix[2];
  445.     ppoint->y = x * matrix[1] + y * matrix[3];
  446. }
  447.  
  448. /* Inverse transform a point by a matrix */
  449.  
  450. void itransform(struct point *ppoint, float *matrix)
  451. {   float x, y, d;
  452.     x = ppoint->x;
  453.     y = ppoint->y;
  454.     d = matrix[0] * matrix[3] - matrix[1] * matrix[2];
  455.     ppoint->x = (x * matrix[3] - y * matrix[2] +
  456.         matrix[5] * matrix[2] - matrix[4] * matrix[3]) / d;
  457.     ppoint->y = (y * matrix[0] - x * matrix[1] +
  458.         matrix[4] * matrix[1] - matrix[5] * matrix[0]) / d;
  459. }
  460.  
  461. /* Inverse delta transform a point by a matrix */
  462.  
  463. void idtransform(struct point *ppoint, float *matrix)
  464. {   float x, y, d;
  465.     x = ppoint->x;
  466.     y = ppoint->y;
  467.     d = matrix[0] * matrix[3] - matrix[1] * matrix[2];
  468.     ppoint->x = (x * matrix[3] - y * matrix[2]) / d;
  469.     ppoint->y = (y * matrix[0] - x * matrix[1]) / d;
  470. }
  471.  
  472. /* Generate a circular arc */
  473.  
  474. void arc(int dir, float radaa[3],
  475.          struct point *centre, struct point *beg, struct point *end)
  476. {   struct point point[3], *ppoint;
  477.     float ang1, ang2, angd, angm, radius, radm, rh, cos1, cos2, sin1, sin2;
  478.     int num;
  479.  
  480.     /* Find out which direction, and the angle of the arc */
  481.  
  482.     radius = radaa[0];
  483.     ang1 = fmod(radaa[1], twopi);
  484.     ang2 = fmod(radaa[2], twopi);
  485.     if      (dir == 0)
  486.     {  if (fabs(ang2 - ang1) > pi)
  487.            if (ang2 > ang1)
  488.                ang1 += twopi;
  489.            else
  490.                ang2 += twopi;
  491.     }
  492.     else if (dir > 0)
  493.     {  if (ang2 < ang1 + pdelta) ang2 += twopi;
  494.     }
  495.     else
  496.        if (ang2 > ang1 + pdelta) ang1 += twopi;
  497.     angd = ang2 - ang1;
  498.  
  499.     /* Determine (a rough upper bound of) the radius, in pixels */
  500.  
  501.     radm = gstate.ctm[0];
  502.     if (gstate.ctm[1] > radm) radm = gstate.ctm[1];
  503.     if (gstate.ctm[2] > radm) radm = gstate.ctm[2];
  504.     if (gstate.ctm[3] > radm) radm = gstate.ctm[3];
  505.     radm *= radaa[0];
  506.  
  507.     /* Determine the number of Bezier curves needed to approximate the arc */
  508.  
  509.     if      (radm <= 27.0)
  510.         angm = pi       + .0001;
  511.     else if (radm <= 1834.0)
  512.         angm = pi / 2.0 + .0001;
  513.     else if (radm <= 20953.0)
  514.         angm = pi / 3.0 + .0001;
  515.     else if (radm <= 117778.0)
  516.         angm = pi / 4.0 + .0001;
  517.     else
  518.         angm = pi / 8.0 + .0001;
  519.     num = (int) ceil(fabs(angd) / angm);
  520.     angd = angd / num;
  521.  
  522.     /* Generate a move or line from the current point */
  523.  
  524.     cos2 = cos(ang1);
  525.     sin2 = sin(ang1);
  526.     point[2].type = ptmove;
  527.     point[2].x = centre->x + radius * cos2;
  528.     point[2].y = centre->y + radius * sin2;
  529.     if (dir == 0) *beg = point[2];
  530.     transform(&point[2], gstate.ctm);
  531.     pathend = gstate.pathend;
  532.     ppoint = &patharray[pathend];
  533.     if (gstate.pathbeg == pathend ||
  534.         fabs(point[2].x - (ppoint - 1)->x) >= 0.2 ||
  535.         fabs(point[2].y - (ppoint - 1)->y) >= 0.2)
  536.     {   if (gstate.pathbeg != pathend) point[2].type = ptline;
  537.         checkpathsize(pathend + 1);
  538.         patharray[pathend++] = point[2];
  539.     }
  540.     point[0].type = ptcurve;
  541.     point[1].type = ptcurve;
  542.     point[2].type = ptcurve;
  543.  
  544.     /* Loop to generate the curves */
  545.  
  546.     while (num--)
  547.     {   ang2 = ang1 + angd;
  548.         cos1 = cos2;
  549.         sin1 = sin2;
  550.         cos2 = cos(ang2);
  551.         sin2 = sin(ang2);
  552.  
  553.         /* We place the intermediate control points on the tangents at the
  554.          * endpoints (so the gradient is correct) and at a height 4/3 the
  555.          * height of the midpoint of the arc (so the midpoint of the curve
  556.          * is the same as the midpoint of the arc) */
  557.  
  558.         rh = radius * f43 * tan(angd / 4.0);
  559.         point[0].x = -rh * sin1;
  560.         point[0].y =  rh * cos1;
  561.         point[1].x =  rh * sin2;
  562.         point[1].y = -rh * cos2;
  563.         dtransform(&point[0], gstate.ctm);
  564.         dtransform(&point[1], gstate.ctm);
  565.         point[0].x += point[2].x;
  566.         point[0].y += point[2].y;
  567.  
  568.         point[2].x = centre->x + radius * cos2;
  569.         point[2].y = centre->y + radius * sin2;
  570.         if (dir == 0) *end = point[2];
  571.         transform(&point[2], gstate.ctm);
  572.         point[1].x += point[2].x;
  573.         point[1].y += point[2].y;
  574.         checkpathsize(pathend + 3);
  575.         ppoint = &patharray[pathend];
  576.         ppoint[0] = point[0];
  577.         ppoint[1] = point[1];
  578.         ppoint[2] = point[2];
  579.         pathend += 3;
  580.         ang1 = ang2;
  581.     }
  582.  
  583.     gstate.pathend = pathend;
  584. }
  585.  
  586. /* Close the current path */
  587.  
  588. void closepath(int type)
  589. {   struct point point, *ppoint;
  590.     if (gstate.pathbeg == gstate.pathend) return;
  591.     ppoint = &patharray[gstate.pathend - 1];
  592.  
  593.     /* If it is closed already, make the close explicit if necessary */
  594.  
  595.     if (ppoint->type == ptclosex)
  596.         return;
  597.     if (ppoint->type == ptclosei)
  598.     {   ppoint->type = type;
  599.         return;
  600.     }
  601.     if (ppoint->type == ptmove)
  602.         return;
  603.  
  604.     /* Scan back to the beginning of the sub path to find the coordinates to
  605.      * close it to */
  606.  
  607.     for (;;)
  608.     {   point = *ppoint;
  609.         if (point.type == ptclosex ||
  610.             point.type == ptclosei ||
  611.             point.type == ptmove)
  612.             break;
  613.         ppoint--;
  614.     }
  615.  
  616.     /* Append a close */
  617.  
  618.     point.type = type;
  619.     checkpathsize(gstate.pathend + 1);
  620.     patharray[gstate.pathend++] = point;
  621.     return;
  622. }
  623.  
  624. /* Flatten the current path */
  625.  
  626. void flattenpath(void)
  627. {   struct point point[4], *ppoint1, *ppoint2;
  628.     int len, num;
  629.  
  630.     len = gstate.pathend - gstate.pathbeg;
  631.  
  632.     /* Skip all elements before the first curve */
  633.  
  634.     ppoint1 = &patharray[gstate.pathbeg];
  635.     for (;;)
  636.     {   if (len == 0) return;
  637.         if (ppoint1->type == ptcurve) break;
  638.         ppoint1++;
  639.         len--;
  640.     }
  641.  
  642.     num = len;
  643.     pathbeg = pathend = gstate.pathend;
  644.  
  645.     /* Flatten curves, copying all points into workspace at the end of the
  646.      * path array */
  647.  
  648.     for (;;)
  649.     {   if (len == 0) break;
  650.         ppoint1 = &patharray[pathbeg - len];
  651.         point[1] = ppoint1[0];
  652.         if (point[1].type == ptcurve)
  653.         {   point[0] = ppoint1[-1];
  654.             point[2] = ppoint1[1];
  655.             point[3] = ppoint1[2];
  656.             flattencurve(point, 0);
  657.             len -= 3;
  658.         }
  659.         else
  660.         {   checkpathsize(pathend + 1);
  661.             patharray[pathend++] = point[1];
  662.             len--;
  663.         }
  664.     }
  665.  
  666.     /* Copy the workspace back to the path */
  667.  
  668.     ppoint1 = &patharray[gstate.pathend - num];
  669.     ppoint2 = &patharray[pathbeg];
  670.     len = pathend - pathbeg;
  671.     gstate.pathend += len - num;
  672.     while (len--) *ppoint1++ = *ppoint2++;
  673. }
  674.  
  675. /* Flatten a curve */
  676.  
  677. void flattencurve(struct point *ppoint, int depth)
  678. {   struct point point, curves[7];
  679.     float f, g, h, a, b, c;
  680.  
  681.     /* Find the flatness of the curve.  As it lies within the convex hull
  682.      * of its control points we just find the maximum distance of the
  683.      * intermediate control points from the straight line joining the ends */
  684.  
  685.     a = ppoint[3].y - ppoint[0].y;
  686.     b = ppoint[0].x - ppoint[3].x;
  687.     c = ppoint[3].x * ppoint[0].y - ppoint[0].x * ppoint[3].y;
  688.     f = a * ppoint[1].x + b * ppoint[1].y + c;
  689.     f = f * f;
  690.     g = a * ppoint[2].x + b * ppoint[2].y + c;
  691.     g = g * g;
  692.     h = gstate.flatness * gstate.flatness * (a * a + b * b);
  693.  
  694.     /* If the curve is not flat enough bisect it and flatten the halves */
  695.  
  696.     if (f > h || g > h)
  697.     {   point.type = ptcurve;
  698.         curves[0] = ppoint[0];
  699.         point.x = ppoint[0].x * f12 + ppoint[1].x * f12;
  700.         point.y = ppoint[0].y * f12 + ppoint[1].y * f12;
  701.         curves[1] = point;
  702.         point.x = ppoint[0].x * f14 + ppoint[1].x * f12 + ppoint[2].x * f14;
  703.         point.y = ppoint[0].y * f14 + ppoint[1].y * f12 + ppoint[2].y * f14;
  704.         curves[2] = point;
  705.         point.x = ppoint[0].x * f18 + ppoint[1].x * f38 + ppoint[2].x * f38
  706.                 + ppoint[3].x * f18;
  707.         point.y = ppoint[0].y * f18 + ppoint[1].y * f38 + ppoint[2].y * f38
  708.                 + ppoint[3].y * f18;
  709.         curves[3] = point;
  710.         point.x = ppoint[1].x * f14 + ppoint[2].x * f12 + ppoint[3].x * f14;
  711.         point.y = ppoint[1].y * f14 + ppoint[2].y * f12 + ppoint[3].y * f14;
  712.         curves[4] = point;
  713.         point.x = ppoint[2].x * f12 + ppoint[3].x * f12;
  714.         point.y = ppoint[2].y * f12 + ppoint[3].y * f12;
  715.         curves[5] = point;
  716.         curves[6] = ppoint[3];
  717.         if (depth == maxdepth) error(errlimitcheck);
  718.         flattencurve(&curves[0], depth + 1);
  719.         flattencurve(&curves[3], depth + 1);
  720.     }
  721.  
  722.     /* Otherwise make it a straight line */
  723.  
  724.     else
  725.     {   point = ppoint[3];
  726.         point.type = ptline;
  727.         checkpathsize(pathend + 1);
  728.         patharray[pathend++] = point;
  729.     }
  730. }
  731.  
  732. /* Create a stroke path; return it or fill it */
  733.  
  734. void strokepath(int fillflag)
  735. {   struct point *ppoint1, *ppoint2;
  736.     int pt1, pt2, pt3, len, lev;
  737.  
  738.     if (fillflag)
  739.         lev = flushlevel(-1);
  740.  
  741.     /* Loop through the path */
  742.  
  743.     pt1 = gstate.pathbeg;
  744.     pt3 = gstate.pathend;
  745.     pathbeg = pathend = gstate.pathend;
  746.  
  747.     while (pt1 < pt3)
  748.     {   ppoint1 = &patharray[pt1];
  749.         ppoint2 = ppoint1;
  750.         pt2 = pt1;
  751.  
  752.         /* Scan to locate the end of the subpath */
  753.  
  754.         while (pt2 < pt3)
  755.         {   pt2++;
  756.             if (ppoint2->type == ptclosei || ppoint2->type == ptclosex)
  757.                 break;
  758.             ppoint2++;
  759.         }
  760.  
  761.         /* If the subpath does not begin with a move, include the previous
  762.          * point - which must have been a close.  Stroke the subpath. N.B.
  763.          * this may invalidate the pointers to the path array */
  764.  
  765.         if (ppoint1->type != ptmove) pt1--;
  766.         strokesub(pt1, pt2);
  767.         pt1 = pt2;
  768.  
  769.         /* If we are filling, do it now and discard the stroke path */
  770.  
  771.         if (fillflag)
  772.         {   fill(pathbeg, pathend, -1);
  773.             pathend = pathbeg;
  774.         }
  775.     }
  776.  
  777.     /* If we are not filling, copy the stroke path to the current path */
  778.  
  779.     if (!fillflag)
  780.     {   len = pathend - pathbeg;
  781.         gstate.pathend = gstate.pathbeg + len;
  782.         ppoint1 = &patharray[gstate.pathbeg];
  783.         ppoint2 = &patharray[pathbeg];
  784.         while (len--) *ppoint1++ = *ppoint2++;
  785.     }
  786.     else
  787.         flushlevel(lev);
  788. }
  789.  
  790. /* Stroke a subpath */
  791.  
  792. void strokesub(int pt1, int pt2)
  793. {   struct point *ppoint1, *ppoint2, *ppoint3;
  794.     float length;
  795.     int type, bjoin, ejoin, sjoin;
  796.  
  797.     if (pt1 + 1 >= pt2) return;
  798.  
  799.     ppoint1 = &patharray[pt1];
  800.     ppoint2 = &patharray[pt2 - 1];
  801.     type = ppoint2->type;
  802.  
  803.     /* If the last line is an implicit close we do not stroke it */
  804.  
  805.     if (type == ptclosei)
  806.     {   ppoint2--;
  807.         pt2--;
  808.         if (pt1 + 1 >= pt2) return;
  809.     }
  810.  
  811.     /* Strip any zero length lines from the end of the subpath */
  812.  
  813.     ppoint3 = ppoint2;
  814.     for (;;)
  815.     {   ppoint3--;
  816.         if (ppoint3->x != ppoint2->x || ppoint3->y != ppoint2->y)
  817.             break;
  818.         pt2--;
  819.         if (pt1 + 1 >= pt2) return;
  820.     }
  821.  
  822.     /* If the path is explicitly closed, then the beginning and end are
  823.      * joined. We must then set the direction of the previous line so we
  824.      * can make the joint */
  825.  
  826.     sjoin = -1;
  827.     if (type == ptclosex)
  828.     {   sjoin = gstate.linejoin;
  829.         strokeparm(ppoint3, ppoint1, &length);
  830.     }
  831.  
  832.     strokeinit();
  833.  
  834.     /* Loop to stroke the lines of the subpath. Skip lines of zero length */
  835.  
  836.     bjoin = sjoin;
  837.     ejoin = gstate.linejoin;
  838.     for (;;)
  839.     {   if (pt1 + 1 >= pt2) return;
  840.         if (pt1 + 2 >= pt2) ejoin = sjoin;
  841.         ppoint1 = &patharray[pt1];
  842.         ppoint2 = ppoint1 + 1;
  843.         if (ppoint1->x != ppoint2->x || ppoint1->y != ppoint2->y)
  844.         {   strokeline(ppoint1, ppoint2, bjoin, ejoin);
  845.             bjoin = ejoin;
  846.         }
  847.         pt1++;
  848.     }
  849. }
  850.  
  851. /* Static variables for line parameters */
  852.  
  853. static struct point cvpt; /* line Vector,                    device space */
  854. static struct point cupt; /* line Unit vector,               user space */
  855. static struct point crpt; /* line Right half width vector,   device space */
  856. static struct point cfpt; /* line Forward half width vector, device space */
  857. static struct point pvpt; /* values of the above for the previous line */
  858. static struct point pupt; /*    ..   */
  859. static struct point prpt; /*    ..   */
  860. static struct point cppt; /* current point */
  861. static struct point eppt; /* end point */
  862.  
  863. /* Stroke set up line parameters */
  864.  
  865. void strokeparm(struct point *ppoint1, struct point *ppoint2, float *len)
  866. {   float length, d;
  867.  
  868.     /* Save the values for the previous line */
  869.  
  870.     pvpt = cvpt;
  871.     pupt = cupt;
  872.     prpt = crpt;
  873.  
  874.     /* Inverse delta transform the line to user space.  Determine its
  875.      * length */
  876.  
  877.     cupt.x = cvpt.x = ppoint2->x - ppoint1->x;
  878.     cupt.y = cvpt.y = ppoint2->y - ppoint1->y;
  879.     idtransform(&cupt, gstate.ctm);
  880.     *len = length = sqrt(cupt.x * cupt.x + cupt.y * cupt.y);
  881.     if (length == 0.0) return;
  882.  
  883.     /* Construct a unit vector along the line */
  884.  
  885.     cupt.x /= length;
  886.     cupt.y /= length;
  887.  
  888.     /* Construct vectors along the line (forward) and across the line (right)
  889.      * of length equal to half the line width.  Then transform them back to
  890.      * device space. */
  891.  
  892.     d = gstate.linewidth / 2.0;
  893.     cfpt.x =  cupt.x * d;
  894.     cfpt.y =  cupt.y * d;
  895.     crpt.x =  cfpt.y;
  896.     crpt.y = -cfpt.x;
  897.     dtransform(&cfpt, gstate.ctm);
  898.     dtransform(&crpt, gstate.ctm);
  899. }
  900.  
  901. /* Static variables for dash lengths */
  902.  
  903. static int dashcnt, dashsub;
  904. static float dashlength;
  905.  
  906. /* Stroke first initialise our location in the dash array */
  907.  
  908. void strokeinit(void)
  909. {   float length;
  910.     dashcnt = 0;
  911.     if (gstate.dasharray.length != 0)
  912.     {   length = gstate.dashoffset;
  913.         dashsub = 0;
  914.         for (;;)
  915.         {   dashlength = gstate.dashlength[dashsub];
  916.             if (dashlength > length)
  917.             {   dashlength -= length;
  918.                 break;
  919.             }
  920.             length -= dashlength;
  921.             dashcnt++;
  922.             dashsub++;
  923.             if (dashsub == gstate.dasharray.length) dashsub = 0;
  924.         }
  925.     }
  926. }
  927.  
  928.  
  929. /* Stroke a line */
  930.  
  931. void strokeline(struct point *ppoint1, struct point *ppoint2,
  932.                 int bjoin, int ejoin)
  933. {   struct point point;
  934.     float x, y, xx, yy, h, s, c, d;
  935.     float linelen, length, segment;
  936.     int join;
  937.  
  938.     /* Set up the parameters */
  939.  
  940.     strokeparm(ppoint1, ppoint2, &length);
  941.     if (length == 0) return;
  942.     linelen = length;
  943.  
  944.     /* Start at the beginning of the line. N.B. generating the stroke
  945.      * path may cause the path array to be  reallocated, invalidating
  946.      * any pointers to it. So pick up the values of the points now. */
  947.  
  948.     join = bjoin;
  949.     cppt = *ppoint1;
  950.     eppt = *ppoint2;
  951.  
  952.     /* Loop stroking segments according to the dash pattern */
  953.  
  954.     for (;;)
  955.     {
  956.         /* Find the length remaining in the current dash */
  957.  
  958.         segment = length;
  959.         if (gstate.dasharray.length != 0)
  960.         {   if (dashlength == 0.0)
  961.             {   dashcnt++;
  962.                 dashsub++;
  963.                 if (dashsub == gstate.dasharray.length) dashsub = 0;
  964.                 dashlength = gstate.dashlength[dashsub];
  965.             }
  966.             if (dashlength >= length)
  967.             {   segment = length;
  968.                 dashlength -= length;
  969.             }
  970.             else
  971.             {   segment = dashlength;
  972.                 dashlength = 0.0;
  973.             }
  974.         }
  975.  
  976.         /* Only draw the segment if we are in a dash */
  977.  
  978.         if ((dashcnt & 1) == 0)
  979.         {   pathseg = pathend;
  980.  
  981.             /* If the line begins with a mitred or beveled join calculate the
  982.              * cross product of the previous and current line vectors; this
  983.              * is the sine of the angle between them, and tells us which side
  984.              * to make the joint on.  If we have a mitred join we must check
  985.              * the mitre limit; first we check the dot product of the unit
  986.              * vectors to see if the angle is less than a right angle; then
  987.              * we check the cross product (sine of the angle) against the
  988.              * mitre limit.  We don't make mitred joins is the angle is very
  989.              * small, as we would divide by zero. */
  990.  
  991.             if (join == 0 || join == 2)
  992.             {   s = pupt.x * cupt.y - pupt.y * cupt.x;
  993.                 if (join == 0)
  994.                 {   c = pupt.x * cupt.x + pupt.y * cupt.y;
  995.                     d = pvpt.x * cvpt.y - cvpt.x * pvpt.y;
  996.                     if ((gstate.mitrelimit > sqrt2) ?
  997.                             (c < 0.0 && fabs(s) < gstate.mitresin) :
  998.                             (c < 0.0 || fabs(s) > gstate.mitresin))
  999.                         join = 2;
  1000.                     if (fabs(d) < 0.0001)
  1001.                         join = 2;
  1002.                 }
  1003.  
  1004.                 /* Make a mitred join.  We make the mitre on one side if
  1005.                  * the angle is less than a right angle, on both if it is
  1006.                  * greater */
  1007.  
  1008.                 if (join == 0)
  1009.                 {   d = pvpt.x * cvpt.y - cvpt.x * pvpt.y;
  1010.                     h = (prpt.x * pvpt.y - prpt.y * pvpt.x) / d;
  1011.                     if (s > 0.0) h = -h;
  1012.                     x = cppt.x + cvpt.x * h;
  1013.                     y = cppt.y + cvpt.y * h;
  1014.                     h = (crpt.y * cvpt.x - crpt.x * cvpt.y) / d;
  1015.                     xx = pvpt.x * h;
  1016.                     yy = pvpt.y * h;
  1017.                     point.type = ptmove;
  1018.                     if (c < 0.0)
  1019.                     {   checkpathsize(pathend + 2);
  1020.                         point.x = x - xx;
  1021.                         point.y = y - yy;
  1022.                         patharray[pathend++] = point;
  1023.                         point.type = ptline;
  1024.                         point.x = x + xx;
  1025.                         point.y = y + yy;
  1026.                         patharray[pathend++] = point;
  1027.                     }
  1028.                     else
  1029.                     {   checkpathsize(pathend + 3);
  1030.                         if (s < 0.0)
  1031.                         {   point.x = cppt.x + crpt.x;
  1032.                             point.y = cppt.y + crpt.y; 
  1033.                             patharray[pathend++] = point;
  1034.                             point.type = ptline;
  1035.                             point.x = cppt.x - prpt.x;
  1036.                             point.y = cppt.y - prpt.y;
  1037.                             patharray[pathend++] = point;
  1038.                             point.x = x + xx;
  1039.                             point.y = y + yy;
  1040.                             patharray[pathend++] = point;
  1041.                         }
  1042.                         else
  1043.                         {   point.x = x - xx;
  1044.                             point.y = y - yy;
  1045.                             patharray[pathend++] = point;
  1046.                             point.type = ptline;
  1047.                             point.x = cppt.x + prpt.x;
  1048.                             point.y = cppt.y + prpt.y; 
  1049.                             patharray[pathend++] = point;
  1050.                             point.x = cppt.x - crpt.x;
  1051.                             point.y = cppt.y - crpt.y;
  1052.                             patharray[pathend++] = point;
  1053.                         }
  1054.                     }
  1055.                 }
  1056.  
  1057.                 /* Make a beveled join */
  1058.  
  1059.                 else
  1060.                 {   checkpathsize(pathend + 3);
  1061.                     point.type = ptmove;
  1062.                     point.x = cppt.x + crpt.x;
  1063.                     point.y = cppt.y + crpt.y;
  1064.                     patharray[pathend++] = point;
  1065.                     point.type = ptline;
  1066.                     if (s != 0.0)
  1067.                     {   point.x = cppt.x;
  1068.                         point.y = cppt.y;
  1069.                         if (s < 0.0)
  1070.                         {   point.x -= prpt.x;
  1071.                             point.y -= prpt.y;
  1072.                         }
  1073.                         else
  1074.                         {   point.x += prpt.x;
  1075.                             point.y += prpt.y;
  1076.                         }
  1077.                         patharray[pathend++] = point;
  1078.                     }
  1079.                     point.x = cppt.x - crpt.x;
  1080.                     point.y = cppt.y - crpt.y;
  1081.                     patharray[pathend++] = point;
  1082.                 }
  1083.             }
  1084.  
  1085.             else
  1086.  
  1087.                 /* Make a round join (like a round cap) or a cap */
  1088.  
  1089.                 strokecap(ptmove, (join == 1) ? 1 : gstate.linecap);
  1090.         }
  1091.  
  1092.         /* The end of the line */
  1093.  
  1094.         if (segment == length)
  1095.         {   join = ejoin;
  1096.             cppt = eppt;
  1097.         }
  1098.         else
  1099.         {   join = -1;
  1100.             s = segment / linelen;
  1101.             cppt.x += cvpt.x * s;
  1102.             cppt.y += cvpt.y * s;
  1103.         }
  1104.  
  1105.         if ((dashcnt & 1) == 0)
  1106.         {
  1107.  
  1108.             /* If the line ends with a join make a butt cap, otherwise end
  1109.              * with the line cap */
  1110.  
  1111.             strokecap(ptline, (join >= 0) ? 0 : gstate.linecap);
  1112.  
  1113.             /* Close the path */
  1114.  
  1115.             point = patharray[pathseg];
  1116.             point.type = ptclosex;
  1117.             checkpathsize(pathend + 1);
  1118.             patharray[pathend++] = point;
  1119.         }
  1120.  
  1121.         join = -1;
  1122.         length -= segment;
  1123.         if (length == 0.0) break;
  1124.     }
  1125. }
  1126.  
  1127. /* Stroke a line cap */
  1128.  
  1129. void strokecap(int type, int cap)
  1130. {   struct point points[7];
  1131.     float fx, fy, rx, ry;
  1132.  
  1133.     /* At the beginning caps face the opposite way to the end */
  1134.  
  1135.     if (type == ptmove)
  1136.     {   fx = -cfpt.x;
  1137.         fy = -cfpt.y;
  1138.         rx = -crpt.x;
  1139.         ry = -crpt.y;
  1140.     }
  1141.     else
  1142.     {   fx =  cfpt.x;
  1143.         fy =  cfpt.y;
  1144.         rx =  crpt.x;
  1145.         ry =  crpt.y;
  1146.     }
  1147.  
  1148.     points[0].type = type;
  1149.     points[0].x = cppt.x - rx;
  1150.     points[0].y = cppt.y - ry;
  1151.     points[6].type = ptline;
  1152.     points[6].x = cppt.x + rx;
  1153.     points[6].y = cppt.y + ry;
  1154.  
  1155.     /* Butt cap */
  1156.  
  1157.     if      (cap == 0)
  1158.     {   checkpathsize(pathend + 2);
  1159.         patharray[pathend++] = points[0];
  1160.         patharray[pathend++] = points[6];
  1161.     }
  1162.  
  1163.     /* Projecting square cap */
  1164.  
  1165.     else if (cap == 2)
  1166.     {   points[0].x += fx;
  1167.         points[0].y += fy;
  1168.         points[6].x += fx;
  1169.         points[6].y += fy;
  1170.         checkpathsize(pathend + 2);
  1171.         patharray[pathend++] = points[0];
  1172.         patharray[pathend++] = points[6];
  1173.     }
  1174.  
  1175.     /* Round cap.  Construct a Bezier curve approximation (in 2 sections) and
  1176.      * flatten it.  We always use two sections because they are faster to
  1177.      * construct than to flatten */
  1178.  
  1179.     else
  1180.     {   points[3].type = ptcurve;
  1181.         points[3].x = cppt.x + fx;
  1182.         points[3].y = cppt.y + fy;
  1183.         fx *= f43rt2;
  1184.         fy *= f43rt2;
  1185.         rx *= f43rt2;
  1186.         ry *= f43rt2;
  1187.         points[1] = points[0];
  1188.         points[1].x += fx;
  1189.         points[1].y += fy;
  1190.         points[2] = points[3];
  1191.         points[2].x -= rx;
  1192.         points[2].y -= ry;
  1193.         points[4] = points[3];
  1194.         points[4].x += rx;
  1195.         points[4].y += ry;
  1196.         points[5] = points[6];
  1197.         points[5].x += fx;
  1198.         points[5].y += fy;
  1199.         checkpathsize(pathend + 1);
  1200.         patharray[pathend++] = points[0];
  1201.         flattencurve(&points[0], 0);
  1202.         flattencurve(&points[3], 0);
  1203.     }
  1204. }
  1205.  
  1206. /* Make a new clipping path by intersecting it with the current path */
  1207.  
  1208. void clip(int rule)
  1209. {   struct point point, *ppoint;
  1210.     struct clip clip1, clip2, *pclip1, *pclip2, *pclipx;
  1211.     double a1, b1, c1, a2, b2, c2;
  1212.     double l1, l2, l3;
  1213.     double h11, h12, h21, h22, hh;
  1214.     int xx, yy, x1, y1;
  1215.     int count, count1, count2, step;
  1216.     int clipold, clipnew, clipmax, clipflg;
  1217.     int cdir1, cdir2, fdir1, fdir2;
  1218.  
  1219.     /* Set up the default clip path */
  1220.  
  1221.     if (!gstate.clipflag)
  1222.     {   cliplength(5);
  1223.         gstate.pathbeg = gstate.clipbeg;
  1224.         count = gstate.pathend;
  1225.         clippath();
  1226.         gstate.pathbeg = gstate.pathend;
  1227.         gstate.pathend = count;
  1228.     }
  1229.  
  1230.     /* Set up the clip array.  We convert the coordinates to fixed point,
  1231.      * with a scale factor of 256.  Then when we come to multiplying the
  1232.      * values to calculate the intersections it will fit into 48 bits or
  1233.      * so, a reasonable minimum accuracy for double precision floating
  1234.      * point */
  1235.  
  1236.     clipend = 0;
  1237.     for (count1 = gstate.clipbeg; count1 < gstate.pathend; count1++)
  1238.     {   ppoint = &patharray[count1];
  1239.         if (ppoint->type != ptmove)
  1240.         {   if (count1 < gstate.pathbeg)
  1241.             {   clip1.cdir = 1;
  1242.                 clip1.fdir = 0;
  1243.             }
  1244.             else
  1245.             {   clip1.cdir = 0;
  1246.                 clip1.fdir = 1;
  1247.             }
  1248.             clip1.flag = 0;
  1249.             clip1.swap = 0;
  1250.             clip1.x1 = floor(ppoint[-1].x * 256.0f + 0.5);
  1251.             clip1.y1 = floor(ppoint[-1].y * 256.0f + 0.5);
  1252.             clip1.x2 = floor(ppoint[0].x * 256.0f + 0.5);
  1253.             clip1.y2 = floor(ppoint[0].y * 256.0f + 0.5);
  1254.             clipline(&clip1);
  1255.         }
  1256.     }
  1257.  
  1258.     /* Split the lines whenever they intersect.  Owing to rounding errors
  1259.      * The resulting new lines are not in exactly the same place as before,
  1260.      * so we loop checking for intersections until we don't find any more
  1261.      */
  1262.  
  1263.     clipnew = 0;
  1264.     for (;;)
  1265.     {
  1266.         /* Shell sort the array in order of y1 */
  1267.  
  1268.         count = clipend;
  1269.         for (;;)
  1270.         {   count = count / 3 + 1;
  1271.             for (count1 = count; count1 < clipend; count1++)
  1272.                 for (count2 = count1 - count;
  1273.                      count2 >= 0 &&
  1274.                          clipptr[count2]->y1 > clipptr[count2 + count]->y1;
  1275.                      count2 -= count)
  1276.                 {    pclip1 = clipptr[count2];
  1277.                      clipptr[count2] = clipptr[count2 + count];
  1278.                      clipptr[count2 + count] = pclip1;
  1279.                 }
  1280.             if (count == 1) break;
  1281.         }
  1282.  
  1283.         /* Exit (with the array sorted) if we have no new lines */
  1284.  
  1285.         if (clipnew == clipend) break;
  1286.  
  1287.         /* Locate all the intersections for each line */
  1288.  
  1289.         count1 = 0;
  1290.         clipnew = clipend;
  1291.         while (count1 < clipend - 1)
  1292.         {   count2 = count1;
  1293.  
  1294.             /* We don't need to check for intersections with the new lines
  1295.              * we created by intersecting with ours */
  1296.  
  1297.             clipmax = clipend - 1;
  1298.             while (count2 < clipmax)
  1299.             {   count2++;
  1300.                 pclip1 = clipptr[count1];
  1301.                 pclip2 = clipptr[count2];
  1302.  
  1303.                 /* When we get to the first line whose y1 is greater than
  1304.                  * our y2 we can skip all the way to the beginning of the
  1305.                  * new lines */
  1306.  
  1307.                 if (pclip2->y1 > pclip1->y2)
  1308.                 {   if (count2 < clipnew) count2 = clipnew;
  1309.                     continue;
  1310.                 }
  1311.  
  1312.                 /* Skip lines whose bounding boxes do not intersect ours */
  1313.  
  1314.                 if (pclip2->y2 < pclip1->y1)
  1315.                     continue;
  1316.                 if (min(pclip1->x1,pclip1->x2) > max(pclip2->x1,pclip2->x2))
  1317.                     continue;
  1318.                 if (max(pclip1->x1,pclip1->x2) < min(pclip2->x1,pclip2->x2))
  1319.                     continue;
  1320.  
  1321.                 /* If the two endpoints of each line are on opposite sides
  1322.                  * of the other line, the lines must intersect.  If one is
  1323.                  * on the line but not the other, they intersect at the end.
  1324.                  * If both are on the line they are colinear.  The distance
  1325.                  * from a point (x,y) to a line (a*X +b*Y + c = 0) is given
  1326.                  * by (a*x + b*y *c) / sqrt(a**2 + b**2).  We don't bother
  1327.                  * with the square root as we only want to know the
  1328.                  * relative distances.  The test is exact as long as the
  1329.                  * numbers (integer values) we are using are not too big to
  1330.                  * be represented exactly in double precision floating point
  1331.                  */
  1332.  
  1333.                 clip1 = *pclip1;
  1334.                 clip2 = *pclip2;
  1335.                 a1 = clip1.y2 - clip1.y1;
  1336.                 b1 = clip1.x2 - clip1.x1;
  1337.                 c1 = (double) clip1.x2 * (double) clip1.y1 -
  1338.                      (double) clip1.x1 * (double) clip1.y2;
  1339.                 h11 = a1 * clip2.x1 - b1 * clip2.y1 + c1;
  1340.                 h12 = a1 * clip2.x2 - b1 * clip2.y2 + c1;
  1341.                 if (h11 > 0.0 && h12 > 0.0) continue;
  1342.                 if (h11 < 0.0 && h12 < 0.0) continue;
  1343.  
  1344.                 a2 = clip2.y2 - clip2.y1;
  1345.                 b2 = clip2.x2 - clip2.x1;
  1346.                 c2 = (double) clip2.x2 * (double) clip2.y1 -
  1347.                      (double) clip2.x1 * (double) clip2.y2;
  1348.                 h21 = a2 * clip1.x1 - b2 * clip1.y1 + c2;
  1349.                 h22 = a2 * clip1.x2 - b2 * clip1.y2 + c2;
  1350.                 if (h21 > 0.0 && h22 > 0.0) continue;
  1351.                 if (h21 < 0.0 && h22 < 0.0) continue;
  1352.  
  1353.                 /* If the lines are colinear we treat them as intersecting
  1354.                  * at the endpoints.  To find out what order the endpoints
  1355.                  * lie in, we take the beginning of line 1 as our origin
  1356.                  * and calculate the dot products of the displacements of
  1357.                  * the other endpoints with line 1 itself.  We then split
  1358.                  * the lines, knowing that the two lines must be in the
  1359.                  * same direction, as we made sure y1 < y2 or x1 < x2
  1360.                  */
  1361.  
  1362.                 if (h11 == 0.0 && h12 == 0.0)
  1363.                 {   l1 = b1 * b1 + a1 * a1;
  1364.                     l2 = (clip2.x1 - clip1.x1) * b1 +
  1365.                          (clip2.y1 - clip1.y1) * a1;
  1366.                     l3 = (clip2.x2 - clip1.x1) * b1 +
  1367.                          (clip2.y2 - clip1.y1) * a1;
  1368.  
  1369.                     if      (l2 < 0 && l3 < l1)
  1370.                     {   clip1.x2 = pclip1->x1 = clip2.x2;
  1371.                         clip1.y2 = pclip1->y1 = clip2.y2;
  1372.                         clip2.x1 = pclip2->x2 = clip1.x1;
  1373.                         clip2.y1 = pclip2->y2 = clip1.y1;
  1374.                     }
  1375.                     else if (l2 <= 0 && l3 >= l1)
  1376.                     {   clip1 = clip2;
  1377.                         clip1.x2 = pclip2->x1 = pclip1->x1;
  1378.                         clip1.y2 = pclip2->y1 = pclip1->y1;
  1379.                         clip2.x1 = pclip2->x2 = pclip1->x2;
  1380.                         clip2.y1 = pclip2->y2 = pclip1->y2;
  1381.                     }
  1382.                     else if (l2 >= 0 && l3 <= l1)
  1383.                     {   clip2 = clip1;
  1384.                         clip1.x2 = pclip1->x1 = pclip2->x1;
  1385.                         clip1.y2 = pclip1->y1 = pclip2->y1;
  1386.                         clip2.x1 = pclip1->x2 = pclip2->x2;
  1387.                         clip2.y1 = pclip1->y2 = pclip2->y2;
  1388.                     }
  1389.                     else if (l2 > 0 && l3 > l1)
  1390.                     {   clip1.x1 = pclip1->x2 = clip2.x1;
  1391.                         clip1.y1 = pclip1->y2 = clip2.y1;
  1392.                         clip2.x2 = pclip2->x1 = clip1.x2;
  1393.                         clip2.y2 = pclip2->y1 = clip1.y2;
  1394.                     }
  1395.                     clipline(&clip1);
  1396.                     clipline(&clip2);
  1397.                 }
  1398.  
  1399.                 /* Otherwise calculate the intersection */
  1400.  
  1401.                 else
  1402.                 {   hh = h22 - h21;
  1403.                     xx = floor((clip1.x1 * h22 - clip1.x2 * h21) / hh + 0.5);
  1404.                     yy = floor((clip1.y1 * h22 - clip1.y2 * h21) / hh + 0.5);
  1405.                     if (xx != clip1.x1 || yy != clip1.y1)
  1406.                     {   pclip1->x2 = clip1.x1 = xx;
  1407.                         pclip1->y2 = clip1.y1 = yy;
  1408.                         clipline(&clip1);
  1409.                     }
  1410.                     pclip2 = clipptr[count2];
  1411.                     if (xx != clip2.x1 || yy != clip2.y1)
  1412.                     {   pclip2->x2 = clip2.x1 = xx;
  1413.                         pclip2->y2 = clip2.y1 = yy;
  1414.                         clipline(&clip2);
  1415.                     }
  1416.                 }
  1417.  
  1418.                 /* We must check the directions in case of rounding error */
  1419.  
  1420.                 clipswap(clipptr[count1]);
  1421.                 clipswap(clipptr[count2]);
  1422.             }
  1423.             count1++;
  1424.         }
  1425.     }
  1426.  
  1427.     /* Count the winding number for each line.  We construct a test line
  1428.      * running horizontally from the left, at a height just greater than y1.
  1429.      * (If the line is horizontal, we regard the test line as being bent at
  1430.      * the end so it meets the line just to the right of x1.)  If we find
  1431.      * any lines colinear with ours we chain them together */
  1432.  
  1433.     count1 = 0;
  1434.     clipold = 0;
  1435.     clipflg = 0;
  1436.     while (count1 < clipend)
  1437.     {   pclip1 = clipptr[count1++];
  1438.         if (pclip1->flag != 0) continue;
  1439.  
  1440.         count2 = clipold;
  1441.         cdir1 = fdir1 = 0;
  1442.         cdir2 = pclip1->cdir;
  1443.         fdir2 = pclip1->fdir;
  1444.         pclipx = NULL;
  1445.  
  1446.         /* Scan the other lines for intersections with the test line */
  1447.  
  1448.         while (count2 < clipend)
  1449.         {   pclip2 = clipptr[count2];
  1450.             count2++;
  1451.             if (pclip2 == pclip1) continue;
  1452.  
  1453.             /* If y2 is less than our y1 we won't need to scan the line
  1454.              * again.  Swap it to the beginning and step past it next time */
  1455.  
  1456.             if (pclip2->y2 < pclip1->y1)
  1457.             {   clipptr[count2 - 1]  = clipptr[clipold];
  1458.                 clipptr[clipold] = pclip2;
  1459.                 clipold++;
  1460.                 continue;
  1461.             }
  1462.  
  1463.             /* Stop scanning when y1 is greater than ours */
  1464.  
  1465.             if (pclip2->y1 > pclip1->y1) break;
  1466.  
  1467.             /* If its y2 is greater than our y1, then if it passes to the
  1468.              * left of our x1 it must intersect the test line */
  1469.  
  1470.             if (pclip2->y2 > pclip1->y1)
  1471.             {   a1 = pclip2->x1 * (double) (pclip2->y2 - pclip1->y1) +
  1472.                      pclip2->x2 * (double) (pclip1->y1 - pclip2->y1);
  1473.                 a2 = pclip1->x1 * (double) (pclip2->y2 - pclip2->y1);
  1474.  
  1475.                 if      (a1 < a2)
  1476.                 {   cdir1 += pclip2->cdir;
  1477.                     fdir1 += pclip2->fdir;
  1478.                 }
  1479.  
  1480.             /* If it passes through our x1 we have to compare the slopes.
  1481.              * The cross procuct is the sine of the angle between them.  If
  1482.              * its slope is greater than ours it must intersect the test
  1483.              * line.  If the slopes are the same they must be colinar;
  1484.              * calculate the winding number for the far side of the line
  1485.              * and chain it */
  1486.  
  1487.                 else if (a1 == a2)
  1488.                 {   hh = (double) (pclip1->x2 - pclip1->x1) *
  1489.                          (double) (pclip2->y2 - pclip2->y1) -
  1490.                          (double) (pclip2->x2 - pclip2->x1) *
  1491.                          (double) (pclip1->y2 - pclip1->y1);
  1492.                     if      (hh > 0.0)
  1493.                     {   cdir1 += pclip2->cdir;
  1494.                         fdir1 += pclip2->fdir;
  1495.                     }
  1496.                     else if (hh == 0.0)
  1497.                     {   cdir2 += pclip2->cdir;
  1498.                         fdir2 += pclip2->fdir;
  1499.                         if (pclip2->flag == 0)
  1500.                         {   pclip2->chain = pclipx;
  1501.                             pclipx = pclip2;
  1502.                         }
  1503.                     }
  1504.                 }
  1505.             }
  1506.  
  1507.             /* Horizontal lines only intersect the test line if they are
  1508.              * colinear with ours */
  1509.  
  1510.             else
  1511.                 if (pclip1->y1 == pclip1->y2 &&
  1512.                     pclip2->y1 == pclip2->y2 &&
  1513.                     pclip2->x1 == pclip1->x1)
  1514.                 {   cdir2 += pclip2->cdir;
  1515.                     fdir2 += pclip2->fdir;
  1516.                     if (pclip2->flag == 0)
  1517.                     {   pclip2->chain = pclipx;
  1518.                         pclipx = pclip2;
  1519.                     }
  1520.                 }
  1521.         }
  1522.  
  1523.         /* If the line is on the boundary of the intersection of the paths,
  1524.          * we keep it.  If it is interior to or on the boundary of the path
  1525.          * it does not belong to, or exterior to or on the boundary of the
  1526.          * other, we must have two or more coincident lines; we keep it and
  1527.          * its pair to preserve the degenerate path, discarding any others
  1528.          * that are also coincident.  Otherwise we discard it.  (We don't
  1529.          * preserve paths where both the clip and fill paths are
  1530.          * degenerate.)  Flag the lines for their ends to be swapped if they
  1531.          * are right or bottom edges */
  1532.  
  1533.         cdir2 = (((cdir1 + cdir2) & rule) != 0);
  1534.         fdir2 = (((fdir1 + fdir2) & rule) != 0);
  1535.         cdir1 = (( cdir1          & rule) != 0);
  1536.         fdir1 = (( fdir1          & rule) != 0);
  1537.  
  1538.         if ((cdir1 & fdir1) == (cdir2 & fdir2))
  1539.             if ((pclip1->fdir != 0 && (cdir1 | cdir2) && !(fdir1 & fdir2)) ||
  1540.                 (pclip1->cdir != 0 && (fdir1 | fdir2) && !(cdir1 & fdir2)))
  1541.             {   pclipx->flag = 2;           /* Keep its pair */
  1542.                 pclipx->swap = 1;           /* Swap one line */
  1543.                 pclipx = pclipx->chain;     /* Discard the rest */
  1544.             }
  1545.             else
  1546.             {   pclip1->flag = 1;           /* Discard the line */
  1547.                 clipflg++;
  1548.                 pclipx = NULL;              /* Leave the rest */
  1549.             }
  1550.         else
  1551.             if ((cdir1 & fdir1) != 0)
  1552.                 pclip1->swap = 1;           /* Swap right and bottom edges */
  1553.  
  1554.         while (pclipx)                      /* Discard the rest */
  1555.         {   pclipx->flag = 1;
  1556.             clipflg++;
  1557.             pclipx = pclipx->chain;
  1558.         }
  1559.     }
  1560.  
  1561.     /* Swap the lines so they are pointing in their proper directions */
  1562.  
  1563.     count1 = clipend;
  1564.     pclip1 = &cliparray[0];
  1565.     while (count1--)
  1566.     {   if (pclip1->swap) clipswap(pclip1);
  1567.         pclip1++;
  1568.     }
  1569.  
  1570.     /* Now join the lines back up to make the path.  The lines are in
  1571.      * approximate order of y2, so we optimise our search on that basis.
  1572.      * We start by picking any line; then we find the one that joins it */
  1573.  
  1574.     cliplength(0);
  1575.     point.type = ptmove;
  1576.     count = 0;
  1577.     step = 0;
  1578.     pathend = gstate.pathend;
  1579.  
  1580.     while (clipflg < clipend)
  1581.     {
  1582.         /* We step alternately backwards and forwards */
  1583.  
  1584.         count = count + step;
  1585.         if (step > 0)
  1586.             step = -step - 1;
  1587.         else
  1588.             step = -step + 1;
  1589.  
  1590.         /* When the array is half empty we compact it */
  1591.  
  1592.         if (clipflg + clipflg > clipend)
  1593.         {   count1 = 0;
  1594.             count2 = 0;
  1595.             while (count2 < clipend)
  1596.             {   if (count2 == count) count = count1;
  1597.                 pclip2 = clipptr[count2++];
  1598.                 if (pclip2->flag != 1) clipptr[count1++] = pclip2;
  1599.             }
  1600.             clipend -= clipflg;
  1601.             clipflg = 0;
  1602.             if (count >= clipend) count = clipend - 1;
  1603.             step = 1;
  1604.         }
  1605.  
  1606.         /* Search for a line that joins the current point */
  1607.  
  1608.         if (count >= 0 && count < clipend)
  1609.         {   pclip1 = clipptr[count];
  1610.             if (pclip1->flag != 1)
  1611.             {
  1612.                 /* At the beginning of a subpath add a move */
  1613.  
  1614.                 if (point.type == ptmove)
  1615.                 {   x1 = pclip1->x1;
  1616.                     y1 = pclip1->y1;
  1617.                     point.x = x1 / 256.0f;
  1618.                     point.y = y1 / 256.0f;
  1619.                     checkpathsize(pathend + 1);
  1620.                     patharray[pathend++] = point;
  1621.                     point.type = ptline;
  1622.                     xx = pclip1->x2;
  1623.                     yy = pclip1->y2;
  1624.                     step = 0;
  1625.                 }
  1626.  
  1627.                 /* Otherwise look for a line that joins the current point */
  1628.  
  1629.                 else if (pclip1->y1 == yy && pclip1->x1 == xx)
  1630.                 {   xx = pclip1->x2;
  1631.                     yy = pclip1->y2;
  1632.                     step = 0;
  1633.                 }
  1634.  
  1635.                 /* Found a line; if it returns to the beginning close the
  1636.                  * subpath */
  1637.  
  1638.                 if (step == 0)
  1639.                 {   pclip1->flag = 1;
  1640.                     clipflg++;
  1641.                     checkpathsize(pathend + 1);
  1642.                     point.x = xx / 256.0f;
  1643.                     point.y = yy / 256.0f;
  1644.                     if (yy == y1 && xx == x1)
  1645.                     {   point.type = ptclosex;
  1646.                         patharray[pathend++] = point;
  1647.                         point.type = ptmove;
  1648.                     }
  1649.                     else
  1650.                         patharray[pathend++] = point;
  1651.                     step = 1;
  1652.                 }
  1653.             }
  1654.         }
  1655.     }
  1656.  
  1657.     /* We now have the new clip path, at the end of the path.  To put the
  1658.      * clip path first, we first swap the order of the contents of the two
  1659.      * paths individually, then swap them both together */
  1660.  
  1661.     swappath(gstate.pathbeg, gstate.pathend);
  1662.     swappath(gstate.pathend, pathend);
  1663.     swappath(gstate.pathbeg, pathend);
  1664.     gstate.pathbeg = gstate.clipbeg + pathend - gstate.pathend;
  1665.     gstate.pathend = pathend;
  1666.     gstate.clipflag = 1;
  1667. }
  1668.  
  1669. /* Add a clip line to the array */
  1670.  
  1671. void clipline(struct clip *pclip)
  1672. {   struct clip *pc;
  1673.  
  1674.     if (pclip->x1 != pclip->x2 || pclip->y1 != pclip->y2)
  1675.     {   clipswap(pclip);
  1676.         checkclipsize(clipend + 1, clipend);
  1677.         pc = &cliparray[clipend];
  1678.         *pc = *pclip;
  1679.         clipptr[clipend++] = pc;
  1680.     }
  1681. }
  1682.  
  1683. /* Swap a clip line if necessary so y2 > y1 (or x2 > x1) */
  1684.  
  1685. void clipswap(struct clip *pclip)
  1686. {   int sw;
  1687.     if (pclip->swap ||
  1688.         pclip->y1 > pclip->y2 ||
  1689.            (pclip->y1 == pclip->y2 && pclip->x1 > pclip->x2))
  1690.     {   pclip->cdir = -pclip->cdir;
  1691.         pclip->fdir = -pclip->fdir;
  1692.         sw = pclip->x1;
  1693.         pclip->x1 = pclip->x2;
  1694.         pclip->x2 = sw;
  1695.         sw = pclip->y1;
  1696.         pclip->y1 = pclip->y2;
  1697.         pclip->y2 = sw;
  1698.     }
  1699. }
  1700.  
  1701. /* Swap the order of the points in a path */
  1702.  
  1703. void swappath(int beg, int end)
  1704. {   struct point point, *ppoint1, *ppoint2;
  1705.     ppoint1 = &patharray[beg];
  1706.     ppoint2 = &patharray[end];
  1707.     for (;;)
  1708.     {   ppoint2--;
  1709.         if (ppoint1 >= ppoint2) break;
  1710.         point = *ppoint1;
  1711.         *ppoint1 = *ppoint2;
  1712.         *ppoint2 = point;
  1713.         ppoint1++;
  1714.     }
  1715. }
  1716.  
  1717. /* End of file "postgraph.c" */
  1718.