diff options
-rw-r--r-- | bench/PathBench.cpp | 45 | ||||
-rw-r--r-- | src/core/SkPath.cpp | 94 | ||||
-rw-r--r-- | src/core/SkPathPriv.h | 2 | ||||
-rw-r--r-- | tests/PathTest.cpp | 52 |
4 files changed, 193 insertions, 0 deletions
diff --git a/bench/PathBench.cpp b/bench/PathBench.cpp index 449d30558e..de8be6c758 100644 --- a/bench/PathBench.cpp +++ b/bench/PathBench.cpp @@ -1076,6 +1076,47 @@ private: /////////////////////////////////////////////////////////////////////////////// +class TightBoundsBench : public Benchmark { + SkPath fPath; + SkString fName; + bool (*fProc)(const SkPath&, SkRect*); + +public: + TightBoundsBench(bool (*proc)(const SkPath&, SkRect*), const char suffix[]) : fProc(proc) { + fName.printf("tight_bounds_%s", suffix); + + const int N = 100; + SkRandom rand; + for (int i = 0; i < N; ++i) { + fPath.moveTo(rand.nextF()*100, rand.nextF()*100); + fPath.lineTo(rand.nextF()*100, rand.nextF()*100); + fPath.quadTo(rand.nextF()*100, rand.nextF()*100, rand.nextF()*100, rand.nextF()*100); + fPath.conicTo(rand.nextF()*100, rand.nextF()*100, rand.nextF()*100, rand.nextF()*100, + rand.nextF()*10); + fPath.cubicTo(rand.nextF()*100, rand.nextF()*100, rand.nextF()*100, rand.nextF()*100, + rand.nextF()*100, rand.nextF()*100); + } + } + +protected: + bool isSuitableFor(Backend backend) override { + return backend == kNonRendering_Backend; + } + + const char* onGetName() override { return fName.c_str(); } + + void onDraw(int loops, SkCanvas* canvas) override { + SkRect bounds; + for (int i = 0; i < loops*100; ++i) { + fProc(fPath, &bounds); + } + } + +private: + typedef Benchmark 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)); @@ -1143,6 +1184,10 @@ DEF_BENCH( return new ConservativelyContainsBench(ConservativelyContainsBench::k DEF_BENCH( return new ConservativelyContainsBench(ConservativelyContainsBench::kRoundRect_Type); ) DEF_BENCH( return new ConservativelyContainsBench(ConservativelyContainsBench::kOval_Type); ) +#include "SkPathOps.h" +#include "SkPathPriv.h" +DEF_BENCH( return new TightBoundsBench(SkPathPriv::ComputeTightBounds, "priv"); ) +DEF_BENCH( return new TightBoundsBench(TightBounds, "pathops"); ) // These seem to be optimized away, which is troublesome for timing. /* diff --git a/src/core/SkPath.cpp b/src/core/SkPath.cpp index 4c7ebe5879..4c18e63b23 100644 --- a/src/core/SkPath.cpp +++ b/src/core/SkPath.cpp @@ -3394,3 +3394,97 @@ void SkPathPriv::CreateDrawArcPath(SkPath* path, const SkRect& oval, SkScalar st path->close(); } } + +/////////////////////////////////////////////////////////////////////////////////////////////////// +#include "SkNx.h" + +static int compute_quad_extremas(const SkPoint src[3], SkPoint extremas[3]) { + SkScalar ts[2]; + int n = SkFindQuadExtrema(src[0].fX, src[1].fX, src[2].fX, ts); + n += SkFindQuadExtrema(src[0].fY, src[1].fY, src[2].fY, &ts[n]); + SkASSERT(n >= 0 && n <= 2); + for (int i = 0; i < n; ++i) { + extremas[i] = SkEvalQuadAt(src, ts[i]); + } + extremas[n] = src[2]; + return n + 1; +} + +static int compute_conic_extremas(const SkPoint src[3], SkScalar w, SkPoint extremas[3]) { + SkConic conic(src[0], src[1], src[2], w); + SkScalar ts[2]; + int n = conic.findXExtrema(ts); + n += conic.findYExtrema(&ts[n]); + SkASSERT(n >= 0 && n <= 2); + for (int i = 0; i < n; ++i) { + extremas[i] = conic.evalAt(ts[i]); + } + extremas[n] = src[2]; + return n + 1; +} + +static int compute_cubic_extremas(const SkPoint src[3], SkPoint extremas[5]) { + SkScalar ts[4]; + int n = SkFindCubicExtrema(src[0].fX, src[1].fX, src[2].fX, src[3].fX, ts); + n += SkFindCubicExtrema(src[0].fY, src[1].fY, src[2].fY, src[3].fY, &ts[n]); + SkASSERT(n >= 0 && n <= 4); + for (int i = 0; i < n; ++i) { + SkEvalCubicAt(src, ts[i], &extremas[i], nullptr, nullptr); + } + extremas[n] = src[3]; + return n + 1; +} + +bool SkPathPriv::ComputeTightBounds(const SkPath& path, SkRect* bounds) { + if (0 == path.countVerbs()) { + return false; + } + + if (path.getSegmentMasks() == SkPath::kLine_SegmentMask) { + *bounds = path.getBounds(); + return true; + } + + SkPoint extremas[5]; // big enough to hold worst-case curve type (cubic) extremas + 1 + SkPoint pts[4]; + SkPath::RawIter iter(path); + + // initial with the first MoveTo, so we don't have to check inside the switch + Sk2s min, max; + min = max = from_point(path.getPoint(0)); + for (;;) { + int count = 0; + switch (iter.next(pts)) { + case SkPath::kMove_Verb: + extremas[0] = pts[0]; + count = 1; + break; + case SkPath::kLine_Verb: + extremas[0] = pts[1]; + count = 1; + break; + case SkPath::kQuad_Verb: + count = compute_quad_extremas(pts, extremas); + break; + case SkPath::kConic_Verb: + count = compute_conic_extremas(pts, iter.conicWeight(), extremas); + break; + case SkPath::kCubic_Verb: + count = compute_cubic_extremas(pts, extremas); + break; + case SkPath::kClose_Verb: + break; + case SkPath::kDone_Verb: + goto DONE; + } + for (int i = 0; i < count; ++i) { + Sk2s tmp = from_point(extremas[i]); + min = Sk2s::Min(min, tmp); + max = Sk2s::Max(max, tmp); + } + } +DONE: + min.store((SkPoint*)&bounds->fLeft); + max.store((SkPoint*)&bounds->fRight); + return true; +} diff --git a/src/core/SkPathPriv.h b/src/core/SkPathPriv.h index 029cb759de..cbbb83edab 100644 --- a/src/core/SkPathPriv.h +++ b/src/core/SkPathPriv.h @@ -121,6 +121,8 @@ public: static const SkScalar* ConicWeightData(const SkPath& path) { return path.fPathRef->conicWeights(); } + + static bool ComputeTightBounds(const SkPath&, SkRect*); }; #endif diff --git a/tests/PathTest.cpp b/tests/PathTest.cpp index 7515d3e261..38bac25ba7 100644 --- a/tests/PathTest.cpp +++ b/tests/PathTest.cpp @@ -4700,3 +4700,55 @@ DEF_TEST(conservatively_contains_rect, reporter) { // this guy should not assert path.conservativelyContainsRect({ -211747, 12.1115f, -197893, 25.0321f }); } + +/////////////////////////////////////////////////////////////////////////////////////////////////// + +static void rand_path(SkPath* path, SkRandom& rand, SkPath::Verb verb, int n) { + for (int i = 0; i < n; ++i) { + switch (verb) { + case SkPath::kLine_Verb: + path->lineTo(rand.nextF()*100, rand.nextF()*100); + break; + case SkPath::kQuad_Verb: + path->quadTo(rand.nextF()*100, rand.nextF()*100, + rand.nextF()*100, rand.nextF()*100); + break; + case SkPath::kConic_Verb: + path->conicTo(rand.nextF()*100, rand.nextF()*100, + rand.nextF()*100, rand.nextF()*100, rand.nextF()*10); + break; + case SkPath::kCubic_Verb: + path->cubicTo(rand.nextF()*100, rand.nextF()*100, + rand.nextF()*100, rand.nextF()*100, + rand.nextF()*100, rand.nextF()*100); + break; + default: + SkASSERT(false); + } + } +} + +#include "SkPathOps.h" +DEF_TEST(path_tight_bounds, reporter) { + SkRandom rand; + + const SkPath::Verb verbs[] = { + SkPath::kLine_Verb, SkPath::kQuad_Verb, SkPath::kConic_Verb, SkPath::kCubic_Verb, + }; + for (int i = 0; i < 1000; ++i) { + for (int n = 1; n <= 10; n += 9) { + for (SkPath::Verb verb : verbs) { + SkPath path; + rand_path(&path, rand, verb, n); + SkRect bounds = path.getBounds(); + SkRect tight; + SkPathPriv::ComputeTightBounds(path, &tight); + REPORTER_ASSERT(reporter, bounds.contains(tight)); + + SkRect tight2; + TightBounds(path, &tight2); + REPORTER_ASSERT(reporter, nearly_equal(tight, tight2)); + } + } + } +} |