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