aboutsummaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
Diffstat
-rw-r--r--gm/hittestpath.cpp36
-rw-r--r--include/core/SkPath.h6
-rw-r--r--include/utils/SkCullPoints.h1
-rw-r--r--src/core/SkPath.cpp250
-rw-r--r--src/utils/SkCullPoints.cpp251
5 files changed, 271 insertions, 273 deletions
diff --git a/gm/hittestpath.cpp b/gm/hittestpath.cpp
index 06f89e4dd2..83f3507da1 100644
--- a/gm/hittestpath.cpp
+++ b/gm/hittestpath.cpp
@@ -10,7 +10,7 @@
#include "SkCullPoints.h"
#include "SkRandom.h"
-static void test_hittest(SkCanvas* canvas, const SkPath& path, bool hires) {
+static void test_hittest(SkCanvas* canvas, const SkPath& path) {
SkPaint paint;
SkRect r = path.getBounds();
@@ -22,14 +22,8 @@ static void test_hittest(SkCanvas* canvas, const SkPath& path, bool hires) {
paint.setColor(0x800000FF);
for (SkScalar y = r.fTop + SK_ScalarHalf - MARGIN; y < r.fBottom + MARGIN; y += SK_Scalar1) {
for (SkScalar x = r.fLeft + SK_ScalarHalf - MARGIN; x < r.fRight + MARGIN; x += SK_Scalar1) {
- if (hires) {
- if (SkHitTestPathEx(path, x, y)) {
- canvas->drawPoint(x, y, paint);
- }
- } else {
- if (SkHitTestPath(path, x, y, false)) {
- canvas->drawPoint(x, y, paint);
- }
+ if (path.contains(x, y)) {
+ canvas->drawPoint(x, y, paint);
}
}
}
@@ -50,25 +44,25 @@ protected:
SkPath path;
SkRandom rand;
- for (int i = 0; i < 5; ++i) {
- path.lineTo(rand.nextUScalar1() * 150, rand.nextUScalar1() * 150);
- path.quadTo(rand.nextUScalar1() * 150, rand.nextUScalar1() * 150,
- rand.nextUScalar1() * 150, rand.nextUScalar1() * 150);
+ int scale = 300;
+ for (int i = 0; i < 4; ++i) {
+ path.lineTo(rand.nextUScalar1() * scale, rand.nextUScalar1() * scale);
+ path.quadTo(rand.nextUScalar1() * scale, rand.nextUScalar1() * scale,
+ rand.nextUScalar1() * scale, rand.nextUScalar1() * scale);
+ path.cubicTo(rand.nextUScalar1() * scale, rand.nextUScalar1() * scale,
+ rand.nextUScalar1() * scale, rand.nextUScalar1() * scale,
+ rand.nextUScalar1() * scale, rand.nextUScalar1() * scale);
}
path.setFillType(SkPath::kEvenOdd_FillType);
path.offset(SkIntToScalar(20), SkIntToScalar(20));
- test_hittest(canvas, path, false);
- canvas->translate(SkIntToScalar(200), 0);
- test_hittest(canvas, path, true);
-
- canvas->translate(-SkIntToScalar(200), SkIntToScalar(200));
+ test_hittest(canvas, path);
+
+ canvas->translate(SkIntToScalar(scale), 0);
path.setFillType(SkPath::kWinding_FillType);
- test_hittest(canvas, path, false);
- canvas->translate(SkIntToScalar(200), 0);
- test_hittest(canvas, path, true);
+ test_hittest(canvas, path);
}
private:
diff --git a/include/core/SkPath.h b/include/core/SkPath.h
index 8440df3f02..8f03de1e86 100644
--- a/include/core/SkPath.h
+++ b/include/core/SkPath.h
@@ -781,6 +781,12 @@ public:
SkPoint fLastPt;
};
+ /**
+ * Returns true if the point { x, y } is contained by the path, taking into
+ * account the FillType.
+ */
+ bool contains(SkScalar x, SkScalar y) const;
+
void dump(bool forceClose, const char title[] = NULL) const;
void dump() const;
diff --git a/include/utils/SkCullPoints.h b/include/utils/SkCullPoints.h
index f08120dd36..5458b29781 100644
--- a/include/utils/SkCullPoints.h
+++ b/include/utils/SkCullPoints.h
@@ -67,6 +67,5 @@ private:
bool SkHitTestPath(const SkPath&, SkRect& target, bool hires);
bool SkHitTestPath(const SkPath&, SkScalar x, SkScalar y, bool hires);
-bool SkHitTestPathEx(const SkPath&, SkScalar x, SkScalar y);
#endif
diff --git a/src/core/SkPath.cpp b/src/core/SkPath.cpp
index 38619771a3..77d0854e51 100644
--- a/src/core/SkPath.cpp
+++ b/src/core/SkPath.cpp
@@ -2255,3 +2255,253 @@ bool SkPath::cheapComputeDirection(Direction* dir) const {
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);
+}
+
diff --git a/src/utils/SkCullPoints.cpp b/src/utils/SkCullPoints.cpp
index a8ec39b042..3e3082f0c0 100644
--- a/src/utils/SkCullPoints.cpp
+++ b/src/utils/SkCullPoints.cpp
@@ -218,254 +218,3 @@ bool SkHitTestPath(const SkPath& path, SkScalar x, SkScalar y, bool hires) {
return SkHitTestPath(path, r, hires);
}
-///////////////////////////////////////////////////////////////////////////////
-
-#include "SkGeometry.h"
-
-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, but maybe 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 SkHitTestPathEx(const SkPath& path, SkScalar x, SkScalar y) {
- bool isInverse = path.isInverseFillType();
- if (path.isEmpty()) {
- return isInverse;
- }
-
- const SkRect& bounds = path.getBounds();
- if (!bounds.contains(x, y)) {
- return isInverse;
- }
-
- SkPath::Iter iter(path, 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 (path.getFillType()) {
- case SkPath::kEvenOdd_FillType:
- case SkPath::kInverseEvenOdd_FillType:
- w &= 1;
- break;
- }
- return SkToBool(w);
-}
-
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-10 15:08:34 +0000