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