home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1996 February / PCWK0296.iso / sharewar / dos / program / gs300sr1 / gs300sr1.exe / GXSTROKE.C < prev    next >
C/C++ Source or Header  |  1994-07-30  |  25KB  |  706 lines
  1. /* Copyright (C) 1989, 1992, 1993, 1994 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of Aladdin Ghostscript.
  4.   
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.   
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* gxstroke.c */
  20. /* Path stroking procedures for Ghostscript library */
  21. #include "math_.h"
  22. #include "gx.h"
  23. #include "gpcheck.h"
  24. #include "gserrors.h"
  25. #include "gxfixed.h"
  26. #include "gxarith.h"
  27. #include "gxmatrix.h"
  28. #include "gscoord.h"
  29. #include "gzstate.h"
  30. #include "gzline.h"
  31. #include "gzpath.h"
  32. #include "gxpaint.h"
  33. #include "gzdraw.h"        /* gz_draw_line_fixed prototype */
  34.  
  35. /* Define the filling adjustment that actually produces no adjustment. */
  36. #define fill_no_adjust ((fixed)1)
  37.  
  38. /*
  39.  * Structure for a partial line (passed to the drawing routine).
  40.  * Two of these are required to do joins right.
  41.  * Each endpoint includes the two ends of the cap as well,
  42.  * and the deltas for square and round cap computation.
  43.  *
  44.  * The two base values for computing the caps of a partial line are the
  45.  * width and the end cap delta.  The width value is one-half the line
  46.  * width (suitably transformed) at 90 degrees counter-clockwise
  47.  * (in device space, but with "90 degrees" interpreted in *user*
  48.  * coordinates) at the end (as opposed to the origin) of the line.
  49.  * The cdelta value is one-half the transformed line width in the same
  50.  * direction as the line.  From these, we compute two other values at each
  51.  * end of the line: co and ce, which are the ends of the cap.
  52.  * Note that the cdelta values at o are the negatives of the values at e,
  53.  * as are the offsets from p to co and ce.
  54.  *
  55.  * Initially, only o.p, e.p, e.cdelta, width, and thin are set.
  56.  * compute_caps fills in the rest.
  57.  */
  58. typedef gs_fixed_point _ss *p_ptr;
  59. typedef struct endpoint_s {
  60.     gs_fixed_point p;        /* the end of the line */
  61.     gs_fixed_point co, ce;        /* ends of the cap, p +/- width */
  62.     gs_fixed_point cdelta;        /* +/- cap length */
  63. } endpoint;
  64. typedef endpoint _ss *ep_ptr;
  65. typedef struct partial_line_s {
  66.     endpoint o;            /* starting coordinate */
  67.     endpoint e;            /* ending coordinate */
  68.     gs_fixed_point width;        /* one-half line width, see above */
  69.     bool thin;            /* true if minimum-width line */
  70. } partial_line;
  71. typedef partial_line _ss *pl_ptr;
  72.  
  73. /* Procedures that stroke a partial_line (the first pl_ptr argument). */
  74. /* If both partial_lines are non-null, the procedure creates */
  75. /* an appropriate join; otherwise, the procedure creates an */
  76. /* end cap.  If the first int is 0, the procedure also starts with */
  77. /* an appropriate cap. */
  78. private int near stroke_add(P5(gx_path *, int, pl_ptr, pl_ptr, gs_state *));
  79. private int near stroke_fill(P5(gx_path *, int, pl_ptr, pl_ptr, gs_state *));
  80.  
  81. /* Other forward declarations */
  82. private int near stroke(P4(const gx_path *, gx_path *,
  83.   int near (*)(P5(gx_path *, int, pl_ptr, pl_ptr, gs_state *)),
  84.   gs_state *));
  85. private void near adjust_stroke(P2(pl_ptr, gs_state *));
  86. private void near compute_caps(P1(pl_ptr));
  87. private int near add_capped(P4(gx_path *, gs_line_cap,
  88.   int (*)(P3(gx_path *, fixed, fixed)),
  89.   ep_ptr));
  90.  
  91. /* Stroke a path for drawing or saving */
  92. int
  93. gx_stroke_fill(const gx_path *ppath, gs_state *pgs)
  94. {    return stroke(ppath, (gx_path *)0, stroke_fill, pgs);
  95. }
  96. int
  97. gx_stroke_add(const gx_path *ppath, gx_path *to_path, gs_state *pgs)
  98. {    int code = stroke(ppath, to_path, stroke_add, pgs);
  99.     /* I don't understand why this code used to be here: */
  100. #if 0
  101.     if ( code < 0 ) return code;
  102.     if ( ppath->subpath_open <= 0 && ppath->position_valid )
  103.         code = gx_path_add_point(to_path, ppath->position.x,
  104.                      ppath->position.y);
  105. #endif
  106.     return code;
  107. }
  108.  
  109. /* Fill a partial stroked path. */
  110. /* Free variables: code, to_path, ppath, stroke_path_body, pgs, exit(label). */
  111. #define fill_stroke_path()\
  112. if(to_path==&stroke_path_body && !gx_path_is_void_inline(&stroke_path_body))\
  113. { code = gx_fill_path(to_path, pgs->dev_color, pgs, gx_rule_winding_number,\
  114.     fill_no_adjust);\
  115.   gx_path_release(to_path);\
  116.   if ( code < 0 ) goto exit;\
  117.   gx_path_init(to_path, ppath->memory);\
  118. }
  119.  
  120. /* Stroke a path.  Call line_proc (stroke_add or stroke_fill) */
  121. /* for each line segment. */
  122. private int near
  123. stroke(const gx_path *ppath, gx_path *to_path,
  124.   int near (*line_proc)(P5(gx_path *, int, pl_ptr, pl_ptr, gs_state *)),
  125.   gs_state *pgs)
  126. {    int code = 0;
  127.     const gx_line_params *lp = pgs->line_params;
  128.     int dash_count = lp->dash.pattern_size;
  129.     gx_path fpath, dpath;
  130.     gx_path stroke_path_body;
  131.     const gx_path *spath;
  132.     float xx = pgs->ctm.xx, xy = pgs->ctm.xy;
  133.     float yx = pgs->ctm.yx, yy = pgs->ctm.yy;
  134.     bool skewed = !is_fzero2(xy, yx);
  135.     int uniform = (skewed ? 0 : xx == yy ? 1 : xx == -yy ? -1 : 0);
  136.     /*
  137.      * We are dealing with a reflected coordinate system
  138.      * if transform(1,0) is counter-clockwise from transform(0,1).
  139.      * See the note in stroke_add for the algorithm.
  140.      */    
  141.     bool reflected =
  142.       (uniform ? uniform < 0 :
  143.        skewed ? xy * yx > xx * yy :
  144.        (xx < 0) != (yy < 0));
  145.     float line_width = lp->width;    /* this is *half* the line width! */
  146.     bool always_thin;
  147.     double line_width_and_scale, line_width_scale_xx;
  148.     const segment *pseg;
  149. #ifdef DEBUG
  150. if ( gs_debug_c('o') )
  151.    {    int count = lp->dash.pattern_size;
  152.     int i;
  153.     dprintf3("[o]half_width=%f, cap=%d, join=%d,\n",
  154.          lp->width, (int)lp->cap, (int)lp->join);
  155.     dprintf2("   miter_limit=%f, miter_check=%f,\n",
  156.          lp->miter_limit, lp->miter_check);
  157.     dprintf1("   dash pattern=%d", count);
  158.     for ( i = 0; i < count; i++ )
  159.         dprintf1(",%f", lp->dash.pattern[i]);
  160.     dprintf4(",\n    offset=%f, init(ink_on=%d, index=%d, dist_left=%f)\n",
  161.          lp->dash.offset, lp->dash.init_ink_on, lp->dash.init_index,
  162.          lp->dash.init_dist_left);
  163.    }
  164. #endif
  165.     if ( line_width < 0 ) line_width = -line_width;
  166.     if ( is_fzero(line_width) )
  167.         always_thin = true;
  168.     else if ( !skewed )
  169.        {    float xxa = xx, yya = yy;
  170.         if ( xxa < 0 ) xxa = -xxa;
  171.         if ( yya < 0 ) yya = -yya;
  172.         always_thin = (max(xxa, yya) * line_width < 0.5);
  173.        }
  174.     else
  175.        {    /* The check is more complicated, but it's worth it. */
  176.         float xsq = xx * xx + xy * xy;
  177.         float ysq = yx * yx + yy * yy;
  178.         float cross = xx * yx + xy * yy;
  179.         if ( cross < 0 ) cross = 0;
  180.         always_thin =
  181.           ((max(xsq, ysq) + cross) * line_width * line_width < 0.5);
  182.        }
  183.     line_width_and_scale = line_width * (double)int2fixed(1);
  184.     if ( !always_thin && uniform )
  185.     {    /* Precompute a value we'll need later. */
  186.         line_width_scale_xx = line_width_and_scale * xx;
  187.         if ( line_width_scale_xx < 0 )
  188.           line_width_scale_xx = -line_width_scale_xx;
  189.     }
  190.     if_debug5('o', "[o]ctm=(%g,%g,%g,%g) thin=%d\n",
  191.           xx, xy, yx, yy, always_thin);
  192.     /* Start by flattening the path.  We should do this on-the-fly.... */
  193.     if ( !ppath->curve_count )    /* don't need to flatten */
  194.        {    if ( !ppath->first_subpath )
  195.           return 0;
  196.         spath = ppath;
  197.        }
  198.     else
  199.        {    if ( (code = gx_path_flatten(ppath, &fpath, pgs->flatness, (int)pgs->in_cachedevice)) < 0 )
  200.            return code;
  201.         spath = &fpath;
  202.        }
  203.     if ( dash_count )
  204.       {    code = gx_path_expand_dashes(spath, &dpath, pgs);
  205.         if ( code < 0 )
  206.           goto exf;
  207.         spath = &dpath;
  208.       }
  209.     if ( to_path == 0 )
  210.       {    /* We might try to defer this if it's expensive.... */
  211.         to_path = &stroke_path_body;
  212.         gx_path_init(to_path, ppath->memory);
  213.       }
  214.     for ( pseg = (const segment *)spath->first_subpath; pseg != 0; )
  215.       { int first = 0;
  216.         int index = 0;
  217.         fixed x = pseg->pt.x;
  218.         fixed y = pseg->pt.y;
  219.         bool is_closed = ((const subpath *)pseg)->is_closed;
  220.         partial_line pl, pl_prev, pl_first;
  221.         while ( (pseg = pseg->next) != 0 && pseg->type != s_start )
  222.           {    /* Compute the width parameters in device space. */
  223.         /* We work with unscaled values, for speed. */
  224.         fixed sx = pseg->pt.x, udx = sx - x;
  225.         fixed sy = pseg->pt.y, udy = sy - y;
  226.         pl.o.p.x = x, pl.o.p.y = y;
  227.         pl.e.p.x = sx, pl.e.p.y = sy;
  228.         if ( !(udx | udy) )    /* degenerate */
  229.           { /* Only consider a degenerate segment */
  230.             /* if the entire subpath is degenerate and */
  231.             /* we are using round caps or joins. */
  232.             if ( index != 0 || (pseg->next != 0 &&
  233.                     pseg->next->type != s_start) ||
  234.              (lp->cap != gs_cap_round &&
  235.               lp->join != gs_join_round)
  236.                )
  237.               goto nd;
  238.             /* Pick an arbitrary orientation. */
  239.             udx = int2fixed(1);
  240.           }
  241.         if ( !always_thin )
  242.            {    if ( uniform != 0 )
  243.                {    /* We can save a lot of work in this case. */
  244.                 float dpx = udx, dpy = udy;
  245.                  float wl = line_width_scale_xx /
  246.                     hypot(dpx, dpy);
  247.                 pl.e.cdelta.x = (fixed)(dpx * wl);
  248.                 pl.e.cdelta.y = (fixed)(dpy * wl);
  249.                 if ( reflected )
  250.                   pl.width.x = pl.e.cdelta.y,
  251.                   pl.width.y = -pl.e.cdelta.x;
  252.                 else
  253.                   pl.width.x = -pl.e.cdelta.y,
  254.                   pl.width.y = pl.e.cdelta.x;
  255.                 pl.thin = false; /* if not always_thin, */
  256.                         /* then never thin. */
  257.                }
  258.             else
  259.                {    gs_point dpt;    /* unscaled */
  260.                 float wl;
  261.                 gs_idtransform(pgs, (float)udx, (float)udy,
  262.                            &dpt);
  263.                 wl = line_width_and_scale /
  264.                     hypot(dpt.x, dpt.y);
  265.                 /* Construct the width vector in */
  266.                 /* user space, still unscaled. */
  267.                 dpt.x *= wl;
  268.                 dpt.y *= wl;
  269.                 /*
  270.                  * We now compute both perpendicular
  271.                  * and (optionally) parallel half-widths,
  272.                  * as deltas in device space.  We use
  273.                  * a fixed-point, unscaled version of
  274.                  * gs_dtransform.  The second computation
  275.                  * folds in a 90-degree rotation (in user
  276.                  * space, before transforming) in the
  277.                  * direction that corresponds to clockwise
  278.                  * in device space.
  279.                  */
  280.                 pl.e.cdelta.x = (fixed)(dpt.x * xx);
  281.                 pl.e.cdelta.y = (fixed)(dpt.y * yy);
  282.                 if ( skewed )
  283.                   pl.e.cdelta.x += (fixed)(dpt.y * yx),
  284.                   pl.e.cdelta.y += (fixed)(dpt.x * xy);
  285.                 if ( reflected )
  286.                   dpt.x = -dpt.x, dpt.y = -dpt.y;
  287.                 pl.width.x = (fixed)(dpt.y * xx),
  288.                 pl.width.y = -(fixed)(dpt.x * yy);
  289.                 if ( skewed )
  290.                   pl.width.x -= (fixed)(dpt.x * yx),
  291.                   pl.width.y += (fixed)(dpt.y * xy);
  292.                 pl.thin =
  293.                   any_abs(pl.width.x) + any_abs(pl.width.y) <
  294.                     float2fixed(0.75);
  295.                }
  296.             if ( !pl.thin )
  297.             {    adjust_stroke(&pl, pgs);
  298.                 compute_caps(&pl);
  299.             }
  300.            }
  301.         else            /* always_thin */
  302.             pl.e.cdelta.x = pl.e.cdelta.y = 0,
  303.             pl.width.x = pl.width.y = 0,
  304.             pl.thin = true;
  305.         if ( first++ == 0 ) pl_first = pl;
  306.         if ( index++ )
  307.         {    code = (*line_proc)(to_path,
  308.                         (is_closed ? 1 : index - 2),
  309.                         &pl_prev, &pl, pgs);
  310.             if ( code < 0 )
  311.               goto exit;
  312.             fill_stroke_path();
  313.         }
  314.         pl_prev = pl;
  315.         x = sx, y = sy;
  316. nd:        ;
  317.           }
  318.         if ( index )
  319.           {    /* If closed, join back to start, else cap. */
  320.         /* For some reason, the Borland compiler requires the cast */
  321.         /* in the following line. */
  322.         pl_ptr lptr = (is_closed ? (pl_ptr)&pl_first : (pl_ptr)0);
  323.         code = (*line_proc)(to_path, index - 1, &pl_prev, lptr, pgs);
  324.         if ( code < 0 )
  325.           goto exit;
  326.         fill_stroke_path();
  327.           }
  328.      }
  329. exit:    if ( to_path == &stroke_path_body )
  330.       gx_path_release(to_path);    /* (only needed if error) */
  331.     if ( dash_count )
  332.       gx_path_release(&dpath);
  333. exf:    if ( ppath->curve_count )
  334.       gx_path_release(&fpath);
  335.     return code;
  336. }
  337.  
  338. /* ------ Internal routines ------ */
  339.  
  340. /* Adjust the endpoints and width of a stroke segment */
  341. /* to achieve more uniform rendering. */
  342. /* Only o.p, e.p, e.cdelta, and width have been set. */
  343. private void near
  344. adjust_stroke(pl_ptr plp, gs_state *pgs)
  345. {    fixed _ss *pw;
  346.     fixed _ss *pov;
  347.     fixed _ss *pev;
  348.     fixed w, w2;
  349.     if ( !pgs->stroke_adjust && plp->width.x != 0 && plp->width.y != 0 )
  350.         return;        /* don't adjust */
  351.     if ( any_abs(plp->width.x) < any_abs(plp->width.y) )
  352.     {    /* More horizontal stroke */
  353.         pw = &plp->width.y, pov = &plp->o.p.y, pev = &plp->e.p.y;
  354.     }
  355.     else
  356.     {    /* More vertical stroke */
  357.         pw = &plp->width.x, pov = &plp->o.p.x, pev = &plp->e.p.x;
  358.     }
  359.     /* Round the larger component of the width up or down, */
  360.     /* whichever way produces a result closer to the correct width. */
  361.     /* Note that just rounding the larger component */
  362.     /* may not produce the correct result. */
  363.     w = *pw;
  364.     if ( *pov == *pev )
  365.     {    /* We're going to round the endpoint coordinates, so */
  366.         /* take the fill adjustment into account now. */
  367.         if ( w >= 0 ) w += pgs->fill_adjust;
  368.         else w -= pgs->fill_adjust;
  369.     }
  370.     w2 = fixed_rounded(w << 1);        /* full line width */
  371.     if ( w2 == 0 && *pw != 0 )
  372.     {    /* Make sure thin lines don't disappear. */
  373.         w2 = (*pw < 0 ? -fixed_1 : fixed_1);
  374.     }
  375.     *pw = arith_rshift_1(w2);
  376.     /* Only adjust the endpoints if the line is horizontal or vertical. */
  377.     if ( *pov == *pev )
  378.     {    if ( w2 & fixed_1 )    /* odd width, move to half-pixel */
  379.         {    *pov = *pev = fixed_floor(*pov) + fixed_half;
  380.         }
  381.         else            /* even width, move to pixel */
  382.         {    *pov = *pev = fixed_rounded(*pov);
  383.         }
  384.     }
  385. }
  386.  
  387. /* Compute the intersection of two lines.  This is a messy algorithm */
  388. /* that somehow ought to be useful in more places than just here.... */
  389. /* If the lines are (nearly) parallel, return -1 without setting *pi; */
  390. /* otherwise, return 0 if the intersection is beyond *pp1 and *pp2 in */
  391. /* the direction determined by *pd1 and *pd2, and 1 otherwise. */
  392. private int
  393. line_intersect(
  394.     p_ptr pp1,                /* point on 1st line */
  395.     p_ptr pd1,                /* slope of 1st line (dx,dy) */
  396.     p_ptr pp2,                /* point on 2nd line */
  397.     p_ptr pd2,                /* slope of 2nd line */
  398.     p_ptr pi)                /* return intersection here */
  399. {    /* We don't have to do any scaling, the factors all work out right. */
  400.     float u1 = pd1->x, v1 = pd1->y;
  401.     float u2 = pd2->x, v2 = pd2->y;
  402.     double denom = u1 * v2 - u2 * v1;
  403.     float xdiff = pp2->x - pp1->x;
  404.     float ydiff = pp2->y - pp1->y;
  405.     double f1;
  406.     double max_result = any_abs(denom) * (double)max_fixed;
  407. #ifdef DEBUG
  408. if ( gs_debug_c('O') )
  409.    {    dprintf4("[o]Intersect %f,%f(%f/%f)",
  410.          fixed2float(pp1->x), fixed2float(pp1->y),
  411.          fixed2float(pd1->x), fixed2float(pd1->y));
  412.     dprintf4(" & %f,%f(%f/%f),\n",
  413.          fixed2float(pp2->x), fixed2float(pp2->y),
  414.          fixed2float(pd2->x), fixed2float(pd2->y));
  415.     dprintf3("\txdiff=%f ydiff=%f denom=%f ->\n",
  416.          xdiff, ydiff, denom);
  417.    }
  418. #endif
  419.     /* Check for degenerate result. */
  420.     if ( any_abs(xdiff) >= max_result || any_abs(ydiff) >= max_result )
  421.        {    /* The lines are nearly parallel, */
  422.         /* or one of them has zero length.  Punt. */
  423.         if_debug0('O', "\tdegenerate!\n");
  424.         return -1;
  425.        }
  426.     f1 = (v2 * xdiff - u2 * ydiff) / denom;
  427.     pi->x = pp1->x + (fixed)(f1 * u1);
  428.     pi->y = pp1->y + (fixed)(f1 * v1);
  429.     if_debug2('O', "\t%f,%f\n",
  430.           fixed2float(pi->x), fixed2float(pi->y));
  431.     return (f1 >= 0 && (v1 * xdiff >= u1 * ydiff ? denom >= 0 : denom < 0) ? 0 : 1);
  432. }
  433.  
  434. #define lix plp->o.p.x
  435. #define liy plp->o.p.y
  436. #define litox plp->e.p.x
  437. #define litoy plp->e.p.y
  438. #define trsign(v, c) ((v) >= 0 ? (c) : -(c))
  439.  
  440. /* Set up the width and delta parameters for a thin line. */
  441. /* We only approximate the width and height. */
  442. private void near
  443. set_thin_widths(register pl_ptr plp)
  444. {    fixed dx = litox - lix, dy = litoy - liy;
  445.     if ( any_abs(dx) > any_abs(dy) )
  446.     {    plp->width.x = plp->e.cdelta.y = 0;
  447.         plp->width.y = plp->e.cdelta.x = trsign(dx, fixed_half);
  448.     }
  449.     else
  450.     {    plp->width.y = plp->e.cdelta.x = 0;
  451.         plp->width.x = -(plp->e.cdelta.y = trsign(dy, fixed_half));
  452.     }
  453. }
  454.  
  455. /* Draw a line on the device. */
  456. private int near
  457. stroke_fill(gx_path *ppath, int first, register pl_ptr plp, pl_ptr nplp,
  458.   gs_state *pgs)
  459. {    if ( plp->thin )
  460.        {    /* Minimum-width line, don't have to be careful. */
  461.         /* We do have to check for the entire line being */
  462.         /* within the clipping rectangle, allowing for some */
  463.         /* slop at the ends. */
  464.         fixed dx = litox - lix, dy = litoy - liy;
  465. #define slop int2fixed(2)
  466.         fixed xslop = trsign(dx, slop);
  467.         fixed yslop = trsign(dy, slop);
  468.         if ( gx_cpath_includes_rectangle(pgs->clip_path,
  469.                 lix - xslop, liy - yslop,
  470.                 litox + xslop, litoy + yslop) )
  471.             return gz_draw_line_fixed(lix, liy, litox, litoy,
  472.                 pgs->dev_color, pgs);
  473. #undef slop
  474. #undef trsign
  475.         /* We didn't set up the endpoint parameters before, */
  476.         /* because the line was thin.  stroke_add will do this. */
  477.        }
  478.     /* General case: construct a path for the fill algorithm. */
  479.     return stroke_add(ppath, first, plp, nplp, pgs);
  480. }
  481.  
  482. #undef lix
  483. #undef liy
  484. #undef litox
  485. #undef litoy
  486.  
  487. /* Add a segment to the path.  This handles all the complex cases. */
  488. private int near add_capped(P4(gx_path *, gs_line_cap, int (*)(P3(gx_path *, fixed, fixed)), ep_ptr));
  489. private int near
  490. stroke_add(gx_path *ppath, int first, register pl_ptr plp, pl_ptr nplp,
  491.   gs_state *pgs)
  492. {    int code;
  493.     if ( plp->thin )
  494.        {    /* We didn't set up the endpoint parameters before, */
  495.         /* because the line was thin.  Do it now. */
  496.         set_thin_widths(plp);
  497.         adjust_stroke(plp, pgs);
  498.         compute_caps(plp);
  499.        }
  500.     if ( (code = add_capped(ppath, (first == 0 ? pgs->line_params->cap : gs_cap_butt), gx_path_add_point, &plp->o)) < 0 )
  501.         return code;
  502.     if ( nplp == 0 )
  503.        {    code = add_capped(ppath, pgs->line_params->cap, gx_path_add_line, &plp->e);
  504.        }
  505.     else if ( pgs->line_params->join == gs_join_round )
  506.        {    code = add_capped(ppath, gs_cap_round, gx_path_add_line, &plp->e);
  507.        }
  508.     else if ( nplp->thin )        /* no join */
  509.       {    code = add_capped(ppath, gs_cap_butt, gx_path_add_line, &plp->e);
  510.       }
  511.     else                /* join_bevel or join_miter */
  512.        {    gs_fixed_point jp1, jp2;
  513.         /*
  514.          * Set np to whichever of nplp->o.co or .ce is outside
  515.          * the current line.  We observe that the point (x2,y2)
  516.          * is counter-clockwise from (x1,y1), relative to the origin,
  517.          * iff
  518.          *    (arctan(y2/x2) - arctan(y1/x1)) mod 2*pi < pi,
  519.          * taking the signs of xi and yi into account to determine
  520.          * the quadrants of the results.  It turns out that
  521.          * even though arctan is monotonic only in the 4th/1st
  522.          * quadrants and the 2nd/3rd quadrants, case analysis on
  523.          * the signs of xi and yi demonstrates that this test
  524.          * is equivalent to the much less expensive test
  525.          *    x1 * y2 > x2 * y1
  526.          * in all cases.
  527.          *
  528.          * In the present instance, x1,y1 are plp->width,
  529.          * x2,y2 are nplp->width, and the origin is
  530.          * their common point (plp->e.p, nplp->o.p).
  531.          */
  532.         /* We make the test using double arithmetic only because */
  533.         /* the !@#&^*% C language doesn't give us access to */
  534.         /* the double-width-result multiplication operation */
  535.         /* that almost all CPUs provide! */
  536.         bool ccw =
  537.           (double)(plp->width.x) *    /* x1 */
  538.             (nplp->width.y) >        /* y2 */
  539.           (double)(nplp->width.x) *    /* x2 */
  540.             (plp->width.y);
  541.         p_ptr outp, np, np1, np2;
  542.         /* Initialize for a bevel join. */
  543.         jp1.x = plp->e.co.x, jp1.y = plp->e.co.y;
  544.         jp2.x = plp->e.ce.x, jp2.y = plp->e.ce.y;
  545.         if ( ccw )
  546.             outp = &jp2, np2 = np = &nplp->o.co, np1 = &plp->e.p;
  547.         else
  548.             outp = &jp1, np1 = np = &nplp->o.ce, np2 = &plp->e.p;
  549.         if_debug1('O', "[o]use %s\n", (ccw ? "co (ccw)" : "ce (cw)"));
  550.         /* Don't bother with the miter check if the two */
  551.         /* points to be joined are very close together, */
  552.         /* namely, in the same square half-pixel. */
  553.         if ( pgs->line_params->join == gs_join_miter &&
  554.              !(fixed2long(outp->x << 1) == fixed2long(np->x << 1) &&
  555.                fixed2long(outp->y << 1) == fixed2long(np->y << 1))
  556.            )
  557.           { /*
  558.              * Check whether a miter join is appropriate.
  559.              * Let a, b be the angles of the two lines.
  560.              * We check tan(a-b) against the miter_check
  561.              * by using the following formula:
  562.              * If tan(a)=u1/v1 and tan(b)=u2/v2, then
  563.              * tan(a-b) = (u1*v2 - u2*v1) / (u1*u2 + v1*v2).
  564.              * We can do all the computations unscaled,
  565.              * because we're only concerned with ratios.
  566.              */
  567.             float u1 = plp->e.cdelta.y, v1 = plp->e.cdelta.x;
  568.             float u2 = nplp->o.cdelta.y, v2 = nplp->o.cdelta.x;
  569.             double num = u1 * v2 - u2 * v1;
  570.             double denom = u1 * u2 + v1 * v2;
  571.             float check = pgs->line_params->miter_check;
  572.             /*
  573.              * We will want either tan(a-b) or tan(b-a)
  574.              * depending on the orientations of the lines.
  575.              * Fortunately we know the relative orientations already.
  576.              */
  577.             if ( !ccw )        /* have plp - nplp, want vice versa */
  578.             num = -num;
  579. #ifdef DEBUG
  580. if ( gs_debug_c('O') )
  581.                    {    dprintf4("[o]Miter check: u1/v1=%f/%f, u2/v2=%f/%f,\n",
  582.                  u1, v1, u2, v2);
  583.             dprintf3("        num=%f, denom=%f, check=%f\n",
  584.                  num, denom, check);
  585.                    }
  586. #endif
  587.             /*
  588.              * If we define T = num / denom, then we want to use
  589.              * a miter join iff arctan(T) >= arctan(check).
  590.              * We know that both of these angles are in the 1st
  591.              * or 2nd quadrant, and since arctan is monotonic
  592.              * within each quadrant, we can do the comparisons
  593.              * on T and check directly, taking signs into account
  594.              * as follows:
  595.              *        sign(T)    sign(check)    atan(T) >= atan(check)
  596.              *        -------    -----------    ----------------------
  597.              *        +    +        T >= check
  598.              *        -    +        true
  599.              *        +    -        false
  600.              *        -    -        T >= check
  601.              */
  602.             if ( denom < 0 )
  603.               num = -num, denom = -denom;
  604.             /* Now denom >= 0, so sign(num) = sign(T). */
  605.             if ( check > 0 ?
  606.             (num < 0 || num >= denom * check) :
  607.             (num < 0 && num >= denom * check)
  608.                )
  609.             {    /* OK to use a miter join. */
  610.             gs_fixed_point mpt;
  611.             if_debug0('O', "    ... passes.\n");
  612.             /* Compute the intersection of */
  613.             /* the extended edge lines. */
  614.             if ( line_intersect(outp, &plp->e.cdelta, np,
  615.                         &nplp->o.cdelta, &mpt) == 0
  616.                )
  617.                 outp->x = mpt.x,
  618.                 outp->y = mpt.y;
  619.             }
  620.            }
  621.         if ( (code = gx_path_add_line(ppath, jp1.x, jp1.y)) < 0 ||
  622.              (code = gx_path_add_line(ppath, np1->x, np1->y)) < 0 ||
  623.              (code = gx_path_add_line(ppath, np2->x, np2->y)) < 0 ||
  624.              (code = gx_path_add_line(ppath, jp2.x, jp2.y)) < 0
  625.            )
  626.             return code;
  627.        }
  628.     if ( code < 0 || (code = gx_path_close_subpath(ppath)) < 0 )
  629.         return code;
  630.     return 0;
  631. }
  632.  
  633. /* Routines for cap computations */
  634.  
  635. /* Compute the endpoints of the two caps of a segment. */
  636. private void near
  637. compute_caps(register pl_ptr plp)
  638. {    fixed wx2 = plp->width.x;
  639.     fixed wy2 = plp->width.y;
  640.     plp->o.co.x = plp->o.p.x + wx2, plp->o.co.y = plp->o.p.y + wy2;
  641.     plp->o.cdelta.x = -plp->e.cdelta.x,
  642.       plp->o.cdelta.y = -plp->e.cdelta.y;
  643.     plp->o.ce.x = plp->o.p.x - wx2, plp->o.ce.y = plp->o.p.y - wy2;
  644.     plp->e.co.x = plp->e.p.x - wx2, plp->e.co.y = plp->e.p.y - wy2;
  645.     plp->e.ce.x = plp->e.p.x + wx2, plp->e.ce.y = plp->e.p.y + wy2;
  646. #ifdef DEBUG
  647. if ( gs_debug_c('O') )
  648.     dprintf4("[o]Stroke o=(%f,%f) e=(%f,%f)\n",
  649.          fixed2float(plp->o.p.x), fixed2float(plp->o.p.y),
  650.          fixed2float(plp->e.p.x), fixed2float(plp->e.p.y)),
  651.     dprintf4("\twxy=(%f,%f) lxy=(%f,%f)\n",
  652.          fixed2float(wx2), fixed2float(wy2),
  653.          fixed2float(plp->e.cdelta.x), fixed2float(plp->e.cdelta.y));
  654. #endif
  655. }
  656.  
  657. /* Add a properly capped line endpoint to the path. */
  658. /* The first point may require either moveto or lineto. */
  659. private int near
  660. add_capped(gx_path *ppath, gs_line_cap type,
  661.   int (*add_proc)(P3(gx_path *, fixed, fixed)),    /* gx_path_add_point/line */
  662.   register ep_ptr endp)
  663. {    int code;
  664. #define px endp->p.x
  665. #define py endp->p.y
  666. #define xo endp->co.x
  667. #define yo endp->co.y
  668. #define xe endp->ce.x
  669. #define ye endp->ce.y
  670. #define cdx endp->cdelta.x
  671. #define cdy endp->cdelta.y
  672. #ifdef DEBUG
  673. if ( gs_debug_c('O') )
  674.     dprintf4("[o]cap: p=(%g,%g), co=(%g,%g),\n",
  675.          fixed2float(px), fixed2float(py),
  676.          fixed2float(xo), fixed2float(yo)),
  677.     dprintf4("[o]\tce=(%g,%g), cd=(%g,%g)\n",
  678.          fixed2float(xe), fixed2float(ye),
  679.          fixed2float(cdx), fixed2float(cdy));
  680. #endif
  681.     switch ( type )
  682.        {
  683.     case gs_cap_round:
  684.        {    fixed xm = px + cdx;
  685.         fixed ym = py + cdy;
  686.         if (    (code = (*add_proc)(ppath, xo, yo)) < 0 ||
  687.             (code = gx_path_add_arc(ppath, xo, yo, xm, ym,
  688.                 xo + cdx, yo + cdy, quarter_arc_fraction)) < 0 ||
  689.             (code = gx_path_add_arc(ppath, xm, ym, xe, ye,
  690.                 xe + cdx, ye + cdy, quarter_arc_fraction)) < 0
  691.            ) return code;
  692.        }
  693.         break;
  694.     case gs_cap_square:
  695.         if (    (code = (*add_proc)(ppath, xo + cdx, yo + cdy)) < 0 ||
  696.             (code = gx_path_add_line(ppath, xe + cdx, ye + cdy)) < 0
  697.            ) return code;
  698.         break;
  699.     case gs_cap_butt:
  700.         if (    (code = (*add_proc)(ppath, xo, yo)) < 0 ||
  701.             (code = gx_path_add_line(ppath, xe, ye)) < 0
  702.            ) return code;
  703.        }
  704.     return code;
  705. }
  706.