| |
| /* |
| * Copyright 2006 The Android Open Source Project |
| * |
| * Use of this source code is governed by a BSD-style license that can be |
| * found in the LICENSE file. |
| */ |
| |
| |
| #include "SkDashPathEffect.h" |
| #include "SkFlattenableBuffers.h" |
| #include "SkPathMeasure.h" |
| |
| static inline int is_even(int x) { |
| return (~x) << 31; |
| } |
| |
| static SkScalar FindFirstInterval(const SkScalar intervals[], SkScalar phase, |
| int32_t* index, int count) { |
| for (int i = 0; i < count; ++i) { |
| if (phase > intervals[i]) { |
| phase -= intervals[i]; |
| } else { |
| *index = i; |
| return intervals[i] - phase; |
| } |
| } |
| // If we get here, phase "appears" to be larger than our length. This |
| // shouldn't happen with perfect precision, but we can accumulate errors |
| // during the initial length computation (rounding can make our sum be too |
| // big or too small. In that event, we just have to eat the error here. |
| *index = 0; |
| return intervals[0]; |
| } |
| |
| SkDashPathEffect::SkDashPathEffect(const SkScalar intervals[], int count, |
| SkScalar phase, bool scaleToFit) |
| : fScaleToFit(scaleToFit) { |
| SkASSERT(intervals); |
| SkASSERT(count > 1 && SkAlign2(count) == count); |
| |
| fIntervals = (SkScalar*)sk_malloc_throw(sizeof(SkScalar) * count); |
| fCount = count; |
| |
| SkScalar len = 0; |
| for (int i = 0; i < count; i++) { |
| SkASSERT(intervals[i] >= 0); |
| fIntervals[i] = intervals[i]; |
| len += intervals[i]; |
| } |
| fIntervalLength = len; |
| |
| // watch out for values that might make us go out of bounds |
| if ((len > 0) && SkScalarIsFinite(phase) && SkScalarIsFinite(len)) { |
| |
| // Adjust phase to be between 0 and len, "flipping" phase if negative. |
| // e.g., if len is 100, then phase of -20 (or -120) is equivalent to 80 |
| if (phase < 0) { |
| phase = -phase; |
| if (phase > len) { |
| phase = SkScalarMod(phase, len); |
| } |
| phase = len - phase; |
| |
| // Due to finite precision, it's possible that phase == len, |
| // even after the subtract (if len >>> phase), so fix that here. |
| // This fixes http://crbug.com/124652 . |
| SkASSERT(phase <= len); |
| if (phase == len) { |
| phase = 0; |
| } |
| } else if (phase >= len) { |
| phase = SkScalarMod(phase, len); |
| } |
| SkASSERT(phase >= 0 && phase < len); |
| |
| fInitialDashLength = FindFirstInterval(intervals, phase, |
| &fInitialDashIndex, count); |
| |
| SkASSERT(fInitialDashLength >= 0); |
| SkASSERT(fInitialDashIndex >= 0 && fInitialDashIndex < fCount); |
| } else { |
| fInitialDashLength = -1; // signal bad dash intervals |
| } |
| } |
| |
| SkDashPathEffect::~SkDashPathEffect() { |
| sk_free(fIntervals); |
| } |
| |
| static void outset_for_stroke(SkRect* rect, const SkStrokeRec& rec) { |
| SkScalar radius = SkScalarHalf(rec.getWidth()); |
| if (0 == radius) { |
| radius = SK_Scalar1; // hairlines |
| } |
| if (SkPaint::kMiter_Join == rec.getJoin()) { |
| radius = SkScalarMul(radius, rec.getMiter()); |
| } |
| rect->outset(radius, radius); |
| } |
| |
| // Only handles lines for now. If returns true, dstPath is the new (smaller) |
| // path. If returns false, then dstPath parameter is ignored. |
| static bool cull_path(const SkPath& srcPath, const SkStrokeRec& rec, |
| const SkRect* cullRect, SkScalar intervalLength, |
| SkPath* dstPath) { |
| if (NULL == cullRect) { |
| return false; |
| } |
| |
| SkPoint pts[2]; |
| if (!srcPath.isLine(pts)) { |
| return false; |
| } |
| |
| SkRect bounds = *cullRect; |
| outset_for_stroke(&bounds, rec); |
| |
| SkScalar dx = pts[1].x() - pts[0].x(); |
| SkScalar dy = pts[1].y() - pts[0].y(); |
| |
| // just do horizontal lines for now (lazy) |
| if (dy) { |
| return false; |
| } |
| |
| SkScalar minX = pts[0].fX; |
| SkScalar maxX = pts[1].fX; |
| |
| if (maxX < bounds.fLeft || minX > bounds.fRight) { |
| return false; |
| } |
| |
| if (dx < 0) { |
| SkTSwap(minX, maxX); |
| } |
| |
| // Now we actually perform the chop, removing the excess to the left and |
| // right of the bounds (keeping our new line "in phase" with the dash, |
| // hence the (mod intervalLength). |
| |
| if (minX < bounds.fLeft) { |
| minX = bounds.fLeft - SkScalarMod(bounds.fLeft - minX, |
| intervalLength); |
| } |
| if (maxX > bounds.fRight) { |
| maxX = bounds.fRight + SkScalarMod(maxX - bounds.fRight, |
| intervalLength); |
| } |
| |
| SkASSERT(maxX >= minX); |
| if (dx < 0) { |
| SkTSwap(minX, maxX); |
| } |
| pts[0].fX = minX; |
| pts[1].fX = maxX; |
| |
| dstPath->moveTo(pts[0]); |
| dstPath->lineTo(pts[1]); |
| return true; |
| } |
| |
| class SpecialLineRec { |
| public: |
| bool init(const SkPath& src, SkPath* dst, SkStrokeRec* rec, |
| int intervalCount, SkScalar intervalLength) { |
| if (rec->isHairlineStyle() || !src.isLine(fPts)) { |
| return false; |
| } |
| |
| // can relax this in the future, if we handle square and round caps |
| if (SkPaint::kButt_Cap != rec->getCap()) { |
| return false; |
| } |
| |
| SkScalar pathLength = SkPoint::Distance(fPts[0], fPts[1]); |
| |
| fTangent = fPts[1] - fPts[0]; |
| if (fTangent.isZero()) { |
| return false; |
| } |
| |
| fPathLength = pathLength; |
| fTangent.scale(SkScalarInvert(pathLength)); |
| fTangent.rotateCCW(&fNormal); |
| fNormal.scale(SkScalarHalf(rec->getWidth())); |
| |
| // now estimate how many quads will be added to the path |
| // resulting segments = pathLen * intervalCount / intervalLen |
| // resulting points = 4 * segments |
| |
| SkScalar ptCount = SkScalarMulDiv(pathLength, |
| SkIntToScalar(intervalCount), |
| intervalLength); |
| int n = SkScalarCeilToInt(ptCount) << 2; |
| dst->incReserve(n); |
| |
| // we will take care of the stroking |
| rec->setFillStyle(); |
| return true; |
| } |
| |
| void addSegment(SkScalar d0, SkScalar d1, SkPath* path) const { |
| SkASSERT(d0 < fPathLength); |
| // clamp the segment to our length |
| if (d1 > fPathLength) { |
| d1 = fPathLength; |
| } |
| |
| SkScalar x0 = fPts[0].fX + SkScalarMul(fTangent.fX, d0); |
| SkScalar x1 = fPts[0].fX + SkScalarMul(fTangent.fX, d1); |
| SkScalar y0 = fPts[0].fY + SkScalarMul(fTangent.fY, d0); |
| SkScalar y1 = fPts[0].fY + SkScalarMul(fTangent.fY, d1); |
| |
| SkPoint pts[4]; |
| pts[0].set(x0 + fNormal.fX, y0 + fNormal.fY); // moveTo |
| pts[1].set(x1 + fNormal.fX, y1 + fNormal.fY); // lineTo |
| pts[2].set(x1 - fNormal.fX, y1 - fNormal.fY); // lineTo |
| pts[3].set(x0 - fNormal.fX, y0 - fNormal.fY); // lineTo |
| |
| path->addPoly(pts, SK_ARRAY_COUNT(pts), false); |
| } |
| |
| private: |
| SkPoint fPts[2]; |
| SkVector fTangent; |
| SkVector fNormal; |
| SkScalar fPathLength; |
| }; |
| |
| bool SkDashPathEffect::filterPath(SkPath* dst, const SkPath& src, |
| SkStrokeRec* rec, const SkRect* cullRect) const { |
| // we do nothing if the src wants to be filled, or if our dashlength is 0 |
| if (rec->isFillStyle() || fInitialDashLength < 0) { |
| return false; |
| } |
| |
| const SkScalar* intervals = fIntervals; |
| SkScalar dashCount = 0; |
| int segCount = 0; |
| |
| SkPath cullPathStorage; |
| const SkPath* srcPtr = &src; |
| if (cull_path(src, *rec, cullRect, fIntervalLength, &cullPathStorage)) { |
| srcPtr = &cullPathStorage; |
| } |
| |
| SpecialLineRec lineRec; |
| bool specialLine = lineRec.init(*srcPtr, dst, rec, fCount >> 1, fIntervalLength); |
| |
| SkPathMeasure meas(*srcPtr, false); |
| |
| do { |
| bool skipFirstSegment = meas.isClosed(); |
| bool addedSegment = false; |
| SkScalar length = meas.getLength(); |
| int index = fInitialDashIndex; |
| SkScalar scale = SK_Scalar1; |
| |
| // Since the path length / dash length ratio may be arbitrarily large, we can exert |
| // significant memory pressure while attempting to build the filtered path. To avoid this, |
| // we simply give up dashing beyond a certain threshold. |
| // |
| // The original bug report (http://crbug.com/165432) is based on a path yielding more than |
| // 90 million dash segments and crashing the memory allocator. A limit of 1 million |
| // segments seems reasonable: at 2 verbs per segment * 9 bytes per verb, this caps the |
| // maximum dash memory overhead at roughly 17MB per path. |
| static const SkScalar kMaxDashCount = 1000000; |
| dashCount += length * (fCount >> 1) / fIntervalLength; |
| if (dashCount > kMaxDashCount) { |
| dst->reset(); |
| return false; |
| } |
| |
| if (fScaleToFit) { |
| if (fIntervalLength >= length) { |
| scale = SkScalarDiv(length, fIntervalLength); |
| } else { |
| SkScalar div = SkScalarDiv(length, fIntervalLength); |
| int n = SkScalarFloor(div); |
| scale = SkScalarDiv(length, n * fIntervalLength); |
| } |
| } |
| |
| // Using double precision to avoid looping indefinitely due to single precision rounding |
| // (for extreme path_length/dash_length ratios). See test_infinite_dash() unittest. |
| double distance = 0; |
| double dlen = SkScalarMul(fInitialDashLength, scale); |
| |
| while (distance < length) { |
| SkASSERT(dlen >= 0); |
| addedSegment = false; |
| if (is_even(index) && dlen > 0 && !skipFirstSegment) { |
| addedSegment = true; |
| ++segCount; |
| |
| if (specialLine) { |
| lineRec.addSegment(SkDoubleToScalar(distance), |
| SkDoubleToScalar(distance + dlen), |
| dst); |
| } else { |
| meas.getSegment(SkDoubleToScalar(distance), |
| SkDoubleToScalar(distance + dlen), |
| dst, true); |
| } |
| } |
| distance += dlen; |
| |
| // clear this so we only respect it the first time around |
| skipFirstSegment = false; |
| |
| // wrap around our intervals array if necessary |
| index += 1; |
| SkASSERT(index <= fCount); |
| if (index == fCount) { |
| index = 0; |
| } |
| |
| // fetch our next dlen |
| dlen = SkScalarMul(intervals[index], scale); |
| } |
| |
| // extend if we ended on a segment and we need to join up with the (skipped) initial segment |
| if (meas.isClosed() && is_even(fInitialDashIndex) && |
| fInitialDashLength > 0) { |
| meas.getSegment(0, SkScalarMul(fInitialDashLength, scale), dst, !addedSegment); |
| ++segCount; |
| } |
| } while (meas.nextContour()); |
| |
| if (segCount > 1) { |
| dst->setConvexity(SkPath::kConcave_Convexity); |
| } |
| |
| return true; |
| } |
| |
| // Currently asPoints is more restrictive then it needs to be. In the future |
| // we need to: |
| // allow kRound_Cap capping (could allow rotations in the matrix with this) |
| // allow paths to be returned |
| bool SkDashPathEffect::asPoints(PointData* results, |
| const SkPath& src, |
| const SkStrokeRec& rec, |
| const SkMatrix& matrix, |
| const SkRect* cullRect) const { |
| // width < 0 -> fill && width == 0 -> hairline so requiring width > 0 rules both out |
| if (fInitialDashLength < 0 || 0 >= rec.getWidth()) { |
| return false; |
| } |
| |
| // TODO: this next test could be eased up. We could allow any number of |
| // intervals as long as all the ons match and all the offs match. |
| // Additionally, they do not necessarily need to be integers. |
| // We cannot allow arbitrary intervals since we want the returned points |
| // to be uniformly sized. |
| if (fCount != 2 || |
| !SkScalarNearlyEqual(fIntervals[0], fIntervals[1]) || |
| !SkScalarIsInt(fIntervals[0]) || |
| !SkScalarIsInt(fIntervals[1])) { |
| return false; |
| } |
| |
| // TODO: this next test could be eased up. The rescaling should not impact |
| // the equality of the ons & offs. However, we would need to remove the |
| // integer intervals restriction first |
| if (fScaleToFit) { |
| return false; |
| } |
| |
| SkPoint pts[2]; |
| |
| if (!src.isLine(pts)) { |
| return false; |
| } |
| |
| // TODO: this test could be eased up to allow circles |
| if (SkPaint::kButt_Cap != rec.getCap()) { |
| return false; |
| } |
| |
| // TODO: this test could be eased up for circles. Rotations could be allowed. |
| if (!matrix.rectStaysRect()) { |
| return false; |
| } |
| |
| SkScalar length = SkPoint::Distance(pts[1], pts[0]); |
| |
| SkVector tangent = pts[1] - pts[0]; |
| if (tangent.isZero()) { |
| return false; |
| } |
| |
| tangent.scale(SkScalarInvert(length)); |
| |
| // TODO: make this test for horizontal & vertical lines more robust |
| bool isXAxis = true; |
| if (SK_Scalar1 == tangent.fX || -SK_Scalar1 == tangent.fX) { |
| results->fSize.set(SkScalarHalf(fIntervals[0]), SkScalarHalf(rec.getWidth())); |
| } else if (SK_Scalar1 == tangent.fY || -SK_Scalar1 == tangent.fY) { |
| results->fSize.set(SkScalarHalf(rec.getWidth()), SkScalarHalf(fIntervals[0])); |
| isXAxis = false; |
| } else if (SkPaint::kRound_Cap != rec.getCap()) { |
| // Angled lines don't have axis-aligned boxes. |
| return false; |
| } |
| |
| if (NULL != results) { |
| results->fFlags = 0; |
| SkScalar clampedInitialDashLength = SkMinScalar(length, fInitialDashLength); |
| |
| if (SkPaint::kRound_Cap == rec.getCap()) { |
| results->fFlags |= PointData::kCircles_PointFlag; |
| } |
| |
| results->fNumPoints = 0; |
| SkScalar len2 = length; |
| if (clampedInitialDashLength > 0 || 0 == fInitialDashIndex) { |
| SkASSERT(len2 >= clampedInitialDashLength); |
| if (0 == fInitialDashIndex) { |
| if (clampedInitialDashLength > 0) { |
| if (clampedInitialDashLength >= fIntervals[0]) { |
| ++results->fNumPoints; // partial first dash |
| } |
| len2 -= clampedInitialDashLength; |
| } |
| len2 -= fIntervals[1]; // also skip first space |
| if (len2 < 0) { |
| len2 = 0; |
| } |
| } else { |
| len2 -= clampedInitialDashLength; // skip initial partial empty |
| } |
| } |
| int numMidPoints = SkScalarFloorToInt(SkScalarDiv(len2, fIntervalLength)); |
| results->fNumPoints += numMidPoints; |
| len2 -= numMidPoints * fIntervalLength; |
| bool partialLast = false; |
| if (len2 > 0) { |
| if (len2 < fIntervals[0]) { |
| partialLast = true; |
| } else { |
| ++numMidPoints; |
| ++results->fNumPoints; |
| } |
| } |
| |
| results->fPoints = new SkPoint[results->fNumPoints]; |
| |
| SkScalar distance = 0; |
| int curPt = 0; |
| |
| if (clampedInitialDashLength > 0 || 0 == fInitialDashIndex) { |
| SkASSERT(clampedInitialDashLength <= length); |
| |
| if (0 == fInitialDashIndex) { |
| if (clampedInitialDashLength > 0) { |
| // partial first block |
| SkASSERT(SkPaint::kRound_Cap != rec.getCap()); // can't handle partial circles |
| SkScalar x = pts[0].fX + SkScalarMul(tangent.fX, SkScalarHalf(clampedInitialDashLength)); |
| SkScalar y = pts[0].fY + SkScalarMul(tangent.fY, SkScalarHalf(clampedInitialDashLength)); |
| SkScalar halfWidth, halfHeight; |
| if (isXAxis) { |
| halfWidth = SkScalarHalf(clampedInitialDashLength); |
| halfHeight = SkScalarHalf(rec.getWidth()); |
| } else { |
| halfWidth = SkScalarHalf(rec.getWidth()); |
| halfHeight = SkScalarHalf(clampedInitialDashLength); |
| } |
| if (clampedInitialDashLength < fIntervals[0]) { |
| // This one will not be like the others |
| results->fFirst.addRect(x - halfWidth, y - halfHeight, |
| x + halfWidth, y + halfHeight); |
| } else { |
| SkASSERT(curPt < results->fNumPoints); |
| results->fPoints[curPt].set(x, y); |
| ++curPt; |
| } |
| |
| distance += clampedInitialDashLength; |
| } |
| |
| distance += fIntervals[1]; // skip over the next blank block too |
| } else { |
| distance += clampedInitialDashLength; |
| } |
| } |
| |
| if (0 != numMidPoints) { |
| distance += SkScalarHalf(fIntervals[0]); |
| |
| for (int i = 0; i < numMidPoints; ++i) { |
| SkScalar x = pts[0].fX + SkScalarMul(tangent.fX, distance); |
| SkScalar y = pts[0].fY + SkScalarMul(tangent.fY, distance); |
| |
| SkASSERT(curPt < results->fNumPoints); |
| results->fPoints[curPt].set(x, y); |
| ++curPt; |
| |
| distance += fIntervalLength; |
| } |
| |
| distance -= SkScalarHalf(fIntervals[0]); |
| } |
| |
| if (partialLast) { |
| // partial final block |
| SkASSERT(SkPaint::kRound_Cap != rec.getCap()); // can't handle partial circles |
| SkScalar temp = length - distance; |
| SkASSERT(temp < fIntervals[0]); |
| SkScalar x = pts[0].fX + SkScalarMul(tangent.fX, distance + SkScalarHalf(temp)); |
| SkScalar y = pts[0].fY + SkScalarMul(tangent.fY, distance + SkScalarHalf(temp)); |
| SkScalar halfWidth, halfHeight; |
| if (isXAxis) { |
| halfWidth = SkScalarHalf(temp); |
| halfHeight = SkScalarHalf(rec.getWidth()); |
| } else { |
| halfWidth = SkScalarHalf(rec.getWidth()); |
| halfHeight = SkScalarHalf(temp); |
| } |
| results->fLast.addRect(x - halfWidth, y - halfHeight, |
| x + halfWidth, y + halfHeight); |
| } |
| |
| SkASSERT(curPt == results->fNumPoints); |
| } |
| |
| return true; |
| } |
| |
| SkFlattenable::Factory SkDashPathEffect::getFactory() { |
| return fInitialDashLength < 0 ? NULL : CreateProc; |
| } |
| |
| void SkDashPathEffect::flatten(SkFlattenableWriteBuffer& buffer) const { |
| SkASSERT(fInitialDashLength >= 0); |
| |
| this->INHERITED::flatten(buffer); |
| buffer.writeInt(fInitialDashIndex); |
| buffer.writeScalar(fInitialDashLength); |
| buffer.writeScalar(fIntervalLength); |
| buffer.writeBool(fScaleToFit); |
| buffer.writeScalarArray(fIntervals, fCount); |
| } |
| |
| SkFlattenable* SkDashPathEffect::CreateProc(SkFlattenableReadBuffer& buffer) { |
| return SkNEW_ARGS(SkDashPathEffect, (buffer)); |
| } |
| |
| SkDashPathEffect::SkDashPathEffect(SkFlattenableReadBuffer& buffer) : INHERITED(buffer) { |
| fInitialDashIndex = buffer.readInt(); |
| fInitialDashLength = buffer.readScalar(); |
| fIntervalLength = buffer.readScalar(); |
| fScaleToFit = buffer.readBool(); |
| |
| fCount = buffer.getArrayCount(); |
| fIntervals = (SkScalar*)sk_malloc_throw(sizeof(SkScalar) * fCount); |
| buffer.readScalarArray(fIntervals); |
| } |
