1/*
2 * Copyright 2006 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 "include/core/SkPath.h"
9
10#include "include/core/SkData.h"
11#include "include/core/SkMath.h"
12#include "include/core/SkRRect.h"
13#include "include/private/SkMacros.h"
14#include "include/private/SkPathRef.h"
15#include "include/private/SkTo.h"
16#include "src/core/SkBuffer.h"
17#include "src/core/SkCubicClipper.h"
18#include "src/core/SkGeometry.h"
19#include "src/core/SkMatrixPriv.h"
20#include "src/core/SkPathMakers.h"
21#include "src/core/SkPathPriv.h"
22#include "src/core/SkPointPriv.h"
23#include "src/core/SkSafeMath.h"
24#include "src/core/SkTLazy.h"
25// need SkDVector
26#include "src/pathops/SkPathOpsPoint.h"
27
28#include <cmath>
29#include <utility>
30
31struct SkPath_Storage_Equivalent {
32 void* fPtr;
33 int32_t fIndex;
34 uint32_t fFlags;
35};
36
37static_assert(sizeof(SkPath) == sizeof(SkPath_Storage_Equivalent),
38 "Please keep an eye on SkPath packing.");
39
40static float poly_eval(float A, float B, float C, float t) {
41 return (A * t + B) * t + C;
42}
43
44static float poly_eval(float A, float B, float C, float D, float t) {
45 return ((A * t + B) * t + C) * t + D;
46}
47
48////////////////////////////////////////////////////////////////////////////
49
50/**
51 * Path.bounds is defined to be the bounds of all the control points.
52 * If we called bounds.join(r) we would skip r if r was empty, which breaks
53 * our promise. Hence we have a custom joiner that doesn't look at emptiness
54 */
55static void joinNoEmptyChecks(SkRect* dst, const SkRect& src) {
56 dst->fLeft = std::min(dst->fLeft, src.fLeft);
57 dst->fTop = std::min(dst->fTop, src.fTop);
58 dst->fRight = std::max(dst->fRight, src.fRight);
59 dst->fBottom = std::max(dst->fBottom, src.fBottom);
60}
61
62static bool is_degenerate(const SkPath& path) {
63 return path.countVerbs() <= 1;
64}
65
66class SkAutoDisableDirectionCheck {
67public:
68 SkAutoDisableDirectionCheck(SkPath* path) : fPath(path) {
69 fSaved = static_cast<SkPathPriv::FirstDirection>(fPath->getFirstDirection());
70 }
71
72 ~SkAutoDisableDirectionCheck() {
73 fPath->setFirstDirection(fSaved);
74 }
75
76private:
77 SkPath* fPath;
78 SkPathPriv::FirstDirection fSaved;
79};
80#define SkAutoDisableDirectionCheck(...) SK_REQUIRE_LOCAL_VAR(SkAutoDisableDirectionCheck)
81
82/* This guy's constructor/destructor bracket a path editing operation. It is
83 used when we know the bounds of the amount we are going to add to the path
84 (usually a new contour, but not required).
85
86 It captures some state about the path up front (i.e. if it already has a
87 cached bounds), and then if it can, it updates the cache bounds explicitly,
88 avoiding the need to revisit all of the points in getBounds().
89
90 It also notes if the path was originally degenerate, and if so, sets
91 isConvex to true. Thus it can only be used if the contour being added is
92 convex.
93 */
94class SkAutoPathBoundsUpdate {
95public:
96 SkAutoPathBoundsUpdate(SkPath* path, const SkRect& r) : fPath(path), fRect(r) {
97 // Cannot use fRect for our bounds unless we know it is sorted
98 fRect.sort();
99 // Mark the path's bounds as dirty if (1) they are, or (2) the path
100 // is non-finite, and therefore its bounds are not meaningful
101 fHasValidBounds = path->hasComputedBounds() && path->isFinite();
102 fEmpty = path->isEmpty();
103 if (fHasValidBounds && !fEmpty) {
104 joinNoEmptyChecks(&fRect, fPath->getBounds());
105 }
106 fDegenerate = is_degenerate(*path);
107 }
108
109 ~SkAutoPathBoundsUpdate() {
110 fPath->setConvexityType(fDegenerate ? SkPathConvexityType::kConvex
111 : SkPathConvexityType::kUnknown);
112 if ((fEmpty || fHasValidBounds) && fRect.isFinite()) {
113 fPath->setBounds(fRect);
114 }
115 }
116
117private:
118 SkPath* fPath;
119 SkRect fRect;
120 bool fHasValidBounds;
121 bool fDegenerate;
122 bool fEmpty;
123};
124#define SkAutoPathBoundsUpdate(...) SK_REQUIRE_LOCAL_VAR(SkAutoPathBoundsUpdate)
125
126////////////////////////////////////////////////////////////////////////////
127
128/*
129 Stores the verbs and points as they are given to us, with exceptions:
130 - we only record "Close" if it was immediately preceeded by Move | Line | Quad | Cubic
131 - we insert a Move(0,0) if Line | Quad | Cubic is our first command
132
133 The iterator does more cleanup, especially if forceClose == true
134 1. If we encounter degenerate segments, remove them
135 2. if we encounter Close, return a cons'd up Line() first (if the curr-pt != start-pt)
136 3. if we encounter Move without a preceeding Close, and forceClose is true, goto #2
137 4. if we encounter Line | Quad | Cubic after Close, cons up a Move
138*/
139
140////////////////////////////////////////////////////////////////////////////
141
142// flag to require a moveTo if we begin with something else, like lineTo etc.
143#define INITIAL_LASTMOVETOINDEX_VALUE ~0
144
145SkPath::SkPath()
146 : fPathRef(SkPathRef::CreateEmpty()) {
147 this->resetFields();
148 fIsVolatile = false;
149}
150
151void SkPath::resetFields() {
152 //fPathRef is assumed to have been emptied by the caller.
153 fLastMoveToIndex = INITIAL_LASTMOVETOINDEX_VALUE;
154 fFillType = SkToU8(SkPathFillType::kWinding);
155 this->setConvexityType(SkPathConvexityType::kUnknown);
156 this->setFirstDirection(SkPathPriv::kUnknown_FirstDirection);
157
158 // We don't touch Android's fSourcePath. It's used to track texture garbage collection, so we
159 // don't want to muck with it if it's been set to something non-nullptr.
160}
161
162SkPath::SkPath(const SkPath& that)
163 : fPathRef(SkRef(that.fPathRef.get())) {
164 this->copyFields(that);
165 SkDEBUGCODE(that.validate();)
166}
167
168SkPath::~SkPath() {
169 SkDEBUGCODE(this->validate();)
170}
171
172SkPath& SkPath::operator=(const SkPath& that) {
173 SkDEBUGCODE(that.validate();)
174
175 if (this != &that) {
176 fPathRef.reset(SkRef(that.fPathRef.get()));
177 this->copyFields(that);
178 }
179 SkDEBUGCODE(this->validate();)
180 return *this;
181}
182
183void SkPath::copyFields(const SkPath& that) {
184 //fPathRef is assumed to have been set by the caller.
185 fLastMoveToIndex = that.fLastMoveToIndex;
186 fFillType = that.fFillType;
187 fIsVolatile = that.fIsVolatile;
188
189 // Non-atomic assignment of atomic values.
190 this->setConvexityType(that.getConvexityTypeOrUnknown());
191 this->setFirstDirection(that.getFirstDirection());
192}
193
194bool operator==(const SkPath& a, const SkPath& b) {
195 // note: don't need to look at isConvex or bounds, since just comparing the
196 // raw data is sufficient.
197 return &a == &b ||
198 (a.fFillType == b.fFillType && *a.fPathRef.get() == *b.fPathRef.get());
199}
200
201void SkPath::swap(SkPath& that) {
202 if (this != &that) {
203 fPathRef.swap(that.fPathRef);
204 std::swap(fLastMoveToIndex, that.fLastMoveToIndex);
205
206 const auto ft = fFillType;
207 fFillType = that.fFillType;
208 that.fFillType = ft;
209
210 const auto iv = fIsVolatile;
211 fIsVolatile = that.fIsVolatile;
212 that.fIsVolatile = iv;
213
214 // Non-atomic swaps of atomic values.
215 SkPathConvexityType c = this->getConvexityTypeOrUnknown();
216 this->setConvexityType(that.getConvexityTypeOrUnknown());
217 that.setConvexityType(c);
218
219 uint8_t fd = this->getFirstDirection();
220 this->setFirstDirection(that.getFirstDirection());
221 that.setFirstDirection(fd);
222 }
223}
224
225bool SkPath::isInterpolatable(const SkPath& compare) const {
226 // need the same structure (verbs, conicweights) and same point-count
227 return fPathRef->fPoints.count() == compare.fPathRef->fPoints.count() &&
228 fPathRef->fVerbs == compare.fPathRef->fVerbs &&
229 fPathRef->fConicWeights == compare.fPathRef->fConicWeights;
230}
231
232bool SkPath::interpolate(const SkPath& ending, SkScalar weight, SkPath* out) const {
233 int pointCount = fPathRef->countPoints();
234 if (pointCount != ending.fPathRef->countPoints()) {
235 return false;
236 }
237 if (!pointCount) {
238 return true;
239 }
240 out->reset();
241 out->addPath(*this);
242 fPathRef->interpolate(*ending.fPathRef, weight, out->fPathRef.get());
243 return true;
244}
245
246static inline bool check_edge_against_rect(const SkPoint& p0,
247 const SkPoint& p1,
248 const SkRect& rect,
249 SkPathPriv::FirstDirection dir) {
250 const SkPoint* edgeBegin;
251 SkVector v;
252 if (SkPathPriv::kCW_FirstDirection == dir) {
253 v = p1 - p0;
254 edgeBegin = &p0;
255 } else {
256 v = p0 - p1;
257 edgeBegin = &p1;
258 }
259 if (v.fX || v.fY) {
260 // check the cross product of v with the vec from edgeBegin to each rect corner
261 SkScalar yL = v.fY * (rect.fLeft - edgeBegin->fX);
262 SkScalar xT = v.fX * (rect.fTop - edgeBegin->fY);
263 SkScalar yR = v.fY * (rect.fRight - edgeBegin->fX);
264 SkScalar xB = v.fX * (rect.fBottom - edgeBegin->fY);
265 if ((xT < yL) || (xT < yR) || (xB < yL) || (xB < yR)) {
266 return false;
267 }
268 }
269 return true;
270}
271
272bool SkPath::conservativelyContainsRect(const SkRect& rect) const {
273 // This only handles non-degenerate convex paths currently.
274 if (!this->isConvex()) {
275 return false;
276 }
277
278 SkPathPriv::FirstDirection direction;
279 if (!SkPathPriv::CheapComputeFirstDirection(*this, &direction)) {
280 return false;
281 }
282
283 SkPoint firstPt;
284 SkPoint prevPt;
285 SkPath::Iter iter(*this, true);
286 SkPath::Verb verb;
287 SkPoint pts[4];
288 int segmentCount = 0;
289 SkDEBUGCODE(int moveCnt = 0;)
290 SkDEBUGCODE(int closeCount = 0;)
291
292 while ((verb = iter.next(pts)) != kDone_Verb) {
293 int nextPt = -1;
294 switch (verb) {
295 case kMove_Verb:
296 SkASSERT(!segmentCount && !closeCount);
297 SkDEBUGCODE(++moveCnt);
298 firstPt = prevPt = pts[0];
299 break;
300 case kLine_Verb:
301 if (!SkPathPriv::AllPointsEq(pts, 2)) {
302 nextPt = 1;
303 SkASSERT(moveCnt && !closeCount);
304 ++segmentCount;
305 }
306 break;
307 case kQuad_Verb:
308 case kConic_Verb:
309 if (!SkPathPriv::AllPointsEq(pts, 3)) {
310 SkASSERT(moveCnt && !closeCount);
311 ++segmentCount;
312 nextPt = 2;
313 }
314 break;
315 case kCubic_Verb:
316 if (!SkPathPriv::AllPointsEq(pts, 4)) {
317 SkASSERT(moveCnt && !closeCount);
318 ++segmentCount;
319 nextPt = 3;
320 }
321 break;
322 case kClose_Verb:
323 SkDEBUGCODE(++closeCount;)
324 break;
325 default:
326 SkDEBUGFAIL("unknown verb");
327 }
328 if (-1 != nextPt) {
329 if (SkPath::kConic_Verb == verb) {
330 SkConic orig;
331 orig.set(pts, iter.conicWeight());
332 SkPoint quadPts[5];
333 int count = orig.chopIntoQuadsPOW2(quadPts, 1);
334 SkASSERT_RELEASE(2 == count);
335
336 if (!check_edge_against_rect(quadPts[0], quadPts[2], rect, direction)) {
337 return false;
338 }
339 if (!check_edge_against_rect(quadPts[2], quadPts[4], rect, direction)) {
340 return false;
341 }
342 } else {
343 if (!check_edge_against_rect(prevPt, pts[nextPt], rect, direction)) {
344 return false;
345 }
346 }
347 prevPt = pts[nextPt];
348 }
349 }
350
351 if (segmentCount) {
352 return check_edge_against_rect(prevPt, firstPt, rect, direction);
353 }
354 return false;
355}
356
357uint32_t SkPath::getGenerationID() const {
358 uint32_t genID = fPathRef->genID();
359#ifdef SK_BUILD_FOR_ANDROID_FRAMEWORK
360 SkASSERT((unsigned)fFillType < (1 << (32 - SkPathPriv::kPathRefGenIDBitCnt)));
361 genID |= static_cast<uint32_t>(fFillType) << SkPathPriv::kPathRefGenIDBitCnt;
362#endif
363 return genID;
364}
365
366SkPath& SkPath::reset() {
367 SkDEBUGCODE(this->validate();)
368
369 fPathRef.reset(SkPathRef::CreateEmpty());
370 this->resetFields();
371 return *this;
372}
373
374SkPath& SkPath::rewind() {
375 SkDEBUGCODE(this->validate();)
376
377 SkPathRef::Rewind(&fPathRef);
378 this->resetFields();
379 return *this;
380}
381
382bool SkPath::isLastContourClosed() const {
383 int verbCount = fPathRef->countVerbs();
384 if (0 == verbCount) {
385 return false;
386 }
387 return kClose_Verb == fPathRef->atVerb(verbCount - 1);
388}
389
390bool SkPath::isLine(SkPoint line[2]) const {
391 int verbCount = fPathRef->countVerbs();
392
393 if (2 == verbCount) {
394 SkASSERT(kMove_Verb == fPathRef->atVerb(0));
395 if (kLine_Verb == fPathRef->atVerb(1)) {
396 SkASSERT(2 == fPathRef->countPoints());
397 if (line) {
398 const SkPoint* pts = fPathRef->points();
399 line[0] = pts[0];
400 line[1] = pts[1];
401 }
402 return true;
403 }
404 }
405 return false;
406}
407
408/*
409 Determines if path is a rect by keeping track of changes in direction
410 and looking for a loop either clockwise or counterclockwise.
411
412 The direction is computed such that:
413 0: vertical up
414 1: horizontal left
415 2: vertical down
416 3: horizontal right
417
418A rectangle cycles up/right/down/left or up/left/down/right.
419
420The test fails if:
421 The path is closed, and followed by a line.
422 A second move creates a new endpoint.
423 A diagonal line is parsed.
424 There's more than four changes of direction.
425 There's a discontinuity on the line (e.g., a move in the middle)
426 The line reverses direction.
427 The path contains a quadratic or cubic.
428 The path contains fewer than four points.
429 *The rectangle doesn't complete a cycle.
430 *The final point isn't equal to the first point.
431
432 *These last two conditions we relax if we have a 3-edge path that would
433 form a rectangle if it were closed (as we do when we fill a path)
434
435It's OK if the path has:
436 Several colinear line segments composing a rectangle side.
437 Single points on the rectangle side.
438
439The direction takes advantage of the corners found since opposite sides
440must travel in opposite directions.
441
442FIXME: Allow colinear quads and cubics to be treated like lines.
443FIXME: If the API passes fill-only, return true if the filled stroke
444 is a rectangle, though the caller failed to close the path.
445
446 directions values:
447 0x1 is set if the segment is horizontal
448 0x2 is set if the segment is moving to the right or down
449 thus:
450 two directions are opposites iff (dirA ^ dirB) == 0x2
451 two directions are perpendicular iff (dirA ^ dirB) == 0x1
452
453 */
454static int rect_make_dir(SkScalar dx, SkScalar dy) {
455 return ((0 != dx) << 0) | ((dx > 0 || dy > 0) << 1);
456}
457
458bool SkPath::isRect(SkRect* rect, bool* isClosed, SkPathDirection* direction) const {
459 SkDEBUGCODE(this->validate();)
460 int currVerb = 0;
461 const SkPoint* pts = fPathRef->points();
462 return SkPathPriv::IsRectContour(*this, false, &currVerb, &pts, isClosed, direction, rect);
463}
464
465bool SkPath::isOval(SkRect* bounds) const {
466 return SkPathPriv::IsOval(*this, bounds, nullptr, nullptr);
467}
468
469bool SkPath::isRRect(SkRRect* rrect) const {
470 return SkPathPriv::IsRRect(*this, rrect, nullptr, nullptr);
471}
472
473int SkPath::countPoints() const {
474 return fPathRef->countPoints();
475}
476
477int SkPath::getPoints(SkPoint dst[], int max) const {
478 SkDEBUGCODE(this->validate();)
479
480 SkASSERT(max >= 0);
481 SkASSERT(!max || dst);
482 int count = std::min(max, fPathRef->countPoints());
483 sk_careful_memcpy(dst, fPathRef->points(), count * sizeof(SkPoint));
484 return fPathRef->countPoints();
485}
486
487SkPoint SkPath::getPoint(int index) const {
488 if ((unsigned)index < (unsigned)fPathRef->countPoints()) {
489 return fPathRef->atPoint(index);
490 }
491 return SkPoint::Make(0, 0);
492}
493
494int SkPath::countVerbs() const {
495 return fPathRef->countVerbs();
496}
497
498int SkPath::getVerbs(uint8_t dst[], int max) const {
499 SkDEBUGCODE(this->validate();)
500
501 SkASSERT(max >= 0);
502 SkASSERT(!max || dst);
503 int count = std::min(max, fPathRef->countVerbs());
504 if (count) {
505 memcpy(dst, fPathRef->verbsBegin(), count);
506 }
507 return fPathRef->countVerbs();
508}
509
510size_t SkPath::approximateBytesUsed() const {
511 size_t size = sizeof (SkPath);
512 if (fPathRef != nullptr) {
513 size += fPathRef->countPoints() * sizeof(SkPoint)
514 + fPathRef->countVerbs()
515 + fPathRef->countWeights() * sizeof(SkScalar);
516 }
517
518 return size;
519}
520
521bool SkPath::getLastPt(SkPoint* lastPt) const {
522 SkDEBUGCODE(this->validate();)
523
524 int count = fPathRef->countPoints();
525 if (count > 0) {
526 if (lastPt) {
527 *lastPt = fPathRef->atPoint(count - 1);
528 }
529 return true;
530 }
531 if (lastPt) {
532 lastPt->set(0, 0);
533 }
534 return false;
535}
536
537void SkPath::setPt(int index, SkScalar x, SkScalar y) {
538 SkDEBUGCODE(this->validate();)
539
540 int count = fPathRef->countPoints();
541 if (count <= index) {
542 return;
543 } else {
544 SkPathRef::Editor ed(&fPathRef);
545 ed.atPoint(index)->set(x, y);
546 }
547}
548
549void SkPath::setLastPt(SkScalar x, SkScalar y) {
550 SkDEBUGCODE(this->validate();)
551
552 int count = fPathRef->countPoints();
553 if (count == 0) {
554 this->moveTo(x, y);
555 } else {
556 SkPathRef::Editor ed(&fPathRef);
557 ed.atPoint(count-1)->set(x, y);
558 }
559}
560
561// This is the public-facing non-const setConvexity().
562void SkPath::setConvexityType(SkPathConvexityType c) {
563 fConvexity.store((uint8_t)c, std::memory_order_relaxed);
564}
565
566// Const hooks for working with fConvexity and fFirstDirection from const methods.
567void SkPath::setConvexityType(SkPathConvexityType c) const {
568 fConvexity.store((uint8_t)c, std::memory_order_relaxed);
569}
570void SkPath::setFirstDirection(uint8_t d) const {
571 fFirstDirection.store(d, std::memory_order_relaxed);
572}
573uint8_t SkPath::getFirstDirection() const {
574 return fFirstDirection.load(std::memory_order_relaxed);
575}
576
577//////////////////////////////////////////////////////////////////////////////
578// Construction methods
579
580SkPath& SkPath::dirtyAfterEdit() {
581 this->setConvexityType(SkPathConvexityType::kUnknown);
582 this->setFirstDirection(SkPathPriv::kUnknown_FirstDirection);
583 return *this;
584}
585
586void SkPath::incReserve(int inc) {
587 SkDEBUGCODE(this->validate();)
588 if (inc > 0) {
589 SkPathRef::Editor(&fPathRef, inc, inc);
590 }
591 SkDEBUGCODE(this->validate();)
592}
593
594SkPath& SkPath::moveTo(SkScalar x, SkScalar y) {
595 SkDEBUGCODE(this->validate();)
596
597 SkPathRef::Editor ed(&fPathRef);
598
599 // remember our index
600 fLastMoveToIndex = fPathRef->countPoints();
601
602 ed.growForVerb(kMove_Verb)->set(x, y);
603
604 return this->dirtyAfterEdit();
605}
606
607SkPath& SkPath::rMoveTo(SkScalar x, SkScalar y) {
608 SkPoint pt;
609 this->getLastPt(&pt);
610 return this->moveTo(pt.fX + x, pt.fY + y);
611}
612
613void SkPath::injectMoveToIfNeeded() {
614 if (fLastMoveToIndex < 0) {
615 SkScalar x, y;
616 if (fPathRef->countVerbs() == 0) {
617 x = y = 0;
618 } else {
619 const SkPoint& pt = fPathRef->atPoint(~fLastMoveToIndex);
620 x = pt.fX;
621 y = pt.fY;
622 }
623 this->moveTo(x, y);
624 }
625}
626
627SkPath& SkPath::lineTo(SkScalar x, SkScalar y) {
628 SkDEBUGCODE(this->validate();)
629
630 this->injectMoveToIfNeeded();
631
632 SkPathRef::Editor ed(&fPathRef);
633 ed.growForVerb(kLine_Verb)->set(x, y);
634
635 return this->dirtyAfterEdit();
636}
637
638SkPath& SkPath::rLineTo(SkScalar x, SkScalar y) {
639 this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt().
640 SkPoint pt;
641 this->getLastPt(&pt);
642 return this->lineTo(pt.fX + x, pt.fY + y);
643}
644
645SkPath& SkPath::quadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) {
646 SkDEBUGCODE(this->validate();)
647
648 this->injectMoveToIfNeeded();
649
650 SkPathRef::Editor ed(&fPathRef);
651 SkPoint* pts = ed.growForVerb(kQuad_Verb);
652 pts[0].set(x1, y1);
653 pts[1].set(x2, y2);
654
655 return this->dirtyAfterEdit();
656}
657
658SkPath& SkPath::rQuadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) {
659 this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt().
660 SkPoint pt;
661 this->getLastPt(&pt);
662 return this->quadTo(pt.fX + x1, pt.fY + y1, pt.fX + x2, pt.fY + y2);
663}
664
665SkPath& SkPath::conicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
666 SkScalar w) {
667 // check for <= 0 or NaN with this test
668 if (!(w > 0)) {
669 this->lineTo(x2, y2);
670 } else if (!SkScalarIsFinite(w)) {
671 this->lineTo(x1, y1);
672 this->lineTo(x2, y2);
673 } else if (SK_Scalar1 == w) {
674 this->quadTo(x1, y1, x2, y2);
675 } else {
676 SkDEBUGCODE(this->validate();)
677
678 this->injectMoveToIfNeeded();
679
680 SkPathRef::Editor ed(&fPathRef);
681 SkPoint* pts = ed.growForVerb(kConic_Verb, w);
682 pts[0].set(x1, y1);
683 pts[1].set(x2, y2);
684
685 (void)this->dirtyAfterEdit();
686 }
687 return *this;
688}
689
690SkPath& SkPath::rConicTo(SkScalar dx1, SkScalar dy1, SkScalar dx2, SkScalar dy2,
691 SkScalar w) {
692 this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt().
693 SkPoint pt;
694 this->getLastPt(&pt);
695 return this->conicTo(pt.fX + dx1, pt.fY + dy1, pt.fX + dx2, pt.fY + dy2, w);
696}
697
698SkPath& SkPath::cubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
699 SkScalar x3, SkScalar y3) {
700 SkDEBUGCODE(this->validate();)
701
702 this->injectMoveToIfNeeded();
703
704 SkPathRef::Editor ed(&fPathRef);
705 SkPoint* pts = ed.growForVerb(kCubic_Verb);
706 pts[0].set(x1, y1);
707 pts[1].set(x2, y2);
708 pts[2].set(x3, y3);
709
710 return this->dirtyAfterEdit();
711}
712
713SkPath& SkPath::rCubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
714 SkScalar x3, SkScalar y3) {
715 this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt().
716 SkPoint pt;
717 this->getLastPt(&pt);
718 return this->cubicTo(pt.fX + x1, pt.fY + y1, pt.fX + x2, pt.fY + y2,
719 pt.fX + x3, pt.fY + y3);
720}
721
722SkPath& SkPath::close() {
723 SkDEBUGCODE(this->validate();)
724
725 int count = fPathRef->countVerbs();
726 if (count > 0) {
727 switch (fPathRef->atVerb(count - 1)) {
728 case kLine_Verb:
729 case kQuad_Verb:
730 case kConic_Verb:
731 case kCubic_Verb:
732 case kMove_Verb: {
733 SkPathRef::Editor ed(&fPathRef);
734 ed.growForVerb(kClose_Verb);
735 break;
736 }
737 case kClose_Verb:
738 // don't add a close if it's the first verb or a repeat
739 break;
740 default:
741 SkDEBUGFAIL("unexpected verb");
742 break;
743 }
744 }
745
746 // signal that we need a moveTo to follow us (unless we're done)
747#if 0
748 if (fLastMoveToIndex >= 0) {
749 fLastMoveToIndex = ~fLastMoveToIndex;
750 }
751#else
752 fLastMoveToIndex ^= ~fLastMoveToIndex >> (8 * sizeof(fLastMoveToIndex) - 1);
753#endif
754 return *this;
755}
756
757///////////////////////////////////////////////////////////////////////////////
758
759static void assert_known_direction(SkPathDirection dir) {
760 SkASSERT(SkPathDirection::kCW == dir || SkPathDirection::kCCW == dir);
761}
762
763SkPath& SkPath::addRect(const SkRect& rect, SkPathDirection dir) {
764 return this->addRect(rect, dir, 0);
765}
766
767SkPath& SkPath::addRect(SkScalar left, SkScalar top, SkScalar right,
768 SkScalar bottom, SkPathDirection dir) {
769 return this->addRect(SkRect::MakeLTRB(left, top, right, bottom), dir, 0);
770}
771
772SkPath& SkPath::addRect(const SkRect &rect, SkPathDirection dir, unsigned startIndex) {
773 assert_known_direction(dir);
774 this->setFirstDirection(this->hasOnlyMoveTos() ? (SkPathPriv::FirstDirection)dir
775 : SkPathPriv::kUnknown_FirstDirection);
776 SkAutoDisableDirectionCheck addc(this);
777 SkAutoPathBoundsUpdate apbu(this, rect);
778
779 SkDEBUGCODE(int initialVerbCount = this->countVerbs());
780
781 const int kVerbs = 5; // moveTo + 3x lineTo + close
782 this->incReserve(kVerbs);
783
784 SkPath_RectPointIterator iter(rect, dir, startIndex);
785
786 this->moveTo(iter.current());
787 this->lineTo(iter.next());
788 this->lineTo(iter.next());
789 this->lineTo(iter.next());
790 this->close();
791
792 SkASSERT(this->countVerbs() == initialVerbCount + kVerbs);
793 return *this;
794}
795
796SkPath& SkPath::addPoly(const SkPoint pts[], int count, bool close) {
797 SkDEBUGCODE(this->validate();)
798 if (count <= 0) {
799 return *this;
800 }
801
802 fLastMoveToIndex = fPathRef->countPoints();
803
804 // +close makes room for the extra kClose_Verb
805 SkPathRef::Editor ed(&fPathRef, count+close, count);
806
807 ed.growForVerb(kMove_Verb)->set(pts[0].fX, pts[0].fY);
808 if (count > 1) {
809 SkPoint* p = ed.growForRepeatedVerb(kLine_Verb, count - 1);
810 memcpy(p, &pts[1], (count-1) * sizeof(SkPoint));
811 }
812
813 if (close) {
814 ed.growForVerb(kClose_Verb);
815 fLastMoveToIndex ^= ~fLastMoveToIndex >> (8 * sizeof(fLastMoveToIndex) - 1);
816 }
817
818 (void)this->dirtyAfterEdit();
819 SkDEBUGCODE(this->validate();)
820 return *this;
821}
822
823#include "src/core/SkGeometry.h"
824
825static bool arc_is_lone_point(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle,
826 SkPoint* pt) {
827 if (0 == sweepAngle && (0 == startAngle || SkIntToScalar(360) == startAngle)) {
828 // Chrome uses this path to move into and out of ovals. If not
829 // treated as a special case the moves can distort the oval's
830 // bounding box (and break the circle special case).
831 pt->set(oval.fRight, oval.centerY());
832 return true;
833 } else if (0 == oval.width() && 0 == oval.height()) {
834 // Chrome will sometimes create 0 radius round rects. Having degenerate
835 // quad segments in the path prevents the path from being recognized as
836 // a rect.
837 // TODO: optimizing the case where only one of width or height is zero
838 // should also be considered. This case, however, doesn't seem to be
839 // as common as the single point case.
840 pt->set(oval.fRight, oval.fTop);
841 return true;
842 }
843 return false;
844}
845
846// Return the unit vectors pointing at the start/stop points for the given start/sweep angles
847//
848static void angles_to_unit_vectors(SkScalar startAngle, SkScalar sweepAngle,
849 SkVector* startV, SkVector* stopV, SkRotationDirection* dir) {
850 SkScalar startRad = SkDegreesToRadians(startAngle),
851 stopRad = SkDegreesToRadians(startAngle + sweepAngle);
852
853 startV->fY = SkScalarSinSnapToZero(startRad);
854 startV->fX = SkScalarCosSnapToZero(startRad);
855 stopV->fY = SkScalarSinSnapToZero(stopRad);
856 stopV->fX = SkScalarCosSnapToZero(stopRad);
857
858 /* If the sweep angle is nearly (but less than) 360, then due to precision
859 loss in radians-conversion and/or sin/cos, we may end up with coincident
860 vectors, which will fool SkBuildQuadArc into doing nothing (bad) instead
861 of drawing a nearly complete circle (good).
862 e.g. canvas.drawArc(0, 359.99, ...)
863 -vs- canvas.drawArc(0, 359.9, ...)
864 We try to detect this edge case, and tweak the stop vector
865 */
866 if (*startV == *stopV) {
867 SkScalar sw = SkScalarAbs(sweepAngle);
868 if (sw < SkIntToScalar(360) && sw > SkIntToScalar(359)) {
869 // make a guess at a tiny angle (in radians) to tweak by
870 SkScalar deltaRad = SkScalarCopySign(SK_Scalar1/512, sweepAngle);
871 // not sure how much will be enough, so we use a loop
872 do {
873 stopRad -= deltaRad;
874 stopV->fY = SkScalarSinSnapToZero(stopRad);
875 stopV->fX = SkScalarCosSnapToZero(stopRad);
876 } while (*startV == *stopV);
877 }
878 }
879 *dir = sweepAngle > 0 ? kCW_SkRotationDirection : kCCW_SkRotationDirection;
880}
881
882/**
883 * If this returns 0, then the caller should just line-to the singlePt, else it should
884 * ignore singlePt and append the specified number of conics.
885 */
886static int build_arc_conics(const SkRect& oval, const SkVector& start, const SkVector& stop,
887 SkRotationDirection dir, SkConic conics[SkConic::kMaxConicsForArc],
888 SkPoint* singlePt) {
889 SkMatrix matrix;
890
891 matrix.setScale(SkScalarHalf(oval.width()), SkScalarHalf(oval.height()));
892 matrix.postTranslate(oval.centerX(), oval.centerY());
893
894 int count = SkConic::BuildUnitArc(start, stop, dir, &matrix, conics);
895 if (0 == count) {
896 matrix.mapXY(stop.x(), stop.y(), singlePt);
897 }
898 return count;
899}
900
901SkPath& SkPath::addRoundRect(const SkRect& rect, const SkScalar radii[],
902 SkPathDirection dir) {
903 SkRRect rrect;
904 rrect.setRectRadii(rect, (const SkVector*) radii);
905 return this->addRRect(rrect, dir);
906}
907
908SkPath& SkPath::addRRect(const SkRRect& rrect, SkPathDirection dir) {
909 // legacy start indices: 6 (CW) and 7(CCW)
910 return this->addRRect(rrect, dir, dir == SkPathDirection::kCW ? 6 : 7);
911}
912
913SkPath& SkPath::addRRect(const SkRRect &rrect, SkPathDirection dir, unsigned startIndex) {
914 assert_known_direction(dir);
915
916 bool isRRect = hasOnlyMoveTos();
917 const SkRect& bounds = rrect.getBounds();
918
919 if (rrect.isRect() || rrect.isEmpty()) {
920 // degenerate(rect) => radii points are collapsing
921 this->addRect(bounds, dir, (startIndex + 1) / 2);
922 } else if (rrect.isOval()) {
923 // degenerate(oval) => line points are collapsing
924 this->addOval(bounds, dir, startIndex / 2);
925 } else {
926 this->setFirstDirection(this->hasOnlyMoveTos() ? (SkPathPriv::FirstDirection)dir
927 : SkPathPriv::kUnknown_FirstDirection);
928
929 SkAutoPathBoundsUpdate apbu(this, bounds);
930 SkAutoDisableDirectionCheck addc(this);
931
932 // we start with a conic on odd indices when moving CW vs. even indices when moving CCW
933 const bool startsWithConic = ((startIndex & 1) == (dir == SkPathDirection::kCW));
934 const SkScalar weight = SK_ScalarRoot2Over2;
935
936 SkDEBUGCODE(int initialVerbCount = this->countVerbs());
937 const int kVerbs = startsWithConic
938 ? 9 // moveTo + 4x conicTo + 3x lineTo + close
939 : 10; // moveTo + 4x lineTo + 4x conicTo + close
940 this->incReserve(kVerbs);
941
942 SkPath_RRectPointIterator rrectIter(rrect, dir, startIndex);
943 // Corner iterator indices follow the collapsed radii model,
944 // adjusted such that the start pt is "behind" the radii start pt.
945 const unsigned rectStartIndex = startIndex / 2 + (dir == SkPathDirection::kCW ? 0 : 1);
946 SkPath_RectPointIterator rectIter(bounds, dir, rectStartIndex);
947
948 this->moveTo(rrectIter.current());
949 if (startsWithConic) {
950 for (unsigned i = 0; i < 3; ++i) {
951 this->conicTo(rectIter.next(), rrectIter.next(), weight);
952 this->lineTo(rrectIter.next());
953 }
954 this->conicTo(rectIter.next(), rrectIter.next(), weight);
955 // final lineTo handled by close().
956 } else {
957 for (unsigned i = 0; i < 4; ++i) {
958 this->lineTo(rrectIter.next());
959 this->conicTo(rectIter.next(), rrectIter.next(), weight);
960 }
961 }
962 this->close();
963
964 SkPathRef::Editor ed(&fPathRef);
965 ed.setIsRRect(isRRect, dir == SkPathDirection::kCCW, startIndex % 8);
966
967 SkASSERT(this->countVerbs() == initialVerbCount + kVerbs);
968 }
969
970 SkDEBUGCODE(fPathRef->validate();)
971 return *this;
972}
973
974bool SkPath::hasOnlyMoveTos() const {
975 int count = fPathRef->countVerbs();
976 const uint8_t* verbs = fPathRef->verbsBegin();
977 for (int i = 0; i < count; ++i) {
978 if (*verbs == kLine_Verb ||
979 *verbs == kQuad_Verb ||
980 *verbs == kConic_Verb ||
981 *verbs == kCubic_Verb) {
982 return false;
983 }
984 ++verbs;
985 }
986 return true;
987}
988
989bool SkPath::isZeroLengthSincePoint(int startPtIndex) const {
990 int count = fPathRef->countPoints() - startPtIndex;
991 if (count < 2) {
992 return true;
993 }
994 const SkPoint* pts = fPathRef.get()->points() + startPtIndex;
995 const SkPoint& first = *pts;
996 for (int index = 1; index < count; ++index) {
997 if (first != pts[index]) {
998 return false;
999 }
1000 }
1001 return true;
1002}
1003
1004SkPath& SkPath::addRoundRect(const SkRect& rect, SkScalar rx, SkScalar ry,
1005 SkPathDirection dir) {
1006 assert_known_direction(dir);
1007
1008 if (rx < 0 || ry < 0) {
1009 return *this;
1010 }
1011
1012 SkRRect rrect;
1013 rrect.setRectXY(rect, rx, ry);
1014 return this->addRRect(rrect, dir);
1015}
1016
1017SkPath& SkPath::addOval(const SkRect& oval, SkPathDirection dir) {
1018 // legacy start index: 1
1019 return this->addOval(oval, dir, 1);
1020}
1021
1022SkPath& SkPath::addOval(const SkRect &oval, SkPathDirection dir, unsigned startPointIndex) {
1023 assert_known_direction(dir);
1024
1025 /* If addOval() is called after previous moveTo(),
1026 this path is still marked as an oval. This is used to
1027 fit into WebKit's calling sequences.
1028 We can't simply check isEmpty() in this case, as additional
1029 moveTo() would mark the path non empty.
1030 */
1031 bool isOval = hasOnlyMoveTos();
1032 if (isOval) {
1033 this->setFirstDirection((SkPathPriv::FirstDirection)dir);
1034 } else {
1035 this->setFirstDirection(SkPathPriv::kUnknown_FirstDirection);
1036 }
1037
1038 SkAutoDisableDirectionCheck addc(this);
1039 SkAutoPathBoundsUpdate apbu(this, oval);
1040
1041 SkDEBUGCODE(int initialVerbCount = this->countVerbs());
1042 const int kVerbs = 6; // moveTo + 4x conicTo + close
1043 this->incReserve(kVerbs);
1044
1045 SkPath_OvalPointIterator ovalIter(oval, dir, startPointIndex);
1046 // The corner iterator pts are tracking "behind" the oval/radii pts.
1047 SkPath_RectPointIterator rectIter(oval, dir, startPointIndex + (dir == SkPathDirection::kCW ? 0 : 1));
1048 const SkScalar weight = SK_ScalarRoot2Over2;
1049
1050 this->moveTo(ovalIter.current());
1051 for (unsigned i = 0; i < 4; ++i) {
1052 this->conicTo(rectIter.next(), ovalIter.next(), weight);
1053 }
1054 this->close();
1055
1056 SkASSERT(this->countVerbs() == initialVerbCount + kVerbs);
1057
1058 SkPathRef::Editor ed(&fPathRef);
1059
1060 ed.setIsOval(isOval, SkPathDirection::kCCW == dir, startPointIndex % 4);
1061 return *this;
1062}
1063
1064SkPath& SkPath::addCircle(SkScalar x, SkScalar y, SkScalar r, SkPathDirection dir) {
1065 if (r > 0) {
1066 this->addOval(SkRect::MakeLTRB(x - r, y - r, x + r, y + r), dir);
1067 }
1068 return *this;
1069}
1070
1071SkPath& SkPath::arcTo(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle,
1072 bool forceMoveTo) {
1073 if (oval.width() < 0 || oval.height() < 0) {
1074 return *this;
1075 }
1076
1077 if (fPathRef->countVerbs() == 0) {
1078 forceMoveTo = true;
1079 }
1080
1081 SkPoint lonePt;
1082 if (arc_is_lone_point(oval, startAngle, sweepAngle, &lonePt)) {
1083 return forceMoveTo ? this->moveTo(lonePt) : this->lineTo(lonePt);
1084 }
1085
1086 SkVector startV, stopV;
1087 SkRotationDirection dir;
1088 angles_to_unit_vectors(startAngle, sweepAngle, &startV, &stopV, &dir);
1089
1090 SkPoint singlePt;
1091
1092 // Adds a move-to to 'pt' if forceMoveTo is true. Otherwise a lineTo unless we're sufficiently
1093 // close to 'pt' currently. This prevents spurious lineTos when adding a series of contiguous
1094 // arcs from the same oval.
1095 auto addPt = [&forceMoveTo, this](const SkPoint& pt) {
1096 SkPoint lastPt;
1097 if (forceMoveTo) {
1098 this->moveTo(pt);
1099 } else if (!this->getLastPt(&lastPt) ||
1100 !SkScalarNearlyEqual(lastPt.fX, pt.fX) ||
1101 !SkScalarNearlyEqual(lastPt.fY, pt.fY)) {
1102 this->lineTo(pt);
1103 }
1104 };
1105
1106 // At this point, we know that the arc is not a lone point, but startV == stopV
1107 // indicates that the sweepAngle is too small such that angles_to_unit_vectors
1108 // cannot handle it.
1109 if (startV == stopV) {
1110 SkScalar endAngle = SkDegreesToRadians(startAngle + sweepAngle);
1111 SkScalar radiusX = oval.width() / 2;
1112 SkScalar radiusY = oval.height() / 2;
1113 // We do not use SkScalar[Sin|Cos]SnapToZero here. When sin(startAngle) is 0 and sweepAngle
1114 // is very small and radius is huge, the expected behavior here is to draw a line. But
1115 // calling SkScalarSinSnapToZero will make sin(endAngle) be 0 which will then draw a dot.
1116 singlePt.set(oval.centerX() + radiusX * SkScalarCos(endAngle),
1117 oval.centerY() + radiusY * SkScalarSin(endAngle));
1118 addPt(singlePt);
1119 return *this;
1120 }
1121
1122 SkConic conics[SkConic::kMaxConicsForArc];
1123 int count = build_arc_conics(oval, startV, stopV, dir, conics, &singlePt);
1124 if (count) {
1125 this->incReserve(count * 2 + 1);
1126 const SkPoint& pt = conics[0].fPts[0];
1127 addPt(pt);
1128 for (int i = 0; i < count; ++i) {
1129 this->conicTo(conics[i].fPts[1], conics[i].fPts[2], conics[i].fW);
1130 }
1131 } else {
1132 addPt(singlePt);
1133 }
1134 return *this;
1135}
1136
1137// This converts the SVG arc to conics.
1138// Partly adapted from Niko's code in kdelibs/kdecore/svgicons.
1139// Then transcribed from webkit/chrome's SVGPathNormalizer::decomposeArcToCubic()
1140// See also SVG implementation notes:
1141// http://www.w3.org/TR/SVG/implnote.html#ArcConversionEndpointToCenter
1142// Note that arcSweep bool value is flipped from the original implementation.
1143SkPath& SkPath::arcTo(SkScalar rx, SkScalar ry, SkScalar angle, SkPath::ArcSize arcLarge,
1144 SkPathDirection arcSweep, SkScalar x, SkScalar y) {
1145 this->injectMoveToIfNeeded();
1146 SkPoint srcPts[2];
1147 this->getLastPt(&srcPts[0]);
1148 // If rx = 0 or ry = 0 then this arc is treated as a straight line segment (a "lineto")
1149 // joining the endpoints.
1150 // http://www.w3.org/TR/SVG/implnote.html#ArcOutOfRangeParameters
1151 if (!rx || !ry) {
1152 return this->lineTo(x, y);
1153 }
1154 // If the current point and target point for the arc are identical, it should be treated as a
1155 // zero length path. This ensures continuity in animations.
1156 srcPts[1].set(x, y);
1157 if (srcPts[0] == srcPts[1]) {
1158 return this->lineTo(x, y);
1159 }
1160 rx = SkScalarAbs(rx);
1161 ry = SkScalarAbs(ry);
1162 SkVector midPointDistance = srcPts[0] - srcPts[1];
1163 midPointDistance *= 0.5f;
1164
1165 SkMatrix pointTransform;
1166 pointTransform.setRotate(-angle);
1167
1168 SkPoint transformedMidPoint;
1169 pointTransform.mapPoints(&transformedMidPoint, &midPointDistance, 1);
1170 SkScalar squareRx = rx * rx;
1171 SkScalar squareRy = ry * ry;
1172 SkScalar squareX = transformedMidPoint.fX * transformedMidPoint.fX;
1173 SkScalar squareY = transformedMidPoint.fY * transformedMidPoint.fY;
1174
1175 // Check if the radii are big enough to draw the arc, scale radii if not.
1176 // http://www.w3.org/TR/SVG/implnote.html#ArcCorrectionOutOfRangeRadii
1177 SkScalar radiiScale = squareX / squareRx + squareY / squareRy;
1178 if (radiiScale > 1) {
1179 radiiScale = SkScalarSqrt(radiiScale);
1180 rx *= radiiScale;
1181 ry *= radiiScale;
1182 }
1183
1184 pointTransform.setScale(1 / rx, 1 / ry);
1185 pointTransform.preRotate(-angle);
1186
1187 SkPoint unitPts[2];
1188 pointTransform.mapPoints(unitPts, srcPts, (int) SK_ARRAY_COUNT(unitPts));
1189 SkVector delta = unitPts[1] - unitPts[0];
1190
1191 SkScalar d = delta.fX * delta.fX + delta.fY * delta.fY;
1192 SkScalar scaleFactorSquared = std::max(1 / d - 0.25f, 0.f);
1193
1194 SkScalar scaleFactor = SkScalarSqrt(scaleFactorSquared);
1195 if ((arcSweep == SkPathDirection::kCCW) != SkToBool(arcLarge)) { // flipped from the original implementation
1196 scaleFactor = -scaleFactor;
1197 }
1198 delta.scale(scaleFactor);
1199 SkPoint centerPoint = unitPts[0] + unitPts[1];
1200 centerPoint *= 0.5f;
1201 centerPoint.offset(-delta.fY, delta.fX);
1202 unitPts[0] -= centerPoint;
1203 unitPts[1] -= centerPoint;
1204 SkScalar theta1 = SkScalarATan2(unitPts[0].fY, unitPts[0].fX);
1205 SkScalar theta2 = SkScalarATan2(unitPts[1].fY, unitPts[1].fX);
1206 SkScalar thetaArc = theta2 - theta1;
1207 if (thetaArc < 0 && (arcSweep == SkPathDirection::kCW)) { // arcSweep flipped from the original implementation
1208 thetaArc += SK_ScalarPI * 2;
1209 } else if (thetaArc > 0 && (arcSweep != SkPathDirection::kCW)) { // arcSweep flipped from the original implementation
1210 thetaArc -= SK_ScalarPI * 2;
1211 }
1212
1213 // Very tiny angles cause our subsequent math to go wonky (skbug.com/9272)
1214 // so we do a quick check here. The precise tolerance amount is just made up.
1215 // PI/million happens to fix the bug in 9272, but a larger value is probably
1216 // ok too.
1217 if (SkScalarAbs(thetaArc) < (SK_ScalarPI / (1000 * 1000))) {
1218 return this->lineTo(x, y);
1219 }
1220
1221 pointTransform.setRotate(angle);
1222 pointTransform.preScale(rx, ry);
1223
1224 // the arc may be slightly bigger than 1/4 circle, so allow up to 1/3rd
1225 int segments = SkScalarCeilToInt(SkScalarAbs(thetaArc / (2 * SK_ScalarPI / 3)));
1226 SkScalar thetaWidth = thetaArc / segments;
1227 SkScalar t = SkScalarTan(0.5f * thetaWidth);
1228 if (!SkScalarIsFinite(t)) {
1229 return *this;
1230 }
1231 SkScalar startTheta = theta1;
1232 SkScalar w = SkScalarSqrt(SK_ScalarHalf + SkScalarCos(thetaWidth) * SK_ScalarHalf);
1233 auto scalar_is_integer = [](SkScalar scalar) -> bool {
1234 return scalar == SkScalarFloorToScalar(scalar);
1235 };
1236 bool expectIntegers = SkScalarNearlyZero(SK_ScalarPI/2 - SkScalarAbs(thetaWidth)) &&
1237 scalar_is_integer(rx) && scalar_is_integer(ry) &&
1238 scalar_is_integer(x) && scalar_is_integer(y);
1239
1240 for (int i = 0; i < segments; ++i) {
1241 SkScalar endTheta = startTheta + thetaWidth,
1242 sinEndTheta = SkScalarSinSnapToZero(endTheta),
1243 cosEndTheta = SkScalarCosSnapToZero(endTheta);
1244
1245 unitPts[1].set(cosEndTheta, sinEndTheta);
1246 unitPts[1] += centerPoint;
1247 unitPts[0] = unitPts[1];
1248 unitPts[0].offset(t * sinEndTheta, -t * cosEndTheta);
1249 SkPoint mapped[2];
1250 pointTransform.mapPoints(mapped, unitPts, (int) SK_ARRAY_COUNT(unitPts));
1251 /*
1252 Computing the arc width introduces rounding errors that cause arcs to start
1253 outside their marks. A round rect may lose convexity as a result. If the input
1254 values are on integers, place the conic on integers as well.
1255 */
1256 if (expectIntegers) {
1257 for (SkPoint& point : mapped) {
1258 point.fX = SkScalarRoundToScalar(point.fX);
1259 point.fY = SkScalarRoundToScalar(point.fY);
1260 }
1261 }
1262 this->conicTo(mapped[0], mapped[1], w);
1263 startTheta = endTheta;
1264 }
1265
1266#ifndef SK_LEGACY_PATH_ARCTO_ENDPOINT
1267 // The final point should match the input point (by definition); replace it to
1268 // ensure that rounding errors in the above math don't cause any problems.
1269 this->setLastPt(x, y);
1270#endif
1271 return *this;
1272}
1273
1274SkPath& SkPath::rArcTo(SkScalar rx, SkScalar ry, SkScalar xAxisRotate, SkPath::ArcSize largeArc,
1275 SkPathDirection sweep, SkScalar dx, SkScalar dy) {
1276 SkPoint currentPoint;
1277 this->getLastPt(&currentPoint);
1278 return this->arcTo(rx, ry, xAxisRotate, largeArc, sweep,
1279 currentPoint.fX + dx, currentPoint.fY + dy);
1280}
1281
1282SkPath& SkPath::addArc(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle) {
1283 if (oval.isEmpty() || 0 == sweepAngle) {
1284 return *this;
1285 }
1286
1287 const SkScalar kFullCircleAngle = SkIntToScalar(360);
1288
1289 if (sweepAngle >= kFullCircleAngle || sweepAngle <= -kFullCircleAngle) {
1290 // We can treat the arc as an oval if it begins at one of our legal starting positions.
1291 // See SkPath::addOval() docs.
1292 SkScalar startOver90 = startAngle / 90.f;
1293 SkScalar startOver90I = SkScalarRoundToScalar(startOver90);
1294 SkScalar error = startOver90 - startOver90I;
1295 if (SkScalarNearlyEqual(error, 0)) {
1296 // Index 1 is at startAngle == 0.
1297 SkScalar startIndex = std::fmod(startOver90I + 1.f, 4.f);
1298 startIndex = startIndex < 0 ? startIndex + 4.f : startIndex;
1299 return this->addOval(oval, sweepAngle > 0 ? SkPathDirection::kCW : SkPathDirection::kCCW,
1300 (unsigned) startIndex);
1301 }
1302 }
1303 return this->arcTo(oval, startAngle, sweepAngle, true);
1304}
1305
1306/*
1307 Need to handle the case when the angle is sharp, and our computed end-points
1308 for the arc go behind pt1 and/or p2...
1309*/
1310SkPath& SkPath::arcTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2, SkScalar radius) {
1311 if (radius == 0) {
1312 return this->lineTo(x1, y1);
1313 }
1314
1315 // need to know our prev pt so we can construct tangent vectors
1316 SkPoint start;
1317 this->getLastPt(&start);
1318
1319 // need double precision for these calcs.
1320 SkDVector befored, afterd;
1321 befored.set({x1 - start.fX, y1 - start.fY}).normalize();
1322 afterd.set({x2 - x1, y2 - y1}).normalize();
1323 double cosh = befored.dot(afterd);
1324 double sinh = befored.cross(afterd);
1325
1326 if (!befored.isFinite() || !afterd.isFinite() || SkScalarNearlyZero(SkDoubleToScalar(sinh))) {
1327 return this->lineTo(x1, y1);
1328 }
1329
1330 // safe to convert back to floats now
1331 SkVector before = befored.asSkVector();
1332 SkVector after = afterd.asSkVector();
1333 SkScalar dist = SkScalarAbs(SkDoubleToScalar(radius * (1 - cosh) / sinh));
1334 SkScalar xx = x1 - dist * before.fX;
1335 SkScalar yy = y1 - dist * before.fY;
1336 after.setLength(dist);
1337 this->lineTo(xx, yy);
1338 SkScalar weight = SkScalarSqrt(SkDoubleToScalar(SK_ScalarHalf + cosh * 0.5));
1339 return this->conicTo(x1, y1, x1 + after.fX, y1 + after.fY, weight);
1340}
1341
1342///////////////////////////////////////////////////////////////////////////////
1343
1344SkPath& SkPath::addPath(const SkPath& path, SkScalar dx, SkScalar dy, AddPathMode mode) {
1345 SkMatrix matrix;
1346
1347 matrix.setTranslate(dx, dy);
1348 return this->addPath(path, matrix, mode);
1349}
1350
1351SkPath& SkPath::addPath(const SkPath& srcPath, const SkMatrix& matrix, AddPathMode mode) {
1352 if (srcPath.isEmpty()) {
1353 return *this;
1354 }
1355
1356 // Detect if we're trying to add ourself
1357 const SkPath* src = &srcPath;
1358 SkTLazy<SkPath> tmp;
1359 if (this == src) {
1360 src = tmp.set(srcPath);
1361 }
1362
1363 if (kAppend_AddPathMode == mode && !matrix.hasPerspective()) {
1364 if (src->fLastMoveToIndex >= 0) {
1365 fLastMoveToIndex = this->countPoints() + src->fLastMoveToIndex;
1366 }
1367 SkPathRef::Editor ed(&fPathRef);
1368 auto [newPts, newWeights] = ed.growForVerbsInPath(*src->fPathRef);
1369 matrix.mapPoints(newPts, src->fPathRef->points(), src->countPoints());
1370 if (int numWeights = src->fPathRef->countWeights()) {
1371 memcpy(newWeights, src->fPathRef->conicWeights(), numWeights * sizeof(newWeights[0]));
1372 }
1373 return this->dirtyAfterEdit();
1374 }
1375
1376 SkPathRef::Editor(&fPathRef, src->countVerbs(), src->countPoints());
1377
1378 RawIter iter(*src);
1379 SkPoint pts[4];
1380 Verb verb;
1381
1382 SkMatrixPriv::MapPtsProc proc = SkMatrixPriv::GetMapPtsProc(matrix);
1383 bool firstVerb = true;
1384 while ((verb = iter.next(pts)) != kDone_Verb) {
1385 switch (verb) {
1386 case kMove_Verb:
1387 proc(matrix, &pts[0], &pts[0], 1);
1388 if (firstVerb && !isEmpty()) {
1389 SkASSERT(mode == kExtend_AddPathMode);
1390 injectMoveToIfNeeded(); // In case last contour is closed
1391 SkPoint lastPt;
1392 // don't add lineTo if it is degenerate
1393 if (fLastMoveToIndex < 0 || !this->getLastPt(&lastPt) || lastPt != pts[0]) {
1394 this->lineTo(pts[0]);
1395 }
1396 } else {
1397 this->moveTo(pts[0]);
1398 }
1399 break;
1400 case kLine_Verb:
1401 proc(matrix, &pts[1], &pts[1], 1);
1402 this->lineTo(pts[1]);
1403 break;
1404 case kQuad_Verb:
1405 proc(matrix, &pts[1], &pts[1], 2);
1406 this->quadTo(pts[1], pts[2]);
1407 break;
1408 case kConic_Verb:
1409 proc(matrix, &pts[1], &pts[1], 2);
1410 this->conicTo(pts[1], pts[2], iter.conicWeight());
1411 break;
1412 case kCubic_Verb:
1413 proc(matrix, &pts[1], &pts[1], 3);
1414 this->cubicTo(pts[1], pts[2], pts[3]);
1415 break;
1416 case kClose_Verb:
1417 this->close();
1418 break;
1419 default:
1420 SkDEBUGFAIL("unknown verb");
1421 }
1422 firstVerb = false;
1423 }
1424 return *this;
1425}
1426
1427///////////////////////////////////////////////////////////////////////////////
1428
1429static int pts_in_verb(unsigned verb) {
1430 static const uint8_t gPtsInVerb[] = {
1431 1, // kMove
1432 1, // kLine
1433 2, // kQuad
1434 2, // kConic
1435 3, // kCubic
1436 0, // kClose
1437 0 // kDone
1438 };
1439
1440 SkASSERT(verb < SK_ARRAY_COUNT(gPtsInVerb));
1441 return gPtsInVerb[verb];
1442}
1443
1444// ignore the last point of the 1st contour
1445SkPath& SkPath::reversePathTo(const SkPath& path) {
1446 if (path.fPathRef->fVerbs.count() == 0) {
1447 return *this;
1448 }
1449
1450 const uint8_t* verbs = path.fPathRef->verbsEnd();
1451 const uint8_t* verbsBegin = path.fPathRef->verbsBegin();
1452 SkASSERT(verbsBegin[0] == kMove_Verb);
1453 const SkPoint* pts = path.fPathRef->pointsEnd() - 1;
1454 const SkScalar* conicWeights = path.fPathRef->conicWeightsEnd();
1455
1456 while (verbs > verbsBegin) {
1457 uint8_t v = *--verbs;
1458 pts -= pts_in_verb(v);
1459 switch (v) {
1460 case kMove_Verb:
1461 // if the path has multiple contours, stop after reversing the last
1462 return *this;
1463 case kLine_Verb:
1464 this->lineTo(pts[0]);
1465 break;
1466 case kQuad_Verb:
1467 this->quadTo(pts[1], pts[0]);
1468 break;
1469 case kConic_Verb:
1470 this->conicTo(pts[1], pts[0], *--conicWeights);
1471 break;
1472 case kCubic_Verb:
1473 this->cubicTo(pts[2], pts[1], pts[0]);
1474 break;
1475 case kClose_Verb:
1476 break;
1477 default:
1478 SkDEBUGFAIL("bad verb");
1479 break;
1480 }
1481 }
1482 return *this;
1483}
1484
1485SkPath& SkPath::reverseAddPath(const SkPath& srcPath) {
1486 // Detect if we're trying to add ourself
1487 const SkPath* src = &srcPath;
1488 SkTLazy<SkPath> tmp;
1489 if (this == src) {
1490 src = tmp.set(srcPath);
1491 }
1492
1493 SkPathRef::Editor ed(&fPathRef, src->countVerbs(), src->countPoints());
1494
1495 const uint8_t* verbsBegin = src->fPathRef->verbsBegin();
1496 const uint8_t* verbs = src->fPathRef->verbsEnd();
1497 const SkPoint* pts = src->fPathRef->pointsEnd();
1498 const SkScalar* conicWeights = src->fPathRef->conicWeightsEnd();
1499
1500 bool needMove = true;
1501 bool needClose = false;
1502 while (verbs > verbsBegin) {
1503 uint8_t v = *--verbs;
1504 int n = pts_in_verb(v);
1505
1506 if (needMove) {
1507 --pts;
1508 this->moveTo(pts->fX, pts->fY);
1509 needMove = false;
1510 }
1511 pts -= n;
1512 switch (v) {
1513 case kMove_Verb:
1514 if (needClose) {
1515 this->close();
1516 needClose = false;
1517 }
1518 needMove = true;
1519 pts += 1; // so we see the point in "if (needMove)" above
1520 break;
1521 case kLine_Verb:
1522 this->lineTo(pts[0]);
1523 break;
1524 case kQuad_Verb:
1525 this->quadTo(pts[1], pts[0]);
1526 break;
1527 case kConic_Verb:
1528 this->conicTo(pts[1], pts[0], *--conicWeights);
1529 break;
1530 case kCubic_Verb:
1531 this->cubicTo(pts[2], pts[1], pts[0]);
1532 break;
1533 case kClose_Verb:
1534 needClose = true;
1535 break;
1536 default:
1537 SkDEBUGFAIL("unexpected verb");
1538 }
1539 }
1540 return *this;
1541}
1542
1543///////////////////////////////////////////////////////////////////////////////
1544
1545void SkPath::offset(SkScalar dx, SkScalar dy, SkPath* dst) const {
1546 SkMatrix matrix;
1547
1548 matrix.setTranslate(dx, dy);
1549 this->transform(matrix, dst);
1550}
1551
1552static void subdivide_cubic_to(SkPath* path, const SkPoint pts[4],
1553 int level = 2) {
1554 if (--level >= 0) {
1555 SkPoint tmp[7];
1556
1557 SkChopCubicAtHalf(pts, tmp);
1558 subdivide_cubic_to(path, &tmp[0], level);
1559 subdivide_cubic_to(path, &tmp[3], level);
1560 } else {
1561 path->cubicTo(pts[1], pts[2], pts[3]);
1562 }
1563}
1564
1565void SkPath::transform(const SkMatrix& matrix, SkPath* dst, SkApplyPerspectiveClip pc) const {
1566 if (matrix.isIdentity()) {
1567 if (dst != nullptr && dst != this) {
1568 *dst = *this;
1569 }
1570 return;
1571 }
1572
1573 SkDEBUGCODE(this->validate();)
1574 if (dst == nullptr) {
1575 dst = (SkPath*)this;
1576 }
1577
1578 if (matrix.hasPerspective()) {
1579 SkPath tmp;
1580 tmp.fFillType = fFillType;
1581
1582 SkPath clipped;
1583 const SkPath* src = this;
1584 if (pc == SkApplyPerspectiveClip::kYes &&
1585 SkPathPriv::PerspectiveClip(*this, matrix, &clipped))
1586 {
1587 src = &clipped;
1588 }
1589
1590 SkPath::Iter iter(*src, false);
1591 SkPoint pts[4];
1592 SkPath::Verb verb;
1593
1594 while ((verb = iter.next(pts)) != kDone_Verb) {
1595 switch (verb) {
1596 case kMove_Verb:
1597 tmp.moveTo(pts[0]);
1598 break;
1599 case kLine_Verb:
1600 tmp.lineTo(pts[1]);
1601 break;
1602 case kQuad_Verb:
1603 // promote the quad to a conic
1604 tmp.conicTo(pts[1], pts[2],
1605 SkConic::TransformW(pts, SK_Scalar1, matrix));
1606 break;
1607 case kConic_Verb:
1608 tmp.conicTo(pts[1], pts[2],
1609 SkConic::TransformW(pts, iter.conicWeight(), matrix));
1610 break;
1611 case kCubic_Verb:
1612 subdivide_cubic_to(&tmp, pts);
1613 break;
1614 case kClose_Verb:
1615 tmp.close();
1616 break;
1617 default:
1618 SkDEBUGFAIL("unknown verb");
1619 break;
1620 }
1621 }
1622
1623 dst->swap(tmp);
1624 SkPathRef::Editor ed(&dst->fPathRef);
1625 matrix.mapPoints(ed.writablePoints(), ed.pathRef()->countPoints());
1626 dst->setFirstDirection(SkPathPriv::kUnknown_FirstDirection);
1627 } else {
1628 SkPathConvexityType convexity = this->getConvexityTypeOrUnknown();
1629
1630 SkPathRef::CreateTransformedCopy(&dst->fPathRef, *fPathRef.get(), matrix);
1631
1632 if (this != dst) {
1633 dst->fLastMoveToIndex = fLastMoveToIndex;
1634 dst->fFillType = fFillType;
1635 dst->fIsVolatile = fIsVolatile;
1636 }
1637
1638 // Due to finite/fragile float numerics, we can't assume that a convex path remains
1639 // convex after a transformation, so mark it as unknown here.
1640 // However, some transformations are thought to be safe:
1641 // axis-aligned values under scale/translate.
1642 //
1643 // See skbug.com/8606
1644 // If we can land a robust convex scan-converter, we may be able to relax/remove this
1645 // check, and keep convex paths marked as such after a general transform...
1646 //
1647 if (matrix.isScaleTranslate() && SkPathPriv::IsAxisAligned(*this)) {
1648 dst->setConvexityType(convexity);
1649 } else {
1650 dst->setConvexityType(SkPathConvexityType::kUnknown);
1651 }
1652
1653 if (this->getFirstDirection() == SkPathPriv::kUnknown_FirstDirection) {
1654 dst->setFirstDirection(SkPathPriv::kUnknown_FirstDirection);
1655 } else {
1656 SkScalar det2x2 =
1657 matrix.get(SkMatrix::kMScaleX) * matrix.get(SkMatrix::kMScaleY) -
1658 matrix.get(SkMatrix::kMSkewX) * matrix.get(SkMatrix::kMSkewY);
1659 if (det2x2 < 0) {
1660 dst->setFirstDirection(
1661 SkPathPriv::OppositeFirstDirection(
1662 (SkPathPriv::FirstDirection)this->getFirstDirection()));
1663 } else if (det2x2 > 0) {
1664 dst->setFirstDirection(this->getFirstDirection());
1665 } else {
1666 dst->setFirstDirection(SkPathPriv::kUnknown_FirstDirection);
1667 }
1668 }
1669
1670 SkDEBUGCODE(dst->validate();)
1671 }
1672}
1673
1674///////////////////////////////////////////////////////////////////////////////
1675///////////////////////////////////////////////////////////////////////////////
1676
1677SkPath::Iter::Iter() {
1678#ifdef SK_DEBUG
1679 fPts = nullptr;
1680 fConicWeights = nullptr;
1681 fMoveTo.fX = fMoveTo.fY = fLastPt.fX = fLastPt.fY = 0;
1682 fForceClose = fCloseLine = false;
1683 fSegmentState = kEmptyContour_SegmentState;
1684#endif
1685 // need to init enough to make next() harmlessly return kDone_Verb
1686 fVerbs = nullptr;
1687 fVerbStop = nullptr;
1688 fNeedClose = false;
1689}
1690
1691SkPath::Iter::Iter(const SkPath& path, bool forceClose) {
1692 this->setPath(path, forceClose);
1693}
1694
1695void SkPath::Iter::setPath(const SkPath& path, bool forceClose) {
1696 fPts = path.fPathRef->points();
1697 fVerbs = path.fPathRef->verbsBegin();
1698 fVerbStop = path.fPathRef->verbsEnd();
1699 fConicWeights = path.fPathRef->conicWeights();
1700 if (fConicWeights) {
1701 fConicWeights -= 1; // begin one behind
1702 }
1703 fLastPt.fX = fLastPt.fY = 0;
1704 fMoveTo.fX = fMoveTo.fY = 0;
1705 fForceClose = SkToU8(forceClose);
1706 fNeedClose = false;
1707 fSegmentState = kEmptyContour_SegmentState;
1708}
1709
1710bool SkPath::Iter::isClosedContour() const {
1711 if (fVerbs == nullptr || fVerbs == fVerbStop) {
1712 return false;
1713 }
1714 if (fForceClose) {
1715 return true;
1716 }
1717
1718 const uint8_t* verbs = fVerbs;
1719 const uint8_t* stop = fVerbStop;
1720
1721 if (kMove_Verb == *verbs) {
1722 verbs += 1; // skip the initial moveto
1723 }
1724
1725 while (verbs < stop) {
1726 // verbs points one beyond the current verb, decrement first.
1727 unsigned v = *verbs++;
1728 if (kMove_Verb == v) {
1729 break;
1730 }
1731 if (kClose_Verb == v) {
1732 return true;
1733 }
1734 }
1735 return false;
1736}
1737
1738SkPath::Verb SkPath::Iter::autoClose(SkPoint pts[2]) {
1739 SkASSERT(pts);
1740 if (fLastPt != fMoveTo) {
1741 // A special case: if both points are NaN, SkPoint::operation== returns
1742 // false, but the iterator expects that they are treated as the same.
1743 // (consider SkPoint is a 2-dimension float point).
1744 if (SkScalarIsNaN(fLastPt.fX) || SkScalarIsNaN(fLastPt.fY) ||
1745 SkScalarIsNaN(fMoveTo.fX) || SkScalarIsNaN(fMoveTo.fY)) {
1746 return kClose_Verb;
1747 }
1748
1749 pts[0] = fLastPt;
1750 pts[1] = fMoveTo;
1751 fLastPt = fMoveTo;
1752 fCloseLine = true;
1753 return kLine_Verb;
1754 } else {
1755 pts[0] = fMoveTo;
1756 return kClose_Verb;
1757 }
1758}
1759
1760const SkPoint& SkPath::Iter::cons_moveTo() {
1761 if (fSegmentState == kAfterMove_SegmentState) {
1762 // Set the first return pt to the move pt
1763 fSegmentState = kAfterPrimitive_SegmentState;
1764 return fMoveTo;
1765 }
1766
1767 SkASSERT(fSegmentState == kAfterPrimitive_SegmentState);
1768 // Set the first return pt to the last pt of the previous primitive.
1769 return fPts[-1];
1770}
1771
1772SkPath::Verb SkPath::Iter::next(SkPoint ptsParam[4]) {
1773 SkASSERT(ptsParam);
1774
1775 if (fVerbs == fVerbStop) {
1776 // Close the curve if requested and if there is some curve to close
1777 if (fNeedClose && fSegmentState == kAfterPrimitive_SegmentState) {
1778 if (kLine_Verb == this->autoClose(ptsParam)) {
1779 return kLine_Verb;
1780 }
1781 fNeedClose = false;
1782 return kClose_Verb;
1783 }
1784 return kDone_Verb;
1785 }
1786
1787 unsigned verb = *fVerbs++;
1788 const SkPoint* SK_RESTRICT srcPts = fPts;
1789 SkPoint* SK_RESTRICT pts = ptsParam;
1790
1791 switch (verb) {
1792 case kMove_Verb:
1793 if (fNeedClose) {
1794 fVerbs--; // move back one verb
1795 verb = this->autoClose(pts);
1796 if (verb == kClose_Verb) {
1797 fNeedClose = false;
1798 }
1799 return (Verb)verb;
1800 }
1801 if (fVerbs == fVerbStop) { // might be a trailing moveto
1802 return kDone_Verb;
1803 }
1804 fMoveTo = *srcPts;
1805 pts[0] = *srcPts;
1806 srcPts += 1;
1807 fSegmentState = kAfterMove_SegmentState;
1808 fLastPt = fMoveTo;
1809 fNeedClose = fForceClose;
1810 break;
1811 case kLine_Verb:
1812 pts[0] = this->cons_moveTo();
1813 pts[1] = srcPts[0];
1814 fLastPt = srcPts[0];
1815 fCloseLine = false;
1816 srcPts += 1;
1817 break;
1818 case kConic_Verb:
1819 fConicWeights += 1;
1820 // fall-through
1821 case kQuad_Verb:
1822 pts[0] = this->cons_moveTo();
1823 memcpy(&pts[1], srcPts, 2 * sizeof(SkPoint));
1824 fLastPt = srcPts[1];
1825 srcPts += 2;
1826 break;
1827 case kCubic_Verb:
1828 pts[0] = this->cons_moveTo();
1829 memcpy(&pts[1], srcPts, 3 * sizeof(SkPoint));
1830 fLastPt = srcPts[2];
1831 srcPts += 3;
1832 break;
1833 case kClose_Verb:
1834 verb = this->autoClose(pts);
1835 if (verb == kLine_Verb) {
1836 fVerbs--; // move back one verb
1837 } else {
1838 fNeedClose = false;
1839 fSegmentState = kEmptyContour_SegmentState;
1840 }
1841 fLastPt = fMoveTo;
1842 break;
1843 }
1844 fPts = srcPts;
1845 return (Verb)verb;
1846}
1847
1848///////////////////////////////////////////////////////////////////////////////
1849
1850#include "include/core/SkStream.h"
1851#include "include/core/SkString.h"
1852#include "src/core/SkStringUtils.h"
1853
1854static void append_params(SkString* str, const char label[], const SkPoint pts[],
1855 int count, SkScalarAsStringType strType, SkScalar conicWeight = -12345) {
1856 str->append(label);
1857 str->append("(");
1858
1859 const SkScalar* values = &pts[0].fX;
1860 count *= 2;
1861
1862 for (int i = 0; i < count; ++i) {
1863 SkAppendScalar(str, values[i], strType);
1864 if (i < count - 1) {
1865 str->append(", ");
1866 }
1867 }
1868 if (conicWeight != -12345) {
1869 str->append(", ");
1870 SkAppendScalar(str, conicWeight, strType);
1871 }
1872 str->append(");");
1873 if (kHex_SkScalarAsStringType == strType) {
1874 str->append(" // ");
1875 for (int i = 0; i < count; ++i) {
1876 SkAppendScalarDec(str, values[i]);
1877 if (i < count - 1) {
1878 str->append(", ");
1879 }
1880 }
1881 if (conicWeight >= 0) {
1882 str->append(", ");
1883 SkAppendScalarDec(str, conicWeight);
1884 }
1885 }
1886 str->append("\n");
1887}
1888
1889void SkPath::dump(SkWStream* wStream, bool forceClose, bool dumpAsHex) const {
1890 SkScalarAsStringType asType = dumpAsHex ? kHex_SkScalarAsStringType : kDec_SkScalarAsStringType;
1891 Iter iter(*this, forceClose);
1892 SkPoint pts[4];
1893 Verb verb;
1894
1895 SkString builder;
1896 char const * const gFillTypeStrs[] = {
1897 "Winding",
1898 "EvenOdd",
1899 "InverseWinding",
1900 "InverseEvenOdd",
1901 };
1902 builder.printf("path.setFillType(SkPathFillType::k%s);\n",
1903 gFillTypeStrs[(int) this->getFillType()]);
1904 while ((verb = iter.next(pts)) != kDone_Verb) {
1905 switch (verb) {
1906 case kMove_Verb:
1907 append_params(&builder, "path.moveTo", &pts[0], 1, asType);
1908 break;
1909 case kLine_Verb:
1910 append_params(&builder, "path.lineTo", &pts[1], 1, asType);
1911 break;
1912 case kQuad_Verb:
1913 append_params(&builder, "path.quadTo", &pts[1], 2, asType);
1914 break;
1915 case kConic_Verb:
1916 append_params(&builder, "path.conicTo", &pts[1], 2, asType, iter.conicWeight());
1917 break;
1918 case kCubic_Verb:
1919 append_params(&builder, "path.cubicTo", &pts[1], 3, asType);
1920 break;
1921 case kClose_Verb:
1922 builder.append("path.close();\n");
1923 break;
1924 default:
1925 SkDebugf(" path: UNKNOWN VERB %d, aborting dump...\n", verb);
1926 verb = kDone_Verb; // stop the loop
1927 break;
1928 }
1929 if (!wStream && builder.size()) {
1930 SkDebugf("%s", builder.c_str());
1931 builder.reset();
1932 }
1933 }
1934 if (wStream) {
1935 wStream->writeText(builder.c_str());
1936 }
1937}
1938
1939void SkPath::dump() const {
1940 this->dump(nullptr, false, false);
1941}
1942
1943void SkPath::dumpHex() const {
1944 this->dump(nullptr, false, true);
1945}
1946
1947
1948bool SkPath::isValidImpl() const {
1949 if ((fFillType & ~3) != 0) {
1950 return false;
1951 }
1952
1953#ifdef SK_DEBUG_PATH
1954 if (!fBoundsIsDirty) {
1955 SkRect bounds;
1956
1957 bool isFinite = compute_pt_bounds(&bounds, *fPathRef.get());
1958 if (SkToBool(fIsFinite) != isFinite) {
1959 return false;
1960 }
1961
1962 if (fPathRef->countPoints() <= 1) {
1963 // if we're empty, fBounds may be empty but translated, so we can't
1964 // necessarily compare to bounds directly
1965 // try path.addOval(2, 2, 2, 2) which is empty, but the bounds will
1966 // be [2, 2, 2, 2]
1967 if (!bounds.isEmpty() || !fBounds.isEmpty()) {
1968 return false;
1969 }
1970 } else {
1971 if (bounds.isEmpty()) {
1972 if (!fBounds.isEmpty()) {
1973 return false;
1974 }
1975 } else {
1976 if (!fBounds.isEmpty()) {
1977 if (!fBounds.contains(bounds)) {
1978 return false;
1979 }
1980 }
1981 }
1982 }
1983 }
1984#endif // SK_DEBUG_PATH
1985 return true;
1986}
1987
1988///////////////////////////////////////////////////////////////////////////////
1989
1990static int sign(SkScalar x) { return x < 0; }
1991#define kValueNeverReturnedBySign 2
1992
1993enum DirChange {
1994 kUnknown_DirChange,
1995 kLeft_DirChange,
1996 kRight_DirChange,
1997 kStraight_DirChange,
1998 kBackwards_DirChange, // if double back, allow simple lines to be convex
1999 kInvalid_DirChange
2000};
2001
2002
2003static bool almost_equal(SkScalar compA, SkScalar compB) {
2004 // The error epsilon was empirically derived; worse case round rects
2005 // with a mid point outset by 2x float epsilon in tests had an error
2006 // of 12.
2007 const int epsilon = 16;
2008 if (!SkScalarIsFinite(compA) || !SkScalarIsFinite(compB)) {
2009 return false;
2010 }
2011 // no need to check for small numbers because SkPath::Iter has removed degenerate values
2012 int aBits = SkFloatAs2sCompliment(compA);
2013 int bBits = SkFloatAs2sCompliment(compB);
2014 return aBits < bBits + epsilon && bBits < aBits + epsilon;
2015}
2016
2017// only valid for a single contour
2018struct Convexicator {
2019
2020 /** The direction returned is only valid if the path is determined convex */
2021 SkPathPriv::FirstDirection getFirstDirection() const { return fFirstDirection; }
2022
2023 void setMovePt(const SkPoint& pt) {
2024 fPriorPt = fLastPt = fCurrPt = pt;
2025 }
2026
2027 bool addPt(const SkPoint& pt) {
2028 if (fCurrPt == pt) {
2029 return true;
2030 }
2031 fCurrPt = pt;
2032 if (fPriorPt == fLastPt) { // should only be true for first non-zero vector
2033 fLastVec = fCurrPt - fLastPt;
2034 fFirstPt = pt;
2035 } else if (!this->addVec(fCurrPt - fLastPt)) {
2036 return false;
2037 }
2038 fPriorPt = fLastPt;
2039 fLastPt = fCurrPt;
2040 return true;
2041 }
2042
2043 static SkPathConvexityType BySign(const SkPoint points[], int count) {
2044 const SkPoint* last = points + count;
2045 SkPoint currPt = *points++;
2046 SkPoint firstPt = currPt;
2047 int dxes = 0;
2048 int dyes = 0;
2049 int lastSx = kValueNeverReturnedBySign;
2050 int lastSy = kValueNeverReturnedBySign;
2051 for (int outerLoop = 0; outerLoop < 2; ++outerLoop ) {
2052 while (points != last) {
2053 SkVector vec = *points - currPt;
2054 if (!vec.isZero()) {
2055 // give up if vector construction failed
2056 if (!vec.isFinite()) {
2057 return SkPathConvexityType::kUnknown;
2058 }
2059 int sx = sign(vec.fX);
2060 int sy = sign(vec.fY);
2061 dxes += (sx != lastSx);
2062 dyes += (sy != lastSy);
2063 if (dxes > 3 || dyes > 3) {
2064 return SkPathConvexityType::kConcave;
2065 }
2066 lastSx = sx;
2067 lastSy = sy;
2068 }
2069 currPt = *points++;
2070 if (outerLoop) {
2071 break;
2072 }
2073 }
2074 points = &firstPt;
2075 }
2076 return SkPathConvexityType::kConvex; // that is, it may be convex, don't know yet
2077 }
2078
2079 bool close() {
2080 return this->addPt(fFirstPt);
2081 }
2082
2083 bool isFinite() const {
2084 return fIsFinite;
2085 }
2086
2087 int reversals() const {
2088 return fReversals;
2089 }
2090
2091private:
2092 DirChange directionChange(const SkVector& curVec) {
2093 SkScalar cross = SkPoint::CrossProduct(fLastVec, curVec);
2094 if (!SkScalarIsFinite(cross)) {
2095 return kUnknown_DirChange;
2096 }
2097 SkScalar smallest = std::min(fCurrPt.fX, std::min(fCurrPt.fY, std::min(fLastPt.fX, fLastPt.fY)));
2098 SkScalar largest = std::max(fCurrPt.fX, std::max(fCurrPt.fY, std::max(fLastPt.fX, fLastPt.fY)));
2099 largest = std::max(largest, -smallest);
2100
2101 if (almost_equal(largest, largest + cross)) {
2102 constexpr SkScalar nearlyZeroSqd = SK_ScalarNearlyZero * SK_ScalarNearlyZero;
2103 if (SkScalarNearlyZero(SkPointPriv::LengthSqd(fLastVec), nearlyZeroSqd) ||
2104 SkScalarNearlyZero(SkPointPriv::LengthSqd(curVec), nearlyZeroSqd)) {
2105 return kUnknown_DirChange;
2106 }
2107 return fLastVec.dot(curVec) < 0 ? kBackwards_DirChange : kStraight_DirChange;
2108 }
2109 return 1 == SkScalarSignAsInt(cross) ? kRight_DirChange : kLeft_DirChange;
2110 }
2111
2112 bool addVec(const SkVector& curVec) {
2113 DirChange dir = this->directionChange(curVec);
2114 switch (dir) {
2115 case kLeft_DirChange: // fall through
2116 case kRight_DirChange:
2117 if (kInvalid_DirChange == fExpectedDir) {
2118 fExpectedDir = dir;
2119 fFirstDirection = (kRight_DirChange == dir) ? SkPathPriv::kCW_FirstDirection
2120 : SkPathPriv::kCCW_FirstDirection;
2121 } else if (dir != fExpectedDir) {
2122 fFirstDirection = SkPathPriv::kUnknown_FirstDirection;
2123 return false;
2124 }
2125 fLastVec = curVec;
2126 break;
2127 case kStraight_DirChange:
2128 break;
2129 case kBackwards_DirChange:
2130 // allow path to reverse direction twice
2131 // Given path.moveTo(0, 0); path.lineTo(1, 1);
2132 // - 1st reversal: direction change formed by line (0,0 1,1), line (1,1 0,0)
2133 // - 2nd reversal: direction change formed by line (1,1 0,0), line (0,0 1,1)
2134 fLastVec = curVec;
2135 return ++fReversals < 3;
2136 case kUnknown_DirChange:
2137 return (fIsFinite = false);
2138 case kInvalid_DirChange:
2139 SK_ABORT("Use of invalid direction change flag");
2140 break;
2141 }
2142 return true;
2143 }
2144
2145 SkPoint fFirstPt {0, 0};
2146 SkPoint fPriorPt {0, 0};
2147 SkPoint fLastPt {0, 0};
2148 SkPoint fCurrPt {0, 0};
2149 SkVector fLastVec {0, 0};
2150 DirChange fExpectedDir { kInvalid_DirChange };
2151 SkPathPriv::FirstDirection fFirstDirection { SkPathPriv::kUnknown_FirstDirection };
2152 int fReversals { 0 };
2153 bool fIsFinite { true };
2154};
2155
2156SkPathConvexityType SkPath::internalGetConvexity() const {
2157 SkPoint pts[4];
2158 SkPath::Verb verb;
2159 SkPath::Iter iter(*this, true);
2160 auto setComputedConvexity = [=](SkPathConvexityType convexity){
2161 SkASSERT(SkPathConvexityType::kUnknown != convexity);
2162 this->setConvexityType(convexity);
2163 return convexity;
2164 };
2165
2166 // Check to see if path changes direction more than three times as quick concave test
2167 int pointCount = this->countPoints();
2168 // last moveTo index may exceed point count if data comes from fuzzer (via SkImageFilter)
2169 if (0 < fLastMoveToIndex && fLastMoveToIndex < pointCount) {
2170 pointCount = fLastMoveToIndex;
2171 }
2172 if (pointCount > 3) {
2173 const SkPoint* points = fPathRef->points();
2174 const SkPoint* last = &points[pointCount];
2175 // only consider the last of the initial move tos
2176 while (SkPath::kMove_Verb == iter.next(pts)) {
2177 ++points;
2178 }
2179 --points;
2180 SkPathConvexityType convexity = Convexicator::BySign(points, (int) (last - points));
2181 if (SkPathConvexityType::kConcave == convexity) {
2182 return setComputedConvexity(SkPathConvexityType::kConcave);
2183 } else if (SkPathConvexityType::kUnknown == convexity) {
2184 return SkPathConvexityType::kUnknown;
2185 }
2186 iter.setPath(*this, true);
2187 } else if (!this->isFinite()) {
2188 return SkPathConvexityType::kUnknown;
2189 }
2190
2191 int contourCount = 0;
2192 int count;
2193 Convexicator state;
2194 auto setFail = [=](){
2195 if (!state.isFinite()) {
2196 return SkPathConvexityType::kUnknown;
2197 }
2198 return setComputedConvexity(SkPathConvexityType::kConcave);
2199 };
2200
2201 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
2202 switch (verb) {
2203 case kMove_Verb:
2204 if (++contourCount > 1) {
2205 return setComputedConvexity(SkPathConvexityType::kConcave);
2206 }
2207 state.setMovePt(pts[0]);
2208 count = 0;
2209 break;
2210 case kLine_Verb:
2211 count = 1;
2212 break;
2213 case kQuad_Verb:
2214 // fall through
2215 case kConic_Verb:
2216 count = 2;
2217 break;
2218 case kCubic_Verb:
2219 count = 3;
2220 break;
2221 case kClose_Verb:
2222 if (!state.close()) {
2223 return setFail();
2224 }
2225 count = 0;
2226 break;
2227 default:
2228 SkDEBUGFAIL("bad verb");
2229 return setComputedConvexity(SkPathConvexityType::kConcave);
2230 }
2231 for (int i = 1; i <= count; i++) {
2232 if (!state.addPt(pts[i])) {
2233 return setFail();
2234 }
2235 }
2236 }
2237
2238 if (this->getFirstDirection() == SkPathPriv::kUnknown_FirstDirection) {
2239 if (state.getFirstDirection() == SkPathPriv::kUnknown_FirstDirection
2240 && !this->getBounds().isEmpty()) {
2241 return setComputedConvexity(state.reversals() < 3 ?
2242 SkPathConvexityType::kConvex : SkPathConvexityType::kConcave);
2243 }
2244 this->setFirstDirection(state.getFirstDirection());
2245 }
2246 return setComputedConvexity(SkPathConvexityType::kConvex);
2247}
2248
2249bool SkPathPriv::IsConvex(const SkPoint points[], int count) {
2250 SkPathConvexityType convexity = Convexicator::BySign(points, count);
2251 if (SkPathConvexityType::kConvex != convexity) {
2252 return false;
2253 }
2254 Convexicator state;
2255 state.setMovePt(points[0]);
2256 for (int i = 1; i < count; i++) {
2257 if (!state.addPt(points[i])) {
2258 return false;
2259 }
2260 }
2261 if (!state.addPt(points[0])) {
2262 return false;
2263 }
2264 if (!state.close()) {
2265 return false;
2266 }
2267 return state.getFirstDirection() != SkPathPriv::kUnknown_FirstDirection
2268 || state.reversals() < 3;
2269}
2270
2271///////////////////////////////////////////////////////////////////////////////
2272
2273class ContourIter {
2274public:
2275 ContourIter(const SkPathRef& pathRef);
2276
2277 bool done() const { return fDone; }
2278 // if !done() then these may be called
2279 int count() const { return fCurrPtCount; }
2280 const SkPoint* pts() const { return fCurrPt; }
2281 void next();
2282
2283private:
2284 int fCurrPtCount;
2285 const SkPoint* fCurrPt;
2286 const uint8_t* fCurrVerb;
2287 const uint8_t* fStopVerbs;
2288 const SkScalar* fCurrConicWeight;
2289 bool fDone;
2290 SkDEBUGCODE(int fContourCounter;)
2291};
2292
2293ContourIter::ContourIter(const SkPathRef& pathRef) {
2294 fStopVerbs = pathRef.verbsEnd();
2295 fDone = false;
2296 fCurrPt = pathRef.points();
2297 fCurrVerb = pathRef.verbsBegin();
2298 fCurrConicWeight = pathRef.conicWeights();
2299 fCurrPtCount = 0;
2300 SkDEBUGCODE(fContourCounter = 0;)
2301 this->next();
2302}
2303
2304void ContourIter::next() {
2305 if (fCurrVerb >= fStopVerbs) {
2306 fDone = true;
2307 }
2308 if (fDone) {
2309 return;
2310 }
2311
2312 // skip pts of prev contour
2313 fCurrPt += fCurrPtCount;
2314
2315 SkASSERT(SkPath::kMove_Verb == fCurrVerb[0]);
2316 int ptCount = 1; // moveTo
2317 const uint8_t* verbs = fCurrVerb;
2318
2319 for (verbs++; verbs < fStopVerbs; verbs++) {
2320 switch (*verbs) {
2321 case SkPath::kMove_Verb:
2322 goto CONTOUR_END;
2323 case SkPath::kLine_Verb:
2324 ptCount += 1;
2325 break;
2326 case SkPath::kConic_Verb:
2327 fCurrConicWeight += 1;
2328 // fall-through
2329 case SkPath::kQuad_Verb:
2330 ptCount += 2;
2331 break;
2332 case SkPath::kCubic_Verb:
2333 ptCount += 3;
2334 break;
2335 case SkPath::kClose_Verb:
2336 break;
2337 default:
2338 SkDEBUGFAIL("unexpected verb");
2339 break;
2340 }
2341 }
2342CONTOUR_END:
2343 fCurrPtCount = ptCount;
2344 fCurrVerb = verbs;
2345 SkDEBUGCODE(++fContourCounter;)
2346}
2347
2348// returns cross product of (p1 - p0) and (p2 - p0)
2349static SkScalar cross_prod(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) {
2350 SkScalar cross = SkPoint::CrossProduct(p1 - p0, p2 - p0);
2351 // We may get 0 when the above subtracts underflow. We expect this to be
2352 // very rare and lazily promote to double.
2353 if (0 == cross) {
2354 double p0x = SkScalarToDouble(p0.fX);
2355 double p0y = SkScalarToDouble(p0.fY);
2356
2357 double p1x = SkScalarToDouble(p1.fX);
2358 double p1y = SkScalarToDouble(p1.fY);
2359
2360 double p2x = SkScalarToDouble(p2.fX);
2361 double p2y = SkScalarToDouble(p2.fY);
2362
2363 cross = SkDoubleToScalar((p1x - p0x) * (p2y - p0y) -
2364 (p1y - p0y) * (p2x - p0x));
2365
2366 }
2367 return cross;
2368}
2369
2370// Returns the first pt with the maximum Y coordinate
2371static int find_max_y(const SkPoint pts[], int count) {
2372 SkASSERT(count > 0);
2373 SkScalar max = pts[0].fY;
2374 int firstIndex = 0;
2375 for (int i = 1; i < count; ++i) {
2376 SkScalar y = pts[i].fY;
2377 if (y > max) {
2378 max = y;
2379 firstIndex = i;
2380 }
2381 }
2382 return firstIndex;
2383}
2384
2385static int find_diff_pt(const SkPoint pts[], int index, int n, int inc) {
2386 int i = index;
2387 for (;;) {
2388 i = (i + inc) % n;
2389 if (i == index) { // we wrapped around, so abort
2390 break;
2391 }
2392 if (pts[index] != pts[i]) { // found a different point, success!
2393 break;
2394 }
2395 }
2396 return i;
2397}
2398
2399/**
2400 * Starting at index, and moving forward (incrementing), find the xmin and
2401 * xmax of the contiguous points that have the same Y.
2402 */
2403static int find_min_max_x_at_y(const SkPoint pts[], int index, int n,
2404 int* maxIndexPtr) {
2405 const SkScalar y = pts[index].fY;
2406 SkScalar min = pts[index].fX;
2407 SkScalar max = min;
2408 int minIndex = index;
2409 int maxIndex = index;
2410 for (int i = index + 1; i < n; ++i) {
2411 if (pts[i].fY != y) {
2412 break;
2413 }
2414 SkScalar x = pts[i].fX;
2415 if (x < min) {
2416 min = x;
2417 minIndex = i;
2418 } else if (x > max) {
2419 max = x;
2420 maxIndex = i;
2421 }
2422 }
2423 *maxIndexPtr = maxIndex;
2424 return minIndex;
2425}
2426
2427static void crossToDir(SkScalar cross, SkPathPriv::FirstDirection* dir) {
2428 *dir = cross > 0 ? SkPathPriv::kCW_FirstDirection : SkPathPriv::kCCW_FirstDirection;
2429}
2430
2431/*
2432 * We loop through all contours, and keep the computed cross-product of the
2433 * contour that contained the global y-max. If we just look at the first
2434 * contour, we may find one that is wound the opposite way (correctly) since
2435 * it is the interior of a hole (e.g. 'o'). Thus we must find the contour
2436 * that is outer most (or at least has the global y-max) before we can consider
2437 * its cross product.
2438 */
2439bool SkPathPriv::CheapComputeFirstDirection(const SkPath& path, FirstDirection* dir) {
2440 auto d = path.getFirstDirection();
2441 if (d != kUnknown_FirstDirection) {
2442 *dir = static_cast<FirstDirection>(d);
2443 return true;
2444 }
2445
2446 // We don't want to pay the cost for computing convexity if it is unknown,
2447 // so we call getConvexityOrUnknown() instead of isConvex().
2448 if (path.getConvexityTypeOrUnknown() == SkPathConvexityType::kConvex) {
2449 SkASSERT(path.getFirstDirection() == kUnknown_FirstDirection);
2450 *dir = static_cast<FirstDirection>(path.getFirstDirection());
2451 return false;
2452 }
2453
2454 ContourIter iter(*path.fPathRef.get());
2455
2456 // initialize with our logical y-min
2457 SkScalar ymax = path.getBounds().fTop;
2458 SkScalar ymaxCross = 0;
2459
2460 for (; !iter.done(); iter.next()) {
2461 int n = iter.count();
2462 if (n < 3) {
2463 continue;
2464 }
2465
2466 const SkPoint* pts = iter.pts();
2467 SkScalar cross = 0;
2468 int index = find_max_y(pts, n);
2469 if (pts[index].fY < ymax) {
2470 continue;
2471 }
2472
2473 // If there is more than 1 distinct point at the y-max, we take the
2474 // x-min and x-max of them and just subtract to compute the dir.
2475 if (pts[(index + 1) % n].fY == pts[index].fY) {
2476 int maxIndex;
2477 int minIndex = find_min_max_x_at_y(pts, index, n, &maxIndex);
2478 if (minIndex == maxIndex) {
2479 goto TRY_CROSSPROD;
2480 }
2481 SkASSERT(pts[minIndex].fY == pts[index].fY);
2482 SkASSERT(pts[maxIndex].fY == pts[index].fY);
2483 SkASSERT(pts[minIndex].fX <= pts[maxIndex].fX);
2484 // we just subtract the indices, and let that auto-convert to
2485 // SkScalar, since we just want - or + to signal the direction.
2486 cross = minIndex - maxIndex;
2487 } else {
2488 TRY_CROSSPROD:
2489 // Find a next and prev index to use for the cross-product test,
2490 // but we try to find pts that form non-zero vectors from pts[index]
2491 //
2492 // Its possible that we can't find two non-degenerate vectors, so
2493 // we have to guard our search (e.g. all the pts could be in the
2494 // same place).
2495
2496 // we pass n - 1 instead of -1 so we don't foul up % operator by
2497 // passing it a negative LH argument.
2498 int prev = find_diff_pt(pts, index, n, n - 1);
2499 if (prev == index) {
2500 // completely degenerate, skip to next contour
2501 continue;
2502 }
2503 int next = find_diff_pt(pts, index, n, 1);
2504 SkASSERT(next != index);
2505 cross = cross_prod(pts[prev], pts[index], pts[next]);
2506 // if we get a zero and the points are horizontal, then we look at the spread in
2507 // x-direction. We really should continue to walk away from the degeneracy until
2508 // there is a divergence.
2509 if (0 == cross && pts[prev].fY == pts[index].fY && pts[next].fY == pts[index].fY) {
2510 // construct the subtract so we get the correct Direction below
2511 cross = pts[index].fX - pts[next].fX;
2512 }
2513 }
2514
2515 if (cross) {
2516 // record our best guess so far
2517 ymax = pts[index].fY;
2518 ymaxCross = cross;
2519 }
2520 }
2521 if (ymaxCross) {
2522 crossToDir(ymaxCross, dir);
2523 path.setFirstDirection(*dir);
2524 return true;
2525 } else {
2526 return false;
2527 }
2528}
2529
2530///////////////////////////////////////////////////////////////////////////////
2531
2532static bool between(SkScalar a, SkScalar b, SkScalar c) {
2533 SkASSERT(((a <= b && b <= c) || (a >= b && b >= c)) == ((a - b) * (c - b) <= 0)
2534 || (SkScalarNearlyZero(a) && SkScalarNearlyZero(b) && SkScalarNearlyZero(c)));
2535 return (a - b) * (c - b) <= 0;
2536}
2537
2538static SkScalar eval_cubic_pts(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3,
2539 SkScalar t) {
2540 SkScalar A = c3 + 3*(c1 - c2) - c0;
2541 SkScalar B = 3*(c2 - c1 - c1 + c0);
2542 SkScalar C = 3*(c1 - c0);
2543 SkScalar D = c0;
2544 return poly_eval(A, B, C, D, t);
2545}
2546
2547template <size_t N> static void find_minmax(const SkPoint pts[],
2548 SkScalar* minPtr, SkScalar* maxPtr) {
2549 SkScalar min, max;
2550 min = max = pts[0].fX;
2551 for (size_t i = 1; i < N; ++i) {
2552 min = std::min(min, pts[i].fX);
2553 max = std::max(max, pts[i].fX);
2554 }
2555 *minPtr = min;
2556 *maxPtr = max;
2557}
2558
2559static bool checkOnCurve(SkScalar x, SkScalar y, const SkPoint& start, const SkPoint& end) {
2560 if (start.fY == end.fY) {
2561 return between(start.fX, x, end.fX) && x != end.fX;
2562 } else {
2563 return x == start.fX && y == start.fY;
2564 }
2565}
2566
2567static int winding_mono_cubic(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) {
2568 SkScalar y0 = pts[0].fY;
2569 SkScalar y3 = pts[3].fY;
2570
2571 int dir = 1;
2572 if (y0 > y3) {
2573 using std::swap;
2574 swap(y0, y3);
2575 dir = -1;
2576 }
2577 if (y < y0 || y > y3) {
2578 return 0;
2579 }
2580 if (checkOnCurve(x, y, pts[0], pts[3])) {
2581 *onCurveCount += 1;
2582 return 0;
2583 }
2584 if (y == y3) {
2585 return 0;
2586 }
2587
2588 // quickreject or quickaccept
2589 SkScalar min, max;
2590 find_minmax<4>(pts, &min, &max);
2591 if (x < min) {
2592 return 0;
2593 }
2594 if (x > max) {
2595 return dir;
2596 }
2597
2598 // compute the actual x(t) value
2599 SkScalar t;
2600 if (!SkCubicClipper::ChopMonoAtY(pts, y, &t)) {
2601 return 0;
2602 }
2603 SkScalar xt = eval_cubic_pts(pts[0].fX, pts[1].fX, pts[2].fX, pts[3].fX, t);
2604 if (SkScalarNearlyEqual(xt, x)) {
2605 if (x != pts[3].fX || y != pts[3].fY) { // don't test end points; they're start points
2606 *onCurveCount += 1;
2607 return 0;
2608 }
2609 }
2610 return xt < x ? dir : 0;
2611}
2612
2613static int winding_cubic(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) {
2614 SkPoint dst[10];
2615 int n = SkChopCubicAtYExtrema(pts, dst);
2616 int w = 0;
2617 for (int i = 0; i <= n; ++i) {
2618 w += winding_mono_cubic(&dst[i * 3], x, y, onCurveCount);
2619 }
2620 return w;
2621}
2622
2623static double conic_eval_numerator(const SkScalar src[], SkScalar w, SkScalar t) {
2624 SkASSERT(src);
2625 SkASSERT(t >= 0 && t <= 1);
2626 SkScalar src2w = src[2] * w;
2627 SkScalar C = src[0];
2628 SkScalar A = src[4] - 2 * src2w + C;
2629 SkScalar B = 2 * (src2w - C);
2630 return poly_eval(A, B, C, t);
2631}
2632
2633
2634static double conic_eval_denominator(SkScalar w, SkScalar t) {
2635 SkScalar B = 2 * (w - 1);
2636 SkScalar C = 1;
2637 SkScalar A = -B;
2638 return poly_eval(A, B, C, t);
2639}
2640
2641static int winding_mono_conic(const SkConic& conic, SkScalar x, SkScalar y, int* onCurveCount) {
2642 const SkPoint* pts = conic.fPts;
2643 SkScalar y0 = pts[0].fY;
2644 SkScalar y2 = pts[2].fY;
2645
2646 int dir = 1;
2647 if (y0 > y2) {
2648 using std::swap;
2649 swap(y0, y2);
2650 dir = -1;
2651 }
2652 if (y < y0 || y > y2) {
2653 return 0;
2654 }
2655 if (checkOnCurve(x, y, pts[0], pts[2])) {
2656 *onCurveCount += 1;
2657 return 0;
2658 }
2659 if (y == y2) {
2660 return 0;
2661 }
2662
2663 SkScalar roots[2];
2664 SkScalar A = pts[2].fY;
2665 SkScalar B = pts[1].fY * conic.fW - y * conic.fW + y;
2666 SkScalar C = pts[0].fY;
2667 A += C - 2 * B; // A = a + c - 2*(b*w - yCept*w + yCept)
2668 B -= C; // B = b*w - w * yCept + yCept - a
2669 C -= y;
2670 int n = SkFindUnitQuadRoots(A, 2 * B, C, roots);
2671 SkASSERT(n <= 1);
2672 SkScalar xt;
2673 if (0 == n) {
2674 // zero roots are returned only when y0 == y
2675 // Need [0] if dir == 1
2676 // and [2] if dir == -1
2677 xt = pts[1 - dir].fX;
2678 } else {
2679 SkScalar t = roots[0];
2680 xt = conic_eval_numerator(&pts[0].fX, conic.fW, t) / conic_eval_denominator(conic.fW, t);
2681 }
2682 if (SkScalarNearlyEqual(xt, x)) {
2683 if (x != pts[2].fX || y != pts[2].fY) { // don't test end points; they're start points
2684 *onCurveCount += 1;
2685 return 0;
2686 }
2687 }
2688 return xt < x ? dir : 0;
2689}
2690
2691static bool is_mono_quad(SkScalar y0, SkScalar y1, SkScalar y2) {
2692 // return SkScalarSignAsInt(y0 - y1) + SkScalarSignAsInt(y1 - y2) != 0;
2693 if (y0 == y1) {
2694 return true;
2695 }
2696 if (y0 < y1) {
2697 return y1 <= y2;
2698 } else {
2699 return y1 >= y2;
2700 }
2701}
2702
2703static int winding_conic(const SkPoint pts[], SkScalar x, SkScalar y, SkScalar weight,
2704 int* onCurveCount) {
2705 SkConic conic(pts, weight);
2706 SkConic chopped[2];
2707 // If the data points are very large, the conic may not be monotonic but may also
2708 // fail to chop. Then, the chopper does not split the original conic in two.
2709 bool isMono = is_mono_quad(pts[0].fY, pts[1].fY, pts[2].fY) || !conic.chopAtYExtrema(chopped);
2710 int w = winding_mono_conic(isMono ? conic : chopped[0], x, y, onCurveCount);
2711 if (!isMono) {
2712 w += winding_mono_conic(chopped[1], x, y, onCurveCount);
2713 }
2714 return w;
2715}
2716
2717static int winding_mono_quad(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) {
2718 SkScalar y0 = pts[0].fY;
2719 SkScalar y2 = pts[2].fY;
2720
2721 int dir = 1;
2722 if (y0 > y2) {
2723 using std::swap;
2724 swap(y0, y2);
2725 dir = -1;
2726 }
2727 if (y < y0 || y > y2) {
2728 return 0;
2729 }
2730 if (checkOnCurve(x, y, pts[0], pts[2])) {
2731 *onCurveCount += 1;
2732 return 0;
2733 }
2734 if (y == y2) {
2735 return 0;
2736 }
2737 // bounds check on X (not required. is it faster?)
2738#if 0
2739 if (pts[0].fX > x && pts[1].fX > x && pts[2].fX > x) {
2740 return 0;
2741 }
2742#endif
2743
2744 SkScalar roots[2];
2745 int n = SkFindUnitQuadRoots(pts[0].fY - 2 * pts[1].fY + pts[2].fY,
2746 2 * (pts[1].fY - pts[0].fY),
2747 pts[0].fY - y,
2748 roots);
2749 SkASSERT(n <= 1);
2750 SkScalar xt;
2751 if (0 == n) {
2752 // zero roots are returned only when y0 == y
2753 // Need [0] if dir == 1
2754 // and [2] if dir == -1
2755 xt = pts[1 - dir].fX;
2756 } else {
2757 SkScalar t = roots[0];
2758 SkScalar C = pts[0].fX;
2759 SkScalar A = pts[2].fX - 2 * pts[1].fX + C;
2760 SkScalar B = 2 * (pts[1].fX - C);
2761 xt = poly_eval(A, B, C, t);
2762 }
2763 if (SkScalarNearlyEqual(xt, x)) {
2764 if (x != pts[2].fX || y != pts[2].fY) { // don't test end points; they're start points
2765 *onCurveCount += 1;
2766 return 0;
2767 }
2768 }
2769 return xt < x ? dir : 0;
2770}
2771
2772static int winding_quad(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) {
2773 SkPoint dst[5];
2774 int n = 0;
2775
2776 if (!is_mono_quad(pts[0].fY, pts[1].fY, pts[2].fY)) {
2777 n = SkChopQuadAtYExtrema(pts, dst);
2778 pts = dst;
2779 }
2780 int w = winding_mono_quad(pts, x, y, onCurveCount);
2781 if (n > 0) {
2782 w += winding_mono_quad(&pts[2], x, y, onCurveCount);
2783 }
2784 return w;
2785}
2786
2787static int winding_line(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) {
2788 SkScalar x0 = pts[0].fX;
2789 SkScalar y0 = pts[0].fY;
2790 SkScalar x1 = pts[1].fX;
2791 SkScalar y1 = pts[1].fY;
2792
2793 SkScalar dy = y1 - y0;
2794
2795 int dir = 1;
2796 if (y0 > y1) {
2797 using std::swap;
2798 swap(y0, y1);
2799 dir = -1;
2800 }
2801 if (y < y0 || y > y1) {
2802 return 0;
2803 }
2804 if (checkOnCurve(x, y, pts[0], pts[1])) {
2805 *onCurveCount += 1;
2806 return 0;
2807 }
2808 if (y == y1) {
2809 return 0;
2810 }
2811 SkScalar cross = (x1 - x0) * (y - pts[0].fY) - dy * (x - x0);
2812
2813 if (!cross) {
2814 // zero cross means the point is on the line, and since the case where
2815 // y of the query point is at the end point is handled above, we can be
2816 // sure that we're on the line (excluding the end point) here
2817 if (x != x1 || y != pts[1].fY) {
2818 *onCurveCount += 1;
2819 }
2820 dir = 0;
2821 } else if (SkScalarSignAsInt(cross) == dir) {
2822 dir = 0;
2823 }
2824 return dir;
2825}
2826
2827static void tangent_cubic(const SkPoint pts[], SkScalar x, SkScalar y,
2828 SkTDArray<SkVector>* tangents) {
2829 if (!between(pts[0].fY, y, pts[1].fY) && !between(pts[1].fY, y, pts[2].fY)
2830 && !between(pts[2].fY, y, pts[3].fY)) {
2831 return;
2832 }
2833 if (!between(pts[0].fX, x, pts[1].fX) && !between(pts[1].fX, x, pts[2].fX)
2834 && !between(pts[2].fX, x, pts[3].fX)) {
2835 return;
2836 }
2837 SkPoint dst[10];
2838 int n = SkChopCubicAtYExtrema(pts, dst);
2839 for (int i = 0; i <= n; ++i) {
2840 SkPoint* c = &dst[i * 3];
2841 SkScalar t;
2842 if (!SkCubicClipper::ChopMonoAtY(c, y, &t)) {
2843 continue;
2844 }
2845 SkScalar xt = eval_cubic_pts(c[0].fX, c[1].fX, c[2].fX, c[3].fX, t);
2846 if (!SkScalarNearlyEqual(x, xt)) {
2847 continue;
2848 }
2849 SkVector tangent;
2850 SkEvalCubicAt(c, t, nullptr, &tangent, nullptr);
2851 tangents->push_back(tangent);
2852 }
2853}
2854
2855static void tangent_conic(const SkPoint pts[], SkScalar x, SkScalar y, SkScalar w,
2856 SkTDArray<SkVector>* tangents) {
2857 if (!between(pts[0].fY, y, pts[1].fY) && !between(pts[1].fY, y, pts[2].fY)) {
2858 return;
2859 }
2860 if (!between(pts[0].fX, x, pts[1].fX) && !between(pts[1].fX, x, pts[2].fX)) {
2861 return;
2862 }
2863 SkScalar roots[2];
2864 SkScalar A = pts[2].fY;
2865 SkScalar B = pts[1].fY * w - y * w + y;
2866 SkScalar C = pts[0].fY;
2867 A += C - 2 * B; // A = a + c - 2*(b*w - yCept*w + yCept)
2868 B -= C; // B = b*w - w * yCept + yCept - a
2869 C -= y;
2870 int n = SkFindUnitQuadRoots(A, 2 * B, C, roots);
2871 for (int index = 0; index < n; ++index) {
2872 SkScalar t = roots[index];
2873 SkScalar xt = conic_eval_numerator(&pts[0].fX, w, t) / conic_eval_denominator(w, t);
2874 if (!SkScalarNearlyEqual(x, xt)) {
2875 continue;
2876 }
2877 SkConic conic(pts, w);
2878 tangents->push_back(conic.evalTangentAt(t));
2879 }
2880}
2881
2882static void tangent_quad(const SkPoint pts[], SkScalar x, SkScalar y,
2883 SkTDArray<SkVector>* tangents) {
2884 if (!between(pts[0].fY, y, pts[1].fY) && !between(pts[1].fY, y, pts[2].fY)) {
2885 return;
2886 }
2887 if (!between(pts[0].fX, x, pts[1].fX) && !between(pts[1].fX, x, pts[2].fX)) {
2888 return;
2889 }
2890 SkScalar roots[2];
2891 int n = SkFindUnitQuadRoots(pts[0].fY - 2 * pts[1].fY + pts[2].fY,
2892 2 * (pts[1].fY - pts[0].fY),
2893 pts[0].fY - y,
2894 roots);
2895 for (int index = 0; index < n; ++index) {
2896 SkScalar t = roots[index];
2897 SkScalar C = pts[0].fX;
2898 SkScalar A = pts[2].fX - 2 * pts[1].fX + C;
2899 SkScalar B = 2 * (pts[1].fX - C);
2900 SkScalar xt = poly_eval(A, B, C, t);
2901 if (!SkScalarNearlyEqual(x, xt)) {
2902 continue;
2903 }
2904 tangents->push_back(SkEvalQuadTangentAt(pts, t));
2905 }
2906}
2907
2908static void tangent_line(const SkPoint pts[], SkScalar x, SkScalar y,
2909 SkTDArray<SkVector>* tangents) {
2910 SkScalar y0 = pts[0].fY;
2911 SkScalar y1 = pts[1].fY;
2912 if (!between(y0, y, y1)) {
2913 return;
2914 }
2915 SkScalar x0 = pts[0].fX;
2916 SkScalar x1 = pts[1].fX;
2917 if (!between(x0, x, x1)) {
2918 return;
2919 }
2920 SkScalar dx = x1 - x0;
2921 SkScalar dy = y1 - y0;
2922 if (!SkScalarNearlyEqual((x - x0) * dy, dx * (y - y0))) {
2923 return;
2924 }
2925 SkVector v;
2926 v.set(dx, dy);
2927 tangents->push_back(v);
2928}
2929
2930static bool contains_inclusive(const SkRect& r, SkScalar x, SkScalar y) {
2931 return r.fLeft <= x && x <= r.fRight && r.fTop <= y && y <= r.fBottom;
2932}
2933
2934bool SkPath::contains(SkScalar x, SkScalar y) const {
2935 bool isInverse = this->isInverseFillType();
2936 if (this->isEmpty()) {
2937 return isInverse;
2938 }
2939
2940 if (!contains_inclusive(this->getBounds(), x, y)) {
2941 return isInverse;
2942 }
2943
2944 SkPath::Iter iter(*this, true);
2945 bool done = false;
2946 int w = 0;
2947 int onCurveCount = 0;
2948 do {
2949 SkPoint pts[4];
2950 switch (iter.next(pts)) {
2951 case SkPath::kMove_Verb:
2952 case SkPath::kClose_Verb:
2953 break;
2954 case SkPath::kLine_Verb:
2955 w += winding_line(pts, x, y, &onCurveCount);
2956 break;
2957 case SkPath::kQuad_Verb:
2958 w += winding_quad(pts, x, y, &onCurveCount);
2959 break;
2960 case SkPath::kConic_Verb:
2961 w += winding_conic(pts, x, y, iter.conicWeight(), &onCurveCount);
2962 break;
2963 case SkPath::kCubic_Verb:
2964 w += winding_cubic(pts, x, y, &onCurveCount);
2965 break;
2966 case SkPath::kDone_Verb:
2967 done = true;
2968 break;
2969 }
2970 } while (!done);
2971 bool evenOddFill = SkPathFillType::kEvenOdd == this->getFillType()
2972 || SkPathFillType::kInverseEvenOdd == this->getFillType();
2973 if (evenOddFill) {
2974 w &= 1;
2975 }
2976 if (w) {
2977 return !isInverse;
2978 }
2979 if (onCurveCount <= 1) {
2980 return SkToBool(onCurveCount) ^ isInverse;
2981 }
2982 if ((onCurveCount & 1) || evenOddFill) {
2983 return SkToBool(onCurveCount & 1) ^ isInverse;
2984 }
2985 // If the point touches an even number of curves, and the fill is winding, check for
2986 // coincidence. Count coincidence as places where the on curve points have identical tangents.
2987 iter.setPath(*this, true);
2988 done = false;
2989 SkTDArray<SkVector> tangents;
2990 do {
2991 SkPoint pts[4];
2992 int oldCount = tangents.count();
2993 switch (iter.next(pts)) {
2994 case SkPath::kMove_Verb:
2995 case SkPath::kClose_Verb:
2996 break;
2997 case SkPath::kLine_Verb:
2998 tangent_line(pts, x, y, &tangents);
2999 break;
3000 case SkPath::kQuad_Verb:
3001 tangent_quad(pts, x, y, &tangents);
3002 break;
3003 case SkPath::kConic_Verb:
3004 tangent_conic(pts, x, y, iter.conicWeight(), &tangents);
3005 break;
3006 case SkPath::kCubic_Verb:
3007 tangent_cubic(pts, x, y, &tangents);
3008 break;
3009 case SkPath::kDone_Verb:
3010 done = true;
3011 break;
3012 }
3013 if (tangents.count() > oldCount) {
3014 int last = tangents.count() - 1;
3015 const SkVector& tangent = tangents[last];
3016 if (SkScalarNearlyZero(SkPointPriv::LengthSqd(tangent))) {
3017 tangents.remove(last);
3018 } else {
3019 for (int index = 0; index < last; ++index) {
3020 const SkVector& test = tangents[index];
3021 if (SkScalarNearlyZero(test.cross(tangent))
3022 && SkScalarSignAsInt(tangent.fX * test.fX) <= 0
3023 && SkScalarSignAsInt(tangent.fY * test.fY) <= 0) {
3024 tangents.remove(last);
3025 tangents.removeShuffle(index);
3026 break;
3027 }
3028 }
3029 }
3030 }
3031 } while (!done);
3032 return SkToBool(tangents.count()) ^ isInverse;
3033}
3034
3035int SkPath::ConvertConicToQuads(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2,
3036 SkScalar w, SkPoint pts[], int pow2) {
3037 const SkConic conic(p0, p1, p2, w);
3038 return conic.chopIntoQuadsPOW2(pts, pow2);
3039}
3040
3041bool SkPathPriv::IsSimpleClosedRect(const SkPath& path, SkRect* rect, SkPathDirection* direction,
3042 unsigned* start) {
3043 if (path.getSegmentMasks() != SkPath::kLine_SegmentMask) {
3044 return false;
3045 }
3046 SkPath::RawIter iter(path);
3047 SkPoint verbPts[4];
3048 SkPath::Verb v;
3049 SkPoint rectPts[5];
3050 int rectPtCnt = 0;
3051 while ((v = iter.next(verbPts)) != SkPath::kDone_Verb) {
3052 switch (v) {
3053 case SkPath::kMove_Verb:
3054 if (0 != rectPtCnt) {
3055 return false;
3056 }
3057 rectPts[0] = verbPts[0];
3058 ++rectPtCnt;
3059 break;
3060 case SkPath::kLine_Verb:
3061 if (5 == rectPtCnt) {
3062 return false;
3063 }
3064 rectPts[rectPtCnt] = verbPts[1];
3065 ++rectPtCnt;
3066 break;
3067 case SkPath::kClose_Verb:
3068 if (4 == rectPtCnt) {
3069 rectPts[4] = rectPts[0];
3070 rectPtCnt = 5;
3071 }
3072 break;
3073 default:
3074 return false;
3075 }
3076 }
3077 if (rectPtCnt < 5) {
3078 return false;
3079 }
3080 if (rectPts[0] != rectPts[4]) {
3081 return false;
3082 }
3083 // Check for two cases of rectangles: pts 0 and 3 form a vertical edge or a horizontal edge (
3084 // and pts 1 and 2 the opposite vertical or horizontal edge).
3085 bool vec03IsVertical;
3086 if (rectPts[0].fX == rectPts[3].fX && rectPts[1].fX == rectPts[2].fX &&
3087 rectPts[0].fY == rectPts[1].fY && rectPts[3].fY == rectPts[2].fY) {
3088 // Make sure it has non-zero width and height
3089 if (rectPts[0].fX == rectPts[1].fX || rectPts[0].fY == rectPts[3].fY) {
3090 return false;
3091 }
3092 vec03IsVertical = true;
3093 } else if (rectPts[0].fY == rectPts[3].fY && rectPts[1].fY == rectPts[2].fY &&
3094 rectPts[0].fX == rectPts[1].fX && rectPts[3].fX == rectPts[2].fX) {
3095 // Make sure it has non-zero width and height
3096 if (rectPts[0].fY == rectPts[1].fY || rectPts[0].fX == rectPts[3].fX) {
3097 return false;
3098 }
3099 vec03IsVertical = false;
3100 } else {
3101 return false;
3102 }
3103 // Set sortFlags so that it has the low bit set if pt index 0 is on right edge and second bit
3104 // set if it is on the bottom edge.
3105 unsigned sortFlags =
3106 ((rectPts[0].fX < rectPts[2].fX) ? 0b00 : 0b01) |
3107 ((rectPts[0].fY < rectPts[2].fY) ? 0b00 : 0b10);
3108 switch (sortFlags) {
3109 case 0b00:
3110 rect->setLTRB(rectPts[0].fX, rectPts[0].fY, rectPts[2].fX, rectPts[2].fY);
3111 *direction = vec03IsVertical ? SkPathDirection::kCW : SkPathDirection::kCCW;
3112 *start = 0;
3113 break;
3114 case 0b01:
3115 rect->setLTRB(rectPts[2].fX, rectPts[0].fY, rectPts[0].fX, rectPts[2].fY);
3116 *direction = vec03IsVertical ? SkPathDirection::kCCW : SkPathDirection::kCW;
3117 *start = 1;
3118 break;
3119 case 0b10:
3120 rect->setLTRB(rectPts[0].fX, rectPts[2].fY, rectPts[2].fX, rectPts[0].fY);
3121 *direction = vec03IsVertical ? SkPathDirection::kCCW : SkPathDirection::kCW;
3122 *start = 3;
3123 break;
3124 case 0b11:
3125 rect->setLTRB(rectPts[2].fX, rectPts[2].fY, rectPts[0].fX, rectPts[0].fY);
3126 *direction = vec03IsVertical ? SkPathDirection::kCW : SkPathDirection::kCCW;
3127 *start = 2;
3128 break;
3129 }
3130 return true;
3131}
3132
3133bool SkPathPriv::DrawArcIsConvex(SkScalar sweepAngle, bool useCenter, bool isFillNoPathEffect) {
3134 if (isFillNoPathEffect && SkScalarAbs(sweepAngle) >= 360.f) {
3135 // This gets converted to an oval.
3136 return true;
3137 }
3138 if (useCenter) {
3139 // This is a pie wedge. It's convex if the angle is <= 180.
3140 return SkScalarAbs(sweepAngle) <= 180.f;
3141 }
3142 // When the angle exceeds 360 this wraps back on top of itself. Otherwise it is a circle clipped
3143 // to a secant, i.e. convex.
3144 return SkScalarAbs(sweepAngle) <= 360.f;
3145}
3146
3147void SkPathPriv::CreateDrawArcPath(SkPath* path, const SkRect& oval, SkScalar startAngle,
3148 SkScalar sweepAngle, bool useCenter, bool isFillNoPathEffect) {
3149 SkASSERT(!oval.isEmpty());
3150 SkASSERT(sweepAngle);
3151
3152 path->reset();
3153 path->setIsVolatile(true);
3154 path->setFillType(SkPathFillType::kWinding);
3155 if (isFillNoPathEffect && SkScalarAbs(sweepAngle) >= 360.f) {
3156 path->addOval(oval);
3157 SkASSERT(path->isConvex() && DrawArcIsConvex(sweepAngle, false, isFillNoPathEffect));
3158 return;
3159 }
3160 if (useCenter) {
3161 path->moveTo(oval.centerX(), oval.centerY());
3162 }
3163 auto firstDir =
3164 sweepAngle > 0 ? SkPathPriv::kCW_FirstDirection : SkPathPriv::kCCW_FirstDirection;
3165 bool convex = DrawArcIsConvex(sweepAngle, useCenter, isFillNoPathEffect);
3166 // Arc to mods at 360 and drawArc is not supposed to.
3167 bool forceMoveTo = !useCenter;
3168 while (sweepAngle <= -360.f) {
3169 path->arcTo(oval, startAngle, -180.f, forceMoveTo);
3170 startAngle -= 180.f;
3171 path->arcTo(oval, startAngle, -180.f, false);
3172 startAngle -= 180.f;
3173 forceMoveTo = false;
3174 sweepAngle += 360.f;
3175 }
3176 while (sweepAngle >= 360.f) {
3177 path->arcTo(oval, startAngle, 180.f, forceMoveTo);
3178 startAngle += 180.f;
3179 path->arcTo(oval, startAngle, 180.f, false);
3180 startAngle += 180.f;
3181 forceMoveTo = false;
3182 sweepAngle -= 360.f;
3183 }
3184 path->arcTo(oval, startAngle, sweepAngle, forceMoveTo);
3185 if (useCenter) {
3186 path->close();
3187 }
3188 path->setConvexityType(convex ? SkPathConvexityType::kConvex : SkPathConvexityType::kConcave);
3189 path->setFirstDirection(firstDir);
3190}
3191
3192///////////////////////////////////////////////////////////////////////////////////////////////////
3193#include "include/private/SkNx.h"
3194
3195static int compute_quad_extremas(const SkPoint src[3], SkPoint extremas[3]) {
3196 SkScalar ts[2];
3197 int n = SkFindQuadExtrema(src[0].fX, src[1].fX, src[2].fX, ts);
3198 n += SkFindQuadExtrema(src[0].fY, src[1].fY, src[2].fY, &ts[n]);
3199 SkASSERT(n >= 0 && n <= 2);
3200 for (int i = 0; i < n; ++i) {
3201 extremas[i] = SkEvalQuadAt(src, ts[i]);
3202 }
3203 extremas[n] = src[2];
3204 return n + 1;
3205}
3206
3207static int compute_conic_extremas(const SkPoint src[3], SkScalar w, SkPoint extremas[3]) {
3208 SkConic conic(src[0], src[1], src[2], w);
3209 SkScalar ts[2];
3210 int n = conic.findXExtrema(ts);
3211 n += conic.findYExtrema(&ts[n]);
3212 SkASSERT(n >= 0 && n <= 2);
3213 for (int i = 0; i < n; ++i) {
3214 extremas[i] = conic.evalAt(ts[i]);
3215 }
3216 extremas[n] = src[2];
3217 return n + 1;
3218}
3219
3220static int compute_cubic_extremas(const SkPoint src[4], SkPoint extremas[5]) {
3221 SkScalar ts[4];
3222 int n = SkFindCubicExtrema(src[0].fX, src[1].fX, src[2].fX, src[3].fX, ts);
3223 n += SkFindCubicExtrema(src[0].fY, src[1].fY, src[2].fY, src[3].fY, &ts[n]);
3224 SkASSERT(n >= 0 && n <= 4);
3225 for (int i = 0; i < n; ++i) {
3226 SkEvalCubicAt(src, ts[i], &extremas[i], nullptr, nullptr);
3227 }
3228 extremas[n] = src[3];
3229 return n + 1;
3230}
3231
3232SkRect SkPath::computeTightBounds() const {
3233 if (0 == this->countVerbs()) {
3234 return SkRect::MakeEmpty();
3235 }
3236
3237 if (this->getSegmentMasks() == SkPath::kLine_SegmentMask) {
3238 return this->getBounds();
3239 }
3240
3241 SkPoint extremas[5]; // big enough to hold worst-case curve type (cubic) extremas + 1
3242 SkPoint pts[4];
3243 SkPath::RawIter iter(*this);
3244
3245 // initial with the first MoveTo, so we don't have to check inside the switch
3246 Sk2s min, max;
3247 min = max = from_point(this->getPoint(0));
3248 for (;;) {
3249 int count = 0;
3250 switch (iter.next(pts)) {
3251 case SkPath::kMove_Verb:
3252 extremas[0] = pts[0];
3253 count = 1;
3254 break;
3255 case SkPath::kLine_Verb:
3256 extremas[0] = pts[1];
3257 count = 1;
3258 break;
3259 case SkPath::kQuad_Verb:
3260 count = compute_quad_extremas(pts, extremas);
3261 break;
3262 case SkPath::kConic_Verb:
3263 count = compute_conic_extremas(pts, iter.conicWeight(), extremas);
3264 break;
3265 case SkPath::kCubic_Verb:
3266 count = compute_cubic_extremas(pts, extremas);
3267 break;
3268 case SkPath::kClose_Verb:
3269 break;
3270 case SkPath::kDone_Verb:
3271 goto DONE;
3272 }
3273 for (int i = 0; i < count; ++i) {
3274 Sk2s tmp = from_point(extremas[i]);
3275 min = Sk2s::Min(min, tmp);
3276 max = Sk2s::Max(max, tmp);
3277 }
3278 }
3279DONE:
3280 SkRect bounds;
3281 min.store((SkPoint*)&bounds.fLeft);
3282 max.store((SkPoint*)&bounds.fRight);
3283 return bounds;
3284}
3285
3286bool SkPath::IsLineDegenerate(const SkPoint& p1, const SkPoint& p2, bool exact) {
3287 return exact ? p1 == p2 : SkPointPriv::EqualsWithinTolerance(p1, p2);
3288}
3289
3290bool SkPath::IsQuadDegenerate(const SkPoint& p1, const SkPoint& p2,
3291 const SkPoint& p3, bool exact) {
3292 return exact ? p1 == p2 && p2 == p3 : SkPointPriv::EqualsWithinTolerance(p1, p2) &&
3293 SkPointPriv::EqualsWithinTolerance(p2, p3);
3294}
3295
3296bool SkPath::IsCubicDegenerate(const SkPoint& p1, const SkPoint& p2,
3297 const SkPoint& p3, const SkPoint& p4, bool exact) {
3298 return exact ? p1 == p2 && p2 == p3 && p3 == p4 :
3299 SkPointPriv::EqualsWithinTolerance(p1, p2) &&
3300 SkPointPriv::EqualsWithinTolerance(p2, p3) &&
3301 SkPointPriv::EqualsWithinTolerance(p3, p4);
3302}
3303
3304//////////////////////////////////////////////////////////////////////////////////////////////////
3305
3306bool SkPathPriv::IsRectContour(const SkPath& path, bool allowPartial, int* currVerb,
3307 const SkPoint** ptsPtr, bool* isClosed, SkPathDirection* direction,
3308 SkRect* rect) {
3309 int corners = 0;
3310 SkPoint closeXY; // used to determine if final line falls on a diagonal
3311 SkPoint lineStart; // used to construct line from previous point
3312 const SkPoint* firstPt = nullptr; // first point in the rect (last of first moves)
3313 const SkPoint* lastPt = nullptr; // last point in the rect (last of lines or first if closed)
3314 SkPoint firstCorner;
3315 SkPoint thirdCorner;
3316 const SkPoint* pts = *ptsPtr;
3317 const SkPoint* savePts = nullptr; // used to allow caller to iterate through a pair of rects
3318 lineStart.set(0, 0);
3319 signed char directions[] = {-1, -1, -1, -1, -1}; // -1 to 3; -1 is uninitialized
3320 bool closedOrMoved = false;
3321 bool autoClose = false;
3322 bool insertClose = false;
3323 int verbCnt = path.fPathRef->countVerbs();
3324 while (*currVerb < verbCnt && (!allowPartial || !autoClose)) {
3325 uint8_t verb = insertClose ? (uint8_t) SkPath::kClose_Verb : path.fPathRef->atVerb(*currVerb);
3326 switch (verb) {
3327 case SkPath::kClose_Verb:
3328 savePts = pts;
3329 autoClose = true;
3330 insertClose = false;
3331 case SkPath::kLine_Verb: {
3332 if (SkPath::kClose_Verb != verb) {
3333 lastPt = pts;
3334 }
3335 SkPoint lineEnd = SkPath::kClose_Verb == verb ? *firstPt : *pts++;
3336 SkVector lineDelta = lineEnd - lineStart;
3337 if (lineDelta.fX && lineDelta.fY) {
3338 return false; // diagonal
3339 }
3340 if (!lineDelta.isFinite()) {
3341 return false; // path contains infinity or NaN
3342 }
3343 if (lineStart == lineEnd) {
3344 break; // single point on side OK
3345 }
3346 int nextDirection = rect_make_dir(lineDelta.fX, lineDelta.fY); // 0 to 3
3347 if (0 == corners) {
3348 directions[0] = nextDirection;
3349 corners = 1;
3350 closedOrMoved = false;
3351 lineStart = lineEnd;
3352 break;
3353 }
3354 if (closedOrMoved) {
3355 return false; // closed followed by a line
3356 }
3357 if (autoClose && nextDirection == directions[0]) {
3358 break; // colinear with first
3359 }
3360 closedOrMoved = autoClose;
3361 if (directions[corners - 1] == nextDirection) {
3362 if (3 == corners && SkPath::kLine_Verb == verb) {
3363 thirdCorner = lineEnd;
3364 }
3365 lineStart = lineEnd;
3366 break; // colinear segment
3367 }
3368 directions[corners++] = nextDirection;
3369 // opposite lines must point in opposite directions; xoring them should equal 2
3370 switch (corners) {
3371 case 2:
3372 firstCorner = lineStart;
3373 break;
3374 case 3:
3375 if ((directions[0] ^ directions[2]) != 2) {
3376 return false;
3377 }
3378 thirdCorner = lineEnd;
3379 break;
3380 case 4:
3381 if ((directions[1] ^ directions[3]) != 2) {
3382 return false;
3383 }
3384 break;
3385 default:
3386 return false; // too many direction changes
3387 }
3388 lineStart = lineEnd;
3389 break;
3390 }
3391 case SkPath::kQuad_Verb:
3392 case SkPath::kConic_Verb:
3393 case SkPath::kCubic_Verb:
3394 return false; // quadratic, cubic not allowed
3395 case SkPath::kMove_Verb:
3396 if (allowPartial && !autoClose && directions[0] >= 0) {
3397 insertClose = true;
3398 *currVerb -= 1; // try move again afterwards
3399 goto addMissingClose;
3400 }
3401 if (!corners) {
3402 firstPt = pts;
3403 } else {
3404 closeXY = *firstPt - *lastPt;
3405 if (closeXY.fX && closeXY.fY) {
3406 return false; // we're diagonal, abort
3407 }
3408 }
3409 lineStart = *pts++;
3410 closedOrMoved = true;
3411 break;
3412 default:
3413 SkDEBUGFAIL("unexpected verb");
3414 break;
3415 }
3416 *currVerb += 1;
3417 addMissingClose:
3418 ;
3419 }
3420 // Success if 4 corners and first point equals last
3421 if (corners < 3 || corners > 4) {
3422 return false;
3423 }
3424 if (savePts) {
3425 *ptsPtr = savePts;
3426 }
3427 // check if close generates diagonal
3428 closeXY = *firstPt - *lastPt;
3429 if (closeXY.fX && closeXY.fY) {
3430 return false;
3431 }
3432 if (rect) {
3433 rect->set(firstCorner, thirdCorner);
3434 }
3435 if (isClosed) {
3436 *isClosed = autoClose;
3437 }
3438 if (direction) {
3439 *direction = directions[0] == ((directions[1] + 1) & 3) ?
3440 SkPathDirection::kCW : SkPathDirection::kCCW;
3441 }
3442 return true;
3443}
3444
3445
3446bool SkPathPriv::IsNestedFillRects(const SkPath& path, SkRect rects[2], SkPathDirection dirs[2]) {
3447 SkDEBUGCODE(path.validate();)
3448 int currVerb = 0;
3449 const SkPoint* pts = path.fPathRef->points();
3450 SkPathDirection testDirs[2];
3451 SkRect testRects[2];
3452 if (!IsRectContour(path, true, &currVerb, &pts, nullptr, &testDirs[0], &testRects[0])) {
3453 return false;
3454 }
3455 if (IsRectContour(path, false, &currVerb, &pts, nullptr, &testDirs[1], &testRects[1])) {
3456 if (testRects[0].contains(testRects[1])) {
3457 if (rects) {
3458 rects[0] = testRects[0];
3459 rects[1] = testRects[1];
3460 }
3461 if (dirs) {
3462 dirs[0] = testDirs[0];
3463 dirs[1] = testDirs[1];
3464 }
3465 return true;
3466 }
3467 if (testRects[1].contains(testRects[0])) {
3468 if (rects) {
3469 rects[0] = testRects[1];
3470 rects[1] = testRects[0];
3471 }
3472 if (dirs) {
3473 dirs[0] = testDirs[1];
3474 dirs[1] = testDirs[0];
3475 }
3476 return true;
3477 }
3478 }
3479 return false;
3480}
3481
3482///////////////////////////////////////////////////////////////////////////////////////////////////
3483
3484#include "src/core/SkEdgeClipper.h"
3485
3486struct SkHalfPlane {
3487 SkScalar fA, fB, fC;
3488
3489 SkScalar eval(SkScalar x, SkScalar y) const {
3490 return fA * x + fB * y + fC;
3491 }
3492 SkScalar operator()(SkScalar x, SkScalar y) const { return this->eval(x, y); }
3493
3494 bool normalize() {
3495 double a = fA;
3496 double b = fB;
3497 double c = fC;
3498 double dmag = sqrt(a * a + b * b);
3499 // length of initial plane normal is zero
3500 if (dmag == 0) {
3501 fA = fB = 0;
3502 fC = SK_Scalar1;
3503 return true;
3504 }
3505 double dscale = sk_ieee_double_divide(1.0, dmag);
3506 a *= dscale;
3507 b *= dscale;
3508 c *= dscale;
3509 // check if we're not finite, or normal is zero-length
3510 if (!sk_float_isfinite(a) || !sk_float_isfinite(b) || !sk_float_isfinite(c) ||
3511 (a == 0 && b == 0)) {
3512 fA = fB = 0;
3513 fC = SK_Scalar1;
3514 return false;
3515 }
3516 fA = a;
3517 fB = b;
3518 fC = c;
3519 return true;
3520 }
3521
3522 enum Result {
3523 kAllNegative,
3524 kAllPositive,
3525 kMixed
3526 };
3527 Result test(const SkRect& bounds) const {
3528 // check whether the diagonal aligned with the normal crosses the plane
3529 SkPoint diagMin, diagMax;
3530 if (fA >= 0) {
3531 diagMin.fX = bounds.fLeft;
3532 diagMax.fX = bounds.fRight;
3533 } else {
3534 diagMin.fX = bounds.fRight;
3535 diagMax.fX = bounds.fLeft;
3536 }
3537 if (fB >= 0) {
3538 diagMin.fY = bounds.fTop;
3539 diagMax.fY = bounds.fBottom;
3540 } else {
3541 diagMin.fY = bounds.fBottom;
3542 diagMax.fY = bounds.fTop;
3543 }
3544 SkScalar test = this->eval(diagMin.fX, diagMin.fY);
3545 SkScalar sign = test*this->eval(diagMax.fX, diagMax.fY);
3546 if (sign > 0) {
3547 // the path is either all on one side of the half-plane or the other
3548 if (test < 0) {
3549 return kAllNegative;
3550 } else {
3551 return kAllPositive;
3552 }
3553 }
3554 return kMixed;
3555 }
3556};
3557
3558// assumes plane is pre-normalized
3559// If we fail in our calculations, we return the empty path
3560static void clip(const SkPath& path, const SkHalfPlane& plane, SkPath* clippedPath) {
3561 SkMatrix mx, inv;
3562 SkPoint p0 = { -plane.fA*plane.fC, -plane.fB*plane.fC };
3563 mx.setAll( plane.fB, plane.fA, p0.fX,
3564 -plane.fA, plane.fB, p0.fY,
3565 0, 0, 1);
3566 if (!mx.invert(&inv)) {
3567 clippedPath->reset();
3568 return;
3569 }
3570
3571 SkPath rotated;
3572 path.transform(inv, &rotated);
3573 if (!rotated.isFinite()) {
3574 clippedPath->reset();
3575 return;
3576 }
3577
3578 SkScalar big = SK_ScalarMax;
3579 SkRect clip = {-big, 0, big, big };
3580
3581 struct Rec {
3582 SkPath* fResult;
3583 SkPoint fPrev;
3584 } rec = { clippedPath, {0, 0} };
3585
3586 SkEdgeClipper::ClipPath(rotated, clip, false,
3587 [](SkEdgeClipper* clipper, bool newCtr, void* ctx) {
3588 Rec* rec = (Rec*)ctx;
3589
3590 bool addLineTo = false;
3591 SkPoint pts[4];
3592 SkPath::Verb verb;
3593 while ((verb = clipper->next(pts)) != SkPath::kDone_Verb) {
3594 if (newCtr) {
3595 rec->fResult->moveTo(pts[0]);
3596 rec->fPrev = pts[0];
3597 newCtr = false;
3598 }
3599
3600 if (addLineTo || pts[0] != rec->fPrev) {
3601 rec->fResult->lineTo(pts[0]);
3602 }
3603
3604 switch (verb) {
3605 case SkPath::kLine_Verb:
3606 rec->fResult->lineTo(pts[1]);
3607 rec->fPrev = pts[1];
3608 break;
3609 case SkPath::kQuad_Verb:
3610 rec->fResult->quadTo(pts[1], pts[2]);
3611 rec->fPrev = pts[2];
3612 break;
3613 case SkPath::kCubic_Verb:
3614 rec->fResult->cubicTo(pts[1], pts[2], pts[3]);
3615 rec->fPrev = pts[3];
3616 break;
3617 default: break;
3618 }
3619 addLineTo = true;
3620 }
3621 }, &rec);
3622
3623 clippedPath->setFillType(path.getFillType());
3624 clippedPath->transform(mx);
3625 if (!path.isFinite()) {
3626 clippedPath->reset();
3627 }
3628}
3629
3630// true means we have written to clippedPath
3631bool SkPathPriv::PerspectiveClip(const SkPath& path, const SkMatrix& matrix, SkPath* clippedPath) {
3632 if (!matrix.hasPerspective()) {
3633 return false;
3634 }
3635
3636 SkHalfPlane plane {
3637 matrix[SkMatrix::kMPersp0],
3638 matrix[SkMatrix::kMPersp1],
3639 matrix[SkMatrix::kMPersp2] - kW0PlaneDistance
3640 };
3641 if (plane.normalize()) {
3642 switch (plane.test(path.getBounds())) {
3643 case SkHalfPlane::kAllPositive:
3644 return false;
3645 case SkHalfPlane::kMixed: {
3646 clip(path, plane, clippedPath);
3647 return true;
3648 } break;
3649 default: break; // handled outside of the switch
3650 }
3651 }
3652 // clipped out (or failed)
3653 clippedPath->reset();
3654 return true;
3655}
3656
3657int SkPathPriv::GenIDChangeListenersCount(const SkPath& path) {
3658 return path.fPathRef->genIDChangeListenerCount();
3659}
3660