diff options
| -rw-r--r-- | bench/PathBench.cpp | 93 | ||||
| -rw-r--r-- | include/core/SkPath.h | 10 | ||||
| -rw-r--r-- | src/core/SkPath.cpp | 80 | ||||
| -rw-r--r-- | tests/PathTest.cpp | 157 |
4 files changed, 339 insertions, 1 deletions
diff --git a/bench/PathBench.cpp b/bench/PathBench.cpp index 6e522ec67c..390c5326ec 100644 --- a/bench/PathBench.cpp +++ b/bench/PathBench.cpp @@ -779,6 +779,90 @@ private: typedef SkBenchmark INHERITED; }; +class ConservativelyContainsBench : public SkBenchmark { +public: + enum Type { + kRect_Type, + kRoundRect_Type, + kOval_Type, + }; + + ConservativelyContainsBench(void* param, Type type) : INHERITED(param) { + fIsRendering = false; + fParity = false; + fName = "conservatively_contains_"; + switch (type) { + case kRect_Type: + fName.append("rect"); + fPath.addRect(kBaseRect); + break; + case kRoundRect_Type: + fName.append("round_rect"); + fPath.addRoundRect(kBaseRect, kRRRadii[0], kRRRadii[1]); + break; + case kOval_Type: + fName.append("oval"); + fPath.addOval(kBaseRect); + break; + } + } + +private: + virtual const char* onGetName() SK_OVERRIDE { + return fName.c_str(); + } + + virtual void onDraw(SkCanvas* canvas) SK_OVERRIDE { + for (int i = 0; i < N; ++i) { + const SkRect& rect = fQueryRects[i % kQueryRectCnt]; + fParity = fParity != fPath.conservativelyContainsRect(rect); + } + } + + virtual void onPreDraw() SK_OVERRIDE { + fQueryRects.setCount(kQueryRectCnt); + + SkRandom rand; + for (int i = 0; i < kQueryRectCnt; ++i) { + SkSize size; + SkPoint xy; + size.fWidth = rand.nextRangeScalar(kQueryMin.fWidth, kQueryMax.fWidth); + size.fHeight = rand.nextRangeScalar(kQueryMin.fHeight, kQueryMax.fHeight); + xy.fX = rand.nextRangeScalar(kBounds.fLeft, kBounds.fRight - size.fWidth); + xy.fY = rand.nextRangeScalar(kBounds.fTop, kBounds.fBottom - size.fHeight); + + fQueryRects[i] = SkRect::MakeXYWH(xy.fX, xy.fY, size.fWidth, size.fHeight); + } + } + + virtual void onPostDraw() SK_OVERRIDE { + fQueryRects.setCount(0); + } + + enum { + N = SkBENCHLOOP(100000), + kQueryRectCnt = 400, + }; + static const SkRect kBounds; // bounds for all random query rects + static const SkSize kQueryMin; // minimum query rect size, should be <= kQueryMax + static const SkSize kQueryMax; // max query rect size, should < kBounds + static const SkRect kBaseRect; // rect that is used to construct the path + static const SkScalar kRRRadii[2]; // x and y radii for round rect + + SkString fName; + SkPath fPath; + bool fParity; + SkTDArray<SkRect> fQueryRects; + + typedef SkBenchmark INHERITED; +}; + +const SkRect ConservativelyContainsBench::kBounds = SkRect::MakeWH(SkIntToScalar(100), SkIntToScalar(100)); +const SkSize ConservativelyContainsBench::kQueryMin = SkSize::Make(SkIntToScalar(1), SkIntToScalar(1)); +const SkSize ConservativelyContainsBench::kQueryMax = SkSize::Make(SkIntToScalar(40), SkIntToScalar(40)); +const SkRect ConservativelyContainsBench::kBaseRect = SkRect::MakeXYWH(SkIntToScalar(25), SkIntToScalar(25), SkIntToScalar(50), SkIntToScalar(50)); +const SkScalar ConservativelyContainsBench::kRRRadii[2] = {SkIntToScalar(5), SkIntToScalar(10)}; + static SkBenchmark* FactT00(void* p) { return new TrianglePathBench(p, FLAGS00); } static SkBenchmark* FactT01(void* p) { return new TrianglePathBench(p, FLAGS01); } static SkBenchmark* FactT10(void* p) { return new TrianglePathBench(p, FLAGS10); } @@ -883,3 +967,12 @@ static BenchRegistry gRegArbRoundRectTest(ArbRoundRectTest); static SkBenchmark* ZeroRadRoundRectTest(void* p) { return new ArbRoundRectBench(p, true); } static BenchRegistry gRegZeroRadRoundRectTest(ZeroRadRoundRectTest); + +static SkBenchmark* RectConservativelyContainsTest(void* p) { return new ConservativelyContainsBench(p, ConservativelyContainsBench::kRect_Type); } +static BenchRegistry gRegRectConservativelyContainsTest(RectConservativelyContainsTest); + +static SkBenchmark* RoundRectConservativelyContainsTest(void* p) { return new ConservativelyContainsBench(p, ConservativelyContainsBench::kRoundRect_Type); } +static BenchRegistry gRegRoundRectConservativelyContainsTest(RoundRectConservativelyContainsTest); + +static SkBenchmark* OvalConservativelyContainsTest(void* p) { return new ConservativelyContainsBench(p, ConservativelyContainsBench::kOval_Type); } +static BenchRegistry gRegOvalConservativelyContainsTest(OvalConservativelyContainsTest); diff --git a/include/core/SkPath.h b/include/core/SkPath.h index ee02c6546b..20d041dd88 100644 --- a/include/core/SkPath.h +++ b/include/core/SkPath.h @@ -292,7 +292,7 @@ public: } /** Calling this will, if the internal cache of the bounds is out of date, - update it so that subsequent calls to getBounds will be instanteous. + update it so that subsequent calls to getBounds will be instantaneous. This also means that any copies or simple transformations of the path will inherit the cached bounds. */ @@ -301,6 +301,14 @@ public: this->getBounds(); } + /** + * Does a conservative test to see whether a rectangle is inside a path. Currently it only + * will ever return true for single convex contour paths. The empty-status of the rect is not + * considered (e.g. a rect that is a point can be inside a path). Points or line segments where + * the rect edge touches the path border are not considered containment violations. + */ + bool conservativelyContainsRect(const SkRect& rect) const; + // Construction methods /** Hint to the path to prepare for adding more points. This can allow the diff --git a/src/core/SkPath.cpp b/src/core/SkPath.cpp index d1b90dd6bf..b7c2162dbf 100644 --- a/src/core/SkPath.cpp +++ b/src/core/SkPath.cpp @@ -311,6 +311,86 @@ void SkPath::swap(SkPath& other) { } } +static inline bool check_edge_against_rect(const SkPoint& p0, + const SkPoint& p1, + const SkRect& rect, + SkPath::Direction dir) { + const SkPoint* edgeBegin; + SkVector v; + if (SkPath::kCW_Direction == dir) { + v = p1 - p0; + edgeBegin = &p0; + } else { + v = p0 - p1; + edgeBegin = &p1; + } + if (v.fX || v.fY) { + // check the cross product of v with the vec from edgeBegin to each rect corner + SkScalar yL = SkScalarMul(v.fY, rect.fLeft - edgeBegin->fX); + SkScalar xT = SkScalarMul(v.fX, rect.fTop - edgeBegin->fY); + SkScalar yR = SkScalarMul(v.fY, rect.fRight - edgeBegin->fX); + SkScalar xB = SkScalarMul(v.fX, rect.fBottom - edgeBegin->fY); + if ((xT < yL) || (xT < yR) || (xB < yL) || (xB < yR)) { + return false; + } + } + return true; +} + +bool SkPath::conservativelyContainsRect(const SkRect& rect) const { + // This only handles non-degenerate convex paths currently. + if (kConvex_Convexity != this->getConvexity()) { + return false; + } + + Direction direction; + if (!this->cheapComputeDirection(&direction)) { + return false; + } + + SkPoint firstPt; + SkPoint prevPt; + RawIter iter(*this); + SkPath::Verb verb; + SkPoint pts[4]; + SkDEBUGCODE(int moveCnt = 0;) + + while ((verb = iter.next(pts)) != kDone_Verb) { + int nextPt = -1; + switch (verb) { + case kMove_Verb: + SkASSERT(!moveCnt); + SkDEBUGCODE(++moveCnt); + firstPt = prevPt = pts[0]; + break; + case kLine_Verb: + nextPt = 1; + SkASSERT(moveCnt); + break; + case kQuad_Verb: + SkASSERT(moveCnt); + nextPt = 2; + break; + case kCubic_Verb: + SkASSERT(moveCnt); + nextPt = 3; + break; + case kClose_Verb: + break; + default: + SkDEBUGFAIL("unknown verb"); + } + if (-1 != nextPt) { + if (!check_edge_against_rect(prevPt, pts[nextPt], rect, direction)) { + return false; + } + prevPt = pts[nextPt]; + } + } + + return check_edge_against_rect(prevPt, firstPt, rect, direction); +} + #ifdef SK_BUILD_FOR_ANDROID uint32_t SkPath::getGenerationID() const { return fGenerationID; diff --git a/tests/PathTest.cpp b/tests/PathTest.cpp index 627ed181b0..a48fc9f6dd 100644 --- a/tests/PathTest.cpp +++ b/tests/PathTest.cpp @@ -822,6 +822,162 @@ static void test_isLine(skiatest::Reporter* reporter) { REPORTER_ASSERT(reporter, pts[1].equals(lineX, lineY)); } +static void test_conservativelyContains(skiatest::Reporter* reporter) { + SkPath path; + + // kBaseRect is used to construct most our test paths: a rect, a circle, and a round-rect. + static const SkRect kBaseRect = SkRect::MakeWH(SkIntToScalar(100), SkIntToScalar(100)); + + // A circle that bounds kBaseRect (with a significant amount of slop) + SkScalar circleR = SkMaxScalar(kBaseRect.width(), kBaseRect.height()); + circleR = SkScalarMul(circleR, SkFloatToScalar(1.75f)) / 2; + static const SkPoint kCircleC = {kBaseRect.centerX(), kBaseRect.centerY()}; + + // round-rect radii + static const SkScalar kRRRadii[] = {SkIntToScalar(5), SkIntToScalar(3)}; + + static const struct { + SkRect fQueryRect; + bool fInRect; + bool fInCircle; + bool fInRR; + } kQueries[] = { + {kBaseRect, true, true, false}, + + // rect well inside of kBaseRect + {SkRect::MakeLTRB(kBaseRect.fLeft + SkFloatToScalar(0.25f)*kBaseRect.width(), + kBaseRect.fTop + SkFloatToScalar(0.25f)*kBaseRect.height(), + kBaseRect.fRight - SkFloatToScalar(0.25f)*kBaseRect.width(), + kBaseRect.fBottom - SkFloatToScalar(0.25f)*kBaseRect.height()), + true, true, true}, + + // rects with edges off by one from kBaseRect's edges + {SkRect::MakeXYWH(kBaseRect.fLeft, kBaseRect.fTop, + kBaseRect.width(), kBaseRect.height() + 1), + false, true, false}, + {SkRect::MakeXYWH(kBaseRect.fLeft, kBaseRect.fTop, + kBaseRect.width() + 1, kBaseRect.height()), + false, true, false}, + {SkRect::MakeXYWH(kBaseRect.fLeft, kBaseRect.fTop, + kBaseRect.width() + 1, kBaseRect.height() + 1), + false, true, false}, + {SkRect::MakeXYWH(kBaseRect.fLeft - 1, kBaseRect.fTop, + kBaseRect.width(), kBaseRect.height()), + false, true, false}, + {SkRect::MakeXYWH(kBaseRect.fLeft, kBaseRect.fTop - 1, + kBaseRect.width(), kBaseRect.height()), + false, true, false}, + {SkRect::MakeXYWH(kBaseRect.fLeft - 1, kBaseRect.fTop, + kBaseRect.width() + 2, kBaseRect.height()), + false, true, false}, + {SkRect::MakeXYWH(kBaseRect.fLeft, kBaseRect.fTop - 1, + kBaseRect.width() + 2, kBaseRect.height()), + false, true, false}, + + // zero-w/h rects at each corner of kBaseRect + {SkRect::MakeXYWH(kBaseRect.fLeft, kBaseRect.fTop, 0, 0), true, true, false}, + {SkRect::MakeXYWH(kBaseRect.fRight, kBaseRect.fTop, 0, 0), true, true, false}, + {SkRect::MakeXYWH(kBaseRect.fLeft, kBaseRect.fBottom, 0, 0), true, true, false}, + {SkRect::MakeXYWH(kBaseRect.fRight, kBaseRect.fBottom, 0, 0), true, true, false}, + + // far away rect + {SkRect::MakeXYWH(10 * kBaseRect.fRight, 10 * kBaseRect.fBottom, + SkIntToScalar(10), SkIntToScalar(10)), + false, false, false}, + + // very large rect containing kBaseRect + {SkRect::MakeXYWH(kBaseRect.fLeft - 5 * kBaseRect.width(), + kBaseRect.fTop - 5 * kBaseRect.height(), + 11 * kBaseRect.width(), 11 * kBaseRect.height()), + false, false, false}, + + // skinny rect that spans same y-range as kBaseRect + {SkRect::MakeXYWH(kBaseRect.centerX(), kBaseRect.fTop, + SkIntToScalar(1), kBaseRect.height()), + true, true, true}, + + // short rect that spans same x-range as kBaseRect + {SkRect::MakeXYWH(kBaseRect.fLeft, kBaseRect.centerY(), kBaseRect.width(), SkScalar(1)), + true, true, true}, + + // skinny rect that spans slightly larger y-range than kBaseRect + {SkRect::MakeXYWH(kBaseRect.centerX(), kBaseRect.fTop, + SkIntToScalar(1), kBaseRect.height() + 1), + false, true, false}, + + // short rect that spans slightly larger x-range than kBaseRect + {SkRect::MakeXYWH(kBaseRect.fLeft, kBaseRect.centerY(), + kBaseRect.width() + 1, SkScalar(1)), + false, true, false}, + }; + + for (int inv = 0; inv < 4; ++inv) { + for (int q = 0; q < SK_ARRAY_COUNT(kQueries); ++q) { + SkRect qRect = kQueries[q].fQueryRect; + if (inv & 0x1) { + SkTSwap(qRect.fLeft, qRect.fRight); + } + if (inv & 0x2) { + SkTSwap(qRect.fTop, qRect.fBottom); + } + for (int d = 0; d < 2; ++d) { + SkPath::Direction dir = d ? SkPath::kCCW_Direction : SkPath::kCW_Direction; + path.reset(); + path.addRect(kBaseRect, dir); + REPORTER_ASSERT(reporter, kQueries[q].fInRect == + path.conservativelyContainsRect(qRect)); + + path.reset(); + path.addCircle(kCircleC.fX, kCircleC.fY, circleR, dir); + REPORTER_ASSERT(reporter, kQueries[q].fInCircle == + path.conservativelyContainsRect(qRect)); + + path.reset(); + path.addRoundRect(kBaseRect, kRRRadii[0], kRRRadii[1], dir); + REPORTER_ASSERT(reporter, kQueries[q].fInRR == + path.conservativelyContainsRect(qRect)); + } + // Slightly non-convex shape, shouldn't contain any rects. + path.reset(); + path.moveTo(0, 0); + path.lineTo(SkIntToScalar(50), SkFloatToScalar(0.05f)); + path.lineTo(SkIntToScalar(100), 0); + path.lineTo(SkIntToScalar(100), SkIntToScalar(100)); + path.lineTo(0, SkIntToScalar(100)); + path.close(); + REPORTER_ASSERT(reporter, !path.conservativelyContainsRect(qRect)); + } + } + + // make sure a minimal convex shape works, a right tri with edges along pos x and y axes. + path.reset(); + path.moveTo(0, 0); + path.lineTo(SkIntToScalar(100), 0); + path.lineTo(0, SkIntToScalar(100)); + + // inside, on along top edge + REPORTER_ASSERT(reporter, path.conservativelyContainsRect(SkRect::MakeXYWH(SkIntToScalar(50), 0, + SkIntToScalar(10), + SkIntToScalar(10)))); + // above + REPORTER_ASSERT(reporter, !path.conservativelyContainsRect( + SkRect::MakeXYWH(SkIntToScalar(50), + SkIntToScalar(-10), + SkIntToScalar(10), + SkIntToScalar(10)))); + // to the left + REPORTER_ASSERT(reporter, !path.conservativelyContainsRect(SkRect::MakeXYWH(SkIntToScalar(-10), + SkIntToScalar(5), + SkIntToScalar(5), + SkIntToScalar(5)))); + + // outside the diagonal edge + REPORTER_ASSERT(reporter, !path.conservativelyContainsRect(SkRect::MakeXYWH(SkIntToScalar(10), + SkIntToScalar(200), + SkIntToScalar(20), + SkIntToScalar(5)))); +} + // Simple isRect test is inline TestPath, below. // test_isRect provides more extensive testing. static void test_isRect(skiatest::Reporter* reporter) { @@ -1810,6 +1966,7 @@ static void TestPath(skiatest::Reporter* reporter) { test_direction(reporter); test_convexity(reporter); test_convexity2(reporter); + test_conservativelyContains(reporter); test_close(reporter); test_segment_masks(reporter); test_flattening(reporter); |