| 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 | } |