1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/core/SkPath.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,2896 @@
1.4 +
1.5 +/*
1.6 + * Copyright 2006 The Android Open Source Project
1.7 + *
1.8 + * Use of this source code is governed by a BSD-style license that can be
1.9 + * found in the LICENSE file.
1.10 + */
1.11 +
1.12 +
1.13 +#include "SkBuffer.h"
1.14 +#include "SkErrorInternals.h"
1.15 +#include "SkMath.h"
1.16 +#include "SkPath.h"
1.17 +#include "SkPathRef.h"
1.18 +#include "SkRRect.h"
1.19 +#include "SkThread.h"
1.20 +
1.21 +////////////////////////////////////////////////////////////////////////////
1.22 +
1.23 +/**
1.24 + * Path.bounds is defined to be the bounds of all the control points.
1.25 + * If we called bounds.join(r) we would skip r if r was empty, which breaks
1.26 + * our promise. Hence we have a custom joiner that doesn't look at emptiness
1.27 + */
1.28 +static void joinNoEmptyChecks(SkRect* dst, const SkRect& src) {
1.29 + dst->fLeft = SkMinScalar(dst->fLeft, src.fLeft);
1.30 + dst->fTop = SkMinScalar(dst->fTop, src.fTop);
1.31 + dst->fRight = SkMaxScalar(dst->fRight, src.fRight);
1.32 + dst->fBottom = SkMaxScalar(dst->fBottom, src.fBottom);
1.33 +}
1.34 +
1.35 +static bool is_degenerate(const SkPath& path) {
1.36 + SkPath::Iter iter(path, false);
1.37 + SkPoint pts[4];
1.38 + return SkPath::kDone_Verb == iter.next(pts);
1.39 +}
1.40 +
1.41 +class SkAutoDisableDirectionCheck {
1.42 +public:
1.43 + SkAutoDisableDirectionCheck(SkPath* path) : fPath(path) {
1.44 + fSaved = static_cast<SkPath::Direction>(fPath->fDirection);
1.45 + }
1.46 +
1.47 + ~SkAutoDisableDirectionCheck() {
1.48 + fPath->fDirection = fSaved;
1.49 + }
1.50 +
1.51 +private:
1.52 + SkPath* fPath;
1.53 + SkPath::Direction fSaved;
1.54 +};
1.55 +#define SkAutoDisableDirectionCheck(...) SK_REQUIRE_LOCAL_VAR(SkAutoDisableDirectionCheck)
1.56 +
1.57 +/* This guy's constructor/destructor bracket a path editing operation. It is
1.58 + used when we know the bounds of the amount we are going to add to the path
1.59 + (usually a new contour, but not required).
1.60 +
1.61 + It captures some state about the path up front (i.e. if it already has a
1.62 + cached bounds), and then if it can, it updates the cache bounds explicitly,
1.63 + avoiding the need to revisit all of the points in getBounds().
1.64 +
1.65 + It also notes if the path was originally degenerate, and if so, sets
1.66 + isConvex to true. Thus it can only be used if the contour being added is
1.67 + convex.
1.68 + */
1.69 +class SkAutoPathBoundsUpdate {
1.70 +public:
1.71 + SkAutoPathBoundsUpdate(SkPath* path, const SkRect& r) : fRect(r) {
1.72 + this->init(path);
1.73 + }
1.74 +
1.75 + SkAutoPathBoundsUpdate(SkPath* path, SkScalar left, SkScalar top,
1.76 + SkScalar right, SkScalar bottom) {
1.77 + fRect.set(left, top, right, bottom);
1.78 + this->init(path);
1.79 + }
1.80 +
1.81 + ~SkAutoPathBoundsUpdate() {
1.82 + fPath->setConvexity(fDegenerate ? SkPath::kConvex_Convexity
1.83 + : SkPath::kUnknown_Convexity);
1.84 + if (fEmpty || fHasValidBounds) {
1.85 + fPath->setBounds(fRect);
1.86 + }
1.87 + }
1.88 +
1.89 +private:
1.90 + SkPath* fPath;
1.91 + SkRect fRect;
1.92 + bool fHasValidBounds;
1.93 + bool fDegenerate;
1.94 + bool fEmpty;
1.95 +
1.96 + void init(SkPath* path) {
1.97 + // Cannot use fRect for our bounds unless we know it is sorted
1.98 + fRect.sort();
1.99 + fPath = path;
1.100 + // Mark the path's bounds as dirty if (1) they are, or (2) the path
1.101 + // is non-finite, and therefore its bounds are not meaningful
1.102 + fHasValidBounds = path->hasComputedBounds() && path->isFinite();
1.103 + fEmpty = path->isEmpty();
1.104 + if (fHasValidBounds && !fEmpty) {
1.105 + joinNoEmptyChecks(&fRect, fPath->getBounds());
1.106 + }
1.107 + fDegenerate = is_degenerate(*path);
1.108 + }
1.109 +};
1.110 +#define SkAutoPathBoundsUpdate(...) SK_REQUIRE_LOCAL_VAR(SkAutoPathBoundsUpdate)
1.111 +
1.112 +////////////////////////////////////////////////////////////////////////////
1.113 +
1.114 +/*
1.115 + Stores the verbs and points as they are given to us, with exceptions:
1.116 + - we only record "Close" if it was immediately preceeded by Move | Line | Quad | Cubic
1.117 + - we insert a Move(0,0) if Line | Quad | Cubic is our first command
1.118 +
1.119 + The iterator does more cleanup, especially if forceClose == true
1.120 + 1. If we encounter degenerate segments, remove them
1.121 + 2. if we encounter Close, return a cons'd up Line() first (if the curr-pt != start-pt)
1.122 + 3. if we encounter Move without a preceeding Close, and forceClose is true, goto #2
1.123 + 4. if we encounter Line | Quad | Cubic after Close, cons up a Move
1.124 +*/
1.125 +
1.126 +////////////////////////////////////////////////////////////////////////////
1.127 +
1.128 +// flag to require a moveTo if we begin with something else, like lineTo etc.
1.129 +#define INITIAL_LASTMOVETOINDEX_VALUE ~0
1.130 +
1.131 +SkPath::SkPath()
1.132 + : fPathRef(SkPathRef::CreateEmpty())
1.133 +#ifdef SK_BUILD_FOR_ANDROID
1.134 + , fSourcePath(NULL)
1.135 +#endif
1.136 +{
1.137 + this->resetFields();
1.138 +}
1.139 +
1.140 +void SkPath::resetFields() {
1.141 + //fPathRef is assumed to have been emptied by the caller.
1.142 + fLastMoveToIndex = INITIAL_LASTMOVETOINDEX_VALUE;
1.143 + fFillType = kWinding_FillType;
1.144 + fConvexity = kUnknown_Convexity;
1.145 + fDirection = kUnknown_Direction;
1.146 +
1.147 + // We don't touch Android's fSourcePath. It's used to track texture garbage collection, so we
1.148 + // don't want to muck with it if it's been set to something non-NULL.
1.149 +}
1.150 +
1.151 +SkPath::SkPath(const SkPath& that)
1.152 + : fPathRef(SkRef(that.fPathRef.get())) {
1.153 + this->copyFields(that);
1.154 +#ifdef SK_BUILD_FOR_ANDROID
1.155 + fSourcePath = that.fSourcePath;
1.156 +#endif
1.157 + SkDEBUGCODE(that.validate();)
1.158 +}
1.159 +
1.160 +SkPath::~SkPath() {
1.161 + SkDEBUGCODE(this->validate();)
1.162 +}
1.163 +
1.164 +SkPath& SkPath::operator=(const SkPath& that) {
1.165 + SkDEBUGCODE(that.validate();)
1.166 +
1.167 + if (this != &that) {
1.168 + fPathRef.reset(SkRef(that.fPathRef.get()));
1.169 + this->copyFields(that);
1.170 +#ifdef SK_BUILD_FOR_ANDROID
1.171 + fSourcePath = that.fSourcePath;
1.172 +#endif
1.173 + }
1.174 + SkDEBUGCODE(this->validate();)
1.175 + return *this;
1.176 +}
1.177 +
1.178 +void SkPath::copyFields(const SkPath& that) {
1.179 + //fPathRef is assumed to have been set by the caller.
1.180 + fLastMoveToIndex = that.fLastMoveToIndex;
1.181 + fFillType = that.fFillType;
1.182 + fConvexity = that.fConvexity;
1.183 + fDirection = that.fDirection;
1.184 +}
1.185 +
1.186 +bool operator==(const SkPath& a, const SkPath& b) {
1.187 + // note: don't need to look at isConvex or bounds, since just comparing the
1.188 + // raw data is sufficient.
1.189 + return &a == &b ||
1.190 + (a.fFillType == b.fFillType && *a.fPathRef.get() == *b.fPathRef.get());
1.191 +}
1.192 +
1.193 +void SkPath::swap(SkPath& that) {
1.194 + SkASSERT(&that != NULL);
1.195 +
1.196 + if (this != &that) {
1.197 + fPathRef.swap(&that.fPathRef);
1.198 + SkTSwap<int>(fLastMoveToIndex, that.fLastMoveToIndex);
1.199 + SkTSwap<uint8_t>(fFillType, that.fFillType);
1.200 + SkTSwap<uint8_t>(fConvexity, that.fConvexity);
1.201 + SkTSwap<uint8_t>(fDirection, that.fDirection);
1.202 +#ifdef SK_BUILD_FOR_ANDROID
1.203 + SkTSwap<const SkPath*>(fSourcePath, that.fSourcePath);
1.204 +#endif
1.205 + }
1.206 +}
1.207 +
1.208 +static inline bool check_edge_against_rect(const SkPoint& p0,
1.209 + const SkPoint& p1,
1.210 + const SkRect& rect,
1.211 + SkPath::Direction dir) {
1.212 + const SkPoint* edgeBegin;
1.213 + SkVector v;
1.214 + if (SkPath::kCW_Direction == dir) {
1.215 + v = p1 - p0;
1.216 + edgeBegin = &p0;
1.217 + } else {
1.218 + v = p0 - p1;
1.219 + edgeBegin = &p1;
1.220 + }
1.221 + if (v.fX || v.fY) {
1.222 + // check the cross product of v with the vec from edgeBegin to each rect corner
1.223 + SkScalar yL = SkScalarMul(v.fY, rect.fLeft - edgeBegin->fX);
1.224 + SkScalar xT = SkScalarMul(v.fX, rect.fTop - edgeBegin->fY);
1.225 + SkScalar yR = SkScalarMul(v.fY, rect.fRight - edgeBegin->fX);
1.226 + SkScalar xB = SkScalarMul(v.fX, rect.fBottom - edgeBegin->fY);
1.227 + if ((xT < yL) || (xT < yR) || (xB < yL) || (xB < yR)) {
1.228 + return false;
1.229 + }
1.230 + }
1.231 + return true;
1.232 +}
1.233 +
1.234 +bool SkPath::conservativelyContainsRect(const SkRect& rect) const {
1.235 + // This only handles non-degenerate convex paths currently.
1.236 + if (kConvex_Convexity != this->getConvexity()) {
1.237 + return false;
1.238 + }
1.239 +
1.240 + Direction direction;
1.241 + if (!this->cheapComputeDirection(&direction)) {
1.242 + return false;
1.243 + }
1.244 +
1.245 + SkPoint firstPt;
1.246 + SkPoint prevPt;
1.247 + RawIter iter(*this);
1.248 + SkPath::Verb verb;
1.249 + SkPoint pts[4];
1.250 + SkDEBUGCODE(int moveCnt = 0;)
1.251 + SkDEBUGCODE(int segmentCount = 0;)
1.252 + SkDEBUGCODE(int closeCount = 0;)
1.253 +
1.254 + while ((verb = iter.next(pts)) != kDone_Verb) {
1.255 + int nextPt = -1;
1.256 + switch (verb) {
1.257 + case kMove_Verb:
1.258 + SkASSERT(!segmentCount && !closeCount);
1.259 + SkDEBUGCODE(++moveCnt);
1.260 + firstPt = prevPt = pts[0];
1.261 + break;
1.262 + case kLine_Verb:
1.263 + nextPt = 1;
1.264 + SkASSERT(moveCnt && !closeCount);
1.265 + SkDEBUGCODE(++segmentCount);
1.266 + break;
1.267 + case kQuad_Verb:
1.268 + case kConic_Verb:
1.269 + SkASSERT(moveCnt && !closeCount);
1.270 + SkDEBUGCODE(++segmentCount);
1.271 + nextPt = 2;
1.272 + break;
1.273 + case kCubic_Verb:
1.274 + SkASSERT(moveCnt && !closeCount);
1.275 + SkDEBUGCODE(++segmentCount);
1.276 + nextPt = 3;
1.277 + break;
1.278 + case kClose_Verb:
1.279 + SkDEBUGCODE(++closeCount;)
1.280 + break;
1.281 + default:
1.282 + SkDEBUGFAIL("unknown verb");
1.283 + }
1.284 + if (-1 != nextPt) {
1.285 + if (!check_edge_against_rect(prevPt, pts[nextPt], rect, direction)) {
1.286 + return false;
1.287 + }
1.288 + prevPt = pts[nextPt];
1.289 + }
1.290 + }
1.291 +
1.292 + return check_edge_against_rect(prevPt, firstPt, rect, direction);
1.293 +}
1.294 +
1.295 +uint32_t SkPath::getGenerationID() const {
1.296 + uint32_t genID = fPathRef->genID();
1.297 +#ifdef SK_BUILD_FOR_ANDROID
1.298 + SkASSERT((unsigned)fFillType < (1 << (32 - kPathRefGenIDBitCnt)));
1.299 + genID |= static_cast<uint32_t>(fFillType) << kPathRefGenIDBitCnt;
1.300 +#endif
1.301 + return genID;
1.302 +}
1.303 +
1.304 +#ifdef SK_BUILD_FOR_ANDROID
1.305 +const SkPath* SkPath::getSourcePath() const {
1.306 + return fSourcePath;
1.307 +}
1.308 +
1.309 +void SkPath::setSourcePath(const SkPath* path) {
1.310 + fSourcePath = path;
1.311 +}
1.312 +#endif
1.313 +
1.314 +void SkPath::reset() {
1.315 + SkDEBUGCODE(this->validate();)
1.316 +
1.317 + fPathRef.reset(SkPathRef::CreateEmpty());
1.318 + this->resetFields();
1.319 +}
1.320 +
1.321 +void SkPath::rewind() {
1.322 + SkDEBUGCODE(this->validate();)
1.323 +
1.324 + SkPathRef::Rewind(&fPathRef);
1.325 + this->resetFields();
1.326 +}
1.327 +
1.328 +bool SkPath::isLine(SkPoint line[2]) const {
1.329 + int verbCount = fPathRef->countVerbs();
1.330 +
1.331 + if (2 == verbCount) {
1.332 + SkASSERT(kMove_Verb == fPathRef->atVerb(0));
1.333 + if (kLine_Verb == fPathRef->atVerb(1)) {
1.334 + SkASSERT(2 == fPathRef->countPoints());
1.335 + if (line) {
1.336 + const SkPoint* pts = fPathRef->points();
1.337 + line[0] = pts[0];
1.338 + line[1] = pts[1];
1.339 + }
1.340 + return true;
1.341 + }
1.342 + }
1.343 + return false;
1.344 +}
1.345 +
1.346 +/*
1.347 + Determines if path is a rect by keeping track of changes in direction
1.348 + and looking for a loop either clockwise or counterclockwise.
1.349 +
1.350 + The direction is computed such that:
1.351 + 0: vertical up
1.352 + 1: horizontal left
1.353 + 2: vertical down
1.354 + 3: horizontal right
1.355 +
1.356 +A rectangle cycles up/right/down/left or up/left/down/right.
1.357 +
1.358 +The test fails if:
1.359 + The path is closed, and followed by a line.
1.360 + A second move creates a new endpoint.
1.361 + A diagonal line is parsed.
1.362 + There's more than four changes of direction.
1.363 + There's a discontinuity on the line (e.g., a move in the middle)
1.364 + The line reverses direction.
1.365 + The path contains a quadratic or cubic.
1.366 + The path contains fewer than four points.
1.367 + *The rectangle doesn't complete a cycle.
1.368 + *The final point isn't equal to the first point.
1.369 +
1.370 + *These last two conditions we relax if we have a 3-edge path that would
1.371 + form a rectangle if it were closed (as we do when we fill a path)
1.372 +
1.373 +It's OK if the path has:
1.374 + Several colinear line segments composing a rectangle side.
1.375 + Single points on the rectangle side.
1.376 +
1.377 +The direction takes advantage of the corners found since opposite sides
1.378 +must travel in opposite directions.
1.379 +
1.380 +FIXME: Allow colinear quads and cubics to be treated like lines.
1.381 +FIXME: If the API passes fill-only, return true if the filled stroke
1.382 + is a rectangle, though the caller failed to close the path.
1.383 +
1.384 + first,last,next direction state-machine:
1.385 + 0x1 is set if the segment is horizontal
1.386 + 0x2 is set if the segment is moving to the right or down
1.387 + thus:
1.388 + two directions are opposites iff (dirA ^ dirB) == 0x2
1.389 + two directions are perpendicular iff (dirA ^ dirB) == 0x1
1.390 +
1.391 + */
1.392 +static int rect_make_dir(SkScalar dx, SkScalar dy) {
1.393 + return ((0 != dx) << 0) | ((dx > 0 || dy > 0) << 1);
1.394 +}
1.395 +bool SkPath::isRectContour(bool allowPartial, int* currVerb, const SkPoint** ptsPtr,
1.396 + bool* isClosed, Direction* direction) const {
1.397 + int corners = 0;
1.398 + SkPoint first, last;
1.399 + const SkPoint* pts = *ptsPtr;
1.400 + const SkPoint* savePts = NULL;
1.401 + first.set(0, 0);
1.402 + last.set(0, 0);
1.403 + int firstDirection = 0;
1.404 + int lastDirection = 0;
1.405 + int nextDirection = 0;
1.406 + bool closedOrMoved = false;
1.407 + bool autoClose = false;
1.408 + int verbCnt = fPathRef->countVerbs();
1.409 + while (*currVerb < verbCnt && (!allowPartial || !autoClose)) {
1.410 + switch (fPathRef->atVerb(*currVerb)) {
1.411 + case kClose_Verb:
1.412 + savePts = pts;
1.413 + pts = *ptsPtr;
1.414 + autoClose = true;
1.415 + case kLine_Verb: {
1.416 + SkScalar left = last.fX;
1.417 + SkScalar top = last.fY;
1.418 + SkScalar right = pts->fX;
1.419 + SkScalar bottom = pts->fY;
1.420 + ++pts;
1.421 + if (left != right && top != bottom) {
1.422 + return false; // diagonal
1.423 + }
1.424 + if (left == right && top == bottom) {
1.425 + break; // single point on side OK
1.426 + }
1.427 + nextDirection = rect_make_dir(right - left, bottom - top);
1.428 + if (0 == corners) {
1.429 + firstDirection = nextDirection;
1.430 + first = last;
1.431 + last = pts[-1];
1.432 + corners = 1;
1.433 + closedOrMoved = false;
1.434 + break;
1.435 + }
1.436 + if (closedOrMoved) {
1.437 + return false; // closed followed by a line
1.438 + }
1.439 + if (autoClose && nextDirection == firstDirection) {
1.440 + break; // colinear with first
1.441 + }
1.442 + closedOrMoved = autoClose;
1.443 + if (lastDirection != nextDirection) {
1.444 + if (++corners > 4) {
1.445 + return false; // too many direction changes
1.446 + }
1.447 + }
1.448 + last = pts[-1];
1.449 + if (lastDirection == nextDirection) {
1.450 + break; // colinear segment
1.451 + }
1.452 + // Possible values for corners are 2, 3, and 4.
1.453 + // When corners == 3, nextDirection opposes firstDirection.
1.454 + // Otherwise, nextDirection at corner 2 opposes corner 4.
1.455 + int turn = firstDirection ^ (corners - 1);
1.456 + int directionCycle = 3 == corners ? 0 : nextDirection ^ turn;
1.457 + if ((directionCycle ^ turn) != nextDirection) {
1.458 + return false; // direction didn't follow cycle
1.459 + }
1.460 + break;
1.461 + }
1.462 + case kQuad_Verb:
1.463 + case kConic_Verb:
1.464 + case kCubic_Verb:
1.465 + return false; // quadratic, cubic not allowed
1.466 + case kMove_Verb:
1.467 + last = *pts++;
1.468 + closedOrMoved = true;
1.469 + break;
1.470 + default:
1.471 + SkDEBUGFAIL("unexpected verb");
1.472 + break;
1.473 + }
1.474 + *currVerb += 1;
1.475 + lastDirection = nextDirection;
1.476 + }
1.477 + // Success if 4 corners and first point equals last
1.478 + bool result = 4 == corners && (first == last || autoClose);
1.479 + if (!result) {
1.480 + // check if we are just an incomplete rectangle, in which case we can
1.481 + // return true, but not claim to be closed.
1.482 + // e.g.
1.483 + // 3 sided rectangle
1.484 + // 4 sided but the last edge is not long enough to reach the start
1.485 + //
1.486 + SkScalar closeX = first.x() - last.x();
1.487 + SkScalar closeY = first.y() - last.y();
1.488 + if (closeX && closeY) {
1.489 + return false; // we're diagonal, abort (can we ever reach this?)
1.490 + }
1.491 + int closeDirection = rect_make_dir(closeX, closeY);
1.492 + // make sure the close-segment doesn't double-back on itself
1.493 + if (3 == corners || (4 == corners && closeDirection == lastDirection)) {
1.494 + result = true;
1.495 + autoClose = false; // we are not closed
1.496 + }
1.497 + }
1.498 + if (savePts) {
1.499 + *ptsPtr = savePts;
1.500 + }
1.501 + if (result && isClosed) {
1.502 + *isClosed = autoClose;
1.503 + }
1.504 + if (result && direction) {
1.505 + *direction = firstDirection == ((lastDirection + 1) & 3) ? kCCW_Direction : kCW_Direction;
1.506 + }
1.507 + return result;
1.508 +}
1.509 +
1.510 +SkPath::PathAsRect SkPath::asRect(Direction* direction) const {
1.511 + SK_COMPILE_ASSERT(0 == kNone_PathAsRect, path_as_rect_mismatch);
1.512 + SK_COMPILE_ASSERT(1 == kFill_PathAsRect, path_as_rect_mismatch);
1.513 + SK_COMPILE_ASSERT(2 == kStroke_PathAsRect, path_as_rect_mismatch);
1.514 + bool isClosed = false;
1.515 + return (PathAsRect) (isRect(&isClosed, direction) + isClosed);
1.516 +}
1.517 +
1.518 +bool SkPath::isRect(SkRect* rect) const {
1.519 + SkDEBUGCODE(this->validate();)
1.520 + int currVerb = 0;
1.521 + const SkPoint* pts = fPathRef->points();
1.522 + bool result = isRectContour(false, &currVerb, &pts, NULL, NULL);
1.523 + if (result && rect) {
1.524 + *rect = getBounds();
1.525 + }
1.526 + return result;
1.527 +}
1.528 +
1.529 +bool SkPath::isRect(bool* isClosed, Direction* direction) const {
1.530 + SkDEBUGCODE(this->validate();)
1.531 + int currVerb = 0;
1.532 + const SkPoint* pts = fPathRef->points();
1.533 + return isRectContour(false, &currVerb, &pts, isClosed, direction);
1.534 +}
1.535 +
1.536 +bool SkPath::isNestedRects(SkRect rects[2], Direction dirs[2]) const {
1.537 + SkDEBUGCODE(this->validate();)
1.538 + int currVerb = 0;
1.539 + const SkPoint* pts = fPathRef->points();
1.540 + const SkPoint* first = pts;
1.541 + Direction testDirs[2];
1.542 + if (!isRectContour(true, &currVerb, &pts, NULL, &testDirs[0])) {
1.543 + return false;
1.544 + }
1.545 + const SkPoint* last = pts;
1.546 + SkRect testRects[2];
1.547 + if (isRectContour(false, &currVerb, &pts, NULL, &testDirs[1])) {
1.548 + testRects[0].set(first, SkToS32(last - first));
1.549 + testRects[1].set(last, SkToS32(pts - last));
1.550 + if (testRects[0].contains(testRects[1])) {
1.551 + if (rects) {
1.552 + rects[0] = testRects[0];
1.553 + rects[1] = testRects[1];
1.554 + }
1.555 + if (dirs) {
1.556 + dirs[0] = testDirs[0];
1.557 + dirs[1] = testDirs[1];
1.558 + }
1.559 + return true;
1.560 + }
1.561 + if (testRects[1].contains(testRects[0])) {
1.562 + if (rects) {
1.563 + rects[0] = testRects[1];
1.564 + rects[1] = testRects[0];
1.565 + }
1.566 + if (dirs) {
1.567 + dirs[0] = testDirs[1];
1.568 + dirs[1] = testDirs[0];
1.569 + }
1.570 + return true;
1.571 + }
1.572 + }
1.573 + return false;
1.574 +}
1.575 +
1.576 +int SkPath::countPoints() const {
1.577 + return fPathRef->countPoints();
1.578 +}
1.579 +
1.580 +int SkPath::getPoints(SkPoint dst[], int max) const {
1.581 + SkDEBUGCODE(this->validate();)
1.582 +
1.583 + SkASSERT(max >= 0);
1.584 + SkASSERT(!max || dst);
1.585 + int count = SkMin32(max, fPathRef->countPoints());
1.586 + memcpy(dst, fPathRef->points(), count * sizeof(SkPoint));
1.587 + return fPathRef->countPoints();
1.588 +}
1.589 +
1.590 +SkPoint SkPath::getPoint(int index) const {
1.591 + if ((unsigned)index < (unsigned)fPathRef->countPoints()) {
1.592 + return fPathRef->atPoint(index);
1.593 + }
1.594 + return SkPoint::Make(0, 0);
1.595 +}
1.596 +
1.597 +int SkPath::countVerbs() const {
1.598 + return fPathRef->countVerbs();
1.599 +}
1.600 +
1.601 +static inline void copy_verbs_reverse(uint8_t* inorderDst,
1.602 + const uint8_t* reversedSrc,
1.603 + int count) {
1.604 + for (int i = 0; i < count; ++i) {
1.605 + inorderDst[i] = reversedSrc[~i];
1.606 + }
1.607 +}
1.608 +
1.609 +int SkPath::getVerbs(uint8_t dst[], int max) const {
1.610 + SkDEBUGCODE(this->validate();)
1.611 +
1.612 + SkASSERT(max >= 0);
1.613 + SkASSERT(!max || dst);
1.614 + int count = SkMin32(max, fPathRef->countVerbs());
1.615 + copy_verbs_reverse(dst, fPathRef->verbs(), count);
1.616 + return fPathRef->countVerbs();
1.617 +}
1.618 +
1.619 +bool SkPath::getLastPt(SkPoint* lastPt) const {
1.620 + SkDEBUGCODE(this->validate();)
1.621 +
1.622 + int count = fPathRef->countPoints();
1.623 + if (count > 0) {
1.624 + if (lastPt) {
1.625 + *lastPt = fPathRef->atPoint(count - 1);
1.626 + }
1.627 + return true;
1.628 + }
1.629 + if (lastPt) {
1.630 + lastPt->set(0, 0);
1.631 + }
1.632 + return false;
1.633 +}
1.634 +
1.635 +void SkPath::setLastPt(SkScalar x, SkScalar y) {
1.636 + SkDEBUGCODE(this->validate();)
1.637 +
1.638 + int count = fPathRef->countPoints();
1.639 + if (count == 0) {
1.640 + this->moveTo(x, y);
1.641 + } else {
1.642 + SkPathRef::Editor ed(&fPathRef);
1.643 + ed.atPoint(count-1)->set(x, y);
1.644 + }
1.645 +}
1.646 +
1.647 +void SkPath::setConvexity(Convexity c) {
1.648 + if (fConvexity != c) {
1.649 + fConvexity = c;
1.650 + }
1.651 +}
1.652 +
1.653 +//////////////////////////////////////////////////////////////////////////////
1.654 +// Construction methods
1.655 +
1.656 +#define DIRTY_AFTER_EDIT \
1.657 + do { \
1.658 + fConvexity = kUnknown_Convexity; \
1.659 + fDirection = kUnknown_Direction; \
1.660 + } while (0)
1.661 +
1.662 +void SkPath::incReserve(U16CPU inc) {
1.663 + SkDEBUGCODE(this->validate();)
1.664 + SkPathRef::Editor(&fPathRef, inc, inc);
1.665 + SkDEBUGCODE(this->validate();)
1.666 +}
1.667 +
1.668 +void SkPath::moveTo(SkScalar x, SkScalar y) {
1.669 + SkDEBUGCODE(this->validate();)
1.670 +
1.671 + SkPathRef::Editor ed(&fPathRef);
1.672 +
1.673 + // remember our index
1.674 + fLastMoveToIndex = fPathRef->countPoints();
1.675 +
1.676 + ed.growForVerb(kMove_Verb)->set(x, y);
1.677 +}
1.678 +
1.679 +void SkPath::rMoveTo(SkScalar x, SkScalar y) {
1.680 + SkPoint pt;
1.681 + this->getLastPt(&pt);
1.682 + this->moveTo(pt.fX + x, pt.fY + y);
1.683 +}
1.684 +
1.685 +void SkPath::injectMoveToIfNeeded() {
1.686 + if (fLastMoveToIndex < 0) {
1.687 + SkScalar x, y;
1.688 + if (fPathRef->countVerbs() == 0) {
1.689 + x = y = 0;
1.690 + } else {
1.691 + const SkPoint& pt = fPathRef->atPoint(~fLastMoveToIndex);
1.692 + x = pt.fX;
1.693 + y = pt.fY;
1.694 + }
1.695 + this->moveTo(x, y);
1.696 + }
1.697 +}
1.698 +
1.699 +void SkPath::lineTo(SkScalar x, SkScalar y) {
1.700 + SkDEBUGCODE(this->validate();)
1.701 +
1.702 + this->injectMoveToIfNeeded();
1.703 +
1.704 + SkPathRef::Editor ed(&fPathRef);
1.705 + ed.growForVerb(kLine_Verb)->set(x, y);
1.706 +
1.707 + DIRTY_AFTER_EDIT;
1.708 +}
1.709 +
1.710 +void SkPath::rLineTo(SkScalar x, SkScalar y) {
1.711 + this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt().
1.712 + SkPoint pt;
1.713 + this->getLastPt(&pt);
1.714 + this->lineTo(pt.fX + x, pt.fY + y);
1.715 +}
1.716 +
1.717 +void SkPath::quadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) {
1.718 + SkDEBUGCODE(this->validate();)
1.719 +
1.720 + this->injectMoveToIfNeeded();
1.721 +
1.722 + SkPathRef::Editor ed(&fPathRef);
1.723 + SkPoint* pts = ed.growForVerb(kQuad_Verb);
1.724 + pts[0].set(x1, y1);
1.725 + pts[1].set(x2, y2);
1.726 +
1.727 + DIRTY_AFTER_EDIT;
1.728 +}
1.729 +
1.730 +void SkPath::rQuadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) {
1.731 + this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt().
1.732 + SkPoint pt;
1.733 + this->getLastPt(&pt);
1.734 + this->quadTo(pt.fX + x1, pt.fY + y1, pt.fX + x2, pt.fY + y2);
1.735 +}
1.736 +
1.737 +void SkPath::conicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
1.738 + SkScalar w) {
1.739 + // check for <= 0 or NaN with this test
1.740 + if (!(w > 0)) {
1.741 + this->lineTo(x2, y2);
1.742 + } else if (!SkScalarIsFinite(w)) {
1.743 + this->lineTo(x1, y1);
1.744 + this->lineTo(x2, y2);
1.745 + } else if (SK_Scalar1 == w) {
1.746 + this->quadTo(x1, y1, x2, y2);
1.747 + } else {
1.748 + SkDEBUGCODE(this->validate();)
1.749 +
1.750 + this->injectMoveToIfNeeded();
1.751 +
1.752 + SkPathRef::Editor ed(&fPathRef);
1.753 + SkPoint* pts = ed.growForVerb(kConic_Verb, w);
1.754 + pts[0].set(x1, y1);
1.755 + pts[1].set(x2, y2);
1.756 +
1.757 + DIRTY_AFTER_EDIT;
1.758 + }
1.759 +}
1.760 +
1.761 +void SkPath::rConicTo(SkScalar dx1, SkScalar dy1, SkScalar dx2, SkScalar dy2,
1.762 + SkScalar w) {
1.763 + this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt().
1.764 + SkPoint pt;
1.765 + this->getLastPt(&pt);
1.766 + this->conicTo(pt.fX + dx1, pt.fY + dy1, pt.fX + dx2, pt.fY + dy2, w);
1.767 +}
1.768 +
1.769 +void SkPath::cubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
1.770 + SkScalar x3, SkScalar y3) {
1.771 + SkDEBUGCODE(this->validate();)
1.772 +
1.773 + this->injectMoveToIfNeeded();
1.774 +
1.775 + SkPathRef::Editor ed(&fPathRef);
1.776 + SkPoint* pts = ed.growForVerb(kCubic_Verb);
1.777 + pts[0].set(x1, y1);
1.778 + pts[1].set(x2, y2);
1.779 + pts[2].set(x3, y3);
1.780 +
1.781 + DIRTY_AFTER_EDIT;
1.782 +}
1.783 +
1.784 +void SkPath::rCubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
1.785 + SkScalar x3, SkScalar y3) {
1.786 + this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt().
1.787 + SkPoint pt;
1.788 + this->getLastPt(&pt);
1.789 + this->cubicTo(pt.fX + x1, pt.fY + y1, pt.fX + x2, pt.fY + y2,
1.790 + pt.fX + x3, pt.fY + y3);
1.791 +}
1.792 +
1.793 +void SkPath::close() {
1.794 + SkDEBUGCODE(this->validate();)
1.795 +
1.796 + int count = fPathRef->countVerbs();
1.797 + if (count > 0) {
1.798 + switch (fPathRef->atVerb(count - 1)) {
1.799 + case kLine_Verb:
1.800 + case kQuad_Verb:
1.801 + case kConic_Verb:
1.802 + case kCubic_Verb:
1.803 + case kMove_Verb: {
1.804 + SkPathRef::Editor ed(&fPathRef);
1.805 + ed.growForVerb(kClose_Verb);
1.806 + break;
1.807 + }
1.808 + case kClose_Verb:
1.809 + // don't add a close if it's the first verb or a repeat
1.810 + break;
1.811 + default:
1.812 + SkDEBUGFAIL("unexpected verb");
1.813 + break;
1.814 + }
1.815 + }
1.816 +
1.817 + // signal that we need a moveTo to follow us (unless we're done)
1.818 +#if 0
1.819 + if (fLastMoveToIndex >= 0) {
1.820 + fLastMoveToIndex = ~fLastMoveToIndex;
1.821 + }
1.822 +#else
1.823 + fLastMoveToIndex ^= ~fLastMoveToIndex >> (8 * sizeof(fLastMoveToIndex) - 1);
1.824 +#endif
1.825 +}
1.826 +
1.827 +///////////////////////////////////////////////////////////////////////////////
1.828 +
1.829 +static void assert_known_direction(int dir) {
1.830 + SkASSERT(SkPath::kCW_Direction == dir || SkPath::kCCW_Direction == dir);
1.831 +}
1.832 +
1.833 +void SkPath::addRect(const SkRect& rect, Direction dir) {
1.834 + this->addRect(rect.fLeft, rect.fTop, rect.fRight, rect.fBottom, dir);
1.835 +}
1.836 +
1.837 +void SkPath::addRect(SkScalar left, SkScalar top, SkScalar right,
1.838 + SkScalar bottom, Direction dir) {
1.839 + assert_known_direction(dir);
1.840 + fDirection = this->hasOnlyMoveTos() ? dir : kUnknown_Direction;
1.841 + SkAutoDisableDirectionCheck addc(this);
1.842 +
1.843 + SkAutoPathBoundsUpdate apbu(this, left, top, right, bottom);
1.844 +
1.845 + this->incReserve(5);
1.846 +
1.847 + this->moveTo(left, top);
1.848 + if (dir == kCCW_Direction) {
1.849 + this->lineTo(left, bottom);
1.850 + this->lineTo(right, bottom);
1.851 + this->lineTo(right, top);
1.852 + } else {
1.853 + this->lineTo(right, top);
1.854 + this->lineTo(right, bottom);
1.855 + this->lineTo(left, bottom);
1.856 + }
1.857 + this->close();
1.858 +}
1.859 +
1.860 +void SkPath::addPoly(const SkPoint pts[], int count, bool close) {
1.861 + SkDEBUGCODE(this->validate();)
1.862 + if (count <= 0) {
1.863 + return;
1.864 + }
1.865 +
1.866 + fLastMoveToIndex = fPathRef->countPoints();
1.867 +
1.868 + // +close makes room for the extra kClose_Verb
1.869 + SkPathRef::Editor ed(&fPathRef, count+close, count);
1.870 +
1.871 + ed.growForVerb(kMove_Verb)->set(pts[0].fX, pts[0].fY);
1.872 + if (count > 1) {
1.873 + SkPoint* p = ed.growForRepeatedVerb(kLine_Verb, count - 1);
1.874 + memcpy(p, &pts[1], (count-1) * sizeof(SkPoint));
1.875 + }
1.876 +
1.877 + if (close) {
1.878 + ed.growForVerb(kClose_Verb);
1.879 + }
1.880 +
1.881 + DIRTY_AFTER_EDIT;
1.882 + SkDEBUGCODE(this->validate();)
1.883 +}
1.884 +
1.885 +#include "SkGeometry.h"
1.886 +
1.887 +static int build_arc_points(const SkRect& oval, SkScalar startAngle,
1.888 + SkScalar sweepAngle,
1.889 + SkPoint pts[kSkBuildQuadArcStorage]) {
1.890 +
1.891 + if (0 == sweepAngle &&
1.892 + (0 == startAngle || SkIntToScalar(360) == startAngle)) {
1.893 + // Chrome uses this path to move into and out of ovals. If not
1.894 + // treated as a special case the moves can distort the oval's
1.895 + // bounding box (and break the circle special case).
1.896 + pts[0].set(oval.fRight, oval.centerY());
1.897 + return 1;
1.898 + } else if (0 == oval.width() && 0 == oval.height()) {
1.899 + // Chrome will sometimes create 0 radius round rects. Having degenerate
1.900 + // quad segments in the path prevents the path from being recognized as
1.901 + // a rect.
1.902 + // TODO: optimizing the case where only one of width or height is zero
1.903 + // should also be considered. This case, however, doesn't seem to be
1.904 + // as common as the single point case.
1.905 + pts[0].set(oval.fRight, oval.fTop);
1.906 + return 1;
1.907 + }
1.908 +
1.909 + SkVector start, stop;
1.910 +
1.911 + start.fY = SkScalarSinCos(SkDegreesToRadians(startAngle), &start.fX);
1.912 + stop.fY = SkScalarSinCos(SkDegreesToRadians(startAngle + sweepAngle),
1.913 + &stop.fX);
1.914 +
1.915 + /* If the sweep angle is nearly (but less than) 360, then due to precision
1.916 + loss in radians-conversion and/or sin/cos, we may end up with coincident
1.917 + vectors, which will fool SkBuildQuadArc into doing nothing (bad) instead
1.918 + of drawing a nearly complete circle (good).
1.919 + e.g. canvas.drawArc(0, 359.99, ...)
1.920 + -vs- canvas.drawArc(0, 359.9, ...)
1.921 + We try to detect this edge case, and tweak the stop vector
1.922 + */
1.923 + if (start == stop) {
1.924 + SkScalar sw = SkScalarAbs(sweepAngle);
1.925 + if (sw < SkIntToScalar(360) && sw > SkIntToScalar(359)) {
1.926 + SkScalar stopRad = SkDegreesToRadians(startAngle + sweepAngle);
1.927 + // make a guess at a tiny angle (in radians) to tweak by
1.928 + SkScalar deltaRad = SkScalarCopySign(SK_Scalar1/512, sweepAngle);
1.929 + // not sure how much will be enough, so we use a loop
1.930 + do {
1.931 + stopRad -= deltaRad;
1.932 + stop.fY = SkScalarSinCos(stopRad, &stop.fX);
1.933 + } while (start == stop);
1.934 + }
1.935 + }
1.936 +
1.937 + SkMatrix matrix;
1.938 +
1.939 + matrix.setScale(SkScalarHalf(oval.width()), SkScalarHalf(oval.height()));
1.940 + matrix.postTranslate(oval.centerX(), oval.centerY());
1.941 +
1.942 + return SkBuildQuadArc(start, stop,
1.943 + sweepAngle > 0 ? kCW_SkRotationDirection :
1.944 + kCCW_SkRotationDirection,
1.945 + &matrix, pts);
1.946 +}
1.947 +
1.948 +void SkPath::addRoundRect(const SkRect& rect, const SkScalar radii[],
1.949 + Direction dir) {
1.950 + SkRRect rrect;
1.951 + rrect.setRectRadii(rect, (const SkVector*) radii);
1.952 + this->addRRect(rrect, dir);
1.953 +}
1.954 +
1.955 +/* The inline clockwise and counterclockwise round rect quad approximations
1.956 + make it easier to see the symmetry patterns used by add corner quads.
1.957 +Clockwise corner value
1.958 + path->lineTo(rect.fLeft, rect.fTop + ry); 0 upper left
1.959 + path->quadTo(rect.fLeft, rect.fTop + offPtY,
1.960 + rect.fLeft + midPtX, rect.fTop + midPtY);
1.961 + path->quadTo(rect.fLeft + offPtX, rect.fTop,
1.962 + rect.fLeft + rx, rect.fTop);
1.963 +
1.964 + path->lineTo(rect.fRight - rx, rect.fTop); 1 upper right
1.965 + path->quadTo(rect.fRight - offPtX, rect.fTop,
1.966 + rect.fRight - midPtX, rect.fTop + midPtY);
1.967 + path->quadTo(rect.fRight, rect.fTop + offPtY,
1.968 + rect.fRight, rect.fTop + ry);
1.969 +
1.970 + path->lineTo(rect.fRight, rect.fBottom - ry); 2 lower right
1.971 + path->quadTo(rect.fRight, rect.fBottom - offPtY,
1.972 + rect.fRight - midPtX, rect.fBottom - midPtY);
1.973 + path->quadTo(rect.fRight - offPtX, rect.fBottom,
1.974 + rect.fRight - rx, rect.fBottom);
1.975 +
1.976 + path->lineTo(rect.fLeft + rx, rect.fBottom); 3 lower left
1.977 + path->quadTo(rect.fLeft + offPtX, rect.fBottom,
1.978 + rect.fLeft + midPtX, rect.fBottom - midPtY);
1.979 + path->quadTo(rect.fLeft, rect.fBottom - offPtY,
1.980 + rect.fLeft, rect.fBottom - ry);
1.981 +
1.982 +Counterclockwise
1.983 + path->lineTo(rect.fLeft, rect.fBottom - ry); 3 lower left
1.984 + path->quadTo(rect.fLeft, rect.fBottom - offPtY,
1.985 + rect.fLeft + midPtX, rect.fBottom - midPtY);
1.986 + path->quadTo(rect.fLeft + offPtX, rect.fBottom,
1.987 + rect.fLeft + rx, rect.fBottom);
1.988 +
1.989 + path->lineTo(rect.fRight - rx, rect.fBottom); 2 lower right
1.990 + path->quadTo(rect.fRight - offPtX, rect.fBottom,
1.991 + rect.fRight - midPtX, rect.fBottom - midPtY);
1.992 + path->quadTo(rect.fRight, rect.fBottom - offPtY,
1.993 + rect.fRight, rect.fBottom - ry);
1.994 +
1.995 + path->lineTo(rect.fRight, rect.fTop + ry); 1 upper right
1.996 + path->quadTo(rect.fRight, rect.fTop + offPtY,
1.997 + rect.fRight - midPtX, rect.fTop + midPtY);
1.998 + path->quadTo(rect.fRight - offPtX, rect.fTop,
1.999 + rect.fRight - rx, rect.fTop);
1.1000 +
1.1001 + path->lineTo(rect.fLeft + rx, rect.fTop); 0 upper left
1.1002 + path->quadTo(rect.fLeft + offPtX, rect.fTop,
1.1003 + rect.fLeft + midPtX, rect.fTop + midPtY);
1.1004 + path->quadTo(rect.fLeft, rect.fTop + offPtY,
1.1005 + rect.fLeft, rect.fTop + ry);
1.1006 +*/
1.1007 +static void add_corner_quads(SkPath* path, const SkRRect& rrect,
1.1008 + SkRRect::Corner corner, SkPath::Direction dir) {
1.1009 + const SkRect& rect = rrect.rect();
1.1010 + const SkVector& radii = rrect.radii(corner);
1.1011 + SkScalar rx = radii.fX;
1.1012 + SkScalar ry = radii.fY;
1.1013 + // The mid point of the quadratic arc approximation is half way between the two
1.1014 + // control points.
1.1015 + const SkScalar mid = 1 - (SK_Scalar1 + SK_ScalarTanPIOver8) / 2;
1.1016 + SkScalar midPtX = rx * mid;
1.1017 + SkScalar midPtY = ry * mid;
1.1018 + const SkScalar control = 1 - SK_ScalarTanPIOver8;
1.1019 + SkScalar offPtX = rx * control;
1.1020 + SkScalar offPtY = ry * control;
1.1021 + static const int kCornerPts = 5;
1.1022 + SkScalar xOff[kCornerPts];
1.1023 + SkScalar yOff[kCornerPts];
1.1024 +
1.1025 + if ((corner & 1) == (dir == SkPath::kCCW_Direction)) { // corners always alternate direction
1.1026 + SkASSERT(dir == SkPath::kCCW_Direction
1.1027 + ? corner == SkRRect::kLowerLeft_Corner || corner == SkRRect::kUpperRight_Corner
1.1028 + : corner == SkRRect::kUpperLeft_Corner || corner == SkRRect::kLowerRight_Corner);
1.1029 + xOff[0] = xOff[1] = 0;
1.1030 + xOff[2] = midPtX;
1.1031 + xOff[3] = offPtX;
1.1032 + xOff[4] = rx;
1.1033 + yOff[0] = ry;
1.1034 + yOff[1] = offPtY;
1.1035 + yOff[2] = midPtY;
1.1036 + yOff[3] = yOff[4] = 0;
1.1037 + } else {
1.1038 + xOff[0] = rx;
1.1039 + xOff[1] = offPtX;
1.1040 + xOff[2] = midPtX;
1.1041 + xOff[3] = xOff[4] = 0;
1.1042 + yOff[0] = yOff[1] = 0;
1.1043 + yOff[2] = midPtY;
1.1044 + yOff[3] = offPtY;
1.1045 + yOff[4] = ry;
1.1046 + }
1.1047 + if ((corner - 1) & 2) {
1.1048 + SkASSERT(corner == SkRRect::kLowerLeft_Corner || corner == SkRRect::kUpperLeft_Corner);
1.1049 + for (int i = 0; i < kCornerPts; ++i) {
1.1050 + xOff[i] = rect.fLeft + xOff[i];
1.1051 + }
1.1052 + } else {
1.1053 + SkASSERT(corner == SkRRect::kLowerRight_Corner || corner == SkRRect::kUpperRight_Corner);
1.1054 + for (int i = 0; i < kCornerPts; ++i) {
1.1055 + xOff[i] = rect.fRight - xOff[i];
1.1056 + }
1.1057 + }
1.1058 + if (corner < SkRRect::kLowerRight_Corner) {
1.1059 + for (int i = 0; i < kCornerPts; ++i) {
1.1060 + yOff[i] = rect.fTop + yOff[i];
1.1061 + }
1.1062 + } else {
1.1063 + for (int i = 0; i < kCornerPts; ++i) {
1.1064 + yOff[i] = rect.fBottom - yOff[i];
1.1065 + }
1.1066 + }
1.1067 +
1.1068 + SkPoint lastPt;
1.1069 + SkAssertResult(path->getLastPt(&lastPt));
1.1070 + if (lastPt.fX != xOff[0] || lastPt.fY != yOff[0]) {
1.1071 + path->lineTo(xOff[0], yOff[0]);
1.1072 + }
1.1073 + if (rx || ry) {
1.1074 + path->quadTo(xOff[1], yOff[1], xOff[2], yOff[2]);
1.1075 + path->quadTo(xOff[3], yOff[3], xOff[4], yOff[4]);
1.1076 + } else {
1.1077 + path->lineTo(xOff[2], yOff[2]);
1.1078 + path->lineTo(xOff[4], yOff[4]);
1.1079 + }
1.1080 +}
1.1081 +
1.1082 +void SkPath::addRRect(const SkRRect& rrect, Direction dir) {
1.1083 + assert_known_direction(dir);
1.1084 +
1.1085 + if (rrect.isEmpty()) {
1.1086 + return;
1.1087 + }
1.1088 +
1.1089 + const SkRect& bounds = rrect.getBounds();
1.1090 +
1.1091 + if (rrect.isRect()) {
1.1092 + this->addRect(bounds, dir);
1.1093 + } else if (rrect.isOval()) {
1.1094 + this->addOval(bounds, dir);
1.1095 +#ifdef SK_IGNORE_QUAD_RR_CORNERS_OPT
1.1096 + } else if (rrect.isSimple()) {
1.1097 + const SkVector& rad = rrect.getSimpleRadii();
1.1098 + this->addRoundRect(bounds, rad.x(), rad.y(), dir);
1.1099 +#endif
1.1100 + } else {
1.1101 + fDirection = this->hasOnlyMoveTos() ? dir : kUnknown_Direction;
1.1102 +
1.1103 + SkAutoPathBoundsUpdate apbu(this, bounds);
1.1104 + SkAutoDisableDirectionCheck addc(this);
1.1105 +
1.1106 + this->incReserve(21);
1.1107 + if (kCW_Direction == dir) {
1.1108 + this->moveTo(bounds.fLeft,
1.1109 + bounds.fBottom - rrect.fRadii[SkRRect::kLowerLeft_Corner].fY);
1.1110 + add_corner_quads(this, rrect, SkRRect::kUpperLeft_Corner, dir);
1.1111 + add_corner_quads(this, rrect, SkRRect::kUpperRight_Corner, dir);
1.1112 + add_corner_quads(this, rrect, SkRRect::kLowerRight_Corner, dir);
1.1113 + add_corner_quads(this, rrect, SkRRect::kLowerLeft_Corner, dir);
1.1114 + } else {
1.1115 + this->moveTo(bounds.fLeft,
1.1116 + bounds.fTop + rrect.fRadii[SkRRect::kUpperLeft_Corner].fY);
1.1117 + add_corner_quads(this, rrect, SkRRect::kLowerLeft_Corner, dir);
1.1118 + add_corner_quads(this, rrect, SkRRect::kLowerRight_Corner, dir);
1.1119 + add_corner_quads(this, rrect, SkRRect::kUpperRight_Corner, dir);
1.1120 + add_corner_quads(this, rrect, SkRRect::kUpperLeft_Corner, dir);
1.1121 + }
1.1122 + this->close();
1.1123 + }
1.1124 +}
1.1125 +
1.1126 +bool SkPath::hasOnlyMoveTos() const {
1.1127 + int count = fPathRef->countVerbs();
1.1128 + const uint8_t* verbs = const_cast<const SkPathRef*>(fPathRef.get())->verbsMemBegin();
1.1129 + for (int i = 0; i < count; ++i) {
1.1130 + if (*verbs == kLine_Verb ||
1.1131 + *verbs == kQuad_Verb ||
1.1132 + *verbs == kConic_Verb ||
1.1133 + *verbs == kCubic_Verb) {
1.1134 + return false;
1.1135 + }
1.1136 + ++verbs;
1.1137 + }
1.1138 + return true;
1.1139 +}
1.1140 +
1.1141 +#ifdef SK_IGNORE_QUAD_RR_CORNERS_OPT
1.1142 +#define CUBIC_ARC_FACTOR ((SK_ScalarSqrt2 - SK_Scalar1) * 4 / 3)
1.1143 +#endif
1.1144 +
1.1145 +void SkPath::addRoundRect(const SkRect& rect, SkScalar rx, SkScalar ry,
1.1146 + Direction dir) {
1.1147 + assert_known_direction(dir);
1.1148 +
1.1149 + if (rx < 0 || ry < 0) {
1.1150 + SkErrorInternals::SetError( kInvalidArgument_SkError,
1.1151 + "I got %f and %f as radii to SkPath::AddRoundRect, "
1.1152 + "but negative radii are not allowed.",
1.1153 + SkScalarToDouble(rx), SkScalarToDouble(ry) );
1.1154 + return;
1.1155 + }
1.1156 +
1.1157 +#ifdef SK_IGNORE_QUAD_RR_CORNERS_OPT
1.1158 + SkScalar w = rect.width();
1.1159 + SkScalar halfW = SkScalarHalf(w);
1.1160 + SkScalar h = rect.height();
1.1161 + SkScalar halfH = SkScalarHalf(h);
1.1162 +
1.1163 + if (halfW <= 0 || halfH <= 0) {
1.1164 + return;
1.1165 + }
1.1166 +
1.1167 + bool skip_hori = rx >= halfW;
1.1168 + bool skip_vert = ry >= halfH;
1.1169 +
1.1170 + if (skip_hori && skip_vert) {
1.1171 + this->addOval(rect, dir);
1.1172 + return;
1.1173 + }
1.1174 +
1.1175 + fDirection = this->hasOnlyMoveTos() ? dir : kUnknown_Direction;
1.1176 +
1.1177 + SkAutoPathBoundsUpdate apbu(this, rect);
1.1178 + SkAutoDisableDirectionCheck addc(this);
1.1179 +
1.1180 + if (skip_hori) {
1.1181 + rx = halfW;
1.1182 + } else if (skip_vert) {
1.1183 + ry = halfH;
1.1184 + }
1.1185 + SkScalar sx = SkScalarMul(rx, CUBIC_ARC_FACTOR);
1.1186 + SkScalar sy = SkScalarMul(ry, CUBIC_ARC_FACTOR);
1.1187 +
1.1188 + this->incReserve(17);
1.1189 + this->moveTo(rect.fRight - rx, rect.fTop); // top-right
1.1190 + if (dir == kCCW_Direction) {
1.1191 + if (!skip_hori) {
1.1192 + this->lineTo(rect.fLeft + rx, rect.fTop); // top
1.1193 + }
1.1194 + this->cubicTo(rect.fLeft + rx - sx, rect.fTop,
1.1195 + rect.fLeft, rect.fTop + ry - sy,
1.1196 + rect.fLeft, rect.fTop + ry); // top-left
1.1197 + if (!skip_vert) {
1.1198 + this->lineTo(rect.fLeft, rect.fBottom - ry); // left
1.1199 + }
1.1200 + this->cubicTo(rect.fLeft, rect.fBottom - ry + sy,
1.1201 + rect.fLeft + rx - sx, rect.fBottom,
1.1202 + rect.fLeft + rx, rect.fBottom); // bot-left
1.1203 + if (!skip_hori) {
1.1204 + this->lineTo(rect.fRight - rx, rect.fBottom); // bottom
1.1205 + }
1.1206 + this->cubicTo(rect.fRight - rx + sx, rect.fBottom,
1.1207 + rect.fRight, rect.fBottom - ry + sy,
1.1208 + rect.fRight, rect.fBottom - ry); // bot-right
1.1209 + if (!skip_vert) {
1.1210 + this->lineTo(rect.fRight, rect.fTop + ry); // right
1.1211 + }
1.1212 + this->cubicTo(rect.fRight, rect.fTop + ry - sy,
1.1213 + rect.fRight - rx + sx, rect.fTop,
1.1214 + rect.fRight - rx, rect.fTop); // top-right
1.1215 + } else {
1.1216 + this->cubicTo(rect.fRight - rx + sx, rect.fTop,
1.1217 + rect.fRight, rect.fTop + ry - sy,
1.1218 + rect.fRight, rect.fTop + ry); // top-right
1.1219 + if (!skip_vert) {
1.1220 + this->lineTo(rect.fRight, rect.fBottom - ry); // right
1.1221 + }
1.1222 + this->cubicTo(rect.fRight, rect.fBottom - ry + sy,
1.1223 + rect.fRight - rx + sx, rect.fBottom,
1.1224 + rect.fRight - rx, rect.fBottom); // bot-right
1.1225 + if (!skip_hori) {
1.1226 + this->lineTo(rect.fLeft + rx, rect.fBottom); // bottom
1.1227 + }
1.1228 + this->cubicTo(rect.fLeft + rx - sx, rect.fBottom,
1.1229 + rect.fLeft, rect.fBottom - ry + sy,
1.1230 + rect.fLeft, rect.fBottom - ry); // bot-left
1.1231 + if (!skip_vert) {
1.1232 + this->lineTo(rect.fLeft, rect.fTop + ry); // left
1.1233 + }
1.1234 + this->cubicTo(rect.fLeft, rect.fTop + ry - sy,
1.1235 + rect.fLeft + rx - sx, rect.fTop,
1.1236 + rect.fLeft + rx, rect.fTop); // top-left
1.1237 + if (!skip_hori) {
1.1238 + this->lineTo(rect.fRight - rx, rect.fTop); // top
1.1239 + }
1.1240 + }
1.1241 + this->close();
1.1242 +#else
1.1243 + SkRRect rrect;
1.1244 + rrect.setRectXY(rect, rx, ry);
1.1245 + this->addRRect(rrect, dir);
1.1246 +#endif
1.1247 +}
1.1248 +
1.1249 +void SkPath::addOval(const SkRect& oval, Direction dir) {
1.1250 + assert_known_direction(dir);
1.1251 +
1.1252 + /* If addOval() is called after previous moveTo(),
1.1253 + this path is still marked as an oval. This is used to
1.1254 + fit into WebKit's calling sequences.
1.1255 + We can't simply check isEmpty() in this case, as additional
1.1256 + moveTo() would mark the path non empty.
1.1257 + */
1.1258 + bool isOval = hasOnlyMoveTos();
1.1259 + if (isOval) {
1.1260 + fDirection = dir;
1.1261 + } else {
1.1262 + fDirection = kUnknown_Direction;
1.1263 + }
1.1264 +
1.1265 + SkAutoDisableDirectionCheck addc(this);
1.1266 +
1.1267 + SkAutoPathBoundsUpdate apbu(this, oval);
1.1268 +
1.1269 + SkScalar cx = oval.centerX();
1.1270 + SkScalar cy = oval.centerY();
1.1271 + SkScalar rx = SkScalarHalf(oval.width());
1.1272 + SkScalar ry = SkScalarHalf(oval.height());
1.1273 +
1.1274 + SkScalar sx = SkScalarMul(rx, SK_ScalarTanPIOver8);
1.1275 + SkScalar sy = SkScalarMul(ry, SK_ScalarTanPIOver8);
1.1276 + SkScalar mx = SkScalarMul(rx, SK_ScalarRoot2Over2);
1.1277 + SkScalar my = SkScalarMul(ry, SK_ScalarRoot2Over2);
1.1278 +
1.1279 + /*
1.1280 + To handle imprecision in computing the center and radii, we revert to
1.1281 + the provided bounds when we can (i.e. use oval.fLeft instead of cx-rx)
1.1282 + to ensure that we don't exceed the oval's bounds *ever*, since we want
1.1283 + to use oval for our fast-bounds, rather than have to recompute it.
1.1284 + */
1.1285 + const SkScalar L = oval.fLeft; // cx - rx
1.1286 + const SkScalar T = oval.fTop; // cy - ry
1.1287 + const SkScalar R = oval.fRight; // cx + rx
1.1288 + const SkScalar B = oval.fBottom; // cy + ry
1.1289 +
1.1290 + this->incReserve(17); // 8 quads + close
1.1291 + this->moveTo(R, cy);
1.1292 + if (dir == kCCW_Direction) {
1.1293 + this->quadTo( R, cy - sy, cx + mx, cy - my);
1.1294 + this->quadTo(cx + sx, T, cx , T);
1.1295 + this->quadTo(cx - sx, T, cx - mx, cy - my);
1.1296 + this->quadTo( L, cy - sy, L, cy );
1.1297 + this->quadTo( L, cy + sy, cx - mx, cy + my);
1.1298 + this->quadTo(cx - sx, B, cx , B);
1.1299 + this->quadTo(cx + sx, B, cx + mx, cy + my);
1.1300 + this->quadTo( R, cy + sy, R, cy );
1.1301 + } else {
1.1302 + this->quadTo( R, cy + sy, cx + mx, cy + my);
1.1303 + this->quadTo(cx + sx, B, cx , B);
1.1304 + this->quadTo(cx - sx, B, cx - mx, cy + my);
1.1305 + this->quadTo( L, cy + sy, L, cy );
1.1306 + this->quadTo( L, cy - sy, cx - mx, cy - my);
1.1307 + this->quadTo(cx - sx, T, cx , T);
1.1308 + this->quadTo(cx + sx, T, cx + mx, cy - my);
1.1309 + this->quadTo( R, cy - sy, R, cy );
1.1310 + }
1.1311 + this->close();
1.1312 +
1.1313 + SkPathRef::Editor ed(&fPathRef);
1.1314 +
1.1315 + ed.setIsOval(isOval);
1.1316 +}
1.1317 +
1.1318 +void SkPath::addCircle(SkScalar x, SkScalar y, SkScalar r, Direction dir) {
1.1319 + if (r > 0) {
1.1320 + SkRect rect;
1.1321 + rect.set(x - r, y - r, x + r, y + r);
1.1322 + this->addOval(rect, dir);
1.1323 + }
1.1324 +}
1.1325 +
1.1326 +void SkPath::arcTo(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle,
1.1327 + bool forceMoveTo) {
1.1328 + if (oval.width() < 0 || oval.height() < 0) {
1.1329 + return;
1.1330 + }
1.1331 +
1.1332 + SkPoint pts[kSkBuildQuadArcStorage];
1.1333 + int count = build_arc_points(oval, startAngle, sweepAngle, pts);
1.1334 + SkASSERT((count & 1) == 1);
1.1335 +
1.1336 + if (fPathRef->countVerbs() == 0) {
1.1337 + forceMoveTo = true;
1.1338 + }
1.1339 + this->incReserve(count);
1.1340 + forceMoveTo ? this->moveTo(pts[0]) : this->lineTo(pts[0]);
1.1341 + for (int i = 1; i < count; i += 2) {
1.1342 + this->quadTo(pts[i], pts[i+1]);
1.1343 + }
1.1344 +}
1.1345 +
1.1346 +void SkPath::addArc(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle) {
1.1347 + if (oval.isEmpty() || 0 == sweepAngle) {
1.1348 + return;
1.1349 + }
1.1350 +
1.1351 + const SkScalar kFullCircleAngle = SkIntToScalar(360);
1.1352 +
1.1353 + if (sweepAngle >= kFullCircleAngle || sweepAngle <= -kFullCircleAngle) {
1.1354 + this->addOval(oval, sweepAngle > 0 ? kCW_Direction : kCCW_Direction);
1.1355 + return;
1.1356 + }
1.1357 +
1.1358 + SkPoint pts[kSkBuildQuadArcStorage];
1.1359 + int count = build_arc_points(oval, startAngle, sweepAngle, pts);
1.1360 +
1.1361 + SkDEBUGCODE(this->validate();)
1.1362 + SkASSERT(count & 1);
1.1363 +
1.1364 + fLastMoveToIndex = fPathRef->countPoints();
1.1365 +
1.1366 + SkPathRef::Editor ed(&fPathRef, 1+(count-1)/2, count);
1.1367 +
1.1368 + ed.growForVerb(kMove_Verb)->set(pts[0].fX, pts[0].fY);
1.1369 + if (count > 1) {
1.1370 + SkPoint* p = ed.growForRepeatedVerb(kQuad_Verb, (count-1)/2);
1.1371 + memcpy(p, &pts[1], (count-1) * sizeof(SkPoint));
1.1372 + }
1.1373 +
1.1374 + DIRTY_AFTER_EDIT;
1.1375 + SkDEBUGCODE(this->validate();)
1.1376 +}
1.1377 +
1.1378 +/*
1.1379 + Need to handle the case when the angle is sharp, and our computed end-points
1.1380 + for the arc go behind pt1 and/or p2...
1.1381 +*/
1.1382 +void SkPath::arcTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
1.1383 + SkScalar radius) {
1.1384 + SkVector before, after;
1.1385 +
1.1386 + // need to know our prev pt so we can construct tangent vectors
1.1387 + {
1.1388 + SkPoint start;
1.1389 + this->getLastPt(&start);
1.1390 + // Handle degenerate cases by adding a line to the first point and
1.1391 + // bailing out.
1.1392 + if ((x1 == start.fX && y1 == start.fY) ||
1.1393 + (x1 == x2 && y1 == y2) ||
1.1394 + radius == 0) {
1.1395 + this->lineTo(x1, y1);
1.1396 + return;
1.1397 + }
1.1398 + before.setNormalize(x1 - start.fX, y1 - start.fY);
1.1399 + after.setNormalize(x2 - x1, y2 - y1);
1.1400 + }
1.1401 +
1.1402 + SkScalar cosh = SkPoint::DotProduct(before, after);
1.1403 + SkScalar sinh = SkPoint::CrossProduct(before, after);
1.1404 +
1.1405 + if (SkScalarNearlyZero(sinh)) { // angle is too tight
1.1406 + this->lineTo(x1, y1);
1.1407 + return;
1.1408 + }
1.1409 +
1.1410 + SkScalar dist = SkScalarMulDiv(radius, SK_Scalar1 - cosh, sinh);
1.1411 + if (dist < 0) {
1.1412 + dist = -dist;
1.1413 + }
1.1414 +
1.1415 + SkScalar xx = x1 - SkScalarMul(dist, before.fX);
1.1416 + SkScalar yy = y1 - SkScalarMul(dist, before.fY);
1.1417 + SkRotationDirection arcDir;
1.1418 +
1.1419 + // now turn before/after into normals
1.1420 + if (sinh > 0) {
1.1421 + before.rotateCCW();
1.1422 + after.rotateCCW();
1.1423 + arcDir = kCW_SkRotationDirection;
1.1424 + } else {
1.1425 + before.rotateCW();
1.1426 + after.rotateCW();
1.1427 + arcDir = kCCW_SkRotationDirection;
1.1428 + }
1.1429 +
1.1430 + SkMatrix matrix;
1.1431 + SkPoint pts[kSkBuildQuadArcStorage];
1.1432 +
1.1433 + matrix.setScale(radius, radius);
1.1434 + matrix.postTranslate(xx - SkScalarMul(radius, before.fX),
1.1435 + yy - SkScalarMul(radius, before.fY));
1.1436 +
1.1437 + int count = SkBuildQuadArc(before, after, arcDir, &matrix, pts);
1.1438 +
1.1439 + this->incReserve(count);
1.1440 + // [xx,yy] == pts[0]
1.1441 + this->lineTo(xx, yy);
1.1442 + for (int i = 1; i < count; i += 2) {
1.1443 + this->quadTo(pts[i], pts[i+1]);
1.1444 + }
1.1445 +}
1.1446 +
1.1447 +///////////////////////////////////////////////////////////////////////////////
1.1448 +
1.1449 +void SkPath::addPath(const SkPath& path, SkScalar dx, SkScalar dy, AddPathMode mode) {
1.1450 + SkMatrix matrix;
1.1451 +
1.1452 + matrix.setTranslate(dx, dy);
1.1453 + this->addPath(path, matrix, mode);
1.1454 +}
1.1455 +
1.1456 +void SkPath::addPath(const SkPath& path, const SkMatrix& matrix, AddPathMode mode) {
1.1457 + SkPathRef::Editor(&fPathRef, path.countVerbs(), path.countPoints());
1.1458 +
1.1459 + RawIter iter(path);
1.1460 + SkPoint pts[4];
1.1461 + Verb verb;
1.1462 +
1.1463 + SkMatrix::MapPtsProc proc = matrix.getMapPtsProc();
1.1464 + bool firstVerb = true;
1.1465 + while ((verb = iter.next(pts)) != kDone_Verb) {
1.1466 + switch (verb) {
1.1467 + case kMove_Verb:
1.1468 + proc(matrix, &pts[0], &pts[0], 1);
1.1469 + if (firstVerb && mode == kExtend_AddPathMode && !isEmpty()) {
1.1470 + injectMoveToIfNeeded(); // In case last contour is closed
1.1471 + this->lineTo(pts[0]);
1.1472 + } else {
1.1473 + this->moveTo(pts[0]);
1.1474 + }
1.1475 + break;
1.1476 + case kLine_Verb:
1.1477 + proc(matrix, &pts[1], &pts[1], 1);
1.1478 + this->lineTo(pts[1]);
1.1479 + break;
1.1480 + case kQuad_Verb:
1.1481 + proc(matrix, &pts[1], &pts[1], 2);
1.1482 + this->quadTo(pts[1], pts[2]);
1.1483 + break;
1.1484 + case kConic_Verb:
1.1485 + proc(matrix, &pts[1], &pts[1], 2);
1.1486 + this->conicTo(pts[1], pts[2], iter.conicWeight());
1.1487 + break;
1.1488 + case kCubic_Verb:
1.1489 + proc(matrix, &pts[1], &pts[1], 3);
1.1490 + this->cubicTo(pts[1], pts[2], pts[3]);
1.1491 + break;
1.1492 + case kClose_Verb:
1.1493 + this->close();
1.1494 + break;
1.1495 + default:
1.1496 + SkDEBUGFAIL("unknown verb");
1.1497 + }
1.1498 + firstVerb = false;
1.1499 + }
1.1500 +}
1.1501 +
1.1502 +///////////////////////////////////////////////////////////////////////////////
1.1503 +
1.1504 +static int pts_in_verb(unsigned verb) {
1.1505 + static const uint8_t gPtsInVerb[] = {
1.1506 + 1, // kMove
1.1507 + 1, // kLine
1.1508 + 2, // kQuad
1.1509 + 2, // kConic
1.1510 + 3, // kCubic
1.1511 + 0, // kClose
1.1512 + 0 // kDone
1.1513 + };
1.1514 +
1.1515 + SkASSERT(verb < SK_ARRAY_COUNT(gPtsInVerb));
1.1516 + return gPtsInVerb[verb];
1.1517 +}
1.1518 +
1.1519 +// ignore the last point of the 1st contour
1.1520 +void SkPath::reversePathTo(const SkPath& path) {
1.1521 + int i, vcount = path.fPathRef->countVerbs();
1.1522 + // exit early if the path is empty, or just has a moveTo.
1.1523 + if (vcount < 2) {
1.1524 + return;
1.1525 + }
1.1526 +
1.1527 + SkPathRef::Editor(&fPathRef, vcount, path.countPoints());
1.1528 +
1.1529 + const uint8_t* verbs = path.fPathRef->verbs();
1.1530 + const SkPoint* pts = path.fPathRef->points();
1.1531 + const SkScalar* conicWeights = path.fPathRef->conicWeights();
1.1532 +
1.1533 + SkASSERT(verbs[~0] == kMove_Verb);
1.1534 + for (i = 1; i < vcount; ++i) {
1.1535 + unsigned v = verbs[~i];
1.1536 + int n = pts_in_verb(v);
1.1537 + if (n == 0) {
1.1538 + break;
1.1539 + }
1.1540 + pts += n;
1.1541 + conicWeights += (SkPath::kConic_Verb == v);
1.1542 + }
1.1543 +
1.1544 + while (--i > 0) {
1.1545 + switch (verbs[~i]) {
1.1546 + case kLine_Verb:
1.1547 + this->lineTo(pts[-1].fX, pts[-1].fY);
1.1548 + break;
1.1549 + case kQuad_Verb:
1.1550 + this->quadTo(pts[-1].fX, pts[-1].fY, pts[-2].fX, pts[-2].fY);
1.1551 + break;
1.1552 + case kConic_Verb:
1.1553 + this->conicTo(pts[-1], pts[-2], *--conicWeights);
1.1554 + break;
1.1555 + case kCubic_Verb:
1.1556 + this->cubicTo(pts[-1].fX, pts[-1].fY, pts[-2].fX, pts[-2].fY,
1.1557 + pts[-3].fX, pts[-3].fY);
1.1558 + break;
1.1559 + default:
1.1560 + SkDEBUGFAIL("bad verb");
1.1561 + break;
1.1562 + }
1.1563 + pts -= pts_in_verb(verbs[~i]);
1.1564 + }
1.1565 +}
1.1566 +
1.1567 +void SkPath::reverseAddPath(const SkPath& src) {
1.1568 + SkPathRef::Editor ed(&fPathRef, src.fPathRef->countPoints(), src.fPathRef->countVerbs());
1.1569 +
1.1570 + const SkPoint* pts = src.fPathRef->pointsEnd();
1.1571 + // we will iterator through src's verbs backwards
1.1572 + const uint8_t* verbs = src.fPathRef->verbsMemBegin(); // points at the last verb
1.1573 + const uint8_t* verbsEnd = src.fPathRef->verbs(); // points just past the first verb
1.1574 + const SkScalar* conicWeights = src.fPathRef->conicWeightsEnd();
1.1575 +
1.1576 + bool needMove = true;
1.1577 + bool needClose = false;
1.1578 + while (verbs < verbsEnd) {
1.1579 + uint8_t v = *(verbs++);
1.1580 + int n = pts_in_verb(v);
1.1581 +
1.1582 + if (needMove) {
1.1583 + --pts;
1.1584 + this->moveTo(pts->fX, pts->fY);
1.1585 + needMove = false;
1.1586 + }
1.1587 + pts -= n;
1.1588 + switch (v) {
1.1589 + case kMove_Verb:
1.1590 + if (needClose) {
1.1591 + this->close();
1.1592 + needClose = false;
1.1593 + }
1.1594 + needMove = true;
1.1595 + pts += 1; // so we see the point in "if (needMove)" above
1.1596 + break;
1.1597 + case kLine_Verb:
1.1598 + this->lineTo(pts[0]);
1.1599 + break;
1.1600 + case kQuad_Verb:
1.1601 + this->quadTo(pts[1], pts[0]);
1.1602 + break;
1.1603 + case kConic_Verb:
1.1604 + this->conicTo(pts[1], pts[0], *--conicWeights);
1.1605 + break;
1.1606 + case kCubic_Verb:
1.1607 + this->cubicTo(pts[2], pts[1], pts[0]);
1.1608 + break;
1.1609 + case kClose_Verb:
1.1610 + needClose = true;
1.1611 + break;
1.1612 + default:
1.1613 + SkDEBUGFAIL("unexpected verb");
1.1614 + }
1.1615 + }
1.1616 +}
1.1617 +
1.1618 +///////////////////////////////////////////////////////////////////////////////
1.1619 +
1.1620 +void SkPath::offset(SkScalar dx, SkScalar dy, SkPath* dst) const {
1.1621 + SkMatrix matrix;
1.1622 +
1.1623 + matrix.setTranslate(dx, dy);
1.1624 + this->transform(matrix, dst);
1.1625 +}
1.1626 +
1.1627 +#include "SkGeometry.h"
1.1628 +
1.1629 +static void subdivide_quad_to(SkPath* path, const SkPoint pts[3],
1.1630 + int level = 2) {
1.1631 + if (--level >= 0) {
1.1632 + SkPoint tmp[5];
1.1633 +
1.1634 + SkChopQuadAtHalf(pts, tmp);
1.1635 + subdivide_quad_to(path, &tmp[0], level);
1.1636 + subdivide_quad_to(path, &tmp[2], level);
1.1637 + } else {
1.1638 + path->quadTo(pts[1], pts[2]);
1.1639 + }
1.1640 +}
1.1641 +
1.1642 +static void subdivide_cubic_to(SkPath* path, const SkPoint pts[4],
1.1643 + int level = 2) {
1.1644 + if (--level >= 0) {
1.1645 + SkPoint tmp[7];
1.1646 +
1.1647 + SkChopCubicAtHalf(pts, tmp);
1.1648 + subdivide_cubic_to(path, &tmp[0], level);
1.1649 + subdivide_cubic_to(path, &tmp[3], level);
1.1650 + } else {
1.1651 + path->cubicTo(pts[1], pts[2], pts[3]);
1.1652 + }
1.1653 +}
1.1654 +
1.1655 +void SkPath::transform(const SkMatrix& matrix, SkPath* dst) const {
1.1656 + SkDEBUGCODE(this->validate();)
1.1657 + if (dst == NULL) {
1.1658 + dst = (SkPath*)this;
1.1659 + }
1.1660 +
1.1661 + if (matrix.hasPerspective()) {
1.1662 + SkPath tmp;
1.1663 + tmp.fFillType = fFillType;
1.1664 +
1.1665 + SkPath::Iter iter(*this, false);
1.1666 + SkPoint pts[4];
1.1667 + SkPath::Verb verb;
1.1668 +
1.1669 + while ((verb = iter.next(pts, false)) != kDone_Verb) {
1.1670 + switch (verb) {
1.1671 + case kMove_Verb:
1.1672 + tmp.moveTo(pts[0]);
1.1673 + break;
1.1674 + case kLine_Verb:
1.1675 + tmp.lineTo(pts[1]);
1.1676 + break;
1.1677 + case kQuad_Verb:
1.1678 + subdivide_quad_to(&tmp, pts);
1.1679 + break;
1.1680 + case kConic_Verb:
1.1681 + SkDEBUGFAIL("TODO: compute new weight");
1.1682 + tmp.conicTo(pts[1], pts[2], iter.conicWeight());
1.1683 + break;
1.1684 + case kCubic_Verb:
1.1685 + subdivide_cubic_to(&tmp, pts);
1.1686 + break;
1.1687 + case kClose_Verb:
1.1688 + tmp.close();
1.1689 + break;
1.1690 + default:
1.1691 + SkDEBUGFAIL("unknown verb");
1.1692 + break;
1.1693 + }
1.1694 + }
1.1695 +
1.1696 + dst->swap(tmp);
1.1697 + SkPathRef::Editor ed(&dst->fPathRef);
1.1698 + matrix.mapPoints(ed.points(), ed.pathRef()->countPoints());
1.1699 + dst->fDirection = kUnknown_Direction;
1.1700 + } else {
1.1701 + SkPathRef::CreateTransformedCopy(&dst->fPathRef, *fPathRef.get(), matrix);
1.1702 +
1.1703 + if (this != dst) {
1.1704 + dst->fFillType = fFillType;
1.1705 + dst->fConvexity = fConvexity;
1.1706 + }
1.1707 +
1.1708 + if (kUnknown_Direction == fDirection) {
1.1709 + dst->fDirection = kUnknown_Direction;
1.1710 + } else {
1.1711 + SkScalar det2x2 =
1.1712 + SkScalarMul(matrix.get(SkMatrix::kMScaleX), matrix.get(SkMatrix::kMScaleY)) -
1.1713 + SkScalarMul(matrix.get(SkMatrix::kMSkewX), matrix.get(SkMatrix::kMSkewY));
1.1714 + if (det2x2 < 0) {
1.1715 + dst->fDirection = SkPath::OppositeDirection(static_cast<Direction>(fDirection));
1.1716 + } else if (det2x2 > 0) {
1.1717 + dst->fDirection = fDirection;
1.1718 + } else {
1.1719 + dst->fConvexity = kUnknown_Convexity;
1.1720 + dst->fDirection = kUnknown_Direction;
1.1721 + }
1.1722 + }
1.1723 +
1.1724 + SkDEBUGCODE(dst->validate();)
1.1725 + }
1.1726 +}
1.1727 +
1.1728 +///////////////////////////////////////////////////////////////////////////////
1.1729 +///////////////////////////////////////////////////////////////////////////////
1.1730 +
1.1731 +enum SegmentState {
1.1732 + kEmptyContour_SegmentState, // The current contour is empty. We may be
1.1733 + // starting processing or we may have just
1.1734 + // closed a contour.
1.1735 + kAfterMove_SegmentState, // We have seen a move, but nothing else.
1.1736 + kAfterPrimitive_SegmentState // We have seen a primitive but not yet
1.1737 + // closed the path. Also the initial state.
1.1738 +};
1.1739 +
1.1740 +SkPath::Iter::Iter() {
1.1741 +#ifdef SK_DEBUG
1.1742 + fPts = NULL;
1.1743 + fConicWeights = NULL;
1.1744 + fMoveTo.fX = fMoveTo.fY = fLastPt.fX = fLastPt.fY = 0;
1.1745 + fForceClose = fCloseLine = false;
1.1746 + fSegmentState = kEmptyContour_SegmentState;
1.1747 +#endif
1.1748 + // need to init enough to make next() harmlessly return kDone_Verb
1.1749 + fVerbs = NULL;
1.1750 + fVerbStop = NULL;
1.1751 + fNeedClose = false;
1.1752 +}
1.1753 +
1.1754 +SkPath::Iter::Iter(const SkPath& path, bool forceClose) {
1.1755 + this->setPath(path, forceClose);
1.1756 +}
1.1757 +
1.1758 +void SkPath::Iter::setPath(const SkPath& path, bool forceClose) {
1.1759 + fPts = path.fPathRef->points();
1.1760 + fVerbs = path.fPathRef->verbs();
1.1761 + fVerbStop = path.fPathRef->verbsMemBegin();
1.1762 + fConicWeights = path.fPathRef->conicWeights() - 1; // begin one behind
1.1763 + fLastPt.fX = fLastPt.fY = 0;
1.1764 + fMoveTo.fX = fMoveTo.fY = 0;
1.1765 + fForceClose = SkToU8(forceClose);
1.1766 + fNeedClose = false;
1.1767 + fSegmentState = kEmptyContour_SegmentState;
1.1768 +}
1.1769 +
1.1770 +bool SkPath::Iter::isClosedContour() const {
1.1771 + if (fVerbs == NULL || fVerbs == fVerbStop) {
1.1772 + return false;
1.1773 + }
1.1774 + if (fForceClose) {
1.1775 + return true;
1.1776 + }
1.1777 +
1.1778 + const uint8_t* verbs = fVerbs;
1.1779 + const uint8_t* stop = fVerbStop;
1.1780 +
1.1781 + if (kMove_Verb == *(verbs - 1)) {
1.1782 + verbs -= 1; // skip the initial moveto
1.1783 + }
1.1784 +
1.1785 + while (verbs > stop) {
1.1786 + // verbs points one beyond the current verb, decrement first.
1.1787 + unsigned v = *(--verbs);
1.1788 + if (kMove_Verb == v) {
1.1789 + break;
1.1790 + }
1.1791 + if (kClose_Verb == v) {
1.1792 + return true;
1.1793 + }
1.1794 + }
1.1795 + return false;
1.1796 +}
1.1797 +
1.1798 +SkPath::Verb SkPath::Iter::autoClose(SkPoint pts[2]) {
1.1799 + SkASSERT(pts);
1.1800 + if (fLastPt != fMoveTo) {
1.1801 + // A special case: if both points are NaN, SkPoint::operation== returns
1.1802 + // false, but the iterator expects that they are treated as the same.
1.1803 + // (consider SkPoint is a 2-dimension float point).
1.1804 + if (SkScalarIsNaN(fLastPt.fX) || SkScalarIsNaN(fLastPt.fY) ||
1.1805 + SkScalarIsNaN(fMoveTo.fX) || SkScalarIsNaN(fMoveTo.fY)) {
1.1806 + return kClose_Verb;
1.1807 + }
1.1808 +
1.1809 + pts[0] = fLastPt;
1.1810 + pts[1] = fMoveTo;
1.1811 + fLastPt = fMoveTo;
1.1812 + fCloseLine = true;
1.1813 + return kLine_Verb;
1.1814 + } else {
1.1815 + pts[0] = fMoveTo;
1.1816 + return kClose_Verb;
1.1817 + }
1.1818 +}
1.1819 +
1.1820 +const SkPoint& SkPath::Iter::cons_moveTo() {
1.1821 + if (fSegmentState == kAfterMove_SegmentState) {
1.1822 + // Set the first return pt to the move pt
1.1823 + fSegmentState = kAfterPrimitive_SegmentState;
1.1824 + return fMoveTo;
1.1825 + } else {
1.1826 + SkASSERT(fSegmentState == kAfterPrimitive_SegmentState);
1.1827 + // Set the first return pt to the last pt of the previous primitive.
1.1828 + return fPts[-1];
1.1829 + }
1.1830 +}
1.1831 +
1.1832 +void SkPath::Iter::consumeDegenerateSegments() {
1.1833 + // We need to step over anything that will not move the current draw point
1.1834 + // forward before the next move is seen
1.1835 + const uint8_t* lastMoveVerb = 0;
1.1836 + const SkPoint* lastMovePt = 0;
1.1837 + SkPoint lastPt = fLastPt;
1.1838 + while (fVerbs != fVerbStop) {
1.1839 + unsigned verb = *(fVerbs - 1); // fVerbs is one beyond the current verb
1.1840 + switch (verb) {
1.1841 + case kMove_Verb:
1.1842 + // Keep a record of this most recent move
1.1843 + lastMoveVerb = fVerbs;
1.1844 + lastMovePt = fPts;
1.1845 + lastPt = fPts[0];
1.1846 + fVerbs--;
1.1847 + fPts++;
1.1848 + break;
1.1849 +
1.1850 + case kClose_Verb:
1.1851 + // A close when we are in a segment is always valid except when it
1.1852 + // follows a move which follows a segment.
1.1853 + if (fSegmentState == kAfterPrimitive_SegmentState && !lastMoveVerb) {
1.1854 + return;
1.1855 + }
1.1856 + // A close at any other time must be ignored
1.1857 + fVerbs--;
1.1858 + break;
1.1859 +
1.1860 + case kLine_Verb:
1.1861 + if (!IsLineDegenerate(lastPt, fPts[0])) {
1.1862 + if (lastMoveVerb) {
1.1863 + fVerbs = lastMoveVerb;
1.1864 + fPts = lastMovePt;
1.1865 + return;
1.1866 + }
1.1867 + return;
1.1868 + }
1.1869 + // Ignore this line and continue
1.1870 + fVerbs--;
1.1871 + fPts++;
1.1872 + break;
1.1873 +
1.1874 + case kConic_Verb:
1.1875 + case kQuad_Verb:
1.1876 + if (!IsQuadDegenerate(lastPt, fPts[0], fPts[1])) {
1.1877 + if (lastMoveVerb) {
1.1878 + fVerbs = lastMoveVerb;
1.1879 + fPts = lastMovePt;
1.1880 + return;
1.1881 + }
1.1882 + return;
1.1883 + }
1.1884 + // Ignore this line and continue
1.1885 + fVerbs--;
1.1886 + fPts += 2;
1.1887 + fConicWeights += (kConic_Verb == verb);
1.1888 + break;
1.1889 +
1.1890 + case kCubic_Verb:
1.1891 + if (!IsCubicDegenerate(lastPt, fPts[0], fPts[1], fPts[2])) {
1.1892 + if (lastMoveVerb) {
1.1893 + fVerbs = lastMoveVerb;
1.1894 + fPts = lastMovePt;
1.1895 + return;
1.1896 + }
1.1897 + return;
1.1898 + }
1.1899 + // Ignore this line and continue
1.1900 + fVerbs--;
1.1901 + fPts += 3;
1.1902 + break;
1.1903 +
1.1904 + default:
1.1905 + SkDEBUGFAIL("Should never see kDone_Verb");
1.1906 + }
1.1907 + }
1.1908 +}
1.1909 +
1.1910 +SkPath::Verb SkPath::Iter::doNext(SkPoint ptsParam[4]) {
1.1911 + SkASSERT(ptsParam);
1.1912 +
1.1913 + if (fVerbs == fVerbStop) {
1.1914 + // Close the curve if requested and if there is some curve to close
1.1915 + if (fNeedClose && fSegmentState == kAfterPrimitive_SegmentState) {
1.1916 + if (kLine_Verb == this->autoClose(ptsParam)) {
1.1917 + return kLine_Verb;
1.1918 + }
1.1919 + fNeedClose = false;
1.1920 + return kClose_Verb;
1.1921 + }
1.1922 + return kDone_Verb;
1.1923 + }
1.1924 +
1.1925 + // fVerbs is one beyond the current verb, decrement first
1.1926 + unsigned verb = *(--fVerbs);
1.1927 + const SkPoint* SK_RESTRICT srcPts = fPts;
1.1928 + SkPoint* SK_RESTRICT pts = ptsParam;
1.1929 +
1.1930 + switch (verb) {
1.1931 + case kMove_Verb:
1.1932 + if (fNeedClose) {
1.1933 + fVerbs++; // move back one verb
1.1934 + verb = this->autoClose(pts);
1.1935 + if (verb == kClose_Verb) {
1.1936 + fNeedClose = false;
1.1937 + }
1.1938 + return (Verb)verb;
1.1939 + }
1.1940 + if (fVerbs == fVerbStop) { // might be a trailing moveto
1.1941 + return kDone_Verb;
1.1942 + }
1.1943 + fMoveTo = *srcPts;
1.1944 + pts[0] = *srcPts;
1.1945 + srcPts += 1;
1.1946 + fSegmentState = kAfterMove_SegmentState;
1.1947 + fLastPt = fMoveTo;
1.1948 + fNeedClose = fForceClose;
1.1949 + break;
1.1950 + case kLine_Verb:
1.1951 + pts[0] = this->cons_moveTo();
1.1952 + pts[1] = srcPts[0];
1.1953 + fLastPt = srcPts[0];
1.1954 + fCloseLine = false;
1.1955 + srcPts += 1;
1.1956 + break;
1.1957 + case kConic_Verb:
1.1958 + fConicWeights += 1;
1.1959 + // fall-through
1.1960 + case kQuad_Verb:
1.1961 + pts[0] = this->cons_moveTo();
1.1962 + memcpy(&pts[1], srcPts, 2 * sizeof(SkPoint));
1.1963 + fLastPt = srcPts[1];
1.1964 + srcPts += 2;
1.1965 + break;
1.1966 + case kCubic_Verb:
1.1967 + pts[0] = this->cons_moveTo();
1.1968 + memcpy(&pts[1], srcPts, 3 * sizeof(SkPoint));
1.1969 + fLastPt = srcPts[2];
1.1970 + srcPts += 3;
1.1971 + break;
1.1972 + case kClose_Verb:
1.1973 + verb = this->autoClose(pts);
1.1974 + if (verb == kLine_Verb) {
1.1975 + fVerbs++; // move back one verb
1.1976 + } else {
1.1977 + fNeedClose = false;
1.1978 + fSegmentState = kEmptyContour_SegmentState;
1.1979 + }
1.1980 + fLastPt = fMoveTo;
1.1981 + break;
1.1982 + }
1.1983 + fPts = srcPts;
1.1984 + return (Verb)verb;
1.1985 +}
1.1986 +
1.1987 +///////////////////////////////////////////////////////////////////////////////
1.1988 +
1.1989 +SkPath::RawIter::RawIter() {
1.1990 +#ifdef SK_DEBUG
1.1991 + fPts = NULL;
1.1992 + fConicWeights = NULL;
1.1993 + fMoveTo.fX = fMoveTo.fY = fLastPt.fX = fLastPt.fY = 0;
1.1994 +#endif
1.1995 + // need to init enough to make next() harmlessly return kDone_Verb
1.1996 + fVerbs = NULL;
1.1997 + fVerbStop = NULL;
1.1998 +}
1.1999 +
1.2000 +SkPath::RawIter::RawIter(const SkPath& path) {
1.2001 + this->setPath(path);
1.2002 +}
1.2003 +
1.2004 +void SkPath::RawIter::setPath(const SkPath& path) {
1.2005 + fPts = path.fPathRef->points();
1.2006 + fVerbs = path.fPathRef->verbs();
1.2007 + fVerbStop = path.fPathRef->verbsMemBegin();
1.2008 + fConicWeights = path.fPathRef->conicWeights() - 1; // begin one behind
1.2009 + fMoveTo.fX = fMoveTo.fY = 0;
1.2010 + fLastPt.fX = fLastPt.fY = 0;
1.2011 +}
1.2012 +
1.2013 +SkPath::Verb SkPath::RawIter::next(SkPoint pts[4]) {
1.2014 + SkASSERT(NULL != pts);
1.2015 + if (fVerbs == fVerbStop) {
1.2016 + return kDone_Verb;
1.2017 + }
1.2018 +
1.2019 + // fVerbs points one beyond next verb so decrement first.
1.2020 + unsigned verb = *(--fVerbs);
1.2021 + const SkPoint* srcPts = fPts;
1.2022 +
1.2023 + switch (verb) {
1.2024 + case kMove_Verb:
1.2025 + pts[0] = *srcPts;
1.2026 + fMoveTo = srcPts[0];
1.2027 + fLastPt = fMoveTo;
1.2028 + srcPts += 1;
1.2029 + break;
1.2030 + case kLine_Verb:
1.2031 + pts[0] = fLastPt;
1.2032 + pts[1] = srcPts[0];
1.2033 + fLastPt = srcPts[0];
1.2034 + srcPts += 1;
1.2035 + break;
1.2036 + case kConic_Verb:
1.2037 + fConicWeights += 1;
1.2038 + // fall-through
1.2039 + case kQuad_Verb:
1.2040 + pts[0] = fLastPt;
1.2041 + memcpy(&pts[1], srcPts, 2 * sizeof(SkPoint));
1.2042 + fLastPt = srcPts[1];
1.2043 + srcPts += 2;
1.2044 + break;
1.2045 + case kCubic_Verb:
1.2046 + pts[0] = fLastPt;
1.2047 + memcpy(&pts[1], srcPts, 3 * sizeof(SkPoint));
1.2048 + fLastPt = srcPts[2];
1.2049 + srcPts += 3;
1.2050 + break;
1.2051 + case kClose_Verb:
1.2052 + fLastPt = fMoveTo;
1.2053 + pts[0] = fMoveTo;
1.2054 + break;
1.2055 + }
1.2056 + fPts = srcPts;
1.2057 + return (Verb)verb;
1.2058 +}
1.2059 +
1.2060 +///////////////////////////////////////////////////////////////////////////////
1.2061 +
1.2062 +/*
1.2063 + Format in compressed buffer: [ptCount, verbCount, pts[], verbs[]]
1.2064 +*/
1.2065 +
1.2066 +size_t SkPath::writeToMemory(void* storage) const {
1.2067 + SkDEBUGCODE(this->validate();)
1.2068 +
1.2069 + if (NULL == storage) {
1.2070 + const int byteCount = sizeof(int32_t) + fPathRef->writeSize();
1.2071 + return SkAlign4(byteCount);
1.2072 + }
1.2073 +
1.2074 + SkWBuffer buffer(storage);
1.2075 +
1.2076 + int32_t packed = (fConvexity << kConvexity_SerializationShift) |
1.2077 + (fFillType << kFillType_SerializationShift) |
1.2078 + (fDirection << kDirection_SerializationShift);
1.2079 +
1.2080 + buffer.write32(packed);
1.2081 +
1.2082 + fPathRef->writeToBuffer(&buffer);
1.2083 +
1.2084 + buffer.padToAlign4();
1.2085 + return buffer.pos();
1.2086 +}
1.2087 +
1.2088 +size_t SkPath::readFromMemory(const void* storage, size_t length) {
1.2089 + SkRBufferWithSizeCheck buffer(storage, length);
1.2090 +
1.2091 + int32_t packed;
1.2092 + if (!buffer.readS32(&packed)) {
1.2093 + return 0;
1.2094 + }
1.2095 +
1.2096 + fConvexity = (packed >> kConvexity_SerializationShift) & 0xFF;
1.2097 + fFillType = (packed >> kFillType_SerializationShift) & 0xFF;
1.2098 + fDirection = (packed >> kDirection_SerializationShift) & 0x3;
1.2099 + SkPathRef* pathRef = SkPathRef::CreateFromBuffer(&buffer);
1.2100 +
1.2101 + size_t sizeRead = 0;
1.2102 + if (buffer.isValid()) {
1.2103 + fPathRef.reset(pathRef);
1.2104 + SkDEBUGCODE(this->validate();)
1.2105 + buffer.skipToAlign4();
1.2106 + sizeRead = buffer.pos();
1.2107 + } else if (NULL != pathRef) {
1.2108 + // If the buffer is not valid, pathRef should be NULL
1.2109 + sk_throw();
1.2110 + }
1.2111 + return sizeRead;
1.2112 +}
1.2113 +
1.2114 +///////////////////////////////////////////////////////////////////////////////
1.2115 +
1.2116 +#include "SkString.h"
1.2117 +
1.2118 +static void append_scalar(SkString* str, SkScalar value) {
1.2119 + SkString tmp;
1.2120 + tmp.printf("%g", value);
1.2121 + if (tmp.contains('.')) {
1.2122 + tmp.appendUnichar('f');
1.2123 + }
1.2124 + str->append(tmp);
1.2125 +}
1.2126 +
1.2127 +static void append_params(SkString* str, const char label[], const SkPoint pts[],
1.2128 + int count, SkScalar conicWeight = -1) {
1.2129 + str->append(label);
1.2130 + str->append("(");
1.2131 +
1.2132 + const SkScalar* values = &pts[0].fX;
1.2133 + count *= 2;
1.2134 +
1.2135 + for (int i = 0; i < count; ++i) {
1.2136 + append_scalar(str, values[i]);
1.2137 + if (i < count - 1) {
1.2138 + str->append(", ");
1.2139 + }
1.2140 + }
1.2141 + if (conicWeight >= 0) {
1.2142 + str->append(", ");
1.2143 + append_scalar(str, conicWeight);
1.2144 + }
1.2145 + str->append(");\n");
1.2146 +}
1.2147 +
1.2148 +void SkPath::dump(bool forceClose, const char title[]) const {
1.2149 + Iter iter(*this, forceClose);
1.2150 + SkPoint pts[4];
1.2151 + Verb verb;
1.2152 +
1.2153 + SkDebugf("path: forceClose=%s %s\n", forceClose ? "true" : "false",
1.2154 + title ? title : "");
1.2155 +
1.2156 + SkString builder;
1.2157 +
1.2158 + while ((verb = iter.next(pts, false)) != kDone_Verb) {
1.2159 + switch (verb) {
1.2160 + case kMove_Verb:
1.2161 + append_params(&builder, "path.moveTo", &pts[0], 1);
1.2162 + break;
1.2163 + case kLine_Verb:
1.2164 + append_params(&builder, "path.lineTo", &pts[1], 1);
1.2165 + break;
1.2166 + case kQuad_Verb:
1.2167 + append_params(&builder, "path.quadTo", &pts[1], 2);
1.2168 + break;
1.2169 + case kConic_Verb:
1.2170 + append_params(&builder, "path.conicTo", &pts[1], 2, iter.conicWeight());
1.2171 + break;
1.2172 + case kCubic_Verb:
1.2173 + append_params(&builder, "path.cubicTo", &pts[1], 3);
1.2174 + break;
1.2175 + case kClose_Verb:
1.2176 + builder.append("path.close();\n");
1.2177 + break;
1.2178 + default:
1.2179 + SkDebugf(" path: UNKNOWN VERB %d, aborting dump...\n", verb);
1.2180 + verb = kDone_Verb; // stop the loop
1.2181 + break;
1.2182 + }
1.2183 + }
1.2184 + SkDebugf("%s\n", builder.c_str());
1.2185 +}
1.2186 +
1.2187 +void SkPath::dump() const {
1.2188 + this->dump(false);
1.2189 +}
1.2190 +
1.2191 +#ifdef SK_DEBUG
1.2192 +void SkPath::validate() const {
1.2193 + SkASSERT(this != NULL);
1.2194 + SkASSERT((fFillType & ~3) == 0);
1.2195 +
1.2196 +#ifdef SK_DEBUG_PATH
1.2197 + if (!fBoundsIsDirty) {
1.2198 + SkRect bounds;
1.2199 +
1.2200 + bool isFinite = compute_pt_bounds(&bounds, *fPathRef.get());
1.2201 + SkASSERT(SkToBool(fIsFinite) == isFinite);
1.2202 +
1.2203 + if (fPathRef->countPoints() <= 1) {
1.2204 + // if we're empty, fBounds may be empty but translated, so we can't
1.2205 + // necessarily compare to bounds directly
1.2206 + // try path.addOval(2, 2, 2, 2) which is empty, but the bounds will
1.2207 + // be [2, 2, 2, 2]
1.2208 + SkASSERT(bounds.isEmpty());
1.2209 + SkASSERT(fBounds.isEmpty());
1.2210 + } else {
1.2211 + if (bounds.isEmpty()) {
1.2212 + SkASSERT(fBounds.isEmpty());
1.2213 + } else {
1.2214 + if (!fBounds.isEmpty()) {
1.2215 + SkASSERT(fBounds.contains(bounds));
1.2216 + }
1.2217 + }
1.2218 + }
1.2219 + }
1.2220 +#endif // SK_DEBUG_PATH
1.2221 +}
1.2222 +#endif // SK_DEBUG
1.2223 +
1.2224 +///////////////////////////////////////////////////////////////////////////////
1.2225 +
1.2226 +static int sign(SkScalar x) { return x < 0; }
1.2227 +#define kValueNeverReturnedBySign 2
1.2228 +
1.2229 +static bool AlmostEqual(SkScalar compA, SkScalar compB) {
1.2230 + // The error epsilon was empirically derived; worse case round rects
1.2231 + // with a mid point outset by 2x float epsilon in tests had an error
1.2232 + // of 12.
1.2233 + const int epsilon = 16;
1.2234 + if (!SkScalarIsFinite(compA) || !SkScalarIsFinite(compB)) {
1.2235 + return false;
1.2236 + }
1.2237 + // no need to check for small numbers because SkPath::Iter has removed degenerate values
1.2238 + int aBits = SkFloatAs2sCompliment(compA);
1.2239 + int bBits = SkFloatAs2sCompliment(compB);
1.2240 + return aBits < bBits + epsilon && bBits < aBits + epsilon;
1.2241 +}
1.2242 +
1.2243 +// only valid for a single contour
1.2244 +struct Convexicator {
1.2245 + Convexicator()
1.2246 + : fPtCount(0)
1.2247 + , fConvexity(SkPath::kConvex_Convexity)
1.2248 + , fDirection(SkPath::kUnknown_Direction) {
1.2249 + fSign = 0;
1.2250 + // warnings
1.2251 + fLastPt.set(0, 0);
1.2252 + fCurrPt.set(0, 0);
1.2253 + fVec0.set(0, 0);
1.2254 + fVec1.set(0, 0);
1.2255 + fFirstVec.set(0, 0);
1.2256 +
1.2257 + fDx = fDy = 0;
1.2258 + fSx = fSy = kValueNeverReturnedBySign;
1.2259 + }
1.2260 +
1.2261 + SkPath::Convexity getConvexity() const { return fConvexity; }
1.2262 +
1.2263 + /** The direction returned is only valid if the path is determined convex */
1.2264 + SkPath::Direction getDirection() const { return fDirection; }
1.2265 +
1.2266 + void addPt(const SkPoint& pt) {
1.2267 + if (SkPath::kConcave_Convexity == fConvexity) {
1.2268 + return;
1.2269 + }
1.2270 +
1.2271 + if (0 == fPtCount) {
1.2272 + fCurrPt = pt;
1.2273 + ++fPtCount;
1.2274 + } else {
1.2275 + SkVector vec = pt - fCurrPt;
1.2276 + if (vec.fX || vec.fY) {
1.2277 + fLastPt = fCurrPt;
1.2278 + fCurrPt = pt;
1.2279 + if (++fPtCount == 2) {
1.2280 + fFirstVec = fVec1 = vec;
1.2281 + } else {
1.2282 + SkASSERT(fPtCount > 2);
1.2283 + this->addVec(vec);
1.2284 + }
1.2285 +
1.2286 + int sx = sign(vec.fX);
1.2287 + int sy = sign(vec.fY);
1.2288 + fDx += (sx != fSx);
1.2289 + fDy += (sy != fSy);
1.2290 + fSx = sx;
1.2291 + fSy = sy;
1.2292 +
1.2293 + if (fDx > 3 || fDy > 3) {
1.2294 + fConvexity = SkPath::kConcave_Convexity;
1.2295 + }
1.2296 + }
1.2297 + }
1.2298 + }
1.2299 +
1.2300 + void close() {
1.2301 + if (fPtCount > 2) {
1.2302 + this->addVec(fFirstVec);
1.2303 + }
1.2304 + }
1.2305 +
1.2306 +private:
1.2307 + void addVec(const SkVector& vec) {
1.2308 + SkASSERT(vec.fX || vec.fY);
1.2309 + fVec0 = fVec1;
1.2310 + fVec1 = vec;
1.2311 + SkScalar cross = SkPoint::CrossProduct(fVec0, fVec1);
1.2312 + SkScalar smallest = SkTMin(fCurrPt.fX, SkTMin(fCurrPt.fY, SkTMin(fLastPt.fX, fLastPt.fY)));
1.2313 + SkScalar largest = SkTMax(fCurrPt.fX, SkTMax(fCurrPt.fY, SkTMax(fLastPt.fX, fLastPt.fY)));
1.2314 + largest = SkTMax(largest, -smallest);
1.2315 + int sign = AlmostEqual(largest, largest + cross) ? 0 : SkScalarSignAsInt(cross);
1.2316 + if (0 == fSign) {
1.2317 + fSign = sign;
1.2318 + if (1 == sign) {
1.2319 + fDirection = SkPath::kCW_Direction;
1.2320 + } else if (-1 == sign) {
1.2321 + fDirection = SkPath::kCCW_Direction;
1.2322 + }
1.2323 + } else if (sign) {
1.2324 + if (fSign != sign) {
1.2325 + fConvexity = SkPath::kConcave_Convexity;
1.2326 + fDirection = SkPath::kUnknown_Direction;
1.2327 + }
1.2328 + }
1.2329 + }
1.2330 +
1.2331 + SkPoint fLastPt;
1.2332 + SkPoint fCurrPt;
1.2333 + SkVector fVec0, fVec1, fFirstVec;
1.2334 + int fPtCount; // non-degenerate points
1.2335 + int fSign;
1.2336 + SkPath::Convexity fConvexity;
1.2337 + SkPath::Direction fDirection;
1.2338 + int fDx, fDy, fSx, fSy;
1.2339 +};
1.2340 +
1.2341 +SkPath::Convexity SkPath::internalGetConvexity() const {
1.2342 + SkASSERT(kUnknown_Convexity == fConvexity);
1.2343 + SkPoint pts[4];
1.2344 + SkPath::Verb verb;
1.2345 + SkPath::Iter iter(*this, true);
1.2346 +
1.2347 + int contourCount = 0;
1.2348 + int count;
1.2349 + Convexicator state;
1.2350 +
1.2351 + while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
1.2352 + switch (verb) {
1.2353 + case kMove_Verb:
1.2354 + if (++contourCount > 1) {
1.2355 + fConvexity = kConcave_Convexity;
1.2356 + return kConcave_Convexity;
1.2357 + }
1.2358 + pts[1] = pts[0];
1.2359 + count = 1;
1.2360 + break;
1.2361 + case kLine_Verb: count = 1; break;
1.2362 + case kQuad_Verb: count = 2; break;
1.2363 + case kConic_Verb: count = 2; break;
1.2364 + case kCubic_Verb: count = 3; break;
1.2365 + case kClose_Verb:
1.2366 + state.close();
1.2367 + count = 0;
1.2368 + break;
1.2369 + default:
1.2370 + SkDEBUGFAIL("bad verb");
1.2371 + fConvexity = kConcave_Convexity;
1.2372 + return kConcave_Convexity;
1.2373 + }
1.2374 +
1.2375 + for (int i = 1; i <= count; i++) {
1.2376 + state.addPt(pts[i]);
1.2377 + }
1.2378 + // early exit
1.2379 + if (kConcave_Convexity == state.getConvexity()) {
1.2380 + fConvexity = kConcave_Convexity;
1.2381 + return kConcave_Convexity;
1.2382 + }
1.2383 + }
1.2384 + fConvexity = state.getConvexity();
1.2385 + if (kConvex_Convexity == fConvexity && kUnknown_Direction == fDirection) {
1.2386 + fDirection = state.getDirection();
1.2387 + }
1.2388 + return static_cast<Convexity>(fConvexity);
1.2389 +}
1.2390 +
1.2391 +///////////////////////////////////////////////////////////////////////////////
1.2392 +
1.2393 +class ContourIter {
1.2394 +public:
1.2395 + ContourIter(const SkPathRef& pathRef);
1.2396 +
1.2397 + bool done() const { return fDone; }
1.2398 + // if !done() then these may be called
1.2399 + int count() const { return fCurrPtCount; }
1.2400 + const SkPoint* pts() const { return fCurrPt; }
1.2401 + void next();
1.2402 +
1.2403 +private:
1.2404 + int fCurrPtCount;
1.2405 + const SkPoint* fCurrPt;
1.2406 + const uint8_t* fCurrVerb;
1.2407 + const uint8_t* fStopVerbs;
1.2408 + const SkScalar* fCurrConicWeight;
1.2409 + bool fDone;
1.2410 + SkDEBUGCODE(int fContourCounter;)
1.2411 +};
1.2412 +
1.2413 +ContourIter::ContourIter(const SkPathRef& pathRef) {
1.2414 + fStopVerbs = pathRef.verbsMemBegin();
1.2415 + fDone = false;
1.2416 + fCurrPt = pathRef.points();
1.2417 + fCurrVerb = pathRef.verbs();
1.2418 + fCurrConicWeight = pathRef.conicWeights();
1.2419 + fCurrPtCount = 0;
1.2420 + SkDEBUGCODE(fContourCounter = 0;)
1.2421 + this->next();
1.2422 +}
1.2423 +
1.2424 +void ContourIter::next() {
1.2425 + if (fCurrVerb <= fStopVerbs) {
1.2426 + fDone = true;
1.2427 + }
1.2428 + if (fDone) {
1.2429 + return;
1.2430 + }
1.2431 +
1.2432 + // skip pts of prev contour
1.2433 + fCurrPt += fCurrPtCount;
1.2434 +
1.2435 + SkASSERT(SkPath::kMove_Verb == fCurrVerb[~0]);
1.2436 + int ptCount = 1; // moveTo
1.2437 + const uint8_t* verbs = fCurrVerb;
1.2438 +
1.2439 + for (--verbs; verbs > fStopVerbs; --verbs) {
1.2440 + switch (verbs[~0]) {
1.2441 + case SkPath::kMove_Verb:
1.2442 + goto CONTOUR_END;
1.2443 + case SkPath::kLine_Verb:
1.2444 + ptCount += 1;
1.2445 + break;
1.2446 + case SkPath::kConic_Verb:
1.2447 + fCurrConicWeight += 1;
1.2448 + // fall-through
1.2449 + case SkPath::kQuad_Verb:
1.2450 + ptCount += 2;
1.2451 + break;
1.2452 + case SkPath::kCubic_Verb:
1.2453 + ptCount += 3;
1.2454 + break;
1.2455 + case SkPath::kClose_Verb:
1.2456 + break;
1.2457 + default:
1.2458 + SkDEBUGFAIL("unexpected verb");
1.2459 + break;
1.2460 + }
1.2461 + }
1.2462 +CONTOUR_END:
1.2463 + fCurrPtCount = ptCount;
1.2464 + fCurrVerb = verbs;
1.2465 + SkDEBUGCODE(++fContourCounter;)
1.2466 +}
1.2467 +
1.2468 +// returns cross product of (p1 - p0) and (p2 - p0)
1.2469 +static SkScalar cross_prod(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) {
1.2470 + SkScalar cross = SkPoint::CrossProduct(p1 - p0, p2 - p0);
1.2471 + // We may get 0 when the above subtracts underflow. We expect this to be
1.2472 + // very rare and lazily promote to double.
1.2473 + if (0 == cross) {
1.2474 + double p0x = SkScalarToDouble(p0.fX);
1.2475 + double p0y = SkScalarToDouble(p0.fY);
1.2476 +
1.2477 + double p1x = SkScalarToDouble(p1.fX);
1.2478 + double p1y = SkScalarToDouble(p1.fY);
1.2479 +
1.2480 + double p2x = SkScalarToDouble(p2.fX);
1.2481 + double p2y = SkScalarToDouble(p2.fY);
1.2482 +
1.2483 + cross = SkDoubleToScalar((p1x - p0x) * (p2y - p0y) -
1.2484 + (p1y - p0y) * (p2x - p0x));
1.2485 +
1.2486 + }
1.2487 + return cross;
1.2488 +}
1.2489 +
1.2490 +// Returns the first pt with the maximum Y coordinate
1.2491 +static int find_max_y(const SkPoint pts[], int count) {
1.2492 + SkASSERT(count > 0);
1.2493 + SkScalar max = pts[0].fY;
1.2494 + int firstIndex = 0;
1.2495 + for (int i = 1; i < count; ++i) {
1.2496 + SkScalar y = pts[i].fY;
1.2497 + if (y > max) {
1.2498 + max = y;
1.2499 + firstIndex = i;
1.2500 + }
1.2501 + }
1.2502 + return firstIndex;
1.2503 +}
1.2504 +
1.2505 +static int find_diff_pt(const SkPoint pts[], int index, int n, int inc) {
1.2506 + int i = index;
1.2507 + for (;;) {
1.2508 + i = (i + inc) % n;
1.2509 + if (i == index) { // we wrapped around, so abort
1.2510 + break;
1.2511 + }
1.2512 + if (pts[index] != pts[i]) { // found a different point, success!
1.2513 + break;
1.2514 + }
1.2515 + }
1.2516 + return i;
1.2517 +}
1.2518 +
1.2519 +/**
1.2520 + * Starting at index, and moving forward (incrementing), find the xmin and
1.2521 + * xmax of the contiguous points that have the same Y.
1.2522 + */
1.2523 +static int find_min_max_x_at_y(const SkPoint pts[], int index, int n,
1.2524 + int* maxIndexPtr) {
1.2525 + const SkScalar y = pts[index].fY;
1.2526 + SkScalar min = pts[index].fX;
1.2527 + SkScalar max = min;
1.2528 + int minIndex = index;
1.2529 + int maxIndex = index;
1.2530 + for (int i = index + 1; i < n; ++i) {
1.2531 + if (pts[i].fY != y) {
1.2532 + break;
1.2533 + }
1.2534 + SkScalar x = pts[i].fX;
1.2535 + if (x < min) {
1.2536 + min = x;
1.2537 + minIndex = i;
1.2538 + } else if (x > max) {
1.2539 + max = x;
1.2540 + maxIndex = i;
1.2541 + }
1.2542 + }
1.2543 + *maxIndexPtr = maxIndex;
1.2544 + return minIndex;
1.2545 +}
1.2546 +
1.2547 +static void crossToDir(SkScalar cross, SkPath::Direction* dir) {
1.2548 + *dir = cross > 0 ? SkPath::kCW_Direction : SkPath::kCCW_Direction;
1.2549 +}
1.2550 +
1.2551 +/*
1.2552 + * We loop through all contours, and keep the computed cross-product of the
1.2553 + * contour that contained the global y-max. If we just look at the first
1.2554 + * contour, we may find one that is wound the opposite way (correctly) since
1.2555 + * it is the interior of a hole (e.g. 'o'). Thus we must find the contour
1.2556 + * that is outer most (or at least has the global y-max) before we can consider
1.2557 + * its cross product.
1.2558 + */
1.2559 +bool SkPath::cheapComputeDirection(Direction* dir) const {
1.2560 + if (kUnknown_Direction != fDirection) {
1.2561 + *dir = static_cast<Direction>(fDirection);
1.2562 + return true;
1.2563 + }
1.2564 +
1.2565 + // don't want to pay the cost for computing this if it
1.2566 + // is unknown, so we don't call isConvex()
1.2567 + if (kConvex_Convexity == this->getConvexityOrUnknown()) {
1.2568 + SkASSERT(kUnknown_Direction == fDirection);
1.2569 + *dir = static_cast<Direction>(fDirection);
1.2570 + return false;
1.2571 + }
1.2572 +
1.2573 + ContourIter iter(*fPathRef.get());
1.2574 +
1.2575 + // initialize with our logical y-min
1.2576 + SkScalar ymax = this->getBounds().fTop;
1.2577 + SkScalar ymaxCross = 0;
1.2578 +
1.2579 + for (; !iter.done(); iter.next()) {
1.2580 + int n = iter.count();
1.2581 + if (n < 3) {
1.2582 + continue;
1.2583 + }
1.2584 +
1.2585 + const SkPoint* pts = iter.pts();
1.2586 + SkScalar cross = 0;
1.2587 + int index = find_max_y(pts, n);
1.2588 + if (pts[index].fY < ymax) {
1.2589 + continue;
1.2590 + }
1.2591 +
1.2592 + // If there is more than 1 distinct point at the y-max, we take the
1.2593 + // x-min and x-max of them and just subtract to compute the dir.
1.2594 + if (pts[(index + 1) % n].fY == pts[index].fY) {
1.2595 + int maxIndex;
1.2596 + int minIndex = find_min_max_x_at_y(pts, index, n, &maxIndex);
1.2597 + if (minIndex == maxIndex) {
1.2598 + goto TRY_CROSSPROD;
1.2599 + }
1.2600 + SkASSERT(pts[minIndex].fY == pts[index].fY);
1.2601 + SkASSERT(pts[maxIndex].fY == pts[index].fY);
1.2602 + SkASSERT(pts[minIndex].fX <= pts[maxIndex].fX);
1.2603 + // we just subtract the indices, and let that auto-convert to
1.2604 + // SkScalar, since we just want - or + to signal the direction.
1.2605 + cross = minIndex - maxIndex;
1.2606 + } else {
1.2607 + TRY_CROSSPROD:
1.2608 + // Find a next and prev index to use for the cross-product test,
1.2609 + // but we try to find pts that form non-zero vectors from pts[index]
1.2610 + //
1.2611 + // Its possible that we can't find two non-degenerate vectors, so
1.2612 + // we have to guard our search (e.g. all the pts could be in the
1.2613 + // same place).
1.2614 +
1.2615 + // we pass n - 1 instead of -1 so we don't foul up % operator by
1.2616 + // passing it a negative LH argument.
1.2617 + int prev = find_diff_pt(pts, index, n, n - 1);
1.2618 + if (prev == index) {
1.2619 + // completely degenerate, skip to next contour
1.2620 + continue;
1.2621 + }
1.2622 + int next = find_diff_pt(pts, index, n, 1);
1.2623 + SkASSERT(next != index);
1.2624 + cross = cross_prod(pts[prev], pts[index], pts[next]);
1.2625 + // if we get a zero and the points are horizontal, then we look at the spread in
1.2626 + // x-direction. We really should continue to walk away from the degeneracy until
1.2627 + // there is a divergence.
1.2628 + if (0 == cross && pts[prev].fY == pts[index].fY && pts[next].fY == pts[index].fY) {
1.2629 + // construct the subtract so we get the correct Direction below
1.2630 + cross = pts[index].fX - pts[next].fX;
1.2631 + }
1.2632 + }
1.2633 +
1.2634 + if (cross) {
1.2635 + // record our best guess so far
1.2636 + ymax = pts[index].fY;
1.2637 + ymaxCross = cross;
1.2638 + }
1.2639 + }
1.2640 + if (ymaxCross) {
1.2641 + crossToDir(ymaxCross, dir);
1.2642 + fDirection = *dir;
1.2643 + return true;
1.2644 + } else {
1.2645 + return false;
1.2646 + }
1.2647 +}
1.2648 +
1.2649 +///////////////////////////////////////////////////////////////////////////////
1.2650 +
1.2651 +static SkScalar eval_cubic_coeff(SkScalar A, SkScalar B, SkScalar C,
1.2652 + SkScalar D, SkScalar t) {
1.2653 + return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D);
1.2654 +}
1.2655 +
1.2656 +static SkScalar eval_cubic_pts(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3,
1.2657 + SkScalar t) {
1.2658 + SkScalar A = c3 + 3*(c1 - c2) - c0;
1.2659 + SkScalar B = 3*(c2 - c1 - c1 + c0);
1.2660 + SkScalar C = 3*(c1 - c0);
1.2661 + SkScalar D = c0;
1.2662 + return eval_cubic_coeff(A, B, C, D, t);
1.2663 +}
1.2664 +
1.2665 +/* Given 4 cubic points (either Xs or Ys), and a target X or Y, compute the
1.2666 + t value such that cubic(t) = target
1.2667 + */
1.2668 +static void chopMonoCubicAt(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3,
1.2669 + SkScalar target, SkScalar* t) {
1.2670 + // SkASSERT(c0 <= c1 && c1 <= c2 && c2 <= c3);
1.2671 + SkASSERT(c0 < target && target < c3);
1.2672 +
1.2673 + SkScalar D = c0 - target;
1.2674 + SkScalar A = c3 + 3*(c1 - c2) - c0;
1.2675 + SkScalar B = 3*(c2 - c1 - c1 + c0);
1.2676 + SkScalar C = 3*(c1 - c0);
1.2677 +
1.2678 + const SkScalar TOLERANCE = SK_Scalar1 / 4096;
1.2679 + SkScalar minT = 0;
1.2680 + SkScalar maxT = SK_Scalar1;
1.2681 + SkScalar mid;
1.2682 + int i;
1.2683 + for (i = 0; i < 16; i++) {
1.2684 + mid = SkScalarAve(minT, maxT);
1.2685 + SkScalar delta = eval_cubic_coeff(A, B, C, D, mid);
1.2686 + if (delta < 0) {
1.2687 + minT = mid;
1.2688 + delta = -delta;
1.2689 + } else {
1.2690 + maxT = mid;
1.2691 + }
1.2692 + if (delta < TOLERANCE) {
1.2693 + break;
1.2694 + }
1.2695 + }
1.2696 + *t = mid;
1.2697 +}
1.2698 +
1.2699 +template <size_t N> static void find_minmax(const SkPoint pts[],
1.2700 + SkScalar* minPtr, SkScalar* maxPtr) {
1.2701 + SkScalar min, max;
1.2702 + min = max = pts[0].fX;
1.2703 + for (size_t i = 1; i < N; ++i) {
1.2704 + min = SkMinScalar(min, pts[i].fX);
1.2705 + max = SkMaxScalar(max, pts[i].fX);
1.2706 + }
1.2707 + *minPtr = min;
1.2708 + *maxPtr = max;
1.2709 +}
1.2710 +
1.2711 +static int winding_mono_cubic(const SkPoint pts[], SkScalar x, SkScalar y) {
1.2712 + SkPoint storage[4];
1.2713 +
1.2714 + int dir = 1;
1.2715 + if (pts[0].fY > pts[3].fY) {
1.2716 + storage[0] = pts[3];
1.2717 + storage[1] = pts[2];
1.2718 + storage[2] = pts[1];
1.2719 + storage[3] = pts[0];
1.2720 + pts = storage;
1.2721 + dir = -1;
1.2722 + }
1.2723 + if (y < pts[0].fY || y >= pts[3].fY) {
1.2724 + return 0;
1.2725 + }
1.2726 +
1.2727 + // quickreject or quickaccept
1.2728 + SkScalar min, max;
1.2729 + find_minmax<4>(pts, &min, &max);
1.2730 + if (x < min) {
1.2731 + return 0;
1.2732 + }
1.2733 + if (x > max) {
1.2734 + return dir;
1.2735 + }
1.2736 +
1.2737 + // compute the actual x(t) value
1.2738 + SkScalar t;
1.2739 + chopMonoCubicAt(pts[0].fY, pts[1].fY, pts[2].fY, pts[3].fY, y, &t);
1.2740 + SkScalar xt = eval_cubic_pts(pts[0].fX, pts[1].fX, pts[2].fX, pts[3].fX, t);
1.2741 + return xt < x ? dir : 0;
1.2742 +}
1.2743 +
1.2744 +static int winding_cubic(const SkPoint pts[], SkScalar x, SkScalar y) {
1.2745 + SkPoint dst[10];
1.2746 + int n = SkChopCubicAtYExtrema(pts, dst);
1.2747 + int w = 0;
1.2748 + for (int i = 0; i <= n; ++i) {
1.2749 + w += winding_mono_cubic(&dst[i * 3], x, y);
1.2750 + }
1.2751 + return w;
1.2752 +}
1.2753 +
1.2754 +static int winding_mono_quad(const SkPoint pts[], SkScalar x, SkScalar y) {
1.2755 + SkScalar y0 = pts[0].fY;
1.2756 + SkScalar y2 = pts[2].fY;
1.2757 +
1.2758 + int dir = 1;
1.2759 + if (y0 > y2) {
1.2760 + SkTSwap(y0, y2);
1.2761 + dir = -1;
1.2762 + }
1.2763 + if (y < y0 || y >= y2) {
1.2764 + return 0;
1.2765 + }
1.2766 +
1.2767 + // bounds check on X (not required. is it faster?)
1.2768 +#if 0
1.2769 + if (pts[0].fX > x && pts[1].fX > x && pts[2].fX > x) {
1.2770 + return 0;
1.2771 + }
1.2772 +#endif
1.2773 +
1.2774 + SkScalar roots[2];
1.2775 + int n = SkFindUnitQuadRoots(pts[0].fY - 2 * pts[1].fY + pts[2].fY,
1.2776 + 2 * (pts[1].fY - pts[0].fY),
1.2777 + pts[0].fY - y,
1.2778 + roots);
1.2779 + SkASSERT(n <= 1);
1.2780 + SkScalar xt;
1.2781 + if (0 == n) {
1.2782 + SkScalar mid = SkScalarAve(y0, y2);
1.2783 + // Need [0] and [2] if dir == 1
1.2784 + // and [2] and [0] if dir == -1
1.2785 + xt = y < mid ? pts[1 - dir].fX : pts[dir - 1].fX;
1.2786 + } else {
1.2787 + SkScalar t = roots[0];
1.2788 + SkScalar C = pts[0].fX;
1.2789 + SkScalar A = pts[2].fX - 2 * pts[1].fX + C;
1.2790 + SkScalar B = 2 * (pts[1].fX - C);
1.2791 + xt = SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C);
1.2792 + }
1.2793 + return xt < x ? dir : 0;
1.2794 +}
1.2795 +
1.2796 +static bool is_mono_quad(SkScalar y0, SkScalar y1, SkScalar y2) {
1.2797 + // return SkScalarSignAsInt(y0 - y1) + SkScalarSignAsInt(y1 - y2) != 0;
1.2798 + if (y0 == y1) {
1.2799 + return true;
1.2800 + }
1.2801 + if (y0 < y1) {
1.2802 + return y1 <= y2;
1.2803 + } else {
1.2804 + return y1 >= y2;
1.2805 + }
1.2806 +}
1.2807 +
1.2808 +static int winding_quad(const SkPoint pts[], SkScalar x, SkScalar y) {
1.2809 + SkPoint dst[5];
1.2810 + int n = 0;
1.2811 +
1.2812 + if (!is_mono_quad(pts[0].fY, pts[1].fY, pts[2].fY)) {
1.2813 + n = SkChopQuadAtYExtrema(pts, dst);
1.2814 + pts = dst;
1.2815 + }
1.2816 + int w = winding_mono_quad(pts, x, y);
1.2817 + if (n > 0) {
1.2818 + w += winding_mono_quad(&pts[2], x, y);
1.2819 + }
1.2820 + return w;
1.2821 +}
1.2822 +
1.2823 +static int winding_line(const SkPoint pts[], SkScalar x, SkScalar y) {
1.2824 + SkScalar x0 = pts[0].fX;
1.2825 + SkScalar y0 = pts[0].fY;
1.2826 + SkScalar x1 = pts[1].fX;
1.2827 + SkScalar y1 = pts[1].fY;
1.2828 +
1.2829 + SkScalar dy = y1 - y0;
1.2830 +
1.2831 + int dir = 1;
1.2832 + if (y0 > y1) {
1.2833 + SkTSwap(y0, y1);
1.2834 + dir = -1;
1.2835 + }
1.2836 + if (y < y0 || y >= y1) {
1.2837 + return 0;
1.2838 + }
1.2839 +
1.2840 + SkScalar cross = SkScalarMul(x1 - x0, y - pts[0].fY) -
1.2841 + SkScalarMul(dy, x - pts[0].fX);
1.2842 +
1.2843 + if (SkScalarSignAsInt(cross) == dir) {
1.2844 + dir = 0;
1.2845 + }
1.2846 + return dir;
1.2847 +}
1.2848 +
1.2849 +static bool contains_inclusive(const SkRect& r, SkScalar x, SkScalar y) {
1.2850 + return r.fLeft <= x && x <= r.fRight && r.fTop <= y && y <= r.fBottom;
1.2851 +}
1.2852 +
1.2853 +bool SkPath::contains(SkScalar x, SkScalar y) const {
1.2854 + bool isInverse = this->isInverseFillType();
1.2855 + if (this->isEmpty()) {
1.2856 + return isInverse;
1.2857 + }
1.2858 +
1.2859 + if (!contains_inclusive(this->getBounds(), x, y)) {
1.2860 + return isInverse;
1.2861 + }
1.2862 +
1.2863 + SkPath::Iter iter(*this, true);
1.2864 + bool done = false;
1.2865 + int w = 0;
1.2866 + do {
1.2867 + SkPoint pts[4];
1.2868 + switch (iter.next(pts, false)) {
1.2869 + case SkPath::kMove_Verb:
1.2870 + case SkPath::kClose_Verb:
1.2871 + break;
1.2872 + case SkPath::kLine_Verb:
1.2873 + w += winding_line(pts, x, y);
1.2874 + break;
1.2875 + case SkPath::kQuad_Verb:
1.2876 + w += winding_quad(pts, x, y);
1.2877 + break;
1.2878 + case SkPath::kConic_Verb:
1.2879 + SkASSERT(0);
1.2880 + break;
1.2881 + case SkPath::kCubic_Verb:
1.2882 + w += winding_cubic(pts, x, y);
1.2883 + break;
1.2884 + case SkPath::kDone_Verb:
1.2885 + done = true;
1.2886 + break;
1.2887 + }
1.2888 + } while (!done);
1.2889 +
1.2890 + switch (this->getFillType()) {
1.2891 + case SkPath::kEvenOdd_FillType:
1.2892 + case SkPath::kInverseEvenOdd_FillType:
1.2893 + w &= 1;
1.2894 + break;
1.2895 + default:
1.2896 + break;
1.2897 + }
1.2898 + return SkToBool(w);
1.2899 +}
