1 /* 2 * Copyright (C) 2015 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.android.layoutlib.bridge.util; 18 19 import android.annotation.NonNull; 20 21 import java.awt.geom.CubicCurve2D; 22 import java.awt.geom.PathIterator; 23 import java.awt.geom.Point2D; 24 import java.awt.geom.QuadCurve2D; 25 import java.util.ArrayList; 26 27 import com.google.android.collect.Lists; 28 29 /** 30 * Class that returns iterators for a given path. These iterators are lightweight and can be reused 31 * multiple times to iterate over the path. 32 */ 33 public class CachedPathIteratorFactory { 34 /* 35 * A few conventions used in the code: 36 * Coordinates or coords arrays store segment coordinates. They use the same format as 37 * PathIterator#currentSegment coordinates array. 38 * float arrays store always points where the first element is X and the second is Y. 39 */ 40 41 // This governs how accurate the approximation of the Path is. 42 private static final float PRECISION = 0.002f; 43 44 private final int mWindingRule; 45 private final int[] mTypes; 46 private final float[][] mCoordinates; 47 private final float[] mSegmentsLength; 48 private final float mTotalLength; 49 CachedPathIteratorFactory(@onNull PathIterator iterator)50 public CachedPathIteratorFactory(@NonNull PathIterator iterator) { 51 mWindingRule = iterator.getWindingRule(); 52 53 ArrayList<Integer> typesArray = Lists.newArrayList(); 54 ArrayList<float[]> pointsArray = Lists.newArrayList(); 55 float[] points = new float[6]; 56 while (!iterator.isDone()) { 57 int type = iterator.currentSegment(points); 58 int nPoints = getNumberOfPoints(type) * 2; // 2 coordinates per point 59 60 typesArray.add(type); 61 float[] itemPoints = new float[nPoints]; 62 System.arraycopy(points, 0, itemPoints, 0, nPoints); 63 pointsArray.add(itemPoints); 64 iterator.next(); 65 } 66 67 mTypes = new int[typesArray.size()]; 68 mCoordinates = new float[mTypes.length][]; 69 for (int i = 0; i < typesArray.size(); i++) { 70 mTypes[i] = typesArray.get(i); 71 mCoordinates[i] = pointsArray.get(i); 72 } 73 74 // Do measurement 75 mSegmentsLength = new float[mTypes.length]; 76 77 // Curves that we can reuse to estimate segments length 78 CubicCurve2D.Float cubicCurve = new CubicCurve2D.Float(); 79 QuadCurve2D.Float quadCurve = new QuadCurve2D.Float(); 80 float lastX = 0; 81 float lastY = 0; 82 float totalLength = 0; 83 for (int i = 0; i < mTypes.length; i++) { 84 switch (mTypes[i]) { 85 case PathIterator.SEG_CUBICTO: 86 cubicCurve.setCurve(lastX, lastY, 87 mCoordinates[i][0], mCoordinates[i][1], mCoordinates[i][2], 88 mCoordinates[i][3], lastX = mCoordinates[i][4], 89 lastY = mCoordinates[i][5]); 90 mSegmentsLength[i] = 91 getFlatPathLength(cubicCurve.getPathIterator(null, PRECISION)); 92 break; 93 case PathIterator.SEG_QUADTO: 94 quadCurve.setCurve(lastX, lastY, mCoordinates[i][0], mCoordinates[i][1], 95 lastX = mCoordinates[i][2], lastY = mCoordinates[i][3]); 96 mSegmentsLength[i] = 97 getFlatPathLength(quadCurve.getPathIterator(null, PRECISION)); 98 break; 99 case PathIterator.SEG_CLOSE: 100 mSegmentsLength[i] = (float) Point2D.distance(lastX, lastY, 101 lastX = mCoordinates[0][0], 102 lastY = mCoordinates[0][1]); 103 mCoordinates[i] = new float[2]; 104 // We convert a SEG_CLOSE segment to a SEG_LINETO so we do not have to worry 105 // about this special case in the rest of the code. 106 mTypes[i] = PathIterator.SEG_LINETO; 107 mCoordinates[i][0] = mCoordinates[0][0]; 108 mCoordinates[i][1] = mCoordinates[0][1]; 109 break; 110 case PathIterator.SEG_MOVETO: 111 mSegmentsLength[i] = 0; 112 lastX = mCoordinates[i][0]; 113 lastY = mCoordinates[i][1]; 114 break; 115 case PathIterator.SEG_LINETO: 116 mSegmentsLength[i] = (float) Point2D.distance(lastX, lastY, mCoordinates[i][0], 117 mCoordinates[i][1]); 118 lastX = mCoordinates[i][0]; 119 lastY = mCoordinates[i][1]; 120 default: 121 } 122 totalLength += mSegmentsLength[i]; 123 } 124 125 mTotalLength = totalLength; 126 } 127 quadCurveSegment(float[] coords, float t0, float t1)128 private static void quadCurveSegment(float[] coords, float t0, float t1) { 129 // Calculate X and Y at 0.5 (We'll use this to reconstruct the control point later) 130 float mt = t0 + (t1 - t0) / 2; 131 float mu = 1 - mt; 132 float mx = mu * mu * coords[0] + 2 * mu * mt * coords[2] + mt * mt * coords[4]; 133 float my = mu * mu * coords[1] + 2 * mu * mt * coords[3] + mt * mt * coords[5]; 134 135 float u0 = 1 - t0; 136 float u1 = 1 - t1; 137 138 // coords at t0 139 coords[0] = coords[0] * u0 * u0 + coords[2] * 2 * t0 * u0 + coords[4] * t0 * t0; 140 coords[1] = coords[1] * u0 * u0 + coords[3] * 2 * t0 * u0 + coords[5] * t0 * t0; 141 142 // coords at t1 143 coords[4] = coords[0] * u1 * u1 + coords[2] * 2 * t1 * u1 + coords[4] * t1 * t1; 144 coords[5] = coords[1] * u1 * u1 + coords[3] * 2 * t1 * u1 + coords[5] * t1 * t1; 145 146 // estimated control point at t'=0.5 147 coords[2] = 2 * mx - coords[0] / 2 - coords[4] / 2; 148 coords[3] = 2 * my - coords[1] / 2 - coords[5] / 2; 149 } 150 cubicCurveSegment(float[] coords, float t0, float t1)151 private static void cubicCurveSegment(float[] coords, float t0, float t1) { 152 // http://stackoverflow.com/questions/11703283/cubic-bezier-curve-segment 153 float u0 = 1 - t0; 154 float u1 = 1 - t1; 155 156 // Calculate the points at t0 and t1 for the quadratic curves formed by (P0, P1, P2) and 157 // (P1, P2, P3) 158 float qxa = coords[0] * u0 * u0 + coords[2] * 2 * t0 * u0 + coords[4] * t0 * t0; 159 float qxb = coords[0] * u1 * u1 + coords[2] * 2 * t1 * u1 + coords[4] * t1 * t1; 160 float qxc = coords[2] * u0 * u0 + coords[4] * 2 * t0 * u0 + coords[6] * t0 * t0; 161 float qxd = coords[2] * u1 * u1 + coords[4] * 2 * t1 * u1 + coords[6] * t1 * t1; 162 163 float qya = coords[1] * u0 * u0 + coords[3] * 2 * t0 * u0 + coords[5] * t0 * t0; 164 float qyb = coords[1] * u1 * u1 + coords[3] * 2 * t1 * u1 + coords[5] * t1 * t1; 165 float qyc = coords[3] * u0 * u0 + coords[5] * 2 * t0 * u0 + coords[7] * t0 * t0; 166 float qyd = coords[3] * u1 * u1 + coords[5] * 2 * t1 * u1 + coords[7] * t1 * t1; 167 168 // Linear interpolation 169 coords[0] = qxa * u0 + qxc * t0; 170 coords[1] = qya * u0 + qyc * t0; 171 172 coords[2] = qxa * u1 + qxc * t1; 173 coords[3] = qya * u1 + qyc * t1; 174 175 coords[4] = qxb * u0 + qxd * t0; 176 coords[5] = qyb * u0 + qyd * t0; 177 178 coords[6] = qxb * u1 + qxd * t1; 179 coords[7] = qyb * u1 + qyd * t1; 180 } 181 182 /** 183 * Returns the end point of a given segment 184 * 185 * @param type the segment type 186 * @param coords the segment coordinates array 187 * @param point the return array where the point will be stored 188 */ getShapeEndPoint(int type, @NonNull float[] coords, @NonNull float[] point)189 private static void getShapeEndPoint(int type, @NonNull float[] coords, @NonNull float[] 190 point) { 191 // start index of the end point for the segment type 192 int pointIndex = (getNumberOfPoints(type) - 1) * 2; 193 point[0] = coords[pointIndex]; 194 point[1] = coords[pointIndex + 1]; 195 } 196 197 /** 198 * Returns the number of points stored in a coordinates array for the given segment type. 199 */ getNumberOfPoints(int segmentType)200 private static int getNumberOfPoints(int segmentType) { 201 switch (segmentType) { 202 case PathIterator.SEG_QUADTO: 203 return 2; 204 case PathIterator.SEG_CUBICTO: 205 return 3; 206 case PathIterator.SEG_CLOSE: 207 return 0; 208 default: 209 return 1; 210 } 211 } 212 213 /** 214 * Returns the estimated length of a flat path. If the passed path is not flat (i.e. contains a 215 * segment that is not {@link PathIterator#SEG_CLOSE}, {@link PathIterator#SEG_MOVETO} or {@link 216 * PathIterator#SEG_LINETO} this method will fail. 217 */ getFlatPathLength(@onNull PathIterator iterator)218 private static float getFlatPathLength(@NonNull PathIterator iterator) { 219 float segment[] = new float[6]; 220 float totalLength = 0; 221 float[] previousPoint = new float[2]; 222 boolean isFirstPoint = true; 223 224 while (!iterator.isDone()) { 225 int type = iterator.currentSegment(segment); 226 assert type == PathIterator.SEG_LINETO || type == PathIterator.SEG_CLOSE || type == 227 PathIterator.SEG_MOVETO; 228 229 // MoveTo shouldn't affect the length 230 if (!isFirstPoint && type != PathIterator.SEG_MOVETO) { 231 totalLength += Point2D.distance(previousPoint[0], previousPoint[1], segment[0], 232 segment[1]); 233 } else { 234 isFirstPoint = false; 235 } 236 previousPoint[0] = segment[0]; 237 previousPoint[1] = segment[1]; 238 iterator.next(); 239 } 240 241 return totalLength; 242 } 243 244 /** 245 * Returns the estimated position along a path of the given length. 246 */ getPointAtLength(int type, @NonNull float[] coords, float lastX, float lastY, float t, @NonNull float[] point)247 private void getPointAtLength(int type, @NonNull float[] coords, float lastX, float 248 lastY, float t, @NonNull float[] point) { 249 if (type == PathIterator.SEG_LINETO) { 250 point[0] = lastX + (coords[0] - lastX) * t; 251 point[1] = lastY + (coords[1] - lastY) * t; 252 // Return here, since we do not need a shape to estimate 253 return; 254 } 255 256 float[] curve = new float[8]; 257 int lastPointIndex = (getNumberOfPoints(type) - 1) * 2; 258 259 System.arraycopy(coords, 0, curve, 2, coords.length); 260 curve[0] = lastX; 261 curve[1] = lastY; 262 if (type == PathIterator.SEG_CUBICTO) { 263 cubicCurveSegment(curve, 0f, t); 264 } else { 265 quadCurveSegment(curve, 0f, t); 266 } 267 268 point[0] = curve[2 + lastPointIndex]; 269 point[1] = curve[2 + lastPointIndex + 1]; 270 } 271 iterator()272 public CachedPathIterator iterator() { 273 return new CachedPathIterator(); 274 } 275 276 /** 277 * Class that allows us to iterate over a path multiple times 278 */ 279 public class CachedPathIterator implements PathIterator { 280 private int mNextIndex; 281 282 /** 283 * Current segment type. 284 * 285 * @see PathIterator 286 */ 287 private int mCurrentType; 288 289 /** 290 * Stores the coordinates array of the current segment. The number of points stored depends 291 * on the segment type. 292 * 293 * @see PathIterator 294 */ 295 private float[] mCurrentCoords = new float[6]; 296 private float mCurrentSegmentLength; 297 298 /** 299 * Current segment length offset. When asking for the length of the current segment, the 300 * length will be reduced by this amount. This is useful when we are only using portions of 301 * the segment. 302 * 303 * @see #jumpToSegment(float) 304 */ 305 private float mOffsetLength; 306 307 /** Point where the current segment started */ 308 private float[] mLastPoint = new float[2]; 309 private boolean isIteratorDone; 310 CachedPathIterator()311 private CachedPathIterator() { 312 next(); 313 } 314 getCurrentSegmentLength()315 public float getCurrentSegmentLength() { 316 return mCurrentSegmentLength; 317 } 318 319 @Override getWindingRule()320 public int getWindingRule() { 321 return mWindingRule; 322 } 323 324 @Override isDone()325 public boolean isDone() { 326 return isIteratorDone; 327 } 328 329 @Override next()330 public void next() { 331 if (mNextIndex >= mTypes.length) { 332 isIteratorDone = true; 333 return; 334 } 335 336 if (mNextIndex >= 1) { 337 // We've already called next() once so there is a previous segment in this path. 338 // We want to get the coordinates where the path ends. 339 getShapeEndPoint(mCurrentType, mCurrentCoords, mLastPoint); 340 } else { 341 // This is the first segment, no previous point so initialize to 0, 0 342 mLastPoint[0] = mLastPoint[1] = 0f; 343 } 344 mCurrentType = mTypes[mNextIndex]; 345 mCurrentSegmentLength = mSegmentsLength[mNextIndex] - mOffsetLength; 346 347 if (mOffsetLength > 0f && (mCurrentType == SEG_CUBICTO || mCurrentType == SEG_QUADTO)) { 348 // We need to skip part of the start of the current segment (because 349 // mOffsetLength > 0) 350 float[] points = new float[8]; 351 352 if (mNextIndex < 1) { 353 points[0] = points[1] = 0f; 354 } else { 355 getShapeEndPoint(mTypes[mNextIndex - 1], mCoordinates[mNextIndex - 1], points); 356 } 357 358 System.arraycopy(mCoordinates[mNextIndex], 0, points, 2, 359 mCoordinates[mNextIndex].length); 360 float t0 = (mSegmentsLength[mNextIndex] - mCurrentSegmentLength) / 361 mSegmentsLength[mNextIndex]; 362 if (mCurrentType == SEG_CUBICTO) { 363 cubicCurveSegment(points, t0, 1f); 364 } else { 365 quadCurveSegment(points, t0, 1f); 366 } 367 System.arraycopy(points, 2, mCurrentCoords, 0, mCoordinates[mNextIndex].length); 368 } else { 369 System.arraycopy(mCoordinates[mNextIndex], 0, mCurrentCoords, 0, 370 mCoordinates[mNextIndex].length); 371 } 372 373 mOffsetLength = 0f; 374 mNextIndex++; 375 } 376 377 @Override currentSegment(float[] coords)378 public int currentSegment(float[] coords) { 379 System.arraycopy(mCurrentCoords, 0, coords, 0, getNumberOfPoints(mCurrentType) * 2); 380 return mCurrentType; 381 } 382 383 @Override currentSegment(double[] coords)384 public int currentSegment(double[] coords) { 385 throw new UnsupportedOperationException(); 386 } 387 388 /** 389 * Returns the point where the current segment ends 390 */ getCurrentSegmentEnd(float[] point)391 public void getCurrentSegmentEnd(float[] point) { 392 point[0] = mLastPoint[0]; 393 point[1] = mLastPoint[1]; 394 } 395 396 /** 397 * Restarts the iterator and jumps all the segments of this path up to the length value. 398 */ jumpToSegment(float length)399 public void jumpToSegment(float length) { 400 isIteratorDone = false; 401 if (length <= 0f) { 402 mNextIndex = 0; 403 return; 404 } 405 406 float accLength = 0; 407 float lastPoint[] = new float[2]; 408 for (mNextIndex = 0; mNextIndex < mTypes.length; mNextIndex++) { 409 float segmentLength = mSegmentsLength[mNextIndex]; 410 if (accLength + segmentLength >= length && mTypes[mNextIndex] != SEG_MOVETO) { 411 float[] estimatedPoint = new float[2]; 412 getPointAtLength(mTypes[mNextIndex], 413 mCoordinates[mNextIndex], lastPoint[0], lastPoint[1], 414 (length - accLength) / segmentLength, 415 estimatedPoint); 416 417 // This segment makes us go further than length so we go back one step, 418 // set a moveto and offset the length of the next segment by the length 419 // of this segment that we've already used. 420 mCurrentType = PathIterator.SEG_MOVETO; 421 mCurrentCoords[0] = estimatedPoint[0]; 422 mCurrentCoords[1] = estimatedPoint[1]; 423 mCurrentSegmentLength = 0; 424 425 // We need to offset next path length to account for the segment we've just 426 // skipped. 427 mOffsetLength = length - accLength; 428 return; 429 } 430 accLength += segmentLength; 431 getShapeEndPoint(mTypes[mNextIndex], mCoordinates[mNextIndex], lastPoint); 432 } 433 } 434 435 /** 436 * Returns the current segment up to certain length. If the current segment is shorter than 437 * length, then the whole segment is returned. The segment coordinates are copied into the 438 * coords array. 439 * 440 * @return the segment type 441 */ currentSegment(@onNull float[] coords, float length)442 public int currentSegment(@NonNull float[] coords, float length) { 443 int type = currentSegment(coords); 444 // If the length is greater than the current segment length, no need to find 445 // the cut point. Same if this is a SEG_MOVETO. 446 if (mCurrentSegmentLength <= length || type == SEG_MOVETO) { 447 return type; 448 } 449 450 float t = length / getCurrentSegmentLength(); 451 452 // We find at which offset the end point is located within the coords array and set 453 // a new end point to cut the segment short 454 switch (type) { 455 case SEG_CUBICTO: 456 case SEG_QUADTO: 457 float[] curve = new float[8]; 458 curve[0] = mLastPoint[0]; 459 curve[1] = mLastPoint[1]; 460 System.arraycopy(coords, 0, curve, 2, coords.length); 461 if (type == SEG_CUBICTO) { 462 cubicCurveSegment(curve, 0f, t); 463 } else { 464 quadCurveSegment(curve, 0f, t); 465 } 466 System.arraycopy(curve, 2, coords, 0, coords.length); 467 break; 468 default: 469 float[] point = new float[2]; 470 getPointAtLength(type, coords, mLastPoint[0], mLastPoint[1], t, point); 471 coords[0] = point[0]; 472 coords[1] = point[1]; 473 } 474 475 return type; 476 } 477 478 /** 479 * Returns the total length of the path 480 */ getTotalLength()481 public float getTotalLength() { 482 return mTotalLength; 483 } 484 } 485 } 486