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