Lines Matching +full:use +full:- +full:case
5 Permission to use, copy, modify, distribute, and sell this software and its
19 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
22 used in advertising or otherwise to promote the sale, use or other dealings
29 Permission to use, copy, modify, and distribute this software and its
40 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
42 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
47 #include <dix-config.h>
73 e = 2Mdy - 2Ndx - dx - B
74 -2dx <= e < 0
77 e = 2Ndx - 2Mdy - dy - B
78 -2dy <= e < 0
83 X major e = 2Mdy - 2Ndx - dx - B
84 = -dx - B
86 Y major e = 2Ndx - 2Mdy - dy - B
87 = -dy - B
92 X major e = 2Mdy - 2Ndx - dx - B
93 = 2dxdy - 2dydx - dx - B
94 = -dx - B
95 Y major e = 2Ndx - 2Mdy - dy - B
96 = 2dydx - 2dxdy - dy - B
97 = -dy - B
109 satisfies the inequality. In that case, since we are representing
110 the Y steps as (dy - N), we will actually want to solve for the
113 Case 1: X major, starting X coordinate moved by M steps
115 -2dx <= 2Mdy - 2Ndx - dx - B < 0
116 2Ndx <= 2Mdy - dx - B + 2dx 2Ndx > 2Mdy - dx - B
117 2Ndx <= 2Mdy + dx - B N > (2Mdy - dx - B) / 2dx
118 N <= (2Mdy + dx - B) / 2dx
121 equations, we should use the > inequality to find the smallest:
123 N = floor((2Mdy - dx - B) / 2dx) + 1
124 = floor((2Mdy - dx - B + 2dx) / 2dx)
125 = floor((2Mdy + dx - B) / 2dx)
127 Case 1b: X major, ending X coordinate moved to M steps
129 Same derivations as Case 1, but we want the largest N that satisfies
130 the equations, so we use the <= inequality:
132 N = floor((2Mdy + dx - B) / 2dx)
134 Case 2: X major, ending X coordinate moved by M steps
136 -2dx <= 2(dx - M)dy - 2(dy - N)dx - dx - B < 0
137 -2dx <= 2dxdy - 2Mdy - 2dxdy + 2Ndx - dx - B < 0
138 -2dx <= 2Ndx - 2Mdy - dx - B < 0
139 2Ndx >= 2Mdy + dx + B - 2dx 2Ndx < 2Mdy + dx + B
140 2Ndx >= 2Mdy - dx + B N < (2Mdy + dx + B) / 2dx
141 N >= (2Mdy - dx + B) / 2dx
145 we should use the >= inequality to find the smallest:
147 N = ceiling((2Mdy - dx + B) / 2dx)
148 = floor((2Mdy - dx + B + 2dx - 1) / 2dx)
149 = floor((2Mdy + dx + B - 1) / 2dx)
151 Case 2b: X major, starting X coordinate moved to M steps from end
153 Same derivations as Case 2, but we want the smallest number of Y
154 steps, so we want the highest N, so we use the < inequality:
156 N = ceiling((2Mdy + dx + B) / 2dx) - 1
157 = floor((2Mdy + dx + B + 2dx - 1) / 2dx) - 1
158 = floor((2Mdy + dx + B + 2dx - 1 - 2dx) / 2dx)
159 = floor((2Mdy + dx + B - 1) / 2dx)
161 Case 3: Y major, starting X coordinate moved by M steps
163 -2dy <= 2Ndx - 2Mdy - dy - B < 0
164 2Ndx >= 2Mdy + dy + B - 2dy 2Ndx < 2Mdy + dy + B
165 2Ndx >= 2Mdy - dy + B N < (2Mdy + dy + B) / 2dx
166 N >= (2Mdy - dy + B) / 2dx
169 equations, we should use the >= inequality to find the smallest:
171 N = ceiling((2Mdy - dy + B) / 2dx)
172 = floor((2Mdy - dy + B + 2dx - 1) / 2dx)
173 = floor((2Mdy - dy + B - 1) / 2dx) + 1
175 Case 3b: Y major, ending X coordinate moved to M steps
177 Same derivations as Case 3, but we want the largest N that satisfies
178 the equations, so we use the < inequality:
180 N = ceiling((2Mdy + dy + B) / 2dx) - 1
181 = floor((2Mdy + dy + B + 2dx - 1) / 2dx) - 1
182 = floor((2Mdy + dy + B + 2dx - 1 - 2dx) / 2dx)
183 = floor((2Mdy + dy + B - 1) / 2dx)
185 Case 4: Y major, ending X coordinate moved by M steps
187 -2dy <= 2(dy - N)dx - 2(dx - M)dy - dy - B < 0
188 -2dy <= 2dxdy - 2Ndx - 2dxdy + 2Mdy - dy - B < 0
189 -2dy <= 2Mdy - 2Ndx - dy - B < 0
190 2Ndx <= 2Mdy - dy - B + 2dy 2Ndx > 2Mdy - dy - B
191 2Ndx <= 2Mdy + dy - B N > (2Mdy - dy - B) / 2dx
192 N <= (2Mdy + dy - B) / 2dx
196 we should use the > inequality to find the smallest:
198 N = floor((2Mdy - dy - B) / 2dx) + 1
200 Case 4b: Y major, starting X coordinate moved to M steps from end
202 Same analysis as Case 4, but we want the smallest number of Y steps
203 which means the largest N, so we use the <= inequality:
205 N = floor((2Mdy + dy - B) / 2dx)
209 Case 5: X major, starting Y coordinate moved by N steps
211 -2dx <= 2Mdy - 2Ndx - dx - B < 0
212 2Mdy >= 2Ndx + dx + B - 2dx 2Mdy < 2Ndx + dx + B
213 2Mdy >= 2Ndx - dx + B M < (2Ndx + dx + B) / 2dy
214 M >= (2Ndx - dx + B) / 2dy
216 Since we are trying to find the smallest M, we use the >= inequality:
218 M = ceiling((2Ndx - dx + B) / 2dy)
219 = floor((2Ndx - dx + B + 2dy - 1) / 2dy)
220 = floor((2Ndx - dx + B - 1) / 2dy) + 1
222 Case 5b: X major, ending Y coordinate moved to N steps
224 Same derivations as Case 5, but we want the largest M that satisfies
225 the equations, so we use the < inequality:
227 M = ceiling((2Ndx + dx + B) / 2dy) - 1
228 = floor((2Ndx + dx + B + 2dy - 1) / 2dy) - 1
229 = floor((2Ndx + dx + B + 2dy - 1 - 2dy) / 2dy)
230 = floor((2Ndx + dx + B - 1) / 2dy)
232 Case 6: X major, ending Y coordinate moved by N steps
234 -2dx <= 2(dx - M)dy - 2(dy - N)dx - dx - B < 0
235 -2dx <= 2dxdy - 2Mdy - 2dxdy + 2Ndx - dx - B < 0
236 -2dx <= 2Ndx - 2Mdy - dx - B < 0
237 2Mdy <= 2Ndx - dx - B + 2dx 2Mdy > 2Ndx - dx - B
238 2Mdy <= 2Ndx + dx - B M > (2Ndx - dx - B) / 2dy
239 M <= (2Ndx + dx - B) / 2dy
241 Largest # of X steps means smallest M, so use the > inequality:
243 M = floor((2Ndx - dx - B) / 2dy) + 1
245 Case 6b: X major, starting Y coordinate moved to N steps from end
247 Same derivations as Case 6, but we want the smallest # of X steps
248 which means the largest M, so use the <= inequality:
250 M = floor((2Ndx + dx - B) / 2dy)
252 Case 7: Y major, starting Y coordinate moved by N steps
254 -2dy <= 2Ndx - 2Mdy - dy - B < 0
255 2Mdy <= 2Ndx - dy - B + 2dy 2Mdy > 2Ndx - dy - B
256 2Mdy <= 2Ndx + dy - B M > (2Ndx - dy - B) / 2dy
257 M <= (2Ndx + dy - B) / 2dy
259 To find the smallest M, use the > inequality:
261 M = floor((2Ndx - dy - B) / 2dy) + 1
262 = floor((2Ndx - dy - B + 2dy) / 2dy)
263 = floor((2Ndx + dy - B) / 2dy)
265 Case 7b: Y major, ending Y coordinate moved to N steps
267 Same derivations as Case 7, but we want the largest M that satisfies
268 the equations, so use the <= inequality:
270 M = floor((2Ndx + dy - B) / 2dy)
272 Case 8: Y major, ending Y coordinate moved by N steps
274 -2dy <= 2(dy - N)dx - 2(dx - M)dy - dy - B < 0
275 -2dy <= 2dxdy - 2Ndx - 2dxdy + 2Mdy - dy - B < 0
276 -2dy <= 2Mdy - 2Ndx - dy - B < 0
277 2Mdy >= 2Ndx + dy + B - 2dy 2Mdy < 2Ndx + dy + B
278 2Mdy >= 2Ndx - dy + B M < (2Ndx + dy + B) / 2dy
279 M >= (2Ndx - dy + B) / 2dy
281 To find the highest X steps, find the smallest M, use the >= inequality:
283 M = ceiling((2Ndx - dy + B) / 2dy)
284 = floor((2Ndx - dy + B + 2dy - 1) / 2dy)
285 = floor((2Ndx + dy + B - 1) / 2dy)
287 Case 8b: Y major, starting Y coordinate moved to N steps from the end
289 Same derivations as Case 8, but we want to find the smallest # of X
290 steps which means the largest M, so we use the < inequality:
292 M = ceiling((2Ndx + dy + B) / 2dy) - 1
293 = floor((2Ndx + dy + B + 2dy - 1) / 2dy) - 1
294 = floor((2Ndx + dy + B + 2dy - 1 - 2dy) / 2dy)
295 = floor((2Ndx + dy + B - 1) / 2dy)
299 1: X major move x1 to x1+M floor((2Mdy + dx - B) / 2dx)
300 1b: X major move x2 to x1+M floor((2Mdy + dx - B) / 2dx)
301 2: X major move x2 to x2-M floor((2Mdy + dx + B - 1) / 2dx)
302 2b: X major move x1 to x2-M floor((2Mdy + dx + B - 1) / 2dx)
304 3: Y major move x1 to x1+M floor((2Mdy - dy + B - 1) / 2dx) + 1
305 3b: Y major move x2 to x1+M floor((2Mdy + dy + B - 1) / 2dx)
306 4: Y major move x2 to x2-M floor((2Mdy - dy - B) / 2dx) + 1
307 4b: Y major move x1 to x2-M floor((2Mdy + dy - B) / 2dx)
309 5: X major move y1 to y1+N floor((2Ndx - dx + B - 1) / 2dy) + 1
310 5b: X major move y2 to y1+N floor((2Ndx + dx + B - 1) / 2dy)
311 6: X major move y2 to y2-N floor((2Ndx - dx - B) / 2dy) + 1
312 6b: X major move y1 to y2-N floor((2Ndx + dx - B) / 2dy)
314 7: Y major move y1 to y1+N floor((2Ndx + dy - B) / 2dy)
315 7b: Y major move y2 to y1+N floor((2Ndx + dy - B) / 2dy)
316 8: Y major move y2 to y2-N floor((2Ndx + dy + B - 1) / 2dy)
317 8b: Y major move y1 to y2-N floor((2Ndx + dy + B - 1) / 2dy)
322 0 <= dx/dy <= 2^16 - 1
333 For all lines, (-B) and (B-1) are both either 0 or -1, depending on the
334 bias. Thus, we have to show that the 2MNdxy +/- dxy terms are all >= 1
340 For the second four equations, M > 0, so 2Mdy >= 2dy so (2Mdy - dy) >= dy
341 So (2Mdy - dy) > 0, since they are Y major lines. Also, (2Mdy + dy) >= 3dy
344 For the third set of four equations, N > 0, so 2Ndx >= 2dx so (2Ndx - dx)
350 To consider overflow, consider the case of 2 * M,N * dx,dy + dx,dy. This
351 is bounded <= 2 * 2^15 * (2^16 - 1) + (2^16 - 1)
352 <= 2^16 * (2^16 - 1) + (2^16 - 1)
353 <= 2^32 - 2^16 + 2^16 - 1
354 <= 2^32 - 1
355 Since the (-B) and (B-1) terms are all 0 or -1, the maximum value of
356 the numerator is therefore (2^32 - 1), which does not overflow an unsigned
403 * -1 for completely clipped line
436 clipDone = -1; in miZeroClipLine()
463 utmp = xmin - x1_orig; in miZeroClipLine()
473 utmp = x2_orig - xmin; in miZeroClipLine()
485 utmp = ymin - y1_orig; in miZeroClipLine()
495 utmp = y2_orig - ymin; in miZeroClipLine()
507 utmp = x1_orig - xmax; in miZeroClipLine()
524 utmp = xmax - x2_orig; in miZeroClipLine()
536 utmp = y1_orig - ymax; in miZeroClipLine()
553 utmp = ymax - y2_orig; in miZeroClipLine()
574 utmp -= adx; in miZeroClipLine()
578 utmp -= ady; in miZeroClipLine()
582 utmp += bias - 1; in miZeroClipLine()
584 utmp -= bias; in miZeroClipLine()
593 utmp = -utmp; in miZeroClipLine()