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
14static inline int is_even(int x) {
15    return (~x) << 31;
16}
17
18static 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
36SkDashPathEffect::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
87SkDashPathEffect::~SkDashPathEffect() {
88    sk_free(fIntervals);
89}
90
91static 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.
104static 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
163class SpecialLineRec {
164public:
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
224private:
225    SkPoint fPts[2];
226    SkVector fTangent;
227    SkVector fNormal;
228    SkScalar fPathLength;
229};
230
231bool SkDashPathEffect::filterPath(SkPath* dst, const SkPath& src,
232                              SkStrokeRec* rec, const SkRect* cullRect) const {
233    // we do nothing if the src wants to be filled, or if our dashlength is 0
234    if (rec->isFillStyle() || fInitialDashLength < 0) {
235        return false;
236    }
237
238    const SkScalar* intervals = fIntervals;
239    SkScalar        dashCount = 0;
240    int             segCount = 0;
241
242    SkPath cullPathStorage;
243    const SkPath* srcPtr = &src;
244    if (cull_path(src, *rec, cullRect, fIntervalLength, &cullPathStorage)) {
245        srcPtr = &cullPathStorage;
246    }
247
248    SpecialLineRec lineRec;
249    bool specialLine = lineRec.init(*srcPtr, dst, rec, fCount >> 1, fIntervalLength);
250
251    SkPathMeasure   meas(*srcPtr, false);
252
253    do {
254        bool        skipFirstSegment = meas.isClosed();
255        bool        addedSegment = false;
256        SkScalar    length = meas.getLength();
257        int         index = fInitialDashIndex;
258        SkScalar    scale = SK_Scalar1;
259
260        // Since the path length / dash length ratio may be arbitrarily large, we can exert
261        // significant memory pressure while attempting to build the filtered path. To avoid this,
262        // we simply give up dashing beyond a certain threshold.
263        //
264        // The original bug report (http://crbug.com/165432) is based on a path yielding more than
265        // 90 million dash segments and crashing the memory allocator. A limit of 1 million
266        // segments seems reasonable: at 2 verbs per segment * 9 bytes per verb, this caps the
267        // maximum dash memory overhead at roughly 17MB per path.
268        static const SkScalar kMaxDashCount = 1000000;
269        dashCount += length * (fCount >> 1) / fIntervalLength;
270        if (dashCount > kMaxDashCount) {
271            dst->reset();
272            return false;
273        }
274
275        if (fScaleToFit) {
276            if (fIntervalLength >= length) {
277                scale = SkScalarDiv(length, fIntervalLength);
278            } else {
279                SkScalar div = SkScalarDiv(length, fIntervalLength);
280                int n = SkScalarFloor(div);
281                scale = SkScalarDiv(length, n * fIntervalLength);
282            }
283        }
284
285        // Using double precision to avoid looping indefinitely due to single precision rounding
286        // (for extreme path_length/dash_length ratios). See test_infinite_dash() unittest.
287        double  distance = 0;
288        double  dlen = SkScalarMul(fInitialDashLength, scale);
289
290        while (distance < length) {
291            SkASSERT(dlen >= 0);
292            addedSegment = false;
293            if (is_even(index) && dlen > 0 && !skipFirstSegment) {
294                addedSegment = true;
295                ++segCount;
296
297                if (specialLine) {
298                    lineRec.addSegment(SkDoubleToScalar(distance),
299                                       SkDoubleToScalar(distance + dlen),
300                                       dst);
301                } else {
302                    meas.getSegment(SkDoubleToScalar(distance),
303                                    SkDoubleToScalar(distance + dlen),
304                                    dst, true);
305                }
306            }
307            distance += dlen;
308
309            // clear this so we only respect it the first time around
310            skipFirstSegment = false;
311
312            // wrap around our intervals array if necessary
313            index += 1;
314            SkASSERT(index <= fCount);
315            if (index == fCount) {
316                index = 0;
317            }
318
319            // fetch our next dlen
320            dlen = SkScalarMul(intervals[index], scale);
321        }
322
323        // extend if we ended on a segment and we need to join up with the (skipped) initial segment
324        if (meas.isClosed() && is_even(fInitialDashIndex) &&
325                fInitialDashLength > 0) {
326            meas.getSegment(0, SkScalarMul(fInitialDashLength, scale), dst, !addedSegment);
327            ++segCount;
328        }
329    } while (meas.nextContour());
330
331    if (segCount > 1) {
332        dst->setConvexity(SkPath::kConcave_Convexity);
333    }
334
335    return true;
336}
337
338// Currently asPoints is more restrictive then it needs to be. In the future
339// we need to:
340//      allow kRound_Cap capping (could allow rotations in the matrix with this)
341//      allow paths to be returned
342bool SkDashPathEffect::asPoints(PointData* results,
343                                const SkPath& src,
344                                const SkStrokeRec& rec,
345                                const SkMatrix& matrix,
346                                const SkRect* cullRect) const {
347    // width < 0 -> fill && width == 0 -> hairline so requiring width > 0 rules both out
348    if (fInitialDashLength < 0 || 0 >= rec.getWidth()) {
349        return false;
350    }
351
352    // TODO: this next test could be eased up. We could allow any number of
353    // intervals as long as all the ons match and all the offs match.
354    // Additionally, they do not necessarily need to be integers.
355    // We cannot allow arbitrary intervals since we want the returned points
356    // to be uniformly sized.
357    if (fCount != 2 ||
358        !SkScalarNearlyEqual(fIntervals[0], fIntervals[1]) ||
359        !SkScalarIsInt(fIntervals[0]) ||
360        !SkScalarIsInt(fIntervals[1])) {
361        return false;
362    }
363
364    // TODO: this next test could be eased up. The rescaling should not impact
365    // the equality of the ons & offs. However, we would need to remove the
366    // integer intervals restriction first
367    if (fScaleToFit) {
368        return false;
369    }
370
371    SkPoint pts[2];
372
373    if (!src.isLine(pts)) {
374        return false;
375    }
376
377    // TODO: this test could be eased up to allow circles
378    if (SkPaint::kButt_Cap != rec.getCap()) {
379        return false;
380    }
381
382    // TODO: this test could be eased up for circles. Rotations could be allowed.
383    if (!matrix.rectStaysRect()) {
384        return false;
385    }
386
387    SkScalar        length = SkPoint::Distance(pts[1], pts[0]);
388
389    SkVector tangent = pts[1] - pts[0];
390    if (tangent.isZero()) {
391        return false;
392    }
393
394    tangent.scale(SkScalarInvert(length));
395
396    // TODO: make this test for horizontal & vertical lines more robust
397    bool isXAxis = true;
398    if (SK_Scalar1 == tangent.fX || -SK_Scalar1 == tangent.fX) {
399        results->fSize.set(SkScalarHalf(fIntervals[0]), SkScalarHalf(rec.getWidth()));
400    } else if (SK_Scalar1 == tangent.fY || -SK_Scalar1 == tangent.fY) {
401        results->fSize.set(SkScalarHalf(rec.getWidth()), SkScalarHalf(fIntervals[0]));
402        isXAxis = false;
403    } else if (SkPaint::kRound_Cap != rec.getCap()) {
404        // Angled lines don't have axis-aligned boxes.
405        return false;
406    }
407
408    if (NULL != results) {
409        results->fFlags = 0;
410        SkScalar clampedInitialDashLength = SkMinScalar(length, fInitialDashLength);
411
412        if (SkPaint::kRound_Cap == rec.getCap()) {
413            results->fFlags |= PointData::kCircles_PointFlag;
414        }
415
416        results->fNumPoints = 0;
417        SkScalar len2 = length;
418        if (clampedInitialDashLength > 0 || 0 == fInitialDashIndex) {
419            SkASSERT(len2 >= clampedInitialDashLength);
420            if (0 == fInitialDashIndex) {
421                if (clampedInitialDashLength > 0) {
422                    if (clampedInitialDashLength >= fIntervals[0]) {
423                        ++results->fNumPoints;  // partial first dash
424                    }
425                    len2 -= clampedInitialDashLength;
426                }
427                len2 -= fIntervals[1];  // also skip first space
428                if (len2 < 0) {
429                    len2 = 0;
430                }
431            } else {
432                len2 -= clampedInitialDashLength; // skip initial partial empty
433            }
434        }
435        int numMidPoints = SkScalarFloorToInt(SkScalarDiv(len2, fIntervalLength));
436        results->fNumPoints += numMidPoints;
437        len2 -= numMidPoints * fIntervalLength;
438        bool partialLast = false;
439        if (len2 > 0) {
440            if (len2 < fIntervals[0]) {
441                partialLast = true;
442            } else {
443                ++numMidPoints;
444                ++results->fNumPoints;
445            }
446        }
447
448        results->fPoints = new SkPoint[results->fNumPoints];
449
450        SkScalar    distance = 0;
451        int         curPt = 0;
452
453        if (clampedInitialDashLength > 0 || 0 == fInitialDashIndex) {
454            SkASSERT(clampedInitialDashLength <= length);
455
456            if (0 == fInitialDashIndex) {
457                if (clampedInitialDashLength > 0) {
458                    // partial first block
459                    SkASSERT(SkPaint::kRound_Cap != rec.getCap()); // can't handle partial circles
460                    SkScalar x = pts[0].fX + SkScalarMul(tangent.fX, SkScalarHalf(clampedInitialDashLength));
461                    SkScalar y = pts[0].fY + SkScalarMul(tangent.fY, SkScalarHalf(clampedInitialDashLength));
462                    SkScalar halfWidth, halfHeight;
463                    if (isXAxis) {
464                        halfWidth = SkScalarHalf(clampedInitialDashLength);
465                        halfHeight = SkScalarHalf(rec.getWidth());
466                    } else {
467                        halfWidth = SkScalarHalf(rec.getWidth());
468                        halfHeight = SkScalarHalf(clampedInitialDashLength);
469                    }
470                    if (clampedInitialDashLength < fIntervals[0]) {
471                        // This one will not be like the others
472                        results->fFirst.addRect(x - halfWidth, y - halfHeight,
473                                                x + halfWidth, y + halfHeight);
474                    } else {
475                        SkASSERT(curPt < results->fNumPoints);
476                        results->fPoints[curPt].set(x, y);
477                        ++curPt;
478                    }
479
480                    distance += clampedInitialDashLength;
481                }
482
483                distance += fIntervals[1];  // skip over the next blank block too
484            } else {
485                distance += clampedInitialDashLength;
486            }
487        }
488
489        if (0 != numMidPoints) {
490            distance += SkScalarHalf(fIntervals[0]);
491
492            for (int i = 0; i < numMidPoints; ++i) {
493                SkScalar x = pts[0].fX + SkScalarMul(tangent.fX, distance);
494                SkScalar y = pts[0].fY + SkScalarMul(tangent.fY, distance);
495
496                SkASSERT(curPt < results->fNumPoints);
497                results->fPoints[curPt].set(x, y);
498                ++curPt;
499
500                distance += fIntervalLength;
501            }
502
503            distance -= SkScalarHalf(fIntervals[0]);
504        }
505
506        if (partialLast) {
507            // partial final block
508            SkASSERT(SkPaint::kRound_Cap != rec.getCap()); // can't handle partial circles
509            SkScalar temp = length - distance;
510            SkASSERT(temp < fIntervals[0]);
511            SkScalar x = pts[0].fX + SkScalarMul(tangent.fX, distance + SkScalarHalf(temp));
512            SkScalar y = pts[0].fY + SkScalarMul(tangent.fY, distance + SkScalarHalf(temp));
513            SkScalar halfWidth, halfHeight;
514            if (isXAxis) {
515                halfWidth = SkScalarHalf(temp);
516                halfHeight = SkScalarHalf(rec.getWidth());
517            } else {
518                halfWidth = SkScalarHalf(rec.getWidth());
519                halfHeight = SkScalarHalf(temp);
520            }
521            results->fLast.addRect(x - halfWidth, y - halfHeight,
522                                   x + halfWidth, y + halfHeight);
523        }
524
525        SkASSERT(curPt == results->fNumPoints);
526    }
527
528    return true;
529}
530
531SkFlattenable::Factory SkDashPathEffect::getFactory() const {
532    return fInitialDashLength < 0 ? NULL : CreateProc;
533}
534
535void SkDashPathEffect::flatten(SkFlattenableWriteBuffer& buffer) const {
536    SkASSERT(fInitialDashLength >= 0);
537
538    this->INHERITED::flatten(buffer);
539    buffer.writeInt(fInitialDashIndex);
540    buffer.writeScalar(fInitialDashLength);
541    buffer.writeScalar(fIntervalLength);
542    buffer.writeBool(fScaleToFit);
543    buffer.writeScalarArray(fIntervals, fCount);
544}
545
546SkFlattenable* SkDashPathEffect::CreateProc(SkFlattenableReadBuffer& buffer) {
547    return SkNEW_ARGS(SkDashPathEffect, (buffer));
548}
549
550SkDashPathEffect::SkDashPathEffect(SkFlattenableReadBuffer& buffer) : INHERITED(buffer) {
551    fInitialDashIndex = buffer.readInt();
552    fInitialDashLength = buffer.readScalar();
553    fIntervalLength = buffer.readScalar();
554    fScaleToFit = buffer.readBool();
555
556    fCount = buffer.getArrayCount();
557    fIntervals = (SkScalar*)sk_malloc_throw(sizeof(SkScalar) * fCount);
558    buffer.readScalarArray(fIntervals, fCount);
559}
560