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