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