egdaniel | a22ea18 | 2014-06-11 06:51:51 -0700 | [diff] [blame] | 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 | |
egdaniel | a22ea18 | 2014-06-11 06:51:51 -0700 | [diff] [blame] | 118 | if (dx < 0) { |
| 119 | SkTSwap(minX, maxX); |
| 120 | } |
| 121 | |
robertphillips | 9f2251c | 2014-11-04 13:33:50 -0800 | [diff] [blame^] | 122 | SkASSERT(minX < maxX); |
| 123 | if (maxX < bounds.fLeft || minX > bounds.fRight) { |
| 124 | return false; |
| 125 | } |
| 126 | |
egdaniel | a22ea18 | 2014-06-11 06:51:51 -0700 | [diff] [blame] | 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 | } |