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