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 "SkStrokeRec.h"
11
12static inline int is_even(int x) {
13    return !(x & 1);
14}
15
16static SkScalar find_first_interval(const SkScalar intervals[], SkScalar phase,
17                                    int32_t* index, int count) {
18    for (int i = 0; i < count; ++i) {
19        SkScalar gap = intervals[i];
20        if (phase > gap || (phase == gap && gap)) {
21            phase -= gap;
22        } else {
23            *index = i;
24            return gap - phase;
25        }
26    }
27    // If we get here, phase "appears" to be larger than our length. This
28    // shouldn't happen with perfect precision, but we can accumulate errors
29    // during the initial length computation (rounding can make our sum be too
30    // big or too small. In that event, we just have to eat the error here.
31    *index = 0;
32    return intervals[0];
33}
34
35void SkDashPath::CalcDashParameters(SkScalar phase, const SkScalar intervals[], int32_t count,
36                                    SkScalar* initialDashLength, int32_t* initialDashIndex,
37                                    SkScalar* intervalLength, SkScalar* adjustedPhase) {
38    SkScalar len = 0;
39    for (int i = 0; i < count; i++) {
40        len += intervals[i];
41    }
42    *intervalLength = len;
43    // Adjust phase to be between 0 and len, "flipping" phase if negative.
44    // e.g., if len is 100, then phase of -20 (or -120) is equivalent to 80
45    if (adjustedPhase) {
46        if (phase < 0) {
47            phase = -phase;
48            if (phase > len) {
49                phase = SkScalarMod(phase, len);
50            }
51            phase = len - phase;
52
53            // Due to finite precision, it's possible that phase == len,
54            // even after the subtract (if len >>> phase), so fix that here.
55            // This fixes http://crbug.com/124652 .
56            SkASSERT(phase <= len);
57            if (phase == len) {
58                phase = 0;
59            }
60        } else if (phase >= len) {
61            phase = SkScalarMod(phase, len);
62        }
63        *adjustedPhase = phase;
64    }
65    SkASSERT(phase >= 0 && phase < len);
66
67    *initialDashLength = find_first_interval(intervals, phase,
68                                            initialDashIndex, count);
69
70    SkASSERT(*initialDashLength >= 0);
71    SkASSERT(*initialDashIndex >= 0 && *initialDashIndex < count);
72}
73
74static void outset_for_stroke(SkRect* rect, const SkStrokeRec& rec) {
75    SkScalar radius = SkScalarHalf(rec.getWidth());
76    if (0 == radius) {
77        radius = SK_Scalar1;    // hairlines
78    }
79    if (SkPaint::kMiter_Join == rec.getJoin()) {
80        radius *= rec.getMiter();
81    }
82    rect->outset(radius, radius);
83}
84
85// Only handles lines for now. If returns true, dstPath is the new (smaller)
86// path. If returns false, then dstPath parameter is ignored.
87static bool cull_path(const SkPath& srcPath, const SkStrokeRec& rec,
88                      const SkRect* cullRect, SkScalar intervalLength,
89                      SkPath* dstPath) {
90    if (nullptr == cullRect) {
91        return false;
92    }
93
94    SkPoint pts[2];
95    if (!srcPath.isLine(pts)) {
96        return false;
97    }
98
99    SkRect bounds = *cullRect;
100    outset_for_stroke(&bounds, rec);
101
102    SkScalar dx = pts[1].x() - pts[0].x();
103    SkScalar dy = pts[1].y() - pts[0].y();
104
105    // just do horizontal lines for now (lazy)
106    if (dy) {
107        return false;
108    }
109
110    SkScalar minX = pts[0].fX;
111    SkScalar maxX = pts[1].fX;
112
113    if (dx < 0) {
114        SkTSwap(minX, maxX);
115    }
116
117    SkASSERT(minX <= maxX);
118    if (maxX < bounds.fLeft || minX > bounds.fRight) {
119        return false;
120    }
121
122    // Now we actually perform the chop, removing the excess to the left and
123    // right of the bounds (keeping our new line "in phase" with the dash,
124    // hence the (mod intervalLength).
125
126    if (minX < bounds.fLeft) {
127        minX = bounds.fLeft - SkScalarMod(bounds.fLeft - minX,
128                                          intervalLength);
129    }
130    if (maxX > bounds.fRight) {
131        maxX = bounds.fRight + SkScalarMod(maxX - bounds.fRight,
132                                           intervalLength);
133    }
134
135    SkASSERT(maxX >= minX);
136    if (dx < 0) {
137        SkTSwap(minX, maxX);
138    }
139    pts[0].fX = minX;
140    pts[1].fX = maxX;
141
142    dstPath->moveTo(pts[0]);
143    dstPath->lineTo(pts[1]);
144    return true;
145}
146
147class SpecialLineRec {
148public:
149    bool init(const SkPath& src, SkPath* dst, SkStrokeRec* rec,
150              int intervalCount, SkScalar intervalLength) {
151        if (rec->isHairlineStyle() || !src.isLine(fPts)) {
152            return false;
153        }
154
155        // can relax this in the future, if we handle square and round caps
156        if (SkPaint::kButt_Cap != rec->getCap()) {
157            return false;
158        }
159
160        SkScalar pathLength = SkPoint::Distance(fPts[0], fPts[1]);
161
162        fTangent = fPts[1] - fPts[0];
163        if (fTangent.isZero()) {
164            return false;
165        }
166
167        fPathLength = pathLength;
168        fTangent.scale(SkScalarInvert(pathLength));
169        fTangent.rotateCCW(&fNormal);
170        fNormal.scale(SkScalarHalf(rec->getWidth()));
171
172        // now estimate how many quads will be added to the path
173        //     resulting segments = pathLen * intervalCount / intervalLen
174        //     resulting points = 4 * segments
175
176        SkScalar ptCount = pathLength * intervalCount / (float)intervalLength;
177        ptCount = SkTMin(ptCount, SkDashPath::kMaxDashCount);
178        int n = SkScalarCeilToInt(ptCount) << 2;
179        dst->incReserve(n);
180
181        // we will take care of the stroking
182        rec->setFillStyle();
183        return true;
184    }
185
186    void addSegment(SkScalar d0, SkScalar d1, SkPath* path) const {
187        SkASSERT(d0 <= fPathLength);
188        // clamp the segment to our length
189        if (d1 > fPathLength) {
190            d1 = fPathLength;
191        }
192
193        SkScalar x0 = fPts[0].fX + fTangent.fX * d0;
194        SkScalar x1 = fPts[0].fX + fTangent.fX * d1;
195        SkScalar y0 = fPts[0].fY + fTangent.fY * d0;
196        SkScalar y1 = fPts[0].fY + fTangent.fY * d1;
197
198        SkPoint pts[4];
199        pts[0].set(x0 + fNormal.fX, y0 + fNormal.fY);   // moveTo
200        pts[1].set(x1 + fNormal.fX, y1 + fNormal.fY);   // lineTo
201        pts[2].set(x1 - fNormal.fX, y1 - fNormal.fY);   // lineTo
202        pts[3].set(x0 - fNormal.fX, y0 - fNormal.fY);   // lineTo
203
204        path->addPoly(pts, SK_ARRAY_COUNT(pts), false);
205    }
206
207private:
208    SkPoint fPts[2];
209    SkVector fTangent;
210    SkVector fNormal;
211    SkScalar fPathLength;
212};
213
214
215bool SkDashPath::InternalFilter(SkPath* dst, const SkPath& src, SkStrokeRec* rec,
216                                const SkRect* cullRect, const SkScalar aIntervals[],
217                                int32_t count, SkScalar initialDashLength, int32_t initialDashIndex,
218                                SkScalar intervalLength,
219                                StrokeRecApplication strokeRecApplication) {
220
221    // we do nothing if the src wants to be filled
222    SkStrokeRec::Style style = rec->getStyle();
223    if (SkStrokeRec::kFill_Style == style || SkStrokeRec::kStrokeAndFill_Style == style) {
224        return false;
225    }
226
227    const SkScalar* intervals = aIntervals;
228    SkScalar        dashCount = 0;
229    int             segCount = 0;
230
231    SkPath cullPathStorage;
232    const SkPath* srcPtr = &src;
233    if (cull_path(src, *rec, cullRect, intervalLength, &cullPathStorage)) {
234        srcPtr = &cullPathStorage;
235    }
236
237    SpecialLineRec lineRec;
238    bool specialLine = (StrokeRecApplication::kAllow == strokeRecApplication) &&
239                       lineRec.init(*srcPtr, dst, rec, count >> 1, intervalLength);
240
241    SkPathMeasure   meas(*srcPtr, false, rec->getResScale());
242
243    do {
244        bool        skipFirstSegment = meas.isClosed();
245        bool        addedSegment = false;
246        SkScalar    length = meas.getLength();
247        int         index = initialDashIndex;
248
249        // Since the path length / dash length ratio may be arbitrarily large, we can exert
250        // significant memory pressure while attempting to build the filtered path. To avoid this,
251        // we simply give up dashing beyond a certain threshold.
252        //
253        // The original bug report (http://crbug.com/165432) is based on a path yielding more than
254        // 90 million dash segments and crashing the memory allocator. A limit of 1 million
255        // segments seems reasonable: at 2 verbs per segment * 9 bytes per verb, this caps the
256        // maximum dash memory overhead at roughly 17MB per path.
257        dashCount += length * (count >> 1) / intervalLength;
258        if (dashCount > kMaxDashCount) {
259            dst->reset();
260            return false;
261        }
262
263        // Using double precision to avoid looping indefinitely due to single precision rounding
264        // (for extreme path_length/dash_length ratios). See test_infinite_dash() unittest.
265        double  distance = 0;
266        double  dlen = initialDashLength;
267
268        while (distance < length) {
269            SkASSERT(dlen >= 0);
270            addedSegment = false;
271            if (is_even(index) && !skipFirstSegment) {
272                addedSegment = true;
273                ++segCount;
274
275                if (specialLine) {
276                    lineRec.addSegment(SkDoubleToScalar(distance),
277                                       SkDoubleToScalar(distance + dlen),
278                                       dst);
279                } else {
280                    meas.getSegment(SkDoubleToScalar(distance),
281                                    SkDoubleToScalar(distance + dlen),
282                                    dst, true);
283                }
284            }
285            distance += dlen;
286
287            // clear this so we only respect it the first time around
288            skipFirstSegment = false;
289
290            // wrap around our intervals array if necessary
291            index += 1;
292            SkASSERT(index <= count);
293            if (index == count) {
294                index = 0;
295            }
296
297            // fetch our next dlen
298            dlen = intervals[index];
299        }
300
301        // extend if we ended on a segment and we need to join up with the (skipped) initial segment
302        if (meas.isClosed() && is_even(initialDashIndex) &&
303            initialDashLength >= 0) {
304            meas.getSegment(0, initialDashLength, dst, !addedSegment);
305            ++segCount;
306        }
307    } while (meas.nextContour());
308
309    if (segCount > 1) {
310        dst->setConvexity(SkPath::kConcave_Convexity);
311    }
312
313    return true;
314}
315
316bool SkDashPath::FilterDashPath(SkPath* dst, const SkPath& src, SkStrokeRec* rec,
317                                const SkRect* cullRect, const SkPathEffect::DashInfo& info) {
318    if (!ValidDashPath(info.fPhase, info.fIntervals, info.fCount)) {
319        return false;
320    }
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 InternalFilter(dst, src, rec, cullRect, info.fIntervals, info.fCount, initialDashLength,
327                          initialDashIndex, intervalLength);
328}
329
330bool SkDashPath::ValidDashPath(SkScalar phase, const SkScalar intervals[], int32_t count) {
331    if (count < 2 || !SkIsAlign2(count)) {
332        return false;
333    }
334    SkScalar length = 0;
335    for (int i = 0; i < count; i++) {
336        if (intervals[i] < 0) {
337            return false;
338        }
339        length += intervals[i];
340    }
341    // watch out for values that might make us go out of bounds
342    return length > 0 && SkScalarIsFinite(phase) && SkScalarIsFinite(length);
343}
344