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
|
/* Copyright (C) 2002 artofcode LLC. 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 the license contained in the file LICENSE in this distribution.
For more information about licensing, please refer to
http://www.ghostscript.com/licensing/. For information on
commercial licensing, go to http://www.artifex.com/licensing/ or
contact Artifex Software, Inc., 101 Lucas Valley Road #110,
San Rafael, CA 94903, U.S.A., +1(415)492-9861.
*/
/* $Id$ */
/* 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.
*/
/*
* 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.
*/
GX_FILL_TRAPEZOID(gx_device * dev, const gs_fixed_edge * left,
const gs_fixed_edge * right, fixed ybot, fixed ytop, int flags,
const gx_device_color * pdevc, gs_logical_operation_t lop)
{
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
gx_color_index cindex = pdevc->colors.pure;
dev_proc_fill_rectangle((*fill_rect)) =
dev_proc(dev, fill_rectangle);
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, lop
* 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, lop) :\
gx_fill_rectangle_device_rop(x, y, w, h, pdevc, dev, lop))
#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))
#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))
#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
/*
* It's worth checking for dxl == dxr, since this is the case
* for parallelograms (including stroked lines).
* Also check for left or right vertical edges.
*/
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 (l.di == 0 && l.df == 0) {
rxl = fixed2int_var(l.x);
rxr = fixed2int_var(r.x);
SET_MINIMAL_WIDTH(rxl, rxr, l, r);
code = FILL_TRAP_RECT(rxl, ry, rxr - rxl, iy1 - ry);
goto xit;
}
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);
if (dxr == dxl && ysr == ysl && r.h == l.h)
r.ldi = l.ldi, r.ldf = l.ldf, r.xf = l.xf;
else
compute_ldx(&r, ysr);
rxl = fixed2int_var(l.x);
rxr = fixed2int_var(r.x);
#define STEP_LINE(ix, tl)\
tl.x += tl.ldi;\
if ( (tl.xf += tl.ldf) >= 0 ) tl.xf -= tl.h, tl.x++;\
ix = fixed2int_var(tl.x)
SET_MINIMAL_WIDTH(rxl, rxr, l, r);
while (++iy != iy1) {
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;
}
}
VD_RECT_SWAPPED(rxl, ry, rxr, iy);
code = FILL_TRAP_RECT(rxl, ry, rxr - rxl, iy - ry);
#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();
return code;
}
}
#undef GX_FILL_TRAPEZOID
#undef CONTIGUOUS_FILL
#undef SWAP_AXES
#undef FLAGS_TYPE
|
