| /* |
| * Copyright 2014 Google Inc. |
| * |
| * Use of this source code is governed by a BSD-style license that can be |
| * found in the LICENSE file. |
| */ |
| |
| #include "src/utils/SkDashPathPriv.h" |
| |
| #include "include/core/SkPaint.h" |
| #include "include/core/SkPath.h" |
| #include "include/core/SkPathEffect.h" |
| #include "include/core/SkPathMeasure.h" |
| #include "include/core/SkPoint.h" |
| #include "include/core/SkRect.h" |
| #include "include/core/SkScalar.h" |
| #include "include/core/SkStrokeRec.h" |
| #include "include/core/SkTypes.h" |
| #include "include/private/base/SkAlign.h" |
| #include "include/private/base/SkPathEnums.h" |
| #include "include/private/base/SkTo.h" |
| #include "src/core/SkPathPriv.h" |
| #include "src/core/SkPointPriv.h" |
| |
| #include <algorithm> |
| #include <cmath> |
| #include <cstdint> |
| #include <iterator> |
| |
| static inline int is_even(int x) { |
| return !(x & 1); |
| } |
| |
| static SkScalar find_first_interval(const SkScalar intervals[], SkScalar phase, |
| int32_t* index, int count) { |
| for (int i = 0; i < count; ++i) { |
| SkScalar gap = intervals[i]; |
| if (phase > gap || (phase == gap && gap)) { |
| phase -= gap; |
| } else { |
| *index = i; |
| return gap - 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]; |
| } |
| |
| void SkDashPath::CalcDashParameters(SkScalar phase, const SkScalar intervals[], int32_t count, |
| SkScalar* initialDashLength, int32_t* initialDashIndex, |
| SkScalar* intervalLength, SkScalar* adjustedPhase) { |
| SkScalar len = 0; |
| for (int i = 0; i < count; i++) { |
| len += intervals[i]; |
| } |
| *intervalLength = 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 (adjustedPhase) { |
| 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); |
| } |
| *adjustedPhase = phase; |
| } |
| SkASSERT(phase >= 0 && phase < len); |
| |
| *initialDashLength = find_first_interval(intervals, phase, |
| initialDashIndex, count); |
| |
| SkASSERT(*initialDashLength >= 0); |
| SkASSERT(*initialDashIndex >= 0 && *initialDashIndex < count); |
| } |
| |
| 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 *= rec.getMiter(); |
| } |
| rect->outset(radius, radius); |
| } |
| |
| // If line is zero-length, bump out the end by a tiny amount |
| // to draw endcaps. The bump factor is sized so that |
| // SkPoint::Distance() computes a non-zero length. |
| // Offsets SK_ScalarNearlyZero or smaller create empty paths when Iter measures length. |
| // Large values are scaled by SK_ScalarNearlyZero so significant bits change. |
| static void adjust_zero_length_line(SkPoint pts[2]) { |
| SkASSERT(pts[0] == pts[1]); |
| pts[1].fX += std::max(1.001f, pts[1].fX) * SK_ScalarNearlyZero; |
| } |
| |
| static bool clip_line(SkPoint pts[2], const SkRect& bounds, SkScalar intervalLength, |
| SkScalar priorPhase) { |
| SkVector dxy = pts[1] - pts[0]; |
| |
| // only horizontal or vertical lines |
| if (dxy.fX && dxy.fY) { |
| return false; |
| } |
| int xyOffset = SkToBool(dxy.fY); // 0 to adjust horizontal, 1 to adjust vertical |
| |
| SkScalar minXY = (&pts[0].fX)[xyOffset]; |
| SkScalar maxXY = (&pts[1].fX)[xyOffset]; |
| bool swapped = maxXY < minXY; |
| if (swapped) { |
| using std::swap; |
| swap(minXY, maxXY); |
| } |
| |
| SkASSERT(minXY <= maxXY); |
| SkScalar leftTop = (&bounds.fLeft)[xyOffset]; |
| SkScalar rightBottom = (&bounds.fRight)[xyOffset]; |
| if (maxXY < leftTop || minXY > rightBottom) { |
| return false; |
| } |
| |
| // Now we actually perform the chop, removing the excess to the left/top and |
| // right/bottom of the bounds (keeping our new line "in phase" with the dash, |
| // hence the (mod intervalLength). |
| |
| if (minXY < leftTop) { |
| minXY = leftTop - SkScalarMod(leftTop - minXY, intervalLength); |
| if (!swapped) { |
| minXY -= priorPhase; // for rectangles, adjust by prior phase |
| } |
| } |
| if (maxXY > rightBottom) { |
| maxXY = rightBottom + SkScalarMod(maxXY - rightBottom, intervalLength); |
| if (swapped) { |
| maxXY += priorPhase; // for rectangles, adjust by prior phase |
| } |
| } |
| |
| SkASSERT(maxXY >= minXY); |
| if (swapped) { |
| using std::swap; |
| swap(minXY, maxXY); |
| } |
| (&pts[0].fX)[xyOffset] = minXY; |
| (&pts[1].fX)[xyOffset] = maxXY; |
| |
| if (minXY == maxXY) { |
| adjust_zero_length_line(pts); |
| } |
| return true; |
| } |
| |
| // Handles only lines and rects. |
| // If cull_path() returns true, dstPath is the new smaller path, |
| // otherwise dstPath may have been changed but you should ignore it. |
| static bool cull_path(const SkPath& srcPath, const SkStrokeRec& rec, |
| const SkRect* cullRect, SkScalar intervalLength, SkPath* dstPath) { |
| if (!cullRect) { |
| SkPoint pts[2]; |
| if (srcPath.isLine(pts) && pts[0] == pts[1]) { |
| adjust_zero_length_line(pts); |
| dstPath->moveTo(pts[0]); |
| dstPath->lineTo(pts[1]); |
| return true; |
| } |
| return false; |
| } |
| |
| SkRect bounds; |
| bounds = *cullRect; |
| outset_for_stroke(&bounds, rec); |
| |
| { |
| SkPoint pts[2]; |
| if (srcPath.isLine(pts)) { |
| if (clip_line(pts, bounds, intervalLength, 0)) { |
| dstPath->moveTo(pts[0]); |
| dstPath->lineTo(pts[1]); |
| return true; |
| } |
| return false; |
| } |
| } |
| |
| if (srcPath.isRect(nullptr)) { |
| // We'll break the rect into four lines, culling each separately. |
| SkPath::Iter iter(srcPath, false); |
| |
| SkPoint pts[4]; // Rects are all moveTo and lineTo, so we'll only use pts[0] and pts[1]. |
| SkAssertResult(SkPath::kMove_Verb == iter.next(pts)); |
| |
| double accum = 0; // Sum of unculled edge lengths to keep the phase correct. |
| // Intentionally a double to minimize the risk of overflow and drift. |
| while (iter.next(pts) == SkPath::kLine_Verb) { |
| // Notice this vector v and accum work with the original unclipped length. |
| SkVector v = pts[1] - pts[0]; |
| |
| if (clip_line(pts, bounds, intervalLength, std::fmod(accum, intervalLength))) { |
| // pts[0] may have just been changed by clip_line(). |
| // If that's not where we ended the previous lineTo(), we need to moveTo() there. |
| SkPoint last; |
| if (!dstPath->getLastPt(&last) || last != pts[0]) { |
| dstPath->moveTo(pts[0]); |
| } |
| dstPath->lineTo(pts[1]); |
| } |
| |
| // We either just traveled v.fX horizontally or v.fY vertically. |
| SkASSERT(v.fX == 0 || v.fY == 0); |
| accum += SkScalarAbs(v.fX + v.fY); |
| } |
| return !dstPath->isEmpty(); |
| } |
| |
| return false; |
| } |
| |
| 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)); |
| SkPointPriv::RotateCCW(fTangent, &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 = pathLength * intervalCount / (float)intervalLength; |
| ptCount = std::min(ptCount, SkDashPath::kMaxDashCount); |
| if (SkScalarIsNaN(ptCount)) { |
| return false; |
| } |
| 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 + fTangent.fX * d0; |
| SkScalar x1 = fPts[0].fX + fTangent.fX * d1; |
| SkScalar y0 = fPts[0].fY + fTangent.fY * d0; |
| SkScalar y1 = fPts[0].fY + 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, std::size(pts), false); |
| } |
| |
| private: |
| SkPoint fPts[2]; |
| SkVector fTangent; |
| SkVector fNormal; |
| SkScalar fPathLength; |
| }; |
| |
| |
| bool SkDashPath::InternalFilter(SkPath* dst, const SkPath& src, SkStrokeRec* rec, |
| const SkRect* cullRect, const SkScalar aIntervals[], |
| int32_t count, SkScalar initialDashLength, int32_t initialDashIndex, |
| SkScalar intervalLength, SkScalar startPhase, |
| StrokeRecApplication strokeRecApplication) { |
| // we must always have an even number of intervals |
| SkASSERT(is_even(count)); |
| |
| // we do nothing if the src wants to be filled |
| SkStrokeRec::Style style = rec->getStyle(); |
| if (SkStrokeRec::kFill_Style == style || SkStrokeRec::kStrokeAndFill_Style == style) { |
| return false; |
| } |
| |
| const SkScalar* intervals = aIntervals; |
| SkScalar dashCount = 0; |
| int segCount = 0; |
| |
| SkPath cullPathStorage; |
| const SkPath* srcPtr = &src; |
| if (cull_path(src, *rec, cullRect, intervalLength, &cullPathStorage)) { |
| // if rect is closed, starts in a dash, and ends in a dash, add the initial join |
| // potentially a better fix is described here: bug.skia.org/7445 |
| if (src.isRect(nullptr) && src.isLastContourClosed() && is_even(initialDashIndex)) { |
| SkScalar pathLength = SkPathMeasure(src, false, rec->getResScale()).getLength(); |
| #if defined(SK_LEGACY_RECT_DASHING_BUG) |
| SkScalar endPhase = SkScalarMod(pathLength + initialDashLength, intervalLength); |
| #else |
| SkScalar endPhase = SkScalarMod(pathLength + startPhase, intervalLength); |
| #endif |
| int index = 0; |
| while (endPhase > intervals[index]) { |
| endPhase -= intervals[index++]; |
| SkASSERT(index <= count); |
| if (index == count) { |
| // We have run out of intervals. endPhase "should" never get to this point, |
| // but it could if the subtracts underflowed. Hence we will pin it as if it |
| // perfectly ran through the intervals. |
| // See crbug.com/875494 (and skbug.com/8274) |
| endPhase = 0; |
| break; |
| } |
| } |
| // if dash ends inside "on", or ends at beginning of "off" |
| if (is_even(index) == (endPhase > 0)) { |
| SkPoint midPoint = src.getPoint(0); |
| // get vector at end of rect |
| int last = src.countPoints() - 1; |
| while (midPoint == src.getPoint(last)) { |
| --last; |
| SkASSERT(last >= 0); |
| } |
| // get vector at start of rect |
| int next = 1; |
| while (midPoint == src.getPoint(next)) { |
| ++next; |
| SkASSERT(next < last); |
| } |
| SkVector v = midPoint - src.getPoint(last); |
| const SkScalar kTinyOffset = SK_ScalarNearlyZero; |
| // scale vector to make start of tiny right angle |
| v *= kTinyOffset; |
| cullPathStorage.moveTo(midPoint - v); |
| cullPathStorage.lineTo(midPoint); |
| v = midPoint - src.getPoint(next); |
| // scale vector to make end of tiny right angle |
| v *= kTinyOffset; |
| cullPathStorage.lineTo(midPoint - v); |
| } |
| } |
| srcPtr = &cullPathStorage; |
| } |
| |
| SpecialLineRec lineRec; |
| bool specialLine = (StrokeRecApplication::kAllow == strokeRecApplication) && |
| lineRec.init(*srcPtr, dst, rec, count >> 1, intervalLength); |
| |
| SkPathMeasure meas(*srcPtr, false, rec->getResScale()); |
| |
| do { |
| bool skipFirstSegment = meas.isClosed(); |
| bool addedSegment = false; |
| SkScalar length = meas.getLength(); |
| int index = initialDashIndex; |
| |
| // 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. |
| dashCount += length * (count >> 1) / intervalLength; |
| if (dashCount > kMaxDashCount) { |
| dst->reset(); |
| return false; |
| } |
| |
| // 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 = initialDashLength; |
| |
| while (distance < length) { |
| SkASSERT(dlen >= 0); |
| addedSegment = false; |
| if (is_even(index) && !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 <= count); |
| if (index == count) { |
| index = 0; |
| } |
| |
| // fetch our next dlen |
| dlen = intervals[index]; |
| } |
| |
| // extend if we ended on a segment and we need to join up with the (skipped) initial segment |
| if (meas.isClosed() && is_even(initialDashIndex) && |
| initialDashLength >= 0) { |
| meas.getSegment(0, initialDashLength, dst, !addedSegment); |
| ++segCount; |
| } |
| } while (meas.nextContour()); |
| |
| // TODO: do we still need this? |
| if (segCount > 1) { |
| SkPathPriv::SetConvexity(*dst, SkPathConvexity::kConcave); |
| } |
| |
| return true; |
| } |
| |
| bool SkDashPath::FilterDashPath(SkPath* dst, const SkPath& src, SkStrokeRec* rec, |
| const SkRect* cullRect, const SkPathEffect::DashInfo& info) { |
| if (!ValidDashPath(info.fPhase, info.fIntervals, info.fCount)) { |
| return false; |
| } |
| SkScalar initialDashLength = 0; |
| int32_t initialDashIndex = 0; |
| SkScalar intervalLength = 0; |
| CalcDashParameters(info.fPhase, info.fIntervals, info.fCount, |
| &initialDashLength, &initialDashIndex, &intervalLength); |
| return InternalFilter(dst, src, rec, cullRect, info.fIntervals, info.fCount, initialDashLength, |
| initialDashIndex, intervalLength, info.fPhase); |
| } |
| |
| bool SkDashPath::ValidDashPath(SkScalar phase, const SkScalar intervals[], int32_t count) { |
| if (count < 2 || !SkIsAlign2(count)) { |
| return false; |
| } |
| SkScalar length = 0; |
| for (int i = 0; i < count; i++) { |
| if (intervals[i] < 0) { |
| return false; |
| } |
| length += intervals[i]; |
| } |
| // watch out for values that might make us go out of bounds |
| return length > 0 && SkScalarIsFinite(phase) && SkScalarIsFinite(length); |
| } |