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