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