From e5f5bf5175e426ebb6aa234f4387831c898f20ad Mon Sep 17 00:00:00 2001 From: Jim Van Verth Date: Fri, 24 Mar 2017 09:40:51 -0400 Subject: [PATCH] Create new inset algorithm for spot shadows BUG=skia: Change-Id: If7c67c2a5b9beea28f86d13362a5156b46394d0e Reviewed-on: https://skia-review.googlesource.com/9875 Commit-Queue: Ravi Mistry Reviewed-by: Brian Salomon Reviewed-by: Robert Phillips --- gm/convex_all_line_paths.cpp | 436 +++++++++++++++++++++++++----------- gm/shadowutils.cpp | 3 +- gn/tests.gni | 1 + gn/utils.gni | 2 + samplecode/SampleAndroidShadows.cpp | 12 +- src/utils/SkInsetConvexPolygon.cpp | 233 +++++++++++++++++++ src/utils/SkInsetConvexPolygon.h | 27 +++ src/utils/SkShadowTessellator.cpp | 379 +++++++++++++++++-------------- tests/InsetConvexPolyTest.cpp | 132 +++++++++++ 9 files changed, 919 insertions(+), 306 deletions(-) create mode 100755 src/utils/SkInsetConvexPolygon.cpp create mode 100755 src/utils/SkInsetConvexPolygon.h create mode 100644 tests/InsetConvexPolyTest.cpp diff --git a/gm/convex_all_line_paths.cpp b/gm/convex_all_line_paths.cpp index 62e8835..a4bc6a6 100644 --- a/gm/convex_all_line_paths.cpp +++ b/gm/convex_all_line_paths.cpp @@ -6,6 +6,7 @@ */ #include "gm.h" +#include "SkInsetConvexPolygon.h" #include "SkPathPriv.h" static void create_ngon(int n, SkPoint* pts, SkScalar width, SkScalar height) { @@ -22,6 +23,135 @@ static void create_ngon(int n, SkPoint* pts, SkScalar width, SkScalar height) { } } +namespace ConvexLineOnlyData { +// 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 } +}; +// Triangle in which the first point should fuse with last +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 }, +}; + +const SkPoint* gPoints[] = { + gPoints0, gPoints1, gPoints2, gPoints3, gPoints4, gPoints5, gPoints6, + gPoints7, gPoints8, gPoints9, gPoints10, +}; + +const size_t gSizes[] = { + 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(gSizes) == SK_ARRAY_COUNT(gPoints), "array_mismatch"); +} + namespace skiagm { // This GM is intended to exercise Ganesh's handling of convex line-only @@ -42,146 +172,19 @@ protected: SkISize onISize() override { return SkISize::Make(kGMWidth, kGMHeight); } bool runAsBench() const override { return true; } - static SkPath GetPath(int index, int offset, SkPath::Direction dir) { - // 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 } - }; - // Triangle in which the first point should fuse with last - 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 }, - }; - - const SkPoint* gPoints[] = { - gPoints0, gPoints1, gPoints2, gPoints3, gPoints4, gPoints5, gPoints6, - gPoints7, gPoints8, gPoints9, gPoints10, - }; - - const size_t gSizes[] = { - 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(gSizes) == SK_ARRAY_COUNT(gPoints), "array_mismatch"); - + static SkPath GetPath(int index, SkPath::Direction dir) { std::unique_ptr data(nullptr); const SkPoint* points; int numPts; - if (index < (int) SK_ARRAY_COUNT(gPoints)) { + if (index < (int) SK_ARRAY_COUNT(ConvexLineOnlyData::gPoints)) { // manually specified - points = gPoints[index]; - numPts = (int) gSizes[index]; + points = ConvexLineOnlyData::gPoints[index]; + numPts = (int)ConvexLineOnlyData::gSizes[index]; } else { // procedurally generated SkScalar width = kMaxPathHeight/2; SkScalar height = kMaxPathHeight/2; - switch (index-SK_ARRAY_COUNT(gPoints)) { + switch (index-SK_ARRAY_COUNT(ConvexLineOnlyData::gPoints)) { case 0: numPts = 3; break; @@ -259,7 +262,7 @@ protected: SkPoint center; { - SkPath path = GetPath(index, 0, SkPath::kCW_Direction); + SkPath path = GetPath(index, SkPath::kCW_Direction); if (offset->fX+path.getBounds().width() > kGMWidth) { offset->fX = 0; offset->fY += kMaxPathHeight; @@ -286,7 +289,7 @@ protected: paint.setAntiAlias(true); for (size_t i = 0; i < SK_ARRAY_COUNT(scales); ++i) { - SkPath path = GetPath(index, (int) i, dirs[i%2]); + SkPath path = GetPath(index, dirs[i%2]); if (fDoStrokeAndFill) { paint.setStyle(SkPaint::kStrokeAndFill_Style); paint.setStrokeJoin(joins[i%3]); @@ -347,8 +350,173 @@ 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* 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 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 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 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/shadowutils.cpp b/gm/shadowutils.cpp index 350a546..53d9b78 100644 --- a/gm/shadowutils.cpp +++ b/gm/shadowutils.cpp @@ -19,7 +19,7 @@ void draw_shadow(SkCanvas* canvas, const SkPath& path, int height, SkColor color color, flags, cache); } -static constexpr int kW = 700; +static constexpr int kW = 800; static constexpr int kH = 800; DEF_SIMPLE_GM(shadow_utils, canvas, kW, kH) { @@ -38,6 +38,7 @@ DEF_SIMPLE_GM(shadow_utils, canvas, kW, kH) { paths.push_back().addRect(SkRect::MakeWH(50, 50)); paths.push_back().addCircle(25, 25, 25); paths.push_back().cubicTo(100, 50, 20, 100, 0, 0); + paths.push_back().addOval(SkRect::MakeWH(20, 60)); static constexpr SkScalar kPad = 15.f; static constexpr SkPoint3 kLightPos = {250, 400, 500}; diff --git a/gn/tests.gni b/gn/tests.gni index 124be39..4435112 100644 --- a/gn/tests.gni +++ b/gn/tests.gni @@ -112,6 +112,7 @@ tests_sources = [ "$_tests/ImageTest.cpp", "$_tests/IndexedPngOverflowTest.cpp", "$_tests/InfRectTest.cpp", + "$_tests/InsetConvexPolyTest.cpp", "$_tests/InterpolatorTest.cpp", "$_tests/IntTextureTest.cpp", "$_tests/InvalidIndexedPngTest.cpp", diff --git a/gn/utils.gni b/gn/utils.gni index 807ae58..bb0bd94 100644 --- a/gn/utils.gni +++ b/gn/utils.gni @@ -42,6 +42,8 @@ skia_utils_sources = [ "$_src/utils/SkDumpCanvas.cpp", "$_src/utils/SkEventTracer.cpp", "$_src/utils/SkFloatUtils.h", + "$_src/utils/SkInsetConvexPolygon.cpp", + "$_src/utils/SkInsetConvexPolygon.h", "$_src/utils/SkInterpolator.cpp", "$_src/utils/SkMatrix22.cpp", "$_src/utils/SkMatrix22.h", diff --git a/samplecode/SampleAndroidShadows.cpp b/samplecode/SampleAndroidShadows.cpp index fa9cb50..271004e 100644 --- a/samplecode/SampleAndroidShadows.cpp +++ b/samplecode/SampleAndroidShadows.cpp @@ -500,8 +500,8 @@ protected: paint.setColor(SK_ColorCYAN); canvas->translate(250, 0); lightPos.fX += 250; - this->drawShadowedPath(canvas, fCubicPath, 16, paint, kAmbientAlpha, - lightPos, kLightWidth, kSpotAlpha); + this->drawShadowedPath(canvas, fCubicPath, SkTMax(1.0f, 16 + fZDelta), paint, + kAmbientAlpha, lightPos, kLightWidth, kSpotAlpha); // circular reveal SkPath tmpPath; @@ -513,7 +513,7 @@ protected: canvas->translate(-125, 60); lightPos.fX -= 125; lightPos.fY += 60; - this->drawShadowedPath(canvas, tmpPath, 32, paint, .1f, + this->drawShadowedPath(canvas, tmpPath, SkTMax(1.0f, 32 + fZDelta), paint, .1f, lightPos, kLightWidth, .5f); // perspective paths @@ -532,7 +532,7 @@ protected: lightPos = fLightPos; lightPos.fX += pivot.fX + translate.fX; lightPos.fY += pivot.fY + translate.fY; - this->drawShadowedPath(canvas, fWideRectPath, 16, paint, .1f, + this->drawShadowedPath(canvas, fWideRectPath, SkTMax(1.0f, 16 + fZDelta), paint, .1f, lightPos, kLightWidth, .5f); pivot = SkPoint::Make(fWideOvalPath.getBounds().width() / 2, @@ -547,12 +547,12 @@ protected: lightPos = fLightPos; lightPos.fX += pivot.fX + translate.fX; lightPos.fY += pivot.fY + translate.fY; - this->drawShadowedPath(canvas, fWideOvalPath, 32, paint, .1f, + this->drawShadowedPath(canvas, fWideOvalPath, SkTMax(1.0f, 32 + fZDelta), paint, .1f, lightPos, kLightWidth, .5f); } bool onAnimate(const SkAnimTimer& timer) override { - fAnimTranslate = timer.pingPong(10, 0, 200, -200); + fAnimTranslate = timer.pingPong(30, 0, 200, -200); return true; } diff --git a/src/utils/SkInsetConvexPolygon.cpp b/src/utils/SkInsetConvexPolygon.cpp new file mode 100755 index 0000000..8df7f0e --- /dev/null +++ b/src/utils/SkInsetConvexPolygon.cpp @@ -0,0 +1,233 @@ +/* + * 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 "SkInsetConvexPolygon.h" + +#include "SkTemplates.h" + +struct InsetSegment { + SkPoint fP0; + SkPoint fP1; +}; + +// Computes perpDot for point compared to segment. +// A positive value means the point is to the left of the segment, +// negative is to the right, 0 is collinear. +static int compute_side(const SkPoint& s0, const SkPoint& s1, const SkPoint& p) { + SkVector v0 = s1 - s0; + SkVector v1 = p - s0; + SkScalar perpDot = v0.cross(v1); + if (!SkScalarNearlyZero(perpDot)) { + return ((perpDot > 0) ? 1 : -1); + } + + return 0; +} + +// returns 1 for ccw, -1 for cw and 0 if degenerate +static int get_winding(const SkPoint* polygonVerts, int polygonSize) { + SkPoint p0 = polygonVerts[0]; + SkPoint p1 = polygonVerts[1]; + + for (int i = 2; i < polygonSize; ++i) { + SkPoint p2 = polygonVerts[i]; + + // determine if cw or ccw + int side = compute_side(p0, p1, p2); + if (0 != side) { + return ((side > 0) ? 1 : -1); + } + + // if nearly collinear, treat as straight line and continue + p1 = p2; + } + + return 0; +} + +// Perpendicularly offset line segment p0-p1 'distance' units in the direction specified by 'dir' +static void inset_edge(const SkPoint& p0, const SkPoint& p1, SkScalar distance, int dir, + InsetSegment* inset) { + SkASSERT(dir == -1 || dir == 1); + // compute perpendicular + SkVector perp; + perp.fX = p0.fY - p1.fY; + perp.fY = p1.fX - p0.fX; + perp.setLength(distance*dir); + inset->fP0 = p0 + perp; + inset->fP1 = p1 + perp; +} + +// 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, + SkPoint* p, SkScalar* s, SkScalar* t) { + 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 (s0.fP1.equalsWithinTolerance(s1.fP0)) { + *p = s0.fP1; + *s = SK_Scalar1; + *t = 0; + return true; + } + if (s1.fP1.equalsWithinTolerance(s0.fP0)) { + *p = s1.fP1; + *s = 0; + *t = SK_Scalar1; + return true; + } + + 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; + } + + v0 *= localS; + *p = s0.fP0 + v0; + *s = localS; + *t = localT; + + return 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 +// parameter to reverse this). We detect this by checking whether the second intersection +// on an edge is closer to its tail than the first one. +// +// We might also have the case that there is no intersection between two neighboring inset edges. +// In this case, one edge will lie to the right of the other and should be discarded along with +// its previous intersection (if any). +// +// Note: the assumption is that inputPolygon is convex and has no coincident points. +// +bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize, + SkScalar insetDistance, SkTDArray* insetPolygon) { + if (inputPolygonSize < 3) { + return false; + } + + int winding = get_winding(inputPolygonVerts, inputPolygonSize); + if (0 == winding) { + return false; + } + + // set up + struct EdgeData { + InsetSegment fInset; + SkPoint fIntersection; + SkScalar fTValue; + bool fValid; + }; + + SkAutoSTMalloc<64, EdgeData> edgeData(inputPolygonSize); + for (int i = 0; i < inputPolygonSize; ++i) { + edgeData[i].fValid = true; + int j = (i + 1) % inputPolygonSize; + inset_edge(inputPolygonVerts[i], inputPolygonVerts[j], insetDistance, winding, + &edgeData[i].fInset); + edgeData[i].fTValue = SK_ScalarMin; + } + + int prevIndex = inputPolygonSize - 1; + int currIndex = 0; + int insetVertexCount = inputPolygonSize; + while (prevIndex != currIndex) { + if (!edgeData[prevIndex].fValid) { + prevIndex = (prevIndex + inputPolygonSize - 1) % inputPolygonSize; + 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 + inputPolygonSize - 1) % inputPolygonSize; + // we've already considered this intersection, we're done + } else if (edgeData[currIndex].fTValue > SK_ScalarMin && + intersection.equalsWithinTolerance(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) % inputPolygonSize; + } + } else { + // if prev to right side of curr + int side = winding*compute_side(edgeData[currIndex].fInset.fP0, + edgeData[currIndex].fInset.fP1, + edgeData[prevIndex].fInset.fP1); + if (side < 0 && side == winding*compute_side(edgeData[currIndex].fInset.fP0, + edgeData[currIndex].fInset.fP1, + edgeData[prevIndex].fInset.fP0)) { + // no point in considering this one again + edgeData[prevIndex].fValid = false; + --insetVertexCount; + // go back one segment + prevIndex = (prevIndex + inputPolygonSize - 1) % inputPolygonSize; + } else { + // move to next segment + edgeData[currIndex].fValid = false; + --insetVertexCount; + currIndex = (currIndex + 1) % inputPolygonSize; + } + } + } + + // store all the valid intersections + insetPolygon->reset(); + insetPolygon->setReserve(insetVertexCount); + for (int i = 0; i < inputPolygonSize; ++i) { + if (edgeData[i].fValid) { + *insetPolygon->push() = edgeData[i].fIntersection; + } + } + +#ifdef SK_DEBUG + bool convex = true; + for (int i = 0; i < insetPolygon->count(); ++i) { + int j = (i + 1) % insetPolygon->count(); + int k = (i + 2) % insetPolygon->count(); + + int side = winding*compute_side((*insetPolygon)[i], (*insetPolygon)[j], + (*insetPolygon)[k]); + if (side < 0) { + convex = false; + break; + } + } + SkASSERT(convex); +#endif + + return (insetPolygon->count() >= 3); +} diff --git a/src/utils/SkInsetConvexPolygon.h b/src/utils/SkInsetConvexPolygon.h new file mode 100755 index 0000000..3ab7558 --- /dev/null +++ b/src/utils/SkInsetConvexPolygon.h @@ -0,0 +1,27 @@ +/* + * Copyright 2017 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +#ifndef SkInsetConvexPolygon_DEFINED +#define SkInsetConvexPolygon_DEFINED + +#include "SkTDArray.h" +#include "SkPoint.h" + + /** + * Generates a polygon that is inset a given distance from the boundary of a given convex polygon. + * + * @param inputPolygonVerts Array of points representing the vertices of the original polygon. + * It should be convex and have no coincident points. + * @param inputPolygonSize Number of vertices in the original polygon. + * @param insetDistance How far we wish to inset the polygon. This should be a positive value. + * @param insetPolygon The resulting inset polygon, if any. + * @return true if an inset polygon exists, false otherwise. + */ +bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize, + SkScalar insetDistance, SkTDArray* insetPolygon); + +#endif diff --git a/src/utils/SkShadowTessellator.cpp b/src/utils/SkShadowTessellator.cpp index ed9e62a..ef8ce32 100644 --- a/src/utils/SkShadowTessellator.cpp +++ b/src/utils/SkShadowTessellator.cpp @@ -8,6 +8,7 @@ #include "SkShadowTessellator.h" #include "SkColorPriv.h" #include "SkGeometry.h" +#include "SkInsetConvexPolygon.h" #include "SkPath.h" #include "SkVertices.h" @@ -439,22 +440,28 @@ public: bool transparent); private: - void computeClipBounds(const SkPath& path, const SkMatrix& ctm, SkPath* devPath); - void checkUmbraAndTransformCentroid(SkScalar scale, const SkVector& xlate, - bool useDistanceToPoint); + void computeClipAndPathPolygons(const SkPath& path, const SkMatrix& ctm, + SkScalar scale, const SkVector& xlate); + void computeClipVectorsAndTestCentroid(); bool clipUmbraPoint(const SkPoint& umbraPoint, const SkPoint& centroid, SkPoint* clipPoint); + int getClosestUmbraPoint(const SkPoint& point); void handleLine(const SkPoint& p) override; + void handlePolyPoint(const SkPoint& p); void mapPoints(SkScalar scale, const SkVector& xlate, SkPoint* pts, int count); - void addInnerPoint(const SkPoint& pathPoint); + bool addInnerPoint(const SkPoint& pathPoint); void addEdge(const SkVector& nextPoint, const SkVector& nextNormal) override; SkTDArray fClipPolygon; SkTDArray fClipVectors; SkPoint fCentroid; + SkScalar fArea; - int fCurrPolyPoint; + SkTDArray fPathPolygon; + SkTDArray fUmbraPolygon; + int fCurrClipPoint; + int fCurrUmbraPoint; bool fPrevUmbraOutside; bool fFirstUmbraOutside; bool fValidUmbra; @@ -467,11 +474,11 @@ SkSpotShadowTessellator::SkSpotShadowTessellator(const SkPath& path, const SkMat SkScalar radius, SkColor umbraColor, SkColor penumbraColor, bool transparent) : INHERITED(radius, umbraColor, penumbraColor, transparent) - , fCurrPolyPoint(0) + , fCurrClipPoint(0) , fPrevUmbraOutside(false) , fFirstUmbraOutside(false) , fValidUmbra(true) { - // TODO: calculate these better + // TODO: calculate these reserves better // Penumbra ring: 3*numPts // Umbra ring: numPts // Inner ring: numPts @@ -480,61 +487,65 @@ SkSpotShadowTessellator::SkSpotShadowTessellator(const SkPath& path, const SkMat // Penumbra ring: 12*numPts // Umbra ring: 3*numPts fIndices.setReserve(15 * path.countPoints()); - fClipPolygon.setReserve(path.countPoints()); - // compute rough clip bounds for umbra, plus centroid - SkPath devPath; - this->computeClipBounds(path, ctm, &devPath); - if (fClipPolygon.count() < 3) { + + // compute rough clip bounds for umbra, plus offset polygon, plus centroid + this->computeClipAndPathPolygons(path, ctm, scale, translate); + if (fClipPolygon.count() < 3 || fPathPolygon.count() < 3) { return; } - // We are going to apply 'scale' and 'xlate' (in that order) to each computed path point. We - // want the effect to be to scale the points relative to the path centroid and then translate - // them by the 'translate' param we were passed. - SkVector xlate = fCentroid * (1.f - scale) + translate; - // check to see if we have a valid umbra at all - bool usePointCheck = path.isRRect(nullptr) || path.isRect(nullptr) || path.isOval(nullptr); - this->checkUmbraAndTransformCentroid(scale, translate, usePointCheck); + // check to see if umbra collapses + SkScalar minDistSq = fCentroid.distanceToLineSegmentBetweenSqd(fPathPolygon[0], + fPathPolygon[1]); + for (int i = 1; i < fPathPolygon.count(); ++i) { + int j = i + 1; + if (i == fPathPolygon.count() - 1) { + j = 0; + } + SkPoint currPoint = fPathPolygon[i]; + SkPoint nextPoint = fPathPolygon[j]; + SkScalar distSq = fCentroid.distanceToLineSegmentBetweenSqd(currPoint, nextPoint); + if (distSq < minDistSq) { + minDistSq = distSq; + } + } + static constexpr auto kTolerance = 1.0e-2f; + if (minDistSq < (radius + kTolerance)*(radius + kTolerance)) { + // if the umbra would collapse, we back off a bit on inner blur and adjust the alpha + SkScalar newRadius = SkScalarSqrt(minDistSq) - kTolerance; + SkScalar ratio = 256 * newRadius / radius; + // they aren't PMColors, but the interpolation algorithm is the same + fUmbraColor = SkPMLerp(fUmbraColor, fPenumbraColor, (unsigned)ratio); + radius = newRadius; + } - // walk around the path, tessellate and generate inner and outer rings - SkPath::Iter iter(devPath, true); - SkPoint pts[4]; - SkPath::Verb verb; + // compute vectors for clip tests + this->computeClipVectorsAndTestCentroid(); + + // generate inner ring + if (!SkInsetConvexPolygon(&fPathPolygon[0], fPathPolygon.count(), radius, &fUmbraPolygon)) { + // this shouldn't happen, but just in case we'll inset using the centroid + fValidUmbra = false; + } + + // walk around the path polygon, generate outer ring and connect to inner ring if (fTransparent) { *fPositions.push() = fCentroid; *fColors.push() = fUmbraColor; } - SkMatrix shadowTransform; - shadowTransform.setScaleTranslate(scale, scale, xlate.fX, xlate.fY); - while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { - switch (verb) { - case SkPath::kLine_Verb: - this->INHERITED::handleLine(shadowTransform, &pts[1]); - break; - case SkPath::kQuad_Verb: - this->handleQuad(shadowTransform, pts); - break; - case SkPath::kCubic_Verb: - this->handleCubic(shadowTransform, pts); - break; - case SkPath::kConic_Verb: - this->handleConic(shadowTransform, pts, iter.conicWeight()); - break; - case SkPath::kMove_Verb: - case SkPath::kClose_Verb: - case SkPath::kDone_Verb: - break; - } + fCurrUmbraPoint = 0; + for (int i = 0; i < fPathPolygon.count(); ++i) { + this->handlePolyPoint(fPathPolygon[i]); } if (!this->indexCount()) { return; } + // finish up the final verts SkVector normal; - if (compute_normal(fPrevPoint, fFirstPoint, fRadius, fDirection, - &normal)) { + if (compute_normal(fPrevPoint, fFirstPoint, fRadius, fDirection, &normal)) { this->addArc(normal); // close out previous arc @@ -600,175 +611,138 @@ SkSpotShadowTessellator::SkSpotShadowTessellator(const SkPath& path, const SkMat fSucceeded = true; } -void SkSpotShadowTessellator::computeClipBounds(const SkPath& path, const SkMatrix& ctm, - SkPath* devPath) { - // walk around the path and compute clip polygon - // if original path is transparent, will accumulate sum of points for centroid - // for Bezier curves, we compute additional interior points on curve +void SkSpotShadowTessellator::computeClipAndPathPolygons(const SkPath& path, const SkMatrix& ctm, + SkScalar scale, const SkVector& xlate) { + // For the path polygon we are going to apply 'scale' and 'xlate' (in that order) to each + // computed path point. We want the effect to be to scale the points relative to the path + // bounds center and then translate them by the 'xlate' param we were passed. + SkPoint center = SkPoint::Make(path.getBounds().centerX(), path.getBounds().centerY()); + ctm.mapPoints(¢er, 1); + SkVector translate = center * (1.f - scale) + xlate; + SkMatrix shadowTransform; + shadowTransform.setScaleTranslate(scale, scale, translate.fX, translate.fY); + + fPathPolygon.setReserve(path.countPoints()); + + // Walk around the path and compute clip polygon and path polygon. + // Will also accumulate sum of areas for centroid. + // For Bezier curves, we compute additional interior points on curve. SkPath::Iter iter(path, true); SkPoint pts[4]; SkPath::Verb verb; - fCentroid = SkPoint::Make(0, 0); - int centroidCount = 0; fClipPolygon.reset(); + // init centroid + fCentroid = SkPoint::Make(0, 0); + fArea = 0; + // coefficients to compute cubic Bezier at t = 5/16 - const SkScalar kA = 0.32495117187f; - const SkScalar kB = 0.44311523437f; - const SkScalar kC = 0.20141601562f; - const SkScalar kD = 0.03051757812f; + static constexpr SkScalar kA = 0.32495117187f; + static constexpr SkScalar kB = 0.44311523437f; + static constexpr SkScalar kC = 0.20141601562f; + static constexpr SkScalar kD = 0.03051757812f; SkPoint curvePoint; SkScalar w; while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { switch (verb) { - case SkPath::kMove_Verb: - ctm.mapPoints(&pts[0], 1); - devPath->moveTo(pts[0]); - break; case SkPath::kLine_Verb: ctm.mapPoints(&pts[1], 1); - devPath->lineTo(pts[1]); - fCentroid += pts[1]; - centroidCount++; *fClipPolygon.push() = pts[1]; + this->INHERITED::handleLine(shadowTransform, &pts[1]); break; case SkPath::kQuad_Verb: ctm.mapPoints(pts, 3); - devPath->quadTo(pts[1], pts[2]); // point at t = 1/2 curvePoint.fX = 0.25f*pts[0].fX + 0.5f*pts[1].fX + 0.25f*pts[2].fX; curvePoint.fY = 0.25f*pts[0].fY + 0.5f*pts[1].fY + 0.25f*pts[2].fY; *fClipPolygon.push() = curvePoint; - fCentroid += curvePoint; *fClipPolygon.push() = pts[2]; - fCentroid += pts[2]; - centroidCount += 2; + this->handleQuad(shadowTransform, pts); break; case SkPath::kConic_Verb: ctm.mapPoints(pts, 3); w = iter.conicWeight(); - devPath->conicTo(pts[1], pts[2], w); // point at t = 1/2 curvePoint.fX = 0.25f*pts[0].fX + w*0.5f*pts[1].fX + 0.25f*pts[2].fX; curvePoint.fY = 0.25f*pts[0].fY + w*0.5f*pts[1].fY + 0.25f*pts[2].fY; curvePoint *= SkScalarInvert(0.5f + 0.5f*w); *fClipPolygon.push() = curvePoint; - fCentroid += curvePoint; *fClipPolygon.push() = pts[2]; - fCentroid += pts[2]; - centroidCount += 2; + this->handleConic(shadowTransform, pts, w); break; case SkPath::kCubic_Verb: ctm.mapPoints(pts, 4); - devPath->cubicTo(pts[1], pts[2], pts[3]); // point at t = 5/16 curvePoint.fX = kA*pts[0].fX + kB*pts[1].fX + kC*pts[2].fX + kD*pts[3].fX; curvePoint.fY = kA*pts[0].fY + kB*pts[1].fY + kC*pts[2].fY + kD*pts[3].fY; *fClipPolygon.push() = curvePoint; - fCentroid += curvePoint; // point at t = 11/16 curvePoint.fX = kD*pts[0].fX + kC*pts[1].fX + kB*pts[2].fX + kA*pts[3].fX; curvePoint.fY = kD*pts[0].fY + kC*pts[1].fY + kB*pts[2].fY + kA*pts[3].fY; *fClipPolygon.push() = curvePoint; - fCentroid += curvePoint; *fClipPolygon.push() = pts[3]; - fCentroid += pts[3]; - centroidCount += 3; + this->handleCubic(shadowTransform, pts); break; + case SkPath::kMove_Verb: case SkPath::kClose_Verb: - devPath->close(); + case SkPath::kDone_Verb: break; default: SkDEBUGFAIL("unknown verb"); } } - fCentroid *= SkScalarInvert(centroidCount); - fCurrPolyPoint = fClipPolygon.count() - 1; + // finish centroid + if (fPathPolygon.count() > 0) { + SkPoint currPoint = fPathPolygon[fPathPolygon.count() - 1]; + SkPoint nextPoint = fPathPolygon[0]; + SkScalar quadArea = currPoint.cross(nextPoint); + fCentroid.fX += (currPoint.fX + nextPoint.fX) * quadArea; + fCentroid.fY += (currPoint.fY + nextPoint.fY) * quadArea; + fArea += quadArea; + fCentroid *= SK_Scalar1 / (3 * fArea); + } + + fCurrClipPoint = fClipPolygon.count() - 1; } -void SkSpotShadowTessellator::checkUmbraAndTransformCentroid(SkScalar scale, - const SkVector& xlate, - bool useDistanceToPoint) { +void SkSpotShadowTessellator::computeClipVectorsAndTestCentroid() { SkASSERT(fClipPolygon.count() >= 3); - SkPoint transformedCentroid = fCentroid; - transformedCentroid += xlate; - SkScalar localRadius = fRadius / scale; - localRadius *= localRadius; - - // init umbra check - SkVector w = fCentroid - fClipPolygon[0]; + // init clip vectors SkVector v0 = fClipPolygon[1] - fClipPolygon[0]; *fClipVectors.push() = v0; - bool validUmbra; - SkScalar minDistance; - // check distance against line segment - if (useDistanceToPoint) { - minDistance = w.lengthSqd(); - } else { - SkScalar vSq = v0.dot(v0); - SkScalar wDotV = w.dot(v0); - minDistance = w.dot(w) - wDotV*wDotV/vSq; - } - validUmbra = (minDistance >= localRadius); // init centroid check bool hiddenCentroid = true; - SkVector v1 = transformedCentroid - fClipPolygon[0]; + SkVector v1 = fCentroid - fClipPolygon[0]; SkScalar initCross = v0.cross(v1); for (int p = 1; p < fClipPolygon.count(); ++p) { - // Determine whether we have a real umbra by insetting clipPolygon by radius/scale - // and see if it extends past centroid. - // TODO: adjust this later for more accurate umbra calcs - w = fCentroid - fClipPolygon[p]; + // add to clip vectors v0 = fClipPolygon[(p + 1) % fClipPolygon.count()] - fClipPolygon[p]; *fClipVectors.push() = v0; - // check distance against line segment - SkScalar distance; - if (useDistanceToPoint) { - distance = w.lengthSqd(); - } else { - SkScalar vSq = v0.dot(v0); - SkScalar wDotV = w.dot(v0); - distance = w.dot(w) - wDotV*wDotV/vSq; - } - if (distance < localRadius) { - validUmbra = false; - } - if (distance < minDistance) { - minDistance = distance; - } // Determine if transformed centroid is inside clipPolygon. - v1 = transformedCentroid - fClipPolygon[p]; + v1 = fCentroid - fClipPolygon[p]; if (initCross*v0.cross(v1) <= 0) { hiddenCentroid = false; } } SkASSERT(fClipVectors.count() == fClipPolygon.count()); - if (!validUmbra) { - SkScalar ratio = 256 * SkScalarSqrt(minDistance / localRadius); - // they aren't PMColors, but the interpolation algorithm is the same - fUmbraColor = SkPMLerp(fUmbraColor, fPenumbraColor, (unsigned)ratio); - } - - fTransparent = fTransparent || !hiddenCentroid || !validUmbra; - fValidUmbra = validUmbra; - fCentroid = transformedCentroid; + fTransparent = fTransparent || !hiddenCentroid; } bool SkSpotShadowTessellator::clipUmbraPoint(const SkPoint& umbraPoint, const SkPoint& centroid, SkPoint* clipPoint) { SkVector segmentVector = centroid - umbraPoint; - int startPolyPoint = fCurrPolyPoint; + int startClipPoint = fCurrClipPoint; do { - SkVector dp = umbraPoint - fClipPolygon[fCurrPolyPoint]; - SkScalar denom = fClipVectors[fCurrPolyPoint].cross(segmentVector); + SkVector dp = umbraPoint - fClipPolygon[fCurrClipPoint]; + SkScalar denom = fClipVectors[fCurrClipPoint].cross(segmentVector); SkScalar t_num = dp.cross(segmentVector); // if line segments are nearly parallel if (SkScalarNearlyZero(denom)) { @@ -779,7 +753,7 @@ bool SkSpotShadowTessellator::clipUmbraPoint(const SkPoint& umbraPoint, const Sk // otherwise are separate, will try the next poly segment // else if crossing lies within poly segment } else if (t_num >= 0 && t_num <= denom) { - SkScalar s_num = dp.cross(fClipVectors[fCurrPolyPoint]); + SkScalar s_num = dp.cross(fClipVectors[fCurrClipPoint]); // if umbra point is inside the clip polygon if (s_num < 0) { return false; @@ -789,12 +763,41 @@ bool SkSpotShadowTessellator::clipUmbraPoint(const SkPoint& umbraPoint, const Sk return true; } } - fCurrPolyPoint = (fCurrPolyPoint + 1) % fClipPolygon.count(); - } while (fCurrPolyPoint != startPolyPoint); + fCurrClipPoint = (fCurrClipPoint + 1) % fClipPolygon.count(); + } while (fCurrClipPoint != startClipPoint); return false; } +int SkSpotShadowTessellator::getClosestUmbraPoint(const SkPoint& p) { + SkScalar minDistance = p.distanceToSqd(fUmbraPolygon[fCurrUmbraPoint]); + int index = fCurrUmbraPoint; + int dir = 1; + int next = (index + dir) % fUmbraPolygon.count(); + + // init travel direction + SkScalar distance = p.distanceToSqd(fUmbraPolygon[next]); + if (distance < minDistance) { + index = next; + minDistance = distance; + } else { + dir = fUmbraPolygon.count()-1; + } + + // iterate until we find a point that increases the distance + next = (index + dir) % fUmbraPolygon.count(); + distance = p.distanceToSqd(fUmbraPolygon[next]); + while (distance < minDistance) { + index = next; + minDistance = distance; + next = (index + dir) % fUmbraPolygon.count(); + distance = p.distanceToSqd(fUmbraPolygon[next]); + } + + fCurrUmbraPoint = index; + return index; +} + void SkSpotShadowTessellator::mapPoints(SkScalar scale, const SkVector& xlate, SkPoint* pts, int count) { // TODO: vectorize @@ -804,7 +807,44 @@ void SkSpotShadowTessellator::mapPoints(SkScalar scale, const SkVector& xlate, } } +static bool duplicate_pt(const SkPoint& p0, const SkPoint& p1) { + static constexpr SkScalar kClose = (SK_Scalar1 / 16); + static constexpr SkScalar kCloseSqd = kClose*kClose; + + SkScalar distSq = p0.distanceToSqd(p1); + return distSq < kCloseSqd; +} + +static bool is_collinear(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) { + SkVector v0 = p1 - p0; + SkVector v1 = p2 - p0; + return (SkScalarNearlyZero(v0.cross(v1))); +} + void SkSpotShadowTessellator::handleLine(const SkPoint& p) { + // remove coincident points and add to centroid + if (fPathPolygon.count() > 0) { + const SkPoint& lastPoint = fPathPolygon[fPathPolygon.count() - 1]; + if (duplicate_pt(p, lastPoint)) { + return; + } + SkScalar quadArea = lastPoint.cross(p); + fCentroid.fX += (p.fX + lastPoint.fX) * quadArea; + fCentroid.fY += (p.fY + lastPoint.fY) * quadArea; + fArea += quadArea; + } + + // try to remove collinear points + if (fPathPolygon.count() > 1 && is_collinear(fPathPolygon[fPathPolygon.count()-2], + fPathPolygon[fPathPolygon.count()-1], + p)) { + fPathPolygon[fPathPolygon.count() - 1] = p; + } else { + *fPathPolygon.push() = p; + } +} + +void SkSpotShadowTessellator::handlePolyPoint(const SkPoint& p) { if (fInitPoints.count() < 2) { *fInitPoints.push() = p; return; @@ -814,7 +854,7 @@ void SkSpotShadowTessellator::handleLine(const SkPoint& p) { // determine if cw or ccw SkVector v0 = fInitPoints[1] - fInitPoints[0]; SkVector v1 = p - fInitPoints[0]; - SkScalar perpDot = v0.fX*v1.fY - v0.fY*v1.fX; + SkScalar perpDot = v0.cross(v1); if (SkScalarNearlyZero(perpDot)) { // nearly parallel, just treat as straight line and continue fInitPoints[1] = p; @@ -867,40 +907,47 @@ void SkSpotShadowTessellator::handleLine(const SkPoint& p) { } } -void SkSpotShadowTessellator::addInnerPoint(const SkPoint& pathPoint) { - SkVector v = fCentroid - pathPoint; - SkScalar distance = v.length(); - SkScalar t; - if (fValidUmbra) { - SkASSERT(distance >= fRadius); - t = fRadius / distance; +bool SkSpotShadowTessellator::addInnerPoint(const SkPoint& pathPoint) { + SkPoint umbraPoint; + if (!fValidUmbra) { + SkVector v = fCentroid - pathPoint; + v *= 0.95f; + umbraPoint = pathPoint + v; } else { - t = 0.95f; + umbraPoint = fUmbraPolygon[this->getClosestUmbraPoint(pathPoint)]; } - v *= t; - SkPoint umbraPoint = pathPoint + v; - *fPositions.push() = umbraPoint; - *fColors.push() = fUmbraColor; fPrevPoint = pathPoint; + + // merge "close" points + if (fPrevUmbraIndex == fFirstVertex || + !duplicate_pt(umbraPoint, fPositions[fPrevUmbraIndex])) { + *fPositions.push() = umbraPoint; + *fColors.push() = fUmbraColor; + + return false; + } else { + return true; + } } void SkSpotShadowTessellator::addEdge(const SkPoint& nextPoint, const SkVector& nextNormal) { // add next umbra point - this->addInnerPoint(nextPoint); - int prevPenumbraIndex = fPositions.count() - 2; - int currUmbraIndex = fPositions.count() - 1; + bool duplicate = this->addInnerPoint(nextPoint); + int prevPenumbraIndex = duplicate ? fPositions.count()-1 : fPositions.count()-2; + int currUmbraIndex = duplicate ? fPrevUmbraIndex : fPositions.count()-1; - // add to center fan if transparent or centroid showing - if (fTransparent) { - *fIndices.push() = 0; - *fIndices.push() = fPrevUmbraIndex; - *fIndices.push() = currUmbraIndex; - // otherwise add to clip ring - } else { - if (!fTransparent) { + if (!duplicate) { + // add to center fan if transparent or centroid showing + if (fTransparent) { + *fIndices.push() = 0; + *fIndices.push() = fPrevUmbraIndex; + *fIndices.push() = currUmbraIndex; + // otherwise add to clip ring + } else { SkPoint clipPoint; - bool isOutside = clipUmbraPoint(fPositions[currUmbraIndex], fCentroid, &clipPoint); + bool isOutside = this->clipUmbraPoint(fPositions[currUmbraIndex], fCentroid, + &clipPoint); if (isOutside) { *fPositions.push() = clipPoint; *fColors.push() = fUmbraColor; @@ -929,9 +976,11 @@ void SkSpotShadowTessellator::addEdge(const SkPoint& nextPoint, const SkVector& *fPositions.push() = newPoint; *fColors.push() = fPenumbraColor; - *fIndices.push() = fPrevUmbraIndex; - *fIndices.push() = prevPenumbraIndex; - *fIndices.push() = currUmbraIndex; + if (!duplicate) { + *fIndices.push() = fPrevUmbraIndex; + *fIndices.push() = prevPenumbraIndex; + *fIndices.push() = currUmbraIndex; + } *fIndices.push() = prevPenumbraIndex; *fIndices.push() = fPositions.count() - 1; diff --git a/tests/InsetConvexPolyTest.cpp b/tests/InsetConvexPolyTest.cpp new file mode 100644 index 0000000..e13a25a --- /dev/null +++ b/tests/InsetConvexPolyTest.cpp @@ -0,0 +1,132 @@ +/* + * 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 "SkInsetConvexPolygon.h" + +static bool is_convex(const SkTDArray& 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); + int side = winding*perpDot; + if (side < 0) { + return false; + } + } + + return true; +} + +DEF_TEST(InsetConvexPoly, reporter) { + SkTDArray rrectPoly; + + // 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 insetPoly; + bool result = SkInsetConvexPolygon(&rrectPoly[0], rrectPoly.count(), 3, &insetPoly); + REPORTER_ASSERT(reporter, result); + REPORTER_ASSERT(reporter, is_convex(insetPoly)); + + // inset to rect + result = SkInsetConvexPolygon(&rrectPoly[0], rrectPoly.count(), 10, &insetPoly); + REPORTER_ASSERT(reporter, result); + REPORTER_ASSERT(reporter, is_convex(insetPoly)); + REPORTER_ASSERT(reporter, insetPoly.count() == 4); + if (insetPoly.count() == 4) { + REPORTER_ASSERT(reporter, insetPoly[0].equals(-95, 45)); + REPORTER_ASSERT(reporter, insetPoly[1].equals(95, 45)); + REPORTER_ASSERT(reporter, insetPoly[2].equals(95, -45)); + REPORTER_ASSERT(reporter, insetPoly[3].equals(-95, -45)); + } + + // just to full inset + // for shadows having a flat poly here is fine + // may want to revisit for strokes + result = SkInsetConvexPolygon(&rrectPoly[0], rrectPoly.count(), 55, &insetPoly); + REPORTER_ASSERT(reporter, result); + REPORTER_ASSERT(reporter, is_convex(insetPoly)); + REPORTER_ASSERT(reporter, insetPoly.count() == 4); + if (insetPoly.count() == 4) { + REPORTER_ASSERT(reporter, insetPoly[0].equals(-50, 0)); + REPORTER_ASSERT(reporter, insetPoly[1].equals(50, 0)); + REPORTER_ASSERT(reporter, insetPoly[2].equals(50, 0)); + REPORTER_ASSERT(reporter, insetPoly[3].equals(-50, 0)); + } + + // past full inset + result = SkInsetConvexPolygon(&rrectPoly[0], rrectPoly.count(), 75, &insetPoly); + REPORTER_ASSERT(reporter, !result); + + // troublesome case + SkTDArray 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 = SkInsetConvexPolygon(&clippedRRectPoly[0], clippedRRectPoly.count(), 32.3699417f, + &insetPoly); + REPORTER_ASSERT(reporter, result); + REPORTER_ASSERT(reporter, is_convex(insetPoly)); +} -- 2.7.4