1/*
2 * Copyright 2006 The Android Open Source Project
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 "include/effects/SkDashPathEffect.h"
9
10#include "include/core/SkStrokeRec.h"
11#include "include/private/SkTo.h"
12#include "src/core/SkReadBuffer.h"
13#include "src/core/SkWriteBuffer.h"
14#include "src/effects/SkDashImpl.h"
15#include "src/utils/SkDashPathPriv.h"
16
17#include <utility>
18
19SkDashImpl::SkDashImpl(const SkScalar intervals[], int count, SkScalar phase)
20        : fPhase(0)
21        , fInitialDashLength(-1)
22        , fInitialDashIndex(0)
23        , fIntervalLength(0) {
24    SkASSERT(intervals);
25    SkASSERT(count > 1 && SkIsAlign2(count));
26
27    fIntervals = (SkScalar*)sk_malloc_throw(sizeof(SkScalar) * count);
28    fCount = count;
29    for (int i = 0; i < count; i++) {
30        fIntervals[i] = intervals[i];
31    }
32
33    // set the internal data members
34    SkDashPath::CalcDashParameters(phase, fIntervals, fCount,
35            &fInitialDashLength, &fInitialDashIndex, &fIntervalLength, &fPhase);
36}
37
38SkDashImpl::~SkDashImpl() {
39    sk_free(fIntervals);
40}
41
42bool SkDashImpl::onFilterPath(SkPath* dst, const SkPath& src, SkStrokeRec* rec,
43                              const SkRect* cullRect, const SkMatrix&) const {
44    return SkDashPath::InternalFilter(dst, src, rec, cullRect, fIntervals, fCount,
45                                      fInitialDashLength, fInitialDashIndex, fIntervalLength);
46}
47
48static void outset_for_stroke(SkRect* rect, const SkStrokeRec& rec) {
49    SkScalar radius = SkScalarHalf(rec.getWidth());
50    if (0 == radius) {
51        radius = SK_Scalar1;    // hairlines
52    }
53    if (SkPaint::kMiter_Join == rec.getJoin()) {
54        radius *= rec.getMiter();
55    }
56    rect->outset(radius, radius);
57}
58
59// Attempt to trim the line to minimally cover the cull rect (currently
60// only works for horizontal and vertical lines).
61// Return true if processing should continue; false otherwise.
62static bool cull_line(SkPoint* pts, const SkStrokeRec& rec,
63                      const SkMatrix& ctm, const SkRect* cullRect,
64                      const SkScalar intervalLength) {
65    if (nullptr == cullRect) {
66        SkASSERT(false); // Shouldn't ever occur in practice
67        return false;
68    }
69
70    SkScalar dx = pts[1].x() - pts[0].x();
71    SkScalar dy = pts[1].y() - pts[0].y();
72
73    if ((dx && dy) || (!dx && !dy)) {
74        return false;
75    }
76
77    SkRect bounds = *cullRect;
78    outset_for_stroke(&bounds, rec);
79
80    // cullRect is in device space while pts are in the local coordinate system
81    // defined by the ctm. We want our answer in the local coordinate system.
82
83    SkASSERT(ctm.rectStaysRect());
84    SkMatrix inv;
85    if (!ctm.invert(&inv)) {
86        return false;
87    }
88
89    inv.mapRect(&bounds);
90
91    if (dx) {
92        SkASSERT(dx && !dy);
93        SkScalar minX = pts[0].fX;
94        SkScalar maxX = pts[1].fX;
95
96        if (dx < 0) {
97            using std::swap;
98            swap(minX, maxX);
99        }
100
101        SkASSERT(minX < maxX);
102        if (maxX <= bounds.fLeft || minX >= bounds.fRight) {
103            return false;
104        }
105
106        // Now we actually perform the chop, removing the excess to the left and
107        // right of the bounds (keeping our new line "in phase" with the dash,
108        // hence the (mod intervalLength).
109
110        if (minX < bounds.fLeft) {
111            minX = bounds.fLeft - SkScalarMod(bounds.fLeft - minX, intervalLength);
112        }
113        if (maxX > bounds.fRight) {
114            maxX = bounds.fRight + SkScalarMod(maxX - bounds.fRight, intervalLength);
115        }
116
117        SkASSERT(maxX > minX);
118        if (dx < 0) {
119            using std::swap;
120            swap(minX, maxX);
121        }
122        pts[0].fX = minX;
123        pts[1].fX = maxX;
124    } else {
125        SkASSERT(dy && !dx);
126        SkScalar minY = pts[0].fY;
127        SkScalar maxY = pts[1].fY;
128
129        if (dy < 0) {
130            using std::swap;
131            swap(minY, maxY);
132        }
133
134        SkASSERT(minY < maxY);
135        if (maxY <= bounds.fTop || minY >= bounds.fBottom) {
136            return false;
137        }
138
139        // Now we actually perform the chop, removing the excess to the top and
140        // bottom of the bounds (keeping our new line "in phase" with the dash,
141        // hence the (mod intervalLength).
142
143        if (minY < bounds.fTop) {
144            minY = bounds.fTop - SkScalarMod(bounds.fTop - minY, intervalLength);
145        }
146        if (maxY > bounds.fBottom) {
147            maxY = bounds.fBottom + SkScalarMod(maxY - bounds.fBottom, intervalLength);
148        }
149
150        SkASSERT(maxY > minY);
151        if (dy < 0) {
152            using std::swap;
153            swap(minY, maxY);
154        }
155        pts[0].fY = minY;
156        pts[1].fY = maxY;
157    }
158
159    return true;
160}
161
162// Currently asPoints is more restrictive then it needs to be. In the future
163// we need to:
164//      allow kRound_Cap capping (could allow rotations in the matrix with this)
165//      allow paths to be returned
166bool SkDashImpl::onAsPoints(PointData* results, const SkPath& src, const SkStrokeRec& rec,
167                            const SkMatrix& matrix, const SkRect* cullRect) const {
168    // width < 0 -> fill && width == 0 -> hairline so requiring width > 0 rules both out
169    if (0 >= rec.getWidth()) {
170        return false;
171    }
172
173    // TODO: this next test could be eased up. We could allow any number of
174    // intervals as long as all the ons match and all the offs match.
175    // Additionally, they do not necessarily need to be integers.
176    // We cannot allow arbitrary intervals since we want the returned points
177    // to be uniformly sized.
178    if (fCount != 2 ||
179        !SkScalarNearlyEqual(fIntervals[0], fIntervals[1]) ||
180        !SkScalarIsInt(fIntervals[0]) ||
181        !SkScalarIsInt(fIntervals[1])) {
182        return false;
183    }
184
185    SkPoint pts[2];
186
187    if (!src.isLine(pts)) {
188        return false;
189    }
190
191    // TODO: this test could be eased up to allow circles
192    if (SkPaint::kButt_Cap != rec.getCap()) {
193        return false;
194    }
195
196    // TODO: this test could be eased up for circles. Rotations could be allowed.
197    if (!matrix.rectStaysRect()) {
198        return false;
199    }
200
201    // See if the line can be limited to something plausible.
202    if (!cull_line(pts, rec, matrix, cullRect, fIntervalLength)) {
203        return false;
204    }
205
206    SkScalar length = SkPoint::Distance(pts[1], pts[0]);
207
208    SkVector tangent = pts[1] - pts[0];
209    if (tangent.isZero()) {
210        return false;
211    }
212
213    tangent.scale(SkScalarInvert(length));
214
215    // TODO: make this test for horizontal & vertical lines more robust
216    bool isXAxis = true;
217    if (SkScalarNearlyEqual(SK_Scalar1, tangent.fX) ||
218        SkScalarNearlyEqual(-SK_Scalar1, tangent.fX)) {
219        results->fSize.set(SkScalarHalf(fIntervals[0]), SkScalarHalf(rec.getWidth()));
220    } else if (SkScalarNearlyEqual(SK_Scalar1, tangent.fY) ||
221               SkScalarNearlyEqual(-SK_Scalar1, tangent.fY)) {
222        results->fSize.set(SkScalarHalf(rec.getWidth()), SkScalarHalf(fIntervals[0]));
223        isXAxis = false;
224    } else if (SkPaint::kRound_Cap != rec.getCap()) {
225        // Angled lines don't have axis-aligned boxes.
226        return false;
227    }
228
229    if (results) {
230        results->fFlags = 0;
231        SkScalar clampedInitialDashLength = std::min(length, fInitialDashLength);
232
233        if (SkPaint::kRound_Cap == rec.getCap()) {
234            results->fFlags |= PointData::kCircles_PointFlag;
235        }
236
237        results->fNumPoints = 0;
238        SkScalar len2 = length;
239        if (clampedInitialDashLength > 0 || 0 == fInitialDashIndex) {
240            SkASSERT(len2 >= clampedInitialDashLength);
241            if (0 == fInitialDashIndex) {
242                if (clampedInitialDashLength > 0) {
243                    if (clampedInitialDashLength >= fIntervals[0]) {
244                        ++results->fNumPoints;  // partial first dash
245                    }
246                    len2 -= clampedInitialDashLength;
247                }
248                len2 -= fIntervals[1];  // also skip first space
249                if (len2 < 0) {
250                    len2 = 0;
251                }
252            } else {
253                len2 -= clampedInitialDashLength; // skip initial partial empty
254            }
255        }
256        // Too many midpoints can cause results->fNumPoints to overflow or
257        // otherwise cause the results->fPoints allocation below to OOM.
258        // Cap it to a sane value.
259        SkScalar numIntervals = len2 / fIntervalLength;
260        if (!SkScalarIsFinite(numIntervals) || numIntervals > SkDashPath::kMaxDashCount) {
261            return false;
262        }
263        int numMidPoints = SkScalarFloorToInt(numIntervals);
264        results->fNumPoints += numMidPoints;
265        len2 -= numMidPoints * fIntervalLength;
266        bool partialLast = false;
267        if (len2 > 0) {
268            if (len2 < fIntervals[0]) {
269                partialLast = true;
270            } else {
271                ++numMidPoints;
272                ++results->fNumPoints;
273            }
274        }
275
276        results->fPoints = new SkPoint[results->fNumPoints];
277
278        SkScalar    distance = 0;
279        int         curPt = 0;
280
281        if (clampedInitialDashLength > 0 || 0 == fInitialDashIndex) {
282            SkASSERT(clampedInitialDashLength <= length);
283
284            if (0 == fInitialDashIndex) {
285                if (clampedInitialDashLength > 0) {
286                    // partial first block
287                    SkASSERT(SkPaint::kRound_Cap != rec.getCap()); // can't handle partial circles
288                    SkScalar x = pts[0].fX + tangent.fX * SkScalarHalf(clampedInitialDashLength);
289                    SkScalar y = pts[0].fY + tangent.fY * SkScalarHalf(clampedInitialDashLength);
290                    SkScalar halfWidth, halfHeight;
291                    if (isXAxis) {
292                        halfWidth = SkScalarHalf(clampedInitialDashLength);
293                        halfHeight = SkScalarHalf(rec.getWidth());
294                    } else {
295                        halfWidth = SkScalarHalf(rec.getWidth());
296                        halfHeight = SkScalarHalf(clampedInitialDashLength);
297                    }
298                    if (clampedInitialDashLength < fIntervals[0]) {
299                        // This one will not be like the others
300                        results->fFirst.addRect(x - halfWidth, y - halfHeight,
301                                                x + halfWidth, y + halfHeight);
302                    } else {
303                        SkASSERT(curPt < results->fNumPoints);
304                        results->fPoints[curPt].set(x, y);
305                        ++curPt;
306                    }
307
308                    distance += clampedInitialDashLength;
309                }
310
311                distance += fIntervals[1];  // skip over the next blank block too
312            } else {
313                distance += clampedInitialDashLength;
314            }
315        }
316
317        if (0 != numMidPoints) {
318            distance += SkScalarHalf(fIntervals[0]);
319
320            for (int i = 0; i < numMidPoints; ++i) {
321                SkScalar x = pts[0].fX + tangent.fX * distance;
322                SkScalar y = pts[0].fY + tangent.fY * distance;
323
324                SkASSERT(curPt < results->fNumPoints);
325                results->fPoints[curPt].set(x, y);
326                ++curPt;
327
328                distance += fIntervalLength;
329            }
330
331            distance -= SkScalarHalf(fIntervals[0]);
332        }
333
334        if (partialLast) {
335            // partial final block
336            SkASSERT(SkPaint::kRound_Cap != rec.getCap()); // can't handle partial circles
337            SkScalar temp = length - distance;
338            SkASSERT(temp < fIntervals[0]);
339            SkScalar x = pts[0].fX + tangent.fX * (distance + SkScalarHalf(temp));
340            SkScalar y = pts[0].fY + tangent.fY * (distance + SkScalarHalf(temp));
341            SkScalar halfWidth, halfHeight;
342            if (isXAxis) {
343                halfWidth = SkScalarHalf(temp);
344                halfHeight = SkScalarHalf(rec.getWidth());
345            } else {
346                halfWidth = SkScalarHalf(rec.getWidth());
347                halfHeight = SkScalarHalf(temp);
348            }
349            results->fLast.addRect(x - halfWidth, y - halfHeight,
350                                   x + halfWidth, y + halfHeight);
351        }
352
353        SkASSERT(curPt == results->fNumPoints);
354    }
355
356    return true;
357}
358
359SkPathEffect::DashType SkDashImpl::onAsADash(DashInfo* info) const {
360    if (info) {
361        if (info->fCount >= fCount && info->fIntervals) {
362            memcpy(info->fIntervals, fIntervals, fCount * sizeof(SkScalar));
363        }
364        info->fCount = fCount;
365        info->fPhase = fPhase;
366    }
367    return kDash_DashType;
368}
369
370void SkDashImpl::flatten(SkWriteBuffer& buffer) const {
371    buffer.writeScalar(fPhase);
372    buffer.writeScalarArray(fIntervals, fCount);
373}
374
375sk_sp<SkFlattenable> SkDashImpl::CreateProc(SkReadBuffer& buffer) {
376    const SkScalar phase = buffer.readScalar();
377    uint32_t count = buffer.getArrayCount();
378
379    // Don't allocate gigantic buffers if there's not data for them.
380    if (!buffer.validateCanReadN<SkScalar>(count)) {
381        return nullptr;
382    }
383
384    SkAutoSTArray<32, SkScalar> intervals(count);
385    if (buffer.readScalarArray(intervals.get(), count)) {
386        return SkDashPathEffect::Make(intervals.get(), SkToInt(count), phase);
387    }
388    return nullptr;
389}
390
391//////////////////////////////////////////////////////////////////////////////////////////////////
392
393sk_sp<SkPathEffect> SkDashPathEffect::Make(const SkScalar intervals[], int count, SkScalar phase) {
394    if (!SkDashPath::ValidDashPath(phase, intervals, count)) {
395        return nullptr;
396    }
397    return sk_sp<SkPathEffect>(new SkDashImpl(intervals, count, phase));
398}
399