1 /* 2 * Copyright (c) 2007, 2010, 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</code> class takes a series of linear commands 32 * (<code>moveTo</code>, <code>lineTo</code>, <code>close</code> and 33 * <code>end</code>) 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 public 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</code>. 64 * 65 * @param out an output <code>PathConsumer2D</code>. 66 * @param dash an array of <code>float</code>s containing the dash pattern 67 * @param phase a <code>float</code> 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); 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.hypot(dx, 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.0001f); 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 public LengthIterator(int reclimit, float err) { 311 this.limit = reclimit; 312 this.minTincrement = 1f / (1 << limit); 313 this.ERR = err; 314 this.recCurveStack = new float[reclimit+1][8]; 315 this.sides = new Side[reclimit]; 316 // if any methods are called without first initializing this object on 317 // a curve, we want it to fail ASAP. 318 this.nextT = Float.MAX_VALUE; 319 this.lenAtNextT = Float.MAX_VALUE; 320 this.lenAtLastSplit = Float.MIN_VALUE; 321 this.recLevel = Integer.MIN_VALUE; 322 this.lastSegLen = Float.MAX_VALUE; 323 this.done = true; 324 } 325 326 public void initializeIterationOnCurve(float[] pts, int type) { 327 System.arraycopy(pts, 0, recCurveStack[0], 0, type); 328 this.curveType = type; 329 this.recLevel = 0; 330 this.lastT = 0; 331 this.lenAtLastT = 0; 332 this.nextT = 0; 333 this.lenAtNextT = 0; 334 goLeft(); // initializes nextT and lenAtNextT properly 335 this.lenAtLastSplit = 0; 336 if (recLevel > 0) { 337 this.sides[0] = Side.LEFT; 338 this.done = false; 339 } else { 340 // the root of the tree is a leaf so we're done. 341 this.sides[0] = Side.RIGHT; 342 this.done = true; 343 } 344 this.lastSegLen = 0; 345 } 346 347 // returns the t value where the remaining curve should be split in 348 // order for the left subdivided curve to have length len. If len 349 // is >= than the length of the uniterated curve, it returns 1. 350 public float next(float len) { 351 float targetLength = lenAtLastSplit + len; 352 while(lenAtNextT < targetLength) { 353 if (done) { 354 lastSegLen = lenAtNextT - lenAtLastSplit; 355 return 1; 356 } 357 goToNextLeaf(); 358 } 359 lenAtLastSplit = targetLength; 360 float t = binSearchForLen(lenAtLastSplit - lenAtLastT, 361 recCurveStack[recLevel], curveType, lenAtNextT - lenAtLastT, ERR); 362 // t is relative to the current leaf, so we must make it a valid parameter 363 // of the original curve. 364 t = t * (nextT - lastT) + lastT; 365 if (t >= 1) { 366 t = 1; 367 done = true; 368 } 369 // even if done = true, if we're here, that means targetLength 370 // is equal to, or very, very close to the total length of the 371 // curve, so lastSegLen won't be too high. In cases where len 372 // overshoots the curve, this method will exit in the while 373 // loop, and lastSegLen will still be set to the right value. 374 lastSegLen = len; 375 return t; 376 } 377 378 public float lastSegLen() { 379 return lastSegLen; 380 } 381 382 // Returns t such that if leaf is subdivided at t the left 383 // curve will have length len. leafLen must be the length of leaf. 384 private static Curve bsc = new Curve(); 385 private static float binSearchForLen(float len, float[] leaf, int type, 386 float leafLen, float err) 387 { 388 assert len <= leafLen; 389 bsc.set(leaf, type); 390 float errBound = err*len; 391 float left = 0, right = 1; 392 while (left < right) { 393 float m = (left + right) / 2; 394 if (m == left || m == right) { 395 return m; 396 } 397 float x = bsc.xat(m); 398 float y = bsc.yat(m); 399 float leftLen = Helpers.linelen(leaf[0], leaf[1], x, y); 400 if (Math.abs(leftLen - len) < errBound) { 401 return m; 402 } 403 if (leftLen < len) { 404 left = m; 405 } else { 406 right = m; 407 } 408 } 409 return left; 410 } 411 412 // go to the next leaf (in an inorder traversal) in the recursion tree 413 // preconditions: must be on a leaf, and that leaf must not be the root. 414 private void goToNextLeaf() { 415 // We must go to the first ancestor node that has an unvisited 416 // right child. 417 recLevel--; 418 while(sides[recLevel] == Side.RIGHT) { 419 if (recLevel == 0) { 420 done = true; 421 return; 422 } 423 recLevel--; 424 } 425 426 sides[recLevel] = Side.RIGHT; 427 System.arraycopy(recCurveStack[recLevel], 0, recCurveStack[recLevel+1], 0, curveType); 428 recLevel++; 429 goLeft(); 430 } 431 432 // go to the leftmost node from the current node. Return its length. 433 private void goLeft() { 434 float len = onLeaf(); 435 if (len >= 0) { 436 lastT = nextT; 437 lenAtLastT = lenAtNextT; 438 nextT += (1 << (limit - recLevel)) * minTincrement; 439 lenAtNextT += len; 440 } else { 441 Helpers.subdivide(recCurveStack[recLevel], 0, 442 recCurveStack[recLevel+1], 0, 443 recCurveStack[recLevel], 0, curveType); 444 sides[recLevel] = Side.LEFT; 445 recLevel++; 446 goLeft(); 447 } 448 } 449 450 // this is a bit of a hack. It returns -1 if we're not on a leaf, and 451 // the length of the leaf if we are on a leaf. 452 private float onLeaf() { 453 float polylen = Helpers.polyLineLength(recCurveStack[recLevel], 0, curveType); 454 float linelen = Helpers.linelen(recCurveStack[recLevel][0], recCurveStack[recLevel][1], 455 recCurveStack[recLevel][curveType - 2], recCurveStack[recLevel][curveType - 1]); 456 return (polylen - linelen < ERR || recLevel == limit) ? 457 (polylen + linelen)/2 : -1; 458 } 459 } 460 461 @Override 462 public void curveTo(float x1, float y1, 463 float x2, float y2, 464 float x3, float y3) 465 { 466 curCurvepts[0] = x0; curCurvepts[1] = y0; 467 curCurvepts[2] = x1; curCurvepts[3] = y1; 468 curCurvepts[4] = x2; curCurvepts[5] = y2; 469 curCurvepts[6] = x3; curCurvepts[7] = y3; 470 somethingTo(8); 471 } 472 473 @Override 474 public void quadTo(float x1, float y1, float x2, float y2) { 475 curCurvepts[0] = x0; curCurvepts[1] = y0; 476 curCurvepts[2] = x1; curCurvepts[3] = y1; 477 curCurvepts[4] = x2; curCurvepts[5] = y2; 478 somethingTo(6); 479 } 480 481 public void closePath() { 482 lineTo(sx, sy); 483 if (firstSegidx > 0) { 484 if (!dashOn || needsMoveTo) { 485 out.moveTo(sx, sy); 486 } 487 emitFirstSegments(); 488 } 489 moveTo(sx, sy); 490 } 491 492 public void pathDone() { 493 if (firstSegidx > 0) { 494 out.moveTo(sx, sy); 495 emitFirstSegments(); 496 } 497 out.pathDone(); 498 } 499 500 @Override 501 public long getNativeConsumer() { 502 throw new InternalError("Dasher does not use a native consumer"); 503 } 504 } 505