diff options
-rw-r--r-- | gm/convex_all_line_paths.cpp | 165 | ||||
-rw-r--r-- | gm/polygonoffset.cpp | 606 | ||||
-rw-r--r-- | gn/gm.gni | 1 | ||||
-rw-r--r-- | gn/tests.gni | 1 | ||||
-rwxr-xr-x | src/utils/SkOffsetPolygon.cpp | 521 | ||||
-rwxr-xr-x | src/utils/SkOffsetPolygon.h | 21 | ||||
-rw-r--r-- | tests/OffsetSimplePolyTest.cpp | 210 |
7 files changed, 1316 insertions, 209 deletions
diff --git a/gm/convex_all_line_paths.cpp b/gm/convex_all_line_paths.cpp index b8cdbce72a..b1907bccb7 100644 --- a/gm/convex_all_line_paths.cpp +++ b/gm/convex_all_line_paths.cpp @@ -350,173 +350,8 @@ private: 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 0000000000..cbf0849675 --- /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);) +} @@ -247,6 +247,7 @@ gm_sources = [ "$_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 958ef3a9cc..154e300858 100644 --- a/gn/tests.gni +++ b/gn/tests.gni @@ -160,6 +160,7 @@ tests_sources = [ "$_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 c8ebbeb7af..bfd12d2bc8 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 @@ bool SkOffsetSegment(const SkPoint& p0, const SkPoint& p1, SkScalar d0, SkScalar // 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; + // 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 perpDot = v0.cross(v1); + SkScalar localS, localT; 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; + // segments are parallel, but not collinear + if (!SkScalarNearlyZero(d.dot(d), SK_ScalarNearlyZero*SK_ScalarNearlyZero)) { + return false; } - return false; - } - - 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; + // 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 @@ static bool compute_intersection(const InsetSegment& s0, const InsetSegment& s1, 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 @@ static bool is_convex(const SkTDArray<SkPoint>& poly) { 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 @@ bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize } // 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 @@ bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize 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 @@ bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize 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 1d5a19c176..a0555ab51e 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 @@ bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize 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 0000000000..50f680ef23 --- /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); + + + +} |