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