J. Duke | 319a3b9 | 2007-12-01 00:00:00 +0000 | [diff] [blame^] | 1 | /* |
| 2 | * Copyright 2000-2001 Sun Microsystems, Inc. All Rights Reserved. |
| 3 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| 4 | * |
| 5 | * This code is free software; you can redistribute it and/or modify it |
| 6 | * under the terms of the GNU General Public License version 2 only, as |
| 7 | * published by the Free Software Foundation. Sun designates this |
| 8 | * particular file as subject to the "Classpath" exception as provided |
| 9 | * by Sun in the LICENSE file that accompanied this code. |
| 10 | * |
| 11 | * This code is distributed in the hope that it will be useful, but WITHOUT |
| 12 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| 13 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| 14 | * version 2 for more details (a copy is included in the LICENSE file that |
| 15 | * accompanied this code). |
| 16 | * |
| 17 | * You should have received a copy of the GNU General Public License version |
| 18 | * 2 along with this work; if not, write to the Free Software Foundation, |
| 19 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| 20 | * |
| 21 | * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
| 22 | * CA 95054 USA or visit www.sun.com if you need additional information or |
| 23 | * have any questions. |
| 24 | */ |
| 25 | |
| 26 | #include "GraphicsPrimitiveMgr.h" |
| 27 | |
| 28 | #include "LineUtils.h" |
| 29 | |
| 30 | #include "sun_java2d_loops_DrawLine.h" |
| 31 | |
| 32 | #define OUTCODE_TOP 1 |
| 33 | #define OUTCODE_BOTTOM 2 |
| 34 | #define OUTCODE_LEFT 4 |
| 35 | #define OUTCODE_RIGHT 8 |
| 36 | |
| 37 | static void |
| 38 | RefineBounds(SurfaceDataBounds *bounds, jint x1, jint y1, jint x2, jint y2) |
| 39 | { |
| 40 | jint min, max; |
| 41 | if (x1 < x2) { |
| 42 | min = x1; |
| 43 | max = x2; |
| 44 | } else { |
| 45 | min = x2; |
| 46 | max = x1; |
| 47 | } |
| 48 | max++; |
| 49 | if (max <= min) { |
| 50 | /* integer overflow */ |
| 51 | max--; |
| 52 | } |
| 53 | if (bounds->x1 < min) bounds->x1 = min; |
| 54 | if (bounds->x2 > max) bounds->x2 = max; |
| 55 | if (y1 < y2) { |
| 56 | min = y1; |
| 57 | max = y2; |
| 58 | } else { |
| 59 | min = y2; |
| 60 | max = y1; |
| 61 | } |
| 62 | max++; |
| 63 | if (max <= min) { |
| 64 | /* integer overflow */ |
| 65 | max--; |
| 66 | } |
| 67 | if (bounds->y1 < min) bounds->y1 = min; |
| 68 | if (bounds->y2 > max) bounds->y2 = max; |
| 69 | } |
| 70 | |
| 71 | #define _out(v, vmin, vmax, cmin, cmax) \ |
| 72 | ((v < vmin) ? cmin : ((v > vmax) ? cmax : 0)) |
| 73 | |
| 74 | #define outcode(x, y, xmin, ymin, xmax, ymax) \ |
| 75 | (_out(y, ymin, ymax, OUTCODE_TOP, OUTCODE_BOTTOM) | \ |
| 76 | _out(x, xmin, xmax, OUTCODE_LEFT, OUTCODE_RIGHT)) |
| 77 | |
| 78 | /* |
| 79 | * "Small" math here will be done if the coordinates are less |
| 80 | * than 15 bits in range (-16384 => 16383). This could be |
| 81 | * expanded to 16 bits if we rearrange some of the math in |
| 82 | * the normal version of SetupBresenham. |
| 83 | * "Big" math here will be done with coordinates with 30 bits |
| 84 | * of total range - 2 bits less than a jint holds. |
| 85 | * Intermediate calculations for "Big" coordinates will be |
| 86 | * done using jlong variables. |
| 87 | */ |
| 88 | #define OverflowsSmall(v) ((v) != (((v) << 17) >> 17)) |
| 89 | #define OverflowsBig(v) ((v) != (((v) << 2) >> 2)) |
| 90 | #define BIG_MAX ((1 << 29) - 1) |
| 91 | #define BIG_MIN (-(1 << 29)) |
| 92 | |
| 93 | #define SETUP_BRESENHAM(CALC_TYPE, ORIGX1, ORIGY1, ORIGX2, ORIGY2, SHORTEN) \ |
| 94 | do { \ |
| 95 | jint X1 = ORIGX1, Y1 = ORIGY1, X2 = ORIGX2, Y2 = ORIGY2; \ |
| 96 | jint dx, dy, ax, ay; \ |
| 97 | jint cxmin, cymin, cxmax, cymax; \ |
| 98 | jint outcode1, outcode2; \ |
| 99 | jboolean xmajor; \ |
| 100 | jint errminor, errmajor; \ |
| 101 | jint error; \ |
| 102 | jint steps; \ |
| 103 | \ |
| 104 | dx = X2 - X1; \ |
| 105 | dy = Y2 - Y1; \ |
| 106 | ax = (dx < 0) ? -dx : dx; \ |
| 107 | ay = (dy < 0) ? -dy : dy; \ |
| 108 | \ |
| 109 | cxmin = pBounds->x1; \ |
| 110 | cymin = pBounds->y1; \ |
| 111 | cxmax = pBounds->x2 - 1; \ |
| 112 | cymax = pBounds->y2 - 1; \ |
| 113 | xmajor = (ax >= ay); \ |
| 114 | \ |
| 115 | outcode1 = outcode(X1, Y1, cxmin, cymin, cxmax, cymax); \ |
| 116 | outcode2 = outcode(X2, Y2, cxmin, cymin, cxmax, cymax); \ |
| 117 | while ((outcode1 | outcode2) != 0) { \ |
| 118 | CALC_TYPE xsteps, ysteps; \ |
| 119 | if ((outcode1 & outcode2) != 0) { \ |
| 120 | return JNI_FALSE; \ |
| 121 | } \ |
| 122 | if (outcode1 != 0) { \ |
| 123 | if (outcode1 & (OUTCODE_TOP | OUTCODE_BOTTOM)) { \ |
| 124 | if (outcode1 & OUTCODE_TOP) { \ |
| 125 | Y1 = cymin; \ |
| 126 | } else { \ |
| 127 | Y1 = cymax; \ |
| 128 | } \ |
| 129 | ysteps = Y1 - ORIGY1; \ |
| 130 | if (ysteps < 0) { \ |
| 131 | ysteps = -ysteps; \ |
| 132 | } \ |
| 133 | xsteps = 2 * ysteps * ax + ay; \ |
| 134 | if (xmajor) { \ |
| 135 | xsteps += ay - ax - 1; \ |
| 136 | } \ |
| 137 | xsteps = xsteps / (2 * ay); \ |
| 138 | if (dx < 0) { \ |
| 139 | xsteps = -xsteps; \ |
| 140 | } \ |
| 141 | X1 = ORIGX1 + (jint) xsteps; \ |
| 142 | } else if (outcode1 & (OUTCODE_LEFT | OUTCODE_RIGHT)) { \ |
| 143 | if (outcode1 & OUTCODE_LEFT) { \ |
| 144 | X1 = cxmin; \ |
| 145 | } else { \ |
| 146 | X1 = cxmax; \ |
| 147 | } \ |
| 148 | xsteps = X1 - ORIGX1; \ |
| 149 | if (xsteps < 0) { \ |
| 150 | xsteps = -xsteps; \ |
| 151 | } \ |
| 152 | ysteps = 2 * xsteps * ay + ax; \ |
| 153 | if (!xmajor) { \ |
| 154 | ysteps += ax - ay - 1; \ |
| 155 | } \ |
| 156 | ysteps = ysteps / (2 * ax); \ |
| 157 | if (dy < 0) { \ |
| 158 | ysteps = -ysteps; \ |
| 159 | } \ |
| 160 | Y1 = ORIGY1 + (jint) ysteps; \ |
| 161 | } \ |
| 162 | outcode1 = outcode(X1, Y1, cxmin, cymin, cxmax, cymax); \ |
| 163 | } else { \ |
| 164 | if (outcode2 & (OUTCODE_TOP | OUTCODE_BOTTOM)) { \ |
| 165 | if (outcode2 & OUTCODE_TOP) { \ |
| 166 | Y2 = cymin; \ |
| 167 | } else { \ |
| 168 | Y2 = cymax; \ |
| 169 | } \ |
| 170 | ysteps = Y2 - ORIGY2; \ |
| 171 | if (ysteps < 0) { \ |
| 172 | ysteps = -ysteps; \ |
| 173 | } \ |
| 174 | xsteps = 2 * ysteps * ax + ay; \ |
| 175 | if (xmajor) { \ |
| 176 | xsteps += ay - ax; \ |
| 177 | } else { \ |
| 178 | xsteps -= 1; \ |
| 179 | } \ |
| 180 | xsteps = xsteps / (2 * ay); \ |
| 181 | if (dx > 0) { \ |
| 182 | xsteps = -xsteps; \ |
| 183 | } \ |
| 184 | X2 = ORIGX2 + (jint) xsteps; \ |
| 185 | } else if (outcode2 & (OUTCODE_LEFT | OUTCODE_RIGHT)) { \ |
| 186 | if (outcode2 & OUTCODE_LEFT) { \ |
| 187 | X2 = cxmin; \ |
| 188 | } else { \ |
| 189 | X2 = cxmax; \ |
| 190 | } \ |
| 191 | xsteps = X2 - ORIGX2; \ |
| 192 | if (xsteps < 0) { \ |
| 193 | xsteps = -xsteps; \ |
| 194 | } \ |
| 195 | ysteps = 2 * xsteps * ay + ax; \ |
| 196 | if (xmajor) { \ |
| 197 | ysteps -= 1; \ |
| 198 | } else { \ |
| 199 | ysteps += ax - ay; \ |
| 200 | } \ |
| 201 | ysteps = ysteps / (2 * ax); \ |
| 202 | if (dy > 0) { \ |
| 203 | ysteps = -ysteps; \ |
| 204 | } \ |
| 205 | Y2 = ORIGY2 + (jint) ysteps; \ |
| 206 | } \ |
| 207 | outcode2 = outcode(X2, Y2, cxmin, cymin, cxmax, cymax); \ |
| 208 | } \ |
| 209 | } \ |
| 210 | *pStartX = X1; \ |
| 211 | *pStartY = Y1; \ |
| 212 | \ |
| 213 | if (xmajor) { \ |
| 214 | errmajor = ay * 2; \ |
| 215 | errminor = ax * 2; \ |
| 216 | *pBumpMajorMask = (dx < 0) ? BUMP_NEG_PIXEL : BUMP_POS_PIXEL; \ |
| 217 | *pBumpMinorMask = (dy < 0) ? BUMP_NEG_SCAN : BUMP_POS_SCAN; \ |
| 218 | ax = -ax; /* For clipping adjustment below */ \ |
| 219 | steps = X2 - X1; \ |
| 220 | if (X2 != ORIGX2) { \ |
| 221 | SHORTEN = 0; \ |
| 222 | } \ |
| 223 | } else { \ |
| 224 | errmajor = ax * 2; \ |
| 225 | errminor = ay * 2; \ |
| 226 | *pBumpMajorMask = (dy < 0) ? BUMP_NEG_SCAN : BUMP_POS_SCAN; \ |
| 227 | *pBumpMinorMask = (dx < 0) ? BUMP_NEG_PIXEL : BUMP_POS_PIXEL; \ |
| 228 | ay = -ay; /* For clipping adjustment below */ \ |
| 229 | steps = Y2 - Y1; \ |
| 230 | if (Y2 != ORIGY2) { \ |
| 231 | SHORTEN = 0; \ |
| 232 | } \ |
| 233 | } \ |
| 234 | if ((steps = ((steps >= 0) ? steps : -steps) + 1 - SHORTEN) == 0) { \ |
| 235 | return JNI_FALSE; \ |
| 236 | } \ |
| 237 | error = - (errminor / 2); \ |
| 238 | if (Y1 != ORIGY1) { \ |
| 239 | jint ysteps = Y1 - ORIGY1; \ |
| 240 | if (ysteps < 0) { \ |
| 241 | ysteps = -ysteps; \ |
| 242 | } \ |
| 243 | error += ysteps * ax * 2; \ |
| 244 | } \ |
| 245 | if (X1 != ORIGX1) { \ |
| 246 | jint xsteps = X1 - ORIGX1; \ |
| 247 | if (xsteps < 0) { \ |
| 248 | xsteps = -xsteps; \ |
| 249 | } \ |
| 250 | error += xsteps * ay * 2; \ |
| 251 | } \ |
| 252 | error += errmajor; \ |
| 253 | errminor -= errmajor; \ |
| 254 | \ |
| 255 | *pSteps = steps; \ |
| 256 | *pError = error; \ |
| 257 | *pErrMajor = errmajor; \ |
| 258 | *pErrMinor = errminor; \ |
| 259 | } while (0) |
| 260 | |
| 261 | static jboolean |
| 262 | LineUtils_SetupBresenhamBig(jint _x1, jint _y1, jint _x2, jint _y2, |
| 263 | jint shorten, |
| 264 | SurfaceDataBounds *pBounds, |
| 265 | jint *pStartX, jint *pStartY, |
| 266 | jint *pSteps, jint *pError, |
| 267 | jint *pErrMajor, jint *pBumpMajorMask, |
| 268 | jint *pErrMinor, jint *pBumpMinorMask) |
| 269 | { |
| 270 | /* |
| 271 | * Part of calculating the Bresenham parameters for line stepping |
| 272 | * involves being able to store numbers that are twice the magnitude |
| 273 | * of the biggest absolute difference in coordinates. Since we |
| 274 | * want the stepping parameters to be stored in jints, we then need |
| 275 | * to avoid any absolute differences more than 30 bits. Thus, we |
| 276 | * need to preprocess the coordinates to reduce their range to 30 |
| 277 | * bits regardless of clipping. We need to cut their range back |
| 278 | * before we do the clipping because the Bresenham stepping values |
| 279 | * need to be calculated based on the "unclipped" coordinates. |
| 280 | * |
| 281 | * Thus, first we perform a "pre-clipping" stage to bring the |
| 282 | * coordinates within the 30-bit range and then we proceed to the |
| 283 | * regular clipping procedure, pretending that these were the |
| 284 | * original coordinates all along. Since this operation occurs |
| 285 | * based on a constant "pre-clip" rectangle of +/- 30 bits without |
| 286 | * any consideration for the final clip, the rounding errors that |
| 287 | * occur here will depend only on the line coordinates and be |
| 288 | * invariant with respect to the particular device/user clip |
| 289 | * rectangles in effect at the time. Thus, rendering a given |
| 290 | * large-range line will be consistent under a variety of |
| 291 | * clipping conditions. |
| 292 | */ |
| 293 | if (OverflowsBig(_x1) || OverflowsBig(_y1) || |
| 294 | OverflowsBig(_x2) || OverflowsBig(_y2)) |
| 295 | { |
| 296 | /* |
| 297 | * Use doubles to get us into range for "Big" arithmetic. |
| 298 | * |
| 299 | * The math of adjusting an endpoint for clipping can involve |
| 300 | * an intermediate result with twice the number of bits as the |
| 301 | * original coordinate range. Since we want to maintain as |
| 302 | * much as 30 bits of precision in the resulting coordinates, |
| 303 | * we will get roundoff here even using IEEE double-precision |
| 304 | * arithmetic which cannot carry 60 bits of mantissa. Since |
| 305 | * the rounding errors will be consistent for a given set |
| 306 | * of input coordinates the potential roundoff error should |
| 307 | * not affect the consistency of our rendering. |
| 308 | */ |
| 309 | double X1d = _x1; |
| 310 | double Y1d = _y1; |
| 311 | double X2d = _x2; |
| 312 | double Y2d = _y2; |
| 313 | double DXd = X2d - X1d; |
| 314 | double DYd = Y2d - Y1d; |
| 315 | if (_x1 < BIG_MIN) { |
| 316 | Y1d = _y1 + (BIG_MIN - _x1) * DYd / DXd; |
| 317 | X1d = BIG_MIN; |
| 318 | } else if (_x1 > BIG_MAX) { |
| 319 | Y1d = _y1 - (_x1 - BIG_MAX) * DYd / DXd; |
| 320 | X1d = BIG_MAX; |
| 321 | } |
| 322 | /* Use Y1d instead of _y1 for testing now as we may have modified it */ |
| 323 | if (Y1d < BIG_MIN) { |
| 324 | X1d = _x1 + (BIG_MIN - _y1) * DXd / DYd; |
| 325 | Y1d = BIG_MIN; |
| 326 | } else if (Y1d > BIG_MAX) { |
| 327 | X1d = _x1 - (_y1 - BIG_MAX) * DXd / DYd; |
| 328 | Y1d = BIG_MAX; |
| 329 | } |
| 330 | if (_x2 < BIG_MIN) { |
| 331 | Y2d = _y2 + (BIG_MIN - _x2) * DYd / DXd; |
| 332 | X2d = BIG_MIN; |
| 333 | } else if (_x2 > BIG_MAX) { |
| 334 | Y2d = _y2 - (_x2 - BIG_MAX) * DYd / DXd; |
| 335 | X2d = BIG_MAX; |
| 336 | } |
| 337 | /* Use Y2d instead of _y2 for testing now as we may have modified it */ |
| 338 | if (Y2d < BIG_MIN) { |
| 339 | X2d = _x2 + (BIG_MIN - _y2) * DXd / DYd; |
| 340 | Y2d = BIG_MIN; |
| 341 | } else if (Y2d > BIG_MAX) { |
| 342 | X2d = _x2 - (_y2 - BIG_MAX) * DXd / DYd; |
| 343 | Y2d = BIG_MAX; |
| 344 | } |
| 345 | _x1 = (int) X1d; |
| 346 | _y1 = (int) Y1d; |
| 347 | _x2 = (int) X2d; |
| 348 | _y2 = (int) Y2d; |
| 349 | } |
| 350 | |
| 351 | SETUP_BRESENHAM(jlong, _x1, _y1, _x2, _y2, shorten); |
| 352 | |
| 353 | return JNI_TRUE; |
| 354 | } |
| 355 | |
| 356 | jboolean |
| 357 | LineUtils_SetupBresenham(jint _x1, jint _y1, jint _x2, jint _y2, |
| 358 | jint shorten, |
| 359 | SurfaceDataBounds *pBounds, |
| 360 | jint *pStartX, jint *pStartY, |
| 361 | jint *pSteps, jint *pError, |
| 362 | jint *pErrMajor, jint *pBumpMajorMask, |
| 363 | jint *pErrMinor, jint *pBumpMinorMask) |
| 364 | { |
| 365 | if (OverflowsSmall(_x1) || OverflowsSmall(_y1) || |
| 366 | OverflowsSmall(_x2) || OverflowsSmall(_y2)) |
| 367 | { |
| 368 | return LineUtils_SetupBresenhamBig(_x1, _y1, _x2, _y2, shorten, |
| 369 | pBounds, |
| 370 | pStartX, pStartY, |
| 371 | pSteps, pError, |
| 372 | pErrMajor, pBumpMajorMask, |
| 373 | pErrMinor, pBumpMinorMask); |
| 374 | } |
| 375 | |
| 376 | SETUP_BRESENHAM(jint, _x1, _y1, _x2, _y2, shorten); |
| 377 | |
| 378 | return JNI_TRUE; |
| 379 | } |
| 380 | |
| 381 | /* |
| 382 | * Class: sun_java2d_loops_DrawLine |
| 383 | * Method: DrawLine |
| 384 | * Signature: (Lsun/java2d/SunGraphics2D;Lsun/java2d/SurfaceData;IIII)V |
| 385 | */ |
| 386 | JNIEXPORT void JNICALL |
| 387 | Java_sun_java2d_loops_DrawLine_DrawLine |
| 388 | (JNIEnv *env, jobject self, |
| 389 | jobject sg2d, jobject sData, |
| 390 | jint x1, jint y1, jint x2, jint y2) |
| 391 | { |
| 392 | SurfaceDataOps *sdOps; |
| 393 | SurfaceDataRasInfo rasInfo; |
| 394 | NativePrimitive *pPrim; |
| 395 | CompositeInfo compInfo; |
| 396 | jint pixel = GrPrim_Sg2dGetPixel(env, sg2d); |
| 397 | |
| 398 | pPrim = GetNativePrim(env, self); |
| 399 | if (pPrim == NULL) { |
| 400 | return; |
| 401 | } |
| 402 | if (pPrim->pCompType->getCompInfo != NULL) { |
| 403 | GrPrim_Sg2dGetCompInfo(env, sg2d, pPrim, &compInfo); |
| 404 | } |
| 405 | |
| 406 | sdOps = SurfaceData_GetOps(env, sData); |
| 407 | if (sdOps == 0) { |
| 408 | return; |
| 409 | } |
| 410 | |
| 411 | GrPrim_Sg2dGetClip(env, sg2d, &rasInfo.bounds); |
| 412 | |
| 413 | RefineBounds(&rasInfo.bounds, x1, y1, x2, y2); |
| 414 | |
| 415 | if (sdOps->Lock(env, sdOps, &rasInfo, pPrim->dstflags) != SD_SUCCESS) { |
| 416 | return; |
| 417 | } |
| 418 | |
| 419 | if (rasInfo.bounds.x2 > rasInfo.bounds.x1 && |
| 420 | rasInfo.bounds.y2 > rasInfo.bounds.y1) |
| 421 | { |
| 422 | sdOps->GetRasInfo(env, sdOps, &rasInfo); |
| 423 | if (rasInfo.rasBase) { |
| 424 | LineUtils_ProcessLine(&rasInfo, pixel, |
| 425 | pPrim->funcs.drawline, pPrim, &compInfo, |
| 426 | x1, y1, x2, y2, 0); |
| 427 | } |
| 428 | SurfaceData_InvokeRelease(env, sdOps, &rasInfo); |
| 429 | } |
| 430 | SurfaceData_InvokeUnlock(env, sdOps, &rasInfo); |
| 431 | } |