add pathops tight bounds; conform path ops' gyp to unit tests

Implement path tight bounds using path ops machinery. This is not
as efficient as it could be; for instance, internally, it creates
a path ops structure more suited to intersection. If this shows
up as a performance bottleneck, it could be improved.

Fix path ops gyp files, which have fallen out of sync with other
tests.

R=mtklein@google.com, bsalomon@google.com
TBR=mtklein
BUG=skia:1712

Author: caryclark@google.com

Review URL: https://codereview.chromium.org/348343002

6 files changed, 195 insertions, 17 deletions

diff --git a/gyp/core.gypi b/gyp/core.gypi
index e1bdbd5289..b4784bba59 100644
--- a/gyp/core.gypi
+++ b/gyp/core.gypi
@@ -340,6 +340,7 @@
         '<(skia_src_path)/pathops/SkPathOpsQuad.cpp',
         '<(skia_src_path)/pathops/SkPathOpsRect.cpp',
         '<(skia_src_path)/pathops/SkPathOpsSimplify.cpp',
+        '<(skia_src_path)/pathops/SkPathOpsTightBounds.cpp',
         '<(skia_src_path)/pathops/SkPathOpsTriangle.cpp',
         '<(skia_src_path)/pathops/SkPathOpsTypes.cpp',
         '<(skia_src_path)/pathops/SkPathWriter.cpp',
diff --git a/gyp/pathops_unittest.gyp b/gyp/pathops_unittest.gyp
index 9803db9382..190b4f3816 100644
--- a/gyp/pathops_unittest.gyp
+++ b/gyp/pathops_unittest.gyp
@@ -1,4 +1,4 @@
-# GYP file to build unit tests.
+# GYP file to build pathops unit tests.
 {
   'includes': [
     'apptype_console.gypi',
@@ -7,34 +7,28 @@
     {
       'target_name': 'pathops_unittest',
       'type': 'executable',
-      'suppress_wildcard': '1',
-      'include_dirs' : [
-        '../src/core',
-        '../src/effects',
-        '../src/lazy',
-        '../src/pathops',
-        '../src/pdf',
-        '../src/pipe/utils',
-        '../src/utils',
-      ],
       'includes': [
         'pathops_unittest.gypi',
       ],
+      'dependencies': [ 'tools.gyp:crash_handler' ],
       'sources': [
         '../tests/PathOpsAngleIdeas.cpp',
         '../tests/PathOpsCubicLineIntersectionIdeas.cpp',
         '../tests/PathOpsDebug.cpp',
         '../tests/PathOpsOpLoopThreadedTest.cpp',
         '../tests/PathOpsSkpClipTest.cpp',
-        '../tests/Test.cpp',
-        '../tests/Test.h',
         '../tests/skia_test.cpp',
       ],
-      'dependencies': [
-        'flags.gyp:flags',
-        'skia_lib.gyp:skia_lib',
-      ],
       'conditions': [
+        [ 'skia_android_framework == 1', {
+          'libraries': [
+            '-lskia',
+          ],
+          'libraries!': [
+            '-lz',
+            '-llog',
+          ],
+        }],
         [ 'skia_gpu == 1', {
           'include_dirs': [
             '../src/gpu',
diff --git a/gyp/pathops_unittest.gypi b/gyp/pathops_unittest.gypi
index e9f40d6406..9e070ab761 100644
--- a/gyp/pathops_unittest.gypi
+++ b/gyp/pathops_unittest.gypi
@@ -1,5 +1,22 @@
+# Common gypi for pathops unit tests.
 {
+  'include_dirs': [
+    '../src/core',
+    '../src/effects',
+    '../src/lazy',
+    '../src/pathops',
+    '../src/pipe/utils',
+    '../src/utils',
+  ],
+  'dependencies': [
+    'flags.gyp:flags',
+    'skia_lib.gyp:skia_lib',
+    'tools.gyp:resources',
+  ],
   'sources': [
+    '../tests/Test.cpp',
+    '../tests/Test.h',
+
     '../tests/PathOpsAngleTest.cpp',
     '../tests/PathOpsBoundsTest.cpp',
     '../tests/PathOpsCubicIntersectionTest.cpp',
@@ -38,6 +55,7 @@
     '../tests/PathOpsSkpTest.cpp',
     '../tests/PathOpsTestCommon.cpp',
     '../tests/PathOpsThreadedCommon.cpp',
+    '../tests/PathOpsTightBoundsTest.cpp',
     '../tests/PathOpsCubicIntersectionTestData.h',
     '../tests/PathOpsExtendedTest.h',
     '../tests/PathOpsQuadIntersectionTestData.h',
diff --git a/include/pathops/SkPathOps.h b/include/pathops/SkPathOps.h
index a98f4ea4d6..ba18f4ba72 100644
--- a/include/pathops/SkPathOps.h
+++ b/include/pathops/SkPathOps.h
@@ -10,6 +10,7 @@
 #include "SkPreConfig.h"
 
 class SkPath;
+struct SkRect;
 
 // FIXME: move everything below into the SkPath class
 /**
@@ -54,4 +55,12 @@ bool SK_API Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result
   */
 bool SK_API Simplify(const SkPath& path, SkPath* result);
 
+/** Set the resulting rectangle to the tight bounds of the path.
+
+    @param path The path measured.
+    @param result The tight bounds of the path.
+    @return True if the bounds could be computed.
+  */
+bool SK_API TightBounds(const SkPath& path, SkRect* result);
+
 #endif
diff --git a/src/pathops/SkPathOpsTightBounds.cpp b/src/pathops/SkPathOpsTightBounds.cpp
new file mode 100644
index 0000000000..0f63f396e7
--- /dev/null
+++ b/src/pathops/SkPathOpsTightBounds.cpp
@@ -0,0 +1,33 @@
+/*
+ * 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 "SkOpEdgeBuilder.h"
+#include "SkPathOpsCommon.h"
+
+bool TightBounds(const SkPath& path, SkRect* result) {
+    // turn path into list of segments
+    SkTArray<SkOpContour> contours;
+    SkOpEdgeBuilder builder(path, contours);
+    if (!builder.finish()) {
+        return false;
+    }
+    SkTArray<SkOpContour*, true> contourList;
+    MakeContourList(contours, contourList, false, false);
+    SkOpContour** currentPtr = contourList.begin();
+    result->setEmpty();
+    if (!currentPtr) {
+        return true;
+    }
+    SkOpContour** listEnd = contourList.end();
+    SkOpContour* current = *currentPtr++;
+    SkPathOpsBounds bounds = current->bounds();
+    while (currentPtr != listEnd) {
+        current = *currentPtr++;
+        bounds.add(current->bounds());
+    }
+    *result = bounds;
+    return true;
+}
diff --git a/tests/PathOpsTightBoundsTest.cpp b/tests/PathOpsTightBoundsTest.cpp
new file mode 100644
index 0000000000..09f962296f
--- /dev/null
+++ b/tests/PathOpsTightBoundsTest.cpp
@@ -0,0 +1,123 @@
+/*
+ * Copyright 2013 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#include "PathOpsExtendedTest.h"
+#include "PathOpsThreadedCommon.h"
+#include "SkCanvas.h"
+#include "SkRandom.h"
+#include "SkTArray.h"
+#include "SkTSort.h"
+#include "Test.h"
+
+static void testTightBoundsLines(PathOpsThreadState* data) {
+    SkRandom ran;
+    for (int index = 0; index < 1000; ++index) {
+        SkPath path;
+        int contourCount = ran.nextRangeU(1, 10);
+        for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
+            int lineCount = ran.nextRangeU(1, 10);
+            path.moveTo(ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000));
+            for (int lIndex = 0; lIndex < lineCount; ++lIndex) {
+                path.lineTo(ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000));
+            }
+            if (ran.nextBool()) {
+                path.close();
+            }
+        }
+        SkRect classicBounds = path.getBounds();
+        SkRect tightBounds;
+        REPORTER_ASSERT(data->fReporter, TightBounds(path, &tightBounds));
+        REPORTER_ASSERT(data->fReporter, classicBounds == tightBounds);
+    }
+}
+
+DEF_TEST(PathOpsTightBoundsLines, reporter) {
+    int threadCount = initializeTests(reporter, "tightBoundsLines");
+    PathOpsThreadedTestRunner testRunner(reporter, threadCount);
+    int outerCount = reporter->allowExtendedTest() ? 100 : 1;
+    for (int index = 0; index < outerCount; ++index) {
+        for (int idx2 = 0; idx2 < 10; ++idx2) {
+            *testRunner.fRunnables.append() = SkNEW_ARGS(PathOpsThreadedRunnable,
+                    (&testTightBoundsLines, 0, 0, 0, 0, &testRunner));
+        }
+    }
+    testRunner.render();
+}
+
+static void testTightBoundsQuads(PathOpsThreadState* data) {
+    SkRandom ran;
+    const int bitWidth = 32;
+    const int bitHeight = 32;
+    const float pathMin = 1;
+    const float pathMax = (float) (bitHeight - 2);
+    SkBitmap& bits = *data->fBitmap;
+    if (bits.width() == 0) {
+        bits.allocN32Pixels(bitWidth, bitHeight);
+    }
+    SkCanvas canvas(bits);
+    SkPaint paint;
+    for (int index = 0; index < 100; ++index) {
+        SkPath path;
+        int contourCount = ran.nextRangeU(1, 10);
+        for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
+            int lineCount = ran.nextRangeU(1, 10);
+            path.moveTo(ran.nextRangeF(1, pathMax), ran.nextRangeF(pathMin, pathMax));
+            for (int lIndex = 0; lIndex < lineCount; ++lIndex) {
+                if (ran.nextBool()) {
+                    path.lineTo(ran.nextRangeF(pathMin, pathMax), ran.nextRangeF(pathMin, pathMax));
+                } else {
+                    path.quadTo(ran.nextRangeF(pathMin, pathMax), ran.nextRangeF(pathMin, pathMax),
+                            ran.nextRangeF(pathMin, pathMax), ran.nextRangeF(pathMin, pathMax));
+                }
+            }
+            if (ran.nextBool()) {
+                path.close();
+            }
+        }
+        SkRect classicBounds = path.getBounds();
+        SkRect tightBounds;
+        REPORTER_ASSERT(data->fReporter, TightBounds(path, &tightBounds));
+        REPORTER_ASSERT(data->fReporter, classicBounds.contains(tightBounds));
+        canvas.drawColor(SK_ColorWHITE);
+        canvas.drawPath(path, paint);
+        SkIRect bitsWritten = {31, 31, 0, 0};
+        for (int y = 0; y < bitHeight; ++y) {
+            uint32_t* addr1 = data->fBitmap->getAddr32(0, y);
+            bool lineWritten = false;
+            for (int x = 0; x < bitWidth; ++x) {
+                if (addr1[x] == (uint32_t) -1) {
+                    continue;
+                }
+                lineWritten = true;
+                bitsWritten.fLeft = SkTMin(bitsWritten.fLeft, x);
+                bitsWritten.fRight = SkTMax(bitsWritten.fRight, x);
+            }
+            if (!lineWritten) {
+                continue;
+            }
+            bitsWritten.fTop = SkTMin(bitsWritten.fTop, y);
+            bitsWritten.fBottom = SkTMax(bitsWritten.fBottom, y);
+        }
+        if (!bitsWritten.isEmpty()) {
+            SkIRect tightOut;
+            tightBounds.roundOut(&tightOut);
+            REPORTER_ASSERT(data->fReporter, tightOut.contains(bitsWritten));
+        }
+    }
+}
+
+DEF_TEST(PathOpsTightBoundsQuads, reporter) {
+    int threadCount = initializeTests(reporter, "tightBoundsQuads");
+    PathOpsThreadedTestRunner testRunner(reporter, threadCount);
+    int outerCount = reporter->allowExtendedTest() ? 100 : 1;
+    for (int index = 0; index < outerCount; ++index) {
+        for (int idx2 = 0; idx2 < 10; ++idx2) {
+            *testRunner.fRunnables.append() = SkNEW_ARGS(PathOpsThreadedRunnable,
+                    (&testTightBoundsQuads, 0, 0, 0, 0, &testRunner));
+        }
+    }
+    testRunner.render();
+}