PathParser.java revision 897f6daeffe965d546ebdc9a05c99a638b37f37d
1/* 2 * Copyright (C) 2014 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 5 * in compliance with the License. You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software distributed under the License 10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 11 * or implied. See the License for the specific language governing permissions and limitations under 12 * the License. 13 */ 14 15package android.util; 16 17import android.graphics.Path; 18import android.util.Log; 19 20import java.util.ArrayList; 21import java.util.Arrays; 22 23/** 24 * @hide 25 */ 26public class PathParser { 27 static final String LOGTAG = PathParser.class.getSimpleName(); 28 29 /** 30 * @param pathData The string representing a path, the same as "d" string in svg file. 31 * @return the generated Path object. 32 */ 33 public static Path createPathFromPathData(String pathData) { 34 Path path = new Path(); 35 PathDataNode[] nodes = createNodesFromPathData(pathData); 36 if (nodes != null) { 37 try { 38 PathDataNode.nodesToPath(nodes, path); 39 } catch (RuntimeException e) { 40 throw new RuntimeException("Error in parsing " + pathData, e); 41 } 42 return path; 43 } 44 return null; 45 } 46 47 /** 48 * @param pathData The string representing a path, the same as "d" string in svg file. 49 * @return an array of the PathDataNode. 50 */ 51 public static PathDataNode[] createNodesFromPathData(String pathData) { 52 if (pathData == null) { 53 return null; 54 } 55 int start = 0; 56 int end = 1; 57 58 ArrayList<PathDataNode> list = new ArrayList<PathDataNode>(); 59 while (end < pathData.length()) { 60 end = nextStart(pathData, end); 61 String s = pathData.substring(start, end).trim(); 62 if (s.length() > 0) { 63 float[] val = getFloats(s); 64 addNode(list, s.charAt(0), val); 65 } 66 67 start = end; 68 end++; 69 } 70 if ((end - start) == 1 && start < pathData.length()) { 71 addNode(list, pathData.charAt(start), new float[0]); 72 } 73 return list.toArray(new PathDataNode[list.size()]); 74 } 75 76 /** 77 * @param source The array of PathDataNode to be duplicated. 78 * @return a deep copy of the <code>source</code>. 79 */ 80 public static PathDataNode[] deepCopyNodes(PathDataNode[] source) { 81 if (source == null) { 82 return null; 83 } 84 PathDataNode[] copy = new PathParser.PathDataNode[source.length]; 85 for (int i = 0; i < source.length; i ++) { 86 copy[i] = new PathDataNode(source[i]); 87 } 88 return copy; 89 } 90 91 /** 92 * @param nodesFrom The source path represented in an array of PathDataNode 93 * @param nodesTo The target path represented in an array of PathDataNode 94 * @return whether the <code>nodesFrom</code> can morph into <code>nodesTo</code> 95 */ 96 public static boolean canMorph(PathDataNode[] nodesFrom, PathDataNode[] nodesTo) { 97 if (nodesFrom == null || nodesTo == null) { 98 return false; 99 } 100 101 if (nodesFrom.length != nodesTo.length) { 102 return false; 103 } 104 105 for (int i = 0; i < nodesFrom.length; i ++) { 106 if (nodesFrom[i].mType != nodesTo[i].mType 107 || nodesFrom[i].mParams.length != nodesTo[i].mParams.length) { 108 return false; 109 } 110 } 111 return true; 112 } 113 114 /** 115 * Update the target's data to match the source. 116 * Before calling this, make sure canMorph(target, source) is true. 117 * 118 * @param target The target path represented in an array of PathDataNode 119 * @param source The source path represented in an array of PathDataNode 120 */ 121 public static void updateNodes(PathDataNode[] target, PathDataNode[] source) { 122 for (int i = 0; i < source.length; i ++) { 123 target[i].mType = source[i].mType; 124 for (int j = 0; j < source[i].mParams.length; j ++) { 125 target[i].mParams[j] = source[i].mParams[j]; 126 } 127 } 128 } 129 130 private static int nextStart(String s, int end) { 131 char c; 132 133 while (end < s.length()) { 134 c = s.charAt(end); 135 // Note that 'e' or 'E' are not valid path commands, but could be 136 // used for floating point numbers' scientific notation. 137 // Therefore, when searching for next command, we should ignore 'e' 138 // and 'E'. 139 if ((((c - 'A') * (c - 'Z') <= 0) || ((c - 'a') * (c - 'z') <= 0)) 140 && c != 'e' && c != 'E') { 141 return end; 142 } 143 end++; 144 } 145 return end; 146 } 147 148 private static void addNode(ArrayList<PathDataNode> list, char cmd, float[] val) { 149 list.add(new PathDataNode(cmd, val)); 150 } 151 152 private static class ExtractFloatResult { 153 // We need to return the position of the next separator and whether the 154 // next float starts with a '-' or a '.'. 155 int mEndPosition; 156 boolean mEndWithNegOrDot; 157 } 158 159 /** 160 * Parse the floats in the string. 161 * This is an optimized version of parseFloat(s.split(",|\\s")); 162 * 163 * @param s the string containing a command and list of floats 164 * @return array of floats 165 */ 166 private static float[] getFloats(String s) { 167 if (s.charAt(0) == 'z' | s.charAt(0) == 'Z') { 168 return new float[0]; 169 } 170 try { 171 float[] results = new float[s.length()]; 172 int count = 0; 173 int startPosition = 1; 174 int endPosition = 0; 175 176 ExtractFloatResult result = new ExtractFloatResult(); 177 int totalLength = s.length(); 178 179 // The startPosition should always be the first character of the 180 // current number, and endPosition is the character after the current 181 // number. 182 while (startPosition < totalLength) { 183 extract(s, startPosition, result); 184 endPosition = result.mEndPosition; 185 186 if (startPosition < endPosition) { 187 results[count++] = Float.parseFloat( 188 s.substring(startPosition, endPosition)); 189 } 190 191 if (result.mEndWithNegOrDot) { 192 // Keep the '-' or '.' sign with next number. 193 startPosition = endPosition; 194 } else { 195 startPosition = endPosition + 1; 196 } 197 } 198 return Arrays.copyOf(results, count); 199 } catch (NumberFormatException e) { 200 throw new RuntimeException("error in parsing \"" + s + "\"", e); 201 } 202 } 203 204 /** 205 * Calculate the position of the next comma or space or negative sign 206 * @param s the string to search 207 * @param start the position to start searching 208 * @param result the result of the extraction, including the position of the 209 * the starting position of next number, whether it is ending with a '-'. 210 */ 211 private static void extract(String s, int start, ExtractFloatResult result) { 212 // Now looking for ' ', ',', '.' or '-' from the start. 213 int currentIndex = start; 214 boolean foundSeparator = false; 215 result.mEndWithNegOrDot = false; 216 boolean secondDot = false; 217 boolean isExponential = false; 218 for (; currentIndex < s.length(); currentIndex++) { 219 boolean isPrevExponential = isExponential; 220 isExponential = false; 221 char currentChar = s.charAt(currentIndex); 222 switch (currentChar) { 223 case ' ': 224 case ',': 225 foundSeparator = true; 226 break; 227 case '-': 228 // The negative sign following a 'e' or 'E' is not a separator. 229 if (currentIndex != start && !isPrevExponential) { 230 foundSeparator = true; 231 result.mEndWithNegOrDot = true; 232 } 233 break; 234 case '.': 235 if (!secondDot) { 236 secondDot = true; 237 } else { 238 // This is the second dot, and it is considered as a separator. 239 foundSeparator = true; 240 result.mEndWithNegOrDot = true; 241 } 242 break; 243 case 'e': 244 case 'E': 245 isExponential = true; 246 break; 247 } 248 if (foundSeparator) { 249 break; 250 } 251 } 252 // When there is nothing found, then we put the end position to the end 253 // of the string. 254 result.mEndPosition = currentIndex; 255 } 256 257 /** 258 * Each PathDataNode represents one command in the "d" attribute of the svg 259 * file. 260 * An array of PathDataNode can represent the whole "d" attribute. 261 */ 262 public static class PathDataNode { 263 private char mType; 264 private float[] mParams; 265 266 private PathDataNode(char type, float[] params) { 267 mType = type; 268 mParams = params; 269 } 270 271 private PathDataNode(PathDataNode n) { 272 mType = n.mType; 273 mParams = Arrays.copyOf(n.mParams, n.mParams.length); 274 } 275 276 /** 277 * Convert an array of PathDataNode to Path. 278 * 279 * @param node The source array of PathDataNode. 280 * @param path The target Path object. 281 */ 282 public static void nodesToPath(PathDataNode[] node, Path path) { 283 float[] current = new float[4]; 284 char previousCommand = 'm'; 285 for (int i = 0; i < node.length; i++) { 286 addCommand(path, current, previousCommand, node[i].mType, node[i].mParams); 287 previousCommand = node[i].mType; 288 } 289 } 290 291 /** 292 * The current PathDataNode will be interpolated between the 293 * <code>nodeFrom</code> and <code>nodeTo</code> according to the 294 * <code>fraction</code>. 295 * 296 * @param nodeFrom The start value as a PathDataNode. 297 * @param nodeTo The end value as a PathDataNode 298 * @param fraction The fraction to interpolate. 299 */ 300 public void interpolatePathDataNode(PathDataNode nodeFrom, 301 PathDataNode nodeTo, float fraction) { 302 for (int i = 0; i < nodeFrom.mParams.length; i++) { 303 mParams[i] = nodeFrom.mParams[i] * (1 - fraction) 304 + nodeTo.mParams[i] * fraction; 305 } 306 } 307 308 private static void addCommand(Path path, float[] current, 309 char previousCmd, char cmd, float[] val) { 310 311 int incr = 2; 312 float currentX = current[0]; 313 float currentY = current[1]; 314 float ctrlPointX = current[2]; 315 float ctrlPointY = current[3]; 316 float reflectiveCtrlPointX; 317 float reflectiveCtrlPointY; 318 319 switch (cmd) { 320 case 'z': 321 case 'Z': 322 path.close(); 323 return; 324 case 'm': 325 case 'M': 326 case 'l': 327 case 'L': 328 case 't': 329 case 'T': 330 incr = 2; 331 break; 332 case 'h': 333 case 'H': 334 case 'v': 335 case 'V': 336 incr = 1; 337 break; 338 case 'c': 339 case 'C': 340 incr = 6; 341 break; 342 case 's': 343 case 'S': 344 case 'q': 345 case 'Q': 346 incr = 4; 347 break; 348 case 'a': 349 case 'A': 350 incr = 7; 351 break; 352 } 353 for (int k = 0; k < val.length; k += incr) { 354 switch (cmd) { 355 case 'm': // moveto - Start a new sub-path (relative) 356 path.rMoveTo(val[k + 0], val[k + 1]); 357 currentX += val[k + 0]; 358 currentY += val[k + 1]; 359 break; 360 case 'M': // moveto - Start a new sub-path 361 path.moveTo(val[k + 0], val[k + 1]); 362 currentX = val[k + 0]; 363 currentY = val[k + 1]; 364 break; 365 case 'l': // lineto - Draw a line from the current point (relative) 366 path.rLineTo(val[k + 0], val[k + 1]); 367 currentX += val[k + 0]; 368 currentY += val[k + 1]; 369 break; 370 case 'L': // lineto - Draw a line from the current point 371 path.lineTo(val[k + 0], val[k + 1]); 372 currentX = val[k + 0]; 373 currentY = val[k + 1]; 374 break; 375 case 'z': // closepath - Close the current subpath 376 case 'Z': // closepath - Close the current subpath 377 path.close(); 378 break; 379 case 'h': // horizontal lineto - Draws a horizontal line (relative) 380 path.rLineTo(val[k + 0], 0); 381 currentX += val[k + 0]; 382 break; 383 case 'H': // horizontal lineto - Draws a horizontal line 384 path.lineTo(val[k + 0], currentY); 385 currentX = val[k + 0]; 386 break; 387 case 'v': // vertical lineto - Draws a vertical line from the current point (r) 388 path.rLineTo(0, val[k + 0]); 389 currentY += val[k + 0]; 390 break; 391 case 'V': // vertical lineto - Draws a vertical line from the current point 392 path.lineTo(currentX, val[k + 0]); 393 currentY = val[k + 0]; 394 break; 395 case 'c': // curveto - Draws a cubic Bézier curve (relative) 396 path.rCubicTo(val[k + 0], val[k + 1], val[k + 2], val[k + 3], 397 val[k + 4], val[k + 5]); 398 399 ctrlPointX = currentX + val[k + 2]; 400 ctrlPointY = currentY + val[k + 3]; 401 currentX += val[k + 4]; 402 currentY += val[k + 5]; 403 404 break; 405 case 'C': // curveto - Draws a cubic Bézier curve 406 path.cubicTo(val[k + 0], val[k + 1], val[k + 2], val[k + 3], 407 val[k + 4], val[k + 5]); 408 currentX = val[k + 4]; 409 currentY = val[k + 5]; 410 ctrlPointX = val[k + 2]; 411 ctrlPointY = val[k + 3]; 412 break; 413 case 's': // smooth curveto - Draws a cubic Bézier curve (reflective cp) 414 reflectiveCtrlPointX = 0; 415 reflectiveCtrlPointY = 0; 416 if (previousCmd == 'c' || previousCmd == 's' 417 || previousCmd == 'C' || previousCmd == 'S') { 418 reflectiveCtrlPointX = currentX - ctrlPointX; 419 reflectiveCtrlPointY = currentY - ctrlPointY; 420 } 421 path.rCubicTo(reflectiveCtrlPointX, reflectiveCtrlPointY, 422 val[k + 0], val[k + 1], 423 val[k + 2], val[k + 3]); 424 425 ctrlPointX = currentX + val[k + 0]; 426 ctrlPointY = currentY + val[k + 1]; 427 currentX += val[k + 2]; 428 currentY += val[k + 3]; 429 break; 430 case 'S': // shorthand/smooth curveto Draws a cubic Bézier curve(reflective cp) 431 reflectiveCtrlPointX = currentX; 432 reflectiveCtrlPointY = currentY; 433 if (previousCmd == 'c' || previousCmd == 's' 434 || previousCmd == 'C' || previousCmd == 'S') { 435 reflectiveCtrlPointX = 2 * currentX - ctrlPointX; 436 reflectiveCtrlPointY = 2 * currentY - ctrlPointY; 437 } 438 path.cubicTo(reflectiveCtrlPointX, reflectiveCtrlPointY, 439 val[k + 0], val[k + 1], val[k + 2], val[k + 3]); 440 ctrlPointX = val[k + 0]; 441 ctrlPointY = val[k + 1]; 442 currentX = val[k + 2]; 443 currentY = val[k + 3]; 444 break; 445 case 'q': // Draws a quadratic Bézier (relative) 446 path.rQuadTo(val[k + 0], val[k + 1], val[k + 2], val[k + 3]); 447 ctrlPointX = currentX + val[k + 0]; 448 ctrlPointY = currentY + val[k + 1]; 449 currentX += val[k + 2]; 450 currentY += val[k + 3]; 451 break; 452 case 'Q': // Draws a quadratic Bézier 453 path.quadTo(val[k + 0], val[k + 1], val[k + 2], val[k + 3]); 454 ctrlPointX = val[k + 0]; 455 ctrlPointY = val[k + 1]; 456 currentX = val[k + 2]; 457 currentY = val[k + 3]; 458 break; 459 case 't': // Draws a quadratic Bézier curve(reflective control point)(relative) 460 reflectiveCtrlPointX = 0; 461 reflectiveCtrlPointY = 0; 462 if (previousCmd == 'q' || previousCmd == 't' 463 || previousCmd == 'Q' || previousCmd == 'T') { 464 reflectiveCtrlPointX = currentX - ctrlPointX; 465 reflectiveCtrlPointY = currentY - ctrlPointY; 466 } 467 path.rQuadTo(reflectiveCtrlPointX, reflectiveCtrlPointY, 468 val[k + 0], val[k + 1]); 469 ctrlPointX = currentX + reflectiveCtrlPointX; 470 ctrlPointY = currentY + reflectiveCtrlPointY; 471 currentX += val[k + 0]; 472 currentY += val[k + 1]; 473 break; 474 case 'T': // Draws a quadratic Bézier curve (reflective control point) 475 reflectiveCtrlPointX = currentX; 476 reflectiveCtrlPointY = currentY; 477 if (previousCmd == 'q' || previousCmd == 't' 478 || previousCmd == 'Q' || previousCmd == 'T') { 479 reflectiveCtrlPointX = 2 * currentX - ctrlPointX; 480 reflectiveCtrlPointY = 2 * currentY - ctrlPointY; 481 } 482 path.quadTo(reflectiveCtrlPointX, reflectiveCtrlPointY, 483 val[k + 0], val[k + 1]); 484 ctrlPointX = reflectiveCtrlPointX; 485 ctrlPointY = reflectiveCtrlPointY; 486 currentX = val[k + 0]; 487 currentY = val[k + 1]; 488 break; 489 case 'a': // Draws an elliptical arc 490 // (rx ry x-axis-rotation large-arc-flag sweep-flag x y) 491 drawArc(path, 492 currentX, 493 currentY, 494 val[k + 5] + currentX, 495 val[k + 6] + currentY, 496 val[k + 0], 497 val[k + 1], 498 val[k + 2], 499 val[k + 3] != 0, 500 val[k + 4] != 0); 501 currentX += val[k + 5]; 502 currentY += val[k + 6]; 503 ctrlPointX = currentX; 504 ctrlPointY = currentY; 505 break; 506 case 'A': // Draws an elliptical arc 507 drawArc(path, 508 currentX, 509 currentY, 510 val[k + 5], 511 val[k + 6], 512 val[k + 0], 513 val[k + 1], 514 val[k + 2], 515 val[k + 3] != 0, 516 val[k + 4] != 0); 517 currentX = val[k + 5]; 518 currentY = val[k + 6]; 519 ctrlPointX = currentX; 520 ctrlPointY = currentY; 521 break; 522 } 523 previousCmd = cmd; 524 } 525 current[0] = currentX; 526 current[1] = currentY; 527 current[2] = ctrlPointX; 528 current[3] = ctrlPointY; 529 } 530 531 private static void drawArc(Path p, 532 float x0, 533 float y0, 534 float x1, 535 float y1, 536 float a, 537 float b, 538 float theta, 539 boolean isMoreThanHalf, 540 boolean isPositiveArc) { 541 542 /* Convert rotation angle from degrees to radians */ 543 double thetaD = Math.toRadians(theta); 544 /* Pre-compute rotation matrix entries */ 545 double cosTheta = Math.cos(thetaD); 546 double sinTheta = Math.sin(thetaD); 547 /* Transform (x0, y0) and (x1, y1) into unit space */ 548 /* using (inverse) rotation, followed by (inverse) scale */ 549 double x0p = (x0 * cosTheta + y0 * sinTheta) / a; 550 double y0p = (-x0 * sinTheta + y0 * cosTheta) / b; 551 double x1p = (x1 * cosTheta + y1 * sinTheta) / a; 552 double y1p = (-x1 * sinTheta + y1 * cosTheta) / b; 553 554 /* Compute differences and averages */ 555 double dx = x0p - x1p; 556 double dy = y0p - y1p; 557 double xm = (x0p + x1p) / 2; 558 double ym = (y0p + y1p) / 2; 559 /* Solve for intersecting unit circles */ 560 double dsq = dx * dx + dy * dy; 561 if (dsq == 0.0) { 562 Log.w(LOGTAG, " Points are coincident"); 563 return; /* Points are coincident */ 564 } 565 double disc = 1.0 / dsq - 1.0 / 4.0; 566 if (disc < 0.0) { 567 Log.w(LOGTAG, "Points are too far apart " + dsq); 568 float adjust = (float) (Math.sqrt(dsq) / 1.99999); 569 drawArc(p, x0, y0, x1, y1, a * adjust, 570 b * adjust, theta, isMoreThanHalf, isPositiveArc); 571 return; /* Points are too far apart */ 572 } 573 double s = Math.sqrt(disc); 574 double sdx = s * dx; 575 double sdy = s * dy; 576 double cx; 577 double cy; 578 if (isMoreThanHalf == isPositiveArc) { 579 cx = xm - sdy; 580 cy = ym + sdx; 581 } else { 582 cx = xm + sdy; 583 cy = ym - sdx; 584 } 585 586 double eta0 = Math.atan2((y0p - cy), (x0p - cx)); 587 588 double eta1 = Math.atan2((y1p - cy), (x1p - cx)); 589 590 double sweep = (eta1 - eta0); 591 if (isPositiveArc != (sweep >= 0)) { 592 if (sweep > 0) { 593 sweep -= 2 * Math.PI; 594 } else { 595 sweep += 2 * Math.PI; 596 } 597 } 598 599 cx *= a; 600 cy *= b; 601 double tcx = cx; 602 cx = cx * cosTheta - cy * sinTheta; 603 cy = tcx * sinTheta + cy * cosTheta; 604 605 arcToBezier(p, cx, cy, a, b, x0, y0, thetaD, eta0, sweep); 606 } 607 608 /** 609 * Converts an arc to cubic Bezier segments and records them in p. 610 * 611 * @param p The target for the cubic Bezier segments 612 * @param cx The x coordinate center of the ellipse 613 * @param cy The y coordinate center of the ellipse 614 * @param a The radius of the ellipse in the horizontal direction 615 * @param b The radius of the ellipse in the vertical direction 616 * @param e1x E(eta1) x coordinate of the starting point of the arc 617 * @param e1y E(eta2) y coordinate of the starting point of the arc 618 * @param theta The angle that the ellipse bounding rectangle makes with horizontal plane 619 * @param start The start angle of the arc on the ellipse 620 * @param sweep The angle (positive or negative) of the sweep of the arc on the ellipse 621 */ 622 private static void arcToBezier(Path p, 623 double cx, 624 double cy, 625 double a, 626 double b, 627 double e1x, 628 double e1y, 629 double theta, 630 double start, 631 double sweep) { 632 // Taken from equations at: http://spaceroots.org/documents/ellipse/node8.html 633 // and http://www.spaceroots.org/documents/ellipse/node22.html 634 635 // Maximum of 45 degrees per cubic Bezier segment 636 int numSegments = Math.abs((int) Math.ceil(sweep * 4 / Math.PI)); 637 638 double eta1 = start; 639 double cosTheta = Math.cos(theta); 640 double sinTheta = Math.sin(theta); 641 double cosEta1 = Math.cos(eta1); 642 double sinEta1 = Math.sin(eta1); 643 double ep1x = (-a * cosTheta * sinEta1) - (b * sinTheta * cosEta1); 644 double ep1y = (-a * sinTheta * sinEta1) + (b * cosTheta * cosEta1); 645 646 double anglePerSegment = sweep / numSegments; 647 for (int i = 0; i < numSegments; i++) { 648 double eta2 = eta1 + anglePerSegment; 649 double sinEta2 = Math.sin(eta2); 650 double cosEta2 = Math.cos(eta2); 651 double e2x = cx + (a * cosTheta * cosEta2) - (b * sinTheta * sinEta2); 652 double e2y = cy + (a * sinTheta * cosEta2) + (b * cosTheta * sinEta2); 653 double ep2x = -a * cosTheta * sinEta2 - b * sinTheta * cosEta2; 654 double ep2y = -a * sinTheta * sinEta2 + b * cosTheta * cosEta2; 655 double tanDiff2 = Math.tan((eta2 - eta1) / 2); 656 double alpha = 657 Math.sin(eta2 - eta1) * (Math.sqrt(4 + (3 * tanDiff2 * tanDiff2)) - 1) / 3; 658 double q1x = e1x + alpha * ep1x; 659 double q1y = e1y + alpha * ep1y; 660 double q2x = e2x - alpha * ep2x; 661 double q2y = e2y - alpha * ep2y; 662 663 p.cubicTo((float) q1x, 664 (float) q1y, 665 (float) q2x, 666 (float) q2y, 667 (float) e2x, 668 (float) e2y); 669 eta1 = eta2; 670 e1x = e2x; 671 e1y = e2y; 672 ep1x = ep2x; 673 ep1y = ep2y; 674 } 675 } 676 } 677} 678