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

Provided by KDAB

Privacy Policy
Learn more about Flutter for embedded and desktop on industrialflutter.com

source code of flutter_engine/third_party/skia/src/core/SkPath.cpp