121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com/* 221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * Copyright 2012 Google Inc. 321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * 421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * Use of this source code is governed by a BSD-style license that can be 521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * found in the LICENSE file. 621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com */ 721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#include "SkIntersections.h" 821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#include "SkOpAngle.h" 93bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com#include "SkOpSegment.h" 1021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#include "SkPathOpsCurve.h" 11d4a6daad3bb2b40cc215fa0e8522873154c5a59bcommit-bot@chromium.org#include "SkTSort.h" 1221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 133bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com#if DEBUG_ANGLE 143bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com#include "SkString.h" 153bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com 163bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.comstatic const char funcName[] = "SkOpSegment::operator<"; 173bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.comstatic const int bugChar = strlen(funcName) + 1; 183bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com#endif 193bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com 203bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com/* Angles are sorted counterclockwise. The smallest angle has a positive x and the smallest 213bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com positive y. The largest angle has a positive x and a zero y. */ 223bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com 233bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com#if DEBUG_ANGLE 243bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com static bool CompareResult(SkString* bugOut, const char* append, bool compare) { 2546e3086c1837da6ab13b48f852bd7bfbab3dc44fcaryclark@google.com bugOut->appendf("%s", append); 263bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com bugOut->writable_str()[bugChar] = "><"[compare]; 273bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkDebugf("%s\n", bugOut->c_str()); 283bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return compare; 293bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 303bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com 313bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com #define COMPARE_RESULT(append, compare) CompareResult(&bugOut, append, compare) 323bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com#else 3365e1cb6c52fd6cf5d4df14a9f258df13aa3facfcskia.committer@gmail.com #define COMPARE_RESULT(append, compare) compare 342274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com#endif 352274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com 363bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.combool SkOpAngle::calcSlop(double x, double y, double rx, double ry, bool* result) const{ 373bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com double absX = fabs(x); 383bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com double absY = fabs(y); 393bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com double length = absX < absY ? absX / 2 + absY : absX + absY / 2; 403bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com int exponent; 413bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com (void) frexp(length, &exponent); 423bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com double epsilon = ldexp(FLT_EPSILON, exponent); 433bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkPath::Verb verb = fSegment->verb(); 443bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkASSERT(verb == SkPath::kQuad_Verb || verb == SkPath::kCubic_Verb); 453bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com // FIXME: the quad and cubic factors are made up ; determine actual values 463bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com double slop = verb == SkPath::kQuad_Verb ? 4 * epsilon : 512 * epsilon; 473bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com double xSlop = slop; 483bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com double ySlop = x * y < 0 ? -xSlop : xSlop; // OPTIMIZATION: use copysign / _copysign ? 493bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com double x1 = x - xSlop; 503bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com double y1 = y + ySlop; 513bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com double x_ry1 = x1 * ry; 523bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com double rx_y1 = rx * y1; 533bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com *result = x_ry1 < rx_y1; 543bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com double x2 = x + xSlop; 553bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com double y2 = y - ySlop; 563bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com double x_ry2 = x2 * ry; 573bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com double rx_y2 = rx * y2; 583bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com bool less2 = x_ry2 < rx_y2; 593bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return *result == less2; 603bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com} 6121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 623bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com/* 6321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comfor quads and cubics, set up a parameterized line (e.g. LineParameters ) 6421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comfor points [0] to [1]. See if point [2] is on that line, or on one side 6521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comor the other. If it both quads' end points are on the same side, choose 6621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comthe shorter tangent. If the tangents are equal, choose the better second 6721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comtangent angle 6821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 693bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.comFIXME: maybe I could set up LineParameters lazily 7021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com*/ 713bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.combool SkOpAngle::operator<(const SkOpAngle& rh) const { // this/lh: left-hand; rh: right-hand 722274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com double y = dy(); 732274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com double ry = rh.dy(); 743bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com#if DEBUG_ANGLE 753bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkString bugOut; 763bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com bugOut.printf("%s _ id=%d segId=%d tStart=%1.9g tEnd=%1.9g" 773bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com " | id=%d segId=%d tStart=%1.9g tEnd=%1.9g ", funcName, 783bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com fID, fSegment->debugID(), fSegment->t(fStart), fSegment->t(fEnd), 793bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com rh.fID, rh.fSegment->debugID(), rh.fSegment->t(rh.fStart), rh.fSegment->t(rh.fEnd)); 803bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com#endif 813bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com double y_ry = y * ry; 823bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (y_ry < 0) { // if y's are opposite signs, we can do a quick return 833bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return COMPARE_RESULT("1 y * ry < 0", y < 0); 842274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com } 853bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com // at this point, both y's must be the same sign, or one (or both) is zero 863bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com double x = dx(); 873bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com double rx = rh.dx(); 883bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (x * rx < 0) { // if x's are opposite signs, use y to determine first or second half 893bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (y < 0 && ry < 0) { // if y's are negative, lh x is smaller if positive 903bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return COMPARE_RESULT("2 x_rx < 0 && y < 0 ...", x > 0); 913bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 923bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (y >= 0 && ry >= 0) { // if y's are zero or positive, lh x is smaller if negative 933bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return COMPARE_RESULT("3 x_rx < 0 && y >= 0 ...", x < 0); 943bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 953bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkASSERT((y == 0) ^ (ry == 0)); // if one y is zero and one is negative, neg y is smaller 963bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return COMPARE_RESULT("4 x_rx < 0 && y == 0 ...", y < 0); 9721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 983bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com // at this point, both x's must be the same sign, or one (or both) is zero 993bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (y_ry == 0) { // if either y is zero 1003bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (y + ry < 0) { // if the other y is less than zero, it must be smaller 1013bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return COMPARE_RESULT("5 y_ry == 0 && y + ry < 0", y < 0); 1023bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 1033bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (y + ry > 0) { // if a y is greater than zero and an x is positive, non zero is smaller 1043bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return COMPARE_RESULT("6 y_ry == 0 && y + ry > 0", (x + rx > 0) ^ (y == 0)); 1053bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 1063bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com // at this point, both y's are zero, so lines are coincident or one is degenerate 1073bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkASSERT(x * rx != 0); // and a degenerate line should haven't gotten this far 10865e1cb6c52fd6cf5d4df14a9f258df13aa3facfcskia.committer@gmail.com } 1093bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com // see if either curve can be lengthened before trying the tangent 1103bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (fSegment->other(fEnd) != rh.fSegment // tangents not absolutely identical 1113bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com && rh.fSegment->other(rh.fEnd) != fSegment) { // and not intersecting 11221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkOpAngle longer = *this; 11321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkOpAngle rhLonger = rh; 1143bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if ((longer.lengthen(rh) | rhLonger.lengthen(*this)) // lengthen both 1153bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com && (fUnorderable || !longer.fUnorderable) 1163bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com && (rh.fUnorderable || !rhLonger.fUnorderable)) { 1173bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com#if DEBUG_ANGLE 1183bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com bugOut.prepend(" "); 1193bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com#endif 1203bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return COMPARE_RESULT("10 longer.lengthen(rh) ...", longer < rhLonger); 1213bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 1223bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 1233bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (y_ry != 0) { // if they aren't coincident, look for a stable cross product 1243bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com // at this point, y's are the same sign, neither is zero 1253bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com // and x's are the same sign, or one (or both) is zero 1263bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com double x_ry = x * ry; 1273bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com double rx_y = rx * y; 1283bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (!fComputed && !rh.fComputed) { 1293bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (!AlmostEqualUlps(x_ry, rx_y)) { 1303bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return COMPARE_RESULT("7 !fComputed && !rh.fComputed", x_ry < rx_y); 1313bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 1323bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } else { 1333bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com // if the vector was a result of subdividing a curve, see if it is stable 1343bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com bool sloppy1 = x_ry < rx_y; 1353bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com bool sloppy2 = !sloppy1; 13665e1cb6c52fd6cf5d4df14a9f258df13aa3facfcskia.committer@gmail.com if ((!fComputed || calcSlop(x, y, rx, ry, &sloppy1)) 1373bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com && (!rh.fComputed || rh.calcSlop(rx, ry, x, y, &sloppy2)) 1383bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com && sloppy1 != sloppy2) { 1393bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return COMPARE_RESULT("8 CalcSlop(x, y ...", sloppy1); 1403bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 14121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 14221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 1433bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (fSide * rh.fSide == 0) { 14446e3086c1837da6ab13b48f852bd7bfbab3dc44fcaryclark@google.com SkASSERT(fSide + rh.fSide != 0); // hitting this assert means coincidence was undetected 1453bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return COMPARE_RESULT("9 fSide * rh.fSide == 0 ...", fSide < rh.fSide); 1463bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 1473bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com // at this point, the initial tangent line is nearly coincident 1483bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com // see if edges curl away from each other 1493bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (fSide * rh.fSide < 0 && (!approximately_zero(fSide) || !approximately_zero(rh.fSide))) { 1503bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return COMPARE_RESULT("9b fSide * rh.fSide < 0 ...", fSide < rh.fSide); 1513bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 1523bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (fUnsortable || rh.fUnsortable) { 1533bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com // even with no solution, return a stable sort 1543bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return COMPARE_RESULT("11 fUnsortable || rh.fUnsortable", this < &rh); 1553bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 1563bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkPath::Verb verb = fSegment->verb(); 1573bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkPath::Verb rVerb = rh.fSegment->verb(); 1583bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if ((verb == SkPath::kLine_Verb && approximately_zero(y) && approximately_zero(x)) 1593bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com || (rVerb == SkPath::kLine_Verb 1603bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com && approximately_zero(ry) && approximately_zero(rx))) { 16121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com // See general unsortable comment below. This case can happen when 16221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com // one line has a non-zero change in t but no change in x and y. 16321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com fUnsortable = true; 1643bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return COMPARE_RESULT("12 verb == SkPath::kLine_Verb ...", this < &rh); 16521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 1663bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (fSegment->isTiny(this) || rh.fSegment->isTiny(&rh)) { 16721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com fUnsortable = true; 1683bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return COMPARE_RESULT("13 verb == fSegment->isTiny(this) ...", this < &rh); 16921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 1703bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkASSERT(verb >= SkPath::kQuad_Verb); 1713bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkASSERT(rVerb >= SkPath::kQuad_Verb); 17221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com // FIXME: until I can think of something better, project a ray from the 17321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com // end of the shorter tangent to midway between the end points 17421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com // through both curves and use the resulting angle to sort 17521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com // FIXME: some of this setup can be moved to set() if it works, or cached if it's expensive 17621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double len = fTangent1.normalSquared(); 17721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double rlen = rh.fTangent1.normalSquared(); 17821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDLine ray; 17921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkIntersections i, ri; 18021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com int roots, rroots; 18121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com bool flip = false; 1822274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com bool useThis; 1832274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com bool leftLessThanRight = fSide > 0; 18421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com do { 1852274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com useThis = (len < rlen) ^ flip; 18621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com const SkDCubic& part = useThis ? fCurvePart : rh.fCurvePart; 1873bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkPath::Verb partVerb = useThis ? verb : rVerb; 18821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com ray[0] = partVerb == SkPath::kCubic_Verb && part[0].approximatelyEqual(part[1]) ? 18921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com part[2] : part[1]; 1903bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com ray[1] = SkDPoint::Mid(part[0], part[SkPathOpsVerbToPoints(partVerb)]); 19121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkASSERT(ray[0] != ray[1]); 1923bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com roots = (i.*CurveRay[SkPathOpsVerbToPoints(verb)])(fSegment->pts(), ray); 1933bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com rroots = (ri.*CurveRay[SkPathOpsVerbToPoints(rVerb)])(rh.fSegment->pts(), ray); 19421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } while ((roots == 0 || rroots == 0) && (flip ^= true)); 19521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (roots == 0 || rroots == 0) { 19621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com // FIXME: we don't have a solution in this case. The interim solution 19721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com // is to mark the edges as unsortable, exclude them from this and 19821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com // future computations, and allow the returned path to be fragmented 19921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com fUnsortable = true; 2003bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return COMPARE_RESULT("roots == 0 || rroots == 0", this < &rh); 20121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 2022274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com SkASSERT(fSide != 0 && rh.fSide != 0); 2032274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com SkASSERT(fSide * rh.fSide > 0); // both are the same sign 2042274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com SkDPoint lLoc; 20521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double best = SK_ScalarInfinity; 2062274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com#if DEBUG_SORT 2072274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com SkDebugf("lh=%d rh=%d use-lh=%d ray={{%1.9g,%1.9g}, {%1.9g,%1.9g}} %c\n", 2082274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com fSegment->debugID(), rh.fSegment->debugID(), useThis, ray[0].fX, ray[0].fY, 2092274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com ray[1].fX, ray[1].fY, "-+"[fSide > 0]); 2102274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com#endif 2112274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com for (int index = 0; index < roots; ++index) { 2122274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com SkDPoint loc = i.pt(index); 2132274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com SkDVector dxy = loc - ray[0]; 2142274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com double dist = dxy.lengthSquared(); 2152274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com#if DEBUG_SORT 216fafcffe3ec9f1c2b55fc2b1644a656c3e4b4d094skia.committer@gmail.com SkDebugf("best=%1.9g dist=%1.9g loc={%1.9g,%1.9g} dxy={%1.9g,%1.9g}\n", 2172274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com best, dist, loc.fX, loc.fY, dxy.fX, dxy.fY); 2182274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com#endif 21921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (best > dist) { 2202274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com lLoc = loc; 22121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com best = dist; 22221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 22321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 2242274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com flip = false; 2252274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com SkDPoint rLoc; 2262274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com for (int index = 0; index < rroots; ++index) { 2272274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com rLoc = ri.pt(index); 2282274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com SkDVector dxy = rLoc - ray[0]; 2292274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com double dist = dxy.lengthSquared(); 2302274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com#if DEBUG_SORT 231fafcffe3ec9f1c2b55fc2b1644a656c3e4b4d094skia.committer@gmail.com SkDebugf("best=%1.9g dist=%1.9g %c=(fSide < 0) rLoc={%1.9g,%1.9g} dxy={%1.9g,%1.9g}\n", 2322274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com best, dist, "><"[fSide < 0], rLoc.fX, rLoc.fY, dxy.fX, dxy.fY); 2332274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com#endif 23421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (best > dist) { 2352274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com flip = true; 2362274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com break; 23721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 23821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 2393bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (flip) { 2402274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com leftLessThanRight = !leftLessThanRight; 2412274f123b56c02b1d0f195c6a980e6cfacc239bfcaryclark@google.com } 2423bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return COMPARE_RESULT("14 leftLessThanRight", leftLessThanRight); 24321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 24421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 2453bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.combool SkOpAngle::isHorizontal() const { 2463bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return dy() == 0 && fSegment->verb() == SkPath::kLine_Verb; 24721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 24821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 2493bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com// lengthen cannot cross opposite angle 2503bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.combool SkOpAngle::lengthen(const SkOpAngle& opp) { 2513bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (fSegment->other(fEnd) == opp.fSegment) { 25221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return false; 25321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 2543bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com // FIXME: make this a while loop instead and make it as large as possible? 2553bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com int newEnd = fEnd; 2563bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (fStart < fEnd ? ++newEnd < fSegment->count() : --newEnd >= 0) { 25721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com fEnd = newEnd; 25821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com setSpans(); 25921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return true; 26021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 26121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return false; 26221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 26321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 2643bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.comvoid SkOpAngle::set(const SkOpSegment* segment, int start, int end) { 26521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com fSegment = segment; 26621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com fStart = start; 26721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com fEnd = end; 26821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com setSpans(); 26921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 27021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 27121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comvoid SkOpAngle::setSpans() { 2723bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com fUnorderable = false; 2733bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (fSegment->verb() == SkPath::kLine_Verb) { 2743bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com fUnsortable = false; 2753bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } else { 2763bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com // if start-1 exists and is tiny, then start pt may have moved 2773bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com int smaller = SkMin32(fStart, fEnd); 2783bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com int tinyCheck = smaller; 2793bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com while (tinyCheck > 0 && fSegment->isTiny(tinyCheck - 1)) { 2803bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com --tinyCheck; 2813bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 2823bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if ((fUnsortable = smaller > 0 && tinyCheck == 0)) { 2833bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return; 2843bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 2853bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com int larger = SkMax32(fStart, fEnd); 2863bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com tinyCheck = larger; 2873bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com int max = fSegment->count() - 1; 2883bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com while (tinyCheck < max && fSegment->isTiny(tinyCheck + 1)) { 2893bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com ++tinyCheck; 2903bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 2913bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if ((fUnsortable = larger < max && tinyCheck == max)) { 2923bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return; 2933bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 2943bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 2953bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com fComputed = fSegment->subDivide(fStart, fEnd, &fCurvePart); 2963bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com // FIXME: slight errors in subdivision cause sort trouble later on. As an experiment, try 2973bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com // rounding the curve part to float precision here 2983bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com // fCurvePart.round(fSegment->verb()); 2993bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com switch (fSegment->verb()) { 30021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com case SkPath::kLine_Verb: { 30121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com // OPTIMIZATION: for pure line compares, we never need fTangent1.c 3023bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com fTangent1.lineEndPoints(*SkTCast<SkDLine*>(&fCurvePart)); 30321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com fSide = 0; 30421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } break; 30521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com case SkPath::kQuad_Verb: { 30621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDQuad& quad = *SkTCast<SkDQuad*>(&fCurvePart); 3073bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com fTangent1.quadEndPoints(quad); 30821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com fSide = -fTangent1.pointDistance(fCurvePart[2]); // not normalized -- compare sign only 3093bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (fComputed && dx() > 0 && approximately_zero(dy())) { 3103bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkDCubic origCurve; // can't use segment's curve in place since it may be flipped 3113bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com int last = fSegment->count() - 1; 3123bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve); 3133bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkLineParameters origTan; 3143bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com origTan.quadEndPoints(*SkTCast<SkDQuad*>(&origCurve)); 3153bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if ((fUnorderable = origTan.dx() <= 0 3163bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com || (dy() != origTan.dy() && dy() * origTan.dy() <= 0))) { // signs match? 3173bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return; 31821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 31921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 3203bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } break; 3213bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com case SkPath::kCubic_Verb: { 3223bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com fTangent1.cubicEndPoints(fCurvePart); 3236645d6469358421636adc7d11e837a90078340abcaryclark@google.com double testTs[4]; 3246645d6469358421636adc7d11e837a90078340abcaryclark@google.com // OPTIMIZATION: keep inflections precomputed with cubic segment? 3253bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com const SkPoint* pts = fSegment->pts(); 3263bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com int testCount = SkDCubic::FindInflections(pts, testTs); 3273bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com double startT = fSegment->t(fStart); 3283bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com double endT = fSegment->t(fEnd); 3296645d6469358421636adc7d11e837a90078340abcaryclark@google.com double limitT = endT; 3306645d6469358421636adc7d11e837a90078340abcaryclark@google.com int index; 3316645d6469358421636adc7d11e837a90078340abcaryclark@google.com for (index = 0; index < testCount; ++index) { 3326645d6469358421636adc7d11e837a90078340abcaryclark@google.com if (!between(startT, testTs[index], limitT)) { 3336645d6469358421636adc7d11e837a90078340abcaryclark@google.com testTs[index] = -1; 3346645d6469358421636adc7d11e837a90078340abcaryclark@google.com } 3356645d6469358421636adc7d11e837a90078340abcaryclark@google.com } 3366645d6469358421636adc7d11e837a90078340abcaryclark@google.com testTs[testCount++] = startT; 3376645d6469358421636adc7d11e837a90078340abcaryclark@google.com testTs[testCount++] = endT; 338d4a6daad3bb2b40cc215fa0e8522873154c5a59bcommit-bot@chromium.org SkTQSort<double>(testTs, &testTs[testCount - 1]); 3396645d6469358421636adc7d11e837a90078340abcaryclark@google.com double bestSide = 0; 3406645d6469358421636adc7d11e837a90078340abcaryclark@google.com int testCases = (testCount << 1) - 1; 3416645d6469358421636adc7d11e837a90078340abcaryclark@google.com index = 0; 3426645d6469358421636adc7d11e837a90078340abcaryclark@google.com while (testTs[index] < 0) { 3436645d6469358421636adc7d11e837a90078340abcaryclark@google.com ++index; 3446645d6469358421636adc7d11e837a90078340abcaryclark@google.com } 3456645d6469358421636adc7d11e837a90078340abcaryclark@google.com index <<= 1; 3466645d6469358421636adc7d11e837a90078340abcaryclark@google.com for (; index < testCases; ++index) { 3476645d6469358421636adc7d11e837a90078340abcaryclark@google.com int testIndex = index >> 1; 3486645d6469358421636adc7d11e837a90078340abcaryclark@google.com double testT = testTs[testIndex]; 3496645d6469358421636adc7d11e837a90078340abcaryclark@google.com if (index & 1) { 3506645d6469358421636adc7d11e837a90078340abcaryclark@google.com testT = (testT + testTs[testIndex + 1]) / 2; 3516645d6469358421636adc7d11e837a90078340abcaryclark@google.com } 3526645d6469358421636adc7d11e837a90078340abcaryclark@google.com // OPTIMIZE: could avoid call for t == startT, endT 3533bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkDPoint pt = dcubic_xy_at_t(pts, testT); 3546645d6469358421636adc7d11e837a90078340abcaryclark@google.com double testSide = fTangent1.pointDistance(pt); 3556645d6469358421636adc7d11e837a90078340abcaryclark@google.com if (fabs(bestSide) < fabs(testSide)) { 3566645d6469358421636adc7d11e837a90078340abcaryclark@google.com bestSide = testSide; 3576645d6469358421636adc7d11e837a90078340abcaryclark@google.com } 35821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 3596645d6469358421636adc7d11e837a90078340abcaryclark@google.com fSide = -bestSide; // compare sign only 3603bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (fComputed && dx() > 0 && approximately_zero(dy())) { 3613bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkDCubic origCurve; // can't use segment's curve in place since it may be flipped 3623bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com int last = fSegment->count() - 1; 3633bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve); 3643bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkLineParameters origTan; 3653bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com origTan.cubicEndPoints(origCurve); 3663bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if ((fUnorderable = origTan.dx() <= 0)) { 3673bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com fUnsortable = fSegment->isTiny(this); 3683bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return; 3693bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 3703bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com // if one is < 0 and the other is >= 0 3713bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if ((fUnorderable = (dy() < 0) ^ (origTan.dy() < 0))) { 3723bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com fUnsortable = fSegment->isTiny(this); 3733bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return; 3743bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 3753bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkDCubicPair split = origCurve.chopAt(startT); 3763bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkLineParameters splitTan; 3773bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com splitTan.cubicEndPoints(fStart < fEnd ? split.second() : split.first()); 3783bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if ((fUnorderable = splitTan.dx() <= 0)) { 3793bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com fUnsortable = fSegment->isTiny(this); 3803bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return; 3813bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 3823bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com // if one is < 0 and the other is >= 0 3833bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if ((fUnorderable = (dy() < 0) ^ (splitTan.dy() < 0))) { 3843bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com fUnsortable = fSegment->isTiny(this); 3853bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return; 3863bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 38765e1cb6c52fd6cf5d4df14a9f258df13aa3facfcskia.committer@gmail.com } 38821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } break; 38921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com default: 39021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkASSERT(0); 39121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 3923bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if ((fUnsortable = approximately_zero(dx()) && approximately_zero(dy()))) { 39321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return; 39421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 39521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkASSERT(fStart != fEnd); 39621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com int step = fStart < fEnd ? 1 : -1; // OPTIMIZE: worth fStart - fEnd >> 31 type macro? 39721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com for (int index = fStart; index != fEnd; index += step) { 39821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#if 1 3993bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com const SkOpSpan& thisSpan = fSegment->span(index); 4003bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com const SkOpSpan& nextSpan = fSegment->span(index + step); 40121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (thisSpan.fTiny || precisely_equal(thisSpan.fT, nextSpan.fT)) { 40221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com continue; 40321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 40421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com fUnsortable = step > 0 ? thisSpan.fUnsortableStart : nextSpan.fUnsortableEnd; 40521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#if DEBUG_UNSORTABLE 40621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (fUnsortable) { 4073bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkPoint iPt = fSegment->xyAtT(index); 4083bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkPoint ePt = fSegment->xyAtT(index + step); 40921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDebugf("%s unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__, 41021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com index, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY); 41121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 41221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#endif 41321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return; 41421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#else 41521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if ((*fSpans)[index].fUnsortableStart) { 41621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com fUnsortable = true; 41721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return; 41821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 41921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#endif 42021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 42121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#if 1 42221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#if DEBUG_UNSORTABLE 4233bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkPoint iPt = fSegment->xyAtT(fStart); 4243bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkPoint ePt = fSegment->xyAtT(fEnd); 42521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDebugf("%s all tiny unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__, 42621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com fStart, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY); 42721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#endif 42821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com fUnsortable = true; 42921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#endif 43021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 431