1 /* Copyright (C) 2001-2019 Artifex Software, Inc.
2 All Rights Reserved.
3
4 This software is provided AS-IS with no warranty, either express or
5 implied.
6
7 This software is distributed under license and may not be copied,
8 modified or distributed except as expressly authorized under the terms
9 of the license contained in the file LICENSE in this distribution.
10
11 Refer to licensing information at http://www.artifex.com or contact
12 Artifex Software, Inc., 1305 Grant Avenue - Suite 200, Novato,
13 CA 94945, U.S.A., +1(415)492-9861, for further information.
14 */
15
16
17 /* Configurable algorithm for filling a trapezoid */
18
19 /*
20 * Since we need several statically defined variants of this agorithm,
21 * we store it in .h file and include several times into gdevddrw.c and
22 * into gxfill.h . Configuration flags (macros) are :
23 *
24 * GX_FILL_TRAPEZOID - a name of method
25 * CONTIGUOUS_FILL - prevent dropouts in narrow trapezoids
26 * SWAP_AXES - assume swapped axes
27 * FILL_DIRECT - See LOOP_FILL_RECTANGLE_DIRECT.
28 * LINEAR_COLOR - Fill with a linear color.
29 * EDGE_TYPE - a type of edge structure.
30 * FILL_ATTRS - operation attributes.
31 */
32
33 /*
34 * Fill a trapezoid. left.start => left.end and right.start => right.end
35 * define the sides; ybot and ytop define the top and bottom. Requires:
36 * {left,right}->start.y <= ybot <= ytop <= {left,right}->end.y.
37 * Lines where left.x >= right.x will not be drawn. Thanks to Paul Haeberli
38 * for an early floating point version of this algorithm.
39 */
40
41 /*
42 * With CONTIGUOUS_FILL is off,
43 * this algorithm paints pixels, which centers fall between
44 * the left and the right side of the trapezoid, excluding the
45 * right side (see PLRM3, 7.5. Scan conversion details).
46 * Particularly 0-width trapezoids are not painted.
47 *
48 * Similarly, it paints pixels, which centers
49 * fall between ybot and ytop, excluding ytop.
50 * Particularly 0-height trapezoids are not painted.
51 *
52 * With CONTIGUOUS_FILL is on, it paints a contigous area,
53 * adding a minimal number of pixels outside the trapezoid.
54 * Particularly it may paint pixels on the right and on the top sides,
55 * if they are necessary for the contiguity.
56 *
57 * With LINEAR_COLOR returns 1 if the gradient arithmetics overflows..
58 */
59
60 /*
61 We must paint pixels with index i such that
62
63 Xl <= i + 0.5 < Xr
64
65 The condition is is equivalent to
66
67 Xl - 0.5 <= i < Xr - 0.5
68
69 which is equivalent to
70
71 (is_integer(Xl - 0.5) ? Xl - 0.5 : ceil(Xl - 0.5)) <= i <
72 (is_integer(Xr - 0.5) ? Xr - 0.5 : floor(Xr - 0.5) + 1)
73
74 (the last '+1" happens due to the strong comparizon '<')
75 which is equivalent to
76
77 ceil(Xl - 0.5) <= i < ceil(Xr - 0.5)
78
79 trap_line represents the intersection coordinate as a rational value :
80
81 Xl = xl + e - fl
82 Xr = xr + e - fr
83
84 Where 'e' is 'fixed_epsilon', 0.5 is 'fixed_half', and fl == l.fx / l.h, fr == - r.fx / r.h,
85 e <= fl < 0, e <= fr < 0.
86 Let
87
88 xl' := xl + 0.5
89 xr' := xr + 0.5
90
91 Then
92
93 xl = xl' - 0.5
94 xr = xr' - 0.5
95
96 Xl = xl' - 0.5 + e - fl
97 Xr = xr' - 0.5 + e - fr
98
99 ceil(xl' - 0.5 + e - fl - 0.5) <= i < ceil(xr' - 0.5 + e - fr - 0.5)
100
101 which is equivalent to
102
103 ceil(xl' + e - fl) - 1 <= i < ceil(xr' + e - fr) - 1
104
105 which is equivalent to
106
107 (is_integer(xl' + e - fl) ? xl' + e - fl - 1 : ceil(xl' + e - fl) - 1) <= i <
108 (is_integer(xr' + e - fr) ? xr' + e - fr - 1 : ceil(xr' + e - fr) - 1)
109
110 which is equivalent to
111
112 (is_integer(xl' + e - fl) ? xl' + e - fl - 1 : floor(xl' + e - fl)) <= i <
113 (is_integer(xr' + e - fr) ? xr' + e - fr - 1 : floor(xr' + e - fr))
114
115 which is equivalent to
116
117 (is_integer(xl') && e == fl ? xl' - 1 : floor(xl' + e - fl)) <= i <
118 (is_integer(xr') && e == fr ? xr' - 1 : floor(xr' + e - fr))
119
120 Note that e != fl ==> floor(xl' + e - fl) == floor(xl') due to e - fl < LeastSignificantBit(xl') ;
121 e == fl ==> floor(xl' + e - fl) == floor(xl') due to e - fl == 0;
122
123 thus the condition is is equivalent to
124
125 (is_integer(xl') && e == fl ? xl' - 1 : floor(xl')) <= i <
126 (is_integer(xr') && e == fr ? xr' - 1 : floor(xr'))
127
128 It is computed with the macro 'rational_floor'.
129
130 */
131
132 #if defined(GX_FILL_TRAPEZOID) && defined(EDGE_TYPE)
133
GX_FILL_TRAPEZOID(gx_device * dev,const EDGE_TYPE * left,const EDGE_TYPE * right,fixed ybot,fixed ytop,int flags,const gx_device_color * pdevc,FILL_ATTRS fa)134 GX_FILL_TRAPEZOID (gx_device * dev, const EDGE_TYPE * left,
135 const EDGE_TYPE * right, fixed ybot, fixed ytop, int flags,
136 const gx_device_color * pdevc, FILL_ATTRS fa)
137 {
138 const fixed ymin = fixed_pixround(ybot) + fixed_half;
139 const fixed ymax = fixed_pixround(ytop);
140
141 if (ymin >= ymax)
142 return 0; /* no scan lines to sample */
143 {
144 int iy = fixed2int_var(ymin);
145 const int iy1 = fixed2int_var(ymax);
146 trap_line l, r;
147 register int rxl, rxr;
148 #if !LINEAR_COLOR
149 int ry;
150 #endif
151 const fixed
152 x0l = left->start.x, x1l = left->end.x, x0r = right->start.x,
153 x1r = right->end.x, dxl = x1l - x0l, dxr = x1r - x0r;
154 const fixed /* partial pixel offset to first line to sample */
155 ysl = ymin - left->start.y, ysr = ymin - right->start.y;
156 fixed fxl;
157 int code;
158 # if CONTIGUOUS_FILL
159 const bool peak0 = ((flags & 1) != 0);
160 const bool peak1 = ((flags & 2) != 0);
161 int peak_y0 = ybot + fixed_half;
162 int peak_y1 = ytop - fixed_half;
163 # endif
164 # if LINEAR_COLOR
165 int num_components = dev->color_info.num_components;
166 frac31 lgc[GX_DEVICE_COLOR_MAX_COMPONENTS];
167 int32_t lgf[GX_DEVICE_COLOR_MAX_COMPONENTS];
168 int32_t lgnum[GX_DEVICE_COLOR_MAX_COMPONENTS];
169 frac31 rgc[GX_DEVICE_COLOR_MAX_COMPONENTS];
170 int32_t rgf[GX_DEVICE_COLOR_MAX_COMPONENTS];
171 int32_t rgnum[GX_DEVICE_COLOR_MAX_COMPONENTS];
172 frac31 xgc[GX_DEVICE_COLOR_MAX_COMPONENTS];
173 int32_t xgf[GX_DEVICE_COLOR_MAX_COMPONENTS];
174 int32_t xgnum[GX_DEVICE_COLOR_MAX_COMPONENTS];
175 trap_gradient lg, rg, xg;
176 # else
177 gx_color_index cindex = pdevc->colors.pure;
178 dev_proc_fill_rectangle((*fill_rect)) =
179 dev_proc(dev, fill_rectangle);
180 # endif
181
182 if_debug2m('z', dev->memory, "[z]y=[%d,%d]\n", iy, iy1);
183
184 l.h = left->end.y - left->start.y;
185 if (l.h == 0)
186 return 0;
187 r.h = right->end.y - right->start.y;
188 if (r.h == 0)
189 return 0;
190 l.x = x0l + (fixed_half - fixed_epsilon);
191 r.x = x0r + (fixed_half - fixed_epsilon);
192 #if !LINEAR_COLOR
193 ry = iy;
194 #endif
195
196 /*
197 * Free variables of FILL_TRAP_RECT:
198 * SWAP_AXES, pdevc, dev, fa
199 * Free variables of FILL_TRAP_RECT_DIRECT:
200 * SWAP_AXES, fill_rect, dev, cindex
201 */
202 #define FILL_TRAP_RECT_INDIRECT(x,y,w,h)\
203 (SWAP_AXES ? gx_fill_rectangle_device_rop(y, x, h, w, pdevc, dev, fa) :\
204 gx_fill_rectangle_device_rop(x, y, w, h, pdevc, dev, fa))
205 #define FILL_TRAP_RECT_DIRECT(x,y,w,h)\
206 (SWAP_AXES ? (*fill_rect)(dev, y, x, h, w, cindex) :\
207 (*fill_rect)(dev, x, y, w, h, cindex))
208
209 #if LINEAR_COLOR
210 # define FILL_TRAP_RECT(x,y,w,h)\
211 (!(w) ? 0 : dev_proc(dev, fill_linear_color_scanline)(dev, fa, x, y, w, xg.c, xg.f, xg.num, xg.den))
212 #else
213 # define FILL_TRAP_RECT(x,y,w,h)\
214 (FILL_DIRECT ? FILL_TRAP_RECT_DIRECT(x,y,w,h) : FILL_TRAP_RECT_INDIRECT(x,y,w,h))
215 #endif
216
217 /* Compute the dx/dy ratios. */
218
219 /*
220 * Compute the x offsets at the first scan line to sample. We need
221 * to be careful in computing ys# * dx#f {/,%} h# because the
222 * multiplication may overflow. We know that all the quantities
223 * involved are non-negative, and that ys# is usually less than 1 (as
224 * a fixed, of course); this gives us a cheap conservative check for
225 * overflow in the multiplication.
226 */
227 #define YMULT_QUO(ys, tl)\
228 (ys < fixed_1 && tl.df < YMULT_LIMIT ? ys * tl.df / tl.h :\
229 fixed_mult_quo(ys, tl.df, tl.h))
230
231 #if CONTIGUOUS_FILL
232 /*
233 * If left and right boundary round to same pixel index,
234 * we would not paing the scan and would get a dropout.
235 * Check for this case and choose one of two pixels
236 * which is closer to the "axis". We need to exclude
237 * 'peak' because it would paint an excessive pixel.
238 */
239 #define SET_MINIMAL_WIDTH(ixl, ixr, l, r) \
240 if (ixl == ixr) \
241 if ((!peak0 || iy >= peak_y0) && (!peak1 || iy <= peak_y1)) {\
242 fixed x = int2fixed(ixl) + fixed_half;\
243 if (x - l.x < r.x - x)\
244 ++ixr;\
245 else\
246 --ixl;\
247 }
248
249 #define CONNECT_RECTANGLES(ixl, ixr, rxl, rxr, iy, ry, adj1, adj2, fill)\
250 if (adj1 < adj2) {\
251 if (iy - ry > 1) {\
252 code = fill(rxl, ry, rxr - rxl, iy - ry - 1);\
253 if (code < 0)\
254 goto xit;\
255 ry = iy - 1;\
256 }\
257 adj1 = adj2 = (adj2 + adj2) / 2;\
258 }
259
260 #else
261 #define SET_MINIMAL_WIDTH(ixl, ixr, l, r) DO_NOTHING
262 #define CONNECT_RECTANGLES(ixl, ixr, rxl, rxr, iy, ry, adj1, adj2, fill) DO_NOTHING
263 #endif
264 if (fixed_floor(l.x) == fixed_pixround(x1l)) {
265 /* Left edge is vertical, we don't need to increment. */
266 l.di = 0, l.df = 0;
267 fxl = 0;
268 } else {
269 compute_dx(&l, dxl, ysl);
270 fxl = YMULT_QUO(ysl, l);
271 l.x += fxl;
272 }
273 if (fixed_floor(r.x) == fixed_pixround(x1r)) {
274 /* Right edge is vertical. If both are vertical, */
275 /* we have a rectangle. */
276 # if !LINEAR_COLOR
277 if (l.di == 0 && l.df == 0) {
278 rxl = fixed2int_var(l.x);
279 rxr = fixed2int_var(r.x);
280 SET_MINIMAL_WIDTH(rxl, rxr, l, r);
281 code = FILL_TRAP_RECT(rxl, ry, rxr - rxl, iy1 - ry);
282 goto xit;
283 }
284 # endif
285 r.di = 0, r.df = 0;
286 }
287 /*
288 * The test for fxl != 0 is required because the right edge might
289 * cross some pixel centers even if the left edge doesn't.
290 */
291 else if (dxr == dxl && fxl != 0) {
292 if (l.di == 0)
293 r.di = 0, r.df = l.df;
294 else
295 compute_dx(&r, dxr, ysr);
296 if (ysr == ysl && r.h == l.h)
297 r.x += fxl;
298 else
299 r.x += YMULT_QUO(ysr, r);
300 } else {
301 compute_dx(&r, dxr, ysr);
302 r.x += YMULT_QUO(ysr, r);
303 }
304 /* Compute one line's worth of dx/dy. */
305 compute_ldx(&l, ysl);
306 compute_ldx(&r, ysr);
307 /* We subtracted fixed_epsilon from l.x, r.x to simplify rounding
308 when the rational part is zero. Now add it back to get xl', xr' */
309 l.x += fixed_epsilon;
310 r.x += fixed_epsilon;
311 # if LINEAR_COLOR
312 # ifdef DEBUG
313 if (check_gradient_overflow(left, right)) {
314 /* The caller must care of.
315 Checking it here looses some performance with triangles. */
316 return_error(gs_error_unregistered);
317 }
318 # endif
319 lg.c = lgc;
320 lg.f = lgf;
321 lg.num = lgnum;
322 rg.c = rgc;
323 rg.f = rgf;
324 rg.num = rgnum;
325 xg.c = xgc;
326 xg.f = xgf;
327 xg.num = xgnum;
328 code = init_gradient(&lg, fa, left, right, &l, ymin, num_components);
329 if (code < 0)
330 return code;
331 code = init_gradient(&rg, fa, right, left, &r, ymin, num_components);
332 if (code < 0)
333 return code;
334
335 # endif
336
337 #define rational_floor(tl)\
338 fixed2int_var(fixed_is_int(tl.x) && tl.xf == -tl.h ? tl.x - fixed_1 : tl.x)
339 #define STEP_LINE(ix, tl)\
340 tl.x += tl.ldi;\
341 if ( (tl.xf += tl.ldf) >= 0 ) tl.xf -= tl.h, tl.x++;\
342 ix = rational_floor(tl)
343
344 rxl = rational_floor(l);
345 rxr = rational_floor(r);
346 SET_MINIMAL_WIDTH(rxl, rxr, l, r);
347 while (LINEAR_COLOR ? 1 : ++iy != iy1) {
348 # if LINEAR_COLOR
349 if (rxl != rxr) {
350 code = set_x_gradient(&xg, &lg, &rg, &l, &r, rxl, rxr, num_components);
351 if (code < 0)
352 goto xit;
353 code = FILL_TRAP_RECT(rxl, iy, rxr - rxl, 1);
354 if (code < 0)
355 goto xit;
356 }
357 if (++iy == iy1)
358 break;
359 STEP_LINE(rxl, l);
360 STEP_LINE(rxr, r);
361 step_gradient(&lg, num_components);
362 step_gradient(&rg, num_components);
363 # else
364 register int ixl, ixr;
365
366 STEP_LINE(ixl, l);
367 STEP_LINE(ixr, r);
368 SET_MINIMAL_WIDTH(ixl, ixr, l, r);
369 if (ixl != rxl || ixr != rxr) {
370 CONNECT_RECTANGLES(ixl, ixr, rxl, rxr, iy, ry, rxr, ixl, FILL_TRAP_RECT);
371 CONNECT_RECTANGLES(ixl, ixr, rxl, rxr, iy, ry, ixr, rxl, FILL_TRAP_RECT);
372 code = FILL_TRAP_RECT(rxl, ry, rxr - rxl, iy - ry);
373 if (code < 0)
374 goto xit;
375 rxl = ixl, rxr = ixr, ry = iy;
376 }
377 # endif
378 }
379 # if !LINEAR_COLOR
380 code = FILL_TRAP_RECT(rxl, ry, rxr - rxl, iy - ry);
381 # else
382 code = 0;
383 # endif
384 #undef STEP_LINE
385 #undef SET_MINIMAL_WIDTH
386 #undef CONNECT_RECTANGLES
387 #undef FILL_TRAP_RECT
388 #undef FILL_TRAP_RECT_DIRECT
389 #undef FILL_TRAP_RECT_INRECT
390 #undef YMULT_QUO
391 xit: if (code < 0 && FILL_DIRECT)
392 return_error(code);
393 return_if_interrupt(dev->memory);
394 return code;
395 }
396 }
397
398 #undef GX_FILL_TRAPEZOID
399 #undef CONTIGUOUS_FILL
400 #undef SWAP_AXES
401 #undef FLAGS_TYPE
402
403 #else
404 int dummy;
405 #endif
406