1 2 /* 3 * Copyright 2006 The Android Open Source Project 4 * 5 * Use of this source code is governed by a BSD-style license that can be 6 * found in the LICENSE file. 7 */ 8 9 10 #include "SkDashPathEffect.h" 11 #include "SkFlattenableBuffers.h" 12 #include "SkPathMeasure.h" 13 14 static inline int is_even(int x) { 15 return (~x) << 31; 16 } 17 18 static SkScalar FindFirstInterval(const SkScalar intervals[], SkScalar phase, 19 int32_t* index, int count) { 20 for (int i = 0; i < count; ++i) { 21 if (phase > intervals[i]) { 22 phase -= intervals[i]; 23 } else { 24 *index = i; 25 return intervals[i] - 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 SkDashPathEffect::SkDashPathEffect(const SkScalar intervals[], int count, 37 SkScalar phase, bool scaleToFit) 38 : fScaleToFit(scaleToFit) { 39 SkASSERT(intervals); 40 SkASSERT(count > 1 && SkAlign2(count) == count); 41 42 fIntervals = (SkScalar*)sk_malloc_throw(sizeof(SkScalar) * count); 43 fCount = count; 44 45 SkScalar len = 0; 46 for (int i = 0; i < count; i++) { 47 SkASSERT(intervals[i] >= 0); 48 fIntervals[i] = intervals[i]; 49 len += intervals[i]; 50 } 51 fIntervalLength = len; 52 53 // watch out for values that might make us go out of bounds 54 if ((len > 0) && SkScalarIsFinite(phase) && SkScalarIsFinite(len)) { 55 56 // Adjust phase to be between 0 and len, "flipping" phase if negative. 57 // e.g., if len is 100, then phase of -20 (or -120) is equivalent to 80 58 if (phase < 0) { 59 phase = -phase; 60 if (phase > len) { 61 phase = SkScalarMod(phase, len); 62 } 63 phase = len - phase; 64 65 // Due to finite precision, it's possible that phase == len, 66 // even after the subtract (if len >>> phase), so fix that here. 67 // This fixes http://crbug.com/124652 . 68 SkASSERT(phase <= len); 69 if (phase == len) { 70 phase = 0; 71 } 72 } else if (phase >= len) { 73 phase = SkScalarMod(phase, len); 74 } 75 SkASSERT(phase >= 0 && phase < len); 76 77 fInitialDashLength = FindFirstInterval(intervals, phase, 78 &fInitialDashIndex, count); 79 80 SkASSERT(fInitialDashLength >= 0); 81 SkASSERT(fInitialDashIndex >= 0 && fInitialDashIndex < fCount); 82 } else { 83 fInitialDashLength = -1; // signal bad dash intervals 84 } 85 } 86 87 SkDashPathEffect::~SkDashPathEffect() { 88 sk_free(fIntervals); 89 } 90 91 static void outset_for_stroke(SkRect* rect, const SkStrokeRec& rec) { 92 SkScalar radius = SkScalarHalf(rec.getWidth()); 93 if (0 == radius) { 94 radius = SK_Scalar1; // hairlines 95 } 96 if (SkPaint::kMiter_Join == rec.getJoin()) { 97 radius = SkScalarMul(radius, rec.getMiter()); 98 } 99 rect->outset(radius, radius); 100 } 101 102 // Only handles lines for now. If returns true, dstPath is the new (smaller) 103 // path. If returns false, then dstPath parameter is ignored. 104 static bool cull_path(const SkPath& srcPath, const SkStrokeRec& rec, 105 const SkRect* cullRect, SkScalar intervalLength, 106 SkPath* dstPath) { 107 if (NULL == cullRect) { 108 return false; 109 } 110 111 SkPoint pts[2]; 112 if (!srcPath.isLine(pts)) { 113 return false; 114 } 115 116 SkRect bounds = *cullRect; 117 outset_for_stroke(&bounds, rec); 118 119 SkScalar dx = pts[1].x() - pts[0].x(); 120 SkScalar dy = pts[1].y() - pts[0].y(); 121 122 // just do horizontal lines for now (lazy) 123 if (dy) { 124 return false; 125 } 126 127 SkScalar minX = pts[0].fX; 128 SkScalar maxX = pts[1].fX; 129 130 if (maxX < bounds.fLeft || minX > bounds.fRight) { 131 return false; 132 } 133 134 if (dx < 0) { 135 SkTSwap(minX, maxX); 136 } 137 138 // Now we actually perform the chop, removing the excess to the left and 139 // right of the bounds (keeping our new line "in phase" with the dash, 140 // hence the (mod intervalLength). 141 142 if (minX < bounds.fLeft) { 143 minX = bounds.fLeft - SkScalarMod(bounds.fLeft - minX, 144 intervalLength); 145 } 146 if (maxX > bounds.fRight) { 147 maxX = bounds.fRight + SkScalarMod(maxX - bounds.fRight, 148 intervalLength); 149 } 150 151 SkASSERT(maxX >= minX); 152 if (dx < 0) { 153 SkTSwap(minX, maxX); 154 } 155 pts[0].fX = minX; 156 pts[1].fX = maxX; 157 158 dstPath->moveTo(pts[0]); 159 dstPath->lineTo(pts[1]); 160 return true; 161 } 162 163 class SpecialLineRec { 164 public: 165 bool init(const SkPath& src, SkPath* dst, SkStrokeRec* rec, 166 int intervalCount, SkScalar intervalLength) { 167 if (rec->isHairlineStyle() || !src.isLine(fPts)) { 168 return false; 169 } 170 171 // can relax this in the future, if we handle square and round caps 172 if (SkPaint::kButt_Cap != rec->getCap()) { 173 return false; 174 } 175 176 SkScalar pathLength = SkPoint::Distance(fPts[0], fPts[1]); 177 178 fTangent = fPts[1] - fPts[0]; 179 if (fTangent.isZero()) { 180 return false; 181 } 182 183 fPathLength = pathLength; 184 fTangent.scale(SkScalarInvert(pathLength)); 185 fTangent.rotateCCW(&fNormal); 186 fNormal.scale(SkScalarHalf(rec->getWidth())); 187 188 // now estimate how many quads will be added to the path 189 // resulting segments = pathLen * intervalCount / intervalLen 190 // resulting points = 4 * segments 191 192 SkScalar ptCount = SkScalarMulDiv(pathLength, 193 SkIntToScalar(intervalCount), 194 intervalLength); 195 int n = SkScalarCeilToInt(ptCount) << 2; 196 dst->incReserve(n); 197 198 // we will take care of the stroking 199 rec->setFillStyle(); 200 return true; 201 } 202 203 void addSegment(SkScalar d0, SkScalar d1, SkPath* path) const { 204 SkASSERT(d0 < fPathLength); 205 // clamp the segment to our length 206 if (d1 > fPathLength) { 207 d1 = fPathLength; 208 } 209 210 SkScalar x0 = fPts[0].fX + SkScalarMul(fTangent.fX, d0); 211 SkScalar x1 = fPts[0].fX + SkScalarMul(fTangent.fX, d1); 212 SkScalar y0 = fPts[0].fY + SkScalarMul(fTangent.fY, d0); 213 SkScalar y1 = fPts[0].fY + SkScalarMul(fTangent.fY, d1); 214 215 SkPoint pts[4]; 216 pts[0].set(x0 + fNormal.fX, y0 + fNormal.fY); // moveTo 217 pts[1].set(x1 + fNormal.fX, y1 + fNormal.fY); // lineTo 218 pts[2].set(x1 - fNormal.fX, y1 - fNormal.fY); // lineTo 219 pts[3].set(x0 - fNormal.fX, y0 - fNormal.fY); // lineTo 220 221 path->addPoly(pts, SK_ARRAY_COUNT(pts), false); 222 } 223 224 private: 225 SkPoint fPts[2]; 226 SkVector fTangent; 227 SkVector fNormal; 228 SkScalar fPathLength; 229 }; 230 231 bool SkDashPathEffect::filterPath(SkPath* dst, const SkPath& src, 232 SkStrokeRec* rec, const SkRect* cullRect) const { 233 234 #ifdef SK_IGNORE_LARGE_DASH_OPT 235 cullRect = NULL; 236 #endif 237 238 // we do nothing if the src wants to be filled, or if our dashlength is 0 239 if (rec->isFillStyle() || fInitialDashLength < 0) { 240 return false; 241 } 242 243 const SkScalar* intervals = fIntervals; 244 SkScalar dashCount = 0; 245 246 SkPath cullPathStorage; 247 const SkPath* srcPtr = &src; 248 if (cull_path(src, *rec, cullRect, fIntervalLength, &cullPathStorage)) { 249 srcPtr = &cullPathStorage; 250 } 251 252 SpecialLineRec lineRec; 253 bool specialLine = lineRec.init(*srcPtr, dst, rec, fCount >> 1, fIntervalLength); 254 255 SkPathMeasure meas(*srcPtr, false); 256 257 do { 258 bool skipFirstSegment = meas.isClosed(); 259 bool addedSegment = false; 260 SkScalar length = meas.getLength(); 261 int index = fInitialDashIndex; 262 SkScalar scale = SK_Scalar1; 263 264 // Since the path length / dash length ratio may be arbitrarily large, we can exert 265 // significant memory pressure while attempting to build the filtered path. To avoid this, 266 // we simply give up dashing beyond a certain threshold. 267 // 268 // The original bug report (http://crbug.com/165432) is based on a path yielding more than 269 // 90 million dash segments and crashing the memory allocator. A limit of 1 million 270 // segments seems reasonable: at 2 verbs per segment * 9 bytes per verb, this caps the 271 // maximum dash memory overhead at roughly 17MB per path. 272 static const SkScalar kMaxDashCount = 1000000; 273 dashCount += length * (fCount >> 1) / fIntervalLength; 274 if (dashCount > kMaxDashCount) { 275 dst->reset(); 276 return false; 277 } 278 279 if (fScaleToFit) { 280 if (fIntervalLength >= length) { 281 scale = SkScalarDiv(length, fIntervalLength); 282 } else { 283 SkScalar div = SkScalarDiv(length, fIntervalLength); 284 int n = SkScalarFloor(div); 285 scale = SkScalarDiv(length, n * fIntervalLength); 286 } 287 } 288 289 // Using double precision to avoid looping indefinitely due to single precision rounding 290 // (for extreme path_length/dash_length ratios). See test_infinite_dash() unittest. 291 double distance = 0; 292 double dlen = SkScalarMul(fInitialDashLength, scale); 293 294 while (distance < length) { 295 SkASSERT(dlen >= 0); 296 addedSegment = false; 297 if (is_even(index) && dlen > 0 && !skipFirstSegment) { 298 addedSegment = true; 299 300 if (specialLine) { 301 lineRec.addSegment(SkDoubleToScalar(distance), 302 SkDoubleToScalar(distance + dlen), 303 dst); 304 } else { 305 meas.getSegment(SkDoubleToScalar(distance), 306 SkDoubleToScalar(distance + dlen), 307 dst, true); 308 } 309 } 310 distance += dlen; 311 312 // clear this so we only respect it the first time around 313 skipFirstSegment = false; 314 315 // wrap around our intervals array if necessary 316 index += 1; 317 SkASSERT(index <= fCount); 318 if (index == fCount) { 319 index = 0; 320 } 321 322 // fetch our next dlen 323 dlen = SkScalarMul(intervals[index], scale); 324 } 325 326 // extend if we ended on a segment and we need to join up with the (skipped) initial segment 327 if (meas.isClosed() && is_even(fInitialDashIndex) && 328 fInitialDashLength > 0) { 329 meas.getSegment(0, SkScalarMul(fInitialDashLength, scale), dst, !addedSegment); 330 } 331 } while (meas.nextContour()); 332 333 return true; 334 } 335 336 // Currently asPoints is more restrictive then it needs to be. In the future 337 // we need to: 338 // allow kRound_Cap capping (could allow rotations in the matrix with this) 339 // allow paths to be returned 340 bool SkDashPathEffect::asPoints(PointData* results, 341 const SkPath& src, 342 const SkStrokeRec& rec, 343 const SkMatrix& matrix, 344 const SkRect* cullRect) const { 345 // width < 0 -> fill && width == 0 -> hairline so requiring width > 0 rules both out 346 if (fInitialDashLength < 0 || 0 >= rec.getWidth()) { 347 return false; 348 } 349 350 // TODO: this next test could be eased up. We could allow any number of 351 // intervals as long as all the ons match and all the offs match. 352 // Additionally, they do not necessarily need to be integers. 353 // We cannot allow arbitrary intervals since we want the returned points 354 // to be uniformly sized. 355 if (fCount != 2 || 356 !SkScalarNearlyEqual(fIntervals[0], fIntervals[1]) || 357 !SkScalarIsInt(fIntervals[0]) || 358 !SkScalarIsInt(fIntervals[1])) { 359 return false; 360 } 361 362 // TODO: this next test could be eased up. The rescaling should not impact 363 // the equality of the ons & offs. However, we would need to remove the 364 // integer intervals restriction first 365 if (fScaleToFit) { 366 return false; 367 } 368 369 SkPoint pts[2]; 370 371 if (!src.isLine(pts)) { 372 return false; 373 } 374 375 // TODO: this test could be eased up to allow circles 376 if (SkPaint::kButt_Cap != rec.getCap()) { 377 return false; 378 } 379 380 // TODO: this test could be eased up for circles. Rotations could be allowed. 381 if (!matrix.rectStaysRect()) { 382 return false; 383 } 384 385 SkScalar length = SkPoint::Distance(pts[1], pts[0]); 386 387 SkVector tangent = pts[1] - pts[0]; 388 if (tangent.isZero()) { 389 return false; 390 } 391 392 tangent.scale(SkScalarInvert(length)); 393 394 // TODO: make this test for horizontal & vertical lines more robust 395 bool isXAxis = true; 396 if (SK_Scalar1 == tangent.fX || -SK_Scalar1 == tangent.fX) { 397 results->fSize.set(SkScalarHalf(fIntervals[0]), SkScalarHalf(rec.getWidth())); 398 } else if (SK_Scalar1 == tangent.fY || -SK_Scalar1 == tangent.fY) { 399 results->fSize.set(SkScalarHalf(rec.getWidth()), SkScalarHalf(fIntervals[0])); 400 isXAxis = false; 401 } else if (SkPaint::kRound_Cap != rec.getCap()) { 402 // Angled lines don't have axis-aligned boxes. 403 return false; 404 } 405 406 if (NULL != results) { 407 results->fFlags = 0; 408 SkScalar clampedInitialDashLength = SkMinScalar(length, fInitialDashLength); 409 410 if (SkPaint::kRound_Cap == rec.getCap()) { 411 results->fFlags |= PointData::kCircles_PointFlag; 412 } 413 414 results->fNumPoints = 0; 415 SkScalar len2 = length; 416 if (clampedInitialDashLength > 0 || 0 == fInitialDashIndex) { 417 SkASSERT(len2 >= clampedInitialDashLength); 418 if (0 == fInitialDashIndex) { 419 if (clampedInitialDashLength > 0) { 420 if (clampedInitialDashLength >= fIntervals[0]) { 421 ++results->fNumPoints; // partial first dash 422 } 423 len2 -= clampedInitialDashLength; 424 } 425 len2 -= fIntervals[1]; // also skip first space 426 if (len2 < 0) { 427 len2 = 0; 428 } 429 } else { 430 len2 -= clampedInitialDashLength; // skip initial partial empty 431 } 432 } 433 int numMidPoints = SkScalarFloorToInt(SkScalarDiv(len2, fIntervalLength)); 434 results->fNumPoints += numMidPoints; 435 len2 -= numMidPoints * fIntervalLength; 436 bool partialLast = false; 437 if (len2 > 0) { 438 if (len2 < fIntervals[0]) { 439 partialLast = true; 440 } else { 441 ++numMidPoints; 442 ++results->fNumPoints; 443 } 444 } 445 446 results->fPoints = new SkPoint[results->fNumPoints]; 447 448 SkScalar distance = 0; 449 int curPt = 0; 450 451 if (clampedInitialDashLength > 0 || 0 == fInitialDashIndex) { 452 SkASSERT(clampedInitialDashLength <= length); 453 454 if (0 == fInitialDashIndex) { 455 if (clampedInitialDashLength > 0) { 456 // partial first block 457 SkASSERT(SkPaint::kRound_Cap != rec.getCap()); // can't handle partial circles 458 SkScalar x = pts[0].fX + SkScalarMul(tangent.fX, SkScalarHalf(clampedInitialDashLength)); 459 SkScalar y = pts[0].fY + SkScalarMul(tangent.fY, SkScalarHalf(clampedInitialDashLength)); 460 SkScalar halfWidth, halfHeight; 461 if (isXAxis) { 462 halfWidth = SkScalarHalf(clampedInitialDashLength); 463 halfHeight = SkScalarHalf(rec.getWidth()); 464 } else { 465 halfWidth = SkScalarHalf(rec.getWidth()); 466 halfHeight = SkScalarHalf(clampedInitialDashLength); 467 } 468 if (clampedInitialDashLength < fIntervals[0]) { 469 // This one will not be like the others 470 results->fFirst.addRect(x - halfWidth, y - halfHeight, 471 x + halfWidth, y + halfHeight); 472 } else { 473 SkASSERT(curPt < results->fNumPoints); 474 results->fPoints[curPt].set(x, y); 475 ++curPt; 476 } 477 478 distance += clampedInitialDashLength; 479 } 480 481 distance += fIntervals[1]; // skip over the next blank block too 482 } else { 483 distance += clampedInitialDashLength; 484 } 485 } 486 487 if (0 != numMidPoints) { 488 distance += SkScalarHalf(fIntervals[0]); 489 490 for (int i = 0; i < numMidPoints; ++i) { 491 SkScalar x = pts[0].fX + SkScalarMul(tangent.fX, distance); 492 SkScalar y = pts[0].fY + SkScalarMul(tangent.fY, distance); 493 494 SkASSERT(curPt < results->fNumPoints); 495 results->fPoints[curPt].set(x, y); 496 ++curPt; 497 498 distance += fIntervalLength; 499 } 500 501 distance -= SkScalarHalf(fIntervals[0]); 502 } 503 504 if (partialLast) { 505 // partial final block 506 SkASSERT(SkPaint::kRound_Cap != rec.getCap()); // can't handle partial circles 507 SkScalar temp = length - distance; 508 SkASSERT(temp < fIntervals[0]); 509 SkScalar x = pts[0].fX + SkScalarMul(tangent.fX, distance + SkScalarHalf(temp)); 510 SkScalar y = pts[0].fY + SkScalarMul(tangent.fY, distance + SkScalarHalf(temp)); 511 SkScalar halfWidth, halfHeight; 512 if (isXAxis) { 513 halfWidth = SkScalarHalf(temp); 514 halfHeight = SkScalarHalf(rec.getWidth()); 515 } else { 516 halfWidth = SkScalarHalf(rec.getWidth()); 517 halfHeight = SkScalarHalf(temp); 518 } 519 results->fLast.addRect(x - halfWidth, y - halfHeight, 520 x + halfWidth, y + halfHeight); 521 } 522 523 SkASSERT(curPt == results->fNumPoints); 524 } 525 526 return true; 527 } 528 529 SkFlattenable::Factory SkDashPathEffect::getFactory() { 530 return fInitialDashLength < 0 ? NULL : CreateProc; 531 } 532 533 void SkDashPathEffect::flatten(SkFlattenableWriteBuffer& buffer) const { 534 SkASSERT(fInitialDashLength >= 0); 535 536 this->INHERITED::flatten(buffer); 537 buffer.writeInt(fInitialDashIndex); 538 buffer.writeScalar(fInitialDashLength); 539 buffer.writeScalar(fIntervalLength); 540 buffer.writeBool(fScaleToFit); 541 buffer.writeScalarArray(fIntervals, fCount); 542 } 543 544 SkFlattenable* SkDashPathEffect::CreateProc(SkFlattenableReadBuffer& buffer) { 545 return SkNEW_ARGS(SkDashPathEffect, (buffer)); 546 } 547 548 SkDashPathEffect::SkDashPathEffect(SkFlattenableReadBuffer& buffer) : INHERITED(buffer) { 549 fInitialDashIndex = buffer.readInt(); 550 fInitialDashLength = buffer.readScalar(); 551 fIntervalLength = buffer.readScalar(); 552 fScaleToFit = buffer.readBool(); 553 554 fCount = buffer.getArrayCount(); 555 fIntervals = (SkScalar*)sk_malloc_throw(sizeof(SkScalar) * fCount); 556 buffer.readScalarArray(fIntervals); 557 } 558