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