gfx/skia/trunk/src/core/SkPath.cpp@129ffea94266
gfx/skia/trunk/src/core/SkPath.cpp
Sat, 03 Jan 2015 20:18:00 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Sat, 03 Jan 2015 20:18:00 +0100
- branch
- TOR_BUG_3246
- changeset 7
- 129ffea94266
- permissions
- -rw-r--r--
Conditionally enable double key logic according to:
private browsing mode or privacy.thirdparty.isolate preference and
implement in GetCookieStringCommon and FindCookie where it counts...
With some reservations of how to convince FindCookie users to test
condition and pass a nullptr when disabling double key logic.
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 */
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"
18 ////////////////////////////////////////////////////////////////////////////
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 */
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 }
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 }
38 class SkAutoDisableDirectionCheck {
39 public:
40 SkAutoDisableDirectionCheck(SkPath* path) : fPath(path) {
41 fSaved = static_cast<SkPath::Direction>(fPath->fDirection);
42 }
44 ~SkAutoDisableDirectionCheck() {
45 fPath->fDirection = fSaved;
46 }
48 private:
49 SkPath* fPath;
50 SkPath::Direction fSaved;
51 };
52 #define SkAutoDisableDirectionCheck(...) SK_REQUIRE_LOCAL_VAR(SkAutoDisableDirectionCheck)
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).
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().
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:
68 SkAutoPathBoundsUpdate(SkPath* path, const SkRect& r) : fRect(r) {
69 this->init(path);
70 }
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 }
78 ~SkAutoPathBoundsUpdate() {
79 fPath->setConvexity(fDegenerate ? SkPath::kConvex_Convexity
80 : SkPath::kUnknown_Convexity);
81 if (fEmpty || fHasValidBounds) {
82 fPath->setBounds(fRect);
83 }
84 }
86 private:
87 SkPath* fPath;
88 SkRect fRect;
89 bool fHasValidBounds;
90 bool fDegenerate;
91 bool fEmpty;
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)
109 ////////////////////////////////////////////////////////////////////////////
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
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 */
123 ////////////////////////////////////////////////////////////////////////////
125 // flag to require a moveTo if we begin with something else, like lineTo etc.
126 #define INITIAL_LASTMOVETOINDEX_VALUE ~0
128 SkPath::SkPath()
129 : fPathRef(SkPathRef::CreateEmpty())
130 #ifdef SK_BUILD_FOR_ANDROID
131 , fSourcePath(NULL)
132 #endif
133 {
134 this->resetFields();
135 }
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;
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 }
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 }
157 SkPath::~SkPath() {
158 SkDEBUGCODE(this->validate();)
159 }
161 SkPath& SkPath::operator=(const SkPath& that) {
162 SkDEBUGCODE(that.validate();)
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 }
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 }
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 }
190 void SkPath::swap(SkPath& that) {
191 SkASSERT(&that != NULL);
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 }
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 }
231 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 }
237 Direction direction;
238 if (!this->cheapComputeDirection(&direction)) {
239 return false;
240 }
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;)
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 }
289 return check_edge_against_rect(prevPt, firstPt, rect, direction);
290 }
292 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 }
301 #ifdef SK_BUILD_FOR_ANDROID
302 const SkPath* SkPath::getSourcePath() const {
303 return fSourcePath;
304 }
306 void SkPath::setSourcePath(const SkPath* path) {
307 fSourcePath = path;
308 }
309 #endif
311 void SkPath::reset() {
312 SkDEBUGCODE(this->validate();)
314 fPathRef.reset(SkPathRef::CreateEmpty());
315 this->resetFields();
316 }
318 void SkPath::rewind() {
319 SkDEBUGCODE(this->validate();)
321 SkPathRef::Rewind(&fPathRef);
322 this->resetFields();
323 }
325 bool SkPath::isLine(SkPoint line[2]) const {
326 int verbCount = fPathRef->countVerbs();
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 }
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.
347 The direction is computed such that:
348 0: vertical up
349 1: horizontal left
350 2: vertical down
351 3: horizontal right
353 A rectangle cycles up/right/down/left or up/left/down/right.
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.
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)
370 It's OK if the path has:
371 Several colinear line segments composing a rectangle side.
372 Single points on the rectangle side.
374 The direction takes advantage of the corners found since opposite sides
375 must travel in opposite directions.
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.
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
388 */
389 static int rect_make_dir(SkScalar dx, SkScalar dy) {
390 return ((0 != dx) << 0) | ((dx > 0 || dy > 0) << 1);
391 }
392 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 }
507 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 }
515 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 }
526 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 }
533 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 }
573 int SkPath::countPoints() const {
574 return fPathRef->countPoints();
575 }
577 int SkPath::getPoints(SkPoint dst[], int max) const {
578 SkDEBUGCODE(this->validate();)
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 }
587 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 }
594 int SkPath::countVerbs() const {
595 return fPathRef->countVerbs();
596 }
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 }
606 int SkPath::getVerbs(uint8_t dst[], int max) const {
607 SkDEBUGCODE(this->validate();)
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 }
616 bool SkPath::getLastPt(SkPoint* lastPt) const {
617 SkDEBUGCODE(this->validate();)
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 }
632 void SkPath::setLastPt(SkScalar x, SkScalar y) {
633 SkDEBUGCODE(this->validate();)
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 }
644 void SkPath::setConvexity(Convexity c) {
645 if (fConvexity != c) {
646 fConvexity = c;
647 }
648 }
650 //////////////////////////////////////////////////////////////////////////////
651 // Construction methods
653 #define DIRTY_AFTER_EDIT \
654 do { \
655 fConvexity = kUnknown_Convexity; \
656 fDirection = kUnknown_Direction; \
657 } while (0)
659 void SkPath::incReserve(U16CPU inc) {
660 SkDEBUGCODE(this->validate();)
661 SkPathRef::Editor(&fPathRef, inc, inc);
662 SkDEBUGCODE(this->validate();)
663 }
665 void SkPath::moveTo(SkScalar x, SkScalar y) {
666 SkDEBUGCODE(this->validate();)
668 SkPathRef::Editor ed(&fPathRef);
670 // remember our index
671 fLastMoveToIndex = fPathRef->countPoints();
673 ed.growForVerb(kMove_Verb)->set(x, y);
674 }
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 }
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 }
696 void SkPath::lineTo(SkScalar x, SkScalar y) {
697 SkDEBUGCODE(this->validate();)
699 this->injectMoveToIfNeeded();
701 SkPathRef::Editor ed(&fPathRef);
702 ed.growForVerb(kLine_Verb)->set(x, y);
704 DIRTY_AFTER_EDIT;
705 }
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 }
714 void SkPath::quadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) {
715 SkDEBUGCODE(this->validate();)
717 this->injectMoveToIfNeeded();
719 SkPathRef::Editor ed(&fPathRef);
720 SkPoint* pts = ed.growForVerb(kQuad_Verb);
721 pts[0].set(x1, y1);
722 pts[1].set(x2, y2);
724 DIRTY_AFTER_EDIT;
725 }
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 }
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();)
747 this->injectMoveToIfNeeded();
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);
754 DIRTY_AFTER_EDIT;
755 }
756 }
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 }
766 void SkPath::cubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
767 SkScalar x3, SkScalar y3) {
768 SkDEBUGCODE(this->validate();)
770 this->injectMoveToIfNeeded();
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);
778 DIRTY_AFTER_EDIT;
779 }
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 }
790 void SkPath::close() {
791 SkDEBUGCODE(this->validate();)
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 }
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 }
824 ///////////////////////////////////////////////////////////////////////////////
826 static void assert_known_direction(int dir) {
827 SkASSERT(SkPath::kCW_Direction == dir || SkPath::kCCW_Direction == dir);
828 }
830 void SkPath::addRect(const SkRect& rect, Direction dir) {
831 this->addRect(rect.fLeft, rect.fTop, rect.fRight, rect.fBottom, dir);
832 }
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);
840 SkAutoPathBoundsUpdate apbu(this, left, top, right, bottom);
842 this->incReserve(5);
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 }
857 void SkPath::addPoly(const SkPoint pts[], int count, bool close) {
858 SkDEBUGCODE(this->validate();)
859 if (count <= 0) {
860 return;
861 }
863 fLastMoveToIndex = fPathRef->countPoints();
865 // +close makes room for the extra kClose_Verb
866 SkPathRef::Editor ed(&fPathRef, count+close, count);
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 }
874 if (close) {
875 ed.growForVerb(kClose_Verb);
876 }
878 DIRTY_AFTER_EDIT;
879 SkDEBUGCODE(this->validate();)
880 }
882 #include "SkGeometry.h"
884 static int build_arc_points(const SkRect& oval, SkScalar startAngle,
885 SkScalar sweepAngle,
886 SkPoint pts[kSkBuildQuadArcStorage]) {
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 }
906 SkVector start, stop;
908 start.fY = SkScalarSinCos(SkDegreesToRadians(startAngle), &start.fX);
909 stop.fY = SkScalarSinCos(SkDegreesToRadians(startAngle + sweepAngle),
910 &stop.fX);
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 }
934 SkMatrix matrix;
936 matrix.setScale(SkScalarHalf(oval.width()), SkScalarHalf(oval.height()));
937 matrix.postTranslate(oval.centerX(), oval.centerY());
939 return SkBuildQuadArc(start, stop,
940 sweepAngle > 0 ? kCW_SkRotationDirection :
941 kCCW_SkRotationDirection,
942 &matrix, pts);
943 }
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 }
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);
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);
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);
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);
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);
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);
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);
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 */
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];
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 }
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 }
1079 void SkPath::addRRect(const SkRRect& rrect, Direction dir) {
1080 assert_known_direction(dir);
1082 if (rrect.isEmpty()) {
1083 return;
1084 }
1086 const SkRect& bounds = rrect.getBounds();
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;
1100 SkAutoPathBoundsUpdate apbu(this, bounds);
1101 SkAutoDisableDirectionCheck addc(this);
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 }
1123 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 }
1138 #ifdef SK_IGNORE_QUAD_RR_CORNERS_OPT
1139 #define CUBIC_ARC_FACTOR ((SK_ScalarSqrt2 - SK_Scalar1) * 4 / 3)
1140 #endif
1142 void SkPath::addRoundRect(const SkRect& rect, SkScalar rx, SkScalar ry,
1143 Direction dir) {
1144 assert_known_direction(dir);
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 }
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);
1160 if (halfW <= 0 || halfH <= 0) {
1161 return;
1162 }
1164 bool skip_hori = rx >= halfW;
1165 bool skip_vert = ry >= halfH;
1167 if (skip_hori && skip_vert) {
1168 this->addOval(rect, dir);
1169 return;
1170 }
1172 fDirection = this->hasOnlyMoveTos() ? dir : kUnknown_Direction;
1174 SkAutoPathBoundsUpdate apbu(this, rect);
1175 SkAutoDisableDirectionCheck addc(this);
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);
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 }
1246 void SkPath::addOval(const SkRect& oval, Direction dir) {
1247 assert_known_direction(dir);
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 }
1262 SkAutoDisableDirectionCheck addc(this);
1264 SkAutoPathBoundsUpdate apbu(this, oval);
1266 SkScalar cx = oval.centerX();
1267 SkScalar cy = oval.centerY();
1268 SkScalar rx = SkScalarHalf(oval.width());
1269 SkScalar ry = SkScalarHalf(oval.height());
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);
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
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();
1310 SkPathRef::Editor ed(&fPathRef);
1312 ed.setIsOval(isOval);
1313 }
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 }
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 }
1329 SkPoint pts[kSkBuildQuadArcStorage];
1330 int count = build_arc_points(oval, startAngle, sweepAngle, pts);
1331 SkASSERT((count & 1) == 1);
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 }
1343 void SkPath::addArc(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle) {
1344 if (oval.isEmpty() || 0 == sweepAngle) {
1345 return;
1346 }
1348 const SkScalar kFullCircleAngle = SkIntToScalar(360);
1350 if (sweepAngle >= kFullCircleAngle || sweepAngle <= -kFullCircleAngle) {
1351 this->addOval(oval, sweepAngle > 0 ? kCW_Direction : kCCW_Direction);
1352 return;
1353 }
1355 SkPoint pts[kSkBuildQuadArcStorage];
1356 int count = build_arc_points(oval, startAngle, sweepAngle, pts);
1358 SkDEBUGCODE(this->validate();)
1359 SkASSERT(count & 1);
1361 fLastMoveToIndex = fPathRef->countPoints();
1363 SkPathRef::Editor ed(&fPathRef, 1+(count-1)/2, count);
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 }
1371 DIRTY_AFTER_EDIT;
1372 SkDEBUGCODE(this->validate();)
1373 }
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 */
1379 void SkPath::arcTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
1380 SkScalar radius) {
1381 SkVector before, after;
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 }
1399 SkScalar cosh = SkPoint::DotProduct(before, after);
1400 SkScalar sinh = SkPoint::CrossProduct(before, after);
1402 if (SkScalarNearlyZero(sinh)) { // angle is too tight
1403 this->lineTo(x1, y1);
1404 return;
1405 }
1407 SkScalar dist = SkScalarMulDiv(radius, SK_Scalar1 - cosh, sinh);
1408 if (dist < 0) {
1409 dist = -dist;
1410 }
1412 SkScalar xx = x1 - SkScalarMul(dist, before.fX);
1413 SkScalar yy = y1 - SkScalarMul(dist, before.fY);
1414 SkRotationDirection arcDir;
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 }
1427 SkMatrix matrix;
1428 SkPoint pts[kSkBuildQuadArcStorage];
1430 matrix.setScale(radius, radius);
1431 matrix.postTranslate(xx - SkScalarMul(radius, before.fX),
1432 yy - SkScalarMul(radius, before.fY));
1434 int count = SkBuildQuadArc(before, after, arcDir, &matrix, pts);
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 }
1444 ///////////////////////////////////////////////////////////////////////////////
1446 void SkPath::addPath(const SkPath& path, SkScalar dx, SkScalar dy, AddPathMode mode) {
1447 SkMatrix matrix;
1449 matrix.setTranslate(dx, dy);
1450 this->addPath(path, matrix, mode);
1451 }
1453 void SkPath::addPath(const SkPath& path, const SkMatrix& matrix, AddPathMode mode) {
1454 SkPathRef::Editor(&fPathRef, path.countVerbs(), path.countPoints());
1456 RawIter iter(path);
1457 SkPoint pts[4];
1458 Verb verb;
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 }
1499 ///////////////////////////////////////////////////////////////////////////////
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 };
1512 SkASSERT(verb < SK_ARRAY_COUNT(gPtsInVerb));
1513 return gPtsInVerb[verb];
1514 }
1516 // ignore the last point of the 1st contour
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 }
1524 SkPathRef::Editor(&fPathRef, vcount, path.countPoints());
1526 const uint8_t* verbs = path.fPathRef->verbs();
1527 const SkPoint* pts = path.fPathRef->points();
1528 const SkScalar* conicWeights = path.fPathRef->conicWeights();
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 }
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 }
1564 void SkPath::reverseAddPath(const SkPath& src) {
1565 SkPathRef::Editor ed(&fPathRef, src.fPathRef->countPoints(), src.fPathRef->countVerbs());
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();
1573 bool needMove = true;
1574 bool needClose = false;
1575 while (verbs < verbsEnd) {
1576 uint8_t v = *(verbs++);
1577 int n = pts_in_verb(v);
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 }
1615 ///////////////////////////////////////////////////////////////////////////////
1617 void SkPath::offset(SkScalar dx, SkScalar dy, SkPath* dst) const {
1618 SkMatrix matrix;
1620 matrix.setTranslate(dx, dy);
1621 this->transform(matrix, dst);
1622 }
1624 #include "SkGeometry.h"
1626 static void subdivide_quad_to(SkPath* path, const SkPoint pts[3],
1627 int level = 2) {
1628 if (--level >= 0) {
1629 SkPoint tmp[5];
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 }
1639 static void subdivide_cubic_to(SkPath* path, const SkPoint pts[4],
1640 int level = 2) {
1641 if (--level >= 0) {
1642 SkPoint tmp[7];
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 }
1652 void SkPath::transform(const SkMatrix& matrix, SkPath* dst) const {
1653 SkDEBUGCODE(this->validate();)
1654 if (dst == NULL) {
1655 dst = (SkPath*)this;
1656 }
1658 if (matrix.hasPerspective()) {
1659 SkPath tmp;
1660 tmp.fFillType = fFillType;
1662 SkPath::Iter iter(*this, false);
1663 SkPoint pts[4];
1664 SkPath::Verb verb;
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 }
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);
1700 if (this != dst) {
1701 dst->fFillType = fFillType;
1702 dst->fConvexity = fConvexity;
1703 }
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 }
1721 SkDEBUGCODE(dst->validate();)
1722 }
1723 }
1725 ///////////////////////////////////////////////////////////////////////////////
1726 ///////////////////////////////////////////////////////////////////////////////
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 };
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 }
1751 SkPath::Iter::Iter(const SkPath& path, bool forceClose) {
1752 this->setPath(path, forceClose);
1753 }
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 }
1767 bool SkPath::Iter::isClosedContour() const {
1768 if (fVerbs == NULL || fVerbs == fVerbStop) {
1769 return false;
1770 }
1771 if (fForceClose) {
1772 return true;
1773 }
1775 const uint8_t* verbs = fVerbs;
1776 const uint8_t* stop = fVerbStop;
1778 if (kMove_Verb == *(verbs - 1)) {
1779 verbs -= 1; // skip the initial moveto
1780 }
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 }
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 }
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 }
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 }
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;
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;
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;
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;
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;
1901 default:
1902 SkDEBUGFAIL("Should never see kDone_Verb");
1903 }
1904 }
1905 }
1907 SkPath::Verb SkPath::Iter::doNext(SkPoint ptsParam[4]) {
1908 SkASSERT(ptsParam);
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 }
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;
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 }
1984 ///////////////////////////////////////////////////////////////////////////////
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 }
1997 SkPath::RawIter::RawIter(const SkPath& path) {
1998 this->setPath(path);
1999 }
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 }
2010 SkPath::Verb SkPath::RawIter::next(SkPoint pts[4]) {
2011 SkASSERT(NULL != pts);
2012 if (fVerbs == fVerbStop) {
2013 return kDone_Verb;
2014 }
2016 // fVerbs points one beyond next verb so decrement first.
2017 unsigned verb = *(--fVerbs);
2018 const SkPoint* srcPts = fPts;
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 }
2057 ///////////////////////////////////////////////////////////////////////////////
2059 /*
2060 Format in compressed buffer: [ptCount, verbCount, pts[], verbs[]]
2061 */
2063 size_t SkPath::writeToMemory(void* storage) const {
2064 SkDEBUGCODE(this->validate();)
2066 if (NULL == storage) {
2067 const int byteCount = sizeof(int32_t) + fPathRef->writeSize();
2068 return SkAlign4(byteCount);
2069 }
2071 SkWBuffer buffer(storage);
2073 int32_t packed = (fConvexity << kConvexity_SerializationShift) |
2074 (fFillType << kFillType_SerializationShift) |
2075 (fDirection << kDirection_SerializationShift);
2077 buffer.write32(packed);
2079 fPathRef->writeToBuffer(&buffer);
2081 buffer.padToAlign4();
2082 return buffer.pos();
2083 }
2085 size_t SkPath::readFromMemory(const void* storage, size_t length) {
2086 SkRBufferWithSizeCheck buffer(storage, length);
2088 int32_t packed;
2089 if (!buffer.readS32(&packed)) {
2090 return 0;
2091 }
2093 fConvexity = (packed >> kConvexity_SerializationShift) & 0xFF;
2094 fFillType = (packed >> kFillType_SerializationShift) & 0xFF;
2095 fDirection = (packed >> kDirection_SerializationShift) & 0x3;
2096 SkPathRef* pathRef = SkPathRef::CreateFromBuffer(&buffer);
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 }
2111 ///////////////////////////////////////////////////////////////////////////////
2113 #include "SkString.h"
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 }
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("(");
2129 const SkScalar* values = &pts[0].fX;
2130 count *= 2;
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 }
2145 void SkPath::dump(bool forceClose, const char title[]) const {
2146 Iter iter(*this, forceClose);
2147 SkPoint pts[4];
2148 Verb verb;
2150 SkDebugf("path: forceClose=%s %s\n", forceClose ? "true" : "false",
2151 title ? title : "");
2153 SkString builder;
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();\n");
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 }
2184 void SkPath::dump() const {
2185 this->dump(false);
2186 }
2188 #ifdef SK_DEBUG
2189 void SkPath::validate() const {
2190 SkASSERT(this != NULL);
2191 SkASSERT((fFillType & ~3) == 0);
2193 #ifdef SK_DEBUG_PATH
2194 if (!fBoundsIsDirty) {
2195 SkRect bounds;
2197 bool isFinite = compute_pt_bounds(&bounds, *fPathRef.get());
2198 SkASSERT(SkToBool(fIsFinite) == isFinite);
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
2221 ///////////////////////////////////////////////////////////////////////////////
2223 static int sign(SkScalar x) { return x < 0; }
2224 #define kValueNeverReturnedBySign 2
2226 static bool AlmostEqual(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 }
2240 // only valid for a single contour
2241 struct Convexicator {
2242 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 fVec0.set(0, 0);
2251 fVec1.set(0, 0);
2252 fFirstVec.set(0, 0);
2254 fDx = fDy = 0;
2255 fSx = fSy = kValueNeverReturnedBySign;
2256 }
2258 SkPath::Convexity getConvexity() const { return fConvexity; }
2260 /** The direction returned is only valid if the path is determined convex */
2261 SkPath::Direction getDirection() const { return fDirection; }
2263 void addPt(const SkPoint& pt) {
2264 if (SkPath::kConcave_Convexity == fConvexity) {
2265 return;
2266 }
2268 if (0 == fPtCount) {
2269 fCurrPt = pt;
2270 ++fPtCount;
2271 } else {
2272 SkVector vec = pt - fCurrPt;
2273 if (vec.fX || vec.fY) {
2274 fLastPt = fCurrPt;
2275 fCurrPt = pt;
2276 if (++fPtCount == 2) {
2277 fFirstVec = fVec1 = vec;
2278 } else {
2279 SkASSERT(fPtCount > 2);
2280 this->addVec(vec);
2281 }
2283 int sx = sign(vec.fX);
2284 int sy = sign(vec.fY);
2285 fDx += (sx != fSx);
2286 fDy += (sy != fSy);
2287 fSx = sx;
2288 fSy = sy;
2290 if (fDx > 3 || fDy > 3) {
2291 fConvexity = SkPath::kConcave_Convexity;
2292 }
2293 }
2294 }
2295 }
2297 void close() {
2298 if (fPtCount > 2) {
2299 this->addVec(fFirstVec);
2300 }
2301 }
2303 private:
2304 void addVec(const SkVector& vec) {
2305 SkASSERT(vec.fX || vec.fY);
2306 fVec0 = fVec1;
2307 fVec1 = vec;
2308 SkScalar cross = SkPoint::CrossProduct(fVec0, fVec1);
2309 SkScalar smallest = SkTMin(fCurrPt.fX, SkTMin(fCurrPt.fY, SkTMin(fLastPt.fX, fLastPt.fY)));
2310 SkScalar largest = SkTMax(fCurrPt.fX, SkTMax(fCurrPt.fY, SkTMax(fLastPt.fX, fLastPt.fY)));
2311 largest = SkTMax(largest, -smallest);
2312 int sign = AlmostEqual(largest, largest + cross) ? 0 : SkScalarSignAsInt(cross);
2313 if (0 == fSign) {
2314 fSign = sign;
2315 if (1 == sign) {
2316 fDirection = SkPath::kCW_Direction;
2317 } else if (-1 == sign) {
2318 fDirection = SkPath::kCCW_Direction;
2319 }
2320 } else if (sign) {
2321 if (fSign != sign) {
2322 fConvexity = SkPath::kConcave_Convexity;
2323 fDirection = SkPath::kUnknown_Direction;
2324 }
2325 }
2326 }
2328 SkPoint fLastPt;
2329 SkPoint fCurrPt;
2330 SkVector fVec0, fVec1, fFirstVec;
2331 int fPtCount; // non-degenerate points
2332 int fSign;
2333 SkPath::Convexity fConvexity;
2334 SkPath::Direction fDirection;
2335 int fDx, fDy, fSx, fSy;
2336 };
2338 SkPath::Convexity SkPath::internalGetConvexity() const {
2339 SkASSERT(kUnknown_Convexity == fConvexity);
2340 SkPoint pts[4];
2341 SkPath::Verb verb;
2342 SkPath::Iter iter(*this, true);
2344 int contourCount = 0;
2345 int count;
2346 Convexicator state;
2348 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
2349 switch (verb) {
2350 case kMove_Verb:
2351 if (++contourCount > 1) {
2352 fConvexity = kConcave_Convexity;
2353 return kConcave_Convexity;
2354 }
2355 pts[1] = pts[0];
2356 count = 1;
2357 break;
2358 case kLine_Verb: count = 1; break;
2359 case kQuad_Verb: count = 2; break;
2360 case kConic_Verb: count = 2; break;
2361 case kCubic_Verb: count = 3; break;
2362 case kClose_Verb:
2363 state.close();
2364 count = 0;
2365 break;
2366 default:
2367 SkDEBUGFAIL("bad verb");
2368 fConvexity = kConcave_Convexity;
2369 return kConcave_Convexity;
2370 }
2372 for (int i = 1; i <= count; i++) {
2373 state.addPt(pts[i]);
2374 }
2375 // early exit
2376 if (kConcave_Convexity == state.getConvexity()) {
2377 fConvexity = kConcave_Convexity;
2378 return kConcave_Convexity;
2379 }
2380 }
2381 fConvexity = state.getConvexity();
2382 if (kConvex_Convexity == fConvexity && kUnknown_Direction == fDirection) {
2383 fDirection = state.getDirection();
2384 }
2385 return static_cast<Convexity>(fConvexity);
2386 }
2388 ///////////////////////////////////////////////////////////////////////////////
2390 class ContourIter {
2391 public:
2392 ContourIter(const SkPathRef& pathRef);
2394 bool done() const { return fDone; }
2395 // if !done() then these may be called
2396 int count() const { return fCurrPtCount; }
2397 const SkPoint* pts() const { return fCurrPt; }
2398 void next();
2400 private:
2401 int fCurrPtCount;
2402 const SkPoint* fCurrPt;
2403 const uint8_t* fCurrVerb;
2404 const uint8_t* fStopVerbs;
2405 const SkScalar* fCurrConicWeight;
2406 bool fDone;
2407 SkDEBUGCODE(int fContourCounter;)
2408 };
2410 ContourIter::ContourIter(const SkPathRef& pathRef) {
2411 fStopVerbs = pathRef.verbsMemBegin();
2412 fDone = false;
2413 fCurrPt = pathRef.points();
2414 fCurrVerb = pathRef.verbs();
2415 fCurrConicWeight = pathRef.conicWeights();
2416 fCurrPtCount = 0;
2417 SkDEBUGCODE(fContourCounter = 0;)
2418 this->next();
2419 }
2421 void ContourIter::next() {
2422 if (fCurrVerb <= fStopVerbs) {
2423 fDone = true;
2424 }
2425 if (fDone) {
2426 return;
2427 }
2429 // skip pts of prev contour
2430 fCurrPt += fCurrPtCount;
2432 SkASSERT(SkPath::kMove_Verb == fCurrVerb[~0]);
2433 int ptCount = 1; // moveTo
2434 const uint8_t* verbs = fCurrVerb;
2436 for (--verbs; verbs > fStopVerbs; --verbs) {
2437 switch (verbs[~0]) {
2438 case SkPath::kMove_Verb:
2439 goto CONTOUR_END;
2440 case SkPath::kLine_Verb:
2441 ptCount += 1;
2442 break;
2443 case SkPath::kConic_Verb:
2444 fCurrConicWeight += 1;
2445 // fall-through
2446 case SkPath::kQuad_Verb:
2447 ptCount += 2;
2448 break;
2449 case SkPath::kCubic_Verb:
2450 ptCount += 3;
2451 break;
2452 case SkPath::kClose_Verb:
2453 break;
2454 default:
2455 SkDEBUGFAIL("unexpected verb");
2456 break;
2457 }
2458 }
2459 CONTOUR_END:
2460 fCurrPtCount = ptCount;
2461 fCurrVerb = verbs;
2462 SkDEBUGCODE(++fContourCounter;)
2463 }
2465 // returns cross product of (p1 - p0) and (p2 - p0)
2466 static SkScalar cross_prod(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) {
2467 SkScalar cross = SkPoint::CrossProduct(p1 - p0, p2 - p0);
2468 // We may get 0 when the above subtracts underflow. We expect this to be
2469 // very rare and lazily promote to double.
2470 if (0 == cross) {
2471 double p0x = SkScalarToDouble(p0.fX);
2472 double p0y = SkScalarToDouble(p0.fY);
2474 double p1x = SkScalarToDouble(p1.fX);
2475 double p1y = SkScalarToDouble(p1.fY);
2477 double p2x = SkScalarToDouble(p2.fX);
2478 double p2y = SkScalarToDouble(p2.fY);
2480 cross = SkDoubleToScalar((p1x - p0x) * (p2y - p0y) -
2481 (p1y - p0y) * (p2x - p0x));
2483 }
2484 return cross;
2485 }
2487 // Returns the first pt with the maximum Y coordinate
2488 static int find_max_y(const SkPoint pts[], int count) {
2489 SkASSERT(count > 0);
2490 SkScalar max = pts[0].fY;
2491 int firstIndex = 0;
2492 for (int i = 1; i < count; ++i) {
2493 SkScalar y = pts[i].fY;
2494 if (y > max) {
2495 max = y;
2496 firstIndex = i;
2497 }
2498 }
2499 return firstIndex;
2500 }
2502 static int find_diff_pt(const SkPoint pts[], int index, int n, int inc) {
2503 int i = index;
2504 for (;;) {
2505 i = (i + inc) % n;
2506 if (i == index) { // we wrapped around, so abort
2507 break;
2508 }
2509 if (pts[index] != pts[i]) { // found a different point, success!
2510 break;
2511 }
2512 }
2513 return i;
2514 }
2516 /**
2517 * Starting at index, and moving forward (incrementing), find the xmin and
2518 * xmax of the contiguous points that have the same Y.
2519 */
2520 static int find_min_max_x_at_y(const SkPoint pts[], int index, int n,
2521 int* maxIndexPtr) {
2522 const SkScalar y = pts[index].fY;
2523 SkScalar min = pts[index].fX;
2524 SkScalar max = min;
2525 int minIndex = index;
2526 int maxIndex = index;
2527 for (int i = index + 1; i < n; ++i) {
2528 if (pts[i].fY != y) {
2529 break;
2530 }
2531 SkScalar x = pts[i].fX;
2532 if (x < min) {
2533 min = x;
2534 minIndex = i;
2535 } else if (x > max) {
2536 max = x;
2537 maxIndex = i;
2538 }
2539 }
2540 *maxIndexPtr = maxIndex;
2541 return minIndex;
2542 }
2544 static void crossToDir(SkScalar cross, SkPath::Direction* dir) {
2545 *dir = cross > 0 ? SkPath::kCW_Direction : SkPath::kCCW_Direction;
2546 }
2548 /*
2549 * We loop through all contours, and keep the computed cross-product of the
2550 * contour that contained the global y-max. If we just look at the first
2551 * contour, we may find one that is wound the opposite way (correctly) since
2552 * it is the interior of a hole (e.g. 'o'). Thus we must find the contour
2553 * that is outer most (or at least has the global y-max) before we can consider
2554 * its cross product.
2555 */
2556 bool SkPath::cheapComputeDirection(Direction* dir) const {
2557 if (kUnknown_Direction != fDirection) {
2558 *dir = static_cast<Direction>(fDirection);
2559 return true;
2560 }
2562 // don't want to pay the cost for computing this if it
2563 // is unknown, so we don't call isConvex()
2564 if (kConvex_Convexity == this->getConvexityOrUnknown()) {
2565 SkASSERT(kUnknown_Direction == fDirection);
2566 *dir = static_cast<Direction>(fDirection);
2567 return false;
2568 }
2570 ContourIter iter(*fPathRef.get());
2572 // initialize with our logical y-min
2573 SkScalar ymax = this->getBounds().fTop;
2574 SkScalar ymaxCross = 0;
2576 for (; !iter.done(); iter.next()) {
2577 int n = iter.count();
2578 if (n < 3) {
2579 continue;
2580 }
2582 const SkPoint* pts = iter.pts();
2583 SkScalar cross = 0;
2584 int index = find_max_y(pts, n);
2585 if (pts[index].fY < ymax) {
2586 continue;
2587 }
2589 // If there is more than 1 distinct point at the y-max, we take the
2590 // x-min and x-max of them and just subtract to compute the dir.
2591 if (pts[(index + 1) % n].fY == pts[index].fY) {
2592 int maxIndex;
2593 int minIndex = find_min_max_x_at_y(pts, index, n, &maxIndex);
2594 if (minIndex == maxIndex) {
2595 goto TRY_CROSSPROD;
2596 }
2597 SkASSERT(pts[minIndex].fY == pts[index].fY);
2598 SkASSERT(pts[maxIndex].fY == pts[index].fY);
2599 SkASSERT(pts[minIndex].fX <= pts[maxIndex].fX);
2600 // we just subtract the indices, and let that auto-convert to
2601 // SkScalar, since we just want - or + to signal the direction.
2602 cross = minIndex - maxIndex;
2603 } else {
2604 TRY_CROSSPROD:
2605 // Find a next and prev index to use for the cross-product test,
2606 // but we try to find pts that form non-zero vectors from pts[index]
2607 //
2608 // Its possible that we can't find two non-degenerate vectors, so
2609 // we have to guard our search (e.g. all the pts could be in the
2610 // same place).
2612 // we pass n - 1 instead of -1 so we don't foul up % operator by
2613 // passing it a negative LH argument.
2614 int prev = find_diff_pt(pts, index, n, n - 1);
2615 if (prev == index) {
2616 // completely degenerate, skip to next contour
2617 continue;
2618 }
2619 int next = find_diff_pt(pts, index, n, 1);
2620 SkASSERT(next != index);
2621 cross = cross_prod(pts[prev], pts[index], pts[next]);
2622 // if we get a zero and the points are horizontal, then we look at the spread in
2623 // x-direction. We really should continue to walk away from the degeneracy until
2624 // there is a divergence.
2625 if (0 == cross && pts[prev].fY == pts[index].fY && pts[next].fY == pts[index].fY) {
2626 // construct the subtract so we get the correct Direction below
2627 cross = pts[index].fX - pts[next].fX;
2628 }
2629 }
2631 if (cross) {
2632 // record our best guess so far
2633 ymax = pts[index].fY;
2634 ymaxCross = cross;
2635 }
2636 }
2637 if (ymaxCross) {
2638 crossToDir(ymaxCross, dir);
2639 fDirection = *dir;
2640 return true;
2641 } else {
2642 return false;
2643 }
2644 }
2646 ///////////////////////////////////////////////////////////////////////////////
2648 static SkScalar eval_cubic_coeff(SkScalar A, SkScalar B, SkScalar C,
2649 SkScalar D, SkScalar t) {
2650 return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D);
2651 }
2653 static SkScalar eval_cubic_pts(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3,
2654 SkScalar t) {
2655 SkScalar A = c3 + 3*(c1 - c2) - c0;
2656 SkScalar B = 3*(c2 - c1 - c1 + c0);
2657 SkScalar C = 3*(c1 - c0);
2658 SkScalar D = c0;
2659 return eval_cubic_coeff(A, B, C, D, t);
2660 }
2662 /* Given 4 cubic points (either Xs or Ys), and a target X or Y, compute the
2663 t value such that cubic(t) = target
2664 */
2665 static void chopMonoCubicAt(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3,
2666 SkScalar target, SkScalar* t) {
2667 // SkASSERT(c0 <= c1 && c1 <= c2 && c2 <= c3);
2668 SkASSERT(c0 < target && target < c3);
2670 SkScalar D = c0 - target;
2671 SkScalar A = c3 + 3*(c1 - c2) - c0;
2672 SkScalar B = 3*(c2 - c1 - c1 + c0);
2673 SkScalar C = 3*(c1 - c0);
2675 const SkScalar TOLERANCE = SK_Scalar1 / 4096;
2676 SkScalar minT = 0;
2677 SkScalar maxT = SK_Scalar1;
2678 SkScalar mid;
2679 int i;
2680 for (i = 0; i < 16; i++) {
2681 mid = SkScalarAve(minT, maxT);
2682 SkScalar delta = eval_cubic_coeff(A, B, C, D, mid);
2683 if (delta < 0) {
2684 minT = mid;
2685 delta = -delta;
2686 } else {
2687 maxT = mid;
2688 }
2689 if (delta < TOLERANCE) {
2690 break;
2691 }
2692 }
2693 *t = mid;
2694 }
2696 template <size_t N> static void find_minmax(const SkPoint pts[],
2697 SkScalar* minPtr, SkScalar* maxPtr) {
2698 SkScalar min, max;
2699 min = max = pts[0].fX;
2700 for (size_t i = 1; i < N; ++i) {
2701 min = SkMinScalar(min, pts[i].fX);
2702 max = SkMaxScalar(max, pts[i].fX);
2703 }
2704 *minPtr = min;
2705 *maxPtr = max;
2706 }
2708 static int winding_mono_cubic(const SkPoint pts[], SkScalar x, SkScalar y) {
2709 SkPoint storage[4];
2711 int dir = 1;
2712 if (pts[0].fY > pts[3].fY) {
2713 storage[0] = pts[3];
2714 storage[1] = pts[2];
2715 storage[2] = pts[1];
2716 storage[3] = pts[0];
2717 pts = storage;
2718 dir = -1;
2719 }
2720 if (y < pts[0].fY || y >= pts[3].fY) {
2721 return 0;
2722 }
2724 // quickreject or quickaccept
2725 SkScalar min, max;
2726 find_minmax<4>(pts, &min, &max);
2727 if (x < min) {
2728 return 0;
2729 }
2730 if (x > max) {
2731 return dir;
2732 }
2734 // compute the actual x(t) value
2735 SkScalar t;
2736 chopMonoCubicAt(pts[0].fY, pts[1].fY, pts[2].fY, pts[3].fY, y, &t);
2737 SkScalar xt = eval_cubic_pts(pts[0].fX, pts[1].fX, pts[2].fX, pts[3].fX, t);
2738 return xt < x ? dir : 0;
2739 }
2741 static int winding_cubic(const SkPoint pts[], SkScalar x, SkScalar y) {
2742 SkPoint dst[10];
2743 int n = SkChopCubicAtYExtrema(pts, dst);
2744 int w = 0;
2745 for (int i = 0; i <= n; ++i) {
2746 w += winding_mono_cubic(&dst[i * 3], x, y);
2747 }
2748 return w;
2749 }
2751 static int winding_mono_quad(const SkPoint pts[], SkScalar x, SkScalar y) {
2752 SkScalar y0 = pts[0].fY;
2753 SkScalar y2 = pts[2].fY;
2755 int dir = 1;
2756 if (y0 > y2) {
2757 SkTSwap(y0, y2);
2758 dir = -1;
2759 }
2760 if (y < y0 || y >= y2) {
2761 return 0;
2762 }
2764 // bounds check on X (not required. is it faster?)
2765 #if 0
2766 if (pts[0].fX > x && pts[1].fX > x && pts[2].fX > x) {
2767 return 0;
2768 }
2769 #endif
2771 SkScalar roots[2];
2772 int n = SkFindUnitQuadRoots(pts[0].fY - 2 * pts[1].fY + pts[2].fY,
2773 2 * (pts[1].fY - pts[0].fY),
2774 pts[0].fY - y,
2775 roots);
2776 SkASSERT(n <= 1);
2777 SkScalar xt;
2778 if (0 == n) {
2779 SkScalar mid = SkScalarAve(y0, y2);
2780 // Need [0] and [2] if dir == 1
2781 // and [2] and [0] if dir == -1
2782 xt = y < mid ? pts[1 - dir].fX : pts[dir - 1].fX;
2783 } else {
2784 SkScalar t = roots[0];
2785 SkScalar C = pts[0].fX;
2786 SkScalar A = pts[2].fX - 2 * pts[1].fX + C;
2787 SkScalar B = 2 * (pts[1].fX - C);
2788 xt = SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C);
2789 }
2790 return xt < x ? dir : 0;
2791 }
2793 static bool is_mono_quad(SkScalar y0, SkScalar y1, SkScalar y2) {
2794 // return SkScalarSignAsInt(y0 - y1) + SkScalarSignAsInt(y1 - y2) != 0;
2795 if (y0 == y1) {
2796 return true;
2797 }
2798 if (y0 < y1) {
2799 return y1 <= y2;
2800 } else {
2801 return y1 >= y2;
2802 }
2803 }
2805 static int winding_quad(const SkPoint pts[], SkScalar x, SkScalar y) {
2806 SkPoint dst[5];
2807 int n = 0;
2809 if (!is_mono_quad(pts[0].fY, pts[1].fY, pts[2].fY)) {
2810 n = SkChopQuadAtYExtrema(pts, dst);
2811 pts = dst;
2812 }
2813 int w = winding_mono_quad(pts, x, y);
2814 if (n > 0) {
2815 w += winding_mono_quad(&pts[2], x, y);
2816 }
2817 return w;
2818 }
2820 static int winding_line(const SkPoint pts[], SkScalar x, SkScalar y) {
2821 SkScalar x0 = pts[0].fX;
2822 SkScalar y0 = pts[0].fY;
2823 SkScalar x1 = pts[1].fX;
2824 SkScalar y1 = pts[1].fY;
2826 SkScalar dy = y1 - y0;
2828 int dir = 1;
2829 if (y0 > y1) {
2830 SkTSwap(y0, y1);
2831 dir = -1;
2832 }
2833 if (y < y0 || y >= y1) {
2834 return 0;
2835 }
2837 SkScalar cross = SkScalarMul(x1 - x0, y - pts[0].fY) -
2838 SkScalarMul(dy, x - pts[0].fX);
2840 if (SkScalarSignAsInt(cross) == dir) {
2841 dir = 0;
2842 }
2843 return dir;
2844 }
2846 static bool contains_inclusive(const SkRect& r, SkScalar x, SkScalar y) {
2847 return r.fLeft <= x && x <= r.fRight && r.fTop <= y && y <= r.fBottom;
2848 }
2850 bool SkPath::contains(SkScalar x, SkScalar y) const {
2851 bool isInverse = this->isInverseFillType();
2852 if (this->isEmpty()) {
2853 return isInverse;
2854 }
2856 if (!contains_inclusive(this->getBounds(), x, y)) {
2857 return isInverse;
2858 }
2860 SkPath::Iter iter(*this, true);
2861 bool done = false;
2862 int w = 0;
2863 do {
2864 SkPoint pts[4];
2865 switch (iter.next(pts, false)) {
2866 case SkPath::kMove_Verb:
2867 case SkPath::kClose_Verb:
2868 break;
2869 case SkPath::kLine_Verb:
2870 w += winding_line(pts, x, y);
2871 break;
2872 case SkPath::kQuad_Verb:
2873 w += winding_quad(pts, x, y);
2874 break;
2875 case SkPath::kConic_Verb:
2876 SkASSERT(0);
2877 break;
2878 case SkPath::kCubic_Verb:
2879 w += winding_cubic(pts, x, y);
2880 break;
2881 case SkPath::kDone_Verb:
2882 done = true;
2883 break;
2884 }
2885 } while (!done);
2887 switch (this->getFillType()) {
2888 case SkPath::kEvenOdd_FillType:
2889 case SkPath::kInverseEvenOdd_FillType:
2890 w &= 1;
2891 break;
2892 default:
2893 break;
2894 }
2895 return SkToBool(w);
2896 }
