mizerclip.c (21883B)
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 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 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 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 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 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 }