Reland "Reland "Add some optimizations to PolyUtils""
This is a reland of 946c37057f2618af7eda34fd6d2dd8625a9e9b61
Original change's description:
> Reland "Add some optimizations to PolyUtils"
>
> This is a reland of 8bb0db3d07450880d346d808018708416c928657
>
> Original change's description:
> > Add some optimizations to PolyUtils
> >
> > * Switch inset/offset code to use a linked list rather than an array
> > * Use std::set to store active edge list for IsSimplePolygon rather than array
> > * Pre-alloc the priority queue for IsSimplePolygon
> > * When adding radial curves, expand the array all at once rather than pushing
> > one at a time.
> >
> > Bug: skia:
> > Change-Id: I692f8c29c500c41ec1d1be39d924d8a752676bf4
> > Reviewed-on: https://skia-review.googlesource.com/140787
> > Reviewed-by: Robert Phillips <robertphillips@google.com>
> > Commit-Queue: Jim Van Verth <jvanverth@google.com>
>
> Bug: skia:
> Change-Id: I3f5d42cfb941deab2b28bed020b37ce199e91d3d
> Reviewed-on: https://skia-review.googlesource.com/142200
> Reviewed-by: Robert Phillips <robertphillips@google.com>
> Commit-Queue: Jim Van Verth <jvanverth@google.com>
Bug: skia:
Change-Id: I598d4be9108d009d0f885cfa72bf9197fc286b3a
Reviewed-on: https://skia-review.googlesource.com/142920
Reviewed-by: Jim Van Verth <jvanverth@google.com>
Commit-Queue: Jim Van Verth <jvanverth@google.com>
diff --git a/bench/PolyUtilsBench.cpp b/bench/PolyUtilsBench.cpp
index 1b987fa..e03c51c 100644
--- a/bench/PolyUtilsBench.cpp
+++ b/bench/PolyUtilsBench.cpp
@@ -9,12 +9,12 @@
#include "SkPolyUtils.h"
class PolyUtilsBench : public Benchmark {
+public:
// Evaluate SkTriangulateSimplePolygon's performance (via derived classes) on:
// a non-self-intersecting star, a circle of tiny line segments and a self-intersecting star
+ enum class Type { kConvexCheck, kSimpleCheck, kInsetConvex, kOffsetSimple, kTessellateSimple };
- SkString fName;
-public:
- PolyUtilsBench() {}
+ PolyUtilsBench(Type type) : fType(type) {}
virtual void appendName(SkString*) = 0;
virtual void makePoly(SkTDArray<SkPoint>* poly) = 0;
@@ -24,32 +24,84 @@
const char* onGetName() override {
fName = "poly_utils_";
this->appendName(&fName);
+ switch (fType) {
+ case Type::kConvexCheck:
+ fName.append("_c");
+ break;
+ case Type::kSimpleCheck:
+ fName.append("_s");
+ break;
+ case Type::kInsetConvex:
+ fName.append("_i");
+ break;
+ case Type::kOffsetSimple:
+ fName.append("_o");
+ break;
+ case Type::kTessellateSimple:
+ fName.append("_t");
+ break;
+ }
return fName.c_str();
}
void onDraw(int loops, SkCanvas* canvas) override {
SkTDArray<SkPoint> poly;
this->makePoly(&poly);
- SkAutoSTMalloc<64, uint16_t> indexMap(poly.count());
- for (int i = 0; i < poly.count(); ++i) {
- indexMap[i] = i;
- }
- SkTDArray<uint16_t> triangleIndices;
- for (int i = 0; i < loops; i++) {
- if (SkIsSimplePolygon(poly.begin(), poly.count())) {
- SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(),
- &triangleIndices);
- }
+ switch (fType) {
+ case Type::kConvexCheck:
+ for (int i = 0; i < loops; i++) {
+ (void)SkIsConvexPolygon(poly.begin(), poly.count());
+ }
+ break;
+ case Type::kSimpleCheck:
+ for (int i = 0; i < loops; i++) {
+ (void)SkIsSimplePolygon(poly.begin(), poly.count());
+ }
+ break;
+ case Type::kInsetConvex:
+ if (SkIsConvexPolygon(poly.begin(), poly.count())) {
+ SkTDArray<SkPoint> result;
+ for (int i = 0; i < loops; i++) {
+ (void)SkInsetConvexPolygon(poly.begin(), poly.count(), 10, &result);
+ (void)SkInsetConvexPolygon(poly.begin(), poly.count(), 40, &result);
+ }
+ }
+ break;
+ case Type::kOffsetSimple:
+ if (SkIsSimplePolygon(poly.begin(), poly.count())) {
+ SkTDArray<SkPoint> result;
+ for (int i = 0; i < loops; i++) {
+ (void)SkOffsetSimplePolygon(poly.begin(), poly.count(), 10, &result);
+ (void)SkOffsetSimplePolygon(poly.begin(), poly.count(), -10, &result);
+ }
+ }
+ break;
+ case Type::kTessellateSimple:
+ if (SkIsSimplePolygon(poly.begin(), poly.count())) {
+ SkAutoSTMalloc<64, uint16_t> indexMap(poly.count());
+ for (int i = 0; i < poly.count(); ++i) {
+ indexMap[i] = i;
+ }
+ SkTDArray<uint16_t> triangleIndices;
+ for (int i = 0; i < loops; i++) {
+ SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(),
+ &triangleIndices);
+ }
+ }
+ break;
}
}
private:
+ SkString fName;
+ Type fType;
+
typedef Benchmark INHERITED;
};
class StarPolyUtilsBench : public PolyUtilsBench {
public:
- StarPolyUtilsBench() {}
+ StarPolyUtilsBench(PolyUtilsBench::Type type) : INHERITED(type) {}
void appendName(SkString* name) override {
name->append("star");
@@ -77,7 +129,7 @@
class CirclePolyUtilsBench : public PolyUtilsBench {
public:
- CirclePolyUtilsBench() {}
+ CirclePolyUtilsBench(PolyUtilsBench::Type type) : INHERITED(type) {}
void appendName(SkString* name) override {
name->append("circle");
@@ -101,7 +153,7 @@
class IntersectingPolyUtilsBench : public PolyUtilsBench {
public:
- IntersectingPolyUtilsBench() {}
+ IntersectingPolyUtilsBench(PolyUtilsBench::Type type) : INHERITED(type) {}
void appendName(SkString* name) override {
name->append("intersecting");
@@ -125,6 +177,18 @@
typedef PolyUtilsBench INHERITED;
};
-DEF_BENCH(return new StarPolyUtilsBench();)
-DEF_BENCH(return new CirclePolyUtilsBench();)
-DEF_BENCH(return new IntersectingPolyUtilsBench();)
+DEF_BENCH(return new StarPolyUtilsBench(PolyUtilsBench::Type::kConvexCheck);)
+DEF_BENCH(return new StarPolyUtilsBench(PolyUtilsBench::Type::kSimpleCheck);)
+DEF_BENCH(return new StarPolyUtilsBench(PolyUtilsBench::Type::kInsetConvex);)
+DEF_BENCH(return new StarPolyUtilsBench(PolyUtilsBench::Type::kOffsetSimple);)
+DEF_BENCH(return new StarPolyUtilsBench(PolyUtilsBench::Type::kTessellateSimple);)
+DEF_BENCH(return new CirclePolyUtilsBench(PolyUtilsBench::Type::kConvexCheck);)
+DEF_BENCH(return new CirclePolyUtilsBench(PolyUtilsBench::Type::kSimpleCheck);)
+DEF_BENCH(return new CirclePolyUtilsBench(PolyUtilsBench::Type::kInsetConvex);)
+DEF_BENCH(return new CirclePolyUtilsBench(PolyUtilsBench::Type::kOffsetSimple);)
+DEF_BENCH(return new CirclePolyUtilsBench(PolyUtilsBench::Type::kTessellateSimple);)
+DEF_BENCH(return new IntersectingPolyUtilsBench(PolyUtilsBench::Type::kConvexCheck);)
+DEF_BENCH(return new IntersectingPolyUtilsBench(PolyUtilsBench::Type::kSimpleCheck);)
+DEF_BENCH(return new IntersectingPolyUtilsBench(PolyUtilsBench::Type::kInsetConvex);)
+DEF_BENCH(return new IntersectingPolyUtilsBench(PolyUtilsBench::Type::kOffsetSimple);)
+DEF_BENCH(return new IntersectingPolyUtilsBench(PolyUtilsBench::Type::kTessellateSimple);)