1 /***********************************************************
3 Copyright 1987, 1998 The Open Group
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
11 The above copyright notice and this permission notice shall be included in
12 all copies or substantial portions of the Software.
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.
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.
25 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
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.
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
45 ******************************************************************/
46 #ifdef HAVE_DIX_CONFIG_H
47 #include <dix-config.h>
53 #include "scrnintstr.h"
55 #include "windowstr.h"
62 The bresenham error equation used in the mi/mfb/cfb line routines is:
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
73 e = 2Mdy - 2Ndx - dx - B
77 e = 2Ndx - 2Mdy - dy - B
80 At the start of the line, we have taken 0 X steps and 0 Y steps,
83 X major e = 2Mdy - 2Ndx - dx - B
86 Y major e = 2Ndx - 2Mdy - dy - B
89 At the end of the line, we have taken dx X steps and dy Y steps,
92 X major e = 2Mdy - 2Ndx - dx - B
93 = 2dxdy - 2dydx - dx - B
95 Y major e = 2Ndx - 2Mdy - dy - B
96 = 2dydx - 2dxdy - dy - B
99 Thus, the error term is the same at the start and end of the line.
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.
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
120 Since we are trying to find the smallest N that satisfies these
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
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:
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
168 Since we are trying to find the smallest N that satisfies these
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
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:
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)
207 Now let's try the Y coordinates, we have the same 4 cases.
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)
297 So, our equations are:
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)
319 We have the following constraints on all of the above terms:
321 0 < M,N <= 2^15 2^15 can be imposed by miZeroClipLine
322 0 <= dx/dy <= 2^16 - 1
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
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
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).
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.
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.
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.
347 For the fourth set of equations, dy > 0 and 2Ndx >= 0, so all numerators
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
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
361 /* Bit codes for the terms of the 16 clipping equations defined below. */
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)
378 /* Bit masks defining the 16 equations used in miZeroClipLine. */
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)
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)
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)
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)
402 * returns: 1 for partially clipped line
403 * -1 for completely clipped line
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
)
418 int x1_orig
, y1_orig
, x2_orig
, y2_orig
;
420 int negslope
= 0, anchorval
= 0;
421 unsigned int eqn
= 0;
423 x1
= x1_orig
= *new_x1
;
424 y1
= y1_orig
= *new_y1
;
425 x2
= x2_orig
= *new_x2
;
426 y2
= y2_orig
= *new_y2
;
431 xmajor
= IsXMajorOctant(octant
);
432 bias
= ((bias
>> octant
) & 1);
435 if ((oc1
& oc2
) != 0) { /* trivial reject */
441 else if ((oc1
| oc2
) == 0) { /* trivial accept */
444 SWAPINT_PAIR(x1
, y1
, x2
, y2
);
445 SWAPINT(clip1
, clip2
);
449 else { /* have to clip */
451 /* only clip one point at a time */
453 SWAPINT_PAIR(x1
, y1
, x2
, y2
);
454 SWAPINT_PAIR(x1_orig
, y1_orig
, x2_orig
, y2_orig
);
456 SWAPINT(clip1
, clip2
);
461 if (oc1
& OUT_LEFT
) {
462 negslope
= IsYDecreasingOctant(octant
);
463 utmp
= xmin
- x1_orig
;
464 if (utmp
<= 32767) { /* clip based on near endpt */
466 eqn
= (swapped
) ? EQN2
: EQN1
;
468 eqn
= (swapped
) ? EQN4
: EQN3
;
471 else { /* clip based on far endpt */
473 utmp
= x2_orig
- xmin
;
475 eqn
= (swapped
) ? EQN1B
: EQN2B
;
477 eqn
= (swapped
) ? EQN3B
: EQN4B
;
479 negslope
= !negslope
;
483 else if (oc1
& OUT_ABOVE
) {
484 negslope
= IsXDecreasingOctant(octant
);
485 utmp
= ymin
- y1_orig
;
486 if (utmp
<= 32767) { /* clip based on near endpt */
488 eqn
= (swapped
) ? EQN6
: EQN5
;
490 eqn
= (swapped
) ? EQN8
: EQN7
;
493 else { /* clip based on far endpt */
495 utmp
= y2_orig
- ymin
;
497 eqn
= (swapped
) ? EQN5B
: EQN6B
;
499 eqn
= (swapped
) ? EQN7B
: EQN8B
;
501 negslope
= !negslope
;
505 else if (oc1
& OUT_RIGHT
) {
506 negslope
= IsYDecreasingOctant(octant
);
507 utmp
= x1_orig
- xmax
;
508 if (utmp
<= 32767) { /* clip based on near endpt */
510 eqn
= (swapped
) ? EQN2
: EQN1
;
512 eqn
= (swapped
) ? EQN4
: EQN3
;
515 else { /* clip based on far endpt */
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.
524 utmp
= xmax
- x2_orig
;
526 eqn
= (swapped
) ? EQN1B
: EQN2B
;
528 eqn
= (swapped
) ? EQN3B
: EQN4B
;
530 negslope
= !negslope
;
534 else if (oc1
& OUT_BELOW
) {
535 negslope
= IsXDecreasingOctant(octant
);
536 utmp
= y1_orig
- ymax
;
537 if (utmp
<= 32767) { /* clip based on near endpt */
539 eqn
= (swapped
) ? EQN6
: EQN5
;
541 eqn
= (swapped
) ? EQN8
: EQN7
;
544 else { /* clip based on far endpt */
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.
553 utmp
= ymax
- y2_orig
;
555 eqn
= (swapped
) ? EQN5B
: EQN6B
;
557 eqn
= (swapped
) ? EQN7B
: EQN8B
;
559 negslope
= !negslope
;
565 negslope
= !negslope
;
567 utmp
<<= 1; /* utmp = 2N or 2M */
570 else /* (eqn & T_2MDY) */
573 if (eqn
& T_SUBDXORY
)
577 else /* (eqn & T_DYNOTX) */ if (eqn
& T_SUBDXORY
)
581 if (eqn
& T_BIASSUBONE
)
583 else /* (eqn & T_SUBBIAS) */
587 else /* (eqn & T_DIV2DY) */
595 if (eqn
& T_2NDX
) /* We are calculating X steps */
596 x1
= anchorval
+ utmp
;
597 else /* else, Y steps */
598 y1
= anchorval
+ utmp
;
601 MIOUTCODES(oc1
, x1
, y1
, xmin
, ymin
, xmax
, ymax
);
610 *pt1_clipped
= clip1
;
611 *pt2_clipped
= clip2
;