1a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel/* 2a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel * Copyright 2014 Google Inc. 3a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel * 4a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel * Use of this source code is governed by a BSD-style license that can be 5a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel * found in the LICENSE file. 6a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel */ 7a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 8a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel#include "SkDashPathPriv.h" 9a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel#include "SkPathMeasure.h" 10a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 11a22ea1882391cc5c84136060636d5c952c1f34b3egdanielstatic inline int is_even(int x) { 12a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel return (~x) << 31; 13a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel} 14a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 15a22ea1882391cc5c84136060636d5c952c1f34b3egdanielstatic SkScalar find_first_interval(const SkScalar intervals[], SkScalar phase, 16a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel int32_t* index, int count) { 17a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel for (int i = 0; i < count; ++i) { 18a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (phase > intervals[i]) { 19a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel phase -= intervals[i]; 20a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } else { 21a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel *index = i; 22a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel return intervals[i] - phase; 23a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 24a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 25a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // If we get here, phase "appears" to be larger than our length. This 26a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // shouldn't happen with perfect precision, but we can accumulate errors 27a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // during the initial length computation (rounding can make our sum be too 28a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // big or too small. In that event, we just have to eat the error here. 29a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel *index = 0; 30a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel return intervals[0]; 31a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel} 32a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 33a22ea1882391cc5c84136060636d5c952c1f34b3egdanielvoid SkDashPath::CalcDashParameters(SkScalar phase, const SkScalar intervals[], int32_t count, 34a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkScalar* initialDashLength, int32_t* initialDashIndex, 35a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkScalar* intervalLength, SkScalar* adjustedPhase) { 36a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkScalar len = 0; 37a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel for (int i = 0; i < count; i++) { 38a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel len += intervals[i]; 39a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 40a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel *intervalLength = len; 41a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 42a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // watch out for values that might make us go out of bounds 43a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if ((len > 0) && SkScalarIsFinite(phase) && SkScalarIsFinite(len)) { 44a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 45a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // Adjust phase to be between 0 and len, "flipping" phase if negative. 46a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // e.g., if len is 100, then phase of -20 (or -120) is equivalent to 80 47a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (adjustedPhase) { 48a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (phase < 0) { 49a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel phase = -phase; 50a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (phase > len) { 51a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel phase = SkScalarMod(phase, len); 52a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 53a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel phase = len - phase; 54a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 55a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // Due to finite precision, it's possible that phase == len, 56a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // even after the subtract (if len >>> phase), so fix that here. 57a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // This fixes http://crbug.com/124652 . 58a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkASSERT(phase <= len); 59a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (phase == len) { 60a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel phase = 0; 61a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 62a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } else if (phase >= len) { 63a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel phase = SkScalarMod(phase, len); 64a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 65a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel *adjustedPhase = phase; 66a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 67a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkASSERT(phase >= 0 && phase < len); 68a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 69a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel *initialDashLength = find_first_interval(intervals, phase, 70a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel initialDashIndex, count); 71a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 72a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkASSERT(*initialDashLength >= 0); 73a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkASSERT(*initialDashIndex >= 0 && *initialDashIndex < count); 74a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } else { 75a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel *initialDashLength = -1; // signal bad dash intervals 76a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 77a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel} 78a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 79a22ea1882391cc5c84136060636d5c952c1f34b3egdanielstatic void outset_for_stroke(SkRect* rect, const SkStrokeRec& rec) { 80a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkScalar radius = SkScalarHalf(rec.getWidth()); 81a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (0 == radius) { 82a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel radius = SK_Scalar1; // hairlines 83a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 84a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (SkPaint::kMiter_Join == rec.getJoin()) { 85a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel radius = SkScalarMul(radius, rec.getMiter()); 86a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 87a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel rect->outset(radius, radius); 88a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel} 89a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 90a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel// Only handles lines for now. If returns true, dstPath is the new (smaller) 91a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel// path. If returns false, then dstPath parameter is ignored. 92a22ea1882391cc5c84136060636d5c952c1f34b3egdanielstatic bool cull_path(const SkPath& srcPath, const SkStrokeRec& rec, 93a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel const SkRect* cullRect, SkScalar intervalLength, 94a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkPath* dstPath) { 95a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (NULL == cullRect) { 96a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel return false; 97a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 98a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 99a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkPoint pts[2]; 100a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (!srcPath.isLine(pts)) { 101a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel return false; 102a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 103a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 104a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkRect bounds = *cullRect; 105a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel outset_for_stroke(&bounds, rec); 106a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 107a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkScalar dx = pts[1].x() - pts[0].x(); 108a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkScalar dy = pts[1].y() - pts[0].y(); 109a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 110a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // just do horizontal lines for now (lazy) 111a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (dy) { 112a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel return false; 113a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 114a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 115a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkScalar minX = pts[0].fX; 116a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkScalar maxX = pts[1].fX; 117a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 118a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (dx < 0) { 119a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkTSwap(minX, maxX); 120a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 121a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 12221402e3851454e90329bad52893f29959da086f7egdaniel SkASSERT(minX <= maxX); 1239f2251c73ed6f417dd1057d487bf523e04488440robertphillips if (maxX < bounds.fLeft || minX > bounds.fRight) { 1249f2251c73ed6f417dd1057d487bf523e04488440robertphillips return false; 1259f2251c73ed6f417dd1057d487bf523e04488440robertphillips } 1269f2251c73ed6f417dd1057d487bf523e04488440robertphillips 127a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // Now we actually perform the chop, removing the excess to the left and 128a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // right of the bounds (keeping our new line "in phase" with the dash, 129a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // hence the (mod intervalLength). 130a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 131a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (minX < bounds.fLeft) { 132a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel minX = bounds.fLeft - SkScalarMod(bounds.fLeft - minX, 133a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel intervalLength); 134a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 135a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (maxX > bounds.fRight) { 136a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel maxX = bounds.fRight + SkScalarMod(maxX - bounds.fRight, 137a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel intervalLength); 138a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 139a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 140a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkASSERT(maxX >= minX); 141a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (dx < 0) { 142a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkTSwap(minX, maxX); 143a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 144a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel pts[0].fX = minX; 145a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel pts[1].fX = maxX; 146a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 147a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel dstPath->moveTo(pts[0]); 148a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel dstPath->lineTo(pts[1]); 149a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel return true; 150a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel} 151a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 152a22ea1882391cc5c84136060636d5c952c1f34b3egdanielclass SpecialLineRec { 153a22ea1882391cc5c84136060636d5c952c1f34b3egdanielpublic: 154a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel bool init(const SkPath& src, SkPath* dst, SkStrokeRec* rec, 155a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel int intervalCount, SkScalar intervalLength) { 156a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (rec->isHairlineStyle() || !src.isLine(fPts)) { 157a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel return false; 158a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 159a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 160a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // can relax this in the future, if we handle square and round caps 161a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (SkPaint::kButt_Cap != rec->getCap()) { 162a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel return false; 163a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 164a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 165a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkScalar pathLength = SkPoint::Distance(fPts[0], fPts[1]); 166a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 167a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel fTangent = fPts[1] - fPts[0]; 168a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (fTangent.isZero()) { 169a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel return false; 170a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 171a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 172a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel fPathLength = pathLength; 173a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel fTangent.scale(SkScalarInvert(pathLength)); 174a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel fTangent.rotateCCW(&fNormal); 175a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel fNormal.scale(SkScalarHalf(rec->getWidth())); 176a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 177a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // now estimate how many quads will be added to the path 178a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // resulting segments = pathLen * intervalCount / intervalLen 179a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // resulting points = 4 * segments 180a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 181a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkScalar ptCount = SkScalarMulDiv(pathLength, 182a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkIntToScalar(intervalCount), 183a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel intervalLength); 184a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel int n = SkScalarCeilToInt(ptCount) << 2; 185a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel dst->incReserve(n); 186a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 187a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // we will take care of the stroking 188a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel rec->setFillStyle(); 189a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel return true; 190a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 191a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 192a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel void addSegment(SkScalar d0, SkScalar d1, SkPath* path) const { 193a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkASSERT(d0 < fPathLength); 194a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // clamp the segment to our length 195a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (d1 > fPathLength) { 196a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel d1 = fPathLength; 197a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 198a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 199a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkScalar x0 = fPts[0].fX + SkScalarMul(fTangent.fX, d0); 200a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkScalar x1 = fPts[0].fX + SkScalarMul(fTangent.fX, d1); 201a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkScalar y0 = fPts[0].fY + SkScalarMul(fTangent.fY, d0); 202a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkScalar y1 = fPts[0].fY + SkScalarMul(fTangent.fY, d1); 203a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 204a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkPoint pts[4]; 205a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel pts[0].set(x0 + fNormal.fX, y0 + fNormal.fY); // moveTo 206a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel pts[1].set(x1 + fNormal.fX, y1 + fNormal.fY); // lineTo 207a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel pts[2].set(x1 - fNormal.fX, y1 - fNormal.fY); // lineTo 208a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel pts[3].set(x0 - fNormal.fX, y0 - fNormal.fY); // lineTo 209a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 210a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel path->addPoly(pts, SK_ARRAY_COUNT(pts), false); 211a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 212a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 213a22ea1882391cc5c84136060636d5c952c1f34b3egdanielprivate: 214a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkPoint fPts[2]; 215a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkVector fTangent; 216a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkVector fNormal; 217a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkScalar fPathLength; 218a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel}; 219a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 220a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 221a22ea1882391cc5c84136060636d5c952c1f34b3egdanielbool SkDashPath::FilterDashPath(SkPath* dst, const SkPath& src, SkStrokeRec* rec, 222a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel const SkRect* cullRect, const SkScalar aIntervals[], 223a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel int32_t count, SkScalar initialDashLength, int32_t initialDashIndex, 224a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkScalar intervalLength) { 225a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 226a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // we do nothing if the src wants to be filled, or if our dashlength is 0 227a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (rec->isFillStyle() || initialDashLength < 0) { 228a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel return false; 229a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 230a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 231a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel const SkScalar* intervals = aIntervals; 232a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkScalar dashCount = 0; 233a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel int segCount = 0; 234a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 235a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkPath cullPathStorage; 236a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel const SkPath* srcPtr = &src; 237a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (cull_path(src, *rec, cullRect, intervalLength, &cullPathStorage)) { 238a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel srcPtr = &cullPathStorage; 239a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 240a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 241a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SpecialLineRec lineRec; 242a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel bool specialLine = lineRec.init(*srcPtr, dst, rec, count >> 1, intervalLength); 243a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 244a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkPathMeasure meas(*srcPtr, false); 245a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 246a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel do { 247a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel bool skipFirstSegment = meas.isClosed(); 248a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel bool addedSegment = false; 249a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkScalar length = meas.getLength(); 250a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel int index = initialDashIndex; 251a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 252a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // Since the path length / dash length ratio may be arbitrarily large, we can exert 253a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // significant memory pressure while attempting to build the filtered path. To avoid this, 254a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // we simply give up dashing beyond a certain threshold. 255a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // 256a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // The original bug report (http://crbug.com/165432) is based on a path yielding more than 257a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // 90 million dash segments and crashing the memory allocator. A limit of 1 million 258a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // segments seems reasonable: at 2 verbs per segment * 9 bytes per verb, this caps the 259a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // maximum dash memory overhead at roughly 17MB per path. 260a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel static const SkScalar kMaxDashCount = 1000000; 261a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel dashCount += length * (count >> 1) / intervalLength; 262a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (dashCount > kMaxDashCount) { 263a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel dst->reset(); 264a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel return false; 265a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 266a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 267a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // Using double precision to avoid looping indefinitely due to single precision rounding 268a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // (for extreme path_length/dash_length ratios). See test_infinite_dash() unittest. 269a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel double distance = 0; 270a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel double dlen = initialDashLength; 271a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 272a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel while (distance < length) { 273a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkASSERT(dlen >= 0); 274a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel addedSegment = false; 275a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (is_even(index) && dlen > 0 && !skipFirstSegment) { 276a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel addedSegment = true; 277a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel ++segCount; 278a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 279a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (specialLine) { 280a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel lineRec.addSegment(SkDoubleToScalar(distance), 281a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkDoubleToScalar(distance + dlen), 282a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel dst); 283a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } else { 284a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel meas.getSegment(SkDoubleToScalar(distance), 285a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkDoubleToScalar(distance + dlen), 286a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel dst, true); 287a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 288a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 289a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel distance += dlen; 290a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 291a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // clear this so we only respect it the first time around 292a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel skipFirstSegment = false; 293a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 294a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // wrap around our intervals array if necessary 295a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel index += 1; 296a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkASSERT(index <= count); 297a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (index == count) { 298a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel index = 0; 299a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 300a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 301a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // fetch our next dlen 302a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel dlen = intervals[index]; 303a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 304a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 305a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel // extend if we ended on a segment and we need to join up with the (skipped) initial segment 306a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (meas.isClosed() && is_even(initialDashIndex) && 307a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel initialDashLength > 0) { 308a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel meas.getSegment(0, initialDashLength, dst, !addedSegment); 309a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel ++segCount; 310a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 311a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } while (meas.nextContour()); 312a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 313a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel if (segCount > 1) { 314a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel dst->setConvexity(SkPath::kConcave_Convexity); 315a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel } 316a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 317a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel return true; 318a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel} 319a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel 320a22ea1882391cc5c84136060636d5c952c1f34b3egdanielbool SkDashPath::FilterDashPath(SkPath* dst, const SkPath& src, SkStrokeRec* rec, 321a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel const SkRect* cullRect, const SkPathEffect::DashInfo& info) { 322a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkScalar initialDashLength = 0; 323a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel int32_t initialDashIndex = 0; 324a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel SkScalar intervalLength = 0; 325a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel CalcDashParameters(info.fPhase, info.fIntervals, info.fCount, 326a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel &initialDashLength, &initialDashIndex, &intervalLength); 327a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel return FilterDashPath(dst, src, rec, cullRect, info.fIntervals, info.fCount, initialDashLength, 328a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel initialDashIndex, intervalLength); 329a22ea1882391cc5c84136060636d5c952c1f34b3egdaniel} 330