| /* |
| * Copyright 2012 Google Inc. |
| * |
| * Use of this source code is governed by a BSD-style license that can be |
| * found in the LICENSE file. |
| */ |
| #include "SkIntersections.h" |
| #include "SkOpAngle.h" |
| #include "SkOpSegment.h" |
| #include "SkPathOpsCurve.h" |
| #include "SkTSort.h" |
| |
| #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()); |
| return compare; |
| } |
| |
| #define COMPARE_RESULT(append, compare) CompareResult(&bugOut, append, compare) |
| #else |
| #define COMPARE_RESULT(append, compare) compare |
| #endif |
| |
| 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; |
| int exponent; |
| (void) frexp(length, &exponent); |
| double epsilon = ldexp(FLT_EPSILON, exponent); |
| SkPath::Verb verb = fSegment->verb(); |
| SkASSERT(verb == SkPath::kQuad_Verb || verb == SkPath::kCubic_Verb); |
| // FIXME: the quad and cubic factors are made up ; determine actual values |
| double slop = verb == SkPath::kQuad_Verb ? 4 * epsilon : 512 * epsilon; |
| double xSlop = slop; |
| double ySlop = x * y < 0 ? -xSlop : xSlop; // OPTIMIZATION: use copysign / _copysign ? |
| double x1 = x - xSlop; |
| double y1 = y + ySlop; |
| double x_ry1 = x1 * ry; |
| double rx_y1 = rx * y1; |
| *result = x_ry1 < rx_y1; |
| double x2 = x + xSlop; |
| double y2 = y - ySlop; |
| double x_ry2 = x2 * ry; |
| double rx_y2 = rx * y2; |
| bool less2 = x_ry2 < rx_y2; |
| 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 |
| |
| 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); |
| } |
| } |
| 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); |
| } |
| if (fSide2 == 0 && rh.fSide2 == 0) { |
| return COMPARE_RESULT("7a !fComputed && !rh.fComputed", x_ry < rx_y); |
| } |
| } 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 (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__); |
| } |
| #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; |
| break; |
| } |
| } |
| if (flip) { |
| leftLessThanRight = !leftLessThanRight; |
| } |
| return COMPARE_RESULT("15 leftLessThanRight", leftLessThanRight); |
| } |
| |
| bool SkOpAngle::isHorizontal() const { |
| return dy() == 0 && fSegment->verb() == SkPath::kLine_Verb; |
| } |
| |
| // lengthen cannot cross opposite angle |
| bool SkOpAngle::lengthen(const SkOpAngle& opp) { |
| if (fSegment->other(fEnd) == opp.fSegment) { |
| return false; |
| } |
| // 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 false; |
| } |
| |
| void SkOpAngle::set(const SkOpSegment* segment, int start, int end) { |
| fSegment = segment; |
| fStart = start; |
| fEnd = end; |
| setSpans(); |
| } |
| |
| 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()) { |
| 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)); |
| fSide = 0; |
| fSide2 = 0; |
| } break; |
| 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; |
| } |
| } |
| } break; |
| case SkPath::kCubic_Verb: { |
| double startT = fSegment->t(fStart); |
| fSide2 = -fTangentHalf.cubicPart(fCurveHalf); |
| fTangentPart.cubicEndPoints(fCurvePart); |
| double testTs[4]; |
| // OPTIMIZATION: keep inflections precomputed with cubic segment? |
| int testCount = SkDCubic::FindInflections(pts, testTs); |
| double endT = fSegment->t(fEnd); |
| double limitT = endT; |
| int index; |
| for (index = 0; index < testCount; ++index) { |
| if (!between(startT, testTs[index], limitT)) { |
| testTs[index] = -1; |
| } |
| } |
| testTs[testCount++] = startT; |
| testTs[testCount++] = endT; |
| SkTQSort<double>(testTs, &testTs[testCount - 1]); |
| double bestSide = 0; |
| int testCases = (testCount << 1) - 1; |
| index = 0; |
| while (testTs[index] < 0) { |
| ++index; |
| } |
| index <<= 1; |
| for (; index < testCases; ++index) { |
| int testIndex = index >> 1; |
| double testT = testTs[testIndex]; |
| if (index & 1) { |
| testT = (testT + testTs[testIndex + 1]) / 2; |
| } |
| // OPTIMIZE: could avoid call for t == startT, endT |
| SkDPoint pt = dcubic_xy_at_t(pts, testT); |
| double testSide = fTangentPart.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); |
| } |
| #endif |
| return; |
| } |
| |
| #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); |
| } |
| #endif |
