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 "include/core/SkPathMeasure.h"
9#include "include/core/SkStrokeRec.h"
10#include "src/core/SkPointPriv.h"
11#include "src/utils/SkDashPathPriv.h"
12
13#include <utility>
14
15static inline int is_even(int x) {
16 return !(x & 1);
17}
18
19static SkScalar find_first_interval(const SkScalar intervals[], SkScalar phase,
20 int32_t* index, int count) {
21 for (int i = 0; i < count; ++i) {
22 SkScalar gap = intervals[i];
23 if (phase > gap || (phase == gap && gap)) {
24 phase -= gap;
25 } else {
26 *index = i;
27 return gap - phase;
28 }
29 }
30 // If we get here, phase "appears" to be larger than our length. This
31 // shouldn't happen with perfect precision, but we can accumulate errors
32 // during the initial length computation (rounding can make our sum be too
33 // big or too small. In that event, we just have to eat the error here.
34 *index = 0;
35 return intervals[0];
36}
37
38void SkDashPath::CalcDashParameters(SkScalar phase, const SkScalar intervals[], int32_t count,
39 SkScalar* initialDashLength, int32_t* initialDashIndex,
40 SkScalar* intervalLength, SkScalar* adjustedPhase) {
41 SkScalar len = 0;
42 for (int i = 0; i < count; i++) {
43 len += intervals[i];
44 }
45 *intervalLength = len;
46 // Adjust phase to be between 0 and len, "flipping" phase if negative.
47 // e.g., if len is 100, then phase of -20 (or -120) is equivalent to 80
48 if (adjustedPhase) {
49 if (phase < 0) {
50 phase = -phase;
51 if (phase > len) {
52 phase = SkScalarMod(phase, len);
53 }
54 phase = len - phase;
55
56 // Due to finite precision, it's possible that phase == len,
57 // even after the subtract (if len >>> phase), so fix that here.
58 // This fixes http://crbug.com/124652 .
59 SkASSERT(phase <= len);
60 if (phase == len) {
61 phase = 0;
62 }
63 } else if (phase >= len) {
64 phase = SkScalarMod(phase, len);
65 }
66 *adjustedPhase = phase;
67 }
68 SkASSERT(phase >= 0 && phase < len);
69
70 *initialDashLength = find_first_interval(intervals, phase,
71 initialDashIndex, count);
72
73 SkASSERT(*initialDashLength >= 0);
74 SkASSERT(*initialDashIndex >= 0 && *initialDashIndex < count);
75}
76
77static void outset_for_stroke(SkRect* rect, const SkStrokeRec& rec) {
78 SkScalar radius = SkScalarHalf(rec.getWidth());
79 if (0 == radius) {
80 radius = SK_Scalar1; // hairlines
81 }
82 if (SkPaint::kMiter_Join == rec.getJoin()) {
83 radius *= rec.getMiter();
84 }
85 rect->outset(radius, radius);
86}
87
88// If line is zero-length, bump out the end by a tiny amount
89// to draw endcaps. The bump factor is sized so that
90// SkPoint::Distance() computes a non-zero length.
91// Offsets SK_ScalarNearlyZero or smaller create empty paths when Iter measures length.
92// Large values are scaled by SK_ScalarNearlyZero so significant bits change.
93static void adjust_zero_length_line(SkPoint pts[2]) {
94 SkASSERT(pts[0] == pts[1]);
95 pts[1].fX += std::max(1.001f, pts[1].fX) * SK_ScalarNearlyZero;
96}
97
98static bool clip_line(SkPoint pts[2], const SkRect& bounds, SkScalar intervalLength,
99 SkScalar priorPhase) {
100 SkVector dxy = pts[1] - pts[0];
101
102 // only horizontal or vertical lines
103 if (dxy.fX && dxy.fY) {
104 return false;
105 }
106 int xyOffset = SkToBool(dxy.fY); // 0 to adjust horizontal, 1 to adjust vertical
107
108 SkScalar minXY = (&pts[0].fX)[xyOffset];
109 SkScalar maxXY = (&pts[1].fX)[xyOffset];
110 bool swapped = maxXY < minXY;
111 if (swapped) {
112 using std::swap;
113 swap(minXY, maxXY);
114 }
115
116 SkASSERT(minXY <= maxXY);
117 SkScalar leftTop = (&bounds.fLeft)[xyOffset];
118 SkScalar rightBottom = (&bounds.fRight)[xyOffset];
119 if (maxXY < leftTop || minXY > rightBottom) {
120 return false;
121 }
122
123 // Now we actually perform the chop, removing the excess to the left/top and
124 // right/bottom of the bounds (keeping our new line "in phase" with the dash,
125 // hence the (mod intervalLength).
126
127 if (minXY < leftTop) {
128 minXY = leftTop - SkScalarMod(leftTop - minXY, intervalLength);
129 if (!swapped) {
130 minXY -= priorPhase; // for rectangles, adjust by prior phase
131 }
132 }
133 if (maxXY > rightBottom) {
134 maxXY = rightBottom + SkScalarMod(maxXY - rightBottom, intervalLength);
135 if (swapped) {
136 maxXY += priorPhase; // for rectangles, adjust by prior phase
137 }
138 }
139
140 SkASSERT(maxXY >= minXY);
141 if (swapped) {
142 using std::swap;
143 swap(minXY, maxXY);
144 }
145 (&pts[0].fX)[xyOffset] = minXY;
146 (&pts[1].fX)[xyOffset] = maxXY;
147
148 if (minXY == maxXY) {
149 adjust_zero_length_line(pts);
150 }
151 return true;
152}
153
154// Handles only lines and rects.
155// If cull_path() returns true, dstPath is the new smaller path,
156// otherwise dstPath may have been changed but you should ignore it.
157static bool cull_path(const SkPath& srcPath, const SkStrokeRec& rec,
158 const SkRect* cullRect, SkScalar intervalLength, SkPath* dstPath) {
159 if (!cullRect) {
160 SkPoint pts[2];
161 if (srcPath.isLine(pts) && pts[0] == pts[1]) {
162 adjust_zero_length_line(pts);
163 dstPath->moveTo(pts[0]);
164 dstPath->lineTo(pts[1]);
165 return true;
166 }
167 return false;
168 }
169
170 SkRect bounds;
171 bounds = *cullRect;
172 outset_for_stroke(&bounds, rec);
173
174 {
175 SkPoint pts[2];
176 if (srcPath.isLine(pts)) {
177 if (clip_line(pts, bounds, intervalLength, 0)) {
178 dstPath->moveTo(pts[0]);
179 dstPath->lineTo(pts[1]);
180 return true;
181 }
182 return false;
183 }
184 }
185
186 if (srcPath.isRect(nullptr)) {
187 // We'll break the rect into four lines, culling each separately.
188 SkPath::Iter iter(srcPath, false);
189
190 SkPoint pts[4]; // Rects are all moveTo and lineTo, so we'll only use pts[0] and pts[1].
191 SkAssertResult(SkPath::kMove_Verb == iter.next(pts));
192
193 SkScalar accum = 0; // Sum of unculled edge lengths to keep the phase correct.
194 while (iter.next(pts) == SkPath::kLine_Verb) {
195 // Notice this vector v and accum work with the original unclipped length.
196 SkVector v = pts[1] - pts[0];
197
198 if (clip_line(pts, bounds, intervalLength, SkScalarMod(accum, intervalLength))) {
199 // pts[0] may have just been changed by clip_line().
200 // If that's not where we ended the previous lineTo(), we need to moveTo() there.
201 SkPoint last;
202 if (!dstPath->getLastPt(&last) || last != pts[0]) {
203 dstPath->moveTo(pts[0]);
204 }
205 dstPath->lineTo(pts[1]);
206 }
207
208 // We either just traveled v.fX horizontally or v.fY vertically.
209 SkASSERT(v.fX == 0 || v.fY == 0);
210 accum += SkScalarAbs(v.fX + v.fY);
211 }
212 return !dstPath->isEmpty();
213 }
214
215 return false;
216}
217
218class SpecialLineRec {
219public:
220 bool init(const SkPath& src, SkPath* dst, SkStrokeRec* rec,
221 int intervalCount, SkScalar intervalLength) {
222 if (rec->isHairlineStyle() || !src.isLine(fPts)) {
223 return false;
224 }
225
226 // can relax this in the future, if we handle square and round caps
227 if (SkPaint::kButt_Cap != rec->getCap()) {
228 return false;
229 }
230
231 SkScalar pathLength = SkPoint::Distance(fPts[0], fPts[1]);
232
233 fTangent = fPts[1] - fPts[0];
234 if (fTangent.isZero()) {
235 return false;
236 }
237
238 fPathLength = pathLength;
239 fTangent.scale(SkScalarInvert(pathLength));
240 SkPointPriv::RotateCCW(fTangent, &fNormal);
241 fNormal.scale(SkScalarHalf(rec->getWidth()));
242
243 // now estimate how many quads will be added to the path
244 // resulting segments = pathLen * intervalCount / intervalLen
245 // resulting points = 4 * segments
246
247 SkScalar ptCount = pathLength * intervalCount / (float)intervalLength;
248 ptCount = std::min(ptCount, SkDashPath::kMaxDashCount);
249 int n = SkScalarCeilToInt(ptCount) << 2;
250 dst->incReserve(n);
251
252 // we will take care of the stroking
253 rec->setFillStyle();
254 return true;
255 }
256
257 void addSegment(SkScalar d0, SkScalar d1, SkPath* path) const {
258 SkASSERT(d0 <= fPathLength);
259 // clamp the segment to our length
260 if (d1 > fPathLength) {
261 d1 = fPathLength;
262 }
263
264 SkScalar x0 = fPts[0].fX + fTangent.fX * d0;
265 SkScalar x1 = fPts[0].fX + fTangent.fX * d1;
266 SkScalar y0 = fPts[0].fY + fTangent.fY * d0;
267 SkScalar y1 = fPts[0].fY + fTangent.fY * d1;
268
269 SkPoint pts[4];
270 pts[0].set(x0 + fNormal.fX, y0 + fNormal.fY); // moveTo
271 pts[1].set(x1 + fNormal.fX, y1 + fNormal.fY); // lineTo
272 pts[2].set(x1 - fNormal.fX, y1 - fNormal.fY); // lineTo
273 pts[3].set(x0 - fNormal.fX, y0 - fNormal.fY); // lineTo
274
275 path->addPoly(pts, SK_ARRAY_COUNT(pts), false);
276 }
277
278private:
279 SkPoint fPts[2];
280 SkVector fTangent;
281 SkVector fNormal;
282 SkScalar fPathLength;
283};
284
285
286bool SkDashPath::InternalFilter(SkPath* dst, const SkPath& src, SkStrokeRec* rec,
287 const SkRect* cullRect, const SkScalar aIntervals[],
288 int32_t count, SkScalar initialDashLength, int32_t initialDashIndex,
289 SkScalar intervalLength,
290 StrokeRecApplication strokeRecApplication) {
291 // we must always have an even number of intervals
292 SkASSERT(is_even(count));
293
294 // we do nothing if the src wants to be filled
295 SkStrokeRec::Style style = rec->getStyle();
296 if (SkStrokeRec::kFill_Style == style || SkStrokeRec::kStrokeAndFill_Style == style) {
297 return false;
298 }
299
300 const SkScalar* intervals = aIntervals;
301 SkScalar dashCount = 0;
302 int segCount = 0;
303
304 SkPath cullPathStorage;
305 const SkPath* srcPtr = &src;
306 if (cull_path(src, *rec, cullRect, intervalLength, &cullPathStorage)) {
307 // if rect is closed, starts in a dash, and ends in a dash, add the initial join
308 // potentially a better fix is described here: bug.skia.org/7445
309 if (src.isRect(nullptr) && src.isLastContourClosed() && is_even(initialDashIndex)) {
310 SkScalar pathLength = SkPathMeasure(src, false, rec->getResScale()).getLength();
311 SkScalar endPhase = SkScalarMod(pathLength + initialDashLength, intervalLength);
312 int index = 0;
313 while (endPhase > intervals[index]) {
314 endPhase -= intervals[index++];
315 SkASSERT(index <= count);
316 if (index == count) {
317 // We have run out of intervals. endPhase "should" never get to this point,
318 // but it could if the subtracts underflowed. Hence we will pin it as if it
319 // perfectly ran through the intervals.
320 // See crbug.com/875494 (and skbug.com/8274)
321 endPhase = 0;
322 break;
323 }
324 }
325 // if dash ends inside "on", or ends at beginning of "off"
326 if (is_even(index) == (endPhase > 0)) {
327 SkPoint midPoint = src.getPoint(0);
328 // get vector at end of rect
329 int last = src.countPoints() - 1;
330 while (midPoint == src.getPoint(last)) {
331 --last;
332 SkASSERT(last >= 0);
333 }
334 // get vector at start of rect
335 int next = 1;
336 while (midPoint == src.getPoint(next)) {
337 ++next;
338 SkASSERT(next < last);
339 }
340 SkVector v = midPoint - src.getPoint(last);
341 const SkScalar kTinyOffset = SK_ScalarNearlyZero;
342 // scale vector to make start of tiny right angle
343 v *= kTinyOffset;
344 cullPathStorage.moveTo(midPoint - v);
345 cullPathStorage.lineTo(midPoint);
346 v = midPoint - src.getPoint(next);
347 // scale vector to make end of tiny right angle
348 v *= kTinyOffset;
349 cullPathStorage.lineTo(midPoint - v);
350 }
351 }
352 srcPtr = &cullPathStorage;
353 }
354
355 SpecialLineRec lineRec;
356 bool specialLine = (StrokeRecApplication::kAllow == strokeRecApplication) &&
357 lineRec.init(*srcPtr, dst, rec, count >> 1, intervalLength);
358
359 SkPathMeasure meas(*srcPtr, false, rec->getResScale());
360
361 do {
362 bool skipFirstSegment = meas.isClosed();
363 bool addedSegment = false;
364 SkScalar length = meas.getLength();
365 int index = initialDashIndex;
366
367 // Since the path length / dash length ratio may be arbitrarily large, we can exert
368 // significant memory pressure while attempting to build the filtered path. To avoid this,
369 // we simply give up dashing beyond a certain threshold.
370 //
371 // The original bug report (http://crbug.com/165432) is based on a path yielding more than
372 // 90 million dash segments and crashing the memory allocator. A limit of 1 million
373 // segments seems reasonable: at 2 verbs per segment * 9 bytes per verb, this caps the
374 // maximum dash memory overhead at roughly 17MB per path.
375 dashCount += length * (count >> 1) / intervalLength;
376 if (dashCount > kMaxDashCount) {
377 dst->reset();
378 return false;
379 }
380
381 // Using double precision to avoid looping indefinitely due to single precision rounding
382 // (for extreme path_length/dash_length ratios). See test_infinite_dash() unittest.
383 double distance = 0;
384 double dlen = initialDashLength;
385
386 while (distance < length) {
387 SkASSERT(dlen >= 0);
388 addedSegment = false;
389 if (is_even(index) && !skipFirstSegment) {
390 addedSegment = true;
391 ++segCount;
392
393 if (specialLine) {
394 lineRec.addSegment(SkDoubleToScalar(distance),
395 SkDoubleToScalar(distance + dlen),
396 dst);
397 } else {
398 meas.getSegment(SkDoubleToScalar(distance),
399 SkDoubleToScalar(distance + dlen),
400 dst, true);
401 }
402 }
403 distance += dlen;
404
405 // clear this so we only respect it the first time around
406 skipFirstSegment = false;
407
408 // wrap around our intervals array if necessary
409 index += 1;
410 SkASSERT(index <= count);
411 if (index == count) {
412 index = 0;
413 }
414
415 // fetch our next dlen
416 dlen = intervals[index];
417 }
418
419 // extend if we ended on a segment and we need to join up with the (skipped) initial segment
420 if (meas.isClosed() && is_even(initialDashIndex) &&
421 initialDashLength >= 0) {
422 meas.getSegment(0, initialDashLength, dst, !addedSegment);
423 ++segCount;
424 }
425 } while (meas.nextContour());
426
427 if (segCount > 1) {
428 dst->setConvexityType(SkPathConvexityType::kConcave);
429 }
430
431 return true;
432}
433
434bool SkDashPath::FilterDashPath(SkPath* dst, const SkPath& src, SkStrokeRec* rec,
435 const SkRect* cullRect, const SkPathEffect::DashInfo& info) {
436 if (!ValidDashPath(info.fPhase, info.fIntervals, info.fCount)) {
437 return false;
438 }
439 SkScalar initialDashLength = 0;
440 int32_t initialDashIndex = 0;
441 SkScalar intervalLength = 0;
442 CalcDashParameters(info.fPhase, info.fIntervals, info.fCount,
443 &initialDashLength, &initialDashIndex, &intervalLength);
444 return InternalFilter(dst, src, rec, cullRect, info.fIntervals, info.fCount, initialDashLength,
445 initialDashIndex, intervalLength);
446}
447
448bool SkDashPath::ValidDashPath(SkScalar phase, const SkScalar intervals[], int32_t count) {
449 if (count < 2 || !SkIsAlign2(count)) {
450 return false;
451 }
452 SkScalar length = 0;
453 for (int i = 0; i < count; i++) {
454 if (intervals[i] < 0) {
455 return false;
456 }
457 length += intervals[i];
458 }
459 // watch out for values that might make us go out of bounds
460 return length > 0 && SkScalarIsFinite(phase) && SkScalarIsFinite(length);
461}
462