1 /* Copyright (C) 1989, 2000 artofcode LLC. All rights reserved.
2
3 This program is free software; you can redistribute it and/or modify it
4 under the terms of the GNU General Public License as published by the
5 Free Software Foundation; either version 2 of the License, or (at your
6 option) any later version.
7
8 This program is distributed in the hope that it will be useful, but
9 WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 General Public License for more details.
12
13 You should have received a copy of the GNU General Public License along
14 with this program; if not, write to the Free Software Foundation, Inc.,
15 59 Temple Place, Suite 330, Boston, MA, 02111-1307.
16
17 */
18
19 /*$Id: gxfill.c,v 1.8.2.1.2.1 2003/01/17 00:49:03 giles Exp $ */
20 /* Lower-level path filling procedures */
21 #include "gx.h"
22 #include "gserrors.h"
23 #include "gsstruct.h"
24 #include "gxfixed.h"
25 #include "gxdevice.h"
26 #include "gzpath.h"
27 #include "gzcpath.h"
28 #include "gxdcolor.h"
29 #include "gxhttile.h"
30 #include "gxistate.h"
31 #include "gxpaint.h" /* for prototypes */
32 #include "gsptype2.h"
33
34 /*
35 * Define which fill algorithm(s) to use. At least one of the following
36 * two #defines must be included (not commented out).
37 */
38 #define FILL_SCAN_LINES
39 #define FILL_TRAPEZOIDS
40 /*
41 * Define whether to sample curves when using the scan line algorithm
42 * rather than flattening them. This produces more accurate output, at
43 * some cost in time.
44 */
45 #define FILL_CURVES
46
47 /* ---------------- Statistics ---------------- */
48
49 #ifdef DEBUG
50 struct stats_fill_s {
51 long
52 fill, fill_alloc, y_up, y_down, horiz, x_step, slow_x, iter, find_y,
53 band, band_step, band_fill, afill, slant, slant_shallow, sfill,
54 mq_cross, cross_slow, cross_low, order, slow_order;
55 } stats_fill;
56
57 # define INCR(x) (++(stats_fill.x))
58 # define INCR_EXPR(x) INCR(x)
59 # define INCR_BY(x,n) (stats_fill.x += (n))
60 #else
61 # define INCR(x) DO_NOTHING
62 # define INCR_EXPR(x) discard(0)
63 # define INCR_BY(x,n) DO_NOTHING
64 #endif
65
66 /* ---------------- Active line management ---------------- */
67
68 /* Define the structure for keeping track of active lines. */
69 typedef struct active_line_s active_line;
70 struct active_line_s {
71 gs_fixed_point start; /* x,y where line starts */
72 gs_fixed_point end; /* x,y where line ends */
73 gs_fixed_point diff; /* end - start */
74 #define AL_DX(alp) ((alp)->diff.x)
75 #define AL_DY(alp) ((alp)->diff.y)
76 fixed y_fast_max; /* can do x_at_y in fixed point */
77 /* if y <= y_fast_max */
78 fixed num_adjust; /* 0 if diff.x >= 0, -diff.y + epsilon if */
79 /* diff.x < 0 and division truncates */
80 #if ARCH_DIV_NEG_POS_TRUNCATES
81 /* neg/pos truncates, we must bias the numberator. */
82 # define SET_NUM_ADJUST(alp) \
83 (alp)->num_adjust =\
84 ((alp)->diff.x >= 0 ? 0 : -(alp)->diff.y + fixed_epsilon)
85 # define ADD_NUM_ADJUST(num, alp) ((num) + (alp)->num_adjust)
86 # define MAX_MINUS_NUM_ADJUST(alp) ADD_NUM_ADJUST(max_fixed, alp)
87 #else
88 /* neg/pos takes the floor, no special action is needed. */
89 # define SET_NUM_ADJUST(alp) DO_NOTHING
90 # define ADD_NUM_ADJUST(num, alp) (num)
91 # define MAX_MINUS_NUM_ADJUST(alp) max_fixed
92 #endif
93 #define SET_AL_POINTS(alp, startp, endp)\
94 BEGIN\
95 (alp)->diff.y = (endp).y - (startp).y;\
96 (alp)->diff.x = (endp).x - (startp).x;\
97 SET_NUM_ADJUST(alp);\
98 (alp)->y_fast_max = MAX_MINUS_NUM_ADJUST(alp) /\
99 (((alp)->diff.x >= 0 ? (alp)->diff.x : -(alp)->diff.x) | 1) +\
100 (startp).y;\
101 (alp)->start = startp, (alp)->end = endp;\
102 END
103 /*
104 * We know that alp->start.y <= yv <= alp->end.y, because the fill loop
105 * guarantees that the only lines being considered are those with this
106 * property.
107 */
108 #define AL_X_AT_Y(alp, yv)\
109 ((yv) == (alp)->end.y ? (alp)->end.x :\
110 ((yv) <= (alp)->y_fast_max ?\
111 ADD_NUM_ADJUST(((yv) - (alp)->start.y) * AL_DX(alp), alp) / AL_DY(alp) :\
112 (INCR_EXPR(slow_x),\
113 fixed_mult_quo(AL_DX(alp), (yv) - (alp)->start.y, AL_DY(alp)))) +\
114 (alp)->start.x)
115 fixed x_current; /* current x position */
116 fixed x_next; /* x position at end of band */
117 const segment *pseg; /* endpoint of this line */
118 int direction; /* direction of line segment */
119 #define DIR_UP 1
120 #define DIR_HORIZONTAL 0 /* (these are handled specially) */
121 #define DIR_DOWN (-1)
122 int curve_k; /* # of subdivisions for curves,-1 for lines */
123 curve_cursor cursor; /* cursor for curves, unused for lines */
124 /*
125 * "Pending" lines (not reached in the Y ordering yet) use next and prev
126 * to order lines by increasing starting Y. "Active" lines (being scanned)
127 * use next and prev to order lines by increasing current X, or if the
128 * current Xs are equal, by increasing final X.
129 */
130 active_line *prev, *next;
131 /* Link together active_lines allocated individually */
132 active_line *alloc_next;
133 };
134
135 /*
136 * Define the ordering criterion for active lines that overlap in Y.
137 * Return -1, 0, or 1 if lp1 precedes, coincides with, or follows lp2.
138 *
139 * The lines' x_current values are correct for some Y value that crosses
140 * both of them and that is not both the start of one and the end of the
141 * other. (Neither line is horizontal.) We want the ordering at this
142 * Y value, or, of the x_current values are equal, greater Y values
143 * (if any: this Y value might be the end of both lines).
144 */
145 private int
x_order(const active_line * lp1,const active_line * lp2)146 x_order(const active_line *lp1, const active_line *lp2)
147 {
148 bool s1;
149
150 INCR(order);
151 if (lp1->x_current < lp2->x_current)
152 return -1;
153 else if (lp1->x_current > lp2->x_current)
154 return 1;
155 /*
156 * We need to compare the slopes of the lines. Start by
157 * checking one fast case, where the slopes have opposite signs.
158 */
159 if ((s1 = lp1->start.x < lp1->end.x) != (lp2->start.x < lp2->end.x))
160 return (s1 ? 1 : -1);
161 /*
162 * We really do have to compare the slopes. Fortunately, this isn't
163 * needed very often. We want the sign of the comparison
164 * dx1/dy1 - dx2/dy2, or (since we know dy1 and dy2 are positive)
165 * dx1 * dy2 - dx2 * dy1. In principle, we can't simply do this using
166 * doubles, since we need complete accuracy and doubles don't have
167 * enough fraction bits. However, with the usual 20+12-bit fixeds and
168 * 64-bit doubles, both of the factors would have to exceed 2^15
169 * device space pixels for the result to be inaccurate, so we
170 * simply disregard this possibility. ****** FIX SOMEDAY ******
171 */
172 INCR(slow_order);
173 {
174 fixed dx1 = lp1->end.x - lp1->start.x,
175 dy1 = lp1->end.y - lp1->start.y;
176 fixed dx2 = lp2->end.x - lp2->start.x,
177 dy2 = lp2->end.y - lp2->start.y;
178 double diff = (double)dx1 * dy2 - (double)dx2 * dy1;
179
180 return (diff < 0 ? -1 : diff > 0 ? 1 : 0);
181 }
182 }
183
184 /*
185 * The active_line structure isn't really simple, but since its instances
186 * only exist temporarily during a fill operation, we don't have to
187 * worry about a garbage collection occurring.
188 */
189 gs_private_st_simple(st_active_line, active_line, "active_line");
190
191 #ifdef DEBUG
192 /* Internal procedures for printing and checking active lines. */
193 private void
print_active_line(const char * label,const active_line * alp)194 print_active_line(const char *label, const active_line * alp)
195 {
196 dlprintf5("[f]%s 0x%lx(%d): x_current=%f x_next=%f\n",
197 label, (ulong) alp, alp->direction,
198 fixed2float(alp->x_current), fixed2float(alp->x_next));
199 dlprintf5(" start=(%f,%f) pt_end=0x%lx(%f,%f)\n",
200 fixed2float(alp->start.x), fixed2float(alp->start.y),
201 (ulong) alp->pseg,
202 fixed2float(alp->end.x), fixed2float(alp->end.y));
203 dlprintf2(" prev=0x%lx next=0x%lx\n",
204 (ulong) alp->prev, (ulong) alp->next);
205 }
206 private void
print_line_list(const active_line * flp)207 print_line_list(const active_line * flp)
208 {
209 const active_line *lp;
210
211 for (lp = flp; lp != 0; lp = lp->next) {
212 fixed xc = lp->x_current, xn = lp->x_next;
213
214 dlprintf3("[f]0x%lx(%d): x_current/next=%g",
215 (ulong) lp, lp->direction,
216 fixed2float(xc));
217 if (xn != xc)
218 dprintf1("/%g", fixed2float(xn));
219 dputc('\n');
220 }
221 }
222 inline private void
print_al(const char * label,const active_line * alp)223 print_al(const char *label, const active_line * alp)
224 {
225 if (gs_debug_c('F'))
226 print_active_line(label, alp);
227 }
228 private int
check_line_list(const active_line * flp)229 check_line_list(const active_line * flp)
230 {
231 const active_line *alp;
232
233 if (flp != 0)
234 for (alp = flp->prev->next; alp != 0; alp = alp->next)
235 if (alp->next != 0 && alp->next->x_current < alp->x_current) {
236 lprintf("[f]Lines out of order!\n");
237 print_active_line(" 1:", alp);
238 print_active_line(" 2:", alp->next);
239 return_error(gs_error_Fatal);
240 }
241 return 0;
242 }
243 #else
244 #define print_al(label,alp) DO_NOTHING
245 #endif
246
247 /* Line list structure */
248 struct line_list_s {
249 gs_memory_t *memory;
250 active_line *active_area; /* allocated active_line list */
251 active_line *next_active; /* next allocation slot */
252 active_line *limit; /* limit of local allocation */
253 int close_count; /* # of added closing lines */
254 active_line *y_list; /* Y-sorted list of pending lines */
255 active_line *y_line; /* most recently inserted line */
256 active_line x_head; /* X-sorted list of active lines */
257 #define x_list x_head.next
258 /* Put the arrays last so the scalars will have */
259 /* small displacements. */
260 /* Allocate a few active_lines locally */
261 /* to avoid round trips through the allocator. */
262 #if arch_small_memory
263 # define MAX_LOCAL_ACTIVE 6 /* don't overburden the stack */
264 #else
265 # define MAX_LOCAL_ACTIVE 20
266 #endif
267 active_line local_active[MAX_LOCAL_ACTIVE];
268 };
269 typedef struct line_list_s line_list;
270 typedef line_list *ll_ptr;
271
272 /* Forward declarations */
273 private void init_line_list(P2(ll_ptr, gs_memory_t *));
274 private void unclose_path(P2(gx_path *, int));
275 private void free_line_list(P1(ll_ptr));
276 private int add_y_list(P5(gx_path *, ll_ptr, fixed, fixed,
277 const gs_fixed_rect *));
278 private int add_y_line(P4(const segment *, const segment *, int, ll_ptr));
279 private void insert_x_new(P2(active_line *, ll_ptr));
280 private bool end_x_line(P2(active_line *, bool));
281
282 #define FILL_LOOP_PROC(proc)\
283 int proc(P11(ll_ptr, gx_device *,\
284 const gx_fill_params *, const gx_device_color *, gs_logical_operation_t,\
285 const gs_fixed_rect *, fixed, fixed, fixed, fixed, fixed))
286 private FILL_LOOP_PROC(fill_loop_by_scan_lines);
287 private FILL_LOOP_PROC(fill_loop_by_trapezoids);
288
289 /*
290 * This is the general path filling algorithm.
291 * It uses the center-of-pixel rule for filling.
292 * We can implement Microsoft's upper-left-corner-of-pixel rule
293 * by subtracting (0.5, 0.5) from all the coordinates in the path.
294 *
295 * The adjust parameters are a hack for keeping regions
296 * from coming out too faint: they specify an amount by which to expand
297 * the sides of every filled region.
298 * Setting adjust = fixed_half is supposed to produce the effect of Adobe's
299 * any-part-of-pixel rule, but it doesn't quite, because of the
300 * closed/open interval rule for regions. We detect this as a special case
301 * and do the slightly ugly things necessary to make it work.
302 */
303
304 /*
305 * Tweak the fill adjustment if necessary so that (nearly) empty
306 * rectangles are guaranteed to produce some output. This is a hack
307 * to work around a bug in the Microsoft Windows PostScript driver,
308 * which draws thin lines by filling zero-width rectangles, and in
309 * some other drivers that try to fill epsilon-width rectangles.
310 */
311 void
gx_adjust_if_empty(const gs_fixed_rect * pbox,gs_fixed_point * adjust)312 gx_adjust_if_empty(const gs_fixed_rect * pbox, gs_fixed_point * adjust)
313 {
314 /*
315 * For extremely large coordinates, the obvious subtractions could
316 * overflow. We can work around this easily by noting that since
317 * we know q.{x,y} >= p.{x,y}, the subtraction overflows iff the
318 * result is negative.
319 */
320 const fixed
321 dx = pbox->q.x - pbox->p.x, dy = pbox->q.y - pbox->p.y;
322
323 if (dx < fixed_half && dx > 0 && (dy >= int2fixed(2) || dy < 0)) {
324 adjust->x = arith_rshift_1(fixed_1 + fixed_epsilon - dx);
325 if_debug1('f', "[f]thin adjust_x=%g\n",
326 fixed2float(adjust->x));
327 } else if (dy < fixed_half && dy > 0 && (dx >= int2fixed(2) || dx < 0)) {
328 adjust->y = arith_rshift_1(fixed_1 + fixed_epsilon - dy);
329 if_debug1('f', "[f]thin adjust_y=%g\n",
330 fixed2float(adjust->y));
331 }
332 }
333
334 /*
335 * The general fill path algorithm.
336 */
337 private 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)338 gx_general_fill_path(gx_device * pdev, const gs_imager_state * pis,
339 gx_path * ppath, const gx_fill_params * params,
340 const gx_device_color * pdevc, const gx_clip_path * pcpath)
341 {
342 gs_fixed_point adjust;
343 gs_logical_operation_t lop = pis->log_op;
344 gs_fixed_rect ibox, bbox;
345 gx_device_clip cdev;
346 gx_device *dev = pdev;
347 gx_device *save_dev = dev;
348 gx_path ffpath;
349 gx_path *pfpath;
350 int code;
351 fixed adjust_left, adjust_right, adjust_below, adjust_above;
352 int max_fill_band = dev->max_fill_band;
353 #define NO_BAND_MASK ((fixed)(-1) << (sizeof(fixed) * 8 - 1))
354 bool fill_by_trapezoids;
355 line_list lst;
356
357 adjust = params->adjust;
358 /*
359 * Compute the bounding box before we flatten the path.
360 * This can save a lot of time if the path has curves.
361 * If the path is neither fully within nor fully outside
362 * the quick-check boxes, we could recompute the bounding box
363 * and make the checks again after flattening the path,
364 * but right now we don't bother.
365 */
366 gx_path_bbox(ppath, &ibox);
367 if (params->fill_zero_width)
368 gx_adjust_if_empty(&ibox, &adjust);
369 /* Check the bounding boxes. */
370 if_debug6('f', "[f]adjust=%g,%g bbox=(%g,%g),(%g,%g)\n",
371 fixed2float(adjust.x), fixed2float(adjust.y),
372 fixed2float(ibox.p.x), fixed2float(ibox.p.y),
373 fixed2float(ibox.q.x), fixed2float(ibox.q.y));
374 if (pcpath)
375 gx_cpath_inner_box(pcpath, &bbox);
376 else
377 (*dev_proc(dev, get_clipping_box)) (dev, &bbox);
378 if (!rect_within(ibox, bbox)) {
379 /*
380 * Intersect the path box and the clip bounding box.
381 * If the intersection is empty, this fill is a no-op.
382 */
383 if (pcpath)
384 gx_cpath_outer_box(pcpath, &bbox);
385 if_debug4('f', " outer_box=(%g,%g),(%g,%g)\n",
386 fixed2float(bbox.p.x), fixed2float(bbox.p.y),
387 fixed2float(bbox.q.x), fixed2float(bbox.q.y));
388 rect_intersect(ibox, bbox);
389 if (ibox.p.x - adjust.x >= ibox.q.x + adjust.x ||
390 ibox.p.y - adjust.y >= ibox.q.y + adjust.y
391 ) { /* Intersection of boxes is empty! */
392 return 0;
393 }
394 /*
395 * The path is neither entirely inside the inner clip box
396 * nor entirely outside the outer clip box.
397 * If we had to flatten the path, this is where we would
398 * recompute its bbox and make the tests again,
399 * but we don't bother right now.
400 *
401 * If there is a clipping path, set up a clipping device.
402 */
403 if (pcpath) {
404 dev = (gx_device *) & cdev;
405 gx_make_clip_device(&cdev, gx_cpath_list(pcpath));
406 cdev.target = save_dev;
407 cdev.max_fill_band = save_dev->max_fill_band;
408 (*dev_proc(dev, open_device)) (dev);
409 }
410 }
411 /*
412 * Compute the proper adjustment values.
413 * To get the effect of the any-part-of-pixel rule,
414 * we may have to tweak them slightly.
415 * NOTE: We changed the adjust_right/above value from 0.5+epsilon
416 * to 0.5 in release 5.01; even though this does the right thing
417 * in every case we could imagine, we aren't confident that it's
418 * correct. (The old values were definitely incorrect, since they
419 * caused 1-pixel-wide/high objects to color 2 pixels even if
420 * they fell exactly on pixel boundaries.)
421 */
422 if (adjust.x == fixed_half)
423 adjust_left = fixed_half - fixed_epsilon,
424 adjust_right = fixed_half /* + fixed_epsilon */ ; /* see above */
425 else
426 adjust_left = adjust_right = adjust.x;
427 if (adjust.y == fixed_half)
428 adjust_below = fixed_half - fixed_epsilon,
429 adjust_above = fixed_half /* + fixed_epsilon */ ; /* see above */
430 else
431 adjust_below = adjust_above = adjust.y;
432 /* Initialize the active line list. */
433 init_line_list(&lst, ppath->memory);
434 /*
435 * We have a choice of two different filling algorithms:
436 * scan-line-based and trapezoid-based. They compare as follows:
437 *
438 * Scan Trap
439 * ---- ----
440 * skip +draw 0-height horizontal lines
441 * slow +fast rectangles
442 * +fast slow curves
443 * +yes no write pixels at most once when adjust != 0
444 *
445 * Normally we use the scan line algorithm for characters, where curve
446 * speed is important, and for non-idempotent RasterOps, where double
447 * pixel writing must be avoided, and the trapezoid algorithm otherwise.
448 * However, we always use the trapezoid algorithm for rectangles.
449 */
450 #define DOUBLE_WRITE_OK() lop_is_idempotent(lop)
451 #ifdef FILL_SCAN_LINES
452 # ifdef FILL_TRAPEZOIDS
453 fill_by_trapezoids =
454 (!gx_path_has_curves(ppath) || params->flatness >= 1.0);
455 # else
456 fill_by_trapezoids = false;
457 # endif
458 #else
459 fill_by_trapezoids = true;
460 #endif
461 #ifdef FILL_TRAPEZOIDS
462 if (fill_by_trapezoids && !DOUBLE_WRITE_OK()) {
463 /* Avoid filling rectangles by scan line. */
464 gs_fixed_rect rbox;
465
466 if (gx_path_is_rectangular(ppath, &rbox)) {
467 int x0 = fixed2int_pixround(rbox.p.x - adjust_left);
468 int y0 = fixed2int_pixround(rbox.p.y - adjust_below);
469 int x1 = fixed2int_pixround(rbox.q.x + adjust_right);
470 int y1 = fixed2int_pixround(rbox.q.y + adjust_above);
471
472 return gx_fill_rectangle_device_rop(x0, y0, x1 - x0, y1 - y0,
473 pdevc, dev, lop);
474 }
475 fill_by_trapezoids = false; /* avoid double write */
476 }
477 #endif
478 #undef DOUBLE_WRITE_OK
479 /*
480 * Pre-process curves. When filling by trapezoids, we need to
481 * flatten the path completely; when filling by scan lines, we only
482 * need to monotonize it, unless FILL_CURVES is undefined.
483 */
484 gx_path_init_local(&ffpath, ppath->memory);
485 if (!gx_path_has_curves(ppath)) /* don't need to flatten */
486 pfpath = ppath;
487 else
488 #if defined(FILL_CURVES) && defined(FILL_SCAN_LINES)
489 /* Filling curves is possible. */
490 # ifdef FILL_TRAPEZOIDS
491 /* Not filling curves is also possible. */
492 if (fill_by_trapezoids)
493 # endif
494 #endif
495 #if !defined(FILL_CURVES) || defined(FILL_TRAPEZOIDS)
496 /* Not filling curves is possible. */
497 {
498 gx_path_init_local(&ffpath, ppath->memory);
499 code = gx_path_add_flattened_accurate(ppath, &ffpath,
500 params->flatness,
501 pis->accurate_curves);
502 if (code < 0)
503 return code;
504 pfpath = &ffpath;
505 }
506 #endif
507 #if defined(FILL_CURVES) && defined(FILL_SCAN_LINES)
508 /* Filling curves is possible. */
509 # ifdef FILL_TRAPEZOIDS
510 /* Not filling curves is also possible. */
511 else
512 # endif
513 if (gx_path_is_monotonic(ppath))
514 pfpath = ppath;
515 else {
516 gx_path_init_local(&ffpath, ppath->memory);
517 code = gx_path_add_monotonized(ppath, &ffpath);
518 if (code < 0)
519 return code;
520 pfpath = &ffpath;
521 }
522 #endif
523 if ((code = add_y_list(pfpath, &lst, adjust_below, adjust_above, &ibox)) < 0)
524 goto nope;
525 {
526 FILL_LOOP_PROC((*fill_loop));
527
528 /* Some short-sighted compilers won't allow a conditional here.... */
529 if (fill_by_trapezoids)
530 fill_loop = fill_loop_by_trapezoids;
531 else
532 fill_loop = fill_loop_by_scan_lines;
533 code = (*fill_loop)
534 (&lst, dev, params, pdevc, lop, &ibox,
535 adjust_left, adjust_right, adjust_below, adjust_above,
536 (max_fill_band == 0 ? NO_BAND_MASK : int2fixed(-max_fill_band)));
537 }
538 nope:if (lst.close_count != 0)
539 unclose_path(pfpath, lst.close_count);
540 free_line_list(&lst);
541 if (pfpath != ppath) /* had to flatten */
542 gx_path_free(pfpath, "gx_default_fill_path(flattened path)");
543 #ifdef DEBUG
544 if (gs_debug_c('f')) {
545 dlputs("[f] # alloc up down horiz step slowx iter find band bstep bfill\n");
546 dlprintf5(" %5ld %5ld %5ld %5ld %5ld",
547 stats_fill.fill, stats_fill.fill_alloc,
548 stats_fill.y_up, stats_fill.y_down,
549 stats_fill.horiz);
550 dlprintf4(" %5ld %5ld %5ld %5ld",
551 stats_fill.x_step, stats_fill.slow_x,
552 stats_fill.iter, stats_fill.find_y);
553 dlprintf3(" %5ld %5ld %5ld\n",
554 stats_fill.band, stats_fill.band_step,
555 stats_fill.band_fill);
556 dlputs("[f] afill slant shall sfill mqcrs order slowo\n");
557 dlprintf7(" %5ld %5ld %5ld %5ld %5ld %5ld %5ld\n",
558 stats_fill.afill, stats_fill.slant,
559 stats_fill.slant_shallow, stats_fill.sfill,
560 stats_fill.mq_cross, stats_fill.order,
561 stats_fill.slow_order);
562 }
563 #endif
564 return code;
565 }
566
567 /*
568 * Fill a path. This is the default implementation of the driver
569 * fill_path procedure.
570 */
571 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)572 gx_default_fill_path(gx_device * pdev, const gs_imager_state * pis,
573 gx_path * ppath, const gx_fill_params * params,
574 const gx_device_color * pdevc, const gx_clip_path * pcpath)
575 {
576 if (gx_dc_is_pattern2_color(pdevc)) {
577 /* Optimization for shading fill :
578 The general path filling algorithm subdivides fill region with
579 trapezoid or rectangle subregions and then paints each subregion
580 with given color. If the color is shading, each subregion to be
581 subdivided into areas of constant color. But with radial
582 shading each area is a high order polygon, being
583 subdivided into smaller subregions, so as total number of
584 subregions grows huge. Faster processing is done here by changing
585 the order of subdivision cycles : we first subdivide the shading into
586 areas of constant color, then apply the general path filling algorithm
587 (i.e. subdivide each area into trapezoids or rectangles), using the
588 filling path as clip mask.
589 */
590
591 gx_clip_path cpath_intersection;
592 gx_path path_intersection;
593 int code;
594
595 /* Shading fill algorithm uses "current path" parameter of the general
596 path filling algorithm as boundary of constant color area,
597 so we need to intersect the filling path with the clip path now,
598 reducing the number of pathes passed to it :
599 */
600 gx_path_init_local(&path_intersection, pdev->memory);
601 gx_cpath_init_local_shared(&cpath_intersection, pcpath, pdev->memory);
602 if ((code = gx_cpath_intersect(&cpath_intersection, ppath, params->rule, (gs_imager_state *)pis)) >= 0)
603 code = gx_cpath_to_path(&cpath_intersection, &path_intersection);
604
605 /* Do fill : */
606 if (code >= 0)
607 code = gx_dc_pattern2_fill_path_adjusted(pdevc, &path_intersection, NULL, pdev);
608
609 /* Destruct local data and return :*/
610 gx_path_free(&path_intersection, "shading_fill_path_intersection");
611 gx_cpath_free(&cpath_intersection, "shading_fill_cpath_intersection");
612 return code;
613 }
614 return gx_general_fill_path(pdev, pis, ppath, params, pdevc, pcpath);
615 }
616
617 /* Initialize the line list for a path. */
618 private void
init_line_list(ll_ptr ll,gs_memory_t * mem)619 init_line_list(ll_ptr ll, gs_memory_t * mem)
620 {
621 ll->memory = mem;
622 ll->active_area = 0;
623 ll->next_active = ll->local_active;
624 ll->limit = ll->next_active + MAX_LOCAL_ACTIVE;
625 ll->close_count = 0;
626 ll->y_list = 0;
627 ll->y_line = 0;
628 INCR(fill);
629 }
630
631 /* Unlink any line_close segments added temporarily. */
632 private void
unclose_path(gx_path * ppath,int count)633 unclose_path(gx_path * ppath, int count)
634 {
635 subpath *psub;
636
637 for (psub = ppath->first_subpath; count != 0;
638 psub = (subpath *) psub->last->next
639 )
640 if (psub->last == (segment *) & psub->closer) {
641 segment *prev = psub->closer.prev, *next = psub->closer.next;
642
643 prev->next = next;
644 if (next)
645 next->prev = prev;
646 psub->last = prev;
647 count--;
648 }
649 }
650
651 /* Free the line list. */
652 private void
free_line_list(ll_ptr ll)653 free_line_list(ll_ptr ll)
654 {
655 /* Free any individually allocated active_lines. */
656 gs_memory_t *mem = ll->memory;
657 active_line *alp;
658
659 while ((alp = ll->active_area) != 0) {
660 active_line *next = alp->alloc_next;
661
662 gs_free_object(mem, alp, "active line");
663 ll->active_area = next;
664 }
665 }
666
667 /*
668 * Construct a Y-sorted list of segments for rasterizing a path. We assume
669 * the path is non-empty. Only include non-horizontal lines or (monotonic)
670 * curve segments where one endpoint is locally Y-minimal, and horizontal
671 * lines that might color some additional pixels.
672 */
673 private int
add_y_list(gx_path * ppath,ll_ptr ll,fixed adjust_below,fixed adjust_above,const gs_fixed_rect * pbox)674 add_y_list(gx_path * ppath, ll_ptr ll, fixed adjust_below, fixed adjust_above,
675 const gs_fixed_rect * pbox)
676 {
677 segment *pseg = (segment *) ppath->first_subpath;
678 int close_count = 0;
679 /* fixed xmin = pbox->p.x; *//* not currently used */
680 fixed ymin = pbox->p.y;
681 /* fixed xmax = pbox->q.x; *//* not currently used */
682 fixed ymax = pbox->q.y;
683 int code;
684
685 while (pseg) {
686 /* We know that pseg points to a subpath head (s_start). */
687 subpath *psub = (subpath *) pseg;
688 segment *plast = psub->last;
689 int dir = 2; /* hack to skip first segment */
690 int first_dir, prev_dir;
691 segment *prev;
692
693 if (plast->type != s_line_close) {
694 /* Create a fake s_line_close */
695 line_close_segment *lp = &psub->closer;
696 segment *next = plast->next;
697
698 lp->next = next;
699 lp->prev = plast;
700 plast->next = (segment *) lp;
701 if (next)
702 next->prev = (segment *) lp;
703 lp->type = s_line_close;
704 lp->pt = psub->pt;
705 lp->sub = psub;
706 psub->last = plast = (segment *) lp;
707 ll->close_count++;
708 }
709 while ((prev_dir = dir, prev = pseg,
710 (pseg = pseg->next) != 0 && pseg->type != s_start)
711 ) {
712 /* This element is either a line or a monotonic curve segment. */
713 fixed iy = pseg->pt.y;
714 fixed py = prev->pt.y;
715
716 /*
717 * Segments falling entirely outside the ibox in Y
718 * are treated as though they were horizontal, *
719 * i.e., they are never put on the list.
720 */
721 #define COMPUTE_DIR(xo, xe, yo, ye)\
722 (ye > yo ? (ye <= ymin || yo >= ymax ? 0 : DIR_UP) :\
723 ye < yo ? (yo <= ymin || ye >= ymax ? 0 : DIR_DOWN) :\
724 2)
725 #define ADD_DIR_LINES(prev2, prev, this, pdir, dir)\
726 BEGIN\
727 if (pdir)\
728 { if ((code = add_y_line(prev2, prev, pdir, ll)) < 0) return code; }\
729 if (dir)\
730 { if ((code = add_y_line(prev, this, dir, ll)) < 0) return code; }\
731 END
732 dir = COMPUTE_DIR(prev->pt.x, pseg->pt.x, py, iy);
733 if (dir == 2) { /* Put horizontal lines on the list */
734 /* if they would color any pixels. */
735 if (fixed2int_pixround(iy - adjust_below) <
736 fixed2int_pixround(iy + adjust_above)
737 ) {
738 INCR(horiz);
739 if ((code = add_y_line(prev, pseg,
740 DIR_HORIZONTAL, ll)) < 0
741 )
742 return code;
743 }
744 dir = 0;
745 }
746 if (dir > prev_dir) {
747 ADD_DIR_LINES(prev->prev, prev, pseg, prev_dir, dir);
748 } else if (prev_dir == 2) /* first segment */
749 first_dir = dir;
750 if (pseg == plast) {
751 /*
752 * We skipped the first segment of the subpath, so the last
753 * segment must receive special consideration. Note that we
754 * have `closed' all subpaths.
755 */
756 if (first_dir > dir) {
757 ADD_DIR_LINES(prev, pseg, psub->next, dir, first_dir);
758 }
759 }
760 }
761 #undef COMPUTE_DIR
762 #undef ADD_DIR_LINES
763 }
764 return close_count;
765 }
766 /*
767 * Internal routine to test a segment and add it to the pending list if
768 * appropriate.
769 */
770 private int
add_y_line(const segment * prev_lp,const segment * lp,int dir,ll_ptr ll)771 add_y_line(const segment * prev_lp, const segment * lp, int dir, ll_ptr ll)
772 {
773 gs_fixed_point this, prev;
774 active_line *alp = ll->next_active;
775 fixed y_start;
776
777 if (alp == ll->limit) { /* Allocate separately */
778 alp = gs_alloc_struct(ll->memory, active_line,
779 &st_active_line, "active line");
780 if (alp == 0)
781 return_error(gs_error_VMerror);
782 alp->alloc_next = ll->active_area;
783 ll->active_area = alp;
784 INCR(fill_alloc);
785 } else
786 ll->next_active++;
787 this.x = lp->pt.x;
788 this.y = lp->pt.y;
789 prev.x = prev_lp->pt.x;
790 prev.y = prev_lp->pt.y;
791 switch ((alp->direction = dir)) {
792 case DIR_UP:
793 y_start = prev.y;
794 SET_AL_POINTS(alp, prev, this);
795 alp->pseg = lp;
796 break;
797 case DIR_DOWN:
798 y_start = this.y;
799 SET_AL_POINTS(alp, this, prev);
800 alp->pseg = prev_lp;
801 break;
802 case DIR_HORIZONTAL:
803 y_start = this.y; /* = prev.y */
804 alp->start = prev;
805 alp->end = this;
806 /* Don't need to set dx or y_fast_max */
807 alp->pseg = prev_lp; /* may not need this either */
808 break;
809 default: /* can't happen */
810 return_error(gs_error_unregistered);
811 }
812 /* Insert the new line in the Y ordering */
813 {
814 active_line *yp = ll->y_line;
815 active_line *nyp;
816
817 if (yp == 0) {
818 alp->next = alp->prev = 0;
819 ll->y_list = alp;
820 } else if (y_start >= yp->start.y) { /* Insert the new line after y_line */
821 while (INCR_EXPR(y_up),
822 ((nyp = yp->next) != NULL &&
823 y_start > nyp->start.y)
824 )
825 yp = nyp;
826 alp->next = nyp;
827 alp->prev = yp;
828 yp->next = alp;
829 if (nyp)
830 nyp->prev = alp;
831 } else { /* Insert the new line before y_line */
832 while (INCR_EXPR(y_down),
833 ((nyp = yp->prev) != NULL &&
834 y_start < nyp->start.y)
835 )
836 yp = nyp;
837 alp->prev = nyp;
838 alp->next = yp;
839 yp->prev = alp;
840 if (nyp)
841 nyp->next = alp;
842 else
843 ll->y_list = alp;
844 }
845 }
846 ll->y_line = alp;
847 print_al("add ", alp);
848 return 0;
849 }
850
851 /* ---------------- Filling loop utilities ---------------- */
852
853 /* Insert a newly active line in the X ordering. */
854 private void
insert_x_new(active_line * alp,ll_ptr ll)855 insert_x_new(active_line * alp, ll_ptr ll)
856 {
857 active_line *next;
858 active_line *prev = &ll->x_head;
859
860 alp->x_current = alp->start.x;
861 while (INCR_EXPR(x_step),
862 (next = prev->next) != 0 && x_order(next, alp) < 0
863 )
864 prev = next;
865 alp->next = next;
866 alp->prev = prev;
867 if (next != 0)
868 next->prev = alp;
869 prev->next = alp;
870 }
871
872 /*
873 * Handle a line segment that just ended. Return true iff this was
874 * the end of a line sequence.
875 */
876 private bool
end_x_line(active_line * alp,bool update)877 end_x_line(active_line *alp, bool update)
878 {
879 const segment *pseg = alp->pseg;
880 /*
881 * The computation of next relies on the fact that
882 * all subpaths have been closed. When we cycle
883 * around to the other end of a subpath, we must be
884 * sure not to process the start/end point twice.
885 */
886 const segment *next =
887 (alp->direction == DIR_UP ?
888 ( /* Upward line, go forward along path. */
889 pseg->type == s_line_close ? /* end of subpath */
890 ((const line_close_segment *)pseg)->sub->next :
891 pseg->next) :
892 ( /* Downward line, go backward along path. */
893 pseg->type == s_start ? /* start of subpath */
894 ((const subpath *)pseg)->last->prev :
895 pseg->prev)
896 );
897 gs_fixed_point npt;
898
899 npt.y = next->pt.y;
900 if (!update)
901 return npt.y <= pseg->pt.y;
902 if_debug5('F', "[F]ended 0x%lx: pseg=0x%lx y=%f next=0x%lx npt.y=%f\n",
903 (ulong) alp, (ulong) pseg, fixed2float(pseg->pt.y),
904 (ulong) next, fixed2float(npt.y));
905 if (npt.y <= pseg->pt.y) { /* End of a line sequence */
906 active_line *nlp = alp->next;
907
908 alp->prev->next = nlp;
909 if (nlp)
910 nlp->prev = alp->prev;
911 if_debug1('F', "[F]drop 0x%lx\n", (ulong) alp);
912 return true;
913 }
914 alp->pseg = next;
915 npt.x = next->pt.x;
916 SET_AL_POINTS(alp, alp->end, npt);
917 print_al("repl", alp);
918 return false;
919 }
920
921 #define LOOP_FILL_RECTANGLE(x, y, w, h)\
922 gx_fill_rectangle_device_rop(x, y, w, h, pdevc, dev, lop)
923 #define LOOP_FILL_RECTANGLE_DIRECT(x, y, w, h)\
924 (fill_direct ?\
925 (*fill_rect)(dev, x, y, w, h, cindex) :\
926 gx_fill_rectangle_device_rop(x, y, w, h, pdevc, dev, lop))
927
928 /* ---------------- Trapezoid filling loop ---------------- */
929
930 /* Forward references */
931 private int fill_slant_adjust(P12(fixed, fixed, fixed, fixed, fixed,
932 fixed, fixed, fixed, const gs_fixed_rect *,
933 const gx_device_color *, gx_device *, gs_logical_operation_t));
934 private void resort_x_line(P1(active_line *));
935
936 /****** PATCH ******/
937 #define LOOP_FILL_TRAPEZOID_FIXED(fx0, fw0, fy0, fx1, fw1, fh)\
938 loop_fill_trap(dev, fx0, fw0, fy0, fx1, fw1, fh, pbox, pdevc, lop)
939 private int
loop_fill_trap(gx_device * dev,fixed fx0,fixed fw0,fixed fy0,fixed fx1,fixed fw1,fixed fh,const gs_fixed_rect * pbox,const gx_device_color * pdevc,gs_logical_operation_t lop)940 loop_fill_trap(gx_device * dev, fixed fx0, fixed fw0, fixed fy0,
941 fixed fx1, fixed fw1, fixed fh, const gs_fixed_rect * pbox,
942 const gx_device_color * pdevc, gs_logical_operation_t lop)
943 {
944 fixed fy1 = fy0 + fh;
945 fixed ybot = max(fy0, pbox->p.y);
946 fixed ytop = min(fy1, pbox->q.y);
947 gs_fixed_edge left, right;
948
949 if (ybot >= ytop)
950 return 0;
951 left.start.y = right.start.y = fy0;
952 left.end.y = right.end.y = fy1;
953 right.start.x = (left.start.x = fx0) + fw0;
954 right.end.x = (left.end.x = fx1) + fw1;
955 return (*dev_proc(dev, fill_trapezoid))
956 (dev, &left, &right, ybot, ytop, false, pdevc, lop);
957 }
958 /****** END PATCH ******/
959
960 /* Main filling loop. Takes lines off of y_list and adds them to */
961 /* x_list as needed. band_mask limits the size of each band, */
962 /* by requiring that ((y1 - 1) & band_mask) == (y0 & band_mask). */
963 private int
fill_loop_by_trapezoids(ll_ptr ll,gx_device * dev,const gx_fill_params * params,const gx_device_color * pdevc,gs_logical_operation_t lop,const gs_fixed_rect * pbox,fixed adjust_left,fixed adjust_right,fixed adjust_below,fixed adjust_above,fixed band_mask)964 fill_loop_by_trapezoids(ll_ptr ll, gx_device * dev,
965 const gx_fill_params * params, const gx_device_color * pdevc,
966 gs_logical_operation_t lop, const gs_fixed_rect * pbox,
967 fixed adjust_left, fixed adjust_right,
968 fixed adjust_below, fixed adjust_above, fixed band_mask)
969 {
970 int rule = params->rule;
971 const fixed y_limit = pbox->q.y;
972 active_line *yll = ll->y_list;
973 fixed y;
974 int code;
975 bool fill_direct = color_writes_pure(pdevc, lop);
976 gx_color_index cindex;
977
978 dev_proc_fill_rectangle((*fill_rect));
979 /*
980 * Define a faster test for
981 * fixed2int_pixround(y - below) != fixed2int_pixround(y + above)
982 * where we know
983 * 0 <= below <= _fixed_pixround_v,
984 * 0 <= above <= min(fixed_half, fixed_1 - below).
985 * Subtracting out the integer parts, this is equivalent to
986 * fixed2int_pixround(fixed_fraction(y) - below) !=
987 * fixed2int_pixround(fixed_fraction(y) + above)
988 * or to
989 * fixed2int(fixed_fraction(y) + _fixed_pixround_v - below) !=
990 * fixed2int(fixed_fraction(y) + _fixed_pixround_v + above)
991 * Letting A = _fixed_pixround_v - below and B = _fixed_pixround_v + above,
992 * we can rewrite this as
993 * fixed2int(fixed_fraction(y) + A) != fixed2int(fixed_fraction(y) + B)
994 * Because of the range constraints given above, this is true precisely when
995 * fixed_fraction(y) + A < fixed_1 && fixed_fraction(y) + B >= fixed_1
996 * or equivalently
997 * fixed_fraction(y + B) < B - A.
998 * i.e.
999 * fixed_fraction(y + _fixed_pixround_v + above) < below + above
1000 */
1001 fixed y_span_delta = _fixed_pixround_v + adjust_above;
1002 fixed y_span_limit = adjust_below + adjust_above;
1003
1004 #define ADJUSTED_Y_SPANS_PIXEL(y)\
1005 (fixed_fraction((y) + y_span_delta) < y_span_limit)
1006
1007 if (yll == 0)
1008 return 0; /* empty list */
1009 if (fill_direct)
1010 cindex = pdevc->colors.pure,
1011 fill_rect = dev_proc(dev, fill_rectangle);
1012 y = yll->start.y; /* first Y value */
1013 ll->x_list = 0;
1014 ll->x_head.x_current = min_fixed; /* stop backward scan */
1015 while (1) {
1016 fixed y1;
1017 active_line *endp, *alp, *stopx;
1018 fixed x;
1019 int draw;
1020
1021 INCR(iter);
1022 /* Move newly active lines from y to x list. */
1023 while (yll != 0 && yll->start.y == y) {
1024 active_line *ynext = yll->next; /* insert smashes next/prev links */
1025
1026 if (yll->direction == DIR_HORIZONTAL) {
1027 /*
1028 * This is a hack to make sure that isolated horizontal
1029 * lines get stroked.
1030 */
1031 int yi = fixed2int_pixround(y - adjust_below);
1032 int xi, wi;
1033
1034 if (yll->start.x <= yll->end.x)
1035 xi = fixed2int_pixround(yll->start.x -
1036 adjust_left),
1037 wi = fixed2int_pixround(yll->end.x +
1038 adjust_right) - xi;
1039 else
1040 xi = fixed2int_pixround(yll->end.x -
1041 adjust_left),
1042 wi = fixed2int_pixround(yll->start.x +
1043 adjust_right) - xi;
1044 code = LOOP_FILL_RECTANGLE_DIRECT(xi, yi, wi, 1);
1045 if (code < 0)
1046 return code;
1047 } else
1048 insert_x_new(yll, ll);
1049 yll = ynext;
1050 }
1051 /* Check whether we've reached the maximum y. */
1052 if (y >= y_limit)
1053 break;
1054 if (ll->x_list == 0) { /* No active lines, skip to next start */
1055 if (yll == 0)
1056 break; /* no lines left */
1057 y = yll->start.y;
1058 continue;
1059 }
1060 /* Find the next evaluation point. */
1061 /* Start by finding the smallest y value */
1062 /* at which any currently active line ends */
1063 /* (or the next to-be-active line begins). */
1064 y1 = (yll != 0 ? yll->start.y : y_limit);
1065 /* Make sure we don't exceed the maximum band height. */
1066 {
1067 fixed y_band = y | ~band_mask;
1068
1069 if (y1 > y_band)
1070 y1 = y_band + 1;
1071 }
1072 for (alp = ll->x_list; alp != 0; alp = alp->next)
1073 if (alp->end.y < y1)
1074 y1 = alp->end.y;
1075 #ifdef DEBUG
1076 if (gs_debug_c('F')) {
1077 dlprintf2("[F]before loop: y=%f y1=%f:\n",
1078 fixed2float(y), fixed2float(y1));
1079 print_line_list(ll->x_list);
1080 }
1081 #endif
1082 /* Now look for line intersections before y1. */
1083 x = min_fixed;
1084 #define HAVE_PIXELS()\
1085 (fixed_pixround(y - adjust_below) < fixed_pixround(y1 + adjust_above))
1086 draw = (HAVE_PIXELS()? 1 : -1);
1087 /*
1088 * Loop invariants:
1089 * alp = endp->next;
1090 * for all lines lp from stopx up to alp,
1091 * lp->x_next = AL_X_AT_Y(lp, y1).
1092 */
1093 for (alp = stopx = ll->x_list;
1094 INCR_EXPR(find_y), alp != 0;
1095 endp = alp, alp = alp->next
1096 ) {
1097 fixed nx = AL_X_AT_Y(alp, y1);
1098 fixed dx_old, dx_den;
1099
1100 /* Check for intersecting lines. */
1101 if (nx >= x)
1102 x = nx;
1103 else if
1104 (draw >= 0 && /* don't bother if no pixels */
1105 (dx_old = alp->x_current - endp->x_current) >= 0 &&
1106 (dx_den = dx_old + endp->x_next - nx) > dx_old
1107 ) { /* Make a good guess at the intersection */
1108 /* Y value using only local information. */
1109 fixed dy = y1 - y, y_new;
1110
1111 if_debug3('F', "[F]cross: dy=%g, dx_old=%g, dx_new=%g\n",
1112 fixed2float(dy), fixed2float(dx_old),
1113 fixed2float(dx_den - dx_old));
1114 /* Do the computation in single precision */
1115 /* if the values are small enough. */
1116 y_new =
1117 ((dy | dx_old) < 1L << (size_of(fixed) * 4 - 1) ?
1118 dy * dx_old / dx_den :
1119 (INCR_EXPR(mq_cross), fixed_mult_quo(dy, dx_old, dx_den)))
1120 + y;
1121 /* The crossing value doesn't have to be */
1122 /* very accurate, but it does have to be */
1123 /* greater than y and less than y1. */
1124 if_debug3('F', "[F]cross y=%g, y_new=%g, y1=%g\n",
1125 fixed2float(y), fixed2float(y_new),
1126 fixed2float(y1));
1127 stopx = alp;
1128 if (y_new <= y) {
1129 /*
1130 * This isn't possible. Recompute the intersection
1131 * accurately.
1132 */
1133 fixed ys, xs0, xs1, ye, xe0, xe1, dy, dx0, dx1;
1134
1135 INCR(cross_slow);
1136 if (endp->start.y < alp->start.y)
1137 ys = alp->start.y,
1138 xs0 = AL_X_AT_Y(endp, ys), xs1 = alp->start.x;
1139 else
1140 ys = endp->start.y,
1141 xs0 = endp->start.x, xs1 = AL_X_AT_Y(alp, ys);
1142 if (endp->end.y > alp->end.y)
1143 ye = alp->end.y,
1144 xe0 = AL_X_AT_Y(endp, ye), xe1 = alp->end.x;
1145 else
1146 ye = endp->end.y,
1147 xe0 = endp->end.x, xe1 = AL_X_AT_Y(alp, ye);
1148 dy = ye - ys;
1149 dx0 = xe0 - xs0;
1150 dx1 = xe1 - xs1;
1151 /* We need xs0 + cross * dx0 == xs1 + cross * dx1. */
1152 if (dx0 == dx1) {
1153 /* The two lines are coincident. Do nothing. */
1154 y_new = y1;
1155 } else {
1156 double cross = (double)(xs0 - xs1) / (dx1 - dx0);
1157
1158 y_new = (fixed)(ys + cross * dy);
1159 if (y_new <= y) {
1160 /*
1161 * This can only happen through some kind of
1162 * numeric disaster, but we have to check.
1163 */
1164 INCR(cross_low);
1165 y_new = y + fixed_epsilon;
1166 }
1167 }
1168 }
1169 if (y_new < y1) {
1170 y1 = y_new;
1171 nx = AL_X_AT_Y(alp, y1);
1172 draw = 0;
1173 }
1174 if (nx > x)
1175 x = nx;
1176 }
1177 alp->x_next = nx;
1178 }
1179 /* Recompute next_x for lines before the intersection. */
1180 for (alp = ll->x_list; alp != stopx; alp = alp->next)
1181 alp->x_next = AL_X_AT_Y(alp, y1);
1182 #ifdef DEBUG
1183 if (gs_debug_c('F')) {
1184 dlprintf1("[F]after loop: y1=%f\n", fixed2float(y1));
1185 print_line_list(ll->x_list);
1186 }
1187 #endif
1188 /* Fill a multi-trapezoid band for the active lines. */
1189 /* Don't bother if no pixel centers lie within the band. */
1190 if (draw > 0 || (draw == 0 && HAVE_PIXELS())) {
1191 fixed height = y1 - y;
1192 fixed xlbot, xltop; /* as of last "outside" line */
1193 int inside = 0;
1194 active_line *nlp;
1195
1196 INCR(band);
1197 for (x = min_fixed, alp = ll->x_list; alp != 0; alp = nlp) {
1198 fixed xbot = alp->x_current;
1199 fixed xtop = alp->x_current = alp->x_next;
1200 fixed wtop;
1201 int xi, xli;
1202 int code;
1203
1204 print_al("step", alp);
1205 INCR(band_step);
1206 nlp = alp->next;
1207 /* Handle ended or out-of-order lines. After this, */
1208 /* the only member of alp we use is alp->direction. */
1209 if (alp->end.y != y1 || !end_x_line(alp, true)) {
1210 if (xtop <= x)
1211 resort_x_line(alp);
1212 else
1213 x = xtop;
1214 }
1215 /* rule = -1 for winding number rule, i.e. */
1216 /* we are inside if the winding number is non-zero; */
1217 /* rule = 1 for even-odd rule, i.e. */
1218 /* we are inside if the winding number is odd. */
1219 #define INSIDE_PATH_P() ((inside & rule) != 0)
1220 if (!INSIDE_PATH_P()) { /* i.e., outside */
1221 inside += alp->direction;
1222 if (INSIDE_PATH_P()) /* about to go in */
1223 xlbot = xbot, xltop = xtop;
1224 continue;
1225 }
1226 /* We're inside a region being filled. */
1227 inside += alp->direction;
1228 if (INSIDE_PATH_P()) /* not about to go out */
1229 continue;
1230 #undef INSIDE_PATH_P
1231 /* We just went from inside to outside, so fill the region. */
1232 wtop = xtop - xltop;
1233 INCR(band_fill);
1234 /*
1235 * If lines are temporarily out of order, we might have
1236 * xtop < xltop. Patch this up now if necessary. Note that
1237 * we can't test wtop < 0, because the subtraction might
1238 * overflow.
1239 */
1240 if (xtop < xltop) {
1241 if_debug2('f', "[f]patch %g,%g\n",
1242 fixed2float(xltop), fixed2float(xtop));
1243 xtop = xltop += arith_rshift(wtop, 1);
1244 wtop = 0;
1245 }
1246 if ((adjust_left | adjust_right) != 0) {
1247 xlbot -= adjust_left;
1248 xbot += adjust_right;
1249 xltop -= adjust_left;
1250 xtop += adjust_right;
1251 wtop = xtop - xltop;
1252 }
1253 if ((xli = fixed2int_var_pixround(xltop)) ==
1254 fixed2int_var_pixround(xlbot) &&
1255 (xi = fixed2int_var_pixround(xtop)) ==
1256 fixed2int_var_pixround(xbot)
1257 ) { /* Rectangle. */
1258 int yi = fixed2int_pixround(y - adjust_below);
1259 int wi = fixed2int_pixround(y1 + adjust_above) - yi;
1260
1261 code = LOOP_FILL_RECTANGLE_DIRECT(xli, yi,
1262 xi - xli, wi);
1263 } else if ((adjust_below | adjust_above) != 0) {
1264 /*
1265 * We want to get the effect of filling an area whose
1266 * outline is formed by dragging a square of side adj2
1267 * along the border of the trapezoid. This is *not*
1268 * equivalent to simply expanding the corners by
1269 * adjust: There are 3 cases needing different
1270 * algorithms, plus rectangles as a fast special case.
1271 */
1272 fixed wbot = xbot - xlbot;
1273
1274 if (xltop <= xlbot) {
1275 if (xtop >= xbot) { /* Top wider than bottom. */
1276 code = LOOP_FILL_TRAPEZOID_FIXED(
1277 xlbot, wbot, y - adjust_below,
1278 xltop, wtop, height);
1279 if (ADJUSTED_Y_SPANS_PIXEL(y1)) {
1280 if (code < 0)
1281 return code;
1282 INCR(afill);
1283 code = LOOP_FILL_RECTANGLE_DIRECT(
1284 xli, fixed2int_pixround(y1 - adjust_below),
1285 fixed2int_var_pixround(xtop) - xli, 1);
1286 }
1287 } else { /* Slanted trapezoid. */
1288 code = fill_slant_adjust(xlbot, xbot, y,
1289 xltop, xtop, height, adjust_below,
1290 adjust_above, pbox,
1291 pdevc, dev, lop);
1292 }
1293 } else {
1294 if (xtop <= xbot) { /* Bottom wider than top. */
1295 if (ADJUSTED_Y_SPANS_PIXEL(y)) {
1296 INCR(afill);
1297 xli = fixed2int_var_pixround(xlbot);
1298 code = LOOP_FILL_RECTANGLE_DIRECT(
1299 xli, fixed2int_pixround(y - adjust_below),
1300 fixed2int_var_pixround(xbot) - xli, 1);
1301 if (code < 0)
1302 return code;
1303 }
1304 code = LOOP_FILL_TRAPEZOID_FIXED(
1305 xlbot, wbot, y + adjust_above,
1306 xltop, wtop, height);
1307 } else { /* Slanted trapezoid. */
1308 code = fill_slant_adjust(xlbot, xbot, y,
1309 xltop, xtop, height, adjust_below,
1310 adjust_above, pbox,
1311 pdevc, dev, lop);
1312 }
1313 }
1314 } else /* No Y adjustment. */
1315 code = LOOP_FILL_TRAPEZOID_FIXED(xlbot, xbot - xlbot,
1316 y, xltop, wtop, height);
1317 if (code < 0)
1318 return code;
1319 }
1320 } else {
1321 /* Just scan for ended or out-of-order lines. */
1322 active_line *nlp;
1323
1324 for (x = min_fixed, alp = ll->x_list; alp != 0;
1325 alp = nlp
1326 ) {
1327 fixed nx = alp->x_current = alp->x_next;
1328
1329 nlp = alp->next;
1330 if_debug4('F',
1331 "[F]check 0x%lx,x=%g 0x%lx,x=%g\n",
1332 (ulong) alp->prev, fixed2float(x),
1333 (ulong) alp, fixed2float(nx));
1334 if (alp->end.y == y1) {
1335 if (end_x_line(alp, true))
1336 continue;
1337 }
1338 if (nx <= x)
1339 resort_x_line(alp);
1340 else
1341 x = nx;
1342 }
1343 }
1344 #ifdef DEBUG
1345 if (gs_debug_c('f')) {
1346 int code = check_line_list(ll->x_list);
1347
1348 if (code < 0)
1349 return code;
1350 }
1351 #endif
1352 y = y1;
1353 }
1354 return 0;
1355 }
1356
1357 /*
1358 * Handle the case of a slanted trapezoid with adjustment.
1359 * To do this exactly right requires filling a central trapezoid
1360 * (or rectangle) plus two horizontal almost-rectangles.
1361 */
1362 private int
fill_slant_adjust(fixed xlbot,fixed xbot,fixed y,fixed xltop,fixed xtop,fixed height,fixed adjust_below,fixed adjust_above,const gs_fixed_rect * pbox,const gx_device_color * pdevc,gx_device * dev,gs_logical_operation_t lop)1363 fill_slant_adjust(fixed xlbot, fixed xbot, fixed y,
1364 fixed xltop, fixed xtop, fixed height, fixed adjust_below,
1365 fixed adjust_above, const gs_fixed_rect * pbox,
1366 const gx_device_color * pdevc, gx_device * dev,
1367 gs_logical_operation_t lop)
1368 {
1369 fixed y1 = y + height;
1370
1371 dev_proc_fill_trapezoid((*fill_trap)) =
1372 dev_proc(dev, fill_trapezoid);
1373 const fixed yb = y - adjust_below;
1374 const fixed ya = y + adjust_above;
1375 const fixed y1b = y1 - adjust_below;
1376 const fixed y1a = y1 + adjust_above;
1377 const gs_fixed_edge *plbot;
1378 const gs_fixed_edge *prbot;
1379 const gs_fixed_edge *pltop;
1380 const gs_fixed_edge *prtop;
1381 gs_fixed_edge vert_left, slant_left, vert_right, slant_right;
1382 int code;
1383
1384 INCR(slant);
1385
1386 /* Set up all the edges, even though we may not need them all. */
1387
1388 if (xlbot < xltop) { /* && xbot < xtop */
1389 vert_left.start.x = vert_left.end.x = xlbot;
1390 vert_left.start.y = yb, vert_left.end.y = ya;
1391 vert_right.start.x = vert_right.end.x = xtop;
1392 vert_right.start.y = y1b, vert_right.end.y = y1a;
1393 slant_left.start.y = ya, slant_left.end.y = y1a;
1394 slant_right.start.y = yb, slant_right.end.y = y1b;
1395 plbot = &vert_left, prbot = &slant_right,
1396 pltop = &slant_left, prtop = &vert_right;
1397 } else {
1398 vert_left.start.x = vert_left.end.x = xltop;
1399 vert_left.start.y = y1b, vert_left.end.y = y1a;
1400 vert_right.start.x = vert_right.end.x = xbot;
1401 vert_right.start.y = yb, vert_right.end.y = ya;
1402 slant_left.start.y = yb, slant_left.end.y = y1b;
1403 slant_right.start.y = ya, slant_right.end.y = y1a;
1404 plbot = &slant_left, prbot = &vert_right,
1405 pltop = &vert_left, prtop = &slant_right;
1406 }
1407 slant_left.start.x = xlbot, slant_left.end.x = xltop;
1408 slant_right.start.x = xbot, slant_right.end.x = xtop;
1409
1410 if (ya >= y1b) {
1411 /*
1412 * The upper and lower adjustment bands overlap.
1413 * Since the entire entity is less than 2 pixels high
1414 * in this case, we could handle it very efficiently
1415 * with no more than 2 rectangle fills, but for right now
1416 * we don't attempt to do this.
1417 */
1418 int iyb = fixed2int_var_pixround(yb);
1419 int iya = fixed2int_var_pixround(ya);
1420 int iy1b = fixed2int_var_pixround(y1b);
1421 int iy1a = fixed2int_var_pixround(y1a);
1422
1423 INCR(slant_shallow);
1424 if (iy1b > iyb) {
1425 code = (*fill_trap) (dev, plbot, prbot,
1426 yb, y1b, false, pdevc, lop);
1427 if (code < 0)
1428 return code;
1429 }
1430 if (iya > iy1b) {
1431 int ix = fixed2int_var_pixround(vert_left.start.x);
1432 int iw = fixed2int_var_pixround(vert_right.start.x) - ix;
1433
1434 code = LOOP_FILL_RECTANGLE(ix, iy1b, iw, iya - iy1b);
1435 if (code < 0)
1436 return code;
1437 }
1438 if (iy1a > iya)
1439 code = (*fill_trap) (dev, pltop, prtop,
1440 ya, y1a, false, pdevc, lop);
1441 else
1442 code = 0;
1443 } else {
1444 /*
1445 * Clip the trapezoid if possible. This can save a lot
1446 * of work when filling paths that cross band boundaries.
1447 */
1448 fixed yac;
1449
1450 if (pbox->p.y < ya) {
1451 code = (*fill_trap) (dev, plbot, prbot,
1452 yb, ya, false, pdevc, lop);
1453 if (code < 0)
1454 return code;
1455 yac = ya;
1456 } else
1457 yac = pbox->p.y;
1458 if (pbox->q.y > y1b) {
1459 code = (*fill_trap) (dev, &slant_left, &slant_right,
1460 yac, y1b, false, pdevc, lop);
1461 if (code < 0)
1462 return code;
1463 code = (*fill_trap) (dev, pltop, prtop,
1464 y1b, y1a, false, pdevc, lop);
1465 } else
1466 code = (*fill_trap) (dev, &slant_left, &slant_right,
1467 yac, pbox->q.y, false, pdevc, lop);
1468 }
1469 return code;
1470 }
1471
1472 /* Re-sort the x list by moving alp backward to its proper spot. */
1473 private void
resort_x_line(active_line * alp)1474 resort_x_line(active_line * alp)
1475 {
1476 active_line *prev = alp->prev;
1477 active_line *next = alp->next;
1478
1479 prev->next = next;
1480 if (next)
1481 next->prev = prev;
1482 while (x_order(prev, alp) > 0) {
1483 if_debug2('F', "[F]swap 0x%lx,0x%lx\n",
1484 (ulong) alp, (ulong) prev);
1485 next = prev, prev = prev->prev;
1486 }
1487 alp->next = next;
1488 alp->prev = prev;
1489 /* next might be null, if alp was in the correct spot already. */
1490 if (next)
1491 next->prev = alp;
1492 prev->next = alp;
1493 }
1494
1495 /* ---------------- Range list management ---------------- */
1496
1497 /*
1498 * We originally thought we would store fixed values in coordinate ranges,
1499 * but it turned out we want to store integers.
1500 */
1501 typedef int coord_value_t;
1502 #define MIN_COORD_VALUE min_int
1503 #define MAX_COORD_VALUE max_int
1504 /*
1505 * The invariant for coord_range_ts in a coord_range_list_t:
1506 * if prev == 0:
1507 * next != 0
1508 * rmin == rmax == MIN_COORD_VALUE
1509 * else if next == 0:
1510 * prev != 0
1511 * rmin == rmax == MAX_COORD_VALUE
1512 * else
1513 * rmin < rmax
1514 * if prev != 0:
1515 * prev->next == this
1516 * prev->rmax < rmin
1517 * if next != 0:
1518 * next->prev = this
1519 * next->rmin > rmax
1520 * A coord_range_list_t has a boundary element at each end to avoid having
1521 * to test for null pointers in the insertion loop. The boundary elements
1522 * are the only empty ranges.
1523 */
1524 typedef struct coord_range_s coord_range_t;
1525 struct coord_range_s {
1526 coord_value_t rmin, rmax;
1527 coord_range_t *prev, *next;
1528 coord_range_t *alloc_next;
1529 };
1530 /* We declare coord_range_ts as simple because they only exist transiently. */
1531 gs_private_st_simple(st_coord_range, coord_range_t, "coord_range_t");
1532
1533 typedef struct coord_range_list_s {
1534 gs_memory_t *memory;
1535 struct rl_ {
1536 coord_range_t *first, *next, *limit;
1537 } local;
1538 coord_range_t *allocated;
1539 coord_range_t *freed;
1540 coord_range_t *current;
1541 coord_range_t first, last;
1542 } coord_range_list_t;
1543
1544 private coord_range_t *
range_alloc(coord_range_list_t * pcrl)1545 range_alloc(coord_range_list_t *pcrl)
1546 {
1547 coord_range_t *pcr;
1548
1549 if (pcrl->freed) {
1550 pcr = pcrl->freed;
1551 pcrl->freed = pcr->next;
1552 } else if (pcrl->local.next < pcrl->local.limit)
1553 pcr = pcrl->local.next++;
1554 else {
1555 pcr = gs_alloc_struct(pcrl->memory, coord_range_t, &st_coord_range,
1556 "range_alloc");
1557 if (pcr == 0)
1558 return 0;
1559 pcr->alloc_next = pcrl->allocated;
1560 pcrl->allocated = pcr;
1561 }
1562 return pcr;
1563 }
1564
1565 private void
range_delete(coord_range_list_t * pcrl,coord_range_t * pcr)1566 range_delete(coord_range_list_t *pcrl, coord_range_t *pcr)
1567 {
1568 if_debug3('Q', "[Qr]delete 0x%lx: [%d,%d)\n", (ulong)pcr, pcr->rmin,
1569 pcr->rmax);
1570 pcr->prev->next = pcr->next;
1571 pcr->next->prev = pcr->prev;
1572 pcr->next = pcrl->freed;
1573 pcrl->freed = pcr;
1574 }
1575
1576 private void
range_list_clear(coord_range_list_t * pcrl)1577 range_list_clear(coord_range_list_t *pcrl)
1578 {
1579 if_debug0('Q', "[Qr]clearing\n");
1580 pcrl->first.next = &pcrl->last;
1581 pcrl->last.prev = &pcrl->first;
1582 pcrl->current = &pcrl->last;
1583 }
1584
1585 /* ------ "Public" procedures ------ */
1586
1587 /* Initialize a range list. We require num_local >= 2. */
1588 private void range_list_clear(P1(coord_range_list_t *));
1589 private void
range_list_init(coord_range_list_t * pcrl,coord_range_t * pcr_local,int num_local,gs_memory_t * mem)1590 range_list_init(coord_range_list_t *pcrl, coord_range_t *pcr_local,
1591 int num_local, gs_memory_t *mem)
1592 {
1593 pcrl->memory = mem;
1594 pcrl->local.first = pcrl->local.next = pcr_local;
1595 pcrl->local.limit = pcr_local + num_local;
1596 pcrl->allocated = pcrl->freed = 0;
1597 pcrl->first.rmin = pcrl->first.rmax = MIN_COORD_VALUE;
1598 pcrl->first.prev = 0;
1599 pcrl->last.rmin = pcrl->last.rmax = MAX_COORD_VALUE;
1600 pcrl->last.next = 0;
1601 range_list_clear(pcrl);
1602 }
1603
1604 /* Reset an initialized range list to the empty state. */
1605 private void
range_list_reset(coord_range_list_t * pcrl)1606 range_list_reset(coord_range_list_t *pcrl)
1607 {
1608 if (pcrl->first.next != &pcrl->last) {
1609 pcrl->last.prev->next = pcrl->freed;
1610 pcrl->freed = pcrl->first.next;
1611 range_list_clear(pcrl);
1612 }
1613 }
1614
1615 /*
1616 * Move the cursor to the beginning of a range list, in the belief that
1617 * the next added ranges will roughly parallel the existing ones.
1618 * (Only affects performance, not function.)
1619 */
1620 inline private void
range_list_rescan(coord_range_list_t * pcrl)1621 range_list_rescan(coord_range_list_t *pcrl)
1622 {
1623 pcrl->current = pcrl->first.next;
1624 }
1625
1626 /* Free a range list. */
1627 private void
range_list_free(coord_range_list_t * pcrl)1628 range_list_free(coord_range_list_t *pcrl)
1629 {
1630 coord_range_t *pcr;
1631
1632 while ((pcr = pcrl->allocated) != 0) {
1633 coord_range_t *next = pcr->alloc_next;
1634
1635 gs_free_object(pcrl->memory, pcr, "range_list_free");
1636 pcrl->allocated = next;
1637 }
1638 }
1639
1640 /* Add a range. */
1641 private int
range_list_add(coord_range_list_t * pcrl,coord_value_t rmin,coord_value_t rmax)1642 range_list_add(coord_range_list_t *pcrl, coord_value_t rmin, coord_value_t rmax)
1643 {
1644 coord_range_t *pcr = pcrl->current;
1645
1646 if (rmin >= rmax)
1647 return 0;
1648 /*
1649 * Usually, ranges are added in increasing order within each scan line,
1650 * and overlapping ranges don't differ much. Optimize accordingly.
1651 */
1652 top:
1653 if (rmax < pcr->rmin) {
1654 if (rmin > pcr->prev->rmax)
1655 goto ins;
1656 pcr = pcr->prev;
1657 goto top;
1658 }
1659 if (rmin > pcr->rmax) {
1660 pcr = pcr->next;
1661 if (rmax < pcr->rmin)
1662 goto ins;
1663 goto top;
1664 }
1665 /*
1666 * Now we know that (rmin,rmax) overlaps (pcr->rmin,pcr->rmax).
1667 * Don't delete or merge into the special min and max ranges.
1668 */
1669 while (rmin <= pcr->prev->rmax) {
1670 /* Merge the range below pcr into this one. */
1671 if (!pcr->prev->prev)
1672 break; /* don't merge into the min range */
1673 pcr->rmin = pcr->prev->rmin;
1674 range_delete(pcrl, pcr->prev);
1675 }
1676 while (rmax >= pcr->next->rmin) {
1677 /* Merge the range above pcr into this one. */
1678 if (!pcr->next->next)
1679 break; /* don't merge into the max range */
1680 pcr->rmax = pcr->next->rmax;
1681 range_delete(pcrl, pcr->next);
1682 }
1683 /*
1684 * Now we know that the union of (rmin,rmax) and (pcr->rmin,pcr->rmax)
1685 * doesn't overlap or abut either adjacent range, except that it may
1686 * abut if the adjacent range is the special min or max range.
1687 */
1688 if (rmin < pcr->rmin) {
1689 if_debug3('Q', "[Qr]update 0x%lx => [%d,%d)\n", (ulong)pcr, rmin,
1690 pcr->rmax);
1691 pcr->rmin = rmin;
1692 }
1693 if (rmax > pcr->rmax) {
1694 if_debug3('Q', "[Qr]update 0x%lx => [%d,%d)\n", (ulong)pcr, pcr->rmin,
1695 rmax);
1696 pcr->rmax = rmax;
1697 }
1698 pcrl->current = pcr->next;
1699 return 0;
1700 ins:
1701 /* Insert a new range below pcr. */
1702 {
1703 coord_range_t *prev = range_alloc(pcrl);
1704
1705 if (prev == 0)
1706 return_error(gs_error_VMerror);
1707 if_debug3('Q', "[Qr]insert 0x%lx: [%d,%d)\n", (ulong)prev, rmin, rmax);
1708 prev->rmin = rmin, prev->rmax = rmax;
1709 (prev->prev = pcr->prev)->next = prev;
1710 prev->next = pcr;
1711 pcr->prev = prev;
1712 }
1713 pcrl->current = pcr;
1714 return 0;
1715 }
1716
1717 /* ---------------- Scan line filling loop ---------------- */
1718
1719 /* Forward references */
1720 private int merge_ranges(P6(coord_range_list_t *pcrl, ll_ptr ll,
1721 fixed y_min, fixed y_top,
1722 fixed adjust_left, fixed adjust_right));
1723 private void set_scan_line_points(P2(active_line *, fixed));
1724
1725 /* Main filling loop. */
1726 private int
fill_loop_by_scan_lines(ll_ptr ll,gx_device * dev,const gx_fill_params * params,const gx_device_color * pdevc,gs_logical_operation_t lop,const gs_fixed_rect * pbox,fixed adjust_left,fixed adjust_right,fixed adjust_below,fixed adjust_above,fixed band_mask)1727 fill_loop_by_scan_lines(ll_ptr ll, gx_device * dev,
1728 const gx_fill_params * params,
1729 const gx_device_color * pdevc,
1730 gs_logical_operation_t lop, const gs_fixed_rect * pbox,
1731 fixed adjust_left, fixed adjust_right,
1732 fixed adjust_below, fixed adjust_above,
1733 fixed band_mask)
1734 {
1735 int rule = params->rule;
1736 fixed fixed_flat = float2fixed(params->flatness);
1737 bool fill_direct = color_writes_pure(pdevc, lop);
1738 gx_color_index cindex;
1739 dev_proc_fill_rectangle((*fill_rect));
1740 active_line *yll = ll->y_list;
1741 fixed y_limit = pbox->q.y;
1742 /*
1743 * The meaning of adjust_below (B) and adjust_above (A) is that the
1744 * pixels that would normally be painted at coordinate Y get "smeared"
1745 * to coordinates Y-B through Y+A-epsilon, inclusive. This is
1746 * equivalent to saying that the pixels actually painted at coordinate Y
1747 * are those contributed by scan lines Y-A+epsilon through Y+B,
1748 * inclusive. (A = B = 0 is a special case, equivalent to B = 0, A =
1749 * epsilon.)
1750 */
1751 fixed y_frac_min =
1752 (adjust_above == fixed_0 ? fixed_half :
1753 fixed_half + fixed_epsilon - adjust_above);
1754 fixed y_frac_max =
1755 fixed_half + adjust_below;
1756 int y0 = fixed2int(min_fixed);
1757 fixed y_bot = min_fixed; /* normally int2fixed(y0) + y_frac_min */
1758 fixed y_top = min_fixed; /* normally int2fixed(y0) + y_frac_max */
1759 coord_range_list_t rlist;
1760 coord_range_t rlocal[MAX_LOCAL_ACTIVE];
1761 int code = 0;
1762
1763 if (yll == 0) /* empty list */
1764 return 0;
1765 range_list_init(&rlist, rlocal, countof(rlocal), ll->memory);
1766 if (fill_direct)
1767 cindex = pdevc->colors.pure,
1768 fill_rect = dev_proc(dev, fill_rectangle);
1769 ll->x_list = 0;
1770 ll->x_head.x_current = min_fixed; /* stop backward scan */
1771 while (code >= 0) {
1772 active_line *alp, *nlp;
1773 fixed y, x;
1774 bool new_band;
1775
1776 INCR(iter);
1777
1778 /*
1779 * Find the next sampling point, either the bottom of a sampling
1780 * band or a line start.
1781 */
1782
1783 if (ll->x_list == 0)
1784 y = (yll == 0 ? y_limit : yll->start.y);
1785 else {
1786 y = y_bot + fixed_1;
1787 if (yll != 0)
1788 y = min(y, yll->start.y);
1789 for (alp = ll->x_list; alp != 0; alp = alp->next)
1790 if (!end_x_line(alp, false))
1791 y = min(y, alp->end.y);
1792 }
1793
1794 /* Move newly active lines from y to x list. */
1795
1796 while (yll != 0 && yll->start.y == y) {
1797 active_line *ynext = yll->next; /* insert smashes next/prev links */
1798
1799 if (yll->direction == DIR_HORIZONTAL) {
1800 /* Ignore for now. */
1801 } else {
1802 insert_x_new(yll, ll);
1803 set_scan_line_points(yll, fixed_flat);
1804 }
1805 yll = ynext;
1806 }
1807
1808 /* Update active lines to y. */
1809
1810 x = min_fixed;
1811 for (alp = ll->x_list; alp != 0; alp = nlp) {
1812 fixed nx;
1813
1814 nlp = alp->next;
1815 e:if (alp->end.y <= y) {
1816 if (end_x_line(alp, true))
1817 continue;
1818 set_scan_line_points(alp, fixed_flat);
1819 goto e;
1820 }
1821 nx = alp->x_current =
1822 (alp->start.y >= y ? alp->start.x :
1823 alp->curve_k < 0 ?
1824 AL_X_AT_Y(alp, y) :
1825 gx_curve_x_at_y(&alp->cursor, y));
1826 if (nx < x) {
1827 /* Move this line backward in the list. */
1828 active_line *ilp = alp;
1829
1830 while (nx < (ilp = ilp->prev)->x_current)
1831 DO_NOTHING;
1832 /* Now ilp->x_current <= nx < ilp->next->x_cur. */
1833 alp->prev->next = alp->next;
1834 if (alp->next)
1835 alp->next->prev = alp->prev;
1836 if (ilp->next)
1837 ilp->next->prev = alp;
1838 alp->next = ilp->next;
1839 ilp->next = alp;
1840 alp->prev = ilp;
1841 continue;
1842 }
1843 x = nx;
1844 }
1845
1846 if (y > y_top || y >= y_limit) {
1847 /* We're beyond the end of the previous sampling band. */
1848 const coord_range_t *pcr;
1849
1850 /* Fill the ranges for y0. */
1851
1852 for (pcr = rlist.first.next; pcr != &rlist.last;
1853 pcr = pcr->next
1854 ) {
1855 int x0 = pcr->rmin, x1 = pcr->rmax;
1856
1857 if_debug4('Q', "[Qr]draw 0x%lx: [%d,%d),%d\n", (ulong)pcr,
1858 x0, x1, y0);
1859 code = LOOP_FILL_RECTANGLE_DIRECT(x0, y0, x1 - x0, 1);
1860 if_debug3('F', "[F]drawing [%d:%d),%d\n", x0, x1, y0);
1861 if (code < 0)
1862 goto done;
1863 }
1864 range_list_reset(&rlist);
1865
1866 /* Check whether we've reached the maximum y. */
1867
1868 if (y >= y_limit)
1869 break;
1870
1871 /* Reset the sampling band. */
1872
1873 y0 = fixed2int(y);
1874 if (fixed_fraction(y) < y_frac_min)
1875 --y0;
1876 y_bot = int2fixed(y0) + y_frac_min;
1877 y_top = int2fixed(y0) + y_frac_max;
1878 new_band = true;
1879 } else
1880 new_band = false;
1881
1882 if (y <= y_top) {
1883 /*
1884 * We're within the same Y pixel. Merge regions for segments
1885 * starting here (at y), up to y_top or the end of the segment.
1886 * If this is the first sampling within the band, run the
1887 * fill/eofill algorithm.
1888 */
1889 fixed y_min;
1890
1891 if (new_band) {
1892 /*
1893 * rule = -1 for winding number rule, i.e.
1894 * we are inside if the winding number is non-zero;
1895 * rule = 1 for even-odd rule, i.e.
1896 * we are inside if the winding number is odd.
1897 */
1898 int inside = 0;
1899
1900 #define INSIDE_PATH_P() ((inside & rule) != 0)
1901 INCR(band);
1902 for (alp = ll->x_list; alp != 0; alp = alp->next) {
1903 int x0 = fixed2int_pixround(alp->x_current - adjust_left);
1904
1905 for (;;) {
1906 /* We're inside a filled region. */
1907 print_al("step", alp);
1908 INCR(band_step);
1909 inside += alp->direction;
1910 if (!INSIDE_PATH_P())
1911 break;
1912 /*
1913 * Since we're dealing with closed paths, the test
1914 * for alp == 0 shouldn't be needed, but we may have
1915 * omitted lines that are to the right of the
1916 * clipping region.
1917 */
1918 if ((alp = alp->next) == 0)
1919 goto out;
1920 }
1921 #undef INSIDE_PATH_P
1922 /* We just went from inside to outside, so fill the region. */
1923 code = range_list_add(&rlist, x0,
1924 fixed2int_rounded(alp->x_current +
1925 adjust_right));
1926 if (code < 0)
1927 goto done;
1928 }
1929 out:
1930 y_min = min_fixed;
1931 } else
1932 y_min = y;
1933 code = merge_ranges(&rlist, ll, y_min, y_top, adjust_left,
1934 adjust_right);
1935 } /* else y < y_bot + 1, do nothing */
1936 }
1937 done:
1938 range_list_free(&rlist);
1939 return code;
1940 }
1941
1942 /*
1943 * Merge regions for active segments starting at a given Y, or all active
1944 * segments, up to the end of the sampling band or the end of the segment,
1945 * into the range list.
1946 */
1947 private int
merge_ranges(coord_range_list_t * pcrl,ll_ptr ll,fixed y_min,fixed y_top,fixed adjust_left,fixed adjust_right)1948 merge_ranges(coord_range_list_t *pcrl, ll_ptr ll, fixed y_min, fixed y_top,
1949 fixed adjust_left, fixed adjust_right)
1950 {
1951 active_line *alp, *nlp;
1952 int code = 0;
1953
1954 range_list_rescan(pcrl);
1955 for (alp = ll->x_list; alp != 0 && code >= 0; alp = nlp) {
1956 fixed x0 = alp->x_current, x1, xt;
1957
1958 nlp = alp->next;
1959 if (alp->start.y < y_min)
1960 continue;
1961 if (alp->end.y < y_top)
1962 x1 = alp->end.x;
1963 else if (alp->curve_k < 0)
1964 x1 = AL_X_AT_Y(alp, y_top);
1965 else
1966 x1 = gx_curve_x_at_y(&alp->cursor, y_top);
1967 if (x0 > x1)
1968 xt = x0, x0 = x1, x1 = xt;
1969 code = range_list_add(pcrl,
1970 fixed2int_pixround(x0 - adjust_left),
1971 fixed2int_rounded(x1 + adjust_right));
1972 }
1973 return code;
1974 }
1975
1976 /*
1977 * Set curve_k and, if necessary, the curve rendering parameters for
1978 * the current segment of an active line.
1979 */
1980 private void
set_scan_line_points(active_line * alp,fixed fixed_flat)1981 set_scan_line_points(active_line * alp, fixed fixed_flat)
1982 {
1983 const segment *pseg = alp->pseg;
1984 const gs_fixed_point *pp0;
1985
1986 if (alp->direction < 0) {
1987 pseg =
1988 (pseg->type == s_line_close ?
1989 ((const line_close_segment *)pseg)->sub->next :
1990 pseg->next);
1991 if (pseg->type != s_curve) {
1992 alp->curve_k = -1;
1993 return;
1994 }
1995 pp0 = &alp->end;
1996 } else {
1997 if (pseg->type != s_curve) {
1998 alp->curve_k = -1;
1999 return;
2000 }
2001 pp0 = &alp->start;
2002 }
2003 {
2004 const curve_segment *const pcseg = (const curve_segment *)pseg;
2005
2006 alp->curve_k =
2007 gx_curve_log2_samples(pp0->x, pp0->y, pcseg, fixed_flat);
2008 gx_curve_cursor_init(&alp->cursor, pp0->x, pp0->y, pcseg,
2009 alp->curve_k);
2010 }
2011 }
2012