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