/src/ghostpdl/base/gxfillts.h
Line | Count | Source (jump to first uncovered line) |
1 | | /* Copyright (C) 2001-2023 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., 39 Mesa Street, Suite 108A, San Francisco, |
13 | | CA 94129, USA, for further information. |
14 | | */ |
15 | | |
16 | | |
17 | | /* Configurable algorithm for filling a slanted trapezoid. */ |
18 | | |
19 | | /* |
20 | | * Since we need several statically defined variants of this agorithm, |
21 | | * we store it in .h file and include it several times into gxfill.c . |
22 | | * Configuration macros (template arguments) are : |
23 | | * |
24 | | * FILL_DIRECT - See LOOP_FILL_RECTANGLE_DIRECT. |
25 | | * TEMPLATE_slant_into_trapezoids - the name of the procedure to generate. |
26 | | * TRY_TO_EXTEND_TRAP - whether we do some extra maths to see if we can |
27 | | * extend a trapezoid to reduce the total number produced. |
28 | | */ |
29 | | |
30 | | #if defined(LOOP_FILL_RECTANGLE_DIRECT) && defined(TEMPLATE_slant_into_trapezoids) && defined(TRY_TO_EXTEND_TRAP) |
31 | | |
32 | | static inline int |
33 | | TEMPLATE_slant_into_trapezoids (const line_list *ll, |
34 | | const active_line *flp, const active_line *alp, fixed y, fixed y1) |
35 | 0 | { |
36 | | /* |
37 | | * We want to get the effect of filling an area whose |
38 | | * outline is formed by dragging a square of side adj2 |
39 | | * along the border of the trapezoid. This is *not* |
40 | | * equivalent to simply expanding the corners by |
41 | | * adjust: There are 3 cases needing different |
42 | | * algorithms, plus rectangles as a fast special case. |
43 | | */ |
44 | 0 | const fill_options * const fo = ll->fo; |
45 | 0 | gs_fixed_edge le, re; |
46 | 0 | int code = 0; |
47 | | /* |
48 | | * Define a faster test for |
49 | | * fixed2int_pixround(y - below) != fixed2int_pixround(y + above) |
50 | | * where we know |
51 | | * 0 <= below <= _fixed_pixround_v, |
52 | | * 0 <= above <= min(fixed_half, fixed_1 - below). |
53 | | * Subtracting out the integer parts, this is equivalent to |
54 | | * fixed2int_pixround(fixed_fraction(y) - below) != |
55 | | * fixed2int_pixround(fixed_fraction(y) + above) |
56 | | * or to |
57 | | * fixed2int(fixed_fraction(y) + _fixed_pixround_v - below) != |
58 | | * fixed2int(fixed_fraction(y) + _fixed_pixround_v + above) |
59 | | * Letting A = _fixed_pixround_v - below and B = _fixed_pixround_v + above, |
60 | | * we can rewrite this as |
61 | | * fixed2int(fixed_fraction(y) + A) != fixed2int(fixed_fraction(y) + B) |
62 | | * Because of the range constraints given above, this is true precisely when |
63 | | * fixed_fraction(y) + A < fixed_1 && fixed_fraction(y) + B >= fixed_1 |
64 | | * or equivalently |
65 | | * fixed_fraction(y + B) < B - A. |
66 | | * i.e. |
67 | | * fixed_fraction(y + _fixed_pixround_v + above) < below + above |
68 | | */ |
69 | 0 | fixed y_span_delta = _fixed_pixround_v + fo->adjust_above; |
70 | 0 | fixed y_span_limit = fo->adjust_below + fo->adjust_above; |
71 | 0 | le.start.x = flp->start.x - fo->adjust_left; |
72 | 0 | le.end.x = flp->end.x - fo->adjust_left; |
73 | 0 | re.start.x = alp->start.x + fo->adjust_right; |
74 | 0 | re.end.x = alp->end.x + fo->adjust_right; |
75 | |
|
76 | 0 | #define ADJUSTED_Y_SPANS_PIXEL(y)\ |
77 | 0 | (fixed_fraction((y) + y_span_delta) < y_span_limit) |
78 | |
|
79 | 0 | if ((le.end.x == le.start.x) && (re.end.x == re.start.x)) { |
80 | | /* Rectangle. */ |
81 | 0 | le.start.x = fixed2int_pixround(le.start.x); |
82 | 0 | le.start.y = fixed2int_pixround(y - fo->adjust_below); |
83 | 0 | re.start.x = fixed2int_pixround(re.start.x); |
84 | 0 | re.start.y = fixed2int_pixround(y1 + fo->adjust_above); |
85 | 0 | return LOOP_FILL_RECTANGLE_DIRECT(fo, le.start.x, le.start.y, |
86 | 0 | re.start.x-le.start.x, re.start.y-le.start.y); |
87 | 0 | } else if ((le.end.x <= le.start.x) && (re.end.x >= re.start.x)) { |
88 | | /* Top wider than bottom. */ |
89 | 0 | le.start.y = flp->start.y - fo->adjust_below; |
90 | 0 | le.end.y = flp->end.y - fo->adjust_below; |
91 | 0 | re.start.y = alp->start.y - fo->adjust_below; |
92 | 0 | re.end.y = alp->end.y - fo->adjust_below; |
93 | |
|
94 | 0 | if (ADJUSTED_Y_SPANS_PIXEL(y1)) { |
95 | | /* Strictly speaking the area we want to fill is a rectangle sat |
96 | | * atop a trapezoid. For some platforms, it would be cheaper to |
97 | | * just emit a single trap if we can get away with it. */ |
98 | 0 | int xli = fixed2int_var_pixround(flp->x_next - fo->adjust_left); |
99 | 0 | int xri = fixed2int_var_pixround(alp->x_next + fo->adjust_right); |
100 | |
|
101 | 0 | if (TRY_TO_EXTEND_TRAP) { |
102 | 0 | int newxl, newxr; |
103 | | |
104 | | /* Find the two X extents at the new top position */ |
105 | 0 | newxl = le.start.x - (fixed) |
106 | 0 | (((int64_t)(le.start.x-le.end.x))* |
107 | 0 | ((int64_t)(y1 + fo->adjust_above-le.start.y))+ |
108 | 0 | (le.end.y-le.start.y-1))/(le.end.y-le.start.y); |
109 | 0 | newxr = re.start.x + (fixed) |
110 | 0 | (((int64_t)(re.end.x-re.start.x))* |
111 | 0 | ((int64_t)(y1 + fo->adjust_above-re.start.y))+ |
112 | 0 | (re.end.y-re.start.y-1))/(re.end.y-re.start.y); |
113 | | |
114 | | /* If extending the trap covers the same pixels as the |
115 | | * rectangle would have done, then just plot it! */ |
116 | 0 | if ((fixed2int_var_pixround(newxl) == xli) && |
117 | 0 | (fixed2int_var_pixround(newxr) == xri)) { |
118 | 0 | gs_fixed_edge newle, newre; |
119 | |
|
120 | 0 | newle.start.x = le.start.x; |
121 | 0 | newle.start.y = le.start.y; |
122 | 0 | newle.end.x = le.end.x; |
123 | 0 | newle.end.y = le.end.y; |
124 | 0 | while (newle.end.y < y1 + fo->adjust_above) { |
125 | 0 | newle.end.x -= le.start.x-le.end.x; |
126 | 0 | newle.end.y += le.end.y-le.start.y; |
127 | 0 | } |
128 | |
|
129 | 0 | newre.start.x = re.start.x; |
130 | 0 | newre.start.y = re.start.y; |
131 | 0 | newre.end.x = re.end.x; |
132 | 0 | newre.end.y = re.end.y; |
133 | 0 | while (newre.end.y < y1 + fo->adjust_above) { |
134 | 0 | newre.end.x += re.end.x-re.start.x; |
135 | 0 | newre.end.y += re.end.y-re.start.y; |
136 | 0 | } |
137 | |
|
138 | 0 | return loop_fill_trap_np(ll, &newle, &newre, |
139 | 0 | y - fo->adjust_below, y1 + fo->adjust_above); |
140 | 0 | } |
141 | 0 | } |
142 | | /* Otherwise we'll emit the rectangle and then the trap */ |
143 | 0 | INCR(afill); |
144 | 0 | code = LOOP_FILL_RECTANGLE_DIRECT(fo, |
145 | 0 | xli, fixed2int_pixround(y1 - fo->adjust_below), |
146 | 0 | xri - xli, 1); |
147 | 0 | if (code < 0) |
148 | 0 | return code; |
149 | 0 | } |
150 | 0 | return loop_fill_trap_np(ll, &le, &re, y - fo->adjust_below, y1 - fo->adjust_below); |
151 | 0 | } else if ((le.end.x >= le.start.x) && (re.end.x <= re.start.x)) { |
152 | | /* Bottom wider than top. */ |
153 | 0 | le.start.y = flp->start.y + fo->adjust_above; |
154 | 0 | le.end.y = flp->end.y + fo->adjust_above; |
155 | 0 | re.start.y = alp->start.y + fo->adjust_above; |
156 | 0 | re.end.y = alp->end.y + fo->adjust_above; |
157 | |
|
158 | 0 | if (ADJUSTED_Y_SPANS_PIXEL(y)) { |
159 | | /* Strictly speaking the area we want to fill is a trapezoid sat |
160 | | * atop a rectangle. For some platforms, it would be cheaper to |
161 | | * just emit a single trap if we can get away with it. */ |
162 | 0 | int xli = fixed2int_var_pixround(flp->x_current - fo->adjust_left); |
163 | 0 | int xri = fixed2int_var_pixround(alp->x_current + fo->adjust_right); |
164 | |
|
165 | 0 | if (TRY_TO_EXTEND_TRAP) { |
166 | 0 | int newxl, newxr; |
167 | | |
168 | | /* Find the two X extents at the new bottom position */ |
169 | 0 | newxl = le.end.x - (fixed) |
170 | 0 | (((int64_t)(le.end.x-le.start.x))* |
171 | 0 | ((int64_t)(le.end.y-(y - fo->adjust_below)))+ |
172 | 0 | (le.end.y-le.start.y+1))/(le.end.y-le.start.y); |
173 | 0 | newxr = re.end.x + (fixed) |
174 | 0 | (((int64_t)(re.start.x-re.end.x))* |
175 | 0 | ((int64_t)(re.end.y-(y - fo->adjust_below)))+ |
176 | 0 | (re.end.y-re.start.y+1))/(re.end.y-re.start.y); |
177 | | |
178 | | /* If extending the trap covers the same pixels as the |
179 | | * rectangle would have done, then just plot it! */ |
180 | 0 | if ((fixed2int_var_pixround(newxl) == xli) && |
181 | 0 | (fixed2int_var_pixround(newxr) == xri)) { |
182 | 0 | gs_fixed_edge newle, newre; |
183 | |
|
184 | 0 | newle.start.x = le.start.x; |
185 | 0 | newle.start.y = le.start.y; |
186 | 0 | newle.end.x = le.end.x; |
187 | 0 | newle.end.y = le.end.y; |
188 | 0 | while (newle.start.y > y - fo->adjust_below) { |
189 | 0 | newle.start.x -= le.end.x-le.start.x; |
190 | 0 | newle.start.y -= le.end.y-le.start.y; |
191 | 0 | } |
192 | |
|
193 | 0 | newre.start.x = re.start.x; |
194 | 0 | newre.start.y = re.start.y; |
195 | 0 | newre.end.x = re.end.x; |
196 | 0 | newre.end.y = re.end.y; |
197 | 0 | while (newre.start.y > y - fo->adjust_below) { |
198 | 0 | newre.start.x += re.start.x-re.end.x; |
199 | 0 | newre.start.y -= re.end.y-re.start.y; |
200 | 0 | } |
201 | |
|
202 | 0 | return loop_fill_trap_np(ll, &newle, &newre, |
203 | 0 | y - fo->adjust_below, y1 + fo->adjust_above); |
204 | 0 | } |
205 | 0 | } |
206 | | /* Otherwise we'll emit the rectangle and then the trap */ |
207 | 0 | INCR(afill); |
208 | 0 | code = LOOP_FILL_RECTANGLE_DIRECT(fo, |
209 | 0 | xli, fixed2int_pixround(y - fo->adjust_below), |
210 | 0 | xri - xli, 1); |
211 | 0 | if (code < 0) |
212 | 0 | return code; |
213 | 0 | } |
214 | 0 | return loop_fill_trap_np(ll, &le, &re, y + fo->adjust_above, y1 + fo->adjust_above); |
215 | 0 | } |
216 | | /* Otherwise, handle it as a slanted trapezoid. */ |
217 | 0 | return fill_slant_adjust(ll, flp, alp, y, y1); |
218 | 0 | } Unexecuted instantiation: gxfill.c:slant_into_trapezoids__fd Unexecuted instantiation: gxfill.c:slant_into_trapezoids__nd |
219 | | |
220 | | #else |
221 | | int dummy; |
222 | | #endif |