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