1 /* Copyright (C) 2002 artofcode LLC. All rights reserved.
2
3 This software is provided AS-IS with no warranty, either express or
4 implied.
5
6 This software is distributed under license and may not be copied,
7 modified or distributed except as expressly authorized under the terms
8 of the license contained in the file LICENSE in this distribution.
9
10 For more information about licensing, please refer to
11 http://www.ghostscript.com/licensing/. For information on
12 commercial licensing, go to http://www.artifex.com/licensing/ or
13 contact Artifex Software, Inc., 101 Lucas Valley Road #110,
14 San Rafael, CA 94903, U.S.A., +1(415)492-9861.
15 */
16
17 /* $Id: gxfillsl.h,v 1.8 2005/02/15 14:47:37 igor Exp $ */
18 /* Configurable algorithm for filling a path by scanlines. */
19
20 /*
21 * Since we need several statically defined variants of this agorithm,
22 * we store it in .h file and include it several times into gxfill.c .
23 * Configuration macros (template arguments) are :
24 *
25 * FILL_DIRECT - See LOOP_FILL_RECTANGLE_DIRECT.
26 * TEMPLATE_spot_into_scanlines - the name of the procedure to generate.
27 */
28
29 private int
TEMPLATE_spot_into_scanlines(line_list * ll,fixed band_mask)30 TEMPLATE_spot_into_scanlines (line_list *ll, fixed band_mask)
31 {
32 const fill_options fo = *ll->fo;
33 active_line *yll = ll->y_list;
34 fixed y_limit = fo.ymax;
35 /*
36 * The meaning of adjust_below (B) and adjust_above (A) is that the
37 * pixels that would normally be painted at coordinate Y get "smeared"
38 * to coordinates Y-B through Y+A-epsilon, inclusive. This is
39 * equivalent to saying that the pixels actually painted at coordinate Y
40 * are those contributed by scan lines Y-A+epsilon through Y+B,
41 * inclusive. (A = B = 0 is a special case, equivalent to B = 0, A =
42 * epsilon.)
43 */
44 fixed y_frac_min =
45 (fo.adjust_above == fixed_0 ? fixed_half :
46 fixed_half + fixed_epsilon - fo.adjust_above);
47 fixed y_frac_max =
48 fixed_half + fo.adjust_below;
49 int y0 = fixed2int(min_fixed);
50 fixed y_bot = min_fixed; /* normally int2fixed(y0) + y_frac_min */
51 fixed y_top = min_fixed; /* normally int2fixed(y0) + y_frac_max */
52 fixed y = min_fixed;
53 coord_range_list_t rlist;
54 coord_range_t rlocal[MAX_LOCAL_ACTIVE];
55 int code = 0;
56
57 if (yll == 0) /* empty list */
58 return 0;
59 range_list_init(&rlist, rlocal, countof(rlocal), ll->memory);
60 ll->x_list = 0;
61 ll->x_head.x_current = min_fixed; /* stop backward scan */
62 while (code >= 0) {
63 active_line *alp, *nlp;
64 fixed x;
65 bool new_band;
66
67 INCR(iter);
68
69 move_al_by_y(ll, y); /* Skip horizontal pieces. */
70 /*
71 * Find the next sampling point, either the bottom of a sampling
72 * band or a line start.
73 */
74
75 if (ll->x_list == 0)
76 y = (yll == 0 ? ll->y_break : yll->start.y);
77 else {
78 y = y_bot + fixed_1;
79 if (yll != 0)
80 y = min(y, yll->start.y);
81 for (alp = ll->x_list; alp != 0; alp = alp->next) {
82 fixed yy = max(alp->fi.y3, alp->fi.y0);
83
84 yy = max(yy, alp->end.y); /* Non-monotonic curves may have an inner extreme. */
85 y = min(y, yy);
86 }
87 }
88
89 /* Move newly active lines from y to x list. */
90
91 while (yll != 0 && yll->start.y == y) {
92 active_line *ynext = yll->next; /* insert smashes next/prev links */
93
94 if (yll->direction == DIR_HORIZONTAL) {
95 /* Ignore for now. */
96 } else
97 insert_x_new(yll, ll);
98 yll = ynext;
99 }
100
101 /* Update active lines to y. */
102
103 x = min_fixed;
104 for (alp = ll->x_list; alp != 0; alp = nlp) {
105 fixed nx;
106
107 nlp = alp->next;
108 e:if (alp->end.y <= y || alp->start.y == alp->end.y) {
109 if (end_x_line(alp, ll, true))
110 continue;
111 if (alp->more_flattened)
112 if (alp->end.y <= y || alp->start.y == alp->end.y)
113 step_al(alp, true);
114 goto e;
115 }
116 nx = alp->x_current = (alp->start.y >= y ? alp->start.x : AL_X_AT_Y(alp, y));
117 if (nx < x) {
118 /* Move this line backward in the list. */
119 active_line *ilp = alp;
120
121 while (nx < (ilp = ilp->prev)->x_current)
122 DO_NOTHING;
123 /* Now ilp->x_current <= nx < ilp->next->x_cur. */
124 alp->prev->next = alp->next;
125 if (alp->next)
126 alp->next->prev = alp->prev;
127 if (ilp->next)
128 ilp->next->prev = alp;
129 alp->next = ilp->next;
130 ilp->next = alp;
131 alp->prev = ilp;
132 continue;
133 }
134 x = nx;
135 }
136
137 if (y > y_top || y >= y_limit) {
138 /* We're beyond the end of the previous sampling band. */
139 const coord_range_t *pcr;
140
141 /* Fill the ranges for y0. */
142
143 for (pcr = rlist.first.next; pcr != &rlist.last;
144 pcr = pcr->next
145 ) {
146 int x0 = pcr->rmin, x1 = pcr->rmax;
147
148 if_debug4('Q', "[Qr]draw 0x%lx: [%d,%d),%d\n", (ulong)pcr,
149 x0, x1, y0);
150 VD_RECT(x0, y0, x1 - x0, 1, VD_TRAP_COLOR);
151 code = LOOP_FILL_RECTANGLE_DIRECT(&fo, x0, y0, x1 - x0, 1);
152 if_debug3('F', "[F]drawing [%d:%d),%d\n", x0, x1, y0);
153 if (code < 0)
154 goto done;
155 }
156 range_list_reset(&rlist);
157
158 /* Check whether we've reached the maximum y. */
159
160 if (y >= y_limit)
161 break;
162
163 /* Reset the sampling band. */
164
165 y0 = fixed2int(y);
166 if (fixed_fraction(y) < y_frac_min)
167 --y0;
168 y_bot = int2fixed(y0) + y_frac_min;
169 y_top = int2fixed(y0) + y_frac_max;
170 new_band = true;
171 } else
172 new_band = false;
173
174 if (y <= y_top) {
175 /*
176 * We're within the same Y pixel. Merge regions for segments
177 * starting here (at y), up to y_top or the end of the segment.
178 * If this is the first sampling within the band, run the
179 * fill/eofill algorithm.
180 */
181 fixed y_min;
182
183 if (new_band) {
184 int inside = 0;
185
186 INCR(band);
187 for (alp = ll->x_list; alp != 0; alp = alp->next) {
188 int x0 = fixed2int_pixround(alp->x_current - fo.adjust_left);
189
190 for (;;) {
191 /* We're inside a filled region. */
192 print_al("step", alp);
193 INCR(band_step);
194 inside += alp->direction;
195 if (!INSIDE_PATH_P(inside, fo.rule))
196 break;
197 /*
198 * Since we're dealing with closed paths, the test
199 * for alp == 0 shouldn't be needed, but we may have
200 * omitted lines that are to the right of the
201 * clipping region.
202 */
203 if ((alp = alp->next) == 0)
204 goto out;
205 }
206 /* We just went from inside to outside, so fill the region. */
207 code = range_list_add(&rlist, x0,
208 fixed2int_rounded(alp->x_current +
209 fo.adjust_right));
210 if (code < 0)
211 goto done;
212 }
213 out:
214 y_min = min_fixed;
215 } else
216 y_min = y;
217 code = merge_ranges(&rlist, ll, y_min, y_top);
218 } /* else y < y_bot + 1, do nothing */
219 }
220 done:
221 range_list_free(&rlist);
222 return code;
223 }
224
225