1 /* Copyright (C) 2001-2006 Artifex Software, Inc. 2 All Rights Reserved. 3 4 This software is provided AS-IS with no warranty, either express or 5 implied. 6 7 This software is distributed under license and may not be copied, modified 8 or distributed except as expressly authorized under the terms of that 9 license. Refer to licensing information at http://www.artifex.com/ 10 or contact Artifex Software, Inc., 7 Mt. Lassen Drive - Suite A-134, 11 San Rafael, CA 94903, U.S.A., +1(415)492-9861, for further information. 12 */ 13 14 /* $Id: gxfill.h 8022 2007-06-05 22:23:38Z giles $ */ 15 /* Common structures for the filling algorithm and dropout prevention. */ 16 17 #ifndef gxfill_INCLUDED 18 # define gxfill_INCLUDED 19 20 /* Define the structure for keeping track of active lines. */ 21 #ifndef active_line_DEFINED 22 # define active_line_DEFINED 23 typedef struct active_line_s active_line; 24 #endif 25 struct active_line_s { 26 gs_fixed_point start; /* x,y where line starts */ 27 gs_fixed_point end; /* x,y where line ends */ 28 gs_fixed_point diff; /* end - start */ 29 fixed y_fast_max; /* can do x_at_y in fixed point */ 30 /* if y <= y_fast_max */ 31 fixed num_adjust; /* 0 if diff.x >= 0, -diff.y + epsilon if */ 32 /* diff.x < 0 and division truncates */ 33 #if ARCH_DIV_NEG_POS_TRUNCATES 34 /* neg/pos truncates, we must bias the numberator. */ 35 # define SET_NUM_ADJUST(alp) \ 36 (alp)->num_adjust =\ 37 ((alp)->diff.x >= 0 ? 0 : -(alp)->diff.y + fixed_epsilon) 38 # define ADD_NUM_ADJUST(num, alp) ((num) + (alp)->num_adjust) 39 # define MAX_MINUS_NUM_ADJUST(alp) ADD_NUM_ADJUST(max_fixed, alp) 40 #else 41 /* neg/pos takes the floor, no special action is needed. */ 42 # define SET_NUM_ADJUST(alp) DO_NOTHING 43 # define ADD_NUM_ADJUST(num, alp) (num) 44 # define MAX_MINUS_NUM_ADJUST(alp) max_fixed 45 #endif 46 #define SET_AL_POINTS(alp, startp, endp)\ 47 BEGIN\ 48 (alp)->diff.y = (endp).y - (startp).y;\ 49 (alp)->diff.x = (endp).x - (startp).x;\ 50 SET_NUM_ADJUST(alp);\ 51 (alp)->y_fast_max = MAX_MINUS_NUM_ADJUST(alp) /\ 52 (((alp)->diff.x >= 0 ? (alp)->diff.x : -(alp)->diff.x) | 1) +\ 53 (startp).y;\ 54 (alp)->start = startp, (alp)->end = endp;\ 55 END 56 /* 57 * We know that alp->start.y <= yv <= alp->end.y, because the fill loop 58 * guarantees that the only lines being considered are those with this 59 * property. 60 */ 61 #define AL_X_AT_Y(alp, yv)\ 62 ((yv) == (alp)->end.y ? (alp)->end.x :\ 63 ((yv) <= (alp)->y_fast_max ?\ 64 ADD_NUM_ADJUST(((yv) - (alp)->start.y) * (alp)->diff.x, alp) / (alp)->diff.y :\ 65 (INCR_EXPR(slow_x),\ 66 fixed_mult_quo((alp)->diff.x, (yv) - (alp)->start.y, (alp)->diff.y))) +\ 67 (alp)->start.x) 68 fixed x_current; /* current x position */ 69 fixed x_next; /* x position at end of band */ 70 const segment *pseg; /* endpoint of this line */ 71 int direction; /* direction of line segment */ 72 #define DIR_UP 1 73 #define DIR_HORIZONTAL 0 /* (these are handled specially) */ 74 #define DIR_DOWN (-1) 75 bool monotonic_x; /* "false" means "don't know"; only for scanline. */ 76 bool monotonic_y; /* "false" means "don't know"; only for scanline. */ 77 gx_flattened_iterator fi; 78 bool more_flattened; 79 int contour_count; 80 /* 81 * "Pending" lines (not reached in the Y ordering yet) use next and prev 82 * to order lines by increasing starting Y. "Active" lines (being scanned) 83 * use next and prev to order lines by increasing current X, or if the 84 * current Xs are equal, by increasing final X. 85 */ 86 active_line *prev, *next; 87 /* Link together active_lines allocated individually */ 88 active_line *alloc_next; 89 }; 90 91 typedef struct fill_options_s { 92 bool pseudo_rasterization; /* See comment about "pseudo-rasterization". */ 93 fixed ymin, ymax; 94 const gx_device_color * pdevc; 95 gs_logical_operation_t lop; 96 bool fill_direct; 97 fixed fixed_flat; 98 bool fill_by_trapezoids; 99 fixed adjust_left, adjust_right; 100 fixed adjust_below, adjust_above; 101 gx_device *dev; 102 const gs_fixed_rect * pbox; 103 bool is_spotan; 104 int rule; 105 dev_proc_fill_rectangle((*fill_rect)); 106 dev_proc_fill_trapezoid((*fill_trap)); 107 } fill_options; 108 109 /* Line list structure */ 110 #ifndef line_list_DEFINED 111 # define line_list_DEFINED 112 typedef struct line_list_s line_list; 113 #endif 114 struct line_list_s { 115 gs_memory_t *memory; 116 active_line *active_area; /* allocated active_line list */ 117 active_line *next_active; /* next allocation slot */ 118 active_line *limit; /* limit of local allocation */ 119 int close_count; /* # of added closing lines */ 120 active_line *y_list; /* Y-sorted list of pending lines */ 121 active_line *y_line; /* most recently inserted line */ 122 active_line x_head; /* X-sorted list of active lines */ 123 #define x_list x_head.next 124 active_line *h_list0, *h_list1; /* lists of horizontal lines for y, y1 */ 125 margin_set margin_set0, margin_set1; 126 margin *free_margin_list; 127 int *windings; 128 int local_margin_alloc_count; 129 int bbox_left, bbox_width; 130 int main_dir; 131 fixed y_break; 132 const fill_options * const fo; 133 int contour_count; 134 /* Put the arrays last so the scalars will have */ 135 /* small displacements. */ 136 /* Allocate a few active_lines locally */ 137 /* to avoid round trips through the allocator. */ 138 #if arch_small_memory 139 # define MAX_LOCAL_ACTIVE 6 /* don't overburden the stack */ 140 # define MAX_LOCAL_SECTION 50 141 #else 142 # define MAX_LOCAL_ACTIVE 20 143 # define MAX_LOCAL_SECTION 100 144 #endif 145 active_line local_active[MAX_LOCAL_ACTIVE]; 146 margin local_margins[MAX_LOCAL_ACTIVE]; 147 section local_section0[MAX_LOCAL_SECTION]; 148 section local_section1[MAX_LOCAL_SECTION]; 149 int local_windings[MAX_LOCAL_ACTIVE]; 150 }; 151 152 #define LOOP_FILL_RECTANGLE_DIRECT(fo, x, y, w, h)\ 153 (/*fo->fill_direct*/FILL_DIRECT ?\ 154 (fo)->fill_rect((fo)->dev, x, y, w, h, (fo)->pdevc->colors.pure) :\ 155 gx_fill_rectangle_device_rop(x, y, w, h, (fo)->pdevc, (fo)->dev, (fo)->lop)) 156 157 /* ---------------- Statistics ---------------- */ 158 159 #ifdef DEBUG 160 struct stats_fill_s { 161 long 162 fill, fill_alloc, y_up, y_down, horiz, x_step, slow_x, iter, find_y, 163 band, band_step, band_fill, afill, slant, slant_shallow, sfill, 164 mq_cross, cross_slow, cross_low, order, slow_order; 165 }; 166 typedef struct stats_fill_s stats_fill_t; 167 extern stats_fill_t stats_fill; 168 169 # define INCR(x) (++(stats_fill.x)) 170 # define INCR_EXPR(x) INCR(x) 171 # define INCR_BY(x,n) (stats_fill.x += (n)) 172 #else 173 # define INCR(x) DO_NOTHING 174 # define INCR_EXPR(x) discard(0) 175 # define INCR_BY(x,n) DO_NOTHING 176 #endif 177 178 #endif /* gxfill_INCLUDED */ 179 180 181