add SkPath::contains(x, y)
git-svn-id: http://skia.googlecode.com/svn/trunk@4526 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/src/core/SkPath.cpp b/src/core/SkPath.cpp
index 3861977..77d0854 100644
--- a/src/core/SkPath.cpp
+++ b/src/core/SkPath.cpp
@@ -2255,3 +2255,253 @@
return ymaxCross ? crossToDir(ymaxCross, dir) : false;
}
+
+///////////////////////////////////////////////////////////////////////////////
+
+static SkScalar eval_cubic_coeff(SkScalar A, SkScalar B, SkScalar C,
+ SkScalar D, SkScalar t) {
+ return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D);
+}
+
+static SkScalar eval_cubic_pts(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3,
+ SkScalar t) {
+ SkScalar A = c3 + 3*(c1 - c2) - c0;
+ SkScalar B = 3*(c2 - c1 - c1 + c0);
+ SkScalar C = 3*(c1 - c0);
+ SkScalar D = c0;
+ return eval_cubic_coeff(A, B, C, D, t);
+}
+
+/* Given 4 cubic points (either Xs or Ys), and a target X or Y, compute the
+ t value such that cubic(t) = target
+ */
+static bool chopMonoCubicAt(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3,
+ SkScalar target, SkScalar* t) {
+ // SkASSERT(c0 <= c1 && c1 <= c2 && c2 <= c3);
+ SkASSERT(c0 < target && target < c3);
+
+ SkScalar D = c0 - target;
+ SkScalar A = c3 + 3*(c1 - c2) - c0;
+ SkScalar B = 3*(c2 - c1 - c1 + c0);
+ SkScalar C = 3*(c1 - c0);
+
+ const SkScalar TOLERANCE = SK_Scalar1 / 4096;
+ SkScalar minT = 0;
+ SkScalar maxT = SK_Scalar1;
+ SkScalar mid;
+ int i;
+ for (i = 0; i < 16; i++) {
+ mid = SkScalarAve(minT, maxT);
+ SkScalar delta = eval_cubic_coeff(A, B, C, D, mid);
+ if (delta < 0) {
+ minT = mid;
+ delta = -delta;
+ } else {
+ maxT = mid;
+ }
+ if (delta < TOLERANCE) {
+ break;
+ }
+ }
+ *t = mid;
+ return true;
+}
+
+template <size_t N> static void find_minmax(const SkPoint pts[],
+ SkScalar* minPtr, SkScalar* maxPtr) {
+ SkScalar min, max;
+ min = max = pts[0].fX;
+ for (size_t i = 1; i < N; ++i) {
+ min = SkMinScalar(min, pts[i].fX);
+ max = SkMaxScalar(max, pts[i].fX);
+ }
+ *minPtr = min;
+ *maxPtr = max;
+}
+
+static int winding_mono_cubic(const SkPoint pts[], SkScalar x, SkScalar y) {
+ SkPoint storage[4];
+
+ int dir = 1;
+ if (pts[0].fY > pts[3].fY) {
+ storage[0] = pts[3];
+ storage[1] = pts[2];
+ storage[2] = pts[1];
+ storage[3] = pts[0];
+ pts = storage;
+ dir = -1;
+ }
+ if (y < pts[0].fY || y >= pts[3].fY) {
+ return 0;
+ }
+
+ // quickreject or quickaccept
+ SkScalar min, max;
+ find_minmax<4>(pts, &min, &max);
+ if (x < min) {
+ return 0;
+ }
+ if (x > max) {
+ return dir;
+ }
+
+ // compute the actual x(t) value
+ SkScalar t, xt;
+ if (chopMonoCubicAt(pts[0].fY, pts[1].fY, pts[2].fY, pts[3].fY, y, &t)) {
+ xt = eval_cubic_pts(pts[0].fX, pts[1].fX, pts[2].fX, pts[3].fX, t);
+ } else {
+ SkScalar mid = SkScalarAve(pts[0].fY, pts[3].fY);
+ xt = y < mid ? pts[0].fX : pts[3].fX;
+ }
+ return xt < x ? dir : 0;
+}
+
+static int winding_cubic(const SkPoint pts[], SkScalar x, SkScalar y) {
+ SkPoint dst[10];
+ int n = SkChopCubicAtYExtrema(pts, dst);
+ int w = 0;
+ for (int i = 0; i <= n; ++i) {
+ w += winding_mono_cubic(&dst[i * 3], x, y);
+ }
+ return w;
+}
+
+static int winding_mono_quad(const SkPoint pts[], SkScalar x, SkScalar y) {
+ SkScalar y0 = pts[0].fY;
+ SkScalar y2 = pts[2].fY;
+
+ int dir = 1;
+ if (y0 > y2) {
+ SkTSwap(y0, y2);
+ dir = -1;
+ }
+ if (y < y0 || y >= y2) {
+ return 0;
+ }
+
+ // bounds check on X (not required. is it faster?)
+#if 0
+ if (pts[0].fX > x && pts[1].fX > x && pts[2].fX > x) {
+ return 0;
+ }
+#endif
+
+ SkScalar roots[2];
+ int n = SkFindUnitQuadRoots(pts[0].fY - 2 * pts[1].fY + pts[2].fY,
+ 2 * (pts[1].fY - pts[0].fY),
+ pts[0].fY - y,
+ roots);
+ SkASSERT(n <= 1);
+ SkScalar xt;
+ if (0 == n) {
+ SkScalar mid = SkScalarAve(y0, y2);
+ // Need [0] and [2] if dir == 1
+ // and [2] and [0] if dir == -1
+ xt = y < mid ? pts[1 - dir].fX : pts[dir - 1].fX;
+ } else {
+ SkScalar t = roots[0];
+ SkScalar C = pts[0].fX;
+ SkScalar A = pts[2].fX - 2 * pts[1].fX + C;
+ SkScalar B = 2 * (pts[1].fX - C);
+ xt = SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C);
+ }
+ return xt < x ? dir : 0;
+}
+
+static bool is_mono_quad(SkScalar y0, SkScalar y1, SkScalar y2) {
+ // return SkScalarSignAsInt(y0 - y1) + SkScalarSignAsInt(y1 - y2) != 0;
+ if (y0 == y1) {
+ return true;
+ }
+ if (y0 < y1) {
+ return y1 <= y2;
+ } else {
+ return y1 >= y2;
+ }
+}
+
+static int winding_quad(const SkPoint pts[], SkScalar x, SkScalar y) {
+ SkPoint dst[5];
+ int n = 0;
+
+ if (!is_mono_quad(pts[0].fY, pts[1].fY, pts[2].fY)) {
+ n = SkChopQuadAtYExtrema(pts, dst);
+ pts = dst;
+ }
+ int w = winding_mono_quad(pts, x, y);
+ if (n > 0) {
+ w += winding_mono_quad(&pts[2], x, y);
+ }
+ return w;
+}
+
+static int winding_line(const SkPoint pts[], SkScalar x, SkScalar y) {
+ SkScalar x0 = pts[0].fX;
+ SkScalar y0 = pts[0].fY;
+ SkScalar x1 = pts[1].fX;
+ SkScalar y1 = pts[1].fY;
+
+ SkScalar dy = y1 - y0;
+
+ int dir = 1;
+ if (y0 > y1) {
+ SkTSwap(y0, y1);
+ dir = -1;
+ }
+ if (y < y0 || y >= y1) {
+ return 0;
+ }
+
+ SkScalar cross = SkScalarMul(x1 - x0, y - pts[0].fY) -
+ SkScalarMul(dy, x - pts[0].fX);
+
+ if (SkScalarSignAsInt(cross) == dir) {
+ dir = 0;
+ }
+ return dir;
+}
+
+bool SkPath::contains(SkScalar x, SkScalar y) const {
+ bool isInverse = this->isInverseFillType();
+ if (this->isEmpty()) {
+ return isInverse;
+ }
+
+ const SkRect& bounds = this->getBounds();
+ if (!bounds.contains(x, y)) {
+ return isInverse;
+ }
+
+ SkPath::Iter iter(*this, true);
+ bool done = false;
+ int w = 0;
+ do {
+ SkPoint pts[4];
+ switch (iter.next(pts, false)) {
+ case SkPath::kMove_Verb:
+ case SkPath::kClose_Verb:
+ break;
+ case SkPath::kLine_Verb:
+ w += winding_line(pts, x, y);
+ break;
+ case SkPath::kQuad_Verb:
+ w += winding_quad(pts, x, y);
+ break;
+ case SkPath::kCubic_Verb:
+ w += winding_cubic(pts, x, y);
+ break;
+ case SkPath::kDone_Verb:
+ done = true;
+ break;
+ }
+ } while (!done);
+
+ switch (this->getFillType()) {
+ case SkPath::kEvenOdd_FillType:
+ case SkPath::kInverseEvenOdd_FillType:
+ w &= 1;
+ break;
+ }
+ return SkToBool(w);
+}
+