1 /* Copyright (C) 2002 artofcode LLC. 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: gxfilltr.h,v 1.12 2005/01/25 11:18:42 igor Exp $ */
18 /* Configurable algorithm for decomposing a spot into trapezoids. */
19
20 /*
21 * Since we need several statically defined variants of this algorithm,
22 * we store it in .h file and include it several times into gxfill.c .
23 * Configuration macros (template arguments) are :
24 *
25 * IS_SPOTAN - is the target device a spot analyzer ("spotan").
26 * PSEUDO_RASTERIZATION - use pseudo-rasterization.
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 */
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 private 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 move_al_by_y(ll, y1);
139 if (code > 0) {
140 yll = ll->y_list; /* add_y_line_aux in process_h_segments changes it. */
141 continue;
142 }
143
144 }
145 if (y >= y_limit)
146 break;
147 /* Now look for line intersections before y1. */
148 covering_pixel_centers = COVERING_PIXEL_CENTERS(y, y1,
149 (!FILL_ADJUST ? 0 : fo.adjust_below),
150 (!FILL_ADJUST ? 0 : fo.adjust_above));
151 if (y != y1) {
152 intersect_al(ll, y, &y1, (covering_pixel_centers ? 1 : -1), all_bands); /* May change 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 }
157 /* Prepare dropout prevention. */
158 if (PSEUDO_RASTERIZATION) {
159 code = start_margin_set(fo.dev, ll, y1);
160 if (code < 0)
161 return code;
162 }
163 /* Fill a multi-trapezoid band for the active lines. */
164 if (covering_pixel_centers || all_bands) {
165 int inside = 0;
166 active_line *flp = NULL;
167
168 INCR(band);
169 /* Generate trapezoids */
170 for (alp = ll->x_list; alp != 0; alp = alp->next) {
171 int code;
172
173 print_al("step", alp);
174 INCR(band_step);
175 if (!INSIDE_PATH_P(inside, rule)) { /* i.e., outside */
176 inside += alp->direction;
177 if (INSIDE_PATH_P(inside, rule)) /* about to go in */
178 flp = alp;
179 continue;
180 }
181 /* We're inside a region being filled. */
182 inside += alp->direction;
183 if (INSIDE_PATH_P(inside, rule)) /* not about to go out */
184 continue;
185 /* We just went from inside to outside,
186 chech whether we'll immediately go inside. */
187 if (alp->next != NULL &&
188 alp->x_current == alp->next->x_current &&
189 alp->x_next == alp->next->x_next) {
190 /* If the next trapezoid contacts this one, unite them.
191 This simplifies data for the spot analyzer
192 and reduces the number of trapezoids in the rasterization.
193 Note that the topology possibly isn't exactly such
194 as we generate by this uniting :
195 Due to arithmetic errors in x_current, x_next
196 we can unite things, which really are not contacting.
197 But this level of the topology precision is enough for
198 the glyph grid fitting.
199 Also note that
200 while a rasterization with dropout prevention
201 it may cause a shift when choosing a pixel
202 to paint with a narrow trapezoid. */
203 alp = alp->next;
204 inside += alp->direction;
205 continue;
206 }
207 /* We just went from inside to outside, so fill the region. */
208 INCR(band_fill);
209 if (FILL_ADJUST && !(flp->end.x == flp->start.x && alp->end.x == alp->start.x) &&
210 (fo.adjust_below | fo.adjust_above) != 0) {
211 /* Assuming pseudo_rasterization = false. */
212 if (FILL_DIRECT)
213 code = slant_into_trapezoids__fd(ll, flp, alp, y, y1);
214 else
215 code = slant_into_trapezoids__nd(ll, flp, alp, y, y1);
216 } else {
217 fixed ybot = max(y, fo.pbox->p.y);
218 fixed ytop = min(y1, fo.pbox->q.y);
219
220 if (IS_SPOTAN) {
221 /* We can't pass data through the device interface because
222 we need to pass segment pointers. We're unhappy of that. */
223 code = gx_san_trap_store((gx_device_spot_analyzer *)fo.dev,
224 y, y1, flp->x_current, alp->x_current, flp->x_next, alp->x_next,
225 flp->pseg, alp->pseg, flp->direction, alp->direction);
226 } else {
227 if (flp->end.x == flp->start.x && alp->end.x == alp->start.x) {
228 if (FILL_ADJUST) {
229 ybot = max(y - fo.adjust_below, fo.pbox->p.y);
230 ytop = min(y1 + fo.adjust_above, fo.pbox->q.y);
231 }
232 if (ytop > ybot) {
233 int yi = fixed2int_pixround(ybot);
234 int hi = fixed2int_pixround(ytop) - yi;
235 int xli = fixed2int_var_pixround(flp->end.x - (!FILL_ADJUST ? 0 : fo.adjust_left));
236 int xi = fixed2int_var_pixround(alp->end.x + (!FILL_ADJUST ? 0 : fo.adjust_right));
237
238 if (PSEUDO_RASTERIZATION && xli == xi) {
239 /*
240 * The scan is empty but we should paint something
241 * against a dropout. Choose one of two pixels which
242 * is closer to the "axis".
243 */
244 fixed xx = int2fixed(xli);
245
246 if (xx - flp->end.x < alp->end.x - xx)
247 ++xi;
248 else
249 --xli;
250 }
251 vd_rect(flp->end.x, y, alp->end.x, y1, 1, VD_TRAP_COLOR);
252 code = LOOP_FILL_RECTANGLE_DIRECT(&fo, xli, yi, xi - xli, hi);
253 } else
254 code = 0;
255 } else if (ybot < ytop) {
256 gs_fixed_edge le, re;
257
258 le.start = flp->start;
259 le.end = flp->end;
260 re.start = alp->start;
261 re.end = alp->end;
262 vd_quad(flp->x_current, ybot, alp->x_current, ybot, alp->x_next, ytop, flp->x_next, ytop, 1, VD_TRAP_COLOR);
263 if (PSEUDO_RASTERIZATION) {
264 int flags = ftf_pseudo_rasterization;
265
266 if (flp->start.x == alp->start.x && flp->start.y == y && alp->start.y == y)
267 flags |= ftf_peak0;
268 if (flp->end.x == alp->end.x && flp->end.y == y1 && alp->end.y == y1)
269 flags |= ftf_peak0;
270 if (FILL_DIRECT)
271 code = gx_fill_trapezoid_cf_fd(fo.dev, &le, &re, ybot, ytop, flags, fo.pdevc, fo.lop);
272 else
273 code = gx_fill_trapezoid_cf_nd(fo.dev, &le, &re, ybot, ytop, flags, fo.pdevc, fo.lop);
274 } else
275 code = fo.fill_trap(fo.dev,
276 &le, &re, ybot, ytop, false, fo.pdevc, fo.lop);
277 } else
278 code = 0;
279 }
280 if (PSEUDO_RASTERIZATION) {
281 if (code < 0)
282 return code;
283 code = complete_margin(ll, flp, alp, y, y1);
284 if (code < 0)
285 return code;
286 code = margin_interior(ll, flp, alp, y, y1);
287 if (code < 0)
288 return code;
289 code = add_margin(ll, flp, alp, y, y1);
290 if (code < 0)
291 return code;
292 code = process_h_lists(ll, plp, flp, alp, y, y1);
293 plp = alp;
294 }
295 }
296 if (code < 0)
297 return code;
298 }
299 } else {
300 /* No trapezoids generation needed. */
301 if (PSEUDO_RASTERIZATION) {
302 /* Process dropouts near trapezoids. */
303 active_line *flp = NULL;
304 int inside = 0;
305
306 for (alp = ll->x_list; alp != 0; alp = alp->next) {
307 if (!INSIDE_PATH_P(inside, rule)) { /* i.e., outside */
308 inside += alp->direction;
309 if (INSIDE_PATH_P(inside, rule)) /* about to go in */
310 flp = alp;
311 continue;
312 }
313 /* We're inside a region being filled. */
314 inside += alp->direction;
315 if (INSIDE_PATH_P(inside, rule)) /* not about to go out */
316 continue;
317 code = continue_margin(ll, flp, alp, y, y1);
318 if (code < 0)
319 return code;
320 code = process_h_lists(ll, plp, flp, alp, y, y1);
321 plp = alp;
322 if (code < 0)
323 return code;
324 }
325 }
326 }
327 if (PSEUDO_RASTERIZATION && plp != 0) {
328 code = process_h_lists(ll, plp, 0, 0, y, y1);
329 if (code < 0)
330 return code;
331 }
332 move_al_by_y(ll, y1);
333 ll->h_list1 = ll->h_list0;
334 ll->h_list0 = 0;
335 y = y1;
336 }
337 if (PSEUDO_RASTERIZATION) {
338 code = process_h_lists(ll, 0, 0, 0, y, y + 1 /*stub*/);
339 if (code < 0)
340 return code;
341 code = close_margins(fo.dev, ll, &ll->margin_set1);
342 if (code < 0)
343 return code;
344 return close_margins(fo.dev, ll, &ll->margin_set0);
345 }
346 return 0;
347 }
348
349