1/*********************************************************** 2 3Copyright 1987, 1998 The Open Group 4 5Permission to use, copy, modify, distribute, and sell this software and its 6documentation for any purpose is hereby granted without fee, provided that 7the above copyright notice appear in all copies and that both that 8copyright notice and this permission notice appear in supporting 9documentation. 10 11The above copyright notice and this permission notice shall be included in 12all copies or substantial portions of the Software. 13 14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 17OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN 18AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 19CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 20 21Except as contained in this notice, the name of The Open Group shall not be 22used in advertising or otherwise to promote the sale, use or other dealings 23in this Software without prior written authorization from The Open Group. 24 25Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts. 26 27 All Rights Reserved 28 29Permission to use, copy, modify, and distribute this software and its 30documentation for any purpose and without fee is hereby granted, 31provided that the above copyright notice appear in all copies and that 32both that copyright notice and this permission notice appear in 33supporting documentation, and that the name of Digital not be 34used in advertising or publicity pertaining to distribution of the 35software without specific, written prior permission. 36 37DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING 38ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL 39DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR 40ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, 41WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, 42ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS 43SOFTWARE. 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 62The 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 80At the start of the line, we have taken 0 X steps and 0 Y steps, 81so 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 89At the end of the line, we have taken dx X steps and dy Y steps, 90so 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 99Thus, the error term is the same at the start and end of the line. 100 101Let us consider clipping an X coordinate. There are 4 cases which 102represent the two independent cases of clipping the start vs. the 103end of the line and an X major vs. a Y major line. In any of these 104cases, we know the number of X steps (M) and we wish to find the 105number of Y steps (N). Thus, we will solve our error term equation. 106If we are clipping the start of the line, we will find the smallest 107N that satisfies our error term inequality. If we are clipping the 108end of the line, we will find the largest number of Y steps that 109satisfies the inequality. In that case, since we are representing 110the Y steps as (dy - N), we will actually want to solve for the 111smallest N in that equation. 112 113Case 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 120Since we are trying to find the smallest N that satisfies these 121equations, 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 127Case 1b: X major, ending X coordinate moved to M steps 128 129Same derivations as Case 1, but we want the largest N that satisfies 130the equations, so we use the <= inequality: 131 132 N = floor((2Mdy + dx - B) / 2dx) 133 134Case 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 143Since we are trying to find the highest number of Y steps that 144satisfies these equations, we need to find the smallest N, so 145we 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 151Case 2b: X major, starting X coordinate moved to M steps from end 152 153Same derivations as Case 2, but we want the smallest number of Y 154steps, 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 161Case 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 168Since we are trying to find the smallest N that satisfies these 169equations, 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 175Case 3b: Y major, ending X coordinate moved to M steps 176 177Same derivations as Case 3, but we want the largest N that satisfies 178the 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 185Case 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 194Since we are trying to find the highest number of Y steps that 195satisfies these equations, we need to find the smallest N, so 196we should use the > inequality to find the smallest: 197 198 N = floor((2Mdy - dy - B) / 2dx) + 1 199 200Case 4b: Y major, starting X coordinate moved to M steps from end 201 202Same analysis as Case 4, but we want the smallest number of Y steps 203which means the largest N, so we use the <= inequality: 204 205 N = floor((2Mdy + dy - B) / 2dx) 206 207Now let's try the Y coordinates, we have the same 4 cases. 208 209Case 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 216Since 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 222Case 5b: X major, ending Y coordinate moved to N steps 223 224Same derivations as Case 5, but we want the largest M that satisfies 225the 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 232Case 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 241Largest # of X steps means smallest M, so use the > inequality: 242 243 M = floor((2Ndx - dx - B) / 2dy) + 1 244 245Case 6b: X major, starting Y coordinate moved to N steps from end 246 247Same derivations as Case 6, but we want the smallest # of X steps 248which means the largest M, so use the <= inequality: 249 250 M = floor((2Ndx + dx - B) / 2dy) 251 252Case 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 259To 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 265Case 7b: Y major, ending Y coordinate moved to N steps 266 267Same derivations as Case 7, but we want the largest M that satisfies 268the equations, so use the <= inequality: 269 270 M = floor((2Ndx + dy - B) / 2dy) 271 272Case 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 281To 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 287Case 8b: Y major, starting Y coordinate moved to N steps from the end 288 289Same derivations as Case 8, but we want to find the smallest # of X 290steps 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 297So, 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 319We 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 325The floor in all of the above equations can be accomplished with a 326simple C divide operation provided that both numerator and denominator 327are positive. 328 329Since dx,dy >= 0 and since moving an X coordinate implies that dx != 0 330and moving a Y coordinate implies dy != 0, we know that the denominators 331are all > 0. 332 333For all lines, (-B) and (B-1) are both either 0 or -1, depending on the 334bias. Thus, we have to show that the 2MNdxy +/- dxy terms are all >= 1 335or > 0 to prove that the numerators are positive (or zero). 336 337For X Major lines we know that dx > 0 and since 2Mdy is >= 0 due to the 338constraints, the first four equations all have numerators >= 0. 339 340For the second four equations, M > 0, so 2Mdy >= 2dy so (2Mdy - dy) >= dy 341So (2Mdy - dy) > 0, since they are Y major lines. Also, (2Mdy + dy) >= 3dy 342or (2Mdy + dy) > 0. So all of their numerators are >= 0. 343 344For 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 347For the fourth set of equations, dy > 0 and 2Ndx >= 0, so all numerators 348are > 0. 349 350To consider overflow, consider the case of 2 * M,N * dx,dy + dx,dy. This 351is 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 355Since the (-B) and (B-1) terms are all 0 or -1, the maximum value of 356the numerator is therefore (2^32 - 1), which does not overflow an unsigned 35732 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 */ 406int 407miZeroClipLine(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} 615