experimental tight-bounds

not sure about api -- perhaps it could just return the bounds, and make them 0,0,0,0 if the path
is empty -- the caller can trivially know if the path is empty themselves.

BUG=skia:

Change-Id: I2dbb861e8d981b27c5a6833643977f5bd6802217
Reviewed-on: https://skia-review.googlesource.com/7989
Reviewed-by: Cary Clark <caryclark@google.com>
Reviewed-by: Florin Malita <fmalita@chromium.org>
Commit-Queue: Mike Reed <reed@google.com>

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));
+            }
+        }
+    }
+}