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.c 9934 2009-08-05 22:12:58Z marcos $ */
15 /* A topological spot decomposition algorithm with dropout prevention. */
16 /*
17 This is a dramaticly reorganized and improved revision of the
18 filling algorithm, iwhich was nitially coded by Henry Stiles.
19 The main improvements are:
20 1. A dropout prevention for character fill.
21 2. The spot topology analysys support
22 for True Type grid fitting.
23 3. Fixed the contiguty of a spot covering
24 for shading fills with no dropouts.
25 */
26 /* See PSEUDO_RASTERISATION and "pseudo_rasterization".
27 about the dropout previntion logics. */
28 /* See is_spotan about the spot topology analyzis support. */
29 /* Also defining lower-level path filling procedures */
30
31 #include "gx.h"
32 #include "gserrors.h"
33 #include "gsstruct.h"
34 #include "gxfixed.h"
35 #include "gxdevice.h"
36 #include "gzpath.h"
37 #include "gzcpath.h"
38 #include "gxdcolor.h"
39 #include "gxhttile.h"
40 #include "gxistate.h"
41 #include "gxpaint.h" /* for prototypes */
42 #include "gxfdrop.h"
43 #include "gxfill.h"
44 #include "gxpath.h"
45 #include "gsptype1.h"
46 #include "gsptype2.h"
47 #include "gxpcolor.h"
48 #include "gdevddrw.h"
49 #include "gzspotan.h" /* Only for gx_san_trap_store. */
50 #include "memory_.h"
51 #include "stdint_.h"
52 #include "vdtrace.h"
53 /*
54 #include "gxfilltr.h" - Do not remove this comment. "gxfilltr.h" is included below.
55 #include "gxfillsl.h" - Do not remove this comment. "gxfillsl.h" is included below.
56 #include "gxfillts.h" - Do not remove this comment. "gxfillts.h" is included below.
57 */
58
59 #ifdef DEBUG
60 /* Define the statistics structure instance. */
61 stats_fill_t stats_fill;
62 #endif
63
64 /* A predicate for spot insideness. */
65 /* rule = -1 for winding number rule, i.e. */
66 /* we are inside if the winding number is non-zero; */
67 /* rule = 1 for even-odd rule, i.e. */
68 /* we are inside if the winding number is odd. */
69 #define INSIDE_PATH_P(inside, rule) ((inside & rule) != 0)
70
71
72 /* ---------------- Active line management ---------------- */
73
74
75 /*
76 * Define the ordering criterion for active lines that overlap in Y.
77 * Return -1, 0, or 1 if lp1 precedes, coincides with, or follows lp2.
78 *
79 * The lines' x_current values are correct for some Y value that crosses
80 * both of them and that is not both the start of one and the end of the
81 * other. (Neither line is horizontal.) We want the ordering at this
82 * Y value, or, of the x_current values are equal, greater Y values
83 * (if any: this Y value might be the end of both lines).
84 */
85 static int
x_order(const active_line * lp1,const active_line * lp2)86 x_order(const active_line *lp1, const active_line *lp2)
87 {
88 bool s1;
89
90 INCR(order);
91 if (lp1->x_current < lp2->x_current)
92 return -1;
93 else if (lp1->x_current > lp2->x_current)
94 return 1;
95 /*
96 * We need to compare the slopes of the lines. Start by
97 * checking one fast case, where the slopes have opposite signs.
98 */
99 if ((s1 = lp1->start.x < lp1->end.x) != (lp2->start.x < lp2->end.x))
100 return (s1 ? 1 : -1);
101 /*
102 * We really do have to compare the slopes. Fortunately, this isn't
103 * needed very often. We want the sign of the comparison
104 * dx1/dy1 - dx2/dy2, or (since we know dy1 and dy2 are positive)
105 * dx1 * dy2 - dx2 * dy1. In principle, we can't simply do this using
106 * doubles, since we need complete accuracy and doubles don't have
107 * enough fraction bits. However, with the usual 20+12-bit fixeds and
108 * 64-bit doubles, both of the factors would have to exceed 2^15
109 * device space pixels for the result to be inaccurate, so we
110 * simply disregard this possibility. ****** FIX SOMEDAY ******
111 */
112 INCR(slow_order);
113 {
114 fixed dx1 = lp1->end.x - lp1->start.x,
115 dy1 = lp1->end.y - lp1->start.y;
116 fixed dx2 = lp2->end.x - lp2->start.x,
117 dy2 = lp2->end.y - lp2->start.y;
118 double diff = (double)dx1 * dy2 - (double)dx2 * dy1;
119
120 return (diff < 0 ? -1 : diff > 0 ? 1 : 0);
121 }
122 }
123
124 /*
125 * The active_line structure isn't really simple, but since its instances
126 * only exist temporarily during a fill operation, we don't have to
127 * worry about a garbage collection occurring.
128 */
129 gs_private_st_simple(st_active_line, active_line, "active_line");
130
131 #ifdef DEBUG
132 /* Internal procedures for printing and checking active lines. */
133 static void
print_active_line(const char * label,const active_line * alp)134 print_active_line(const char *label, const active_line * alp)
135 {
136 dlprintf5("[f]%s 0x%lx(%d): x_current=%f x_next=%f\n",
137 label, (ulong) alp, alp->direction,
138 fixed2float(alp->x_current), fixed2float(alp->x_next));
139 dlprintf5(" start=(%f,%f) pt_end=0x%lx(%f,%f)\n",
140 fixed2float(alp->start.x), fixed2float(alp->start.y),
141 (ulong) alp->pseg,
142 fixed2float(alp->end.x), fixed2float(alp->end.y));
143 dlprintf2(" prev=0x%lx next=0x%lx\n",
144 (ulong) alp->prev, (ulong) alp->next);
145 }
146 static void
print_line_list(const active_line * flp)147 print_line_list(const active_line * flp)
148 {
149 const active_line *lp;
150
151 for (lp = flp; lp != 0; lp = lp->next) {
152 fixed xc = lp->x_current, xn = lp->x_next;
153
154 dlprintf3("[f]0x%lx(%d): x_current/next=%g",
155 (ulong) lp, lp->direction,
156 fixed2float(xc));
157 if (xn != xc)
158 dprintf1("/%g", fixed2float(xn));
159 dputc('\n');
160 }
161 }
162 static inline void
print_al(const char * label,const active_line * alp)163 print_al(const char *label, const active_line * alp)
164 {
165 if (gs_debug_c('F'))
166 print_active_line(label, alp);
167 }
168 #else
169 #define print_al(label,alp) DO_NOTHING
170 #endif
171
172 static inline bool
is_spotan_device(gx_device * dev)173 is_spotan_device(gx_device * dev)
174 {
175 /* Use open_device procedure to identify the type of the device
176 * instead of the standard gs_object_type() because gs_cpath_accum_device
177 * is allocaded on the stack i.e. has no block header with a descriptor
178 * but has dev->memory set like a heap-allocated device.
179 */
180 return dev->procs.open_device == san_open;
181 }
182
183 /* Forward declarations */
184 static void free_line_list(line_list *);
185 static int add_y_list(gx_path *, line_list *);
186 static int add_y_line_aux(const segment * prev_lp, const segment * lp,
187 const gs_fixed_point *curr, const gs_fixed_point *prev, int dir, line_list *ll);
188 static void insert_x_new(active_line *, line_list *);
189 static int end_x_line(active_line *, const line_list *, bool);
190 static int step_al(active_line *alp, bool move_iterator);
191
192
193 #define FILL_LOOP_PROC(proc) int proc(line_list *, fixed band_mask)
194 static FILL_LOOP_PROC(spot_into_scan_lines);
195 static FILL_LOOP_PROC(spot_into_trapezoids);
196
197 /*
198 * This is the general path filling algorithm.
199 * It uses the center-of-pixel rule for filling
200 * (except for pseudo_rasterization - see below).
201 * We can implement Microsoft's upper-left-corner-of-pixel rule
202 * by subtracting (0.5, 0.5) from all the coordinates in the path.
203 *
204 * The adjust parameters are a hack for keeping regions
205 * from coming out too faint: they specify an amount by which to expand
206 * the sides of every filled region.
207 * Setting adjust = fixed_half is supposed to produce the effect of Adobe's
208 * any-part-of-pixel rule, but it doesn't quite, because of the
209 * closed/open interval rule for regions. We detect this as a special case
210 * and do the slightly ugly things necessary to make it work.
211 */
212
213 /* Initialize the line list for a path. */
214 static inline void
init_line_list(line_list * ll,gs_memory_t * mem)215 init_line_list(line_list *ll, gs_memory_t * mem)
216 {
217 ll->memory = mem;
218 ll->active_area = 0;
219 ll->next_active = ll->local_active;
220 ll->limit = ll->next_active + MAX_LOCAL_ACTIVE;
221 ll->close_count = 0;
222 ll->y_list = 0;
223 ll->y_line = 0;
224 ll->h_list0 = ll->h_list1 = 0;
225 ll->margin_set0.margin_list = ll->margin_set1.margin_list = 0;
226 ll->margin_set0.margin_touched = ll->margin_set1.margin_touched = 0;
227 ll->margin_set0.y = ll->margin_set1.y = 0; /* A stub against indeterminism. Don't use it. */
228 ll->free_margin_list = 0;
229 ll->local_margin_alloc_count = 0;
230 ll->margin_set0.sect = ll->local_section0;
231 ll->margin_set1.sect = ll->local_section1;
232 /* Do not initialize ll->bbox_left, ll->bbox_width - they were set in advance. */
233 INCR(fill);
234 }
235
236
237 /* Unlink any line_close segments added temporarily. */
238 static inline void
unclose_path(gx_path * ppath,int count)239 unclose_path(gx_path * ppath, int count)
240 {
241 subpath *psub;
242
243 for (psub = ppath->first_subpath; count != 0;
244 psub = (subpath *) psub->last->next
245 )
246 if (psub->last == (segment *) & psub->closer) {
247 segment *prev = psub->closer.prev, *next = psub->closer.next;
248
249 prev->next = next;
250 if (next)
251 next->prev = prev;
252 psub->last = prev;
253 count--;
254 }
255 }
256
257 /*
258 * The general fill path algorithm.
259 */
260 static int
gx_general_fill_path(gx_device * pdev,const gs_imager_state * pis,gx_path * ppath,const gx_fill_params * params,const gx_device_color * pdevc,const gx_clip_path * pcpath)261 gx_general_fill_path(gx_device * pdev, const gs_imager_state * pis,
262 gx_path * ppath, const gx_fill_params * params,
263 const gx_device_color * pdevc, const gx_clip_path * pcpath)
264 {
265 gs_fixed_point adjust;
266 gs_logical_operation_t lop = pis->log_op;
267 gs_fixed_rect ibox, bbox, sbox;
268 gx_device_clip cdev;
269 gx_device *dev = pdev;
270 gx_device *save_dev = dev;
271 gx_path ffpath;
272 gx_path *pfpath;
273 int code;
274 int max_fill_band = dev->max_fill_band;
275 #define NO_BAND_MASK ((fixed)(-1) << (sizeof(fixed) * 8 - 1))
276 const bool is_character = params->adjust.x == -1; /* See gxistate.h */
277 bool fill_by_trapezoids;
278 bool pseudo_rasterization;
279 bool big_path = ppath->subpath_count > 50;
280 fill_options fo;
281 line_list lst;
282 extern bool CPSI_mode;
283
284 *(const fill_options **)&lst.fo = &fo; /* break 'const'. */
285 /*
286 * Compute the bounding box before we flatten the path.
287 * This can save a lot of time if the path has curves.
288 * If the path is neither fully within nor fully outside
289 * the quick-check boxes, we could recompute the bounding box
290 * and make the checks again after flattening the path,
291 * but right now we don't bother.
292 */
293 gx_path_bbox(ppath, &ibox);
294 # define SMALL_CHARACTER 500
295 pseudo_rasterization = (is_character &&
296 !is_spotan_device(dev) &&
297 ibox.q.y - ibox.p.y < SMALL_CHARACTER * fixed_scale &&
298 ibox.q.x - ibox.p.x < SMALL_CHARACTER * fixed_scale);
299 if (is_character)
300 adjust.x = adjust.y = 0;
301 else
302 adjust = params->adjust;
303 lst.contour_count = 0;
304 lst.windings = NULL;
305 lst.bbox_left = fixed2int(ibox.p.x - adjust.x - fixed_epsilon);
306 lst.bbox_width = fixed2int(fixed_ceiling(ibox.q.x + adjust.x)) - lst.bbox_left;
307 if (vd_enabled) {
308 fixed x0 = int2fixed(fixed2int(ibox.p.x - adjust.x - fixed_epsilon));
309 fixed x1 = int2fixed(fixed2int(ibox.q.x + adjust.x + fixed_scale - fixed_epsilon));
310 fixed y0 = int2fixed(fixed2int(ibox.p.y - adjust.y - fixed_epsilon));
311 fixed y1 = int2fixed(fixed2int(ibox.q.y + adjust.y + fixed_scale - fixed_epsilon)), k;
312
313 for (k = x0; k <= x1; k += fixed_scale)
314 vd_bar(k, y0, k, y1, 1, RGB(128, 128, 128));
315 for (k = y0; k <= y1; k += fixed_scale)
316 vd_bar(x0, k, x1, k, 1, RGB(128, 128, 128));
317 }
318 /* Check the bounding boxes. */
319 if_debug6('f', "[f]adjust=%g,%g bbox=(%g,%g),(%g,%g)\n",
320 fixed2float(adjust.x), fixed2float(adjust.y),
321 fixed2float(ibox.p.x), fixed2float(ibox.p.y),
322 fixed2float(ibox.q.x), fixed2float(ibox.q.y));
323 if (pcpath)
324 gx_cpath_inner_box(pcpath, &bbox);
325 else
326 (*dev_proc(dev, get_clipping_box)) (dev, &bbox);
327 if (!rect_within(ibox, bbox)) {
328 /*
329 * Intersect the path box and the clip bounding box.
330 * If the intersection is empty, this fill is a no-op.
331 */
332 if (pcpath)
333 gx_cpath_outer_box(pcpath, &bbox);
334 if_debug4('f', " outer_box=(%g,%g),(%g,%g)\n",
335 fixed2float(bbox.p.x), fixed2float(bbox.p.y),
336 fixed2float(bbox.q.x), fixed2float(bbox.q.y));
337 rect_intersect(ibox, bbox);
338 if (ibox.p.x - adjust.x >= ibox.q.x + adjust.x ||
339 ibox.p.y - adjust.y >= ibox.q.y + adjust.y
340 ) { /* Intersection of boxes is empty! */
341 return 0;
342 }
343 /*
344 * The path is neither entirely inside the inner clip box
345 * nor entirely outside the outer clip box.
346 * If we had to flatten the path, this is where we would
347 * recompute its bbox and make the tests again,
348 * but we don't bother right now.
349 *
350 * If there is a clipping path, set up a clipping device.
351 */
352 if (pcpath) {
353 dev = (gx_device *) & cdev;
354 gx_make_clip_device_on_stack(&cdev, pcpath, save_dev);
355 cdev.max_fill_band = save_dev->max_fill_band;
356 }
357 }
358 /*
359 * Compute the proper adjustment values.
360 * To get the effect of the any-part-of-pixel rule,
361 * we may have to tweak them slightly.
362 * NOTE: We changed the adjust_right/above value from 0.5+epsilon
363 * to 0.5 in release 5.01; even though this does the right thing
364 * in every case we could imagine, we aren't confident that it's
365 * correct. (The old values were definitely incorrect, since they
366 * caused 1-pixel-wide/high objects to color 2 pixels even if
367 * they fell exactly on pixel boundaries.)
368 */
369 if (adjust.x == fixed_half)
370 fo.adjust_left = fixed_half - fixed_epsilon,
371 fo.adjust_right = fixed_half /* + fixed_epsilon */ ; /* see above */
372 else
373 fo.adjust_left = fo.adjust_right = adjust.x;
374 if (adjust.y == fixed_half)
375 fo.adjust_below = fixed_half - fixed_epsilon,
376 fo.adjust_above = fixed_half /* + fixed_epsilon */ ; /* see above */
377 else
378 fo.adjust_below = fo.adjust_above = adjust.y;
379 /* Initialize the active line list. */
380 init_line_list(&lst, ppath->memory);
381 sbox.p.x = ibox.p.x - adjust.x;
382 sbox.p.y = ibox.p.y - adjust.y;
383 sbox.q.x = ibox.q.x + adjust.x;
384 sbox.q.y = ibox.q.y + adjust.y;
385 fo.pseudo_rasterization = pseudo_rasterization;
386 fo.pdevc = pdevc;
387 fo.lop = lop;
388 fo.fixed_flat = float2fixed(params->flatness);
389 fo.ymin = ibox.p.y;
390 fo.ymax = ibox.q.y;
391 fo.dev = dev;
392 fo.pbox = &sbox;
393 fo.rule = params->rule;
394 fo.is_spotan = is_spotan_device(dev);
395 fo.fill_direct = color_writes_pure(pdevc, lop);
396 fo.fill_rect = (fo.fill_direct ? dev_proc(dev, fill_rectangle) : NULL);
397 fo.fill_trap = dev_proc(dev, fill_trapezoid);
398
399 /*
400 * We have a choice of two different filling algorithms:
401 * scan-line-based and trapezoid-based. They compare as follows:
402 *
403 * Scan Trap
404 * ---- ----
405 * skip +draw 0-height horizontal lines
406 * slow +fast rectangles
407 * +fast slow curves
408 * +yes no write pixels at most once when adjust != 0
409 *
410 * Normally we use the scan line algorithm for characters, where curve
411 * speed is important, and for non-idempotent RasterOps, where double
412 * pixel writing must be avoided, and the trapezoid algorithm otherwise.
413 * However, we always use the trapezoid algorithm for rectangles.
414 */
415 fill_by_trapezoids =
416 (pseudo_rasterization || !gx_path_has_curves(ppath) ||
417 params->flatness >= 1.0 || fo.is_spotan);
418 if (fill_by_trapezoids && !fo.is_spotan && !lop_is_idempotent(lop)) {
419 gs_fixed_rect rbox;
420
421 if (gx_path_is_rectangular(ppath, &rbox)) {
422 int x0 = fixed2int_pixround(rbox.p.x - fo.adjust_left);
423 int y0 = fixed2int_pixround(rbox.p.y - fo.adjust_below);
424 int x1 = fixed2int_pixround(rbox.q.x + fo.adjust_right);
425 int y1 = fixed2int_pixround(rbox.q.y + fo.adjust_above);
426
427 return gx_fill_rectangle_device_rop(x0, y0, x1 - x0, y1 - y0,
428 pdevc, dev, lop);
429 }
430 if (fo.adjust_left | fo.adjust_right | fo.adjust_below | fo.adjust_above)
431 fill_by_trapezoids = false; /* avoid double writing pixels */
432 }
433 gx_path_init_local(&ffpath, ppath->memory);
434 if (!big_path && !gx_path_has_curves(ppath)) /* don't need to flatten */
435 pfpath = ppath;
436 else if (is_spotan_device(dev))
437 pfpath = ppath;
438 else if (!big_path && gx_path__check_curves(ppath, pco_small_curves, fo.fixed_flat))
439 pfpath = ppath;
440 else {
441 code = gx_path_copy_reducing(ppath, &ffpath, fo.fixed_flat, NULL,
442 pco_small_curves);
443 if (code < 0)
444 return code;
445 pfpath = &ffpath;
446 if (big_path) {
447 code = gx_path_merge_contacting_contours(pfpath);
448 if (code < 0)
449 return code;
450 }
451 }
452 fo.fill_by_trapezoids = fill_by_trapezoids;
453 if ((code = add_y_list(pfpath, &lst)) < 0)
454 goto nope;
455 {
456 FILL_LOOP_PROC((*fill_loop));
457
458 /* Some short-sighted compilers won't allow a conditional here.... */
459 if (fill_by_trapezoids)
460 fill_loop = spot_into_trapezoids;
461 else
462 fill_loop = spot_into_scan_lines;
463 if (lst.bbox_width > MAX_LOCAL_SECTION && fo.pseudo_rasterization) {
464 /*
465 * Note that execution pass here only for character size
466 * grater that MAX_LOCAL_SECTION and lesser than
467 * SMALL_CHARACTER. Therefore with !arch_small_memory
468 * the dynamic allocation only happens for characters
469 * wider than 100 pixels.
470 */
471 lst.margin_set0.sect = (section *)gs_alloc_struct_array(pdev->memory, lst.bbox_width * 2,
472 section, &st_section, "gx_general_fill_path");
473 if (lst.margin_set0.sect == 0)
474 return_error(gs_error_VMerror);
475 lst.margin_set1.sect = lst.margin_set0.sect + lst.bbox_width;
476 }
477 if (fo.pseudo_rasterization) {
478 init_section(lst.margin_set0.sect, 0, lst.bbox_width);
479 init_section(lst.margin_set1.sect, 0, lst.bbox_width);
480 }
481 if (CPSI_mode && is_character) {
482 if (lst.contour_count > countof(lst.local_windings)) {
483 lst.windings = (int *)gs_alloc_byte_array(pdev->memory, lst.contour_count,
484 sizeof(int), "gx_general_fill_path");
485 } else
486 lst.windings = lst.local_windings;
487 memset(lst.windings, 0, sizeof(lst.windings[0]) * lst.contour_count);
488 }
489 code = (*fill_loop)
490 (&lst, (max_fill_band == 0 ? NO_BAND_MASK : int2fixed(-max_fill_band)));
491 if (lst.margin_set0.sect != lst.local_section0 &&
492 lst.margin_set0.sect != lst.local_section1)
493 gs_free_object(pdev->memory, min(lst.margin_set0.sect, lst.margin_set1.sect), "gx_general_fill_path");
494 if (lst.windings != NULL && lst.windings != lst.local_windings)
495 gs_free_object(pdev->memory, lst.windings, "gx_general_fill_path");
496 }
497 nope:if (lst.close_count != 0)
498 unclose_path(pfpath, lst.close_count);
499 free_line_list(&lst);
500 if (pfpath != ppath) /* had to flatten */
501 gx_path_free(pfpath, "gx_general_fill_path");
502 #ifdef DEBUG
503 if (gs_debug_c('f')) {
504 dlputs("[f] # alloc up down horiz step slowx iter find band bstep bfill\n");
505 dlprintf5(" %5ld %5ld %5ld %5ld %5ld",
506 stats_fill.fill, stats_fill.fill_alloc,
507 stats_fill.y_up, stats_fill.y_down,
508 stats_fill.horiz);
509 dlprintf4(" %5ld %5ld %5ld %5ld",
510 stats_fill.x_step, stats_fill.slow_x,
511 stats_fill.iter, stats_fill.find_y);
512 dlprintf3(" %5ld %5ld %5ld\n",
513 stats_fill.band, stats_fill.band_step,
514 stats_fill.band_fill);
515 dlputs("[f] afill slant shall sfill mqcrs order slowo\n");
516 dlprintf7(" %5ld %5ld %5ld %5ld %5ld %5ld %5ld\n",
517 stats_fill.afill, stats_fill.slant,
518 stats_fill.slant_shallow, stats_fill.sfill,
519 stats_fill.mq_cross, stats_fill.order,
520 stats_fill.slow_order);
521 }
522 #endif
523 return code;
524 }
525
526 static int
pass_shading_area_through_clip_path_device(gx_device * pdev,const gs_imager_state * pis,gx_path * ppath,const gx_fill_params * params,const gx_device_color * pdevc,const gx_clip_path * pcpath)527 pass_shading_area_through_clip_path_device(gx_device * pdev, const gs_imager_state * pis,
528 gx_path * ppath, const gx_fill_params * params,
529 const gx_device_color * pdevc, const gx_clip_path * pcpath)
530 {
531 if (pdevc == NULL) {
532 gx_device_clip *cdev = (gx_device_clip *)pdev;
533
534 return dev_proc(cdev->target, fill_path)(cdev->target, pis, ppath, params, pdevc, pcpath);
535 }
536 /* We know that tha clip path device implements fill_path with default proc. */
537 return gx_default_fill_path(pdev, pis, ppath, params, pdevc, pcpath);
538 }
539
540 /*
541 * Fill a path. This is the default implementation of the driver
542 * fill_path procedure.
543 */
544 int
gx_default_fill_path(gx_device * pdev,const gs_imager_state * pis,gx_path * ppath,const gx_fill_params * params,const gx_device_color * pdevc,const gx_clip_path * pcpath)545 gx_default_fill_path(gx_device * pdev, const gs_imager_state * pis,
546 gx_path * ppath, const gx_fill_params * params,
547 const gx_device_color * pdevc, const gx_clip_path * pcpath)
548 {
549 int code = 0;
550
551 if (gx_dc_is_pattern2_color(pdevc)
552 || pdevc->type == &gx_dc_type_data_ht_colored
553 || (gx_dc_is_pattern1_color(pdevc) && gx_pattern_tile_is_clist(pdevc->colors.pattern.p_tile))
554 ) {
555 /* Optimization for shading and halftone fill :
556 The general filling algorithm subdivides the fill region into
557 trapezoid or rectangle subregions and then paints each subregion
558 with given color. If the color is complex, it also needs to be subdivided
559 into constant color rectangles. In the worst case it gives
560 a multiple of numbers of rectangles, which may be too slow.
561 A faster processing may be obtained with installing a clipper
562 device with the filling path, and then render the complex color
563 through it. The speeding up happens due to the clipper device
564 is optimised for fast scans through neighbour clipping rectangles.
565 */
566 /* We need a single clipping path here, because shadings and
567 halftones don't take 2 paths. Compute the clipping path intersection.
568 */
569 gx_clip_path cpath_intersection, cpath_with_shading_bbox;
570 const gx_clip_path *pcpath1, *pcpath2;
571 gs_imager_state *pis_noconst = (gs_imager_state *)pis; /* Break const. */
572
573 if (ppath != NULL) {
574 code = gx_cpath_init_local_shared(&cpath_intersection, pcpath, pdev->memory);
575 if (code < 0)
576 return code;
577 if (pcpath == NULL) {
578 gs_fixed_rect clip_box1;
579
580 (*dev_proc(pdev, get_clipping_box)) (pdev, &clip_box1);
581 code = gx_cpath_from_rectangle(&cpath_intersection, &clip_box1);
582 }
583 if (code >= 0)
584 code = gx_cpath_intersect_with_params(&cpath_intersection, ppath, params->rule,
585 pis_noconst, params);
586 pcpath1 = &cpath_intersection;
587 } else
588 pcpath1 = pcpath;
589 pcpath2 = pcpath1;
590 if (code >= 0)
591 code = gx_dc_pattern2_clip_with_bbox(pdevc, pdev, &cpath_with_shading_bbox, &pcpath1);
592 /* Do fill : */
593 if (code >= 0) {
594 gs_fixed_rect clip_box;
595 gs_int_rect cb;
596 const gx_rop_source_t *rs = NULL;
597 gx_device *dev;
598 gx_device_clip cdev;
599
600 gx_cpath_outer_box(pcpath1, &clip_box);
601 cb.p.x = fixed2int_pixround(clip_box.p.x);
602 cb.p.y = fixed2int_pixround(clip_box.p.y);
603 cb.q.x = fixed2int_pixround(clip_box.q.x);
604 cb.q.y = fixed2int_pixround(clip_box.q.y);
605 if (gx_dc_is_pattern2_color(pdevc) &&
606 (*dev_proc(pdev, pattern_manage))(pdev, gs_no_id, NULL, pattern_manage__handles_clip_path) > 0) {
607 /* A special interaction with clist writer device :
608 pass the intersected clipping path. It uses an unusual call to
609 fill_path with NULL device color. */
610 code = (*dev_proc(pdev, fill_path))(pdev, pis, ppath, params, NULL, pcpath1);
611 dev = pdev;
612 } else {
613 gx_make_clip_device_on_stack(&cdev, pcpath1, pdev);
614 dev = (gx_device *)&cdev;
615 if ((*dev_proc(pdev, pattern_manage))(pdev,
616 gs_no_id, NULL, pattern_manage__shading_area) > 0)
617 set_dev_proc(&cdev, fill_path, pass_shading_area_through_clip_path_device);
618 code = 0;
619 }
620 if (code >= 0)
621 code = pdevc->type->fill_rectangle(pdevc,
622 cb.p.x, cb.p.y, cb.q.x - cb.p.x, cb.q.y - cb.p.y,
623 dev, pis->log_op, rs);
624 }
625 if (ppath != NULL)
626 gx_cpath_free(&cpath_intersection, "shading_fill_cpath_intersection");
627 if (pcpath1 != pcpath2)
628 gx_cpath_free(&cpath_with_shading_bbox, "shading_fill_cpath_intersection");
629 } else {
630 bool got_dc = false;
631 vd_save;
632 if (vd_allowed('F') || vd_allowed('f')) {
633 if (!vd_enabled) {
634 vd_get_dc( (params->adjust.x > 0 || params->adjust.y > 0) ? 'F' : 'f');
635 got_dc = vd_enabled;
636 }
637 if (vd_enabled) {
638 vd_set_shift(0, 100);
639 vd_set_scale(VD_SCALE);
640 vd_set_origin(0, 0);
641 vd_erase(RGB(192, 192, 192));
642 }
643 } else
644 vd_disable;
645 code = gx_general_fill_path(pdev, pis, ppath, params, pdevc, pcpath);
646 if (got_dc)
647 vd_release_dc;
648 vd_restore;
649 }
650 return code;
651 }
652
653 /* Free the line list. */
654 static void
free_line_list(line_list * ll)655 free_line_list(line_list *ll)
656 {
657 /* Free any individually allocated active_lines. */
658 gs_memory_t *mem = ll->memory;
659 active_line *alp;
660
661 while ((alp = ll->active_area) != 0) {
662 active_line *next = alp->alloc_next;
663
664 gs_free_object(mem, alp, "active line");
665 ll->active_area = next;
666 }
667 free_all_margins(ll);
668 }
669
670 static inline active_line *
make_al(line_list * ll)671 make_al(line_list *ll)
672 {
673 active_line *alp = ll->next_active;
674
675 if (alp == ll->limit) { /* Allocate separately */
676 alp = gs_alloc_struct(ll->memory, active_line,
677 &st_active_line, "active line");
678 if (alp == 0)
679 return NULL;
680 alp->alloc_next = ll->active_area;
681 ll->active_area = alp;
682 INCR(fill_alloc);
683 } else
684 ll->next_active++;
685 alp->contour_count = ll->contour_count;
686 return alp;
687 }
688
689 /* Insert the new line in the Y ordering */
690 static void
insert_y_line(line_list * ll,active_line * alp)691 insert_y_line(line_list *ll, active_line *alp)
692 {
693 active_line *yp = ll->y_line;
694 active_line *nyp;
695 fixed y_start = alp->start.y;
696
697 vd_bar(alp->start.x, alp->start.y, alp->end.x, alp->end.y, 0, RGB(255, 0, 0));
698 if (yp == 0) {
699 alp->next = alp->prev = 0;
700 ll->y_list = alp;
701 } else if (y_start >= yp->start.y) { /* Insert the new line after y_line */
702 while (INCR_EXPR(y_up),
703 ((nyp = yp->next) != NULL &&
704 y_start > nyp->start.y)
705 )
706 yp = nyp;
707 alp->next = nyp;
708 alp->prev = yp;
709 yp->next = alp;
710 if (nyp)
711 nyp->prev = alp;
712 } else { /* Insert the new line before y_line */
713 while (INCR_EXPR(y_down),
714 ((nyp = yp->prev) != NULL &&
715 y_start < nyp->start.y)
716 )
717 yp = nyp;
718 alp->prev = nyp;
719 alp->next = yp;
720 yp->prev = alp;
721 if (nyp)
722 nyp->next = alp;
723 else
724 ll->y_list = alp;
725 }
726 ll->y_line = alp;
727 vd_bar(alp->start.x, alp->start.y, alp->end.x, alp->end.y, 1, RGB(0, 255, 0));
728 print_al("add ", alp);
729 }
730
731 typedef struct contour_cursor_s {
732 segment *prev, *pseg, *pfirst, *plast;
733 gx_flattened_iterator *fi;
734 bool more_flattened;
735 bool first_flattened;
736 int dir;
737 bool monotonic_y;
738 bool monotonic_x;
739 bool crossing;
740 } contour_cursor;
741
742 static inline int
compute_dir(const fill_options * fo,fixed y0,fixed y1)743 compute_dir(const fill_options *fo, fixed y0, fixed y1)
744 {
745 if (max(y0, y1) < fo->ymin)
746 return 2;
747 if (min(y0, y1) > fo->ymax)
748 return 2;
749 return (y0 < y1 ? DIR_UP :
750 y0 > y1 ? DIR_DOWN : DIR_HORIZONTAL);
751 }
752
753 static inline int
add_y_curve_part(line_list * ll,segment * s0,segment * s1,int dir,gx_flattened_iterator * fi,bool more1,bool step_back,bool monotonic_x)754 add_y_curve_part(line_list *ll, segment *s0, segment *s1, int dir,
755 gx_flattened_iterator *fi, bool more1, bool step_back, bool monotonic_x)
756 {
757 active_line *alp = make_al(ll);
758 int code;
759
760 if (alp == NULL)
761 return_error(gs_error_VMerror);
762 alp->pseg = (dir == DIR_UP ? s1 : s0);
763 alp->direction = dir;
764 alp->fi = *fi;
765 alp->more_flattened = more1;
766 if (dir != DIR_UP && more1)
767 gx_flattened_iterator__switch_to_backscan(&alp->fi, more1);
768 if (step_back) {
769 do {
770 code = gx_flattened_iterator__prev(&alp->fi);
771 if (code < 0)
772 return code;
773 alp->more_flattened = code;
774 if (compute_dir(ll->fo, alp->fi.ly0, alp->fi.ly1) != 2)
775 break;
776 } while (alp->more_flattened);
777 }
778 code = step_al(alp, false);
779 if (code < 0)
780 return code;
781 alp->monotonic_y = false;
782 alp->monotonic_x = monotonic_x;
783 insert_y_line(ll, alp);
784 return 0;
785 }
786
787 static inline int
add_y_line(const segment * prev_lp,const segment * lp,int dir,line_list * ll)788 add_y_line(const segment * prev_lp, const segment * lp, int dir, line_list *ll)
789 {
790 return add_y_line_aux(prev_lp, lp, &lp->pt, &prev_lp->pt, dir, ll);
791 }
792
793 static inline int
start_al_pair(line_list * ll,contour_cursor * q,contour_cursor * p)794 start_al_pair(line_list *ll, contour_cursor *q, contour_cursor *p)
795 {
796 int code;
797
798 if (q->monotonic_y)
799 code = add_y_line(q->prev, q->pseg, DIR_DOWN, ll);
800 else
801 code = add_y_curve_part(ll, q->prev, q->pseg, DIR_DOWN, q->fi,
802 !q->first_flattened, false, q->monotonic_x);
803 if (code < 0)
804 return code;
805 if (p->monotonic_y)
806 code = add_y_line(p->prev, p->pseg, DIR_UP, ll);
807 else
808 code = add_y_curve_part(ll, p->prev, p->pseg, DIR_UP, p->fi,
809 p->more_flattened, false, p->monotonic_x);
810 return code;
811 }
812
813 /* Start active lines from a minimum of a possibly non-monotonic curve. */
814 static int
start_al_pair_from_min(line_list * ll,contour_cursor * q)815 start_al_pair_from_min(line_list *ll, contour_cursor *q)
816 {
817 int dir, code;
818 const fill_options * const fo = ll->fo;
819
820 /* q stands at the first segment, which isn't last. */
821 do {
822 code = gx_flattened_iterator__next(q->fi);
823 if (code < 0)
824 return code;
825 q->more_flattened = code;
826 dir = compute_dir(fo, q->fi->ly0, q->fi->ly1);
827 if (q->fi->ly0 > fo->ymax && ll->y_break > q->fi->y0)
828 ll->y_break = q->fi->ly0;
829 if (q->fi->ly1 > fo->ymax && ll->y_break > q->fi->ly1)
830 ll->y_break = q->fi->ly1;
831 if (dir == DIR_UP && ll->main_dir == DIR_DOWN && q->fi->ly0 >= fo->ymin) {
832 code = add_y_curve_part(ll, q->prev, q->pseg, DIR_DOWN, q->fi,
833 true, true, q->monotonic_x);
834 if (code < 0)
835 return code;
836 code = add_y_curve_part(ll, q->prev, q->pseg, DIR_UP, q->fi,
837 q->more_flattened, false, q->monotonic_x);
838 if (code < 0)
839 return code;
840 } else if (q->fi->ly0 < fo->ymin && q->fi->ly1 >= fo->ymin) {
841 code = add_y_curve_part(ll, q->prev, q->pseg, DIR_UP, q->fi,
842 q->more_flattened, false, q->monotonic_x);
843 if (code < 0)
844 return code;
845 } else if (q->fi->ly0 >= fo->ymin && q->fi->ly1 < fo->ymin) {
846 code = add_y_curve_part(ll, q->prev, q->pseg, DIR_DOWN, q->fi,
847 true, false, q->monotonic_x);
848 if (code < 0)
849 return code;
850 }
851 q->first_flattened = false;
852 q->dir = dir;
853 ll->main_dir = (dir == DIR_DOWN ? DIR_DOWN :
854 dir == DIR_UP ? DIR_UP : ll->main_dir);
855 if (!q->more_flattened)
856 break;
857 } while(q->more_flattened);
858 /* q stands at the last segment. */
859 return 0;
860 /* note : it doesn't depend on the number of curve minimums,
861 which may vary due to arithmetic errors. */
862 }
863
864 static inline int
init_contour_cursor(line_list * ll,contour_cursor * q)865 init_contour_cursor(line_list *ll, contour_cursor *q)
866 {
867 const fill_options * const fo = ll->fo;
868
869 if (q->pseg->type == s_curve) {
870 curve_segment *s = (curve_segment *)q->pseg;
871 fixed ymin = min(min(q->prev->pt.y, s->p1.y), min(s->p2.y, s->pt.y));
872 fixed ymax = max(max(q->prev->pt.y, s->p1.y), max(s->p2.y, s->pt.y));
873 bool in_band = ymin <= fo->ymax && ymax >= fo->ymin;
874 q->crossing = ymin < fo->ymin && ymax >= fo->ymin;
875 q->monotonic_y = !in_band ||
876 (!q->crossing &&
877 ((q->prev->pt.y <= s->p1.y && s->p1.y <= s->p2.y && s->p2.y <= s->pt.y) ||
878 (q->prev->pt.y >= s->p1.y && s->p1.y >= s->p2.y && s->p2.y >= s->pt.y)));
879 q->monotonic_x =
880 ((q->prev->pt.x <= s->p1.x && s->p1.x <= s->p2.x && s->p2.x <= s->pt.x) ||
881 (q->prev->pt.x >= s->p1.x && s->p1.x >= s->p2.x && s->p2.x >= s->pt.x));
882 } else
883 q->monotonic_y = true;
884 if (!q->monotonic_y) {
885 curve_segment *s = (curve_segment *)q->pseg;
886 int k = gx_curve_log2_samples(q->prev->pt.x, q->prev->pt.y, s, fo->fixed_flat);
887
888 if (!gx_flattened_iterator__init(q->fi, q->prev->pt.x, q->prev->pt.y, s, k))
889 return_error(gs_error_rangecheck);
890 } else {
891 q->dir = compute_dir(fo, q->prev->pt.y, q->pseg->pt.y);
892 gx_flattened_iterator__init_line(q->fi,
893 q->prev->pt.x, q->prev->pt.y, q->pseg->pt.x, q->pseg->pt.y); /* fake for curves. */
894 vd_bar(q->prev->pt.x, q->prev->pt.y, q->pseg->pt.x, q->pseg->pt.y, 1, RGB(0, 0, 255));
895 }
896 q->first_flattened = true;
897 return 0;
898 }
899
900 static int
scan_contour(line_list * ll,contour_cursor * q)901 scan_contour(line_list *ll, contour_cursor *q)
902 {
903 contour_cursor p;
904 gx_flattened_iterator fi, save_fi;
905 segment *pseg;
906 int code;
907 bool only_horizontal = true, saved = false;
908 const fill_options * const fo = ll->fo;
909 contour_cursor save_q;
910
911 memset(&save_q, 0, sizeof(save_q)); /* Quiet gcc warning. */
912 p.monotonic_x = false; /* Quiet gcc warning. */
913 p.fi = &fi;
914 save_q.dir = 2;
915 ll->main_dir = DIR_HORIZONTAL;
916 for (; ; q->pseg = q->prev, q->prev = q->prev->prev) {
917 code = init_contour_cursor(ll, q);
918 if (code < 0)
919 return code;
920 for (;;) {
921 code = gx_flattened_iterator__next(q->fi);
922 if (code < 0)
923 return code;
924 if (!code)
925 break;
926 q->first_flattened = false;
927 q->dir = compute_dir(fo, q->fi->ly0, q->fi->ly1);
928 ll->main_dir = (q->dir == DIR_DOWN ? DIR_DOWN :
929 q->dir == DIR_UP ? DIR_UP : ll->main_dir);
930 }
931 q->dir = compute_dir(fo, q->fi->ly0, q->fi->ly1);
932 q->more_flattened = false;
933 ll->main_dir = (q->dir == DIR_DOWN ? DIR_DOWN :
934 q->dir == DIR_UP ? DIR_UP : ll->main_dir);
935 if (ll->main_dir != DIR_HORIZONTAL) {
936 only_horizontal = false;
937 break;
938 }
939 if (!saved && q->dir != 2) {
940 save_q = *q;
941 save_fi = *q->fi;
942 saved = true;
943 }
944 if (q->prev == q->pfirst)
945 break;
946 }
947 if (saved) {
948 *q = save_q;
949 *q->fi = save_fi;
950 }
951 for (pseg = q->pfirst; pseg != q->plast; pseg = pseg->next) {
952 p.prev = pseg;
953 p.pseg = pseg->next;
954 if (!fo->pseudo_rasterization || only_horizontal
955 || p.prev->pt.x != p.pseg->pt.x || p.prev->pt.y != p.pseg->pt.y
956 || p.pseg->type == s_curve) {
957 code = init_contour_cursor(ll, &p);
958 if (code < 0)
959 return code;
960 do {
961 code = gx_flattened_iterator__next(p.fi);
962 if (code < 0)
963 return code;
964 p.more_flattened = code;
965 p.dir = compute_dir(fo, p.fi->ly0, p.fi->ly1);
966 } while (p.more_flattened && p.dir == 2);
967 if (p.fi->ly0 > fo->ymax && ll->y_break > p.fi->ly0)
968 ll->y_break = p.fi->ly0;
969 if (p.fi->ly1 > fo->ymax && ll->y_break > p.fi->ly1)
970 ll->y_break = p.fi->ly1;
971 if (p.monotonic_y && p.dir == DIR_HORIZONTAL &&
972 !fo->pseudo_rasterization &&
973 #ifdef FILL_ZERO_WIDTH
974 (fo->adjust_below | fo->adjust_above) != 0) {
975 #else
976 fixed2int_pixround(p.pseg->pt.y - fo->adjust_below) <
977 fixed2int_pixround(p.pseg->pt.y + fo->adjust_above)) {
978 #endif
979 /* Add it here to avoid double processing in process_h_segments. */
980 code = add_y_line(p.prev, p.pseg, DIR_HORIZONTAL, ll);
981 if (code < 0)
982 return code;
983 }
984 if (p.monotonic_y && p.dir == DIR_HORIZONTAL &&
985 fo->pseudo_rasterization && only_horizontal) {
986 /* Add it here to avoid double processing in process_h_segments. */
987 code = add_y_line(p.prev, p.pseg, DIR_HORIZONTAL, ll);
988 if (code < 0)
989 return code;
990 }
991 if (p.fi->ly0 >= fo->ymin && p.dir == DIR_UP && ll->main_dir == DIR_DOWN) {
992 code = start_al_pair(ll, q, &p);
993 if (code < 0)
994 return code;
995 }
996 if (p.fi->ly0 < fo->ymin && p.fi->ly1 >= fo->ymin) {
997 if (p.monotonic_y)
998 code = add_y_line(p.prev, p.pseg, DIR_UP, ll);
999 else
1000 code = add_y_curve_part(ll, p.prev, p.pseg, DIR_UP, p.fi,
1001 p.more_flattened, false, p.monotonic_x);
1002 if (code < 0)
1003 return code;
1004 }
1005 if (p.fi->ly0 >= fo->ymin && p.fi->ly1 < fo->ymin) {
1006 if (p.monotonic_y)
1007 code = add_y_line(p.prev, p.pseg, DIR_DOWN, ll);
1008 else
1009 code = add_y_curve_part(ll, p.prev, p.pseg, DIR_DOWN, p.fi,
1010 !p.first_flattened, false, p.monotonic_x);
1011 if (code < 0)
1012 return code;
1013 }
1014 ll->main_dir = (p.dir == DIR_DOWN ? DIR_DOWN :
1015 p.dir == DIR_UP ? DIR_UP : ll->main_dir);
1016 if (!p.monotonic_y && p.more_flattened) {
1017 code = start_al_pair_from_min(ll, &p);
1018 if (code < 0)
1019 return code;
1020 }
1021 if (p.dir == DIR_DOWN || p.dir == DIR_HORIZONTAL) {
1022 gx_flattened_iterator *fi1 = q->fi;
1023 q->prev = p.prev;
1024 q->pseg = p.pseg;
1025 q->monotonic_y = p.monotonic_y;
1026 q->more_flattened = p.more_flattened;
1027 q->first_flattened = p.first_flattened;
1028 q->fi = p.fi;
1029 q->dir = p.dir;
1030 p.fi = fi1;
1031 }
1032 }
1033 }
1034 q->fi = NULL; /* safety. */
1035 return 0;
1036 }
1037
1038 /*
1039 * Construct a Y-sorted list of segments for rasterizing a path. We assume
1040 * the path is non-empty. Only include non-horizontal lines or (monotonic)
1041 * curve segments where one endpoint is locally Y-minimal, and horizontal
1042 * lines that might color some additional pixels.
1043 */
1044 static int
1045 add_y_list(gx_path * ppath, line_list *ll)
1046 {
1047 subpath *psub = ppath->first_subpath;
1048 int close_count = 0;
1049 int code;
1050 contour_cursor q;
1051 gx_flattened_iterator fi;
1052
1053 q.monotonic_x = false; /* Quiet gcc warning. */
1054 ll->y_break = max_fixed;
1055
1056 for (;psub; psub = (subpath *)psub->last->next) {
1057 /* We know that pseg points to a subpath head (s_start). */
1058 segment *pfirst = (segment *)psub;
1059 segment *plast = psub->last, *prev;
1060
1061 q.fi = &fi;
1062 if (plast->type != s_line_close) {
1063 /* Create a fake s_line_close */
1064 line_close_segment *lp = &psub->closer;
1065 segment *next = plast->next;
1066
1067 lp->next = next;
1068 lp->prev = plast;
1069 plast->next = (segment *) lp;
1070 if (next)
1071 next->prev = (segment *) lp;
1072 lp->type = s_line_close;
1073 lp->pt = psub->pt;
1074 lp->sub = psub;
1075 psub->last = plast = (segment *) lp;
1076 ll->close_count++;
1077 }
1078 prev = plast->prev;
1079 if (ll->fo->pseudo_rasterization && prev != pfirst &&
1080 prev->pt.x == plast->pt.x && prev->pt.y == plast->pt.y) {
1081 plast = prev;
1082 prev = prev->prev;
1083 }
1084 q.prev = prev;
1085 q.pseg = plast;
1086 q.pfirst = pfirst;
1087 q.plast = plast;
1088 code = scan_contour(ll, &q);
1089 if (code < 0)
1090 return code;
1091 ll->contour_count++;
1092 }
1093 return close_count;
1094 }
1095
1096
1097 static int
1098 step_al(active_line *alp, bool move_iterator)
1099 {
1100 bool forth = (alp->direction == DIR_UP || !alp->fi.curve);
1101
1102 if (move_iterator) {
1103 int code;
1104
1105 if (forth)
1106 code = gx_flattened_iterator__next(&alp->fi);
1107 else
1108 code = gx_flattened_iterator__prev(&alp->fi);
1109 if (code < 0)
1110 return code;
1111 alp->more_flattened = code;
1112 } else
1113 vd_bar(alp->fi.lx0, alp->fi.ly0, alp->fi.lx1, alp->fi.ly1, 1, RGB(0, 0, 255));
1114 /* Note that we can get alp->fi.ly0 == alp->fi.ly1
1115 if the curve tangent is horizontal. */
1116 alp->start.x = (forth ? alp->fi.lx0 : alp->fi.lx1);
1117 alp->start.y = (forth ? alp->fi.ly0 : alp->fi.ly1);
1118 alp->end.x = (forth ? alp->fi.lx1 : alp->fi.lx0);
1119 alp->end.y = (forth ? alp->fi.ly1 : alp->fi.ly0);
1120 alp->diff.x = alp->end.x - alp->start.x;
1121 alp->diff.y = alp->end.y - alp->start.y;
1122 SET_NUM_ADJUST(alp);
1123 (alp)->y_fast_max = MAX_MINUS_NUM_ADJUST(alp) /
1124 ((alp->diff.x >= 0 ? alp->diff.x : -alp->diff.x) | 1) + alp->start.y;
1125 return 0;
1126 }
1127
1128 static int
1129 init_al(active_line *alp, const segment *s0, const segment *s1, const line_list *ll)
1130 {
1131 const segment *ss = (alp->direction == DIR_UP ? s1 : s0);
1132 /* Warning : p0 may be equal to &alp->end. */
1133 bool curve = (ss != NULL && ss->type == s_curve);
1134 int code;
1135
1136 if (curve) {
1137 if (alp->direction == DIR_UP) {
1138 const curve_segment *cs = (const curve_segment *)s1;
1139 int k = gx_curve_log2_samples(s0->pt.x, s0->pt.y, cs, ll->fo->fixed_flat);
1140
1141 gx_flattened_iterator__init(&alp->fi,
1142 s0->pt.x, s0->pt.y, (const curve_segment *)s1, k);
1143 code = step_al(alp, true);
1144 if (code < 0)
1145 return code;
1146 if (!ll->fo->fill_by_trapezoids) {
1147 alp->monotonic_y = (s0->pt.y <= cs->p1.y && cs->p1.y <= cs->p2.y && cs->p2.y <= cs->pt.y);
1148 alp->monotonic_x = (s0->pt.x <= cs->p1.x && cs->p1.x <= cs->p2.x && cs->p2.x <= cs->pt.x) ||
1149 (s0->pt.x >= cs->p1.x && cs->p1.x >= cs->p2.x && cs->p2.x >= cs->pt.x);
1150 }
1151 } else {
1152 const curve_segment *cs = (const curve_segment *)s0;
1153 int k = gx_curve_log2_samples(s1->pt.x, s1->pt.y, cs, ll->fo->fixed_flat);
1154 bool more;
1155
1156 gx_flattened_iterator__init(&alp->fi,
1157 s1->pt.x, s1->pt.y, (const curve_segment *)s0, k);
1158 alp->more_flattened = false;
1159 do {
1160 code = gx_flattened_iterator__next(&alp->fi);
1161 if (code < 0)
1162 return code;
1163 more = code;
1164 alp->more_flattened |= more;
1165 } while(more);
1166 gx_flattened_iterator__switch_to_backscan(&alp->fi, alp->more_flattened);
1167 code = step_al(alp, false);
1168 if (code < 0)
1169 return code;
1170 if (!ll->fo->fill_by_trapezoids) {
1171 alp->monotonic_y = (s0->pt.y >= cs->p1.y && cs->p1.y >= cs->p2.y && cs->p2.y >= cs->pt.y);
1172 alp->monotonic_x = (s0->pt.x <= cs->p1.x && cs->p1.x <= cs->p2.x && cs->p2.x <= cs->pt.x) ||
1173 (s0->pt.x >= cs->p1.x && cs->p1.x >= cs->p2.x && cs->p2.x >= cs->pt.x);
1174 }
1175 }
1176 } else {
1177 gx_flattened_iterator__init_line(&alp->fi,
1178 s0->pt.x, s0->pt.y, s1->pt.x, s1->pt.y);
1179 code = step_al(alp, true);
1180 if (code < 0)
1181 return code;
1182 alp->monotonic_x = alp->monotonic_y = true;
1183 }
1184 alp->pseg = s1;
1185 return 0;
1186 }
1187 /*
1188 * Internal routine to test a segment and add it to the pending list if
1189 * appropriate.
1190 */
1191 static int
1192 add_y_line_aux(const segment * prev_lp, const segment * lp,
1193 const gs_fixed_point *curr, const gs_fixed_point *prev, int dir, line_list *ll)
1194 {
1195 int code;
1196
1197 active_line *alp = make_al(ll);
1198 if (alp == NULL)
1199 return_error(gs_error_VMerror);
1200 alp->more_flattened = false;
1201 switch ((alp->direction = dir)) {
1202 case DIR_UP:
1203 code = init_al(alp, prev_lp, lp, ll);
1204 if (code < 0)
1205 return code;
1206 break;
1207 case DIR_DOWN:
1208 code = init_al(alp, lp, prev_lp, ll);
1209 if (code < 0)
1210 return code;
1211 break;
1212 case DIR_HORIZONTAL:
1213 alp->start = *prev;
1214 alp->end = *curr;
1215 /* Don't need to set dx or y_fast_max */
1216 alp->pseg = prev_lp; /* may not need this either */
1217 break;
1218 default: /* can't happen */
1219 return_error(gs_error_unregistered);
1220 }
1221 insert_y_line(ll, alp);
1222 return 0;
1223 }
1224
1225
1226 /* ---------------- Filling loop utilities ---------------- */
1227
1228 /* Insert a newly active line in the X ordering. */
1229 static void
1230 insert_x_new(active_line * alp, line_list *ll)
1231 {
1232 active_line *next;
1233 active_line *prev = &ll->x_head;
1234
1235 vd_bar(alp->start.x, alp->start.y, alp->end.x, alp->end.y, 1, RGB(128, 128, 0));
1236 alp->x_current = alp->start.x;
1237 alp->x_next = alp->start.x; /* If the spot starts with a horizontal segment,
1238 we need resort_x_line to work properly
1239 in the very beginning. */
1240 while (INCR_EXPR(x_step),
1241 (next = prev->next) != 0 && x_order(next, alp) < 0
1242 )
1243 prev = next;
1244 alp->next = next;
1245 alp->prev = prev;
1246 if (next != 0)
1247 next->prev = alp;
1248 prev->next = alp;
1249 }
1250
1251 /* Insert a newly active line in the h list. */
1252 /* h list isn't ordered because x intervals may overlap. */
1253 /* todo : optimize with maintaining ordered interval list;
1254 Unite contacting inrevals, like we did in add_margin.
1255 */
1256 static inline void
1257 insert_h_new(active_line * alp, line_list *ll)
1258 {
1259 alp->next = ll->h_list0;
1260 alp->prev = 0;
1261 if (ll->h_list0 != 0)
1262 ll->h_list0->prev = alp;
1263 ll->h_list0 = alp;
1264 /*
1265 * h list keeps horizontal lines for a given y.
1266 * There are 2 lists, corresponding to upper and lower ends
1267 * of the Y-interval, which spot_into_trapezoids currently proceeds.
1268 * Parts of horizontal lines, which do not contact a filled trapezoid,
1269 * are parts of the spot bondairy. They to be marked in
1270 * the 'sect' array. - see process_h_lists.
1271 */
1272 }
1273
1274 static inline void
1275 remove_al(const line_list *ll, active_line *alp)
1276 {
1277 active_line *nlp = alp->next;
1278
1279 alp->prev->next = nlp;
1280 if (nlp)
1281 nlp->prev = alp->prev;
1282 if_debug1('F', "[F]drop 0x%lx\n", (ulong) alp);
1283 }
1284
1285 /*
1286 * Handle a line segment that just ended. Return true iff this was
1287 * the end of a line sequence.
1288 */
1289 static int
1290 end_x_line(active_line *alp, const line_list *ll, bool update)
1291 {
1292 const segment *pseg = alp->pseg;
1293 /*
1294 * The computation of next relies on the fact that
1295 * all subpaths have been closed. When we cycle
1296 * around to the other end of a subpath, we must be
1297 * sure not to process the start/end point twice.
1298 */
1299 const segment *next =
1300 (alp->direction == DIR_UP ?
1301 ( /* Upward line, go forward along path. */
1302 pseg->type == s_line_close ? /* end of subpath */
1303 ((const line_close_segment *)pseg)->sub->next :
1304 pseg->next) :
1305 ( /* Downward line, go backward along path. */
1306 pseg->type == s_start ? /* start of subpath */
1307 ((const subpath *)pseg)->last->prev :
1308 pseg->prev)
1309 );
1310 int code;
1311
1312 if (alp->end.y < alp->start.y) {
1313 /* fixme: The condition above causes a horizontal
1314 part of a curve near an Y maximum to process twice :
1315 once scanning the left spot boundary and once scanning the right one.
1316 In both cases it will go to the H list.
1317 However the dropout prevention logic isn't
1318 sensitive to that, and such segments does not affect
1319 trapezoids. Thus the resulting raster doesn't depend on that.
1320 However it would be nice to improve someday.
1321 */
1322 remove_al(ll, alp);
1323 return true;
1324 } else if (alp->more_flattened)
1325 return false;
1326 code = init_al(alp, pseg, next, ll);
1327 if (code < 0)
1328 return code;
1329 if (alp->start.y > alp->end.y) {
1330 /* See comment above. */
1331 remove_al(ll, alp);
1332 return true;
1333 }
1334 alp->x_current = alp->x_next = alp->start.x;
1335 vd_bar(alp->start.x, alp->start.y, alp->end.x, alp->end.y, 1, RGB(128, 0, 128));
1336 print_al("repl", alp);
1337 return false;
1338 }
1339
1340 static inline int
1341 add_margin(line_list * ll, active_line * flp, active_line * alp, fixed y0, fixed y1)
1342 { vd_bar(alp->start.x, alp->start.y, alp->end.x, alp->end.y, 1, RGB(255, 255, 255));
1343 vd_bar(flp->start.x, flp->start.y, flp->end.x, flp->end.y, 1, RGB(255, 255, 255));
1344 return continue_margin_common(ll, &ll->margin_set0, flp, alp, y0, y1);
1345 }
1346
1347 static inline int
1348 continue_margin(line_list * ll, active_line * flp, active_line * alp, fixed y0, fixed y1)
1349 {
1350 return continue_margin_common(ll, &ll->margin_set0, flp, alp, y0, y1);
1351 }
1352
1353 static inline int
1354 complete_margin(line_list * ll, active_line * flp, active_line * alp, fixed y0, fixed y1)
1355 {
1356 return continue_margin_common(ll, &ll->margin_set1, flp, alp, y0, y1);
1357 }
1358
1359 /*
1360 * Handle the case of a slanted trapezoid with adjustment.
1361 * To do this exactly right requires filling a central trapezoid
1362 * (or rectangle) plus two horizontal almost-rectangles.
1363 */
1364 static int
1365 fill_slant_adjust(const line_list *ll,
1366 const active_line *flp, const active_line *alp, fixed y, fixed y1)
1367 {
1368 const fill_options * const fo = ll->fo;
1369 const fixed Yb = y - fo->adjust_below;
1370 const fixed Ya = y + fo->adjust_above;
1371 const fixed Y1b = y1 - fo->adjust_below;
1372 const fixed Y1a = y1 + fo->adjust_above;
1373 const gs_fixed_edge *plbot, *prbot, *pltop, *prtop;
1374 gs_fixed_edge vert_left, slant_left, vert_right, slant_right;
1375 int code;
1376
1377 INCR(slant);
1378 vd_quad(flp->x_current, y, alp->x_current, y,
1379 alp->x_next, y1, flp->x_next, y1, 1, VD_TRAP_COLOR); /* fixme: Wrong X. */
1380
1381 /* Set up all the edges, even though we may not need them all. */
1382
1383 if (flp->start.x < flp->end.x) {
1384 vert_left.start.x = vert_left.end.x = flp->x_current - fo->adjust_left;
1385 vert_left.start.y = Yb, vert_left.end.y = Ya;
1386 vert_right.start.x = vert_right.end.x = alp->x_next + fo->adjust_right;
1387 vert_right.start.y = Y1b, vert_right.end.y = Y1a;
1388 slant_left.start.y = flp->start.y + fo->adjust_above;
1389 slant_left.end.y = flp->end.y + fo->adjust_above;
1390 slant_right.start.y = alp->start.y - fo->adjust_below;
1391 slant_right.end.y = alp->end.y - fo->adjust_below;
1392 plbot = &vert_left, prbot = &slant_right;
1393 pltop = &slant_left, prtop = &vert_right;
1394 } else {
1395 vert_left.start.x = vert_left.end.x = flp->x_next - fo->adjust_left;
1396 vert_left.start.y = Y1b, vert_left.end.y = Y1a;
1397 vert_right.start.x = vert_right.end.x = alp->x_current + fo->adjust_right;
1398 vert_right.start.y = Yb, vert_right.end.y = Ya;
1399 slant_left.start.y = flp->start.y - fo->adjust_below;
1400 slant_left.end.y = flp->end.y - fo->adjust_below;
1401 slant_right.start.y = alp->start.y + fo->adjust_above;
1402 slant_right.end.y = alp->end.y + fo->adjust_above;
1403 plbot = &slant_left, prbot = &vert_right;
1404 pltop = &vert_left, prtop = &slant_right;
1405 }
1406 slant_left.start.x = flp->start.x - fo->adjust_left;
1407 slant_left.end.x = flp->end.x - fo->adjust_left;
1408 slant_right.start.x = alp->start.x + fo->adjust_right;
1409 slant_right.end.x = alp->end.x + fo->adjust_right;
1410
1411 if (Ya >= Y1b) {
1412 /*
1413 * The upper and lower adjustment bands overlap.
1414 * Since the entire entity is less than 2 pixels high
1415 * in this case, we could handle it very efficiently
1416 * with no more than 2 rectangle fills, but for right now
1417 * we don't attempt to do this.
1418 */
1419 int iYb = fixed2int_var_pixround(Yb);
1420 int iYa = fixed2int_var_pixround(Ya);
1421 int iY1b = fixed2int_var_pixround(Y1b);
1422 int iY1a = fixed2int_var_pixround(Y1a);
1423
1424 INCR(slant_shallow);
1425 if (iY1b > iYb) {
1426 code = fo->fill_trap(fo->dev, plbot, prbot,
1427 Yb, Y1b, false, fo->pdevc, fo->lop);
1428 if (code < 0)
1429 return code;
1430 }
1431 if (iYa > iY1b) {
1432 int ix = fixed2int_var_pixround(vert_left.start.x);
1433 int iw = fixed2int_var_pixround(vert_right.start.x) - ix;
1434
1435 code = gx_fill_rectangle_device_rop(ix, iY1b, iw, iYa - iY1b,
1436 fo->pdevc, fo->dev, fo->lop);
1437 if (code < 0)
1438 return code;
1439 }
1440 if (iY1a > iYa)
1441 code = fo->fill_trap(fo->dev, pltop, prtop,
1442 Ya, Y1a, false, fo->pdevc, fo->lop);
1443 else
1444 code = 0;
1445 } else {
1446 /*
1447 * Clip the trapezoid if possible. This can save a lot
1448 * of work when filling paths that cross band boundaries.
1449 */
1450 fixed Yac;
1451
1452 if (fo->pbox->p.y < Ya) {
1453 code = fo->fill_trap(fo->dev, plbot, prbot,
1454 Yb, Ya, false, fo->pdevc, fo->lop);
1455 if (code < 0)
1456 return code;
1457 Yac = Ya;
1458 } else
1459 Yac = fo->pbox->p.y;
1460 if (fo->pbox->q.y > Y1b) {
1461 code = fo->fill_trap(fo->dev, &slant_left, &slant_right,
1462 Yac, Y1b, false, fo->pdevc, fo->lop);
1463 if (code < 0)
1464 return code;
1465 code = fo->fill_trap(fo->dev, pltop, prtop,
1466 Y1b, Y1a, false, fo->pdevc, fo->lop);
1467 } else
1468 code = fo->fill_trap(fo->dev, &slant_left, &slant_right,
1469 Yac, fo->pbox->q.y, false, fo->pdevc, fo->lop);
1470 }
1471 return code;
1472 }
1473
1474 /* Re-sort the x list by moving alp backward to its proper spot. */
1475 static inline void
1476 resort_x_line(active_line * alp)
1477 {
1478 active_line *prev = alp->prev;
1479 active_line *next = alp->next;
1480
1481 prev->next = next;
1482 if (next)
1483 next->prev = prev;
1484 while (x_order(prev, alp) > 0) {
1485 if_debug2('F', "[F]swap 0x%lx,0x%lx\n",
1486 (ulong) alp, (ulong) prev);
1487 next = prev, prev = prev->prev;
1488 }
1489 alp->next = next;
1490 alp->prev = prev;
1491 /* next might be null, if alp was in the correct spot already. */
1492 if (next)
1493 next->prev = alp;
1494 prev->next = alp;
1495 }
1496
1497 /* Move active lines by Y. */
1498 static inline int
1499 move_al_by_y(line_list *ll, fixed y1)
1500 {
1501 fixed x;
1502 active_line *alp, *nlp;
1503 int code;
1504
1505 for (x = min_fixed, alp = ll->x_list; alp != 0; alp = nlp) {
1506 bool notend = false;
1507 alp->x_current = alp->x_next;
1508
1509 nlp = alp->next;
1510 if (alp->end.y == y1 && alp->more_flattened) {
1511 code = step_al(alp, true);
1512 if (code < 0)
1513 return code;
1514 alp->x_current = alp->x_next = alp->start.x;
1515 notend = (alp->end.y >= alp->start.y);
1516 }
1517 if (alp->end.y > y1 || notend) {
1518 if (alp->x_next <= x)
1519 resort_x_line(alp);
1520 else
1521 x = alp->x_next;
1522 } else {
1523 code = end_x_line(alp, ll, true);
1524 if (code < 0)
1525 return code;
1526 if (!code) {
1527 if (alp->x_next <= x)
1528 resort_x_line(alp);
1529 else
1530 x = alp->x_next;
1531 }
1532 }
1533 }
1534 if (ll->x_list != 0 && ll->fo->pseudo_rasterization) {
1535 /* Ensure that contacting vertical stems are properly ordered.
1536 We don't want to unite contacting stems into
1537 a single margin, because it can cause a dropout :
1538 narrow stems are widened against a dropout, but
1539 an united wide one may be left unwidened.
1540 */
1541 for (alp = ll->x_list; alp->next != 0; ) {
1542 if (alp->start.x == alp->end.x &&
1543 alp->start.x == alp->next->start.x &&
1544 alp->next->start.x == alp->next->end.x &&
1545 alp->direction > alp->next->direction) {
1546 /* Exchange. */
1547 active_line *prev = alp->prev;
1548 active_line *next = alp->next;
1549 active_line *next2 = next->next;
1550 if (prev)
1551 prev->next = next;
1552 else
1553 ll->x_list = next;
1554 next->prev = prev;
1555 alp->prev = next;
1556 alp->next = next2;
1557 next->next = alp;
1558 if (next2)
1559 next2->prev = alp;
1560 } else
1561 alp = alp->next;
1562 }
1563 }
1564 return 0;
1565 }
1566
1567 /* Process horizontal segment of curves. */
1568 static inline int
1569 process_h_segments(line_list *ll, fixed y)
1570 {
1571 active_line *alp, *nlp;
1572 int code, inserted = 0;
1573
1574 for (alp = ll->x_list; alp != 0; alp = nlp) {
1575 nlp = alp->next;
1576 if (alp->start.y == y && alp->end.y == y) {
1577 if (ll->fo->pseudo_rasterization) {
1578 code = add_y_line_aux(NULL, NULL, &alp->start, &alp->end, DIR_HORIZONTAL, ll);
1579 if (code < 0)
1580 return code;
1581 }
1582 inserted = 1;
1583 }
1584 }
1585 return inserted;
1586 /* After this should call move_al_by_y and step to the next band. */
1587 }
1588
1589 static inline int
1590 loop_fill_trap_np(const line_list *ll, const gs_fixed_edge *le, const gs_fixed_edge *re, fixed y, fixed y1)
1591 {
1592 const fill_options * const fo = ll->fo;
1593 fixed ybot = max(y, fo->pbox->p.y);
1594 fixed ytop = min(y1, fo->pbox->q.y);
1595
1596 if (ybot >= ytop)
1597 return 0;
1598 vd_quad(le->start.x, ybot, re->start.x, ybot, re->end.x, ytop, le->end.x, ytop, 1, VD_TRAP_COLOR);
1599 return (*fo->fill_trap)
1600 (fo->dev, le, re, ybot, ytop, false, fo->pdevc, fo->lop);
1601 }
1602
1603 /* Define variants of the algorithm for filling a slanted trapezoid. */
1604 #define TEMPLATE_slant_into_trapezoids slant_into_trapezoids__fd
1605 #define FILL_DIRECT 1
1606 #include "gxfillts.h"
1607 #undef TEMPLATE_slant_into_trapezoids
1608 #undef FILL_DIRECT
1609
1610 #define TEMPLATE_slant_into_trapezoids slant_into_trapezoids__nd
1611 #define FILL_DIRECT 0
1612 #include "gxfillts.h"
1613 #undef TEMPLATE_slant_into_trapezoids
1614 #undef FILL_DIRECT
1615
1616
1617 #define COVERING_PIXEL_CENTERS(y, y1, adjust_below, adjust_above)\
1618 (fixed_pixround(y - adjust_below) < fixed_pixround(y1 + adjust_above))
1619
1620 /* Find an intersection within y, y1. */
1621 /* lp->x_current, lp->x_next must be set for y, y1. */
1622 static bool
1623 intersect(active_line *endp, active_line *alp, fixed y, fixed y1, fixed *p_y_new)
1624 {
1625 fixed y_new, dy;
1626 fixed dx_old = alp->x_current - endp->x_current;
1627 fixed dx_den = dx_old + endp->x_next - alp->x_next;
1628
1629 if (dx_den <= dx_old)
1630 return false; /* Intersection isn't possible. */
1631 dy = y1 - y;
1632 if_debug3('F', "[F]cross: dy=%g, dx_old=%g, dx_new=%g\n",
1633 fixed2float(dy), fixed2float(dx_old),
1634 fixed2float(dx_den - dx_old));
1635 /* Do the computation in single precision */
1636 /* if the values are small enough. */
1637 y_new =
1638 ((dy | dx_old) < 1L << (size_of(fixed) * 4 - 1) ?
1639 dy * dx_old / dx_den :
1640 (INCR_EXPR(mq_cross), fixed_mult_quo(dy, dx_old, dx_den)))
1641 + y;
1642 /* The crossing value doesn't have to be */
1643 /* very accurate, but it does have to be */
1644 /* greater than y and less than y1. */
1645 if_debug3('F', "[F]cross y=%g, y_new=%g, y1=%g\n",
1646 fixed2float(y), fixed2float(y_new),
1647 fixed2float(y1));
1648 if (y_new <= y) {
1649 /*
1650 * This isn't possible. Recompute the intersection
1651 * accurately.
1652 */
1653 fixed ys, xs0, xs1, ye, xe0, xe1, dy, dx0, dx1;
1654
1655 INCR(cross_slow);
1656 if (endp->start.y < alp->start.y)
1657 ys = alp->start.y,
1658 xs0 = AL_X_AT_Y(endp, ys), xs1 = alp->start.x;
1659 else
1660 ys = endp->start.y,
1661 xs0 = endp->start.x, xs1 = AL_X_AT_Y(alp, ys);
1662 if (endp->end.y > alp->end.y)
1663 ye = alp->end.y,
1664 xe0 = AL_X_AT_Y(endp, ye), xe1 = alp->end.x;
1665 else
1666 ye = endp->end.y,
1667 xe0 = endp->end.x, xe1 = AL_X_AT_Y(alp, ye);
1668 dy = ye - ys;
1669 dx0 = xe0 - xs0;
1670 dx1 = xe1 - xs1;
1671 /* We need xs0 + cross * dx0 == xs1 + cross * dx1. */
1672 if (dx0 == dx1) {
1673 /* The two lines are coincident. Do nothing. */
1674 y_new = y1;
1675 } else {
1676 double cross = (double)(xs0 - xs1) / (dx1 - dx0);
1677
1678 y_new = (fixed)(ys + cross * dy);
1679 if (y_new <= y) {
1680 /*
1681 * This can only happen through some kind of
1682 * numeric disaster, but we have to check.
1683 */
1684 INCR(cross_low);
1685 y_new = y + fixed_epsilon;
1686 }
1687 }
1688 }
1689 *p_y_new = y_new;
1690 return true;
1691 }
1692
1693 static inline void
1694 set_x_next(active_line *endp, active_line *alp, fixed x)
1695 {
1696 while(endp != alp) {
1697 endp->x_next = x;
1698 endp = endp->next;
1699 }
1700 }
1701
1702 static inline int
1703 coord_weight(const active_line *alp)
1704 {
1705 return 1 + min(any_abs((int)((int64_t)alp->diff.y * 8 / alp->diff.x)), 256);
1706 }
1707
1708
1709 /* Find intersections of active lines within the band.
1710 Intersect and reorder them, and correct the bund top. */
1711 static void
1712 intersect_al(line_list *ll, fixed y, fixed *y_top, int draw, bool all_bands)
1713 {
1714 fixed x = min_fixed, y1 = *y_top;
1715 active_line *alp, *stopx = NULL;
1716 active_line *endp = NULL;
1717
1718 /* don't bother if no pixels with no pseudo_rasterization */
1719 if (y == y1) {
1720 /* Rather the intersection algorithm can handle this case with
1721 retrieving x_next equal to x_current,
1722 we bypass it for safety reason.
1723 */
1724 } else if (ll->fo->pseudo_rasterization || draw >= 0 || all_bands) {
1725 /*
1726 * Loop invariants:
1727 * alp = endp->next;
1728 * for all lines lp from stopx up to alp,
1729 * lp->x_next = AL_X_AT_Y(lp, y1).
1730 */
1731 for (alp = stopx = ll->x_list;
1732 INCR_EXPR(find_y), alp != 0;
1733 endp = alp, alp = alp->next
1734 ) {
1735 fixed nx = AL_X_AT_Y(alp, y1);
1736 fixed y_new;
1737
1738 alp->x_next = nx;
1739 /* Check for intersecting lines. */
1740 if (nx >= x)
1741 x = nx;
1742 else if (alp->x_current >= endp->x_current &&
1743 intersect(endp, alp, y, y1, &y_new)) {
1744 if (y_new <= y1) {
1745 stopx = endp;
1746 y1 = y_new;
1747 if (endp->diff.x == 0)
1748 nx = endp->start.x;
1749 else if (alp->diff.x == 0)
1750 nx = alp->start.x;
1751 else {
1752 fixed nx0 = AL_X_AT_Y(endp, y1);
1753 fixed nx1 = AL_X_AT_Y(alp, y1);
1754 if (nx0 != nx1) {
1755 /* Different results due to arithmetic errors.
1756 Choose an imtermediate point.
1757 We don't like to use floating numbners here,
1758 but the code with int64_t isn't much better. */
1759 int64_t w0 = coord_weight(endp);
1760 int64_t w1 = coord_weight(alp);
1761
1762 nx = (fixed)((w0 * nx0 + w1 * nx1) / (w0 + w1));
1763 } else
1764 nx = nx0;
1765 }
1766 endp->x_next = alp->x_next = nx; /* Ensure same X. */
1767 draw = 0;
1768 /* Can't guarantee same x for triple intersections here.
1769 Will take care below */
1770 }
1771 if (nx > x)
1772 x = nx;
1773 }
1774 }
1775 /* Recompute next_x for lines before the intersection. */
1776 for (alp = ll->x_list; alp != stopx; alp = alp->next)
1777 alp->x_next = AL_X_AT_Y(alp, y1);
1778 /* Ensure X monotonity (particularly imporoves triple intersections). */
1779 if (ll->x_list != NULL) {
1780 for (;;) {
1781 fixed x1;
1782 double sx = 0xbaadf00d; /* 'fixed' can overflow. We operate 7-bytes integers. */
1783 int k = 0xbaadf00d, n;
1784
1785 endp = ll->x_list;
1786 x1 = endp->x_next;
1787 for (alp = endp->next; alp != NULL; x1 = alp->x_next, alp = alp->next)
1788 if (alp->x_next < x1)
1789 break;
1790 if (alp == NULL)
1791 break;
1792 x1 = endp->x_next;
1793 n = 0;
1794 for (alp = endp->next; alp != NULL; alp = alp->next) {
1795 x = alp->x_next;
1796 if (x < x1) {
1797 if (n == 0) {
1798 if (endp->diff.x == 0) {
1799 k = -1;
1800 sx = x1;
1801 } else {
1802 k = coord_weight(endp);
1803 sx = (double)x1 * k;
1804 }
1805 n = 1;
1806 }
1807 n++;
1808 if (alp->diff.x == 0) {
1809 /* Vertical lines have a higher priority. */
1810 if (k <= -1) {
1811 sx += x;
1812 k--;
1813 } else {
1814 k = -1;
1815 sx = x;
1816 }
1817 } else if (k > 0) {
1818 int w = coord_weight(alp);
1819
1820 sx += (double)x * w;
1821 k += w;
1822 }
1823 } else {
1824 if (n > 1) {
1825 k = any_abs(k);
1826 set_x_next(endp, alp, (fixed)((sx + k / 2) / k));
1827 }
1828 x1 = alp->x_next;
1829 n = 0;
1830 endp = alp;
1831 }
1832 }
1833 if (n > 1) {
1834 k = any_abs(k);
1835 set_x_next(endp, alp, (fixed)((sx + k / 2) / k));
1836 }
1837 }
1838 }
1839 } else {
1840 /* Recompute next_x for lines before the intersection. */
1841 for (alp = ll->x_list; alp != stopx; alp = alp->next)
1842 alp->x_next = AL_X_AT_Y(alp, y1);
1843 }
1844 #ifdef DEBUG
1845 if (gs_debug_c('F')) {
1846 dlprintf1("[F]after loop: y1=%f\n", fixed2float(y1));
1847 print_line_list(ll->x_list);
1848 }
1849 #endif
1850 *y_top = y1;
1851 }
1852
1853 static inline int sign(int a)
1854 {
1855 return a < 0 ? -1 : a > 0 ? 1 : 0;
1856 }
1857
1858 /* ---------------- Trapezoid filling loop ---------------- */
1859
1860 /* Generate specialized algorythms for the most important cases : */
1861
1862 /* The smart winding counter advance operator : */
1863 #define signed_eo(a) ((a) < 0 ? -((a) & 1) : (a) > 0 ? ((a) & 1) : 0)
1864 #define ADVANCE_WINDING(inside, alp, ll) \
1865 { int k = alp->contour_count; \
1866 int v = ll->windings[k]; \
1867 inside -= signed_eo(v); \
1868 v = ll->windings[k] += alp->direction; \
1869 inside += signed_eo(v); \
1870 }
1871
1872 #define IS_SPOTAN 0
1873 #define PSEUDO_RASTERIZATION 1
1874 #define SMART_WINDING 1
1875 #define FILL_ADJUST 0
1876 #define FILL_DIRECT 1
1877 #define TEMPLATE_spot_into_trapezoids spot_into_trapezoids__pr_fd_sw
1878 #include "gxfilltr.h"
1879 #undef IS_SPOTAN
1880 #undef PSEUDO_RASTERIZATION
1881 #undef SMART_WINDING
1882 #undef FILL_ADJUST
1883 #undef FILL_DIRECT
1884 #undef TEMPLATE_spot_into_trapezoids
1885
1886 #define IS_SPOTAN 0
1887 #define PSEUDO_RASTERIZATION 1
1888 #define SMART_WINDING 1
1889 #define FILL_ADJUST 0
1890 #define FILL_DIRECT 0
1891 #define TEMPLATE_spot_into_trapezoids spot_into_trapezoids__pr_nd_sw
1892 #include "gxfilltr.h"
1893 #undef IS_SPOTAN
1894 #undef PSEUDO_RASTERIZATION
1895 #undef SMART_WINDING
1896 #undef FILL_ADJUST
1897 #undef FILL_DIRECT
1898 #undef TEMPLATE_spot_into_trapezoids
1899
1900 #define IS_SPOTAN 0
1901 #define PSEUDO_RASTERIZATION 0
1902 #define SMART_WINDING 1
1903 #define FILL_ADJUST 0
1904 #define FILL_DIRECT 1
1905 #define TEMPLATE_spot_into_trapezoids spot_into_trapezoids__nj_fd_sw
1906 #include "gxfilltr.h"
1907 #undef IS_SPOTAN
1908 #undef PSEUDO_RASTERIZATION
1909 #undef SMART_WINDING
1910 #undef FILL_ADJUST
1911 #undef FILL_DIRECT
1912 #undef TEMPLATE_spot_into_trapezoids
1913
1914 #define IS_SPOTAN 0
1915 #define PSEUDO_RASTERIZATION 0
1916 #define SMART_WINDING 1
1917 #define FILL_ADJUST 0
1918 #define FILL_DIRECT 0
1919 #define TEMPLATE_spot_into_trapezoids spot_into_trapezoids__nj_nd_sw
1920 #include "gxfilltr.h"
1921 #undef IS_SPOTAN
1922 #undef PSEUDO_RASTERIZATION
1923 #undef SMART_WINDING
1924 #undef FILL_ADJUST
1925 #undef FILL_DIRECT
1926 #undef TEMPLATE_spot_into_trapezoids
1927
1928 #undef signed_eo
1929 #undef ADVANCE_WINDING
1930 /* The simple winding counter advance operator : */
1931 #define ADVANCE_WINDING(inside, alp, ll) inside += alp->direction
1932
1933 #define IS_SPOTAN 1
1934 #define PSEUDO_RASTERIZATION 0
1935 #define SMART_WINDING 0
1936 #define FILL_ADJUST 0
1937 #define FILL_DIRECT 1
1938 #define TEMPLATE_spot_into_trapezoids spot_into_trapezoids__spotan
1939 #include "gxfilltr.h"
1940 #undef IS_SPOTAN
1941 #undef PSEUDO_RASTERIZATION
1942 #undef SMART_WINDING
1943 #undef FILL_ADJUST
1944 #undef FILL_DIRECT
1945 #undef TEMPLATE_spot_into_trapezoids
1946
1947 #define IS_SPOTAN 0
1948 #define PSEUDO_RASTERIZATION 1
1949 #define SMART_WINDING 0
1950 #define FILL_ADJUST 0
1951 #define FILL_DIRECT 1
1952 #define TEMPLATE_spot_into_trapezoids spot_into_trapezoids__pr_fd
1953 #include "gxfilltr.h"
1954 #undef IS_SPOTAN
1955 #undef PSEUDO_RASTERIZATION
1956 #undef SMART_WINDING
1957 #undef FILL_ADJUST
1958 #undef FILL_DIRECT
1959 #undef TEMPLATE_spot_into_trapezoids
1960
1961 #define IS_SPOTAN 0
1962 #define PSEUDO_RASTERIZATION 1
1963 #define SMART_WINDING 0
1964 #define FILL_ADJUST 0
1965 #define FILL_DIRECT 0
1966 #define TEMPLATE_spot_into_trapezoids spot_into_trapezoids__pr_nd
1967 #include "gxfilltr.h"
1968 #undef IS_SPOTAN
1969 #undef PSEUDO_RASTERIZATION
1970 #undef SMART_WINDING
1971 #undef FILL_ADJUST
1972 #undef FILL_DIRECT
1973 #undef TEMPLATE_spot_into_trapezoids
1974
1975 #define IS_SPOTAN 0
1976 #define PSEUDO_RASTERIZATION 0
1977 #define SMART_WINDING 0
1978 #define FILL_ADJUST 1
1979 #define FILL_DIRECT 1
1980 #define TEMPLATE_spot_into_trapezoids spot_into_trapezoids__aj_fd
1981 #include "gxfilltr.h"
1982 #undef IS_SPOTAN
1983 #undef PSEUDO_RASTERIZATION
1984 #undef SMART_WINDING
1985 #undef FILL_ADJUST
1986 #undef FILL_DIRECT
1987 #undef TEMPLATE_spot_into_trapezoids
1988
1989 #define IS_SPOTAN 0
1990 #define PSEUDO_RASTERIZATION 0
1991 #define SMART_WINDING 0
1992 #define FILL_ADJUST 1
1993 #define FILL_DIRECT 0
1994 #define TEMPLATE_spot_into_trapezoids spot_into_trapezoids__aj_nd
1995 #include "gxfilltr.h"
1996 #undef IS_SPOTAN
1997 #undef PSEUDO_RASTERIZATION
1998 #undef SMART_WINDING
1999 #undef FILL_ADJUST
2000 #undef FILL_DIRECT
2001 #undef TEMPLATE_spot_into_trapezoids
2002
2003 #define IS_SPOTAN 0
2004 #define PSEUDO_RASTERIZATION 0
2005 #define SMART_WINDING 0
2006 #define FILL_ADJUST 0
2007 #define FILL_DIRECT 1
2008 #define TEMPLATE_spot_into_trapezoids spot_into_trapezoids__nj_fd
2009 #include "gxfilltr.h"
2010 #undef IS_SPOTAN
2011 #undef PSEUDO_RASTERIZATION
2012 #undef SMART_WINDING
2013 #undef FILL_ADJUST
2014 #undef FILL_DIRECT
2015 #undef TEMPLATE_spot_into_trapezoids
2016
2017 #define IS_SPOTAN 0
2018 #define PSEUDO_RASTERIZATION 0
2019 #define SMART_WINDING 0
2020 #define FILL_ADJUST 0
2021 #define FILL_DIRECT 0
2022 #define TEMPLATE_spot_into_trapezoids spot_into_trapezoids__nj_nd
2023 #include "gxfilltr.h"
2024 #undef IS_SPOTAN
2025 #undef PSEUDO_RASTERIZATION
2026 #undef SMART_WINDING
2027 #undef FILL_ADJUST
2028 #undef FILL_DIRECT
2029 #undef TEMPLATE_spot_into_trapezoids
2030
2031 #undef ADVANCE_WINDING
2032
2033 /* Main filling loop. Takes lines off of y_list and adds them to */
2034 /* x_list as needed. band_mask limits the size of each band, */
2035 /* by requiring that ((y1 - 1) & band_mask) == (y0 & band_mask). */
2036 static int
2037 spot_into_trapezoids(line_list *ll, fixed band_mask)
2038 {
2039 /* For better porformance, choose a specialized algorithm : */
2040 const fill_options * const fo = ll->fo;
2041
2042 if (fo->is_spotan)
2043 return spot_into_trapezoids__spotan(ll, band_mask);
2044 if (fo->pseudo_rasterization) {
2045 if (ll->windings != NULL) {
2046 if (fo->fill_direct)
2047 return spot_into_trapezoids__pr_fd_sw(ll, band_mask);
2048 else
2049 return spot_into_trapezoids__pr_nd_sw(ll, band_mask);
2050 } else {
2051 if (fo->fill_direct)
2052 return spot_into_trapezoids__pr_fd(ll, band_mask);
2053 else
2054 return spot_into_trapezoids__pr_nd(ll, band_mask);
2055 }
2056 }
2057 if (fo->adjust_below | fo->adjust_above | fo->adjust_left | fo->adjust_right) {
2058 if (fo->fill_direct)
2059 return spot_into_trapezoids__aj_fd(ll, band_mask);
2060 else
2061 return spot_into_trapezoids__aj_nd(ll, band_mask);
2062 } else if (ll->windings != NULL) {
2063 if (fo->fill_direct)
2064 return spot_into_trapezoids__nj_fd_sw(ll, band_mask);
2065 else
2066 return spot_into_trapezoids__nj_nd_sw(ll, band_mask);
2067 } else {
2068 if (fo->fill_direct)
2069 return spot_into_trapezoids__nj_fd(ll, band_mask);
2070 else
2071 return spot_into_trapezoids__nj_nd(ll, band_mask);
2072 }
2073 }
2074
2075 /* ---------------- Range list management ---------------- */
2076
2077 /*
2078 * We originally thought we would store fixed values in coordinate ranges,
2079 * but it turned out we want to store integers.
2080 */
2081 typedef int coord_value_t;
2082 #define MIN_COORD_VALUE min_int
2083 #define MAX_COORD_VALUE max_int
2084 /*
2085 * The invariant for coord_range_ts in a coord_range_list_t:
2086 * if prev == 0:
2087 * next != 0
2088 * rmin == rmax == MIN_COORD_VALUE
2089 * else if next == 0:
2090 * prev != 0
2091 * rmin == rmax == MAX_COORD_VALUE
2092 * else
2093 * rmin < rmax
2094 * if prev != 0:
2095 * prev->next == this
2096 * prev->rmax < rmin
2097 * if next != 0:
2098 * next->prev = this
2099 * next->rmin > rmax
2100 * A coord_range_list_t has a boundary element at each end to avoid having
2101 * to test for null pointers in the insertion loop. The boundary elements
2102 * are the only empty ranges.
2103 */
2104 typedef struct coord_range_s coord_range_t;
2105 struct coord_range_s {
2106 coord_value_t rmin, rmax;
2107 coord_range_t *prev, *next;
2108 coord_range_t *alloc_next;
2109 };
2110 /* We declare coord_range_ts as simple because they only exist transiently. */
2111 gs_private_st_simple(st_coord_range, coord_range_t, "coord_range_t");
2112
2113 typedef struct coord_range_list_s {
2114 gs_memory_t *memory;
2115 struct rl_ {
2116 coord_range_t *first, *next, *limit;
2117 } local;
2118 coord_range_t *allocated;
2119 coord_range_t *freed;
2120 coord_range_t *current;
2121 coord_range_t first, last;
2122 } coord_range_list_t;
2123
2124 static coord_range_t *
2125 range_alloc(coord_range_list_t *pcrl)
2126 {
2127 coord_range_t *pcr;
2128
2129 if (pcrl->freed) {
2130 pcr = pcrl->freed;
2131 pcrl->freed = pcr->next;
2132 } else if (pcrl->local.next < pcrl->local.limit)
2133 pcr = pcrl->local.next++;
2134 else {
2135 pcr = gs_alloc_struct(pcrl->memory, coord_range_t, &st_coord_range,
2136 "range_alloc");
2137 if (pcr == 0)
2138 return 0;
2139 pcr->alloc_next = pcrl->allocated;
2140 pcrl->allocated = pcr;
2141 }
2142 return pcr;
2143 }
2144
2145 static void
2146 range_delete(coord_range_list_t *pcrl, coord_range_t *pcr)
2147 {
2148 if_debug3('Q', "[Qr]delete 0x%lx: [%d,%d)\n", (ulong)pcr, pcr->rmin,
2149 pcr->rmax);
2150 pcr->prev->next = pcr->next;
2151 pcr->next->prev = pcr->prev;
2152 pcr->next = pcrl->freed;
2153 pcrl->freed = pcr;
2154 }
2155
2156 static void
2157 range_list_clear(coord_range_list_t *pcrl)
2158 {
2159 if_debug0('Q', "[Qr]clearing\n");
2160 pcrl->first.next = &pcrl->last;
2161 pcrl->last.prev = &pcrl->first;
2162 pcrl->current = &pcrl->last;
2163 }
2164
2165 /* ------ "Public" procedures ------ */
2166
2167 /* Initialize a range list. We require num_local >= 2. */
2168 static void range_list_clear(coord_range_list_t *);
2169 static void
2170 range_list_init(coord_range_list_t *pcrl, coord_range_t *pcr_local,
2171 int num_local, gs_memory_t *mem)
2172 {
2173 pcrl->memory = mem;
2174 pcrl->local.first = pcrl->local.next = pcr_local;
2175 pcrl->local.limit = pcr_local + num_local;
2176 pcrl->allocated = pcrl->freed = 0;
2177 pcrl->first.rmin = pcrl->first.rmax = MIN_COORD_VALUE;
2178 pcrl->first.prev = 0;
2179 pcrl->last.rmin = pcrl->last.rmax = MAX_COORD_VALUE;
2180 pcrl->last.next = 0;
2181 range_list_clear(pcrl);
2182 }
2183
2184 /* Reset an initialized range list to the empty state. */
2185 static void
2186 range_list_reset(coord_range_list_t *pcrl)
2187 {
2188 if (pcrl->first.next != &pcrl->last) {
2189 pcrl->last.prev->next = pcrl->freed;
2190 pcrl->freed = pcrl->first.next;
2191 range_list_clear(pcrl);
2192 }
2193 }
2194
2195 /*
2196 * Move the cursor to the beginning of a range list, in the belief that
2197 * the next added ranges will roughly parallel the existing ones.
2198 * (Only affects performance, not function.)
2199 */
2200 static inline void
2201 range_list_rescan(coord_range_list_t *pcrl)
2202 {
2203 pcrl->current = pcrl->first.next;
2204 }
2205
2206 /* Free a range list. */
2207 static void
2208 range_list_free(coord_range_list_t *pcrl)
2209 {
2210 coord_range_t *pcr;
2211
2212 while ((pcr = pcrl->allocated) != 0) {
2213 coord_range_t *next = pcr->alloc_next;
2214
2215 gs_free_object(pcrl->memory, pcr, "range_list_free");
2216 pcrl->allocated = next;
2217 }
2218 }
2219
2220 /* Add a range. */
2221 static int
2222 range_list_add(coord_range_list_t *pcrl, coord_value_t rmin, coord_value_t rmax)
2223 {
2224 coord_range_t *pcr = pcrl->current;
2225
2226 if (rmin >= rmax)
2227 return 0;
2228 /*
2229 * Usually, ranges are added in increasing order within each scan line,
2230 * and overlapping ranges don't differ much. Optimize accordingly.
2231 */
2232 top:
2233 if (rmax < pcr->rmin) {
2234 if (rmin > pcr->prev->rmax)
2235 goto ins;
2236 pcr = pcr->prev;
2237 goto top;
2238 }
2239 if (rmin > pcr->rmax) {
2240 pcr = pcr->next;
2241 if (rmax < pcr->rmin)
2242 goto ins;
2243 goto top;
2244 }
2245 /*
2246 * Now we know that (rmin,rmax) overlaps (pcr->rmin,pcr->rmax).
2247 * Don't delete or merge into the special min and max ranges.
2248 */
2249 while (rmin <= pcr->prev->rmax) {
2250 /* Merge the range below pcr into this one. */
2251 if (!pcr->prev->prev)
2252 break; /* don't merge into the min range */
2253 pcr->rmin = pcr->prev->rmin;
2254 range_delete(pcrl, pcr->prev);
2255 }
2256 while (rmax >= pcr->next->rmin) {
2257 /* Merge the range above pcr into this one. */
2258 if (!pcr->next->next)
2259 break; /* don't merge into the max range */
2260 pcr->rmax = pcr->next->rmax;
2261 range_delete(pcrl, pcr->next);
2262 }
2263 /*
2264 * Now we know that the union of (rmin,rmax) and (pcr->rmin,pcr->rmax)
2265 * doesn't overlap or abut either adjacent range, except that it may
2266 * abut if the adjacent range is the special min or max range.
2267 */
2268 if (rmin < pcr->rmin) {
2269 if_debug3('Q', "[Qr]update 0x%lx => [%d,%d)\n", (ulong)pcr, rmin,
2270 pcr->rmax);
2271 pcr->rmin = rmin;
2272 }
2273 if (rmax > pcr->rmax) {
2274 if_debug3('Q', "[Qr]update 0x%lx => [%d,%d)\n", (ulong)pcr, pcr->rmin,
2275 rmax);
2276 pcr->rmax = rmax;
2277 }
2278 pcrl->current = pcr->next;
2279 return 0;
2280 ins:
2281 /* Insert a new range below pcr. */
2282 {
2283 coord_range_t *prev = range_alloc(pcrl);
2284
2285 if (prev == 0)
2286 return_error(gs_error_VMerror);
2287 if_debug3('Q', "[Qr]insert 0x%lx: [%d,%d)\n", (ulong)prev, rmin, rmax);
2288 prev->rmin = rmin, prev->rmax = rmax;
2289 (prev->prev = pcr->prev)->next = prev;
2290 prev->next = pcr;
2291 pcr->prev = prev;
2292 }
2293 pcrl->current = pcr;
2294 return 0;
2295 }
2296
2297 /*
2298 * Merge regions for active segments starting at a given Y, or all active
2299 * segments, up to the end of the sampling band or the end of the segment,
2300 * into the range list.
2301 */
2302 static int
2303 merge_ranges(coord_range_list_t *pcrl, const line_list *ll, fixed y_min, fixed y_top)
2304 {
2305 active_line *alp, *nlp;
2306 int code = 0;
2307
2308 range_list_rescan(pcrl);
2309 for (alp = ll->x_list; alp != 0 && code >= 0; alp = nlp) {
2310 fixed x0 = alp->x_current, x1, xt;
2311 bool forth = (alp->direction == DIR_UP || !alp->fi.curve);
2312 fixed xe = (forth ? alp->fi.x3 : alp->fi.x0);
2313 fixed ye = (forth ? alp->fi.y3 : alp->fi.y0);
2314
2315 nlp = alp->next;
2316 if (alp->start.y < y_min)
2317 continue;
2318 if (alp->monotonic_x && alp->monotonic_y && ye <= y_top) {
2319 vd_bar(alp->start.x, alp->start.y, alp->end.x, alp->end.y, 0, RGB(255, 0, 0));
2320 x1 = xe;
2321 if (x0 > x1)
2322 xt = x0, x0 = x1, x1 = xt;
2323 code = range_list_add(pcrl,
2324 fixed2int_pixround(x0 - ll->fo->adjust_left),
2325 fixed2int_rounded(x1 + ll->fo->adjust_right));
2326 alp->more_flattened = false; /* Skip all the segments left. */
2327 } else {
2328 x1 = x0;
2329 for (;;) {
2330 if (alp->end.y <= y_top)
2331 xt = alp->end.x;
2332 else
2333 xt = AL_X_AT_Y(alp, y_top);
2334 x0 = min(x0, xt);
2335 x1 = max(x1, xt);
2336 if (!alp->more_flattened || alp->end.y > y_top)
2337 break;
2338 code = step_al(alp, true);
2339 if (code < 0)
2340 return code;
2341 if (alp->end.y < alp->start.y) {
2342 remove_al(ll, alp); /* End of a monotonic part of a curve. */
2343 break;
2344 }
2345 }
2346 code = range_list_add(pcrl,
2347 fixed2int_pixround(x0 - ll->fo->adjust_left),
2348 fixed2int_rounded(x1 + ll->fo->adjust_right));
2349 }
2350
2351 }
2352 return code;
2353 }
2354
2355 /* ---------------- Scan line filling loop ---------------- */
2356
2357 /* defina specializations of the scanline algorithm. */
2358
2359 #define FILL_DIRECT 1
2360 #define TEMPLATE_spot_into_scanlines spot_into_scan_lines_fd
2361 #include "gxfillsl.h"
2362 #undef FILL_DIRECT
2363 #undef TEMPLATE_spot_into_scanlines
2364
2365 #define FILL_DIRECT 0
2366 #define TEMPLATE_spot_into_scanlines spot_into_scan_lines_nd
2367 #include "gxfillsl.h"
2368 #undef FILL_DIRECT
2369 #undef TEMPLATE_spot_into_scanlines
2370
2371 static int
2372 spot_into_scan_lines(line_list *ll, fixed band_mask)
2373 {
2374 if (ll->fo->fill_direct)
2375 return spot_into_scan_lines_fd(ll, band_mask);
2376 else
2377 return spot_into_scan_lines_nd(ll, band_mask);
2378 }
2379
2380