submodule/skia/src/pathops/SkOpAngle.cpp

   1 /*
   2  * Copyright 2012 Google Inc.
   3  *
   4  * Use of this source code is governed by a BSD-style license that can be
   5  * found in the LICENSE file.
   6  */
   7 #include "src/core/SkTSort.h"
   8 #include "src/pathops/SkOpAngle.h"
   9 #include "src/pathops/SkOpSegment.h"
  10 #include "src/pathops/SkPathOpsCurve.h"
  11
  12 /* Angles are sorted counterclockwise. The smallest angle has a positive x and the smallest
  13    positive y. The largest angle has a positive x and a zero y. */
  14
  15 #if DEBUG_ANGLE
  16     static bool CompareResult(const char* func, SkString* bugOut, SkString* bugPart, int append,
  17              bool compare) {
  18         SkDebugf("%s %c %d\n", bugOut->c_str(), compare ? 'T' : 'F', append);
  19         SkDebugf("%sPart %s\n", func, bugPart[0].c_str());
  20         SkDebugf("%sPart %s\n", func, bugPart[1].c_str());
  21         SkDebugf("%sPart %s\n", func, bugPart[2].c_str());
  22         return compare;
  23     }
  24
  25     #define COMPARE_RESULT(append, compare) CompareResult(__FUNCTION__, &bugOut, bugPart, append, \
  26             compare)
  27 #else
  28     #define COMPARE_RESULT(append, compare) compare
  29 #endif
  30
  31 /*             quarter angle values for sector
  32
  33 31   x > 0, y == 0              horizontal line (to the right)
  34 0    x > 0, y == epsilon        quad/cubic horizontal tangent eventually going +y
  35 1    x > 0, y > 0, x > y        nearer horizontal angle
  36 2                  x + e == y   quad/cubic 45 going horiz
  37 3    x > 0, y > 0, x == y       45 angle
  38 4                  x == y + e   quad/cubic 45 going vert
  39 5    x > 0, y > 0, x < y        nearer vertical angle
  40 6    x == epsilon, y > 0        quad/cubic vertical tangent eventually going +x
  41 7    x == 0, y > 0              vertical line (to the top)
  42
  43                                       8  7  6
  44                                  9       |       5
  45                               10         |          4
  46                             11           |            3
  47                           12  \          |           / 2
  48                          13              |              1
  49                         14               |               0
  50                         15 --------------+------------- 31
  51                         16               |              30
  52                          17              |             29
  53                           18  /          |          \ 28
  54                             19           |           27
  55                               20         |         26
  56                                  21      |      25
  57                                      22 23 24
  58 */
  59
  60 // return true if lh < this < rh
  61 bool SkOpAngle::after(SkOpAngle* test) {
  62     SkOpAngle* lh = test;
  63     SkOpAngle* rh = lh->fNext;
  64     SkASSERT(lh != rh);
  65     fPart.fCurve = fOriginalCurvePart;
  66     lh->fPart.fCurve = lh->fOriginalCurvePart;
  67     lh->fPart.fCurve.offset(lh->segment()->verb(), fPart.fCurve[0] - lh->fPart.fCurve[0]);
  68     rh->fPart.fCurve = rh->fOriginalCurvePart;
  69     rh->fPart.fCurve.offset(rh->segment()->verb(), fPart.fCurve[0] - rh->fPart.fCurve[0]);
  70
  71 #if DEBUG_ANGLE
  72     SkString bugOut;
  73     bugOut.printf("%s [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
  74                   " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
  75                   " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g ", __FUNCTION__,
  76             lh->segment()->debugID(), lh->debugID(), lh->fSectorStart, lh->fSectorEnd,
  77             lh->fStart->t(), lh->fEnd->t(),
  78             segment()->debugID(), debugID(), fSectorStart, fSectorEnd, fStart->t(), fEnd->t(),
  79             rh->segment()->debugID(), rh->debugID(), rh->fSectorStart, rh->fSectorEnd,
  80             rh->fStart->t(), rh->fEnd->t());
  81     SkString bugPart[3] = { lh->debugPart(), this->debugPart(), rh->debugPart() };
  82 #endif
  83     if (lh->fComputeSector && !lh->computeSector()) {
  84         return COMPARE_RESULT(1, true);
  85     }
  86     if (fComputeSector && !this->computeSector()) {
  87         return COMPARE_RESULT(2, true);
  88     }
  89     if (rh->fComputeSector && !rh->computeSector()) {
  90         return COMPARE_RESULT(3, true);
  91     }
  92 #if DEBUG_ANGLE  // reset bugOut with computed sectors
  93     bugOut.printf("%s [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
  94                   " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
  95                   " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g ", __FUNCTION__,
  96             lh->segment()->debugID(), lh->debugID(), lh->fSectorStart, lh->fSectorEnd,
  97             lh->fStart->t(), lh->fEnd->t(),
  98             segment()->debugID(), debugID(), fSectorStart, fSectorEnd, fStart->t(), fEnd->t(),
  99             rh->segment()->debugID(), rh->debugID(), rh->fSectorStart, rh->fSectorEnd,
 100             rh->fStart->t(), rh->fEnd->t());
 101 #endif
 102     bool ltrOverlap = (lh->fSectorMask | rh->fSectorMask) & fSectorMask;
 103     bool lrOverlap = lh->fSectorMask & rh->fSectorMask;
 104     int lrOrder;  // set to -1 if either order works
 105     if (!lrOverlap) {  // no lh/rh sector overlap
 106         if (!ltrOverlap) {  // no lh/this/rh sector overlap
 107             return COMPARE_RESULT(4,  (lh->fSectorEnd > rh->fSectorStart)
 108                     ^ (fSectorStart > lh->fSectorEnd) ^ (fSectorStart > rh->fSectorStart));
 109         }
 110         int lrGap = (rh->fSectorStart - lh->fSectorStart + 32) & 0x1f;
 111         /* A tiny change can move the start +/- 4. The order can only be determined if
 112            lr gap is not 12 to 20 or -12 to -20.
 113                -31 ..-21      1
 114                -20 ..-12     -1
 115                -11 .. -1      0
 116                  0          shouldn't get here
 117                 11 ..  1      1
 118                 12 .. 20     -1
 119                 21 .. 31      0
 120          */
 121         lrOrder = lrGap > 20 ? 0 : lrGap > 11 ? -1 : 1;
 122     } else {
 123         lrOrder = lh->orderable(rh);
 124         if (!ltrOverlap && lrOrder >= 0) {
 125             return COMPARE_RESULT(5, !lrOrder);
 126         }
 127     }
 128     int ltOrder;
 129     SkASSERT((lh->fSectorMask & fSectorMask) || (rh->fSectorMask & fSectorMask) || -1 == lrOrder);
 130     if (lh->fSectorMask & fSectorMask) {
 131         ltOrder = lh->orderable(this);
 132     } else {
 133         int ltGap = (fSectorStart - lh->fSectorStart + 32) & 0x1f;
 134         ltOrder = ltGap > 20 ? 0 : ltGap > 11 ? -1 : 1;
 135     }
 136     int trOrder;
 137     if (rh->fSectorMask & fSectorMask) {
 138         trOrder = this->orderable(rh);
 139     } else {
 140         int trGap = (rh->fSectorStart - fSectorStart + 32) & 0x1f;
 141         trOrder = trGap > 20 ? 0 : trGap > 11 ? -1 : 1;
 142     }
 143     this->alignmentSameSide(lh, &ltOrder);
 144     this->alignmentSameSide(rh, &trOrder);
 145     if (lrOrder >= 0 && ltOrder >= 0 && trOrder >= 0) {
 146         return COMPARE_RESULT(7, lrOrder ? (ltOrder & trOrder) : (ltOrder | trOrder));
 147     }
 148 //    SkASSERT(lrOrder >= 0 || ltOrder >= 0 || trOrder >= 0);
 149 // There's not enough information to sort. Get the pairs of angles in opposite planes.
 150 // If an order is < 0, the pair is already in an opposite plane. Check the remaining pairs.
 151     // FIXME : once all variants are understood, rewrite this more simply
 152     if (ltOrder == 0 && lrOrder == 0) {
 153         SkASSERT(trOrder < 0);
 154         // FIXME : once this is verified to work, remove one opposite angle call
 155         SkDEBUGCODE(bool lrOpposite = lh->oppositePlanes(rh));
 156         bool ltOpposite = lh->oppositePlanes(this);
 157         SkOPASSERT(lrOpposite != ltOpposite);
 158         return COMPARE_RESULT(8, ltOpposite);
 159     } else if (ltOrder == 1 && trOrder == 0) {
 160         SkASSERT(lrOrder < 0);
 161         bool trOpposite = oppositePlanes(rh);
 162         return COMPARE_RESULT(9, trOpposite);
 163     } else if (lrOrder == 1 && trOrder == 1) {
 164         SkASSERT(ltOrder < 0);
 165 //        SkDEBUGCODE(bool trOpposite = oppositePlanes(rh));
 166         bool lrOpposite = lh->oppositePlanes(rh);
 167 //        SkASSERT(lrOpposite != trOpposite);
 168         return COMPARE_RESULT(10, lrOpposite);
 169     }
 170     // If a pair couldn't be ordered, there's not enough information to determine the sort.
 171     // Refer to:  https://docs.google.com/drawings/d/1KV-8SJTedku9fj4K6fd1SB-8divuV_uivHVsSgwXICQ
 172     if (fUnorderable || lh->fUnorderable || rh->fUnorderable) {
 173         // limit to lines; should work with curves, but wait for a failing test to verify
 174         if (!fPart.isCurve() && !lh->fPart.isCurve() && !rh->fPart.isCurve()) {
 175             // see if original raw data is orderable
 176             // if two share a point, check if third has both points in same half plane
 177             int ltShare = lh->fOriginalCurvePart[0] == fOriginalCurvePart[0];
 178             int lrShare = lh->fOriginalCurvePart[0] == rh->fOriginalCurvePart[0];
 179             int trShare = fOriginalCurvePart[0] == rh->fOriginalCurvePart[0];
 180             // if only one pair are the same, the third point touches neither of the pair
 181             if (ltShare + lrShare + trShare == 1) {
 182                 if (lrShare) {
 183                     int ltOOrder = lh->linesOnOriginalSide(this);
 184                     int rtOOrder = rh->linesOnOriginalSide(this);
 185                     if ((rtOOrder ^ ltOOrder) == 1) {
 186                         return ltOOrder;
 187                     }
 188                 } else if (trShare) {
 189                     int tlOOrder = this->linesOnOriginalSide(lh);
 190                     int rlOOrder = rh->linesOnOriginalSide(lh);
 191                     if ((tlOOrder ^ rlOOrder) == 1) {
 192                         return rlOOrder;
 193                     }
 194                 } else {
 195                     SkASSERT(ltShare);
 196                     int trOOrder = rh->linesOnOriginalSide(this);
 197                     int lrOOrder = lh->linesOnOriginalSide(rh);
 198                     // result must be 0 and 1 or 1 and 0 to be valid
 199                     if ((lrOOrder ^ trOOrder) == 1) {
 200                         return trOOrder;
 201                     }
 202                 }
 203             }
 204         }
 205     }
 206     if (lrOrder < 0) {
 207         if (ltOrder < 0) {
 208             return COMPARE_RESULT(11, trOrder);
 209         }
 210         return COMPARE_RESULT(12, ltOrder);
 211     }
 212     return COMPARE_RESULT(13, !lrOrder);
 213 }
 214
 215 int SkOpAngle::lineOnOneSide(const SkDPoint& origin, const SkDVector& line, const SkOpAngle* test,
 216         bool useOriginal) const {
 217     double crosses[3];
 218     SkPath::Verb testVerb = test->segment()->verb();
 219     int iMax = SkPathOpsVerbToPoints(testVerb);
 220 //    SkASSERT(origin == test.fCurveHalf[0]);
 221     const SkDCurve& testCurve = useOriginal ? test->fOriginalCurvePart : test->fPart.fCurve;
 222     for (int index = 1; index <= iMax; ++index) {
 223         double xy1 = line.fX * (testCurve[index].fY - origin.fY);
 224         double xy2 = line.fY * (testCurve[index].fX - origin.fX);
 225         crosses[index - 1] = AlmostBequalUlps(xy1, xy2) ? 0 : xy1 - xy2;
 226     }
 227     if (crosses[0] * crosses[1] < 0) {
 228         return -1;
 229     }
 230     if (SkPath::kCubic_Verb == testVerb) {
 231         if (crosses[0] * crosses[2] < 0 || crosses[1] * crosses[2] < 0) {
 232             return -1;
 233         }
 234     }
 235     if (crosses[0]) {
 236         return crosses[0] < 0;
 237     }
 238     if (crosses[1]) {
 239         return crosses[1] < 0;
 240     }
 241     if (SkPath::kCubic_Verb == testVerb && crosses[2]) {
 242         return crosses[2] < 0;
 243     }
 244     return -2;
 245 }
 246
 247 // given a line, see if the opposite curve's convex hull is all on one side
 248 // returns -1=not on one side    0=this CW of test   1=this CCW of test
 249 int SkOpAngle::lineOnOneSide(const SkOpAngle* test, bool useOriginal) {
 250     SkASSERT(!fPart.isCurve());
 251     SkASSERT(test->fPart.isCurve());
 252     SkDPoint origin = fPart.fCurve[0];
 253     SkDVector line = fPart.fCurve[1] - origin;
 254     int result = this->lineOnOneSide(origin, line, test, useOriginal);
 255     if (-2 == result) {
 256         fUnorderable = true;
 257         result = -1;
 258     }
 259     return result;
 260 }
 261
 262 // experiment works only with lines for now
 263 int SkOpAngle::linesOnOriginalSide(const SkOpAngle* test) {
 264     SkASSERT(!fPart.isCurve());
 265     SkASSERT(!test->fPart.isCurve());
 266     SkDPoint origin = fOriginalCurvePart[0];
 267     SkDVector line = fOriginalCurvePart[1] - origin;
 268     double dots[2];
 269     double crosses[2];
 270     const SkDCurve& testCurve = test->fOriginalCurvePart;
 271     for (int index = 0; index < 2; ++index) {
 272         SkDVector testLine = testCurve[index] - origin;
 273         double xy1 = line.fX * testLine.fY;
 274         double xy2 = line.fY * testLine.fX;
 275         dots[index] = line.fX * testLine.fX + line.fY * testLine.fY;
 276         crosses[index] = AlmostBequalUlps(xy1, xy2) ? 0 : xy1 - xy2;
 277     }
 278     if (crosses[0] * crosses[1] < 0) {
 279         return -1;
 280     }
 281     if (crosses[0]) {
 282         return crosses[0] < 0;
 283     }
 284     if (crosses[1]) {
 285         return crosses[1] < 0;
 286     }
 287     if ((!dots[0] && dots[1] < 0) || (dots[0] < 0 && !dots[1])) {
 288         return 2;  // 180 degrees apart
 289     }
 290     fUnorderable = true;
 291     return -1;
 292 }
 293
 294 // To sort the angles, all curves are translated to have the same starting point.
 295 // If the curve's control point in its original position is on one side of a compared line,
 296 // and translated is on the opposite side, reverse the previously computed order.
 297 void SkOpAngle::alignmentSameSide(const SkOpAngle* test, int* order) const {
 298     if (*order < 0) {
 299         return;
 300     }
 301     if (fPart.isCurve()) {
 302         // This should support all curve types, but only bug that requires this has lines
 303         // Turning on for curves causes existing tests to fail
 304         return;
 305     }
 306     if (test->fPart.isCurve()) {
 307         return;
 308     }
 309     const SkDPoint& xOrigin = test->fPart.fCurve.fLine[0];
 310     const SkDPoint& oOrigin = test->fOriginalCurvePart.fLine[0];
 311     if (xOrigin == oOrigin) {
 312         return;
 313     }
 314     int iMax = SkPathOpsVerbToPoints(this->segment()->verb());
 315     SkDVector xLine = test->fPart.fCurve.fLine[1] - xOrigin;
 316     SkDVector oLine = test->fOriginalCurvePart.fLine[1] - oOrigin;
 317     for (int index = 1; index <= iMax; ++index) {
 318         const SkDPoint& testPt = fPart.fCurve[index];
 319         double xCross = oLine.crossCheck(testPt - xOrigin);
 320         double oCross = xLine.crossCheck(testPt - oOrigin);
 321         if (oCross * xCross < 0) {
 322             *order ^= 1;
 323             break;
 324         }
 325     }
 326 }
 327
 328 bool SkOpAngle::checkCrossesZero() const {
 329     int start = std::min(fSectorStart, fSectorEnd);
 330     int end = std::max(fSectorStart, fSectorEnd);
 331     bool crossesZero = end - start > 16;
 332     return crossesZero;
 333 }
 334
 335 bool SkOpAngle::checkParallel(SkOpAngle* rh) {
 336     SkDVector scratch[2];
 337     const SkDVector* sweep, * tweep;
 338     if (this->fPart.isOrdered()) {
 339         sweep = this->fPart.fSweep;
 340     } else {
 341         scratch[0] = this->fPart.fCurve[1] - this->fPart.fCurve[0];
 342         sweep = &scratch[0];
 343     }
 344     if (rh->fPart.isOrdered()) {
 345         tweep = rh->fPart.fSweep;
 346     } else {
 347         scratch[1] = rh->fPart.fCurve[1] - rh->fPart.fCurve[0];
 348         tweep = &scratch[1];
 349     }
 350     double s0xt0 = sweep->crossCheck(*tweep);
 351     if (tangentsDiverge(rh, s0xt0)) {
 352         return s0xt0 < 0;
 353     }
 354     // compute the perpendicular to the endpoints and see where it intersects the opposite curve
 355     // if the intersections within the t range, do a cross check on those
 356     bool inside;
 357     if (!fEnd->contains(rh->fEnd)) {
 358         if (this->endToSide(rh, &inside)) {
 359             return inside;
 360         }
 361         if (rh->endToSide(this, &inside)) {
 362             return !inside;
 363         }
 364     }
 365     if (this->midToSide(rh, &inside)) {
 366         return inside;
 367     }
 368     if (rh->midToSide(this, &inside)) {
 369         return !inside;
 370     }
 371     // compute the cross check from the mid T values (last resort)
 372     SkDVector m0 = segment()->dPtAtT(this->midT()) - this->fPart.fCurve[0];
 373     SkDVector m1 = rh->segment()->dPtAtT(rh->midT()) - rh->fPart.fCurve[0];
 374     double m0xm1 = m0.crossCheck(m1);
 375     if (m0xm1 == 0) {
 376         this->fUnorderable = true;
 377         rh->fUnorderable = true;
 378         return true;
 379     }
 380     return m0xm1 < 0;
 381 }
 382
 383 // the original angle is too short to get meaningful sector information
 384 // lengthen it until it is long enough to be meaningful or leave it unset if lengthening it
 385 // would cause it to intersect one of the adjacent angles
 386 bool SkOpAngle::computeSector() {
 387     if (fComputedSector) {
 388         return !fUnorderable;
 389     }
 390     fComputedSector = true;
 391     bool stepUp = fStart->t() < fEnd->t();
 392     SkOpSpanBase* checkEnd = fEnd;
 393     if (checkEnd->final() && stepUp) {
 394         fUnorderable = true;
 395         return false;
 396     }
 397     do {
 398 // advance end
 399         const SkOpSegment* other = checkEnd->segment();
 400         const SkOpSpanBase* oSpan = other->head();
 401         do {
 402             if (oSpan->segment() != segment()) {
 403                 continue;
 404             }
 405             if (oSpan == checkEnd) {
 406                 continue;
 407             }
 408             if (!approximately_equal(oSpan->t(), checkEnd->t())) {
 409                 continue;
 410             }
 411             goto recomputeSector;
 412         } while (!oSpan->final() && (oSpan = oSpan->upCast()->next()));
 413         checkEnd = stepUp ? !checkEnd->final()
 414                 ? checkEnd->upCast()->next() : nullptr
 415                 : checkEnd->prev();
 416     } while (checkEnd);
 417 recomputeSector:
 418     SkOpSpanBase* computedEnd = stepUp ? checkEnd ? checkEnd->prev() : fEnd->segment()->head()
 419             : checkEnd ? checkEnd->upCast()->next() : fEnd->segment()->tail();
 420     if (checkEnd == fEnd || computedEnd == fEnd || computedEnd == fStart) {
 421         fUnorderable = true;
 422         return false;
 423     }
 424     if (stepUp != (fStart->t() < computedEnd->t())) {
 425         fUnorderable = true;
 426         return false;
 427     }
 428     SkOpSpanBase* saveEnd = fEnd;
 429     fComputedEnd = fEnd = computedEnd;
 430     setSpans();
 431     setSector();
 432     fEnd = saveEnd;
 433     return !fUnorderable;
 434 }
 435
 436 int SkOpAngle::convexHullOverlaps(const SkOpAngle* rh) {
 437     const SkDVector* sweep = this->fPart.fSweep;
 438     const SkDVector* tweep = rh->fPart.fSweep;
 439     double s0xs1 = sweep[0].crossCheck(sweep[1]);
 440     double s0xt0 = sweep[0].crossCheck(tweep[0]);
 441     double s1xt0 = sweep[1].crossCheck(tweep[0]);
 442     bool tBetweenS = s0xs1 > 0 ? s0xt0 > 0 && s1xt0 < 0 : s0xt0 < 0 && s1xt0 > 0;
 443     double s0xt1 = sweep[0].crossCheck(tweep[1]);
 444     double s1xt1 = sweep[1].crossCheck(tweep[1]);
 445     tBetweenS |= s0xs1 > 0 ? s0xt1 > 0 && s1xt1 < 0 : s0xt1 < 0 && s1xt1 > 0;
 446     double t0xt1 = tweep[0].crossCheck(tweep[1]);
 447     if (tBetweenS) {
 448         return -1;
 449     }
 450     if ((s0xt0 == 0 && s1xt1 == 0) || (s1xt0 == 0 && s0xt1 == 0)) {  // s0 to s1 equals t0 to t1
 451         return -1;
 452     }
 453     bool sBetweenT = t0xt1 > 0 ? s0xt0 < 0 && s0xt1 > 0 : s0xt0 > 0 && s0xt1 < 0;
 454     sBetweenT |= t0xt1 > 0 ? s1xt0 < 0 && s1xt1 > 0 : s1xt0 > 0 && s1xt1 < 0;
 455     if (sBetweenT) {
 456         return -1;
 457     }
 458     // if all of the sweeps are in the same half plane, then the order of any pair is enough
 459     if (s0xt0 >= 0 && s0xt1 >= 0 && s1xt0 >= 0 && s1xt1 >= 0) {
 460         return 0;
 461     }
 462     if (s0xt0 <= 0 && s0xt1 <= 0 && s1xt0 <= 0 && s1xt1 <= 0) {
 463         return 1;
 464     }
 465     // if the outside sweeps are greater than 180 degress:
 466         // first assume the inital tangents are the ordering
 467         // if the midpoint direction matches the inital order, that is enough
 468     SkDVector m0 = this->segment()->dPtAtT(this->midT()) - this->fPart.fCurve[0];
 469     SkDVector m1 = rh->segment()->dPtAtT(rh->midT()) - rh->fPart.fCurve[0];
 470     double m0xm1 = m0.crossCheck(m1);
 471     if (s0xt0 > 0 && m0xm1 > 0) {
 472         return 0;
 473     }
 474     if (s0xt0 < 0 && m0xm1 < 0) {
 475         return 1;
 476     }
 477     if (tangentsDiverge(rh, s0xt0)) {
 478         return s0xt0 < 0;
 479     }
 480     return m0xm1 < 0;
 481 }
 482
 483 // OPTIMIZATION: longest can all be either lazily computed here or precomputed in setup
 484 double SkOpAngle::distEndRatio(double dist) const {
 485     double longest = 0;
 486     const SkOpSegment& segment = *this->segment();
 487     int ptCount = SkPathOpsVerbToPoints(segment.verb());
 488     const SkPoint* pts = segment.pts();
 489     for (int idx1 = 0; idx1 <= ptCount - 1; ++idx1) {
 490         for (int idx2 = idx1 + 1; idx2 <= ptCount; ++idx2) {
 491             if (idx1 == idx2) {
 492                 continue;
 493             }
 494             SkDVector v;
 495             v.set(pts[idx2] - pts[idx1]);
 496             double lenSq = v.lengthSquared();
 497             longest = std::max(longest, lenSq);
 498         }
 499     }
 500     return sqrt(longest) / dist;
 501 }
 502
 503 bool SkOpAngle::endsIntersect(SkOpAngle* rh) {
 504     SkPath::Verb lVerb = this->segment()->verb();
 505     SkPath::Verb rVerb = rh->segment()->verb();
 506     int lPts = SkPathOpsVerbToPoints(lVerb);
 507     int rPts = SkPathOpsVerbToPoints(rVerb);
 508     SkDLine rays[] = {{{this->fPart.fCurve[0], rh->fPart.fCurve[rPts]}},
 509             {{this->fPart.fCurve[0], this->fPart.fCurve[lPts]}}};
 510     if (this->fEnd->contains(rh->fEnd)) {
 511         return checkParallel(rh);
 512     }
 513     double smallTs[2] = {-1, -1};
 514     bool limited[2] = {false, false};
 515     for (int index = 0; index < 2; ++index) {
 516         SkPath::Verb cVerb = index ? rVerb : lVerb;
 517         // if the curve is a line, then the line and the ray intersect only at their crossing
 518         if (cVerb == SkPath::kLine_Verb) {
 519             continue;
 520         }
 521         const SkOpSegment& segment = index ? *rh->segment() : *this->segment();
 522         SkIntersections i;
 523         (*CurveIntersectRay[cVerb])(segment.pts(), segment.weight(), rays[index], &i);
 524         double tStart = index ? rh->fStart->t() : this->fStart->t();
 525         double tEnd = index ? rh->fComputedEnd->t() : this->fComputedEnd->t();
 526         bool testAscends = tStart < (index ? rh->fComputedEnd->t() : this->fComputedEnd->t());
 527         double t = testAscends ? 0 : 1;
 528         for (int idx2 = 0; idx2 < i.used(); ++idx2) {
 529             double testT = i[0][idx2];
 530             if (!approximately_between_orderable(tStart, testT, tEnd)) {
 531                 continue;
 532             }
 533             if (approximately_equal_orderable(tStart, testT)) {
 534                 continue;
 535             }
 536             smallTs[index] = t = testAscends ? std::max(t, testT) : std::min(t, testT);
 537             limited[index] = approximately_equal_orderable(t, tEnd);
 538         }
 539     }
 540     bool sRayLonger = false;
 541     SkDVector sCept = {0, 0};
 542     double sCeptT = -1;
 543     int sIndex = -1;
 544     bool useIntersect = false;
 545     for (int index = 0; index < 2; ++index) {
 546         if (smallTs[index] < 0) {
 547             continue;
 548         }
 549         const SkOpSegment& segment = index ? *rh->segment() : *this->segment();
 550         const SkDPoint& dPt = segment.dPtAtT(smallTs[index]);
 551         SkDVector cept = dPt - rays[index][0];
 552         // If this point is on the curve, it should have been detected earlier by ordinary
 553         // curve intersection. This may be hard to determine in general, but for lines,
 554         // the point could be close to or equal to its end, but shouldn't be near the start.
 555         if ((index ? lPts : rPts) == 1) {
 556             SkDVector total = rays[index][1] - rays[index][0];
 557             if (cept.lengthSquared() * 2 < total.lengthSquared()) {
 558                 continue;
 559             }
 560         }
 561         SkDVector end = rays[index][1] - rays[index][0];
 562         if (cept.fX * end.fX < 0 || cept.fY * end.fY < 0) {
 563             continue;
 564         }
 565         double rayDist = cept.length();
 566         double endDist = end.length();
 567         bool rayLonger = rayDist > endDist;
 568         if (limited[0] && limited[1] && rayLonger) {
 569             useIntersect = true;
 570             sRayLonger = rayLonger;
 571             sCept = cept;
 572             sCeptT = smallTs[index];
 573             sIndex = index;
 574             break;
 575         }
 576         double delta = fabs(rayDist - endDist);
 577         double minX, minY, maxX, maxY;
 578         minX = minY = SK_ScalarInfinity;
 579         maxX = maxY = -SK_ScalarInfinity;
 580         const SkDCurve& curve = index ? rh->fPart.fCurve : this->fPart.fCurve;
 581         int ptCount = index ? rPts : lPts;
 582         for (int idx2 = 0; idx2 <= ptCount; ++idx2) {
 583             minX = std::min(minX, curve[idx2].fX);
 584             minY = std::min(minY, curve[idx2].fY);
 585             maxX = std::max(maxX, curve[idx2].fX);
 586             maxY = std::max(maxY, curve[idx2].fY);
 587         }
 588         double maxWidth = std::max(maxX - minX, maxY - minY);
 589         delta = sk_ieee_double_divide(delta, maxWidth);
 590         // FIXME: move these magic numbers
 591         // This fixes skbug.com/8380
 592         // Larger changes (like changing the constant in the next block) cause other
 593         // tests to fail as documented in the bug.
 594         // This could probably become a more general test: e.g., if translating the
 595         // curve causes the cross product of any control point or end point to change
 596         // sign with regard to the opposite curve's hull, treat the curves as parallel.
 597
 598         // Moreso, this points to the general fragility of this approach of assigning
 599         // winding by sorting the angles of curves sharing a common point, as mentioned
 600         // in the bug.
 601         if (delta < 4e-3 && delta > 1e-3 && !useIntersect && fPart.isCurve()
 602                 && rh->fPart.isCurve() && fOriginalCurvePart[0] != fPart.fCurve.fLine[0]) {
 603             // see if original curve is on one side of hull; translated is on the other
 604             const SkDPoint& origin = rh->fOriginalCurvePart[0];
 605             int count = SkPathOpsVerbToPoints(rh->segment()->verb());
 606             const SkDVector line = rh->fOriginalCurvePart[count] - origin;
 607             int originalSide = rh->lineOnOneSide(origin, line, this, true);
 608             if (originalSide >= 0) {
 609                 int translatedSide = rh->lineOnOneSide(origin, line, this, false);
 610                 if (originalSide != translatedSide) {
 611                     continue;
 612                 }
 613             }
 614         }
 615         if (delta > 1e-3 && (useIntersect ^= true)) {
 616             sRayLonger = rayLonger;
 617             sCept = cept;
 618             sCeptT = smallTs[index];
 619             sIndex = index;
 620         }
 621     }
 622     if (useIntersect) {
 623         const SkDCurve& curve = sIndex ? rh->fPart.fCurve : this->fPart.fCurve;
 624         const SkOpSegment& segment = sIndex ? *rh->segment() : *this->segment();
 625         double tStart = sIndex ? rh->fStart->t() : fStart->t();
 626         SkDVector mid = segment.dPtAtT(tStart + (sCeptT - tStart) / 2) - curve[0];
 627         double septDir = mid.crossCheck(sCept);
 628         if (!septDir) {
 629             return checkParallel(rh);
 630         }
 631         return sRayLonger ^ (sIndex == 0) ^ (septDir < 0);
 632     } else {
 633         return checkParallel(rh);
 634     }
 635 }
 636
 637 bool SkOpAngle::endToSide(const SkOpAngle* rh, bool* inside) const {
 638     const SkOpSegment* segment = this->segment();
 639     SkPath::Verb verb = segment->verb();
 640     SkDLine rayEnd;
 641     rayEnd[0].set(this->fEnd->pt());
 642     rayEnd[1] = rayEnd[0];
 643     SkDVector slopeAtEnd = (*CurveDSlopeAtT[verb])(segment->pts(), segment->weight(),
 644             this->fEnd->t());
 645     rayEnd[1].fX += slopeAtEnd.fY;
 646     rayEnd[1].fY -= slopeAtEnd.fX;
 647     SkIntersections iEnd;
 648     const SkOpSegment* oppSegment = rh->segment();
 649     SkPath::Verb oppVerb = oppSegment->verb();
 650     (*CurveIntersectRay[oppVerb])(oppSegment->pts(), oppSegment->weight(), rayEnd, &iEnd);
 651     double endDist;
 652     int closestEnd = iEnd.closestTo(rh->fStart->t(), rh->fEnd->t(), rayEnd[0], &endDist);
 653     if (closestEnd < 0) {
 654         return false;
 655     }
 656     if (!endDist) {
 657         return false;
 658     }
 659     SkDPoint start;
 660     start.set(this->fStart->pt());
 661     // OPTIMIZATION: multiple times in the code we find the max scalar
 662     double minX, minY, maxX, maxY;
 663     minX = minY = SK_ScalarInfinity;
 664     maxX = maxY = -SK_ScalarInfinity;
 665     const SkDCurve& curve = rh->fPart.fCurve;
 666     int oppPts = SkPathOpsVerbToPoints(oppVerb);
 667     for (int idx2 = 0; idx2 <= oppPts; ++idx2) {
 668         minX = std::min(minX, curve[idx2].fX);
 669         minY = std::min(minY, curve[idx2].fY);
 670         maxX = std::max(maxX, curve[idx2].fX);
 671         maxY = std::max(maxY, curve[idx2].fY);
 672     }
 673     double maxWidth = std::max(maxX - minX, maxY - minY);
 674     endDist = sk_ieee_double_divide(endDist, maxWidth);
 675     if (!(endDist >= 5e-12)) {  // empirically found
 676         return false; // ! above catches NaN
 677     }
 678     const SkDPoint* endPt = &rayEnd[0];
 679     SkDPoint oppPt = iEnd.pt(closestEnd);
 680     SkDVector vLeft = *endPt - start;
 681     SkDVector vRight = oppPt - start;
 682     double dir = vLeft.crossNoNormalCheck(vRight);
 683     if (!dir) {
 684         return false;
 685     }
 686     *inside = dir < 0;
 687     return true;
 688 }
 689
 690 /*      y<0 y==0 y>0  x<0 x==0 x>0 xy<0 xy==0 xy>0
 691     0    x                      x               x
 692     1    x                      x          x
 693     2    x                      x    x
 694     3    x                  x        x
 695     4    x             x             x
 696     5    x             x                   x
 697     6    x             x                        x
 698     7         x        x                        x
 699     8             x    x                        x
 700     9             x    x                   x
 701     10            x    x             x
 702     11            x         x        x
 703     12            x             x    x
 704     13            x             x          x
 705     14            x             x               x
 706     15        x                 x               x
 707 */
 708 int SkOpAngle::findSector(SkPath::Verb verb, double x, double y) const {
 709     double absX = fabs(x);
 710     double absY = fabs(y);
 711     double xy = SkPath::kLine_Verb == verb || !AlmostEqualUlps(absX, absY) ? absX - absY : 0;
 712     // If there are four quadrants and eight octants, and since the Latin for sixteen is sedecim,
 713     // one could coin the term sedecimant for a space divided into 16 sections.
 714    // http://english.stackexchange.com/questions/133688/word-for-something-partitioned-into-16-parts
 715     static const int sedecimant[3][3][3] = {
 716     //       y<0           y==0           y>0
 717     //   x<0 x==0 x>0  x<0 x==0 x>0  x<0 x==0 x>0
 718         {{ 4,  3,  2}, { 7, -1, 15}, {10, 11, 12}},  // abs(x) <  abs(y)
 719         {{ 5, -1,  1}, {-1, -1, -1}, { 9, -1, 13}},  // abs(x) == abs(y)
 720         {{ 6,  3,  0}, { 7, -1, 15}, { 8, 11, 14}},  // abs(x) >  abs(y)
 721     };
 722     int sector = sedecimant[(xy >= 0) + (xy > 0)][(y >= 0) + (y > 0)][(x >= 0) + (x > 0)] * 2 + 1;
 723 //    SkASSERT(SkPath::kLine_Verb == verb || sector >= 0);
 724     return sector;
 725 }
 726
 727 SkOpGlobalState* SkOpAngle::globalState() const {
 728     return this->segment()->globalState();
 729 }
 730
 731
 732 // OPTIMIZE: if this loops to only one other angle, after first compare fails, insert on other side
 733 // OPTIMIZE: return where insertion succeeded. Then, start next insertion on opposite side
 734 bool SkOpAngle::insert(SkOpAngle* angle) {
 735     if (angle->fNext) {
 736         if (loopCount() >= angle->loopCount()) {
 737             if (!merge(angle)) {
 738                 return true;
 739             }
 740         } else if (fNext) {
 741             if (!angle->merge(this)) {
 742                 return true;
 743             }
 744         } else {
 745             angle->insert(this);
 746         }
 747         return true;
 748     }
 749     bool singleton = nullptr == fNext;
 750     if (singleton) {
 751         fNext = this;
 752     }
 753     SkOpAngle* next = fNext;
 754     if (next->fNext == this) {
 755         if (singleton || angle->after(this)) {
 756             this->fNext = angle;
 757             angle->fNext = next;
 758         } else {
 759             next->fNext = angle;
 760             angle->fNext = this;
 761         }
 762         debugValidateNext();
 763         return true;
 764     }
 765     SkOpAngle* last = this;
 766     bool flipAmbiguity = false;
 767     do {
 768         SkASSERT(last->fNext == next);
 769         if (angle->after(last) ^ (angle->tangentsAmbiguous() & flipAmbiguity)) {
 770             last->fNext = angle;
 771             angle->fNext = next;
 772             debugValidateNext();
 773             return true;
 774         }
 775         last = next;
 776         if (last == this) {
 777             FAIL_IF(flipAmbiguity);
 778             // We're in a loop. If a sort was ambiguous, flip it to end the loop.
 779             flipAmbiguity = true;
 780         }
 781         next = next->fNext;
 782     } while (true);
 783     return true;
 784 }
 785
 786 SkOpSpanBase* SkOpAngle::lastMarked() const {
 787     if (fLastMarked) {
 788         if (fLastMarked->chased()) {
 789             return nullptr;
 790         }
 791         fLastMarked->setChased(true);
 792     }
 793     return fLastMarked;
 794 }
 795
 796 bool SkOpAngle::loopContains(const SkOpAngle* angle) const {
 797     if (!fNext) {
 798         return false;
 799     }
 800     const SkOpAngle* first = this;
 801     const SkOpAngle* loop = this;
 802     const SkOpSegment* tSegment = angle->fStart->segment();
 803     double tStart = angle->fStart->t();
 804     double tEnd = angle->fEnd->t();
 805     do {
 806         const SkOpSegment* lSegment = loop->fStart->segment();
 807         if (lSegment != tSegment) {
 808             continue;
 809         }
 810         double lStart = loop->fStart->t();
 811         if (lStart != tEnd) {
 812             continue;
 813         }
 814         double lEnd = loop->fEnd->t();
 815         if (lEnd == tStart) {
 816             return true;
 817         }
 818     } while ((loop = loop->fNext) != first);
 819     return false;
 820 }
 821
 822 int SkOpAngle::loopCount() const {
 823     int count = 0;
 824     const SkOpAngle* first = this;
 825     const SkOpAngle* next = this;
 826     do {
 827         next = next->fNext;
 828         ++count;
 829     } while (next && next != first);
 830     return count;
 831 }
 832
 833 bool SkOpAngle::merge(SkOpAngle* angle) {
 834     SkASSERT(fNext);
 835     SkASSERT(angle->fNext);
 836     SkOpAngle* working = angle;
 837     do {
 838         if (this == working) {
 839             return false;
 840         }
 841         working = working->fNext;
 842     } while (working != angle);
 843     do {
 844         SkOpAngle* next = working->fNext;
 845         working->fNext = nullptr;
 846         insert(working);
 847         working = next;
 848     } while (working != angle);
 849     // it's likely that a pair of the angles are unorderable
 850     debugValidateNext();
 851     return true;
 852 }
 853
 854 double SkOpAngle::midT() const {
 855     return (fStart->t() + fEnd->t()) / 2;
 856 }
 857
 858 bool SkOpAngle::midToSide(const SkOpAngle* rh, bool* inside) const {
 859     const SkOpSegment* segment = this->segment();
 860     SkPath::Verb verb = segment->verb();
 861     const SkPoint& startPt = this->fStart->pt();
 862     const SkPoint& endPt = this->fEnd->pt();
 863     SkDPoint dStartPt;
 864     dStartPt.set(startPt);
 865     SkDLine rayMid;
 866     rayMid[0].fX = (startPt.fX + endPt.fX) / 2;
 867     rayMid[0].fY = (startPt.fY + endPt.fY) / 2;
 868     rayMid[1].fX = rayMid[0].fX + (endPt.fY - startPt.fY);
 869     rayMid[1].fY = rayMid[0].fY - (endPt.fX - startPt.fX);
 870     SkIntersections iMid;
 871     (*CurveIntersectRay[verb])(segment->pts(), segment->weight(), rayMid, &iMid);
 872     int iOutside = iMid.mostOutside(this->fStart->t(), this->fEnd->t(), dStartPt);
 873     if (iOutside < 0) {
 874         return false;
 875     }
 876     const SkOpSegment* oppSegment = rh->segment();
 877     SkPath::Verb oppVerb = oppSegment->verb();
 878     SkIntersections oppMid;
 879     (*CurveIntersectRay[oppVerb])(oppSegment->pts(), oppSegment->weight(), rayMid, &oppMid);
 880     int oppOutside = oppMid.mostOutside(rh->fStart->t(), rh->fEnd->t(), dStartPt);
 881     if (oppOutside < 0) {
 882         return false;
 883     }
 884     SkDVector iSide = iMid.pt(iOutside) - dStartPt;
 885     SkDVector oppSide = oppMid.pt(oppOutside) - dStartPt;
 886     double dir = iSide.crossCheck(oppSide);
 887     if (!dir) {
 888         return false;
 889     }
 890     *inside = dir < 0;
 891     return true;
 892 }
 893
 894 bool SkOpAngle::oppositePlanes(const SkOpAngle* rh) const {
 895     int startSpan = SkTAbs(rh->fSectorStart - fSectorStart);
 896     return startSpan >= 8;
 897 }
 898
 899 int SkOpAngle::orderable(SkOpAngle* rh) {
 900     int result;
 901     if (!fPart.isCurve()) {
 902         if (!rh->fPart.isCurve()) {
 903             double leftX = fTangentHalf.dx();
 904             double leftY = fTangentHalf.dy();
 905             double rightX = rh->fTangentHalf.dx();
 906             double rightY = rh->fTangentHalf.dy();
 907             double x_ry = leftX * rightY;
 908             double rx_y = rightX * leftY;
 909             if (x_ry == rx_y) {
 910                 if (leftX * rightX < 0 || leftY * rightY < 0) {
 911                     return 1;  // exactly 180 degrees apart
 912                 }
 913                 goto unorderable;
 914             }
 915             SkASSERT(x_ry != rx_y); // indicates an undetected coincidence -- worth finding earlier
 916             return x_ry < rx_y ? 1 : 0;
 917         }
 918         if ((result = this->lineOnOneSide(rh, false)) >= 0) {
 919             return result;
 920         }
 921         if (fUnorderable || approximately_zero(rh->fSide)) {
 922             goto unorderable;
 923         }
 924     } else if (!rh->fPart.isCurve()) {
 925         if ((result = rh->lineOnOneSide(this, false)) >= 0) {
 926             return result ? 0 : 1;
 927         }
 928         if (rh->fUnorderable || approximately_zero(fSide)) {
 929             goto unorderable;
 930         }
 931     } else if ((result = this->convexHullOverlaps(rh)) >= 0) {
 932         return result;
 933     }
 934     return this->endsIntersect(rh) ? 1 : 0;
 935 unorderable:
 936     fUnorderable = true;
 937     rh->fUnorderable = true;
 938     return -1;
 939 }
 940
 941 // OPTIMIZE: if this shows up in a profile, add a previous pointer
 942 // as is, this should be rarely called
 943 SkOpAngle* SkOpAngle::previous() const {
 944     SkOpAngle* last = fNext;
 945     do {
 946         SkOpAngle* next = last->fNext;
 947         if (next == this) {
 948             return last;
 949         }
 950         last = next;
 951     } while (true);
 952 }
 953
 954 SkOpSegment* SkOpAngle::segment() const {
 955     return fStart->segment();
 956 }
 957
 958 void SkOpAngle::set(SkOpSpanBase* start, SkOpSpanBase* end) {
 959     fStart = start;
 960     fComputedEnd = fEnd = end;
 961     SkASSERT(start != end);
 962     fNext = nullptr;
 963     fComputeSector = fComputedSector = fCheckCoincidence = fTangentsAmbiguous = false;
 964     setSpans();
 965     setSector();
 966     SkDEBUGCODE(fID = start ? start->globalState()->nextAngleID() : -1);
 967 }
 968
 969 void SkOpAngle::setSpans() {
 970     fUnorderable = false;
 971     fLastMarked = nullptr;
 972     if (!fStart) {
 973         fUnorderable = true;
 974         return;
 975     }
 976     const SkOpSegment* segment = fStart->segment();
 977     const SkPoint* pts = segment->pts();
 978     SkDEBUGCODE(fPart.fCurve.fVerb = SkPath::kCubic_Verb);  // required for SkDCurve debug check
 979     SkDEBUGCODE(fPart.fCurve[2].fX = fPart.fCurve[2].fY = fPart.fCurve[3].fX = fPart.fCurve[3].fY
 980             = SK_ScalarNaN);   //  make the non-line part uninitialized
 981     SkDEBUGCODE(fPart.fCurve.fVerb = segment->verb());  //  set the curve type for real
 982     segment->subDivide(fStart, fEnd, &fPart.fCurve);  //  set at least the line part if not more
 983     fOriginalCurvePart = fPart.fCurve;
 984     const SkPath::Verb verb = segment->verb();
 985     fPart.setCurveHullSweep(verb);
 986     if (SkPath::kLine_Verb != verb && !fPart.isCurve()) {
 987         SkDLine lineHalf;
 988         fPart.fCurve[1] = fPart.fCurve[SkPathOpsVerbToPoints(verb)];
 989         fOriginalCurvePart[1] = fPart.fCurve[1];
 990         lineHalf[0].set(fPart.fCurve[0].asSkPoint());
 991         lineHalf[1].set(fPart.fCurve[1].asSkPoint());
 992         fTangentHalf.lineEndPoints(lineHalf);
 993         fSide = 0;
 994     }
 995     switch (verb) {
 996     case SkPath::kLine_Verb: {
 997         SkASSERT(fStart != fEnd);
 998         const SkPoint& cP1 = pts[fStart->t() < fEnd->t()];
 999         SkDLine lineHalf;
1000         lineHalf[0].set(fStart->pt());
1001         lineHalf[1].set(cP1);
1002         fTangentHalf.lineEndPoints(lineHalf);
1003         fSide = 0;
1004         } return;
1005     case SkPath::kQuad_Verb:
1006     case SkPath::kConic_Verb: {
1007         SkLineParameters tangentPart;
1008         (void) tangentPart.quadEndPoints(fPart.fCurve.fQuad);
1009         fSide = -tangentPart.pointDistance(fPart.fCurve[2]);  // not normalized -- compare sign only
1010         } break;
1011     case SkPath::kCubic_Verb: {
1012         SkLineParameters tangentPart;
1013         (void) tangentPart.cubicPart(fPart.fCurve.fCubic);
1014         fSide = -tangentPart.pointDistance(fPart.fCurve[3]);
1015         double testTs[4];
1016         // OPTIMIZATION: keep inflections precomputed with cubic segment?
1017         int testCount = SkDCubic::FindInflections(pts, testTs);
1018         double startT = fStart->t();
1019         double endT = fEnd->t();
1020         double limitT = endT;
1021         int index;
1022         for (index = 0; index < testCount; ++index) {
1023             if (!::between(startT, testTs[index], limitT)) {
1024                 testTs[index] = -1;
1025             }
1026         }
1027         testTs[testCount++] = startT;
1028         testTs[testCount++] = endT;
1029         SkTQSort<double>(testTs, testTs + testCount);
1030         double bestSide = 0;
1031         int testCases = (testCount << 1) - 1;
1032         index = 0;
1033         while (testTs[index] < 0) {
1034             ++index;
1035         }
1036         index <<= 1;
1037         for (; index < testCases; ++index) {
1038             int testIndex = index >> 1;
1039             double testT = testTs[testIndex];
1040             if (index & 1) {
1041                 testT = (testT + testTs[testIndex + 1]) / 2;
1042             }
1043             // OPTIMIZE: could avoid call for t == startT, endT
1044             SkDPoint pt = dcubic_xy_at_t(pts, segment->weight(), testT);
1045             SkLineParameters testPart;
1046             testPart.cubicEndPoints(fPart.fCurve.fCubic);
1047             double testSide = testPart.pointDistance(pt);
1048             if (fabs(bestSide) < fabs(testSide)) {
1049                 bestSide = testSide;
1050             }
1051         }
1052         fSide = -bestSide;  // compare sign only
1053         } break;
1054     default:
1055         SkASSERT(0);
1056     }
1057 }
1058
1059 void SkOpAngle::setSector() {
1060     if (!fStart) {
1061         fUnorderable = true;
1062         return;
1063     }
1064     const SkOpSegment* segment = fStart->segment();
1065     SkPath::Verb verb = segment->verb();
1066     fSectorStart = this->findSector(verb, fPart.fSweep[0].fX, fPart.fSweep[0].fY);
1067     if (fSectorStart < 0) {
1068         goto deferTilLater;
1069     }
1070     if (!fPart.isCurve()) {  // if it's a line or line-like, note that both sectors are the same
1071         SkASSERT(fSectorStart >= 0);
1072         fSectorEnd = fSectorStart;
1073         fSectorMask = 1 << fSectorStart;
1074         return;
1075     }
1076     SkASSERT(SkPath::kLine_Verb != verb);
1077     fSectorEnd = this->findSector(verb, fPart.fSweep[1].fX, fPart.fSweep[1].fY);
1078     if (fSectorEnd < 0) {
1079 deferTilLater:
1080         fSectorStart = fSectorEnd = -1;
1081         fSectorMask = 0;
1082         fComputeSector = true;  // can't determine sector until segment length can be found
1083         return;
1084     }
1085     if (fSectorEnd == fSectorStart
1086             && (fSectorStart & 3) != 3) { // if the sector has no span, it can't be an exact angle
1087         fSectorMask = 1 << fSectorStart;
1088         return;
1089     }
1090     bool crossesZero = this->checkCrossesZero();
1091     int start = std::min(fSectorStart, fSectorEnd);
1092     bool curveBendsCCW = (fSectorStart == start) ^ crossesZero;
1093     // bump the start and end of the sector span if they are on exact compass points
1094     if ((fSectorStart & 3) == 3) {
1095         fSectorStart = (fSectorStart + (curveBendsCCW ? 1 : 31)) & 0x1f;
1096     }
1097     if ((fSectorEnd & 3) == 3) {
1098         fSectorEnd = (fSectorEnd + (curveBendsCCW ? 31 : 1)) & 0x1f;
1099     }
1100     crossesZero = this->checkCrossesZero();
1101     start = std::min(fSectorStart, fSectorEnd);
1102     int end = std::max(fSectorStart, fSectorEnd);
1103     if (!crossesZero) {
1104         fSectorMask = (unsigned) -1 >> (31 - end + start) << start;
1105     } else {
1106         fSectorMask = (unsigned) -1 >> (31 - start) | ((unsigned) -1 << end);
1107     }
1108 }
1109
1110 SkOpSpan* SkOpAngle::starter() {
1111     return fStart->starter(fEnd);
1112 }
1113
1114 bool SkOpAngle::tangentsDiverge(const SkOpAngle* rh, double s0xt0) {
1115     if (s0xt0 == 0) {
1116         return false;
1117     }
1118     // if the ctrl tangents are not nearly parallel, use them
1119     // solve for opposite direction displacement scale factor == m
1120     // initial dir = v1.cross(v2) == v2.x * v1.y - v2.y * v1.x
1121     // displacement of q1[1] : dq1 = { -m * v1.y, m * v1.x } + q1[1]
1122     // straight angle when : v2.x * (dq1.y - q1[0].y) == v2.y * (dq1.x - q1[0].x)
1123     //                       v2.x * (m * v1.x + v1.y) == v2.y * (-m * v1.y + v1.x)
1124     // - m * (v2.x * v1.x + v2.y * v1.y) == v2.x * v1.y - v2.y * v1.x
1125     // m = (v2.y * v1.x - v2.x * v1.y) / (v2.x * v1.x + v2.y * v1.y)
1126     // m = v1.cross(v2) / v1.dot(v2)
1127     const SkDVector* sweep = fPart.fSweep;
1128     const SkDVector* tweep = rh->fPart.fSweep;
1129     double s0dt0 = sweep[0].dot(tweep[0]);
1130     if (!s0dt0) {
1131         return true;
1132     }
1133     SkASSERT(s0dt0 != 0);
1134     double m = s0xt0 / s0dt0;
1135     double sDist = sweep[0].length() * m;
1136     double tDist = tweep[0].length() * m;
1137     bool useS = fabs(sDist) < fabs(tDist);
1138     double mFactor = fabs(useS ? this->distEndRatio(sDist) : rh->distEndRatio(tDist));
1139     fTangentsAmbiguous = mFactor >= 50 && mFactor < 200;
1140     return mFactor < 50;   // empirically found limit
1141 }