Add SkOffsetSimplePolygon.
Performs inset and outset operations on simple polygons and returns
a simple polygon, if possible.
Bug: skia:
Change-Id: I6d468174ad70b5279b736c532e19cbb84ff9f955
Reviewed-on: https://skia-review.googlesource.com/116483
Commit-Queue: Jim Van Verth <jvanverth@google.com>
Reviewed-by: Robert Phillips <robertphillips@google.com>
diff --git a/gm/convex_all_line_paths.cpp b/gm/convex_all_line_paths.cpp
index b8cdbce..b1907bc 100644
--- a/gm/convex_all_line_paths.cpp
+++ b/gm/convex_all_line_paths.cpp
@@ -350,173 +350,8 @@
typedef GM INHERITED;
};
-// This GM is intended to exercise the insetting of convex polygons
-class ConvexPolygonInsetGM : public GM {
-public:
- ConvexPolygonInsetGM() {
- this->setBGColor(0xFFFFFFFF);
- }
-
-protected:
- SkString onShortName() override {
- return SkString("convex-polygon-inset");
- }
- SkISize onISize() override { return SkISize::Make(kGMWidth, kGMHeight); }
- bool runAsBench() const override { return true; }
-
- static void GetPath(int index, SkPath::Direction dir,
- std::unique_ptr<SkPoint[]>* data, int* numPts) {
- if (index < (int)SK_ARRAY_COUNT(ConvexLineOnlyData::gPoints)) {
- // manually specified
- *numPts = (int)ConvexLineOnlyData::gSizes[index];
- data->reset(new SkPoint[*numPts]);
- if (SkPath::kCW_Direction == dir) {
- for (int i = 0; i < *numPts; ++i) {
- (*data)[i] = ConvexLineOnlyData::gPoints[index][i];
- }
- } else {
- for (int i = 0; i < *numPts; ++i) {
- (*data)[i] = ConvexLineOnlyData::gPoints[index][*numPts - i - 1];
- }
- }
- } else {
- // procedurally generated
- SkScalar width = kMaxPathHeight / 2;
- SkScalar height = kMaxPathHeight / 2;
- switch (index - SK_ARRAY_COUNT(ConvexLineOnlyData::gPoints)) {
- case 0:
- *numPts = 3;
- break;
- case 1:
- *numPts = 4;
- break;
- case 2:
- *numPts = 5;
- break;
- case 3: // squashed pentagon
- *numPts = 5;
- width = kMaxPathHeight / 5;
- break;
- case 4:
- *numPts = 6;
- break;
- case 5:
- *numPts = 8;
- break;
- case 6: // squashed octogon
- *numPts = 8;
- width = kMaxPathHeight / 5;
- break;
- case 7:
- *numPts = 20;
- break;
- case 8:
- *numPts = 100;
- break;
- default:
- *numPts = 3;
- break;
- }
-
- data->reset(new SkPoint[*numPts]);
-
- create_ngon(*numPts, data->get(), width, height);
- if (SkPath::kCCW_Direction == dir) {
- // reverse it
- for (int i = 0; i < *numPts/2; ++i) {
- SkPoint tmp = (*data)[i];
- (*data)[i] = (*data)[*numPts - i - 1];
- (*data)[*numPts - i - 1] = tmp;
- }
- }
- }
- }
-
- // Draw a single path several times, shrinking it, flipping its direction
- // and changing its start vertex each time.
- void drawPath(SkCanvas* canvas, int index, SkPoint* offset) {
-
- SkPoint center;
- {
- std::unique_ptr<SkPoint[]> data(nullptr);
- int numPts;
- GetPath(index, SkPath::kCW_Direction, &data, &numPts);
- SkRect bounds;
- bounds.set(data.get(), numPts);
- if (offset->fX + bounds.width() > kGMWidth) {
- offset->fX = 0;
- offset->fY += kMaxPathHeight;
- }
- center = { offset->fX + SkScalarHalf(bounds.width()), offset->fY };
- offset->fX += bounds.width();
- }
-
- const SkPath::Direction dirs[2] = { SkPath::kCW_Direction, SkPath::kCCW_Direction };
- const float insets[] = { 5, 10, 15, 20, 25, 30, 35, 40 };
- const SkColor colors[] = { 0xFF901313, 0xFF8D6214, 0xFF698B14, 0xFF1C8914,
- 0xFF148755, 0xFF146C84, 0xFF142482, 0xFF4A1480 };
-
- SkPaint paint;
- paint.setAntiAlias(true);
- paint.setStyle(SkPaint::kStroke_Style);
- paint.setStrokeWidth(1);
-
- std::unique_ptr<SkPoint[]> data(nullptr);
- int numPts;
- GetPath(index, dirs[index % 2], &data, &numPts);
- {
- SkPath path;
- path.moveTo(data.get()[0]);
- for (int i = 1; i < numPts; ++i) {
- path.lineTo(data.get()[i]);
- }
- path.close();
- canvas->save();
- canvas->translate(center.fX, center.fY);
- canvas->drawPath(path, paint);
- canvas->restore();
- }
-
- SkTDArray<SkPoint> insetPoly;
- for (size_t i = 0; i < SK_ARRAY_COUNT(insets); ++i) {
- if (SkInsetConvexPolygon(data.get(), numPts, insets[i], &insetPoly)) {
- SkPath path;
- path.moveTo(insetPoly[0]);
- for (int i = 1; i < insetPoly.count(); ++i) {
- path.lineTo(insetPoly[i]);
- }
- path.close();
-
- paint.setColor(colors[i]);
- canvas->save();
- canvas->translate(center.fX, center.fY);
- canvas->drawPath(path, paint);
- canvas->restore();
- }
- }
- }
-
- void onDraw(SkCanvas* canvas) override {
- // the right edge of the last drawn path
- SkPoint offset = { 0, SkScalarHalf(kMaxPathHeight) };
-
- for (int i = 0; i < kNumPaths; ++i) {
- this->drawPath(canvas, i, &offset);
- }
- }
-
-private:
- static constexpr int kNumPaths = 20;
- static constexpr int kMaxPathHeight = 100;
- static constexpr int kGMWidth = 512;
- static constexpr int kGMHeight = 512;
-
- typedef GM INHERITED;
-};
-
//////////////////////////////////////////////////////////////////////////////
DEF_GM(return new ConvexLineOnlyPathsGM(false);)
DEF_GM(return new ConvexLineOnlyPathsGM(true);)
-DEF_GM(return new ConvexPolygonInsetGM();)
}
diff --git a/gm/polygonoffset.cpp b/gm/polygonoffset.cpp
new file mode 100644
index 0000000..cbf0849
--- /dev/null
+++ b/gm/polygonoffset.cpp
@@ -0,0 +1,606 @@
+/*
+ * Copyright 2018 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "gm.h"
+#include "sk_tool_utils.h"
+#include "SkOffsetPolygon.h"
+#include "SkPathPriv.h"
+
+static void create_ngon(int n, SkPoint* pts, SkScalar w, SkScalar h, SkPath::Direction dir) {
+ float angleStep = 360.0f / n, angle = 0.0f, sin, cos;
+ if ((n % 2) == 1) {
+ angle = angleStep/2.0f;
+ }
+ if (SkPath::kCCW_Direction == dir) {
+ angle = -angle;
+ angleStep = -angleStep;
+ }
+
+ for (int i = 0; i < n; ++i) {
+ sin = SkScalarSinCos(SkDegreesToRadians(angle), &cos);
+ pts[i].fX = -sin * w;
+ pts[i].fY = cos * h;
+ angle += angleStep;
+ }
+}
+
+namespace PolygonOffsetData {
+// narrow rect
+const SkPoint gPoints0[] = {
+ { -1.5f, -50.0f },
+ { 1.5f, -50.0f },
+ { 1.5f, 50.0f },
+ { -1.5f, 50.0f }
+};
+// narrow rect on an angle
+const SkPoint gPoints1[] = {
+ { -50.0f, -49.0f },
+ { -49.0f, -50.0f },
+ { 50.0f, 49.0f },
+ { 49.0f, 50.0f }
+};
+// trap - narrow on top - wide on bottom
+const SkPoint gPoints2[] = {
+ { -10.0f, -50.0f },
+ { 10.0f, -50.0f },
+ { 50.0f, 50.0f },
+ { -50.0f, 50.0f }
+};
+// wide skewed rect
+const SkPoint gPoints3[] = {
+ { -50.0f, -50.0f },
+ { 0.0f, -50.0f },
+ { 50.0f, 50.0f },
+ { 0.0f, 50.0f }
+};
+// thin rect with colinear-ish lines
+const SkPoint gPoints4[] = {
+ { -6.0f, -50.0f },
+ { 4.0f, -50.0f },
+ { 5.0f, -25.0f },
+ { 6.0f, 0.0f },
+ { 5.0f, 25.0f },
+ { 4.0f, 50.0f },
+ { -4.0f, 50.0f }
+};
+// degenerate
+const SkPoint gPoints5[] = {
+ { -0.025f, -0.025f },
+ { 0.025f, -0.025f },
+ { 0.025f, 0.025f },
+ { -0.025f, 0.025f }
+};
+// Quad with near coincident point
+const SkPoint gPoints6[] = {
+ { -20.0f, -13.0f },
+ { -20.0f, -13.05f },
+ { 20.0f, -13.0f },
+ { 20.0f, 27.0f }
+};
+// thin rect with colinear lines
+const SkPoint gPoints7[] = {
+ { -10.0f, -50.0f },
+ { 10.0f, -50.0f },
+ { 10.0f, -25.0f },
+ { 10.0f, 0.0f },
+ { 10.0f, 25.0f },
+ { 10.0f, 50.0f },
+ { -10.0f, 50.0f }
+};
+// capped teardrop
+const SkPoint gPoints8[] = {
+ { 50.00f, 50.00f },
+ { 0.00f, 50.00f },
+ { -15.45f, 47.55f },
+ { -29.39f, 40.45f },
+ { -40.45f, 29.39f },
+ { -47.55f, 15.45f },
+ { -50.00f, 0.00f },
+ { -47.55f, -15.45f },
+ { -40.45f, -29.39f },
+ { -29.39f, -40.45f },
+ { -15.45f, -47.55f },
+ { 0.00f, -50.00f },
+ { 50.00f, -50.00f }
+};
+// teardrop
+const SkPoint gPoints9[] = {
+ { 4.39f, 40.45f },
+ { -9.55f, 47.55f },
+ { -25.00f, 50.00f },
+ { -40.45f, 47.55f },
+ { -54.39f, 40.45f },
+ { -65.45f, 29.39f },
+ { -72.55f, 15.45f },
+ { -75.00f, 0.00f },
+ { -72.55f, -15.45f },
+ { -65.45f, -29.39f },
+ { -54.39f, -40.45f },
+ { -40.45f, -47.55f },
+ { -25.0f, -50.0f },
+ { -9.55f, -47.55f },
+ { 4.39f, -40.45f },
+ { 75.00f, 0.00f }
+};
+// clipped triangle
+const SkPoint gPoints10[] = {
+ { -10.0f, -50.0f },
+ { 10.0f, -50.0f },
+ { 50.0f, 31.0f },
+ { 40.0f, 50.0f },
+ { -40.0f, 50.0f },
+ { -50.0f, 31.0f },
+};
+
+// tab
+const SkPoint gPoints11[] = {
+ { -45, -25 },
+ { 45, -25 },
+ { 45, 25 },
+ { 20, 25 },
+ { 19.6157f, 25.f + 3.9018f },
+ { 18.4776f, 25.f + 7.6537f },
+ { 16.6294f, 25.f + 11.1114f },
+ { 14.1421f, 25.f + 14.1421f },
+ { 11.1114f, 25.f + 16.6294f },
+ { 7.6537f, 25.f + 18.4776f },
+ { 3.9018f, 25.f + 19.6157f },
+ { 0, 45.f },
+ { -3.9018f, 25.f + 19.6157f },
+ { -7.6537f, 25.f + 18.4776f },
+ { -11.1114f, 25.f + 16.6294f },
+ { -14.1421f, 25.f + 14.1421f },
+ { -16.6294f, 25.f + 11.1114f },
+ { -18.4776f, 25.f + 7.6537f },
+ { -19.6157f, 25.f + 3.9018f },
+ { -20, 25 },
+ { -45, 25 }
+};
+
+// star of david
+const SkPoint gPoints12[] = {
+ { 0.0f, -50.0f },
+ { 14.43f, -25.0f },
+ { 43.30f, -25.0f },
+ { 28.86f, 0.0f },
+ { 43.30f, 25.0f },
+ { 14.43f, 25.0f },
+ { 0.0f, 50.0f },
+ { -14.43f, 25.0f },
+ { -43.30f, 25.0f },
+ { -28.86f, 0.0f },
+ { -43.30f, -25.0f },
+ { -14.43f, -25.0f },
+};
+
+// notch
+const SkScalar kBottom = 25.f;
+const SkPoint gPoints13[] = {
+ { -50, kBottom - 50.f },
+ { 50, kBottom - 50.f },
+ { 50, kBottom },
+ { 20, kBottom },
+ { 19.6157f, kBottom - 3.9018f },
+ { 18.4776f, kBottom - 7.6537f },
+ { 16.6294f, kBottom - 11.1114f },
+ { 14.1421f, kBottom - 14.1421f },
+ { 11.1114f, kBottom - 16.6294f },
+ { 7.6537f, kBottom - 18.4776f },
+ { 3.9018f, kBottom - 19.6157f },
+ { 0, kBottom - 20.f },
+ { -3.9018f, kBottom - 19.6157f },
+ { -7.6537f, kBottom - 18.4776f },
+ { -11.1114f, kBottom - 16.6294f },
+ { -14.1421f, kBottom - 14.1421f },
+ { -16.6294f, kBottom - 11.1114f },
+ { -18.4776f, kBottom - 7.6537f },
+ { -19.6157f, kBottom - 3.9018f },
+ { -20, kBottom },
+ { -50, kBottom }
+};
+
+// crown
+const SkPoint gPoints14[] = {
+ { -40, -39 },
+ { 40, -39 },
+ { 40, -20 },
+ { 30, 40 },
+ { 20, -20 },
+ { 10, 40 },
+ { 0, -20 },
+ { -10, 40 },
+ { -20, -20 },
+ { -30, 40 },
+ { -40, -20 }
+};
+
+// dumbbell
+const SkPoint gPoints15[] = {
+ { -26, -3 },
+ { -24, -6.2f },
+ { -22.5f, -8 },
+ { -20, -9.9f },
+ { -17.5f, -10.3f },
+ { -15, -10.9f },
+ { -12.5f, -10.2f },
+ { -10, -9.7f },
+ { -7.5f, -8.1f },
+ { -5, -7.7f },
+ { -2.5f, -7.4f },
+ { 0, -7.7f },
+ { 3, -9 },
+ { 6.5f, -11.5f },
+ { 10.6f, -14 },
+ { 14, -15.2f },
+ { 17, -15.5f },
+ { 20, -15.2f },
+ { 23.4f, -14 },
+ { 27.5f, -11.5f },
+ { 30, -8 },
+ { 32, -4 },
+ { 32.5f, 0 },
+ { 32, 4 },
+ { 30, 8 },
+ { 27.5f, 11.5f },
+ { 23.4f, 14 },
+ { 20, 15.2f },
+ { 17, 15.5f },
+ { 14, 15.2f },
+ { 10.6f, 14 },
+ { 6.5f, 11.5f },
+ { 3, 9 },
+ { 0, 7.7f },
+ { -2.5f, 7.4f },
+ { -5, 7.7f },
+ { -7.5f, 8.1f },
+ { -10, 9.7f },
+ { -12.5f, 10.2f },
+ { -15, 10.9f },
+ { -17.5f, 10.3f },
+ { -20, 9.9f },
+ { -22.5f, 8 },
+ { -24, 6.2f },
+ { -26, 3 },
+ { -26.5f, 0 }
+};
+
+// truncated dumbbell
+// (checks winding computation in OffsetSimplePolygon)
+const SkPoint gPoints16[] = {
+ { -15 + 3, -9 },
+ { -15 + 6.5f, -11.5f },
+ { -15 + 10.6f, -14 },
+ { -15 + 14, -15.2f },
+ { -15 + 17, -15.5f },
+ { -15 + 20, -15.2f },
+ { -15 + 23.4f, -14 },
+ { -15 + 27.5f, -11.5f },
+ { -15 + 30, -8 },
+ { -15 + 32, -4 },
+ { -15 + 32.5f, 0 },
+ { -15 + 32, 4 },
+ { -15 + 30, 8 },
+ { -15 + 27.5f, 11.5f },
+ { -15 + 23.4f, 14 },
+ { -15 + 20, 15.2f },
+ { -15 + 17, 15.5f },
+ { -15 + 14, 15.2f },
+ { -15 + 10.6f, 14 },
+ { -15 + 6.5f, 11.5f },
+ { -15 + 3, 9 },
+};
+
+// square notch
+// (to detect segment-segment intersection)
+const SkPoint gPoints17[] = {
+ { -50, kBottom - 50.f },
+ { 50, kBottom - 50.f },
+ { 50, kBottom },
+ { 20, kBottom },
+ { 20, kBottom - 20.f },
+ { -20, kBottom - 20.f },
+ { -20, kBottom },
+ { -50, kBottom }
+};
+
+// box with Peano curve
+const SkPoint gPoints18[] = {
+ { 0, 0 },
+ { 0, -12 },
+ { -6, -12 },
+ { -6, 0 },
+ { -12, 0 },
+ { -12, -12},
+ { -18, -12},
+ { -18, 18},
+ { -12, 18},
+ {-12, 6},
+ {-6, 6},
+ {-6, 36},
+ {-12, 36},
+ {-12, 24},
+ {-18, 24},
+ {-18, 36},
+ {-24, 36},
+ {-24, 24},
+ {-30, 24},
+ {-30, 36},
+ {-36, 36},
+ {-36, 6},
+ {-30, 6},
+ {-30, 18},
+ {-24, 18},
+ {-24, -12},
+ {-30, -12},
+ {-30, 0},
+ {-36, 0},
+ {-36, -36},
+ {36, -36},
+ {36, 36},
+ {12, 36},
+ {12, 24},
+ {6, 24},
+ {6, 36},
+ {0, 36},
+ {0, 6},
+ {6, 6},
+ {6, 18},
+ {12, 18},
+ {12, -12},
+ {6, -12},
+ {6, 0}
+};
+
+
+const SkPoint* gConvexPoints[] = {
+ gPoints0, gPoints1, gPoints2, gPoints3, gPoints4, gPoints5, gPoints6,
+ gPoints7, gPoints8, gPoints9, gPoints10,
+};
+
+const size_t gConvexSizes[] = {
+ SK_ARRAY_COUNT(gPoints0),
+ SK_ARRAY_COUNT(gPoints1),
+ SK_ARRAY_COUNT(gPoints2),
+ SK_ARRAY_COUNT(gPoints3),
+ SK_ARRAY_COUNT(gPoints4),
+ SK_ARRAY_COUNT(gPoints5),
+ SK_ARRAY_COUNT(gPoints6),
+ SK_ARRAY_COUNT(gPoints7),
+ SK_ARRAY_COUNT(gPoints8),
+ SK_ARRAY_COUNT(gPoints9),
+ SK_ARRAY_COUNT(gPoints10),
+};
+static_assert(SK_ARRAY_COUNT(gConvexSizes) == SK_ARRAY_COUNT(gConvexPoints), "array_mismatch");
+
+const SkPoint* gSimplePoints[] = {
+ gPoints0, gPoints1, gPoints2, gPoints4, gPoints5, gPoints7,
+ gPoints8, gPoints11, gPoints12, gPoints13, gPoints14, gPoints15,
+ gPoints16, gPoints17, gPoints18,
+};
+
+const size_t gSimpleSizes[] = {
+ SK_ARRAY_COUNT(gPoints0),
+ SK_ARRAY_COUNT(gPoints1),
+ SK_ARRAY_COUNT(gPoints2),
+ SK_ARRAY_COUNT(gPoints4),
+ SK_ARRAY_COUNT(gPoints5),
+ SK_ARRAY_COUNT(gPoints7),
+ SK_ARRAY_COUNT(gPoints8),
+ SK_ARRAY_COUNT(gPoints11),
+ SK_ARRAY_COUNT(gPoints12),
+ SK_ARRAY_COUNT(gPoints13),
+ SK_ARRAY_COUNT(gPoints14),
+ SK_ARRAY_COUNT(gPoints15),
+ SK_ARRAY_COUNT(gPoints16),
+ SK_ARRAY_COUNT(gPoints17),
+ SK_ARRAY_COUNT(gPoints18),
+};
+static_assert(SK_ARRAY_COUNT(gSimpleSizes) == SK_ARRAY_COUNT(gSimplePoints), "array_mismatch");
+
+}
+
+namespace skiagm {
+
+// This GM is intended to exercise the offsetting of polygons
+class PolygonOffsetGM : public GM {
+public:
+ PolygonOffsetGM(bool convexOnly) : fConvexOnly(convexOnly) {
+ this->setBGColor(0xFFFFFFFF);
+ }
+
+protected:
+ SkString onShortName() override {
+ if (fConvexOnly) {
+ return SkString("convex-polygon-inset");
+ } else {
+ return SkString("simple-polygon-offset");
+ }
+ }
+ SkISize onISize() override { return SkISize::Make(kGMWidth, kGMHeight); }
+ bool runAsBench() const override { return true; }
+
+ static void GetConvexPolygon(int index, SkPath::Direction dir,
+ std::unique_ptr<SkPoint[]>* data, int* numPts) {
+ if (index < (int)SK_ARRAY_COUNT(PolygonOffsetData::gConvexPoints)) {
+ // manually specified
+ *numPts = (int)PolygonOffsetData::gConvexSizes[index];
+ data->reset(new SkPoint[*numPts]);
+ if (SkPath::kCW_Direction == dir) {
+ for (int i = 0; i < *numPts; ++i) {
+ (*data)[i] = PolygonOffsetData::gConvexPoints[index][i];
+ }
+ } else {
+ for (int i = 0; i < *numPts; ++i) {
+ (*data)[i] = PolygonOffsetData::gConvexPoints[index][*numPts - i - 1];
+ }
+ }
+ } else {
+ // procedurally generated
+ SkScalar width = kMaxPathHeight / 2;
+ SkScalar height = kMaxPathHeight / 2;
+ int numPtsArray[] = { 3, 4, 5, 5, 6, 8, 8, 20, 100 };
+
+ size_t arrayIndex = index - SK_ARRAY_COUNT(PolygonOffsetData::gConvexPoints);
+ SkASSERT(arrayIndex < SK_ARRAY_COUNT(numPtsArray));
+ *numPts = numPtsArray[arrayIndex];
+ if (arrayIndex == 3 || arrayIndex == 6) {
+ // squashed pentagon and octagon
+ width = kMaxPathHeight / 5;
+ }
+
+ data->reset(new SkPoint[*numPts]);
+
+ create_ngon(*numPts, data->get(), width, height, dir);
+ }
+ }
+
+ static void GetSimplePolygon(int index, SkPath::Direction dir,
+ std::unique_ptr<SkPoint[]>* data, int* numPts) {
+ if (index < (int)SK_ARRAY_COUNT(PolygonOffsetData::gSimplePoints)) {
+ // manually specified
+ *numPts = (int)PolygonOffsetData::gSimpleSizes[index];
+ data->reset(new SkPoint[*numPts]);
+ if (SkPath::kCW_Direction == dir) {
+ for (int i = 0; i < *numPts; ++i) {
+ (*data)[i] = PolygonOffsetData::gSimplePoints[index][i];
+ }
+ } else {
+ for (int i = 0; i < *numPts; ++i) {
+ (*data)[i] = PolygonOffsetData::gSimplePoints[index][*numPts - i - 1];
+ }
+ }
+ } else {
+ // procedurally generated
+ SkScalar width = kMaxPathHeight / 2;
+ SkScalar height = kMaxPathHeight / 2;
+ int numPtsArray[] = { 5, 7, 8, 20, 100 };
+
+ size_t arrayIndex = index - SK_ARRAY_COUNT(PolygonOffsetData::gSimplePoints);
+ arrayIndex = SkTMin(arrayIndex, SK_ARRAY_COUNT(numPtsArray) - 1);
+ SkASSERT(arrayIndex < SK_ARRAY_COUNT(numPtsArray));
+ *numPts = numPtsArray[arrayIndex];
+ // squash horizontally
+ width = kMaxPathHeight / 5;
+
+ data->reset(new SkPoint[*numPts]);
+
+ create_ngon(*numPts, data->get(), width, height, dir);
+ }
+ }
+ // Draw a single polygon with insets and potentially outsets
+ void drawPolygon(SkCanvas* canvas, int index, SkPoint* offset) {
+
+ SkPoint center;
+ {
+ std::unique_ptr<SkPoint[]> data(nullptr);
+ int numPts;
+ if (fConvexOnly) {
+ GetConvexPolygon(index, SkPath::kCW_Direction, &data, &numPts);
+ } else {
+ GetSimplePolygon(index, SkPath::kCW_Direction, &data, &numPts);
+ }
+ SkRect bounds;
+ bounds.set(data.get(), numPts);
+ if (!fConvexOnly) {
+ bounds.outset(kMaxOutset, kMaxOutset);
+ }
+ if (offset->fX + bounds.width() > kGMWidth) {
+ offset->fX = 0;
+ offset->fY += kMaxPathHeight;
+ }
+ center = { offset->fX + SkScalarHalf(bounds.width()), offset->fY };
+ offset->fX += bounds.width();
+ }
+
+ const SkPath::Direction dirs[2] = { SkPath::kCW_Direction, SkPath::kCCW_Direction };
+ const float insets[] = { 5, 10, 15, 20, 25, 30, 35, 40 };
+ const float offsets[] = { 2, 5, 9, 14, 20, 27, 35, 44, -2, -5, -9 };
+ const SkColor colors[] = { 0xFF901313, 0xFF8D6214, 0xFF698B14, 0xFF1C8914,
+ 0xFF148755, 0xFF146C84, 0xFF142482, 0xFF4A1480,
+ 0xFF901313, 0xFF8D6214, 0xFF698B14 };
+
+ SkPaint paint;
+ paint.setAntiAlias(true);
+ paint.setStyle(SkPaint::kStroke_Style);
+ paint.setStrokeWidth(1);
+
+ std::unique_ptr<SkPoint[]> data(nullptr);
+ int numPts;
+ if (fConvexOnly) {
+ GetConvexPolygon(index, dirs[index % 2], &data, &numPts);
+ } else {
+ GetSimplePolygon(index, dirs[index % 2], &data, &numPts);
+ }
+
+ {
+ SkPath path;
+ path.moveTo(data.get()[0]);
+ for (int i = 1; i < numPts; ++i) {
+ path.lineTo(data.get()[i]);
+ }
+ path.close();
+ canvas->save();
+ canvas->translate(center.fX, center.fY);
+ canvas->drawPath(path, paint);
+ canvas->restore();
+ }
+
+ SkTDArray<SkPoint> offsetPoly;
+ size_t count = fConvexOnly ? SK_ARRAY_COUNT(insets) : SK_ARRAY_COUNT(offsets);
+ for (size_t i = 0; i < count; ++i) {
+ bool result;
+ if (fConvexOnly) {
+ result = SkInsetConvexPolygon(data.get(), numPts, insets[i], &offsetPoly);
+ } else {
+ result = SkOffsetSimplePolygon(data.get(), numPts, offsets[i], &offsetPoly);
+ }
+ if (result) {
+ SkPath path;
+ path.moveTo(offsetPoly[0]);
+ for (int i = 1; i < offsetPoly.count(); ++i) {
+ path.lineTo(offsetPoly[i]);
+ }
+ path.close();
+
+ paint.setColor(sk_tool_utils::color_to_565(colors[i]));
+ canvas->save();
+ canvas->translate(center.fX, center.fY);
+ canvas->drawPath(path, paint);
+ canvas->restore();
+ }
+ }
+ }
+
+ void onDraw(SkCanvas* canvas) override {
+ // the right edge of the last drawn path
+ SkPoint offset = { 0, SkScalarHalf(kMaxPathHeight) };
+ if (!fConvexOnly) {
+ offset.fY += kMaxOutset;
+ }
+
+ for (int i = 0; i < kNumPaths; ++i) {
+ this->drawPolygon(canvas, i, &offset);
+ }
+ }
+
+private:
+ static constexpr int kNumPaths = 20;
+ static constexpr int kMaxPathHeight = 100;
+ static constexpr int kMaxOutset = 16;
+ static constexpr int kGMWidth = 512;
+ static constexpr int kGMHeight = 512;
+
+ bool fConvexOnly;
+
+ typedef GM INHERITED;
+};
+
+//////////////////////////////////////////////////////////////////////////////
+
+DEF_GM(return new PolygonOffsetGM(true);)
+DEF_GM(return new PolygonOffsetGM(false);)
+}
diff --git a/gn/gm.gni b/gn/gm.gni
index 5443fa8..1558881 100644
--- a/gn/gm.gni
+++ b/gn/gm.gni
@@ -247,6 +247,7 @@
"$_gm/points.cpp",
"$_gm/poly2poly.cpp",
"$_gm/polygons.cpp",
+ "$_gm/polygonoffset.cpp",
"$_gm/quadpaths.cpp",
"$_gm/radial_gradient_precision.cpp",
"$_gm/readpixels.cpp",
diff --git a/gn/tests.gni b/gn/tests.gni
index 958ef3a..154e300 100644
--- a/gn/tests.gni
+++ b/gn/tests.gni
@@ -160,6 +160,7 @@
"$_tests/PDFMetadataAttributeTest.cpp",
"$_tests/PDFOpaqueSrcModeToSrcOverTest.cpp",
"$_tests/PDFPrimitivesTest.cpp",
+ "$_tests/OffsetSimplePolyTest.cpp",
"$_tests/OnFlushCallbackTest.cpp",
"$_tests/PathRendererCacheTests.cpp",
"$_tests/PictureBBHTest.cpp",
diff --git a/src/utils/SkOffsetPolygon.cpp b/src/utils/SkOffsetPolygon.cpp
index c8ebbeb..bfd12d2 100755
--- a/src/utils/SkOffsetPolygon.cpp
+++ b/src/utils/SkOffsetPolygon.cpp
@@ -8,9 +8,11 @@
#include "SkOffsetPolygon.h"
#include "SkPointPriv.h"
+#include "SkTArray.h"
#include "SkTemplates.h"
+#include "SkTDPQueue.h"
-struct InsetSegment {
+struct OffsetSegment {
SkPoint fP0;
SkPoint fP1;
};
@@ -95,39 +97,65 @@
// Compute the intersection 'p' between segments s0 and s1, if any.
// 's' is the parametric value for the intersection along 's0' & 't' is the same for 's1'.
// Returns false if there is no intersection.
-static bool compute_intersection(const InsetSegment& s0, const InsetSegment& s1,
+static bool compute_intersection(const OffsetSegment& s0, const OffsetSegment& s1,
SkPoint* p, SkScalar* s, SkScalar* t) {
+ // Common cases for polygon chains -- check if endpoints are touching
+ if (SkPointPriv::EqualsWithinTolerance(s0.fP1, s1.fP0)) {
+ *p = s0.fP1;
+ *s = SK_Scalar1;
+ *t = 0;
+ return true;
+ }
+ if (SkPointPriv::EqualsWithinTolerance(s1.fP1, s0.fP0)) {
+ *p = s1.fP1;
+ *s = 0;
+ *t = SK_Scalar1;
+ return true;
+ }
+
SkVector v0 = s0.fP1 - s0.fP0;
SkVector v1 = s1.fP1 - s1.fP0;
-
- SkScalar perpDot = v0.cross(v1);
- if (SkScalarNearlyZero(perpDot)) {
- // segments are parallel
- // check if endpoints are touching
- if (SkPointPriv::EqualsWithinTolerance(s0.fP1, s1.fP0)) {
- *p = s0.fP1;
- *s = SK_Scalar1;
- *t = 0;
- return true;
- }
- if (SkPointPriv::EqualsWithinTolerance(s1.fP1, s0.fP0)) {
- *p = s1.fP1;
- *s = 0;
- *t = SK_Scalar1;
- return true;
- }
-
- return false;
- }
+ // We should have culled coincident points before this
+ SkASSERT(!SkPointPriv::EqualsWithinTolerance(s0.fP0, s0.fP1));
+ SkASSERT(!SkPointPriv::EqualsWithinTolerance(s1.fP0, s1.fP1));
SkVector d = s1.fP0 - s0.fP0;
- SkScalar localS = d.cross(v1) / perpDot;
- if (localS < 0 || localS > SK_Scalar1) {
- return false;
- }
- SkScalar localT = d.cross(v0) / perpDot;
- if (localT < 0 || localT > SK_Scalar1) {
- return false;
+ SkScalar perpDot = v0.cross(v1);
+ SkScalar localS, localT;
+ if (SkScalarNearlyZero(perpDot)) {
+ // segments are parallel, but not collinear
+ if (!SkScalarNearlyZero(d.dot(d), SK_ScalarNearlyZero*SK_ScalarNearlyZero)) {
+ return false;
+ }
+
+ // project segment1's endpoints onto segment0
+ localS = d.fX / v0.fX;
+ localT = 0;
+ if (localS < 0 || localS > SK_Scalar1) {
+ // the first endpoint doesn't lie on segment0, try the other one
+ SkScalar oldLocalS = localS;
+ localS = (s1.fP1.fX - s0.fP0.fX) / v0.fX;
+ localT = SK_Scalar1;
+ if (localS < 0 || localS > SK_Scalar1) {
+ // it's possible that segment1's interval surrounds segment0
+ // this is false if the params have the same signs, and in that case no collision
+ if (localS*oldLocalS > 0) {
+ return false;
+ }
+ // otherwise project segment0's endpoint onto segment1 instead
+ localS = 0;
+ localT = -d.fX / v1.fX;
+ }
+ }
+ } else {
+ localS = d.cross(v1) / perpDot;
+ if (localS < 0 || localS > SK_Scalar1) {
+ return false;
+ }
+ localT = d.cross(v0) / perpDot;
+ if (localT < 0 || localT > SK_Scalar1) {
+ return false;
+ }
}
v0 *= localS;
@@ -138,6 +166,30 @@
return true;
}
+// computes the line intersection and then the distance to s0's endpoint
+static SkScalar compute_crossing_distance(const OffsetSegment& s0, const OffsetSegment& s1) {
+ SkVector v0 = s0.fP1 - s0.fP0;
+ SkVector v1 = s1.fP1 - s1.fP0;
+
+ SkScalar perpDot = v0.cross(v1);
+ if (SkScalarNearlyZero(perpDot)) {
+ // segments are parallel
+ return SK_ScalarMax;
+ }
+
+ SkVector d = s1.fP0 - s0.fP0;
+ SkScalar localS = d.cross(v1) / perpDot;
+ if (localS < 0) {
+ localS = -localS;
+ } else {
+ localS -= SK_Scalar1;
+ }
+
+ localS *= v0.length();
+
+ return localS;
+}
+
static bool is_convex(const SkTDArray<SkPoint>& poly) {
if (poly.count() <= 3) {
return true;
@@ -162,6 +214,19 @@
return true;
}
+struct EdgeData {
+ OffsetSegment fInset;
+ SkPoint fIntersection;
+ SkScalar fTValue;
+ bool fValid;
+
+ void init() {
+ fIntersection = fInset.fP0;
+ fTValue = SK_ScalarMin;
+ fValid = true;
+ }
+};
+
// The objective here is to inset all of the edges by the given distance, and then
// remove any invalid inset edges by detecting right-hand turns. In a ccw polygon,
// we should only be making left-hand turns (for cw polygons, we use the winding
@@ -187,13 +252,6 @@
}
// set up
- struct EdgeData {
- InsetSegment fInset;
- SkPoint fIntersection;
- SkScalar fTValue;
- bool fValid;
- };
-
SkAutoSTMalloc<64, EdgeData> edgeData(inputPolygonSize);
for (int i = 0; i < inputPolygonSize; ++i) {
int j = (i + 1) % inputPolygonSize;
@@ -203,13 +261,13 @@
inputPolygonVerts[k])*winding < 0) {
return false;
}
- SkOffsetSegment(inputPolygonVerts[i], inputPolygonVerts[j],
- insetDistanceFunc(i), insetDistanceFunc(j),
- winding,
- &edgeData[i].fInset.fP0, &edgeData[i].fInset.fP1);
- edgeData[i].fIntersection = edgeData[i].fInset.fP0;
- edgeData[i].fTValue = SK_ScalarMin;
- edgeData[i].fValid = true;
+ if (!SkOffsetSegment(inputPolygonVerts[i], inputPolygonVerts[j],
+ insetDistanceFunc(i), insetDistanceFunc(j),
+ winding,
+ &edgeData[i].fInset.fP0, &edgeData[i].fInset.fP1)) {
+ return false;
+ }
+ edgeData[i].init();
}
int prevIndex = inputPolygonSize - 1;
@@ -294,3 +352,386 @@
return (insetPolygon->count() >= 3 && is_convex(*insetPolygon));
}
+
+// compute the number of points needed for a circular join when offsetting a reflex vertex
+static void compute_radial_steps(const SkVector& v1, const SkVector& v2, SkScalar r,
+ SkScalar* rotSin, SkScalar* rotCos, int* n) {
+ const SkScalar kRecipPixelsPerArcSegment = 0.25f;
+
+ SkScalar rCos = v1.dot(v2);
+ SkScalar rSin = v1.cross(v2);
+ SkScalar theta = SkScalarATan2(rSin, rCos);
+
+ int steps = SkScalarRoundToInt(SkScalarAbs(r*theta*kRecipPixelsPerArcSegment));
+
+ SkScalar dTheta = theta / steps;
+ *rotSin = SkScalarSinCos(dTheta, rotCos);
+ *n = steps;
+}
+
+// tolerant less-than comparison
+static inline bool nearly_lt(SkScalar a, SkScalar b, SkScalar tolerance = SK_ScalarNearlyZero) {
+ return a < b - tolerance;
+}
+
+// a point is "left" to another if its x coordinate is less, or if equal, its y coordinate
+static bool left(const SkPoint& p0, const SkPoint& p1) {
+ return nearly_lt(p0.fX, p1.fX) ||
+ (SkScalarNearlyEqual(p0.fX, p1.fX) && nearly_lt(p0.fY, p1.fY));
+}
+
+struct Vertex {
+ static bool Left(const Vertex& qv0, const Vertex& qv1) {
+ return left(qv0.fPosition, qv1.fPosition);
+ }
+ // packed to fit into 16 bytes (one cache line)
+ SkPoint fPosition;
+ uint16_t fIndex; // index in unsorted polygon
+ uint16_t fPrevIndex; // indices for previous and next vertex in unsorted polygon
+ uint16_t fNextIndex;
+ uint16_t fFlags;
+};
+
+enum VertexFlags {
+ kPrevLeft_VertexFlag = 0x1,
+ kNextLeft_VertexFlag = 0x2,
+};
+
+struct Edge {
+ // returns true if "this" is above "that"
+ bool above(const Edge& that, SkScalar tolerance = SK_ScalarNearlyZero) {
+ SkASSERT(nearly_lt(this->fSegment.fP0.fX, that.fSegment.fP0.fX, tolerance) ||
+ SkScalarNearlyEqual(this->fSegment.fP0.fX, that.fSegment.fP0.fX, tolerance));
+ // The idea here is that if the vector between the origins of the two segments (dv)
+ // rotates counterclockwise up to the vector representing the "this" segment (u),
+ // then we know that "this" is above that. If the result is clockwise we say it's below.
+ SkVector dv = that.fSegment.fP0 - this->fSegment.fP0;
+ SkVector u = this->fSegment.fP1 - this->fSegment.fP0;
+ SkScalar cross = dv.cross(u);
+ if (cross > tolerance) {
+ return true;
+ } else if (cross < -tolerance) {
+ return false;
+ }
+ // If the result is 0 then either the two origins are equal or the origin of "that"
+ // lies on dv. So then we try the same for the vector from the tail of "this"
+ // to the head of "that". Again, ccw means "this" is above "that".
+ dv = that.fSegment.fP1 - this->fSegment.fP0;
+ return (dv.cross(u) > tolerance);
+ }
+
+ bool intersect(const Edge& that) const {
+ SkPoint intersection;
+ SkScalar s, t;
+ // check first to see if these edges are neighbors in the polygon
+ if (this->fIndex0 == that.fIndex0 || this->fIndex1 == that.fIndex0 ||
+ this->fIndex0 == that.fIndex1 || this->fIndex1 == that.fIndex1) {
+ return false;
+ }
+ return compute_intersection(this->fSegment, that.fSegment, &intersection, &s, &t);
+ }
+
+ bool operator==(const Edge& that) const {
+ return (this->fIndex0 == that.fIndex0 && this->fIndex1 == that.fIndex1);
+ }
+
+ bool operator!=(const Edge& that) const {
+ return !operator==(that);
+ }
+
+ OffsetSegment fSegment;
+ int32_t fIndex0; // indices for previous and next vertex
+ int32_t fIndex1;
+};
+
+class EdgeList {
+public:
+ void reserve(int count) { fEdges.reserve(count); }
+
+ bool insert(const Edge& newEdge) {
+ // linear search for now (expected case is very few active edges)
+ int insertIndex = 0;
+ while (insertIndex < fEdges.count() && fEdges[insertIndex].above(newEdge)) {
+ ++insertIndex;
+ }
+ // if we intersect with the existing edge above or below us
+ // then we know this polygon is not simple, so don't insert, just fail
+ if (insertIndex > 0 && newEdge.intersect(fEdges[insertIndex - 1])) {
+ return false;
+ }
+ if (insertIndex < fEdges.count() && newEdge.intersect(fEdges[insertIndex])) {
+ return false;
+ }
+
+ fEdges.push_back();
+ for (int i = fEdges.count() - 1; i > insertIndex; --i) {
+ fEdges[i] = fEdges[i - 1];
+ }
+ fEdges[insertIndex] = newEdge;
+
+ return true;
+ }
+
+ bool remove(const Edge& edge) {
+ SkASSERT(fEdges.count() > 0);
+
+ // linear search for now (expected case is very few active edges)
+ int removeIndex = 0;
+ while (removeIndex < fEdges.count() && fEdges[removeIndex] != edge) {
+ ++removeIndex;
+ }
+ // we'd better find it or something is wrong
+ SkASSERT(removeIndex < fEdges.count());
+
+ // if we intersect with the edge above or below us
+ // then we know this polygon is not simple, so don't remove, just fail
+ if (removeIndex > 0 && fEdges[removeIndex].intersect(fEdges[removeIndex-1])) {
+ return false;
+ }
+ if (removeIndex < fEdges.count()-1) {
+ if (fEdges[removeIndex].intersect(fEdges[removeIndex + 1])) {
+ return false;
+ }
+ // copy over the old entry
+ memmove(&fEdges[removeIndex], &fEdges[removeIndex + 1],
+ sizeof(Edge)*(fEdges.count() - removeIndex - 1));
+ }
+
+ fEdges.pop_back();
+ return true;
+ }
+
+private:
+ SkSTArray<1, Edge> fEdges;
+};
+
+// Here we implement a sweep line algorithm to determine whether the provided points
+// represent a simple polygon, i.e., the polygon is non-self-intersecting.
+// We first insert the vertices into a priority queue sorting horizontally from left to right.
+// Then as we pop the vertices from the queue we generate events which indicate that an edge
+// should be added or removed from an edge list. If any intersections are detected in the edge
+// list, then we know the polygon is self-intersecting and hence not simple.
+static bool is_simple_polygon(const SkPoint* polygon, int polygonSize) {
+ SkTDPQueue <Vertex, Vertex::Left> vertexQueue;
+ EdgeList sweepLine;
+
+ sweepLine.reserve(polygonSize);
+ for (int i = 0; i < polygonSize; ++i) {
+ Vertex newVertex;
+ newVertex.fPosition = polygon[i];
+ newVertex.fIndex = i;
+ newVertex.fPrevIndex = (i - 1 + polygonSize) % polygonSize;
+ newVertex.fNextIndex = (i + 1) % polygonSize;
+ newVertex.fFlags = 0;
+ if (left(polygon[newVertex.fPrevIndex], polygon[i])) {
+ newVertex.fFlags |= kPrevLeft_VertexFlag;
+ }
+ if (left(polygon[newVertex.fNextIndex], polygon[i])) {
+ newVertex.fFlags |= kNextLeft_VertexFlag;
+ }
+ vertexQueue.insert(newVertex);
+ }
+
+ // pop each vertex from the queue and generate events depending on
+ // where it lies relative to its neighboring edges
+ while (vertexQueue.count() > 0) {
+ const Vertex& v = vertexQueue.peek();
+
+ // check edge to previous vertex
+ if (v.fFlags & kPrevLeft_VertexFlag) {
+ Edge edge{ { polygon[v.fPrevIndex], v.fPosition }, v.fPrevIndex, v.fIndex };
+ if (!sweepLine.remove(edge)) {
+ break;
+ }
+ } else {
+ Edge edge{ { v.fPosition, polygon[v.fPrevIndex] }, v.fIndex, v.fPrevIndex };
+ if (!sweepLine.insert(edge)) {
+ break;
+ }
+ }
+
+ // check edge to next vertex
+ if (v.fFlags & kNextLeft_VertexFlag) {
+ Edge edge{ { polygon[v.fNextIndex], v.fPosition }, v.fNextIndex, v.fIndex };
+ if (!sweepLine.remove(edge)) {
+ break;
+ }
+ } else {
+ Edge edge{ { v.fPosition, polygon[v.fNextIndex] }, v.fIndex, v.fNextIndex };
+ if (!sweepLine.insert(edge)) {
+ break;
+ }
+ }
+
+ vertexQueue.pop();
+ }
+
+ return (vertexQueue.count() == 0);
+}
+
+// TODO: assuming a constant offset here -- do we want to support variable offset?
+bool SkOffsetSimplePolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize,
+ SkScalar offset, SkTDArray<SkPoint>* offsetPolygon) {
+ if (inputPolygonSize < 3) {
+ return false;
+ }
+
+ if (!is_simple_polygon(inputPolygonVerts, inputPolygonSize)) {
+ return false;
+ }
+
+ // compute area and use sign to determine winding
+ // do initial pass to build normals
+ SkAutoSTMalloc<64, SkVector> normals(inputPolygonSize);
+ SkScalar quadArea = 0;
+ for (int curr = 0; curr < inputPolygonSize; ++curr) {
+ int next = (curr + 1) % inputPolygonSize;
+ SkVector tangent = inputPolygonVerts[next] - inputPolygonVerts[curr];
+ SkVector normal = SkVector::Make(-tangent.fY, tangent.fX);
+ normals[curr] = normal;
+ quadArea += inputPolygonVerts[curr].cross(inputPolygonVerts[next]);
+ }
+ // 1 == ccw, -1 == cw
+ int winding = (quadArea > 0) ? 1 : -1;
+ if (0 == winding) {
+ return false;
+ }
+
+ // resize normals to match offset
+ for (int curr = 0; curr < inputPolygonSize; ++curr) {
+ normals[curr].setLength(winding*offset);
+ }
+
+ // build initial offset edge list
+ SkSTArray<64, EdgeData> edgeData(inputPolygonSize);
+ int prevIndex = inputPolygonSize - 1;
+ int currIndex = 0;
+ int nextIndex = 1;
+ while (currIndex < inputPolygonSize) {
+ int side = compute_side(inputPolygonVerts[prevIndex],
+ inputPolygonVerts[currIndex],
+ inputPolygonVerts[nextIndex]);
+
+ // if reflex point, fill in curve
+ if (side*winding*offset < 0) {
+ SkScalar rotSin, rotCos;
+ int numSteps;
+ SkVector prevNormal = normals[prevIndex];
+ compute_radial_steps(prevNormal, normals[currIndex], SkScalarAbs(offset),
+ &rotSin, &rotCos, &numSteps);
+ for (int i = 0; i < numSteps - 1; ++i) {
+ SkVector currNormal = SkVector::Make(prevNormal.fX*rotCos - prevNormal.fY*rotSin,
+ prevNormal.fY*rotCos + prevNormal.fX*rotSin);
+ EdgeData& edge = edgeData.push_back();
+ edge.fInset.fP0 = inputPolygonVerts[currIndex] + prevNormal;
+ edge.fInset.fP1 = inputPolygonVerts[currIndex] + currNormal;
+ edge.init();
+ prevNormal = currNormal;
+ }
+ EdgeData& edge = edgeData.push_back();
+ edge.fInset.fP0 = inputPolygonVerts[currIndex] + prevNormal;
+ edge.fInset.fP1 = inputPolygonVerts[currIndex] + normals[currIndex];
+ edge.init();
+ }
+
+ // Add the edge
+ EdgeData& edge = edgeData.push_back();
+ edge.fInset.fP0 = inputPolygonVerts[currIndex] + normals[currIndex];
+ edge.fInset.fP1 = inputPolygonVerts[nextIndex] + normals[currIndex];
+ edge.init();
+
+ prevIndex = currIndex;
+ currIndex++;
+ nextIndex = (nextIndex + 1) % inputPolygonSize;
+ }
+
+ int edgeDataSize = edgeData.count();
+ prevIndex = edgeDataSize - 1;
+ currIndex = 0;
+ int insetVertexCount = edgeDataSize;
+ while (prevIndex != currIndex) {
+ if (!edgeData[prevIndex].fValid) {
+ prevIndex = (prevIndex + edgeDataSize - 1) % edgeDataSize;
+ continue;
+ }
+
+ SkScalar s, t;
+ SkPoint intersection;
+ if (compute_intersection(edgeData[prevIndex].fInset, edgeData[currIndex].fInset,
+ &intersection, &s, &t)) {
+ // if new intersection is further back on previous inset from the prior intersection
+ if (s < edgeData[prevIndex].fTValue) {
+ // no point in considering this one again
+ edgeData[prevIndex].fValid = false;
+ --insetVertexCount;
+ // go back one segment
+ prevIndex = (prevIndex + edgeDataSize - 1) % edgeDataSize;
+ // we've already considered this intersection, we're done
+ } else if (edgeData[currIndex].fTValue > SK_ScalarMin &&
+ SkPointPriv::EqualsWithinTolerance(intersection,
+ edgeData[currIndex].fIntersection,
+ 1.0e-6f)) {
+ break;
+ } else {
+ // add intersection
+ edgeData[currIndex].fIntersection = intersection;
+ edgeData[currIndex].fTValue = t;
+
+ // go to next segment
+ prevIndex = currIndex;
+ currIndex = (currIndex + 1) % edgeDataSize;
+ }
+ } else {
+ // If there is no intersection, we want to minimize the distance between
+ // the point where the segment lines cross and the segments themselves.
+ SkScalar prevPrevIndex = (prevIndex + edgeDataSize - 1) % edgeDataSize;
+ SkScalar currNextIndex = (currIndex + 1) % edgeDataSize;
+ SkScalar dist0 = compute_crossing_distance(edgeData[currIndex].fInset,
+ edgeData[prevPrevIndex].fInset);
+ SkScalar dist1 = compute_crossing_distance(edgeData[prevIndex].fInset,
+ edgeData[currNextIndex].fInset);
+ if (dist0 < dist1) {
+ edgeData[prevIndex].fValid = false;
+ prevIndex = prevPrevIndex;
+ } else {
+ edgeData[currIndex].fValid = false;
+ currIndex = currNextIndex;
+ }
+ --insetVertexCount;
+ }
+ }
+
+ // store all the valid intersections that aren't nearly coincident
+ // TODO: look at the main algorithm and see if we can detect these better
+ static constexpr SkScalar kCleanupTolerance = 0.01f;
+
+ offsetPolygon->reset();
+ offsetPolygon->setReserve(insetVertexCount);
+ currIndex = -1;
+ for (int i = 0; i < edgeData.count(); ++i) {
+ if (edgeData[i].fValid && (currIndex == -1 ||
+ !SkPointPriv::EqualsWithinTolerance(edgeData[i].fIntersection,
+ (*offsetPolygon)[currIndex],
+ kCleanupTolerance))) {
+ *offsetPolygon->push() = edgeData[i].fIntersection;
+ currIndex++;
+ }
+ }
+ // make sure the first and last points aren't coincident
+ if (currIndex >= 1 &&
+ SkPointPriv::EqualsWithinTolerance((*offsetPolygon)[0], (*offsetPolygon)[currIndex],
+ kCleanupTolerance)) {
+ offsetPolygon->pop();
+ }
+
+ // compute signed area to check winding (it should be same as the original polygon)
+ quadArea = 0;
+ for (int curr = 0; curr < offsetPolygon->count(); ++curr) {
+ int next = (curr + 1) % offsetPolygon->count();
+ quadArea += (*offsetPolygon)[curr].cross((*offsetPolygon)[next]);
+ }
+
+ return (winding*quadArea > 0 &&
+ is_simple_polygon(offsetPolygon->begin(), offsetPolygon->count()));
+}
+
diff --git a/src/utils/SkOffsetPolygon.h b/src/utils/SkOffsetPolygon.h
index 1d5a19c..a0555ab 100755
--- a/src/utils/SkOffsetPolygon.h
+++ b/src/utils/SkOffsetPolygon.h
@@ -5,8 +5,8 @@
* found in the LICENSE file.
*/
-#ifndef SkInsetConvexPolygon_DEFINED
-#define SkInsetConvexPolygon_DEFINED
+#ifndef SkOffsetPolygon_DEFINED
+#define SkOffsetPolygon_DEFINED
#include <functional>
@@ -29,14 +29,27 @@
SkTDArray<SkPoint>* insetPolygon);
inline bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize,
- SkScalar inset,
- SkTDArray<SkPoint>* insetPolygon) {
+ SkScalar inset, SkTDArray<SkPoint>* insetPolygon) {
return SkInsetConvexPolygon(inputPolygonVerts, inputPolygonSize,
[inset](int) { return inset; },
insetPolygon);
}
/**
+ * Generates a simple polygon (if possible) that is offset a given distance from the boundary of a
+ * given simple polygon.
+ *
+ * @param inputPolygonVerts Array of points representing the vertices of the original polygon.
+ * @param inputPolygonSize Number of vertices in the original polygon.
+ * @param offset How far we wish to offset the polygon.
+ * Positive value means inset, negative value means outset.
+ * @param offsetPolgon The resulting offset polygon, if any.
+ * @return true if an offset simple polygon exists, false otherwise.
+ */
+bool SkOffsetSimplePolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize,
+ SkScalar offset, SkTDArray<SkPoint>* offsetPolygon);
+
+/**
* Offset a segment by the given distance at each point.
* Uses the outer tangents of two circles centered on each endpoint.
* See: https://en.wikipedia.org/wiki/Tangent_lines_to_circles
diff --git a/tests/OffsetSimplePolyTest.cpp b/tests/OffsetSimplePolyTest.cpp
new file mode 100644
index 0000000..50f680e
--- /dev/null
+++ b/tests/OffsetSimplePolyTest.cpp
@@ -0,0 +1,210 @@
+/*
+ * Copyright 2017 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#include "Test.h"
+#include "SkOffsetPolygon.h"
+
+static bool is_convex(const SkTDArray<SkPoint>& poly) {
+ if (poly.count() < 3) {
+ return false;
+ }
+
+ SkVector v0 = poly[0] - poly[poly.count() - 1];
+ SkVector v1 = poly[1] - poly[poly.count() - 1];
+ SkScalar winding = v0.cross(v1);
+
+ for (int i = 0; i < poly.count()-1; ++i) {
+ int j = i + 1;
+ int k = (i + 2) % poly.count();
+
+ SkVector v0 = poly[j] - poly[i];
+ SkVector v1 = poly[k] - poly[i];
+ SkScalar perpDot = v0.cross(v1);
+ if (winding*perpDot < 0) {
+ return false;
+ }
+ }
+
+ return true;
+}
+
+DEF_TEST(OffsetSimplePoly, reporter) {
+ SkTDArray<SkPoint> rrectPoly;
+
+ ///////////////////////////////////////////////////////////////////////
+ // Try convex tests first
+
+ // round rect
+ *rrectPoly.push() = SkPoint::Make(-100, 55);
+ *rrectPoly.push() = SkPoint::Make(100, 55);
+ *rrectPoly.push() = SkPoint::Make(100 + 2.5f, 50 + 4.330127f);
+ *rrectPoly.push() = SkPoint::Make(100 + 3.535534f, 50 + 3.535534f);
+ *rrectPoly.push() = SkPoint::Make(100 + 4.330127f, 50 + 2.5f);
+ *rrectPoly.push() = SkPoint::Make(105, 50);
+ *rrectPoly.push() = SkPoint::Make(105, -50);
+ *rrectPoly.push() = SkPoint::Make(100 + 4.330127f, -50 - 2.5f);
+ *rrectPoly.push() = SkPoint::Make(100 + 3.535534f, -50 - 3.535534f);
+ *rrectPoly.push() = SkPoint::Make(100 + 2.5f, -50 - 4.330127f);
+ *rrectPoly.push() = SkPoint::Make(100, -55);
+ *rrectPoly.push() = SkPoint::Make(-100, -55);
+ *rrectPoly.push() = SkPoint::Make(-100 - 2.5f, -50 - 4.330127f);
+ *rrectPoly.push() = SkPoint::Make(-100 - 3.535534f, -50 - 3.535534f);
+ *rrectPoly.push() = SkPoint::Make(-100 - 4.330127f, -50 - 2.5f);
+ *rrectPoly.push() = SkPoint::Make(-105, -50);
+ *rrectPoly.push() = SkPoint::Make(-105, 50);
+ *rrectPoly.push() = SkPoint::Make(-100 - 4.330127f, 50 + 2.5f);
+ *rrectPoly.push() = SkPoint::Make(-100 - 3.535534f, 50 + 3.535534f);
+ *rrectPoly.push() = SkPoint::Make(-100 - 2.5f, 50 + 4.330127f);
+ REPORTER_ASSERT(reporter, is_convex(rrectPoly));
+
+ // inset a little
+ SkTDArray<SkPoint> offsetPoly;
+ bool result = SkOffsetSimplePolygon(&rrectPoly[0], rrectPoly.count(), 3, &offsetPoly);
+ REPORTER_ASSERT(reporter, result);
+ REPORTER_ASSERT(reporter, is_convex(offsetPoly));
+
+ // inset to rect
+ result = SkOffsetSimplePolygon(&rrectPoly[0], rrectPoly.count(), 10, &offsetPoly);
+ REPORTER_ASSERT(reporter, result);
+ REPORTER_ASSERT(reporter, is_convex(offsetPoly));
+ REPORTER_ASSERT(reporter, offsetPoly.count() == 4);
+ if (offsetPoly.count() == 4) {
+ REPORTER_ASSERT(reporter, offsetPoly[0].equals(-95, 45));
+ REPORTER_ASSERT(reporter, offsetPoly[1].equals(95, 45));
+ REPORTER_ASSERT(reporter, offsetPoly[2].equals(95, -45));
+ REPORTER_ASSERT(reporter, offsetPoly[3].equals(-95, -45));
+ }
+
+ // just to full inset
+ // fails, but outputs a line segment
+ result = SkOffsetSimplePolygon(&rrectPoly[0], rrectPoly.count(), 55, &offsetPoly);
+ REPORTER_ASSERT(reporter, !result);
+ REPORTER_ASSERT(reporter, !is_convex(offsetPoly));
+ REPORTER_ASSERT(reporter, offsetPoly.count() == 2);
+ if (offsetPoly.count() == 2) {
+ REPORTER_ASSERT(reporter, offsetPoly[0].equals(-50, 0));
+ REPORTER_ASSERT(reporter, offsetPoly[1].equals(50, 0));
+ }
+
+ // past full inset
+ result = SkOffsetSimplePolygon(&rrectPoly[0], rrectPoly.count(), 75, &offsetPoly);
+ REPORTER_ASSERT(reporter, !result);
+ REPORTER_ASSERT(reporter, offsetPoly.count() == 0);
+
+ // troublesome case
+ SkTDArray<SkPoint> clippedRRectPoly;
+ *clippedRRectPoly.push() = SkPoint::Make(335.928101f, 428.219055f);
+ *clippedRRectPoly.push() = SkPoint::Make(330.414459f, 423.034912f);
+ *clippedRRectPoly.push() = SkPoint::Make(325.749084f, 417.395508f);
+ *clippedRRectPoly.push() = SkPoint::Make(321.931946f, 411.300842f);
+ *clippedRRectPoly.push() = SkPoint::Make(318.963074f, 404.750977f);
+ *clippedRRectPoly.push() = SkPoint::Make(316.842468f, 397.745850f);
+ *clippedRRectPoly.push() = SkPoint::Make(315.570068f, 390.285522f);
+ *clippedRRectPoly.push() = SkPoint::Make(315.145966f, 382.369965f);
+ *clippedRRectPoly.push() = SkPoint::Make(315.570068f, 374.454346f);
+ *clippedRRectPoly.push() = SkPoint::Make(316.842468f, 366.994019f);
+ *clippedRRectPoly.push() = SkPoint::Make(318.963074f, 359.988892f);
+ *clippedRRectPoly.push() = SkPoint::Make(321.931946f, 353.439056f);
+ *clippedRRectPoly.push() = SkPoint::Make(325.749084f, 347.344421f);
+ *clippedRRectPoly.push() = SkPoint::Make(330.414459f, 341.705017f);
+ *clippedRRectPoly.push() = SkPoint::Make(335.928101f, 336.520813f);
+ *clippedRRectPoly.push() = SkPoint::Make(342.289948f, 331.791901f);
+ *clippedRRectPoly.push() = SkPoint::Make(377.312134f, 331.791901f);
+ *clippedRRectPoly.push() = SkPoint::Make(381.195313f, 332.532593f);
+ *clippedRRectPoly.push() = SkPoint::Make(384.464935f, 334.754700f);
+ *clippedRRectPoly.push() = SkPoint::Make(386.687042f, 338.024292f);
+ *clippedRRectPoly.push() = SkPoint::Make(387.427765f, 341.907532f);
+ *clippedRRectPoly.push() = SkPoint::Make(387.427765f, 422.832367f);
+ *clippedRRectPoly.push() = SkPoint::Make(386.687042f, 426.715576f);
+ *clippedRRectPoly.push() = SkPoint::Make(384.464935f, 429.985168f);
+ *clippedRRectPoly.push() = SkPoint::Make(381.195313f, 432.207275f);
+ *clippedRRectPoly.push() = SkPoint::Make(377.312134f, 432.947998f);
+ *clippedRRectPoly.push() = SkPoint::Make(342.289948f, 432.947998f);
+ REPORTER_ASSERT(reporter, is_convex(clippedRRectPoly));
+
+ result = SkOffsetSimplePolygon(&clippedRRectPoly[0], clippedRRectPoly.count(), 32.3699417f,
+ &offsetPoly);
+ REPORTER_ASSERT(reporter, result);
+ REPORTER_ASSERT(reporter, is_convex(offsetPoly));
+
+ ////////////////////////////////////////////////////////////////////////////////
+ // Concave tests
+
+ SkTDArray<SkPoint> starPoly;
+ *starPoly.push() = SkPoint::Make(0.0f, -50.0f);
+ *starPoly.push() = SkPoint::Make(14.43f, -25.0f);
+ *starPoly.push() = SkPoint::Make(43.30f, -25.0f);
+ *starPoly.push() = SkPoint::Make(28.86f, 0.0f);
+ *starPoly.push() = SkPoint::Make(43.30f, 25.0f);
+ *starPoly.push() = SkPoint::Make(14.43f, 25.0f);
+ *starPoly.push() = SkPoint::Make(0.0f, 50.0f);
+ *starPoly.push() = SkPoint::Make(-14.43f, 25.0f);
+ *starPoly.push() = SkPoint::Make(-43.30f, 25.0f);
+ *starPoly.push() = SkPoint::Make(-28.86f, 0.0f);
+ *starPoly.push() = SkPoint::Make(-43.30f, -25.0f);
+ *starPoly.push() = SkPoint::Make(-14.43f, -25.0f);
+
+ // try a variety of distances
+ result = SkOffsetSimplePolygon(&starPoly[0], starPoly.count(), 0.1f,
+ &offsetPoly);
+ REPORTER_ASSERT(reporter, result);
+
+ result = SkOffsetSimplePolygon(&starPoly[0], starPoly.count(), 5.665f,
+ &offsetPoly);
+ REPORTER_ASSERT(reporter, result);
+
+ result = SkOffsetSimplePolygon(&starPoly[0], starPoly.count(), 28,
+ &offsetPoly);
+ REPORTER_ASSERT(reporter, result);
+
+ // down to a point
+ result = SkOffsetSimplePolygon(&starPoly[0], starPoly.count(), 28.866f,
+ &offsetPoly);
+ REPORTER_ASSERT(reporter, !result);
+
+ // and past
+ result = SkOffsetSimplePolygon(&starPoly[0], starPoly.count(), 50.5f,
+ &offsetPoly);
+ REPORTER_ASSERT(reporter, !result);
+
+ // and now out
+ result = SkOffsetSimplePolygon(&starPoly[0], starPoly.count(), -0.1f,
+ &offsetPoly);
+ REPORTER_ASSERT(reporter, result);
+
+ result = SkOffsetSimplePolygon(&starPoly[0], starPoly.count(), -5.6665f,
+ &offsetPoly);
+ REPORTER_ASSERT(reporter, result);
+
+ result = SkOffsetSimplePolygon(&starPoly[0], starPoly.count(), -50,
+ &offsetPoly);
+ REPORTER_ASSERT(reporter, result);
+
+ result = SkOffsetSimplePolygon(&starPoly[0], starPoly.count(), -100,
+ &offsetPoly);
+ REPORTER_ASSERT(reporter, result);
+
+ SkTDArray<SkPoint> intersectingPoly;
+ *intersectingPoly.push() = SkPoint::Make(0.0f, -50.0f);
+ *intersectingPoly.push() = SkPoint::Make(14.43f, -25.0f);
+ *intersectingPoly.push() = SkPoint::Make(43.30f, -25.0f);
+ *intersectingPoly.push() = SkPoint::Make(-28.86f, 0.0f);
+ *intersectingPoly.push() = SkPoint::Make(43.30f, 25.0f);
+ *intersectingPoly.push() = SkPoint::Make(14.43f, 25.0f);
+ *intersectingPoly.push() = SkPoint::Make(0.0f, 50.0f);
+ *intersectingPoly.push() = SkPoint::Make(-14.43f, 25.0f);
+ *intersectingPoly.push() = SkPoint::Make(-43.30f, 25.0f);
+ *intersectingPoly.push() = SkPoint::Make(28.86f, 0.0f);
+ *intersectingPoly.push() = SkPoint::Make(-43.30f, -25.0f);
+ *intersectingPoly.push() = SkPoint::Make(-14.43f, -25.0f);
+
+ result = SkOffsetSimplePolygon(&intersectingPoly[0], intersectingPoly.count(), -100,
+ &offsetPoly);
+ REPORTER_ASSERT(reporter, !result);
+
+
+
+}