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: gxfilltr.h 9783 2009-06-08 18:16:29Z ray $ */
15 /* Configurable algorithm for decomposing a spot into trapezoids. */
16
17 /*
18 * Since we need several statically defined variants of this algorithm,
19 * we store it in .h file and include it several times into gxfill.c .
20 * Configuration macros (template arguments) are :
21 *
22 * IS_SPOTAN - is the target device a spot analyzer ("spotan").
23 * PSEUDO_RASTERIZATION - use pseudo-rasterization.
24 * SMART_WINDING - even-odd filling rule for each contour independently.
25 * FILL_ADJUST - fill adjustment is not zero
26 * FILL_DIRECT - See LOOP_FILL_RECTANGLE_DIRECT.
27 * TEMPLATE_spot_into_trapezoids - the name of the procedure to generate.
28 * ADVANCE_WINDING(inside, alp, ll) - a macro for advancing the winding counter.
29 * INSIDE_PATH_P(inside, rule) - a macro for checking the winding rule.
30 */
31
32 /* ---------------- Trapezoid decomposition loop ---------------- */
33
34 /* Takes lines off of y_list and adds them to */
35 /* x_list as needed. band_mask limits the size of each band, */
36 /* by requiring that ((y1 - 1) & band_mask) == (y0 & band_mask). */
37 static int
TEMPLATE_spot_into_trapezoids(line_list * ll,fixed band_mask)38 TEMPLATE_spot_into_trapezoids (line_list *ll, fixed band_mask)
39 {
40 const fill_options fo = *ll->fo;
41 int rule = fo.rule;
42 const fixed y_limit = fo.ymax;
43 active_line *yll = ll->y_list;
44 fixed y;
45 int code;
46 const bool all_bands = fo.is_spotan;
47
48 if (yll == 0)
49 return 0; /* empty list */
50 y = yll->start.y; /* first Y value */
51 ll->x_list = 0;
52 ll->x_head.x_current = min_fixed; /* stop backward scan */
53 ll->margin_set0.y = fixed_pixround(y) - fixed_half;
54 ll->margin_set1.y = fixed_pixround(y) - fixed_1 - fixed_half;
55 while (1) {
56 fixed y1;
57 active_line *alp, *plp = NULL;
58 bool covering_pixel_centers;
59
60 INCR(iter);
61 /* Move newly active lines from y to x list. */
62 while (yll != 0 && yll->start.y == y) {
63 active_line *ynext = yll->next; /* insert smashes next/prev links */
64
65 ll->y_list = ynext;
66 if (ll->y_line == yll)
67 ll->y_line = ynext;
68 if (ynext != NULL)
69 ynext->prev = NULL;
70 if (yll->direction == DIR_HORIZONTAL) {
71 if (!PSEUDO_RASTERIZATION) {
72 /*
73 * This is a hack to make sure that isolated horizontal
74 * lines get stroked.
75 */
76 int yi = fixed2int_pixround(y - (!FILL_ADJUST ? 0 : fo.adjust_below));
77 int xi, wi;
78
79 if (yll->start.x <= yll->end.x) {
80 xi = fixed2int_pixround(yll->start.x - (!FILL_ADJUST ? 0 : fo.adjust_left));
81 wi = fixed2int_pixround(yll->end.x + (!FILL_ADJUST ? 0 : fo.adjust_right)) - xi;
82 } else {
83 xi = fixed2int_pixround(yll->end.x - (!FILL_ADJUST ? 0 : fo.adjust_left));
84 wi = fixed2int_pixround(yll->start.x + (!FILL_ADJUST ? 0 : fo.adjust_right)) - xi;
85 }
86 VD_RECT(xi, yi, wi, 1, VD_TRAP_COLOR);
87 code = LOOP_FILL_RECTANGLE_DIRECT(&fo, xi, yi, wi, 1);
88 if (code < 0)
89 return code;
90 } else if (PSEUDO_RASTERIZATION)
91 insert_h_new(yll, ll);
92 } else
93 insert_x_new(yll, ll);
94 yll = ynext;
95 }
96 /* Mustn't leave by Y before process_h_segments. */
97 if (ll->x_list == 0) { /* No active lines, skip to next start */
98 if (yll == 0)
99 break; /* no lines left */
100 /* We don't close margin set here because the next set
101 * may fall into same window. */
102 y = yll->start.y;
103 ll->h_list1 = ll->h_list0;
104 ll->h_list0 = 0;
105 continue;
106 }
107 if (vd_enabled) {
108 vd_circle(0, y, 3, RGB(255, 0, 0));
109 y += 0; /* Just a good place for a debugger breakpoint */
110 }
111 /* Find the next evaluation point. */
112 /* Start by finding the smallest y value */
113 /* at which any currently active line ends */
114 /* (or the next to-be-active line begins). */
115 y1 = (yll != 0 ? yll->start.y : ll->y_break);
116 /* Make sure we don't exceed the maximum band height. */
117 {
118 fixed y_band = y | ~band_mask;
119
120 if (y1 > y_band)
121 y1 = y_band + 1;
122 }
123 for (alp = ll->x_list; alp != 0; alp = alp->next) {
124 if (alp->end.y < y1)
125 y1 = alp->end.y;
126 }
127 # ifdef DEBUG
128 if (gs_debug_c('F')) {
129 dlprintf2("[F]before loop: y=%f y1=%f:\n",
130 fixed2float(y), fixed2float(y1));
131 print_line_list(ll->x_list);
132 }
133 # endif
134 if (y == y1) {
135 code = process_h_segments(ll, y);
136 if (code < 0)
137 return code;
138 { int code1 = move_al_by_y(ll, y1);
139 if (code1 < 0)
140 return code1;
141 }
142 if (code > 0) {
143 yll = ll->y_list; /* add_y_line_aux in process_h_segments changes it. */
144 continue;
145 }
146
147 }
148 if (y >= y_limit)
149 break;
150 /* Now look for line intersections before y1. */
151 covering_pixel_centers = COVERING_PIXEL_CENTERS(y, y1,
152 (!FILL_ADJUST ? 0 : fo.adjust_below),
153 (!FILL_ADJUST ? 0 : fo.adjust_above));
154 if (y != y1) {
155 intersect_al(ll, y, &y1, (covering_pixel_centers ? 1 : -1), all_bands); /* May change y1. */
156 covering_pixel_centers = COVERING_PIXEL_CENTERS(y, y1,
157 (!FILL_ADJUST ? 0 : fo.adjust_below),
158 (!FILL_ADJUST ? 0 : fo.adjust_above));
159 }
160 /* Prepare dropout prevention. */
161 if (PSEUDO_RASTERIZATION) {
162 code = start_margin_set(fo.dev, ll, y1);
163 if (code < 0)
164 return code;
165 }
166 /* Fill a multi-trapezoid band for the active lines. */
167 if (covering_pixel_centers || all_bands) {
168 int inside = 0;
169 active_line *flp = NULL;
170
171 if (SMART_WINDING)
172 memset(ll->windings, 0, sizeof(ll->windings[0]) * ll->contour_count);
173 INCR(band);
174 /* Generate trapezoids */
175 for (alp = ll->x_list; alp != 0; alp = alp->next) {
176 int code;
177
178 print_al("step", alp);
179 INCR(band_step);
180 if (!INSIDE_PATH_P(inside, rule)) { /* i.e., outside */
181 ADVANCE_WINDING(inside, alp, ll);
182 if (INSIDE_PATH_P(inside, rule)) /* about to go in */
183 flp = alp;
184 continue;
185 }
186 /* We're inside a region being filled. */
187 ADVANCE_WINDING(inside, alp, ll);
188 if (INSIDE_PATH_P(inside, rule)) /* not about to go out */
189 continue;
190 /* We just went from inside to outside,
191 chech whether we'll immediately go inside. */
192 if (alp->next != NULL &&
193 alp->x_current == alp->next->x_current &&
194 alp->x_next == alp->next->x_next) {
195 /* If the next trapezoid contacts this one, unite them.
196 This simplifies data for the spot analyzer
197 and reduces the number of trapezoids in the rasterization.
198 Note that the topology possibly isn't exactly such
199 as we generate by this uniting :
200 Due to arithmetic errors in x_current, x_next
201 we can unite things, which really are not contacting.
202 But this level of the topology precision is enough for
203 the glyph grid fitting.
204 Also note that
205 while a rasterization with dropout prevention
206 it may cause a shift when choosing a pixel
207 to paint with a narrow trapezoid. */
208 alp = alp->next;
209 ADVANCE_WINDING(inside, alp, ll);
210 continue;
211 }
212 /* We just went from inside to outside, so fill the region. */
213 INCR(band_fill);
214 if (FILL_ADJUST && !(flp->end.x == flp->start.x && alp->end.x == alp->start.x) &&
215 (fo.adjust_below | fo.adjust_above) != 0) {
216 /* Assuming pseudo_rasterization = false. */
217 if (FILL_DIRECT)
218 code = slant_into_trapezoids__fd(ll, flp, alp, y, y1);
219 else
220 code = slant_into_trapezoids__nd(ll, flp, alp, y, y1);
221 } else {
222 fixed ybot = max(y, fo.pbox->p.y);
223 fixed ytop = min(y1, fo.pbox->q.y);
224
225 if (IS_SPOTAN) {
226 /* We can't pass data through the device interface because
227 we need to pass segment pointers. We're unhappy of that. */
228 code = gx_san_trap_store((gx_device_spot_analyzer *)fo.dev,
229 y, y1, flp->x_current, alp->x_current, flp->x_next, alp->x_next,
230 flp->pseg, alp->pseg, flp->direction, alp->direction);
231 } else {
232 if (flp->end.x == flp->start.x && alp->end.x == alp->start.x) {
233 if (FILL_ADJUST) {
234 ybot = max(y - fo.adjust_below, fo.pbox->p.y);
235 ytop = min(y1 + fo.adjust_above, fo.pbox->q.y);
236 }
237 if (ytop > ybot) {
238 int yi = fixed2int_pixround(ybot);
239 int hi = fixed2int_pixround(ytop) - yi;
240 int xli = fixed2int_var_pixround(flp->end.x - (!FILL_ADJUST ? 0 : fo.adjust_left));
241 int xi = fixed2int_var_pixround(alp->end.x + (!FILL_ADJUST ? 0 : fo.adjust_right));
242
243 #ifdef FILL_ZERO_WIDTH
244 if ( (xli == xi) && (PSEUDO_RASTERIZATION ||
245 (FILL_ADJUST && (fo.adjust_right | fo.adjust_left) != 0))) {
246 #else
247 if (PSEUDO_RASTERIZATION && xli == xi) {
248 #endif
249 /*
250 * The scan is empty but we should paint something
251 * against a dropout. Choose one of two pixels which
252 * is closer to the "axis".
253 */
254 fixed xx = int2fixed(xli);
255
256 if (xx - flp->end.x < alp->end.x - xx)
257 ++xi;
258 else
259 --xli;
260 }
261 vd_rect(flp->end.x, y, alp->end.x, y1, 1, VD_TRAP_COLOR);
262 code = LOOP_FILL_RECTANGLE_DIRECT(&fo, xli, yi, xi - xli, hi);
263 } else
264 code = 0;
265 } else if (ybot < ytop) {
266 gs_fixed_edge le, re;
267
268 le.start = flp->start;
269 le.end = flp->end;
270 re.start = alp->start;
271 re.end = alp->end;
272 vd_quad(flp->x_current, ybot, alp->x_current, ybot, alp->x_next, ytop, flp->x_next, ytop, 1, VD_TRAP_COLOR);
273 if (PSEUDO_RASTERIZATION) {
274 int flags = ftf_pseudo_rasterization;
275
276 if (flp->start.x == alp->start.x && flp->start.y == y && alp->start.y == y)
277 flags |= ftf_peak0;
278 if (flp->end.x == alp->end.x && flp->end.y == y1 && alp->end.y == y1)
279 flags |= ftf_peak0;
280 if (FILL_DIRECT)
281 code = gx_fill_trapezoid_cf_fd(fo.dev, &le, &re, ybot, ytop, flags, fo.pdevc, fo.lop);
282 else
283 code = gx_fill_trapezoid_cf_nd(fo.dev, &le, &re, ybot, ytop, flags, fo.pdevc, fo.lop);
284 } else
285 code = fo.fill_trap(fo.dev,
286 &le, &re, ybot, ytop, false, fo.pdevc, fo.lop);
287 } else
288 code = 0;
289 }
290 if (PSEUDO_RASTERIZATION) {
291 if (code < 0)
292 return code;
293 code = complete_margin(ll, flp, alp, y, y1);
294 if (code < 0)
295 return code;
296 code = margin_interior(ll, flp, alp, y, y1);
297 if (code < 0)
298 return code;
299 code = add_margin(ll, flp, alp, y, y1);
300 if (code < 0)
301 return code;
302 code = process_h_lists(ll, plp, flp, alp, y, y1);
303 plp = alp;
304 }
305 }
306 if (code < 0)
307 return code;
308 }
309 } else {
310 /* No trapezoids generation needed. */
311 if (PSEUDO_RASTERIZATION) {
312 /* Process dropouts near trapezoids. */
313 active_line *flp = NULL;
314 int inside = 0;
315
316 if (SMART_WINDING)
317 memset(ll->windings, 0, sizeof(ll->windings[0]) * ll->contour_count);
318 for (alp = ll->x_list; alp != 0; alp = alp->next) {
319 if (!INSIDE_PATH_P(inside, rule)) { /* i.e., outside */
320 ADVANCE_WINDING(inside, alp, ll);
321 if (INSIDE_PATH_P(inside, rule)) /* about to go in */
322 flp = alp;
323 continue;
324 }
325 /* We're inside a region being filled. */
326 ADVANCE_WINDING(inside, alp, ll);
327 if (INSIDE_PATH_P(inside, rule)) /* not about to go out */
328 continue;
329 code = continue_margin(ll, flp, alp, y, y1);
330 if (code < 0)
331 return code;
332 code = process_h_lists(ll, plp, flp, alp, y, y1);
333 plp = alp;
334 if (code < 0)
335 return code;
336 }
337 }
338 }
339 if (PSEUDO_RASTERIZATION && plp != 0) {
340 code = process_h_lists(ll, plp, 0, 0, y, y1);
341 if (code < 0)
342 return code;
343 }
344 code = move_al_by_y(ll, y1);
345 if (code < 0)
346 return code;
347 ll->h_list1 = ll->h_list0;
348 ll->h_list0 = 0;
349 y = y1;
350 }
351 if (PSEUDO_RASTERIZATION) {
352 code = process_h_lists(ll, 0, 0, 0, y, y + 1 /*stub*/);
353 if (code < 0)
354 return code;
355 code = close_margins(fo.dev, ll, &ll->margin_set1);
356 if (code < 0)
357 return code;
358 return close_margins(fo.dev, ll, &ll->margin_set0);
359 }
360 return 0;
361 }
362
363