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 "SkBuffer.h"
9 #include "SkErrorInternals.h"
10 #include "SkGeometry.h"
11 #include "SkMath.h"
12 #include "SkPath.h"
13 #include "SkPathRef.h"
14 #include "SkRRect.h"
15 #include "SkThread.h"
16
17 ////////////////////////////////////////////////////////////////////////////
18
19 /**
20 * Path.bounds is defined to be the bounds of all the control points.
21 * If we called bounds.join(r) we would skip r if r was empty, which breaks
22 * our promise. Hence we have a custom joiner that doesn't look at emptiness
23 */
joinNoEmptyChecks(SkRect * dst,const SkRect & src)24 static void joinNoEmptyChecks(SkRect* dst, const SkRect& src) {
25 dst->fLeft = SkMinScalar(dst->fLeft, src.fLeft);
26 dst->fTop = SkMinScalar(dst->fTop, src.fTop);
27 dst->fRight = SkMaxScalar(dst->fRight, src.fRight);
28 dst->fBottom = SkMaxScalar(dst->fBottom, src.fBottom);
29 }
30
is_degenerate(const SkPath & path)31 static bool is_degenerate(const SkPath& path) {
32 SkPath::Iter iter(path, false);
33 SkPoint pts[4];
34 return SkPath::kDone_Verb == iter.next(pts);
35 }
36
37 class SkAutoDisableDirectionCheck {
38 public:
SkAutoDisableDirectionCheck(SkPath * path)39 SkAutoDisableDirectionCheck(SkPath* path) : fPath(path) {
40 fSaved = static_cast<SkPath::Direction>(fPath->fDirection);
41 }
42
~SkAutoDisableDirectionCheck()43 ~SkAutoDisableDirectionCheck() {
44 fPath->fDirection = fSaved;
45 }
46
47 private:
48 SkPath* fPath;
49 SkPath::Direction fSaved;
50 };
51 #define SkAutoDisableDirectionCheck(...) SK_REQUIRE_LOCAL_VAR(SkAutoDisableDirectionCheck)
52
53 /* This guy's constructor/destructor bracket a path editing operation. It is
54 used when we know the bounds of the amount we are going to add to the path
55 (usually a new contour, but not required).
56
57 It captures some state about the path up front (i.e. if it already has a
58 cached bounds), and then if it can, it updates the cache bounds explicitly,
59 avoiding the need to revisit all of the points in getBounds().
60
61 It also notes if the path was originally degenerate, and if so, sets
62 isConvex to true. Thus it can only be used if the contour being added is
63 convex.
64 */
65 class SkAutoPathBoundsUpdate {
66 public:
SkAutoPathBoundsUpdate(SkPath * path,const SkRect & r)67 SkAutoPathBoundsUpdate(SkPath* path, const SkRect& r) : fRect(r) {
68 this->init(path);
69 }
70
SkAutoPathBoundsUpdate(SkPath * path,SkScalar left,SkScalar top,SkScalar right,SkScalar bottom)71 SkAutoPathBoundsUpdate(SkPath* path, SkScalar left, SkScalar top,
72 SkScalar right, SkScalar bottom) {
73 fRect.set(left, top, right, bottom);
74 this->init(path);
75 }
76
~SkAutoPathBoundsUpdate()77 ~SkAutoPathBoundsUpdate() {
78 fPath->setConvexity(fDegenerate ? SkPath::kConvex_Convexity
79 : SkPath::kUnknown_Convexity);
80 if (fEmpty || fHasValidBounds) {
81 fPath->setBounds(fRect);
82 }
83 }
84
85 private:
86 SkPath* fPath;
87 SkRect fRect;
88 bool fHasValidBounds;
89 bool fDegenerate;
90 bool fEmpty;
91
init(SkPath * path)92 void init(SkPath* path) {
93 // Cannot use fRect for our bounds unless we know it is sorted
94 fRect.sort();
95 fPath = path;
96 // Mark the path's bounds as dirty if (1) they are, or (2) the path
97 // is non-finite, and therefore its bounds are not meaningful
98 fHasValidBounds = path->hasComputedBounds() && path->isFinite();
99 fEmpty = path->isEmpty();
100 if (fHasValidBounds && !fEmpty) {
101 joinNoEmptyChecks(&fRect, fPath->getBounds());
102 }
103 fDegenerate = is_degenerate(*path);
104 }
105 };
106 #define SkAutoPathBoundsUpdate(...) SK_REQUIRE_LOCAL_VAR(SkAutoPathBoundsUpdate)
107
108 ////////////////////////////////////////////////////////////////////////////
109
110 /*
111 Stores the verbs and points as they are given to us, with exceptions:
112 - we only record "Close" if it was immediately preceeded by Move | Line | Quad | Cubic
113 - we insert a Move(0,0) if Line | Quad | Cubic is our first command
114
115 The iterator does more cleanup, especially if forceClose == true
116 1. If we encounter degenerate segments, remove them
117 2. if we encounter Close, return a cons'd up Line() first (if the curr-pt != start-pt)
118 3. if we encounter Move without a preceeding Close, and forceClose is true, goto #2
119 4. if we encounter Line | Quad | Cubic after Close, cons up a Move
120 */
121
122 ////////////////////////////////////////////////////////////////////////////
123
124 // flag to require a moveTo if we begin with something else, like lineTo etc.
125 #define INITIAL_LASTMOVETOINDEX_VALUE ~0
126
SkPath()127 SkPath::SkPath()
128 : fPathRef(SkPathRef::CreateEmpty()) {
129 this->resetFields();
130 fIsVolatile = false;
131 }
132
resetFields()133 void SkPath::resetFields() {
134 //fPathRef is assumed to have been emptied by the caller.
135 fLastMoveToIndex = INITIAL_LASTMOVETOINDEX_VALUE;
136 fFillType = kWinding_FillType;
137 fConvexity = kUnknown_Convexity;
138 fDirection = kUnknown_Direction;
139
140 // We don't touch Android's fSourcePath. It's used to track texture garbage collection, so we
141 // don't want to muck with it if it's been set to something non-NULL.
142 }
143
SkPath(const SkPath & that)144 SkPath::SkPath(const SkPath& that)
145 : fPathRef(SkRef(that.fPathRef.get())) {
146 this->copyFields(that);
147 SkDEBUGCODE(that.validate();)
148 }
149
~SkPath()150 SkPath::~SkPath() {
151 SkDEBUGCODE(this->validate();)
152 }
153
operator =(const SkPath & that)154 SkPath& SkPath::operator=(const SkPath& that) {
155 SkDEBUGCODE(that.validate();)
156
157 if (this != &that) {
158 fPathRef.reset(SkRef(that.fPathRef.get()));
159 this->copyFields(that);
160 }
161 SkDEBUGCODE(this->validate();)
162 return *this;
163 }
164
copyFields(const SkPath & that)165 void SkPath::copyFields(const SkPath& that) {
166 //fPathRef is assumed to have been set by the caller.
167 fLastMoveToIndex = that.fLastMoveToIndex;
168 fFillType = that.fFillType;
169 fConvexity = that.fConvexity;
170 fDirection = that.fDirection;
171 fIsVolatile = that.fIsVolatile;
172 }
173
operator ==(const SkPath & a,const SkPath & b)174 bool operator==(const SkPath& a, const SkPath& b) {
175 // note: don't need to look at isConvex or bounds, since just comparing the
176 // raw data is sufficient.
177 return &a == &b ||
178 (a.fFillType == b.fFillType && *a.fPathRef.get() == *b.fPathRef.get());
179 }
180
swap(SkPath & that)181 void SkPath::swap(SkPath& that) {
182 if (this != &that) {
183 fPathRef.swap(&that.fPathRef);
184 SkTSwap<int>(fLastMoveToIndex, that.fLastMoveToIndex);
185 SkTSwap<uint8_t>(fFillType, that.fFillType);
186 SkTSwap<uint8_t>(fConvexity, that.fConvexity);
187 SkTSwap<uint8_t>(fDirection, that.fDirection);
188 SkTSwap<SkBool8>(fIsVolatile, that.fIsVolatile);
189 }
190 }
191
check_edge_against_rect(const SkPoint & p0,const SkPoint & p1,const SkRect & rect,SkPath::Direction dir)192 static inline bool check_edge_against_rect(const SkPoint& p0,
193 const SkPoint& p1,
194 const SkRect& rect,
195 SkPath::Direction dir) {
196 const SkPoint* edgeBegin;
197 SkVector v;
198 if (SkPath::kCW_Direction == dir) {
199 v = p1 - p0;
200 edgeBegin = &p0;
201 } else {
202 v = p0 - p1;
203 edgeBegin = &p1;
204 }
205 if (v.fX || v.fY) {
206 // check the cross product of v with the vec from edgeBegin to each rect corner
207 SkScalar yL = SkScalarMul(v.fY, rect.fLeft - edgeBegin->fX);
208 SkScalar xT = SkScalarMul(v.fX, rect.fTop - edgeBegin->fY);
209 SkScalar yR = SkScalarMul(v.fY, rect.fRight - edgeBegin->fX);
210 SkScalar xB = SkScalarMul(v.fX, rect.fBottom - edgeBegin->fY);
211 if ((xT < yL) || (xT < yR) || (xB < yL) || (xB < yR)) {
212 return false;
213 }
214 }
215 return true;
216 }
217
conservativelyContainsRect(const SkRect & rect) const218 bool SkPath::conservativelyContainsRect(const SkRect& rect) const {
219 // This only handles non-degenerate convex paths currently.
220 if (kConvex_Convexity != this->getConvexity()) {
221 return false;
222 }
223
224 Direction direction;
225 if (!this->cheapComputeDirection(&direction)) {
226 return false;
227 }
228
229 SkPoint firstPt;
230 SkPoint prevPt;
231 RawIter iter(*this);
232 SkPath::Verb verb;
233 SkPoint pts[4];
234 SkDEBUGCODE(int moveCnt = 0;)
235 SkDEBUGCODE(int segmentCount = 0;)
236 SkDEBUGCODE(int closeCount = 0;)
237
238 while ((verb = iter.next(pts)) != kDone_Verb) {
239 int nextPt = -1;
240 switch (verb) {
241 case kMove_Verb:
242 SkASSERT(!segmentCount && !closeCount);
243 SkDEBUGCODE(++moveCnt);
244 firstPt = prevPt = pts[0];
245 break;
246 case kLine_Verb:
247 nextPt = 1;
248 SkASSERT(moveCnt && !closeCount);
249 SkDEBUGCODE(++segmentCount);
250 break;
251 case kQuad_Verb:
252 case kConic_Verb:
253 SkASSERT(moveCnt && !closeCount);
254 SkDEBUGCODE(++segmentCount);
255 nextPt = 2;
256 break;
257 case kCubic_Verb:
258 SkASSERT(moveCnt && !closeCount);
259 SkDEBUGCODE(++segmentCount);
260 nextPt = 3;
261 break;
262 case kClose_Verb:
263 SkDEBUGCODE(++closeCount;)
264 break;
265 default:
266 SkDEBUGFAIL("unknown verb");
267 }
268 if (-1 != nextPt) {
269 if (SkPath::kConic_Verb == verb) {
270 SkConic orig;
271 orig.set(pts, iter.conicWeight());
272 SkPoint quadPts[5];
273 int count = orig.chopIntoQuadsPOW2(quadPts, 1);
274 SK_ALWAYSBREAK(2 == count);
275
276 if (!check_edge_against_rect(quadPts[0], quadPts[2], rect, direction)) {
277 return false;
278 }
279 if (!check_edge_against_rect(quadPts[2], quadPts[4], rect, direction)) {
280 return false;
281 }
282 } else {
283 if (!check_edge_against_rect(prevPt, pts[nextPt], rect, direction)) {
284 return false;
285 }
286 }
287 prevPt = pts[nextPt];
288 }
289 }
290
291 return check_edge_against_rect(prevPt, firstPt, rect, direction);
292 }
293
getGenerationID() const294 uint32_t SkPath::getGenerationID() const {
295 uint32_t genID = fPathRef->genID();
296 #ifdef SK_BUILD_FOR_ANDROID_FRAMEWORK
297 SkASSERT((unsigned)fFillType < (1 << (32 - kPathRefGenIDBitCnt)));
298 genID |= static_cast<uint32_t>(fFillType) << kPathRefGenIDBitCnt;
299 #endif
300 return genID;
301 }
302
reset()303 void SkPath::reset() {
304 SkDEBUGCODE(this->validate();)
305
306 fPathRef.reset(SkPathRef::CreateEmpty());
307 this->resetFields();
308 }
309
rewind()310 void SkPath::rewind() {
311 SkDEBUGCODE(this->validate();)
312
313 SkPathRef::Rewind(&fPathRef);
314 this->resetFields();
315 }
316
isLine(SkPoint line[2]) const317 bool SkPath::isLine(SkPoint line[2]) const {
318 int verbCount = fPathRef->countVerbs();
319
320 if (2 == verbCount) {
321 SkASSERT(kMove_Verb == fPathRef->atVerb(0));
322 if (kLine_Verb == fPathRef->atVerb(1)) {
323 SkASSERT(2 == fPathRef->countPoints());
324 if (line) {
325 const SkPoint* pts = fPathRef->points();
326 line[0] = pts[0];
327 line[1] = pts[1];
328 }
329 return true;
330 }
331 }
332 return false;
333 }
334
335 /*
336 Determines if path is a rect by keeping track of changes in direction
337 and looking for a loop either clockwise or counterclockwise.
338
339 The direction is computed such that:
340 0: vertical up
341 1: horizontal left
342 2: vertical down
343 3: horizontal right
344
345 A rectangle cycles up/right/down/left or up/left/down/right.
346
347 The test fails if:
348 The path is closed, and followed by a line.
349 A second move creates a new endpoint.
350 A diagonal line is parsed.
351 There's more than four changes of direction.
352 There's a discontinuity on the line (e.g., a move in the middle)
353 The line reverses direction.
354 The path contains a quadratic or cubic.
355 The path contains fewer than four points.
356 *The rectangle doesn't complete a cycle.
357 *The final point isn't equal to the first point.
358
359 *These last two conditions we relax if we have a 3-edge path that would
360 form a rectangle if it were closed (as we do when we fill a path)
361
362 It's OK if the path has:
363 Several colinear line segments composing a rectangle side.
364 Single points on the rectangle side.
365
366 The direction takes advantage of the corners found since opposite sides
367 must travel in opposite directions.
368
369 FIXME: Allow colinear quads and cubics to be treated like lines.
370 FIXME: If the API passes fill-only, return true if the filled stroke
371 is a rectangle, though the caller failed to close the path.
372
373 first,last,next direction state-machine:
374 0x1 is set if the segment is horizontal
375 0x2 is set if the segment is moving to the right or down
376 thus:
377 two directions are opposites iff (dirA ^ dirB) == 0x2
378 two directions are perpendicular iff (dirA ^ dirB) == 0x1
379
380 */
rect_make_dir(SkScalar dx,SkScalar dy)381 static int rect_make_dir(SkScalar dx, SkScalar dy) {
382 return ((0 != dx) << 0) | ((dx > 0 || dy > 0) << 1);
383 }
isRectContour(bool allowPartial,int * currVerb,const SkPoint ** ptsPtr,bool * isClosed,Direction * direction) const384 bool SkPath::isRectContour(bool allowPartial, int* currVerb, const SkPoint** ptsPtr,
385 bool* isClosed, Direction* direction) const {
386 int corners = 0;
387 SkPoint first, last;
388 const SkPoint* pts = *ptsPtr;
389 const SkPoint* savePts = NULL;
390 first.set(0, 0);
391 last.set(0, 0);
392 int firstDirection = 0;
393 int lastDirection = 0;
394 int nextDirection = 0;
395 bool closedOrMoved = false;
396 bool autoClose = false;
397 bool insertClose = false;
398 int verbCnt = fPathRef->countVerbs();
399 while (*currVerb < verbCnt && (!allowPartial || !autoClose)) {
400 uint8_t verb = insertClose ? (uint8_t) kClose_Verb : fPathRef->atVerb(*currVerb);
401 switch (verb) {
402 case kClose_Verb:
403 savePts = pts;
404 pts = *ptsPtr;
405 autoClose = true;
406 insertClose = false;
407 case kLine_Verb: {
408 SkScalar left = last.fX;
409 SkScalar top = last.fY;
410 SkScalar right = pts->fX;
411 SkScalar bottom = pts->fY;
412 ++pts;
413 if (left != right && top != bottom) {
414 return false; // diagonal
415 }
416 if (left == right && top == bottom) {
417 break; // single point on side OK
418 }
419 nextDirection = rect_make_dir(right - left, bottom - top);
420 if (0 == corners) {
421 firstDirection = nextDirection;
422 first = last;
423 last = pts[-1];
424 corners = 1;
425 closedOrMoved = false;
426 break;
427 }
428 if (closedOrMoved) {
429 return false; // closed followed by a line
430 }
431 if (autoClose && nextDirection == firstDirection) {
432 break; // colinear with first
433 }
434 closedOrMoved = autoClose;
435 if (lastDirection != nextDirection) {
436 if (++corners > 4) {
437 return false; // too many direction changes
438 }
439 }
440 last = pts[-1];
441 if (lastDirection == nextDirection) {
442 break; // colinear segment
443 }
444 // Possible values for corners are 2, 3, and 4.
445 // When corners == 3, nextDirection opposes firstDirection.
446 // Otherwise, nextDirection at corner 2 opposes corner 4.
447 int turn = firstDirection ^ (corners - 1);
448 int directionCycle = 3 == corners ? 0 : nextDirection ^ turn;
449 if ((directionCycle ^ turn) != nextDirection) {
450 return false; // direction didn't follow cycle
451 }
452 break;
453 }
454 case kQuad_Verb:
455 case kConic_Verb:
456 case kCubic_Verb:
457 return false; // quadratic, cubic not allowed
458 case kMove_Verb:
459 if (allowPartial && !autoClose && firstDirection) {
460 insertClose = true;
461 *currVerb -= 1; // try move again afterwards
462 goto addMissingClose;
463 }
464 last = *pts++;
465 closedOrMoved = true;
466 break;
467 default:
468 SkDEBUGFAIL("unexpected verb");
469 break;
470 }
471 *currVerb += 1;
472 lastDirection = nextDirection;
473 addMissingClose:
474 ;
475 }
476 // Success if 4 corners and first point equals last
477 bool result = 4 == corners && (first == last || autoClose);
478 if (!result) {
479 // check if we are just an incomplete rectangle, in which case we can
480 // return true, but not claim to be closed.
481 // e.g.
482 // 3 sided rectangle
483 // 4 sided but the last edge is not long enough to reach the start
484 //
485 SkScalar closeX = first.x() - last.x();
486 SkScalar closeY = first.y() - last.y();
487 if (closeX && closeY) {
488 return false; // we're diagonal, abort (can we ever reach this?)
489 }
490 int closeDirection = rect_make_dir(closeX, closeY);
491 // make sure the close-segment doesn't double-back on itself
492 if (3 == corners || (4 == corners && closeDirection == lastDirection)) {
493 result = true;
494 autoClose = false; // we are not closed
495 }
496 }
497 if (savePts) {
498 *ptsPtr = savePts;
499 }
500 if (result && isClosed) {
501 *isClosed = autoClose;
502 }
503 if (result && direction) {
504 *direction = firstDirection == ((lastDirection + 1) & 3) ? kCCW_Direction : kCW_Direction;
505 }
506 return result;
507 }
508
isRect(SkRect * rect,bool * isClosed,Direction * direction) const509 bool SkPath::isRect(SkRect* rect, bool* isClosed, Direction* direction) const {
510 SkDEBUGCODE(this->validate();)
511 int currVerb = 0;
512 const SkPoint* pts = fPathRef->points();
513 const SkPoint* first = pts;
514 if (!this->isRectContour(false, &currVerb, &pts, isClosed, direction)) {
515 return false;
516 }
517 if (rect) {
518 int32_t num = SkToS32(pts - first);
519 if (num) {
520 rect->set(first, num);
521 } else {
522 // 'pts' isn't updated for open rects
523 *rect = this->getBounds();
524 }
525 }
526 return true;
527 }
528
isNestedFillRects(SkRect rects[2],Direction dirs[2]) const529 bool SkPath::isNestedFillRects(SkRect rects[2], Direction dirs[2]) const {
530 SkDEBUGCODE(this->validate();)
531 int currVerb = 0;
532 const SkPoint* pts = fPathRef->points();
533 const SkPoint* first = pts;
534 Direction testDirs[2];
535 if (!isRectContour(true, &currVerb, &pts, NULL, &testDirs[0])) {
536 return false;
537 }
538 const SkPoint* last = pts;
539 SkRect testRects[2];
540 bool isClosed;
541 if (isRectContour(false, &currVerb, &pts, &isClosed, &testDirs[1])) {
542 testRects[0].set(first, SkToS32(last - first));
543 if (!isClosed) {
544 pts = fPathRef->points() + fPathRef->countPoints();
545 }
546 testRects[1].set(last, SkToS32(pts - last));
547 if (testRects[0].contains(testRects[1])) {
548 if (rects) {
549 rects[0] = testRects[0];
550 rects[1] = testRects[1];
551 }
552 if (dirs) {
553 dirs[0] = testDirs[0];
554 dirs[1] = testDirs[1];
555 }
556 return true;
557 }
558 if (testRects[1].contains(testRects[0])) {
559 if (rects) {
560 rects[0] = testRects[1];
561 rects[1] = testRects[0];
562 }
563 if (dirs) {
564 dirs[0] = testDirs[1];
565 dirs[1] = testDirs[0];
566 }
567 return true;
568 }
569 }
570 return false;
571 }
572
countPoints() const573 int SkPath::countPoints() const {
574 return fPathRef->countPoints();
575 }
576
getPoints(SkPoint dst[],int max) const577 int SkPath::getPoints(SkPoint dst[], int max) const {
578 SkDEBUGCODE(this->validate();)
579
580 SkASSERT(max >= 0);
581 SkASSERT(!max || dst);
582 int count = SkMin32(max, fPathRef->countPoints());
583 memcpy(dst, fPathRef->points(), count * sizeof(SkPoint));
584 return fPathRef->countPoints();
585 }
586
getPoint(int index) const587 SkPoint SkPath::getPoint(int index) const {
588 if ((unsigned)index < (unsigned)fPathRef->countPoints()) {
589 return fPathRef->atPoint(index);
590 }
591 return SkPoint::Make(0, 0);
592 }
593
countVerbs() const594 int SkPath::countVerbs() const {
595 return fPathRef->countVerbs();
596 }
597
copy_verbs_reverse(uint8_t * inorderDst,const uint8_t * reversedSrc,int count)598 static inline void copy_verbs_reverse(uint8_t* inorderDst,
599 const uint8_t* reversedSrc,
600 int count) {
601 for (int i = 0; i < count; ++i) {
602 inorderDst[i] = reversedSrc[~i];
603 }
604 }
605
getVerbs(uint8_t dst[],int max) const606 int SkPath::getVerbs(uint8_t dst[], int max) const {
607 SkDEBUGCODE(this->validate();)
608
609 SkASSERT(max >= 0);
610 SkASSERT(!max || dst);
611 int count = SkMin32(max, fPathRef->countVerbs());
612 copy_verbs_reverse(dst, fPathRef->verbs(), count);
613 return fPathRef->countVerbs();
614 }
615
getLastPt(SkPoint * lastPt) const616 bool SkPath::getLastPt(SkPoint* lastPt) const {
617 SkDEBUGCODE(this->validate();)
618
619 int count = fPathRef->countPoints();
620 if (count > 0) {
621 if (lastPt) {
622 *lastPt = fPathRef->atPoint(count - 1);
623 }
624 return true;
625 }
626 if (lastPt) {
627 lastPt->set(0, 0);
628 }
629 return false;
630 }
631
setPt(int index,SkScalar x,SkScalar y)632 void SkPath::setPt(int index, SkScalar x, SkScalar y) {
633 SkDEBUGCODE(this->validate();)
634
635 int count = fPathRef->countPoints();
636 if (count <= index) {
637 return;
638 } else {
639 SkPathRef::Editor ed(&fPathRef);
640 ed.atPoint(index)->set(x, y);
641 }
642 }
643
setLastPt(SkScalar x,SkScalar y)644 void SkPath::setLastPt(SkScalar x, SkScalar y) {
645 SkDEBUGCODE(this->validate();)
646
647 int count = fPathRef->countPoints();
648 if (count == 0) {
649 this->moveTo(x, y);
650 } else {
651 SkPathRef::Editor ed(&fPathRef);
652 ed.atPoint(count-1)->set(x, y);
653 }
654 }
655
setConvexity(Convexity c)656 void SkPath::setConvexity(Convexity c) {
657 if (fConvexity != c) {
658 fConvexity = c;
659 }
660 }
661
662 //////////////////////////////////////////////////////////////////////////////
663 // Construction methods
664
665 #define DIRTY_AFTER_EDIT \
666 do { \
667 fConvexity = kUnknown_Convexity; \
668 fDirection = kUnknown_Direction; \
669 } while (0)
670
incReserve(U16CPU inc)671 void SkPath::incReserve(U16CPU inc) {
672 SkDEBUGCODE(this->validate();)
673 SkPathRef::Editor(&fPathRef, inc, inc);
674 SkDEBUGCODE(this->validate();)
675 }
676
moveTo(SkScalar x,SkScalar y)677 void SkPath::moveTo(SkScalar x, SkScalar y) {
678 SkDEBUGCODE(this->validate();)
679
680 SkPathRef::Editor ed(&fPathRef);
681
682 // remember our index
683 fLastMoveToIndex = fPathRef->countPoints();
684
685 ed.growForVerb(kMove_Verb)->set(x, y);
686
687 DIRTY_AFTER_EDIT;
688 }
689
rMoveTo(SkScalar x,SkScalar y)690 void SkPath::rMoveTo(SkScalar x, SkScalar y) {
691 SkPoint pt;
692 this->getLastPt(&pt);
693 this->moveTo(pt.fX + x, pt.fY + y);
694 }
695
injectMoveToIfNeeded()696 void SkPath::injectMoveToIfNeeded() {
697 if (fLastMoveToIndex < 0) {
698 SkScalar x, y;
699 if (fPathRef->countVerbs() == 0) {
700 x = y = 0;
701 } else {
702 const SkPoint& pt = fPathRef->atPoint(~fLastMoveToIndex);
703 x = pt.fX;
704 y = pt.fY;
705 }
706 this->moveTo(x, y);
707 }
708 }
709
lineTo(SkScalar x,SkScalar y)710 void SkPath::lineTo(SkScalar x, SkScalar y) {
711 SkDEBUGCODE(this->validate();)
712
713 this->injectMoveToIfNeeded();
714
715 SkPathRef::Editor ed(&fPathRef);
716 ed.growForVerb(kLine_Verb)->set(x, y);
717
718 DIRTY_AFTER_EDIT;
719 }
720
rLineTo(SkScalar x,SkScalar y)721 void SkPath::rLineTo(SkScalar x, SkScalar y) {
722 this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt().
723 SkPoint pt;
724 this->getLastPt(&pt);
725 this->lineTo(pt.fX + x, pt.fY + y);
726 }
727
quadTo(SkScalar x1,SkScalar y1,SkScalar x2,SkScalar y2)728 void SkPath::quadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) {
729 SkDEBUGCODE(this->validate();)
730
731 this->injectMoveToIfNeeded();
732
733 SkPathRef::Editor ed(&fPathRef);
734 SkPoint* pts = ed.growForVerb(kQuad_Verb);
735 pts[0].set(x1, y1);
736 pts[1].set(x2, y2);
737
738 DIRTY_AFTER_EDIT;
739 }
740
rQuadTo(SkScalar x1,SkScalar y1,SkScalar x2,SkScalar y2)741 void SkPath::rQuadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) {
742 this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt().
743 SkPoint pt;
744 this->getLastPt(&pt);
745 this->quadTo(pt.fX + x1, pt.fY + y1, pt.fX + x2, pt.fY + y2);
746 }
747
conicTo(SkScalar x1,SkScalar y1,SkScalar x2,SkScalar y2,SkScalar w)748 void SkPath::conicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
749 SkScalar w) {
750 // check for <= 0 or NaN with this test
751 if (!(w > 0)) {
752 this->lineTo(x2, y2);
753 } else if (!SkScalarIsFinite(w)) {
754 this->lineTo(x1, y1);
755 this->lineTo(x2, y2);
756 } else if (SK_Scalar1 == w) {
757 this->quadTo(x1, y1, x2, y2);
758 } else {
759 SkDEBUGCODE(this->validate();)
760
761 this->injectMoveToIfNeeded();
762
763 SkPathRef::Editor ed(&fPathRef);
764 SkPoint* pts = ed.growForVerb(kConic_Verb, w);
765 pts[0].set(x1, y1);
766 pts[1].set(x2, y2);
767
768 DIRTY_AFTER_EDIT;
769 }
770 }
771
rConicTo(SkScalar dx1,SkScalar dy1,SkScalar dx2,SkScalar dy2,SkScalar w)772 void SkPath::rConicTo(SkScalar dx1, SkScalar dy1, SkScalar dx2, SkScalar dy2,
773 SkScalar w) {
774 this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt().
775 SkPoint pt;
776 this->getLastPt(&pt);
777 this->conicTo(pt.fX + dx1, pt.fY + dy1, pt.fX + dx2, pt.fY + dy2, w);
778 }
779
cubicTo(SkScalar x1,SkScalar y1,SkScalar x2,SkScalar y2,SkScalar x3,SkScalar y3)780 void SkPath::cubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
781 SkScalar x3, SkScalar y3) {
782 SkDEBUGCODE(this->validate();)
783
784 this->injectMoveToIfNeeded();
785
786 SkPathRef::Editor ed(&fPathRef);
787 SkPoint* pts = ed.growForVerb(kCubic_Verb);
788 pts[0].set(x1, y1);
789 pts[1].set(x2, y2);
790 pts[2].set(x3, y3);
791
792 DIRTY_AFTER_EDIT;
793 }
794
rCubicTo(SkScalar x1,SkScalar y1,SkScalar x2,SkScalar y2,SkScalar x3,SkScalar y3)795 void SkPath::rCubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
796 SkScalar x3, SkScalar y3) {
797 this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt().
798 SkPoint pt;
799 this->getLastPt(&pt);
800 this->cubicTo(pt.fX + x1, pt.fY + y1, pt.fX + x2, pt.fY + y2,
801 pt.fX + x3, pt.fY + y3);
802 }
803
close()804 void SkPath::close() {
805 SkDEBUGCODE(this->validate();)
806
807 int count = fPathRef->countVerbs();
808 if (count > 0) {
809 switch (fPathRef->atVerb(count - 1)) {
810 case kLine_Verb:
811 case kQuad_Verb:
812 case kConic_Verb:
813 case kCubic_Verb:
814 case kMove_Verb: {
815 SkPathRef::Editor ed(&fPathRef);
816 ed.growForVerb(kClose_Verb);
817 break;
818 }
819 case kClose_Verb:
820 // don't add a close if it's the first verb or a repeat
821 break;
822 default:
823 SkDEBUGFAIL("unexpected verb");
824 break;
825 }
826 }
827
828 // signal that we need a moveTo to follow us (unless we're done)
829 #if 0
830 if (fLastMoveToIndex >= 0) {
831 fLastMoveToIndex = ~fLastMoveToIndex;
832 }
833 #else
834 fLastMoveToIndex ^= ~fLastMoveToIndex >> (8 * sizeof(fLastMoveToIndex) - 1);
835 #endif
836 }
837
838 ///////////////////////////////////////////////////////////////////////////////
839
assert_known_direction(int dir)840 static void assert_known_direction(int dir) {
841 SkASSERT(SkPath::kCW_Direction == dir || SkPath::kCCW_Direction == dir);
842 }
843
addRect(const SkRect & rect,Direction dir)844 void SkPath::addRect(const SkRect& rect, Direction dir) {
845 this->addRect(rect.fLeft, rect.fTop, rect.fRight, rect.fBottom, dir);
846 }
847
addRect(SkScalar left,SkScalar top,SkScalar right,SkScalar bottom,Direction dir)848 void SkPath::addRect(SkScalar left, SkScalar top, SkScalar right,
849 SkScalar bottom, Direction dir) {
850 assert_known_direction(dir);
851 fDirection = this->hasOnlyMoveTos() ? dir : kUnknown_Direction;
852 SkAutoDisableDirectionCheck addc(this);
853
854 SkAutoPathBoundsUpdate apbu(this, left, top, right, bottom);
855
856 this->incReserve(5);
857
858 this->moveTo(left, top);
859 if (dir == kCCW_Direction) {
860 this->lineTo(left, bottom);
861 this->lineTo(right, bottom);
862 this->lineTo(right, top);
863 } else {
864 this->lineTo(right, top);
865 this->lineTo(right, bottom);
866 this->lineTo(left, bottom);
867 }
868 this->close();
869 }
870
addPoly(const SkPoint pts[],int count,bool close)871 void SkPath::addPoly(const SkPoint pts[], int count, bool close) {
872 SkDEBUGCODE(this->validate();)
873 if (count <= 0) {
874 return;
875 }
876
877 fLastMoveToIndex = fPathRef->countPoints();
878
879 // +close makes room for the extra kClose_Verb
880 SkPathRef::Editor ed(&fPathRef, count+close, count);
881
882 ed.growForVerb(kMove_Verb)->set(pts[0].fX, pts[0].fY);
883 if (count > 1) {
884 SkPoint* p = ed.growForRepeatedVerb(kLine_Verb, count - 1);
885 memcpy(p, &pts[1], (count-1) * sizeof(SkPoint));
886 }
887
888 if (close) {
889 ed.growForVerb(kClose_Verb);
890 fLastMoveToIndex ^= ~fLastMoveToIndex >> (8 * sizeof(fLastMoveToIndex) - 1);
891 }
892
893 DIRTY_AFTER_EDIT;
894 SkDEBUGCODE(this->validate();)
895 }
896
897 #include "SkGeometry.h"
898
arc_is_lone_point(const SkRect & oval,SkScalar startAngle,SkScalar sweepAngle,SkPoint * pt)899 static bool arc_is_lone_point(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle,
900 SkPoint* pt) {
901 if (0 == sweepAngle && (0 == startAngle || SkIntToScalar(360) == startAngle)) {
902 // Chrome uses this path to move into and out of ovals. If not
903 // treated as a special case the moves can distort the oval's
904 // bounding box (and break the circle special case).
905 pt->set(oval.fRight, oval.centerY());
906 return true;
907 } else if (0 == oval.width() && 0 == oval.height()) {
908 // Chrome will sometimes create 0 radius round rects. Having degenerate
909 // quad segments in the path prevents the path from being recognized as
910 // a rect.
911 // TODO: optimizing the case where only one of width or height is zero
912 // should also be considered. This case, however, doesn't seem to be
913 // as common as the single point case.
914 pt->set(oval.fRight, oval.fTop);
915 return true;
916 }
917 return false;
918 }
919
920 // Return the unit vectors pointing at the start/stop points for the given start/sweep angles
921 //
angles_to_unit_vectors(SkScalar startAngle,SkScalar sweepAngle,SkVector * startV,SkVector * stopV,SkRotationDirection * dir)922 static void angles_to_unit_vectors(SkScalar startAngle, SkScalar sweepAngle,
923 SkVector* startV, SkVector* stopV, SkRotationDirection* dir) {
924 startV->fY = SkScalarSinCos(SkDegreesToRadians(startAngle), &startV->fX);
925 stopV->fY = SkScalarSinCos(SkDegreesToRadians(startAngle + sweepAngle), &stopV->fX);
926
927 /* If the sweep angle is nearly (but less than) 360, then due to precision
928 loss in radians-conversion and/or sin/cos, we may end up with coincident
929 vectors, which will fool SkBuildQuadArc into doing nothing (bad) instead
930 of drawing a nearly complete circle (good).
931 e.g. canvas.drawArc(0, 359.99, ...)
932 -vs- canvas.drawArc(0, 359.9, ...)
933 We try to detect this edge case, and tweak the stop vector
934 */
935 if (*startV == *stopV) {
936 SkScalar sw = SkScalarAbs(sweepAngle);
937 if (sw < SkIntToScalar(360) && sw > SkIntToScalar(359)) {
938 SkScalar stopRad = SkDegreesToRadians(startAngle + sweepAngle);
939 // make a guess at a tiny angle (in radians) to tweak by
940 SkScalar deltaRad = SkScalarCopySign(SK_Scalar1/512, sweepAngle);
941 // not sure how much will be enough, so we use a loop
942 do {
943 stopRad -= deltaRad;
944 stopV->fY = SkScalarSinCos(stopRad, &stopV->fX);
945 } while (*startV == *stopV);
946 }
947 }
948 *dir = sweepAngle > 0 ? kCW_SkRotationDirection : kCCW_SkRotationDirection;
949 }
950
951 /**
952 * If this returns 0, then the caller should just line-to the singlePt, else it should
953 * ignore singlePt and append the specified number of conics.
954 */
build_arc_conics(const SkRect & oval,const SkVector & start,const SkVector & stop,SkRotationDirection dir,SkConic conics[SkConic::kMaxConicsForArc],SkPoint * singlePt)955 static int build_arc_conics(const SkRect& oval, const SkVector& start, const SkVector& stop,
956 SkRotationDirection dir, SkConic conics[SkConic::kMaxConicsForArc],
957 SkPoint* singlePt) {
958 SkMatrix matrix;
959
960 matrix.setScale(SkScalarHalf(oval.width()), SkScalarHalf(oval.height()));
961 matrix.postTranslate(oval.centerX(), oval.centerY());
962
963 int count = SkConic::BuildUnitArc(start, stop, dir, &matrix, conics);
964 if (0 == count) {
965 matrix.mapXY(start.x(), start.y(), singlePt);
966 }
967 return count;
968 }
969
addRoundRect(const SkRect & rect,const SkScalar radii[],Direction dir)970 void SkPath::addRoundRect(const SkRect& rect, const SkScalar radii[],
971 Direction dir) {
972 SkRRect rrect;
973 rrect.setRectRadii(rect, (const SkVector*) radii);
974 this->addRRect(rrect, dir);
975 }
976
addRRect(const SkRRect & rrect,Direction dir)977 void SkPath::addRRect(const SkRRect& rrect, Direction dir) {
978 assert_known_direction(dir);
979
980 if (rrect.isEmpty()) {
981 return;
982 }
983
984 const SkRect& bounds = rrect.getBounds();
985
986 if (rrect.isRect()) {
987 this->addRect(bounds, dir);
988 } else if (rrect.isOval()) {
989 this->addOval(bounds, dir);
990 } else {
991 fDirection = this->hasOnlyMoveTos() ? dir : kUnknown_Direction;
992
993 SkAutoPathBoundsUpdate apbu(this, bounds);
994 SkAutoDisableDirectionCheck addc(this);
995
996 const SkScalar L = bounds.fLeft;
997 const SkScalar T = bounds.fTop;
998 const SkScalar R = bounds.fRight;
999 const SkScalar B = bounds.fBottom;
1000 const SkScalar W = SK_ScalarRoot2Over2;
1001
1002 this->incReserve(13);
1003 if (kCW_Direction == dir) {
1004 this->moveTo(L, B - rrect.fRadii[SkRRect::kLowerLeft_Corner].fY);
1005
1006 this->lineTo(L, T + rrect.fRadii[SkRRect::kUpperLeft_Corner].fY);
1007 this->conicTo(L, T, L + rrect.fRadii[SkRRect::kUpperLeft_Corner].fX, T, W);
1008
1009 this->lineTo(R - rrect.fRadii[SkRRect::kUpperRight_Corner].fX, T);
1010 this->conicTo(R, T, R, T + rrect.fRadii[SkRRect::kUpperRight_Corner].fY, W);
1011
1012 this->lineTo(R, B - rrect.fRadii[SkRRect::kLowerRight_Corner].fY);
1013 this->conicTo(R, B, R - rrect.fRadii[SkRRect::kLowerRight_Corner].fX, B, W);
1014
1015 this->lineTo(L + rrect.fRadii[SkRRect::kLowerLeft_Corner].fX, B);
1016 this->conicTo(L, B, L, B - rrect.fRadii[SkRRect::kLowerLeft_Corner].fY, W);
1017 } else {
1018 this->moveTo(L, T + rrect.fRadii[SkRRect::kUpperLeft_Corner].fY);
1019
1020 this->lineTo(L, B - rrect.fRadii[SkRRect::kLowerLeft_Corner].fY);
1021 this->conicTo(L, B, L + rrect.fRadii[SkRRect::kLowerLeft_Corner].fX, B, W);
1022
1023 this->lineTo(R - rrect.fRadii[SkRRect::kLowerRight_Corner].fX, B);
1024 this->conicTo(R, B, R, B - rrect.fRadii[SkRRect::kLowerRight_Corner].fY, W);
1025
1026 this->lineTo(R, T + rrect.fRadii[SkRRect::kUpperRight_Corner].fY);
1027 this->conicTo(R, T, R - rrect.fRadii[SkRRect::kUpperRight_Corner].fX, T, W);
1028
1029 this->lineTo(L + rrect.fRadii[SkRRect::kUpperLeft_Corner].fX, T);
1030 this->conicTo(L, T, L, T + rrect.fRadii[SkRRect::kUpperLeft_Corner].fY, W);
1031 }
1032 this->close();
1033 }
1034 SkDEBUGCODE(fPathRef->validate();)
1035 }
1036
hasOnlyMoveTos() const1037 bool SkPath::hasOnlyMoveTos() const {
1038 int count = fPathRef->countVerbs();
1039 const uint8_t* verbs = const_cast<const SkPathRef*>(fPathRef.get())->verbsMemBegin();
1040 for (int i = 0; i < count; ++i) {
1041 if (*verbs == kLine_Verb ||
1042 *verbs == kQuad_Verb ||
1043 *verbs == kConic_Verb ||
1044 *verbs == kCubic_Verb) {
1045 return false;
1046 }
1047 ++verbs;
1048 }
1049 return true;
1050 }
1051
addRoundRect(const SkRect & rect,SkScalar rx,SkScalar ry,Direction dir)1052 void SkPath::addRoundRect(const SkRect& rect, SkScalar rx, SkScalar ry,
1053 Direction dir) {
1054 assert_known_direction(dir);
1055
1056 if (rx < 0 || ry < 0) {
1057 SkErrorInternals::SetError( kInvalidArgument_SkError,
1058 "I got %f and %f as radii to SkPath::AddRoundRect, "
1059 "but negative radii are not allowed.",
1060 SkScalarToDouble(rx), SkScalarToDouble(ry) );
1061 return;
1062 }
1063
1064 SkRRect rrect;
1065 rrect.setRectXY(rect, rx, ry);
1066 this->addRRect(rrect, dir);
1067 }
1068
addOval(const SkRect & oval,Direction dir)1069 void SkPath::addOval(const SkRect& oval, Direction dir) {
1070 assert_known_direction(dir);
1071
1072 /* If addOval() is called after previous moveTo(),
1073 this path is still marked as an oval. This is used to
1074 fit into WebKit's calling sequences.
1075 We can't simply check isEmpty() in this case, as additional
1076 moveTo() would mark the path non empty.
1077 */
1078 bool isOval = hasOnlyMoveTos();
1079 if (isOval) {
1080 fDirection = dir;
1081 } else {
1082 fDirection = kUnknown_Direction;
1083 }
1084
1085 SkAutoDisableDirectionCheck addc(this);
1086
1087 SkAutoPathBoundsUpdate apbu(this, oval);
1088
1089 const SkScalar L = oval.fLeft;
1090 const SkScalar T = oval.fTop;
1091 const SkScalar R = oval.fRight;
1092 const SkScalar B = oval.fBottom;
1093 const SkScalar cx = oval.centerX();
1094 const SkScalar cy = oval.centerY();
1095 const SkScalar weight = SK_ScalarRoot2Over2;
1096
1097 this->incReserve(9); // move + 4 conics
1098 this->moveTo(R, cy);
1099 if (dir == kCCW_Direction) {
1100 this->conicTo(R, T, cx, T, weight);
1101 this->conicTo(L, T, L, cy, weight);
1102 this->conicTo(L, B, cx, B, weight);
1103 this->conicTo(R, B, R, cy, weight);
1104 } else {
1105 this->conicTo(R, B, cx, B, weight);
1106 this->conicTo(L, B, L, cy, weight);
1107 this->conicTo(L, T, cx, T, weight);
1108 this->conicTo(R, T, R, cy, weight);
1109 }
1110 this->close();
1111
1112 SkPathRef::Editor ed(&fPathRef);
1113
1114 ed.setIsOval(isOval);
1115 }
1116
addCircle(SkScalar x,SkScalar y,SkScalar r,Direction dir)1117 void SkPath::addCircle(SkScalar x, SkScalar y, SkScalar r, Direction dir) {
1118 if (r > 0) {
1119 SkRect rect;
1120 rect.set(x - r, y - r, x + r, y + r);
1121 this->addOval(rect, dir);
1122 }
1123 }
1124
arcTo(const SkRect & oval,SkScalar startAngle,SkScalar sweepAngle,bool forceMoveTo)1125 void SkPath::arcTo(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle,
1126 bool forceMoveTo) {
1127 if (oval.width() < 0 || oval.height() < 0) {
1128 return;
1129 }
1130
1131 if (fPathRef->countVerbs() == 0) {
1132 forceMoveTo = true;
1133 }
1134
1135 SkPoint lonePt;
1136 if (arc_is_lone_point(oval, startAngle, sweepAngle, &lonePt)) {
1137 forceMoveTo ? this->moveTo(lonePt) : this->lineTo(lonePt);
1138 return;
1139 }
1140
1141 SkVector startV, stopV;
1142 SkRotationDirection dir;
1143 angles_to_unit_vectors(startAngle, sweepAngle, &startV, &stopV, &dir);
1144
1145 SkPoint singlePt;
1146 SkConic conics[SkConic::kMaxConicsForArc];
1147 int count = build_arc_conics(oval, startV, stopV, dir, conics, &singlePt);
1148 if (count) {
1149 this->incReserve(count * 2 + 1);
1150 const SkPoint& pt = conics[0].fPts[0];
1151 forceMoveTo ? this->moveTo(pt) : this->lineTo(pt);
1152 for (int i = 0; i < count; ++i) {
1153 this->conicTo(conics[i].fPts[1], conics[i].fPts[2], conics[i].fW);
1154 }
1155 } else {
1156 forceMoveTo ? this->moveTo(singlePt) : this->lineTo(singlePt);
1157 }
1158 }
1159
addArc(const SkRect & oval,SkScalar startAngle,SkScalar sweepAngle)1160 void SkPath::addArc(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle) {
1161 if (oval.isEmpty() || 0 == sweepAngle) {
1162 return;
1163 }
1164
1165 const SkScalar kFullCircleAngle = SkIntToScalar(360);
1166
1167 if (sweepAngle >= kFullCircleAngle || sweepAngle <= -kFullCircleAngle) {
1168 this->addOval(oval, sweepAngle > 0 ? kCW_Direction : kCCW_Direction);
1169 } else {
1170 this->arcTo(oval, startAngle, sweepAngle, true);
1171 }
1172 }
1173
1174 /*
1175 Need to handle the case when the angle is sharp, and our computed end-points
1176 for the arc go behind pt1 and/or p2...
1177 */
arcTo(SkScalar x1,SkScalar y1,SkScalar x2,SkScalar y2,SkScalar radius)1178 void SkPath::arcTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2, SkScalar radius) {
1179 if (radius == 0) {
1180 this->lineTo(x1, y1);
1181 return;
1182 }
1183
1184 SkVector before, after;
1185
1186 // need to know our prev pt so we can construct tangent vectors
1187 {
1188 SkPoint start;
1189 this->getLastPt(&start);
1190 // Handle degenerate cases by adding a line to the first point and
1191 // bailing out.
1192 before.setNormalize(x1 - start.fX, y1 - start.fY);
1193 after.setNormalize(x2 - x1, y2 - y1);
1194 }
1195
1196 SkScalar cosh = SkPoint::DotProduct(before, after);
1197 SkScalar sinh = SkPoint::CrossProduct(before, after);
1198
1199 if (SkScalarNearlyZero(sinh)) { // angle is too tight
1200 this->lineTo(x1, y1);
1201 return;
1202 }
1203
1204 SkScalar dist = SkScalarMulDiv(radius, SK_Scalar1 - cosh, sinh);
1205 if (dist < 0) {
1206 dist = -dist;
1207 }
1208
1209 SkScalar xx = x1 - SkScalarMul(dist, before.fX);
1210 SkScalar yy = y1 - SkScalarMul(dist, before.fY);
1211 SkRotationDirection arcDir;
1212
1213 // now turn before/after into normals
1214 if (sinh > 0) {
1215 before.rotateCCW();
1216 after.rotateCCW();
1217 arcDir = kCW_SkRotationDirection;
1218 } else {
1219 before.rotateCW();
1220 after.rotateCW();
1221 arcDir = kCCW_SkRotationDirection;
1222 }
1223
1224 SkMatrix matrix;
1225 SkPoint pts[kSkBuildQuadArcStorage];
1226
1227 matrix.setScale(radius, radius);
1228 matrix.postTranslate(xx - SkScalarMul(radius, before.fX),
1229 yy - SkScalarMul(radius, before.fY));
1230
1231 int count = SkBuildQuadArc(before, after, arcDir, &matrix, pts);
1232
1233 this->incReserve(count);
1234 // [xx,yy] == pts[0]
1235 this->lineTo(xx, yy);
1236 for (int i = 1; i < count; i += 2) {
1237 this->quadTo(pts[i], pts[i+1]);
1238 }
1239 }
1240
1241 ///////////////////////////////////////////////////////////////////////////////
1242
addPath(const SkPath & path,SkScalar dx,SkScalar dy,AddPathMode mode)1243 void SkPath::addPath(const SkPath& path, SkScalar dx, SkScalar dy, AddPathMode mode) {
1244 SkMatrix matrix;
1245
1246 matrix.setTranslate(dx, dy);
1247 this->addPath(path, matrix, mode);
1248 }
1249
addPath(const SkPath & path,const SkMatrix & matrix,AddPathMode mode)1250 void SkPath::addPath(const SkPath& path, const SkMatrix& matrix, AddPathMode mode) {
1251 SkPathRef::Editor(&fPathRef, path.countVerbs(), path.countPoints());
1252
1253 RawIter iter(path);
1254 SkPoint pts[4];
1255 Verb verb;
1256
1257 SkMatrix::MapPtsProc proc = matrix.getMapPtsProc();
1258 bool firstVerb = true;
1259 while ((verb = iter.next(pts)) != kDone_Verb) {
1260 switch (verb) {
1261 case kMove_Verb:
1262 proc(matrix, &pts[0], &pts[0], 1);
1263 if (firstVerb && mode == kExtend_AddPathMode && !isEmpty()) {
1264 injectMoveToIfNeeded(); // In case last contour is closed
1265 this->lineTo(pts[0]);
1266 } else {
1267 this->moveTo(pts[0]);
1268 }
1269 break;
1270 case kLine_Verb:
1271 proc(matrix, &pts[1], &pts[1], 1);
1272 this->lineTo(pts[1]);
1273 break;
1274 case kQuad_Verb:
1275 proc(matrix, &pts[1], &pts[1], 2);
1276 this->quadTo(pts[1], pts[2]);
1277 break;
1278 case kConic_Verb:
1279 proc(matrix, &pts[1], &pts[1], 2);
1280 this->conicTo(pts[1], pts[2], iter.conicWeight());
1281 break;
1282 case kCubic_Verb:
1283 proc(matrix, &pts[1], &pts[1], 3);
1284 this->cubicTo(pts[1], pts[2], pts[3]);
1285 break;
1286 case kClose_Verb:
1287 this->close();
1288 break;
1289 default:
1290 SkDEBUGFAIL("unknown verb");
1291 }
1292 firstVerb = false;
1293 }
1294 }
1295
1296 ///////////////////////////////////////////////////////////////////////////////
1297
pts_in_verb(unsigned verb)1298 static int pts_in_verb(unsigned verb) {
1299 static const uint8_t gPtsInVerb[] = {
1300 1, // kMove
1301 1, // kLine
1302 2, // kQuad
1303 2, // kConic
1304 3, // kCubic
1305 0, // kClose
1306 0 // kDone
1307 };
1308
1309 SkASSERT(verb < SK_ARRAY_COUNT(gPtsInVerb));
1310 return gPtsInVerb[verb];
1311 }
1312
1313 // ignore the last point of the 1st contour
reversePathTo(const SkPath & path)1314 void SkPath::reversePathTo(const SkPath& path) {
1315 int i, vcount = path.fPathRef->countVerbs();
1316 // exit early if the path is empty, or just has a moveTo.
1317 if (vcount < 2) {
1318 return;
1319 }
1320
1321 SkPathRef::Editor(&fPathRef, vcount, path.countPoints());
1322
1323 const uint8_t* verbs = path.fPathRef->verbs();
1324 const SkPoint* pts = path.fPathRef->points();
1325 const SkScalar* conicWeights = path.fPathRef->conicWeights();
1326
1327 SkASSERT(verbs[~0] == kMove_Verb);
1328 for (i = 1; i < vcount; ++i) {
1329 unsigned v = verbs[~i];
1330 int n = pts_in_verb(v);
1331 if (n == 0) {
1332 break;
1333 }
1334 pts += n;
1335 conicWeights += (SkPath::kConic_Verb == v);
1336 }
1337
1338 while (--i > 0) {
1339 switch (verbs[~i]) {
1340 case kLine_Verb:
1341 this->lineTo(pts[-1].fX, pts[-1].fY);
1342 break;
1343 case kQuad_Verb:
1344 this->quadTo(pts[-1].fX, pts[-1].fY, pts[-2].fX, pts[-2].fY);
1345 break;
1346 case kConic_Verb:
1347 this->conicTo(pts[-1], pts[-2], *--conicWeights);
1348 break;
1349 case kCubic_Verb:
1350 this->cubicTo(pts[-1].fX, pts[-1].fY, pts[-2].fX, pts[-2].fY,
1351 pts[-3].fX, pts[-3].fY);
1352 break;
1353 default:
1354 SkDEBUGFAIL("bad verb");
1355 break;
1356 }
1357 pts -= pts_in_verb(verbs[~i]);
1358 }
1359 }
1360
reverseAddPath(const SkPath & src)1361 void SkPath::reverseAddPath(const SkPath& src) {
1362 SkPathRef::Editor ed(&fPathRef, src.fPathRef->countPoints(), src.fPathRef->countVerbs());
1363
1364 const SkPoint* pts = src.fPathRef->pointsEnd();
1365 // we will iterator through src's verbs backwards
1366 const uint8_t* verbs = src.fPathRef->verbsMemBegin(); // points at the last verb
1367 const uint8_t* verbsEnd = src.fPathRef->verbs(); // points just past the first verb
1368 const SkScalar* conicWeights = src.fPathRef->conicWeightsEnd();
1369
1370 bool needMove = true;
1371 bool needClose = false;
1372 while (verbs < verbsEnd) {
1373 uint8_t v = *(verbs++);
1374 int n = pts_in_verb(v);
1375
1376 if (needMove) {
1377 --pts;
1378 this->moveTo(pts->fX, pts->fY);
1379 needMove = false;
1380 }
1381 pts -= n;
1382 switch (v) {
1383 case kMove_Verb:
1384 if (needClose) {
1385 this->close();
1386 needClose = false;
1387 }
1388 needMove = true;
1389 pts += 1; // so we see the point in "if (needMove)" above
1390 break;
1391 case kLine_Verb:
1392 this->lineTo(pts[0]);
1393 break;
1394 case kQuad_Verb:
1395 this->quadTo(pts[1], pts[0]);
1396 break;
1397 case kConic_Verb:
1398 this->conicTo(pts[1], pts[0], *--conicWeights);
1399 break;
1400 case kCubic_Verb:
1401 this->cubicTo(pts[2], pts[1], pts[0]);
1402 break;
1403 case kClose_Verb:
1404 needClose = true;
1405 break;
1406 default:
1407 SkDEBUGFAIL("unexpected verb");
1408 }
1409 }
1410 }
1411
1412 ///////////////////////////////////////////////////////////////////////////////
1413
offset(SkScalar dx,SkScalar dy,SkPath * dst) const1414 void SkPath::offset(SkScalar dx, SkScalar dy, SkPath* dst) const {
1415 SkMatrix matrix;
1416
1417 matrix.setTranslate(dx, dy);
1418 this->transform(matrix, dst);
1419 }
1420
subdivide_cubic_to(SkPath * path,const SkPoint pts[4],int level=2)1421 static void subdivide_cubic_to(SkPath* path, const SkPoint pts[4],
1422 int level = 2) {
1423 if (--level >= 0) {
1424 SkPoint tmp[7];
1425
1426 SkChopCubicAtHalf(pts, tmp);
1427 subdivide_cubic_to(path, &tmp[0], level);
1428 subdivide_cubic_to(path, &tmp[3], level);
1429 } else {
1430 path->cubicTo(pts[1], pts[2], pts[3]);
1431 }
1432 }
1433
transform(const SkMatrix & matrix,SkPath * dst) const1434 void SkPath::transform(const SkMatrix& matrix, SkPath* dst) const {
1435 SkDEBUGCODE(this->validate();)
1436 if (dst == NULL) {
1437 dst = (SkPath*)this;
1438 }
1439
1440 if (matrix.hasPerspective()) {
1441 SkPath tmp;
1442 tmp.fFillType = fFillType;
1443
1444 SkPath::Iter iter(*this, false);
1445 SkPoint pts[4];
1446 SkPath::Verb verb;
1447
1448 while ((verb = iter.next(pts, false)) != kDone_Verb) {
1449 switch (verb) {
1450 case kMove_Verb:
1451 tmp.moveTo(pts[0]);
1452 break;
1453 case kLine_Verb:
1454 tmp.lineTo(pts[1]);
1455 break;
1456 case kQuad_Verb:
1457 // promote the quad to a conic
1458 tmp.conicTo(pts[1], pts[2],
1459 SkConic::TransformW(pts, SK_Scalar1, matrix));
1460 break;
1461 case kConic_Verb:
1462 tmp.conicTo(pts[1], pts[2],
1463 SkConic::TransformW(pts, iter.conicWeight(), matrix));
1464 break;
1465 case kCubic_Verb:
1466 subdivide_cubic_to(&tmp, pts);
1467 break;
1468 case kClose_Verb:
1469 tmp.close();
1470 break;
1471 default:
1472 SkDEBUGFAIL("unknown verb");
1473 break;
1474 }
1475 }
1476
1477 dst->swap(tmp);
1478 SkPathRef::Editor ed(&dst->fPathRef);
1479 matrix.mapPoints(ed.points(), ed.pathRef()->countPoints());
1480 dst->fDirection = kUnknown_Direction;
1481 } else {
1482 SkPathRef::CreateTransformedCopy(&dst->fPathRef, *fPathRef.get(), matrix);
1483
1484 if (this != dst) {
1485 dst->fFillType = fFillType;
1486 dst->fConvexity = fConvexity;
1487 dst->fIsVolatile = fIsVolatile;
1488 }
1489
1490 if (kUnknown_Direction == fDirection) {
1491 dst->fDirection = kUnknown_Direction;
1492 } else {
1493 SkScalar det2x2 =
1494 SkScalarMul(matrix.get(SkMatrix::kMScaleX), matrix.get(SkMatrix::kMScaleY)) -
1495 SkScalarMul(matrix.get(SkMatrix::kMSkewX), matrix.get(SkMatrix::kMSkewY));
1496 if (det2x2 < 0) {
1497 dst->fDirection = SkPath::OppositeDirection(static_cast<Direction>(fDirection));
1498 } else if (det2x2 > 0) {
1499 dst->fDirection = fDirection;
1500 } else {
1501 dst->fConvexity = kUnknown_Convexity;
1502 dst->fDirection = kUnknown_Direction;
1503 }
1504 }
1505
1506 SkDEBUGCODE(dst->validate();)
1507 }
1508 }
1509
1510 ///////////////////////////////////////////////////////////////////////////////
1511 ///////////////////////////////////////////////////////////////////////////////
1512
1513 enum SegmentState {
1514 kEmptyContour_SegmentState, // The current contour is empty. We may be
1515 // starting processing or we may have just
1516 // closed a contour.
1517 kAfterMove_SegmentState, // We have seen a move, but nothing else.
1518 kAfterPrimitive_SegmentState // We have seen a primitive but not yet
1519 // closed the path. Also the initial state.
1520 };
1521
Iter()1522 SkPath::Iter::Iter() {
1523 #ifdef SK_DEBUG
1524 fPts = NULL;
1525 fConicWeights = NULL;
1526 fMoveTo.fX = fMoveTo.fY = fLastPt.fX = fLastPt.fY = 0;
1527 fForceClose = fCloseLine = false;
1528 fSegmentState = kEmptyContour_SegmentState;
1529 #endif
1530 // need to init enough to make next() harmlessly return kDone_Verb
1531 fVerbs = NULL;
1532 fVerbStop = NULL;
1533 fNeedClose = false;
1534 }
1535
Iter(const SkPath & path,bool forceClose)1536 SkPath::Iter::Iter(const SkPath& path, bool forceClose) {
1537 this->setPath(path, forceClose);
1538 }
1539
setPath(const SkPath & path,bool forceClose)1540 void SkPath::Iter::setPath(const SkPath& path, bool forceClose) {
1541 fPts = path.fPathRef->points();
1542 fVerbs = path.fPathRef->verbs();
1543 fVerbStop = path.fPathRef->verbsMemBegin();
1544 fConicWeights = path.fPathRef->conicWeights() - 1; // begin one behind
1545 fLastPt.fX = fLastPt.fY = 0;
1546 fMoveTo.fX = fMoveTo.fY = 0;
1547 fForceClose = SkToU8(forceClose);
1548 fNeedClose = false;
1549 fSegmentState = kEmptyContour_SegmentState;
1550 }
1551
isClosedContour() const1552 bool SkPath::Iter::isClosedContour() const {
1553 if (fVerbs == NULL || fVerbs == fVerbStop) {
1554 return false;
1555 }
1556 if (fForceClose) {
1557 return true;
1558 }
1559
1560 const uint8_t* verbs = fVerbs;
1561 const uint8_t* stop = fVerbStop;
1562
1563 if (kMove_Verb == *(verbs - 1)) {
1564 verbs -= 1; // skip the initial moveto
1565 }
1566
1567 while (verbs > stop) {
1568 // verbs points one beyond the current verb, decrement first.
1569 unsigned v = *(--verbs);
1570 if (kMove_Verb == v) {
1571 break;
1572 }
1573 if (kClose_Verb == v) {
1574 return true;
1575 }
1576 }
1577 return false;
1578 }
1579
autoClose(SkPoint pts[2])1580 SkPath::Verb SkPath::Iter::autoClose(SkPoint pts[2]) {
1581 SkASSERT(pts);
1582 if (fLastPt != fMoveTo) {
1583 // A special case: if both points are NaN, SkPoint::operation== returns
1584 // false, but the iterator expects that they are treated as the same.
1585 // (consider SkPoint is a 2-dimension float point).
1586 if (SkScalarIsNaN(fLastPt.fX) || SkScalarIsNaN(fLastPt.fY) ||
1587 SkScalarIsNaN(fMoveTo.fX) || SkScalarIsNaN(fMoveTo.fY)) {
1588 return kClose_Verb;
1589 }
1590
1591 pts[0] = fLastPt;
1592 pts[1] = fMoveTo;
1593 fLastPt = fMoveTo;
1594 fCloseLine = true;
1595 return kLine_Verb;
1596 } else {
1597 pts[0] = fMoveTo;
1598 return kClose_Verb;
1599 }
1600 }
1601
cons_moveTo()1602 const SkPoint& SkPath::Iter::cons_moveTo() {
1603 if (fSegmentState == kAfterMove_SegmentState) {
1604 // Set the first return pt to the move pt
1605 fSegmentState = kAfterPrimitive_SegmentState;
1606 return fMoveTo;
1607 } else {
1608 SkASSERT(fSegmentState == kAfterPrimitive_SegmentState);
1609 // Set the first return pt to the last pt of the previous primitive.
1610 return fPts[-1];
1611 }
1612 }
1613
consumeDegenerateSegments()1614 void SkPath::Iter::consumeDegenerateSegments() {
1615 // We need to step over anything that will not move the current draw point
1616 // forward before the next move is seen
1617 const uint8_t* lastMoveVerb = 0;
1618 const SkPoint* lastMovePt = 0;
1619 const SkScalar* lastMoveWeight = NULL;
1620 SkPoint lastPt = fLastPt;
1621 while (fVerbs != fVerbStop) {
1622 unsigned verb = *(fVerbs - 1); // fVerbs is one beyond the current verb
1623 switch (verb) {
1624 case kMove_Verb:
1625 // Keep a record of this most recent move
1626 lastMoveVerb = fVerbs;
1627 lastMovePt = fPts;
1628 lastMoveWeight = fConicWeights;
1629 lastPt = fPts[0];
1630 fVerbs--;
1631 fPts++;
1632 break;
1633
1634 case kClose_Verb:
1635 // A close when we are in a segment is always valid except when it
1636 // follows a move which follows a segment.
1637 if (fSegmentState == kAfterPrimitive_SegmentState && !lastMoveVerb) {
1638 return;
1639 }
1640 // A close at any other time must be ignored
1641 fVerbs--;
1642 break;
1643
1644 case kLine_Verb:
1645 if (!IsLineDegenerate(lastPt, fPts[0])) {
1646 if (lastMoveVerb) {
1647 fVerbs = lastMoveVerb;
1648 fPts = lastMovePt;
1649 fConicWeights = lastMoveWeight;
1650 return;
1651 }
1652 return;
1653 }
1654 // Ignore this line and continue
1655 fVerbs--;
1656 fPts++;
1657 break;
1658
1659 case kConic_Verb:
1660 case kQuad_Verb:
1661 if (!IsQuadDegenerate(lastPt, fPts[0], fPts[1])) {
1662 if (lastMoveVerb) {
1663 fVerbs = lastMoveVerb;
1664 fPts = lastMovePt;
1665 fConicWeights = lastMoveWeight;
1666 return;
1667 }
1668 return;
1669 }
1670 // Ignore this line and continue
1671 fVerbs--;
1672 fPts += 2;
1673 fConicWeights += (kConic_Verb == verb);
1674 break;
1675
1676 case kCubic_Verb:
1677 if (!IsCubicDegenerate(lastPt, fPts[0], fPts[1], fPts[2])) {
1678 if (lastMoveVerb) {
1679 fVerbs = lastMoveVerb;
1680 fPts = lastMovePt;
1681 fConicWeights = lastMoveWeight;
1682 return;
1683 }
1684 return;
1685 }
1686 // Ignore this line and continue
1687 fVerbs--;
1688 fPts += 3;
1689 break;
1690
1691 default:
1692 SkDEBUGFAIL("Should never see kDone_Verb");
1693 }
1694 }
1695 }
1696
doNext(SkPoint ptsParam[4])1697 SkPath::Verb SkPath::Iter::doNext(SkPoint ptsParam[4]) {
1698 SkASSERT(ptsParam);
1699
1700 if (fVerbs == fVerbStop) {
1701 // Close the curve if requested and if there is some curve to close
1702 if (fNeedClose && fSegmentState == kAfterPrimitive_SegmentState) {
1703 if (kLine_Verb == this->autoClose(ptsParam)) {
1704 return kLine_Verb;
1705 }
1706 fNeedClose = false;
1707 return kClose_Verb;
1708 }
1709 return kDone_Verb;
1710 }
1711
1712 // fVerbs is one beyond the current verb, decrement first
1713 unsigned verb = *(--fVerbs);
1714 const SkPoint* SK_RESTRICT srcPts = fPts;
1715 SkPoint* SK_RESTRICT pts = ptsParam;
1716
1717 switch (verb) {
1718 case kMove_Verb:
1719 if (fNeedClose) {
1720 fVerbs++; // move back one verb
1721 verb = this->autoClose(pts);
1722 if (verb == kClose_Verb) {
1723 fNeedClose = false;
1724 }
1725 return (Verb)verb;
1726 }
1727 if (fVerbs == fVerbStop) { // might be a trailing moveto
1728 return kDone_Verb;
1729 }
1730 fMoveTo = *srcPts;
1731 pts[0] = *srcPts;
1732 srcPts += 1;
1733 fSegmentState = kAfterMove_SegmentState;
1734 fLastPt = fMoveTo;
1735 fNeedClose = fForceClose;
1736 break;
1737 case kLine_Verb:
1738 pts[0] = this->cons_moveTo();
1739 pts[1] = srcPts[0];
1740 fLastPt = srcPts[0];
1741 fCloseLine = false;
1742 srcPts += 1;
1743 break;
1744 case kConic_Verb:
1745 fConicWeights += 1;
1746 // fall-through
1747 case kQuad_Verb:
1748 pts[0] = this->cons_moveTo();
1749 memcpy(&pts[1], srcPts, 2 * sizeof(SkPoint));
1750 fLastPt = srcPts[1];
1751 srcPts += 2;
1752 break;
1753 case kCubic_Verb:
1754 pts[0] = this->cons_moveTo();
1755 memcpy(&pts[1], srcPts, 3 * sizeof(SkPoint));
1756 fLastPt = srcPts[2];
1757 srcPts += 3;
1758 break;
1759 case kClose_Verb:
1760 verb = this->autoClose(pts);
1761 if (verb == kLine_Verb) {
1762 fVerbs++; // move back one verb
1763 } else {
1764 fNeedClose = false;
1765 fSegmentState = kEmptyContour_SegmentState;
1766 }
1767 fLastPt = fMoveTo;
1768 break;
1769 }
1770 fPts = srcPts;
1771 return (Verb)verb;
1772 }
1773
1774 ///////////////////////////////////////////////////////////////////////////////
1775
RawIter()1776 SkPath::RawIter::RawIter() {
1777 #ifdef SK_DEBUG
1778 fPts = NULL;
1779 fConicWeights = NULL;
1780 fMoveTo.fX = fMoveTo.fY = 0;
1781 #endif
1782 // need to init enough to make next() harmlessly return kDone_Verb
1783 fVerbs = NULL;
1784 fVerbStop = NULL;
1785 }
1786
RawIter(const SkPath & path)1787 SkPath::RawIter::RawIter(const SkPath& path) {
1788 this->setPath(path);
1789 }
1790
setPath(const SkPath & path)1791 void SkPath::RawIter::setPath(const SkPath& path) {
1792 fPts = path.fPathRef->points();
1793 fVerbs = path.fPathRef->verbs();
1794 fVerbStop = path.fPathRef->verbsMemBegin();
1795 fConicWeights = path.fPathRef->conicWeights() - 1; // begin one behind
1796 fMoveTo.fX = fMoveTo.fY = 0;
1797 }
1798
next(SkPoint pts[4])1799 SkPath::Verb SkPath::RawIter::next(SkPoint pts[4]) {
1800 SkASSERT(pts);
1801 if (fVerbs == fVerbStop) {
1802 return kDone_Verb;
1803 }
1804
1805 // fVerbs points one beyond next verb so decrement first.
1806 unsigned verb = *(--fVerbs);
1807 const SkPoint* srcPts = fPts;
1808
1809 switch (verb) {
1810 case kMove_Verb:
1811 fMoveTo = pts[0] = srcPts[0];
1812 srcPts += 1;
1813 break;
1814 case kLine_Verb:
1815 pts[0] = srcPts[-1];
1816 pts[1] = srcPts[0];
1817 srcPts += 1;
1818 break;
1819 case kConic_Verb:
1820 fConicWeights += 1;
1821 // fall-through
1822 case kQuad_Verb:
1823 pts[0] = srcPts[-1];
1824 pts[1] = srcPts[0];
1825 pts[2] = srcPts[1];
1826 srcPts += 2;
1827 break;
1828 case kCubic_Verb:
1829 pts[0] = srcPts[-1];
1830 pts[1] = srcPts[0];
1831 pts[2] = srcPts[1];
1832 pts[3] = srcPts[2];
1833 srcPts += 3;
1834 break;
1835 case kClose_Verb:
1836 pts[0] = fMoveTo;
1837 break;
1838 }
1839 fPts = srcPts;
1840 return (Verb)verb;
1841 }
1842
1843 ///////////////////////////////////////////////////////////////////////////////
1844
1845 /*
1846 Format in compressed buffer: [ptCount, verbCount, pts[], verbs[]]
1847 */
1848
writeToMemory(void * storage) const1849 size_t SkPath::writeToMemory(void* storage) const {
1850 SkDEBUGCODE(this->validate();)
1851
1852 if (NULL == storage) {
1853 const int byteCount = sizeof(int32_t) + fPathRef->writeSize();
1854 return SkAlign4(byteCount);
1855 }
1856
1857 SkWBuffer buffer(storage);
1858
1859 int32_t packed = (fConvexity << kConvexity_SerializationShift) |
1860 (fFillType << kFillType_SerializationShift) |
1861 (fDirection << kDirection_SerializationShift) |
1862 (fIsVolatile << kIsVolatile_SerializationShift);
1863
1864 buffer.write32(packed);
1865
1866 fPathRef->writeToBuffer(&buffer);
1867
1868 buffer.padToAlign4();
1869 return buffer.pos();
1870 }
1871
readFromMemory(const void * storage,size_t length)1872 size_t SkPath::readFromMemory(const void* storage, size_t length) {
1873 SkRBufferWithSizeCheck buffer(storage, length);
1874
1875 int32_t packed;
1876 if (!buffer.readS32(&packed)) {
1877 return 0;
1878 }
1879
1880 fConvexity = (packed >> kConvexity_SerializationShift) & 0xFF;
1881 fFillType = (packed >> kFillType_SerializationShift) & 0xFF;
1882 fDirection = (packed >> kDirection_SerializationShift) & 0x3;
1883 fIsVolatile = (packed >> kIsVolatile_SerializationShift) & 0x1;
1884 SkPathRef* pathRef = SkPathRef::CreateFromBuffer(&buffer);
1885
1886 size_t sizeRead = 0;
1887 if (buffer.isValid()) {
1888 fPathRef.reset(pathRef);
1889 SkDEBUGCODE(this->validate();)
1890 buffer.skipToAlign4();
1891 sizeRead = buffer.pos();
1892 } else if (pathRef) {
1893 // If the buffer is not valid, pathRef should be NULL
1894 sk_throw();
1895 }
1896 return sizeRead;
1897 }
1898
1899 ///////////////////////////////////////////////////////////////////////////////
1900
1901 #include "SkStringUtils.h"
1902 #include "SkStream.h"
1903
append_params(SkString * str,const char label[],const SkPoint pts[],int count,SkScalarAsStringType strType,SkScalar conicWeight=-1)1904 static void append_params(SkString* str, const char label[], const SkPoint pts[],
1905 int count, SkScalarAsStringType strType, SkScalar conicWeight = -1) {
1906 str->append(label);
1907 str->append("(");
1908
1909 const SkScalar* values = &pts[0].fX;
1910 count *= 2;
1911
1912 for (int i = 0; i < count; ++i) {
1913 SkAppendScalar(str, values[i], strType);
1914 if (i < count - 1) {
1915 str->append(", ");
1916 }
1917 }
1918 if (conicWeight >= 0) {
1919 str->append(", ");
1920 SkAppendScalar(str, conicWeight, strType);
1921 }
1922 str->append(");");
1923 if (kHex_SkScalarAsStringType == strType) {
1924 str->append(" // ");
1925 for (int i = 0; i < count; ++i) {
1926 SkAppendScalarDec(str, values[i]);
1927 if (i < count - 1) {
1928 str->append(", ");
1929 }
1930 }
1931 if (conicWeight >= 0) {
1932 str->append(", ");
1933 SkAppendScalarDec(str, conicWeight);
1934 }
1935 }
1936 str->append("\n");
1937 }
1938
dump(SkWStream * wStream,bool forceClose,bool dumpAsHex) const1939 void SkPath::dump(SkWStream* wStream, bool forceClose, bool dumpAsHex) const {
1940 SkScalarAsStringType asType = dumpAsHex ? kHex_SkScalarAsStringType : kDec_SkScalarAsStringType;
1941 Iter iter(*this, forceClose);
1942 SkPoint pts[4];
1943 Verb verb;
1944
1945 if (!wStream) {
1946 SkDebugf("path: forceClose=%s\n", forceClose ? "true" : "false");
1947 }
1948 SkString builder;
1949
1950 while ((verb = iter.next(pts, false)) != kDone_Verb) {
1951 switch (verb) {
1952 case kMove_Verb:
1953 append_params(&builder, "path.moveTo", &pts[0], 1, asType);
1954 break;
1955 case kLine_Verb:
1956 append_params(&builder, "path.lineTo", &pts[1], 1, asType);
1957 break;
1958 case kQuad_Verb:
1959 append_params(&builder, "path.quadTo", &pts[1], 2, asType);
1960 break;
1961 case kConic_Verb:
1962 append_params(&builder, "path.conicTo", &pts[1], 2, asType, iter.conicWeight());
1963 break;
1964 case kCubic_Verb:
1965 append_params(&builder, "path.cubicTo", &pts[1], 3, asType);
1966 break;
1967 case kClose_Verb:
1968 builder.append("path.close();\n");
1969 break;
1970 default:
1971 SkDebugf(" path: UNKNOWN VERB %d, aborting dump...\n", verb);
1972 verb = kDone_Verb; // stop the loop
1973 break;
1974 }
1975 if (!wStream && builder.size()) {
1976 SkDebugf("%s", builder.c_str());
1977 builder.reset();
1978 }
1979 }
1980 if (wStream) {
1981 wStream->writeText(builder.c_str());
1982 }
1983 }
1984
dump() const1985 void SkPath::dump() const {
1986 this->dump(NULL, false, false);
1987 }
1988
dumpHex() const1989 void SkPath::dumpHex() const {
1990 this->dump(NULL, false, true);
1991 }
1992
1993 #ifdef SK_DEBUG
validate() const1994 void SkPath::validate() const {
1995 SkASSERT((fFillType & ~3) == 0);
1996
1997 #ifdef SK_DEBUG_PATH
1998 if (!fBoundsIsDirty) {
1999 SkRect bounds;
2000
2001 bool isFinite = compute_pt_bounds(&bounds, *fPathRef.get());
2002 SkASSERT(SkToBool(fIsFinite) == isFinite);
2003
2004 if (fPathRef->countPoints() <= 1) {
2005 // if we're empty, fBounds may be empty but translated, so we can't
2006 // necessarily compare to bounds directly
2007 // try path.addOval(2, 2, 2, 2) which is empty, but the bounds will
2008 // be [2, 2, 2, 2]
2009 SkASSERT(bounds.isEmpty());
2010 SkASSERT(fBounds.isEmpty());
2011 } else {
2012 if (bounds.isEmpty()) {
2013 SkASSERT(fBounds.isEmpty());
2014 } else {
2015 if (!fBounds.isEmpty()) {
2016 SkASSERT(fBounds.contains(bounds));
2017 }
2018 }
2019 }
2020 }
2021 #endif // SK_DEBUG_PATH
2022 }
2023 #endif // SK_DEBUG
2024
2025 ///////////////////////////////////////////////////////////////////////////////
2026
sign(SkScalar x)2027 static int sign(SkScalar x) { return x < 0; }
2028 #define kValueNeverReturnedBySign 2
2029
2030 enum DirChange {
2031 kLeft_DirChange,
2032 kRight_DirChange,
2033 kStraight_DirChange,
2034 kBackwards_DirChange,
2035
2036 kInvalid_DirChange
2037 };
2038
2039
almost_equal(SkScalar compA,SkScalar compB)2040 static bool almost_equal(SkScalar compA, SkScalar compB) {
2041 // The error epsilon was empirically derived; worse case round rects
2042 // with a mid point outset by 2x float epsilon in tests had an error
2043 // of 12.
2044 const int epsilon = 16;
2045 if (!SkScalarIsFinite(compA) || !SkScalarIsFinite(compB)) {
2046 return false;
2047 }
2048 // no need to check for small numbers because SkPath::Iter has removed degenerate values
2049 int aBits = SkFloatAs2sCompliment(compA);
2050 int bBits = SkFloatAs2sCompliment(compB);
2051 return aBits < bBits + epsilon && bBits < aBits + epsilon;
2052 }
2053
approximately_zero_when_compared_to(double x,double y)2054 static bool approximately_zero_when_compared_to(double x, double y) {
2055 return x == 0 || fabs(x) < fabs(y * FLT_EPSILON);
2056 }
2057
2058
2059 // only valid for a single contour
2060 struct Convexicator {
ConvexicatorConvexicator2061 Convexicator()
2062 : fPtCount(0)
2063 , fConvexity(SkPath::kConvex_Convexity)
2064 , fDirection(SkPath::kUnknown_Direction)
2065 , fIsFinite(true)
2066 , fIsCurve(false) {
2067 fExpectedDir = kInvalid_DirChange;
2068 // warnings
2069 fLastPt.set(0, 0);
2070 fCurrPt.set(0, 0);
2071 fLastVec.set(0, 0);
2072 fFirstVec.set(0, 0);
2073
2074 fDx = fDy = 0;
2075 fSx = fSy = kValueNeverReturnedBySign;
2076 }
2077
getConvexityConvexicator2078 SkPath::Convexity getConvexity() const { return fConvexity; }
2079
2080 /** The direction returned is only valid if the path is determined convex */
getDirectionConvexicator2081 SkPath::Direction getDirection() const { return fDirection; }
2082
addPtConvexicator2083 void addPt(const SkPoint& pt) {
2084 if (SkPath::kConcave_Convexity == fConvexity || !fIsFinite) {
2085 return;
2086 }
2087
2088 if (0 == fPtCount) {
2089 fCurrPt = pt;
2090 ++fPtCount;
2091 } else {
2092 SkVector vec = pt - fCurrPt;
2093 SkScalar lengthSqd = vec.lengthSqd();
2094 if (!SkScalarIsFinite(lengthSqd)) {
2095 fIsFinite = false;
2096 } else if (!SkScalarNearlyZero(lengthSqd, SK_ScalarNearlyZero*SK_ScalarNearlyZero)) {
2097 fPriorPt = fLastPt;
2098 fLastPt = fCurrPt;
2099 fCurrPt = pt;
2100 if (++fPtCount == 2) {
2101 fFirstVec = fLastVec = vec;
2102 } else {
2103 SkASSERT(fPtCount > 2);
2104 this->addVec(vec);
2105 }
2106
2107 int sx = sign(vec.fX);
2108 int sy = sign(vec.fY);
2109 fDx += (sx != fSx);
2110 fDy += (sy != fSy);
2111 fSx = sx;
2112 fSy = sy;
2113
2114 if (fDx > 3 || fDy > 3) {
2115 fConvexity = SkPath::kConcave_Convexity;
2116 }
2117 }
2118 }
2119 }
2120
closeConvexicator2121 void close() {
2122 if (fPtCount > 2) {
2123 this->addVec(fFirstVec);
2124 }
2125 }
2126
directionChangeConvexicator2127 DirChange directionChange(const SkVector& curVec) {
2128 SkScalar cross = SkPoint::CrossProduct(fLastVec, curVec);
2129
2130 SkScalar smallest = SkTMin(fCurrPt.fX, SkTMin(fCurrPt.fY, SkTMin(fLastPt.fX, fLastPt.fY)));
2131 SkScalar largest = SkTMax(fCurrPt.fX, SkTMax(fCurrPt.fY, SkTMax(fLastPt.fX, fLastPt.fY)));
2132 largest = SkTMax(largest, -smallest);
2133
2134 if (!almost_equal(largest, largest + cross)) {
2135 int sign = SkScalarSignAsInt(cross);
2136 if (sign) {
2137 return (1 == sign) ? kRight_DirChange : kLeft_DirChange;
2138 }
2139 }
2140
2141 if (cross) {
2142 double dLastVecX = SkScalarToDouble(fLastPt.fX) - SkScalarToDouble(fPriorPt.fX);
2143 double dLastVecY = SkScalarToDouble(fLastPt.fY) - SkScalarToDouble(fPriorPt.fY);
2144 double dCurrVecX = SkScalarToDouble(fCurrPt.fX) - SkScalarToDouble(fLastPt.fX);
2145 double dCurrVecY = SkScalarToDouble(fCurrPt.fY) - SkScalarToDouble(fLastPt.fY);
2146 double dCross = dLastVecX * dCurrVecY - dLastVecY * dCurrVecX;
2147 if (!approximately_zero_when_compared_to(dCross, SkScalarToDouble(largest))) {
2148 int sign = SkScalarSignAsInt(SkDoubleToScalar(dCross));
2149 if (sign) {
2150 return (1 == sign) ? kRight_DirChange : kLeft_DirChange;
2151 }
2152 }
2153 }
2154
2155 if (!SkScalarNearlyZero(fLastVec.lengthSqd(), SK_ScalarNearlyZero*SK_ScalarNearlyZero) &&
2156 !SkScalarNearlyZero(curVec.lengthSqd(), SK_ScalarNearlyZero*SK_ScalarNearlyZero) &&
2157 fLastVec.dot(curVec) < 0.0f) {
2158 return kBackwards_DirChange;
2159 }
2160
2161 return kStraight_DirChange;
2162 }
2163
2164
isFiniteConvexicator2165 bool isFinite() const {
2166 return fIsFinite;
2167 }
2168
setCurveConvexicator2169 void setCurve(bool isCurve) {
2170 fIsCurve = isCurve;
2171 }
2172
2173 private:
addVecConvexicator2174 void addVec(const SkVector& vec) {
2175 SkASSERT(vec.fX || vec.fY);
2176 DirChange dir = this->directionChange(vec);
2177 switch (dir) {
2178 case kLeft_DirChange: // fall through
2179 case kRight_DirChange:
2180 if (kInvalid_DirChange == fExpectedDir) {
2181 fExpectedDir = dir;
2182 fDirection = (kRight_DirChange == dir) ? SkPath::kCW_Direction
2183 : SkPath::kCCW_Direction;
2184 } else if (dir != fExpectedDir) {
2185 fConvexity = SkPath::kConcave_Convexity;
2186 fDirection = SkPath::kUnknown_Direction;
2187 }
2188 fLastVec = vec;
2189 break;
2190 case kStraight_DirChange:
2191 break;
2192 case kBackwards_DirChange:
2193 if (fIsCurve) {
2194 fConvexity = SkPath::kConcave_Convexity;
2195 fDirection = SkPath::kUnknown_Direction;
2196 }
2197 fLastVec = vec;
2198 break;
2199 case kInvalid_DirChange:
2200 SkFAIL("Use of invalid direction change flag");
2201 break;
2202 }
2203 }
2204
2205 SkPoint fPriorPt;
2206 SkPoint fLastPt;
2207 SkPoint fCurrPt;
2208 // fLastVec does not necessarily start at fLastPt. We only advance it when the cross product
2209 // value with the current vec is deemed to be of a significant value.
2210 SkVector fLastVec, fFirstVec;
2211 int fPtCount; // non-degenerate points
2212 DirChange fExpectedDir;
2213 SkPath::Convexity fConvexity;
2214 SkPath::Direction fDirection;
2215 int fDx, fDy, fSx, fSy;
2216 bool fIsFinite;
2217 bool fIsCurve;
2218 };
2219
internalGetConvexity() const2220 SkPath::Convexity SkPath::internalGetConvexity() const {
2221 SkASSERT(kUnknown_Convexity == fConvexity);
2222 SkPoint pts[4];
2223 SkPath::Verb verb;
2224 SkPath::Iter iter(*this, true);
2225
2226 int contourCount = 0;
2227 int count;
2228 Convexicator state;
2229
2230 if (!isFinite()) {
2231 return kUnknown_Convexity;
2232 }
2233 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
2234 switch (verb) {
2235 case kMove_Verb:
2236 if (++contourCount > 1) {
2237 fConvexity = kConcave_Convexity;
2238 return kConcave_Convexity;
2239 }
2240 pts[1] = pts[0];
2241 // fall through
2242 case kLine_Verb:
2243 count = 1;
2244 state.setCurve(false);
2245 break;
2246 case kQuad_Verb:
2247 // fall through
2248 case kConic_Verb:
2249 // fall through
2250 case kCubic_Verb:
2251 count = 2 + (kCubic_Verb == verb);
2252 // As an additional enhancement, this could set curve true only
2253 // if the curve is nonlinear
2254 state.setCurve(true);
2255 break;
2256 case kClose_Verb:
2257 state.setCurve(false);
2258 state.close();
2259 count = 0;
2260 break;
2261 default:
2262 SkDEBUGFAIL("bad verb");
2263 fConvexity = kConcave_Convexity;
2264 return kConcave_Convexity;
2265 }
2266
2267 for (int i = 1; i <= count; i++) {
2268 state.addPt(pts[i]);
2269 }
2270 // early exit
2271 if (!state.isFinite()) {
2272 return kUnknown_Convexity;
2273 }
2274 if (kConcave_Convexity == state.getConvexity()) {
2275 fConvexity = kConcave_Convexity;
2276 return kConcave_Convexity;
2277 }
2278 }
2279 fConvexity = state.getConvexity();
2280 if (kConvex_Convexity == fConvexity && kUnknown_Direction == fDirection) {
2281 fDirection = state.getDirection();
2282 }
2283 return static_cast<Convexity>(fConvexity);
2284 }
2285
2286 ///////////////////////////////////////////////////////////////////////////////
2287
2288 class ContourIter {
2289 public:
2290 ContourIter(const SkPathRef& pathRef);
2291
done() const2292 bool done() const { return fDone; }
2293 // if !done() then these may be called
count() const2294 int count() const { return fCurrPtCount; }
pts() const2295 const SkPoint* pts() const { return fCurrPt; }
2296 void next();
2297
2298 private:
2299 int fCurrPtCount;
2300 const SkPoint* fCurrPt;
2301 const uint8_t* fCurrVerb;
2302 const uint8_t* fStopVerbs;
2303 const SkScalar* fCurrConicWeight;
2304 bool fDone;
2305 SkDEBUGCODE(int fContourCounter;)
2306 };
2307
ContourIter(const SkPathRef & pathRef)2308 ContourIter::ContourIter(const SkPathRef& pathRef) {
2309 fStopVerbs = pathRef.verbsMemBegin();
2310 fDone = false;
2311 fCurrPt = pathRef.points();
2312 fCurrVerb = pathRef.verbs();
2313 fCurrConicWeight = pathRef.conicWeights();
2314 fCurrPtCount = 0;
2315 SkDEBUGCODE(fContourCounter = 0;)
2316 this->next();
2317 }
2318
next()2319 void ContourIter::next() {
2320 if (fCurrVerb <= fStopVerbs) {
2321 fDone = true;
2322 }
2323 if (fDone) {
2324 return;
2325 }
2326
2327 // skip pts of prev contour
2328 fCurrPt += fCurrPtCount;
2329
2330 SkASSERT(SkPath::kMove_Verb == fCurrVerb[~0]);
2331 int ptCount = 1; // moveTo
2332 const uint8_t* verbs = fCurrVerb;
2333
2334 for (--verbs; verbs > fStopVerbs; --verbs) {
2335 switch (verbs[~0]) {
2336 case SkPath::kMove_Verb:
2337 goto CONTOUR_END;
2338 case SkPath::kLine_Verb:
2339 ptCount += 1;
2340 break;
2341 case SkPath::kConic_Verb:
2342 fCurrConicWeight += 1;
2343 // fall-through
2344 case SkPath::kQuad_Verb:
2345 ptCount += 2;
2346 break;
2347 case SkPath::kCubic_Verb:
2348 ptCount += 3;
2349 break;
2350 case SkPath::kClose_Verb:
2351 break;
2352 default:
2353 SkDEBUGFAIL("unexpected verb");
2354 break;
2355 }
2356 }
2357 CONTOUR_END:
2358 fCurrPtCount = ptCount;
2359 fCurrVerb = verbs;
2360 SkDEBUGCODE(++fContourCounter;)
2361 }
2362
2363 // returns cross product of (p1 - p0) and (p2 - p0)
cross_prod(const SkPoint & p0,const SkPoint & p1,const SkPoint & p2)2364 static SkScalar cross_prod(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) {
2365 SkScalar cross = SkPoint::CrossProduct(p1 - p0, p2 - p0);
2366 // We may get 0 when the above subtracts underflow. We expect this to be
2367 // very rare and lazily promote to double.
2368 if (0 == cross) {
2369 double p0x = SkScalarToDouble(p0.fX);
2370 double p0y = SkScalarToDouble(p0.fY);
2371
2372 double p1x = SkScalarToDouble(p1.fX);
2373 double p1y = SkScalarToDouble(p1.fY);
2374
2375 double p2x = SkScalarToDouble(p2.fX);
2376 double p2y = SkScalarToDouble(p2.fY);
2377
2378 cross = SkDoubleToScalar((p1x - p0x) * (p2y - p0y) -
2379 (p1y - p0y) * (p2x - p0x));
2380
2381 }
2382 return cross;
2383 }
2384
2385 // Returns the first pt with the maximum Y coordinate
find_max_y(const SkPoint pts[],int count)2386 static int find_max_y(const SkPoint pts[], int count) {
2387 SkASSERT(count > 0);
2388 SkScalar max = pts[0].fY;
2389 int firstIndex = 0;
2390 for (int i = 1; i < count; ++i) {
2391 SkScalar y = pts[i].fY;
2392 if (y > max) {
2393 max = y;
2394 firstIndex = i;
2395 }
2396 }
2397 return firstIndex;
2398 }
2399
find_diff_pt(const SkPoint pts[],int index,int n,int inc)2400 static int find_diff_pt(const SkPoint pts[], int index, int n, int inc) {
2401 int i = index;
2402 for (;;) {
2403 i = (i + inc) % n;
2404 if (i == index) { // we wrapped around, so abort
2405 break;
2406 }
2407 if (pts[index] != pts[i]) { // found a different point, success!
2408 break;
2409 }
2410 }
2411 return i;
2412 }
2413
2414 /**
2415 * Starting at index, and moving forward (incrementing), find the xmin and
2416 * xmax of the contiguous points that have the same Y.
2417 */
find_min_max_x_at_y(const SkPoint pts[],int index,int n,int * maxIndexPtr)2418 static int find_min_max_x_at_y(const SkPoint pts[], int index, int n,
2419 int* maxIndexPtr) {
2420 const SkScalar y = pts[index].fY;
2421 SkScalar min = pts[index].fX;
2422 SkScalar max = min;
2423 int minIndex = index;
2424 int maxIndex = index;
2425 for (int i = index + 1; i < n; ++i) {
2426 if (pts[i].fY != y) {
2427 break;
2428 }
2429 SkScalar x = pts[i].fX;
2430 if (x < min) {
2431 min = x;
2432 minIndex = i;
2433 } else if (x > max) {
2434 max = x;
2435 maxIndex = i;
2436 }
2437 }
2438 *maxIndexPtr = maxIndex;
2439 return minIndex;
2440 }
2441
crossToDir(SkScalar cross,SkPath::Direction * dir)2442 static void crossToDir(SkScalar cross, SkPath::Direction* dir) {
2443 *dir = cross > 0 ? SkPath::kCW_Direction : SkPath::kCCW_Direction;
2444 }
2445
2446 /*
2447 * We loop through all contours, and keep the computed cross-product of the
2448 * contour that contained the global y-max. If we just look at the first
2449 * contour, we may find one that is wound the opposite way (correctly) since
2450 * it is the interior of a hole (e.g. 'o'). Thus we must find the contour
2451 * that is outer most (or at least has the global y-max) before we can consider
2452 * its cross product.
2453 */
cheapComputeDirection(Direction * dir) const2454 bool SkPath::cheapComputeDirection(Direction* dir) const {
2455 if (kUnknown_Direction != fDirection) {
2456 *dir = static_cast<Direction>(fDirection);
2457 return true;
2458 }
2459
2460 // don't want to pay the cost for computing this if it
2461 // is unknown, so we don't call isConvex()
2462 if (kConvex_Convexity == this->getConvexityOrUnknown()) {
2463 SkASSERT(kUnknown_Direction == fDirection);
2464 *dir = static_cast<Direction>(fDirection);
2465 return false;
2466 }
2467
2468 ContourIter iter(*fPathRef.get());
2469
2470 // initialize with our logical y-min
2471 SkScalar ymax = this->getBounds().fTop;
2472 SkScalar ymaxCross = 0;
2473
2474 for (; !iter.done(); iter.next()) {
2475 int n = iter.count();
2476 if (n < 3) {
2477 continue;
2478 }
2479
2480 const SkPoint* pts = iter.pts();
2481 SkScalar cross = 0;
2482 int index = find_max_y(pts, n);
2483 if (pts[index].fY < ymax) {
2484 continue;
2485 }
2486
2487 // If there is more than 1 distinct point at the y-max, we take the
2488 // x-min and x-max of them and just subtract to compute the dir.
2489 if (pts[(index + 1) % n].fY == pts[index].fY) {
2490 int maxIndex;
2491 int minIndex = find_min_max_x_at_y(pts, index, n, &maxIndex);
2492 if (minIndex == maxIndex) {
2493 goto TRY_CROSSPROD;
2494 }
2495 SkASSERT(pts[minIndex].fY == pts[index].fY);
2496 SkASSERT(pts[maxIndex].fY == pts[index].fY);
2497 SkASSERT(pts[minIndex].fX <= pts[maxIndex].fX);
2498 // we just subtract the indices, and let that auto-convert to
2499 // SkScalar, since we just want - or + to signal the direction.
2500 cross = minIndex - maxIndex;
2501 } else {
2502 TRY_CROSSPROD:
2503 // Find a next and prev index to use for the cross-product test,
2504 // but we try to find pts that form non-zero vectors from pts[index]
2505 //
2506 // Its possible that we can't find two non-degenerate vectors, so
2507 // we have to guard our search (e.g. all the pts could be in the
2508 // same place).
2509
2510 // we pass n - 1 instead of -1 so we don't foul up % operator by
2511 // passing it a negative LH argument.
2512 int prev = find_diff_pt(pts, index, n, n - 1);
2513 if (prev == index) {
2514 // completely degenerate, skip to next contour
2515 continue;
2516 }
2517 int next = find_diff_pt(pts, index, n, 1);
2518 SkASSERT(next != index);
2519 cross = cross_prod(pts[prev], pts[index], pts[next]);
2520 // if we get a zero and the points are horizontal, then we look at the spread in
2521 // x-direction. We really should continue to walk away from the degeneracy until
2522 // there is a divergence.
2523 if (0 == cross && pts[prev].fY == pts[index].fY && pts[next].fY == pts[index].fY) {
2524 // construct the subtract so we get the correct Direction below
2525 cross = pts[index].fX - pts[next].fX;
2526 }
2527 }
2528
2529 if (cross) {
2530 // record our best guess so far
2531 ymax = pts[index].fY;
2532 ymaxCross = cross;
2533 }
2534 }
2535 if (ymaxCross) {
2536 crossToDir(ymaxCross, dir);
2537 fDirection = *dir;
2538 return true;
2539 } else {
2540 return false;
2541 }
2542 }
2543
2544 ///////////////////////////////////////////////////////////////////////////////
2545
eval_cubic_coeff(SkScalar A,SkScalar B,SkScalar C,SkScalar D,SkScalar t)2546 static SkScalar eval_cubic_coeff(SkScalar A, SkScalar B, SkScalar C,
2547 SkScalar D, SkScalar t) {
2548 return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D);
2549 }
2550
eval_cubic_pts(SkScalar c0,SkScalar c1,SkScalar c2,SkScalar c3,SkScalar t)2551 static SkScalar eval_cubic_pts(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3,
2552 SkScalar t) {
2553 SkScalar A = c3 + 3*(c1 - c2) - c0;
2554 SkScalar B = 3*(c2 - c1 - c1 + c0);
2555 SkScalar C = 3*(c1 - c0);
2556 SkScalar D = c0;
2557 return eval_cubic_coeff(A, B, C, D, t);
2558 }
2559
2560 /* Given 4 cubic points (either Xs or Ys), and a target X or Y, compute the
2561 t value such that cubic(t) = target
2562 */
chopMonoCubicAt(SkScalar c0,SkScalar c1,SkScalar c2,SkScalar c3,SkScalar target,SkScalar * t)2563 static void chopMonoCubicAt(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3,
2564 SkScalar target, SkScalar* t) {
2565 // SkASSERT(c0 <= c1 && c1 <= c2 && c2 <= c3);
2566 SkASSERT(c0 < target && target < c3);
2567
2568 SkScalar D = c0 - target;
2569 SkScalar A = c3 + 3*(c1 - c2) - c0;
2570 SkScalar B = 3*(c2 - c1 - c1 + c0);
2571 SkScalar C = 3*(c1 - c0);
2572
2573 const SkScalar TOLERANCE = SK_Scalar1 / 4096;
2574 SkScalar minT = 0;
2575 SkScalar maxT = SK_Scalar1;
2576 SkScalar mid;
2577 int i;
2578 for (i = 0; i < 16; i++) {
2579 mid = SkScalarAve(minT, maxT);
2580 SkScalar delta = eval_cubic_coeff(A, B, C, D, mid);
2581 if (delta < 0) {
2582 minT = mid;
2583 delta = -delta;
2584 } else {
2585 maxT = mid;
2586 }
2587 if (delta < TOLERANCE) {
2588 break;
2589 }
2590 }
2591 *t = mid;
2592 }
2593
find_minmax(const SkPoint pts[],SkScalar * minPtr,SkScalar * maxPtr)2594 template <size_t N> static void find_minmax(const SkPoint pts[],
2595 SkScalar* minPtr, SkScalar* maxPtr) {
2596 SkScalar min, max;
2597 min = max = pts[0].fX;
2598 for (size_t i = 1; i < N; ++i) {
2599 min = SkMinScalar(min, pts[i].fX);
2600 max = SkMaxScalar(max, pts[i].fX);
2601 }
2602 *minPtr = min;
2603 *maxPtr = max;
2604 }
2605
winding_mono_cubic(const SkPoint pts[],SkScalar x,SkScalar y)2606 static int winding_mono_cubic(const SkPoint pts[], SkScalar x, SkScalar y) {
2607 SkPoint storage[4];
2608
2609 int dir = 1;
2610 if (pts[0].fY > pts[3].fY) {
2611 storage[0] = pts[3];
2612 storage[1] = pts[2];
2613 storage[2] = pts[1];
2614 storage[3] = pts[0];
2615 pts = storage;
2616 dir = -1;
2617 }
2618 if (y < pts[0].fY || y >= pts[3].fY) {
2619 return 0;
2620 }
2621
2622 // quickreject or quickaccept
2623 SkScalar min, max;
2624 find_minmax<4>(pts, &min, &max);
2625 if (x < min) {
2626 return 0;
2627 }
2628 if (x > max) {
2629 return dir;
2630 }
2631
2632 // compute the actual x(t) value
2633 SkScalar t;
2634 chopMonoCubicAt(pts[0].fY, pts[1].fY, pts[2].fY, pts[3].fY, y, &t);
2635 SkScalar xt = eval_cubic_pts(pts[0].fX, pts[1].fX, pts[2].fX, pts[3].fX, t);
2636 return xt < x ? dir : 0;
2637 }
2638
winding_cubic(const SkPoint pts[],SkScalar x,SkScalar y)2639 static int winding_cubic(const SkPoint pts[], SkScalar x, SkScalar y) {
2640 SkPoint dst[10];
2641 int n = SkChopCubicAtYExtrema(pts, dst);
2642 int w = 0;
2643 for (int i = 0; i <= n; ++i) {
2644 w += winding_mono_cubic(&dst[i * 3], x, y);
2645 }
2646 return w;
2647 }
2648
winding_mono_quad(const SkPoint pts[],SkScalar x,SkScalar y)2649 static int winding_mono_quad(const SkPoint pts[], SkScalar x, SkScalar y) {
2650 SkScalar y0 = pts[0].fY;
2651 SkScalar y2 = pts[2].fY;
2652
2653 int dir = 1;
2654 if (y0 > y2) {
2655 SkTSwap(y0, y2);
2656 dir = -1;
2657 }
2658 if (y < y0 || y >= y2) {
2659 return 0;
2660 }
2661
2662 // bounds check on X (not required. is it faster?)
2663 #if 0
2664 if (pts[0].fX > x && pts[1].fX > x && pts[2].fX > x) {
2665 return 0;
2666 }
2667 #endif
2668
2669 SkScalar roots[2];
2670 int n = SkFindUnitQuadRoots(pts[0].fY - 2 * pts[1].fY + pts[2].fY,
2671 2 * (pts[1].fY - pts[0].fY),
2672 pts[0].fY - y,
2673 roots);
2674 SkASSERT(n <= 1);
2675 SkScalar xt;
2676 if (0 == n) {
2677 SkScalar mid = SkScalarAve(y0, y2);
2678 // Need [0] and [2] if dir == 1
2679 // and [2] and [0] if dir == -1
2680 xt = y < mid ? pts[1 - dir].fX : pts[dir - 1].fX;
2681 } else {
2682 SkScalar t = roots[0];
2683 SkScalar C = pts[0].fX;
2684 SkScalar A = pts[2].fX - 2 * pts[1].fX + C;
2685 SkScalar B = 2 * (pts[1].fX - C);
2686 xt = SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C);
2687 }
2688 return xt < x ? dir : 0;
2689 }
2690
is_mono_quad(SkScalar y0,SkScalar y1,SkScalar y2)2691 static bool is_mono_quad(SkScalar y0, SkScalar y1, SkScalar y2) {
2692 // return SkScalarSignAsInt(y0 - y1) + SkScalarSignAsInt(y1 - y2) != 0;
2693 if (y0 == y1) {
2694 return true;
2695 }
2696 if (y0 < y1) {
2697 return y1 <= y2;
2698 } else {
2699 return y1 >= y2;
2700 }
2701 }
2702
winding_quad(const SkPoint pts[],SkScalar x,SkScalar y)2703 static int winding_quad(const SkPoint pts[], SkScalar x, SkScalar y) {
2704 SkPoint dst[5];
2705 int n = 0;
2706
2707 if (!is_mono_quad(pts[0].fY, pts[1].fY, pts[2].fY)) {
2708 n = SkChopQuadAtYExtrema(pts, dst);
2709 pts = dst;
2710 }
2711 int w = winding_mono_quad(pts, x, y);
2712 if (n > 0) {
2713 w += winding_mono_quad(&pts[2], x, y);
2714 }
2715 return w;
2716 }
2717
winding_line(const SkPoint pts[],SkScalar x,SkScalar y)2718 static int winding_line(const SkPoint pts[], SkScalar x, SkScalar y) {
2719 SkScalar x0 = pts[0].fX;
2720 SkScalar y0 = pts[0].fY;
2721 SkScalar x1 = pts[1].fX;
2722 SkScalar y1 = pts[1].fY;
2723
2724 SkScalar dy = y1 - y0;
2725
2726 int dir = 1;
2727 if (y0 > y1) {
2728 SkTSwap(y0, y1);
2729 dir = -1;
2730 }
2731 if (y < y0 || y >= y1) {
2732 return 0;
2733 }
2734
2735 SkScalar cross = SkScalarMul(x1 - x0, y - pts[0].fY) -
2736 SkScalarMul(dy, x - pts[0].fX);
2737
2738 if (SkScalarSignAsInt(cross) == dir) {
2739 dir = 0;
2740 }
2741 return dir;
2742 }
2743
contains_inclusive(const SkRect & r,SkScalar x,SkScalar y)2744 static bool contains_inclusive(const SkRect& r, SkScalar x, SkScalar y) {
2745 return r.fLeft <= x && x <= r.fRight && r.fTop <= y && y <= r.fBottom;
2746 }
2747
contains(SkScalar x,SkScalar y) const2748 bool SkPath::contains(SkScalar x, SkScalar y) const {
2749 bool isInverse = this->isInverseFillType();
2750 if (this->isEmpty()) {
2751 return isInverse;
2752 }
2753
2754 if (!contains_inclusive(this->getBounds(), x, y)) {
2755 return isInverse;
2756 }
2757
2758 SkPath::Iter iter(*this, true);
2759 bool done = false;
2760 int w = 0;
2761 do {
2762 SkPoint pts[4];
2763 switch (iter.next(pts, false)) {
2764 case SkPath::kMove_Verb:
2765 case SkPath::kClose_Verb:
2766 break;
2767 case SkPath::kLine_Verb:
2768 w += winding_line(pts, x, y);
2769 break;
2770 case SkPath::kQuad_Verb:
2771 w += winding_quad(pts, x, y);
2772 break;
2773 case SkPath::kConic_Verb:
2774 SkASSERT(0);
2775 break;
2776 case SkPath::kCubic_Verb:
2777 w += winding_cubic(pts, x, y);
2778 break;
2779 case SkPath::kDone_Verb:
2780 done = true;
2781 break;
2782 }
2783 } while (!done);
2784
2785 switch (this->getFillType()) {
2786 case SkPath::kEvenOdd_FillType:
2787 case SkPath::kInverseEvenOdd_FillType:
2788 w &= 1;
2789 break;
2790 default:
2791 break;
2792 }
2793 return SkToBool(w);
2794 }
2795