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