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