File: gxdtfill.h

package info (click to toggle)
ghostscript 8.71~dfsg2-9+squeeze1
  • links: PTS, VCS
  • area: main
  • in suites: squeeze
  • size: 79,896 kB
  • ctags: 80,654
  • sloc: ansic: 501,432; sh: 25,689; python: 4,853; cpp: 3,633; perl: 3,597; tcl: 1,480; makefile: 1,187; lisp: 407; asm: 284; xml: 263; awk: 66; csh: 17; yacc: 15
file content (400 lines) | stat: -rw-r--r-- 12,450 bytes parent folder | download | duplicates (3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
/* Copyright (C) 2001-2006 Artifex Software, Inc.
   All Rights Reserved.
  
   This software is provided AS-IS with no warranty, either express or
   implied.

   This software is distributed under license and may not be copied, modified
   or distributed except as expressly authorized under the terms of that
   license.  Refer to licensing information at http://www.artifex.com/
   or contact Artifex Software, Inc.,  7 Mt. Lassen Drive - Suite A-134,
   San Rafael, CA  94903, U.S.A., +1(415)492-9861, for further information.
*/

/* $Id: gxdtfill.h 8022 2007-06-05 22:23:38Z giles $ */
/* Configurable algorithm for filling a trapezoid */

/*
 * Since we need several statically defined variants of this agorithm,
 * we store it in .h file and include several times into gdevddrw.c and 
 * into gxfill.h . Configuration flags (macros) are :
 * 
 *   GX_FILL_TRAPEZOID - a name of method
 *   CONTIGUOUS_FILL   - prevent dropouts in narrow trapezoids
 *   SWAP_AXES         - assume swapped axes
 *   FILL_DIRECT       - See LOOP_FILL_RECTANGLE_DIRECT.
 *   LINEAR_COLOR      - Fill with a linear color.
 *   EDGE_TYPE	       - a type of edge structure.
 *   FILL_ATTRS        - operation attributes. 
 */

/*
 * Fill a trapezoid.  left.start => left.end and right.start => right.end
 * define the sides; ybot and ytop define the top and bottom.  Requires:
 *      {left,right}->start.y <= ybot <= ytop <= {left,right}->end.y.
 * Lines where left.x >= right.x will not be drawn.  Thanks to Paul Haeberli
 * for an early floating point version of this algorithm.
 */

/*
 * With CONTIGUOUS_FILL is off, 
 * this algorithm paints pixels, which centers fall between
 * the left and the right side of the trapezoid, excluding the 
 * right side (see PLRM3, 7.5. Scan conversion details). 
 * Particularly 0-width trapezoids are not painted.
 *
 * Similarly, it paints pixels, which centers
 * fall between ybot and ytop, excluding ytop.
 * Particularly 0-height trapezoids are not painted.
 *
 * With CONTIGUOUS_FILL is on, it paints a contigous area,
 * adding a minimal number of pixels outside the trapezoid.
 * Particularly it may paint pixels on the right and on the top sides,
 * if they are necessary for the contiguity.
 *
 * With LINEAR_COLOR returns 1 if the gradient arithmetics overflows.. 
 */

/*
We must paint pixels with index i such that

    Xl <= i + 0.5 < Xr

The condition is is equivalent to

    Xl - 0.5 <= i < Xr - 0.5

which is equivalent to

    (is_integer(Xl - 0.5) ? Xl - 0.5 : ceil(Xl - 0.5)) <= i <
    (is_integer(Xr - 0.5) ? Xr - 0.5 : floor(Xr - 0.5) + 1)

(the last '+1" happens due to the strong comparizon '<')
which is equivalent to

    ceil(Xl - 0.5) <= i < ceil(Xr - 0.5)

trap_line represents the intersection coordinate as a rational value :

    Xl = xl + e - fl
    Xr = xr + e - fr

Where 'e' is 'fixed_epsilon', 0.5 is 'fixed_half', and fl == l.fx / l.h, fr == - r.fx / r.h,
e <= fl < 0, e <= fr < 0.
Let 

    xl' := xl + 0.5
    xr' := xr + 0.5

Then 

    xl = xl' - 0.5
    xr = xr' - 0.5

    Xl = xl' - 0.5 + e - fl
    Xr = xr' - 0.5 + e - fr

    ceil(xl' - 0.5 + e - fl - 0.5) <= i < ceil(xr' - 0.5 + e - fr - 0.5)
    
which is equivalent to

    ceil(xl' + e - fl) - 1 <= i < ceil(xr' + e - fr) - 1

which is equivalent to

    (is_integer(xl' + e - fl) ? xl' + e - fl - 1 : ceil(xl' + e - fl) - 1) <= i <
    (is_integer(xr' + e - fr) ? xr' + e - fr - 1 : ceil(xr' + e - fr) - 1)

which is equivalent to

    (is_integer(xl' + e - fl) ? xl' + e - fl - 1 : floor(xl' + e - fl)) <= i <
    (is_integer(xr' + e - fr) ? xr' + e - fr - 1 : floor(xr' + e - fr))

which is equivalent to

    (is_integer(xl') && e == fl ? xl' - 1 : floor(xl' + e - fl)) <= i <
    (is_integer(xr') && e == fr ? xr' - 1 : floor(xr' + e - fr))

Note that e != fl ==> floor(xl' + e - fl) == floor(xl')  due to e - fl < LeastSignificantBit(xl') ;
          e == fl ==> floor(xl' + e - fl) == floor(xl')  due to e - fl == 0;

thus the condition is is equivalent to

    (is_integer(xl') && e == fl ? xl' - 1 : floor(xl')) <= i <
    (is_integer(xr') && e == fr ? xr' - 1 : floor(xr'))

It is computed with the macro 'rational_floor'.

*/

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)
{
    const fixed ymin = fixed_pixround(ybot) + fixed_half;
    const fixed ymax = fixed_pixround(ytop);

    if (ymin >= ymax)
	return 0;		/* no scan lines to sample */
    {
	int iy = fixed2int_var(ymin);
	const int iy1 = fixed2int_var(ymax);
	trap_line l, r;
	register int rxl, rxr;
	int ry;
	const fixed
	    x0l = left->start.x, x1l = left->end.x, x0r = right->start.x,
	    x1r = right->end.x, dxl = x1l - x0l, dxr = x1r - x0r;
	const fixed	/* partial pixel offset to first line to sample */
	    ysl = ymin - left->start.y, ysr = ymin - right->start.y;
	fixed fxl;
	int code;
#	if CONTIGUOUS_FILL
	    const bool peak0 = ((flags & 1) != 0);
	    const bool peak1 = ((flags & 2) != 0);
	    int peak_y0 = ybot + fixed_half;
	    int peak_y1 = ytop - fixed_half;
#	endif
#	if LINEAR_COLOR
	    int num_components = dev->color_info.num_components;
	    frac31 lgc[GX_DEVICE_COLOR_MAX_COMPONENTS];
	    int32_t lgf[GX_DEVICE_COLOR_MAX_COMPONENTS];
	    int32_t lgnum[GX_DEVICE_COLOR_MAX_COMPONENTS];
	    frac31 rgc[GX_DEVICE_COLOR_MAX_COMPONENTS];
	    int32_t rgf[GX_DEVICE_COLOR_MAX_COMPONENTS];
	    int32_t rgnum[GX_DEVICE_COLOR_MAX_COMPONENTS];
	    frac31 xgc[GX_DEVICE_COLOR_MAX_COMPONENTS];
	    int32_t xgf[GX_DEVICE_COLOR_MAX_COMPONENTS];
	    int32_t xgnum[GX_DEVICE_COLOR_MAX_COMPONENTS];
	    trap_gradient lg, rg, xg;
#	else
	    gx_color_index cindex = pdevc->colors.pure;
	    dev_proc_fill_rectangle((*fill_rect)) =
		dev_proc(dev, fill_rectangle);
#	endif

	if_debug2('z', "[z]y=[%d,%d]\n", iy, iy1);

	l.h = left->end.y - left->start.y;
	r.h = right->end.y - right->start.y;
	l.x = x0l + (fixed_half - fixed_epsilon);
	r.x = x0r + (fixed_half - fixed_epsilon);
	ry = iy;

/*
 * Free variables of FILL_TRAP_RECT:
 *	SWAP_AXES, pdevc, dev, fa
 * Free variables of FILL_TRAP_RECT_DIRECT:
 *	SWAP_AXES, fill_rect, dev, cindex
 */
#define FILL_TRAP_RECT_INDIRECT(x,y,w,h)\
  (SWAP_AXES ? gx_fill_rectangle_device_rop(y, x, h, w, pdevc, dev, fa) :\
   gx_fill_rectangle_device_rop(x, y, w, h, pdevc, dev, fa))
#define FILL_TRAP_RECT_DIRECT(x,y,w,h)\
  (SWAP_AXES ? (*fill_rect)(dev, y, x, h, w, cindex) :\
   (*fill_rect)(dev, x, y, w, h, cindex))

#if LINEAR_COLOR
#   define FILL_TRAP_RECT(x,y,w,h)\
	(!(w) ? 0 : dev_proc(dev, fill_linear_color_scanline)(dev, fa, x, y, w, xg.c, xg.f, xg.num, xg.den))
#else
#   define FILL_TRAP_RECT(x,y,w,h)\
	(FILL_DIRECT ? FILL_TRAP_RECT_DIRECT(x,y,w,h) : FILL_TRAP_RECT_INDIRECT(x,y,w,h))
#endif

#define VD_RECT_SWAPPED(rxl, ry, rxr, iy)\
    vd_rect(int2fixed(SWAP_AXES ? ry : rxl), int2fixed(SWAP_AXES ? rxl : ry),\
            int2fixed(SWAP_AXES ? iy : rxr), int2fixed(SWAP_AXES ? rxr : iy),\
	    1, VD_RECT_COLOR);

	/* Compute the dx/dy ratios. */

	/*
	 * Compute the x offsets at the first scan line to sample.  We need
	 * to be careful in computing ys# * dx#f {/,%} h# because the
	 * multiplication may overflow.  We know that all the quantities
	 * involved are non-negative, and that ys# is usually less than 1 (as
	 * a fixed, of course); this gives us a cheap conservative check for
	 * overflow in the multiplication.
	 */
#define YMULT_QUO(ys, tl)\
  (ys < fixed_1 && tl.df < YMULT_LIMIT ? ys * tl.df / tl.h :\
   fixed_mult_quo(ys, tl.df, tl.h))

#if CONTIGUOUS_FILL
/*
 * If left and right boundary round to same pixel index,
 * we would not paing the scan and would get a dropout.
 * Check for this case and choose one of two pixels
 * which is closer to the "axis". We need to exclude
 * 'peak' because it would paint an excessive pixel.
 */
#define SET_MINIMAL_WIDTH(ixl, ixr, l, r) \
    if (ixl == ixr) \
	if ((!peak0 || iy >= peak_y0) && (!peak1 || iy <= peak_y1)) {\
	    fixed x = int2fixed(ixl) + fixed_half;\
	    if (x - l.x < r.x - x)\
		++ixr;\
	    else\
		--ixl;\
	}

#define CONNECT_RECTANGLES(ixl, ixr, rxl, rxr, iy, ry, adj1, adj2, fill)\
    if (adj1 < adj2) {\
	if (iy - ry > 1) {\
	    VD_RECT_SWAPPED(rxl, ry, rxr, iy - 1);\
	    code = fill(rxl, ry, rxr - rxl, iy - ry - 1);\
	    if (code < 0)\
		goto xit;\
	    ry = iy - 1;\
	}\
	adj1 = adj2 = (adj2 + adj2) / 2;\
    }

#else
#define SET_MINIMAL_WIDTH(ixl, ixr, l, r) DO_NOTHING
#define CONNECT_RECTANGLES(ixl, ixr, rxl, rxr, iy, ry, adj1, adj2, fill) DO_NOTHING
#endif
	if (fixed_floor(l.x) == fixed_pixround(x1l)) {
	    /* Left edge is vertical, we don't need to increment. */
	    l.di = 0, l.df = 0;
	    fxl = 0;
	} else {
	    compute_dx(&l, dxl, ysl);
	    fxl = YMULT_QUO(ysl, l);
	    l.x += fxl;
	}
	if (fixed_floor(r.x) == fixed_pixround(x1r)) {
	    /* Right edge is vertical.  If both are vertical, */
	    /* we have a rectangle. */
#	    if !LINEAR_COLOR
		if (l.di == 0 && l.df == 0) {
		    rxl = fixed2int_var(l.x);
		    rxr = fixed2int_var(r.x);
		    SET_MINIMAL_WIDTH(rxl, rxr, l, r);
		    VD_RECT_SWAPPED(rxl, ry, rxr, iy1);
		    code = FILL_TRAP_RECT(rxl, ry, rxr - rxl, iy1 - ry);
		    goto xit;
		}
#	    endif
	    r.di = 0, r.df = 0;
	}
	/*
	 * The test for fxl != 0 is required because the right edge might
	 * cross some pixel centers even if the left edge doesn't.
	 */
	else if (dxr == dxl && fxl != 0) {
	    if (l.di == 0)
		r.di = 0, r.df = l.df;
	    else
		compute_dx(&r, dxr, ysr);
	    if (ysr == ysl && r.h == l.h)
		r.x += fxl;
	    else
		r.x += YMULT_QUO(ysr, r);
	} else {
	    compute_dx(&r, dxr, ysr);
	    r.x += YMULT_QUO(ysr, r);
	}
	/* Compute one line's worth of dx/dy. */
	compute_ldx(&l, ysl);
	compute_ldx(&r, ysr);
	/* We subtracted fixed_epsilon from l.x, r.x to simplify rounding
	   when the rational part is zero. Now add it back to get xl', xr' */
	l.x += fixed_epsilon;
	r.x += fixed_epsilon;
#	if LINEAR_COLOR
#	    ifdef DEBUG
		if (check_gradient_overflow(left, right, num_components)) {
		    /* The caller must care of. 
		       Checking it here looses some performance with triangles. */
		    return_error(gs_error_unregistered);
		}
#	    endif
	    lg.c = lgc;
	    lg.f = lgf;
	    lg.num = lgnum;
	    rg.c = rgc;
	    rg.f = rgf;
	    rg.num = rgnum;
	    xg.c = xgc;
	    xg.f = xgf;
	    xg.num = xgnum;
	    code = init_gradient(&lg, fa, left, right, &l, ymin, num_components);
	    if (code < 0)
		return code;
	    code = init_gradient(&rg, fa, right, left, &r, ymin, num_components);
	    if (code < 0)
		return code;

#	endif

#define rational_floor(tl)\
  fixed2int_var(fixed_is_int(tl.x) && tl.xf == -tl.h ? tl.x - fixed_1 : tl.x)
#define STEP_LINE(ix, tl)\
  tl.x += tl.ldi;\
  if ( (tl.xf += tl.ldf) >= 0 ) tl.xf -= tl.h, tl.x++;\
  ix = rational_floor(tl)

	rxl = rational_floor(l);
	rxr = rational_floor(r);
	SET_MINIMAL_WIDTH(rxl, rxr, l, r);
	while (LINEAR_COLOR ? 1 : ++iy != iy1) {
#	    if LINEAR_COLOR
		if (rxl != rxr) {
		    code = set_x_gradient(&xg, &lg, &rg, &l, &r, rxl, rxr, num_components);
		    if (code < 0)
			goto xit;
		    /*VD_RECT_SWAPPED(rxl, iy, rxr, iy + 1);*/
		    code = FILL_TRAP_RECT(rxl, iy, rxr - rxl, 1);
		    if (code < 0)
			goto xit;
		}
		if (++iy == iy1)
		    break;
		STEP_LINE(rxl, l);
		STEP_LINE(rxr, r);
		step_gradient(&lg, num_components);
		step_gradient(&rg, num_components);
#	    else
		register int ixl, ixr;

		STEP_LINE(ixl, l);
		STEP_LINE(ixr, r);
		SET_MINIMAL_WIDTH(ixl, ixr, l, r);
		if (ixl != rxl || ixr != rxr) {
		    CONNECT_RECTANGLES(ixl, ixr, rxl, rxr, iy, ry, rxr, ixl, FILL_TRAP_RECT);
		    CONNECT_RECTANGLES(ixl, ixr, rxl, rxr, iy, ry, ixr, rxl, FILL_TRAP_RECT);
		    VD_RECT_SWAPPED(rxl, ry, rxr, iy);
		    code = FILL_TRAP_RECT(rxl, ry, rxr - rxl, iy - ry);
		    if (code < 0)
			goto xit;
		    rxl = ixl, rxr = ixr, ry = iy;
		}
#	    endif
	}
#	if !LINEAR_COLOR
	    VD_RECT_SWAPPED(rxl, ry, rxr, iy);
	    code = FILL_TRAP_RECT(rxl, ry, rxr - rxl, iy - ry);
#	else
	    code = 0;
#	endif
#undef STEP_LINE
#undef SET_MINIMAL_WIDTH
#undef CONNECT_RECTANGLES
#undef FILL_TRAP_RECT
#undef FILL_TRAP_RECT_DIRECT
#undef FILL_TRAP_RECT_INRECT
#undef YMULT_QUO
#undef VD_RECT_SWAPPED
xit:	if (code < 0 && FILL_DIRECT)
	    return_error(code);
	return_if_interrupt(dev->memory);
	return code;
    }
}

#undef GX_FILL_TRAPEZOID
#undef CONTIGUOUS_FILL
#undef SWAP_AXES
#undef FLAGS_TYPE