Index: src/pathops/SkOpAngle.cpp |
diff --git a/src/pathops/SkOpAngle.cpp b/src/pathops/SkOpAngle.cpp |
index 742a161f6c49221e373c78f1144ffb8af480fda3..364ab1bf1f53555e7ae98c76286628dd32a21b87 100644 |
--- a/src/pathops/SkOpAngle.cpp |
+++ b/src/pathops/SkOpAngle.cpp |
@@ -12,19 +12,14 @@ |
#if DEBUG_ANGLE |
#include "SkString.h" |
- |
-static const char funcName[] = "SkOpSegment::operator<"; |
-static const int bugChar = strlen(funcName) + 1; |
#endif |
/* Angles are sorted counterclockwise. The smallest angle has a positive x and the smallest |
positive y. The largest angle has a positive x and a zero y. */ |
#if DEBUG_ANGLE |
- static bool CompareResult(SkString* bugOut, const char* append, bool compare) { |
- bugOut->appendf("%s", append); |
- bugOut->writable_str()[bugChar] = "><"[compare]; |
- SkDebugf("%s\n", bugOut->c_str()); |
+ static bool CompareResult(SkString* bugOut, int append, bool compare) { |
+ SkDebugf("%s %c %d\n", bugOut->c_str(), compare ? 'T' : 'F', append); |
return compare; |
} |
@@ -33,7 +28,197 @@ static const int bugChar = strlen(funcName) + 1; |
#define COMPARE_RESULT(append, compare) compare |
#endif |
-bool SkOpAngle::calcSlop(double x, double y, double rx, double ry, bool* result) const{ |
+/* quarter angle values for sector |
+ |
+31 x > 0, y == 0 horizontal line (to the right) |
+0 x > 0, y == epsilon quad/cubic horizontal tangent eventually going +y |
+1 x > 0, y > 0, x > y nearer horizontal angle |
+2 x + e == y quad/cubic 45 going horiz |
+3 x > 0, y > 0, x == y 45 angle |
+4 x == y + e quad/cubic 45 going vert |
+5 x > 0, y > 0, x < y nearer vertical angle |
+6 x == epsilon, y > 0 quad/cubic vertical tangent eventually going +x |
+7 x == 0, y > 0 vertical line (to the top) |
+ |
+ 8 7 6 |
+ 9 | 5 |
+ 10 | 4 |
+ 11 | 3 |
+ 12 \ | / 2 |
+ 13 | 1 |
+ 14 | 0 |
+ 15 --------------+------------- 31 |
+ 16 | 30 |
+ 17 | 29 |
+ 18 / | \ 28 |
+ 19 | 27 |
+ 20 | 26 |
+ 21 | 25 |
+ 22 23 24 |
+*/ |
+ |
+// return true if lh < this < rh |
+bool SkOpAngle::after(const SkOpAngle* test) const { |
+ const SkOpAngle& lh = *test; |
+ const SkOpAngle& rh = *lh.fNext; |
+ SkASSERT(&lh != &rh); |
+#if DEBUG_ANGLE |
+ SkString bugOut; |
+ bugOut.printf("%s [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g" |
+ " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g" |
+ " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g ", __FUNCTION__, |
+ lh.fSegment->debugID(), lh.debugID(), lh.fSectorStart, lh.fSectorEnd, |
+ lh.fSegment->t(lh.fStart), lh.fSegment->t(lh.fEnd), |
+ fSegment->debugID(), debugID(), fSectorStart, fSectorEnd, fSegment->t(fStart), |
+ fSegment->t(fEnd), |
+ rh.fSegment->debugID(), rh.debugID(), rh.fSectorStart, rh.fSectorEnd, |
+ rh.fSegment->t(rh.fStart), rh.fSegment->t(rh.fEnd)); |
+#endif |
+ if (lh.fComputeSector && !const_cast<SkOpAngle&>(lh).computeSector()) { |
+ return COMPARE_RESULT(1, true); |
+ } |
+ if (fComputeSector && !const_cast<SkOpAngle*>(this)->computeSector()) { |
+ return COMPARE_RESULT(2, true); |
+ } |
+ if (rh.fComputeSector && !const_cast<SkOpAngle&>(rh).computeSector()) { |
+ return COMPARE_RESULT(3, true); |
+ } |
+#if DEBUG_ANGLE // reset bugOut with computed sectors |
+ bugOut.printf("%s [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g" |
+ " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g" |
+ " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g ", __FUNCTION__, |
+ lh.fSegment->debugID(), lh.debugID(), lh.fSectorStart, lh.fSectorEnd, |
+ lh.fSegment->t(lh.fStart), lh.fSegment->t(lh.fEnd), |
+ fSegment->debugID(), debugID(), fSectorStart, fSectorEnd, fSegment->t(fStart), |
+ fSegment->t(fEnd), |
+ rh.fSegment->debugID(), rh.debugID(), rh.fSectorStart, rh.fSectorEnd, |
+ rh.fSegment->t(rh.fStart), rh.fSegment->t(rh.fEnd)); |
+#endif |
+ bool ltrOverlap = (lh.fSectorMask | rh.fSectorMask) & fSectorMask; |
+ bool lrOverlap = lh.fSectorMask & rh.fSectorMask; |
+ int lrOrder; // set to -1 if either order works |
+ if (!lrOverlap) { // no lh/rh sector overlap |
+ if (!ltrOverlap) { // no lh/this/rh sector overlap |
+ return COMPARE_RESULT(4, (lh.fSectorEnd > rh.fSectorStart) |
+ ^ (fSectorStart > lh.fSectorEnd) ^ (fSectorStart > rh.fSectorStart)); |
+ } |
+ int lrGap = (rh.fSectorStart - lh.fSectorStart + 32) & 0x1f; |
+ /* A tiny change can move the start +/- 4. The order can only be determined if |
+ lr gap is not 12 to 20 or -12 to -20. |
+ -31 ..-21 1 |
+ -20 ..-12 -1 |
+ -11 .. -1 0 |
+ 0 shouldn't get here |
+ 11 .. 1 1 |
+ 12 .. 20 -1 |
+ 21 .. 31 0 |
+ */ |
+ lrOrder = lrGap > 20 ? 0 : lrGap > 11 ? -1 : 1; |
+ } else { |
+ lrOrder = (int) lh.orderable(rh); |
+ if (!ltrOverlap) { |
+ return COMPARE_RESULT(5, !lrOrder); |
+ } |
+ } |
+ int ltOrder; |
+ SkASSERT((lh.fSectorMask & fSectorMask) || (rh.fSectorMask & fSectorMask)); |
+ if (lh.fSectorMask & fSectorMask) { |
+ ltOrder = (int) lh.orderable(*this); |
+ } else { |
+ int ltGap = (fSectorStart - lh.fSectorStart + 32) & 0x1f; |
+ ltOrder = ltGap > 20 ? 0 : ltGap > 11 ? -1 : 1; |
+ } |
+ int trOrder; |
+ if (rh.fSectorMask & fSectorMask) { |
+ trOrder = (int) orderable(rh); |
+ } else { |
+ int trGap = (rh.fSectorStart - fSectorStart + 32) & 0x1f; |
+ trOrder = trGap > 20 ? 0 : trGap > 11 ? -1 : 1; |
+ } |
+ if (lrOrder >= 0 && ltOrder >= 0 && trOrder >= 0) { |
+ return COMPARE_RESULT(7, lrOrder ? (ltOrder & trOrder) : (ltOrder | trOrder)); |
+ } |
+ SkASSERT(lrOrder >= 0 || ltOrder >= 0 || trOrder >= 0); |
+// There's not enough information to sort. Get the pairs of angles in opposite planes. |
+// If an order is < 0, the pair is already in an opposite plane. Check the remaining pairs. |
+ // FIXME : once all variants are understood, rewrite this more simply |
+ if (ltOrder == 0 && lrOrder == 0) { |
+ SkASSERT(trOrder < 0); |
+ // FIXME : once this is verified to work, remove one opposite angle call |
+ SkDEBUGCODE(bool lrOpposite = lh.oppositePlanes(rh)); |
+ bool ltOpposite = lh.oppositePlanes(*this); |
+ SkASSERT(lrOpposite != ltOpposite); |
+ return COMPARE_RESULT(8, ltOpposite); |
+ } else if (ltOrder == 1 && trOrder == 0) { |
+ SkASSERT(lrOrder < 0); |
+ SkDEBUGCODE(bool ltOpposite = lh.oppositePlanes(*this)); |
+ bool trOpposite = oppositePlanes(rh); |
+ SkASSERT(ltOpposite != trOpposite); |
+ return COMPARE_RESULT(9, trOpposite); |
+ } else if (lrOrder == 1 && trOrder == 1) { |
+ SkASSERT(ltOrder < 0); |
+ SkDEBUGCODE(bool trOpposite = oppositePlanes(rh)); |
+ bool lrOpposite = lh.oppositePlanes(rh); |
+ SkASSERT(lrOpposite != trOpposite); |
+ return COMPARE_RESULT(10, lrOpposite); |
+ } |
+ if (lrOrder < 0) { |
+ if (ltOrder < 0) { |
+ return COMPARE_RESULT(11, trOrder); |
+ } |
+ return COMPARE_RESULT(12, ltOrder); |
+ } |
+ return COMPARE_RESULT(13, !lrOrder); |
+} |
+ |
+// given a line, see if the opposite curve's convex hull is all on one side |
+// returns -1=not on one side 0=this CW of test 1=this CCW of test |
+int SkOpAngle::allOnOneSide(const SkOpAngle& test) const { |
+ SkASSERT(!fIsCurve); |
+ SkASSERT(test.fIsCurve); |
+ const SkDPoint& origin = test.fCurvePart[0]; |
+ SkVector line; |
+ if (fSegment->verb() == SkPath::kLine_Verb) { |
+ const SkPoint* linePts = fSegment->pts(); |
+ int lineStart = fStart < fEnd ? 0 : 1; |
+ line = linePts[lineStart ^ 1] - linePts[lineStart]; |
+ } else { |
+ SkPoint shortPts[2] = { fCurvePart[0].asSkPoint(), fCurvePart[1].asSkPoint() }; |
+ line = shortPts[1] - shortPts[0]; |
+ } |
+ float crosses[3]; |
+ SkPath::Verb testVerb = test.fSegment->verb(); |
+ int iMax = SkPathOpsVerbToPoints(testVerb); |
+// SkASSERT(origin == test.fCurveHalf[0]); |
+ const SkDCubic& testCurve = test.fCurvePart; |
+// do { |
+ for (int index = 1; index <= iMax; ++index) { |
+ float xy1 = (float) (line.fX * (testCurve[index].fY - origin.fY)); |
+ float xy2 = (float) (line.fY * (testCurve[index].fX - origin.fX)); |
+ crosses[index - 1] = AlmostEqualUlps(xy1, xy2) ? 0 : xy1 - xy2; |
+ } |
+ if (crosses[0] * crosses[1] < 0) { |
+ return -1; |
+ } |
+ if (SkPath::kCubic_Verb == testVerb) { |
+ if (crosses[0] * crosses[2] < 0 || crosses[1] * crosses[2] < 0) { |
+ return -1; |
+ } |
+ } |
+ if (crosses[0]) { |
+ return crosses[0] < 0; |
+ } |
+ if (crosses[1]) { |
+ return crosses[1] < 0; |
+ } |
+ if (SkPath::kCubic_Verb == testVerb && crosses[2]) { |
+ return crosses[2] < 0; |
+ } |
+ fUnorderable = true; |
+ return -1; |
+} |
+ |
+bool SkOpAngle::calcSlop(double x, double y, double rx, double ry, bool* result) const { |
double absX = fabs(x); |
double absY = fabs(y); |
double length = absX < absY ? absX / 2 + absY : absX + absY / 2; |
@@ -59,280 +244,733 @@ bool SkOpAngle::calcSlop(double x, double y, double rx, double ry, bool* result) |
return *result == less2; |
} |
-/* |
-for quads and cubics, set up a parameterized line (e.g. LineParameters ) |
-for points [0] to [1]. See if point [2] is on that line, or on one side |
-or the other. If it both quads' end points are on the same side, choose |
-the shorter tangent. If the tangents are equal, choose the better second |
-tangent angle |
+bool SkOpAngle::checkCrossesZero() const { |
+ int start = SkTMin(fSectorStart, fSectorEnd); |
+ int end = SkTMax(fSectorStart, fSectorEnd); |
+ bool crossesZero = end - start > 16; |
+ return crossesZero; |
+} |
-FIXME: maybe I could set up LineParameters lazily |
-*/ |
-bool SkOpAngle::operator<(const SkOpAngle& rh) const { // this/lh: left-hand; rh: right-hand |
- double y = dy(); |
- double ry = rh.dy(); |
-#if DEBUG_ANGLE |
- SkString bugOut; |
- bugOut.printf("%s _ id=%d segId=%d tStart=%1.9g tEnd=%1.9g" |
- " | id=%d segId=%d tStart=%1.9g tEnd=%1.9g ", funcName, |
- fID, fSegment->debugID(), fSegment->t(fStart), fSegment->t(fEnd), |
- rh.fID, rh.fSegment->debugID(), rh.fSegment->t(rh.fStart), rh.fSegment->t(rh.fEnd)); |
-#endif |
- double y_ry = y * ry; |
- if (y_ry < 0) { // if y's are opposite signs, we can do a quick return |
- return COMPARE_RESULT("1 y * ry < 0", y < 0); |
- } |
- // at this point, both y's must be the same sign, or one (or both) is zero |
- double x = dx(); |
- double rx = rh.dx(); |
- if (x * rx < 0) { // if x's are opposite signs, use y to determine first or second half |
- if (y < 0 && ry < 0) { // if y's are negative, lh x is smaller if positive |
- return COMPARE_RESULT("2 x_rx < 0 && y < 0 ...", x > 0); |
- } |
- if (y >= 0 && ry >= 0) { // if y's are zero or positive, lh x is smaller if negative |
- return COMPARE_RESULT("3 x_rx < 0 && y >= 0 ...", x < 0); |
- } |
- SkASSERT((y == 0) ^ (ry == 0)); // if one y is zero and one is negative, neg y is smaller |
- return COMPARE_RESULT("4 x_rx < 0 && y == 0 ...", y < 0); |
- } |
- // at this point, both x's must be the same sign, or one (or both) is zero |
- if (y_ry == 0) { // if either y is zero |
- if (y + ry < 0) { // if the other y is less than zero, it must be smaller |
- return COMPARE_RESULT("5 y_ry == 0 && y + ry < 0", y < 0); |
- } |
- if (y + ry > 0) { // if a y is greater than zero and an x is positive, non zero is smaller |
- return COMPARE_RESULT("6 y_ry == 0 && y + ry > 0", (x + rx > 0) ^ (y == 0)); |
- } |
- // at this point, both y's are zero, so lines are coincident or one is degenerate |
- SkASSERT(x * rx != 0); // and a degenerate line should haven't gotten this far |
- } |
- // see if either curve can be lengthened before trying the tangent |
- if (fSegment->other(fEnd) != rh.fSegment // tangents not absolutely identical |
- && rh.fSegment->other(rh.fEnd) != fSegment |
- && y != -DBL_EPSILON |
- && ry != -DBL_EPSILON) { // and not intersecting |
- SkOpAngle longer = *this; |
- SkOpAngle rhLonger = rh; |
- if ((longer.lengthen(rh) | rhLonger.lengthen(*this)) // lengthen both |
- && (fUnorderable || !longer.fUnorderable) |
- && (rh.fUnorderable || !rhLonger.fUnorderable)) { |
-#if DEBUG_ANGLE |
- bugOut.prepend(" "); |
-#endif |
- return COMPARE_RESULT("10 longer.lengthen(rh) ...", longer < rhLonger); |
+bool SkOpAngle::checkParallel(const SkOpAngle& rh) const { |
+ SkDVector scratch[2]; |
+ const SkDVector* sweep, * tweep; |
+ if (!fUnorderedSweep) { |
+ sweep = fSweep; |
+ } else { |
+ scratch[0] = fCurvePart[1] - fCurvePart[0]; |
+ sweep = &scratch[0]; |
+ } |
+ if (!rh.fUnorderedSweep) { |
+ tweep = rh.fSweep; |
+ } else { |
+ scratch[1] = rh.fCurvePart[1] - rh.fCurvePart[0]; |
+ tweep = &scratch[1]; |
+ } |
+ double s0xt0 = sweep->crossCheck(*tweep); |
+ if (tangentsDiverge(rh, s0xt0)) { |
+ return s0xt0 < 0; |
+ } |
+ SkDVector m0 = fSegment->dPtAtT(midT()) - fCurvePart[0]; |
+ SkDVector m1 = rh.fSegment->dPtAtT(rh.midT()) - rh.fCurvePart[0]; |
+ double m0xm1 = m0.crossCheck(m1); |
+ if (m0xm1 == 0) { |
+ fUnorderable = true; |
+ rh.fUnorderable = true; |
+ return true; |
+ } |
+ return m0xm1 < 0; |
+} |
+ |
+// the original angle is too short to get meaningful sector information |
+// lengthen it until it is long enough to be meaningful or leave it unset if lengthening it |
+// would cause it to intersect one of the adjacent angles |
+bool SkOpAngle::computeSector() { |
+ if (fComputedSector) { |
+ // FIXME: logically, this should return !fUnorderable, but doing so breaks testQuadratic51 |
+ // -- but in general, this code may not work so this may be the least of problems |
+ // adding the bang fixes testQuads46x in release, however |
+ return fUnorderable; |
+ } |
+ SkASSERT(fSegment->verb() != SkPath::kLine_Verb && small()); |
+ fComputedSector = true; |
+ int step = fStart < fEnd ? 1 : -1; |
+ int limit = step > 0 ? fSegment->count() : -1; |
+ int checkEnd = fEnd; |
+ do { |
+// advance end |
+ const SkOpSpan& span = fSegment->span(checkEnd); |
+ const SkOpSegment* other = span.fOther; |
+ int oCount = other->count(); |
+ for (int oIndex = 0; oIndex < oCount; ++oIndex) { |
+ const SkOpSpan& oSpan = other->span(oIndex); |
+ if (oSpan.fOther != fSegment) { |
+ continue; |
+ } |
+ if (oSpan.fOtherIndex == checkEnd) { |
+ continue; |
+ } |
+ if (!approximately_equal(oSpan.fOtherT, span.fT)) { |
+ continue; |
+ } |
+ goto recomputeSector; |
} |
+ checkEnd += step; |
+ } while (checkEnd != limit); |
+recomputeSector: |
+ if (checkEnd == fEnd || checkEnd - step == fEnd) { |
+ fUnorderable = true; |
+ return false; |
} |
- SkPath::Verb verb = fSegment->verb(); |
- SkPath::Verb rVerb = rh.fSegment->verb(); |
- if (y_ry != 0) { // if they aren't coincident, look for a stable cross product |
- // at this point, y's are the same sign, neither is zero |
- // and x's are the same sign, or one (or both) is zero |
- double x_ry = x * ry; |
- double rx_y = rx * y; |
- if (!fComputed && !rh.fComputed) { |
- if (!SkDLine::NearRay(x, y, rx, ry) && x_ry != rx_y) { |
- return COMPARE_RESULT("7 !fComputed && !rh.fComputed", x_ry < rx_y); |
+ fEnd = checkEnd - step; |
+ setSpans(); |
+ setSector(); |
+ return !fUnorderable; |
+} |
+ |
+// returns -1 if overlaps 0 if no overlap cw 1 if no overlap ccw |
+int SkOpAngle::convexHullOverlaps(const SkOpAngle& rh) const { |
+ const SkDVector* sweep = fSweep; |
+ const SkDVector* tweep = rh.fSweep; |
+ double s0xs1 = sweep[0].crossCheck(sweep[1]); |
+ double s0xt0 = sweep[0].crossCheck(tweep[0]); |
+ double s1xt0 = sweep[1].crossCheck(tweep[0]); |
+ bool tBetweenS = s0xs1 > 0 ? s0xt0 > 0 && s1xt0 < 0 : s0xt0 < 0 && s1xt0 > 0; |
+ double s0xt1 = sweep[0].crossCheck(tweep[1]); |
+ double s1xt1 = sweep[1].crossCheck(tweep[1]); |
+ tBetweenS |= s0xs1 > 0 ? s0xt1 > 0 && s1xt1 < 0 : s0xt1 < 0 && s1xt1 > 0; |
+ double t0xt1 = tweep[0].crossCheck(tweep[1]); |
+ if (tBetweenS) { |
+ return -1; |
+ } |
+ if ((s0xt0 == 0 && s1xt1 == 0) || (s1xt0 == 0 && s0xt1 == 0)) { // s0 to s1 equals t0 to t1 |
+ return -1; |
+ } |
+ bool sBetweenT = t0xt1 > 0 ? s0xt0 < 0 && s0xt1 > 0 : s0xt0 > 0 && s0xt1 < 0; |
+ sBetweenT |= t0xt1 > 0 ? s1xt0 < 0 && s1xt1 > 0 : s1xt0 > 0 && s1xt1 < 0; |
+ if (sBetweenT) { |
+ return -1; |
+ } |
+ // if all of the sweeps are in the same half plane, then the order of any pair is enough |
+ if (s0xt0 >= 0 && s0xt1 >= 0 && s1xt0 >= 0 && s1xt1 >= 0) { |
+ return 0; |
+ } |
+ if (s0xt0 <= 0 && s0xt1 <= 0 && s1xt0 <= 0 && s1xt1 <= 0) { |
+ return 1; |
+ } |
+ // if the outside sweeps are greater than 180 degress: |
+ // first assume the inital tangents are the ordering |
+ // if the midpoint direction matches the inital order, that is enough |
+ SkDVector m0 = fSegment->dPtAtT(midT()) - fCurvePart[0]; |
+ SkDVector m1 = rh.fSegment->dPtAtT(rh.midT()) - rh.fCurvePart[0]; |
+ double m0xm1 = m0.crossCheck(m1); |
+ if (s0xt0 > 0 && m0xm1 > 0) { |
+ return 0; |
+ } |
+ if (s0xt0 < 0 && m0xm1 < 0) { |
+ return 1; |
+ } |
+ if (tangentsDiverge(rh, s0xt0)) { |
+ return s0xt0 < 0; |
+ } |
+ return m0xm1 < 0; |
+} |
+ |
+// OPTIMIZATION: longest can all be either lazily computed here or precomputed in setup |
+double SkOpAngle::distEndRatio(double dist) const { |
+ double longest = 0; |
+ const SkOpSegment& segment = *this->segment(); |
+ int ptCount = SkPathOpsVerbToPoints(segment.verb()); |
+ const SkPoint* pts = segment.pts(); |
+ for (int idx1 = 0; idx1 <= ptCount - 1; ++idx1) { |
+ for (int idx2 = idx1 + 1; idx2 <= ptCount; ++idx2) { |
+ if (idx1 == idx2) { |
+ continue; |
} |
- if (fSide2 == 0 && rh.fSide2 == 0) { |
- return COMPARE_RESULT("7a !fComputed && !rh.fComputed", x_ry < rx_y); |
+ SkDVector v; |
+ v.set(pts[idx2] - pts[idx1]); |
+ double lenSq = v.lengthSquared(); |
+ longest = SkTMax(longest, lenSq); |
+ } |
+ } |
+ return sqrt(longest) / dist; |
+} |
+ |
+bool SkOpAngle::endsIntersect(const SkOpAngle& rh) const { |
+ SkPath::Verb lVerb = fSegment->verb(); |
+ SkPath::Verb rVerb = rh.fSegment->verb(); |
+ int lPts = SkPathOpsVerbToPoints(lVerb); |
+ int rPts = SkPathOpsVerbToPoints(rVerb); |
+ SkDLine rays[] = {{{fCurvePart[0], rh.fCurvePart[rPts]}}, |
+ {{fCurvePart[0], fCurvePart[lPts]}}}; |
+ if (rays[0][1] == rays[1][1]) { |
+ return checkParallel(rh); |
+ } |
+ double smallTs[2] = {-1, -1}; |
+ bool limited[2] = {false, false}; |
+ for (int index = 0; index < 2; ++index) { |
+ const SkOpSegment& segment = index ? *rh.fSegment : *fSegment; |
+ SkIntersections i; |
+ (*CurveIntersectRay[index ? rPts : lPts])(segment.pts(), rays[index], &i); |
+// SkASSERT(i.used() >= 1); |
+ if (i.used() <= 1) { |
+ continue; |
+ } |
+ double tStart = segment.t(index ? rh.fStart : fStart); |
+ double tEnd = segment.t(index ? rh.fEnd : fEnd); |
+ bool testAscends = index ? rh.fStart < rh.fEnd : fStart < fEnd; |
+ double t = testAscends ? 0 : 1; |
+ for (int idx2 = 0; idx2 < i.used(); ++idx2) { |
+ double testT = i[0][idx2]; |
+ if (!approximately_between_orderable(tStart, testT, tEnd)) { |
+ continue; |
} |
- } else { |
- // if the vector was a result of subdividing a curve, see if it is stable |
- bool sloppy1 = x_ry < rx_y; |
- bool sloppy2 = !sloppy1; |
- if ((!fComputed || calcSlop(x, y, rx, ry, &sloppy1)) |
- && (!rh.fComputed || rh.calcSlop(rx, ry, x, y, &sloppy2)) |
- && sloppy1 != sloppy2) { |
- return COMPARE_RESULT("8 CalcSlop(x, y ...", sloppy1); |
+ if (approximately_equal_orderable(tStart, testT)) { |
+ continue; |
} |
+ smallTs[index] = t = testAscends ? SkTMax(t, testT) : SkTMin(t, testT); |
+ limited[index] = approximately_equal_orderable(t, tEnd); |
} |
} |
- if (fSide2 * rh.fSide2 == 0) { // one is zero |
-#if DEBUG_ANGLE |
- if (fSide2 == rh.fSide2 && y_ry) { // both is zero; coincidence was undetected |
- SkDebugf("%s coincidence!\n", __FUNCTION__); |
+#if 0 |
+ if (smallTs[0] < 0 && smallTs[1] < 0) { // if neither ray intersects, do endpoint sort |
+ double m0xm1 = 0; |
+ if (lVerb == SkPath::kLine_Verb) { |
+ SkASSERT(rVerb != SkPath::kLine_Verb); |
+ SkDVector m0 = rays[1][1] - fCurvePart[0]; |
+ SkDPoint endPt; |
+ endPt.set(rh.fSegment->pts()[rh.fStart < rh.fEnd ? rPts : 0]); |
+ SkDVector m1 = endPt - fCurvePart[0]; |
+ m0xm1 = m0.crossCheck(m1); |
} |
+ if (rVerb == SkPath::kLine_Verb) { |
+ SkDPoint endPt; |
+ endPt.set(fSegment->pts()[fStart < fEnd ? lPts : 0]); |
+ SkDVector m0 = endPt - fCurvePart[0]; |
+ SkDVector m1 = rays[0][1] - fCurvePart[0]; |
+ m0xm1 = m0.crossCheck(m1); |
+ } |
+ if (m0xm1 != 0) { |
+ return m0xm1 < 0; |
+ } |
+ } |
#endif |
- return COMPARE_RESULT("9a fSide2 * rh.fSide2 == 0 ...", fSide2 < rh.fSide2); |
- } |
- // at this point, the initial tangent line is nearly coincident |
- // see if edges curl away from each other |
- if (fSide * rh.fSide < 0 && (!approximately_zero(fSide) || !approximately_zero(rh.fSide))) { |
- return COMPARE_RESULT("9b fSide * rh.fSide < 0 ...", fSide < rh.fSide); |
- } |
- if (fUnsortable || rh.fUnsortable) { |
- // even with no solution, return a stable sort |
- return COMPARE_RESULT("11 fUnsortable || rh.fUnsortable", this < &rh); |
- } |
- if ((verb == SkPath::kLine_Verb && approximately_zero(y) && approximately_zero(x)) |
- || (rVerb == SkPath::kLine_Verb |
- && approximately_zero(ry) && approximately_zero(rx))) { |
- // See general unsortable comment below. This case can happen when |
- // one line has a non-zero change in t but no change in x and y. |
- fUnsortable = true; |
- return COMPARE_RESULT("12 verb == SkPath::kLine_Verb ...", this < &rh); |
- } |
- if (fSegment->isTiny(this) || rh.fSegment->isTiny(&rh)) { |
- fUnsortable = true; |
- return COMPARE_RESULT("13 verb == fSegment->isTiny(this) ...", this < &rh); |
- } |
- SkASSERT(verb >= SkPath::kQuad_Verb); |
- SkASSERT(rVerb >= SkPath::kQuad_Verb); |
- // FIXME: until I can think of something better, project a ray from the |
- // end of the shorter tangent to midway between the end points |
- // through both curves and use the resulting angle to sort |
- // FIXME: some of this setup can be moved to set() if it works, or cached if it's expensive |
- double len = fTangentPart.normalSquared(); |
- double rlen = rh.fTangentPart.normalSquared(); |
- SkDLine ray; |
- SkIntersections i, ri; |
- int roots, rroots; |
- bool flip = false; |
- bool useThis; |
- bool leftLessThanRight = fSide > 0; |
- do { |
- useThis = (len < rlen) ^ flip; |
- const SkDCubic& part = useThis ? fCurvePart : rh.fCurvePart; |
- SkPath::Verb partVerb = useThis ? verb : rVerb; |
- ray[0] = partVerb == SkPath::kCubic_Verb && part[0].approximatelyEqual(part[1]) ? |
- part[2] : part[1]; |
- ray[1] = SkDPoint::Mid(part[0], part[SkPathOpsVerbToPoints(partVerb)]); |
- SkASSERT(ray[0] != ray[1]); |
- roots = (i.*CurveRay[SkPathOpsVerbToPoints(verb)])(fSegment->pts(), ray); |
- rroots = (ri.*CurveRay[SkPathOpsVerbToPoints(rVerb)])(rh.fSegment->pts(), ray); |
- } while ((roots == 0 || rroots == 0) && (flip ^= true)); |
- if (roots == 0 || rroots == 0) { |
- // FIXME: we don't have a solution in this case. The interim solution |
- // is to mark the edges as unsortable, exclude them from this and |
- // future computations, and allow the returned path to be fragmented |
- fUnsortable = true; |
- return COMPARE_RESULT("roots == 0 || rroots == 0", this < &rh); |
- } |
- SkASSERT(fSide != 0 && rh.fSide != 0); |
- if (fSide * rh.fSide < 0) { |
- fUnsortable = true; |
- return COMPARE_RESULT("14 fSide * rh.fSide < 0", this < &rh); |
- } |
- SkDPoint lLoc; |
- double best = SK_ScalarInfinity; |
-#if DEBUG_SORT |
- SkDebugf("lh=%d rh=%d use-lh=%d ray={{%1.9g,%1.9g}, {%1.9g,%1.9g}} %c\n", |
- fSegment->debugID(), rh.fSegment->debugID(), useThis, ray[0].fX, ray[0].fY, |
- ray[1].fX, ray[1].fY, "-+"[fSide > 0]); |
-#endif |
- for (int index = 0; index < roots; ++index) { |
- SkDPoint loc = i.pt(index); |
- SkDVector dxy = loc - ray[0]; |
- double dist = dxy.lengthSquared(); |
-#if DEBUG_SORT |
- SkDebugf("best=%1.9g dist=%1.9g loc={%1.9g,%1.9g} dxy={%1.9g,%1.9g}\n", |
- best, dist, loc.fX, loc.fY, dxy.fX, dxy.fY); |
-#endif |
- if (best > dist) { |
- lLoc = loc; |
- best = dist; |
- } |
- } |
- flip = false; |
- SkDPoint rLoc; |
- for (int index = 0; index < rroots; ++index) { |
- rLoc = ri.pt(index); |
- SkDVector dxy = rLoc - ray[0]; |
- double dist = dxy.lengthSquared(); |
-#if DEBUG_SORT |
- SkDebugf("best=%1.9g dist=%1.9g %c=(fSide < 0) rLoc={%1.9g,%1.9g} dxy={%1.9g,%1.9g}\n", |
- best, dist, "><"[fSide < 0], rLoc.fX, rLoc.fY, dxy.fX, dxy.fY); |
-#endif |
- if (best > dist) { |
- flip = true; |
+ bool sRayLonger = false; |
+ SkDVector sCept = {0, 0}; |
+ double sCeptT = -1; |
+ int sIndex = -1; |
+ bool useIntersect = false; |
+ for (int index = 0; index < 2; ++index) { |
+ if (smallTs[index] < 0) { |
+ continue; |
+ } |
+ const SkOpSegment& segment = index ? *rh.fSegment : *fSegment; |
+ const SkDPoint& dPt = segment.dPtAtT(smallTs[index]); |
+ SkDVector cept = dPt - rays[index][0]; |
+ // If this point is on the curve, it should have been detected earlier by ordinary |
+ // curve intersection. This may be hard to determine in general, but for lines, |
+ // the point could be close to or equal to its end, but shouldn't be near the start. |
+ if ((index ? lPts : rPts) == 1) { |
+ SkDVector total = rays[index][1] - rays[index][0]; |
+ if (cept.lengthSquared() * 2 < total.lengthSquared()) { |
+ continue; |
+ } |
+ } |
+ SkDVector end = rays[index][1] - rays[index][0]; |
+ if (cept.fX * end.fX < 0 || cept.fY * end.fY < 0) { |
+ continue; |
+ } |
+ double rayDist = cept.length(); |
+ double endDist = end.length(); |
+ bool rayLonger = rayDist > endDist; |
+ if (limited[0] && limited[1] && rayLonger) { |
+ useIntersect = true; |
+ sRayLonger = rayLonger; |
+ sCept = cept; |
+ sCeptT = smallTs[index]; |
+ sIndex = index; |
+ break; |
+ } |
+ double delta = fabs(rayDist - endDist); |
+ double minX, minY, maxX, maxY; |
+ minX = minY = SK_ScalarInfinity; |
+ maxX = maxY = -SK_ScalarInfinity; |
+ const SkDCubic& curve = index ? rh.fCurvePart : fCurvePart; |
+ int ptCount = index ? rPts : lPts; |
+ for (int idx2 = 0; idx2 <= ptCount; ++idx2) { |
+ minX = SkTMin(minX, curve[idx2].fX); |
+ minY = SkTMin(minY, curve[idx2].fY); |
+ maxX = SkTMax(maxX, curve[idx2].fX); |
+ maxY = SkTMax(maxY, curve[idx2].fY); |
+ } |
+ double maxWidth = SkTMax(maxX - minX, maxY - minY); |
+ delta /= maxWidth; |
+ if (delta > 1e-4 && (useIntersect ^= true)) { // FIXME: move this magic number |
+ sRayLonger = rayLonger; |
+ sCept = cept; |
+ sCeptT = smallTs[index]; |
+ sIndex = index; |
+ } |
+ } |
+ if (useIntersect) { |
+ const SkDCubic& curve = sIndex ? rh.fCurvePart : fCurvePart; |
+ const SkOpSegment& segment = sIndex ? *rh.fSegment : *fSegment; |
+ double tStart = segment.t(sIndex ? rh.fStart : fStart); |
+ SkDVector mid = segment.dPtAtT(tStart + (sCeptT - tStart) / 2) - curve[0]; |
+ double septDir = mid.crossCheck(sCept); |
+ if (!septDir) { |
+ return checkParallel(rh); |
+ } |
+ return sRayLonger ^ (sIndex == 0) ^ (septDir < 0); |
+ } else { |
+ return checkParallel(rh); |
+ } |
+} |
+ |
+// Most of the time, the first one can be found trivially by detecting the smallest sector value. |
+// If all angles have the same sector value, actual sorting is required. |
+const SkOpAngle* SkOpAngle::findFirst() const { |
+ const SkOpAngle* best = this; |
+ int bestStart = SkTMin(fSectorStart, fSectorEnd); |
+ const SkOpAngle* angle = this; |
+ while ((angle = angle->fNext) != this) { |
+ int angleEnd = SkTMax(angle->fSectorStart, angle->fSectorEnd); |
+ if (angleEnd < bestStart) { |
+ return angle; // we wrapped around |
+ } |
+ int angleStart = SkTMin(angle->fSectorStart, angle->fSectorEnd); |
+ if (bestStart > angleStart) { |
+ best = angle; |
+ bestStart = angleStart; |
+ } |
+ } |
+ // back up to the first possible angle |
+ const SkOpAngle* firstBest = best; |
+ angle = best; |
+ int bestEnd = SkTMax(best->fSectorStart, best->fSectorEnd); |
+ while ((angle = angle->previous()) != firstBest) { |
+ if (angle->fStop) { |
break; |
} |
+ int angleStart = SkTMin(angle->fSectorStart, angle->fSectorEnd); |
+ // angles that are smaller by one aren't necessary better, since the larger may be a line |
+ // and the smaller may be a curve that curls to the other side of the line. |
+ if (bestEnd + 1 < angleStart) { |
+ return best; |
+ } |
+ best = angle; |
+ bestEnd = SkTMax(angle->fSectorStart, angle->fSectorEnd); |
+ } |
+ // in the case where all angles are nearly in the same sector, check the order to find the best |
+ firstBest = best; |
+ angle = best; |
+ do { |
+ angle = angle->fNext; |
+ if (angle->fStop) { |
+ return firstBest; |
+ } |
+ bool orderable = best->orderable(*angle); // note: may return an unorderable angle |
+ if (orderable == 0) { |
+ return angle; |
+ } |
+ best = angle; |
+ } while (angle != firstBest); |
+ // if the angles are equally ordered, fall back on the initial tangent |
+ bool foundBelow = false; |
+ while ((angle = angle->fNext)) { |
+ SkDVector scratch[2]; |
+ const SkDVector* sweep; |
+ if (!angle->fUnorderedSweep) { |
+ sweep = angle->fSweep; |
+ } else { |
+ scratch[0] = angle->fCurvePart[1] - angle->fCurvePart[0]; |
+ sweep = &scratch[0]; |
+ } |
+ bool isAbove = sweep->fY <= 0; |
+ if (isAbove && foundBelow) { |
+ return angle; |
+ } |
+ foundBelow |= !isAbove; |
+ if (angle == firstBest) { |
+ return NULL; // should not loop around |
+ } |
+ } |
+ SkASSERT(0); // should never get here |
+ return NULL; |
+} |
+ |
+/* y<0 y==0 y>0 x<0 x==0 x>0 xy<0 xy==0 xy>0 |
+ 0 x x x |
+ 1 x x x |
+ 2 x x x |
+ 3 x x x |
+ 4 x x x |
+ 5 x x x |
+ 6 x x x |
+ 7 x x x |
+ 8 x x x |
+ 9 x x x |
+ 10 x x x |
+ 11 x x x |
+ 12 x x x |
+ 13 x x x |
+ 14 x x x |
+ 15 x x x |
+*/ |
+int SkOpAngle::findSector(SkPath::Verb verb, double x, double y) const { |
+ double absX = fabs(x); |
+ double absY = fabs(y); |
+ double xy = SkPath::kLine_Verb == verb || !AlmostEqualUlps(absX, absY) ? absX - absY : 0; |
+ // If there are four quadrants and eight octants, and since the Latin for sixteen is sedecim, |
+ // one could coin the term sedecimant for a space divided into 16 sections. |
+ // http://english.stackexchange.com/questions/133688/word-for-something-partitioned-into-16-parts |
+ static const int sedecimant[3][3][3] = { |
+ // y<0 y==0 y>0 |
+ // x<0 x==0 x>0 x<0 x==0 x>0 x<0 x==0 x>0 |
+ {{ 4, 3, 2}, { 7, -1, 15}, {10, 11, 12}}, // abs(x) < abs(y) |
+ {{ 5, -1, 1}, {-1, -1, -1}, { 9, -1, 13}}, // abs(x) == abs(y) |
+ {{ 6, 3, 0}, { 7, -1, 15}, { 8, 11, 14}}, // abs(x) > abs(y) |
+ }; |
+ int sector = sedecimant[(xy >= 0) + (xy > 0)][(y >= 0) + (y > 0)][(x >= 0) + (x > 0)] * 2 + 1; |
+ SkASSERT(SkPath::kLine_Verb == verb || sector >= 0); |
+ return sector; |
+} |
+ |
+// OPTIMIZE: if this loops to only one other angle, after first compare fails, insert on other side |
+// OPTIMIZE: return where insertion succeeded. Then, start next insertion on opposite side |
+void SkOpAngle::insert(SkOpAngle* angle) { |
+ if (angle->fNext) { |
+ if (loopCount() >= angle->loopCount()) { |
+ if (!merge(angle)) { |
+ return; |
+ } |
+ } else if (fNext) { |
+ if (!angle->merge(this)) { |
+ return; |
+ } |
+ } else { |
+ angle->insert(this); |
+ } |
+ return; |
} |
- if (flip) { |
- leftLessThanRight = !leftLessThanRight; |
+ bool singleton = NULL == fNext; |
+ if (singleton) { |
+ fNext = this; |
} |
- return COMPARE_RESULT("15 leftLessThanRight", leftLessThanRight); |
+ SkOpAngle* next = fNext; |
+ if (next->fNext == this) { |
+ if (singleton || angle->after(this)) { |
+ this->fNext = angle; |
+ angle->fNext = next; |
+ } else { |
+ next->fNext = angle; |
+ angle->fNext = this; |
+ } |
+ debugValidateNext(); |
+ return; |
+ } |
+ SkOpAngle* last = this; |
+ do { |
+ SkASSERT(last->fNext == next); |
+ if (angle->after(last)) { |
+ last->fNext = angle; |
+ angle->fNext = next; |
+ debugValidateNext(); |
+ return; |
+ } |
+ last = next; |
+ next = next->fNext; |
+ if (last == this && next->fUnorderable) { |
+ fUnorderable = true; |
+ return; |
+ } |
+ SkASSERT(last != this); |
+ } while (true); |
} |
bool SkOpAngle::isHorizontal() const { |
- return dy() == 0 && fSegment->verb() == SkPath::kLine_Verb; |
+ return !fIsCurve && fSweep[0].fY == 0; |
} |
-// lengthen cannot cross opposite angle |
-bool SkOpAngle::lengthen(const SkOpAngle& opp) { |
- if (fSegment->other(fEnd) == opp.fSegment) { |
- return false; |
+SkOpSpan* SkOpAngle::lastMarked() const { |
+ if (fLastMarked) { |
+ if (fLastMarked->fChased) { |
+ return NULL; |
+ } |
+ fLastMarked->fChased = true; |
} |
- // FIXME: make this a while loop instead and make it as large as possible? |
- int newEnd = fEnd; |
- if (fStart < fEnd ? ++newEnd < fSegment->count() : --newEnd >= 0) { |
- fEnd = newEnd; |
- setSpans(); |
- return true; |
+ return fLastMarked; |
+} |
+ |
+int SkOpAngle::loopCount() const { |
+ int count = 0; |
+ const SkOpAngle* first = this; |
+ const SkOpAngle* next = this; |
+ do { |
+ next = next->fNext; |
+ ++count; |
+ } while (next && next != first); |
+ return count; |
+} |
+ |
+// OPTIMIZATION: can this be done better in after when angles are sorted? |
+void SkOpAngle::markStops() { |
+ SkOpAngle* angle = this; |
+ int lastEnd = SkTMax(fSectorStart, fSectorEnd); |
+ do { |
+ angle = angle->fNext; |
+ int angleStart = SkTMin(angle->fSectorStart, angle->fSectorEnd); |
+ // angles that are smaller by one aren't necessary better, since the larger may be a line |
+ // and the smaller may be a curve that curls to the other side of the line. |
+ if (lastEnd + 1 < angleStart) { |
+ angle->fStop = true; |
+ } |
+ lastEnd = SkTMax(angle->fSectorStart, angle->fSectorEnd); |
+ } while (angle != this); |
+} |
+ |
+bool SkOpAngle::merge(SkOpAngle* angle) { |
+ SkASSERT(fNext); |
+ SkASSERT(angle->fNext); |
+ SkOpAngle* working = angle; |
+ do { |
+ if (this == working) { |
+ return false; |
+ } |
+ working = working->fNext; |
+ } while (working != angle); |
+ do { |
+ SkOpAngle* next = working->fNext; |
+ working->fNext = NULL; |
+ insert(working); |
+ working = next; |
+ } while (working != angle); |
+ // it's likely that a pair of the angles are unorderable |
+#if DEBUG_ANGLE |
+ SkOpAngle* last = angle; |
+ working = angle->fNext; |
+ do { |
+ SkASSERT(last->fNext == working); |
+ last->fNext = working->fNext; |
+ SkASSERT(working->after(last)); |
+ last->fNext = working; |
+ last = working; |
+ working = working->fNext; |
+ } while (last != angle); |
+#endif |
+ debugValidateNext(); |
+ return true; |
+} |
+ |
+double SkOpAngle::midT() const { |
+ return (fSegment->t(fStart) + fSegment->t(fEnd)) / 2; |
+} |
+ |
+bool SkOpAngle::oppositePlanes(const SkOpAngle& rh) const { |
+ int startSpan = abs(rh.fSectorStart - fSectorStart); |
+ return startSpan >= 8; |
+} |
+ |
+bool SkOpAngle::orderable(const SkOpAngle& rh) const { |
+ int result; |
+ if (!fIsCurve) { |
+ if (!rh.fIsCurve) { |
+ double leftX = fTangentHalf.dx(); |
+ double leftY = fTangentHalf.dy(); |
+ double rightX = rh.fTangentHalf.dx(); |
+ double rightY = rh.fTangentHalf.dy(); |
+ double x_ry = leftX * rightY; |
+ double rx_y = rightX * leftY; |
+ if (x_ry == rx_y) { |
+ if (leftX * rightX < 0 || leftY * rightY < 0) { |
+ return true; // exactly 180 degrees apart |
+ } |
+ goto unorderable; |
+ } |
+ SkASSERT(x_ry != rx_y); // indicates an undetected coincidence -- worth finding earlier |
+ return x_ry < rx_y; |
+ } |
+ if ((result = allOnOneSide(rh)) >= 0) { |
+ return result; |
+ } |
+ if (fUnorderable || approximately_zero(rh.fSide)) { |
+ goto unorderable; |
+ } |
+ } else if (!rh.fIsCurve) { |
+ if ((result = rh.allOnOneSide(*this)) >= 0) { |
+ return !result; |
+ } |
+ if (rh.fUnorderable || approximately_zero(fSide)) { |
+ goto unorderable; |
+ } |
} |
- return false; |
+ if ((result = convexHullOverlaps(rh)) >= 0) { |
+ return result; |
+ } |
+ return endsIntersect(rh); |
+unorderable: |
+ fUnorderable = true; |
+ rh.fUnorderable = true; |
+ return true; |
+} |
+ |
+// OPTIMIZE: if this shows up in a profile, add a previous pointer |
+// as is, this should be rarely called |
+SkOpAngle* SkOpAngle::previous() const { |
+ SkOpAngle* last = fNext; |
+ do { |
+ SkOpAngle* next = last->fNext; |
+ if (next == this) { |
+ return last; |
+ } |
+ last = next; |
+ } while (true); |
} |
void SkOpAngle::set(const SkOpSegment* segment, int start, int end) { |
+#if DEBUG_ANGLE |
+ fID = 0; |
+#endif |
fSegment = segment; |
fStart = start; |
fEnd = end; |
+ fNext = NULL; |
+ fComputeSector = fComputedSector = false; |
+ fStop = false; |
setSpans(); |
+ setSector(); |
+} |
+ |
+void SkOpAngle::setCurveHullSweep() { |
+ fUnorderedSweep = false; |
+ fSweep[0] = fCurvePart[1] - fCurvePart[0]; |
+ if (SkPath::kLine_Verb == fSegment->verb()) { |
+ fSweep[1] = fSweep[0]; |
+ return; |
+ } |
+ fSweep[1] = fCurvePart[2] - fCurvePart[0]; |
+ if (SkPath::kCubic_Verb != fSegment->verb()) { |
+ if (!fSweep[0].fX && !fSweep[0].fY) { |
+ fSweep[0] = fSweep[1]; |
+ } |
+ return; |
+ } |
+ SkDVector thirdSweep = fCurvePart[3] - fCurvePart[0]; |
+ if (fSweep[0].fX == 0 && fSweep[0].fY == 0) { |
+ fSweep[0] = fSweep[1]; |
+ fSweep[1] = thirdSweep; |
+ if (fSweep[0].fX == 0 && fSweep[0].fY == 0) { |
+ fSweep[0] = fSweep[1]; |
+ fCurvePart[1] = fCurvePart[3]; |
+ fIsCurve = false; |
+ } |
+ return; |
+ } |
+ double s1x3 = fSweep[0].crossCheck(thirdSweep); |
+ double s3x2 = thirdSweep.crossCheck(fSweep[1]); |
+ if (s1x3 * s3x2 >= 0) { // if third vector is on or between first two vectors |
+ return; |
+ } |
+ double s2x1 = fSweep[1].crossCheck(fSweep[0]); |
+ // FIXME: If the sweep of the cubic is greater than 180 degrees, we're in trouble |
+ // probably such wide sweeps should be artificially subdivided earlier so that never happens |
+ SkASSERT(s1x3 * s2x1 < 0 || s1x3 * s3x2 < 0); |
+ if (s3x2 * s2x1 < 0) { |
+ SkASSERT(s2x1 * s1x3 > 0); |
+ fSweep[0] = fSweep[1]; |
+ fUnorderedSweep = true; |
+ } |
+ fSweep[1] = thirdSweep; |
+} |
+ |
+void SkOpAngle::setSector() { |
+ SkPath::Verb verb = fSegment->verb(); |
+ if (SkPath::kLine_Verb != verb && small()) { |
+ fSectorStart = fSectorEnd = -1; |
+ fSectorMask = 0; |
+ fComputeSector = true; // can't determine sector until segment length can be found |
+ return; |
+ } |
+ fSectorStart = findSector(verb, fSweep[0].fX, fSweep[0].fY); |
+ if (!fIsCurve) { // if it's a line or line-like, note that both sectors are the same |
+ SkASSERT(fSectorStart >= 0); |
+ fSectorEnd = fSectorStart; |
+ fSectorMask = 1 << fSectorStart; |
+ return; |
+ } |
+ SkASSERT(SkPath::kLine_Verb != verb); |
+ fSectorEnd = findSector(verb, fSweep[1].fX, fSweep[1].fY); |
+ if (fSectorEnd == fSectorStart) { |
+ SkASSERT((fSectorStart & 3) != 3); // if the sector has no span, it can't be an exact angle |
+ fSectorMask = 1 << fSectorStart; |
+ return; |
+ } |
+ bool crossesZero = checkCrossesZero(); |
+ int start = SkTMin(fSectorStart, fSectorEnd); |
+ bool curveBendsCCW = (fSectorStart == start) ^ crossesZero; |
+ // bump the start and end of the sector span if they are on exact compass points |
+ if ((fSectorStart & 3) == 3) { |
+ fSectorStart = (fSectorStart + (curveBendsCCW ? 1 : 31)) & 0x1f; |
+ } |
+ if ((fSectorEnd & 3) == 3) { |
+ fSectorEnd = (fSectorEnd + (curveBendsCCW ? 31 : 1)) & 0x1f; |
+ } |
+ crossesZero = checkCrossesZero(); |
+ start = SkTMin(fSectorStart, fSectorEnd); |
+ int end = SkTMax(fSectorStart, fSectorEnd); |
+ if (!crossesZero) { |
+ fSectorMask = (unsigned) -1 >> (31 - end + start) << start; |
+ } else { |
+ fSectorMask = (unsigned) -1 >> (31 - start) | (-1 << end); |
+ } |
} |
void SkOpAngle::setSpans() { |
fUnorderable = fSegment->isTiny(this); |
fLastMarked = NULL; |
- fUnsortable = false; |
const SkPoint* pts = fSegment->pts(); |
- if (fSegment->verb() != SkPath::kLine_Verb) { |
- fComputed = fSegment->subDivide(fStart, fEnd, &fCurvePart); |
- fSegment->subDivide(fStart, fStart < fEnd ? fSegment->count() - 1 : 0, &fCurveHalf); |
- } |
- // FIXME: slight errors in subdivision cause sort trouble later on. As an experiment, try |
- // rounding the curve part to float precision here |
- // fCurvePart.round(fSegment->verb()); |
- switch (fSegment->verb()) { |
+ SkDEBUGCODE(fCurvePart[2].fX = fCurvePart[2].fY = fCurvePart[3].fX = fCurvePart[3].fY |
+ = SK_ScalarNaN); |
+ fSegment->subDivide(fStart, fEnd, &fCurvePart); |
+ setCurveHullSweep(); |
+ const SkPath::Verb verb = fSegment->verb(); |
+ if (verb != SkPath::kLine_Verb |
+ && !(fIsCurve = fSweep[0].crossCheck(fSweep[1]) != 0)) { |
+ SkDLine lineHalf; |
+ lineHalf[0].set(fCurvePart[0].asSkPoint()); |
+ lineHalf[1].set(fCurvePart[SkPathOpsVerbToPoints(verb)].asSkPoint()); |
+ fTangentHalf.lineEndPoints(lineHalf); |
+ fSide = 0; |
+ } |
+ switch (verb) { |
case SkPath::kLine_Verb: { |
SkASSERT(fStart != fEnd); |
- fCurvePart[0].set(pts[fStart > fEnd]); |
- fCurvePart[1].set(pts[fStart < fEnd]); |
- fComputed = false; |
- // OPTIMIZATION: for pure line compares, we never need fTangentPart.c |
- fTangentPart.lineEndPoints(*SkTCast<SkDLine*>(&fCurvePart)); |
+ const SkPoint& cP1 = pts[fStart < fEnd]; |
+ SkDLine lineHalf; |
+ lineHalf[0].set(fSegment->span(fStart).fPt); |
+ lineHalf[1].set(cP1); |
+ fTangentHalf.lineEndPoints(lineHalf); |
fSide = 0; |
- fSide2 = 0; |
- } break; |
+ fIsCurve = false; |
+ } return; |
case SkPath::kQuad_Verb: { |
- fSide2 = -fTangentHalf.quadPart(*SkTCast<SkDQuad*>(&fCurveHalf)); |
- SkDQuad& quad = *SkTCast<SkDQuad*>(&fCurvePart); |
- fTangentPart.quadEndPoints(quad); |
- fSide = -fTangentPart.pointDistance(fCurvePart[2]); // not normalized -- compare sign only |
- if (fComputed && dx() > 0 && approximately_zero(dy())) { |
- SkDCubic origCurve; // can't use segment's curve in place since it may be flipped |
- int last = fSegment->count() - 1; |
- fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve); |
- SkLineParameters origTan; |
- origTan.quadEndPoints(*SkTCast<SkDQuad*>(&origCurve)); |
- if (origTan.dx() <= 0 |
- || (dy() != origTan.dy() && dy() * origTan.dy() <= 0)) { // signs match? |
- fUnorderable = true; |
- return; |
- } |
- } |
+ SkLineParameters tangentPart; |
+ SkDQuad& quad2 = *SkTCast<SkDQuad*>(&fCurvePart); |
+ (void) tangentPart.quadEndPoints(quad2); |
+ fSide = -tangentPart.pointDistance(fCurvePart[2]); // not normalized -- compare sign only |
} break; |
case SkPath::kCubic_Verb: { |
- double startT = fSegment->t(fStart); |
- fSide2 = -fTangentHalf.cubicPart(fCurveHalf); |
- fTangentPart.cubicEndPoints(fCurvePart); |
+ SkLineParameters tangentPart; |
+ (void) tangentPart.cubicPart(fCurvePart); |
+ fSide = -tangentPart.pointDistance(fCurvePart[3]); |
double testTs[4]; |
// OPTIMIZATION: keep inflections precomputed with cubic segment? |
int testCount = SkDCubic::FindInflections(pts, testTs); |
+ double startT = fSegment->t(fStart); |
double endT = fSegment->t(fEnd); |
double limitT = endT; |
int index; |
for (index = 0; index < testCount; ++index) { |
- if (!between(startT, testTs[index], limitT)) { |
+ if (!::between(startT, testTs[index], limitT)) { |
testTs[index] = -1; |
} |
} |
@@ -354,82 +992,56 @@ void SkOpAngle::setSpans() { |
} |
// OPTIMIZE: could avoid call for t == startT, endT |
SkDPoint pt = dcubic_xy_at_t(pts, testT); |
- double testSide = fTangentPart.pointDistance(pt); |
+ SkLineParameters tangentPart; |
+ tangentPart.cubicEndPoints(fCurvePart); |
+ double testSide = tangentPart.pointDistance(pt); |
if (fabs(bestSide) < fabs(testSide)) { |
bestSide = testSide; |
} |
} |
fSide = -bestSide; // compare sign only |
- SkASSERT(fSide == 0 || fSide2 != 0); |
- if (fComputed && dx() > 0 && approximately_zero(dy())) { |
- SkDCubic origCurve; // can't use segment's curve in place since it may be flipped |
- int last = fSegment->count() - 1; |
- fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve); |
- SkDCubicPair split = origCurve.chopAt(startT); |
- SkLineParameters splitTan; |
- splitTan.cubicEndPoints(fStart < fEnd ? split.second() : split.first()); |
- if (splitTan.dx() <= 0) { |
- fUnorderable = true; |
- fUnsortable = fSegment->isTiny(this); |
- return; |
- } |
- // if one is < 0 and the other is >= 0 |
- if (dy() * splitTan.dy() < 0) { |
- fUnorderable = true; |
- fUnsortable = fSegment->isTiny(this); |
- return; |
- } |
- } |
} break; |
default: |
SkASSERT(0); |
} |
- if ((fUnsortable = approximately_zero(dx()) && approximately_zero(dy()))) { |
- return; |
- } |
- if (fSegment->verb() == SkPath::kLine_Verb) { |
- return; |
- } |
- SkASSERT(fStart != fEnd); |
- int smaller = SkMin32(fStart, fEnd); |
- int larger = SkMax32(fStart, fEnd); |
- while (smaller < larger && fSegment->span(smaller).fTiny) { |
- ++smaller; |
- } |
- if (precisely_equal(fSegment->span(smaller).fT, fSegment->span(larger).fT)) { |
- #if DEBUG_UNSORTABLE |
- SkPoint iPt = fSegment->xyAtT(fStart); |
- SkPoint ePt = fSegment->xyAtT(fEnd); |
- SkDebugf("%s all tiny unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__, |
- fStart, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY); |
- #endif |
- fUnsortable = true; |
- return; |
- } |
- fUnsortable = fStart < fEnd ? fSegment->span(smaller).fUnsortableStart |
- : fSegment->span(larger).fUnsortableEnd; |
-#if DEBUG_UNSORTABLE |
- if (fUnsortable) { |
- SkPoint iPt = fSegment->xyAtT(smaller); |
- SkPoint ePt = fSegment->xyAtT(larger); |
- SkDebugf("%s unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__, |
- smaller, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY); |
+} |
+ |
+bool SkOpAngle::small() const { |
+ int min = SkMin32(fStart, fEnd); |
+ int max = SkMax32(fStart, fEnd); |
+ for (int index = min; index < max; ++index) { |
+ const SkOpSpan& mSpan = fSegment->span(index); |
+ if (!mSpan.fSmall) { |
+ return false; |
+ } |
} |
-#endif |
- return; |
+ return true; |
} |
-#ifdef SK_DEBUG |
-void SkOpAngle::dump() const { |
- const SkOpSpan& spanStart = fSegment->span(fStart); |
- const SkOpSpan& spanEnd = fSegment->span(fEnd); |
- const SkOpSpan& spanMin = fStart < fEnd ? spanStart : spanEnd; |
- SkDebugf("id=%d (%1.9g,%1.9g) start=%d (%1.9g) end=%d (%1.9g) sumWind=", |
- fSegment->debugID(), fSegment->xAtT(fStart), fSegment->yAtT(fStart), |
- fStart, spanStart.fT, fEnd, spanEnd.fT); |
- SkPathOpsDebug::WindingPrintf(spanMin.fWindSum); |
- SkDebugf(" oppWind="); |
- SkPathOpsDebug::WindingPrintf(spanMin.fOppSum), |
- SkDebugf(" done=%d\n", spanMin.fDone); |
+bool SkOpAngle::tangentsDiverge(const SkOpAngle& rh, double s0xt0) const { |
+ if (s0xt0 == 0) { |
+ return false; |
+ } |
+ // if the ctrl tangents are not nearly parallel, use them |
+ // solve for opposite direction displacement scale factor == m |
+ // initial dir = v1.cross(v2) == v2.x * v1.y - v2.y * v1.x |
+ // displacement of q1[1] : dq1 = { -m * v1.y, m * v1.x } + q1[1] |
+ // straight angle when : v2.x * (dq1.y - q1[0].y) == v2.y * (dq1.x - q1[0].x) |
+ // v2.x * (m * v1.x + v1.y) == v2.y * (-m * v1.y + v1.x) |
+ // - m * (v2.x * v1.x + v2.y * v1.y) == v2.x * v1.y - v2.y * v1.x |
+ // m = (v2.y * v1.x - v2.x * v1.y) / (v2.x * v1.x + v2.y * v1.y) |
+ // m = v1.cross(v2) / v1.dot(v2) |
+ const SkDVector* sweep = fSweep; |
+ const SkDVector* tweep = rh.fSweep; |
+ double s0dt0 = sweep[0].dot(tweep[0]); |
+ if (!s0dt0) { |
+ return true; |
+ } |
+ SkASSERT(s0dt0 != 0); |
+ double m = s0xt0 / s0dt0; |
+ double sDist = sweep[0].length() * m; |
+ double tDist = tweep[0].length() * m; |
+ bool useS = fabs(sDist) < fabs(tDist); |
+ double mFactor = fabs(useS ? distEndRatio(sDist) : rh.distEndRatio(tDist)); |
+ return mFactor < 5000; // empirically found limit |
} |
-#endif |