diff -r 000000000000 -r 6474c204b198 gfx/skia/trunk/src/core/SkPath.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/gfx/skia/trunk/src/core/SkPath.cpp Wed Dec 31 06:09:35 2014 +0100 @@ -0,0 +1,2896 @@ + +/* + * Copyright 2006 The Android Open Source Project + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + + +#include "SkBuffer.h" +#include "SkErrorInternals.h" +#include "SkMath.h" +#include "SkPath.h" +#include "SkPathRef.h" +#include "SkRRect.h" +#include "SkThread.h" + +//////////////////////////////////////////////////////////////////////////// + +/** + * Path.bounds is defined to be the bounds of all the control points. + * If we called bounds.join(r) we would skip r if r was empty, which breaks + * our promise. Hence we have a custom joiner that doesn't look at emptiness + */ +static void joinNoEmptyChecks(SkRect* dst, const SkRect& src) { + dst->fLeft = SkMinScalar(dst->fLeft, src.fLeft); + dst->fTop = SkMinScalar(dst->fTop, src.fTop); + dst->fRight = SkMaxScalar(dst->fRight, src.fRight); + dst->fBottom = SkMaxScalar(dst->fBottom, src.fBottom); +} + +static bool is_degenerate(const SkPath& path) { + SkPath::Iter iter(path, false); + SkPoint pts[4]; + return SkPath::kDone_Verb == iter.next(pts); +} + +class SkAutoDisableDirectionCheck { +public: + SkAutoDisableDirectionCheck(SkPath* path) : fPath(path) { + fSaved = static_cast(fPath->fDirection); + } + + ~SkAutoDisableDirectionCheck() { + fPath->fDirection = fSaved; + } + +private: + SkPath* fPath; + SkPath::Direction fSaved; +}; +#define SkAutoDisableDirectionCheck(...) SK_REQUIRE_LOCAL_VAR(SkAutoDisableDirectionCheck) + +/* This guy's constructor/destructor bracket a path editing operation. It is + used when we know the bounds of the amount we are going to add to the path + (usually a new contour, but not required). + + It captures some state about the path up front (i.e. if it already has a + cached bounds), and then if it can, it updates the cache bounds explicitly, + avoiding the need to revisit all of the points in getBounds(). + + It also notes if the path was originally degenerate, and if so, sets + isConvex to true. Thus it can only be used if the contour being added is + convex. + */ +class SkAutoPathBoundsUpdate { +public: + SkAutoPathBoundsUpdate(SkPath* path, const SkRect& r) : fRect(r) { + this->init(path); + } + + SkAutoPathBoundsUpdate(SkPath* path, SkScalar left, SkScalar top, + SkScalar right, SkScalar bottom) { + fRect.set(left, top, right, bottom); + this->init(path); + } + + ~SkAutoPathBoundsUpdate() { + fPath->setConvexity(fDegenerate ? SkPath::kConvex_Convexity + : SkPath::kUnknown_Convexity); + if (fEmpty || fHasValidBounds) { + fPath->setBounds(fRect); + } + } + +private: + SkPath* fPath; + SkRect fRect; + bool fHasValidBounds; + bool fDegenerate; + bool fEmpty; + + void init(SkPath* path) { + // Cannot use fRect for our bounds unless we know it is sorted + fRect.sort(); + fPath = path; + // Mark the path's bounds as dirty if (1) they are, or (2) the path + // is non-finite, and therefore its bounds are not meaningful + fHasValidBounds = path->hasComputedBounds() && path->isFinite(); + fEmpty = path->isEmpty(); + if (fHasValidBounds && !fEmpty) { + joinNoEmptyChecks(&fRect, fPath->getBounds()); + } + fDegenerate = is_degenerate(*path); + } +}; +#define SkAutoPathBoundsUpdate(...) SK_REQUIRE_LOCAL_VAR(SkAutoPathBoundsUpdate) + +//////////////////////////////////////////////////////////////////////////// + +/* + Stores the verbs and points as they are given to us, with exceptions: + - we only record "Close" if it was immediately preceeded by Move | Line | Quad | Cubic + - we insert a Move(0,0) if Line | Quad | Cubic is our first command + + The iterator does more cleanup, especially if forceClose == true + 1. If we encounter degenerate segments, remove them + 2. if we encounter Close, return a cons'd up Line() first (if the curr-pt != start-pt) + 3. if we encounter Move without a preceeding Close, and forceClose is true, goto #2 + 4. if we encounter Line | Quad | Cubic after Close, cons up a Move +*/ + +//////////////////////////////////////////////////////////////////////////// + +// flag to require a moveTo if we begin with something else, like lineTo etc. +#define INITIAL_LASTMOVETOINDEX_VALUE ~0 + +SkPath::SkPath() + : fPathRef(SkPathRef::CreateEmpty()) +#ifdef SK_BUILD_FOR_ANDROID + , fSourcePath(NULL) +#endif +{ + this->resetFields(); +} + +void SkPath::resetFields() { + //fPathRef is assumed to have been emptied by the caller. + fLastMoveToIndex = INITIAL_LASTMOVETOINDEX_VALUE; + fFillType = kWinding_FillType; + fConvexity = kUnknown_Convexity; + fDirection = kUnknown_Direction; + + // We don't touch Android's fSourcePath. It's used to track texture garbage collection, so we + // don't want to muck with it if it's been set to something non-NULL. +} + +SkPath::SkPath(const SkPath& that) + : fPathRef(SkRef(that.fPathRef.get())) { + this->copyFields(that); +#ifdef SK_BUILD_FOR_ANDROID + fSourcePath = that.fSourcePath; +#endif + SkDEBUGCODE(that.validate();) +} + +SkPath::~SkPath() { + SkDEBUGCODE(this->validate();) +} + +SkPath& SkPath::operator=(const SkPath& that) { + SkDEBUGCODE(that.validate();) + + if (this != &that) { + fPathRef.reset(SkRef(that.fPathRef.get())); + this->copyFields(that); +#ifdef SK_BUILD_FOR_ANDROID + fSourcePath = that.fSourcePath; +#endif + } + SkDEBUGCODE(this->validate();) + return *this; +} + +void SkPath::copyFields(const SkPath& that) { + //fPathRef is assumed to have been set by the caller. + fLastMoveToIndex = that.fLastMoveToIndex; + fFillType = that.fFillType; + fConvexity = that.fConvexity; + fDirection = that.fDirection; +} + +bool operator==(const SkPath& a, const SkPath& b) { + // note: don't need to look at isConvex or bounds, since just comparing the + // raw data is sufficient. + return &a == &b || + (a.fFillType == b.fFillType && *a.fPathRef.get() == *b.fPathRef.get()); +} + +void SkPath::swap(SkPath& that) { + SkASSERT(&that != NULL); + + if (this != &that) { + fPathRef.swap(&that.fPathRef); + SkTSwap(fLastMoveToIndex, that.fLastMoveToIndex); + SkTSwap(fFillType, that.fFillType); + SkTSwap(fConvexity, that.fConvexity); + SkTSwap(fDirection, that.fDirection); +#ifdef SK_BUILD_FOR_ANDROID + SkTSwap(fSourcePath, that.fSourcePath); +#endif + } +} + +static inline bool check_edge_against_rect(const SkPoint& p0, + const SkPoint& p1, + const SkRect& rect, + SkPath::Direction dir) { + const SkPoint* edgeBegin; + SkVector v; + if (SkPath::kCW_Direction == dir) { + v = p1 - p0; + edgeBegin = &p0; + } else { + v = p0 - p1; + edgeBegin = &p1; + } + if (v.fX || v.fY) { + // check the cross product of v with the vec from edgeBegin to each rect corner + SkScalar yL = SkScalarMul(v.fY, rect.fLeft - edgeBegin->fX); + SkScalar xT = SkScalarMul(v.fX, rect.fTop - edgeBegin->fY); + SkScalar yR = SkScalarMul(v.fY, rect.fRight - edgeBegin->fX); + SkScalar xB = SkScalarMul(v.fX, rect.fBottom - edgeBegin->fY); + if ((xT < yL) || (xT < yR) || (xB < yL) || (xB < yR)) { + return false; + } + } + return true; +} + +bool SkPath::conservativelyContainsRect(const SkRect& rect) const { + // This only handles non-degenerate convex paths currently. + if (kConvex_Convexity != this->getConvexity()) { + return false; + } + + Direction direction; + if (!this->cheapComputeDirection(&direction)) { + return false; + } + + SkPoint firstPt; + SkPoint prevPt; + RawIter iter(*this); + SkPath::Verb verb; + SkPoint pts[4]; + SkDEBUGCODE(int moveCnt = 0;) + SkDEBUGCODE(int segmentCount = 0;) + SkDEBUGCODE(int closeCount = 0;) + + while ((verb = iter.next(pts)) != kDone_Verb) { + int nextPt = -1; + switch (verb) { + case kMove_Verb: + SkASSERT(!segmentCount && !closeCount); + SkDEBUGCODE(++moveCnt); + firstPt = prevPt = pts[0]; + break; + case kLine_Verb: + nextPt = 1; + SkASSERT(moveCnt && !closeCount); + SkDEBUGCODE(++segmentCount); + break; + case kQuad_Verb: + case kConic_Verb: + SkASSERT(moveCnt && !closeCount); + SkDEBUGCODE(++segmentCount); + nextPt = 2; + break; + case kCubic_Verb: + SkASSERT(moveCnt && !closeCount); + SkDEBUGCODE(++segmentCount); + nextPt = 3; + break; + case kClose_Verb: + SkDEBUGCODE(++closeCount;) + break; + default: + SkDEBUGFAIL("unknown verb"); + } + if (-1 != nextPt) { + if (!check_edge_against_rect(prevPt, pts[nextPt], rect, direction)) { + return false; + } + prevPt = pts[nextPt]; + } + } + + return check_edge_against_rect(prevPt, firstPt, rect, direction); +} + +uint32_t SkPath::getGenerationID() const { + uint32_t genID = fPathRef->genID(); +#ifdef SK_BUILD_FOR_ANDROID + SkASSERT((unsigned)fFillType < (1 << (32 - kPathRefGenIDBitCnt))); + genID |= static_cast(fFillType) << kPathRefGenIDBitCnt; +#endif + return genID; +} + +#ifdef SK_BUILD_FOR_ANDROID +const SkPath* SkPath::getSourcePath() const { + return fSourcePath; +} + +void SkPath::setSourcePath(const SkPath* path) { + fSourcePath = path; +} +#endif + +void SkPath::reset() { + SkDEBUGCODE(this->validate();) + + fPathRef.reset(SkPathRef::CreateEmpty()); + this->resetFields(); +} + +void SkPath::rewind() { + SkDEBUGCODE(this->validate();) + + SkPathRef::Rewind(&fPathRef); + this->resetFields(); +} + +bool SkPath::isLine(SkPoint line[2]) const { + int verbCount = fPathRef->countVerbs(); + + if (2 == verbCount) { + SkASSERT(kMove_Verb == fPathRef->atVerb(0)); + if (kLine_Verb == fPathRef->atVerb(1)) { + SkASSERT(2 == fPathRef->countPoints()); + if (line) { + const SkPoint* pts = fPathRef->points(); + line[0] = pts[0]; + line[1] = pts[1]; + } + return true; + } + } + return false; +} + +/* + Determines if path is a rect by keeping track of changes in direction + and looking for a loop either clockwise or counterclockwise. + + The direction is computed such that: + 0: vertical up + 1: horizontal left + 2: vertical down + 3: horizontal right + +A rectangle cycles up/right/down/left or up/left/down/right. + +The test fails if: + The path is closed, and followed by a line. + A second move creates a new endpoint. + A diagonal line is parsed. + There's more than four changes of direction. + There's a discontinuity on the line (e.g., a move in the middle) + The line reverses direction. + The path contains a quadratic or cubic. + The path contains fewer than four points. + *The rectangle doesn't complete a cycle. + *The final point isn't equal to the first point. + + *These last two conditions we relax if we have a 3-edge path that would + form a rectangle if it were closed (as we do when we fill a path) + +It's OK if the path has: + Several colinear line segments composing a rectangle side. + Single points on the rectangle side. + +The direction takes advantage of the corners found since opposite sides +must travel in opposite directions. + +FIXME: Allow colinear quads and cubics to be treated like lines. +FIXME: If the API passes fill-only, return true if the filled stroke + is a rectangle, though the caller failed to close the path. + + first,last,next direction state-machine: + 0x1 is set if the segment is horizontal + 0x2 is set if the segment is moving to the right or down + thus: + two directions are opposites iff (dirA ^ dirB) == 0x2 + two directions are perpendicular iff (dirA ^ dirB) == 0x1 + + */ +static int rect_make_dir(SkScalar dx, SkScalar dy) { + return ((0 != dx) << 0) | ((dx > 0 || dy > 0) << 1); +} +bool SkPath::isRectContour(bool allowPartial, int* currVerb, const SkPoint** ptsPtr, + bool* isClosed, Direction* direction) const { + int corners = 0; + SkPoint first, last; + const SkPoint* pts = *ptsPtr; + const SkPoint* savePts = NULL; + first.set(0, 0); + last.set(0, 0); + int firstDirection = 0; + int lastDirection = 0; + int nextDirection = 0; + bool closedOrMoved = false; + bool autoClose = false; + int verbCnt = fPathRef->countVerbs(); + while (*currVerb < verbCnt && (!allowPartial || !autoClose)) { + switch (fPathRef->atVerb(*currVerb)) { + case kClose_Verb: + savePts = pts; + pts = *ptsPtr; + autoClose = true; + case kLine_Verb: { + SkScalar left = last.fX; + SkScalar top = last.fY; + SkScalar right = pts->fX; + SkScalar bottom = pts->fY; + ++pts; + if (left != right && top != bottom) { + return false; // diagonal + } + if (left == right && top == bottom) { + break; // single point on side OK + } + nextDirection = rect_make_dir(right - left, bottom - top); + if (0 == corners) { + firstDirection = nextDirection; + first = last; + last = pts[-1]; + corners = 1; + closedOrMoved = false; + break; + } + if (closedOrMoved) { + return false; // closed followed by a line + } + if (autoClose && nextDirection == firstDirection) { + break; // colinear with first + } + closedOrMoved = autoClose; + if (lastDirection != nextDirection) { + if (++corners > 4) { + return false; // too many direction changes + } + } + last = pts[-1]; + if (lastDirection == nextDirection) { + break; // colinear segment + } + // Possible values for corners are 2, 3, and 4. + // When corners == 3, nextDirection opposes firstDirection. + // Otherwise, nextDirection at corner 2 opposes corner 4. + int turn = firstDirection ^ (corners - 1); + int directionCycle = 3 == corners ? 0 : nextDirection ^ turn; + if ((directionCycle ^ turn) != nextDirection) { + return false; // direction didn't follow cycle + } + break; + } + case kQuad_Verb: + case kConic_Verb: + case kCubic_Verb: + return false; // quadratic, cubic not allowed + case kMove_Verb: + last = *pts++; + closedOrMoved = true; + break; + default: + SkDEBUGFAIL("unexpected verb"); + break; + } + *currVerb += 1; + lastDirection = nextDirection; + } + // Success if 4 corners and first point equals last + bool result = 4 == corners && (first == last || autoClose); + if (!result) { + // check if we are just an incomplete rectangle, in which case we can + // return true, but not claim to be closed. + // e.g. + // 3 sided rectangle + // 4 sided but the last edge is not long enough to reach the start + // + SkScalar closeX = first.x() - last.x(); + SkScalar closeY = first.y() - last.y(); + if (closeX && closeY) { + return false; // we're diagonal, abort (can we ever reach this?) + } + int closeDirection = rect_make_dir(closeX, closeY); + // make sure the close-segment doesn't double-back on itself + if (3 == corners || (4 == corners && closeDirection == lastDirection)) { + result = true; + autoClose = false; // we are not closed + } + } + if (savePts) { + *ptsPtr = savePts; + } + if (result && isClosed) { + *isClosed = autoClose; + } + if (result && direction) { + *direction = firstDirection == ((lastDirection + 1) & 3) ? kCCW_Direction : kCW_Direction; + } + return result; +} + +SkPath::PathAsRect SkPath::asRect(Direction* direction) const { + SK_COMPILE_ASSERT(0 == kNone_PathAsRect, path_as_rect_mismatch); + SK_COMPILE_ASSERT(1 == kFill_PathAsRect, path_as_rect_mismatch); + SK_COMPILE_ASSERT(2 == kStroke_PathAsRect, path_as_rect_mismatch); + bool isClosed = false; + return (PathAsRect) (isRect(&isClosed, direction) + isClosed); +} + +bool SkPath::isRect(SkRect* rect) const { + SkDEBUGCODE(this->validate();) + int currVerb = 0; + const SkPoint* pts = fPathRef->points(); + bool result = isRectContour(false, &currVerb, &pts, NULL, NULL); + if (result && rect) { + *rect = getBounds(); + } + return result; +} + +bool SkPath::isRect(bool* isClosed, Direction* direction) const { + SkDEBUGCODE(this->validate();) + int currVerb = 0; + const SkPoint* pts = fPathRef->points(); + return isRectContour(false, &currVerb, &pts, isClosed, direction); +} + +bool SkPath::isNestedRects(SkRect rects[2], Direction dirs[2]) const { + SkDEBUGCODE(this->validate();) + int currVerb = 0; + const SkPoint* pts = fPathRef->points(); + const SkPoint* first = pts; + Direction testDirs[2]; + if (!isRectContour(true, &currVerb, &pts, NULL, &testDirs[0])) { + return false; + } + const SkPoint* last = pts; + SkRect testRects[2]; + if (isRectContour(false, &currVerb, &pts, NULL, &testDirs[1])) { + testRects[0].set(first, SkToS32(last - first)); + testRects[1].set(last, SkToS32(pts - last)); + if (testRects[0].contains(testRects[1])) { + if (rects) { + rects[0] = testRects[0]; + rects[1] = testRects[1]; + } + if (dirs) { + dirs[0] = testDirs[0]; + dirs[1] = testDirs[1]; + } + return true; + } + if (testRects[1].contains(testRects[0])) { + if (rects) { + rects[0] = testRects[1]; + rects[1] = testRects[0]; + } + if (dirs) { + dirs[0] = testDirs[1]; + dirs[1] = testDirs[0]; + } + return true; + } + } + return false; +} + +int SkPath::countPoints() const { + return fPathRef->countPoints(); +} + +int SkPath::getPoints(SkPoint dst[], int max) const { + SkDEBUGCODE(this->validate();) + + SkASSERT(max >= 0); + SkASSERT(!max || dst); + int count = SkMin32(max, fPathRef->countPoints()); + memcpy(dst, fPathRef->points(), count * sizeof(SkPoint)); + return fPathRef->countPoints(); +} + +SkPoint SkPath::getPoint(int index) const { + if ((unsigned)index < (unsigned)fPathRef->countPoints()) { + return fPathRef->atPoint(index); + } + return SkPoint::Make(0, 0); +} + +int SkPath::countVerbs() const { + return fPathRef->countVerbs(); +} + +static inline void copy_verbs_reverse(uint8_t* inorderDst, + const uint8_t* reversedSrc, + int count) { + for (int i = 0; i < count; ++i) { + inorderDst[i] = reversedSrc[~i]; + } +} + +int SkPath::getVerbs(uint8_t dst[], int max) const { + SkDEBUGCODE(this->validate();) + + SkASSERT(max >= 0); + SkASSERT(!max || dst); + int count = SkMin32(max, fPathRef->countVerbs()); + copy_verbs_reverse(dst, fPathRef->verbs(), count); + return fPathRef->countVerbs(); +} + +bool SkPath::getLastPt(SkPoint* lastPt) const { + SkDEBUGCODE(this->validate();) + + int count = fPathRef->countPoints(); + if (count > 0) { + if (lastPt) { + *lastPt = fPathRef->atPoint(count - 1); + } + return true; + } + if (lastPt) { + lastPt->set(0, 0); + } + return false; +} + +void SkPath::setLastPt(SkScalar x, SkScalar y) { + SkDEBUGCODE(this->validate();) + + int count = fPathRef->countPoints(); + if (count == 0) { + this->moveTo(x, y); + } else { + SkPathRef::Editor ed(&fPathRef); + ed.atPoint(count-1)->set(x, y); + } +} + +void SkPath::setConvexity(Convexity c) { + if (fConvexity != c) { + fConvexity = c; + } +} + +////////////////////////////////////////////////////////////////////////////// +// Construction methods + +#define DIRTY_AFTER_EDIT \ + do { \ + fConvexity = kUnknown_Convexity; \ + fDirection = kUnknown_Direction; \ + } while (0) + +void SkPath::incReserve(U16CPU inc) { + SkDEBUGCODE(this->validate();) + SkPathRef::Editor(&fPathRef, inc, inc); + SkDEBUGCODE(this->validate();) +} + +void SkPath::moveTo(SkScalar x, SkScalar y) { + SkDEBUGCODE(this->validate();) + + SkPathRef::Editor ed(&fPathRef); + + // remember our index + fLastMoveToIndex = fPathRef->countPoints(); + + ed.growForVerb(kMove_Verb)->set(x, y); +} + +void SkPath::rMoveTo(SkScalar x, SkScalar y) { + SkPoint pt; + this->getLastPt(&pt); + this->moveTo(pt.fX + x, pt.fY + y); +} + +void SkPath::injectMoveToIfNeeded() { + if (fLastMoveToIndex < 0) { + SkScalar x, y; + if (fPathRef->countVerbs() == 0) { + x = y = 0; + } else { + const SkPoint& pt = fPathRef->atPoint(~fLastMoveToIndex); + x = pt.fX; + y = pt.fY; + } + this->moveTo(x, y); + } +} + +void SkPath::lineTo(SkScalar x, SkScalar y) { + SkDEBUGCODE(this->validate();) + + this->injectMoveToIfNeeded(); + + SkPathRef::Editor ed(&fPathRef); + ed.growForVerb(kLine_Verb)->set(x, y); + + DIRTY_AFTER_EDIT; +} + +void SkPath::rLineTo(SkScalar x, SkScalar y) { + this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt(). + SkPoint pt; + this->getLastPt(&pt); + this->lineTo(pt.fX + x, pt.fY + y); +} + +void SkPath::quadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) { + SkDEBUGCODE(this->validate();) + + this->injectMoveToIfNeeded(); + + SkPathRef::Editor ed(&fPathRef); + SkPoint* pts = ed.growForVerb(kQuad_Verb); + pts[0].set(x1, y1); + pts[1].set(x2, y2); + + DIRTY_AFTER_EDIT; +} + +void SkPath::rQuadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) { + this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt(). + SkPoint pt; + this->getLastPt(&pt); + this->quadTo(pt.fX + x1, pt.fY + y1, pt.fX + x2, pt.fY + y2); +} + +void SkPath::conicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2, + SkScalar w) { + // check for <= 0 or NaN with this test + if (!(w > 0)) { + this->lineTo(x2, y2); + } else if (!SkScalarIsFinite(w)) { + this->lineTo(x1, y1); + this->lineTo(x2, y2); + } else if (SK_Scalar1 == w) { + this->quadTo(x1, y1, x2, y2); + } else { + SkDEBUGCODE(this->validate();) + + this->injectMoveToIfNeeded(); + + SkPathRef::Editor ed(&fPathRef); + SkPoint* pts = ed.growForVerb(kConic_Verb, w); + pts[0].set(x1, y1); + pts[1].set(x2, y2); + + DIRTY_AFTER_EDIT; + } +} + +void SkPath::rConicTo(SkScalar dx1, SkScalar dy1, SkScalar dx2, SkScalar dy2, + SkScalar w) { + this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt(). + SkPoint pt; + this->getLastPt(&pt); + this->conicTo(pt.fX + dx1, pt.fY + dy1, pt.fX + dx2, pt.fY + dy2, w); +} + +void SkPath::cubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2, + SkScalar x3, SkScalar y3) { + SkDEBUGCODE(this->validate();) + + this->injectMoveToIfNeeded(); + + SkPathRef::Editor ed(&fPathRef); + SkPoint* pts = ed.growForVerb(kCubic_Verb); + pts[0].set(x1, y1); + pts[1].set(x2, y2); + pts[2].set(x3, y3); + + DIRTY_AFTER_EDIT; +} + +void SkPath::rCubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2, + SkScalar x3, SkScalar y3) { + this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt(). + SkPoint pt; + this->getLastPt(&pt); + this->cubicTo(pt.fX + x1, pt.fY + y1, pt.fX + x2, pt.fY + y2, + pt.fX + x3, pt.fY + y3); +} + +void SkPath::close() { + SkDEBUGCODE(this->validate();) + + int count = fPathRef->countVerbs(); + if (count > 0) { + switch (fPathRef->atVerb(count - 1)) { + case kLine_Verb: + case kQuad_Verb: + case kConic_Verb: + case kCubic_Verb: + case kMove_Verb: { + SkPathRef::Editor ed(&fPathRef); + ed.growForVerb(kClose_Verb); + break; + } + case kClose_Verb: + // don't add a close if it's the first verb or a repeat + break; + default: + SkDEBUGFAIL("unexpected verb"); + break; + } + } + + // signal that we need a moveTo to follow us (unless we're done) +#if 0 + if (fLastMoveToIndex >= 0) { + fLastMoveToIndex = ~fLastMoveToIndex; + } +#else + fLastMoveToIndex ^= ~fLastMoveToIndex >> (8 * sizeof(fLastMoveToIndex) - 1); +#endif +} + +/////////////////////////////////////////////////////////////////////////////// + +static void assert_known_direction(int dir) { + SkASSERT(SkPath::kCW_Direction == dir || SkPath::kCCW_Direction == dir); +} + +void SkPath::addRect(const SkRect& rect, Direction dir) { + this->addRect(rect.fLeft, rect.fTop, rect.fRight, rect.fBottom, dir); +} + +void SkPath::addRect(SkScalar left, SkScalar top, SkScalar right, + SkScalar bottom, Direction dir) { + assert_known_direction(dir); + fDirection = this->hasOnlyMoveTos() ? dir : kUnknown_Direction; + SkAutoDisableDirectionCheck addc(this); + + SkAutoPathBoundsUpdate apbu(this, left, top, right, bottom); + + this->incReserve(5); + + this->moveTo(left, top); + if (dir == kCCW_Direction) { + this->lineTo(left, bottom); + this->lineTo(right, bottom); + this->lineTo(right, top); + } else { + this->lineTo(right, top); + this->lineTo(right, bottom); + this->lineTo(left, bottom); + } + this->close(); +} + +void SkPath::addPoly(const SkPoint pts[], int count, bool close) { + SkDEBUGCODE(this->validate();) + if (count <= 0) { + return; + } + + fLastMoveToIndex = fPathRef->countPoints(); + + // +close makes room for the extra kClose_Verb + SkPathRef::Editor ed(&fPathRef, count+close, count); + + ed.growForVerb(kMove_Verb)->set(pts[0].fX, pts[0].fY); + if (count > 1) { + SkPoint* p = ed.growForRepeatedVerb(kLine_Verb, count - 1); + memcpy(p, &pts[1], (count-1) * sizeof(SkPoint)); + } + + if (close) { + ed.growForVerb(kClose_Verb); + } + + DIRTY_AFTER_EDIT; + SkDEBUGCODE(this->validate();) +} + +#include "SkGeometry.h" + +static int build_arc_points(const SkRect& oval, SkScalar startAngle, + SkScalar sweepAngle, + SkPoint pts[kSkBuildQuadArcStorage]) { + + if (0 == sweepAngle && + (0 == startAngle || SkIntToScalar(360) == startAngle)) { + // Chrome uses this path to move into and out of ovals. If not + // treated as a special case the moves can distort the oval's + // bounding box (and break the circle special case). + pts[0].set(oval.fRight, oval.centerY()); + return 1; + } else if (0 == oval.width() && 0 == oval.height()) { + // Chrome will sometimes create 0 radius round rects. Having degenerate + // quad segments in the path prevents the path from being recognized as + // a rect. + // TODO: optimizing the case where only one of width or height is zero + // should also be considered. This case, however, doesn't seem to be + // as common as the single point case. + pts[0].set(oval.fRight, oval.fTop); + return 1; + } + + SkVector start, stop; + + start.fY = SkScalarSinCos(SkDegreesToRadians(startAngle), &start.fX); + stop.fY = SkScalarSinCos(SkDegreesToRadians(startAngle + sweepAngle), + &stop.fX); + + /* If the sweep angle is nearly (but less than) 360, then due to precision + loss in radians-conversion and/or sin/cos, we may end up with coincident + vectors, which will fool SkBuildQuadArc into doing nothing (bad) instead + of drawing a nearly complete circle (good). + e.g. canvas.drawArc(0, 359.99, ...) + -vs- canvas.drawArc(0, 359.9, ...) + We try to detect this edge case, and tweak the stop vector + */ + if (start == stop) { + SkScalar sw = SkScalarAbs(sweepAngle); + if (sw < SkIntToScalar(360) && sw > SkIntToScalar(359)) { + SkScalar stopRad = SkDegreesToRadians(startAngle + sweepAngle); + // make a guess at a tiny angle (in radians) to tweak by + SkScalar deltaRad = SkScalarCopySign(SK_Scalar1/512, sweepAngle); + // not sure how much will be enough, so we use a loop + do { + stopRad -= deltaRad; + stop.fY = SkScalarSinCos(stopRad, &stop.fX); + } while (start == stop); + } + } + + SkMatrix matrix; + + matrix.setScale(SkScalarHalf(oval.width()), SkScalarHalf(oval.height())); + matrix.postTranslate(oval.centerX(), oval.centerY()); + + return SkBuildQuadArc(start, stop, + sweepAngle > 0 ? kCW_SkRotationDirection : + kCCW_SkRotationDirection, + &matrix, pts); +} + +void SkPath::addRoundRect(const SkRect& rect, const SkScalar radii[], + Direction dir) { + SkRRect rrect; + rrect.setRectRadii(rect, (const SkVector*) radii); + this->addRRect(rrect, dir); +} + +/* The inline clockwise and counterclockwise round rect quad approximations + make it easier to see the symmetry patterns used by add corner quads. +Clockwise corner value + path->lineTo(rect.fLeft, rect.fTop + ry); 0 upper left + path->quadTo(rect.fLeft, rect.fTop + offPtY, + rect.fLeft + midPtX, rect.fTop + midPtY); + path->quadTo(rect.fLeft + offPtX, rect.fTop, + rect.fLeft + rx, rect.fTop); + + path->lineTo(rect.fRight - rx, rect.fTop); 1 upper right + path->quadTo(rect.fRight - offPtX, rect.fTop, + rect.fRight - midPtX, rect.fTop + midPtY); + path->quadTo(rect.fRight, rect.fTop + offPtY, + rect.fRight, rect.fTop + ry); + + path->lineTo(rect.fRight, rect.fBottom - ry); 2 lower right + path->quadTo(rect.fRight, rect.fBottom - offPtY, + rect.fRight - midPtX, rect.fBottom - midPtY); + path->quadTo(rect.fRight - offPtX, rect.fBottom, + rect.fRight - rx, rect.fBottom); + + path->lineTo(rect.fLeft + rx, rect.fBottom); 3 lower left + path->quadTo(rect.fLeft + offPtX, rect.fBottom, + rect.fLeft + midPtX, rect.fBottom - midPtY); + path->quadTo(rect.fLeft, rect.fBottom - offPtY, + rect.fLeft, rect.fBottom - ry); + +Counterclockwise + path->lineTo(rect.fLeft, rect.fBottom - ry); 3 lower left + path->quadTo(rect.fLeft, rect.fBottom - offPtY, + rect.fLeft + midPtX, rect.fBottom - midPtY); + path->quadTo(rect.fLeft + offPtX, rect.fBottom, + rect.fLeft + rx, rect.fBottom); + + path->lineTo(rect.fRight - rx, rect.fBottom); 2 lower right + path->quadTo(rect.fRight - offPtX, rect.fBottom, + rect.fRight - midPtX, rect.fBottom - midPtY); + path->quadTo(rect.fRight, rect.fBottom - offPtY, + rect.fRight, rect.fBottom - ry); + + path->lineTo(rect.fRight, rect.fTop + ry); 1 upper right + path->quadTo(rect.fRight, rect.fTop + offPtY, + rect.fRight - midPtX, rect.fTop + midPtY); + path->quadTo(rect.fRight - offPtX, rect.fTop, + rect.fRight - rx, rect.fTop); + + path->lineTo(rect.fLeft + rx, rect.fTop); 0 upper left + path->quadTo(rect.fLeft + offPtX, rect.fTop, + rect.fLeft + midPtX, rect.fTop + midPtY); + path->quadTo(rect.fLeft, rect.fTop + offPtY, + rect.fLeft, rect.fTop + ry); +*/ +static void add_corner_quads(SkPath* path, const SkRRect& rrect, + SkRRect::Corner corner, SkPath::Direction dir) { + const SkRect& rect = rrect.rect(); + const SkVector& radii = rrect.radii(corner); + SkScalar rx = radii.fX; + SkScalar ry = radii.fY; + // The mid point of the quadratic arc approximation is half way between the two + // control points. + const SkScalar mid = 1 - (SK_Scalar1 + SK_ScalarTanPIOver8) / 2; + SkScalar midPtX = rx * mid; + SkScalar midPtY = ry * mid; + const SkScalar control = 1 - SK_ScalarTanPIOver8; + SkScalar offPtX = rx * control; + SkScalar offPtY = ry * control; + static const int kCornerPts = 5; + SkScalar xOff[kCornerPts]; + SkScalar yOff[kCornerPts]; + + if ((corner & 1) == (dir == SkPath::kCCW_Direction)) { // corners always alternate direction + SkASSERT(dir == SkPath::kCCW_Direction + ? corner == SkRRect::kLowerLeft_Corner || corner == SkRRect::kUpperRight_Corner + : corner == SkRRect::kUpperLeft_Corner || corner == SkRRect::kLowerRight_Corner); + xOff[0] = xOff[1] = 0; + xOff[2] = midPtX; + xOff[3] = offPtX; + xOff[4] = rx; + yOff[0] = ry; + yOff[1] = offPtY; + yOff[2] = midPtY; + yOff[3] = yOff[4] = 0; + } else { + xOff[0] = rx; + xOff[1] = offPtX; + xOff[2] = midPtX; + xOff[3] = xOff[4] = 0; + yOff[0] = yOff[1] = 0; + yOff[2] = midPtY; + yOff[3] = offPtY; + yOff[4] = ry; + } + if ((corner - 1) & 2) { + SkASSERT(corner == SkRRect::kLowerLeft_Corner || corner == SkRRect::kUpperLeft_Corner); + for (int i = 0; i < kCornerPts; ++i) { + xOff[i] = rect.fLeft + xOff[i]; + } + } else { + SkASSERT(corner == SkRRect::kLowerRight_Corner || corner == SkRRect::kUpperRight_Corner); + for (int i = 0; i < kCornerPts; ++i) { + xOff[i] = rect.fRight - xOff[i]; + } + } + if (corner < SkRRect::kLowerRight_Corner) { + for (int i = 0; i < kCornerPts; ++i) { + yOff[i] = rect.fTop + yOff[i]; + } + } else { + for (int i = 0; i < kCornerPts; ++i) { + yOff[i] = rect.fBottom - yOff[i]; + } + } + + SkPoint lastPt; + SkAssertResult(path->getLastPt(&lastPt)); + if (lastPt.fX != xOff[0] || lastPt.fY != yOff[0]) { + path->lineTo(xOff[0], yOff[0]); + } + if (rx || ry) { + path->quadTo(xOff[1], yOff[1], xOff[2], yOff[2]); + path->quadTo(xOff[3], yOff[3], xOff[4], yOff[4]); + } else { + path->lineTo(xOff[2], yOff[2]); + path->lineTo(xOff[4], yOff[4]); + } +} + +void SkPath::addRRect(const SkRRect& rrect, Direction dir) { + assert_known_direction(dir); + + if (rrect.isEmpty()) { + return; + } + + const SkRect& bounds = rrect.getBounds(); + + if (rrect.isRect()) { + this->addRect(bounds, dir); + } else if (rrect.isOval()) { + this->addOval(bounds, dir); +#ifdef SK_IGNORE_QUAD_RR_CORNERS_OPT + } else if (rrect.isSimple()) { + const SkVector& rad = rrect.getSimpleRadii(); + this->addRoundRect(bounds, rad.x(), rad.y(), dir); +#endif + } else { + fDirection = this->hasOnlyMoveTos() ? dir : kUnknown_Direction; + + SkAutoPathBoundsUpdate apbu(this, bounds); + SkAutoDisableDirectionCheck addc(this); + + this->incReserve(21); + if (kCW_Direction == dir) { + this->moveTo(bounds.fLeft, + bounds.fBottom - rrect.fRadii[SkRRect::kLowerLeft_Corner].fY); + add_corner_quads(this, rrect, SkRRect::kUpperLeft_Corner, dir); + add_corner_quads(this, rrect, SkRRect::kUpperRight_Corner, dir); + add_corner_quads(this, rrect, SkRRect::kLowerRight_Corner, dir); + add_corner_quads(this, rrect, SkRRect::kLowerLeft_Corner, dir); + } else { + this->moveTo(bounds.fLeft, + bounds.fTop + rrect.fRadii[SkRRect::kUpperLeft_Corner].fY); + add_corner_quads(this, rrect, SkRRect::kLowerLeft_Corner, dir); + add_corner_quads(this, rrect, SkRRect::kLowerRight_Corner, dir); + add_corner_quads(this, rrect, SkRRect::kUpperRight_Corner, dir); + add_corner_quads(this, rrect, SkRRect::kUpperLeft_Corner, dir); + } + this->close(); + } +} + +bool SkPath::hasOnlyMoveTos() const { + int count = fPathRef->countVerbs(); + const uint8_t* verbs = const_cast(fPathRef.get())->verbsMemBegin(); + for (int i = 0; i < count; ++i) { + if (*verbs == kLine_Verb || + *verbs == kQuad_Verb || + *verbs == kConic_Verb || + *verbs == kCubic_Verb) { + return false; + } + ++verbs; + } + return true; +} + +#ifdef SK_IGNORE_QUAD_RR_CORNERS_OPT +#define CUBIC_ARC_FACTOR ((SK_ScalarSqrt2 - SK_Scalar1) * 4 / 3) +#endif + +void SkPath::addRoundRect(const SkRect& rect, SkScalar rx, SkScalar ry, + Direction dir) { + assert_known_direction(dir); + + if (rx < 0 || ry < 0) { + SkErrorInternals::SetError( kInvalidArgument_SkError, + "I got %f and %f as radii to SkPath::AddRoundRect, " + "but negative radii are not allowed.", + SkScalarToDouble(rx), SkScalarToDouble(ry) ); + return; + } + +#ifdef SK_IGNORE_QUAD_RR_CORNERS_OPT + SkScalar w = rect.width(); + SkScalar halfW = SkScalarHalf(w); + SkScalar h = rect.height(); + SkScalar halfH = SkScalarHalf(h); + + if (halfW <= 0 || halfH <= 0) { + return; + } + + bool skip_hori = rx >= halfW; + bool skip_vert = ry >= halfH; + + if (skip_hori && skip_vert) { + this->addOval(rect, dir); + return; + } + + fDirection = this->hasOnlyMoveTos() ? dir : kUnknown_Direction; + + SkAutoPathBoundsUpdate apbu(this, rect); + SkAutoDisableDirectionCheck addc(this); + + if (skip_hori) { + rx = halfW; + } else if (skip_vert) { + ry = halfH; + } + SkScalar sx = SkScalarMul(rx, CUBIC_ARC_FACTOR); + SkScalar sy = SkScalarMul(ry, CUBIC_ARC_FACTOR); + + this->incReserve(17); + this->moveTo(rect.fRight - rx, rect.fTop); // top-right + if (dir == kCCW_Direction) { + if (!skip_hori) { + this->lineTo(rect.fLeft + rx, rect.fTop); // top + } + this->cubicTo(rect.fLeft + rx - sx, rect.fTop, + rect.fLeft, rect.fTop + ry - sy, + rect.fLeft, rect.fTop + ry); // top-left + if (!skip_vert) { + this->lineTo(rect.fLeft, rect.fBottom - ry); // left + } + this->cubicTo(rect.fLeft, rect.fBottom - ry + sy, + rect.fLeft + rx - sx, rect.fBottom, + rect.fLeft + rx, rect.fBottom); // bot-left + if (!skip_hori) { + this->lineTo(rect.fRight - rx, rect.fBottom); // bottom + } + this->cubicTo(rect.fRight - rx + sx, rect.fBottom, + rect.fRight, rect.fBottom - ry + sy, + rect.fRight, rect.fBottom - ry); // bot-right + if (!skip_vert) { + this->lineTo(rect.fRight, rect.fTop + ry); // right + } + this->cubicTo(rect.fRight, rect.fTop + ry - sy, + rect.fRight - rx + sx, rect.fTop, + rect.fRight - rx, rect.fTop); // top-right + } else { + this->cubicTo(rect.fRight - rx + sx, rect.fTop, + rect.fRight, rect.fTop + ry - sy, + rect.fRight, rect.fTop + ry); // top-right + if (!skip_vert) { + this->lineTo(rect.fRight, rect.fBottom - ry); // right + } + this->cubicTo(rect.fRight, rect.fBottom - ry + sy, + rect.fRight - rx + sx, rect.fBottom, + rect.fRight - rx, rect.fBottom); // bot-right + if (!skip_hori) { + this->lineTo(rect.fLeft + rx, rect.fBottom); // bottom + } + this->cubicTo(rect.fLeft + rx - sx, rect.fBottom, + rect.fLeft, rect.fBottom - ry + sy, + rect.fLeft, rect.fBottom - ry); // bot-left + if (!skip_vert) { + this->lineTo(rect.fLeft, rect.fTop + ry); // left + } + this->cubicTo(rect.fLeft, rect.fTop + ry - sy, + rect.fLeft + rx - sx, rect.fTop, + rect.fLeft + rx, rect.fTop); // top-left + if (!skip_hori) { + this->lineTo(rect.fRight - rx, rect.fTop); // top + } + } + this->close(); +#else + SkRRect rrect; + rrect.setRectXY(rect, rx, ry); + this->addRRect(rrect, dir); +#endif +} + +void SkPath::addOval(const SkRect& oval, Direction dir) { + assert_known_direction(dir); + + /* If addOval() is called after previous moveTo(), + this path is still marked as an oval. This is used to + fit into WebKit's calling sequences. + We can't simply check isEmpty() in this case, as additional + moveTo() would mark the path non empty. + */ + bool isOval = hasOnlyMoveTos(); + if (isOval) { + fDirection = dir; + } else { + fDirection = kUnknown_Direction; + } + + SkAutoDisableDirectionCheck addc(this); + + SkAutoPathBoundsUpdate apbu(this, oval); + + SkScalar cx = oval.centerX(); + SkScalar cy = oval.centerY(); + SkScalar rx = SkScalarHalf(oval.width()); + SkScalar ry = SkScalarHalf(oval.height()); + + SkScalar sx = SkScalarMul(rx, SK_ScalarTanPIOver8); + SkScalar sy = SkScalarMul(ry, SK_ScalarTanPIOver8); + SkScalar mx = SkScalarMul(rx, SK_ScalarRoot2Over2); + SkScalar my = SkScalarMul(ry, SK_ScalarRoot2Over2); + + /* + To handle imprecision in computing the center and radii, we revert to + the provided bounds when we can (i.e. use oval.fLeft instead of cx-rx) + to ensure that we don't exceed the oval's bounds *ever*, since we want + to use oval for our fast-bounds, rather than have to recompute it. + */ + const SkScalar L = oval.fLeft; // cx - rx + const SkScalar T = oval.fTop; // cy - ry + const SkScalar R = oval.fRight; // cx + rx + const SkScalar B = oval.fBottom; // cy + ry + + this->incReserve(17); // 8 quads + close + this->moveTo(R, cy); + if (dir == kCCW_Direction) { + this->quadTo( R, cy - sy, cx + mx, cy - my); + this->quadTo(cx + sx, T, cx , T); + this->quadTo(cx - sx, T, cx - mx, cy - my); + this->quadTo( L, cy - sy, L, cy ); + this->quadTo( L, cy + sy, cx - mx, cy + my); + this->quadTo(cx - sx, B, cx , B); + this->quadTo(cx + sx, B, cx + mx, cy + my); + this->quadTo( R, cy + sy, R, cy ); + } else { + this->quadTo( R, cy + sy, cx + mx, cy + my); + this->quadTo(cx + sx, B, cx , B); + this->quadTo(cx - sx, B, cx - mx, cy + my); + this->quadTo( L, cy + sy, L, cy ); + this->quadTo( L, cy - sy, cx - mx, cy - my); + this->quadTo(cx - sx, T, cx , T); + this->quadTo(cx + sx, T, cx + mx, cy - my); + this->quadTo( R, cy - sy, R, cy ); + } + this->close(); + + SkPathRef::Editor ed(&fPathRef); + + ed.setIsOval(isOval); +} + +void SkPath::addCircle(SkScalar x, SkScalar y, SkScalar r, Direction dir) { + if (r > 0) { + SkRect rect; + rect.set(x - r, y - r, x + r, y + r); + this->addOval(rect, dir); + } +} + +void SkPath::arcTo(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle, + bool forceMoveTo) { + if (oval.width() < 0 || oval.height() < 0) { + return; + } + + SkPoint pts[kSkBuildQuadArcStorage]; + int count = build_arc_points(oval, startAngle, sweepAngle, pts); + SkASSERT((count & 1) == 1); + + if (fPathRef->countVerbs() == 0) { + forceMoveTo = true; + } + this->incReserve(count); + forceMoveTo ? this->moveTo(pts[0]) : this->lineTo(pts[0]); + for (int i = 1; i < count; i += 2) { + this->quadTo(pts[i], pts[i+1]); + } +} + +void SkPath::addArc(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle) { + if (oval.isEmpty() || 0 == sweepAngle) { + return; + } + + const SkScalar kFullCircleAngle = SkIntToScalar(360); + + if (sweepAngle >= kFullCircleAngle || sweepAngle <= -kFullCircleAngle) { + this->addOval(oval, sweepAngle > 0 ? kCW_Direction : kCCW_Direction); + return; + } + + SkPoint pts[kSkBuildQuadArcStorage]; + int count = build_arc_points(oval, startAngle, sweepAngle, pts); + + SkDEBUGCODE(this->validate();) + SkASSERT(count & 1); + + fLastMoveToIndex = fPathRef->countPoints(); + + SkPathRef::Editor ed(&fPathRef, 1+(count-1)/2, count); + + ed.growForVerb(kMove_Verb)->set(pts[0].fX, pts[0].fY); + if (count > 1) { + SkPoint* p = ed.growForRepeatedVerb(kQuad_Verb, (count-1)/2); + memcpy(p, &pts[1], (count-1) * sizeof(SkPoint)); + } + + DIRTY_AFTER_EDIT; + SkDEBUGCODE(this->validate();) +} + +/* + Need to handle the case when the angle is sharp, and our computed end-points + for the arc go behind pt1 and/or p2... +*/ +void SkPath::arcTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2, + SkScalar radius) { + SkVector before, after; + + // need to know our prev pt so we can construct tangent vectors + { + SkPoint start; + this->getLastPt(&start); + // Handle degenerate cases by adding a line to the first point and + // bailing out. + if ((x1 == start.fX && y1 == start.fY) || + (x1 == x2 && y1 == y2) || + radius == 0) { + this->lineTo(x1, y1); + return; + } + before.setNormalize(x1 - start.fX, y1 - start.fY); + after.setNormalize(x2 - x1, y2 - y1); + } + + SkScalar cosh = SkPoint::DotProduct(before, after); + SkScalar sinh = SkPoint::CrossProduct(before, after); + + if (SkScalarNearlyZero(sinh)) { // angle is too tight + this->lineTo(x1, y1); + return; + } + + SkScalar dist = SkScalarMulDiv(radius, SK_Scalar1 - cosh, sinh); + if (dist < 0) { + dist = -dist; + } + + SkScalar xx = x1 - SkScalarMul(dist, before.fX); + SkScalar yy = y1 - SkScalarMul(dist, before.fY); + SkRotationDirection arcDir; + + // now turn before/after into normals + if (sinh > 0) { + before.rotateCCW(); + after.rotateCCW(); + arcDir = kCW_SkRotationDirection; + } else { + before.rotateCW(); + after.rotateCW(); + arcDir = kCCW_SkRotationDirection; + } + + SkMatrix matrix; + SkPoint pts[kSkBuildQuadArcStorage]; + + matrix.setScale(radius, radius); + matrix.postTranslate(xx - SkScalarMul(radius, before.fX), + yy - SkScalarMul(radius, before.fY)); + + int count = SkBuildQuadArc(before, after, arcDir, &matrix, pts); + + this->incReserve(count); + // [xx,yy] == pts[0] + this->lineTo(xx, yy); + for (int i = 1; i < count; i += 2) { + this->quadTo(pts[i], pts[i+1]); + } +} + +/////////////////////////////////////////////////////////////////////////////// + +void SkPath::addPath(const SkPath& path, SkScalar dx, SkScalar dy, AddPathMode mode) { + SkMatrix matrix; + + matrix.setTranslate(dx, dy); + this->addPath(path, matrix, mode); +} + +void SkPath::addPath(const SkPath& path, const SkMatrix& matrix, AddPathMode mode) { + SkPathRef::Editor(&fPathRef, path.countVerbs(), path.countPoints()); + + RawIter iter(path); + SkPoint pts[4]; + Verb verb; + + SkMatrix::MapPtsProc proc = matrix.getMapPtsProc(); + bool firstVerb = true; + while ((verb = iter.next(pts)) != kDone_Verb) { + switch (verb) { + case kMove_Verb: + proc(matrix, &pts[0], &pts[0], 1); + if (firstVerb && mode == kExtend_AddPathMode && !isEmpty()) { + injectMoveToIfNeeded(); // In case last contour is closed + this->lineTo(pts[0]); + } else { + this->moveTo(pts[0]); + } + break; + case kLine_Verb: + proc(matrix, &pts[1], &pts[1], 1); + this->lineTo(pts[1]); + break; + case kQuad_Verb: + proc(matrix, &pts[1], &pts[1], 2); + this->quadTo(pts[1], pts[2]); + break; + case kConic_Verb: + proc(matrix, &pts[1], &pts[1], 2); + this->conicTo(pts[1], pts[2], iter.conicWeight()); + break; + case kCubic_Verb: + proc(matrix, &pts[1], &pts[1], 3); + this->cubicTo(pts[1], pts[2], pts[3]); + break; + case kClose_Verb: + this->close(); + break; + default: + SkDEBUGFAIL("unknown verb"); + } + firstVerb = false; + } +} + +/////////////////////////////////////////////////////////////////////////////// + +static int pts_in_verb(unsigned verb) { + static const uint8_t gPtsInVerb[] = { + 1, // kMove + 1, // kLine + 2, // kQuad + 2, // kConic + 3, // kCubic + 0, // kClose + 0 // kDone + }; + + SkASSERT(verb < SK_ARRAY_COUNT(gPtsInVerb)); + return gPtsInVerb[verb]; +} + +// ignore the last point of the 1st contour +void SkPath::reversePathTo(const SkPath& path) { + int i, vcount = path.fPathRef->countVerbs(); + // exit early if the path is empty, or just has a moveTo. + if (vcount < 2) { + return; + } + + SkPathRef::Editor(&fPathRef, vcount, path.countPoints()); + + const uint8_t* verbs = path.fPathRef->verbs(); + const SkPoint* pts = path.fPathRef->points(); + const SkScalar* conicWeights = path.fPathRef->conicWeights(); + + SkASSERT(verbs[~0] == kMove_Verb); + for (i = 1; i < vcount; ++i) { + unsigned v = verbs[~i]; + int n = pts_in_verb(v); + if (n == 0) { + break; + } + pts += n; + conicWeights += (SkPath::kConic_Verb == v); + } + + while (--i > 0) { + switch (verbs[~i]) { + case kLine_Verb: + this->lineTo(pts[-1].fX, pts[-1].fY); + break; + case kQuad_Verb: + this->quadTo(pts[-1].fX, pts[-1].fY, pts[-2].fX, pts[-2].fY); + break; + case kConic_Verb: + this->conicTo(pts[-1], pts[-2], *--conicWeights); + break; + case kCubic_Verb: + this->cubicTo(pts[-1].fX, pts[-1].fY, pts[-2].fX, pts[-2].fY, + pts[-3].fX, pts[-3].fY); + break; + default: + SkDEBUGFAIL("bad verb"); + break; + } + pts -= pts_in_verb(verbs[~i]); + } +} + +void SkPath::reverseAddPath(const SkPath& src) { + SkPathRef::Editor ed(&fPathRef, src.fPathRef->countPoints(), src.fPathRef->countVerbs()); + + const SkPoint* pts = src.fPathRef->pointsEnd(); + // we will iterator through src's verbs backwards + const uint8_t* verbs = src.fPathRef->verbsMemBegin(); // points at the last verb + const uint8_t* verbsEnd = src.fPathRef->verbs(); // points just past the first verb + const SkScalar* conicWeights = src.fPathRef->conicWeightsEnd(); + + bool needMove = true; + bool needClose = false; + while (verbs < verbsEnd) { + uint8_t v = *(verbs++); + int n = pts_in_verb(v); + + if (needMove) { + --pts; + this->moveTo(pts->fX, pts->fY); + needMove = false; + } + pts -= n; + switch (v) { + case kMove_Verb: + if (needClose) { + this->close(); + needClose = false; + } + needMove = true; + pts += 1; // so we see the point in "if (needMove)" above + break; + case kLine_Verb: + this->lineTo(pts[0]); + break; + case kQuad_Verb: + this->quadTo(pts[1], pts[0]); + break; + case kConic_Verb: + this->conicTo(pts[1], pts[0], *--conicWeights); + break; + case kCubic_Verb: + this->cubicTo(pts[2], pts[1], pts[0]); + break; + case kClose_Verb: + needClose = true; + break; + default: + SkDEBUGFAIL("unexpected verb"); + } + } +} + +/////////////////////////////////////////////////////////////////////////////// + +void SkPath::offset(SkScalar dx, SkScalar dy, SkPath* dst) const { + SkMatrix matrix; + + matrix.setTranslate(dx, dy); + this->transform(matrix, dst); +} + +#include "SkGeometry.h" + +static void subdivide_quad_to(SkPath* path, const SkPoint pts[3], + int level = 2) { + if (--level >= 0) { + SkPoint tmp[5]; + + SkChopQuadAtHalf(pts, tmp); + subdivide_quad_to(path, &tmp[0], level); + subdivide_quad_to(path, &tmp[2], level); + } else { + path->quadTo(pts[1], pts[2]); + } +} + +static void subdivide_cubic_to(SkPath* path, const SkPoint pts[4], + int level = 2) { + if (--level >= 0) { + SkPoint tmp[7]; + + SkChopCubicAtHalf(pts, tmp); + subdivide_cubic_to(path, &tmp[0], level); + subdivide_cubic_to(path, &tmp[3], level); + } else { + path->cubicTo(pts[1], pts[2], pts[3]); + } +} + +void SkPath::transform(const SkMatrix& matrix, SkPath* dst) const { + SkDEBUGCODE(this->validate();) + if (dst == NULL) { + dst = (SkPath*)this; + } + + if (matrix.hasPerspective()) { + SkPath tmp; + tmp.fFillType = fFillType; + + SkPath::Iter iter(*this, false); + SkPoint pts[4]; + SkPath::Verb verb; + + while ((verb = iter.next(pts, false)) != kDone_Verb) { + switch (verb) { + case kMove_Verb: + tmp.moveTo(pts[0]); + break; + case kLine_Verb: + tmp.lineTo(pts[1]); + break; + case kQuad_Verb: + subdivide_quad_to(&tmp, pts); + break; + case kConic_Verb: + SkDEBUGFAIL("TODO: compute new weight"); + tmp.conicTo(pts[1], pts[2], iter.conicWeight()); + break; + case kCubic_Verb: + subdivide_cubic_to(&tmp, pts); + break; + case kClose_Verb: + tmp.close(); + break; + default: + SkDEBUGFAIL("unknown verb"); + break; + } + } + + dst->swap(tmp); + SkPathRef::Editor ed(&dst->fPathRef); + matrix.mapPoints(ed.points(), ed.pathRef()->countPoints()); + dst->fDirection = kUnknown_Direction; + } else { + SkPathRef::CreateTransformedCopy(&dst->fPathRef, *fPathRef.get(), matrix); + + if (this != dst) { + dst->fFillType = fFillType; + dst->fConvexity = fConvexity; + } + + if (kUnknown_Direction == fDirection) { + dst->fDirection = kUnknown_Direction; + } else { + SkScalar det2x2 = + SkScalarMul(matrix.get(SkMatrix::kMScaleX), matrix.get(SkMatrix::kMScaleY)) - + SkScalarMul(matrix.get(SkMatrix::kMSkewX), matrix.get(SkMatrix::kMSkewY)); + if (det2x2 < 0) { + dst->fDirection = SkPath::OppositeDirection(static_cast(fDirection)); + } else if (det2x2 > 0) { + dst->fDirection = fDirection; + } else { + dst->fConvexity = kUnknown_Convexity; + dst->fDirection = kUnknown_Direction; + } + } + + SkDEBUGCODE(dst->validate();) + } +} + +/////////////////////////////////////////////////////////////////////////////// +/////////////////////////////////////////////////////////////////////////////// + +enum SegmentState { + kEmptyContour_SegmentState, // The current contour is empty. We may be + // starting processing or we may have just + // closed a contour. + kAfterMove_SegmentState, // We have seen a move, but nothing else. + kAfterPrimitive_SegmentState // We have seen a primitive but not yet + // closed the path. Also the initial state. +}; + +SkPath::Iter::Iter() { +#ifdef SK_DEBUG + fPts = NULL; + fConicWeights = NULL; + fMoveTo.fX = fMoveTo.fY = fLastPt.fX = fLastPt.fY = 0; + fForceClose = fCloseLine = false; + fSegmentState = kEmptyContour_SegmentState; +#endif + // need to init enough to make next() harmlessly return kDone_Verb + fVerbs = NULL; + fVerbStop = NULL; + fNeedClose = false; +} + +SkPath::Iter::Iter(const SkPath& path, bool forceClose) { + this->setPath(path, forceClose); +} + +void SkPath::Iter::setPath(const SkPath& path, bool forceClose) { + fPts = path.fPathRef->points(); + fVerbs = path.fPathRef->verbs(); + fVerbStop = path.fPathRef->verbsMemBegin(); + fConicWeights = path.fPathRef->conicWeights() - 1; // begin one behind + fLastPt.fX = fLastPt.fY = 0; + fMoveTo.fX = fMoveTo.fY = 0; + fForceClose = SkToU8(forceClose); + fNeedClose = false; + fSegmentState = kEmptyContour_SegmentState; +} + +bool SkPath::Iter::isClosedContour() const { + if (fVerbs == NULL || fVerbs == fVerbStop) { + return false; + } + if (fForceClose) { + return true; + } + + const uint8_t* verbs = fVerbs; + const uint8_t* stop = fVerbStop; + + if (kMove_Verb == *(verbs - 1)) { + verbs -= 1; // skip the initial moveto + } + + while (verbs > stop) { + // verbs points one beyond the current verb, decrement first. + unsigned v = *(--verbs); + if (kMove_Verb == v) { + break; + } + if (kClose_Verb == v) { + return true; + } + } + return false; +} + +SkPath::Verb SkPath::Iter::autoClose(SkPoint pts[2]) { + SkASSERT(pts); + if (fLastPt != fMoveTo) { + // A special case: if both points are NaN, SkPoint::operation== returns + // false, but the iterator expects that they are treated as the same. + // (consider SkPoint is a 2-dimension float point). + if (SkScalarIsNaN(fLastPt.fX) || SkScalarIsNaN(fLastPt.fY) || + SkScalarIsNaN(fMoveTo.fX) || SkScalarIsNaN(fMoveTo.fY)) { + return kClose_Verb; + } + + pts[0] = fLastPt; + pts[1] = fMoveTo; + fLastPt = fMoveTo; + fCloseLine = true; + return kLine_Verb; + } else { + pts[0] = fMoveTo; + return kClose_Verb; + } +} + +const SkPoint& SkPath::Iter::cons_moveTo() { + if (fSegmentState == kAfterMove_SegmentState) { + // Set the first return pt to the move pt + fSegmentState = kAfterPrimitive_SegmentState; + return fMoveTo; + } else { + SkASSERT(fSegmentState == kAfterPrimitive_SegmentState); + // Set the first return pt to the last pt of the previous primitive. + return fPts[-1]; + } +} + +void SkPath::Iter::consumeDegenerateSegments() { + // We need to step over anything that will not move the current draw point + // forward before the next move is seen + const uint8_t* lastMoveVerb = 0; + const SkPoint* lastMovePt = 0; + SkPoint lastPt = fLastPt; + while (fVerbs != fVerbStop) { + unsigned verb = *(fVerbs - 1); // fVerbs is one beyond the current verb + switch (verb) { + case kMove_Verb: + // Keep a record of this most recent move + lastMoveVerb = fVerbs; + lastMovePt = fPts; + lastPt = fPts[0]; + fVerbs--; + fPts++; + break; + + case kClose_Verb: + // A close when we are in a segment is always valid except when it + // follows a move which follows a segment. + if (fSegmentState == kAfterPrimitive_SegmentState && !lastMoveVerb) { + return; + } + // A close at any other time must be ignored + fVerbs--; + break; + + case kLine_Verb: + if (!IsLineDegenerate(lastPt, fPts[0])) { + if (lastMoveVerb) { + fVerbs = lastMoveVerb; + fPts = lastMovePt; + return; + } + return; + } + // Ignore this line and continue + fVerbs--; + fPts++; + break; + + case kConic_Verb: + case kQuad_Verb: + if (!IsQuadDegenerate(lastPt, fPts[0], fPts[1])) { + if (lastMoveVerb) { + fVerbs = lastMoveVerb; + fPts = lastMovePt; + return; + } + return; + } + // Ignore this line and continue + fVerbs--; + fPts += 2; + fConicWeights += (kConic_Verb == verb); + break; + + case kCubic_Verb: + if (!IsCubicDegenerate(lastPt, fPts[0], fPts[1], fPts[2])) { + if (lastMoveVerb) { + fVerbs = lastMoveVerb; + fPts = lastMovePt; + return; + } + return; + } + // Ignore this line and continue + fVerbs--; + fPts += 3; + break; + + default: + SkDEBUGFAIL("Should never see kDone_Verb"); + } + } +} + +SkPath::Verb SkPath::Iter::doNext(SkPoint ptsParam[4]) { + SkASSERT(ptsParam); + + if (fVerbs == fVerbStop) { + // Close the curve if requested and if there is some curve to close + if (fNeedClose && fSegmentState == kAfterPrimitive_SegmentState) { + if (kLine_Verb == this->autoClose(ptsParam)) { + return kLine_Verb; + } + fNeedClose = false; + return kClose_Verb; + } + return kDone_Verb; + } + + // fVerbs is one beyond the current verb, decrement first + unsigned verb = *(--fVerbs); + const SkPoint* SK_RESTRICT srcPts = fPts; + SkPoint* SK_RESTRICT pts = ptsParam; + + switch (verb) { + case kMove_Verb: + if (fNeedClose) { + fVerbs++; // move back one verb + verb = this->autoClose(pts); + if (verb == kClose_Verb) { + fNeedClose = false; + } + return (Verb)verb; + } + if (fVerbs == fVerbStop) { // might be a trailing moveto + return kDone_Verb; + } + fMoveTo = *srcPts; + pts[0] = *srcPts; + srcPts += 1; + fSegmentState = kAfterMove_SegmentState; + fLastPt = fMoveTo; + fNeedClose = fForceClose; + break; + case kLine_Verb: + pts[0] = this->cons_moveTo(); + pts[1] = srcPts[0]; + fLastPt = srcPts[0]; + fCloseLine = false; + srcPts += 1; + break; + case kConic_Verb: + fConicWeights += 1; + // fall-through + case kQuad_Verb: + pts[0] = this->cons_moveTo(); + memcpy(&pts[1], srcPts, 2 * sizeof(SkPoint)); + fLastPt = srcPts[1]; + srcPts += 2; + break; + case kCubic_Verb: + pts[0] = this->cons_moveTo(); + memcpy(&pts[1], srcPts, 3 * sizeof(SkPoint)); + fLastPt = srcPts[2]; + srcPts += 3; + break; + case kClose_Verb: + verb = this->autoClose(pts); + if (verb == kLine_Verb) { + fVerbs++; // move back one verb + } else { + fNeedClose = false; + fSegmentState = kEmptyContour_SegmentState; + } + fLastPt = fMoveTo; + break; + } + fPts = srcPts; + return (Verb)verb; +} + +/////////////////////////////////////////////////////////////////////////////// + +SkPath::RawIter::RawIter() { +#ifdef SK_DEBUG + fPts = NULL; + fConicWeights = NULL; + fMoveTo.fX = fMoveTo.fY = fLastPt.fX = fLastPt.fY = 0; +#endif + // need to init enough to make next() harmlessly return kDone_Verb + fVerbs = NULL; + fVerbStop = NULL; +} + +SkPath::RawIter::RawIter(const SkPath& path) { + this->setPath(path); +} + +void SkPath::RawIter::setPath(const SkPath& path) { + fPts = path.fPathRef->points(); + fVerbs = path.fPathRef->verbs(); + fVerbStop = path.fPathRef->verbsMemBegin(); + fConicWeights = path.fPathRef->conicWeights() - 1; // begin one behind + fMoveTo.fX = fMoveTo.fY = 0; + fLastPt.fX = fLastPt.fY = 0; +} + +SkPath::Verb SkPath::RawIter::next(SkPoint pts[4]) { + SkASSERT(NULL != pts); + if (fVerbs == fVerbStop) { + return kDone_Verb; + } + + // fVerbs points one beyond next verb so decrement first. + unsigned verb = *(--fVerbs); + const SkPoint* srcPts = fPts; + + switch (verb) { + case kMove_Verb: + pts[0] = *srcPts; + fMoveTo = srcPts[0]; + fLastPt = fMoveTo; + srcPts += 1; + break; + case kLine_Verb: + pts[0] = fLastPt; + pts[1] = srcPts[0]; + fLastPt = srcPts[0]; + srcPts += 1; + break; + case kConic_Verb: + fConicWeights += 1; + // fall-through + case kQuad_Verb: + pts[0] = fLastPt; + memcpy(&pts[1], srcPts, 2 * sizeof(SkPoint)); + fLastPt = srcPts[1]; + srcPts += 2; + break; + case kCubic_Verb: + pts[0] = fLastPt; + memcpy(&pts[1], srcPts, 3 * sizeof(SkPoint)); + fLastPt = srcPts[2]; + srcPts += 3; + break; + case kClose_Verb: + fLastPt = fMoveTo; + pts[0] = fMoveTo; + break; + } + fPts = srcPts; + return (Verb)verb; +} + +/////////////////////////////////////////////////////////////////////////////// + +/* + Format in compressed buffer: [ptCount, verbCount, pts[], verbs[]] +*/ + +size_t SkPath::writeToMemory(void* storage) const { + SkDEBUGCODE(this->validate();) + + if (NULL == storage) { + const int byteCount = sizeof(int32_t) + fPathRef->writeSize(); + return SkAlign4(byteCount); + } + + SkWBuffer buffer(storage); + + int32_t packed = (fConvexity << kConvexity_SerializationShift) | + (fFillType << kFillType_SerializationShift) | + (fDirection << kDirection_SerializationShift); + + buffer.write32(packed); + + fPathRef->writeToBuffer(&buffer); + + buffer.padToAlign4(); + return buffer.pos(); +} + +size_t SkPath::readFromMemory(const void* storage, size_t length) { + SkRBufferWithSizeCheck buffer(storage, length); + + int32_t packed; + if (!buffer.readS32(&packed)) { + return 0; + } + + fConvexity = (packed >> kConvexity_SerializationShift) & 0xFF; + fFillType = (packed >> kFillType_SerializationShift) & 0xFF; + fDirection = (packed >> kDirection_SerializationShift) & 0x3; + SkPathRef* pathRef = SkPathRef::CreateFromBuffer(&buffer); + + size_t sizeRead = 0; + if (buffer.isValid()) { + fPathRef.reset(pathRef); + SkDEBUGCODE(this->validate();) + buffer.skipToAlign4(); + sizeRead = buffer.pos(); + } else if (NULL != pathRef) { + // If the buffer is not valid, pathRef should be NULL + sk_throw(); + } + return sizeRead; +} + +/////////////////////////////////////////////////////////////////////////////// + +#include "SkString.h" + +static void append_scalar(SkString* str, SkScalar value) { + SkString tmp; + tmp.printf("%g", value); + if (tmp.contains('.')) { + tmp.appendUnichar('f'); + } + str->append(tmp); +} + +static void append_params(SkString* str, const char label[], const SkPoint pts[], + int count, SkScalar conicWeight = -1) { + str->append(label); + str->append("("); + + const SkScalar* values = &pts[0].fX; + count *= 2; + + for (int i = 0; i < count; ++i) { + append_scalar(str, values[i]); + if (i < count - 1) { + str->append(", "); + } + } + if (conicWeight >= 0) { + str->append(", "); + append_scalar(str, conicWeight); + } + str->append(");\n"); +} + +void SkPath::dump(bool forceClose, const char title[]) const { + Iter iter(*this, forceClose); + SkPoint pts[4]; + Verb verb; + + SkDebugf("path: forceClose=%s %s\n", forceClose ? "true" : "false", + title ? title : ""); + + SkString builder; + + while ((verb = iter.next(pts, false)) != kDone_Verb) { + switch (verb) { + case kMove_Verb: + append_params(&builder, "path.moveTo", &pts[0], 1); + break; + case kLine_Verb: + append_params(&builder, "path.lineTo", &pts[1], 1); + break; + case kQuad_Verb: + append_params(&builder, "path.quadTo", &pts[1], 2); + break; + case kConic_Verb: + append_params(&builder, "path.conicTo", &pts[1], 2, iter.conicWeight()); + break; + case kCubic_Verb: + append_params(&builder, "path.cubicTo", &pts[1], 3); + break; + case kClose_Verb: + builder.append("path.close();\n"); + break; + default: + SkDebugf(" path: UNKNOWN VERB %d, aborting dump...\n", verb); + verb = kDone_Verb; // stop the loop + break; + } + } + SkDebugf("%s\n", builder.c_str()); +} + +void SkPath::dump() const { + this->dump(false); +} + +#ifdef SK_DEBUG +void SkPath::validate() const { + SkASSERT(this != NULL); + SkASSERT((fFillType & ~3) == 0); + +#ifdef SK_DEBUG_PATH + if (!fBoundsIsDirty) { + SkRect bounds; + + bool isFinite = compute_pt_bounds(&bounds, *fPathRef.get()); + SkASSERT(SkToBool(fIsFinite) == isFinite); + + if (fPathRef->countPoints() <= 1) { + // if we're empty, fBounds may be empty but translated, so we can't + // necessarily compare to bounds directly + // try path.addOval(2, 2, 2, 2) which is empty, but the bounds will + // be [2, 2, 2, 2] + SkASSERT(bounds.isEmpty()); + SkASSERT(fBounds.isEmpty()); + } else { + if (bounds.isEmpty()) { + SkASSERT(fBounds.isEmpty()); + } else { + if (!fBounds.isEmpty()) { + SkASSERT(fBounds.contains(bounds)); + } + } + } + } +#endif // SK_DEBUG_PATH +} +#endif // SK_DEBUG + +/////////////////////////////////////////////////////////////////////////////// + +static int sign(SkScalar x) { return x < 0; } +#define kValueNeverReturnedBySign 2 + +static bool AlmostEqual(SkScalar compA, SkScalar compB) { + // The error epsilon was empirically derived; worse case round rects + // with a mid point outset by 2x float epsilon in tests had an error + // of 12. + const int epsilon = 16; + if (!SkScalarIsFinite(compA) || !SkScalarIsFinite(compB)) { + return false; + } + // no need to check for small numbers because SkPath::Iter has removed degenerate values + int aBits = SkFloatAs2sCompliment(compA); + int bBits = SkFloatAs2sCompliment(compB); + return aBits < bBits + epsilon && bBits < aBits + epsilon; +} + +// only valid for a single contour +struct Convexicator { + Convexicator() + : fPtCount(0) + , fConvexity(SkPath::kConvex_Convexity) + , fDirection(SkPath::kUnknown_Direction) { + fSign = 0; + // warnings + fLastPt.set(0, 0); + fCurrPt.set(0, 0); + fVec0.set(0, 0); + fVec1.set(0, 0); + fFirstVec.set(0, 0); + + fDx = fDy = 0; + fSx = fSy = kValueNeverReturnedBySign; + } + + SkPath::Convexity getConvexity() const { return fConvexity; } + + /** The direction returned is only valid if the path is determined convex */ + SkPath::Direction getDirection() const { return fDirection; } + + void addPt(const SkPoint& pt) { + if (SkPath::kConcave_Convexity == fConvexity) { + return; + } + + if (0 == fPtCount) { + fCurrPt = pt; + ++fPtCount; + } else { + SkVector vec = pt - fCurrPt; + if (vec.fX || vec.fY) { + fLastPt = fCurrPt; + fCurrPt = pt; + if (++fPtCount == 2) { + fFirstVec = fVec1 = vec; + } else { + SkASSERT(fPtCount > 2); + this->addVec(vec); + } + + int sx = sign(vec.fX); + int sy = sign(vec.fY); + fDx += (sx != fSx); + fDy += (sy != fSy); + fSx = sx; + fSy = sy; + + if (fDx > 3 || fDy > 3) { + fConvexity = SkPath::kConcave_Convexity; + } + } + } + } + + void close() { + if (fPtCount > 2) { + this->addVec(fFirstVec); + } + } + +private: + void addVec(const SkVector& vec) { + SkASSERT(vec.fX || vec.fY); + fVec0 = fVec1; + fVec1 = vec; + SkScalar cross = SkPoint::CrossProduct(fVec0, fVec1); + SkScalar smallest = SkTMin(fCurrPt.fX, SkTMin(fCurrPt.fY, SkTMin(fLastPt.fX, fLastPt.fY))); + SkScalar largest = SkTMax(fCurrPt.fX, SkTMax(fCurrPt.fY, SkTMax(fLastPt.fX, fLastPt.fY))); + largest = SkTMax(largest, -smallest); + int sign = AlmostEqual(largest, largest + cross) ? 0 : SkScalarSignAsInt(cross); + if (0 == fSign) { + fSign = sign; + if (1 == sign) { + fDirection = SkPath::kCW_Direction; + } else if (-1 == sign) { + fDirection = SkPath::kCCW_Direction; + } + } else if (sign) { + if (fSign != sign) { + fConvexity = SkPath::kConcave_Convexity; + fDirection = SkPath::kUnknown_Direction; + } + } + } + + SkPoint fLastPt; + SkPoint fCurrPt; + SkVector fVec0, fVec1, fFirstVec; + int fPtCount; // non-degenerate points + int fSign; + SkPath::Convexity fConvexity; + SkPath::Direction fDirection; + int fDx, fDy, fSx, fSy; +}; + +SkPath::Convexity SkPath::internalGetConvexity() const { + SkASSERT(kUnknown_Convexity == fConvexity); + SkPoint pts[4]; + SkPath::Verb verb; + SkPath::Iter iter(*this, true); + + int contourCount = 0; + int count; + Convexicator state; + + while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { + switch (verb) { + case kMove_Verb: + if (++contourCount > 1) { + fConvexity = kConcave_Convexity; + return kConcave_Convexity; + } + pts[1] = pts[0]; + count = 1; + break; + case kLine_Verb: count = 1; break; + case kQuad_Verb: count = 2; break; + case kConic_Verb: count = 2; break; + case kCubic_Verb: count = 3; break; + case kClose_Verb: + state.close(); + count = 0; + break; + default: + SkDEBUGFAIL("bad verb"); + fConvexity = kConcave_Convexity; + return kConcave_Convexity; + } + + for (int i = 1; i <= count; i++) { + state.addPt(pts[i]); + } + // early exit + if (kConcave_Convexity == state.getConvexity()) { + fConvexity = kConcave_Convexity; + return kConcave_Convexity; + } + } + fConvexity = state.getConvexity(); + if (kConvex_Convexity == fConvexity && kUnknown_Direction == fDirection) { + fDirection = state.getDirection(); + } + return static_cast(fConvexity); +} + +/////////////////////////////////////////////////////////////////////////////// + +class ContourIter { +public: + ContourIter(const SkPathRef& pathRef); + + bool done() const { return fDone; } + // if !done() then these may be called + int count() const { return fCurrPtCount; } + const SkPoint* pts() const { return fCurrPt; } + void next(); + +private: + int fCurrPtCount; + const SkPoint* fCurrPt; + const uint8_t* fCurrVerb; + const uint8_t* fStopVerbs; + const SkScalar* fCurrConicWeight; + bool fDone; + SkDEBUGCODE(int fContourCounter;) +}; + +ContourIter::ContourIter(const SkPathRef& pathRef) { + fStopVerbs = pathRef.verbsMemBegin(); + fDone = false; + fCurrPt = pathRef.points(); + fCurrVerb = pathRef.verbs(); + fCurrConicWeight = pathRef.conicWeights(); + fCurrPtCount = 0; + SkDEBUGCODE(fContourCounter = 0;) + this->next(); +} + +void ContourIter::next() { + if (fCurrVerb <= fStopVerbs) { + fDone = true; + } + if (fDone) { + return; + } + + // skip pts of prev contour + fCurrPt += fCurrPtCount; + + SkASSERT(SkPath::kMove_Verb == fCurrVerb[~0]); + int ptCount = 1; // moveTo + const uint8_t* verbs = fCurrVerb; + + for (--verbs; verbs > fStopVerbs; --verbs) { + switch (verbs[~0]) { + case SkPath::kMove_Verb: + goto CONTOUR_END; + case SkPath::kLine_Verb: + ptCount += 1; + break; + case SkPath::kConic_Verb: + fCurrConicWeight += 1; + // fall-through + case SkPath::kQuad_Verb: + ptCount += 2; + break; + case SkPath::kCubic_Verb: + ptCount += 3; + break; + case SkPath::kClose_Verb: + break; + default: + SkDEBUGFAIL("unexpected verb"); + break; + } + } +CONTOUR_END: + fCurrPtCount = ptCount; + fCurrVerb = verbs; + SkDEBUGCODE(++fContourCounter;) +} + +// returns cross product of (p1 - p0) and (p2 - p0) +static SkScalar cross_prod(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) { + SkScalar cross = SkPoint::CrossProduct(p1 - p0, p2 - p0); + // We may get 0 when the above subtracts underflow. We expect this to be + // very rare and lazily promote to double. + if (0 == cross) { + double p0x = SkScalarToDouble(p0.fX); + double p0y = SkScalarToDouble(p0.fY); + + double p1x = SkScalarToDouble(p1.fX); + double p1y = SkScalarToDouble(p1.fY); + + double p2x = SkScalarToDouble(p2.fX); + double p2y = SkScalarToDouble(p2.fY); + + cross = SkDoubleToScalar((p1x - p0x) * (p2y - p0y) - + (p1y - p0y) * (p2x - p0x)); + + } + return cross; +} + +// Returns the first pt with the maximum Y coordinate +static int find_max_y(const SkPoint pts[], int count) { + SkASSERT(count > 0); + SkScalar max = pts[0].fY; + int firstIndex = 0; + for (int i = 1; i < count; ++i) { + SkScalar y = pts[i].fY; + if (y > max) { + max = y; + firstIndex = i; + } + } + return firstIndex; +} + +static int find_diff_pt(const SkPoint pts[], int index, int n, int inc) { + int i = index; + for (;;) { + i = (i + inc) % n; + if (i == index) { // we wrapped around, so abort + break; + } + if (pts[index] != pts[i]) { // found a different point, success! + break; + } + } + return i; +} + +/** + * Starting at index, and moving forward (incrementing), find the xmin and + * xmax of the contiguous points that have the same Y. + */ +static int find_min_max_x_at_y(const SkPoint pts[], int index, int n, + int* maxIndexPtr) { + const SkScalar y = pts[index].fY; + SkScalar min = pts[index].fX; + SkScalar max = min; + int minIndex = index; + int maxIndex = index; + for (int i = index + 1; i < n; ++i) { + if (pts[i].fY != y) { + break; + } + SkScalar x = pts[i].fX; + if (x < min) { + min = x; + minIndex = i; + } else if (x > max) { + max = x; + maxIndex = i; + } + } + *maxIndexPtr = maxIndex; + return minIndex; +} + +static void crossToDir(SkScalar cross, SkPath::Direction* dir) { + *dir = cross > 0 ? SkPath::kCW_Direction : SkPath::kCCW_Direction; +} + +/* + * We loop through all contours, and keep the computed cross-product of the + * contour that contained the global y-max. If we just look at the first + * contour, we may find one that is wound the opposite way (correctly) since + * it is the interior of a hole (e.g. 'o'). Thus we must find the contour + * that is outer most (or at least has the global y-max) before we can consider + * its cross product. + */ +bool SkPath::cheapComputeDirection(Direction* dir) const { + if (kUnknown_Direction != fDirection) { + *dir = static_cast(fDirection); + return true; + } + + // don't want to pay the cost for computing this if it + // is unknown, so we don't call isConvex() + if (kConvex_Convexity == this->getConvexityOrUnknown()) { + SkASSERT(kUnknown_Direction == fDirection); + *dir = static_cast(fDirection); + return false; + } + + ContourIter iter(*fPathRef.get()); + + // initialize with our logical y-min + SkScalar ymax = this->getBounds().fTop; + SkScalar ymaxCross = 0; + + for (; !iter.done(); iter.next()) { + int n = iter.count(); + if (n < 3) { + continue; + } + + const SkPoint* pts = iter.pts(); + SkScalar cross = 0; + int index = find_max_y(pts, n); + if (pts[index].fY < ymax) { + continue; + } + + // If there is more than 1 distinct point at the y-max, we take the + // x-min and x-max of them and just subtract to compute the dir. + if (pts[(index + 1) % n].fY == pts[index].fY) { + int maxIndex; + int minIndex = find_min_max_x_at_y(pts, index, n, &maxIndex); + if (minIndex == maxIndex) { + goto TRY_CROSSPROD; + } + SkASSERT(pts[minIndex].fY == pts[index].fY); + SkASSERT(pts[maxIndex].fY == pts[index].fY); + SkASSERT(pts[minIndex].fX <= pts[maxIndex].fX); + // we just subtract the indices, and let that auto-convert to + // SkScalar, since we just want - or + to signal the direction. + cross = minIndex - maxIndex; + } else { + TRY_CROSSPROD: + // Find a next and prev index to use for the cross-product test, + // but we try to find pts that form non-zero vectors from pts[index] + // + // Its possible that we can't find two non-degenerate vectors, so + // we have to guard our search (e.g. all the pts could be in the + // same place). + + // we pass n - 1 instead of -1 so we don't foul up % operator by + // passing it a negative LH argument. + int prev = find_diff_pt(pts, index, n, n - 1); + if (prev == index) { + // completely degenerate, skip to next contour + continue; + } + int next = find_diff_pt(pts, index, n, 1); + SkASSERT(next != index); + cross = cross_prod(pts[prev], pts[index], pts[next]); + // if we get a zero and the points are horizontal, then we look at the spread in + // x-direction. We really should continue to walk away from the degeneracy until + // there is a divergence. + if (0 == cross && pts[prev].fY == pts[index].fY && pts[next].fY == pts[index].fY) { + // construct the subtract so we get the correct Direction below + cross = pts[index].fX - pts[next].fX; + } + } + + if (cross) { + // record our best guess so far + ymax = pts[index].fY; + ymaxCross = cross; + } + } + if (ymaxCross) { + crossToDir(ymaxCross, dir); + fDirection = *dir; + return true; + } else { + return false; + } +} + +/////////////////////////////////////////////////////////////////////////////// + +static SkScalar eval_cubic_coeff(SkScalar A, SkScalar B, SkScalar C, + SkScalar D, SkScalar t) { + return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D); +} + +static SkScalar eval_cubic_pts(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3, + SkScalar t) { + SkScalar A = c3 + 3*(c1 - c2) - c0; + SkScalar B = 3*(c2 - c1 - c1 + c0); + SkScalar C = 3*(c1 - c0); + SkScalar D = c0; + return eval_cubic_coeff(A, B, C, D, t); +} + +/* Given 4 cubic points (either Xs or Ys), and a target X or Y, compute the + t value such that cubic(t) = target + */ +static void chopMonoCubicAt(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3, + SkScalar target, SkScalar* t) { + // SkASSERT(c0 <= c1 && c1 <= c2 && c2 <= c3); + SkASSERT(c0 < target && target < c3); + + SkScalar D = c0 - target; + SkScalar A = c3 + 3*(c1 - c2) - c0; + SkScalar B = 3*(c2 - c1 - c1 + c0); + SkScalar C = 3*(c1 - c0); + + const SkScalar TOLERANCE = SK_Scalar1 / 4096; + SkScalar minT = 0; + SkScalar maxT = SK_Scalar1; + SkScalar mid; + int i; + for (i = 0; i < 16; i++) { + mid = SkScalarAve(minT, maxT); + SkScalar delta = eval_cubic_coeff(A, B, C, D, mid); + if (delta < 0) { + minT = mid; + delta = -delta; + } else { + maxT = mid; + } + if (delta < TOLERANCE) { + break; + } + } + *t = mid; +} + +template static void find_minmax(const SkPoint pts[], + SkScalar* minPtr, SkScalar* maxPtr) { + SkScalar min, max; + min = max = pts[0].fX; + for (size_t i = 1; i < N; ++i) { + min = SkMinScalar(min, pts[i].fX); + max = SkMaxScalar(max, pts[i].fX); + } + *minPtr = min; + *maxPtr = max; +} + +static int winding_mono_cubic(const SkPoint pts[], SkScalar x, SkScalar y) { + SkPoint storage[4]; + + int dir = 1; + if (pts[0].fY > pts[3].fY) { + storage[0] = pts[3]; + storage[1] = pts[2]; + storage[2] = pts[1]; + storage[3] = pts[0]; + pts = storage; + dir = -1; + } + if (y < pts[0].fY || y >= pts[3].fY) { + return 0; + } + + // quickreject or quickaccept + SkScalar min, max; + find_minmax<4>(pts, &min, &max); + if (x < min) { + return 0; + } + if (x > max) { + return dir; + } + + // compute the actual x(t) value + SkScalar t; + chopMonoCubicAt(pts[0].fY, pts[1].fY, pts[2].fY, pts[3].fY, y, &t); + SkScalar xt = eval_cubic_pts(pts[0].fX, pts[1].fX, pts[2].fX, pts[3].fX, t); + return xt < x ? dir : 0; +} + +static int winding_cubic(const SkPoint pts[], SkScalar x, SkScalar y) { + SkPoint dst[10]; + int n = SkChopCubicAtYExtrema(pts, dst); + int w = 0; + for (int i = 0; i <= n; ++i) { + w += winding_mono_cubic(&dst[i * 3], x, y); + } + return w; +} + +static int winding_mono_quad(const SkPoint pts[], SkScalar x, SkScalar y) { + SkScalar y0 = pts[0].fY; + SkScalar y2 = pts[2].fY; + + int dir = 1; + if (y0 > y2) { + SkTSwap(y0, y2); + dir = -1; + } + if (y < y0 || y >= y2) { + return 0; + } + + // bounds check on X (not required. is it faster?) +#if 0 + if (pts[0].fX > x && pts[1].fX > x && pts[2].fX > x) { + return 0; + } +#endif + + SkScalar roots[2]; + int n = SkFindUnitQuadRoots(pts[0].fY - 2 * pts[1].fY + pts[2].fY, + 2 * (pts[1].fY - pts[0].fY), + pts[0].fY - y, + roots); + SkASSERT(n <= 1); + SkScalar xt; + if (0 == n) { + SkScalar mid = SkScalarAve(y0, y2); + // Need [0] and [2] if dir == 1 + // and [2] and [0] if dir == -1 + xt = y < mid ? pts[1 - dir].fX : pts[dir - 1].fX; + } else { + SkScalar t = roots[0]; + SkScalar C = pts[0].fX; + SkScalar A = pts[2].fX - 2 * pts[1].fX + C; + SkScalar B = 2 * (pts[1].fX - C); + xt = SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C); + } + return xt < x ? dir : 0; +} + +static bool is_mono_quad(SkScalar y0, SkScalar y1, SkScalar y2) { + // return SkScalarSignAsInt(y0 - y1) + SkScalarSignAsInt(y1 - y2) != 0; + if (y0 == y1) { + return true; + } + if (y0 < y1) { + return y1 <= y2; + } else { + return y1 >= y2; + } +} + +static int winding_quad(const SkPoint pts[], SkScalar x, SkScalar y) { + SkPoint dst[5]; + int n = 0; + + if (!is_mono_quad(pts[0].fY, pts[1].fY, pts[2].fY)) { + n = SkChopQuadAtYExtrema(pts, dst); + pts = dst; + } + int w = winding_mono_quad(pts, x, y); + if (n > 0) { + w += winding_mono_quad(&pts[2], x, y); + } + return w; +} + +static int winding_line(const SkPoint pts[], SkScalar x, SkScalar y) { + SkScalar x0 = pts[0].fX; + SkScalar y0 = pts[0].fY; + SkScalar x1 = pts[1].fX; + SkScalar y1 = pts[1].fY; + + SkScalar dy = y1 - y0; + + int dir = 1; + if (y0 > y1) { + SkTSwap(y0, y1); + dir = -1; + } + if (y < y0 || y >= y1) { + return 0; + } + + SkScalar cross = SkScalarMul(x1 - x0, y - pts[0].fY) - + SkScalarMul(dy, x - pts[0].fX); + + if (SkScalarSignAsInt(cross) == dir) { + dir = 0; + } + return dir; +} + +static bool contains_inclusive(const SkRect& r, SkScalar x, SkScalar y) { + return r.fLeft <= x && x <= r.fRight && r.fTop <= y && y <= r.fBottom; +} + +bool SkPath::contains(SkScalar x, SkScalar y) const { + bool isInverse = this->isInverseFillType(); + if (this->isEmpty()) { + return isInverse; + } + + if (!contains_inclusive(this->getBounds(), x, y)) { + return isInverse; + } + + SkPath::Iter iter(*this, true); + bool done = false; + int w = 0; + do { + SkPoint pts[4]; + switch (iter.next(pts, false)) { + case SkPath::kMove_Verb: + case SkPath::kClose_Verb: + break; + case SkPath::kLine_Verb: + w += winding_line(pts, x, y); + break; + case SkPath::kQuad_Verb: + w += winding_quad(pts, x, y); + break; + case SkPath::kConic_Verb: + SkASSERT(0); + break; + case SkPath::kCubic_Verb: + w += winding_cubic(pts, x, y); + break; + case SkPath::kDone_Verb: + done = true; + break; + } + } while (!done); + + switch (this->getFillType()) { + case SkPath::kEvenOdd_FillType: + case SkPath::kInverseEvenOdd_FillType: + w &= 1; + break; + default: + break; + } + return SkToBool(w); +}