1 /* 2 * Copyright (c) 2007, 2011, 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.pisces; 27 28 import sun.awt.geom.PathConsumer2D; 29 30 /** 31 * The {@code Dasher} class takes a series of linear commands 32 * ({@code moveTo}, {@code lineTo}, {@code close} and 33 * {@code end}) and breaks them into smaller segments according to a 34 * dash pattern array and a starting dash phase. 35 * 36 * <p> Issues: in J2Se, a zero length dash segment as drawn as a very 37 * short dash, whereas Pisces does not draw anything. The PostScript 38 * semantics are unclear. 39 * 40 */ 41 final class Dasher implements sun.awt.geom.PathConsumer2D { 42 43 private final PathConsumer2D out; 44 private final float[] dash; 45 private final float startPhase; 46 private final boolean startDashOn; 47 private final int startIdx; 48 49 private boolean starting; 50 private boolean needsMoveTo; 51 52 private int idx; 53 private boolean dashOn; 54 private float phase; 55 56 private float sx, sy; 57 private float x0, y0; 58 59 // temporary storage for the current curve 60 private float[] curCurvepts; 61 62 /** 63 * Constructs a {@code Dasher}. 64 * 65 * @param out an output {@code PathConsumer2D}. 66 * @param dash an array of {@code float}s containing the dash pattern 67 * @param phase a {@code float} containing the dash phase 68 */ 69 public Dasher(PathConsumer2D out, float[] dash, float phase) { 70 if (phase < 0) { 71 throw new IllegalArgumentException("phase < 0 !"); 72 } 73 74 this.out = out; 75 76 // Normalize so 0 <= phase < dash[0] 77 int idx = 0; 78 dashOn = true; 79 float d; 80 while (phase >= (d = dash[idx])) { 81 phase -= d; 82 idx = (idx + 1) % dash.length; 83 dashOn = !dashOn; 84 } 85 86 this.dash = dash; 87 this.startPhase = this.phase = phase; 88 this.startDashOn = dashOn; 89 this.startIdx = idx; 90 this.starting = true; 91 92 // we need curCurvepts to be able to contain 2 curves because when 93 // dashing curves, we need to subdivide it 94 curCurvepts = new float[8 * 2]; 95 } 96 97 public void moveTo(float x0, float y0) { 98 if (firstSegidx > 0) { 99 out.moveTo(sx, sy); 100 emitFirstSegments(); 101 } 102 needsMoveTo = true; 103 this.idx = startIdx; 104 this.dashOn = this.startDashOn; 105 this.phase = this.startPhase; 106 this.sx = this.x0 = x0; 107 this.sy = this.y0 = y0; 108 this.starting = true; 109 } 110 111 private void emitSeg(float[] buf, int off, int type) { 112 switch (type) { 113 case 8: 114 out.curveTo(buf[off+0], buf[off+1], 115 buf[off+2], buf[off+3], 116 buf[off+4], buf[off+5]); 117 break; 118 case 6: 119 out.quadTo(buf[off+0], buf[off+1], 120 buf[off+2], buf[off+3]); 121 break; 122 case 4: 123 out.lineTo(buf[off], buf[off+1]); 124 } 125 } 126 127 private void emitFirstSegments() { 128 for (int i = 0; i < firstSegidx; ) { 129 emitSeg(firstSegmentsBuffer, i+1, (int)firstSegmentsBuffer[i]); 130 i += (((int)firstSegmentsBuffer[i]) - 1); 131 } 132 firstSegidx = 0; 133 } 134 135 // We don't emit the first dash right away. If we did, caps would be 136 // drawn on it, but we need joins to be drawn if there's a closePath() 137 // So, we store the path elements that make up the first dash in the 138 // buffer below. 139 private float[] firstSegmentsBuffer = new float[7]; 140 private int firstSegidx = 0; 141 // precondition: pts must be in relative coordinates (relative to x0,y0) 142 // fullCurve is true iff the curve in pts has not been split. 143 private void goTo(float[] pts, int off, final int type) { 144 float x = pts[off + type - 4]; 145 float y = pts[off + type - 3]; 146 if (dashOn) { 147 if (starting) { 148 firstSegmentsBuffer = Helpers.widenArray(firstSegmentsBuffer, 149 firstSegidx, type - 2 + 1); 150 firstSegmentsBuffer[firstSegidx++] = type; 151 System.arraycopy(pts, off, firstSegmentsBuffer, firstSegidx, type - 2); 152 firstSegidx += type - 2; 153 } else { 154 if (needsMoveTo) { 155 out.moveTo(x0, y0); 156 needsMoveTo = false; 157 } 158 emitSeg(pts, off, type); 159 } 160 } else { 161 starting = false; 162 needsMoveTo = true; 163 } 164 this.x0 = x; 165 this.y0 = y; 166 } 167 168 public void lineTo(float x1, float y1) { 169 float dx = x1 - x0; 170 float dy = y1 - y0; 171 172 float len = (float) Math.sqrt(dx*dx + dy*dy); 173 174 if (len == 0) { 175 return; 176 } 177 178 // The scaling factors needed to get the dx and dy of the 179 // transformed dash segments. 180 float cx = dx / len; 181 float cy = dy / len; 182 183 while (true) { 184 float leftInThisDashSegment = dash[idx] - phase; 185 if (len <= leftInThisDashSegment) { 186 curCurvepts[0] = x1; 187 curCurvepts[1] = y1; 188 goTo(curCurvepts, 0, 4); 189 // Advance phase within current dash segment 190 phase += len; 191 if (len == leftInThisDashSegment) { 192 phase = 0f; 193 idx = (idx + 1) % dash.length; 194 dashOn = !dashOn; 195 } 196 return; 197 } 198 199 float dashdx = dash[idx] * cx; 200 float dashdy = dash[idx] * cy; 201 if (phase == 0) { 202 curCurvepts[0] = x0 + dashdx; 203 curCurvepts[1] = y0 + dashdy; 204 } else { 205 float p = leftInThisDashSegment / dash[idx]; 206 curCurvepts[0] = x0 + p * dashdx; 207 curCurvepts[1] = y0 + p * dashdy; 208 } 209 210 goTo(curCurvepts, 0, 4); 211 212 len -= leftInThisDashSegment; 213 // Advance to next dash segment 214 idx = (idx + 1) % dash.length; 215 dashOn = !dashOn; 216 phase = 0; 217 } 218 } 219 220 private LengthIterator li = null; 221 222 // preconditions: curCurvepts must be an array of length at least 2 * type, 223 // that contains the curve we want to dash in the first type elements 224 private void somethingTo(int type) { 225 if (pointCurve(curCurvepts, type)) { 226 return; 227 } 228 if (li == null) { 229 li = new LengthIterator(4, 0.01f); 230 } 231 li.initializeIterationOnCurve(curCurvepts, type); 232 233 int curCurveoff = 0; // initially the current curve is at curCurvepts[0...type] 234 float lastSplitT = 0; 235 float t = 0; 236 float leftInThisDashSegment = dash[idx] - phase; 237 while ((t = li.next(leftInThisDashSegment)) < 1) { 238 if (t != 0) { 239 Helpers.subdivideAt((t - lastSplitT) / (1 - lastSplitT), 240 curCurvepts, curCurveoff, 241 curCurvepts, 0, 242 curCurvepts, type, type); 243 lastSplitT = t; 244 goTo(curCurvepts, 2, type); 245 curCurveoff = type; 246 } 247 // Advance to next dash segment 248 idx = (idx + 1) % dash.length; 249 dashOn = !dashOn; 250 phase = 0; 251 leftInThisDashSegment = dash[idx]; 252 } 253 goTo(curCurvepts, curCurveoff+2, type); 254 phase += li.lastSegLen(); 255 if (phase >= dash[idx]) { 256 phase = 0f; 257 idx = (idx + 1) % dash.length; 258 dashOn = !dashOn; 259 } 260 } 261 262 private static boolean pointCurve(float[] curve, int type) { 263 for (int i = 2; i < type; i++) { 264 if (curve[i] != curve[i-2]) { 265 return false; 266 } 267 } 268 return true; 269 } 270 271 // Objects of this class are used to iterate through curves. They return 272 // t values where the left side of the curve has a specified length. 273 // It does this by subdividing the input curve until a certain error 274 // condition has been met. A recursive subdivision procedure would 275 // return as many as 1<<limit curves, but this is an iterator and we 276 // don't need all the curves all at once, so what we carry out a 277 // lazy inorder traversal of the recursion tree (meaning we only move 278 // through the tree when we need the next subdivided curve). This saves 279 // us a lot of memory because at any one time we only need to store 280 // limit+1 curves - one for each level of the tree + 1. 281 // NOTE: the way we do things here is not enough to traverse a general 282 // tree; however, the trees we are interested in have the property that 283 // every non leaf node has exactly 2 children 284 private static class LengthIterator { 285 private enum Side {LEFT, RIGHT}; 286 // Holds the curves at various levels of the recursion. The root 287 // (i.e. the original curve) is at recCurveStack[0] (but then it 288 // gets subdivided, the left half is put at 1, so most of the time 289 // only the right half of the original curve is at 0) 290 private float[][] recCurveStack; 291 // sides[i] indicates whether the node at level i+1 in the path from 292 // the root to the current leaf is a left or right child of its parent. 293 private Side[] sides; 294 private int curveType; 295 private final int limit; 296 private final float ERR; 297 private final float minTincrement; 298 // lastT and nextT delimit the current leaf. 299 private float nextT; 300 private float lenAtNextT; 301 private float lastT; 302 private float lenAtLastT; 303 private float lenAtLastSplit; 304 private float lastSegLen; 305 // the current level in the recursion tree. 0 is the root. limit 306 // is the deepest possible leaf. 307 private int recLevel; 308 private boolean done; 309 310 // the lengths of the lines of the control polygon. Only its first 311 // curveType/2 - 1 elements are valid. This is an optimization. See 312 // next(float) for more detail. 313 private float[] curLeafCtrlPolyLengths = new float[3]; 314 315 public LengthIterator(int reclimit, float err) { 316 this.limit = reclimit; 317 this.minTincrement = 1f / (1 << limit); 318 this.ERR = err; 319 this.recCurveStack = new float[reclimit+1][8]; 320 this.sides = new Side[reclimit]; 321 // if any methods are called without first initializing this object on 322 // a curve, we want it to fail ASAP. 323 this.nextT = Float.MAX_VALUE; 324 this.lenAtNextT = Float.MAX_VALUE; 325 this.lenAtLastSplit = Float.MIN_VALUE; 326 this.recLevel = Integer.MIN_VALUE; 327 this.lastSegLen = Float.MAX_VALUE; 328 this.done = true; 329 } 330 331 public void initializeIterationOnCurve(float[] pts, int type) { 332 System.arraycopy(pts, 0, recCurveStack[0], 0, type); 333 this.curveType = type; 334 this.recLevel = 0; 335 this.lastT = 0; 336 this.lenAtLastT = 0; 337 this.nextT = 0; 338 this.lenAtNextT = 0; 339 goLeft(); // initializes nextT and lenAtNextT properly 340 this.lenAtLastSplit = 0; 341 if (recLevel > 0) { 342 this.sides[0] = Side.LEFT; 343 this.done = false; 344 } else { 345 // the root of the tree is a leaf so we're done. 346 this.sides[0] = Side.RIGHT; 347 this.done = true; 348 } 349 this.lastSegLen = 0; 350 } 351 352 // 0 == false, 1 == true, -1 == invalid cached value. 353 private int cachedHaveLowAcceleration = -1; 354 355 private boolean haveLowAcceleration(float err) { 356 if (cachedHaveLowAcceleration == -1) { 357 final float len1 = curLeafCtrlPolyLengths[0]; 358 final float len2 = curLeafCtrlPolyLengths[1]; 359 // the test below is equivalent to !within(len1/len2, 1, err). 360 // It is using a multiplication instead of a division, so it 361 // should be a bit faster. 362 if (!Helpers.within(len1, len2, err*len2)) { 363 cachedHaveLowAcceleration = 0; 364 return false; 365 } 366 if (curveType == 8) { 367 final float len3 = curLeafCtrlPolyLengths[2]; 368 // if len1 is close to 2 and 2 is close to 3, that probably 369 // means 1 is close to 3 so the second part of this test might 370 // not be needed, but it doesn't hurt to include it. 371 if (!(Helpers.within(len2, len3, err*len3) && 372 Helpers.within(len1, len3, err*len3))) { 373 cachedHaveLowAcceleration = 0; 374 return false; 375 } 376 } 377 cachedHaveLowAcceleration = 1; 378 return true; 379 } 380 381 return (cachedHaveLowAcceleration == 1); 382 } 383 384 // we want to avoid allocations/gc so we keep this array so we 385 // can put roots in it, 386 private float[] nextRoots = new float[4]; 387 388 // caches the coefficients of the current leaf in its flattened 389 // form (see inside next() for what that means). The cache is 390 // invalid when it's third element is negative, since in any 391 // valid flattened curve, this would be >= 0. 392 private float[] flatLeafCoefCache = new float[] {0, 0, -1, 0}; 393 // returns the t value where the remaining curve should be split in 394 // order for the left subdivided curve to have length len. If len 395 // is >= than the length of the uniterated curve, it returns 1. 396 public float next(final float len) { 397 final float targetLength = lenAtLastSplit + len; 398 while(lenAtNextT < targetLength) { 399 if (done) { 400 lastSegLen = lenAtNextT - lenAtLastSplit; 401 return 1; 402 } 403 goToNextLeaf(); 404 } 405 lenAtLastSplit = targetLength; 406 final float leaflen = lenAtNextT - lenAtLastT; 407 float t = (targetLength - lenAtLastT) / leaflen; 408 409 // cubicRootsInAB is a fairly expensive call, so we just don't do it 410 // if the acceleration in this section of the curve is small enough. 411 if (!haveLowAcceleration(0.05f)) { 412 // We flatten the current leaf along the x axis, so that we're 413 // left with a, b, c which define a 1D Bezier curve. We then 414 // solve this to get the parameter of the original leaf that 415 // gives us the desired length. 416 417 if (flatLeafCoefCache[2] < 0) { 418 float x = 0+curLeafCtrlPolyLengths[0], 419 y = x+curLeafCtrlPolyLengths[1]; 420 if (curveType == 8) { 421 float z = y + curLeafCtrlPolyLengths[2]; 422 flatLeafCoefCache[0] = 3*(x - y) + z; 423 flatLeafCoefCache[1] = 3*(y - 2*x); 424 flatLeafCoefCache[2] = 3*x; 425 flatLeafCoefCache[3] = -z; 426 } else if (curveType == 6) { 427 flatLeafCoefCache[0] = 0f; 428 flatLeafCoefCache[1] = y - 2*x; 429 flatLeafCoefCache[2] = 2*x; 430 flatLeafCoefCache[3] = -y; 431 } 432 } 433 float a = flatLeafCoefCache[0]; 434 float b = flatLeafCoefCache[1]; 435 float c = flatLeafCoefCache[2]; 436 float d = t*flatLeafCoefCache[3]; 437 438 // we use cubicRootsInAB here, because we want only roots in 0, 1, 439 // and our quadratic root finder doesn't filter, so it's just a 440 // matter of convenience. 441 int n = Helpers.cubicRootsInAB(a, b, c, d, nextRoots, 0, 0, 1); 442 if (n == 1 && !Float.isNaN(nextRoots[0])) { 443 t = nextRoots[0]; 444 } 445 } 446 // t is relative to the current leaf, so we must make it a valid parameter 447 // of the original curve. 448 t = t * (nextT - lastT) + lastT; 449 if (t >= 1) { 450 t = 1; 451 done = true; 452 } 453 // even if done = true, if we're here, that means targetLength 454 // is equal to, or very, very close to the total length of the 455 // curve, so lastSegLen won't be too high. In cases where len 456 // overshoots the curve, this method will exit in the while 457 // loop, and lastSegLen will still be set to the right value. 458 lastSegLen = len; 459 return t; 460 } 461 462 public float lastSegLen() { 463 return lastSegLen; 464 } 465 466 // go to the next leaf (in an inorder traversal) in the recursion tree 467 // preconditions: must be on a leaf, and that leaf must not be the root. 468 private void goToNextLeaf() { 469 // We must go to the first ancestor node that has an unvisited 470 // right child. 471 recLevel--; 472 while(sides[recLevel] == Side.RIGHT) { 473 if (recLevel == 0) { 474 done = true; 475 return; 476 } 477 recLevel--; 478 } 479 480 sides[recLevel] = Side.RIGHT; 481 System.arraycopy(recCurveStack[recLevel], 0, recCurveStack[recLevel+1], 0, curveType); 482 recLevel++; 483 goLeft(); 484 } 485 486 // go to the leftmost node from the current node. Return its length. 487 private void goLeft() { 488 float len = onLeaf(); 489 if (len >= 0) { 490 lastT = nextT; 491 lenAtLastT = lenAtNextT; 492 nextT += (1 << (limit - recLevel)) * minTincrement; 493 lenAtNextT += len; 494 // invalidate caches 495 flatLeafCoefCache[2] = -1; 496 cachedHaveLowAcceleration = -1; 497 } else { 498 Helpers.subdivide(recCurveStack[recLevel], 0, 499 recCurveStack[recLevel+1], 0, 500 recCurveStack[recLevel], 0, curveType); 501 sides[recLevel] = Side.LEFT; 502 recLevel++; 503 goLeft(); 504 } 505 } 506 507 // this is a bit of a hack. It returns -1 if we're not on a leaf, and 508 // the length of the leaf if we are on a leaf. 509 private float onLeaf() { 510 float[] curve = recCurveStack[recLevel]; 511 float polyLen = 0; 512 513 float x0 = curve[0], y0 = curve[1]; 514 for (int i = 2; i < curveType; i += 2) { 515 final float x1 = curve[i], y1 = curve[i+1]; 516 final float len = Helpers.linelen(x0, y0, x1, y1); 517 polyLen += len; 518 curLeafCtrlPolyLengths[i/2 - 1] = len; 519 x0 = x1; 520 y0 = y1; 521 } 522 523 final float lineLen = Helpers.linelen(curve[0], curve[1], curve[curveType-2], curve[curveType-1]); 524 if (polyLen - lineLen < ERR || recLevel == limit) { 525 return (polyLen + lineLen)/2; 526 } 527 return -1; 528 } 529 } 530 531 @Override 532 public void curveTo(float x1, float y1, 533 float x2, float y2, 534 float x3, float y3) 535 { 536 curCurvepts[0] = x0; curCurvepts[1] = y0; 537 curCurvepts[2] = x1; curCurvepts[3] = y1; 538 curCurvepts[4] = x2; curCurvepts[5] = y2; 539 curCurvepts[6] = x3; curCurvepts[7] = y3; 540 somethingTo(8); 541 } 542 543 @Override 544 public void quadTo(float x1, float y1, float x2, float y2) { 545 curCurvepts[0] = x0; curCurvepts[1] = y0; 546 curCurvepts[2] = x1; curCurvepts[3] = y1; 547 curCurvepts[4] = x2; curCurvepts[5] = y2; 548 somethingTo(6); 549 } 550 551 public void closePath() { 552 lineTo(sx, sy); 553 if (firstSegidx > 0) { 554 if (!dashOn || needsMoveTo) { 555 out.moveTo(sx, sy); 556 } 557 emitFirstSegments(); 558 } 559 moveTo(sx, sy); 560 } 561 562 public void pathDone() { 563 if (firstSegidx > 0) { 564 out.moveTo(sx, sy); 565 emitFirstSegments(); 566 } 567 out.pathDone(); 568 } 569 570 @Override 571 public long getNativeConsumer() { 572 throw new InternalError("Dasher does not use a native consumer"); 573 } 574 } 575