From 946c37057f2618af7eda34fd6d2dd8625a9e9b61 Mon Sep 17 00:00:00 2001 From: Jim Van Verth Date: Wed, 18 Jul 2018 13:38:25 -0400 Subject: 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 > Commit-Queue: Jim Van Verth Bug: skia: Change-Id: I3f5d42cfb941deab2b28bed020b37ce199e91d3d Reviewed-on: https://skia-review.googlesource.com/142200 Reviewed-by: Robert Phillips Commit-Queue: Jim Van Verth --- bench/PolyUtilsBench.cpp | 102 ++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 83 insertions(+), 19 deletions(-) (limited to 'bench') diff --git a/bench/PolyUtilsBench.cpp b/bench/PolyUtilsBench.cpp index 1b987fa038..e03c51cf8d 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* poly) = 0; @@ -24,32 +24,84 @@ protected: 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 poly; this->makePoly(&poly); - SkAutoSTMalloc<64, uint16_t> indexMap(poly.count()); - for (int i = 0; i < poly.count(); ++i) { - indexMap[i] = i; - } - SkTDArray 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 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 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 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 @@ private: class CirclePolyUtilsBench : public PolyUtilsBench { public: - CirclePolyUtilsBench() {} + CirclePolyUtilsBench(PolyUtilsBench::Type type) : INHERITED(type) {} void appendName(SkString* name) override { name->append("circle"); @@ -101,7 +153,7 @@ private: class IntersectingPolyUtilsBench : public PolyUtilsBench { public: - IntersectingPolyUtilsBench() {} + IntersectingPolyUtilsBench(PolyUtilsBench::Type type) : INHERITED(type) {} void appendName(SkString* name) override { name->append("intersecting"); @@ -125,6 +177,18 @@ private: 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);) -- cgit v1.2.3