1 /* 2 * Copyright (c) 2007, 2016, 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 31 /** 32 * The <code>Dasher</code> class takes a series of linear commands 33 * (<code>moveTo</code>, <code>lineTo</code>, <code>close</code> and 34 * <code>end</code>) and breaks them into smaller segments according to a 35 * dash pattern array and a starting dash phase. 36 * 37 * <p> Issues: in J2Se, a zero length dash segment as drawn as a very 38 * short dash, whereas Pisces does not draw anything. The PostScript 39 * semantics are unclear. 40 * 41 */ 42 final class Dasher implements sun.awt.geom.PathConsumer2D, MarlinConst { 43 44 static final int REC_LIMIT = 4; 45 static final float ERR = 0.01f; 46 static final float MIN_T_INC = 1f / (1 << REC_LIMIT); 47 48 private PathConsumer2D out; 49 private float[] dash; 50 private int dashLen; 51 private float startPhase; 52 private boolean startDashOn; 53 private int startIdx; 54 55 private boolean starting; 56 private boolean needsMoveTo; 57 58 private int idx; 59 private boolean dashOn; 60 private float phase; 61 62 private float sx, sy; 63 private float x0, y0; 64 65 // temporary storage for the current curve 66 private final float[] curCurvepts; 89 firstSegmentsBuffer = firstSegmentsBuffer_ref.initial; 90 91 // we need curCurvepts to be able to contain 2 curves because when 92 // dashing curves, we need to subdivide it 93 curCurvepts = new float[8 * 2]; 94 } 95 96 /** 97 * Initialize the <code>Dasher</code>. 98 * 99 * @param out an output <code>PathConsumer2D</code>. 100 * @param dash an array of <code>float</code>s containing the dash pattern 101 * @param dashLen length of the given dash array 102 * @param phase a <code>float</code> containing the dash phase 103 * @param recycleDashes true to indicate to recycle the given dash array 104 * @return this instance 105 */ 106 Dasher init(final PathConsumer2D out, float[] dash, int dashLen, 107 float phase, boolean recycleDashes) 108 { 109 if (phase < 0f) { 110 throw new IllegalArgumentException("phase < 0 !"); 111 } 112 this.out = out; 113 114 // Normalize so 0 <= phase < dash[0] 115 int idx = 0; 116 dashOn = true; 117 float d; 118 while (phase >= (d = dash[idx])) { 119 phase -= d; 120 idx = (idx + 1) % dashLen; 121 dashOn = !dashOn; 122 } 123 124 this.dash = dash; 125 this.dashLen = dashLen; 126 this.startPhase = this.phase = phase; 127 this.startDashOn = dashOn; 128 this.startIdx = idx; 129 this.starting = true; 130 needsMoveTo = false; 131 firstSegidx = 0; 132 133 this.recycleDashes = recycleDashes; 134 135 return this; // fluent API 136 } 137 138 /** 139 * Disposes this dasher: 140 * clean up before reusing this instance 141 */ 142 void dispose() { 143 if (DO_CLEAN_DIRTY) { 144 // Force zero-fill dirty arrays: 145 Arrays.fill(curCurvepts, 0f); 146 } 147 // Return arrays: 148 if (recycleDashes) { 149 dash = dashes_ref.putArray(dash); 150 } 151 firstSegmentsBuffer = firstSegmentsBuffer_ref.putArray(firstSegmentsBuffer); 152 } 153 154 @Override 155 public void moveTo(float x0, float y0) { 156 if (firstSegidx > 0) { 157 out.moveTo(sx, sy); 158 emitFirstSegments(); 159 } 160 needsMoveTo = true; 161 this.idx = startIdx; 162 this.dashOn = this.startDashOn; 163 this.phase = this.startPhase; 164 this.sx = this.x0 = x0; 165 this.sy = this.y0 = y0; 166 this.starting = true; 167 } 168 169 private void emitSeg(float[] buf, int off, int type) { 170 switch (type) { 171 case 8: 172 out.curveTo(buf[off+0], buf[off+1], 173 buf[off+2], buf[off+3], 185 } 186 187 private void emitFirstSegments() { 188 final float[] fSegBuf = firstSegmentsBuffer; 189 190 for (int i = 0; i < firstSegidx; ) { 191 int type = (int)fSegBuf[i]; 192 emitSeg(fSegBuf, i + 1, type); 193 i += (type - 1); 194 } 195 firstSegidx = 0; 196 } 197 // We don't emit the first dash right away. If we did, caps would be 198 // drawn on it, but we need joins to be drawn if there's a closePath() 199 // So, we store the path elements that make up the first dash in the 200 // buffer below. 201 private float[] firstSegmentsBuffer; // dynamic array 202 private int firstSegidx; 203 204 // precondition: pts must be in relative coordinates (relative to x0,y0) 205 // fullCurve is true iff the curve in pts has not been split. 206 private void goTo(float[] pts, int off, final int type) { 207 float x = pts[off + type - 4]; 208 float y = pts[off + type - 3]; 209 if (dashOn) { 210 if (starting) { 211 int len = type - 2 + 1; 212 int segIdx = firstSegidx; 213 float[] buf = firstSegmentsBuffer; 214 if (segIdx + len > buf.length) { 215 if (DO_STATS) { 216 rdrCtx.stats.stat_array_dasher_firstSegmentsBuffer 217 .add(segIdx + len); 218 } 219 firstSegmentsBuffer = buf 220 = firstSegmentsBuffer_ref.widenArray(buf, segIdx, 221 segIdx + len); 222 } 223 buf[segIdx++] = type; 224 len--; 225 // small arraycopy (2, 4 or 6) but with offset: 226 System.arraycopy(pts, off, buf, segIdx, len); 227 segIdx += len; 228 firstSegidx = segIdx; 229 } else { 230 if (needsMoveTo) { 231 out.moveTo(x0, y0); 232 needsMoveTo = false; 233 } 234 emitSeg(pts, off, type); 235 } 236 } else { 237 starting = false; 238 needsMoveTo = true; 239 } 240 this.x0 = x; 241 this.y0 = y; 242 } 243 244 @Override 245 public void lineTo(float x1, float y1) { 246 float dx = x1 - x0; 247 float dy = y1 - y0; 248 249 float len = dx*dx + dy*dy; 250 if (len == 0f) { 251 return; 252 } 253 len = (float) Math.sqrt(len); 254 255 // The scaling factors needed to get the dx and dy of the 256 // transformed dash segments. 257 final float cx = dx / len; 258 final float cy = dy / len; 259 260 final float[] _curCurvepts = curCurvepts; 261 final float[] _dash = dash; 262 263 float leftInThisDashSegment; 264 float dashdx, dashdy, p; 265 266 while (true) { 267 leftInThisDashSegment = _dash[idx] - phase; 268 269 if (len <= leftInThisDashSegment) { 270 _curCurvepts[0] = x1; 271 _curCurvepts[1] = y1; 272 goTo(_curCurvepts, 0, 4); 273 274 // Advance phase within current dash segment 275 phase += len; 276 // TODO: compare float values using epsilon: 277 if (len == leftInThisDashSegment) { 278 phase = 0f; 279 idx = (idx + 1) % dashLen; 280 dashOn = !dashOn; 281 } 282 return; 283 } 284 285 dashdx = _dash[idx] * cx; 286 dashdy = _dash[idx] * cy; 287 288 if (phase == 0f) { 289 _curCurvepts[0] = x0 + dashdx; 290 _curCurvepts[1] = y0 + dashdy; 291 } else { 292 p = leftInThisDashSegment / _dash[idx]; 293 _curCurvepts[0] = x0 + p * dashdx; 294 _curCurvepts[1] = y0 + p * dashdy; 295 } 296 297 goTo(_curCurvepts, 0, 4); 298 299 len -= leftInThisDashSegment; 300 // Advance to next dash segment 301 idx = (idx + 1) % dashLen; 302 dashOn = !dashOn; 303 phase = 0f; 304 } 305 } 306 307 // shared instance in Dasher 308 private final LengthIterator li = new LengthIterator(); 309 310 // preconditions: curCurvepts must be an array of length at least 2 * type, 311 // that contains the curve we want to dash in the first type elements 312 private void somethingTo(int type) { 313 if (pointCurve(curCurvepts, type)) { 314 return; 315 } 316 li.initializeIterationOnCurve(curCurvepts, type); 317 318 // initially the current curve is at curCurvepts[0...type] 319 int curCurveoff = 0; 320 float lastSplitT = 0f; 321 float t; 322 float leftInThisDashSegment = dash[idx] - phase; 323 324 while ((t = li.next(leftInThisDashSegment)) < 1f) { 325 if (t != 0f) { 326 Helpers.subdivideAt((t - lastSplitT) / (1f - lastSplitT), 327 curCurvepts, curCurveoff, 328 curCurvepts, 0, 329 curCurvepts, type, type); 330 lastSplitT = t; 331 goTo(curCurvepts, 2, type); 332 curCurveoff = type; 333 } 334 // Advance to next dash segment 335 idx = (idx + 1) % dashLen; 336 dashOn = !dashOn; 337 phase = 0f; 338 leftInThisDashSegment = dash[idx]; 339 } 340 goTo(curCurvepts, curCurveoff+2, type); 341 phase += li.lastSegLen(); 342 if (phase >= dash[idx]) { 343 phase = 0f; 344 idx = (idx + 1) % dashLen; 345 dashOn = !dashOn; 346 } 347 // reset LengthIterator: 348 li.reset(); 349 } 350 351 private static boolean pointCurve(float[] curve, int type) { 352 for (int i = 2; i < type; i++) { 353 if (curve[i] != curve[i-2]) { 354 return false; 355 } 356 } 357 return true; 358 } 359 360 // Objects of this class are used to iterate through curves. They return 361 // t values where the left side of the curve has a specified length. 362 // It does this by subdividing the input curve until a certain error 363 // condition has been met. A recursive subdivision procedure would 378 // only the right half of the original curve is at 0) 379 private final float[][] recCurveStack; // dirty 380 // sides[i] indicates whether the node at level i+1 in the path from 381 // the root to the current leaf is a left or right child of its parent. 382 private final Side[] sides; // dirty 383 private int curveType; 384 // lastT and nextT delimit the current leaf. 385 private float nextT; 386 private float lenAtNextT; 387 private float lastT; 388 private float lenAtLastT; 389 private float lenAtLastSplit; 390 private float lastSegLen; 391 // the current level in the recursion tree. 0 is the root. limit 392 // is the deepest possible leaf. 393 private int recLevel; 394 private boolean done; 395 396 // the lengths of the lines of the control polygon. Only its first 397 // curveType/2 - 1 elements are valid. This is an optimization. See 398 // next(float) for more detail. 399 private final float[] curLeafCtrlPolyLengths = new float[3]; 400 401 LengthIterator() { 402 this.recCurveStack = new float[REC_LIMIT + 1][8]; 403 this.sides = new Side[REC_LIMIT]; 404 // if any methods are called without first initializing this object 405 // on a curve, we want it to fail ASAP. 406 this.nextT = Float.MAX_VALUE; 407 this.lenAtNextT = Float.MAX_VALUE; 408 this.lenAtLastSplit = Float.MIN_VALUE; 409 this.recLevel = Integer.MIN_VALUE; 410 this.lastSegLen = Float.MAX_VALUE; 411 this.done = true; 412 } 413 414 /** 415 * Reset this LengthIterator. 416 */ 417 void reset() { 418 // keep data dirty 419 // as it appears not useful to reset data: 420 if (DO_CLEAN_DIRTY) { 421 final int recLimit = recCurveStack.length - 1; 422 for (int i = recLimit; i >= 0; i--) { 423 Arrays.fill(recCurveStack[i], 0f); 424 } 425 Arrays.fill(sides, Side.LEFT); 426 Arrays.fill(curLeafCtrlPolyLengths, 0f); 427 Arrays.fill(nextRoots, 0f); 428 Arrays.fill(flatLeafCoefCache, 0f); 429 flatLeafCoefCache[2] = -1f; 430 } 431 } 432 433 void initializeIterationOnCurve(float[] pts, int type) { 434 // optimize arraycopy (8 values faster than 6 = type): 435 System.arraycopy(pts, 0, recCurveStack[0], 0, 8); 436 this.curveType = type; 437 this.recLevel = 0; 438 this.lastT = 0f; 439 this.lenAtLastT = 0f; 440 this.nextT = 0f; 441 this.lenAtNextT = 0f; 442 goLeft(); // initializes nextT and lenAtNextT properly 443 this.lenAtLastSplit = 0f; 444 if (recLevel > 0) { 445 this.sides[0] = Side.LEFT; 446 this.done = false; 447 } else { 448 // the root of the tree is a leaf so we're done. 449 this.sides[0] = Side.RIGHT; 450 this.done = true; 451 } 452 this.lastSegLen = 0f; 453 } 454 455 // 0 == false, 1 == true, -1 == invalid cached value. 456 private int cachedHaveLowAcceleration = -1; 457 458 private boolean haveLowAcceleration(float err) { 459 if (cachedHaveLowAcceleration == -1) { 460 final float len1 = curLeafCtrlPolyLengths[0]; 461 final float len2 = curLeafCtrlPolyLengths[1]; 462 // the test below is equivalent to !within(len1/len2, 1, err). 463 // It is using a multiplication instead of a division, so it 464 // should be a bit faster. 465 if (!Helpers.within(len1, len2, err*len2)) { 466 cachedHaveLowAcceleration = 0; 467 return false; 468 } 469 if (curveType == 8) { 470 final float len3 = curLeafCtrlPolyLengths[2]; 471 // if len1 is close to 2 and 2 is close to 3, that probably 472 // means 1 is close to 3 so the second part of this test might 473 // not be needed, but it doesn't hurt to include it. 474 final float errLen3 = err * len3; 475 if (!(Helpers.within(len2, len3, errLen3) && 476 Helpers.within(len1, len3, errLen3))) { 477 cachedHaveLowAcceleration = 0; 478 return false; 479 } 480 } 481 cachedHaveLowAcceleration = 1; 482 return true; 483 } 484 485 return (cachedHaveLowAcceleration == 1); 486 } 487 488 // we want to avoid allocations/gc so we keep this array so we 489 // can put roots in it, 490 private final float[] nextRoots = new float[4]; 491 492 // caches the coefficients of the current leaf in its flattened 493 // form (see inside next() for what that means). The cache is 494 // invalid when it's third element is negative, since in any 495 // valid flattened curve, this would be >= 0. 496 private final float[] flatLeafCoefCache = new float[]{0f, 0f, -1f, 0f}; 497 498 // returns the t value where the remaining curve should be split in 499 // order for the left subdivided curve to have length len. If len 500 // is >= than the length of the uniterated curve, it returns 1. 501 float next(final float len) { 502 final float targetLength = lenAtLastSplit + len; 503 while (lenAtNextT < targetLength) { 504 if (done) { 505 lastSegLen = lenAtNextT - lenAtLastSplit; 506 return 1f; 507 } 508 goToNextLeaf(); 509 } 510 lenAtLastSplit = targetLength; 511 final float leaflen = lenAtNextT - lenAtLastT; 512 float t = (targetLength - lenAtLastT) / leaflen; 513 514 // cubicRootsInAB is a fairly expensive call, so we just don't do it 515 // if the acceleration in this section of the curve is small enough. 516 if (!haveLowAcceleration(0.05f)) { 517 // We flatten the current leaf along the x axis, so that we're 518 // left with a, b, c which define a 1D Bezier curve. We then 519 // solve this to get the parameter of the original leaf that 520 // gives us the desired length. 521 final float[] _flatLeafCoefCache = flatLeafCoefCache; 522 523 if (_flatLeafCoefCache[2] < 0) { 524 float x = 0f + curLeafCtrlPolyLengths[0], 525 y = x + curLeafCtrlPolyLengths[1]; 526 if (curveType == 8) { 527 float z = y + curLeafCtrlPolyLengths[2]; 528 _flatLeafCoefCache[0] = 3f * (x - y) + z; 529 _flatLeafCoefCache[1] = 3f * (y - 2f * x); 530 _flatLeafCoefCache[2] = 3f * x; 531 _flatLeafCoefCache[3] = -z; 532 } else if (curveType == 6) { 533 _flatLeafCoefCache[0] = 0f; 534 _flatLeafCoefCache[1] = y - 2f * x; 535 _flatLeafCoefCache[2] = 2f * x; 536 _flatLeafCoefCache[3] = -y; 537 } 538 } 539 float a = _flatLeafCoefCache[0]; 540 float b = _flatLeafCoefCache[1]; 541 float c = _flatLeafCoefCache[2]; 542 float d = t * _flatLeafCoefCache[3]; 543 544 // we use cubicRootsInAB here, because we want only roots in 0, 1, 545 // and our quadratic root finder doesn't filter, so it's just a 546 // matter of convenience. 547 int n = Helpers.cubicRootsInAB(a, b, c, d, nextRoots, 0, 0, 1); 548 if (n == 1 && !Float.isNaN(nextRoots[0])) { 549 t = nextRoots[0]; 550 } 551 } 552 // t is relative to the current leaf, so we must make it a valid parameter 553 // of the original curve. 554 t = t * (nextT - lastT) + lastT; 555 if (t >= 1f) { 556 t = 1f; 557 done = true; 558 } 559 // even if done = true, if we're here, that means targetLength 560 // is equal to, or very, very close to the total length of the 561 // curve, so lastSegLen won't be too high. In cases where len 562 // overshoots the curve, this method will exit in the while 563 // loop, and lastSegLen will still be set to the right value. 564 lastSegLen = len; 565 return t; 566 } 567 568 float lastSegLen() { 569 return lastSegLen; 570 } 571 572 // go to the next leaf (in an inorder traversal) in the recursion tree 573 // preconditions: must be on a leaf, and that leaf must not be the root. 574 private void goToNextLeaf() { 575 // We must go to the first ancestor node that has an unvisited 576 // right child. 583 recLevel = 0; 584 done = true; 585 return; 586 } 587 _recLevel--; 588 } 589 590 _sides[_recLevel] = Side.RIGHT; 591 // optimize arraycopy (8 values faster than 6 = type): 592 System.arraycopy(recCurveStack[_recLevel], 0, 593 recCurveStack[_recLevel+1], 0, 8); 594 _recLevel++; 595 596 recLevel = _recLevel; 597 goLeft(); 598 } 599 600 // go to the leftmost node from the current node. Return its length. 601 private void goLeft() { 602 float len = onLeaf(); 603 if (len >= 0f) { 604 lastT = nextT; 605 lenAtLastT = lenAtNextT; 606 nextT += (1 << (REC_LIMIT - recLevel)) * MIN_T_INC; 607 lenAtNextT += len; 608 // invalidate caches 609 flatLeafCoefCache[2] = -1f; 610 cachedHaveLowAcceleration = -1; 611 } else { 612 Helpers.subdivide(recCurveStack[recLevel], 0, 613 recCurveStack[recLevel+1], 0, 614 recCurveStack[recLevel], 0, curveType); 615 sides[recLevel] = Side.LEFT; 616 recLevel++; 617 goLeft(); 618 } 619 } 620 621 // this is a bit of a hack. It returns -1 if we're not on a leaf, and 622 // the length of the leaf if we are on a leaf. 623 private float onLeaf() { 624 float[] curve = recCurveStack[recLevel]; 625 float polyLen = 0f; 626 627 float x0 = curve[0], y0 = curve[1]; 628 for (int i = 2; i < curveType; i += 2) { 629 final float x1 = curve[i], y1 = curve[i+1]; 630 final float len = Helpers.linelen(x0, y0, x1, y1); 631 polyLen += len; 632 curLeafCtrlPolyLengths[i/2 - 1] = len; 633 x0 = x1; 634 y0 = y1; 635 } 636 637 final float lineLen = Helpers.linelen(curve[0], curve[1], 638 curve[curveType-2], 639 curve[curveType-1]); 640 if ((polyLen - lineLen) < ERR || recLevel == REC_LIMIT) { 641 return (polyLen + lineLen) / 2f; 642 } 643 return -1f; 644 } 645 } 646 647 @Override 648 public void curveTo(float x1, float y1, 649 float x2, float y2, 650 float x3, float y3) 651 { 652 final float[] _curCurvepts = curCurvepts; 653 _curCurvepts[0] = x0; _curCurvepts[1] = y0; 654 _curCurvepts[2] = x1; _curCurvepts[3] = y1; 655 _curCurvepts[4] = x2; _curCurvepts[5] = y2; 656 _curCurvepts[6] = x3; _curCurvepts[7] = y3; 657 somethingTo(8); 658 } 659 660 @Override 661 public void quadTo(float x1, float y1, float x2, float y2) { 662 final float[] _curCurvepts = curCurvepts; 663 _curCurvepts[0] = x0; _curCurvepts[1] = y0; | 1 /* 2 * Copyright (c) 2007, 2017, 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 31 /** 32 * The <code>Dasher</code> class takes a series of linear commands 33 * (<code>moveTo</code>, <code>lineTo</code>, <code>close</code> and 34 * <code>end</code>) and breaks them into smaller segments according to a 35 * dash pattern array and a starting dash phase. 36 * 37 * <p> Issues: in J2Se, a zero length dash segment as drawn as a very 38 * short dash, whereas Pisces does not draw anything. The PostScript 39 * semantics are unclear. 40 * 41 */ 42 final class Dasher implements PathConsumer2D, MarlinConst { 43 44 static final int REC_LIMIT = 4; 45 static final float ERR = 0.01f; 46 static final float MIN_T_INC = 1.0f / (1 << REC_LIMIT); 47 48 // More than 24 bits of mantissa means we can no longer accurately 49 // measure the number of times cycled through the dash array so we 50 // punt and override the phase to just be 0 past that point. 51 static final float MAX_CYCLES = 16000000.0f; 52 53 private PathConsumer2D out; 54 private float[] dash; 55 private int dashLen; 56 private float startPhase; 57 private boolean startDashOn; 58 private int startIdx; 59 60 private boolean starting; 61 private boolean needsMoveTo; 62 63 private int idx; 64 private boolean dashOn; 65 private float phase; 66 67 private float sx, sy; 68 private float x0, y0; 69 70 // temporary storage for the current curve 71 private final float[] curCurvepts; 94 firstSegmentsBuffer = firstSegmentsBuffer_ref.initial; 95 96 // we need curCurvepts to be able to contain 2 curves because when 97 // dashing curves, we need to subdivide it 98 curCurvepts = new float[8 * 2]; 99 } 100 101 /** 102 * Initialize the <code>Dasher</code>. 103 * 104 * @param out an output <code>PathConsumer2D</code>. 105 * @param dash an array of <code>float</code>s containing the dash pattern 106 * @param dashLen length of the given dash array 107 * @param phase a <code>float</code> containing the dash phase 108 * @param recycleDashes true to indicate to recycle the given dash array 109 * @return this instance 110 */ 111 Dasher init(final PathConsumer2D out, float[] dash, int dashLen, 112 float phase, boolean recycleDashes) 113 { 114 this.out = out; 115 116 // Normalize so 0 <= phase < dash[0] 117 int sidx = 0; 118 dashOn = true; 119 float sum = 0.0f; 120 for (float d : dash) { 121 sum += d; 122 } 123 float cycles = phase / sum; 124 if (phase < 0.0f) { 125 if (-cycles >= MAX_CYCLES) { 126 phase = 0.0f; 127 } else { 128 int fullcycles = FloatMath.floor_int(-cycles); 129 if ((fullcycles & dash.length & 1) != 0) { 130 dashOn = !dashOn; 131 } 132 phase += fullcycles * sum; 133 while (phase < 0.0f) { 134 if (--sidx < 0) { 135 sidx = dash.length - 1; 136 } 137 phase += dash[sidx]; 138 dashOn = !dashOn; 139 } 140 } 141 } else if (phase > 0) { 142 if (cycles >= MAX_CYCLES) { 143 phase = 0.0f; 144 } else { 145 int fullcycles = FloatMath.floor_int(cycles); 146 if ((fullcycles & dash.length & 1) != 0) { 147 dashOn = !dashOn; 148 } 149 phase -= fullcycles * sum; 150 float d; 151 while (phase >= (d = dash[sidx])) { 152 phase -= d; 153 sidx = (sidx + 1) % dash.length; 154 dashOn = !dashOn; 155 } 156 } 157 } 158 159 this.dash = dash; 160 this.dashLen = dashLen; 161 this.startPhase = this.phase = phase; 162 this.startDashOn = dashOn; 163 this.startIdx = sidx; 164 this.starting = true; 165 needsMoveTo = false; 166 firstSegidx = 0; 167 168 this.recycleDashes = recycleDashes; 169 170 return this; // fluent API 171 } 172 173 /** 174 * Disposes this dasher: 175 * clean up before reusing this instance 176 */ 177 void dispose() { 178 if (DO_CLEAN_DIRTY) { 179 // Force zero-fill dirty arrays: 180 Arrays.fill(curCurvepts, 0.0f); 181 } 182 // Return arrays: 183 if (recycleDashes) { 184 dash = dashes_ref.putArray(dash); 185 } 186 firstSegmentsBuffer = firstSegmentsBuffer_ref.putArray(firstSegmentsBuffer); 187 } 188 189 float[] copyDashArray(final float[] dashes) { 190 final int len = dashes.length; 191 final float[] newDashes; 192 if (len <= MarlinConst.INITIAL_ARRAY) { 193 newDashes = dashes_ref.initial; 194 } else { 195 if (DO_STATS) { 196 rdrCtx.stats.stat_array_dasher_dasher.add(len); 197 } 198 newDashes = dashes_ref.getArray(len); 199 } 200 System.arraycopy(dashes, 0, newDashes, 0, len); 201 return newDashes; 202 } 203 204 @Override 205 public void moveTo(float x0, float y0) { 206 if (firstSegidx > 0) { 207 out.moveTo(sx, sy); 208 emitFirstSegments(); 209 } 210 needsMoveTo = true; 211 this.idx = startIdx; 212 this.dashOn = this.startDashOn; 213 this.phase = this.startPhase; 214 this.sx = this.x0 = x0; 215 this.sy = this.y0 = y0; 216 this.starting = true; 217 } 218 219 private void emitSeg(float[] buf, int off, int type) { 220 switch (type) { 221 case 8: 222 out.curveTo(buf[off+0], buf[off+1], 223 buf[off+2], buf[off+3], 235 } 236 237 private void emitFirstSegments() { 238 final float[] fSegBuf = firstSegmentsBuffer; 239 240 for (int i = 0; i < firstSegidx; ) { 241 int type = (int)fSegBuf[i]; 242 emitSeg(fSegBuf, i + 1, type); 243 i += (type - 1); 244 } 245 firstSegidx = 0; 246 } 247 // We don't emit the first dash right away. If we did, caps would be 248 // drawn on it, but we need joins to be drawn if there's a closePath() 249 // So, we store the path elements that make up the first dash in the 250 // buffer below. 251 private float[] firstSegmentsBuffer; // dynamic array 252 private int firstSegidx; 253 254 // precondition: pts must be in relative coordinates (relative to x0,y0) 255 private void goTo(float[] pts, int off, final int type) { 256 float x = pts[off + type - 4]; 257 float y = pts[off + type - 3]; 258 if (dashOn) { 259 if (starting) { 260 int len = type - 1; // - 2 + 1 261 int segIdx = firstSegidx; 262 float[] buf = firstSegmentsBuffer; 263 if (segIdx + len > buf.length) { 264 if (DO_STATS) { 265 rdrCtx.stats.stat_array_dasher_firstSegmentsBuffer 266 .add(segIdx + len); 267 } 268 firstSegmentsBuffer = buf 269 = firstSegmentsBuffer_ref.widenArray(buf, segIdx, 270 segIdx + len); 271 } 272 buf[segIdx++] = type; 273 len--; 274 // small arraycopy (2, 4 or 6) but with offset: 275 System.arraycopy(pts, off, buf, segIdx, len); 276 segIdx += len; 277 firstSegidx = segIdx; 278 } else { 279 if (needsMoveTo) { 280 out.moveTo(x0, y0); 281 needsMoveTo = false; 282 } 283 emitSeg(pts, off, type); 284 } 285 } else { 286 starting = false; 287 needsMoveTo = true; 288 } 289 this.x0 = x; 290 this.y0 = y; 291 } 292 293 @Override 294 public void lineTo(float x1, float y1) { 295 float dx = x1 - x0; 296 float dy = y1 - y0; 297 298 float len = dx*dx + dy*dy; 299 if (len == 0.0f) { 300 return; 301 } 302 len = (float) Math.sqrt(len); 303 304 // The scaling factors needed to get the dx and dy of the 305 // transformed dash segments. 306 final float cx = dx / len; 307 final float cy = dy / len; 308 309 final float[] _curCurvepts = curCurvepts; 310 final float[] _dash = dash; 311 312 float leftInThisDashSegment; 313 float dashdx, dashdy, p; 314 315 while (true) { 316 leftInThisDashSegment = _dash[idx] - phase; 317 318 if (len <= leftInThisDashSegment) { 319 _curCurvepts[0] = x1; 320 _curCurvepts[1] = y1; 321 goTo(_curCurvepts, 0, 4); 322 323 // Advance phase within current dash segment 324 phase += len; 325 // TODO: compare float values using epsilon: 326 if (len == leftInThisDashSegment) { 327 phase = 0.0f; 328 idx = (idx + 1) % dashLen; 329 dashOn = !dashOn; 330 } 331 return; 332 } 333 334 dashdx = _dash[idx] * cx; 335 dashdy = _dash[idx] * cy; 336 337 if (phase == 0.0f) { 338 _curCurvepts[0] = x0 + dashdx; 339 _curCurvepts[1] = y0 + dashdy; 340 } else { 341 p = leftInThisDashSegment / _dash[idx]; 342 _curCurvepts[0] = x0 + p * dashdx; 343 _curCurvepts[1] = y0 + p * dashdy; 344 } 345 346 goTo(_curCurvepts, 0, 4); 347 348 len -= leftInThisDashSegment; 349 // Advance to next dash segment 350 idx = (idx + 1) % dashLen; 351 dashOn = !dashOn; 352 phase = 0.0f; 353 } 354 } 355 356 // shared instance in Dasher 357 private final LengthIterator li = new LengthIterator(); 358 359 // preconditions: curCurvepts must be an array of length at least 2 * type, 360 // that contains the curve we want to dash in the first type elements 361 private void somethingTo(int type) { 362 if (pointCurve(curCurvepts, type)) { 363 return; 364 } 365 li.initializeIterationOnCurve(curCurvepts, type); 366 367 // initially the current curve is at curCurvepts[0...type] 368 int curCurveoff = 0; 369 float lastSplitT = 0.0f; 370 float t; 371 float leftInThisDashSegment = dash[idx] - phase; 372 373 while ((t = li.next(leftInThisDashSegment)) < 1.0f) { 374 if (t != 0.0f) { 375 Helpers.subdivideAt((t - lastSplitT) / (1.0f - lastSplitT), 376 curCurvepts, curCurveoff, 377 curCurvepts, 0, 378 curCurvepts, type, type); 379 lastSplitT = t; 380 goTo(curCurvepts, 2, type); 381 curCurveoff = type; 382 } 383 // Advance to next dash segment 384 idx = (idx + 1) % dashLen; 385 dashOn = !dashOn; 386 phase = 0.0f; 387 leftInThisDashSegment = dash[idx]; 388 } 389 goTo(curCurvepts, curCurveoff+2, type); 390 phase += li.lastSegLen(); 391 if (phase >= dash[idx]) { 392 phase = 0.0f; 393 idx = (idx + 1) % dashLen; 394 dashOn = !dashOn; 395 } 396 // reset LengthIterator: 397 li.reset(); 398 } 399 400 private static boolean pointCurve(float[] curve, int type) { 401 for (int i = 2; i < type; i++) { 402 if (curve[i] != curve[i-2]) { 403 return false; 404 } 405 } 406 return true; 407 } 408 409 // Objects of this class are used to iterate through curves. They return 410 // t values where the left side of the curve has a specified length. 411 // It does this by subdividing the input curve until a certain error 412 // condition has been met. A recursive subdivision procedure would 427 // only the right half of the original curve is at 0) 428 private final float[][] recCurveStack; // dirty 429 // sides[i] indicates whether the node at level i+1 in the path from 430 // the root to the current leaf is a left or right child of its parent. 431 private final Side[] sides; // dirty 432 private int curveType; 433 // lastT and nextT delimit the current leaf. 434 private float nextT; 435 private float lenAtNextT; 436 private float lastT; 437 private float lenAtLastT; 438 private float lenAtLastSplit; 439 private float lastSegLen; 440 // the current level in the recursion tree. 0 is the root. limit 441 // is the deepest possible leaf. 442 private int recLevel; 443 private boolean done; 444 445 // the lengths of the lines of the control polygon. Only its first 446 // curveType/2 - 1 elements are valid. This is an optimization. See 447 // next() for more detail. 448 private final float[] curLeafCtrlPolyLengths = new float[3]; 449 450 LengthIterator() { 451 this.recCurveStack = new float[REC_LIMIT + 1][8]; 452 this.sides = new Side[REC_LIMIT]; 453 // if any methods are called without first initializing this object 454 // on a curve, we want it to fail ASAP. 455 this.nextT = Float.MAX_VALUE; 456 this.lenAtNextT = Float.MAX_VALUE; 457 this.lenAtLastSplit = Float.MIN_VALUE; 458 this.recLevel = Integer.MIN_VALUE; 459 this.lastSegLen = Float.MAX_VALUE; 460 this.done = true; 461 } 462 463 /** 464 * Reset this LengthIterator. 465 */ 466 void reset() { 467 // keep data dirty 468 // as it appears not useful to reset data: 469 if (DO_CLEAN_DIRTY) { 470 final int recLimit = recCurveStack.length - 1; 471 for (int i = recLimit; i >= 0; i--) { 472 Arrays.fill(recCurveStack[i], 0.0f); 473 } 474 Arrays.fill(sides, Side.LEFT); 475 Arrays.fill(curLeafCtrlPolyLengths, 0.0f); 476 Arrays.fill(nextRoots, 0.0f); 477 Arrays.fill(flatLeafCoefCache, 0.0f); 478 flatLeafCoefCache[2] = -1.0f; 479 } 480 } 481 482 void initializeIterationOnCurve(float[] pts, int type) { 483 // optimize arraycopy (8 values faster than 6 = type): 484 System.arraycopy(pts, 0, recCurveStack[0], 0, 8); 485 this.curveType = type; 486 this.recLevel = 0; 487 this.lastT = 0.0f; 488 this.lenAtLastT = 0.0f; 489 this.nextT = 0.0f; 490 this.lenAtNextT = 0.0f; 491 goLeft(); // initializes nextT and lenAtNextT properly 492 this.lenAtLastSplit = 0.0f; 493 if (recLevel > 0) { 494 this.sides[0] = Side.LEFT; 495 this.done = false; 496 } else { 497 // the root of the tree is a leaf so we're done. 498 this.sides[0] = Side.RIGHT; 499 this.done = true; 500 } 501 this.lastSegLen = 0.0f; 502 } 503 504 // 0 == false, 1 == true, -1 == invalid cached value. 505 private int cachedHaveLowAcceleration = -1; 506 507 private boolean haveLowAcceleration(float err) { 508 if (cachedHaveLowAcceleration == -1) { 509 final float len1 = curLeafCtrlPolyLengths[0]; 510 final float len2 = curLeafCtrlPolyLengths[1]; 511 // the test below is equivalent to !within(len1/len2, 1, err). 512 // It is using a multiplication instead of a division, so it 513 // should be a bit faster. 514 if (!Helpers.within(len1, len2, err * len2)) { 515 cachedHaveLowAcceleration = 0; 516 return false; 517 } 518 if (curveType == 8) { 519 final float len3 = curLeafCtrlPolyLengths[2]; 520 // if len1 is close to 2 and 2 is close to 3, that probably 521 // means 1 is close to 3 so the second part of this test might 522 // not be needed, but it doesn't hurt to include it. 523 final float errLen3 = err * len3; 524 if (!(Helpers.within(len2, len3, errLen3) && 525 Helpers.within(len1, len3, errLen3))) { 526 cachedHaveLowAcceleration = 0; 527 return false; 528 } 529 } 530 cachedHaveLowAcceleration = 1; 531 return true; 532 } 533 534 return (cachedHaveLowAcceleration == 1); 535 } 536 537 // we want to avoid allocations/gc so we keep this array so we 538 // can put roots in it, 539 private final float[] nextRoots = new float[4]; 540 541 // caches the coefficients of the current leaf in its flattened 542 // form (see inside next() for what that means). The cache is 543 // invalid when it's third element is negative, since in any 544 // valid flattened curve, this would be >= 0. 545 private final float[] flatLeafCoefCache = new float[]{0.0f, 0.0f, -1.0f, 0.0f}; 546 547 // returns the t value where the remaining curve should be split in 548 // order for the left subdivided curve to have length len. If len 549 // is >= than the length of the uniterated curve, it returns 1. 550 float next(final float len) { 551 final float targetLength = lenAtLastSplit + len; 552 while (lenAtNextT < targetLength) { 553 if (done) { 554 lastSegLen = lenAtNextT - lenAtLastSplit; 555 return 1.0f; 556 } 557 goToNextLeaf(); 558 } 559 lenAtLastSplit = targetLength; 560 final float leaflen = lenAtNextT - lenAtLastT; 561 float t = (targetLength - lenAtLastT) / leaflen; 562 563 // cubicRootsInAB is a fairly expensive call, so we just don't do it 564 // if the acceleration in this section of the curve is small enough. 565 if (!haveLowAcceleration(0.05f)) { 566 // We flatten the current leaf along the x axis, so that we're 567 // left with a, b, c which define a 1D Bezier curve. We then 568 // solve this to get the parameter of the original leaf that 569 // gives us the desired length. 570 final float[] _flatLeafCoefCache = flatLeafCoefCache; 571 572 if (_flatLeafCoefCache[2] < 0.0f) { 573 float x = curLeafCtrlPolyLengths[0], 574 y = x + curLeafCtrlPolyLengths[1]; 575 if (curveType == 8) { 576 float z = y + curLeafCtrlPolyLengths[2]; 577 _flatLeafCoefCache[0] = 3.0f * (x - y) + z; 578 _flatLeafCoefCache[1] = 3.0f * (y - 2.0f * x); 579 _flatLeafCoefCache[2] = 3.0f * x; 580 _flatLeafCoefCache[3] = -z; 581 } else if (curveType == 6) { 582 _flatLeafCoefCache[0] = 0.0f; 583 _flatLeafCoefCache[1] = y - 2.0f * x; 584 _flatLeafCoefCache[2] = 2.0f * x; 585 _flatLeafCoefCache[3] = -y; 586 } 587 } 588 float a = _flatLeafCoefCache[0]; 589 float b = _flatLeafCoefCache[1]; 590 float c = _flatLeafCoefCache[2]; 591 float d = t * _flatLeafCoefCache[3]; 592 593 // we use cubicRootsInAB here, because we want only roots in 0, 1, 594 // and our quadratic root finder doesn't filter, so it's just a 595 // matter of convenience. 596 int n = Helpers.cubicRootsInAB(a, b, c, d, nextRoots, 0, 0.0f, 1.0f); 597 if (n == 1 && !Float.isNaN(nextRoots[0])) { 598 t = nextRoots[0]; 599 } 600 } 601 // t is relative to the current leaf, so we must make it a valid parameter 602 // of the original curve. 603 t = t * (nextT - lastT) + lastT; 604 if (t >= 1.0f) { 605 t = 1.0f; 606 done = true; 607 } 608 // even if done = true, if we're here, that means targetLength 609 // is equal to, or very, very close to the total length of the 610 // curve, so lastSegLen won't be too high. In cases where len 611 // overshoots the curve, this method will exit in the while 612 // loop, and lastSegLen will still be set to the right value. 613 lastSegLen = len; 614 return t; 615 } 616 617 float lastSegLen() { 618 return lastSegLen; 619 } 620 621 // go to the next leaf (in an inorder traversal) in the recursion tree 622 // preconditions: must be on a leaf, and that leaf must not be the root. 623 private void goToNextLeaf() { 624 // We must go to the first ancestor node that has an unvisited 625 // right child. 632 recLevel = 0; 633 done = true; 634 return; 635 } 636 _recLevel--; 637 } 638 639 _sides[_recLevel] = Side.RIGHT; 640 // optimize arraycopy (8 values faster than 6 = type): 641 System.arraycopy(recCurveStack[_recLevel], 0, 642 recCurveStack[_recLevel+1], 0, 8); 643 _recLevel++; 644 645 recLevel = _recLevel; 646 goLeft(); 647 } 648 649 // go to the leftmost node from the current node. Return its length. 650 private void goLeft() { 651 float len = onLeaf(); 652 if (len >= 0.0f) { 653 lastT = nextT; 654 lenAtLastT = lenAtNextT; 655 nextT += (1 << (REC_LIMIT - recLevel)) * MIN_T_INC; 656 lenAtNextT += len; 657 // invalidate caches 658 flatLeafCoefCache[2] = -1.0f; 659 cachedHaveLowAcceleration = -1; 660 } else { 661 Helpers.subdivide(recCurveStack[recLevel], 0, 662 recCurveStack[recLevel+1], 0, 663 recCurveStack[recLevel], 0, curveType); 664 sides[recLevel] = Side.LEFT; 665 recLevel++; 666 goLeft(); 667 } 668 } 669 670 // this is a bit of a hack. It returns -1 if we're not on a leaf, and 671 // the length of the leaf if we are on a leaf. 672 private float onLeaf() { 673 float[] curve = recCurveStack[recLevel]; 674 float polyLen = 0.0f; 675 676 float x0 = curve[0], y0 = curve[1]; 677 for (int i = 2; i < curveType; i += 2) { 678 final float x1 = curve[i], y1 = curve[i+1]; 679 final float len = Helpers.linelen(x0, y0, x1, y1); 680 polyLen += len; 681 curLeafCtrlPolyLengths[i/2 - 1] = len; 682 x0 = x1; 683 y0 = y1; 684 } 685 686 final float lineLen = Helpers.linelen(curve[0], curve[1], 687 curve[curveType-2], 688 curve[curveType-1]); 689 if ((polyLen - lineLen) < ERR || recLevel == REC_LIMIT) { 690 return (polyLen + lineLen) / 2.0f; 691 } 692 return -1.0f; 693 } 694 } 695 696 @Override 697 public void curveTo(float x1, float y1, 698 float x2, float y2, 699 float x3, float y3) 700 { 701 final float[] _curCurvepts = curCurvepts; 702 _curCurvepts[0] = x0; _curCurvepts[1] = y0; 703 _curCurvepts[2] = x1; _curCurvepts[3] = y1; 704 _curCurvepts[4] = x2; _curCurvepts[5] = y2; 705 _curCurvepts[6] = x3; _curCurvepts[7] = y3; 706 somethingTo(8); 707 } 708 709 @Override 710 public void quadTo(float x1, float y1, float x2, float y2) { 711 final float[] _curCurvepts = curCurvepts; 712 _curCurvepts[0] = x0; _curCurvepts[1] = y0; |