• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright 2008 The Android Open Source Project
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 "SkStrokerPriv.h"
9 #include "SkGeometry.h"
10 #include "SkPathPriv.h"
11 
12 enum {
13     kTangent_RecursiveLimit,
14     kCubic_RecursiveLimit,
15     kConic_RecursiveLimit,
16     kQuad_RecursiveLimit
17 };
18 
19 // quads with extreme widths (e.g. (0,1) (1,6) (0,3) width=5e7) recurse to point of failure
20 // largest seen for normal cubics : 5, 26
21 // largest seen for normal quads : 11
22 static const int kRecursiveLimits[] = { 5*3, 26*3, 11*3, 11*3 }; // 3x limits seen in practice
23 
24 static_assert(0 == kTangent_RecursiveLimit, "cubic_stroke_relies_on_tangent_equalling_zero");
25 static_assert(1 == kCubic_RecursiveLimit, "cubic_stroke_relies_on_cubic_equalling_one");
26 static_assert(SK_ARRAY_COUNT(kRecursiveLimits) == kQuad_RecursiveLimit + 1,
27               "recursive_limits_mismatch");
28 
29 #ifdef SK_DEBUG
30     int gMaxRecursion[SK_ARRAY_COUNT(kRecursiveLimits)] = { 0 };
31 #endif
32 #ifndef DEBUG_QUAD_STROKER
33     #define DEBUG_QUAD_STROKER 0
34 #endif
35 
36 #if DEBUG_QUAD_STROKER
37     /* Enable to show the decisions made in subdividing the curve -- helpful when the resulting
38         stroke has more than the optimal number of quadratics and lines */
39     #define STROKER_RESULT(resultType, depth, quadPts, format, ...) \
40             SkDebugf("[%d] %s " format "\n", depth, __FUNCTION__, __VA_ARGS__), \
41             SkDebugf("  " #resultType " t=(%g,%g)\n", quadPts->fStartT, quadPts->fEndT), \
42             resultType
43     #define STROKER_DEBUG_PARAMS(...) , __VA_ARGS__
44 #else
45     #define STROKER_RESULT(resultType, depth, quadPts, format, ...) \
46             resultType
47     #define STROKER_DEBUG_PARAMS(...)
48 #endif
49 
degenerate_vector(const SkVector & v)50 static inline bool degenerate_vector(const SkVector& v) {
51     return !SkPoint::CanNormalize(v.fX, v.fY);
52 }
53 
set_normal_unitnormal(const SkPoint & before,const SkPoint & after,SkScalar scale,SkScalar radius,SkVector * normal,SkVector * unitNormal)54 static bool set_normal_unitnormal(const SkPoint& before, const SkPoint& after, SkScalar scale,
55                                   SkScalar radius,
56                                   SkVector* normal, SkVector* unitNormal) {
57     if (!unitNormal->setNormalize((after.fX - before.fX) * scale,
58                                   (after.fY - before.fY) * scale)) {
59         return false;
60     }
61     unitNormal->rotateCCW();
62     unitNormal->scale(radius, normal);
63     return true;
64 }
65 
set_normal_unitnormal(const SkVector & vec,SkScalar radius,SkVector * normal,SkVector * unitNormal)66 static bool set_normal_unitnormal(const SkVector& vec,
67                                   SkScalar radius,
68                                   SkVector* normal, SkVector* unitNormal) {
69     if (!unitNormal->setNormalize(vec.fX, vec.fY)) {
70         return false;
71     }
72     unitNormal->rotateCCW();
73     unitNormal->scale(radius, normal);
74     return true;
75 }
76 
77 ///////////////////////////////////////////////////////////////////////////////
78 
79 struct SkQuadConstruct {    // The state of the quad stroke under construction.
80     SkPoint fQuad[3];       // the stroked quad parallel to the original curve
81     SkPoint fTangentStart;  // a point tangent to fQuad[0]
82     SkPoint fTangentEnd;    // a point tangent to fQuad[2]
83     SkScalar fStartT;       // a segment of the original curve
84     SkScalar fMidT;         //              "
85     SkScalar fEndT;         //              "
86     bool fStartSet;         // state to share common points across structs
87     bool fEndSet;           //                     "
88     bool fOppositeTangents; // set if coincident tangents have opposite directions
89 
90     // return false if start and end are too close to have a unique middle
initSkQuadConstruct91     bool init(SkScalar start, SkScalar end) {
92         fStartT = start;
93         fMidT = (start + end) * SK_ScalarHalf;
94         fEndT = end;
95         fStartSet = fEndSet = false;
96         return fStartT < fMidT && fMidT < fEndT;
97     }
98 
initWithStartSkQuadConstruct99     bool initWithStart(SkQuadConstruct* parent) {
100         if (!init(parent->fStartT, parent->fMidT)) {
101             return false;
102         }
103         fQuad[0] = parent->fQuad[0];
104         fTangentStart = parent->fTangentStart;
105         fStartSet = true;
106         return true;
107     }
108 
initWithEndSkQuadConstruct109     bool initWithEnd(SkQuadConstruct* parent) {
110         if (!init(parent->fMidT, parent->fEndT)) {
111             return false;
112         }
113         fQuad[2] = parent->fQuad[2];
114         fTangentEnd = parent->fTangentEnd;
115         fEndSet = true;
116         return true;
117    }
118 };
119 
120 class SkPathStroker {
121 public:
122     SkPathStroker(const SkPath& src,
123                   SkScalar radius, SkScalar miterLimit, SkPaint::Cap,
124                   SkPaint::Join, SkScalar resScale,
125                   bool canIgnoreCenter);
126 
hasOnlyMoveTo() const127     bool hasOnlyMoveTo() const { return 0 == fSegmentCount; }
moveToPt() const128     SkPoint moveToPt() const { return fFirstPt; }
129 
130     void moveTo(const SkPoint&);
131     void lineTo(const SkPoint&, const SkPath::Iter* iter = nullptr);
132     void quadTo(const SkPoint&, const SkPoint&);
133     void conicTo(const SkPoint&, const SkPoint&, SkScalar weight);
134     void cubicTo(const SkPoint&, const SkPoint&, const SkPoint&);
close(bool isLine)135     void close(bool isLine) { this->finishContour(true, isLine); }
136 
done(SkPath * dst,bool isLine)137     void done(SkPath* dst, bool isLine) {
138         this->finishContour(false, isLine);
139         dst->swap(fOuter);
140     }
141 
getResScale() const142     SkScalar getResScale() const { return fResScale; }
143 
isCurrentContourEmpty() const144     bool isCurrentContourEmpty() const {
145         return fInner.isZeroLengthSincePoint(0) &&
146                fOuter.isZeroLengthSincePoint(fFirstOuterPtIndexInContour);
147     }
148 
149 private:
150     SkScalar    fRadius;
151     SkScalar    fInvMiterLimit;
152     SkScalar    fResScale;
153     SkScalar    fInvResScale;
154     SkScalar    fInvResScaleSquared;
155 
156     SkVector    fFirstNormal, fPrevNormal, fFirstUnitNormal, fPrevUnitNormal;
157     SkPoint     fFirstPt, fPrevPt;  // on original path
158     SkPoint     fFirstOuterPt;
159     int         fFirstOuterPtIndexInContour;
160     int         fSegmentCount;
161     bool        fPrevIsLine;
162     bool        fCanIgnoreCenter;
163 
164     SkStrokerPriv::CapProc  fCapper;
165     SkStrokerPriv::JoinProc fJoiner;
166 
167     SkPath  fInner, fOuter; // outer is our working answer, inner is temp
168 
169     enum StrokeType {
170         kOuter_StrokeType = 1,      // use sign-opposite values later to flip perpendicular axis
171         kInner_StrokeType = -1
172     } fStrokeType;
173 
174     enum ResultType {
175         kSplit_ResultType,          // the caller should split the quad stroke in two
176         kDegenerate_ResultType,     // the caller should add a line
177         kQuad_ResultType,           // the caller should (continue to try to) add a quad stroke
178     };
179 
180     enum ReductionType {
181         kPoint_ReductionType,       // all curve points are practically identical
182         kLine_ReductionType,        // the control point is on the line between the ends
183         kQuad_ReductionType,        // the control point is outside the line between the ends
184         kDegenerate_ReductionType,  // the control point is on the line but outside the ends
185         kDegenerate2_ReductionType, // two control points are on the line but outside ends (cubic)
186         kDegenerate3_ReductionType, // three areas of max curvature found (for cubic)
187     };
188 
189     enum IntersectRayType {
190         kCtrlPt_RayType,
191         kResultType_RayType,
192     };
193 
194     int fRecursionDepth;            // track stack depth to abort if numerics run amok
195     bool fFoundTangents;            // do less work until tangents meet (cubic)
196     bool fJoinCompleted;            // previous join was not degenerate
197 
198     void addDegenerateLine(const SkQuadConstruct* );
199     static ReductionType CheckConicLinear(const SkConic& , SkPoint* reduction);
200     static ReductionType CheckCubicLinear(const SkPoint cubic[4], SkPoint reduction[3],
201                                    const SkPoint** tanPtPtr);
202     static ReductionType CheckQuadLinear(const SkPoint quad[3], SkPoint* reduction);
203     ResultType compareQuadConic(const SkConic& , SkQuadConstruct* ) const;
204     ResultType compareQuadCubic(const SkPoint cubic[4], SkQuadConstruct* );
205     ResultType compareQuadQuad(const SkPoint quad[3], SkQuadConstruct* );
206     void conicPerpRay(const SkConic& , SkScalar t, SkPoint* tPt, SkPoint* onPt,
207                       SkPoint* tangent) const;
208     void conicQuadEnds(const SkConic& , SkQuadConstruct* ) const;
209     bool conicStroke(const SkConic& , SkQuadConstruct* );
210     bool cubicMidOnLine(const SkPoint cubic[4], const SkQuadConstruct* ) const;
211     void cubicPerpRay(const SkPoint cubic[4], SkScalar t, SkPoint* tPt, SkPoint* onPt,
212                       SkPoint* tangent) const;
213     void cubicQuadEnds(const SkPoint cubic[4], SkQuadConstruct* );
214     void cubicQuadMid(const SkPoint cubic[4], const SkQuadConstruct* , SkPoint* mid) const;
215     bool cubicStroke(const SkPoint cubic[4], SkQuadConstruct* );
216     void init(StrokeType strokeType, SkQuadConstruct* , SkScalar tStart, SkScalar tEnd);
217     ResultType intersectRay(SkQuadConstruct* , IntersectRayType  STROKER_DEBUG_PARAMS(int) ) const;
218     bool ptInQuadBounds(const SkPoint quad[3], const SkPoint& pt) const;
219     void quadPerpRay(const SkPoint quad[3], SkScalar t, SkPoint* tPt, SkPoint* onPt,
220                      SkPoint* tangent) const;
221     bool quadStroke(const SkPoint quad[3], SkQuadConstruct* );
222     void setConicEndNormal(const SkConic& ,
223                            const SkVector& normalAB, const SkVector& unitNormalAB,
224                            SkVector* normalBC, SkVector* unitNormalBC);
225     void setCubicEndNormal(const SkPoint cubic[4],
226                            const SkVector& normalAB, const SkVector& unitNormalAB,
227                            SkVector* normalCD, SkVector* unitNormalCD);
228     void setQuadEndNormal(const SkPoint quad[3],
229                           const SkVector& normalAB, const SkVector& unitNormalAB,
230                           SkVector* normalBC, SkVector* unitNormalBC);
231     void setRayPts(const SkPoint& tPt, SkVector* dxy, SkPoint* onPt, SkPoint* tangent) const;
232     static bool SlightAngle(SkQuadConstruct* );
233     ResultType strokeCloseEnough(const SkPoint stroke[3], const SkPoint ray[2],
234                                  SkQuadConstruct*  STROKER_DEBUG_PARAMS(int depth) ) const;
235     ResultType tangentsMeet(const SkPoint cubic[4], SkQuadConstruct* );
236 
237     void    finishContour(bool close, bool isLine);
238     bool    preJoinTo(const SkPoint&, SkVector* normal, SkVector* unitNormal,
239                       bool isLine);
240     void    postJoinTo(const SkPoint&, const SkVector& normal,
241                        const SkVector& unitNormal);
242 
243     void    line_to(const SkPoint& currPt, const SkVector& normal);
244 };
245 
246 ///////////////////////////////////////////////////////////////////////////////
247 
preJoinTo(const SkPoint & currPt,SkVector * normal,SkVector * unitNormal,bool currIsLine)248 bool SkPathStroker::preJoinTo(const SkPoint& currPt, SkVector* normal,
249                               SkVector* unitNormal, bool currIsLine) {
250     SkASSERT(fSegmentCount >= 0);
251 
252     SkScalar    prevX = fPrevPt.fX;
253     SkScalar    prevY = fPrevPt.fY;
254 
255     if (!set_normal_unitnormal(fPrevPt, currPt, fResScale, fRadius, normal, unitNormal)) {
256         if (SkStrokerPriv::CapFactory(SkPaint::kButt_Cap) == fCapper) {
257             return false;
258         }
259         /* Square caps and round caps draw even if the segment length is zero.
260            Since the zero length segment has no direction, set the orientation
261            to upright as the default orientation */
262         normal->set(fRadius, 0);
263         unitNormal->set(1, 0);
264     }
265 
266     if (fSegmentCount == 0) {
267         fFirstNormal = *normal;
268         fFirstUnitNormal = *unitNormal;
269         fFirstOuterPt.set(prevX + normal->fX, prevY + normal->fY);
270 
271         fOuter.moveTo(fFirstOuterPt.fX, fFirstOuterPt.fY);
272         fInner.moveTo(prevX - normal->fX, prevY - normal->fY);
273     } else {    // we have a previous segment
274         fJoiner(&fOuter, &fInner, fPrevUnitNormal, fPrevPt, *unitNormal,
275                 fRadius, fInvMiterLimit, fPrevIsLine, currIsLine);
276     }
277     fPrevIsLine = currIsLine;
278     return true;
279 }
280 
postJoinTo(const SkPoint & currPt,const SkVector & normal,const SkVector & unitNormal)281 void SkPathStroker::postJoinTo(const SkPoint& currPt, const SkVector& normal,
282                                const SkVector& unitNormal) {
283     fJoinCompleted = true;
284     fPrevPt = currPt;
285     fPrevUnitNormal = unitNormal;
286     fPrevNormal = normal;
287     fSegmentCount += 1;
288 }
289 
finishContour(bool close,bool currIsLine)290 void SkPathStroker::finishContour(bool close, bool currIsLine) {
291     if (fSegmentCount > 0) {
292         SkPoint pt;
293 
294         if (close) {
295             fJoiner(&fOuter, &fInner, fPrevUnitNormal, fPrevPt,
296                     fFirstUnitNormal, fRadius, fInvMiterLimit,
297                     fPrevIsLine, currIsLine);
298             fOuter.close();
299 
300             if (fCanIgnoreCenter) {
301                 if (!fOuter.getBounds().contains(fInner.getBounds())) {
302                     SkASSERT(fInner.getBounds().contains(fOuter.getBounds()));
303                     fInner.swap(fOuter);
304                 }
305             } else {
306                 // now add fInner as its own contour
307                 fInner.getLastPt(&pt);
308                 fOuter.moveTo(pt.fX, pt.fY);
309                 fOuter.reversePathTo(fInner);
310                 fOuter.close();
311             }
312         } else {    // add caps to start and end
313             // cap the end
314             fInner.getLastPt(&pt);
315             fCapper(&fOuter, fPrevPt, fPrevNormal, pt,
316                     currIsLine ? &fInner : nullptr);
317             fOuter.reversePathTo(fInner);
318             // cap the start
319             fCapper(&fOuter, fFirstPt, -fFirstNormal, fFirstOuterPt,
320                     fPrevIsLine ? &fInner : nullptr);
321             fOuter.close();
322         }
323     }
324     // since we may re-use fInner, we rewind instead of reset, to save on
325     // reallocating its internal storage.
326     fInner.rewind();
327     fSegmentCount = -1;
328     fFirstOuterPtIndexInContour = fOuter.countPoints();
329 }
330 
331 ///////////////////////////////////////////////////////////////////////////////
332 
SkPathStroker(const SkPath & src,SkScalar radius,SkScalar miterLimit,SkPaint::Cap cap,SkPaint::Join join,SkScalar resScale,bool canIgnoreCenter)333 SkPathStroker::SkPathStroker(const SkPath& src,
334                              SkScalar radius, SkScalar miterLimit,
335                              SkPaint::Cap cap, SkPaint::Join join, SkScalar resScale,
336                              bool canIgnoreCenter)
337         : fRadius(radius)
338         , fResScale(resScale)
339         , fCanIgnoreCenter(canIgnoreCenter) {
340 
341     /*  This is only used when join is miter_join, but we initialize it here
342         so that it is always defined, to fis valgrind warnings.
343     */
344     fInvMiterLimit = 0;
345 
346     if (join == SkPaint::kMiter_Join) {
347         if (miterLimit <= SK_Scalar1) {
348             join = SkPaint::kBevel_Join;
349         } else {
350             fInvMiterLimit = SkScalarInvert(miterLimit);
351         }
352     }
353     fCapper = SkStrokerPriv::CapFactory(cap);
354     fJoiner = SkStrokerPriv::JoinFactory(join);
355     fSegmentCount = -1;
356     fFirstOuterPtIndexInContour = 0;
357     fPrevIsLine = false;
358 
359     // Need some estimate of how large our final result (fOuter)
360     // and our per-contour temp (fInner) will be, so we don't spend
361     // extra time repeatedly growing these arrays.
362     //
363     // 3x for result == inner + outer + join (swag)
364     // 1x for inner == 'wag' (worst contour length would be better guess)
365     fOuter.incReserve(src.countPoints() * 3);
366     fOuter.setIsVolatile(true);
367     fInner.incReserve(src.countPoints());
368     fInner.setIsVolatile(true);
369     // TODO : write a common error function used by stroking and filling
370     // The '4' below matches the fill scan converter's error term
371     fInvResScale = SkScalarInvert(resScale * 4);
372     fInvResScaleSquared = fInvResScale * fInvResScale;
373     fRecursionDepth = 0;
374 }
375 
moveTo(const SkPoint & pt)376 void SkPathStroker::moveTo(const SkPoint& pt) {
377     if (fSegmentCount > 0) {
378         this->finishContour(false, false);
379     }
380     fSegmentCount = 0;
381     fFirstPt = fPrevPt = pt;
382     fJoinCompleted = false;
383 }
384 
line_to(const SkPoint & currPt,const SkVector & normal)385 void SkPathStroker::line_to(const SkPoint& currPt, const SkVector& normal) {
386     fOuter.lineTo(currPt.fX + normal.fX, currPt.fY + normal.fY);
387     fInner.lineTo(currPt.fX - normal.fX, currPt.fY - normal.fY);
388 }
389 
has_valid_tangent(const SkPath::Iter * iter)390 static bool has_valid_tangent(const SkPath::Iter* iter) {
391     SkPath::Iter copy = *iter;
392     SkPath::Verb verb;
393     SkPoint pts[4];
394     while ((verb = copy.next(pts))) {
395         switch (verb) {
396             case SkPath::kMove_Verb:
397                 return false;
398             case SkPath::kLine_Verb:
399                 if (pts[0] == pts[1]) {
400                     continue;
401                 }
402                 return true;
403             case SkPath::kQuad_Verb:
404             case SkPath::kConic_Verb:
405                 if (pts[0] == pts[1] && pts[0] == pts[2]) {
406                     continue;
407                 }
408                 return true;
409             case SkPath::kCubic_Verb:
410                 if (pts[0] == pts[1] && pts[0] == pts[2] && pts[0] == pts[3]) {
411                     continue;
412                 }
413                 return true;
414             case SkPath::kClose_Verb:
415             case SkPath::kDone_Verb:
416                 return false;
417         }
418     }
419     return false;
420 }
421 
lineTo(const SkPoint & currPt,const SkPath::Iter * iter)422 void SkPathStroker::lineTo(const SkPoint& currPt, const SkPath::Iter* iter) {
423     bool teenyLine = fPrevPt.equalsWithinTolerance(currPt, SK_ScalarNearlyZero * fInvResScale);
424     if (SkStrokerPriv::CapFactory(SkPaint::kButt_Cap) == fCapper && teenyLine) {
425         return;
426     }
427     if (teenyLine && (fJoinCompleted || (iter && has_valid_tangent(iter)))) {
428         return;
429     }
430     SkVector    normal, unitNormal;
431 
432     if (!this->preJoinTo(currPt, &normal, &unitNormal, true)) {
433         return;
434     }
435     this->line_to(currPt, normal);
436     this->postJoinTo(currPt, normal, unitNormal);
437 }
438 
setQuadEndNormal(const SkPoint quad[3],const SkVector & normalAB,const SkVector & unitNormalAB,SkVector * normalBC,SkVector * unitNormalBC)439 void SkPathStroker::setQuadEndNormal(const SkPoint quad[3], const SkVector& normalAB,
440         const SkVector& unitNormalAB, SkVector* normalBC, SkVector* unitNormalBC) {
441     if (!set_normal_unitnormal(quad[1], quad[2], fResScale, fRadius, normalBC, unitNormalBC)) {
442         *normalBC = normalAB;
443         *unitNormalBC = unitNormalAB;
444     }
445 }
446 
setConicEndNormal(const SkConic & conic,const SkVector & normalAB,const SkVector & unitNormalAB,SkVector * normalBC,SkVector * unitNormalBC)447 void SkPathStroker::setConicEndNormal(const SkConic& conic, const SkVector& normalAB,
448         const SkVector& unitNormalAB, SkVector* normalBC, SkVector* unitNormalBC) {
449     setQuadEndNormal(conic.fPts, normalAB, unitNormalAB, normalBC, unitNormalBC);
450 }
451 
setCubicEndNormal(const SkPoint cubic[4],const SkVector & normalAB,const SkVector & unitNormalAB,SkVector * normalCD,SkVector * unitNormalCD)452 void SkPathStroker::setCubicEndNormal(const SkPoint cubic[4], const SkVector& normalAB,
453         const SkVector& unitNormalAB, SkVector* normalCD, SkVector* unitNormalCD) {
454     SkVector    ab = cubic[1] - cubic[0];
455     SkVector    cd = cubic[3] - cubic[2];
456 
457     bool    degenerateAB = degenerate_vector(ab);
458     bool    degenerateCD = degenerate_vector(cd);
459 
460     if (degenerateAB && degenerateCD) {
461         goto DEGENERATE_NORMAL;
462     }
463 
464     if (degenerateAB) {
465         ab = cubic[2] - cubic[0];
466         degenerateAB = degenerate_vector(ab);
467     }
468     if (degenerateCD) {
469         cd = cubic[3] - cubic[1];
470         degenerateCD = degenerate_vector(cd);
471     }
472     if (degenerateAB || degenerateCD) {
473 DEGENERATE_NORMAL:
474         *normalCD = normalAB;
475         *unitNormalCD = unitNormalAB;
476         return;
477     }
478     SkAssertResult(set_normal_unitnormal(cd, fRadius, normalCD, unitNormalCD));
479 }
480 
init(StrokeType strokeType,SkQuadConstruct * quadPts,SkScalar tStart,SkScalar tEnd)481 void SkPathStroker::init(StrokeType strokeType, SkQuadConstruct* quadPts, SkScalar tStart,
482         SkScalar tEnd) {
483     fStrokeType = strokeType;
484     fFoundTangents = false;
485     quadPts->init(tStart, tEnd);
486 }
487 
488 // returns the distance squared from the point to the line
pt_to_line(const SkPoint & pt,const SkPoint & lineStart,const SkPoint & lineEnd)489 static SkScalar pt_to_line(const SkPoint& pt, const SkPoint& lineStart, const SkPoint& lineEnd) {
490     SkVector dxy = lineEnd - lineStart;
491     if (degenerate_vector(dxy)) {
492         return pt.distanceToSqd(lineStart);
493     }
494     SkVector ab0 = pt - lineStart;
495     SkScalar numer = dxy.dot(ab0);
496     SkScalar denom = dxy.dot(dxy);
497     SkScalar t = numer / denom;
498     SkPoint hit;
499     hit.fX = lineStart.fX * (1 - t) + lineEnd.fX * t;
500     hit.fY = lineStart.fY * (1 - t) + lineEnd.fY * t;
501     return hit.distanceToSqd(pt);
502 }
503 
504 /*  Given a cubic, determine if all four points are in a line.
505     Return true if the inner points is close to a line connecting the outermost points.
506 
507     Find the outermost point by looking for the largest difference in X or Y.
508     Given the indices of the outermost points, and that outer_1 is greater than outer_2,
509     this table shows the index of the smaller of the remaining points:
510 
511                       outer_2
512                   0    1    2    3
513       outer_1     ----------------
514          0     |  -    2    1    1
515          1     |  -    -    0    0
516          2     |  -    -    -    0
517          3     |  -    -    -    -
518 
519     If outer_1 == 0 and outer_2 == 1, the smaller of the remaining indices (2 and 3) is 2.
520 
521     This table can be collapsed to: (1 + (2 >> outer_2)) >> outer_1
522 
523     Given three indices (outer_1 outer_2 mid_1) from 0..3, the remaining index is:
524 
525                mid_2 == (outer_1 ^ outer_2 ^ mid_1)
526  */
cubic_in_line(const SkPoint cubic[4])527 static bool cubic_in_line(const SkPoint cubic[4]) {
528     SkScalar ptMax = -1;
529     int outer1 SK_INIT_TO_AVOID_WARNING;
530     int outer2 SK_INIT_TO_AVOID_WARNING;
531     for (int index = 0; index < 3; ++index) {
532         for (int inner = index + 1; inner < 4; ++inner) {
533             SkVector testDiff = cubic[inner] - cubic[index];
534             SkScalar testMax = SkTMax(SkScalarAbs(testDiff.fX), SkScalarAbs(testDiff.fY));
535             if (ptMax < testMax) {
536                 outer1 = index;
537                 outer2 = inner;
538                 ptMax = testMax;
539             }
540         }
541     }
542     SkASSERT(outer1 >= 0 && outer1 <= 2);
543     SkASSERT(outer2 >= 1 && outer2 <= 3);
544     SkASSERT(outer1 < outer2);
545     int mid1 = (1 + (2 >> outer2)) >> outer1;
546     SkASSERT(mid1 >= 0 && mid1 <= 2);
547     SkASSERT(outer1 != mid1 && outer2 != mid1);
548     int mid2 = outer1 ^ outer2 ^ mid1;
549     SkASSERT(mid2 >= 1 && mid2 <= 3);
550     SkASSERT(mid2 != outer1 && mid2 != outer2 && mid2 != mid1);
551     SkASSERT(((1 << outer1) | (1 << outer2) | (1 << mid1) | (1 << mid2)) == 0x0f);
552     SkScalar lineSlop = ptMax * ptMax * 0.00001f;  // this multiplier is pulled out of the air
553     return pt_to_line(cubic[mid1], cubic[outer1], cubic[outer2]) <= lineSlop
554             && pt_to_line(cubic[mid2], cubic[outer1], cubic[outer2]) <= lineSlop;
555 }
556 
557 /* Given quad, see if all there points are in a line.
558    Return true if the inside point is close to a line connecting the outermost points.
559 
560    Find the outermost point by looking for the largest difference in X or Y.
561    Since the XOR of the indices is 3  (0 ^ 1 ^ 2)
562    the missing index equals: outer_1 ^ outer_2 ^ 3
563  */
quad_in_line(const SkPoint quad[3])564 static bool quad_in_line(const SkPoint quad[3]) {
565     SkScalar ptMax = -1;
566     int outer1 SK_INIT_TO_AVOID_WARNING;
567     int outer2 SK_INIT_TO_AVOID_WARNING;
568     for (int index = 0; index < 2; ++index) {
569         for (int inner = index + 1; inner < 3; ++inner) {
570             SkVector testDiff = quad[inner] - quad[index];
571             SkScalar testMax = SkTMax(SkScalarAbs(testDiff.fX), SkScalarAbs(testDiff.fY));
572             if (ptMax < testMax) {
573                 outer1 = index;
574                 outer2 = inner;
575                 ptMax = testMax;
576             }
577         }
578     }
579     SkASSERT(outer1 >= 0 && outer1 <= 1);
580     SkASSERT(outer2 >= 1 && outer2 <= 2);
581     SkASSERT(outer1 < outer2);
582     int mid = outer1 ^ outer2 ^ 3;
583     SkScalar lineSlop =  ptMax * ptMax * 0.00001f;  // this multiplier is pulled out of the air
584     return pt_to_line(quad[mid], quad[outer1], quad[outer2]) <= lineSlop;
585 }
586 
conic_in_line(const SkConic & conic)587 static bool conic_in_line(const SkConic& conic) {
588     return quad_in_line(conic.fPts);
589 }
590 
CheckCubicLinear(const SkPoint cubic[4],SkPoint reduction[3],const SkPoint ** tangentPtPtr)591 SkPathStroker::ReductionType SkPathStroker::CheckCubicLinear(const SkPoint cubic[4],
592         SkPoint reduction[3], const SkPoint** tangentPtPtr) {
593     bool degenerateAB = degenerate_vector(cubic[1] - cubic[0]);
594     bool degenerateBC = degenerate_vector(cubic[2] - cubic[1]);
595     bool degenerateCD = degenerate_vector(cubic[3] - cubic[2]);
596     if (degenerateAB & degenerateBC & degenerateCD) {
597         return kPoint_ReductionType;
598     }
599     if (degenerateAB + degenerateBC + degenerateCD == 2) {
600         return kLine_ReductionType;
601     }
602     if (!cubic_in_line(cubic)) {
603         *tangentPtPtr = degenerateAB ? &cubic[2] : &cubic[1];
604         return kQuad_ReductionType;
605     }
606     SkScalar tValues[3];
607     int count = SkFindCubicMaxCurvature(cubic, tValues);
608     if (count == 0) {
609         return kLine_ReductionType;
610     }
611     int rCount = 0;
612     // Now loop over the t-values, and reject any that evaluate to either end-point
613     for (int index = 0; index < count; ++index) {
614         SkScalar t = tValues[index];
615         SkEvalCubicAt(cubic, t, &reduction[rCount], nullptr, nullptr);
616         if (reduction[rCount] != cubic[0] && reduction[rCount] != cubic[3]) {
617             ++rCount;
618         }
619     }
620     if (rCount == 0) {
621         return kLine_ReductionType;
622     }
623     static_assert(kQuad_ReductionType + 1 == kDegenerate_ReductionType, "enum_out_of_whack");
624     static_assert(kQuad_ReductionType + 2 == kDegenerate2_ReductionType, "enum_out_of_whack");
625     static_assert(kQuad_ReductionType + 3 == kDegenerate3_ReductionType, "enum_out_of_whack");
626 
627     return (ReductionType) (kQuad_ReductionType + rCount);
628 }
629 
CheckConicLinear(const SkConic & conic,SkPoint * reduction)630 SkPathStroker::ReductionType SkPathStroker::CheckConicLinear(const SkConic& conic,
631         SkPoint* reduction) {
632     bool degenerateAB = degenerate_vector(conic.fPts[1] - conic.fPts[0]);
633     bool degenerateBC = degenerate_vector(conic.fPts[2] - conic.fPts[1]);
634     if (degenerateAB & degenerateBC) {
635         return kPoint_ReductionType;
636     }
637     if (degenerateAB | degenerateBC) {
638         return kLine_ReductionType;
639     }
640     if (!conic_in_line(conic)) {
641         return kQuad_ReductionType;
642     }
643 #if 0   // once findMaxCurvature is implemented, this will be a better solution
644     SkScalar t;
645     if (!conic.findMaxCurvature(&t) || 0 == t) {
646         return kLine_ReductionType;
647     }
648 #else  // but for now, use extrema instead
649     SkScalar xT = 0, yT = 0;
650     (void) conic.findXExtrema(&xT);
651     (void) conic.findYExtrema(&yT);
652     SkScalar t = SkTMax(xT, yT);
653     if (0 == t) {
654         return kLine_ReductionType;
655     }
656 #endif
657     conic.evalAt(t, reduction, nullptr);
658     return kDegenerate_ReductionType;
659 }
660 
CheckQuadLinear(const SkPoint quad[3],SkPoint * reduction)661 SkPathStroker::ReductionType SkPathStroker::CheckQuadLinear(const SkPoint quad[3],
662         SkPoint* reduction) {
663     bool degenerateAB = degenerate_vector(quad[1] - quad[0]);
664     bool degenerateBC = degenerate_vector(quad[2] - quad[1]);
665     if (degenerateAB & degenerateBC) {
666         return kPoint_ReductionType;
667     }
668     if (degenerateAB | degenerateBC) {
669         return kLine_ReductionType;
670     }
671     if (!quad_in_line(quad)) {
672         return kQuad_ReductionType;
673     }
674     SkScalar t = SkFindQuadMaxCurvature(quad);
675     if (0 == t) {
676         return kLine_ReductionType;
677     }
678     *reduction = SkEvalQuadAt(quad, t);
679     return kDegenerate_ReductionType;
680 }
681 
conicTo(const SkPoint & pt1,const SkPoint & pt2,SkScalar weight)682 void SkPathStroker::conicTo(const SkPoint& pt1, const SkPoint& pt2, SkScalar weight) {
683     const SkConic conic(fPrevPt, pt1, pt2, weight);
684     SkPoint reduction;
685     ReductionType reductionType = CheckConicLinear(conic, &reduction);
686     if (kPoint_ReductionType == reductionType) {
687         /* If the stroke consists of a moveTo followed by a degenerate curve, treat it
688             as if it were followed by a zero-length line. Lines without length
689             can have square and round end caps. */
690         this->lineTo(pt2);
691         return;
692     }
693     if (kLine_ReductionType == reductionType) {
694         this->lineTo(pt2);
695         return;
696     }
697     if (kDegenerate_ReductionType == reductionType) {
698         this->lineTo(reduction);
699         SkStrokerPriv::JoinProc saveJoiner = fJoiner;
700         fJoiner = SkStrokerPriv::JoinFactory(SkPaint::kRound_Join);
701         this->lineTo(pt2);
702         fJoiner = saveJoiner;
703         return;
704     }
705     SkASSERT(kQuad_ReductionType == reductionType);
706     SkVector normalAB, unitAB, normalBC, unitBC;
707     if (!this->preJoinTo(pt1, &normalAB, &unitAB, false)) {
708         this->lineTo(pt2);
709         return;
710     }
711     SkQuadConstruct quadPts;
712     this->init(kOuter_StrokeType, &quadPts, 0, 1);
713     (void) this->conicStroke(conic, &quadPts);
714     this->init(kInner_StrokeType, &quadPts, 0, 1);
715     (void) this->conicStroke(conic, &quadPts);
716     this->setConicEndNormal(conic, normalAB, unitAB, &normalBC, &unitBC);
717     this->postJoinTo(pt2, normalBC, unitBC);
718 }
719 
quadTo(const SkPoint & pt1,const SkPoint & pt2)720 void SkPathStroker::quadTo(const SkPoint& pt1, const SkPoint& pt2) {
721     const SkPoint quad[3] = { fPrevPt, pt1, pt2 };
722     SkPoint reduction;
723     ReductionType reductionType = CheckQuadLinear(quad, &reduction);
724     if (kPoint_ReductionType == reductionType) {
725         /* If the stroke consists of a moveTo followed by a degenerate curve, treat it
726             as if it were followed by a zero-length line. Lines without length
727             can have square and round end caps. */
728         this->lineTo(pt2);
729         return;
730     }
731     if (kLine_ReductionType == reductionType) {
732         this->lineTo(pt2);
733         return;
734     }
735     if (kDegenerate_ReductionType == reductionType) {
736         this->lineTo(reduction);
737         SkStrokerPriv::JoinProc saveJoiner = fJoiner;
738         fJoiner = SkStrokerPriv::JoinFactory(SkPaint::kRound_Join);
739         this->lineTo(pt2);
740         fJoiner = saveJoiner;
741         return;
742     }
743     SkASSERT(kQuad_ReductionType == reductionType);
744     SkVector normalAB, unitAB, normalBC, unitBC;
745     if (!this->preJoinTo(pt1, &normalAB, &unitAB, false)) {
746         this->lineTo(pt2);
747         return;
748     }
749     SkQuadConstruct quadPts;
750     this->init(kOuter_StrokeType, &quadPts, 0, 1);
751     (void) this->quadStroke(quad, &quadPts);
752     this->init(kInner_StrokeType, &quadPts, 0, 1);
753     (void) this->quadStroke(quad, &quadPts);
754     this->setQuadEndNormal(quad, normalAB, unitAB, &normalBC, &unitBC);
755 
756     this->postJoinTo(pt2, normalBC, unitBC);
757 }
758 
759 // Given a point on the curve and its derivative, scale the derivative by the radius, and
760 // compute the perpendicular point and its tangent.
setRayPts(const SkPoint & tPt,SkVector * dxy,SkPoint * onPt,SkPoint * tangent) const761 void SkPathStroker::setRayPts(const SkPoint& tPt, SkVector* dxy, SkPoint* onPt,
762         SkPoint* tangent) const {
763     SkPoint oldDxy = *dxy;
764     if (!dxy->setLength(fRadius)) {  // consider moving double logic into SkPoint::setLength
765         double xx = oldDxy.fX;
766         double yy = oldDxy.fY;
767         double dscale = fRadius / sqrt(xx * xx + yy * yy);
768         dxy->fX = SkDoubleToScalar(xx * dscale);
769         dxy->fY = SkDoubleToScalar(yy * dscale);
770     }
771     SkScalar axisFlip = SkIntToScalar(fStrokeType);  // go opposite ways for outer, inner
772     onPt->fX = tPt.fX + axisFlip * dxy->fY;
773     onPt->fY = tPt.fY - axisFlip * dxy->fX;
774     if (tangent) {
775         tangent->fX = onPt->fX + dxy->fX;
776         tangent->fY = onPt->fY + dxy->fY;
777     }
778 }
779 
780 // Given a conic and t, return the point on curve, its perpendicular, and the perpendicular tangent.
781 // Returns false if the perpendicular could not be computed (because the derivative collapsed to 0)
conicPerpRay(const SkConic & conic,SkScalar t,SkPoint * tPt,SkPoint * onPt,SkPoint * tangent) const782 void SkPathStroker::conicPerpRay(const SkConic& conic, SkScalar t, SkPoint* tPt, SkPoint* onPt,
783         SkPoint* tangent) const {
784     SkVector dxy;
785     conic.evalAt(t, tPt, &dxy);
786     if (dxy.fX == 0 && dxy.fY == 0) {
787         dxy = conic.fPts[2] - conic.fPts[0];
788     }
789     this->setRayPts(*tPt, &dxy, onPt, tangent);
790 }
791 
792 // Given a conic and a t range, find the start and end if they haven't been found already.
conicQuadEnds(const SkConic & conic,SkQuadConstruct * quadPts) const793 void SkPathStroker::conicQuadEnds(const SkConic& conic, SkQuadConstruct* quadPts) const {
794     if (!quadPts->fStartSet) {
795         SkPoint conicStartPt;
796         this->conicPerpRay(conic, quadPts->fStartT, &conicStartPt, &quadPts->fQuad[0],
797                 &quadPts->fTangentStart);
798         quadPts->fStartSet = true;
799     }
800     if (!quadPts->fEndSet) {
801         SkPoint conicEndPt;
802         this->conicPerpRay(conic, quadPts->fEndT, &conicEndPt, &quadPts->fQuad[2],
803                 &quadPts->fTangentEnd);
804         quadPts->fEndSet = true;
805     }
806 }
807 
808 
809 // Given a cubic and t, return the point on curve, its perpendicular, and the perpendicular tangent.
cubicPerpRay(const SkPoint cubic[4],SkScalar t,SkPoint * tPt,SkPoint * onPt,SkPoint * tangent) const810 void SkPathStroker::cubicPerpRay(const SkPoint cubic[4], SkScalar t, SkPoint* tPt, SkPoint* onPt,
811         SkPoint* tangent) const {
812     SkVector dxy;
813     SkPoint chopped[7];
814     SkEvalCubicAt(cubic, t, tPt, &dxy, nullptr);
815     if (dxy.fX == 0 && dxy.fY == 0) {
816         const SkPoint* cPts = cubic;
817         if (SkScalarNearlyZero(t)) {
818             dxy = cubic[2] - cubic[0];
819         } else if (SkScalarNearlyZero(1 - t)) {
820             dxy = cubic[3] - cubic[1];
821         } else {
822             // If the cubic inflection falls on the cusp, subdivide the cubic
823             // to find the tangent at that point.
824             SkChopCubicAt(cubic, chopped, t);
825             dxy = chopped[3] - chopped[2];
826             if (dxy.fX == 0 && dxy.fY == 0) {
827                 dxy = chopped[3] - chopped[1];
828                 cPts = chopped;
829             }
830         }
831         if (dxy.fX == 0 && dxy.fY == 0) {
832             dxy = cPts[3] - cPts[0];
833         }
834     }
835     setRayPts(*tPt, &dxy, onPt, tangent);
836 }
837 
838 // Given a cubic and a t range, find the start and end if they haven't been found already.
cubicQuadEnds(const SkPoint cubic[4],SkQuadConstruct * quadPts)839 void SkPathStroker::cubicQuadEnds(const SkPoint cubic[4], SkQuadConstruct* quadPts) {
840     if (!quadPts->fStartSet) {
841         SkPoint cubicStartPt;
842         this->cubicPerpRay(cubic, quadPts->fStartT, &cubicStartPt, &quadPts->fQuad[0],
843                 &quadPts->fTangentStart);
844         quadPts->fStartSet = true;
845     }
846     if (!quadPts->fEndSet) {
847         SkPoint cubicEndPt;
848         this->cubicPerpRay(cubic, quadPts->fEndT, &cubicEndPt, &quadPts->fQuad[2],
849                 &quadPts->fTangentEnd);
850         quadPts->fEndSet = true;
851     }
852 }
853 
cubicQuadMid(const SkPoint cubic[4],const SkQuadConstruct * quadPts,SkPoint * mid) const854 void SkPathStroker::cubicQuadMid(const SkPoint cubic[4], const SkQuadConstruct* quadPts,
855         SkPoint* mid) const {
856     SkPoint cubicMidPt;
857     this->cubicPerpRay(cubic, quadPts->fMidT, &cubicMidPt, mid, nullptr);
858 }
859 
860 // Given a quad and t, return the point on curve, its perpendicular, and the perpendicular tangent.
quadPerpRay(const SkPoint quad[3],SkScalar t,SkPoint * tPt,SkPoint * onPt,SkPoint * tangent) const861 void SkPathStroker::quadPerpRay(const SkPoint quad[3], SkScalar t, SkPoint* tPt, SkPoint* onPt,
862         SkPoint* tangent) const {
863     SkVector dxy;
864     SkEvalQuadAt(quad, t, tPt, &dxy);
865     if (dxy.fX == 0 && dxy.fY == 0) {
866         dxy = quad[2] - quad[0];
867     }
868     setRayPts(*tPt, &dxy, onPt, tangent);
869 }
870 
871 // Find the intersection of the stroke tangents to construct a stroke quad.
872 // Return whether the stroke is a degenerate (a line), a quad, or must be split.
873 // Optionally compute the quad's control point.
intersectRay(SkQuadConstruct * quadPts,IntersectRayType intersectRayType STROKER_DEBUG_PARAMS (int depth)) const874 SkPathStroker::ResultType SkPathStroker::intersectRay(SkQuadConstruct* quadPts,
875         IntersectRayType intersectRayType  STROKER_DEBUG_PARAMS(int depth)) const {
876     const SkPoint& start = quadPts->fQuad[0];
877     const SkPoint& end = quadPts->fQuad[2];
878     SkVector aLen = quadPts->fTangentStart - start;
879     SkVector bLen = quadPts->fTangentEnd - end;
880     /* Slopes match when denom goes to zero:
881                       axLen / ayLen ==                   bxLen / byLen
882     (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen
883              byLen  * axLen         ==  ayLen          * bxLen
884              byLen  * axLen         -   ayLen          * bxLen         ( == denom )
885      */
886     SkScalar denom = aLen.cross(bLen);
887     if (denom == 0 || !SkScalarIsFinite(denom)) {
888         quadPts->fOppositeTangents = aLen.dot(bLen) < 0;
889         return STROKER_RESULT(kDegenerate_ResultType, depth, quadPts, "denom == 0");
890     }
891     quadPts->fOppositeTangents = false;
892     SkVector ab0 = start - end;
893     SkScalar numerA = bLen.cross(ab0);
894     SkScalar numerB = aLen.cross(ab0);
895     if ((numerA >= 0) == (numerB >= 0)) { // if the control point is outside the quad ends
896         // if the perpendicular distances from the quad points to the opposite tangent line
897         // are small, a straight line is good enough
898         SkScalar dist1 = pt_to_line(start, end, quadPts->fTangentEnd);
899         SkScalar dist2 = pt_to_line(end, start, quadPts->fTangentStart);
900         if (SkTMax(dist1, dist2) <= fInvResScaleSquared) {
901             return STROKER_RESULT(kDegenerate_ResultType, depth, quadPts,
902                     "SkTMax(dist1=%g, dist2=%g) <= fInvResScaleSquared", dist1, dist2);
903         }
904         return STROKER_RESULT(kSplit_ResultType, depth, quadPts,
905                 "(numerA=%g >= 0) == (numerB=%g >= 0)", numerA, numerB);
906     }
907     // check to see if the denominator is teeny relative to the numerator
908     // if the offset by one will be lost, the ratio is too large
909     numerA /= denom;
910     bool validDivide = numerA > numerA - 1;
911     if (validDivide) {
912         if (kCtrlPt_RayType == intersectRayType) {
913             SkPoint* ctrlPt = &quadPts->fQuad[1];
914             // the intersection of the tangents need not be on the tangent segment
915             // so 0 <= numerA <= 1 is not necessarily true
916             ctrlPt->fX = start.fX * (1 - numerA) + quadPts->fTangentStart.fX * numerA;
917             ctrlPt->fY = start.fY * (1 - numerA) + quadPts->fTangentStart.fY * numerA;
918         }
919         return STROKER_RESULT(kQuad_ResultType, depth, quadPts,
920                 "(numerA=%g >= 0) != (numerB=%g >= 0)", numerA, numerB);
921     }
922     quadPts->fOppositeTangents = aLen.dot(bLen) < 0;
923     // if the lines are parallel, straight line is good enough
924     return STROKER_RESULT(kDegenerate_ResultType, depth, quadPts,
925             "SkScalarNearlyZero(denom=%g)", denom);
926 }
927 
928 // Given a cubic and a t-range, determine if the stroke can be described by a quadratic.
tangentsMeet(const SkPoint cubic[4],SkQuadConstruct * quadPts)929 SkPathStroker::ResultType SkPathStroker::tangentsMeet(const SkPoint cubic[4],
930         SkQuadConstruct* quadPts) {
931     this->cubicQuadEnds(cubic, quadPts);
932     return this->intersectRay(quadPts, kResultType_RayType  STROKER_DEBUG_PARAMS(fRecursionDepth));
933 }
934 
935 // Intersect the line with the quad and return the t values on the quad where the line crosses.
intersect_quad_ray(const SkPoint line[2],const SkPoint quad[3],SkScalar roots[2])936 static int intersect_quad_ray(const SkPoint line[2], const SkPoint quad[3], SkScalar roots[2]) {
937     SkVector vec = line[1] - line[0];
938     SkScalar r[3];
939     for (int n = 0; n < 3; ++n) {
940         r[n] = (quad[n].fY - line[0].fY) * vec.fX - (quad[n].fX - line[0].fX) * vec.fY;
941     }
942     SkScalar A = r[2];
943     SkScalar B = r[1];
944     SkScalar C = r[0];
945     A += C - 2 * B;  // A = a - 2*b + c
946     B -= C;  // B = -(b - c)
947     return SkFindUnitQuadRoots(A, 2 * B, C, roots);
948 }
949 
950 // Return true if the point is close to the bounds of the quad. This is used as a quick reject.
ptInQuadBounds(const SkPoint quad[3],const SkPoint & pt) const951 bool SkPathStroker::ptInQuadBounds(const SkPoint quad[3], const SkPoint& pt) const {
952     SkScalar xMin = SkTMin(SkTMin(quad[0].fX, quad[1].fX), quad[2].fX);
953     if (pt.fX + fInvResScale < xMin) {
954         return false;
955     }
956     SkScalar xMax = SkTMax(SkTMax(quad[0].fX, quad[1].fX), quad[2].fX);
957     if (pt.fX - fInvResScale > xMax) {
958         return false;
959     }
960     SkScalar yMin = SkTMin(SkTMin(quad[0].fY, quad[1].fY), quad[2].fY);
961     if (pt.fY + fInvResScale < yMin) {
962         return false;
963     }
964     SkScalar yMax = SkTMax(SkTMax(quad[0].fY, quad[1].fY), quad[2].fY);
965     if (pt.fY - fInvResScale > yMax) {
966         return false;
967     }
968     return true;
969 }
970 
points_within_dist(const SkPoint & nearPt,const SkPoint & farPt,SkScalar limit)971 static bool points_within_dist(const SkPoint& nearPt, const SkPoint& farPt, SkScalar limit) {
972     return nearPt.distanceToSqd(farPt) <= limit * limit;
973 }
974 
sharp_angle(const SkPoint quad[3])975 static bool sharp_angle(const SkPoint quad[3]) {
976     SkVector smaller = quad[1] - quad[0];
977     SkVector larger = quad[1] - quad[2];
978     SkScalar smallerLen = smaller.lengthSqd();
979     SkScalar largerLen = larger.lengthSqd();
980     if (smallerLen > largerLen) {
981         SkTSwap(smaller, larger);
982         largerLen = smallerLen;
983     }
984     if (!smaller.setLength(largerLen)) {
985         return false;
986     }
987     SkScalar dot = smaller.dot(larger);
988     return dot > 0;
989 }
990 
strokeCloseEnough(const SkPoint stroke[3],const SkPoint ray[2],SkQuadConstruct * quadPts STROKER_DEBUG_PARAMS (int depth)) const991 SkPathStroker::ResultType SkPathStroker::strokeCloseEnough(const SkPoint stroke[3],
992         const SkPoint ray[2], SkQuadConstruct* quadPts  STROKER_DEBUG_PARAMS(int depth)) const {
993     SkPoint strokeMid = SkEvalQuadAt(stroke, SK_ScalarHalf);
994     // measure the distance from the curve to the quad-stroke midpoint, compare to radius
995     if (points_within_dist(ray[0], strokeMid, fInvResScale)) {  // if the difference is small
996         if (sharp_angle(quadPts->fQuad)) {
997             return STROKER_RESULT(kSplit_ResultType, depth, quadPts,
998                     "sharp_angle (1) =%g,%g, %g,%g, %g,%g",
999                     quadPts->fQuad[0].fX, quadPts->fQuad[0].fY,
1000                     quadPts->fQuad[1].fX, quadPts->fQuad[1].fY,
1001                     quadPts->fQuad[2].fX, quadPts->fQuad[2].fY);
1002         }
1003         return STROKER_RESULT(kQuad_ResultType, depth, quadPts,
1004                 "points_within_dist(ray[0]=%g,%g, strokeMid=%g,%g, fInvResScale=%g)",
1005                 ray[0].fX, ray[0].fY, strokeMid.fX, strokeMid.fY, fInvResScale);
1006     }
1007     // measure the distance to quad's bounds (quick reject)
1008         // an alternative : look for point in triangle
1009     if (!ptInQuadBounds(stroke, ray[0])) {  // if far, subdivide
1010         return STROKER_RESULT(kSplit_ResultType, depth, quadPts,
1011                 "!pt_in_quad_bounds(stroke=(%g,%g %g,%g %g,%g), ray[0]=%g,%g)",
1012                 stroke[0].fX, stroke[0].fY, stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY,
1013                 ray[0].fX, ray[0].fY);
1014     }
1015     // measure the curve ray distance to the quad-stroke
1016     SkScalar roots[2];
1017     int rootCount = intersect_quad_ray(ray, stroke, roots);
1018     if (rootCount != 1) {
1019         return STROKER_RESULT(kSplit_ResultType, depth, quadPts,
1020                 "rootCount=%d != 1", rootCount);
1021     }
1022     SkPoint quadPt = SkEvalQuadAt(stroke, roots[0]);
1023     SkScalar error = fInvResScale * (SK_Scalar1 - SkScalarAbs(roots[0] - 0.5f) * 2);
1024     if (points_within_dist(ray[0], quadPt, error)) {  // if the difference is small, we're done
1025         if (sharp_angle(quadPts->fQuad)) {
1026             return STROKER_RESULT(kSplit_ResultType, depth, quadPts,
1027                     "sharp_angle (2) =%g,%g, %g,%g, %g,%g",
1028                     quadPts->fQuad[0].fX, quadPts->fQuad[0].fY,
1029                     quadPts->fQuad[1].fX, quadPts->fQuad[1].fY,
1030                     quadPts->fQuad[2].fX, quadPts->fQuad[2].fY);
1031         }
1032         return STROKER_RESULT(kQuad_ResultType, depth, quadPts,
1033                 "points_within_dist(ray[0]=%g,%g, quadPt=%g,%g, error=%g)",
1034                 ray[0].fX, ray[0].fY, quadPt.fX, quadPt.fY, error);
1035     }
1036     // otherwise, subdivide
1037     return STROKER_RESULT(kSplit_ResultType, depth, quadPts, "%s", "fall through");
1038 }
1039 
compareQuadCubic(const SkPoint cubic[4],SkQuadConstruct * quadPts)1040 SkPathStroker::ResultType SkPathStroker::compareQuadCubic(const SkPoint cubic[4],
1041         SkQuadConstruct* quadPts) {
1042     // get the quadratic approximation of the stroke
1043     this->cubicQuadEnds(cubic, quadPts);
1044     ResultType resultType = this->intersectRay(quadPts, kCtrlPt_RayType
1045             STROKER_DEBUG_PARAMS(fRecursionDepth) );
1046     if (resultType != kQuad_ResultType) {
1047         return resultType;
1048     }
1049     // project a ray from the curve to the stroke
1050     SkPoint ray[2];  // points near midpoint on quad, midpoint on cubic
1051     this->cubicPerpRay(cubic, quadPts->fMidT, &ray[1], &ray[0], nullptr);
1052     return this->strokeCloseEnough(quadPts->fQuad, ray, quadPts
1053             STROKER_DEBUG_PARAMS(fRecursionDepth));
1054 }
1055 
compareQuadConic(const SkConic & conic,SkQuadConstruct * quadPts) const1056 SkPathStroker::ResultType SkPathStroker::compareQuadConic(const SkConic& conic,
1057         SkQuadConstruct* quadPts) const {
1058     // get the quadratic approximation of the stroke
1059     this->conicQuadEnds(conic, quadPts);
1060     ResultType resultType = this->intersectRay(quadPts, kCtrlPt_RayType
1061             STROKER_DEBUG_PARAMS(fRecursionDepth) );
1062     if (resultType != kQuad_ResultType) {
1063         return resultType;
1064     }
1065     // project a ray from the curve to the stroke
1066     SkPoint ray[2];  // points near midpoint on quad, midpoint on conic
1067     this->conicPerpRay(conic, quadPts->fMidT, &ray[1], &ray[0], nullptr);
1068     return this->strokeCloseEnough(quadPts->fQuad, ray, quadPts
1069             STROKER_DEBUG_PARAMS(fRecursionDepth));
1070 }
1071 
compareQuadQuad(const SkPoint quad[3],SkQuadConstruct * quadPts)1072 SkPathStroker::ResultType SkPathStroker::compareQuadQuad(const SkPoint quad[3],
1073         SkQuadConstruct* quadPts) {
1074     // get the quadratic approximation of the stroke
1075     if (!quadPts->fStartSet) {
1076         SkPoint quadStartPt;
1077         this->quadPerpRay(quad, quadPts->fStartT, &quadStartPt, &quadPts->fQuad[0],
1078                 &quadPts->fTangentStart);
1079         quadPts->fStartSet = true;
1080     }
1081     if (!quadPts->fEndSet) {
1082         SkPoint quadEndPt;
1083         this->quadPerpRay(quad, quadPts->fEndT, &quadEndPt, &quadPts->fQuad[2],
1084                 &quadPts->fTangentEnd);
1085         quadPts->fEndSet = true;
1086     }
1087     ResultType resultType = this->intersectRay(quadPts, kCtrlPt_RayType
1088             STROKER_DEBUG_PARAMS(fRecursionDepth));
1089     if (resultType != kQuad_ResultType) {
1090         return resultType;
1091     }
1092     // project a ray from the curve to the stroke
1093     SkPoint ray[2];
1094     this->quadPerpRay(quad, quadPts->fMidT, &ray[1], &ray[0], nullptr);
1095     return this->strokeCloseEnough(quadPts->fQuad, ray, quadPts
1096             STROKER_DEBUG_PARAMS(fRecursionDepth));
1097 }
1098 
addDegenerateLine(const SkQuadConstruct * quadPts)1099 void SkPathStroker::addDegenerateLine(const SkQuadConstruct* quadPts) {
1100     const SkPoint* quad = quadPts->fQuad;
1101     SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner;
1102     path->lineTo(quad[2].fX, quad[2].fY);
1103 }
1104 
cubicMidOnLine(const SkPoint cubic[4],const SkQuadConstruct * quadPts) const1105 bool SkPathStroker::cubicMidOnLine(const SkPoint cubic[4], const SkQuadConstruct* quadPts) const {
1106     SkPoint strokeMid;
1107     this->cubicQuadMid(cubic, quadPts, &strokeMid);
1108     SkScalar dist = pt_to_line(strokeMid, quadPts->fQuad[0], quadPts->fQuad[2]);
1109     return dist < fInvResScaleSquared;
1110 }
1111 
cubicStroke(const SkPoint cubic[4],SkQuadConstruct * quadPts)1112 bool SkPathStroker::cubicStroke(const SkPoint cubic[4], SkQuadConstruct* quadPts) {
1113     if (!fFoundTangents) {
1114         ResultType resultType = this->tangentsMeet(cubic, quadPts);
1115         if (kQuad_ResultType != resultType) {
1116             if ((kDegenerate_ResultType == resultType
1117                     || points_within_dist(quadPts->fQuad[0], quadPts->fQuad[2],
1118                     fInvResScale)) && cubicMidOnLine(cubic, quadPts)) {
1119                 addDegenerateLine(quadPts);
1120                 return true;
1121             }
1122         } else {
1123             fFoundTangents = true;
1124         }
1125     }
1126     if (fFoundTangents) {
1127         ResultType resultType = this->compareQuadCubic(cubic, quadPts);
1128         if (kQuad_ResultType == resultType) {
1129             SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner;
1130             const SkPoint* stroke = quadPts->fQuad;
1131             path->quadTo(stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY);
1132             return true;
1133         }
1134         if (kDegenerate_ResultType == resultType) {
1135             if (!quadPts->fOppositeTangents) {
1136               addDegenerateLine(quadPts);
1137               return true;
1138             }
1139         }
1140     }
1141     if (!SkScalarIsFinite(quadPts->fQuad[2].fX) || !SkScalarIsFinite(quadPts->fQuad[2].fY)) {
1142         return false;  // just abort if projected quad isn't representable
1143     }
1144     SkDEBUGCODE(gMaxRecursion[fFoundTangents] = SkTMax(gMaxRecursion[fFoundTangents],
1145             fRecursionDepth + 1));
1146     if (++fRecursionDepth > kRecursiveLimits[fFoundTangents]) {
1147         return false;  // just abort if projected quad isn't representable
1148     }
1149     SkQuadConstruct half;
1150     if (!half.initWithStart(quadPts)) {
1151         addDegenerateLine(quadPts);
1152         return true;
1153     }
1154     if (!this->cubicStroke(cubic, &half)) {
1155         return false;
1156     }
1157     if (!half.initWithEnd(quadPts)) {
1158         addDegenerateLine(quadPts);
1159         return true;
1160     }
1161     if (!this->cubicStroke(cubic, &half)) {
1162         return false;
1163     }
1164     --fRecursionDepth;
1165     return true;
1166 }
1167 
conicStroke(const SkConic & conic,SkQuadConstruct * quadPts)1168 bool SkPathStroker::conicStroke(const SkConic& conic, SkQuadConstruct* quadPts) {
1169     ResultType resultType = this->compareQuadConic(conic, quadPts);
1170     if (kQuad_ResultType == resultType) {
1171         const SkPoint* stroke = quadPts->fQuad;
1172         SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner;
1173         path->quadTo(stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY);
1174         return true;
1175     }
1176     if (kDegenerate_ResultType == resultType) {
1177         addDegenerateLine(quadPts);
1178         return true;
1179     }
1180     SkDEBUGCODE(gMaxRecursion[kConic_RecursiveLimit] = SkTMax(gMaxRecursion[kConic_RecursiveLimit],
1181             fRecursionDepth + 1));
1182     if (++fRecursionDepth > kRecursiveLimits[kConic_RecursiveLimit]) {
1183         return false;  // just abort if projected quad isn't representable
1184     }
1185     SkQuadConstruct half;
1186     (void) half.initWithStart(quadPts);
1187     if (!this->conicStroke(conic, &half)) {
1188         return false;
1189     }
1190     (void) half.initWithEnd(quadPts);
1191     if (!this->conicStroke(conic, &half)) {
1192         return false;
1193     }
1194     --fRecursionDepth;
1195     return true;
1196 }
1197 
quadStroke(const SkPoint quad[3],SkQuadConstruct * quadPts)1198 bool SkPathStroker::quadStroke(const SkPoint quad[3], SkQuadConstruct* quadPts) {
1199     ResultType resultType = this->compareQuadQuad(quad, quadPts);
1200     if (kQuad_ResultType == resultType) {
1201         const SkPoint* stroke = quadPts->fQuad;
1202         SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner;
1203         path->quadTo(stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY);
1204         return true;
1205     }
1206     if (kDegenerate_ResultType == resultType) {
1207         addDegenerateLine(quadPts);
1208         return true;
1209     }
1210     SkDEBUGCODE(gMaxRecursion[kQuad_RecursiveLimit] = SkTMax(gMaxRecursion[kQuad_RecursiveLimit],
1211             fRecursionDepth + 1));
1212     if (++fRecursionDepth > kRecursiveLimits[kQuad_RecursiveLimit]) {
1213         return false;  // just abort if projected quad isn't representable
1214     }
1215     SkQuadConstruct half;
1216     (void) half.initWithStart(quadPts);
1217     if (!this->quadStroke(quad, &half)) {
1218         return false;
1219     }
1220     (void) half.initWithEnd(quadPts);
1221     if (!this->quadStroke(quad, &half)) {
1222         return false;
1223     }
1224     --fRecursionDepth;
1225     return true;
1226 }
1227 
cubicTo(const SkPoint & pt1,const SkPoint & pt2,const SkPoint & pt3)1228 void SkPathStroker::cubicTo(const SkPoint& pt1, const SkPoint& pt2,
1229                             const SkPoint& pt3) {
1230     const SkPoint cubic[4] = { fPrevPt, pt1, pt2, pt3 };
1231     SkPoint reduction[3];
1232     const SkPoint* tangentPt;
1233     ReductionType reductionType = CheckCubicLinear(cubic, reduction, &tangentPt);
1234     if (kPoint_ReductionType == reductionType) {
1235         /* If the stroke consists of a moveTo followed by a degenerate curve, treat it
1236             as if it were followed by a zero-length line. Lines without length
1237             can have square and round end caps. */
1238         this->lineTo(pt3);
1239         return;
1240     }
1241     if (kLine_ReductionType == reductionType) {
1242         this->lineTo(pt3);
1243         return;
1244     }
1245     if (kDegenerate_ReductionType <= reductionType && kDegenerate3_ReductionType >= reductionType) {
1246         this->lineTo(reduction[0]);
1247         SkStrokerPriv::JoinProc saveJoiner = fJoiner;
1248         fJoiner = SkStrokerPriv::JoinFactory(SkPaint::kRound_Join);
1249         if (kDegenerate2_ReductionType <= reductionType) {
1250             this->lineTo(reduction[1]);
1251         }
1252         if (kDegenerate3_ReductionType == reductionType) {
1253             this->lineTo(reduction[2]);
1254         }
1255         this->lineTo(pt3);
1256         fJoiner = saveJoiner;
1257         return;
1258     }
1259     SkASSERT(kQuad_ReductionType == reductionType);
1260     SkVector normalAB, unitAB, normalCD, unitCD;
1261     if (!this->preJoinTo(*tangentPt, &normalAB, &unitAB, false)) {
1262         this->lineTo(pt3);
1263         return;
1264     }
1265     SkScalar tValues[2];
1266     int count = SkFindCubicInflections(cubic, tValues);
1267     SkScalar lastT = 0;
1268     for (int index = 0; index <= count; ++index) {
1269         SkScalar nextT = index < count ? tValues[index] : 1;
1270         SkQuadConstruct quadPts;
1271         this->init(kOuter_StrokeType, &quadPts, lastT, nextT);
1272         (void) this->cubicStroke(cubic, &quadPts);
1273         this->init(kInner_StrokeType, &quadPts, lastT, nextT);
1274         (void) this->cubicStroke(cubic, &quadPts);
1275         lastT = nextT;
1276     }
1277     // emit the join even if one stroke succeeded but the last one failed
1278     // this avoids reversing an inner stroke with a partial path followed by another moveto
1279     this->setCubicEndNormal(cubic, normalAB, unitAB, &normalCD, &unitCD);
1280 
1281     this->postJoinTo(pt3, normalCD, unitCD);
1282 }
1283 
1284 ///////////////////////////////////////////////////////////////////////////////
1285 ///////////////////////////////////////////////////////////////////////////////
1286 
1287 #include "SkPaintDefaults.h"
1288 
SkStroke()1289 SkStroke::SkStroke() {
1290     fWidth      = SK_Scalar1;
1291     fMiterLimit = SkPaintDefaults_MiterLimit;
1292     fResScale   = 1;
1293     fCap        = SkPaint::kDefault_Cap;
1294     fJoin       = SkPaint::kDefault_Join;
1295     fDoFill     = false;
1296 }
1297 
SkStroke(const SkPaint & p)1298 SkStroke::SkStroke(const SkPaint& p) {
1299     fWidth      = p.getStrokeWidth();
1300     fMiterLimit = p.getStrokeMiter();
1301     fResScale   = 1;
1302     fCap        = (uint8_t)p.getStrokeCap();
1303     fJoin       = (uint8_t)p.getStrokeJoin();
1304     fDoFill     = SkToU8(p.getStyle() == SkPaint::kStrokeAndFill_Style);
1305 }
1306 
SkStroke(const SkPaint & p,SkScalar width)1307 SkStroke::SkStroke(const SkPaint& p, SkScalar width) {
1308     fWidth      = width;
1309     fMiterLimit = p.getStrokeMiter();
1310     fResScale   = 1;
1311     fCap        = (uint8_t)p.getStrokeCap();
1312     fJoin       = (uint8_t)p.getStrokeJoin();
1313     fDoFill     = SkToU8(p.getStyle() == SkPaint::kStrokeAndFill_Style);
1314 }
1315 
setWidth(SkScalar width)1316 void SkStroke::setWidth(SkScalar width) {
1317     SkASSERT(width >= 0);
1318     fWidth = width;
1319 }
1320 
setMiterLimit(SkScalar miterLimit)1321 void SkStroke::setMiterLimit(SkScalar miterLimit) {
1322     SkASSERT(miterLimit >= 0);
1323     fMiterLimit = miterLimit;
1324 }
1325 
setCap(SkPaint::Cap cap)1326 void SkStroke::setCap(SkPaint::Cap cap) {
1327     SkASSERT((unsigned)cap < SkPaint::kCapCount);
1328     fCap = SkToU8(cap);
1329 }
1330 
setJoin(SkPaint::Join join)1331 void SkStroke::setJoin(SkPaint::Join join) {
1332     SkASSERT((unsigned)join < SkPaint::kJoinCount);
1333     fJoin = SkToU8(join);
1334 }
1335 
1336 ///////////////////////////////////////////////////////////////////////////////
1337 
1338 // If src==dst, then we use a tmp path to record the stroke, and then swap
1339 // its contents with src when we're done.
1340 class AutoTmpPath {
1341 public:
AutoTmpPath(const SkPath & src,SkPath ** dst)1342     AutoTmpPath(const SkPath& src, SkPath** dst) : fSrc(src) {
1343         if (&src == *dst) {
1344             *dst = &fTmpDst;
1345             fSwapWithSrc = true;
1346         } else {
1347             (*dst)->reset();
1348             fSwapWithSrc = false;
1349         }
1350     }
1351 
~AutoTmpPath()1352     ~AutoTmpPath() {
1353         if (fSwapWithSrc) {
1354             fTmpDst.swap(*const_cast<SkPath*>(&fSrc));
1355         }
1356     }
1357 
1358 private:
1359     SkPath          fTmpDst;
1360     const SkPath&   fSrc;
1361     bool            fSwapWithSrc;
1362 };
1363 
strokePath(const SkPath & src,SkPath * dst) const1364 void SkStroke::strokePath(const SkPath& src, SkPath* dst) const {
1365     SkASSERT(dst);
1366 
1367     SkScalar radius = SkScalarHalf(fWidth);
1368 
1369     AutoTmpPath tmp(src, &dst);
1370 
1371     if (radius <= 0) {
1372         return;
1373     }
1374 
1375     // If src is really a rect, call our specialty strokeRect() method
1376     {
1377         SkRect rect;
1378         bool isClosed;
1379         SkPath::Direction dir;
1380         if (src.isRect(&rect, &isClosed, &dir) && isClosed) {
1381             this->strokeRect(rect, dst, dir);
1382             // our answer should preserve the inverseness of the src
1383             if (src.isInverseFillType()) {
1384                 SkASSERT(!dst->isInverseFillType());
1385                 dst->toggleInverseFillType();
1386             }
1387             return;
1388         }
1389     }
1390 
1391     // We can always ignore centers for stroke and fill convex line-only paths
1392     // TODO: remove the line-only restriction
1393     bool ignoreCenter = fDoFill && (src.getSegmentMasks() == SkPath::kLine_SegmentMask) &&
1394                         src.isLastContourClosed() && src.isConvex();
1395 
1396     SkPathStroker   stroker(src, radius, fMiterLimit, this->getCap(), this->getJoin(),
1397                             fResScale, ignoreCenter);
1398     SkPath::Iter    iter(src, false);
1399     SkPath::Verb    lastSegment = SkPath::kMove_Verb;
1400 
1401     for (;;) {
1402         SkPoint  pts[4];
1403         switch (iter.next(pts, false)) {
1404             case SkPath::kMove_Verb:
1405                 stroker.moveTo(pts[0]);
1406                 break;
1407             case SkPath::kLine_Verb:
1408                 stroker.lineTo(pts[1], &iter);
1409                 lastSegment = SkPath::kLine_Verb;
1410                 break;
1411             case SkPath::kQuad_Verb:
1412                 stroker.quadTo(pts[1], pts[2]);
1413                 lastSegment = SkPath::kQuad_Verb;
1414                 break;
1415             case SkPath::kConic_Verb: {
1416                 stroker.conicTo(pts[1], pts[2], iter.conicWeight());
1417                 lastSegment = SkPath::kConic_Verb;
1418                 break;
1419             } break;
1420             case SkPath::kCubic_Verb:
1421                 stroker.cubicTo(pts[1], pts[2], pts[3]);
1422                 lastSegment = SkPath::kCubic_Verb;
1423                 break;
1424             case SkPath::kClose_Verb:
1425                 if (SkPaint::kButt_Cap != this->getCap()) {
1426                     /* If the stroke consists of a moveTo followed by a close, treat it
1427                        as if it were followed by a zero-length line. Lines without length
1428                        can have square and round end caps. */
1429                     if (stroker.hasOnlyMoveTo()) {
1430                         stroker.lineTo(stroker.moveToPt());
1431                         goto ZERO_LENGTH;
1432                     }
1433                     /* If the stroke consists of a moveTo followed by one or more zero-length
1434                        verbs, then followed by a close, treat is as if it were followed by a
1435                        zero-length line. Lines without length can have square & round end caps. */
1436                     if (stroker.isCurrentContourEmpty()) {
1437                 ZERO_LENGTH:
1438                         lastSegment = SkPath::kLine_Verb;
1439                         break;
1440                     }
1441                 }
1442                 stroker.close(lastSegment == SkPath::kLine_Verb);
1443                 break;
1444             case SkPath::kDone_Verb:
1445                 goto DONE;
1446         }
1447     }
1448 DONE:
1449     stroker.done(dst, lastSegment == SkPath::kLine_Verb);
1450 
1451     if (fDoFill && !ignoreCenter) {
1452         if (SkPathPriv::CheapIsFirstDirection(src, SkPathPriv::kCCW_FirstDirection)) {
1453             dst->reverseAddPath(src);
1454         } else {
1455             dst->addPath(src);
1456         }
1457     } else {
1458         //  Seems like we can assume that a 2-point src would always result in
1459         //  a convex stroke, but testing has proved otherwise.
1460         //  TODO: fix the stroker to make this assumption true (without making
1461         //  it slower that the work that will be done in computeConvexity())
1462 #if 0
1463         // this test results in a non-convex stroke :(
1464         static void test(SkCanvas* canvas) {
1465             SkPoint pts[] = { 146.333328,  192.333328, 300.333344, 293.333344 };
1466             SkPaint paint;
1467             paint.setStrokeWidth(7);
1468             paint.setStrokeCap(SkPaint::kRound_Cap);
1469             canvas->drawLine(pts[0].fX, pts[0].fY, pts[1].fX, pts[1].fY, paint);
1470         }
1471 #endif
1472 #if 0
1473         if (2 == src.countPoints()) {
1474             dst->setIsConvex(true);
1475         }
1476 #endif
1477     }
1478 
1479     // our answer should preserve the inverseness of the src
1480     if (src.isInverseFillType()) {
1481         SkASSERT(!dst->isInverseFillType());
1482         dst->toggleInverseFillType();
1483     }
1484 }
1485 
reverse_direction(SkPath::Direction dir)1486 static SkPath::Direction reverse_direction(SkPath::Direction dir) {
1487     static const SkPath::Direction gOpposite[] = { SkPath::kCCW_Direction, SkPath::kCW_Direction };
1488     return gOpposite[dir];
1489 }
1490 
addBevel(SkPath * path,const SkRect & r,const SkRect & outer,SkPath::Direction dir)1491 static void addBevel(SkPath* path, const SkRect& r, const SkRect& outer, SkPath::Direction dir) {
1492     SkPoint pts[8];
1493 
1494     if (SkPath::kCW_Direction == dir) {
1495         pts[0].set(r.fLeft, outer.fTop);
1496         pts[1].set(r.fRight, outer.fTop);
1497         pts[2].set(outer.fRight, r.fTop);
1498         pts[3].set(outer.fRight, r.fBottom);
1499         pts[4].set(r.fRight, outer.fBottom);
1500         pts[5].set(r.fLeft, outer.fBottom);
1501         pts[6].set(outer.fLeft, r.fBottom);
1502         pts[7].set(outer.fLeft, r.fTop);
1503     } else {
1504         pts[7].set(r.fLeft, outer.fTop);
1505         pts[6].set(r.fRight, outer.fTop);
1506         pts[5].set(outer.fRight, r.fTop);
1507         pts[4].set(outer.fRight, r.fBottom);
1508         pts[3].set(r.fRight, outer.fBottom);
1509         pts[2].set(r.fLeft, outer.fBottom);
1510         pts[1].set(outer.fLeft, r.fBottom);
1511         pts[0].set(outer.fLeft, r.fTop);
1512     }
1513     path->addPoly(pts, 8, true);
1514 }
1515 
strokeRect(const SkRect & origRect,SkPath * dst,SkPath::Direction dir) const1516 void SkStroke::strokeRect(const SkRect& origRect, SkPath* dst,
1517                           SkPath::Direction dir) const {
1518     SkASSERT(dst != nullptr);
1519     dst->reset();
1520 
1521     SkScalar radius = SkScalarHalf(fWidth);
1522     if (radius <= 0) {
1523         return;
1524     }
1525 
1526     SkScalar rw = origRect.width();
1527     SkScalar rh = origRect.height();
1528     if ((rw < 0) ^ (rh < 0)) {
1529         dir = reverse_direction(dir);
1530     }
1531     SkRect rect(origRect);
1532     rect.sort();
1533     // reassign these, now that we know they'll be >= 0
1534     rw = rect.width();
1535     rh = rect.height();
1536 
1537     SkRect r(rect);
1538     r.outset(radius, radius);
1539 
1540     SkPaint::Join join = (SkPaint::Join)fJoin;
1541     if (SkPaint::kMiter_Join == join && fMiterLimit < SK_ScalarSqrt2) {
1542         join = SkPaint::kBevel_Join;
1543     }
1544 
1545     switch (join) {
1546         case SkPaint::kMiter_Join:
1547             dst->addRect(r, dir);
1548             break;
1549         case SkPaint::kBevel_Join:
1550             addBevel(dst, rect, r, dir);
1551             break;
1552         case SkPaint::kRound_Join:
1553             dst->addRoundRect(r, radius, radius, dir);
1554             break;
1555         default:
1556             break;
1557     }
1558 
1559     if (fWidth < SkMinScalar(rw, rh) && !fDoFill) {
1560         r = rect;
1561         r.inset(radius, radius);
1562         dst->addRect(r, reverse_direction(dir));
1563     }
1564 }
1565