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