SkDashPath.cpp revision 9f2251c73ed6f417dd1057d487bf523e04488440 
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
11static inline int is_even(int x) {
12    return (~x) << 31;
13}
14
15static 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
33void 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
79static 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.
92static 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 (dx < 0) {
119        SkTSwap(minX, maxX);
120    }
121
122    SkASSERT(minX < maxX);
123    if (maxX < bounds.fLeft || minX > bounds.fRight) {
124        return false;
125    }
126
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
152class SpecialLineRec {
153public:
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
213private:
214    SkPoint fPts[2];
215    SkVector fTangent;
216    SkVector fNormal;
217    SkScalar fPathLength;
218};
219
220
221bool 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
320bool 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}
330