1 /* 2 * Copyright (c) 2007, 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.marlin; 27 28 import java.util.Arrays; 29 import sun.awt.geom.PathConsumer2D; 30 import sun.java2d.marlin.stats.Histogram; 31 import sun.java2d.marlin.stats.StatLong; 32 33 final class Helpers implements MarlinConst { 34 35 private Helpers() { 36 throw new Error("This is a non instantiable class"); 37 } 38 39 static boolean within(final float x, final float y, final float err) { 40 final float d = y - x; 41 return (d <= err && d >= -err); 42 } 43 44 static boolean within(final double x, final double y, final double err) { 45 final double d = y - x; 46 return (d <= err && d >= -err); 47 } 48 49 static float evalCubic(final float a, final float b, 50 final float c, final float d, 51 final float t) 52 { 53 return t * (t * (t * a + b) + c) + d; 54 } 55 56 static float evalQuad(final float a, final float b, 57 final float c, final float t) 58 { 59 return t * (t * a + b) + c; 60 } 61 62 static int quadraticRoots(final float a, final float b, final float c, 63 final float[] zeroes, final int off) 64 { 65 int ret = off; 66 if (a != 0.0f) { 67 final float dis = b*b - 4.0f * a * c; 68 if (dis > 0.0f) { 69 final float sqrtDis = (float) Math.sqrt(dis); 70 // depending on the sign of b we use a slightly different 71 // algorithm than the traditional one to find one of the roots 72 // so we can avoid adding numbers of different signs (which 73 // might result in loss of precision). 74 if (b >= 0.0f) { 75 zeroes[ret++] = (2.0f * c) / (-b - sqrtDis); 76 zeroes[ret++] = (-b - sqrtDis) / (2.0f * a); 77 } else { 78 zeroes[ret++] = (-b + sqrtDis) / (2.0f * a); 79 zeroes[ret++] = (2.0f * c) / (-b + sqrtDis); 80 } 81 } else if (dis == 0.0f) { 82 zeroes[ret++] = -b / (2.0f * a); 83 } 84 } else if (b != 0.0f) { 85 zeroes[ret++] = -c / b; 86 } 87 return ret - off; 88 } 89 90 // find the roots of g(t) = d*t^3 + a*t^2 + b*t + c in [A,B) 91 static int cubicRootsInAB(final float d0, float a0, float b0, float c0, 92 final float[] pts, final int off, 93 final float A, final float B) 94 { 95 if (d0 == 0.0f) { 96 final int num = quadraticRoots(a0, b0, c0, pts, off); 97 return filterOutNotInAB(pts, off, num, A, B) - off; 98 } 99 // From Graphics Gems: 100 // https://github.com/erich666/GraphicsGems/blob/master/gems/Roots3And4.c 101 // (also from awt.geom.CubicCurve2D. But here we don't need as 102 // much accuracy and we don't want to create arrays so we use 103 // our own customized version). 104 105 // normal form: x^3 + ax^2 + bx + c = 0 106 107 // 2018.1: Need double precision if d is very small (flat curve) ! 108 /* 109 * TODO: cleanup all that code after reading Roots3And4.c 110 */ 111 final double a = ((double)a0) / d0; 112 final double b = ((double)b0) / d0; 113 final double c = ((double)c0) / d0; 114 115 // substitute x = y - A/3 to eliminate quadratic term: 116 // x^3 +Px + Q = 0 117 // 118 // Since we actually need P/3 and Q/2 for all of the 119 // calculations that follow, we will calculate 120 // p = P/3 121 // q = Q/2 122 // instead and use those values for simplicity of the code. 123 final double sub = (1.0d / 3.0d) * a; 124 final double sq_A = a * a; 125 final double p = (1.0d / 3.0d) * ((-1.0d / 3.0d) * sq_A + b); 126 final double q = (1.0d / 2.0d) * ((2.0d / 27.0d) * a * sq_A - sub * b + c); 127 128 // use Cardano's formula 129 130 final double cb_p = p * p * p; 131 final double D = q * q + cb_p; 132 133 int num; 134 if (D < 0.0d) { 135 // see: http://en.wikipedia.org/wiki/Cubic_function#Trigonometric_.28and_hyperbolic.29_method 136 final double phi = (1.0d / 3.0d) * Math.acos(-q / Math.sqrt(-cb_p)); 137 final double t = 2.0d * Math.sqrt(-p); 138 139 pts[off ] = (float) ( t * Math.cos(phi) - sub); 140 pts[off + 1] = (float) (-t * Math.cos(phi + (Math.PI / 3.0d)) - sub); 141 pts[off + 2] = (float) (-t * Math.cos(phi - (Math.PI / 3.0d)) - sub); 142 num = 3; 143 } else { 144 final double sqrt_D = Math.sqrt(D); 145 final double u = Math.cbrt(sqrt_D - q); 146 final double v = - Math.cbrt(sqrt_D + q); 147 148 pts[off ] = (float) (u + v - sub); 149 num = 1; 150 151 if (within(D, 0.0d, 1e-8d)) { 152 pts[off + 1] = (float)((-1.0d / 2.0d) * (u + v) - sub); 153 num = 2; 154 } 155 } 156 157 return filterOutNotInAB(pts, off, num, A, B) - off; 158 } 159 160 // returns the index 1 past the last valid element remaining after filtering 161 static int filterOutNotInAB(final float[] nums, final int off, final int len, 162 final float a, final float b) 163 { 164 int ret = off; 165 for (int i = off, end = off + len; i < end; i++) { 166 if (nums[i] >= a && nums[i] < b) { 167 nums[ret++] = nums[i]; 168 } 169 } 170 return ret; 171 } 172 173 static float fastLineLen(final float x0, final float y0, 174 final float x1, final float y1) 175 { 176 final float dx = x1 - x0; 177 final float dy = y1 - y0; 178 179 // use manhattan norm: 180 return Math.abs(dx) + Math.abs(dy); 181 } 182 183 static float linelen(final float x0, final float y0, 184 final float x1, final float y1) 185 { 186 final float dx = x1 - x0; 187 final float dy = y1 - y0; 188 return (float) Math.sqrt(dx * dx + dy * dy); 189 } 190 191 static float fastQuadLen(final float x0, final float y0, 192 final float x1, final float y1, 193 final float x2, final float y2) 194 { 195 final float dx1 = x1 - x0; 196 final float dx2 = x2 - x1; 197 final float dy1 = y1 - y0; 198 final float dy2 = y2 - y1; 199 200 // use manhattan norm: 201 return Math.abs(dx1) + Math.abs(dx2) 202 + Math.abs(dy1) + Math.abs(dy2); 203 } 204 205 static float quadlen(final float x0, final float y0, 206 final float x1, final float y1, 207 final float x2, final float y2) 208 { 209 return (linelen(x0, y0, x1, y1) 210 + linelen(x1, y1, x2, y2) 211 + linelen(x0, y0, x2, y2)) / 2.0f; 212 } 213 214 215 static float fastCurvelen(final float x0, final float y0, 216 final float x1, final float y1, 217 final float x2, final float y2, 218 final float x3, final float y3) 219 { 220 final float dx1 = x1 - x0; 221 final float dx2 = x2 - x1; 222 final float dx3 = x3 - x2; 223 final float dy1 = y1 - y0; 224 final float dy2 = y2 - y1; 225 final float dy3 = y3 - y2; 226 227 // use manhattan norm: 228 return Math.abs(dx1) + Math.abs(dx2) + Math.abs(dx3) 229 + Math.abs(dy1) + Math.abs(dy2) + Math.abs(dy3); 230 } 231 232 static float curvelen(final float x0, final float y0, 233 final float x1, final float y1, 234 final float x2, final float y2, 235 final float x3, final float y3) 236 { 237 return (linelen(x0, y0, x1, y1) 238 + linelen(x1, y1, x2, y2) 239 + linelen(x2, y2, x3, y3) 240 + linelen(x0, y0, x3, y3)) / 2.0f; 241 } 242 243 // finds values of t where the curve in pts should be subdivided in order 244 // to get good offset curves a distance of w away from the middle curve. 245 // Stores the points in ts, and returns how many of them there were. 246 static int findSubdivPoints(final Curve c, final float[] pts, 247 final float[] ts, final int type, 248 final float w2) 249 { 250 final float x12 = pts[2] - pts[0]; 251 final float y12 = pts[3] - pts[1]; 252 // if the curve is already parallel to either axis we gain nothing 253 // from rotating it. 254 if ((y12 != 0.0f && x12 != 0.0f)) { 255 // we rotate it so that the first vector in the control polygon is 256 // parallel to the x-axis. This will ensure that rotated quarter 257 // circles won't be subdivided. 258 final float hypot = (float)Math.sqrt(x12 * x12 + y12 * y12); 259 final float cos = x12 / hypot; 260 final float sin = y12 / hypot; 261 final float x1 = cos * pts[0] + sin * pts[1]; 262 final float y1 = cos * pts[1] - sin * pts[0]; 263 final float x2 = cos * pts[2] + sin * pts[3]; 264 final float y2 = cos * pts[3] - sin * pts[2]; 265 final float x3 = cos * pts[4] + sin * pts[5]; 266 final float y3 = cos * pts[5] - sin * pts[4]; 267 268 switch(type) { 269 case 8: 270 final float x4 = cos * pts[6] + sin * pts[7]; 271 final float y4 = cos * pts[7] - sin * pts[6]; 272 c.set(x1, y1, x2, y2, x3, y3, x4, y4); 273 break; 274 case 6: 275 c.set(x1, y1, x2, y2, x3, y3); 276 break; 277 default: 278 } 279 } else { 280 c.set(pts, type); 281 } 282 283 int ret = 0; 284 // we subdivide at values of t such that the remaining rotated 285 // curves are monotonic in x and y. 286 ret += c.dxRoots(ts, ret); 287 ret += c.dyRoots(ts, ret); 288 289 // subdivide at inflection points. 290 if (type == 8) { 291 // quadratic curves can't have inflection points 292 ret += c.infPoints(ts, ret); 293 } 294 295 // now we must subdivide at points where one of the offset curves will have 296 // a cusp. This happens at ts where the radius of curvature is equal to w. 297 ret += c.rootsOfROCMinusW(ts, ret, w2, 0.0001f); 298 299 ret = filterOutNotInAB(ts, 0, ret, 0.0001f, 0.9999f); 300 isort(ts, ret); 301 return ret; 302 } 303 304 // finds values of t where the curve in pts should be subdivided in order 305 // to get intersections with the given clip rectangle. 306 // Stores the points in ts, and returns how many of them there were. 307 static int findClipPoints(final Curve curve, final float[] pts, 308 final float[] ts, final int type, 309 final int outCodeOR, 310 final float[] clipRect) 311 { 312 curve.set(pts, type); 313 314 // clip rectangle (ymin, ymax, xmin, xmax) 315 int ret = 0; 316 317 if ((outCodeOR & OUTCODE_LEFT) != 0) { 318 ret += curve.xPoints(ts, ret, clipRect[2]); 319 } 320 if ((outCodeOR & OUTCODE_RIGHT) != 0) { 321 ret += curve.xPoints(ts, ret, clipRect[3]); 322 } 323 if ((outCodeOR & OUTCODE_TOP) != 0) { 324 ret += curve.yPoints(ts, ret, clipRect[0]); 325 } 326 if ((outCodeOR & OUTCODE_BOTTOM) != 0) { 327 ret += curve.yPoints(ts, ret, clipRect[1]); 328 } 329 isort(ts, ret); 330 return ret; 331 } 332 333 static void subdivide(final float[] src, 334 final float[] left, final float[] right, 335 final int type) 336 { 337 switch(type) { 338 case 8: 339 subdivideCubic(src, left, right); 340 return; 341 case 6: 342 subdivideQuad(src, left, right); 343 return; 344 default: 345 throw new InternalError("Unsupported curve type"); 346 } 347 } 348 349 static void isort(final float[] a, final int len) { 350 for (int i = 1, j; i < len; i++) { 351 final float ai = a[i]; 352 j = i - 1; 353 for (; j >= 0 && a[j] > ai; j--) { 354 a[j + 1] = a[j]; 355 } 356 a[j + 1] = ai; 357 } 358 } 359 360 // Most of these are copied from classes in java.awt.geom because we need 361 // both single and double precision variants of these functions, and Line2D, 362 // CubicCurve2D, QuadCurve2D don't provide them. 363 /** 364 * Subdivides the cubic curve specified by the coordinates 365 * stored in the <code>src</code> array at indices <code>srcoff</code> 366 * through (<code>srcoff</code> + 7) and stores the 367 * resulting two subdivided curves into the two result arrays at the 368 * corresponding indices. 369 * Either or both of the <code>left</code> and <code>right</code> 370 * arrays may be <code>null</code> or a reference to the same array 371 * as the <code>src</code> array. 372 * Note that the last point in the first subdivided curve is the 373 * same as the first point in the second subdivided curve. Thus, 374 * it is possible to pass the same array for <code>left</code> 375 * and <code>right</code> and to use offsets, such as <code>rightoff</code> 376 * equals (<code>leftoff</code> + 6), in order 377 * to avoid allocating extra storage for this common point. 378 * @param src the array holding the coordinates for the source curve 379 * @param left the array for storing the coordinates for the first 380 * half of the subdivided curve 381 * @param right the array for storing the coordinates for the second 382 * half of the subdivided curve 383 * @since 1.7 384 */ 385 static void subdivideCubic(final float[] src, 386 final float[] left, 387 final float[] right) 388 { 389 float x1 = src[0]; 390 float y1 = src[1]; 391 float cx1 = src[2]; 392 float cy1 = src[3]; 393 float cx2 = src[4]; 394 float cy2 = src[5]; 395 float x2 = src[6]; 396 float y2 = src[7]; 397 398 left[0] = x1; 399 left[1] = y1; 400 401 right[6] = x2; 402 right[7] = y2; 403 404 x1 = (x1 + cx1) / 2.0f; 405 y1 = (y1 + cy1) / 2.0f; 406 x2 = (x2 + cx2) / 2.0f; 407 y2 = (y2 + cy2) / 2.0f; 408 409 float cx = (cx1 + cx2) / 2.0f; 410 float cy = (cy1 + cy2) / 2.0f; 411 412 cx1 = (x1 + cx) / 2.0f; 413 cy1 = (y1 + cy) / 2.0f; 414 cx2 = (x2 + cx) / 2.0f; 415 cy2 = (y2 + cy) / 2.0f; 416 cx = (cx1 + cx2) / 2.0f; 417 cy = (cy1 + cy2) / 2.0f; 418 419 left[2] = x1; 420 left[3] = y1; 421 left[4] = cx1; 422 left[5] = cy1; 423 left[6] = cx; 424 left[7] = cy; 425 426 right[0] = cx; 427 right[1] = cy; 428 right[2] = cx2; 429 right[3] = cy2; 430 right[4] = x2; 431 right[5] = y2; 432 } 433 434 static void subdivideCubicAt(final float t, 435 final float[] src, final int offS, 436 final float[] pts, final int offL, final int offR) 437 { 438 float x1 = src[offS ]; 439 float y1 = src[offS + 1]; 440 float cx1 = src[offS + 2]; 441 float cy1 = src[offS + 3]; 442 float cx2 = src[offS + 4]; 443 float cy2 = src[offS + 5]; 444 float x2 = src[offS + 6]; 445 float y2 = src[offS + 7]; 446 447 pts[offL ] = x1; 448 pts[offL + 1] = y1; 449 450 pts[offR + 6] = x2; 451 pts[offR + 7] = y2; 452 453 x1 = x1 + t * (cx1 - x1); 454 y1 = y1 + t * (cy1 - y1); 455 x2 = cx2 + t * (x2 - cx2); 456 y2 = cy2 + t * (y2 - cy2); 457 458 float cx = cx1 + t * (cx2 - cx1); 459 float cy = cy1 + t * (cy2 - cy1); 460 461 cx1 = x1 + t * (cx - x1); 462 cy1 = y1 + t * (cy - y1); 463 cx2 = cx + t * (x2 - cx); 464 cy2 = cy + t * (y2 - cy); 465 cx = cx1 + t * (cx2 - cx1); 466 cy = cy1 + t * (cy2 - cy1); 467 468 pts[offL + 2] = x1; 469 pts[offL + 3] = y1; 470 pts[offL + 4] = cx1; 471 pts[offL + 5] = cy1; 472 pts[offL + 6] = cx; 473 pts[offL + 7] = cy; 474 475 pts[offR ] = cx; 476 pts[offR + 1] = cy; 477 pts[offR + 2] = cx2; 478 pts[offR + 3] = cy2; 479 pts[offR + 4] = x2; 480 pts[offR + 5] = y2; 481 } 482 483 static void subdivideQuad(final float[] src, 484 final float[] left, 485 final float[] right) 486 { 487 float x1 = src[0]; 488 float y1 = src[1]; 489 float cx = src[2]; 490 float cy = src[3]; 491 float x2 = src[4]; 492 float y2 = src[5]; 493 494 left[0] = x1; 495 left[1] = y1; 496 497 right[4] = x2; 498 right[5] = y2; 499 500 x1 = (x1 + cx) / 2.0f; 501 y1 = (y1 + cy) / 2.0f; 502 x2 = (x2 + cx) / 2.0f; 503 y2 = (y2 + cy) / 2.0f; 504 cx = (x1 + x2) / 2.0f; 505 cy = (y1 + y2) / 2.0f; 506 507 left[2] = x1; 508 left[3] = y1; 509 left[4] = cx; 510 left[5] = cy; 511 512 right[0] = cx; 513 right[1] = cy; 514 right[2] = x2; 515 right[3] = y2; 516 } 517 518 static void subdivideQuadAt(final float t, 519 final float[] src, final int offS, 520 final float[] pts, final int offL, final int offR) 521 { 522 float x1 = src[offS ]; 523 float y1 = src[offS + 1]; 524 float cx = src[offS + 2]; 525 float cy = src[offS + 3]; 526 float x2 = src[offS + 4]; 527 float y2 = src[offS + 5]; 528 529 pts[offL ] = x1; 530 pts[offL + 1] = y1; 531 532 pts[offR + 4] = x2; 533 pts[offR + 5] = y2; 534 535 x1 = x1 + t * (cx - x1); 536 y1 = y1 + t * (cy - y1); 537 x2 = cx + t * (x2 - cx); 538 y2 = cy + t * (y2 - cy); 539 cx = x1 + t * (x2 - x1); 540 cy = y1 + t * (y2 - y1); 541 542 pts[offL + 2] = x1; 543 pts[offL + 3] = y1; 544 pts[offL + 4] = cx; 545 pts[offL + 5] = cy; 546 547 pts[offR ] = cx; 548 pts[offR + 1] = cy; 549 pts[offR + 2] = x2; 550 pts[offR + 3] = y2; 551 } 552 553 static void subdivideLineAt(final float t, 554 final float[] src, final int offS, 555 final float[] pts, final int offL, final int offR) 556 { 557 float x1 = src[offS ]; 558 float y1 = src[offS + 1]; 559 float x2 = src[offS + 2]; 560 float y2 = src[offS + 3]; 561 562 pts[offL ] = x1; 563 pts[offL + 1] = y1; 564 565 pts[offR + 2] = x2; 566 pts[offR + 3] = y2; 567 568 x1 = x1 + t * (x2 - x1); 569 y1 = y1 + t * (y2 - y1); 570 571 pts[offL + 2] = x1; 572 pts[offL + 3] = y1; 573 574 pts[offR ] = x1; 575 pts[offR + 1] = y1; 576 } 577 578 static void subdivideAt(final float t, 579 final float[] src, final int offS, 580 final float[] pts, final int offL, final int type) 581 { 582 // if instead of switch (perf + most probable cases first) 583 if (type == 8) { 584 subdivideCubicAt(t, src, offS, pts, offL, offL + type); 585 } else if (type == 4) { 586 subdivideLineAt(t, src, offS, pts, offL, offL + type); 587 } else { 588 subdivideQuadAt(t, src, offS, pts, offL, offL + type); 589 } 590 } 591 592 // From sun.java2d.loops.GeneralRenderer: 593 594 static int outcode(final float x, final float y, 595 final float[] clipRect) 596 { 597 int code; 598 if (y < clipRect[0]) { 599 code = OUTCODE_TOP; 600 } else if (y >= clipRect[1]) { 601 code = OUTCODE_BOTTOM; 602 } else { 603 code = 0; 604 } 605 if (x < clipRect[2]) { 606 code |= OUTCODE_LEFT; 607 } else if (x >= clipRect[3]) { 608 code |= OUTCODE_RIGHT; 609 } 610 return code; 611 } 612 613 // a stack of polynomial curves where each curve shares endpoints with 614 // adjacent ones. 615 static final class PolyStack { 616 private static final byte TYPE_LINETO = (byte) 0; 617 private static final byte TYPE_QUADTO = (byte) 1; 618 private static final byte TYPE_CUBICTO = (byte) 2; 619 620 // curves capacity = edges count (8192) = edges x 2 (coords) 621 private static final int INITIAL_CURVES_COUNT = INITIAL_EDGES_COUNT << 1; 622 623 // types capacity = edges count (4096) 624 private static final int INITIAL_TYPES_COUNT = INITIAL_EDGES_COUNT; 625 626 float[] curves; 627 int end; 628 byte[] curveTypes; 629 int numCurves; 630 631 // curves ref (dirty) 632 final FloatArrayCache.Reference curves_ref; 633 // curveTypes ref (dirty) 634 final ByteArrayCache.Reference curveTypes_ref; 635 636 // used marks (stats only) 637 int curveTypesUseMark; 638 int curvesUseMark; 639 640 private final StatLong stat_polystack_types; 641 private final StatLong stat_polystack_curves; 642 private final Histogram hist_polystack_curves; 643 private final StatLong stat_array_polystack_curves; 644 private final StatLong stat_array_polystack_curveTypes; 645 646 PolyStack(final RendererContext rdrCtx) { 647 this(rdrCtx, null, null, null, null, null); 648 } 649 650 PolyStack(final RendererContext rdrCtx, 651 final StatLong stat_polystack_types, 652 final StatLong stat_polystack_curves, 653 final Histogram hist_polystack_curves, 654 final StatLong stat_array_polystack_curves, 655 final StatLong stat_array_polystack_curveTypes) 656 { 657 curves_ref = rdrCtx.newDirtyFloatArrayRef(INITIAL_CURVES_COUNT); // 32K 658 curves = curves_ref.initial; 659 660 curveTypes_ref = rdrCtx.newDirtyByteArrayRef(INITIAL_TYPES_COUNT); // 4K 661 curveTypes = curveTypes_ref.initial; 662 numCurves = 0; 663 end = 0; 664 665 if (DO_STATS) { 666 curveTypesUseMark = 0; 667 curvesUseMark = 0; 668 } 669 this.stat_polystack_types = stat_polystack_types; 670 this.stat_polystack_curves = stat_polystack_curves; 671 this.hist_polystack_curves = hist_polystack_curves; 672 this.stat_array_polystack_curves = stat_array_polystack_curves; 673 this.stat_array_polystack_curveTypes = stat_array_polystack_curveTypes; 674 } 675 676 /** 677 * Disposes this PolyStack: 678 * clean up before reusing this instance 679 */ 680 void dispose() { 681 end = 0; 682 numCurves = 0; 683 684 if (DO_STATS) { 685 stat_polystack_types.add(curveTypesUseMark); 686 stat_polystack_curves.add(curvesUseMark); 687 hist_polystack_curves.add(curvesUseMark); 688 689 // reset marks 690 curveTypesUseMark = 0; 691 curvesUseMark = 0; 692 } 693 694 // Return arrays: 695 // curves and curveTypes are kept dirty 696 curves = curves_ref.putArray(curves); 697 curveTypes = curveTypes_ref.putArray(curveTypes); 698 } 699 700 private void ensureSpace(final int n) { 701 // use substraction to avoid integer overflow: 702 if (curves.length - end < n) { 703 if (DO_STATS) { 704 stat_array_polystack_curves.add(end + n); 705 } 706 curves = curves_ref.widenArray(curves, end, end + n); 707 } 708 if (curveTypes.length <= numCurves) { 709 if (DO_STATS) { 710 stat_array_polystack_curveTypes.add(numCurves + 1); 711 } 712 curveTypes = curveTypes_ref.widenArray(curveTypes, 713 numCurves, 714 numCurves + 1); 715 } 716 } 717 718 void pushCubic(float x0, float y0, 719 float x1, float y1, 720 float x2, float y2) 721 { 722 ensureSpace(6); 723 curveTypes[numCurves++] = TYPE_CUBICTO; 724 // we reverse the coordinate order to make popping easier 725 final float[] _curves = curves; 726 int e = end; 727 _curves[e++] = x2; _curves[e++] = y2; 728 _curves[e++] = x1; _curves[e++] = y1; 729 _curves[e++] = x0; _curves[e++] = y0; 730 end = e; 731 } 732 733 void pushQuad(float x0, float y0, 734 float x1, float y1) 735 { 736 ensureSpace(4); 737 curveTypes[numCurves++] = TYPE_QUADTO; 738 final float[] _curves = curves; 739 int e = end; 740 _curves[e++] = x1; _curves[e++] = y1; 741 _curves[e++] = x0; _curves[e++] = y0; 742 end = e; 743 } 744 745 void pushLine(float x, float y) { 746 ensureSpace(2); 747 curveTypes[numCurves++] = TYPE_LINETO; 748 curves[end++] = x; curves[end++] = y; 749 } 750 751 void pullAll(final PathConsumer2D io) { 752 final int nc = numCurves; 753 if (nc == 0) { 754 return; 755 } 756 if (DO_STATS) { 757 // update used marks: 758 if (numCurves > curveTypesUseMark) { 759 curveTypesUseMark = numCurves; 760 } 761 if (end > curvesUseMark) { 762 curvesUseMark = end; 763 } 764 } 765 final byte[] _curveTypes = curveTypes; 766 final float[] _curves = curves; 767 int e = 0; 768 769 for (int i = 0; i < nc; i++) { 770 switch(_curveTypes[i]) { 771 case TYPE_LINETO: 772 io.lineTo(_curves[e], _curves[e+1]); 773 e += 2; 774 continue; 775 case TYPE_QUADTO: 776 io.quadTo(_curves[e], _curves[e+1], 777 _curves[e+2], _curves[e+3]); 778 e += 4; 779 continue; 780 case TYPE_CUBICTO: 781 io.curveTo(_curves[e], _curves[e+1], 782 _curves[e+2], _curves[e+3], 783 _curves[e+4], _curves[e+5]); 784 e += 6; 785 continue; 786 default: 787 } 788 } 789 numCurves = 0; 790 end = 0; 791 } 792 793 void popAll(final PathConsumer2D io) { 794 int nc = numCurves; 795 if (nc == 0) { 796 return; 797 } 798 if (DO_STATS) { 799 // update used marks: 800 if (numCurves > curveTypesUseMark) { 801 curveTypesUseMark = numCurves; 802 } 803 if (end > curvesUseMark) { 804 curvesUseMark = end; 805 } 806 } 807 final byte[] _curveTypes = curveTypes; 808 final float[] _curves = curves; 809 int e = end; 810 811 while (nc != 0) { 812 switch(_curveTypes[--nc]) { 813 case TYPE_LINETO: 814 e -= 2; 815 io.lineTo(_curves[e], _curves[e+1]); 816 continue; 817 case TYPE_QUADTO: 818 e -= 4; 819 io.quadTo(_curves[e], _curves[e+1], 820 _curves[e+2], _curves[e+3]); 821 continue; 822 case TYPE_CUBICTO: 823 e -= 6; 824 io.curveTo(_curves[e], _curves[e+1], 825 _curves[e+2], _curves[e+3], 826 _curves[e+4], _curves[e+5]); 827 continue; 828 default: 829 } 830 } 831 numCurves = 0; 832 end = 0; 833 } 834 835 @Override 836 public String toString() { 837 String ret = ""; 838 int nc = numCurves; 839 int last = end; 840 int len; 841 while (nc != 0) { 842 switch(curveTypes[--nc]) { 843 case TYPE_LINETO: 844 len = 2; 845 ret += "line: "; 846 break; 847 case TYPE_QUADTO: 848 len = 4; 849 ret += "quad: "; 850 break; 851 case TYPE_CUBICTO: 852 len = 6; 853 ret += "cubic: "; 854 break; 855 default: 856 len = 0; 857 } 858 last -= len; 859 ret += Arrays.toString(Arrays.copyOfRange(curves, last, last+len)) 860 + "\n"; 861 } 862 return ret; 863 } 864 } 865 866 // a stack of integer indices 867 static final class IndexStack { 868 869 // integer capacity = edges count / 4 ~ 1024 870 private static final int INITIAL_COUNT = INITIAL_EDGES_COUNT >> 2; 871 872 private int end; 873 private int[] indices; 874 875 // indices ref (dirty) 876 private final IntArrayCache.Reference indices_ref; 877 878 // used marks (stats only) 879 private int indicesUseMark; 880 881 private final StatLong stat_idxstack_indices; 882 private final Histogram hist_idxstack_indices; 883 private final StatLong stat_array_idxstack_indices; 884 885 IndexStack(final RendererContext rdrCtx) { 886 this(rdrCtx, null, null, null); 887 } 888 889 IndexStack(final RendererContext rdrCtx, 890 final StatLong stat_idxstack_indices, 891 final Histogram hist_idxstack_indices, 892 final StatLong stat_array_idxstack_indices) 893 { 894 indices_ref = rdrCtx.newDirtyIntArrayRef(INITIAL_COUNT); // 4K 895 indices = indices_ref.initial; 896 end = 0; 897 898 if (DO_STATS) { 899 indicesUseMark = 0; 900 } 901 this.stat_idxstack_indices = stat_idxstack_indices; 902 this.hist_idxstack_indices = hist_idxstack_indices; 903 this.stat_array_idxstack_indices = stat_array_idxstack_indices; 904 } 905 906 /** 907 * Disposes this PolyStack: 908 * clean up before reusing this instance 909 */ 910 void dispose() { 911 end = 0; 912 913 if (DO_STATS) { 914 stat_idxstack_indices.add(indicesUseMark); 915 hist_idxstack_indices.add(indicesUseMark); 916 917 // reset marks 918 indicesUseMark = 0; 919 } 920 921 // Return arrays: 922 // values is kept dirty 923 indices = indices_ref.putArray(indices); 924 } 925 926 boolean isEmpty() { 927 return (end == 0); 928 } 929 930 void reset() { 931 end = 0; 932 } 933 934 void push(final int v) { 935 // remove redundant values (reverse order): 936 int[] _values = indices; 937 final int nc = end; 938 if (nc != 0) { 939 if (_values[nc - 1] == v) { 940 // remove both duplicated values: 941 end--; 942 return; 943 } 944 } 945 if (_values.length <= nc) { 946 if (DO_STATS) { 947 stat_array_idxstack_indices.add(nc + 1); 948 } 949 indices = _values = indices_ref.widenArray(_values, nc, nc + 1); 950 } 951 _values[end++] = v; 952 953 if (DO_STATS) { 954 // update used marks: 955 if (end > indicesUseMark) { 956 indicesUseMark = end; 957 } 958 } 959 } 960 961 void pullAll(final float[] points, final PathConsumer2D io) { 962 final int nc = end; 963 if (nc == 0) { 964 return; 965 } 966 final int[] _values = indices; 967 968 for (int i = 0, j; i < nc; i++) { 969 j = _values[i] << 1; 970 io.lineTo(points[j], points[j + 1]); 971 } 972 end = 0; 973 } 974 } 975 }