| /* |
| * Copyright (C) 2015 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package com.android.layoutlib.bridge.util; |
| |
| import android.annotation.NonNull; |
| |
| import java.awt.geom.CubicCurve2D; |
| import java.awt.geom.PathIterator; |
| import java.awt.geom.Point2D; |
| import java.awt.geom.QuadCurve2D; |
| import java.util.ArrayList; |
| |
| import com.google.android.collect.Lists; |
| |
| /** |
| * Class that returns iterators for a given path. These iterators are lightweight and can be reused |
| * multiple times to iterate over the path. |
| */ |
| public class CachedPathIteratorFactory { |
| /* |
| * A few conventions used in the code: |
| * Coordinates or coords arrays store segment coordinates. They use the same format as |
| * PathIterator#currentSegment coordinates array. |
| * float arrays store always points where the first element is X and the second is Y. |
| */ |
| |
| // This governs how accurate the approximation of the Path is. |
| private static final float PRECISION = 0.002f; |
| |
| private final int mWindingRule; |
| private final int[] mTypes; |
| private final float[][] mCoordinates; |
| private final float[] mSegmentsLength; |
| private final float mTotalLength; |
| |
| public CachedPathIteratorFactory(@NonNull PathIterator iterator) { |
| mWindingRule = iterator.getWindingRule(); |
| |
| ArrayList<Integer> typesArray = Lists.newArrayList(); |
| ArrayList<float[]> pointsArray = Lists.newArrayList(); |
| float[] points = new float[6]; |
| while (!iterator.isDone()) { |
| int type = iterator.currentSegment(points); |
| int nPoints = getNumberOfPoints(type) * 2; // 2 coordinates per point |
| |
| typesArray.add(type); |
| float[] itemPoints = new float[nPoints]; |
| System.arraycopy(points, 0, itemPoints, 0, nPoints); |
| pointsArray.add(itemPoints); |
| iterator.next(); |
| } |
| |
| mTypes = new int[typesArray.size()]; |
| mCoordinates = new float[mTypes.length][]; |
| for (int i = 0; i < typesArray.size(); i++) { |
| mTypes[i] = typesArray.get(i); |
| mCoordinates[i] = pointsArray.get(i); |
| } |
| |
| // Do measurement |
| mSegmentsLength = new float[mTypes.length]; |
| |
| // Curves that we can reuse to estimate segments length |
| CubicCurve2D.Float cubicCurve = new CubicCurve2D.Float(); |
| QuadCurve2D.Float quadCurve = new QuadCurve2D.Float(); |
| float lastX = 0; |
| float lastY = 0; |
| float totalLength = 0; |
| for (int i = 0; i < mTypes.length; i++) { |
| switch (mTypes[i]) { |
| case PathIterator.SEG_CUBICTO: |
| cubicCurve.setCurve(lastX, lastY, |
| mCoordinates[i][0], mCoordinates[i][1], mCoordinates[i][2], |
| mCoordinates[i][3], lastX = mCoordinates[i][4], |
| lastY = mCoordinates[i][5]); |
| mSegmentsLength[i] = |
| getFlatPathLength(cubicCurve.getPathIterator(null, PRECISION)); |
| break; |
| case PathIterator.SEG_QUADTO: |
| quadCurve.setCurve(lastX, lastY, mCoordinates[i][0], mCoordinates[i][1], |
| lastX = mCoordinates[i][2], lastY = mCoordinates[i][3]); |
| mSegmentsLength[i] = |
| getFlatPathLength(quadCurve.getPathIterator(null, PRECISION)); |
| break; |
| case PathIterator.SEG_CLOSE: |
| mSegmentsLength[i] = (float) Point2D.distance(lastX, lastY, |
| lastX = mCoordinates[0][0], |
| lastY = mCoordinates[0][1]); |
| mCoordinates[i] = new float[2]; |
| // We convert a SEG_CLOSE segment to a SEG_LINETO so we do not have to worry |
| // about this special case in the rest of the code. |
| mTypes[i] = PathIterator.SEG_LINETO; |
| mCoordinates[i][0] = mCoordinates[0][0]; |
| mCoordinates[i][1] = mCoordinates[0][1]; |
| break; |
| case PathIterator.SEG_MOVETO: |
| mSegmentsLength[i] = 0; |
| lastX = mCoordinates[i][0]; |
| lastY = mCoordinates[i][1]; |
| break; |
| case PathIterator.SEG_LINETO: |
| mSegmentsLength[i] = (float) Point2D.distance(lastX, lastY, mCoordinates[i][0], |
| mCoordinates[i][1]); |
| lastX = mCoordinates[i][0]; |
| lastY = mCoordinates[i][1]; |
| default: |
| } |
| totalLength += mSegmentsLength[i]; |
| } |
| |
| mTotalLength = totalLength; |
| } |
| |
| private static void quadCurveSegment(float[] coords, float t0, float t1) { |
| // Calculate X and Y at 0.5 (We'll use this to reconstruct the control point later) |
| float mt = t0 + (t1 - t0) / 2; |
| float mu = 1 - mt; |
| float mx = mu * mu * coords[0] + 2 * mu * mt * coords[2] + mt * mt * coords[4]; |
| float my = mu * mu * coords[1] + 2 * mu * mt * coords[3] + mt * mt * coords[5]; |
| |
| float u0 = 1 - t0; |
| float u1 = 1 - t1; |
| |
| // coords at t0 |
| coords[0] = coords[0] * u0 * u0 + coords[2] * 2 * t0 * u0 + coords[4] * t0 * t0; |
| coords[1] = coords[1] * u0 * u0 + coords[3] * 2 * t0 * u0 + coords[5] * t0 * t0; |
| |
| // coords at t1 |
| coords[4] = coords[0] * u1 * u1 + coords[2] * 2 * t1 * u1 + coords[4] * t1 * t1; |
| coords[5] = coords[1] * u1 * u1 + coords[3] * 2 * t1 * u1 + coords[5] * t1 * t1; |
| |
| // estimated control point at t'=0.5 |
| coords[2] = 2 * mx - coords[0] / 2 - coords[4] / 2; |
| coords[3] = 2 * my - coords[1] / 2 - coords[5] / 2; |
| } |
| |
| private static void cubicCurveSegment(float[] coords, float t0, float t1) { |
| // http://stackoverflow.com/questions/11703283/cubic-bezier-curve-segment |
| float u0 = 1 - t0; |
| float u1 = 1 - t1; |
| |
| // Calculate the points at t0 and t1 for the quadratic curves formed by (P0, P1, P2) and |
| // (P1, P2, P3) |
| float qxa = coords[0] * u0 * u0 + coords[2] * 2 * t0 * u0 + coords[4] * t0 * t0; |
| float qxb = coords[0] * u1 * u1 + coords[2] * 2 * t1 * u1 + coords[4] * t1 * t1; |
| float qxc = coords[2] * u0 * u0 + coords[4] * 2 * t0 * u0 + coords[6] * t0 * t0; |
| float qxd = coords[2] * u1 * u1 + coords[4] * 2 * t1 * u1 + coords[6] * t1 * t1; |
| |
| float qya = coords[1] * u0 * u0 + coords[3] * 2 * t0 * u0 + coords[5] * t0 * t0; |
| float qyb = coords[1] * u1 * u1 + coords[3] * 2 * t1 * u1 + coords[5] * t1 * t1; |
| float qyc = coords[3] * u0 * u0 + coords[5] * 2 * t0 * u0 + coords[7] * t0 * t0; |
| float qyd = coords[3] * u1 * u1 + coords[5] * 2 * t1 * u1 + coords[7] * t1 * t1; |
| |
| // Linear interpolation |
| coords[0] = qxa * u0 + qxc * t0; |
| coords[1] = qya * u0 + qyc * t0; |
| |
| coords[2] = qxa * u1 + qxc * t1; |
| coords[3] = qya * u1 + qyc * t1; |
| |
| coords[4] = qxb * u0 + qxd * t0; |
| coords[5] = qyb * u0 + qyd * t0; |
| |
| coords[6] = qxb * u1 + qxd * t1; |
| coords[7] = qyb * u1 + qyd * t1; |
| } |
| |
| /** |
| * Returns the end point of a given segment |
| * |
| * @param type the segment type |
| * @param coords the segment coordinates array |
| * @param point the return array where the point will be stored |
| */ |
| private static void getShapeEndPoint(int type, @NonNull float[] coords, @NonNull float[] |
| point) { |
| // start index of the end point for the segment type |
| int pointIndex = (getNumberOfPoints(type) - 1) * 2; |
| point[0] = coords[pointIndex]; |
| point[1] = coords[pointIndex + 1]; |
| } |
| |
| /** |
| * Returns the number of points stored in a coordinates array for the given segment type. |
| */ |
| private static int getNumberOfPoints(int segmentType) { |
| switch (segmentType) { |
| case PathIterator.SEG_QUADTO: |
| return 2; |
| case PathIterator.SEG_CUBICTO: |
| return 3; |
| case PathIterator.SEG_CLOSE: |
| return 0; |
| default: |
| return 1; |
| } |
| } |
| |
| /** |
| * Returns the estimated length of a flat path. If the passed path is not flat (i.e. contains a |
| * segment that is not {@link PathIterator#SEG_CLOSE}, {@link PathIterator#SEG_MOVETO} or {@link |
| * PathIterator#SEG_LINETO} this method will fail. |
| */ |
| private static float getFlatPathLength(@NonNull PathIterator iterator) { |
| float segment[] = new float[6]; |
| float totalLength = 0; |
| float[] previousPoint = new float[2]; |
| boolean isFirstPoint = true; |
| |
| while (!iterator.isDone()) { |
| int type = iterator.currentSegment(segment); |
| assert type == PathIterator.SEG_LINETO || type == PathIterator.SEG_CLOSE || type == |
| PathIterator.SEG_MOVETO; |
| |
| // MoveTo shouldn't affect the length |
| if (!isFirstPoint && type != PathIterator.SEG_MOVETO) { |
| totalLength += Point2D.distance(previousPoint[0], previousPoint[1], segment[0], |
| segment[1]); |
| } else { |
| isFirstPoint = false; |
| } |
| previousPoint[0] = segment[0]; |
| previousPoint[1] = segment[1]; |
| iterator.next(); |
| } |
| |
| return totalLength; |
| } |
| |
| /** |
| * Returns the estimated position along a path of the given length. |
| */ |
| private void getPointAtLength(int type, @NonNull float[] coords, float lastX, float |
| lastY, float t, @NonNull float[] point) { |
| if (type == PathIterator.SEG_LINETO) { |
| point[0] = lastX + (coords[0] - lastX) * t; |
| point[1] = lastY + (coords[1] - lastY) * t; |
| // Return here, since we do not need a shape to estimate |
| return; |
| } |
| |
| float[] curve = new float[8]; |
| int lastPointIndex = (getNumberOfPoints(type) - 1) * 2; |
| |
| System.arraycopy(coords, 0, curve, 2, coords.length); |
| curve[0] = lastX; |
| curve[1] = lastY; |
| if (type == PathIterator.SEG_CUBICTO) { |
| cubicCurveSegment(curve, 0f, t); |
| } else { |
| quadCurveSegment(curve, 0f, t); |
| } |
| |
| point[0] = curve[2 + lastPointIndex]; |
| point[1] = curve[2 + lastPointIndex + 1]; |
| } |
| |
| public CachedPathIterator iterator() { |
| return new CachedPathIterator(); |
| } |
| |
| /** |
| * Class that allows us to iterate over a path multiple times |
| */ |
| public class CachedPathIterator implements PathIterator { |
| private int mNextIndex; |
| |
| /** |
| * Current segment type. |
| * |
| * @see PathIterator |
| */ |
| private int mCurrentType; |
| |
| /** |
| * Stores the coordinates array of the current segment. The number of points stored depends |
| * on the segment type. |
| * |
| * @see PathIterator |
| */ |
| private float[] mCurrentCoords = new float[6]; |
| private float mCurrentSegmentLength; |
| |
| /** |
| * Current segment length offset. When asking for the length of the current segment, the |
| * length will be reduced by this amount. This is useful when we are only using portions of |
| * the segment. |
| * |
| * @see #jumpToSegment(float) |
| */ |
| private float mOffsetLength; |
| |
| /** Point where the current segment started */ |
| private float[] mLastPoint = new float[2]; |
| private boolean isIteratorDone; |
| |
| private CachedPathIterator() { |
| next(); |
| } |
| |
| public float getCurrentSegmentLength() { |
| return mCurrentSegmentLength; |
| } |
| |
| @Override |
| public int getWindingRule() { |
| return mWindingRule; |
| } |
| |
| @Override |
| public boolean isDone() { |
| return isIteratorDone; |
| } |
| |
| @Override |
| public void next() { |
| if (mNextIndex >= mTypes.length) { |
| isIteratorDone = true; |
| return; |
| } |
| |
| if (mNextIndex >= 1) { |
| // We've already called next() once so there is a previous segment in this path. |
| // We want to get the coordinates where the path ends. |
| getShapeEndPoint(mCurrentType, mCurrentCoords, mLastPoint); |
| } else { |
| // This is the first segment, no previous point so initialize to 0, 0 |
| mLastPoint[0] = mLastPoint[1] = 0f; |
| } |
| mCurrentType = mTypes[mNextIndex]; |
| mCurrentSegmentLength = mSegmentsLength[mNextIndex] - mOffsetLength; |
| |
| if (mOffsetLength > 0f && (mCurrentType == SEG_CUBICTO || mCurrentType == SEG_QUADTO)) { |
| // We need to skip part of the start of the current segment (because |
| // mOffsetLength > 0) |
| float[] points = new float[8]; |
| |
| if (mNextIndex < 1) { |
| points[0] = points[1] = 0f; |
| } else { |
| getShapeEndPoint(mTypes[mNextIndex - 1], mCoordinates[mNextIndex - 1], points); |
| } |
| |
| System.arraycopy(mCoordinates[mNextIndex], 0, points, 2, |
| mCoordinates[mNextIndex].length); |
| float t0 = (mSegmentsLength[mNextIndex] - mCurrentSegmentLength) / |
| mSegmentsLength[mNextIndex]; |
| if (mCurrentType == SEG_CUBICTO) { |
| cubicCurveSegment(points, t0, 1f); |
| } else { |
| quadCurveSegment(points, t0, 1f); |
| } |
| System.arraycopy(points, 2, mCurrentCoords, 0, mCoordinates[mNextIndex].length); |
| } else { |
| System.arraycopy(mCoordinates[mNextIndex], 0, mCurrentCoords, 0, |
| mCoordinates[mNextIndex].length); |
| } |
| |
| mOffsetLength = 0f; |
| mNextIndex++; |
| } |
| |
| @Override |
| public int currentSegment(float[] coords) { |
| System.arraycopy(mCurrentCoords, 0, coords, 0, getNumberOfPoints(mCurrentType) * 2); |
| return mCurrentType; |
| } |
| |
| @Override |
| public int currentSegment(double[] coords) { |
| throw new UnsupportedOperationException(); |
| } |
| |
| /** |
| * Returns the point where the current segment ends |
| */ |
| public void getCurrentSegmentEnd(float[] point) { |
| point[0] = mLastPoint[0]; |
| point[1] = mLastPoint[1]; |
| } |
| |
| /** |
| * Restarts the iterator and jumps all the segments of this path up to the length value. |
| */ |
| public void jumpToSegment(float length) { |
| isIteratorDone = false; |
| if (length <= 0f) { |
| mNextIndex = 0; |
| return; |
| } |
| |
| float accLength = 0; |
| float lastPoint[] = new float[2]; |
| for (mNextIndex = 0; mNextIndex < mTypes.length; mNextIndex++) { |
| float segmentLength = mSegmentsLength[mNextIndex]; |
| if (accLength + segmentLength >= length && mTypes[mNextIndex] != SEG_MOVETO) { |
| float[] estimatedPoint = new float[2]; |
| getPointAtLength(mTypes[mNextIndex], |
| mCoordinates[mNextIndex], lastPoint[0], lastPoint[1], |
| (length - accLength) / segmentLength, |
| estimatedPoint); |
| |
| // This segment makes us go further than length so we go back one step, |
| // set a moveto and offset the length of the next segment by the length |
| // of this segment that we've already used. |
| mCurrentType = PathIterator.SEG_MOVETO; |
| mCurrentCoords[0] = estimatedPoint[0]; |
| mCurrentCoords[1] = estimatedPoint[1]; |
| mCurrentSegmentLength = 0; |
| |
| // We need to offset next path length to account for the segment we've just |
| // skipped. |
| mOffsetLength = length - accLength; |
| return; |
| } |
| accLength += segmentLength; |
| getShapeEndPoint(mTypes[mNextIndex], mCoordinates[mNextIndex], lastPoint); |
| } |
| } |
| |
| /** |
| * Returns the current segment up to certain length. If the current segment is shorter than |
| * length, then the whole segment is returned. The segment coordinates are copied into the |
| * coords array. |
| * |
| * @return the segment type |
| */ |
| public int currentSegment(@NonNull float[] coords, float length) { |
| int type = currentSegment(coords); |
| // If the length is greater than the current segment length, no need to find |
| // the cut point. Same if this is a SEG_MOVETO. |
| if (mCurrentSegmentLength <= length || type == SEG_MOVETO) { |
| return type; |
| } |
| |
| float t = length / getCurrentSegmentLength(); |
| |
| // We find at which offset the end point is located within the coords array and set |
| // a new end point to cut the segment short |
| switch (type) { |
| case SEG_CUBICTO: |
| case SEG_QUADTO: |
| float[] curve = new float[8]; |
| curve[0] = mLastPoint[0]; |
| curve[1] = mLastPoint[1]; |
| System.arraycopy(coords, 0, curve, 2, coords.length); |
| if (type == SEG_CUBICTO) { |
| cubicCurveSegment(curve, 0f, t); |
| } else { |
| quadCurveSegment(curve, 0f, t); |
| } |
| System.arraycopy(curve, 2, coords, 0, coords.length); |
| break; |
| default: |
| float[] point = new float[2]; |
| getPointAtLength(type, coords, mLastPoint[0], mLastPoint[1], t, point); |
| coords[0] = point[0]; |
| coords[1] = point[1]; |
| } |
| |
| return type; |
| } |
| |
| /** |
| * Returns the total length of the path |
| */ |
| public float getTotalLength() { |
| return mTotalLength; |
| } |
| } |
| } |