Commit | Line | Data |
---|---|---|
a09e091a JB |
1 | /*********************************************************** |
2 | ||
3 | Copyright 1987, 1998 The Open Group | |
4 | ||
5 | Permission to use, copy, modify, distribute, and sell this software and its | |
6 | documentation for any purpose is hereby granted without fee, provided that | |
7 | the above copyright notice appear in all copies and that both that | |
8 | copyright notice and this permission notice appear in supporting | |
9 | documentation. | |
10 | ||
11 | The above copyright notice and this permission notice shall be included in | |
12 | all copies or substantial portions of the Software. | |
13 | ||
14 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
15 | IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
16 | FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE | |
17 | OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN | |
18 | AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN | |
19 | CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. | |
20 | ||
21 | Except as contained in this notice, the name of The Open Group shall not be | |
22 | used in advertising or otherwise to promote the sale, use or other dealings | |
23 | in this Software without prior written authorization from The Open Group. | |
24 | ||
25 | Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts. | |
26 | ||
27 | All Rights Reserved | |
28 | ||
29 | Permission to use, copy, modify, and distribute this software and its | |
30 | documentation for any purpose and without fee is hereby granted, | |
31 | provided that the above copyright notice appear in all copies and that | |
32 | both that copyright notice and this permission notice appear in | |
33 | supporting documentation, and that the name of Digital not be | |
34 | used in advertising or publicity pertaining to distribution of the | |
35 | software without specific, written prior permission. | |
36 | ||
37 | DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING | |
38 | ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL | |
39 | DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR | |
40 | ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, | |
41 | WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, | |
42 | ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS | |
43 | SOFTWARE. | |
44 | ||
45 | ******************************************************************/ | |
46 | #ifdef HAVE_DIX_CONFIG_H | |
47 | #include <dix-config.h> | |
48 | #endif | |
49 | ||
50 | #include <X11/X.h> | |
51 | ||
52 | #include "misc.h" | |
53 | #include "scrnintstr.h" | |
54 | #include "gcstruct.h" | |
55 | #include "windowstr.h" | |
56 | #include "pixmap.h" | |
57 | #include "mi.h" | |
58 | #include "miline.h" | |
59 | ||
60 | /* | |
61 | ||
62 | The bresenham error equation used in the mi/mfb/cfb line routines is: | |
63 | ||
64 | e = error | |
65 | dx = difference in raw X coordinates | |
66 | dy = difference in raw Y coordinates | |
67 | M = # of steps in X direction | |
68 | N = # of steps in Y direction | |
69 | B = 0 to prefer diagonal steps in a given octant, | |
70 | 1 to prefer axial steps in a given octant | |
71 | ||
72 | For X major lines: | |
73 | e = 2Mdy - 2Ndx - dx - B | |
74 | -2dx <= e < 0 | |
75 | ||
76 | For Y major lines: | |
77 | e = 2Ndx - 2Mdy - dy - B | |
78 | -2dy <= e < 0 | |
79 | ||
80 | At the start of the line, we have taken 0 X steps and 0 Y steps, | |
81 | so M = 0 and N = 0: | |
82 | ||
83 | X major e = 2Mdy - 2Ndx - dx - B | |
84 | = -dx - B | |
85 | ||
86 | Y major e = 2Ndx - 2Mdy - dy - B | |
87 | = -dy - B | |
88 | ||
89 | At the end of the line, we have taken dx X steps and dy Y steps, | |
90 | so M = dx and N = dy: | |
91 | ||
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 | |
98 | ||
99 | Thus, the error term is the same at the start and end of the line. | |
100 | ||
101 | Let us consider clipping an X coordinate. There are 4 cases which | |
102 | represent the two independent cases of clipping the start vs. the | |
103 | end of the line and an X major vs. a Y major line. In any of these | |
104 | cases, we know the number of X steps (M) and we wish to find the | |
105 | number of Y steps (N). Thus, we will solve our error term equation. | |
106 | If we are clipping the start of the line, we will find the smallest | |
107 | N that satisfies our error term inequality. If we are clipping the | |
108 | end of the line, we will find the largest number of Y steps that | |
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 | |
111 | smallest N in that equation. | |
112 | \f | |
113 | Case 1: X major, starting X coordinate moved by M steps | |
114 | ||
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 | |
119 | ||
120 | Since we are trying to find the smallest N that satisfies these | |
121 | equations, we should use the > inequality to find the smallest: | |
122 | ||
123 | N = floor((2Mdy - dx - B) / 2dx) + 1 | |
124 | = floor((2Mdy - dx - B + 2dx) / 2dx) | |
125 | = floor((2Mdy + dx - B) / 2dx) | |
126 | ||
127 | Case 1b: X major, ending X coordinate moved to M steps | |
128 | ||
129 | Same derivations as Case 1, but we want the largest N that satisfies | |
130 | the equations, so we use the <= inequality: | |
131 | ||
132 | N = floor((2Mdy + dx - B) / 2dx) | |
133 | ||
134 | Case 2: X major, ending X coordinate moved by M steps | |
135 | ||
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 | |
142 | ||
143 | Since we are trying to find the highest number of Y steps that | |
144 | satisfies these equations, we need to find the smallest N, so | |
145 | we should use the >= inequality to find the smallest: | |
146 | ||
147 | N = ceiling((2Mdy - dx + B) / 2dx) | |
148 | = floor((2Mdy - dx + B + 2dx - 1) / 2dx) | |
149 | = floor((2Mdy + dx + B - 1) / 2dx) | |
150 | ||
151 | Case 2b: X major, starting X coordinate moved to M steps from end | |
152 | ||
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: | |
155 | ||
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) | |
160 | \f | |
161 | Case 3: Y major, starting X coordinate moved by M steps | |
162 | ||
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 | |
167 | ||
168 | Since we are trying to find the smallest N that satisfies these | |
169 | equations, we should use the >= inequality to find the smallest: | |
170 | ||
171 | N = ceiling((2Mdy - dy + B) / 2dx) | |
172 | = floor((2Mdy - dy + B + 2dx - 1) / 2dx) | |
173 | = floor((2Mdy - dy + B - 1) / 2dx) + 1 | |
174 | ||
175 | Case 3b: Y major, ending X coordinate moved to M steps | |
176 | ||
177 | Same derivations as Case 3, but we want the largest N that satisfies | |
178 | the equations, so we use the < inequality: | |
179 | ||
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) | |
184 | ||
185 | Case 4: Y major, ending X coordinate moved by M steps | |
186 | ||
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 | |
193 | ||
194 | Since we are trying to find the highest number of Y steps that | |
195 | satisfies these equations, we need to find the smallest N, so | |
196 | we should use the > inequality to find the smallest: | |
197 | ||
198 | N = floor((2Mdy - dy - B) / 2dx) + 1 | |
199 | ||
200 | Case 4b: Y major, starting X coordinate moved to M steps from end | |
201 | ||
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: | |
204 | ||
205 | N = floor((2Mdy + dy - B) / 2dx) | |
206 | \f | |
207 | Now let's try the Y coordinates, we have the same 4 cases. | |
208 | ||
209 | Case 5: X major, starting Y coordinate moved by N steps | |
210 | ||
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 | |
215 | ||
216 | Since we are trying to find the smallest M, we use the >= inequality: | |
217 | ||
218 | M = ceiling((2Ndx - dx + B) / 2dy) | |
219 | = floor((2Ndx - dx + B + 2dy - 1) / 2dy) | |
220 | = floor((2Ndx - dx + B - 1) / 2dy) + 1 | |
221 | ||
222 | Case 5b: X major, ending Y coordinate moved to N steps | |
223 | ||
224 | Same derivations as Case 5, but we want the largest M that satisfies | |
225 | the equations, so we use the < inequality: | |
226 | ||
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) | |
231 | ||
232 | Case 6: X major, ending Y coordinate moved by N steps | |
233 | ||
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 | |
240 | ||
241 | Largest # of X steps means smallest M, so use the > inequality: | |
242 | ||
243 | M = floor((2Ndx - dx - B) / 2dy) + 1 | |
244 | ||
245 | Case 6b: X major, starting Y coordinate moved to N steps from end | |
246 | ||
247 | Same derivations as Case 6, but we want the smallest # of X steps | |
248 | which means the largest M, so use the <= inequality: | |
249 | ||
250 | M = floor((2Ndx + dx - B) / 2dy) | |
251 | \f | |
252 | Case 7: Y major, starting Y coordinate moved by N steps | |
253 | ||
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 | |
258 | ||
259 | To find the smallest M, use the > inequality: | |
260 | ||
261 | M = floor((2Ndx - dy - B) / 2dy) + 1 | |
262 | = floor((2Ndx - dy - B + 2dy) / 2dy) | |
263 | = floor((2Ndx + dy - B) / 2dy) | |
264 | ||
265 | Case 7b: Y major, ending Y coordinate moved to N steps | |
266 | ||
267 | Same derivations as Case 7, but we want the largest M that satisfies | |
268 | the equations, so use the <= inequality: | |
269 | ||
270 | M = floor((2Ndx + dy - B) / 2dy) | |
271 | ||
272 | Case 8: Y major, ending Y coordinate moved by N steps | |
273 | ||
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 | |
280 | ||
281 | To find the highest X steps, find the smallest M, use the >= inequality: | |
282 | ||
283 | M = ceiling((2Ndx - dy + B) / 2dy) | |
284 | = floor((2Ndx - dy + B + 2dy - 1) / 2dy) | |
285 | = floor((2Ndx + dy + B - 1) / 2dy) | |
286 | ||
287 | Case 8b: Y major, starting Y coordinate moved to N steps from the end | |
288 | ||
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: | |
291 | ||
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) | |
296 | \f | |
297 | So, our equations are: | |
298 | ||
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) | |
303 | ||
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) | |
308 | ||
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) | |
313 | ||
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) | |
318 | ||
319 | We have the following constraints on all of the above terms: | |
320 | ||
321 | 0 < M,N <= 2^15 2^15 can be imposed by miZeroClipLine | |
322 | 0 <= dx/dy <= 2^16 - 1 | |
323 | 0 <= B <= 1 | |
324 | ||
325 | The floor in all of the above equations can be accomplished with a | |
326 | simple C divide operation provided that both numerator and denominator | |
327 | are positive. | |
328 | ||
329 | Since dx,dy >= 0 and since moving an X coordinate implies that dx != 0 | |
330 | and moving a Y coordinate implies dy != 0, we know that the denominators | |
331 | are all > 0. | |
332 | ||
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 | |
335 | or > 0 to prove that the numerators are positive (or zero). | |
336 | ||
337 | For X Major lines we know that dx > 0 and since 2Mdy is >= 0 due to the | |
338 | constraints, the first four equations all have numerators >= 0. | |
339 | ||
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 | |
342 | or (2Mdy + dy) > 0. So all of their numerators are >= 0. | |
343 | ||
344 | For the third set of four equations, N > 0, so 2Ndx >= 2dx so (2Ndx - dx) | |
345 | >= dx > 0. Similarly (2Ndx + dx) >= 3dx > 0. So all numerators >= 0. | |
346 | ||
347 | For the fourth set of equations, dy > 0 and 2Ndx >= 0, so all numerators | |
348 | are > 0. | |
349 | ||
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 | |
357 | 32 bit variable. | |
358 | ||
359 | */ | |
360 | ||
361 | /* Bit codes for the terms of the 16 clipping equations defined below. */ | |
362 | ||
363 | #define T_2NDX (1 << 0) | |
364 | #define T_2MDY (0) /* implicit term */ | |
365 | #define T_DXNOTY (1 << 1) | |
366 | #define T_DYNOTX (0) /* implicit term */ | |
367 | #define T_SUBDXORY (1 << 2) | |
368 | #define T_ADDDX (T_DXNOTY) /* composite term */ | |
369 | #define T_SUBDX (T_DXNOTY | T_SUBDXORY) /* composite term */ | |
370 | #define T_ADDDY (T_DYNOTX) /* composite term */ | |
371 | #define T_SUBDY (T_DYNOTX | T_SUBDXORY) /* composite term */ | |
372 | #define T_BIASSUBONE (1 << 3) | |
373 | #define T_SUBBIAS (0) /* implicit term */ | |
374 | #define T_DIV2DX (1 << 4) | |
375 | #define T_DIV2DY (0) /* implicit term */ | |
376 | #define T_ADDONE (1 << 5) | |
377 | ||
378 | /* Bit masks defining the 16 equations used in miZeroClipLine. */ | |
379 | ||
380 | #define EQN1 (T_2MDY | T_ADDDX | T_SUBBIAS | T_DIV2DX) | |
381 | #define EQN1B (T_2MDY | T_ADDDX | T_SUBBIAS | T_DIV2DX) | |
382 | #define EQN2 (T_2MDY | T_ADDDX | T_BIASSUBONE | T_DIV2DX) | |
383 | #define EQN2B (T_2MDY | T_ADDDX | T_BIASSUBONE | T_DIV2DX) | |
384 | ||
385 | #define EQN3 (T_2MDY | T_SUBDY | T_BIASSUBONE | T_DIV2DX | T_ADDONE) | |
386 | #define EQN3B (T_2MDY | T_ADDDY | T_BIASSUBONE | T_DIV2DX) | |
387 | #define EQN4 (T_2MDY | T_SUBDY | T_SUBBIAS | T_DIV2DX | T_ADDONE) | |
388 | #define EQN4B (T_2MDY | T_ADDDY | T_SUBBIAS | T_DIV2DX) | |
389 | ||
390 | #define EQN5 (T_2NDX | T_SUBDX | T_BIASSUBONE | T_DIV2DY | T_ADDONE) | |
391 | #define EQN5B (T_2NDX | T_ADDDX | T_BIASSUBONE | T_DIV2DY) | |
392 | #define EQN6 (T_2NDX | T_SUBDX | T_SUBBIAS | T_DIV2DY | T_ADDONE) | |
393 | #define EQN6B (T_2NDX | T_ADDDX | T_SUBBIAS | T_DIV2DY) | |
394 | ||
395 | #define EQN7 (T_2NDX | T_ADDDY | T_SUBBIAS | T_DIV2DY) | |
396 | #define EQN7B (T_2NDX | T_ADDDY | T_SUBBIAS | T_DIV2DY) | |
397 | #define EQN8 (T_2NDX | T_ADDDY | T_BIASSUBONE | T_DIV2DY) | |
398 | #define EQN8B (T_2NDX | T_ADDDY | T_BIASSUBONE | T_DIV2DY) | |
399 | ||
400 | /* miZeroClipLine | |
401 | * | |
402 | * returns: 1 for partially clipped line | |
403 | * -1 for completely clipped line | |
404 | * | |
405 | */ | |
406 | int | |
407 | miZeroClipLine(int xmin, int ymin, int xmax, int ymax, | |
408 | int *new_x1, int *new_y1, int *new_x2, int *new_y2, | |
409 | unsigned int adx, unsigned int ady, | |
410 | int *pt1_clipped, int *pt2_clipped, | |
411 | int octant, unsigned int bias, int oc1, int oc2) | |
412 | { | |
413 | int swapped = 0; | |
414 | int clipDone = 0; | |
415 | CARD32 utmp = 0; | |
416 | int clip1, clip2; | |
417 | int x1, y1, x2, y2; | |
418 | int x1_orig, y1_orig, x2_orig, y2_orig; | |
419 | int xmajor; | |
420 | int negslope = 0, anchorval = 0; | |
421 | unsigned int eqn = 0; | |
422 | ||
423 | x1 = x1_orig = *new_x1; | |
424 | y1 = y1_orig = *new_y1; | |
425 | x2 = x2_orig = *new_x2; | |
426 | y2 = y2_orig = *new_y2; | |
427 | ||
428 | clip1 = 0; | |
429 | clip2 = 0; | |
430 | ||
431 | xmajor = IsXMajorOctant(octant); | |
432 | bias = ((bias >> octant) & 1); | |
433 | ||
434 | while (1) { | |
435 | if ((oc1 & oc2) != 0) { /* trivial reject */ | |
436 | clipDone = -1; | |
437 | clip1 = oc1; | |
438 | clip2 = oc2; | |
439 | break; | |
440 | } | |
441 | else if ((oc1 | oc2) == 0) { /* trivial accept */ | |
442 | clipDone = 1; | |
443 | if (swapped) { | |
444 | SWAPINT_PAIR(x1, y1, x2, y2); | |
445 | SWAPINT(clip1, clip2); | |
446 | } | |
447 | break; | |
448 | } | |
449 | else { /* have to clip */ | |
450 | ||
451 | /* only clip one point at a time */ | |
452 | if (oc1 == 0) { | |
453 | SWAPINT_PAIR(x1, y1, x2, y2); | |
454 | SWAPINT_PAIR(x1_orig, y1_orig, x2_orig, y2_orig); | |
455 | SWAPINT(oc1, oc2); | |
456 | SWAPINT(clip1, clip2); | |
457 | swapped = !swapped; | |
458 | } | |
459 | ||
460 | clip1 |= oc1; | |
461 | if (oc1 & OUT_LEFT) { | |
462 | negslope = IsYDecreasingOctant(octant); | |
463 | utmp = xmin - x1_orig; | |
464 | if (utmp <= 32767) { /* clip based on near endpt */ | |
465 | if (xmajor) | |
466 | eqn = (swapped) ? EQN2 : EQN1; | |
467 | else | |
468 | eqn = (swapped) ? EQN4 : EQN3; | |
469 | anchorval = y1_orig; | |
470 | } | |
471 | else { /* clip based on far endpt */ | |
472 | ||
473 | utmp = x2_orig - xmin; | |
474 | if (xmajor) | |
475 | eqn = (swapped) ? EQN1B : EQN2B; | |
476 | else | |
477 | eqn = (swapped) ? EQN3B : EQN4B; | |
478 | anchorval = y2_orig; | |
479 | negslope = !negslope; | |
480 | } | |
481 | x1 = xmin; | |
482 | } | |
483 | else if (oc1 & OUT_ABOVE) { | |
484 | negslope = IsXDecreasingOctant(octant); | |
485 | utmp = ymin - y1_orig; | |
486 | if (utmp <= 32767) { /* clip based on near endpt */ | |
487 | if (xmajor) | |
488 | eqn = (swapped) ? EQN6 : EQN5; | |
489 | else | |
490 | eqn = (swapped) ? EQN8 : EQN7; | |
491 | anchorval = x1_orig; | |
492 | } | |
493 | else { /* clip based on far endpt */ | |
494 | ||
495 | utmp = y2_orig - ymin; | |
496 | if (xmajor) | |
497 | eqn = (swapped) ? EQN5B : EQN6B; | |
498 | else | |
499 | eqn = (swapped) ? EQN7B : EQN8B; | |
500 | anchorval = x2_orig; | |
501 | negslope = !negslope; | |
502 | } | |
503 | y1 = ymin; | |
504 | } | |
505 | else if (oc1 & OUT_RIGHT) { | |
506 | negslope = IsYDecreasingOctant(octant); | |
507 | utmp = x1_orig - xmax; | |
508 | if (utmp <= 32767) { /* clip based on near endpt */ | |
509 | if (xmajor) | |
510 | eqn = (swapped) ? EQN2 : EQN1; | |
511 | else | |
512 | eqn = (swapped) ? EQN4 : EQN3; | |
513 | anchorval = y1_orig; | |
514 | } | |
515 | else { /* clip based on far endpt */ | |
516 | ||
517 | /* | |
518 | * Technically since the equations can handle | |
519 | * utmp == 32768, this overflow code isn't | |
520 | * needed since X11 protocol can't generate | |
521 | * a line which goes more than 32768 pixels | |
522 | * to the right of a clip rectangle. | |
523 | */ | |
524 | utmp = xmax - x2_orig; | |
525 | if (xmajor) | |
526 | eqn = (swapped) ? EQN1B : EQN2B; | |
527 | else | |
528 | eqn = (swapped) ? EQN3B : EQN4B; | |
529 | anchorval = y2_orig; | |
530 | negslope = !negslope; | |
531 | } | |
532 | x1 = xmax; | |
533 | } | |
534 | else if (oc1 & OUT_BELOW) { | |
535 | negslope = IsXDecreasingOctant(octant); | |
536 | utmp = y1_orig - ymax; | |
537 | if (utmp <= 32767) { /* clip based on near endpt */ | |
538 | if (xmajor) | |
539 | eqn = (swapped) ? EQN6 : EQN5; | |
540 | else | |
541 | eqn = (swapped) ? EQN8 : EQN7; | |
542 | anchorval = x1_orig; | |
543 | } | |
544 | else { /* clip based on far endpt */ | |
545 | ||
546 | /* | |
547 | * Technically since the equations can handle | |
548 | * utmp == 32768, this overflow code isn't | |
549 | * needed since X11 protocol can't generate | |
550 | * a line which goes more than 32768 pixels | |
551 | * below the bottom of a clip rectangle. | |
552 | */ | |
553 | utmp = ymax - y2_orig; | |
554 | if (xmajor) | |
555 | eqn = (swapped) ? EQN5B : EQN6B; | |
556 | else | |
557 | eqn = (swapped) ? EQN7B : EQN8B; | |
558 | anchorval = x2_orig; | |
559 | negslope = !negslope; | |
560 | } | |
561 | y1 = ymax; | |
562 | } | |
563 | ||
564 | if (swapped) | |
565 | negslope = !negslope; | |
566 | ||
567 | utmp <<= 1; /* utmp = 2N or 2M */ | |
568 | if (eqn & T_2NDX) | |
569 | utmp = (utmp * adx); | |
570 | else /* (eqn & T_2MDY) */ | |
571 | utmp = (utmp * ady); | |
572 | if (eqn & T_DXNOTY) | |
573 | if (eqn & T_SUBDXORY) | |
574 | utmp -= adx; | |
575 | else | |
576 | utmp += adx; | |
577 | else /* (eqn & T_DYNOTX) */ if (eqn & T_SUBDXORY) | |
578 | utmp -= ady; | |
579 | else | |
580 | utmp += ady; | |
581 | if (eqn & T_BIASSUBONE) | |
582 | utmp += bias - 1; | |
583 | else /* (eqn & T_SUBBIAS) */ | |
584 | utmp -= bias; | |
585 | if (eqn & T_DIV2DX) | |
586 | utmp /= (adx << 1); | |
587 | else /* (eqn & T_DIV2DY) */ | |
588 | utmp /= (ady << 1); | |
589 | if (eqn & T_ADDONE) | |
590 | utmp++; | |
591 | ||
592 | if (negslope) | |
593 | utmp = -utmp; | |
594 | ||
595 | if (eqn & T_2NDX) /* We are calculating X steps */ | |
596 | x1 = anchorval + utmp; | |
597 | else /* else, Y steps */ | |
598 | y1 = anchorval + utmp; | |
599 | ||
600 | oc1 = 0; | |
601 | MIOUTCODES(oc1, x1, y1, xmin, ymin, xmax, ymax); | |
602 | } | |
603 | } | |
604 | ||
605 | *new_x1 = x1; | |
606 | *new_y1 = y1; | |
607 | *new_x2 = x2; | |
608 | *new_y2 = y2; | |
609 | ||
610 | *pt1_clipped = clip1; | |
611 | *pt2_clipped = clip2; | |
612 | ||
613 | return clipDone; | |
614 | } |