17839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger/* 27839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * Copyright 2012 Google Inc. 37839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * 47839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * Use of this source code is governed by a BSD-style license that can be 57839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * found in the LICENSE file. 67839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger */ 77839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#include "SkIntersections.h" 87839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#include "SkOpAngle.h" 958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#include "SkOpSegment.h" 107839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#include "SkPathOpsCurve.h" 117839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#include "SkTSort.h" 127839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger 1358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#if DEBUG_ANGLE 1458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#include "SkString.h" 1558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger 1658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenbergerstatic const char funcName[] = "SkOpSegment::operator<"; 1758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenbergerstatic const int bugChar = strlen(funcName) + 1; 1858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#endif 1958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger 2058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger/* Angles are sorted counterclockwise. The smallest angle has a positive x and the smallest 2158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger positive y. The largest angle has a positive x and a zero y. */ 2258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger 2358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#if DEBUG_ANGLE 2458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger static bool CompareResult(SkString* bugOut, const char* append, bool compare) { 2558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger bugOut->appendf("%s", append); 2658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger bugOut->writable_str()[bugChar] = "><"[compare]; 2758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkDebugf("%s\n", bugOut->c_str()); 2858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return compare; 2958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 3058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger 3158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger #define COMPARE_RESULT(append, compare) CompareResult(&bugOut, append, compare) 3258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#else 3358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger #define COMPARE_RESULT(append, compare) compare 347839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#endif 357839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger 3658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenbergerbool SkOpAngle::calcSlop(double x, double y, double rx, double ry, bool* result) const{ 3758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger double absX = fabs(x); 3858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger double absY = fabs(y); 3958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger double length = absX < absY ? absX / 2 + absY : absX + absY / 2; 4058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger int exponent; 4158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger (void) frexp(length, &exponent); 4258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger double epsilon = ldexp(FLT_EPSILON, exponent); 4358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkPath::Verb verb = fSegment->verb(); 4458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(verb == SkPath::kQuad_Verb || verb == SkPath::kCubic_Verb); 4558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // FIXME: the quad and cubic factors are made up ; determine actual values 4658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger double slop = verb == SkPath::kQuad_Verb ? 4 * epsilon : 512 * epsilon; 4758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger double xSlop = slop; 4858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger double ySlop = x * y < 0 ? -xSlop : xSlop; // OPTIMIZATION: use copysign / _copysign ? 4958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger double x1 = x - xSlop; 5058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger double y1 = y + ySlop; 5158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger double x_ry1 = x1 * ry; 5258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger double rx_y1 = rx * y1; 5358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger *result = x_ry1 < rx_y1; 5458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger double x2 = x + xSlop; 5558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger double y2 = y - ySlop; 5658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger double x_ry2 = x2 * ry; 5758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger double rx_y2 = rx * y2; 5858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger bool less2 = x_ry2 < rx_y2; 5958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return *result == less2; 6058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger} 617839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger 6258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger/* 637839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenbergerfor quads and cubics, set up a parameterized line (e.g. LineParameters ) 647839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenbergerfor points [0] to [1]. See if point [2] is on that line, or on one side 657839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenbergeror the other. If it both quads' end points are on the same side, choose 667839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenbergerthe shorter tangent. If the tangents are equal, choose the better second 677839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenbergertangent angle 687839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger 6958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek SollenbergerFIXME: maybe I could set up LineParameters lazily 707839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger*/ 7158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenbergerbool SkOpAngle::operator<(const SkOpAngle& rh) const { // this/lh: left-hand; rh: right-hand 7258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger double y = dy(); 7358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger double ry = rh.dy(); 7458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#if DEBUG_ANGLE 7558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkString bugOut; 7658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger bugOut.printf("%s _ id=%d segId=%d tStart=%1.9g tEnd=%1.9g" 7758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger " | id=%d segId=%d tStart=%1.9g tEnd=%1.9g ", funcName, 7858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fID, fSegment->debugID(), fSegment->t(fStart), fSegment->t(fEnd), 7958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger rh.fID, rh.fSegment->debugID(), rh.fSegment->t(rh.fStart), rh.fSegment->t(rh.fEnd)); 8058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#endif 8158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger double y_ry = y * ry; 8258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (y_ry < 0) { // if y's are opposite signs, we can do a quick return 8358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return COMPARE_RESULT("1 y * ry < 0", y < 0); 847839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 8558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // at this point, both y's must be the same sign, or one (or both) is zero 867839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger double x = dx(); 877839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger double rx = rh.dx(); 8858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (x * rx < 0) { // if x's are opposite signs, use y to determine first or second half 8958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (y < 0 && ry < 0) { // if y's are negative, lh x is smaller if positive 9058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return COMPARE_RESULT("2 x_rx < 0 && y < 0 ...", x > 0); 9158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 9258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (y >= 0 && ry >= 0) { // if y's are zero or positive, lh x is smaller if negative 9358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return COMPARE_RESULT("3 x_rx < 0 && y >= 0 ...", x < 0); 9458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 9558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT((y == 0) ^ (ry == 0)); // if one y is zero and one is negative, neg y is smaller 9658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return COMPARE_RESULT("4 x_rx < 0 && y == 0 ...", y < 0); 977839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 9858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // at this point, both x's must be the same sign, or one (or both) is zero 9958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (y_ry == 0) { // if either y is zero 10058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (y + ry < 0) { // if the other y is less than zero, it must be smaller 10158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return COMPARE_RESULT("5 y_ry == 0 && y + ry < 0", y < 0); 10258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 10358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (y + ry > 0) { // if a y is greater than zero and an x is positive, non zero is smaller 10458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return COMPARE_RESULT("6 y_ry == 0 && y + ry > 0", (x + rx > 0) ^ (y == 0)); 10558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 10658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // at this point, both y's are zero, so lines are coincident or one is degenerate 10758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(x * rx != 0); // and a degenerate line should haven't gotten this far 1087839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 10958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // see if either curve can be lengthened before trying the tangent 11058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (fSegment->other(fEnd) != rh.fSegment // tangents not absolutely identical 11158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger && rh.fSegment->other(rh.fEnd) != fSegment) { // and not intersecting 1127839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkOpAngle longer = *this; 1137839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkOpAngle rhLonger = rh; 11458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if ((longer.lengthen(rh) | rhLonger.lengthen(*this)) // lengthen both 11558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger && (fUnorderable || !longer.fUnorderable) 11658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger && (rh.fUnorderable || !rhLonger.fUnorderable)) { 11758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#if DEBUG_ANGLE 11858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger bugOut.prepend(" "); 11958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#endif 12058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return COMPARE_RESULT("10 longer.lengthen(rh) ...", longer < rhLonger); 12158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 12258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 12358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (y_ry != 0) { // if they aren't coincident, look for a stable cross product 12458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // at this point, y's are the same sign, neither is zero 12558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // and x's are the same sign, or one (or both) is zero 12658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger double x_ry = x * ry; 12758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger double rx_y = rx * y; 12858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (!fComputed && !rh.fComputed) { 12958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (!AlmostEqualUlps(x_ry, rx_y)) { 13058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return COMPARE_RESULT("7 !fComputed && !rh.fComputed", x_ry < rx_y); 13158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 13258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } else { 13358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // if the vector was a result of subdividing a curve, see if it is stable 13458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger bool sloppy1 = x_ry < rx_y; 13558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger bool sloppy2 = !sloppy1; 13658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if ((!fComputed || calcSlop(x, y, rx, ry, &sloppy1)) 13758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger && (!rh.fComputed || rh.calcSlop(rx, ry, x, y, &sloppy2)) 13858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger && sloppy1 != sloppy2) { 13958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return COMPARE_RESULT("8 CalcSlop(x, y ...", sloppy1); 14058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 1417839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 1427839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 14358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (fSide * rh.fSide == 0) { 14458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fSide + rh.fSide != 0); // hitting this assert means coincidence was undetected 14558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return COMPARE_RESULT("9 fSide * rh.fSide == 0 ...", fSide < rh.fSide); 14658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 14758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // at this point, the initial tangent line is nearly coincident 14858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // see if edges curl away from each other 14958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (fSide * rh.fSide < 0 && (!approximately_zero(fSide) || !approximately_zero(rh.fSide))) { 15058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return COMPARE_RESULT("9b fSide * rh.fSide < 0 ...", fSide < rh.fSide); 15158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 15258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (fUnsortable || rh.fUnsortable) { 15358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // even with no solution, return a stable sort 15458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return COMPARE_RESULT("11 fUnsortable || rh.fUnsortable", this < &rh); 15558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 15658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkPath::Verb verb = fSegment->verb(); 15758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkPath::Verb rVerb = rh.fSegment->verb(); 15858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if ((verb == SkPath::kLine_Verb && approximately_zero(y) && approximately_zero(x)) 15958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger || (rVerb == SkPath::kLine_Verb 16058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger && approximately_zero(ry) && approximately_zero(rx))) { 1617839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger // See general unsortable comment below. This case can happen when 1627839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger // one line has a non-zero change in t but no change in x and y. 1637839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fUnsortable = true; 16458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return COMPARE_RESULT("12 verb == SkPath::kLine_Verb ...", this < &rh); 1657839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 16658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (fSegment->isTiny(this) || rh.fSegment->isTiny(&rh)) { 1677839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fUnsortable = true; 16858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return COMPARE_RESULT("13 verb == fSegment->isTiny(this) ...", this < &rh); 1697839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 17058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(verb >= SkPath::kQuad_Verb); 17158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(rVerb >= SkPath::kQuad_Verb); 1727839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger // FIXME: until I can think of something better, project a ray from the 1737839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger // end of the shorter tangent to midway between the end points 1747839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger // through both curves and use the resulting angle to sort 1757839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger // FIXME: some of this setup can be moved to set() if it works, or cached if it's expensive 1767839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger double len = fTangent1.normalSquared(); 1777839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger double rlen = rh.fTangent1.normalSquared(); 1787839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkDLine ray; 1797839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkIntersections i, ri; 1807839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger int roots, rroots; 1817839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger bool flip = false; 1827839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger bool useThis; 1837839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger bool leftLessThanRight = fSide > 0; 1847839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger do { 1857839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger useThis = (len < rlen) ^ flip; 1867839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger const SkDCubic& part = useThis ? fCurvePart : rh.fCurvePart; 18758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkPath::Verb partVerb = useThis ? verb : rVerb; 1887839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger ray[0] = partVerb == SkPath::kCubic_Verb && part[0].approximatelyEqual(part[1]) ? 1897839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger part[2] : part[1]; 19058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger ray[1] = SkDPoint::Mid(part[0], part[SkPathOpsVerbToPoints(partVerb)]); 1917839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkASSERT(ray[0] != ray[1]); 19258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger roots = (i.*CurveRay[SkPathOpsVerbToPoints(verb)])(fSegment->pts(), ray); 19358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger rroots = (ri.*CurveRay[SkPathOpsVerbToPoints(rVerb)])(rh.fSegment->pts(), ray); 1947839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } while ((roots == 0 || rroots == 0) && (flip ^= true)); 1957839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (roots == 0 || rroots == 0) { 1967839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger // FIXME: we don't have a solution in this case. The interim solution 1977839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger // is to mark the edges as unsortable, exclude them from this and 1987839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger // future computations, and allow the returned path to be fragmented 1997839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fUnsortable = true; 20058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return COMPARE_RESULT("roots == 0 || rroots == 0", this < &rh); 2017839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 2027839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkASSERT(fSide != 0 && rh.fSide != 0); 2037839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkASSERT(fSide * rh.fSide > 0); // both are the same sign 2047839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkDPoint lLoc; 2057839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger double best = SK_ScalarInfinity; 2067839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#if DEBUG_SORT 2077839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkDebugf("lh=%d rh=%d use-lh=%d ray={{%1.9g,%1.9g}, {%1.9g,%1.9g}} %c\n", 2087839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fSegment->debugID(), rh.fSegment->debugID(), useThis, ray[0].fX, ray[0].fY, 2097839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger ray[1].fX, ray[1].fY, "-+"[fSide > 0]); 2107839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#endif 2117839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger for (int index = 0; index < roots; ++index) { 2127839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkDPoint loc = i.pt(index); 2137839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkDVector dxy = loc - ray[0]; 2147839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger double dist = dxy.lengthSquared(); 2157839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#if DEBUG_SORT 2167839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkDebugf("best=%1.9g dist=%1.9g loc={%1.9g,%1.9g} dxy={%1.9g,%1.9g}\n", 2177839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger best, dist, loc.fX, loc.fY, dxy.fX, dxy.fY); 2187839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#endif 2197839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (best > dist) { 2207839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger lLoc = loc; 2217839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger best = dist; 2227839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 2237839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 2247839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger flip = false; 2257839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkDPoint rLoc; 2267839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger for (int index = 0; index < rroots; ++index) { 2277839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger rLoc = ri.pt(index); 2287839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkDVector dxy = rLoc - ray[0]; 2297839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger double dist = dxy.lengthSquared(); 2307839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#if DEBUG_SORT 2317839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkDebugf("best=%1.9g dist=%1.9g %c=(fSide < 0) rLoc={%1.9g,%1.9g} dxy={%1.9g,%1.9g}\n", 2327839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger best, dist, "><"[fSide < 0], rLoc.fX, rLoc.fY, dxy.fX, dxy.fY); 2337839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#endif 2347839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (best > dist) { 2357839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger flip = true; 2367839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger break; 2377839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 2387839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 23958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (flip) { 2407839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger leftLessThanRight = !leftLessThanRight; 2417839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 24258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return COMPARE_RESULT("14 leftLessThanRight", leftLessThanRight); 2437839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger} 2447839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger 24558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenbergerbool SkOpAngle::isHorizontal() const { 24658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return dy() == 0 && fSegment->verb() == SkPath::kLine_Verb; 2477839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger} 2487839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger 24958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger// lengthen cannot cross opposite angle 25058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenbergerbool SkOpAngle::lengthen(const SkOpAngle& opp) { 25158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (fSegment->other(fEnd) == opp.fSegment) { 2527839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger return false; 2537839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 25458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // FIXME: make this a while loop instead and make it as large as possible? 25558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger int newEnd = fEnd; 25658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (fStart < fEnd ? ++newEnd < fSegment->count() : --newEnd >= 0) { 2577839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fEnd = newEnd; 2587839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger setSpans(); 2597839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger return true; 2607839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 2617839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger return false; 2627839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger} 2637839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger 26458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenbergervoid SkOpAngle::set(const SkOpSegment* segment, int start, int end) { 2657839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fSegment = segment; 2667839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fStart = start; 2677839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fEnd = end; 2687839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger setSpans(); 2697839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger} 2707839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger 2717839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenbergervoid SkOpAngle::setSpans() { 27258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fUnorderable = false; 27358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (fSegment->verb() == SkPath::kLine_Verb) { 27458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fUnsortable = false; 27558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } else { 27658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // if start-1 exists and is tiny, then start pt may have moved 27758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger int smaller = SkMin32(fStart, fEnd); 27858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger int tinyCheck = smaller; 27958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger while (tinyCheck > 0 && fSegment->isTiny(tinyCheck - 1)) { 28058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger --tinyCheck; 28158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 28258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if ((fUnsortable = smaller > 0 && tinyCheck == 0)) { 28358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return; 28458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 28558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger int larger = SkMax32(fStart, fEnd); 28658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger tinyCheck = larger; 28758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger int max = fSegment->count() - 1; 28858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger while (tinyCheck < max && fSegment->isTiny(tinyCheck + 1)) { 28958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger ++tinyCheck; 29058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 29158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if ((fUnsortable = larger < max && tinyCheck == max)) { 29258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return; 29358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 29458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 29558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fComputed = fSegment->subDivide(fStart, fEnd, &fCurvePart); 29658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // FIXME: slight errors in subdivision cause sort trouble later on. As an experiment, try 29758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // rounding the curve part to float precision here 29858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // fCurvePart.round(fSegment->verb()); 29958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger switch (fSegment->verb()) { 3007839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger case SkPath::kLine_Verb: { 3017839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger // OPTIMIZATION: for pure line compares, we never need fTangent1.c 30258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fTangent1.lineEndPoints(*SkTCast<SkDLine*>(&fCurvePart)); 3037839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fSide = 0; 3047839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } break; 3057839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger case SkPath::kQuad_Verb: { 3067839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkDQuad& quad = *SkTCast<SkDQuad*>(&fCurvePart); 30758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fTangent1.quadEndPoints(quad); 3087839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fSide = -fTangent1.pointDistance(fCurvePart[2]); // not normalized -- compare sign only 30958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (fComputed && dx() > 0 && approximately_zero(dy())) { 31058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkDCubic origCurve; // can't use segment's curve in place since it may be flipped 31158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger int last = fSegment->count() - 1; 31258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve); 31358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkLineParameters origTan; 31458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger origTan.quadEndPoints(*SkTCast<SkDQuad*>(&origCurve)); 31558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if ((fUnorderable = origTan.dx() <= 0 31658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger || (dy() != origTan.dy() && dy() * origTan.dy() <= 0))) { // signs match? 31758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return; 3187839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 3197839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 32058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } break; 32158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger case SkPath::kCubic_Verb: { 32258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fTangent1.cubicEndPoints(fCurvePart); 3237839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger double testTs[4]; 3247839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger // OPTIMIZATION: keep inflections precomputed with cubic segment? 32558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger const SkPoint* pts = fSegment->pts(); 32658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger int testCount = SkDCubic::FindInflections(pts, testTs); 32758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger double startT = fSegment->t(fStart); 32858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger double endT = fSegment->t(fEnd); 3297839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger double limitT = endT; 3307839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger int index; 3317839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger for (index = 0; index < testCount; ++index) { 3327839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (!between(startT, testTs[index], limitT)) { 3337839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger testTs[index] = -1; 3347839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 3357839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 3367839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger testTs[testCount++] = startT; 3377839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger testTs[testCount++] = endT; 3387839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkTQSort<double>(testTs, &testTs[testCount - 1]); 3397839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger double bestSide = 0; 3407839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger int testCases = (testCount << 1) - 1; 3417839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger index = 0; 3427839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger while (testTs[index] < 0) { 3437839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger ++index; 3447839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 3457839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger index <<= 1; 3467839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger for (; index < testCases; ++index) { 3477839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger int testIndex = index >> 1; 3487839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger double testT = testTs[testIndex]; 3497839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (index & 1) { 3507839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger testT = (testT + testTs[testIndex + 1]) / 2; 3517839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 3527839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger // OPTIMIZE: could avoid call for t == startT, endT 35358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkDPoint pt = dcubic_xy_at_t(pts, testT); 3547839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger double testSide = fTangent1.pointDistance(pt); 3557839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (fabs(bestSide) < fabs(testSide)) { 3567839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger bestSide = testSide; 3577839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 3587839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 3597839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fSide = -bestSide; // compare sign only 36058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (fComputed && dx() > 0 && approximately_zero(dy())) { 36158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkDCubic origCurve; // can't use segment's curve in place since it may be flipped 36258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger int last = fSegment->count() - 1; 36358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve); 36458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkLineParameters origTan; 36558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger origTan.cubicEndPoints(origCurve); 36658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if ((fUnorderable = origTan.dx() <= 0)) { 36758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fUnsortable = fSegment->isTiny(this); 36858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return; 36958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 37058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // if one is < 0 and the other is >= 0 37158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if ((fUnorderable = (dy() < 0) ^ (origTan.dy() < 0))) { 37258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fUnsortable = fSegment->isTiny(this); 37358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return; 37458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 37558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkDCubicPair split = origCurve.chopAt(startT); 37658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkLineParameters splitTan; 37758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger splitTan.cubicEndPoints(fStart < fEnd ? split.second() : split.first()); 37858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if ((fUnorderable = splitTan.dx() <= 0)) { 37958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fUnsortable = fSegment->isTiny(this); 38058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return; 38158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 38258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // if one is < 0 and the other is >= 0 38358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if ((fUnorderable = (dy() < 0) ^ (splitTan.dy() < 0))) { 38458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fUnsortable = fSegment->isTiny(this); 38558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return; 38658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 38758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 3887839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } break; 3897839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger default: 3907839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkASSERT(0); 3917839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 39258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if ((fUnsortable = approximately_zero(dx()) && approximately_zero(dy()))) { 3937839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger return; 3947839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 3957839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkASSERT(fStart != fEnd); 3967839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger int step = fStart < fEnd ? 1 : -1; // OPTIMIZE: worth fStart - fEnd >> 31 type macro? 3977839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger for (int index = fStart; index != fEnd; index += step) { 3987839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#if 1 39958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger const SkOpSpan& thisSpan = fSegment->span(index); 40058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger const SkOpSpan& nextSpan = fSegment->span(index + step); 4017839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (thisSpan.fTiny || precisely_equal(thisSpan.fT, nextSpan.fT)) { 4027839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger continue; 4037839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 4047839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fUnsortable = step > 0 ? thisSpan.fUnsortableStart : nextSpan.fUnsortableEnd; 4057839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#if DEBUG_UNSORTABLE 4067839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (fUnsortable) { 40758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkPoint iPt = fSegment->xyAtT(index); 40858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkPoint ePt = fSegment->xyAtT(index + step); 4097839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkDebugf("%s unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__, 4107839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger index, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY); 4117839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 4127839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#endif 4137839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger return; 4147839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#else 4157839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if ((*fSpans)[index].fUnsortableStart) { 4167839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fUnsortable = true; 4177839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger return; 4187839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 4197839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#endif 4207839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 4217839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#if 1 4227839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#if DEBUG_UNSORTABLE 42358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkPoint iPt = fSegment->xyAtT(fStart); 42458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkPoint ePt = fSegment->xyAtT(fEnd); 4257839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkDebugf("%s all tiny unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__, 4267839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fStart, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY); 4277839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#endif 4287839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fUnsortable = true; 4297839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#endif 4307839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger} 431