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