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