1 /* 2 * Copyright (c) 2005, 2018, Oracle and/or its affiliates. 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. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 #include <math.h> 27 #include <assert.h> 28 #include <stdlib.h> 29 #include <string.h> 30 31 #include "jni.h" 32 #include "j2d_md.h" 33 #include "java_awt_geom_PathIterator.h" 34 35 #include "ProcessPath.h" 36 37 /* 38 * This framework performs filling and drawing of paths with sub-pixel 39 * precision. Also, it performs clipping by the specified view area. 40 * 41 * Drawing of the shapes is performed not pixel by pixel but segment by segment 42 * except several pixels near endpoints of the drawn line. This approach saves 43 * lot's of cpu cycles especially in case of large primitives (like ovals with 44 * sizes more than 50) and helps in achieving appropriate visual quality. Also, 45 * such method of drawing is useful for the accelerated pipelines where 46 * overhead of the per-pixel drawing could eliminate all benefits of the 47 * hardware acceleration. 48 * 49 * Filling of the path was taken from 50 * 51 * [Graphics Gems, edited by Andrew S Glassner. Academic Press 1990, 52 * ISBN 0-12-286165-5 (Concave polygon scan conversion), 87-91] 53 * 54 * and modified to work with sub-pixel precision and non-continuous paths. 55 * It's also speeded up by using hash table by rows of the filled objects. 56 * 57 * Here is high level scheme showing the rendering process: 58 * 59 * doDrawPath doFillPath 60 * \ / 61 * ProcessPath 62 * | 63 * CheckPathSegment 64 * | 65 * --------+------ 66 * | | 67 * | | 68 * | | 69 * _->ProcessCurve | 70 * / / | | 71 * \___/ | | 72 * | | 73 * DrawCurve ProcessLine 74 * \ / 75 * \ / 76 * \ / 77 * \ / 78 * ------+------ 79 * (filling) / \ (drawing) 80 * / \ 81 * Clipping and Clipping 82 * clamping \ 83 * | \ 84 * StoreFixedLine ProcessFixedLine 85 * | / \ 86 * | / \ 87 * FillPolygon PROCESS_LINE PROCESS_POINT 88 * 89 * 90 * 91 * CheckPathSegment - rough checking and skipping path's segments in case of 92 * invalid or huge coordinates of the control points to 93 * avoid calculation problems with NaNs and values close 94 * to the FLT_MAX 95 * 96 * ProcessCurve - (ProcessQuad, ProcessCubic) Splitting the curve into 97 * monotonic parts having appropriate size (calculated as 98 * boundary box of the control points) 99 * 100 * DrawMonotonicCurve - (DrawMonotonicQuad, DrawMonotonicCubic) flattening 101 * monotonic curve using adaptive forward differencing 102 * 103 * StoreFixedLine - storing segment from the flattened path to the 104 * FillData structure. Performing clipping and clamping if 105 * necessary. 106 * 107 * PROCESS_LINE, PROCESS_POINT - Helpers for calling appropriate primitive from 108 * DrawHandler structure 109 * 110 * ProcessFixedLine - Drawing line segment with subpixel precision. 111 * 112 */ 113 114 #define PROCESS_LINE(hnd, fX0, fY0, fX1, fY1, checkBounds, pixelInfo) \ 115 do { \ 116 jint X0 = (fX0) >> MDP_PREC; \ 117 jint Y0 = (fY0) >> MDP_PREC; \ 118 jint X1 = (fX1) >> MDP_PREC; \ 119 jint Y1 = (fY1) >> MDP_PREC; \ 120 jint res; \ 121 \ 122 /* Checking bounds and clipping if necessary. \ 123 * REMIND: It's temporary solution to avoid OOB in rendering code. \ 124 * Current approach uses float equations which are unreliable for \ 125 * clipping and makes assumptions about the line biases of the \ 126 * rendering algorithm. Also, clipping code should be moved down \ 127 * into only those output renderers that need it. \ 128 */ \ 129 if (checkBounds) { \ 130 jfloat xMinf = hnd->dhnd->xMinf + 0.5f; \ 131 jfloat yMinf = hnd->dhnd->yMinf + 0.5f; \ 132 jfloat xMaxf = hnd->dhnd->xMaxf + 0.5f; \ 133 jfloat yMaxf = hnd->dhnd->yMaxf + 0.5f; \ 134 TESTANDCLIP(yMinf, yMaxf, Y0, X0, Y1, X1, jint, res); \ 135 if (res == CRES_INVISIBLE) break; \ 136 TESTANDCLIP(yMinf, yMaxf, Y1, X1, Y0, X0, jint, res); \ 137 if (res == CRES_INVISIBLE) break; \ 138 TESTANDCLIP(xMinf, xMaxf, X0, Y0, X1, Y1, jint, res); \ 139 if (res == CRES_INVISIBLE) break; \ 140 TESTANDCLIP(xMinf, xMaxf, X1, Y1, X0, Y0, jint, res); \ 141 if (res == CRES_INVISIBLE) break; \ 142 } \ 143 \ 144 /* Handling lines having just one pixel */ \ 145 if (((X0^X1) | (Y0^Y1)) == 0) { \ 146 if (pixelInfo[0] == 0) { \ 147 pixelInfo[0] = 1; \ 148 pixelInfo[1] = X0; \ 149 pixelInfo[2] = Y0; \ 150 pixelInfo[3] = X0; \ 151 pixelInfo[4] = Y0; \ 152 hnd->dhnd->pDrawPixel(hnd->dhnd, X0, Y0); \ 153 } else if ((X0 != pixelInfo[3] || Y0 != pixelInfo[4]) && \ 154 (X0 != pixelInfo[1] || Y0 != pixelInfo[2])) { \ 155 hnd->dhnd->pDrawPixel(hnd->dhnd, X0, Y0); \ 156 pixelInfo[3] = X0; \ 157 pixelInfo[4] = Y0; \ 158 } \ 159 break; \ 160 } \ 161 \ 162 if (pixelInfo[0] && \ 163 ((pixelInfo[1] == X0 && pixelInfo[2] == Y0) || \ 164 (pixelInfo[3] == X0 && pixelInfo[4] == Y0))) \ 165 { \ 166 hnd->dhnd->pDrawPixel(hnd->dhnd, X0, Y0); \ 167 } \ 168 \ 169 hnd->dhnd->pDrawLine(hnd->dhnd, X0, Y0, X1, Y1); \ 170 \ 171 if (pixelInfo[0] == 0) { \ 172 pixelInfo[0] = 1; \ 173 pixelInfo[1] = X0; \ 174 pixelInfo[2] = Y0; \ 175 pixelInfo[3] = X0; \ 176 pixelInfo[4] = Y0; \ 177 } \ 178 \ 179 /* Switch on last pixel of the line if it was already \ 180 * drawn during rendering of the previous segments \ 181 */ \ 182 if ((pixelInfo[1] == X1 && pixelInfo[2] == Y1) || \ 183 (pixelInfo[3] == X1 && pixelInfo[4] == Y1)) \ 184 { \ 185 hnd->dhnd->pDrawPixel(hnd->dhnd, X1, Y1); \ 186 } \ 187 pixelInfo[3] = X1; \ 188 pixelInfo[4] = Y1; \ 189 } while(0) 190 191 #define PROCESS_POINT(hnd, fX, fY, checkBounds, pixelInfo) \ 192 do { \ 193 jint X_ = (fX)>> MDP_PREC; \ 194 jint Y_ = (fY)>> MDP_PREC; \ 195 if (checkBounds && \ 196 (hnd->dhnd->yMin > Y_ || \ 197 hnd->dhnd->yMax <= Y_ || \ 198 hnd->dhnd->xMin > X_ || \ 199 hnd->dhnd->xMax <= X_)) break; \ 200 /* \ 201 * (X_,Y_) should be inside boundaries \ 202 * \ 203 * assert(hnd->dhnd->yMin <= Y_ && \ 204 * hnd->dhnd->yMax > Y_ && \ 205 * hnd->dhnd->xMin <= X_ && \ 206 * hnd->dhnd->xMax > X_); \ 207 * \ 208 */ \ 209 if (pixelInfo[0] == 0) { \ 210 pixelInfo[0] = 1; \ 211 pixelInfo[1] = X_; \ 212 pixelInfo[2] = Y_; \ 213 pixelInfo[3] = X_; \ 214 pixelInfo[4] = Y_; \ 215 hnd->dhnd->pDrawPixel(hnd->dhnd, X_, Y_); \ 216 } else if ((X_ != pixelInfo[3] || Y_ != pixelInfo[4]) && \ 217 (X_ != pixelInfo[1] || Y_ != pixelInfo[2])) { \ 218 hnd->dhnd->pDrawPixel(hnd->dhnd, X_, Y_); \ 219 pixelInfo[3] = X_; \ 220 pixelInfo[4] = Y_; \ 221 } \ 222 } while(0) 223 224 225 /* 226 * Constants for the forward differencing 227 * of the cubic and quad curves 228 */ 229 230 /* Maximum size of the cubic curve (calculated as the size of the bounding box 231 * of the control points) which could be rendered without splitting 232 */ 233 #define MAX_CUB_SIZE 256 234 235 /* Maximum size of the quad curve (calculated as the size of the bounding box 236 * of the control points) which could be rendered without splitting 237 */ 238 #define MAX_QUAD_SIZE 1024 239 240 /* Default power of 2 steps used in the forward differencing. Here DF prefix 241 * stands for DeFault. Constants below are used as initial values for the 242 * adaptive forward differencing algorithm. 243 */ 244 #define DF_CUB_STEPS 3 245 #define DF_QUAD_STEPS 2 246 247 /* Shift of the current point of the curve for preparing to the midpoint 248 * rounding 249 */ 250 #define DF_CUB_SHIFT (FWD_PREC + DF_CUB_STEPS*3 - MDP_PREC) 251 #define DF_QUAD_SHIFT (FWD_PREC + DF_QUAD_STEPS*2 - MDP_PREC) 252 253 /* Default amount of steps of the forward differencing */ 254 #define DF_CUB_COUNT (1<<DF_CUB_STEPS) 255 #define DF_QUAD_COUNT (1<<DF_QUAD_STEPS) 256 257 /* Default boundary constants used to check the necessity of the restepping */ 258 #define DF_CUB_DEC_BND (1<<(DF_CUB_STEPS*3 + FWD_PREC + 2)) 259 #define DF_CUB_INC_BND (1<<(DF_CUB_STEPS*3 + FWD_PREC - 1)) 260 #define DF_QUAD_DEC_BND (1<<(DF_QUAD_STEPS*2 + FWD_PREC + 2)) 261 262 /* Multiplyers for the coefficients of the polynomial form of the cubic and 263 * quad curves representation 264 */ 265 #define CUB_A_SHIFT FWD_PREC 266 #define CUB_B_SHIFT (DF_CUB_STEPS + FWD_PREC + 1) 267 #define CUB_C_SHIFT (DF_CUB_STEPS*2 + FWD_PREC) 268 269 #define CUB_A_MDP_MULT (1<<CUB_A_SHIFT) 270 #define CUB_B_MDP_MULT (1<<CUB_B_SHIFT) 271 #define CUB_C_MDP_MULT (1<<CUB_C_SHIFT) 272 273 #define QUAD_A_SHIFT FWD_PREC 274 #define QUAD_B_SHIFT (DF_QUAD_STEPS + FWD_PREC) 275 276 #define QUAD_A_MDP_MULT (1<<QUAD_A_SHIFT) 277 #define QUAD_B_MDP_MULT (1<<QUAD_B_SHIFT) 278 279 #define CALC_MAX(MAX, X) ((MAX)=((X)>(MAX))?(X):(MAX)) 280 #define CALC_MIN(MIN, X) ((MIN)=((X)<(MIN))?(X):(MIN)) 281 #define MAX(MAX, X) (((X)>(MAX))?(X):(MAX)) 282 #define MIN(MIN, X) (((X)<(MIN))?(X):(MIN)) 283 #define ABS32(X) (((X)^((X)>>31))-((X)>>31)) 284 #define SIGN32(X) ((X) >> 31) | ((juint)(-(X)) >> 31) 285 286 /* Boundaries used for clipping large path segments (those are inside 287 * [UPPER/LOWER]_BND boundaries) 288 */ 289 #define UPPER_OUT_BND (1 << (30 - MDP_PREC)) 290 #define LOWER_OUT_BND (-UPPER_OUT_BND) 291 292 #define ADJUST(X, LBND, UBND) \ 293 do { \ 294 if ((X) < (LBND)) { \ 295 (X) = (LBND); \ 296 } else if ((X) > UBND) { \ 297 (X) = (UBND); \ 298 } \ 299 } while(0) 300 301 /* Following constants are used for providing open boundaries of the intervals 302 */ 303 #define EPSFX 1 304 #define EPSF (((jfloat)EPSFX)/MDP_MULT) 305 306 /* Calculation boundary. It is used for switching to the more slow but allowing 307 * larger input values method of calculation of the initial values of the scan 308 * converted line segments inside the FillPolygon. 309 */ 310 #define CALC_BND (1 << (30 - MDP_PREC)) 311 312 /* Clipping macros for drawing and filling algorithms */ 313 314 #define CLIP(a1, b1, a2, b2, t) \ 315 (b1 + ((jdouble)(t - a1)*(b2 - b1)) / (a2 - a1)) 316 317 enum { 318 CRES_MIN_CLIPPED, 319 CRES_MAX_CLIPPED, 320 CRES_NOT_CLIPPED, 321 CRES_INVISIBLE 322 }; 323 324 #define IS_CLIPPED(res) (res == CRES_MIN_CLIPPED || res == CRES_MAX_CLIPPED) 325 326 #define TESTANDCLIP(LINE_MIN, LINE_MAX, a1, b1, a2, b2, TYPE, res) \ 327 do { \ 328 jdouble t; \ 329 res = CRES_NOT_CLIPPED; \ 330 if (a1 < (LINE_MIN) || a1 > (LINE_MAX)) { \ 331 if (a1 < (LINE_MIN)) { \ 332 if (a2 < (LINE_MIN)) { \ 333 res = CRES_INVISIBLE; \ 334 break; \ 335 }; \ 336 res = CRES_MIN_CLIPPED; \ 337 t = (LINE_MIN); \ 338 } else { \ 339 if (a2 > (LINE_MAX)) { \ 340 res = CRES_INVISIBLE; \ 341 break; \ 342 }; \ 343 res = CRES_MAX_CLIPPED; \ 344 t = (LINE_MAX); \ 345 } \ 346 b1 = (TYPE)CLIP(a1, b1, a2, b2, t); \ 347 a1 = (TYPE)t; \ 348 } \ 349 } while (0) 350 351 /* Following macro is used for clipping and clumping filled shapes. 352 * An example of this process is shown on the picture below: 353 * ----+ ----+ 354 * |/ | |/ | 355 * + | + | 356 * /| | I | 357 * / | | I | 358 * | | | ===> I | 359 * \ | | I | 360 * \| | I | 361 * + | + | 362 * |\ | |\ | 363 * | ----+ | ----+ 364 * boundary boundary 365 * 366 * We can only perform clipping in case of right side of the output area 367 * because all segments passed out the right boundary don't influence on the 368 * result of scan conversion algorithm (it correctly handles half open 369 * contours). 370 * 371 */ 372 #define CLIPCLAMP(LINE_MIN, LINE_MAX, a1, b1, a2, b2, a3, b3, TYPE, res) \ 373 do { \ 374 a3 = a1; \ 375 b3 = b1; \ 376 TESTANDCLIP(LINE_MIN, LINE_MAX, a1, b1, a2, b2, TYPE, res); \ 377 if (res == CRES_MIN_CLIPPED) { \ 378 a3 = a1; \ 379 } else if (res == CRES_MAX_CLIPPED) { \ 380 a3 = a1; \ 381 res = CRES_MAX_CLIPPED; \ 382 } else if (res == CRES_INVISIBLE) { \ 383 if (a1 > LINE_MAX) { \ 384 res = CRES_INVISIBLE; \ 385 } else { \ 386 a1 = (TYPE)LINE_MIN; \ 387 a2 = (TYPE)LINE_MIN; \ 388 res = CRES_NOT_CLIPPED; \ 389 } \ 390 } \ 391 } while (0) 392 393 /* Following macro is used for solving quadratic equations: 394 * A*t^2 + B*t + C = 0 395 * in (0,1) range. That means we put to the RES the only roots which 396 * belongs to the (0,1) range. Note: 0 and 1 are not included. 397 * See solveQuadratic method in 398 * src/share/classes/java/awt/geom/QuadCurve2D.java 399 * for more info about calculations 400 */ 401 #define SOLVEQUADINRANGE(A,B,C,RES,RCNT) \ 402 do { \ 403 double param; \ 404 if ((A) != 0) { \ 405 /* Calculating roots of the following equation \ 406 * A*t^2 + B*t + C = 0 \ 407 */ \ 408 double d = (B)*(B) - 4*(A)*(C); \ 409 double q; \ 410 if (d < 0) { \ 411 break; \ 412 } \ 413 d = sqrt(d); \ 414 /* For accuracy, calculate one root using: \ 415 * (-B +/- d) / 2*A \ 416 * and the other using: \ 417 * 2*C / (-B +/- d) \ 418 * Choose the sign of the +/- so that B+D gets larger \ 419 * in magnitude \ 420 */ \ 421 if ((B) < 0) { \ 422 d = -d; \ 423 } \ 424 q = ((B) + d) / -2.0; \ 425 param = q/(A); \ 426 if (param < 1.0 && param > 0.0) { \ 427 (RES)[(RCNT)++] = param; \ 428 } \ 429 if (d == 0 || q == 0) { \ 430 break; \ 431 } \ 432 param = (C)/q; \ 433 if (param < 1.0 && param > 0.0) { \ 434 (RES)[(RCNT)++] = param; \ 435 } \ 436 } else { \ 437 /* Calculating root of the following equation \ 438 * B*t + C = 0 \ 439 */ \ 440 if ((B) == 0) { \ 441 break; \ 442 } \ 443 param = -(C)/(B); \ 444 if (param < 1.0 && param > 0.0) { \ 445 (RES)[(RCNT)++] = param; \ 446 } \ 447 } \ 448 } while(0) 449 450 /* Drawing line with subpixel endpoints 451 * 452 * (x1, y1), (x2, y2) - fixed point coordinates of the endpoints 453 * with MDP_PREC bits for the fractional part 454 * 455 * pixelInfo - structure which keeps drawing info for avoiding 456 * multiple drawing at the same position on the 457 * screen (required for the XOR mode of drawing) 458 * 459 * pixelInfo[0] - state of the drawing 460 * 0 - no pixel drawn between 461 * moveTo/close of the path 462 * 1 - there are drawn pixels 463 * 464 * pixelInfo[1,2] - first pixel of the path 465 * between moveTo/close of the 466 * path 467 * 468 * pixelInfo[3,4] - last drawn pixel between 469 * moveTo/close of the path 470 * 471 * checkBounds - flag showing necessity of checking the clip 472 * 473 */ 474 void ProcessFixedLine(ProcessHandler* hnd,jint x1,jint y1,jint x2,jint y2, 475 jint* pixelInfo,jboolean checkBounds, 476 jboolean endSubPath) 477 { 478 /* Checking if line is inside a (X,Y),(X+MDP_MULT,Y+MDP_MULT) box */ 479 jint c = ((x1 ^ x2) | (y1 ^ y2)); 480 jint rx1, ry1, rx2, ry2; 481 if ((c & MDP_W_MASK) == 0) { 482 /* Checking for the segments with integer coordinates having 483 * the same start and end points 484 */ 485 if (c == 0) { 486 PROCESS_POINT(hnd, x1 + MDP_HALF_MULT, y1 + MDP_HALF_MULT, 487 checkBounds, pixelInfo); 488 } 489 return; 490 } 491 492 if (x1 == x2 || y1 == y2) { 493 rx1 = x1 + MDP_HALF_MULT; 494 rx2 = x2 + MDP_HALF_MULT; 495 ry1 = y1 + MDP_HALF_MULT; 496 ry2 = y2 + MDP_HALF_MULT; 497 } else { 498 /* Neither dx nor dy can be zero because of the check above */ 499 jint dx = x2 - x1; 500 jint dy = y2 - y1; 501 502 /* Floor of x1, y1, x2, y2 */ 503 jint fx1 = x1 & MDP_W_MASK; 504 jint fy1 = y1 & MDP_W_MASK; 505 jint fx2 = x2 & MDP_W_MASK; 506 jint fy2 = y2 & MDP_W_MASK; 507 508 /* Processing first endpoint */ 509 if (fx1 == x1 || fy1 == y1) { 510 /* Adding MDP_HALF_MULT to the [xy]1 if f[xy]1 == [xy]1 will not 511 * affect the result 512 */ 513 rx1 = x1 + MDP_HALF_MULT; 514 ry1 = y1 + MDP_HALF_MULT; 515 } else { 516 /* Boundary at the direction from (x1,y1) to (x2,y2) */ 517 jint bx1 = (x1 < x2) ? fx1 + MDP_MULT : fx1; 518 jint by1 = (y1 < y2) ? fy1 + MDP_MULT : fy1; 519 520 /* intersection with column bx1 */ 521 jint cross = y1 + ((bx1 - x1)*dy)/dx; 522 if (cross >= fy1 && cross <= fy1 + MDP_MULT) { 523 rx1 = bx1; 524 ry1 = cross + MDP_HALF_MULT; 525 } else { 526 /* intersection with row by1 */ 527 cross = x1 + ((by1 - y1)*dx)/dy; 528 rx1 = cross + MDP_HALF_MULT; 529 ry1 = by1; 530 } 531 } 532 533 /* Processing second endpoint */ 534 if (fx2 == x2 || fy2 == y2) { 535 /* Adding MDP_HALF_MULT to the [xy]2 if f[xy]2 == [xy]2 will not 536 * affect the result 537 */ 538 rx2 = x2 + MDP_HALF_MULT; 539 ry2 = y2 + MDP_HALF_MULT; 540 } else { 541 /* Boundary at the direction from (x2,y2) to (x1,y1) */ 542 jint bx2 = (x1 > x2) ? fx2 + MDP_MULT : fx2; 543 jint by2 = (y1 > y2) ? fy2 + MDP_MULT : fy2; 544 545 /* intersection with column bx2 */ 546 jint cross = y2 + ((bx2 - x2)*dy)/dx; 547 if (cross >= fy2 && cross <= fy2 + MDP_MULT) { 548 rx2 = bx2; 549 ry2 = cross + MDP_HALF_MULT; 550 } else { 551 /* intersection with row by2 */ 552 cross = x2 + ((by2 - y2)*dx)/dy; 553 rx2 = cross + MDP_HALF_MULT; 554 ry2 = by2; 555 } 556 } 557 } 558 559 PROCESS_LINE(hnd, rx1, ry1, rx2, ry2, checkBounds, pixelInfo); 560 } 561 562 /* Performing drawing of the monotonic in X and Y quadratic curves with sizes 563 * less than MAX_QUAD_SIZE by using forward differencing method of calculation. 564 * See comments to the DrawMonotonicCubic. 565 */ 566 static void DrawMonotonicQuad(ProcessHandler* hnd, 567 jfloat *coords, 568 jboolean checkBounds, 569 jint* pixelInfo) 570 { 571 jint x0 = (jint)(coords[0]*MDP_MULT); 572 jint y0 = (jint)(coords[1]*MDP_MULT); 573 574 jint xe = (jint)(coords[4]*MDP_MULT); 575 jint ye = (jint)(coords[5]*MDP_MULT); 576 577 /* Extracting fractional part of coordinates of first control point */ 578 jint px = (x0 & (~MDP_W_MASK)) << DF_QUAD_SHIFT; 579 jint py = (y0 & (~MDP_W_MASK)) << DF_QUAD_SHIFT; 580 581 /* Setting default amount of steps */ 582 jint count = DF_QUAD_COUNT; 583 584 /* Setting default shift for preparing to the midpoint rounding */ 585 jint shift = DF_QUAD_SHIFT; 586 587 jint ax = (jint)((coords[0] - 2*coords[2] + 588 coords[4])*QUAD_A_MDP_MULT); 589 jint ay = (jint)((coords[1] - 2*coords[3] + 590 coords[5])*QUAD_A_MDP_MULT); 591 592 jint bx = (jint)((-2*coords[0] + 2*coords[2])*QUAD_B_MDP_MULT); 593 jint by = (jint)((-2*coords[1] + 2*coords[3])*QUAD_B_MDP_MULT); 594 595 jint ddpx = 2*ax; 596 jint ddpy = 2*ay; 597 598 jint dpx = ax + bx; 599 jint dpy = ay + by; 600 601 jint x1, y1; 602 603 jint x2 = x0; 604 jint y2 = y0; 605 606 jint maxDD = MAX(ABS32(ddpx),ABS32(ddpy)); 607 jint x0w = x0 & MDP_W_MASK; 608 jint y0w = y0 & MDP_W_MASK; 609 610 jint dx = xe - x0; 611 jint dy = ye - y0; 612 613 /* Perform decreasing step in 2 times if slope of the second forward 614 * difference changes too quickly (more than a pixel per step in X or Y 615 * direction). We can perform adjusting of the step size before the 616 * rendering loop because the curvature of the quad curve remains the same 617 * along all the curve 618 */ 619 while (maxDD > DF_QUAD_DEC_BND) { 620 dpx = (dpx<<1) - ax; 621 dpy = (dpy<<1) - ay; 622 count <<= 1; 623 maxDD >>= 2; 624 px <<=2; 625 py <<=2; 626 shift += 2; 627 } 628 629 while(count-- > 1) { 630 631 px += dpx; 632 py += dpy; 633 634 dpx += ddpx; 635 dpy += ddpy; 636 637 x1 = x2; 638 y1 = y2; 639 640 x2 = x0w + (px >> shift); 641 y2 = y0w + (py >> shift); 642 643 /* Checking that we are not running out of the endpoint and bounding 644 * violating coordinate. The check is pretty simple because the curve 645 * passed to the DrawMonotonicQuad already split into the monotonic 646 * in X and Y pieces 647 */ 648 649 /* Bounding x2 by xe */ 650 if (((xe-x2)^dx) < 0) { 651 x2 = xe; 652 } 653 654 /* Bounding y2 by ye */ 655 if (((ye-y2)^dy) < 0) { 656 y2 = ye; 657 } 658 659 hnd->pProcessFixedLine(hnd, x1, y1, x2, y2, pixelInfo, checkBounds, 660 JNI_FALSE); 661 } 662 663 /* We are performing one step less than necessary and use actual (xe,ye) 664 * curve's endpoint instead of calculated. This prevent us from accumulated 665 * errors at the last point. 666 */ 667 668 hnd->pProcessFixedLine(hnd, x2, y2, xe, ye, pixelInfo, checkBounds, 669 JNI_FALSE); 670 } 671 672 /* 673 * Checking size of the quad curves and split them if necessary. 674 * Calling DrawMonotonicQuad for the curves of the appropriate size. 675 * Note: coords array could be changed 676 */ 677 static void ProcessMonotonicQuad(ProcessHandler* hnd, 678 jfloat *coords, 679 jint* pixelInfo) { 680 681 jfloat coords1[6]; 682 jfloat xMin, xMax; 683 jfloat yMin, yMax; 684 685 xMin = xMax = coords[0]; 686 yMin = yMax = coords[1]; 687 688 CALC_MIN(xMin, coords[2]); 689 CALC_MAX(xMax, coords[2]); 690 CALC_MIN(yMin, coords[3]); 691 CALC_MAX(yMax, coords[3]); 692 CALC_MIN(xMin, coords[4]); 693 CALC_MAX(xMax, coords[4]); 694 CALC_MIN(yMin, coords[5]); 695 CALC_MAX(yMax, coords[5]); 696 697 698 if (hnd->clipMode == PH_MODE_DRAW_CLIP) { 699 700 /* In case of drawing we could just skip curves which are completely 701 * out of bounds 702 */ 703 if (hnd->dhnd->xMaxf < xMin || hnd->dhnd->xMinf > xMax || 704 hnd->dhnd->yMaxf < yMin || hnd->dhnd->yMinf > yMax) { 705 return; 706 } 707 } else { 708 709 /* In case of filling we could skip curves which are above, 710 * below and behind the right boundary of the visible area 711 */ 712 713 if (hnd->dhnd->yMaxf < yMin || hnd->dhnd->yMinf > yMax || 714 hnd->dhnd->xMaxf < xMin) 715 { 716 return; 717 } 718 719 /* We could clamp x coordinates to the corresponding boundary 720 * if the curve is completely behind the left one 721 */ 722 723 if (hnd->dhnd->xMinf > xMax) { 724 coords[0] = coords[2] = coords[4] = hnd->dhnd->xMinf; 725 } 726 } 727 728 if (xMax - xMin > MAX_QUAD_SIZE || yMax - yMin > MAX_QUAD_SIZE) { 729 coords1[4] = coords[4]; 730 coords1[5] = coords[5]; 731 coords1[2] = (coords[2] + coords[4])/2.0f; 732 coords1[3] = (coords[3] + coords[5])/2.0f; 733 coords[2] = (coords[0] + coords[2])/2.0f; 734 coords[3] = (coords[1] + coords[3])/2.0f; 735 coords[4] = coords1[0] = (coords[2] + coords1[2])/2.0f; 736 coords[5] = coords1[1] = (coords[3] + coords1[3])/2.0f; 737 738 ProcessMonotonicQuad(hnd, coords, pixelInfo); 739 740 ProcessMonotonicQuad(hnd, coords1, pixelInfo); 741 } else { 742 DrawMonotonicQuad(hnd, coords, 743 /* Set checkBounds parameter if curve intersects 744 * boundary of the visible area. We know that the 745 * curve is visible, so the check is pretty simple 746 */ 747 hnd->dhnd->xMinf >= xMin || hnd->dhnd->xMaxf <= xMax || 748 hnd->dhnd->yMinf >= yMin || hnd->dhnd->yMaxf <= yMax, 749 pixelInfo); 750 } 751 } 752 753 /* 754 * Bite the piece of the quadratic curve from start point till the point 755 * corresponding to the specified parameter then call ProcessQuad for the 756 * bitten part. 757 * Note: coords array will be changed 758 */ 759 static void ProcessFirstMonotonicPartOfQuad(ProcessHandler* hnd, jfloat* coords, 760 jint* pixelInfo, jfloat t) 761 { 762 jfloat coords1[6]; 763 764 coords1[0] = coords[0]; 765 coords1[1] = coords[1]; 766 coords1[2] = coords[0] + t*(coords[2] - coords[0]); 767 coords1[3] = coords[1] + t*(coords[3] - coords[1]); 768 coords[2] = coords[2] + t*(coords[4] - coords[2]); 769 coords[3] = coords[3] + t*(coords[5] - coords[3]); 770 coords[0] = coords1[4] = coords1[2] + t*(coords[2] - coords1[2]); 771 coords[1] = coords1[5] = coords1[3] + t*(coords[3] - coords1[3]); 772 773 ProcessMonotonicQuad(hnd, coords1, pixelInfo); 774 } 775 776 /* 777 * Split quadratic curve into monotonic in X and Y parts. Calling 778 * ProcessMonotonicQuad for each monotonic piece of the curve. 779 * Note: coords array could be changed 780 */ 781 static void ProcessQuad(ProcessHandler* hnd, jfloat* coords, jint* pixelInfo) { 782 783 /* Temporary array for holding parameters corresponding to the extreme in X 784 * and Y points. The values are inside the (0,1) range (0 and 1 excluded) 785 * and in ascending order. 786 */ 787 double params[2] = {0.0, 0.0}; 788 789 jint cnt = 0; 790 double param = 0.0; 791 792 /* Simple check for monotonicity in X before searching for the extreme 793 * points of the X(t) function. We first check if the curve is monotonic 794 * in X by seeing if all of the X coordinates are strongly ordered. 795 */ 796 if ((coords[0] > coords[2] || coords[2] > coords[4]) && 797 (coords[0] < coords[2] || coords[2] < coords[4])) 798 { 799 /* Searching for extreme points of the X(t) function by solving 800 * dX(t) 801 * ---- = 0 equation 802 * dt 803 */ 804 double ax = coords[0] - 2*coords[2] + coords[4]; 805 if (ax != 0) { 806 /* Calculating root of the following equation 807 * ax*t + bx = 0 808 */ 809 double bx = coords[0] - coords[2]; 810 811 param = bx/ax; 812 if (param < 1.0 && param > 0.0) { 813 params[cnt++] = param; 814 } 815 } 816 } 817 818 /* Simple check for monotonicity in Y before searching for the extreme 819 * points of the Y(t) function. We first check if the curve is monotonic 820 * in Y by seeing if all of the Y coordinates are strongly ordered. 821 */ 822 if ((coords[1] > coords[3] || coords[3] > coords[5]) && 823 (coords[1] < coords[3] || coords[3] < coords[5])) 824 { 825 /* Searching for extreme points of the Y(t) function by solving 826 * dY(t) 827 * ----- = 0 equation 828 * dt 829 */ 830 double ay = coords[1] - 2*coords[3] + coords[5]; 831 832 if (ay != 0) { 833 /* Calculating root of the following equation 834 * ay*t + by = 0 835 */ 836 double by = coords[1] - coords[3]; 837 838 param = by/ay; 839 if (param < 1.0 && param > 0.0) { 840 if (cnt > 0) { 841 /* Inserting parameter only if it differs from 842 * already stored 843 */ 844 if (params[0] > param) { 845 params[cnt++] = params[0]; 846 params[0] = param; 847 } else if (params[0] < param) { 848 params[cnt++] = param; 849 } 850 } else { 851 params[cnt++] = param; 852 } 853 } 854 } 855 } 856 857 /* Processing obtained monotonic parts */ 858 switch(cnt) { 859 case 0: 860 break; 861 case 1: 862 ProcessFirstMonotonicPartOfQuad(hnd, coords, pixelInfo, 863 (jfloat)params[0]); 864 break; 865 case 2: 866 ProcessFirstMonotonicPartOfQuad(hnd, coords, pixelInfo, 867 (jfloat)params[0]); 868 param = params[1] - params[0]; 869 if (param > 0) { 870 ProcessFirstMonotonicPartOfQuad(hnd, coords, pixelInfo, 871 /* Scale parameter to match with rest of the curve */ 872 (jfloat)(param/(1.0 - params[0]))); 873 } 874 break; 875 } 876 877 ProcessMonotonicQuad(hnd,coords,pixelInfo); 878 } 879 880 /* 881 * Performing drawing of the monotonic in X and Y cubic curves with sizes less 882 * than MAX_CUB_SIZE by using forward differencing method of calculation. 883 * 884 * Here is some math used in the code below. 885 * 886 * If we express the parametric equation for the coordinates as 887 * simple polynomial: 888 * 889 * V(t) = a * t^3 + b * t^2 + c * t + d 890 * 891 * The equations for how we derive these polynomial coefficients 892 * from the Bezier control points can be found in the method comments 893 * for the CubicCurve.fillEqn Java method. 894 * 895 * From this polynomial, we can derive the forward differences to 896 * allow us to calculate V(t+K) from V(t) as follows: 897 * 898 * 1) V1(0) 899 * = V(K)-V(0) 900 * = aK^3 + bK^2 + cK + d - d 901 * = aK^3 + bK^2 + cK 902 * 903 * 2) V1(K) 904 * = V(2K)-V(K) 905 * = 8aK^3 + 4bK^2 + 2cK + d - aK^3 - bK^2 - cK - d 906 * = 7aK^3 + 3bK^2 + cK 907 * 908 * 3) V1(2K) 909 * = V(3K)-V(2K) 910 * = 27aK^3 + 9bK^2 + 3cK + d - 8aK^3 - 4bK^2 - 2cK - d 911 * = 19aK^3 + 5bK^2 + cK 912 * 913 * 4) V2(0) 914 * = V1(K) - V1(0) 915 * = 7aK^3 + 3bK^2 + cK - aK^3 - bK^2 - cK 916 * = 6aK^3 + 2bK^2 917 * 918 * 5) V2(K) 919 * = V1(2K) - V1(K) 920 * = 19aK^3 + 5bK^2 + cK - 7aK^3 - 3bK^2 - cK 921 * = 12aK^3 + 2bK^2 922 * 923 * 6) V3(0) 924 * = V2(K) - V2(0) 925 * = 12aK^3 + 2bK^2 - 6aK^3 - 2bK^2 926 * = 6aK^3 927 * 928 * Note that if we continue on to calculate V1(3K), V2(2K) and 929 * V3(K) we will see that V3(K) == V3(0) so we need at most 930 * 3 cascading forward differences to step through the cubic 931 * curve. 932 * 933 * Note, b coefficient calculating in the DrawCubic is actually twice the b 934 * coefficient seen above. It's been done for the better accuracy. 935 * 936 * In our case, initialy K is chosen as 1/(2^DF_CUB_STEPS) this value is taken 937 * with FWD_PREC bits precision. This means that we should do 2^DF_CUB_STEPS 938 * steps to pass through all the curve. 939 * 940 * On each step we examine how far we are stepping by examining our first(V1) 941 * and second (V2) order derivatives and verifying that they are met following 942 * conditions: 943 * 944 * abs(V2) <= DF_CUB_DEC_BND 945 * abs(V1) > DF_CUB_INC_BND 946 * 947 * So, ensures that we step through the curve more slowly when its curvature is 948 * high and faster when its curvature is lower. If the step size needs 949 * adjustment we adjust it so that we step either twice as fast, or twice as 950 * slow until our step size is within range. This modifies our stepping 951 * variables as follows: 952 * 953 * Decreasing step size 954 * (See Graphics Gems/by A.Glassner,(Tutorial on forward differencing),601-602) 955 * 956 * V3 = oV3/8 957 * V2 = oV2/4 - V3 958 * V1 = (oV1 - V2)/2 959 * 960 * Here V1-V3 stands for new values of the forward differencies and oV1 - oV3 961 * for the old ones 962 * 963 * Using the equations above it's easy to calculating stepping variables for 964 * the increasing step size: 965 * 966 * V1 = 2*oV1 + oV2 967 * V2 = 4*oV2 + 4*oV3 968 * V3 = 8*oV3 969 * 970 * And then for not to running out of 32 bit precision we are performing 3 bit 971 * shift of the forward differencing precision (keeping in shift variable) in 972 * left or right direction depending on what is happening (decreasing or 973 * increasing). So, all oV1 - oV3 variables should be thought as appropriately 974 * shifted in regard to the V1 - V3. 975 * 976 * Taking all of the above into account we will have following: 977 * 978 * Decreasing step size: 979 * 980 * shift = shift + 3 981 * V3 keeps the same 982 * V2 = 2*oV2 - V3 983 * V1 = 4*oV1 - V2/2 984 * 985 * Increasing step size: 986 * 987 * shift = shift - 3 988 * V1 = oV1/4 + oV2/8 989 * V2 = oV2/2 + oV3/2 990 * V3 keeps the same 991 * 992 */ 993 994 static void DrawMonotonicCubic(ProcessHandler* hnd, 995 jfloat *coords, 996 jboolean checkBounds, 997 jint* pixelInfo) 998 { 999 jint x0 = (jint)(coords[0]*MDP_MULT); 1000 jint y0 = (jint)(coords[1]*MDP_MULT); 1001 1002 jint xe = (jint)(coords[6]*MDP_MULT); 1003 jint ye = (jint)(coords[7]*MDP_MULT); 1004 1005 /* Extracting fractional part of coordinates of first control point */ 1006 jint px = (x0 & (~MDP_W_MASK)) << DF_CUB_SHIFT; 1007 jint py = (y0 & (~MDP_W_MASK)) << DF_CUB_SHIFT; 1008 1009 /* Setting default boundary values for checking first and second forward 1010 * difference for the necessity of the restepping. See comments to the 1011 * boundary values in ProcessQuad for more info. 1012 */ 1013 jint incStepBnd1 = DF_CUB_INC_BND; 1014 jint incStepBnd2 = DF_CUB_INC_BND << 1; 1015 jint decStepBnd1 = DF_CUB_DEC_BND; 1016 jint decStepBnd2 = DF_CUB_DEC_BND << 1; 1017 1018 /* Setting default amount of steps */ 1019 jint count = DF_CUB_COUNT; 1020 1021 /* Setting default shift for preparing to the midpoint rounding */ 1022 jint shift = DF_CUB_SHIFT; 1023 1024 jint ax = (jint)((-coords[0] + 3*coords[2] - 3*coords[4] + 1025 coords[6])*CUB_A_MDP_MULT); 1026 jint ay = (jint)((-coords[1] + 3*coords[3] - 3*coords[5] + 1027 coords[7])*CUB_A_MDP_MULT); 1028 1029 jint bx = (jint)((3*coords[0] - 6*coords[2] + 1030 3*coords[4])*CUB_B_MDP_MULT); 1031 jint by = (jint)((3*coords[1] - 6*coords[3] + 1032 3*coords[5])*CUB_B_MDP_MULT); 1033 1034 jint cx = (jint)((-3*coords[0] + 3*coords[2])*(CUB_C_MDP_MULT)); 1035 jint cy = (jint)((-3*coords[1] + 3*coords[3])*(CUB_C_MDP_MULT)); 1036 1037 jint dddpx = 6*ax; 1038 jint dddpy = 6*ay; 1039 1040 jint ddpx = dddpx + bx; 1041 jint ddpy = dddpy + by; 1042 1043 jint dpx = ax + (bx>>1) + cx; 1044 jint dpy = ay + (by>>1) + cy; 1045 1046 jint x1, y1; 1047 1048 jint x2 = x0; 1049 jint y2 = y0; 1050 1051 /* Calculating whole part of the first point of the curve */ 1052 jint x0w = x0 & MDP_W_MASK; 1053 jint y0w = y0 & MDP_W_MASK; 1054 1055 jint dx = xe - x0; 1056 jint dy = ye - y0; 1057 1058 while (count > 0) { 1059 /* Perform decreasing step in 2 times if necessary */ 1060 while ( 1061 /* The code below is an optimized version of the checks: 1062 * abs(ddpx) > decStepBnd1 || 1063 * abs(ddpy) > decStepBnd1 1064 */ 1065 (juint)(ddpx + decStepBnd1) > (juint)decStepBnd2 || 1066 (juint)(ddpy + decStepBnd1) > (juint)decStepBnd2) 1067 { 1068 ddpx = (ddpx<<1) - dddpx; 1069 ddpy = (ddpy<<1) - dddpy; 1070 dpx = (dpx<<2) - (ddpx>>1); 1071 dpy = (dpy<<2) - (ddpy>>1); 1072 count <<=1; 1073 decStepBnd1 <<=3; 1074 decStepBnd2 <<=3; 1075 incStepBnd1 <<=3; 1076 incStepBnd2 <<=3; 1077 px <<=3; 1078 py <<=3; 1079 shift += 3; 1080 } 1081 1082 /* Perform increasing step in 2 times if necessary. 1083 * Note: we could do it only in even steps 1084 */ 1085 1086 while (((count & 1) ^ 1) && shift > DF_CUB_SHIFT && 1087 /* The code below is an optimized version of the check: 1088 * abs(dpx) <= incStepBnd1 && 1089 * abs(dpy) <= incStepBnd1 1090 */ 1091 (juint)(dpx + incStepBnd1) <= (juint)incStepBnd2 && 1092 (juint)(dpy + incStepBnd1) <= (juint)incStepBnd2) 1093 { 1094 dpx = (dpx>>2) + (ddpx>>3); 1095 dpy = (dpy>>2) + (ddpy>>3); 1096 ddpx = (ddpx + dddpx)>>1; 1097 ddpy = (ddpy + dddpy)>>1; 1098 count >>=1; 1099 decStepBnd1 >>=3; 1100 decStepBnd2 >>=3; 1101 incStepBnd1 >>=3; 1102 incStepBnd2 >>=3; 1103 px >>=3; 1104 py >>=3; 1105 shift -= 3; 1106 } 1107 1108 count--; 1109 1110 /* We are performing one step less than necessary and use actual 1111 * (xe,ye) endpoint of the curve instead of calculated. This prevent 1112 * us from accumulated errors at the last point. 1113 */ 1114 if (count) { 1115 1116 px += dpx; 1117 py += dpy; 1118 1119 dpx += ddpx; 1120 dpy += ddpy; 1121 ddpx += dddpx; 1122 ddpy += dddpy; 1123 1124 x1 = x2; 1125 y1 = y2; 1126 1127 x2 = x0w + (px >> shift); 1128 y2 = y0w + (py >> shift); 1129 1130 /* Checking that we are not running out of the endpoint and 1131 * bounding violating coordinate. The check is pretty simple 1132 * because the curve passed to the DrawMonotonicCubic already 1133 * split into the monotonic in X and Y pieces 1134 */ 1135 1136 /* Bounding x2 by xe */ 1137 if (((xe-x2)^dx) < 0) { 1138 x2 = xe; 1139 } 1140 1141 /* Bounding y2 by ye */ 1142 if (((ye-y2)^dy) < 0) { 1143 y2 = ye; 1144 } 1145 1146 hnd->pProcessFixedLine(hnd, x1, y1, x2, y2, pixelInfo, checkBounds, 1147 JNI_FALSE); 1148 } else { 1149 hnd->pProcessFixedLine(hnd, x2, y2, xe, ye, pixelInfo, checkBounds, 1150 JNI_FALSE); 1151 } 1152 } 1153 } 1154 1155 /* 1156 * Checking size of the cubic curves and split them if necessary. 1157 * Calling DrawMonotonicCubic for the curves of the appropriate size. 1158 * Note: coords array could be changed 1159 */ 1160 static void ProcessMonotonicCubic(ProcessHandler* hnd, 1161 jfloat *coords, 1162 jint* pixelInfo) { 1163 1164 jfloat coords1[8]; 1165 jfloat tx, ty; 1166 jfloat xMin, xMax; 1167 jfloat yMin, yMax; 1168 1169 xMin = xMax = coords[0]; 1170 yMin = yMax = coords[1]; 1171 1172 CALC_MIN(xMin, coords[2]); 1173 CALC_MAX(xMax, coords[2]); 1174 CALC_MIN(yMin, coords[3]); 1175 CALC_MAX(yMax, coords[3]); 1176 CALC_MIN(xMin, coords[4]); 1177 CALC_MAX(xMax, coords[4]); 1178 CALC_MIN(yMin, coords[5]); 1179 CALC_MAX(yMax, coords[5]); 1180 CALC_MIN(xMin, coords[6]); 1181 CALC_MAX(xMax, coords[6]); 1182 CALC_MIN(yMin, coords[7]); 1183 CALC_MAX(yMax, coords[7]); 1184 1185 if (hnd->clipMode == PH_MODE_DRAW_CLIP) { 1186 1187 /* In case of drawing we could just skip curves which are completely 1188 * out of bounds 1189 */ 1190 if (hnd->dhnd->xMaxf < xMin || hnd->dhnd->xMinf > xMax || 1191 hnd->dhnd->yMaxf < yMin || hnd->dhnd->yMinf > yMax) { 1192 return; 1193 } 1194 } else { 1195 1196 /* In case of filling we could skip curves which are above, 1197 * below and behind the right boundary of the visible area 1198 */ 1199 1200 if (hnd->dhnd->yMaxf < yMin || hnd->dhnd->yMinf > yMax || 1201 hnd->dhnd->xMaxf < xMin) 1202 { 1203 return; 1204 } 1205 1206 /* We could clamp x coordinates to the corresponding boundary 1207 * if the curve is completely behind the left one 1208 */ 1209 1210 if (hnd->dhnd->xMinf > xMax) { 1211 coords[0] = coords[2] = coords[4] = coords[6] = 1212 hnd->dhnd->xMinf; 1213 } 1214 } 1215 1216 if (xMax - xMin > MAX_CUB_SIZE || yMax - yMin > MAX_CUB_SIZE) { 1217 coords1[6] = coords[6]; 1218 coords1[7] = coords[7]; 1219 coords1[4] = (coords[4] + coords[6])/2.0f; 1220 coords1[5] = (coords[5] + coords[7])/2.0f; 1221 tx = (coords[2] + coords[4])/2.0f; 1222 ty = (coords[3] + coords[5])/2.0f; 1223 coords1[2] = (tx + coords1[4])/2.0f; 1224 coords1[3] = (ty + coords1[5])/2.0f; 1225 coords[2] = (coords[0] + coords[2])/2.0f; 1226 coords[3] = (coords[1] + coords[3])/2.0f; 1227 coords[4] = (coords[2] + tx)/2.0f; 1228 coords[5] = (coords[3] + ty)/2.0f; 1229 coords[6]=coords1[0]=(coords[4] + coords1[2])/2.0f; 1230 coords[7]=coords1[1]=(coords[5] + coords1[3])/2.0f; 1231 1232 ProcessMonotonicCubic(hnd, coords, pixelInfo); 1233 1234 ProcessMonotonicCubic(hnd, coords1, pixelInfo); 1235 1236 } else { 1237 DrawMonotonicCubic(hnd, coords, 1238 /* Set checkBounds parameter if curve intersects 1239 * boundary of the visible area. We know that the 1240 * curve is visible, so the check is pretty simple 1241 */ 1242 hnd->dhnd->xMinf > xMin || hnd->dhnd->xMaxf < xMax || 1243 hnd->dhnd->yMinf > yMin || hnd->dhnd->yMaxf < yMax, 1244 pixelInfo); 1245 } 1246 } 1247 1248 /* 1249 * Bite the piece of the cubic curve from start point till the point 1250 * corresponding to the specified parameter then call ProcessMonotonicCubic for 1251 * the bitten part. 1252 * Note: coords array will be changed 1253 */ 1254 static void ProcessFirstMonotonicPartOfCubic(ProcessHandler* hnd, 1255 jfloat* coords, jint* pixelInfo, 1256 jfloat t) 1257 { 1258 jfloat coords1[8]; 1259 jfloat tx, ty; 1260 1261 coords1[0] = coords[0]; 1262 coords1[1] = coords[1]; 1263 tx = coords[2] + t*(coords[4] - coords[2]); 1264 ty = coords[3] + t*(coords[5] - coords[3]); 1265 coords1[2] = coords[0] + t*(coords[2] - coords[0]); 1266 coords1[3] = coords[1] + t*(coords[3] - coords[1]); 1267 coords1[4] = coords1[2] + t*(tx - coords1[2]); 1268 coords1[5] = coords1[3] + t*(ty - coords1[3]); 1269 coords[4] = coords[4] + t*(coords[6] - coords[4]); 1270 coords[5] = coords[5] + t*(coords[7] - coords[5]); 1271 coords[2] = tx + t*(coords[4] - tx); 1272 coords[3] = ty + t*(coords[5] - ty); 1273 coords[0]=coords1[6]=coords1[4] + t*(coords[2] - coords1[4]); 1274 coords[1]=coords1[7]=coords1[5] + t*(coords[3] - coords1[5]); 1275 1276 ProcessMonotonicCubic(hnd, coords1, pixelInfo); 1277 } 1278 1279 /* 1280 * Split cubic curve into monotonic in X and Y parts. Calling ProcessCubic for 1281 * each monotonic piece of the curve. 1282 * 1283 * Note: coords array could be changed 1284 */ 1285 static void ProcessCubic(ProcessHandler* hnd, jfloat* coords, jint* pixelInfo) 1286 { 1287 /* Temporary array for holding parameters corresponding to the extreme in X 1288 * and Y points. The values are inside the (0,1) range (0 and 1 excluded) 1289 * and in ascending order. 1290 */ 1291 double params[4]; 1292 jint cnt = 0, i; 1293 1294 /* Simple check for monotonicity in X before searching for the extreme 1295 * points of the X(t) function. We first check if the curve is monotonic in 1296 * X by seeing if all of the X coordinates are strongly ordered. 1297 */ 1298 if ((coords[0] > coords[2] || coords[2] > coords[4] || 1299 coords[4] > coords[6]) && 1300 (coords[0] < coords[2] || coords[2] < coords[4] || 1301 coords[4] < coords[6])) 1302 { 1303 /* Searching for extreme points of the X(t) function by solving 1304 * dX(t) 1305 * ---- = 0 equation 1306 * dt 1307 */ 1308 double ax = -coords[0] + 3*coords[2] - 3*coords[4] + coords[6]; 1309 double bx = 2*(coords[0] - 2*coords[2] + coords[4]); 1310 double cx = -coords[0] + coords[2]; 1311 1312 SOLVEQUADINRANGE(ax,bx,cx,params,cnt); 1313 } 1314 1315 /* Simple check for monotonicity in Y before searching for the extreme 1316 * points of the Y(t) function. We first check if the curve is monotonic in 1317 * Y by seeing if all of the Y coordinates are strongly ordered. 1318 */ 1319 if ((coords[1] > coords[3] || coords[3] > coords[5] || 1320 coords[5] > coords[7]) && 1321 (coords[1] < coords[3] || coords[3] < coords[5] || 1322 coords[5] < coords[7])) 1323 { 1324 /* Searching for extreme points of the Y(t) function by solving 1325 * dY(t) 1326 * ----- = 0 equation 1327 * dt 1328 */ 1329 double ay = -coords[1] + 3*coords[3] - 3*coords[5] + coords[7]; 1330 double by = 2*(coords[1] - 2*coords[3] + coords[5]); 1331 double cy = -coords[1] + coords[3]; 1332 1333 SOLVEQUADINRANGE(ay,by,cy,params,cnt); 1334 } 1335 1336 if (cnt > 0) { 1337 /* Sorting parameter values corresponding to the extremum points of 1338 * the curve. We are using insertion sort because of tiny size of the 1339 * array. 1340 */ 1341 jint j; 1342 1343 for(i = 1; i < cnt; i++) { 1344 double value = params[i]; 1345 for (j = i - 1; j >= 0 && params[j] > value; j--) { 1346 params[j + 1] = params[j]; 1347 } 1348 params[j + 1] = value; 1349 } 1350 1351 /* Processing obtained monotonic parts */ 1352 ProcessFirstMonotonicPartOfCubic(hnd, coords, pixelInfo, 1353 (jfloat)params[0]); 1354 for (i = 1; i < cnt; i++) { 1355 double param = params[i] - params[i-1]; 1356 if (param > 0) { 1357 ProcessFirstMonotonicPartOfCubic(hnd, coords, pixelInfo, 1358 /* Scale parameter to match with rest of the curve */ 1359 (float)(param/(1.0 - params[i - 1]))); 1360 } 1361 } 1362 } 1363 1364 ProcessMonotonicCubic(hnd,coords,pixelInfo); 1365 } 1366 1367 static void ProcessLine(ProcessHandler* hnd, 1368 jfloat *coord1, jfloat *coord2, jint* pixelInfo) { 1369 1370 jfloat xMin, yMin, xMax, yMax; 1371 jint X1, Y1, X2, Y2, X3, Y3, res; 1372 jboolean clipped = JNI_FALSE; 1373 jfloat x1 = coord1[0]; 1374 jfloat y1 = coord1[1]; 1375 jfloat x2 = coord2[0]; 1376 jfloat y2 = coord2[1]; 1377 jfloat x3,y3; 1378 1379 jboolean lastClipped; 1380 1381 xMin = hnd->dhnd->xMinf; 1382 yMin = hnd->dhnd->yMinf; 1383 xMax = hnd->dhnd->xMaxf; 1384 yMax = hnd->dhnd->yMaxf; 1385 1386 TESTANDCLIP(yMin, yMax, y1, x1, y2, x2, jfloat, res); 1387 if (res == CRES_INVISIBLE) return; 1388 clipped = IS_CLIPPED(res); 1389 TESTANDCLIP(yMin, yMax, y2, x2, y1, x1, jfloat, res); 1390 if (res == CRES_INVISIBLE) return; 1391 lastClipped = IS_CLIPPED(res); 1392 clipped = clipped || lastClipped; 1393 1394 if (hnd->clipMode == PH_MODE_DRAW_CLIP) { 1395 TESTANDCLIP(xMin, xMax, 1396 x1, y1, x2, y2, jfloat, res); 1397 if (res == CRES_INVISIBLE) return; 1398 clipped = clipped || IS_CLIPPED(res); 1399 TESTANDCLIP(xMin, xMax, 1400 x2, y2, x1, y1, jfloat, res); 1401 if (res == CRES_INVISIBLE) return; 1402 lastClipped = lastClipped || IS_CLIPPED(res); 1403 clipped = clipped || lastClipped; 1404 X1 = (jint)(x1*MDP_MULT); 1405 Y1 = (jint)(y1*MDP_MULT); 1406 X2 = (jint)(x2*MDP_MULT); 1407 Y2 = (jint)(y2*MDP_MULT); 1408 1409 hnd->pProcessFixedLine(hnd, X1, Y1, X2, Y2, pixelInfo, 1410 clipped, /* enable boundary checking in case 1411 of clipping to avoid entering 1412 out of bounds which could 1413 happens during rounding 1414 */ 1415 lastClipped /* Notify pProcessFixedLine that 1416 this is the end of the 1417 subpath (because of exiting 1418 out of boundaries) 1419 */ 1420 ); 1421 } else { 1422 /* Clamping starting from first vertex of the processed segment 1423 */ 1424 CLIPCLAMP(xMin, xMax, x1, y1, x2, y2, x3, y3, jfloat, res); 1425 X1 = (jint)(x1*MDP_MULT); 1426 Y1 = (jint)(y1*MDP_MULT); 1427 1428 /* Clamping only by left boundary */ 1429 if (res == CRES_MIN_CLIPPED) { 1430 X3 = (jint)(x3*MDP_MULT); 1431 Y3 = (jint)(y3*MDP_MULT); 1432 hnd->pProcessFixedLine(hnd, X3, Y3, X1, Y1, pixelInfo, 1433 JNI_FALSE, lastClipped); 1434 1435 } else if (res == CRES_INVISIBLE) { 1436 return; 1437 } 1438 1439 /* Clamping starting from last vertex of the processed segment 1440 */ 1441 CLIPCLAMP(xMin, xMax, x2, y2, x1, y1, x3, y3, jfloat, res); 1442 1443 /* Checking if there was a clip by right boundary */ 1444 lastClipped = lastClipped || (res == CRES_MAX_CLIPPED); 1445 1446 X2 = (jint)(x2*MDP_MULT); 1447 Y2 = (jint)(y2*MDP_MULT); 1448 hnd->pProcessFixedLine(hnd, X1, Y1, X2, Y2, pixelInfo, 1449 JNI_FALSE, lastClipped); 1450 1451 /* Clamping only by left boundary */ 1452 if (res == CRES_MIN_CLIPPED) { 1453 X3 = (jint)(x3*MDP_MULT); 1454 Y3 = (jint)(y3*MDP_MULT); 1455 hnd->pProcessFixedLine(hnd, X2, Y2, X3, Y3, pixelInfo, 1456 JNI_FALSE, lastClipped); 1457 } 1458 } 1459 } 1460 1461 jboolean ProcessPath(ProcessHandler* hnd, 1462 jfloat transXf, jfloat transYf, 1463 jfloat* coords, jint maxCoords, 1464 jbyte* types, jint numTypes) 1465 { 1466 jfloat tCoords[8]; 1467 jfloat closeCoord[2]; 1468 jint pixelInfo[5]; 1469 jboolean skip = JNI_FALSE; 1470 jboolean subpathStarted = JNI_FALSE; 1471 jfloat lastX, lastY; 1472 int i, index = 0; 1473 1474 pixelInfo[0] = 0; 1475 1476 /* Adding support of the KEY_STROKE_CONTROL rendering hint. 1477 * Now we are supporting two modes: "pixels at centers" and 1478 * "pixels at corners". 1479 * First one is disabled by default but could be enabled by setting 1480 * VALUE_STROKE_PURE to the rendering hint. It means that pixel at the 1481 * screen (x,y) has (x + 0.5, y + 0.5) float coordinates. 1482 * 1483 * Second one is enabled by default and means straightforward mapping 1484 * (x,y) --> (x,y) 1485 * 1486 */ 1487 if (hnd->stroke == PH_STROKE_PURE) { 1488 closeCoord[0] = -0.5f; 1489 closeCoord[1] = -0.5f; 1490 transXf -= 0.5; 1491 transYf -= 0.5; 1492 } else { 1493 closeCoord[0] = 0.0f; 1494 closeCoord[1] = 0.0f; 1495 } 1496 1497 /* Adjusting boundaries to the capabilities of the ProcessPath code */ 1498 ADJUST(hnd->dhnd->xMin, LOWER_OUT_BND, UPPER_OUT_BND); 1499 ADJUST(hnd->dhnd->yMin, LOWER_OUT_BND, UPPER_OUT_BND); 1500 ADJUST(hnd->dhnd->xMax, LOWER_OUT_BND, UPPER_OUT_BND); 1501 ADJUST(hnd->dhnd->yMax, LOWER_OUT_BND, UPPER_OUT_BND); 1502 1503 1504 /* Setting up fractional clipping box 1505 * 1506 * We are using following float -> int mapping: 1507 * 1508 * xi = floor(xf + 0.5) 1509 * 1510 * So, fractional values that hit the [xmin, xmax) integer interval will be 1511 * situated inside the [xmin-0.5, xmax - 0.5) fractional interval. We are 1512 * using EPSF constant to provide that upper boundary is not included. 1513 */ 1514 hnd->dhnd->xMinf = hnd->dhnd->xMin - 0.5f; 1515 hnd->dhnd->yMinf = hnd->dhnd->yMin - 0.5f; 1516 hnd->dhnd->xMaxf = hnd->dhnd->xMax - 0.5f - EPSF; 1517 hnd->dhnd->yMaxf = hnd->dhnd->yMax - 0.5f - EPSF; 1518 1519 1520 for (i = 0; i < numTypes; i++) { 1521 switch (types[i]) { 1522 case java_awt_geom_PathIterator_SEG_MOVETO: 1523 if (index + 2 <= maxCoords) { 1524 /* Performing closing of the unclosed segments */ 1525 if (subpathStarted & !skip) { 1526 if (hnd->clipMode == PH_MODE_FILL_CLIP) { 1527 if (tCoords[0] != closeCoord[0] || 1528 tCoords[1] != closeCoord[1]) 1529 { 1530 ProcessLine(hnd, tCoords, closeCoord, 1531 pixelInfo); 1532 } 1533 } 1534 hnd->pProcessEndSubPath(hnd); 1535 } 1536 1537 tCoords[0] = coords[index++] + transXf; 1538 tCoords[1] = coords[index++] + transYf; 1539 1540 /* Checking SEG_MOVETO coordinates if they are out of the 1541 * [LOWER_BND, UPPER_BND] range. This check also handles 1542 * NaN and Infinity values. Skipping next path segment in 1543 * case of invalid data. 1544 */ 1545 1546 if (tCoords[0] < UPPER_BND && 1547 tCoords[0] > LOWER_BND && 1548 tCoords[1] < UPPER_BND && 1549 tCoords[1] > LOWER_BND) 1550 { 1551 subpathStarted = JNI_TRUE; 1552 skip = JNI_FALSE; 1553 closeCoord[0] = tCoords[0]; 1554 closeCoord[1] = tCoords[1]; 1555 } else { 1556 skip = JNI_TRUE; 1557 } 1558 } else { 1559 return JNI_FALSE; 1560 } 1561 break; 1562 case java_awt_geom_PathIterator_SEG_LINETO: 1563 if (index + 2 <= maxCoords) { 1564 lastX = tCoords[2] = coords[index++] + transXf; 1565 lastY = tCoords[3] = coords[index++] + transYf; 1566 1567 /* Checking SEG_LINETO coordinates if they are out of the 1568 * [LOWER_BND, UPPER_BND] range. This check also handles 1569 * NaN and Infinity values. Ignoring current path segment 1570 * in case of invalid data. If segment is skipped its 1571 * endpoint (if valid) is used to begin new subpath. 1572 */ 1573 1574 if (lastX < UPPER_BND && 1575 lastX > LOWER_BND && 1576 lastY < UPPER_BND && 1577 lastY > LOWER_BND) 1578 { 1579 if (skip) { 1580 tCoords[0] = closeCoord[0] = lastX; 1581 tCoords[1] = closeCoord[1] = lastY; 1582 subpathStarted = JNI_TRUE; 1583 skip = JNI_FALSE; 1584 } else { 1585 ProcessLine(hnd, tCoords, tCoords + 2, 1586 pixelInfo); 1587 tCoords[0] = lastX; 1588 tCoords[1] = lastY; 1589 } 1590 } 1591 } else { 1592 return JNI_FALSE; 1593 } 1594 break; 1595 case java_awt_geom_PathIterator_SEG_QUADTO: 1596 if (index + 4 <= maxCoords) { 1597 tCoords[2] = coords[index++] + transXf; 1598 tCoords[3] = coords[index++] + transYf; 1599 lastX = tCoords[4] = coords[index++] + transXf; 1600 lastY = tCoords[5] = coords[index++] + transYf; 1601 1602 /* Checking SEG_QUADTO coordinates if they are out of the 1603 * [LOWER_BND, UPPER_BND] range. This check also handles 1604 * NaN and Infinity values. Ignoring current path segment 1605 * in case of invalid endpoints's data. Equivalent to 1606 * the SEG_LINETO if endpoint coordinates are valid but 1607 * there are invalid data among other coordinates 1608 */ 1609 1610 if (lastX < UPPER_BND && 1611 lastX > LOWER_BND && 1612 lastY < UPPER_BND && 1613 lastY > LOWER_BND) 1614 { 1615 if (skip) { 1616 tCoords[0] = closeCoord[0] = lastX; 1617 tCoords[1] = closeCoord[1] = lastY; 1618 subpathStarted = JNI_TRUE; 1619 skip = JNI_FALSE; 1620 } else { 1621 if (tCoords[2] < UPPER_BND && 1622 tCoords[2] > LOWER_BND && 1623 tCoords[3] < UPPER_BND && 1624 tCoords[3] > LOWER_BND) 1625 { 1626 ProcessQuad(hnd, tCoords, pixelInfo); 1627 } else { 1628 ProcessLine(hnd, tCoords, 1629 tCoords + 4, pixelInfo); 1630 } 1631 tCoords[0] = lastX; 1632 tCoords[1] = lastY; 1633 } 1634 } 1635 } else { 1636 return JNI_FALSE; 1637 } 1638 break; 1639 case java_awt_geom_PathIterator_SEG_CUBICTO: 1640 if (index + 6 <= maxCoords) { 1641 tCoords[2] = coords[index++] + transXf; 1642 tCoords[3] = coords[index++] + transYf; 1643 tCoords[4] = coords[index++] + transXf; 1644 tCoords[5] = coords[index++] + transYf; 1645 lastX = tCoords[6] = coords[index++] + transXf; 1646 lastY = tCoords[7] = coords[index++] + transYf; 1647 1648 /* Checking SEG_CUBICTO coordinates if they are out of the 1649 * [LOWER_BND, UPPER_BND] range. This check also handles 1650 * NaN and Infinity values. Ignoring current path segment 1651 * in case of invalid endpoints's data. Equivalent to 1652 * the SEG_LINETO if endpoint coordinates are valid but 1653 * there are invalid data among other coordinates 1654 */ 1655 1656 if (lastX < UPPER_BND && 1657 lastX > LOWER_BND && 1658 lastY < UPPER_BND && 1659 lastY > LOWER_BND) 1660 { 1661 if (skip) { 1662 tCoords[0] = closeCoord[0] = tCoords[6]; 1663 tCoords[1] = closeCoord[1] = tCoords[7]; 1664 subpathStarted = JNI_TRUE; 1665 skip = JNI_FALSE; 1666 } else { 1667 if (tCoords[2] < UPPER_BND && 1668 tCoords[2] > LOWER_BND && 1669 tCoords[3] < UPPER_BND && 1670 tCoords[3] > LOWER_BND && 1671 tCoords[4] < UPPER_BND && 1672 tCoords[4] > LOWER_BND && 1673 tCoords[5] < UPPER_BND && 1674 tCoords[5] > LOWER_BND) 1675 { 1676 ProcessCubic(hnd, tCoords, pixelInfo); 1677 } else { 1678 ProcessLine(hnd, tCoords, tCoords + 6, 1679 pixelInfo); 1680 } 1681 tCoords[0] = lastX; 1682 tCoords[1] = lastY; 1683 } 1684 } 1685 } else { 1686 return JNI_FALSE; 1687 } 1688 break; 1689 case java_awt_geom_PathIterator_SEG_CLOSE: 1690 if (subpathStarted && !skip) { 1691 skip = JNI_FALSE; 1692 if (tCoords[0] != closeCoord[0] || 1693 tCoords[1] != closeCoord[1]) 1694 { 1695 ProcessLine(hnd, tCoords, closeCoord, pixelInfo); 1696 /* Storing last path's point for using in 1697 * following segments without initial moveTo 1698 */ 1699 tCoords[0] = closeCoord[0]; 1700 tCoords[1] = closeCoord[1]; 1701 } 1702 1703 hnd->pProcessEndSubPath(hnd); 1704 } 1705 1706 break; 1707 } 1708 } 1709 1710 /* Performing closing of the unclosed segments */ 1711 if (subpathStarted & !skip) { 1712 if (hnd->clipMode == PH_MODE_FILL_CLIP) { 1713 if (tCoords[0] != closeCoord[0] || 1714 tCoords[1] != closeCoord[1]) 1715 { 1716 ProcessLine(hnd, tCoords, closeCoord, 1717 pixelInfo); 1718 } 1719 } 1720 hnd->pProcessEndSubPath(hnd); 1721 } 1722 1723 return JNI_TRUE; 1724 } 1725 1726 /* TODO Add checking of the result of the malloc/realloc functions to handle 1727 * out of memory error and don't leak earlier allocated data 1728 */ 1729 1730 1731 #define ALLOC(ptr, type, n) \ 1732 ptr = (type *)malloc((n)*sizeof(type)) 1733 #define REALLOC(ptr, type, n) \ 1734 ptr = (type *)realloc(ptr, (n)*sizeof(type)) 1735 1736 1737 struct _Edge; 1738 1739 typedef struct _Point { 1740 jint x; 1741 jint y; 1742 jboolean lastPoint; 1743 struct _Point* prev; 1744 struct _Point* next; 1745 struct _Point* nextByY; 1746 jboolean endSL; 1747 struct _Edge* edge; 1748 } Point; 1749 1750 1751 typedef struct _Edge { 1752 jint x; 1753 jint dx; 1754 Point* p; 1755 jint dir; 1756 struct _Edge* prev; 1757 struct _Edge* next; 1758 } Edge; 1759 1760 /* Size of the default buffer in the FillData structure. This buffer is 1761 * replaced with heap allocated in case of large paths. 1762 */ 1763 #define DF_MAX_POINT 256 1764 1765 /* Following structure accumulates points of the non-continuous flattened 1766 * path during iteration through the origin path's segments . The end 1767 * of the each subpath is marked as lastPoint flag set at the last point 1768 */ 1769 1770 typedef struct { 1771 Point *plgPnts; 1772 Point dfPlgPnts[DF_MAX_POINT]; 1773 jint plgSize; 1774 jint plgMax; 1775 jint plgYMin; 1776 jint plgYMax; 1777 } FillData; 1778 1779 #define FD_INIT(PTR) \ 1780 do { \ 1781 (PTR)->plgPnts = (PTR)->dfPlgPnts; \ 1782 (PTR)->plgSize = 0; \ 1783 (PTR)->plgMax = DF_MAX_POINT; \ 1784 } while(0) 1785 1786 #define FD_ADD_POINT(PTR, X, Y, LASTPT) \ 1787 do { \ 1788 Point* _pnts = (PTR)->plgPnts; \ 1789 jint _size = (PTR)->plgSize; \ 1790 if (_size >= (PTR)->plgMax) { \ 1791 jint newMax = (PTR)->plgMax*2; \ 1792 if ((PTR)->plgPnts == (PTR)->dfPlgPnts) { \ 1793 (PTR)->plgPnts = (Point*)malloc(newMax*sizeof(Point)); \ 1794 memcpy((PTR)->plgPnts, _pnts, _size*sizeof(Point)); \ 1795 } else { \ 1796 (PTR)->plgPnts = (Point*)realloc( \ 1797 _pnts, newMax*sizeof(Point)); \ 1798 } \ 1799 _pnts = (PTR)->plgPnts; \ 1800 (PTR)->plgMax = newMax; \ 1801 } \ 1802 _pnts += _size; \ 1803 _pnts->x = X; \ 1804 _pnts->y = Y; \ 1805 _pnts->lastPoint = LASTPT; \ 1806 if (_size) { \ 1807 if ((PTR)->plgYMin > Y) (PTR)->plgYMin = Y; \ 1808 if ((PTR)->plgYMax < Y) (PTR)->plgYMax = Y; \ 1809 } else { \ 1810 (PTR)->plgYMin = Y; \ 1811 (PTR)->plgYMax = Y; \ 1812 } \ 1813 (PTR)->plgSize = _size + 1; \ 1814 } while(0) 1815 1816 1817 #define FD_FREE_POINTS(PTR) \ 1818 do { \ 1819 if ((PTR)->plgPnts != (PTR)->dfPlgPnts) { \ 1820 free((PTR)->plgPnts); \ 1821 } \ 1822 } while(0) 1823 1824 #define FD_IS_EMPTY(PTR) (!((PTR)->plgSize)) 1825 1826 #define FD_IS_ENDED(PTR) ((PTR)->plgPnts[(PTR)->plgSize - 1].lastPoint) 1827 1828 #define FD_SET_ENDED(PTR) \ 1829 do { \ 1830 (PTR)->plgPnts[(PTR)->plgSize - 1].lastPoint = JNI_TRUE; \ 1831 } while(0) 1832 1833 #define PFD(HND) ((FillData*)(HND)->pData) 1834 1835 /* Bubble sorting in the ascending order of the linked list. This 1836 * implementation stops processing the list if there were no changes during the 1837 * previous pass. 1838 * 1839 * LIST - ptr to the ptr to the first element of the list 1840 * ETYPE - type of the element in the list 1841 * NEXT - accessor to the next field in the list element 1842 * GET_LKEY - accessor to the key of the list element 1843 */ 1844 #define LBUBBLE_SORT(LIST, ETYPE, NEXT, GET_LKEY) \ 1845 do { \ 1846 ETYPE *p, *q, *r, *s = NULL, *temp ; \ 1847 jint wasSwap = 1; \ 1848 /* r precedes p and s points to the node up to which comparisons \ 1849 * are to be made */ \ 1850 while ( s != NEXT(*LIST) && wasSwap) { \ 1851 r = p = *LIST; \ 1852 q = NEXT(p); \ 1853 wasSwap = 0; \ 1854 while ( p != s ) { \ 1855 if (GET_LKEY(p) >= GET_LKEY(q)) { \ 1856 wasSwap = 1; \ 1857 if ( p == *LIST ) { \ 1858 temp = NEXT(q); \ 1859 NEXT(q) = p ; \ 1860 NEXT(p) = temp ; \ 1861 *LIST = q ; \ 1862 r = q ; \ 1863 } else { \ 1864 temp = NEXT(q); \ 1865 NEXT(q) = p ; \ 1866 NEXT(p) = temp ; \ 1867 NEXT(r) = q ; \ 1868 r = q ; \ 1869 } \ 1870 } else { \ 1871 r = p ; \ 1872 p = NEXT(p); \ 1873 } \ 1874 q = NEXT(p); \ 1875 if ( q == s ) s = p ; \ 1876 } \ 1877 } \ 1878 } while(0); 1879 1880 /* Accessors for the Edge structure to work with LBUBBLE_SORT */ 1881 #define GET_ACTIVE_KEY(a) (a->x) 1882 #define GET_ACTIVE_NEXT(a) ((a)->next) 1883 1884 /* TODO: Implement stack/heap allocation technique for active edges 1885 */ 1886 #define DELETE_ACTIVE(head,pnt) \ 1887 do { \ 1888 Edge *prevp = pnt->prev; \ 1889 Edge *nextp = pnt->next; \ 1890 if (prevp) { \ 1891 prevp->next = nextp; \ 1892 } else { \ 1893 head = nextp; \ 1894 } \ 1895 if (nextp) { \ 1896 nextp->prev = prevp; \ 1897 } \ 1898 } while(0); 1899 1900 #define INSERT_ACTIVE(head,pnt,cy) \ 1901 do { \ 1902 Point *np = pnt->next; \ 1903 Edge *ne = active + nact; \ 1904 if (pnt->y == np->y) { \ 1905 /* Skipping horizontal segments */ \ 1906 break; \ 1907 } else { \ 1908 jint dX = np->x - pnt->x; \ 1909 jint dY = np->y - pnt->y; \ 1910 jint dy; \ 1911 if (pnt->y < np->y) { \ 1912 ne->dir = -1; \ 1913 ne->p = pnt; \ 1914 ne->x = pnt->x; \ 1915 dy = cy - pnt->y; \ 1916 } else { /* pnt->y > np->y */ \ 1917 ne->dir = 1; \ 1918 ne->p = np; \ 1919 ne->x = np->x; \ 1920 dy = cy - np->y; \ 1921 } \ 1922 \ 1923 /* We need to worry only about dX because dY is in */\ 1924 /* denominator and abs(dy) < MDP_MULT (cy is a first */\ 1925 /* scanline of the scan converted segment and we subtract */\ 1926 /* y coordinate of the nearest segment's end from it to */\ 1927 /* obtain dy) */\ 1928 if (ABS32(dX) > CALC_BND) { \ 1929 ne->dx = (jint)((((jdouble)dX)*MDP_MULT)/dY); \ 1930 ne->x += (jint)((((jdouble)dX)*dy)/dY); \ 1931 } else { \ 1932 ne->dx = ((dX)<<MDP_PREC)/dY; \ 1933 ne->x += (dX*dy)/dY; \ 1934 } \ 1935 } \ 1936 ne->next = head; \ 1937 ne->prev = NULL; \ 1938 if (head) { \ 1939 head->prev = ne; \ 1940 } \ 1941 head = active + nact; \ 1942 pnt->edge = head; \ 1943 nact++; \ 1944 } while(0); 1945 1946 void FillPolygon(ProcessHandler* hnd, 1947 jint fillRule) { 1948 jint k, y, xl, xr; 1949 jint drawing; 1950 Edge* activeList, *active; 1951 Edge* curEdge, *prevEdge; 1952 jint nact; 1953 jint n; 1954 Point* pt, *curpt, *ept; 1955 Point** yHash; 1956 Point** curHash; 1957 jint rightBnd = hnd->dhnd->xMax - 1; 1958 FillData* pfd = (FillData*)(hnd->pData); 1959 jint yMin = pfd->plgYMin; 1960 jint yMax = pfd->plgYMax; 1961 jint hashSize = ((yMax - yMin)>>MDP_PREC) + 4; 1962 1963 /* Because of support of the KEY_STROKE_CONTROL hint we are performing 1964 * shift of the coordinates at the higher level 1965 */ 1966 jint hashOffset = ((yMin - 1) & MDP_W_MASK); 1967 1968 // TODO creating lists using fake first element to avoid special casing of 1969 // the first element in the list (which otherwise should be performed in each 1970 // list operation) 1971 1972 /* Winding counter */ 1973 jint counter; 1974 1975 /* Calculating mask to be applied to the winding counter */ 1976 jint counterMask = 1977 (fillRule == java_awt_geom_PathIterator_WIND_NON_ZERO)? -1:1; 1978 pt = pfd->plgPnts; 1979 n = pfd->plgSize; 1980 1981 if (n <=1) return; 1982 1983 ALLOC(yHash, Point*, hashSize); 1984 for (k = 0; k < hashSize; k++) { 1985 yHash[k] = NULL; 1986 } 1987 1988 ALLOC(active, Edge, n); 1989 1990 /* Creating double linked list (prev, next links) describing path order and 1991 * hash table with points which fall between scanlines. nextByY link is 1992 * used for the points which are between same scanlines. Scanlines are 1993 * passed through the centers of the pixels. 1994 */ 1995 curpt = pt; 1996 curpt->prev = NULL; 1997 ept = pt + n - 1; 1998 for (curpt = pt; curpt != ept; curpt++) { 1999 Point* nextpt = curpt + 1; 2000 curHash = yHash + ((curpt->y - hashOffset - 1) >> MDP_PREC); 2001 curpt->nextByY = *curHash; 2002 *curHash = curpt; 2003 curpt->next = nextpt; 2004 nextpt->prev = curpt; 2005 curpt->edge = NULL; 2006 } 2007 2008 curHash = yHash + ((ept->y - hashOffset - 1) >> MDP_PREC); 2009 ept->nextByY = *curHash; 2010 *curHash = ept; 2011 ept->next = NULL; 2012 ept->edge = NULL; 2013 nact = 0; 2014 2015 activeList = NULL; 2016 for (y=hashOffset + MDP_MULT,k = 0; 2017 y<=yMax && k < hashSize; y += MDP_MULT, k++) 2018 { 2019 for(pt = yHash[k];pt; pt=pt->nextByY) { 2020 /* pt->y should be inside hashed interval 2021 * assert(y-MDP_MULT <= pt->y && pt->y < y); 2022 */ 2023 if (pt->prev && !pt->prev->lastPoint) { 2024 if (pt->prev->edge && pt->prev->y <= y) { 2025 DELETE_ACTIVE(activeList, pt->prev->edge); 2026 pt->prev->edge = NULL; 2027 } else if (pt->prev->y > y) { 2028 INSERT_ACTIVE(activeList, pt->prev, y); 2029 } 2030 } 2031 2032 if (!pt->lastPoint && pt->next) { 2033 if (pt->edge && pt->next->y <= y) { 2034 DELETE_ACTIVE(activeList, pt->edge); 2035 pt->edge = NULL; 2036 } else if (pt->next->y > y) { 2037 INSERT_ACTIVE(activeList, pt, y); 2038 } 2039 } 2040 } 2041 2042 if (!activeList) continue; 2043 2044 /* We could not use O(N) Radix sort here because in most cases list of 2045 * edges almost sorted. So, bubble sort (O(N^2))is working much 2046 * better. Note, in case of array of edges Shell sort is more 2047 * efficient. 2048 */ 2049 LBUBBLE_SORT((&activeList), Edge, GET_ACTIVE_NEXT, GET_ACTIVE_KEY); 2050 2051 /* Correction of the back links in the double linked edge list */ 2052 curEdge=activeList; 2053 prevEdge = NULL; 2054 while (curEdge) { 2055 curEdge->prev = prevEdge; 2056 prevEdge = curEdge; 2057 curEdge = curEdge->next; 2058 } 2059 2060 xl = xr = hnd->dhnd->xMin; 2061 curEdge = activeList; 2062 counter = 0; 2063 drawing = 0; 2064 for(;curEdge; curEdge = curEdge->next) { 2065 counter += curEdge->dir; 2066 if ((counter & counterMask) && !drawing) { 2067 xl = (curEdge->x + MDP_MULT - 1)>>MDP_PREC; 2068 drawing = 1; 2069 } 2070 2071 if (!(counter & counterMask) && drawing) { 2072 xr = (curEdge->x - 1)>>MDP_PREC; 2073 if (xl <= xr) { 2074 hnd->dhnd->pDrawScanline(hnd->dhnd, xl, xr, y >> MDP_PREC); 2075 } 2076 drawing = 0; 2077 } 2078 2079 curEdge->x += curEdge->dx; 2080 } 2081 2082 /* Performing drawing till the right boundary (for correct rendering 2083 * shapes clipped at the right side) 2084 */ 2085 if (drawing && xl <= rightBnd) { 2086 hnd->dhnd->pDrawScanline(hnd->dhnd, xl, rightBnd, y >> MDP_PREC); 2087 } 2088 } 2089 free(active); 2090 free(yHash); 2091 } 2092 2093 2094 2095 void StoreFixedLine(ProcessHandler* hnd,jint x1,jint y1,jint x2,jint y2, 2096 jint* pixelInfo,jboolean checkBounds, 2097 jboolean endSubPath) { 2098 FillData* pfd; 2099 jint outXMin, outXMax, outYMin, outYMax; 2100 jint x3, y3, res; 2101 2102 /* There is no need to round line coordinates to the forward differencing 2103 * precision anymore. Such a rounding was used for preventing the curve go 2104 * out the endpoint (this sometimes does not help). The problem was fixed 2105 * in the forward differencing loops. 2106 */ 2107 2108 if (checkBounds) { 2109 jboolean lastClipped = JNI_FALSE; 2110 2111 /* This function is used only for filling shapes, so there is no 2112 * check for the type of clipping 2113 */ 2114 outXMin = (jint)(hnd->dhnd->xMinf * MDP_MULT); 2115 outXMax = (jint)(hnd->dhnd->xMaxf * MDP_MULT); 2116 outYMin = (jint)(hnd->dhnd->yMinf * MDP_MULT); 2117 outYMax = (jint)(hnd->dhnd->yMaxf * MDP_MULT); 2118 2119 TESTANDCLIP(outYMin, outYMax, y1, x1, y2, x2, jint, res); 2120 if (res == CRES_INVISIBLE) return; 2121 TESTANDCLIP(outYMin, outYMax, y2, x2, y1, x1, jint, res); 2122 if (res == CRES_INVISIBLE) return; 2123 lastClipped = IS_CLIPPED(res); 2124 2125 /* Clamping starting from first vertex of the processed segment */ 2126 CLIPCLAMP(outXMin, outXMax, x1, y1, x2, y2, x3, y3, jint, res); 2127 2128 /* Clamping only by left boundary */ 2129 if (res == CRES_MIN_CLIPPED) { 2130 StoreFixedLine(hnd, x3, y3, x1, y1, pixelInfo, 2131 JNI_FALSE, lastClipped); 2132 2133 } else if (res == CRES_INVISIBLE) { 2134 return; 2135 } 2136 2137 /* Clamping starting from last vertex of the processed segment */ 2138 CLIPCLAMP(outXMin, outXMax, x2, y2, x1, y1, x3, y3, jint, res); 2139 2140 /* Checking if there was a clip by right boundary */ 2141 lastClipped = lastClipped || (res == CRES_MAX_CLIPPED); 2142 2143 StoreFixedLine(hnd, x1, y1, x2, y2, pixelInfo, 2144 JNI_FALSE, lastClipped); 2145 2146 /* Clamping only by left boundary */ 2147 if (res == CRES_MIN_CLIPPED) { 2148 StoreFixedLine(hnd, x2, y2, x3, y3, pixelInfo, 2149 JNI_FALSE, lastClipped); 2150 } 2151 2152 return; 2153 } 2154 pfd = (FillData*)(hnd->pData); 2155 2156 /* Adding first point of the line only in case of empty or just finished 2157 * path 2158 */ 2159 if (FD_IS_EMPTY(pfd) || FD_IS_ENDED(pfd)) { 2160 FD_ADD_POINT(pfd, x1, y1, JNI_FALSE); 2161 } 2162 2163 FD_ADD_POINT(pfd, x2, y2, JNI_FALSE); 2164 2165 if (endSubPath) { 2166 FD_SET_ENDED(pfd); 2167 } 2168 } 2169 2170 2171 static void endSubPath(ProcessHandler* hnd) { 2172 FillData* pfd = (FillData*)(hnd->pData); 2173 if (!FD_IS_EMPTY(pfd)) { 2174 FD_SET_ENDED(pfd); 2175 } 2176 } 2177 2178 static void stubEndSubPath(ProcessHandler* hnd) { 2179 } 2180 2181 JNIEXPORT jboolean JNICALL 2182 doFillPath(DrawHandler* dhnd, 2183 jint transX, jint transY, 2184 jfloat* coords, jint maxCoords, 2185 jbyte* types, jint numTypes, 2186 PHStroke stroke, jint fillRule) 2187 { 2188 jint res; 2189 2190 FillData fillData; 2191 2192 ProcessHandler hnd = 2193 { 2194 &StoreFixedLine, 2195 &endSubPath, 2196 NULL, 2197 PH_STROKE_DEFAULT, 2198 PH_MODE_FILL_CLIP, 2199 NULL 2200 }; 2201 2202 /* Initialization of the following fields in the declaration of the hnd 2203 * above causes warnings on sun studio compiler with -xc99=%none option 2204 * applied (this option means compliance with C90 standard instead of C99) 2205 */ 2206 hnd.dhnd = dhnd; 2207 hnd.pData = &fillData; 2208 hnd.stroke = stroke; 2209 2210 FD_INIT(&fillData); 2211 res = ProcessPath(&hnd, (jfloat)transX, (jfloat)transY, 2212 coords, maxCoords, types, numTypes); 2213 if (!res) { 2214 FD_FREE_POINTS(&fillData); 2215 return JNI_FALSE; 2216 } 2217 FillPolygon(&hnd, fillRule); 2218 FD_FREE_POINTS(&fillData); 2219 return JNI_TRUE; 2220 } 2221 2222 JNIEXPORT jboolean JNICALL 2223 doDrawPath(DrawHandler* dhnd, 2224 void (*pProcessEndSubPath)(ProcessHandler*), 2225 jint transX, jint transY, 2226 jfloat* coords, jint maxCoords, 2227 jbyte* types, jint numTypes, PHStroke stroke) 2228 { 2229 ProcessHandler hnd = 2230 { 2231 &ProcessFixedLine, 2232 NULL, 2233 NULL, 2234 PH_STROKE_DEFAULT, 2235 PH_MODE_DRAW_CLIP, 2236 NULL 2237 }; 2238 2239 /* Initialization of the following fields in the declaration of the hnd 2240 * above causes warnings on sun studio compiler with -xc99=%none option 2241 * applied (this option means compliance with C90 standard instead of C99) 2242 */ 2243 hnd.dhnd = dhnd; 2244 hnd.stroke = stroke; 2245 2246 hnd.pProcessEndSubPath = (pProcessEndSubPath == NULL)? 2247 stubEndSubPath : pProcessEndSubPath; 2248 return ProcessPath(&hnd, (jfloat)transX, (jfloat)transY, coords, maxCoords, 2249 types, numTypes); 2250 }