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 "SkPointPriv.h" 11 #include "SkStrokeRec.h" 12 13 static inline int is_even(int x) { 14 return !(x & 1); 15 } 16 17 static SkScalar find_first_interval(const SkScalar intervals[], SkScalar phase, 18 int32_t* index, int count) { 19 for (int i = 0; i < count; ++i) { 20 SkScalar gap = intervals[i]; 21 if (phase > gap || (phase == gap && gap)) { 22 phase -= gap; 23 } else { 24 *index = i; 25 return gap - phase; 26 } 27 } 28 // If we get here, phase "appears" to be larger than our length. This 29 // shouldn't happen with perfect precision, but we can accumulate errors 30 // during the initial length computation (rounding can make our sum be too 31 // big or too small. In that event, we just have to eat the error here. 32 *index = 0; 33 return intervals[0]; 34 } 35 36 void SkDashPath::CalcDashParameters(SkScalar phase, const SkScalar intervals[], int32_t count, 37 SkScalar* initialDashLength, int32_t* initialDashIndex, 38 SkScalar* intervalLength, SkScalar* adjustedPhase) { 39 SkScalar len = 0; 40 for (int i = 0; i < count; i++) { 41 len += intervals[i]; 42 } 43 *intervalLength = len; 44 // Adjust phase to be between 0 and len, "flipping" phase if negative. 45 // e.g., if len is 100, then phase of -20 (or -120) is equivalent to 80 46 if (adjustedPhase) { 47 if (phase < 0) { 48 phase = -phase; 49 if (phase > len) { 50 phase = SkScalarMod(phase, len); 51 } 52 phase = len - phase; 53 54 // Due to finite precision, it's possible that phase == len, 55 // even after the subtract (if len >>> phase), so fix that here. 56 // This fixes http://crbug.com/124652 . 57 SkASSERT(phase <= len); 58 if (phase == len) { 59 phase = 0; 60 } 61 } else if (phase >= len) { 62 phase = SkScalarMod(phase, len); 63 } 64 *adjustedPhase = phase; 65 } 66 SkASSERT(phase >= 0 && phase < len); 67 68 *initialDashLength = find_first_interval(intervals, phase, 69 initialDashIndex, count); 70 71 SkASSERT(*initialDashLength >= 0); 72 SkASSERT(*initialDashIndex >= 0 && *initialDashIndex < count); 73 } 74 75 static void outset_for_stroke(SkRect* rect, const SkStrokeRec& rec) { 76 SkScalar radius = SkScalarHalf(rec.getWidth()); 77 if (0 == radius) { 78 radius = SK_Scalar1; // hairlines 79 } 80 if (SkPaint::kMiter_Join == rec.getJoin()) { 81 radius *= rec.getMiter(); 82 } 83 rect->outset(radius, radius); 84 } 85 86 #ifndef SK_SUPPORT_LEGACY_DASH_CULL_PATH 87 // If line is zero-length, bump out the end by a tiny amount 88 // to draw endcaps. The bump factor is sized so that 89 // SkPoint::Distance() computes a non-zero length. 90 // Offsets SK_ScalarNearlyZero or smaller create empty paths when Iter measures length. 91 // Large values are scaled by SK_ScalarNearlyZero so significant bits change. 92 static void adjust_zero_length_line(SkPoint pts[2]) { 93 SkASSERT(pts[0] == pts[1]); 94 pts[1].fX += SkTMax(1.001f, pts[1].fX) * SK_ScalarNearlyZero; 95 } 96 97 static bool clip_line(SkPoint pts[2], const SkRect& bounds, SkScalar intervalLength, 98 SkScalar priorPhase) { 99 SkVector dxy = pts[1] - pts[0]; 100 101 // only horizontal or vertical lines 102 if (dxy.fX && dxy.fY) { 103 return false; 104 } 105 int xyOffset = SkToBool(dxy.fY); // 0 to adjust horizontal, 1 to adjust vertical 106 107 SkScalar minXY = (&pts[0].fX)[xyOffset]; 108 SkScalar maxXY = (&pts[1].fX)[xyOffset]; 109 bool swapped = maxXY < minXY; 110 if (swapped) { 111 SkTSwap(minXY, maxXY); 112 } 113 114 SkASSERT(minXY <= maxXY); 115 SkScalar leftTop = (&bounds.fLeft)[xyOffset]; 116 SkScalar rightBottom = (&bounds.fRight)[xyOffset]; 117 if (maxXY < leftTop || minXY > rightBottom) { 118 return false; 119 } 120 121 // Now we actually perform the chop, removing the excess to the left/top and 122 // right/bottom of the bounds (keeping our new line "in phase" with the dash, 123 // hence the (mod intervalLength). 124 125 if (minXY < leftTop) { 126 minXY = leftTop - SkScalarMod(leftTop - minXY, intervalLength); 127 if (!swapped) { 128 minXY -= priorPhase; // for rectangles, adjust by prior phase 129 } 130 } 131 if (maxXY > rightBottom) { 132 maxXY = rightBottom + SkScalarMod(maxXY - rightBottom, intervalLength); 133 if (swapped) { 134 maxXY += priorPhase; // for rectangles, adjust by prior phase 135 } 136 } 137 138 SkASSERT(maxXY >= minXY); 139 if (swapped) { 140 SkTSwap(minXY, maxXY); 141 } 142 (&pts[0].fX)[xyOffset] = minXY; 143 (&pts[1].fX)[xyOffset] = maxXY; 144 145 if (minXY == maxXY) { 146 adjust_zero_length_line(pts); 147 } 148 return true; 149 } 150 151 static bool contains_inclusive(const SkRect& rect, const SkPoint& pt) { 152 return rect.fLeft <= pt.fX && pt.fX <= rect.fRight && 153 rect.fTop <= pt.fY && pt.fY <= rect.fBottom; 154 } 155 156 // Returns true is b is between a and c, that is: a <= b <= c, or a >= b >= c. 157 // Can perform this test with one branch by observing that, relative to b, 158 // the condition is true only if one side is positive and one side is negative. 159 // If the numbers are very small, the optimization may return the wrong result 160 // because the multiply may generate a zero where the simple compare does not. 161 // For this reason the assert does not fire when all three numbers are near zero. 162 static bool between(SkScalar a, SkScalar b, SkScalar c) { 163 SkASSERT(((a <= b && b <= c) || (a >= b && b >= c)) == ((a - b) * (c - b) <= 0) 164 || (SkScalarNearlyZero(a) && SkScalarNearlyZero(b) && SkScalarNearlyZero(c))); 165 return (a - b) * (c - b) <= 0; 166 } 167 #endif 168 169 // Only handles lines for now. If returns true, dstPath is the new (smaller) 170 // path. If returns false, then dstPath parameter is ignored. 171 static bool cull_path(const SkPath& srcPath, const SkStrokeRec& rec, 172 const SkRect* cullRect, SkScalar intervalLength, 173 SkPath* dstPath) { 174 #ifdef SK_SUPPORT_LEGACY_DASH_CULL_PATH 175 if (nullptr == cullRect) { 176 return false; 177 } 178 179 SkPoint pts[2]; 180 if (!srcPath.isLine(pts)) { 181 return false; 182 } 183 184 SkRect bounds = *cullRect; 185 outset_for_stroke(&bounds, rec); 186 187 SkScalar dx = pts[1].x() - pts[0].x(); 188 SkScalar dy = pts[1].y() - pts[0].y(); 189 190 // just do horizontal lines for now (lazy) 191 if (dy) { 192 return false; 193 } 194 195 SkScalar minX = pts[0].fX; 196 SkScalar maxX = pts[1].fX; 197 198 if (dx < 0) { 199 SkTSwap(minX, maxX); 200 } 201 202 SkASSERT(minX <= maxX); 203 if (maxX < bounds.fLeft || minX > bounds.fRight) { 204 return false; 205 } 206 207 // Now we actually perform the chop, removing the excess to the left and 208 // right of the bounds (keeping our new line "in phase" with the dash, 209 // hence the (mod intervalLength). 210 211 if (minX < bounds.fLeft) { 212 minX = bounds.fLeft - SkScalarMod(bounds.fLeft - minX, 213 intervalLength); 214 } 215 if (maxX > bounds.fRight) { 216 maxX = bounds.fRight + SkScalarMod(maxX - bounds.fRight, 217 intervalLength); 218 } 219 220 SkASSERT(maxX >= minX); 221 if (dx < 0) { 222 SkTSwap(minX, maxX); 223 } 224 pts[0].fX = minX; 225 pts[1].fX = maxX; 226 227 // If line is zero-length, bump out the end by a tiny amount 228 // to draw endcaps. The bump factor is sized so that 229 // SkPoint::Distance() computes a non-zero length. 230 if (minX == maxX) { 231 pts[1].fX += maxX * FLT_EPSILON * 32; // 16 instead of 32 does not draw; length stays zero 232 } 233 #else // !SK_SUPPORT_LEGACY_DASH_CULL_PATH 234 SkPoint pts[4]; 235 if (nullptr == cullRect) { 236 if (srcPath.isLine(pts) && pts[0] == pts[1]) { 237 adjust_zero_length_line(pts); 238 } else { 239 return false; 240 } 241 } else { 242 SkRect bounds; 243 bool isLine = srcPath.isLine(pts); 244 bool isRect = !isLine && srcPath.isRect(nullptr); 245 if (!isLine && !isRect) { 246 return false; 247 } 248 bounds = *cullRect; 249 outset_for_stroke(&bounds, rec); 250 if (isRect) { 251 // break rect into four lines, and call each one separately 252 SkPath::Iter iter(srcPath, false); 253 SkAssertResult(SkPath::kMove_Verb == iter.next(pts)); 254 SkScalar priorLength = 0; 255 while (SkPath::kLine_Verb == iter.next(pts)) { 256 SkVector v = pts[1] - pts[0]; 257 // if line is entirely outside clip rect, skip it 258 if (v.fX ? between(bounds.fTop, pts[0].fY, bounds.fBottom) : 259 between(bounds.fLeft, pts[0].fX, bounds.fRight)) { 260 bool skipMoveTo = contains_inclusive(bounds, pts[0]); 261 if (clip_line(pts, bounds, intervalLength, 262 SkScalarMod(priorLength, intervalLength))) { 263 if (0 == priorLength || !skipMoveTo) { 264 dstPath->moveTo(pts[0]); 265 } 266 dstPath->lineTo(pts[1]); 267 } 268 } 269 // keep track of all prior lengths to set phase of next line 270 priorLength += SkScalarAbs(v.fX ? v.fX : v.fY); 271 } 272 return !dstPath->isEmpty(); 273 } 274 SkASSERT(isLine); 275 if (!clip_line(pts, bounds, intervalLength, 0)) { 276 return false; 277 } 278 } 279 #endif 280 dstPath->moveTo(pts[0]); 281 dstPath->lineTo(pts[1]); 282 return true; 283 } 284 285 class SpecialLineRec { 286 public: 287 bool init(const SkPath& src, SkPath* dst, SkStrokeRec* rec, 288 int intervalCount, SkScalar intervalLength) { 289 if (rec->isHairlineStyle() || !src.isLine(fPts)) { 290 return false; 291 } 292 293 // can relax this in the future, if we handle square and round caps 294 if (SkPaint::kButt_Cap != rec->getCap()) { 295 return false; 296 } 297 298 SkScalar pathLength = SkPoint::Distance(fPts[0], fPts[1]); 299 300 fTangent = fPts[1] - fPts[0]; 301 if (fTangent.isZero()) { 302 return false; 303 } 304 305 fPathLength = pathLength; 306 fTangent.scale(SkScalarInvert(pathLength)); 307 SkPointPriv::RotateCCW(fTangent, &fNormal); 308 fNormal.scale(SkScalarHalf(rec->getWidth())); 309 310 // now estimate how many quads will be added to the path 311 // resulting segments = pathLen * intervalCount / intervalLen 312 // resulting points = 4 * segments 313 314 SkScalar ptCount = pathLength * intervalCount / (float)intervalLength; 315 ptCount = SkTMin(ptCount, SkDashPath::kMaxDashCount); 316 int n = SkScalarCeilToInt(ptCount) << 2; 317 dst->incReserve(n); 318 319 // we will take care of the stroking 320 rec->setFillStyle(); 321 return true; 322 } 323 324 void addSegment(SkScalar d0, SkScalar d1, SkPath* path) const { 325 SkASSERT(d0 <= fPathLength); 326 // clamp the segment to our length 327 if (d1 > fPathLength) { 328 d1 = fPathLength; 329 } 330 331 SkScalar x0 = fPts[0].fX + fTangent.fX * d0; 332 SkScalar x1 = fPts[0].fX + fTangent.fX * d1; 333 SkScalar y0 = fPts[0].fY + fTangent.fY * d0; 334 SkScalar y1 = fPts[0].fY + fTangent.fY * d1; 335 336 SkPoint pts[4]; 337 pts[0].set(x0 + fNormal.fX, y0 + fNormal.fY); // moveTo 338 pts[1].set(x1 + fNormal.fX, y1 + fNormal.fY); // lineTo 339 pts[2].set(x1 - fNormal.fX, y1 - fNormal.fY); // lineTo 340 pts[3].set(x0 - fNormal.fX, y0 - fNormal.fY); // lineTo 341 342 path->addPoly(pts, SK_ARRAY_COUNT(pts), false); 343 } 344 345 private: 346 SkPoint fPts[2]; 347 SkVector fTangent; 348 SkVector fNormal; 349 SkScalar fPathLength; 350 }; 351 352 353 bool SkDashPath::InternalFilter(SkPath* dst, const SkPath& src, SkStrokeRec* rec, 354 const SkRect* cullRect, const SkScalar aIntervals[], 355 int32_t count, SkScalar initialDashLength, int32_t initialDashIndex, 356 SkScalar intervalLength, 357 StrokeRecApplication strokeRecApplication) { 358 359 // we do nothing if the src wants to be filled 360 SkStrokeRec::Style style = rec->getStyle(); 361 if (SkStrokeRec::kFill_Style == style || SkStrokeRec::kStrokeAndFill_Style == style) { 362 return false; 363 } 364 365 const SkScalar* intervals = aIntervals; 366 SkScalar dashCount = 0; 367 int segCount = 0; 368 369 SkPath cullPathStorage; 370 const SkPath* srcPtr = &src; 371 if (cull_path(src, *rec, cullRect, intervalLength, &cullPathStorage)) { 372 // if rect is closed, starts in a dash, and ends in a dash, add the initial join 373 // potentially a better fix is described here: bug.skia.org/7445 374 if (src.isRect(nullptr) && src.isLastContourClosed() && is_even(initialDashIndex)) { 375 SkScalar pathLength = SkPathMeasure(src, false, rec->getResScale()).getLength(); 376 SkScalar endPhase = SkScalarMod(pathLength + initialDashLength, intervalLength); 377 int index = 0; 378 while (endPhase > intervals[index]) { 379 endPhase -= intervals[index++]; 380 SkASSERT(index <= count); 381 } 382 // if dash ends inside "on", or ends at beginning of "off" 383 if (is_even(index) == (endPhase > 0)) { 384 SkPoint midPoint = src.getPoint(0); 385 // get vector at end of rect 386 int last = src.countPoints() - 1; 387 while (midPoint == src.getPoint(last)) { 388 --last; 389 SkASSERT(last >= 0); 390 } 391 // get vector at start of rect 392 int next = 1; 393 while (midPoint == src.getPoint(next)) { 394 ++next; 395 SkASSERT(next < last); 396 } 397 SkVector v = midPoint - src.getPoint(last); 398 const SkScalar kTinyOffset = SK_ScalarNearlyZero; 399 // scale vector to make start of tiny right angle 400 v *= kTinyOffset; 401 cullPathStorage.moveTo(midPoint - v); 402 cullPathStorage.lineTo(midPoint); 403 v = midPoint - src.getPoint(next); 404 // scale vector to make end of tiny right angle 405 v *= kTinyOffset; 406 cullPathStorage.lineTo(midPoint - v); 407 } 408 } 409 srcPtr = &cullPathStorage; 410 } 411 412 SpecialLineRec lineRec; 413 bool specialLine = (StrokeRecApplication::kAllow == strokeRecApplication) && 414 lineRec.init(*srcPtr, dst, rec, count >> 1, intervalLength); 415 416 SkPathMeasure meas(*srcPtr, false, rec->getResScale()); 417 418 do { 419 bool skipFirstSegment = meas.isClosed(); 420 bool addedSegment = false; 421 SkScalar length = meas.getLength(); 422 int index = initialDashIndex; 423 424 // Since the path length / dash length ratio may be arbitrarily large, we can exert 425 // significant memory pressure while attempting to build the filtered path. To avoid this, 426 // we simply give up dashing beyond a certain threshold. 427 // 428 // The original bug report (http://crbug.com/165432) is based on a path yielding more than 429 // 90 million dash segments and crashing the memory allocator. A limit of 1 million 430 // segments seems reasonable: at 2 verbs per segment * 9 bytes per verb, this caps the 431 // maximum dash memory overhead at roughly 17MB per path. 432 dashCount += length * (count >> 1) / intervalLength; 433 if (dashCount > kMaxDashCount) { 434 dst->reset(); 435 return false; 436 } 437 438 // Using double precision to avoid looping indefinitely due to single precision rounding 439 // (for extreme path_length/dash_length ratios). See test_infinite_dash() unittest. 440 double distance = 0; 441 double dlen = initialDashLength; 442 443 while (distance < length) { 444 SkASSERT(dlen >= 0); 445 addedSegment = false; 446 if (is_even(index) && !skipFirstSegment) { 447 addedSegment = true; 448 ++segCount; 449 450 if (specialLine) { 451 lineRec.addSegment(SkDoubleToScalar(distance), 452 SkDoubleToScalar(distance + dlen), 453 dst); 454 } else { 455 meas.getSegment(SkDoubleToScalar(distance), 456 SkDoubleToScalar(distance + dlen), 457 dst, true); 458 } 459 } 460 distance += dlen; 461 462 // clear this so we only respect it the first time around 463 skipFirstSegment = false; 464 465 // wrap around our intervals array if necessary 466 index += 1; 467 SkASSERT(index <= count); 468 if (index == count) { 469 index = 0; 470 } 471 472 // fetch our next dlen 473 dlen = intervals[index]; 474 } 475 476 // extend if we ended on a segment and we need to join up with the (skipped) initial segment 477 if (meas.isClosed() && is_even(initialDashIndex) && 478 initialDashLength >= 0) { 479 meas.getSegment(0, initialDashLength, dst, !addedSegment); 480 ++segCount; 481 } 482 } while (meas.nextContour()); 483 484 if (segCount > 1) { 485 dst->setConvexity(SkPath::kConcave_Convexity); 486 } 487 488 return true; 489 } 490 491 bool SkDashPath::FilterDashPath(SkPath* dst, const SkPath& src, SkStrokeRec* rec, 492 const SkRect* cullRect, const SkPathEffect::DashInfo& info) { 493 if (!ValidDashPath(info.fPhase, info.fIntervals, info.fCount)) { 494 return false; 495 } 496 SkScalar initialDashLength = 0; 497 int32_t initialDashIndex = 0; 498 SkScalar intervalLength = 0; 499 CalcDashParameters(info.fPhase, info.fIntervals, info.fCount, 500 &initialDashLength, &initialDashIndex, &intervalLength); 501 return InternalFilter(dst, src, rec, cullRect, info.fIntervals, info.fCount, initialDashLength, 502 initialDashIndex, intervalLength); 503 } 504 505 bool SkDashPath::ValidDashPath(SkScalar phase, const SkScalar intervals[], int32_t count) { 506 if (count < 2 || !SkIsAlign2(count)) { 507 return false; 508 } 509 SkScalar length = 0; 510 for (int i = 0; i < count; i++) { 511 if (intervals[i] < 0) { 512 return false; 513 } 514 length += intervals[i]; 515 } 516 // watch out for values that might make us go out of bounds 517 return length > 0 && SkScalarIsFinite(phase) && SkScalarIsFinite(length); 518 } 519