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