home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 5 / FreshFish_July-August1994.bin / bbs / gnu / gs-2.6.1.4-src.lha / src / amiga / gs-2.6.1.4 / gxpcopy.c < prev    next >
C/C++ Source or Header  |  1994-01-27  |  17KB  |  501 lines
  1. /* Copyright (C) 1992, 1993 Aladdin Enterprises.  All rights reserved.
  2.  
  3. This file is part of Ghostscript.
  4.  
  5. Ghostscript is distributed in the hope that it will be useful, but
  6. WITHOUT ANY WARRANTY.  No author or distributor accepts responsibility
  7. to anyone for the consequences of using it or for whether it serves any
  8. particular purpose or works at all, unless he says so in writing.  Refer
  9. to the Ghostscript General Public License for full details.
  10.  
  11. Everyone is granted permission to copy, modify and redistribute
  12. Ghostscript, but only under the conditions described in the Ghostscript
  13. General Public License.  A copy of this license is supposed to have been
  14. given to you along with Ghostscript so you can know your rights and
  15. responsibilities.  It should be in a file named COPYING.  Among other
  16. things, the copyright notice and this notice must be preserved on all
  17. copies.  */
  18.  
  19. /* gxpcopy.c */
  20. /* Path copying and flattening for Ghostscript library */
  21. #include "math_.h"
  22. #include "gx.h"
  23. #include "gserrors.h"
  24. #include "gxfixed.h"
  25. #include "gxarith.h"
  26. #include "gzpath.h"
  27.  
  28. /* Forward declarations */
  29. private int copy_path(P4(const gx_path *, gx_path *, fixed, int));
  30. private int flatten_recur(P8(gx_path *,
  31.   fixed, fixed, fixed, fixed, fixed, fixed, fixed));
  32. private int flatten_sample(P8(gx_path *, int,
  33.   fixed, fixed, fixed, fixed, fixed, fixed));
  34.  
  35. /* Copy a path */
  36. int
  37. gx_path_copy(const gx_path *ppath_old, gx_path *ppath, int init)
  38. {    return copy_path(ppath_old, ppath, max_fixed, init);
  39. }
  40.  
  41. /* Flatten a path. */
  42. /* If flatness is zero, use sampling rather than subdivision: */
  43. /* this is important for Type 1 fonts. */
  44. private fixed
  45. scale_flatness(floatp flatness)
  46. {    fixed scaled_flat = float2fixed(flatness);
  47.     return (scaled_flat > int2fixed(100) ? int2fixed(100) :
  48.         scaled_flat < fixed_half ? fixed_0 :
  49.         scaled_flat);
  50. }
  51. int
  52. gx_path_flatten(const gx_path *ppath_old, gx_path *ppath, floatp flatness, int in_BuildCharGlyph)
  53. {    return copy_path(ppath_old, ppath,
  54.              (in_BuildCharGlyph ? fixed_0 : scale_flatness(flatness)),
  55.              1);
  56. }
  57.  
  58. /* Add a flattened curve to a path. */
  59. int
  60. gx_path_add_flattened_curve(gx_path *ppath,
  61.   fixed x1, fixed y1, fixed x2, fixed y2, fixed x3, fixed y3,
  62.   floatp flatness)
  63. {    return flatten_recur(ppath, x1, y1, x2, y2, x3, y3,
  64.                  scale_flatness(flatness));
  65. }
  66.  
  67. /* Copy a path, optionally flattening it. */
  68. /* If the copy fails, free the new path. */
  69. private int
  70. copy_path(const gx_path *ppath_old, gx_path *ppath, fixed scaled_flat,
  71.   int init)
  72. {    gx_path old;
  73.     const segment *pseg;
  74.     int code;
  75. #ifdef DEBUG
  76. if ( gs_debug['p'] )
  77.     gx_dump_path(ppath_old, "before copy_path");
  78. #endif
  79.     old = *ppath_old;
  80.     if ( init )
  81.         gx_path_init(ppath, ppath_old->memory_procs);
  82.     pseg = (const segment *)(old.first_subpath);
  83.     while ( pseg )
  84.        {    switch ( pseg->type )
  85.            {
  86.         case s_start:
  87.             code = gx_path_add_point(ppath, pseg->pt.x, pseg->pt.y);
  88.             break;
  89.         case s_curve:
  90.            {    curve_segment *pc = (curve_segment *)pseg;
  91.             if ( scaled_flat == max_fixed )    /* don't flatten */
  92.                 code = gx_path_add_curve(ppath,
  93.                     pc->p1.x, pc->p1.y,
  94.                     pc->p2.x, pc->p2.y,
  95.                     pc->pt.x, pc->pt.y);
  96.             else
  97.                 code = flatten_recur(ppath,
  98.                     pc->p1.x, pc->p1.y,
  99.                     pc->p2.x, pc->p2.y,
  100.                     pc->pt.x, pc->pt.y,
  101.                     scaled_flat);
  102.             break;
  103.            }
  104.         case s_line:
  105.             code = gx_path_add_line(ppath, pseg->pt.x, pseg->pt.y);
  106.             break;
  107.         case s_line_close:
  108.             code = gx_path_close_subpath(ppath);
  109.             break;
  110.            }
  111.         if ( code )
  112.            {    gx_path_release(ppath);
  113.             if ( ppath == ppath_old )
  114.                 *ppath = old;
  115.             return code;
  116.            }
  117.         pseg = pseg->next;
  118.     }
  119.     if ( !old.subpath_open && old.position_valid )
  120.         gx_path_add_point(ppath, old.position.x, old.position.y);
  121. #ifdef DEBUG
  122. if ( gs_debug['p'] )
  123.     gx_dump_path(ppath, "after copy_path");
  124. #endif
  125.     return 0;
  126. }
  127. /* Internal routine to flatten a curve. */
  128. /* This calls itself recursively, using binary subdivision, */
  129. /* until the approximation is good enough to satisfy the */
  130. /* flatness requirement.  The starting point is ppath->position, */
  131. /* which gets updated as line segments are added. */
  132.  
  133. /* Maximum number of points for sampling if we want accurate rasterizing. */
  134. /* (num_sample_max - 1)^3 must fit into an int with a bit to spare. */
  135. #if arch_sizeof_int == 2
  136. #  define num_sample_max 26
  137. #else
  138. #  define num_sample_max (1 << ((size_of(int) * 8 - 2) / 3))
  139. #endif
  140.  
  141. /* Table of f(i) = 256 * sqrt(1 + (i/64)^2). */
  142. /* This is good to within 1% or better. */
  143. #define sqrt_index_shift 6        /* scaling of index */
  144. #define sqrt_value_shift 8        /* scaling of value */
  145. private int scaled_sqrt_tab[65] =
  146.    {    256, 256, 256, 256, 256, 256, 257, 257,
  147.     257, 258, 259, 259, 260, 261, 262, 262,
  148.     263, 264, 265, 267, 268, 269, 270, 272,
  149.     273, 274, 276, 277, 279, 281, 282, 284,
  150.     286, 288, 289, 291, 293, 295, 297, 299,
  151.     301, 304, 306, 308, 310, 312, 315, 317,
  152.     320, 322, 324, 327, 329, 332, 334, 337,
  153.     340, 342, 345, 348, 350, 353, 356, 359,
  154.     362
  155.    };
  156.  
  157. private int
  158. flatten_recur(gx_path *ppath,
  159.   fixed x1, fixed y1, fixed x2, fixed y2, fixed x3, fixed y3,
  160.   fixed scaled_flat)
  161. {    fixed
  162.       x0 = ppath->position.x,
  163.       y0 = ppath->position.y;
  164. top:
  165. #ifdef DEBUG
  166. if ( gs_debug['2'] )
  167.     dprintf4("[2]x0=%f y0=%f x1=%f y1=%f\n",
  168.          fixed2float(x0), fixed2float(y0),
  169.          fixed2float(x1), fixed2float(y1)),
  170.     dprintf4("   x2=%f y2=%f x3=%f y3=%f\n",
  171.          fixed2float(x2), fixed2float(y2),
  172.          fixed2float(x3), fixed2float(y3));
  173. #endif
  174.     /*
  175.      * Compute the maximum distance of the curve from
  176.      * the line (x0,y0)->(x3,y3).  We do this conservatively
  177.      * by observing that the curve is enclosed by the
  178.      * quadrilateral of its control points, so we simply
  179.      * compute the distances of (x1,y1) and (x2,y2)
  180.      * from the line.  Letting dx = x3-x0 and dy = y3-y0,
  181.      * the distance of (xp,yp) from the line is
  182.      * abs(N)/sqrt(D), where N = dy*(xp-x0)-dx*(yp-y0) and
  183.      * D = dx*dx+dy*dy; hence we want to test abs(N) <= sqrt(D)*F,
  184.      * where F is the flatness parameter from the graphics state.
  185.      * We can do this more efficiently by letting t=dy/dx, and
  186.      * testing abs(N1) <= sqrt(D1)*f, where N1=t*(xp-x0)-(yp-y0) and
  187.      * D1 = 1+t*t.  If dx < dy, we swap x and y for this
  188.      * computation.  This guarantees abs(t) <= 1, which allows us to
  189.      * compute sqrt(1+t*t) by table lookup on the high bits of abs(t).
  190.      *
  191.      * To avoid replacing shallow curves by short straight lines,
  192.      * we halve the flatness if the curve is very short.
  193.      * We don't do anything about long, nearly flat curves.
  194.      *
  195.      * Note that if scaled_flat is very small, we don't do any of this;
  196.      * instead, we just check whether abs(dx) and abs(dy) are
  197.      * small enough to switch over to sampling rather than dividing.
  198.       */
  199.      { fixed dx3 = x3 - x0;
  200.        fixed adx3 = any_abs(dx3);
  201.        fixed dy3 = y3 - y0;
  202.        fixed ady3 = any_abs(dy3);
  203.        fixed flat = scaled_flat;
  204.        /* We have to be quite careful to ensure that */
  205.        /* none of the multiplications will overflow. */
  206. #define short_max 0x7ff0L
  207. #define reduce_3(ad3, maxv)\
  208.   while ( ad3 > maxv )\
  209.     adx3 >>= 1, ady3 >>= 1,\
  210.     dx3 = arith_rshift_1(dx3), dy3 = arith_rshift_1(dy3)
  211. #define reduce_d(d)\
  212.   for ( shift = 0; (d < 0 ? d < -short_max : d > short_max); shift++ )\
  213.     d = arith_rshift_1(d)
  214.        if ( adx3 > ady3 )
  215.         {    fixed d, dx, dy, dist;
  216.         int shift;
  217.         if ( scaled_flat == 0 )
  218.         { if ( adx3 < int2fixed(num_sample_max - 1) / 2 )
  219.           { int n = fixed2int_var_rounded(adx3) * 2 + 1;
  220.             int code = flatten_sample(ppath, max(n, 3), x1, y1,
  221.                           x2, y2, x3, y3);
  222.             if ( code <= 0 ) return code;
  223.           }
  224.           goto sub;
  225.         }
  226.         if ( adx3 < 16 ) flat >>= 1;
  227.         reduce_3(ady3, short_max);
  228.         d = (scaled_sqrt_tab[(ady3 << sqrt_index_shift) / adx3] * flat) >> sqrt_value_shift;
  229.         dx = x1 - x0, dy = y1 - y0;
  230.         reduce_d(dx);
  231.         if ( ((dist = ((dx * dy3 / dx3) << shift) - dy) < 0 ?
  232.               -dist : dist) > d )
  233.           goto sub;    /* not flat enough */
  234.         dx = x2 - x0, dy = y2 - y0;
  235.         reduce_d(dx);
  236.         if ( ((dist = ((dx * dy3 / dx3) << shift) - dy) < 0 ?
  237.               -dist : dist) > d )
  238.           goto sub;    /* not flat enough */
  239.         }
  240.        else if ( ady3 != 0 )
  241.         {    fixed d, dy, dx, dist;
  242.         int shift;
  243.         if ( scaled_flat == 0 )
  244.         { if ( ady3 < int2fixed(num_sample_max - 1) / 2 )
  245.           { int n = fixed2int_var_rounded(ady3) * 2 + 1;
  246.             int c