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