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