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 / gxfill.c < prev    next >
C/C++ Source or Header  |  1994-01-27  |  23KB  |  719 lines
  1. /* Copyright (C) 1989, 1992 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. /* gxfill.c */
  20. /* Lower-level path filling procedures for Ghostscript library */
  21. #include "gx.h"
  22. #include "gserrors.h"
  23. #include "gxfixed.h"
  24. #include "gxmatrix.h"
  25. #include "gxdevice.h"            /* for gx_color_index */
  26. #include "gzcolor.h"
  27. #include "gzpath.h"
  28. #include "gzstate.h"
  29. #include "gxcpath.h"
  30.  
  31. /* Import the fixed * fixed / fixed routine from gxdraw.c. */
  32. /* The second argument must be less than or equal to the third; */
  33. /* all must be non-negative, and the last must be non-zero. */
  34. extern fixed fixed_mult_quo(P3(fixed, fixed, fixed));
  35.  
  36. /* Define the structure for keeping track of active lines. */
  37. typedef struct active_line_s active_line;
  38. struct active_line_s {
  39.     gs_fixed_point start;        /* x,y where line starts */
  40.     gs_fixed_point end;        /* x,y where line ends */
  41.     fixed dx;            /* end.x - start.x */
  42. #define al_dx(alp) ((alp)->dx)
  43. #define al_dy(alp) ((alp)->end.y - (alp)->start.y)
  44.     fixed y_fast_max;        /* can do x_at_y in fixed point */
  45.                     /* if y <= y_fast_max */
  46. #define set_al_points(alp, startp, endp)\
  47.   (alp)->dx = (endp).x - (startp).x,\
  48.   (alp)->y_fast_max = max_fixed /\
  49.     (((alp)->dx >= 0 ? (alp)->dx : -(alp)->dx) | 1) + (startp).y,\
  50.   (alp)->start = startp, (alp)->end = endp
  51. #define al_x_at_y(alp, yv)\
  52.   ((yv) == (alp)->end.y ? (alp)->end.x :\
  53.    ((yv) <= (alp)->y_fast_max ?\
  54.     ((yv) - (alp)->start.y) * al_dx(alp) / al_dy(alp) :\
  55.     (stat(n_slow_x),\
  56.      fixed_mult_quo(al_dx(alp), (yv) - (alp)->start.y, al_dy(alp)))) +\
  57.    (alp)->start.x)
  58.     fixed x_current;        /* current x position */
  59.     fixed x_next;            /* x position at end of band */
  60.     const segment *pseg;        /* endpoint of this line */
  61.     int direction;            /* direction of line segment */
  62. #define dir_up 1
  63. #define dir_down (-1)
  64. /* "Pending" lines (not reached in the Y ordering yet) use next and prev */
  65. /* to order lines by increasing starting Y.  "Active" lines (being scanned) */
  66. /* use next and prev to order lines by increasing current X, or if the */
  67. /* current Xs are equal, by increasing final X. */
  68.     active_line *prev, *next;
  69. /* Link together active_lines allocated individually */
  70.     active_line *alloc_next;
  71. };
  72.  
  73. /* Define the ordering criterion for active lines. */
  74. /* The xc argument is a copy of lp2->x_current. */
  75. #define x_precedes(lp1, lp2, xc)\
  76.   (lp1->x_current < xc || lp1->x_current == xc &&\
  77.    (lp1->start.x > lp2->start.x || lp1->end.x < lp2->end.x))
  78.  
  79. #ifdef DEBUG
  80. /* Internal procedures for printing active lines */
  81. private void
  82. print_active_line(char *label, active_line *alp)
  83. {    dprintf5("[f]%s %lx(%d): x_current=%f x_next=%f\n",
  84.              label, (ulong)alp, alp->direction,
  85.              fixed2float(alp->x_current), fixed2float(alp->x_next));
  86.     dprintf5("    start=(%f,%f) pt_end=%lx(%f,%f)\n",
  87.              fixed2float(alp->start.x), fixed2float(alp->start.y),
  88.              (ulong)alp->pseg,
  89.              fixed2float(alp->end.x), fixed2float(alp->end.y));
  90.     dprintf2("    prev=%lx next=%lx\n",
  91.          (ulong)alp->prev, (ulong)alp->next);
  92. }
  93. private void
  94. print_line_list(active_line *flp)
  95. {    active_line *lp;
  96.     for ( lp = flp; lp != 0; lp = lp->next )
  97.        {    fixed xc = lp->x_current, xn = lp->x_next;
  98.         dprintf3("[f]%lx(%d): x_current/next=%g",
  99.                  (ulong)lp, lp->direction,
  100.                  fixed2float(xc));
  101.         if ( xn != xc ) dprintf1("/%g", fixed2float(xn));
  102.         dputc('\n');
  103.        }
  104. }
  105. #define print_al(label,alp)\
  106.   if ( gs_debug['F'] ) print_active_line(label, alp)
  107. #else
  108. #define print_al(label,alp) 0
  109. #endif
  110.  
  111. /* Line list structure */
  112. struct line_list_s {
  113.     active_line *active_area;    /* allocated active_line list */
  114.     line_close_segment *close_area;    /* allocated closing line area */
  115.     uint close_count;
  116.     gs_fixed_rect box;        /* intersection of bounding boxes, */
  117.                     /* disregard lines outside this */
  118.     active_line *next_active;    /* next allocation slot */
  119.     active_line *limit;        /* limit of local allocation */
  120.     line_close_segment *next_line;    /* next line allocation slot */
  121.     active_line *y_list;        /* Y-sorted list of pending lines */
  122.     active_line *y_line;        /* most recently inserted line */
  123.     active_line x_head;        /* X-sorted list of active lines */
  124. #define x_list x_head.next
  125.         /* Put the arrays last so the scalars will have */
  126.         /* small displacements. */
  127.         /* Allocate a few active_lines and line_close_segments */
  128.         /* locally to avoid round trips through the allocator. */
  129. #define max_local_active 20
  130.     active_line local_active[max_local_active];
  131. #define max_local_close 5
  132.     line_close_segment local_close[max_local_close];
  133. };
  134. typedef struct line_list_s line_list;
  135. typedef line_list _ss *ll_ptr;
  136.  
  137. /* Forward declarations */
  138. private int alloc_line_list(P2(ll_ptr, uint));
  139. private void free_line_list(P1(ll_ptr));
  140. private int add_y_list(P2(gx_path *, ll_ptr));
  141. private int add_y_line(P4(const segment *, const segment *, int, ll_ptr));
  142. private int fill_loop(P5(const gx_device_color *, int, ll_ptr,
  143.   gs_state *, fixed));
  144. private void insert_x_new(P2(active_line *, ll_ptr));
  145. private int update_x_list(P2(active_line *, fixed));
  146.  
  147. /* Statistics */
  148. #ifdef DEBUG
  149. #define stat(x) (x++)
  150. #define statn(x,n) (x += (n))
  151. private long n_fill;
  152. private long n_fill_alloc;
  153. private long n_y_up;
  154. private long n_y_down;
  155. private long n_x_step;
  156. private long n_slow_x;
  157. private long n_iter;
  158. private long n_find_y;
  159. private long n_band;
  160. private long n_band_step;
  161. private long n_band_fill;
  162. #else
  163. #define stat(x) 0
  164. #define statn(x,n) 0
  165. #endif
  166.  
  167. /* General area filling algorithm. */
  168. /* The adjust parameter is a hack for keeping small characters */
  169. /* from coming out too faint: it specifies an amount by which to expand */
  170. /* all sides of every filled region. */
  171. int
  172. gx_fill_path(gx_path *ppath, gx_device_color *pdevc, gs_state *pgs,
  173.   int rule, fixed adjust)
  174. {    const gx_clip_path *pcpath = pgs->clip_path;
  175.     gs_fixed_rect cbox;
  176.     gx_path *pfpath;
  177.     gx_path ffpath;
  178.     int code;
  179.     line_list lst;
  180.     uint sub_count;
  181.     gx_device_clip cdev;
  182.     int do_clip;
  183.     /* Fatten everything a little to make it look better. */
  184.     /****** This is something of a hack. ******/
  185.     if ( adjust == 0 ) adjust = pgs->fill_adjust;
  186.     /* Start by flattening the path.  We should do this on-the-fly.... */
  187.     if ( !ppath->curve_count )    /* don't need to flatten */
  188.         pfpath = ppath;
  189.     else
  190.        {    if ( (code = gx_path_flatten(ppath, &ffpath, pgs->flatness, (int)pgs->in_cachedevice)) < 0 ) return code;
  191.         pfpath = &ffpath;
  192.        }
  193.     /* Check the bounding boxes. */
  194. #define ibox lst.box
  195.     gx_path_bbox(pfpath, &ibox);
  196.     gx_cpath_box_for_check(pcpath, &cbox);
  197.     if ( ibox.q.y <= cbox.q.y && ibox.q.x <= cbox.q.x &&
  198.          ibox.p.y >= cbox.p.y && ibox.p.x >= cbox.p.x
  199.        )
  200.        {    /* Path lies entirely within clipping rectangle */
  201.         do_clip = 0;
  202.        }
  203.     else
  204.        {    /* Intersect the path box and the clip bounding box. */
  205.         /* If the intersection is empty, this fill is a no-op. */
  206.         gs_fixed_rect bbox;
  207.         bbox = pcpath->path.bbox;
  208.         if ( ibox.p.x >= bbox.q.x || ibox.p.y >= bbox.q.y ||
  209.             ibox.q.x <= bbox.p.x || ibox.q.y <= bbox.p.y
  210.            )
  211.            {    /* Intersection of boxes is empty! */
  212.             code = 0;
  213.             goto skip;
  214.            }
  215.         do_clip = 1;
  216.        }
  217. #undef ibox
  218.     sub_count = pfpath->subpath_count;
  219.     if ( !(code = alloc_line_list(&lst, sub_count)) )
  220.        {    gx_device *save_dev;
  221.         if ( (code = add_y_list(pfpath, &lst)) < 0 )
  222.             goto nope;
  223.         if ( do_clip )
  224.            {    /* Set up a clipping device. */
  225.             gx_device *dev = (gx_device *)&cdev;
  226.             save_dev = gs_currentdevice(pgs);
  227.             cdev = gs_clip_device;
  228.             cdev.target = sav