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