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