Line data Source code
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 "SkStrokeRec.h"
11 :
12 0 : static inline int is_even(int x) {
13 0 : return !(x & 1);
14 : }
15 :
16 0 : static SkScalar find_first_interval(const SkScalar intervals[], SkScalar phase,
17 : int32_t* index, int count) {
18 0 : for (int i = 0; i < count; ++i) {
19 0 : SkScalar gap = intervals[i];
20 0 : if (phase > gap || (phase == gap && gap)) {
21 0 : phase -= gap;
22 : } else {
23 0 : *index = i;
24 0 : return gap - phase;
25 : }
26 : }
27 : // If we get here, phase "appears" to be larger than our length. This
28 : // shouldn't happen with perfect precision, but we can accumulate errors
29 : // during the initial length computation (rounding can make our sum be too
30 : // big or too small. In that event, we just have to eat the error here.
31 0 : *index = 0;
32 0 : return intervals[0];
33 : }
34 :
35 0 : void SkDashPath::CalcDashParameters(SkScalar phase, const SkScalar intervals[], int32_t count,
36 : SkScalar* initialDashLength, int32_t* initialDashIndex,
37 : SkScalar* intervalLength, SkScalar* adjustedPhase) {
38 0 : SkScalar len = 0;
39 0 : for (int i = 0; i < count; i++) {
40 0 : len += intervals[i];
41 : }
42 0 : *intervalLength = len;
43 : // Adjust phase to be between 0 and len, "flipping" phase if negative.
44 : // e.g., if len is 100, then phase of -20 (or -120) is equivalent to 80
45 0 : if (adjustedPhase) {
46 0 : if (phase < 0) {
47 0 : phase = -phase;
48 0 : if (phase > len) {
49 0 : phase = SkScalarMod(phase, len);
50 : }
51 0 : phase = len - phase;
52 :
53 : // Due to finite precision, it's possible that phase == len,
54 : // even after the subtract (if len >>> phase), so fix that here.
55 : // This fixes http://crbug.com/124652 .
56 0 : SkASSERT(phase <= len);
57 0 : if (phase == len) {
58 0 : phase = 0;
59 : }
60 0 : } else if (phase >= len) {
61 0 : phase = SkScalarMod(phase, len);
62 : }
63 0 : *adjustedPhase = phase;
64 : }
65 0 : SkASSERT(phase >= 0 && phase < len);
66 :
67 0 : *initialDashLength = find_first_interval(intervals, phase,
68 : initialDashIndex, count);
69 :
70 0 : SkASSERT(*initialDashLength >= 0);
71 0 : SkASSERT(*initialDashIndex >= 0 && *initialDashIndex < count);
72 0 : }
73 :
74 0 : static void outset_for_stroke(SkRect* rect, const SkStrokeRec& rec) {
75 0 : SkScalar radius = SkScalarHalf(rec.getWidth());
76 0 : if (0 == radius) {
77 0 : radius = SK_Scalar1; // hairlines
78 : }
79 0 : if (SkPaint::kMiter_Join == rec.getJoin()) {
80 0 : radius *= rec.getMiter();
81 : }
82 0 : rect->outset(radius, radius);
83 0 : }
84 :
85 : // Only handles lines for now. If returns true, dstPath is the new (smaller)
86 : // path. If returns false, then dstPath parameter is ignored.
87 0 : static bool cull_path(const SkPath& srcPath, const SkStrokeRec& rec,
88 : const SkRect* cullRect, SkScalar intervalLength,
89 : SkPath* dstPath) {
90 0 : if (nullptr == cullRect) {
91 0 : return false;
92 : }
93 :
94 : SkPoint pts[2];
95 0 : if (!srcPath.isLine(pts)) {
96 0 : return false;
97 : }
98 :
99 0 : SkRect bounds = *cullRect;
100 0 : outset_for_stroke(&bounds, rec);
101 :
102 0 : SkScalar dx = pts[1].x() - pts[0].x();
103 0 : SkScalar dy = pts[1].y() - pts[0].y();
104 :
105 : // just do horizontal lines for now (lazy)
106 0 : if (dy) {
107 0 : return false;
108 : }
109 :
110 0 : SkScalar minX = pts[0].fX;
111 0 : SkScalar maxX = pts[1].fX;
112 :
113 0 : if (dx < 0) {
114 0 : SkTSwap(minX, maxX);
115 : }
116 :
117 0 : SkASSERT(minX <= maxX);
118 0 : if (maxX < bounds.fLeft || minX > bounds.fRight) {
119 0 : 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 0 : if (minX < bounds.fLeft) {
127 0 : minX = bounds.fLeft - SkScalarMod(bounds.fLeft - minX,
128 : intervalLength);
129 : }
130 0 : if (maxX > bounds.fRight) {
131 0 : maxX = bounds.fRight + SkScalarMod(maxX - bounds.fRight,
132 : intervalLength);
133 : }
134 :
135 0 : SkASSERT(maxX >= minX);
136 0 : if (dx < 0) {
137 0 : SkTSwap(minX, maxX);
138 : }
139 0 : pts[0].fX = minX;
140 0 : pts[1].fX = maxX;
141 :
142 0 : dstPath->moveTo(pts[0]);
143 0 : dstPath->lineTo(pts[1]);
144 0 : return true;
145 : }
146 :
147 : class SpecialLineRec {
148 : public:
149 0 : bool init(const SkPath& src, SkPath* dst, SkStrokeRec* rec,
150 : int intervalCount, SkScalar intervalLength) {
151 0 : if (rec->isHairlineStyle() || !src.isLine(fPts)) {
152 0 : return false;
153 : }
154 :
155 : // can relax this in the future, if we handle square and round caps
156 0 : if (SkPaint::kButt_Cap != rec->getCap()) {
157 0 : return false;
158 : }
159 :
160 0 : SkScalar pathLength = SkPoint::Distance(fPts[0], fPts[1]);
161 :
162 0 : fTangent = fPts[1] - fPts[0];
163 0 : if (fTangent.isZero()) {
164 0 : return false;
165 : }
166 :
167 0 : fPathLength = pathLength;
168 0 : fTangent.scale(SkScalarInvert(pathLength));
169 0 : fTangent.rotateCCW(&fNormal);
170 0 : fNormal.scale(SkScalarHalf(rec->getWidth()));
171 :
172 : // now estimate how many quads will be added to the path
173 : // resulting segments = pathLen * intervalCount / intervalLen
174 : // resulting points = 4 * segments
175 :
176 0 : SkScalar ptCount = pathLength * intervalCount / (float)intervalLength;
177 0 : ptCount = SkTMin(ptCount, SkDashPath::kMaxDashCount);
178 0 : int n = SkScalarCeilToInt(ptCount) << 2;
179 0 : dst->incReserve(n);
180 :
181 : // we will take care of the stroking
182 0 : rec->setFillStyle();
183 0 : return true;
184 : }
185 :
186 0 : void addSegment(SkScalar d0, SkScalar d1, SkPath* path) const {
187 0 : SkASSERT(d0 <= fPathLength);
188 : // clamp the segment to our length
189 0 : if (d1 > fPathLength) {
190 0 : d1 = fPathLength;
191 : }
192 :
193 0 : SkScalar x0 = fPts[0].fX + fTangent.fX * d0;
194 0 : SkScalar x1 = fPts[0].fX + fTangent.fX * d1;
195 0 : SkScalar y0 = fPts[0].fY + fTangent.fY * d0;
196 0 : SkScalar y1 = fPts[0].fY + fTangent.fY * d1;
197 :
198 : SkPoint pts[4];
199 0 : pts[0].set(x0 + fNormal.fX, y0 + fNormal.fY); // moveTo
200 0 : pts[1].set(x1 + fNormal.fX, y1 + fNormal.fY); // lineTo
201 0 : pts[2].set(x1 - fNormal.fX, y1 - fNormal.fY); // lineTo
202 0 : pts[3].set(x0 - fNormal.fX, y0 - fNormal.fY); // lineTo
203 :
204 0 : path->addPoly(pts, SK_ARRAY_COUNT(pts), false);
205 0 : }
206 :
207 : private:
208 : SkPoint fPts[2];
209 : SkVector fTangent;
210 : SkVector fNormal;
211 : SkScalar fPathLength;
212 : };
213 :
214 :
215 0 : bool SkDashPath::InternalFilter(SkPath* dst, const SkPath& src, SkStrokeRec* rec,
216 : const SkRect* cullRect, const SkScalar aIntervals[],
217 : int32_t count, SkScalar initialDashLength, int32_t initialDashIndex,
218 : SkScalar intervalLength,
219 : StrokeRecApplication strokeRecApplication) {
220 :
221 : // we do nothing if the src wants to be filled
222 0 : SkStrokeRec::Style style = rec->getStyle();
223 0 : if (SkStrokeRec::kFill_Style == style || SkStrokeRec::kStrokeAndFill_Style == style) {
224 0 : return false;
225 : }
226 :
227 0 : const SkScalar* intervals = aIntervals;
228 0 : SkScalar dashCount = 0;
229 0 : int segCount = 0;
230 :
231 0 : SkPath cullPathStorage;
232 0 : const SkPath* srcPtr = &src;
233 0 : if (cull_path(src, *rec, cullRect, intervalLength, &cullPathStorage)) {
234 0 : srcPtr = &cullPathStorage;
235 : }
236 :
237 : SpecialLineRec lineRec;
238 0 : bool specialLine = (StrokeRecApplication::kAllow == strokeRecApplication) &&
239 0 : lineRec.init(*srcPtr, dst, rec, count >> 1, intervalLength);
240 :
241 0 : SkPathMeasure meas(*srcPtr, false, rec->getResScale());
242 :
243 0 : do {
244 0 : bool skipFirstSegment = meas.isClosed();
245 0 : bool addedSegment = false;
246 0 : SkScalar length = meas.getLength();
247 0 : int index = initialDashIndex;
248 :
249 : // Since the path length / dash length ratio may be arbitrarily large, we can exert
250 : // significant memory pressure while attempting to build the filtered path. To avoid this,
251 : // we simply give up dashing beyond a certain threshold.
252 : //
253 : // The original bug report (http://crbug.com/165432) is based on a path yielding more than
254 : // 90 million dash segments and crashing the memory allocator. A limit of 1 million
255 : // segments seems reasonable: at 2 verbs per segment * 9 bytes per verb, this caps the
256 : // maximum dash memory overhead at roughly 17MB per path.
257 0 : dashCount += length * (count >> 1) / intervalLength;
258 0 : if (dashCount > kMaxDashCount) {
259 0 : dst->reset();
260 0 : return false;
261 : }
262 :
263 : // Using double precision to avoid looping indefinitely due to single precision rounding
264 : // (for extreme path_length/dash_length ratios). See test_infinite_dash() unittest.
265 0 : double distance = 0;
266 0 : double dlen = initialDashLength;
267 :
268 0 : while (distance < length) {
269 0 : SkASSERT(dlen >= 0);
270 0 : addedSegment = false;
271 0 : if (is_even(index) && !skipFirstSegment) {
272 0 : addedSegment = true;
273 0 : ++segCount;
274 :
275 0 : if (specialLine) {
276 0 : lineRec.addSegment(SkDoubleToScalar(distance),
277 0 : SkDoubleToScalar(distance + dlen),
278 0 : dst);
279 : } else {
280 0 : meas.getSegment(SkDoubleToScalar(distance),
281 0 : SkDoubleToScalar(distance + dlen),
282 0 : dst, true);
283 : }
284 : }
285 0 : distance += dlen;
286 :
287 : // clear this so we only respect it the first time around
288 0 : skipFirstSegment = false;
289 :
290 : // wrap around our intervals array if necessary
291 0 : index += 1;
292 0 : SkASSERT(index <= count);
293 0 : if (index == count) {
294 0 : index = 0;
295 : }
296 :
297 : // fetch our next dlen
298 0 : dlen = intervals[index];
299 : }
300 :
301 : // extend if we ended on a segment and we need to join up with the (skipped) initial segment
302 0 : if (meas.isClosed() && is_even(initialDashIndex) &&
303 : initialDashLength >= 0) {
304 0 : meas.getSegment(0, initialDashLength, dst, !addedSegment);
305 0 : ++segCount;
306 : }
307 : } while (meas.nextContour());
308 :
309 0 : if (segCount > 1) {
310 0 : dst->setConvexity(SkPath::kConcave_Convexity);
311 : }
312 :
313 0 : return true;
314 : }
315 :
316 0 : bool SkDashPath::FilterDashPath(SkPath* dst, const SkPath& src, SkStrokeRec* rec,
317 : const SkRect* cullRect, const SkPathEffect::DashInfo& info) {
318 0 : if (!ValidDashPath(info.fPhase, info.fIntervals, info.fCount)) {
319 0 : return false;
320 : }
321 0 : SkScalar initialDashLength = 0;
322 0 : int32_t initialDashIndex = 0;
323 0 : SkScalar intervalLength = 0;
324 0 : CalcDashParameters(info.fPhase, info.fIntervals, info.fCount,
325 0 : &initialDashLength, &initialDashIndex, &intervalLength);
326 0 : return InternalFilter(dst, src, rec, cullRect, info.fIntervals, info.fCount, initialDashLength,
327 0 : initialDashIndex, intervalLength);
328 : }
329 :
330 0 : bool SkDashPath::ValidDashPath(SkScalar phase, const SkScalar intervals[], int32_t count) {
331 0 : if (count < 2 || !SkIsAlign2(count)) {
332 0 : return false;
333 : }
334 0 : SkScalar length = 0;
335 0 : for (int i = 0; i < count; i++) {
336 0 : if (intervals[i] < 0) {
337 0 : return false;
338 : }
339 0 : length += intervals[i];
340 : }
341 : // watch out for values that might make us go out of bounds
342 0 : return length > 0 && SkScalarIsFinite(phase) && SkScalarIsFinite(length);
343 : }
|
