cleanup and optimize rect intersect routines
BUG=skia:
Review URL: https://codereview.chromium.org/640723004
diff --git a/bench/GeometryBench.cpp b/bench/GeometryBench.cpp
new file mode 100644
index 0000000..cd58e3c
--- /dev/null
+++ b/bench/GeometryBench.cpp
@@ -0,0 +1,115 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "Benchmark.h"
+#include "SkGeometry.h"
+#include "SkRandom.h"
+#include "SkRect.h"
+
+class GeometryBench : public Benchmark {
+public:
+ GeometryBench(const char suffix[]) : fVolatileInt(0) {
+ fName.printf("geo_%s", suffix);
+ }
+
+ virtual const char* onGetName() SK_OVERRIDE {
+ return fName.c_str();
+ }
+
+ virtual bool isSuitableFor(Backend backend) SK_OVERRIDE {
+ return kNonRendering_Backend == backend;
+ }
+
+protected:
+ volatile int fVolatileInt;
+
+ /**
+ * Subclasses can call this to try to defeat the optimizer (with some result of their
+ * inner loop), since it will fool the compiler into assuming that "n" is actually
+ * needed somewhere, and since this method is not const, the member fields cannot
+ * be assumed to be const before and after the call.
+ */
+ virtual void virtualCallToFoilOptimizers(int n) { fVolatileInt += n; }
+
+private:
+ SkString fName;
+};
+
+class GeoRectBench : public GeometryBench {
+public:
+ GeoRectBench(const char suffix[]) : GeometryBench(suffix) {}
+
+protected:
+ SkRect fRects[2048];
+
+ virtual void onPreDraw() {
+ const SkScalar min = -100;
+ const SkScalar max = 100;
+ SkRandom rand;
+ for (size_t i = 0; i < SK_ARRAY_COUNT(fRects); ++i) {
+ SkScalar x = rand.nextRangeScalar(min, max);
+ SkScalar y = rand.nextRangeScalar(min, max);
+ SkScalar w = rand.nextRangeScalar(min, max);
+ SkScalar h = rand.nextRangeScalar(min, max);
+ fRects[i].setXYWH(x, y, w, h);
+ }
+ }
+};
+
+class GeoRectBench_intersect : public GeoRectBench {
+public:
+ GeoRectBench_intersect() : GeoRectBench("rect_intersect") {}
+
+protected:
+ virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE {
+ for (int outer = 0; outer < loops; ++outer) {
+ int count = 0;
+ for (size_t i = 0; i < SK_ARRAY_COUNT(fRects); ++i) {
+ SkRect r = fRects[0];
+ count += r.intersect(fRects[i]);
+ }
+ this->virtualCallToFoilOptimizers(count);
+ }
+ }
+};
+
+class GeoRectBench_intersect_rect : public GeoRectBench {
+public:
+ GeoRectBench_intersect_rect() : GeoRectBench("rect_intersect_rect") {}
+
+protected:
+ virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE {
+ for (int outer = 0; outer < loops; ++outer) {
+ int count = 0;
+ SkRect r;
+ for (size_t i = 0; i < SK_ARRAY_COUNT(fRects); ++i) {
+ count += r.intersect(fRects[0], fRects[i]);
+ }
+ this->virtualCallToFoilOptimizers(count);
+ }
+ }
+};
+
+class GeoRectBench_Intersects : public GeoRectBench {
+public:
+ GeoRectBench_Intersects() : GeoRectBench("rect_Intersects") {}
+
+protected:
+ virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE {
+ for (int outer = 0; outer < loops; ++outer) {
+ int count = 0;
+ for (size_t i = 0; i < SK_ARRAY_COUNT(fRects); ++i) {
+ count += SkRect::Intersects(fRects[0], fRects[i]);
+ }
+ this->virtualCallToFoilOptimizers(count);
+ }
+ }
+};
+
+DEF_BENCH( return new GeoRectBench_intersect; )
+DEF_BENCH( return new GeoRectBench_intersect_rect; )
+DEF_BENCH( return new GeoRectBench_Intersects; )
diff --git a/bench/RegionBench.cpp b/bench/RegionBench.cpp
index b3722d4..91ab286 100644
--- a/bench/RegionBench.cpp
+++ b/bench/RegionBench.cpp
@@ -117,59 +117,6 @@
typedef Benchmark INHERITED;
};
-class RectSectBench : public Benchmark {
- enum {
- N = 1000
- };
- SkRect fArray0[N];
- SkRect fArray1[N];
- SkString fName;
- bool fNewWay;
-
-public:
- static void RandRect(SkRect* r, SkRandom& rand) {
- r->set(rand.nextSScalar1(), rand.nextSScalar1(),
- rand.nextSScalar1(), rand.nextSScalar1());
- r->sort();
- }
-
- RectSectBench(bool newWay) : fNewWay(newWay) {
- fName.printf("rect_intersect_%s", newWay ? "new" : "old");
-
- SkRandom rand;
- for (int i = 0; i < N; i++) {
- RandRect(&fArray0[i], rand);
- RandRect(&fArray1[i], rand);
- }
- }
-
- virtual bool isSuitableFor(Backend backend) SK_OVERRIDE {
- return backend == kNonRendering_Backend;
- }
-
-protected:
- virtual const char* onGetName() { return fName.c_str(); }
-
- virtual void onDraw(const int loops, SkCanvas* canvas) {
- for (int i = 0; i < loops; ++i) {
- if (fNewWay) {
- for (int j = 0; j < N; ++j) {
- SkRect r = fArray0[j];
- r.intersect2(fArray1[j]);
- }
- } else {
- for (int j = 0; j < N; ++j) {
- SkRect r = fArray0[j];
- r.intersect(fArray1[j]);
- }
- }
- }
- }
-
-private:
- typedef Benchmark INHERITED;
-};
-
///////////////////////////////////////////////////////////////////////////////
#define SMALL 16
@@ -183,6 +130,3 @@
DEF_BENCH( return SkNEW_ARGS(RegionBench, (SMALL, sectsrgn_proc, "intersectsrgn")); )
DEF_BENCH( return SkNEW_ARGS(RegionBench, (SMALL, sectsrect_proc, "intersectsrect")); )
DEF_BENCH( return SkNEW_ARGS(RegionBench, (SMALL, containsxy_proc, "containsxy")); )
-
-DEF_BENCH( return SkNEW_ARGS(RectSectBench, (false)); )
-DEF_BENCH( return SkNEW_ARGS(RectSectBench, (true)); )
diff --git a/gyp/bench.gypi b/gyp/bench.gypi
index b057e89..7207819 100644
--- a/gyp/bench.gypi
+++ b/gyp/bench.gypi
@@ -49,6 +49,7 @@
'../bench/FontCacheBench.cpp',
'../bench/FontScalerBench.cpp',
'../bench/GameBench.cpp',
+ '../bench/GeometryBench.cpp',
'../bench/GrMemoryPoolBench.cpp',
'../bench/GrResourceCacheBench.cpp',
'../bench/GrOrderedSetBench.cpp',
diff --git a/include/core/SkRect.h b/include/core/SkRect.h
index d249aee..d9ef7a5 100644
--- a/include/core/SkRect.h
+++ b/include/core/SkRect.h
@@ -651,7 +651,6 @@
If either rectangle is empty, do nothing and return false.
*/
bool intersect(const SkRect& r);
- bool intersect2(const SkRect& r);
/** If this rectangle intersects the rectangle specified by left, top, right, bottom,
return true and set this rectangle to that intersection, otherwise return false
@@ -661,31 +660,38 @@
bool intersect(SkScalar left, SkScalar top, SkScalar right, SkScalar bottom);
/**
- * Return true if this rectangle is not empty, and the specified sides of
- * a rectangle are not empty, and they intersect.
- */
- bool intersects(SkScalar left, SkScalar top, SkScalar right, SkScalar bottom) const {
- return // first check that both are not empty
- left < right && top < bottom &&
- fLeft < fRight && fTop < fBottom &&
- // now check for intersection
- fLeft < right && left < fRight &&
- fTop < bottom && top < fBottom;
- }
-
- /** If rectangles a and b intersect, return true and set this rectangle to
+ * If rectangles a and b intersect, return true and set this rectangle to
* that intersection, otherwise return false and do not change this
* rectangle. If either rectangle is empty, do nothing and return false.
*/
bool intersect(const SkRect& a, const SkRect& b);
+
+private:
+ static bool Intersects(SkScalar al, SkScalar at, SkScalar ar, SkScalar ab,
+ SkScalar bl, SkScalar bt, SkScalar br, SkScalar bb) {
+ SkScalar L = SkMaxScalar(al, bl);
+ SkScalar R = SkMinScalar(ar, br);
+ SkScalar T = SkMaxScalar(at, bt);
+ SkScalar B = SkMinScalar(ab, bb);
+ return L < R && T < B;
+ }
+
+public:
+ /**
+ * Return true if this rectangle is not empty, and the specified sides of
+ * a rectangle are not empty, and they intersect.
+ */
+ bool intersects(SkScalar left, SkScalar top, SkScalar right, SkScalar bottom) const {
+ return Intersects(fLeft, fTop, fRight, fBottom, left, top, right, bottom);
+ }
+
/**
* Return true if rectangles a and b are not empty and intersect.
*/
static bool Intersects(const SkRect& a, const SkRect& b) {
- return !a.isEmpty() && !b.isEmpty() &&
- a.fLeft < b.fRight && b.fLeft < a.fRight &&
- a.fTop < b.fBottom && b.fTop < a.fBottom;
+ return Intersects(a.fLeft, a.fTop, a.fRight, a.fBottom,
+ b.fLeft, b.fTop, b.fRight, b.fBottom);
}
/**
diff --git a/src/core/SkRect.cpp b/src/core/SkRect.cpp
index 12f7652..7340098 100644
--- a/src/core/SkRect.cpp
+++ b/src/core/SkRect.cpp
@@ -99,51 +99,27 @@
return isFinite;
}
-bool SkRect::intersect(SkScalar left, SkScalar top, SkScalar right,
- SkScalar bottom) {
- if (left < right && top < bottom && !this->isEmpty() && // check for empties
- fLeft < right && left < fRight && fTop < bottom && top < fBottom)
- {
- if (fLeft < left) fLeft = left;
- if (fTop < top) fTop = top;
- if (fRight > right) fRight = right;
- if (fBottom > bottom) fBottom = bottom;
- return true;
- }
- return false;
+#define CHECK_INTERSECT(al, at, ar, ab, bl, bt, br, bb) \
+ SkScalar L = SkMaxScalar(al, bl); \
+ SkScalar R = SkMinScalar(ar, br); \
+ SkScalar T = SkMaxScalar(at, bt); \
+ SkScalar B = SkMinScalar(ab, bb); \
+ do { if (L >= R || T >= B) return false; } while (0)
+
+bool SkRect::intersect(SkScalar left, SkScalar top, SkScalar right, SkScalar bottom) {
+ CHECK_INTERSECT(left, top, right, bottom, fLeft, fTop, fRight, fBottom);
+ this->setLTRB(L, T, R, B);
+ return true;
}
bool SkRect::intersect(const SkRect& r) {
return this->intersect(r.fLeft, r.fTop, r.fRight, r.fBottom);
}
-bool SkRect::intersect2(const SkRect& r) {
- SkScalar L = SkMaxScalar(fLeft, r.fLeft);
- SkScalar R = SkMinScalar(fRight, r.fRight);
- if (L >= R) {
- return false;
- }
- SkScalar T = SkMaxScalar(fTop, r.fTop);
- SkScalar B = SkMinScalar(fBottom, r.fBottom);
- if (T >= B) {
- return false;
- }
- this->set(L, T, R, B);
- return true;
-}
-
bool SkRect::intersect(const SkRect& a, const SkRect& b) {
-
- if (!a.isEmpty() && !b.isEmpty() &&
- a.fLeft < b.fRight && b.fLeft < a.fRight &&
- a.fTop < b.fBottom && b.fTop < a.fBottom) {
- fLeft = SkMaxScalar(a.fLeft, b.fLeft);
- fTop = SkMaxScalar(a.fTop, b.fTop);
- fRight = SkMinScalar(a.fRight, b.fRight);
- fBottom = SkMinScalar(a.fBottom, b.fBottom);
- return true;
- }
- return false;
+ CHECK_INTERSECT(a.fLeft, a.fTop, a.fRight, a.fBottom, b.fLeft, b.fTop, b.fRight, b.fBottom);
+ this->setLTRB(L, T, R, B);
+ return true;
}
void SkRect::join(SkScalar left, SkScalar top, SkScalar right, SkScalar bottom) {
@@ -162,3 +138,4 @@
fBottom = SkMaxScalar(fBottom, bottom);
}
}
+