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