| OLD | NEW |
|---|
| (Empty) |
| 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* initia
lDashIndex, | |
| 35 SkScalar* intervalLength, SkScalar* adjusted
Phase) { | |
| 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 (maxX < bounds.fLeft || minX > bounds.fRight) { | |
| 119 return false; | |
| 120 } | |
| 121 | |
| 122 if (dx < 0) { | |
| 123 SkTSwap(minX, maxX); | |
| 124 } | |
| 125 | |
| 126 // Now we actually perform the chop, removing the excess to the left and | |
| 127 // right of the bounds (keeping our new line "in phase" with the dash, | |
| 128 // hence the (mod intervalLength). | |
| 129 | |
| 130 if (minX < bounds.fLeft) { | |
| 131 minX = bounds.fLeft - SkScalarMod(bounds.fLeft - minX, | |
| 132 intervalLength); | |
| 133 } | |
| 134 if (maxX > bounds.fRight) { | |
| 135 maxX = bounds.fRight + SkScalarMod(maxX - bounds.fRight, | |
| 136 intervalLength); | |
| 137 } | |
| 138 | |
| 139 SkASSERT(maxX >= minX); | |
| 140 if (dx < 0) { | |
| 141 SkTSwap(minX, maxX); | |
| 142 } | |
| 143 pts[0].fX = minX; | |
| 144 pts[1].fX = maxX; | |
| 145 | |
| 146 dstPath->moveTo(pts[0]); | |
| 147 dstPath->lineTo(pts[1]); | |
| 148 return true; | |
| 149 } | |
| 150 | |
| 151 class SpecialLineRec { | |
| 152 public: | |
| 153 bool init(const SkPath& src, SkPath* dst, SkStrokeRec* rec, | |
| 154 int intervalCount, SkScalar intervalLength) { | |
| 155 if (rec->isHairlineStyle() || !src.isLine(fPts)) { | |
| 156 return false; | |
| 157 } | |
| 158 | |
| 159 // can relax this in the future, if we handle square and round caps | |
| 160 if (SkPaint::kButt_Cap != rec->getCap()) { | |
| 161 return false; | |
| 162 } | |
| 163 | |
| 164 SkScalar pathLength = SkPoint::Distance(fPts[0], fPts[1]); | |
| 165 | |
| 166 fTangent = fPts[1] - fPts[0]; | |
| 167 if (fTangent.isZero()) { | |
| 168 return false; | |
| 169 } | |
| 170 | |
| 171 fPathLength = pathLength; | |
| 172 fTangent.scale(SkScalarInvert(pathLength)); | |
| 173 fTangent.rotateCCW(&fNormal); | |
| 174 fNormal.scale(SkScalarHalf(rec->getWidth())); | |
| 175 | |
| 176 // now estimate how many quads will be added to the path | |
| 177 // resulting segments = pathLen * intervalCount / intervalLen | |
| 178 // resulting points = 4 * segments | |
| 179 | |
| 180 SkScalar ptCount = SkScalarMulDiv(pathLength, | |
| 181 SkIntToScalar(intervalCount), | |
| 182 intervalLength); | |
| 183 int n = SkScalarCeilToInt(ptCount) << 2; | |
| 184 dst->incReserve(n); | |
| 185 | |
| 186 // we will take care of the stroking | |
| 187 rec->setFillStyle(); | |
| 188 return true; | |
| 189 } | |
| 190 | |
| 191 void addSegment(SkScalar d0, SkScalar d1, SkPath* path) const { | |
| 192 SkASSERT(d0 < fPathLength); | |
| 193 // clamp the segment to our length | |
| 194 if (d1 > fPathLength) { | |
| 195 d1 = fPathLength; | |
| 196 } | |
| 197 | |
| 198 SkScalar x0 = fPts[0].fX + SkScalarMul(fTangent.fX, d0); | |
| 199 SkScalar x1 = fPts[0].fX + SkScalarMul(fTangent.fX, d1); | |
| 200 SkScalar y0 = fPts[0].fY + SkScalarMul(fTangent.fY, d0); | |
| 201 SkScalar y1 = fPts[0].fY + SkScalarMul(fTangent.fY, d1); | |
| 202 | |
| 203 SkPoint pts[4]; | |
| 204 pts[0].set(x0 + fNormal.fX, y0 + fNormal.fY); // moveTo | |
| 205 pts[1].set(x1 + fNormal.fX, y1 + fNormal.fY); // lineTo | |
| 206 pts[2].set(x1 - fNormal.fX, y1 - fNormal.fY); // lineTo | |
| 207 pts[3].set(x0 - fNormal.fX, y0 - fNormal.fY); // lineTo | |
| 208 | |
| 209 path->addPoly(pts, SK_ARRAY_COUNT(pts), false); | |
| 210 } | |
| 211 | |
| 212 private: | |
| 213 SkPoint fPts[2]; | |
| 214 SkVector fTangent; | |
| 215 SkVector fNormal; | |
| 216 SkScalar fPathLength; | |
| 217 }; | |
| 218 | |
| 219 | |
| 220 bool SkDashPath::FilterDashPath(SkPath* dst, const SkPath& src, SkStrokeRec* rec
, | |
| 221 const SkRect* cullRect, const SkScalar aInterval
s[], | |
| 222 int32_t count, SkScalar initialDashLength, int32
_t initialDashIndex, | |
| 223 SkScalar intervalLength) { | |
| 224 | |
| 225 // we do nothing if the src wants to be filled, or if our dashlength is 0 | |
| 226 if (rec->isFillStyle() || initialDashLength < 0) { | |
| 227 return false; | |
| 228 } | |
| 229 | |
| 230 const SkScalar* intervals = aIntervals; | |
| 231 SkScalar dashCount = 0; | |
| 232 int segCount = 0; | |
| 233 | |
| 234 SkPath cullPathStorage; | |
| 235 const SkPath* srcPtr = &src; | |
| 236 if (cull_path(src, *rec, cullRect, intervalLength, &cullPathStorage)) { | |
| 237 srcPtr = &cullPathStorage; | |
| 238 } | |
| 239 | |
| 240 SpecialLineRec lineRec; | |
| 241 bool specialLine = lineRec.init(*srcPtr, dst, rec, count >> 1, intervalLengt
h); | |
| 242 | |
| 243 SkPathMeasure meas(*srcPtr, false); | |
| 244 | |
| 245 do { | |
| 246 bool skipFirstSegment = meas.isClosed(); | |
| 247 bool addedSegment = false; | |
| 248 SkScalar length = meas.getLength(); | |
| 249 int index = initialDashIndex; | |
| 250 | |
| 251 // Since the path length / dash length ratio may be arbitrarily large, w
e can exert | |
| 252 // significant memory pressure while attempting to build the filtered pa
th. To avoid this, | |
| 253 // we simply give up dashing beyond a certain threshold. | |
| 254 // | |
| 255 // The original bug report (http://crbug.com/165432) is based on a path
yielding more than | |
| 256 // 90 million dash segments and crashing the memory allocator. A limit o
f 1 million | |
| 257 // segments seems reasonable: at 2 verbs per segment * 9 bytes per verb,
this caps the | |
| 258 // maximum dash memory overhead at roughly 17MB per path. | |
| 259 static const SkScalar kMaxDashCount = 1000000; | |
| 260 dashCount += length * (count >> 1) / intervalLength; | |
| 261 if (dashCount > kMaxDashCount) { | |
| 262 dst->reset(); | |
| 263 return false; | |
| 264 } | |
| 265 | |
| 266 // Using double precision to avoid looping indefinitely due to single pr
ecision rounding | |
| 267 // (for extreme path_length/dash_length ratios). See test_infinite_dash(
) unittest. | |
| 268 double distance = 0; | |
| 269 double dlen = initialDashLength; | |
| 270 | |
| 271 while (distance < length) { | |
| 272 SkASSERT(dlen >= 0); | |
| 273 addedSegment = false; | |
| 274 if (is_even(index) && dlen > 0 && !skipFirstSegment) { | |
| 275 addedSegment = true; | |
| 276 ++segCount; | |
| 277 | |
| 278 if (specialLine) { | |
| 279 lineRec.addSegment(SkDoubleToScalar(distance), | |
| 280 SkDoubleToScalar(distance + dlen), | |
| 281 dst); | |
| 282 } else { | |
| 283 meas.getSegment(SkDoubleToScalar(distance), | |
| 284 SkDoubleToScalar(distance + dlen), | |
| 285 dst, true); | |
| 286 } | |
| 287 } | |
| 288 distance += dlen; | |
| 289 | |
| 290 // clear this so we only respect it the first time around | |
| 291 skipFirstSegment = false; | |
| 292 | |
| 293 // wrap around our intervals array if necessary | |
| 294 index += 1; | |
| 295 SkASSERT(index <= count); | |
| 296 if (index == count) { | |
| 297 index = 0; | |
| 298 } | |
| 299 | |
| 300 // fetch our next dlen | |
| 301 dlen = intervals[index]; | |
| 302 } | |
| 303 | |
| 304 // extend if we ended on a segment and we need to join up with the (skip
ped) initial segment | |
| 305 if (meas.isClosed() && is_even(initialDashIndex) && | |
| 306 initialDashLength > 0) { | |
| 307 meas.getSegment(0, initialDashLength, dst, !addedSegment); | |
| 308 ++segCount; | |
| 309 } | |
| 310 } while (meas.nextContour()); | |
| 311 | |
| 312 if (segCount > 1) { | |
| 313 dst->setConvexity(SkPath::kConcave_Convexity); | |
| 314 } | |
| 315 | |
| 316 return true; | |
| 317 } | |
| 318 | |
| 319 bool SkDashPath::FilterDashPath(SkPath* dst, const SkPath& src, SkStrokeRec* rec
, | |
| 320 const SkRect* cullRect, const SkPathEffect::Dash
Info& info) { | |
| 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 FilterDashPath(dst, src, rec, cullRect, info.fIntervals, info.fCount,
initialDashLength, | |
| 327 initialDashIndex, intervalLength); | |
| 328 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 317663003:
Revert of Move Dashing filterPath to a dashing utils file (Closed)
Base URL: https://skia.googlesource.com/skia.git@master