From 66560ca776773858abfffd59974eac32c942acc3 Mon Sep 17 00:00:00 2001 From: "caryclark@google.com" Date: Fri, 26 Apr 2013 19:51:16 +0000 Subject: [PATCH] path ops -- handle non-finite numbers Op() and Simplify() do nothing if the input is non-finite. Add code and tests. Review URL: https://codereview.chromium.org/14407006 git-svn-id: http://skia.googlecode.com/svn/trunk@8882 2bbb7eff-a529-9590-31e7-b0007b416f81 --- gyp/pathops_unittest.gypi | 1 + include/pathops/SkPathOps.h | 38 +++++++++++----- src/pathops/SkOpEdgeBuilder.cpp | 93 ++++++++++++++++++++++++------------- src/pathops/SkOpEdgeBuilder.h | 19 +++++--- src/pathops/SkPathOpsOp.cpp | 10 ++-- src/pathops/SkPathOpsSimplify.cpp | 16 ++++--- tests/PathOpsExtendedTest.cpp | 18 ++++++-- tests/PathOpsSimplifyFailTest.cpp | 96 +++++++++++++++++++++++++++++++++++++++ tests/PathOpsSimplifyTest.cpp | 45 ++++++++++++++++++ 9 files changed, 276 insertions(+), 60 deletions(-) create mode 100644 tests/PathOpsSimplifyFailTest.cpp diff --git a/gyp/pathops_unittest.gypi b/gyp/pathops_unittest.gypi index 21fb929..271edbf 100644 --- a/gyp/pathops_unittest.gypi +++ b/gyp/pathops_unittest.gypi @@ -28,6 +28,7 @@ '../tests/PathOpsQuadParameterizationTest.cpp', '../tests/PathOpsQuadReduceOrderTest.cpp', '../tests/PathOpsSimplifyDegenerateThreadedTest.cpp', + '../tests/PathOpsSimplifyFailTest.cpp', '../tests/PathOpsSimplifyQuadralateralsThreadedTest.cpp', '../tests/PathOpsSimplifyQuadThreadedTest.cpp', '../tests/PathOpsSimplifyRectThreadedTest.cpp', diff --git a/include/pathops/SkPathOps.h b/include/pathops/SkPathOps.h index 2851186..ba60274 100644 --- a/include/pathops/SkPathOps.h +++ b/include/pathops/SkPathOps.h @@ -21,19 +21,35 @@ enum SkPathOp { kReverseDifference_PathOp, //!< subtract the first path from the op path }; -/** - * Set this path to the result of applying the Op to this path and the - * specified path: this = (this op operand). The resulting path will be constructed - * from non-overlapping contours. The curve order is reduced where possible so that cubics may - * be turned into quadratics, and quadratics maybe turned into lines. +/** Set this path to the result of applying the Op to this path and the + specified path: this = (this op operand). + The resulting path will be constructed from non-overlapping contours. + The curve order is reduced where possible so that cubics may be turned + into quadratics, and quadratics maybe turned into lines. + + Returns true if operation was able to produce a result; + otherwise, result is unmodified. + + @param one The first operand (for difference, the minuend) + @param two The second operand (for difference, the subtrahend) + @param result The product of the operands. The result may be one of the + inputs. + @return True if operation succeeded. */ -void Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result); +bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result); -/** - * Set this path to a set of non-overlapping contours that describe the same - * area as the original path. The curve order is reduced where possible so that cubics may - * be turned into quadratics, and quadratics maybe turned into lines. +/** Set this path to a set of non-overlapping contours that describe the + same area as the original path. + The curve order is reduced where possible so that cubics may + be turned into quadratics, and quadratics maybe turned into lines. + + Returns true if operation was able to produce a result; + otherwise, result is unmodified. + + @param path The path to simplify. + @param result The simplified path. The result may be the input. + @return True if simplification succeeded. */ -void Simplify(const SkPath& path, SkPath* result); +bool Simplify(const SkPath& path, SkPath* result); #endif diff --git a/src/pathops/SkOpEdgeBuilder.cpp b/src/pathops/SkOpEdgeBuilder.cpp index d1d7af8..57e3b41 100644 --- a/src/pathops/SkOpEdgeBuilder.cpp +++ b/src/pathops/SkOpEdgeBuilder.cpp @@ -16,6 +16,7 @@ void SkOpEdgeBuilder::init() { gContourID = 0; gSegmentID = 0; #endif + fUnparseable = false; fSecondHalf = preFetch(); } @@ -28,8 +29,10 @@ void SkOpEdgeBuilder::addOperand(const SkPath& path) { preFetch(); } -void SkOpEdgeBuilder::finish() { - walk(); +bool SkOpEdgeBuilder::finish() { + if (fUnparseable || !walk()) { + return false; + } complete(); if (fCurrentContour && !fCurrentContour->segments().count()) { fContours.pop_back(); @@ -51,6 +54,7 @@ void SkOpEdgeBuilder::finish() { &fReducePts[rIndex]); } fExtra.reset(); // we're done with this + return true; } // Note that copying the points here avoids copying the resulting path later. @@ -59,6 +63,10 @@ void SkOpEdgeBuilder::finish() { // OPTIMIZATION: This copies both sets of input points every time. If the input data was read // directly, the output path would only need to be copied if it was also one of the input paths. int SkOpEdgeBuilder::preFetch() { + if (!fPath->isFinite()) { + fUnparseable = true; + return 0; + } SkPath::RawIter iter(*fPath); SkPoint pts[4]; SkPath::Verb verb; @@ -74,14 +82,25 @@ int SkOpEdgeBuilder::preFetch() { return fPathVerbs.count() - 1; } -void SkOpEdgeBuilder::walk() { +bool SkOpEdgeBuilder::close() { + if (fFinalCurveStart && fFinalCurveEnd && *fFinalCurveStart != *fFinalCurveEnd) { + *fReducePts.append() = *fFinalCurveStart; + *fReducePts.append() = *fFinalCurveEnd; + const SkPoint* lineStart = fReducePts.end() - 2; + *fExtra.append() = fCurrentContour->addLine(lineStart); + } + complete(); + return true; +} + +bool SkOpEdgeBuilder::walk() { SkPath::Verb reducedVerb; uint8_t* verbPtr = fPathVerbs.begin(); uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf]; const SkPoint* pointsPtr = fPathPts.begin(); - const SkPoint* finalCurveStart = NULL; - const SkPoint* finalCurveEnd = NULL; SkPath::Verb verb; + fFinalCurveStart = NULL; + fFinalCurveEnd = NULL; while ((verb = (SkPath::Verb) *verbPtr) != SkPath::kDone_Verb) { if (verbPtr == endOfFirstHalf) { fOperand = true; @@ -89,64 +108,76 @@ void SkOpEdgeBuilder::walk() { verbPtr++; switch (verb) { case SkPath::kMove_Verb: - complete(); + if (fCurrentContour) { + if (fAllowOpenContours) { + complete(); + } else if (!close()) { + return false; + } + } if (!fCurrentContour) { fCurrentContour = fContours.push_back_n(1); fCurrentContour->setOperand(fOperand); fCurrentContour->setXor(fXorMask[fOperand] == kEvenOdd_PathOpsMask); *fExtra.append() = -1; // start new contour } - finalCurveEnd = pointsPtr++; + fFinalCurveEnd = pointsPtr++; continue; - case SkPath::kLine_Verb: + case SkPath::kLine_Verb: { + const SkPoint& lineEnd = pointsPtr[0]; + const SkPoint& lineStart = pointsPtr[-1]; // skip degenerate points - if (pointsPtr[-1].fX != pointsPtr[0].fX || pointsPtr[-1].fY != pointsPtr[0].fY) { - fCurrentContour->addLine(&pointsPtr[-1]); + if (lineStart.fX != lineEnd.fX || lineStart.fY != lineEnd.fY) { + fCurrentContour->addLine(&lineStart); } - break; - case SkPath::kQuad_Verb: - reducedVerb = SkReduceOrder::Quad(&pointsPtr[-1], &fReducePts); + } break; + case SkPath::kQuad_Verb: { + const SkPoint* quadStart = &pointsPtr[-1]; + reducedVerb = SkReduceOrder::Quad(quadStart, &fReducePts); if (reducedVerb == 0) { break; // skip degenerate points } if (reducedVerb == 1) { - *fExtra.append() = - fCurrentContour->addLine(fReducePts.end() - 2); + const SkPoint* lineStart = fReducePts.end() - 2; + *fExtra.append() = fCurrentContour->addLine(lineStart); break; } - fCurrentContour->addQuad(&pointsPtr[-1]); - break; - case SkPath::kCubic_Verb: - reducedVerb = SkReduceOrder::Cubic(&pointsPtr[-1], &fReducePts); + fCurrentContour->addQuad(quadStart); + } break; + case SkPath::kCubic_Verb: { + const SkPoint* cubicStart = &pointsPtr[-1]; + reducedVerb = SkReduceOrder::Cubic(cubicStart, &fReducePts); if (reducedVerb == 0) { break; // skip degenerate points } if (reducedVerb == 1) { - *fExtra.append() = fCurrentContour->addLine(fReducePts.end() - 2); + const SkPoint* lineStart = fReducePts.end() - 2; + *fExtra.append() = fCurrentContour->addLine(lineStart); break; } if (reducedVerb == 2) { - *fExtra.append() = fCurrentContour->addQuad(fReducePts.end() - 3); + const SkPoint* quadStart = fReducePts.end() - 3; + *fExtra.append() = fCurrentContour->addQuad(quadStart); break; } - fCurrentContour->addCubic(&pointsPtr[-1]); - break; + fCurrentContour->addCubic(cubicStart); + } break; case SkPath::kClose_Verb: SkASSERT(fCurrentContour); - if (finalCurveStart && finalCurveEnd - && *finalCurveStart != *finalCurveEnd) { - *fReducePts.append() = *finalCurveStart; - *fReducePts.append() = *finalCurveEnd; - *fExtra.append() = fCurrentContour->addLine(fReducePts.end() - 2); + if (!close()) { + return false; } - complete(); continue; default: SkDEBUGFAIL("bad verb"); - return; + return false; } - finalCurveStart = &pointsPtr[verb - 1]; + fFinalCurveStart = &pointsPtr[verb - 1]; pointsPtr += verb; SkASSERT(fCurrentContour); } + if (fCurrentContour && !fAllowOpenContours && !close()) { + return false; + } + return true; } diff --git a/src/pathops/SkOpEdgeBuilder.h b/src/pathops/SkOpEdgeBuilder.h index 68afc93..b827a2a 100644 --- a/src/pathops/SkOpEdgeBuilder.h +++ b/src/pathops/SkOpEdgeBuilder.h @@ -16,13 +16,15 @@ class SkOpEdgeBuilder { public: SkOpEdgeBuilder(const SkPathWriter& path, SkTArray& contours) : fPath(path.nativePath()) - , fContours(contours) { + , fContours(contours) + , fAllowOpenContours(true) { init(); } SkOpEdgeBuilder(const SkPath& path, SkTArray& contours) : fPath(&path) - , fContours(contours) { + , fContours(contours) + , fAllowOpenContours(false) { init(); } @@ -38,23 +40,28 @@ public: } void addOperand(const SkPath& path); - void finish(); + bool finish(); void init(); private: + bool close(); int preFetch(); - void walk(); + bool walk(); const SkPath* fPath; - SkTDArray fPathPts; // FIXME: point directly to path pts instead - SkTDArray fPathVerbs; // FIXME: remove + SkTDArray fPathPts; + SkTDArray fPathVerbs; SkOpContour* fCurrentContour; SkTArray& fContours; SkTDArray fReducePts; // segments created on the fly SkTDArray fExtra; // -1 marks new contour, > 0 offsets into contour SkPathOpsMask fXorMask[2]; + const SkPoint* fFinalCurveStart; + const SkPoint* fFinalCurveEnd; int fSecondHalf; bool fOperand; + bool fAllowOpenContours; + bool fUnparseable; }; #endif diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp index a0071a0..80e698c 100644 --- a/src/pathops/SkPathOpsOp.cpp +++ b/src/pathops/SkPathOpsOp.cpp @@ -226,7 +226,7 @@ static const bool gOutInverse[kReverseDifference_PathOp + 1][2][2] = { {{ false, true }, { false, false }}, // rev diff }; -void Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { +bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()]; SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()] ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType; @@ -246,7 +246,9 @@ void Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { SkOpEdgeBuilder builder(*minuend, contours); const int xorMask = builder.xorMask(); builder.addOperand(*subtrahend); - builder.finish(); + if (!builder.finish()) { + return false; + } result->reset(); result->setFillType(fillType); const int xorOpMask = builder.xorMask(); @@ -255,7 +257,7 @@ void Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { xorOpMask == kEvenOdd_PathOpsMask); SkOpContour** currentPtr = contourList.begin(); if (!currentPtr) { - return; + return true; } SkOpContour** listEnd = contourList.end(); // find all intersections between segments @@ -298,5 +300,7 @@ void Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { SkPathWriter assembled(temp); Assemble(wrapper, &assembled); *result = *assembled.nativePath(); + result->setFillType(fillType); } + return true; } diff --git a/src/pathops/SkPathOpsSimplify.cpp b/src/pathops/SkPathOpsSimplify.cpp index 5c9d683..cb00aff 100644 --- a/src/pathops/SkPathOpsSimplify.cpp +++ b/src/pathops/SkPathOpsSimplify.cpp @@ -143,26 +143,27 @@ static bool bridgeXor(SkTDArray& contourList, SkPathWriter* simple } // FIXME : add this as a member of SkPath -void Simplify(const SkPath& path, SkPath* result) { +bool Simplify(const SkPath& path, SkPath* result) { #if DEBUG_SORT || DEBUG_SWAP_TOP gDebugSortCount = gDebugSortCountDefault; #endif // returns 1 for evenodd, -1 for winding, regardless of inverse-ness - result->reset(); SkPath::FillType fillType = path.isInverseFillType() ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType; - result->setFillType(fillType); - SkPathWriter simple(*result); // turn path into list of segments SkTArray contours; SkOpEdgeBuilder builder(path, contours); - builder.finish(); + if (!builder.finish()) { + return false; + } SkTDArray contourList; MakeContourList(contours, contourList, false, false); SkOpContour** currentPtr = contourList.begin(); + result->setFillType(fillType); + result->reset(); if (!currentPtr) { - return; + return true; } SkOpContour** listEnd = contourList.end(); // find all intersections between segments @@ -185,6 +186,7 @@ void Simplify(const SkPath& path, SkPath* result) { DebugShowActiveSpans(contourList); #endif // construct closed contours + SkPathWriter simple(*result); if (builder.xorMask() == kWinding_PathOpsMask ? bridgeWinding(contourList, &simple) : !bridgeXor(contourList, &simple)) { // if some edges could not be resolved, assemble remaining fragments @@ -193,5 +195,7 @@ void Simplify(const SkPath& path, SkPath* result) { SkPathWriter assembled(temp); Assemble(simple, &assembled); *result = *assembled.nativePath(); + result->setFillType(fillType); } + return true; } diff --git a/tests/PathOpsExtendedTest.cpp b/tests/PathOpsExtendedTest.cpp index 4626454..8d7ca28 100644 --- a/tests/PathOpsExtendedTest.cpp +++ b/tests/PathOpsExtendedTest.cpp @@ -449,7 +449,11 @@ bool testSimplify(SkPath& path, bool useXor, SkPath& out, PathOpsThreadState& st if (gShowPath) { showPath(path); } - Simplify(path, &out); + if (!Simplify(path, &out)) { + SkDebugf("%s did not expect failure\n", __FUNCTION__); + REPORTER_ASSERT(state.fReporter, 0); + return false; + } if (!gComparePaths) { return true; } @@ -478,7 +482,11 @@ bool testSimplify(skiatest::Reporter* reporter, const SkPath& path) { showPathData(path); #endif SkPath out; - Simplify(path, &out); + if (!Simplify(path, &out)) { + SkDebugf("%s did not expect failure\n", __FUNCTION__); + REPORTER_ASSERT(reporter, 0); + return false; + } SkBitmap bitmap; int result = comparePaths(reporter, path, out, bitmap); if (result && gPathStrAssert) { @@ -496,7 +504,11 @@ bool testPathOp(skiatest::Reporter* reporter, const SkPath& a, const SkPath& b, showPathData(b); #endif SkPath out; - Op(a, b, shapeOp, &out); + if (!Op(a, b, shapeOp, &out) ) { + SkDebugf("%s did not expect failure\n", __FUNCTION__); + REPORTER_ASSERT(reporter, 0); + return false; + } SkPath pathOut, scaledPathOut; SkRegion rgnA, rgnB, openClip, rgnOut; openClip.setRect(-16000, -16000, 16000, 16000); diff --git a/tests/PathOpsSimplifyFailTest.cpp b/tests/PathOpsSimplifyFailTest.cpp new file mode 100644 index 0000000..4b248c0 --- /dev/null +++ b/tests/PathOpsSimplifyFailTest.cpp @@ -0,0 +1,96 @@ +/* + * Copyright 2013 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ +#include "SkPathOps.h" +#include "SkPath.h" +#include "SkPoint.h" +#include "Test.h" + +static const SkPoint nonFinitePts[] = { + { SK_ScalarInfinity, 0 }, + { 0, SK_ScalarInfinity }, + { SK_ScalarInfinity, SK_ScalarInfinity }, + { SK_ScalarNegativeInfinity, 0}, + { 0, SK_ScalarNegativeInfinity }, + { SK_ScalarNegativeInfinity, SK_ScalarNegativeInfinity }, + { SK_ScalarNegativeInfinity, SK_ScalarInfinity }, + { SK_ScalarInfinity, SK_ScalarNegativeInfinity }, + { SK_ScalarNaN, 0 }, + { 0, SK_ScalarNaN }, + { SK_ScalarNaN, SK_ScalarNaN }, +}; + +const size_t nonFinitePtsCount = sizeof(nonFinitePts) / sizeof(nonFinitePts[0]); + +static const SkPoint finitePts[] = { + { 0, 0 }, + { SK_ScalarMax, 0 }, + { 0, SK_ScalarMax }, + { SK_ScalarMax, SK_ScalarMax }, + { SK_ScalarMin, 0 }, + { 0, SK_ScalarMin }, + { SK_ScalarMin, SK_ScalarMin }, +}; + +const size_t finitePtsCount = sizeof(finitePts) / sizeof(finitePts[0]); + +static void PathOpsSimplifyFailTest(skiatest::Reporter* reporter) { + for (int index = 0; index < (int) (13 * nonFinitePtsCount * finitePtsCount); ++index) { + SkPath path; + int i = (int) (index % nonFinitePtsCount); + int f = (int) (index % finitePtsCount); + int g = (int) ((f + 1) % finitePtsCount); + switch (index % 13) { + case 0: path.lineTo(nonFinitePts[i]); break; + case 1: path.quadTo(nonFinitePts[i], nonFinitePts[i]); break; + case 2: path.quadTo(nonFinitePts[i], finitePts[f]); break; + case 3: path.quadTo(finitePts[f], nonFinitePts[i]); break; + case 4: path.cubicTo(nonFinitePts[i], finitePts[f], finitePts[f]); break; + case 5: path.cubicTo(finitePts[f], nonFinitePts[i], finitePts[f]); break; + case 6: path.cubicTo(finitePts[f], finitePts[f], nonFinitePts[i]); break; + case 7: path.cubicTo(nonFinitePts[i], nonFinitePts[i], finitePts[f]); break; + case 8: path.cubicTo(nonFinitePts[i], finitePts[f], nonFinitePts[i]); break; + case 9: path.cubicTo(finitePts[f], nonFinitePts[i], nonFinitePts[i]); break; + case 10: path.cubicTo(nonFinitePts[i], nonFinitePts[i], nonFinitePts[i]); break; + case 11: path.cubicTo(nonFinitePts[i], finitePts[f], finitePts[g]); break; + case 12: path.moveTo(nonFinitePts[i]); break; + } + SkPath result; + result.setFillType(SkPath::kWinding_FillType); + bool success = Simplify(path, &result); + REPORTER_ASSERT(reporter, !success); + REPORTER_ASSERT(reporter, result.isEmpty()); + REPORTER_ASSERT(reporter, result.getFillType() == SkPath::kWinding_FillType); + reporter->bumpTestCount(); + } + for (int index = 0; index < (int) (11 * finitePtsCount); ++index) { + SkPath path; + int f = (int) (index % finitePtsCount); + int g = (int) ((f + 1) % finitePtsCount); + switch (index % 11) { + case 0: path.lineTo(finitePts[f]); break; + case 1: path.quadTo(finitePts[f], finitePts[f]); break; + case 2: path.quadTo(finitePts[f], finitePts[g]); break; + case 3: path.quadTo(finitePts[g], finitePts[f]); break; + case 4: path.cubicTo(finitePts[f], finitePts[f], finitePts[f]); break; + case 5: path.cubicTo(finitePts[f], finitePts[f], finitePts[g]); break; + case 6: path.cubicTo(finitePts[f], finitePts[g], finitePts[f]); break; + case 7: path.cubicTo(finitePts[f], finitePts[g], finitePts[g]); break; + case 8: path.cubicTo(finitePts[g], finitePts[f], finitePts[f]); break; + case 9: path.cubicTo(finitePts[g], finitePts[f], finitePts[g]); break; + case 10: path.moveTo(finitePts[f]); break; + } + SkPath result; + result.setFillType(SkPath::kWinding_FillType); + bool success = Simplify(path, &result); + REPORTER_ASSERT(reporter, success); + REPORTER_ASSERT(reporter, result.getFillType() != SkPath::kWinding_FillType); + reporter->bumpTestCount(); + } +} + +#include "TestClassDef.h" +DEFINE_TESTCLASS_SHORT(PathOpsSimplifyFailTest) diff --git a/tests/PathOpsSimplifyTest.cpp b/tests/PathOpsSimplifyTest.cpp index 356f172..c0d13c8 100644 --- a/tests/PathOpsSimplifyTest.cpp +++ b/tests/PathOpsSimplifyTest.cpp @@ -3652,9 +3652,54 @@ static void testTriangles2(skiatest::Reporter* reporter) { testSimplify(reporter, path); } +// A test this for this case: +// contourA has two segments that are coincident +// contourB has two segments that are coincident in the same place +// each ends up with +2/0 pairs for winding count +// since logic in OpSegment::addTCoincident doesn't transfer count (only increments/decrements) +// can this be resolved to +4/0 ? +static void testAddTCoincident1(skiatest::Reporter* reporter) { + SkPath path; + path.moveTo(2, 0); + path.lineTo(2, 2); + path.lineTo(1, 1); + path.lineTo(2, 0); + path.lineTo(2, 2); + path.lineTo(1, 1); + path.close(); + path.moveTo(2, 0); + path.lineTo(2, 2); + path.lineTo(3, 1); + path.lineTo(2, 0); + path.lineTo(2, 2); + path.lineTo(3, 1); + path.close(); + testSimplify(reporter, path); +} + +// test with implicit close +static void testAddTCoincident2(skiatest::Reporter* reporter) { + SkPath path; + path.moveTo(2, 0); + path.lineTo(2, 2); + path.lineTo(1, 1); + path.lineTo(2, 0); + path.lineTo(2, 2); + path.lineTo(1, 1); + path.moveTo(2, 0); + path.lineTo(2, 2); + path.lineTo(3, 1); + path.lineTo(2, 0); + path.lineTo(2, 2); + path.lineTo(3, 1); + testSimplify(reporter, path); +} + static void (*firstTest)(skiatest::Reporter* ) = 0; static TestDesc tests[] = { + TEST(testAddTCoincident2), + TEST(testAddTCoincident1), TEST(testTriangles2), TEST(testTriangles1), TEST(testQuadratic97), -- 2.7.4