From 9f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333 Mon Sep 17 00:00:00 2001 From: "caryclark@google.com" Date: Mon, 10 Dec 2012 12:50:53 +0000 Subject: [PATCH] shape ops work in progress rewrite binary edge inclusion lookup fix warnings git-svn-id: http://skia.googlecode.com/svn/trunk@6726 2bbb7eff-a529-9590-31e7-b0007b416f81 --- experimental/Intersection/ActiveEdge_Test.cpp | 8 +- experimental/Intersection/CubicIntersection.cpp | 2 +- experimental/Intersection/CubicReduceOrder.cpp | 4 +- .../Intersection/CubicReduceOrder_Test.cpp | 16 +-- experimental/Intersection/EdgeWalker.cpp | 4 +- .../Intersection/EdgeWalkerRectangles_Test.cpp | 4 +- experimental/Intersection/LineIntersection.cpp | 4 +- experimental/Intersection/LineUtilities.cpp | 8 +- experimental/Intersection/MiniSimplify_Test.cpp | 2 + experimental/Intersection/QuadraticReduceOrder.cpp | 4 +- experimental/Intersection/Simplify.cpp | 118 ++++++++------------- experimental/Intersection/SimplifyNew_Test.cpp | 2 +- 12 files changed, 73 insertions(+), 103 deletions(-) diff --git a/experimental/Intersection/ActiveEdge_Test.cpp b/experimental/Intersection/ActiveEdge_Test.cpp index 8ded8ff..1ac340e4 100755 --- a/experimental/Intersection/ActiveEdge_Test.cpp +++ b/experimental/Intersection/ActiveEdge_Test.cpp @@ -48,10 +48,10 @@ size_t leftRightCount = sizeof(leftRight) / sizeof(leftRight[0]); // older code that worked mostly static bool operator_less_than(const UnitTest::ActiveEdge& lh, const UnitTest::ActiveEdge& rh) { - if (rh.fAbove.fY - lh.fAbove.fY > lh.fBelow.fY - rh.fAbove.fY - && lh.fBelow.fY < rh.fBelow.fY - || lh.fAbove.fY - rh.fAbove.fY < rh.fBelow.fY - lh.fAbove.fY - && rh.fBelow.fY < lh.fBelow.fY) { + if ((rh.fAbove.fY - lh.fAbove.fY > lh.fBelow.fY - rh.fAbove.fY + && lh.fBelow.fY < rh.fBelow.fY) + || (lh.fAbove.fY - rh.fAbove.fY < rh.fBelow.fY - lh.fAbove.fY + && rh.fBelow.fY < lh.fBelow.fY)) { const SkPoint& check = rh.fBelow.fY <= lh.fBelow.fY && lh.fBelow != rh.fBelow ? rh.fBelow : rh.fAbove; diff --git a/experimental/Intersection/CubicIntersection.cpp b/experimental/Intersection/CubicIntersection.cpp index 452ef29..cc86f0c 100644 --- a/experimental/Intersection/CubicIntersection.cpp +++ b/experimental/Intersection/CubicIntersection.cpp @@ -145,7 +145,7 @@ bool chop(double minT1, double maxT1, double minT2, double maxT2, int split) { private: -static const double tClipLimit = 0.8; // http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf see Multiple intersections +const double tClipLimit = 0.8; // http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf see Multiple intersections const Cubic& cubic1; const Cubic& cubic2; Intersections& intersections; diff --git a/experimental/Intersection/CubicReduceOrder.cpp b/experimental/Intersection/CubicReduceOrder.cpp index 38e853a..294d18c 100644 --- a/experimental/Intersection/CubicReduceOrder.cpp +++ b/experimental/Intersection/CubicReduceOrder.cpp @@ -133,13 +133,13 @@ static int check_linear(const Cubic& cubic, Cubic& reduction, continue; } replace = (extrema.x < cubic[0].x | extrema.x < cubic[3].x) - ^ cubic[0].x < cubic[3].x; + ^ (cubic[0].x < cubic[3].x); } else { if (extrema.y < cubic[0].y ^ extrema.y < cubic[3].y) { continue; } replace = (extrema.y < cubic[0].y | extrema.y < cubic[3].y) - ^ cubic[0].y < cubic[3].y; + ^ (cubic[0].y < cubic[3].y); } reduction[replace] = extrema; } diff --git a/experimental/Intersection/CubicReduceOrder_Test.cpp b/experimental/Intersection/CubicReduceOrder_Test.cpp index d01629c..2981156 100644 --- a/experimental/Intersection/CubicReduceOrder_Test.cpp +++ b/experimental/Intersection/CubicReduceOrder_Test.cpp @@ -121,10 +121,10 @@ void CubicReduceOrder_Test() { printf("[%d] line computed ends match order=%d\n", (int) index, order); } if (controlsInside) { - if ( reduce[0].x != cubic[0].x && reduce[0].x != cubic[3].x - || reduce[0].y != cubic[0].y && reduce[0].y != cubic[3].y - || reduce[1].x != cubic[0].x && reduce[1].x != cubic[3].x - || reduce[1].y != cubic[0].y && reduce[1].y != cubic[3].y) { + if ( (reduce[0].x != cubic[0].x && reduce[0].x != cubic[3].x) + || (reduce[0].y != cubic[0].y && reduce[0].y != cubic[3].y) + || (reduce[1].x != cubic[0].x && reduce[1].x != cubic[3].x) + || (reduce[1].y != cubic[0].y && reduce[1].y != cubic[3].y)) { printf("[%d] line computed ends order=%d\n", (int) index, order); } } else { @@ -132,10 +132,10 @@ void CubicReduceOrder_Test() { // while a control point is outside of bounding box formed by end points, split _Rect bounds = {DBL_MAX, DBL_MAX, -DBL_MAX, -DBL_MAX}; find_tight_bounds(cubic, bounds); - if ( !approximately_equal(reduce[0].x, bounds.left) && !approximately_equal(reduce[0].x, bounds.right) - || !approximately_equal(reduce[0].y, bounds.top) && !approximately_equal(reduce[0].y, bounds.bottom) - || !approximately_equal(reduce[1].x, bounds.left) && !approximately_equal(reduce[1].x, bounds.right) - || !approximately_equal(reduce[1].y, bounds.top) && !approximately_equal(reduce[1].y, bounds.bottom)) { + if ( (!approximately_equal(reduce[0].x, bounds.left) && !approximately_equal(reduce[0].x, bounds.right)) + || (!approximately_equal(reduce[0].y, bounds.top) && !approximately_equal(reduce[0].y, bounds.bottom)) + || (!approximately_equal(reduce[1].x, bounds.left) && !approximately_equal(reduce[1].x, bounds.right)) + || (!approximately_equal(reduce[1].y, bounds.top) && !approximately_equal(reduce[1].y, bounds.bottom))) { printf("[%d] line computed tight bounds order=%d\n", (int) index, order); } diff --git a/experimental/Intersection/EdgeWalker.cpp b/experimental/Intersection/EdgeWalker.cpp index 47bd037..12fe30d 100644 --- a/experimental/Intersection/EdgeWalker.cpp +++ b/experimental/Intersection/EdgeWalker.cpp @@ -741,7 +741,7 @@ struct Bounds : public SkRect { bool isEmpty() { return fLeft > fRight || fTop > fBottom - || fLeft == fRight && fTop == fBottom + || (fLeft == fRight && fTop == fBottom) || isnan(fLeft) || isnan(fRight) || isnan(fTop) || isnan(fBottom); } @@ -2206,7 +2206,7 @@ static void makeHorizontalList(SkTDArray& edges, static void skipCoincidence(int lastWinding, int winding, int windingMask, ActiveEdge* activePtr, ActiveEdge* firstCoincident) { - if (((lastWinding & windingMask) == 0) ^ (winding & windingMask) != 0) { + if (((lastWinding & windingMask) == 0) ^ ((winding & windingMask) != 0)) { return; } // FIXME: ? shouldn't this be if (lastWinding & windingMask) ? diff --git a/experimental/Intersection/EdgeWalkerRectangles_Test.cpp b/experimental/Intersection/EdgeWalkerRectangles_Test.cpp index dae1d70..31edd74 100644 --- a/experimental/Intersection/EdgeWalkerRectangles_Test.cpp +++ b/experimental/Intersection/EdgeWalkerRectangles_Test.cpp @@ -149,8 +149,8 @@ static void testSimplifyCorner() { } SkRect one = SkRect::MakeLTRB(10, 10, 20, 20); SkRect two = SkRect::MakeLTRB(20, 20, 40, 40); - if (boundsArray[0] != one && boundsArray[0] != two - || boundsArray[1] != one && boundsArray[1] != two) { + if ((boundsArray[0] != one && boundsArray[0] != two) + || (boundsArray[1] != one && boundsArray[1] != two)) { SkDebugf("%s expected match\n", __FUNCTION__); } } diff --git a/experimental/Intersection/LineIntersection.cpp b/experimental/Intersection/LineIntersection.cpp index 11f42ba..c425cd1 100644 --- a/experimental/Intersection/LineIntersection.cpp +++ b/experimental/Intersection/LineIntersection.cpp @@ -95,11 +95,11 @@ int intersect(const _Line& a, const _Line& b, double aRange[2], double bRange[2] double ab0y = a[0].y - b[0].y; double ab0x = a[0].x - b[0].x; double numerA = ab0y * bxLen - byLen * ab0x; - if (numerA < 0 && denom > numerA || numerA > 0 && denom < numerA) { + if ((numerA < 0 && denom > numerA) || (numerA > 0 && denom < numerA)) { return 0; } double numerB = ab0y * axLen - ayLen * ab0x; - if (numerB < 0 && denom > numerB || numerB > 0 && denom < numerB) { + if ((numerB < 0 && denom > numerB) || (numerB > 0 && denom < numerB)) { return 0; } /* Is the intersection along the the segments */ diff --git a/experimental/Intersection/LineUtilities.cpp b/experimental/Intersection/LineUtilities.cpp index fc19885..25bd88d 100644 --- a/experimental/Intersection/LineUtilities.cpp +++ b/experimental/Intersection/LineUtilities.cpp @@ -103,14 +103,14 @@ void x_at(const _Point& p1, const _Point& p2, double top, double bottom, // if p1.y > p2.y, maxX can be affected double slope = (p2.x - p1.x) / (p2.y - p1.y); int topFlags = flags & (kFindTopMin | kFindTopMax); - if (topFlags && (top <= p1.y && top >= p2.y - || top >= p1.y && top <= p2.y)) { + if (topFlags && ((top <= p1.y && top >= p2.y) + || (top >= p1.y && top <= p2.y))) { double x = p1.x + (top - p1.y) * slope; setMinMax(x, topFlags, minX, maxX); } int bottomFlags = flags & (kFindBottomMin | kFindBottomMax); - if (bottomFlags && (bottom <= p1.y && bottom >= p2.y - || bottom >= p1.y && bottom <= p2.y)) { + if (bottomFlags && ((bottom <= p1.y && bottom >= p2.y) + || (bottom >= p1.y && bottom <= p2.y))) { double x = p1.x + (bottom - p1.y) * slope; setMinMax(x, bottomFlags, minX, maxX); } diff --git a/experimental/Intersection/MiniSimplify_Test.cpp b/experimental/Intersection/MiniSimplify_Test.cpp index 6d6036c..3cb90ab 100644 --- a/experimental/Intersection/MiniSimplify_Test.cpp +++ b/experimental/Intersection/MiniSimplify_Test.cpp @@ -58,6 +58,8 @@ static void construct() { case SkPath::kCubic_Verb: path.cubicTo(test->pts[1].fX, test->pts[1].fY, test->pts[2].fX, test->pts[2].fY, test->pts[3].fX, test->pts[3].fY); break; + default: + SkASSERT(0); } test++; } while (!pathComplete); diff --git a/experimental/Intersection/QuadraticReduceOrder.cpp b/experimental/Intersection/QuadraticReduceOrder.cpp index 3904817..b68a68b 100644 --- a/experimental/Intersection/QuadraticReduceOrder.cpp +++ b/experimental/Intersection/QuadraticReduceOrder.cpp @@ -100,13 +100,13 @@ static int check_linear(const Quadratic& quad, Quadratic& reduction, return 2; } replace = (extrema.x < quad[0].x | extrema.x < quad[2].x) - ^ quad[0].x < quad[2].x; + ^ (quad[0].x < quad[2].x); } else { if (extrema.y < quad[0].y ^ extrema.y < quad[2].y) { return 2; } replace = (extrema.y < quad[0].y | extrema.y < quad[2].y) - ^ quad[0].y < quad[2].y; + ^ (quad[0].y < quad[2].y); } reduction[replace] = extrema; } diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp index b3072f3..9f8176b 100644 --- a/experimental/Intersection/Simplify.cpp +++ b/experimental/Intersection/Simplify.cpp @@ -794,7 +794,7 @@ struct Bounds : public SkRect { void add(const Bounds& toAdd) { add(toAdd.fLeft, toAdd.fTop, toAdd.fRight, toAdd.fBottom); } - + bool isEmpty() { return fLeft > fRight || fTop > fBottom || (fLeft == fRight && fTop == fBottom) @@ -823,7 +823,7 @@ struct Bounds : public SkRect { // return outerWinding * innerWinding > 0 // || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0))) static bool useInnerWinding(int outerWinding, int innerWinding) { - SkASSERT(outerWinding != innerWinding); + // SkASSERT(outerWinding != innerWinding); int absOut = abs(outerWinding); int absIn = abs(innerWinding); bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn; @@ -836,18 +836,22 @@ static bool useInnerWinding(int outerWinding, int innerWinding) { return result; } -static const bool gOpLookup[][2][2] = { - // ==0 !=0 - // b a b a - {{true , false}, {false, true }}, // a - b - {{false, false}, {true , true }}, // a & b - {{true , true }, {false, false}}, // a | b - {{true , true }, {true , true }}, // a ^ b +#define F (false) // discard the edge +#define T (true) // keep the edge + +static const bool gActiveEdge[kShapeOp_Count][2][2][2][2] = { +// miFrom=0 miFrom=1 +// miTo=0 miTo=1 miTo=0 miTo=1 +// suFrom=0 1 suFrom=0 1 suFrom=0 1 suFrom=0 1 +// suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 + {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}}, // mi - su + {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}}, // mi & su + {{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}}, // mi | su + {{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}}, // mi ^ su }; -static bool isActiveOp(bool angleIsOp, int otherNonZero, ShapeOp op) { - return gOpLookup[op][otherNonZero][angleIsOp]; -} +#undef F +#undef T // wrap path to keep track of whether the contour is initialized and non-empty class PathWrapper { @@ -1098,46 +1102,32 @@ public: } int maxWinding, sumWinding, oppMaxWinding, oppSumWinding; return activeOp(xorMiMask, xorSuMask, index, endIndex, op, sumMiWinding, sumSuWinding, - maxWinding, sumWinding, oppMaxWinding, oppSumWinding); + maxWinding, sumWinding, oppMaxWinding, oppSumWinding); } - - bool activeOp(int xorMiMask, int xorSuMask, - int index, int endIndex, ShapeOp op, + + bool activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, ShapeOp op, int& sumMiWinding, int& sumSuWinding, int& maxWinding, int& sumWinding, int& oppMaxWinding, int& oppSumWinding) { setUpWindings(index, endIndex, sumMiWinding, sumSuWinding, maxWinding, sumWinding, oppMaxWinding, oppSumWinding); - int mask, oppMask; + bool miFrom; + bool miTo; + bool suFrom; + bool suTo; if (operand()) { - mask = xorSuMask; - oppMask = xorMiMask; + miFrom = (oppMaxWinding & xorMiMask) != 0; + miTo = (oppSumWinding & xorMiMask) != 0; + suFrom = (maxWinding & xorSuMask) != 0; + suTo = (sumWinding & xorSuMask) != 0; } else { - mask = xorMiMask; - oppMask = xorSuMask; + miFrom = (maxWinding & xorMiMask) != 0; + miTo = (sumWinding & xorMiMask) != 0; + suFrom = (oppMaxWinding & xorSuMask) != 0; + suTo = (oppSumWinding & xorSuMask) != 0; } - if ((sumWinding & mask) && (maxWinding & mask)) { - return false; - } - int oppCoin = oppSign(index, endIndex) & oppMask; - if (oppCoin) { - bool oppCrossZero = !(oppSumWinding & oppMask) || !(oppMaxWinding & oppMask); - bool outside = !(oppSumWinding & oppMask) ^ !(sumWinding & mask); - switch (op) { - case kIntersect_Op: - return !oppCrossZero | !outside; - case kUnion_Op: - return oppCrossZero & !outside; - case kDifference_Op: - return oppCrossZero ? outside : operand(); - case kXor_Op: - return !oppCrossZero; - default: - SkASSERT(0); - } - - } - bool oppNonZero = oppMaxWinding & oppMask; - return isActiveOp(operand(), oppNonZero, op); + bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo]; + SkASSERT(result != -1); + return result; } void addAngle(SkTDArray& angles, int start, int end) const { @@ -2481,8 +2471,7 @@ public: // iterate through T intersections and return topmost // topmost tangent from y-min to first pt is closer to horizontal SkASSERT(!done()); - int firstT; - int lastT; + int firstT = -1; SkPoint topPt; topPt.fY = SK_ScalarMax; int count = fTs.count(); @@ -2499,15 +2488,14 @@ public: if (topPt.fY > intercept.fY || (topPt.fY == intercept.fY && topPt.fX > intercept.fX)) { topPt = intercept; - firstT = lastT = index; - } else if (topPt == intercept) { - lastT = index; + firstT = index; } } next: lastDone = span.fDone; lastUnsortable = span.fUnsortableEnd; } + SkASSERT(firstT >= 0); // sort the edges to find the leftmost int step = 1; int end = nextSpan(firstT, step); @@ -2565,7 +2553,7 @@ public: } } } - + void init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd) { fDoneSpans = 0; fOperand = operand; @@ -2700,7 +2688,7 @@ public: Span* markAndChaseWinding(const Angle* angle, const int winding) { int index = angle->start(); int endIndex = angle->end(); - int step = SkSign32(endIndex - index); + int step = SkSign32(endIndex - index); int min = SkMin32(index, endIndex); markWinding(min, winding); Span* last; @@ -2775,7 +2763,7 @@ public: void markDoneBinary(int index, int winding, int oppWinding) { // SkASSERT(!done()); - SkASSERT(winding); + SkASSERT(winding || oppWinding); double referenceT = fTs[index].fT; int lesser = index; while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) { @@ -3148,7 +3136,7 @@ public: *outsideTs.append() = start; } } - + void undoneSpan(int& start, int& end) { size_t tCount = fTs.count(); size_t index; @@ -3200,7 +3188,7 @@ public: int lesser = SkMin32(index, endIndex); int winding = windSum(lesser); int spanWinding = spanSign(index, endIndex); - if (useInnerWinding(winding - spanWinding, winding)) { + if (winding && useInnerWinding(winding - spanWinding, winding)) { winding -= spanWinding; } return winding; @@ -3642,22 +3630,6 @@ public: } #endif -#if DEBUG_WINDING - bool debugVerifyWinding(int start, int end, int winding) const { - const Span& span = fTs[SkMin32(start, end)]; - int spanWinding = span.fWindSum; - if (spanWinding == SK_MinS32) { - return true; - } - int spanSign = SkSign32(start - end); - int signedVal = spanSign * span.fWindValue; - if (signedVal < 0) { - spanWinding -= signedVal; - } - return span.fWindSum == winding; - } -#endif - private: const SkPoint* fPts; Bounds fBounds; @@ -3921,7 +3893,7 @@ public: void setOperand(bool isOp) { fOperand = isOp; } - + void setOppXor(bool isOppXor) { fOppXor = isOppXor; int segmentCount = fSegments.count(); @@ -5203,7 +5175,6 @@ static bool bridgeWinding(SkTDArray& contourList, PathWrapper& simple) #endif } #if DEBUG_WINDING - // SkASSERT(current->debugVerifyWinding(index, endIndex, contourWinding)); SkDebugf("%s contourWinding=%d\n", __FUNCTION__, contourWinding); #endif } @@ -5460,13 +5431,10 @@ static void assemble(const PathWrapper& path, PathWrapper& simple) { first = false; simple.deferredMove(startPtr[0]); } - const SkPoint* endPtr; if (forward) { contour.toPartialForward(simple); - endPtr = &contour.end(); } else { contour.toPartialBackward(simple); - endPtr = &contour.start(); } if (sIndex == eIndex) { simple.close(); diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp index dfdc75e..5be846b 100644 --- a/experimental/Intersection/SimplifyNew_Test.cpp +++ b/experimental/Intersection/SimplifyNew_Test.cpp @@ -3330,7 +3330,7 @@ static struct { static const size_t subTestCount = sizeof(subTests) / sizeof(subTests[0]); -static void (*firstBinaryTest)() = 0; +static void (*firstBinaryTest)() = testOp2d; static bool skipAll = false; static bool runBinaryTestsFirst = true; -- 2.7.4