src/third_party/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 "SkIntersections.h"
   8 #include "SkOpAngle.h"
   9 #include "SkOpSegment.h"
  10 #include "SkPathOpsCurve.h"
  11 #include "SkTSort.h"
  12
  13 #if DEBUG_ANGLE
  14 #include "SkString.h"
  15 #endif
  16
  17 /* Angles are sorted counterclockwise. The smallest angle has a positive x and the smallest
  18    positive y. The largest angle has a positive x and a zero y. */
  19
  20 #if DEBUG_ANGLE
  21     static bool CompareResult(SkString* bugOut, int append, bool compare) {
  22         SkDebugf("%s %c %d\n", bugOut->c_str(), compare ? 'T' : 'F', append);
  23         return compare;
  24     }
  25
  26     #define COMPARE_RESULT(append, compare) CompareResult(&bugOut, append, 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(const SkOpAngle* test) const {
  62     const SkOpAngle& lh = *test;
  63     const SkOpAngle& rh = *lh.fNext;
  64     SkASSERT(&lh != &rh);
  65 #if DEBUG_ANGLE
  66     SkString bugOut;
  67     bugOut.printf("%s [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
  68                   " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
  69                   " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g ", __FUNCTION__,
  70             lh.fSegment->debugID(), lh.debugID(), lh.fSectorStart, lh.fSectorEnd,
  71             lh.fSegment->t(lh.fStart), lh.fSegment->t(lh.fEnd),
  72             fSegment->debugID(), debugID(), fSectorStart, fSectorEnd, fSegment->t(fStart),
  73             fSegment->t(fEnd),
  74             rh.fSegment->debugID(), rh.debugID(), rh.fSectorStart, rh.fSectorEnd,
  75             rh.fSegment->t(rh.fStart), rh.fSegment->t(rh.fEnd));
  76 #endif
  77     if (lh.fComputeSector && !const_cast<SkOpAngle&>(lh).computeSector()) {
  78         return COMPARE_RESULT(1, true);
  79     }
  80     if (fComputeSector && !const_cast<SkOpAngle*>(this)->computeSector()) {
  81         return COMPARE_RESULT(2, true);
  82     }
  83     if (rh.fComputeSector && !const_cast<SkOpAngle&>(rh).computeSector()) {
  84         return COMPARE_RESULT(3, true);
  85     }
  86 #if DEBUG_ANGLE  // reset bugOut with computed sectors
  87     bugOut.printf("%s [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
  88                   " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
  89                   " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g ", __FUNCTION__,
  90             lh.fSegment->debugID(), lh.debugID(), lh.fSectorStart, lh.fSectorEnd,
  91             lh.fSegment->t(lh.fStart), lh.fSegment->t(lh.fEnd),
  92             fSegment->debugID(), debugID(), fSectorStart, fSectorEnd, fSegment->t(fStart),
  93             fSegment->t(fEnd),
  94             rh.fSegment->debugID(), rh.debugID(), rh.fSectorStart, rh.fSectorEnd,
  95             rh.fSegment->t(rh.fStart), rh.fSegment->t(rh.fEnd));
  96 #endif
  97     bool ltrOverlap = (lh.fSectorMask | rh.fSectorMask) & fSectorMask;
  98     bool lrOverlap = lh.fSectorMask & rh.fSectorMask;
  99     int lrOrder;  // set to -1 if either order works
 100     if (!lrOverlap) {  // no lh/rh sector overlap
 101         if (!ltrOverlap) {  // no lh/this/rh sector overlap
 102             return COMPARE_RESULT(4,  (lh.fSectorEnd > rh.fSectorStart)
 103                     ^ (fSectorStart > lh.fSectorEnd) ^ (fSectorStart > rh.fSectorStart));
 104         }
 105         int lrGap = (rh.fSectorStart - lh.fSectorStart + 32) & 0x1f;
 106         /* A tiny change can move the start +/- 4. The order can only be determined if
 107            lr gap is not 12 to 20 or -12 to -20.
 108                -31 ..-21      1
 109                -20 ..-12     -1
 110                -11 .. -1      0
 111                  0          shouldn't get here
 112                 11 ..  1      1
 113                 12 .. 20     -1
 114                 21 .. 31      0
 115          */
 116         lrOrder = lrGap > 20 ? 0 : lrGap > 11 ? -1 : 1;
 117     } else {
 118         lrOrder = (int) lh.orderable(rh);
 119         if (!ltrOverlap) {
 120             return COMPARE_RESULT(5, !lrOrder);
 121         }
 122     }
 123     int ltOrder;
 124     SkASSERT((lh.fSectorMask & fSectorMask) || (rh.fSectorMask & fSectorMask));
 125     if (lh.fSectorMask & fSectorMask) {
 126         ltOrder = (int) lh.orderable(*this);
 127     } else {
 128         int ltGap = (fSectorStart - lh.fSectorStart + 32) & 0x1f;
 129         ltOrder = ltGap > 20 ? 0 : ltGap > 11 ? -1 : 1;
 130     }
 131     int trOrder;
 132     if (rh.fSectorMask & fSectorMask) {
 133         trOrder = (int) orderable(rh);
 134     } else {
 135         int trGap = (rh.fSectorStart - fSectorStart + 32) & 0x1f;
 136         trOrder = trGap > 20 ? 0 : trGap > 11 ? -1 : 1;
 137     }
 138     if (lrOrder >= 0 && ltOrder >= 0 && trOrder >= 0) {
 139         return COMPARE_RESULT(7, lrOrder ? (ltOrder & trOrder) : (ltOrder | trOrder));
 140     }
 141     SkASSERT(lrOrder >= 0 || ltOrder >= 0 || trOrder >= 0);
 142 // There's not enough information to sort. Get the pairs of angles in opposite planes.
 143 // If an order is < 0, the pair is already in an opposite plane. Check the remaining pairs.
 144     // FIXME : once all variants are understood, rewrite this more simply
 145     if (ltOrder == 0 && lrOrder == 0) {
 146         SkASSERT(trOrder < 0);
 147         // FIXME : once this is verified to work, remove one opposite angle call
 148         SkDEBUGCODE(bool lrOpposite = lh.oppositePlanes(rh));
 149         bool ltOpposite = lh.oppositePlanes(*this);
 150         SkASSERT(lrOpposite != ltOpposite);
 151         return COMPARE_RESULT(8, ltOpposite);
 152     } else if (ltOrder == 1 && trOrder == 0) {
 153         SkASSERT(lrOrder < 0);
 154         SkDEBUGCODE(bool ltOpposite = lh.oppositePlanes(*this));
 155         bool trOpposite = oppositePlanes(rh);
 156         SkASSERT(ltOpposite != trOpposite);
 157         return COMPARE_RESULT(9, trOpposite);
 158     } else if (lrOrder == 1 && trOrder == 1) {
 159         SkASSERT(ltOrder < 0);
 160         SkDEBUGCODE(bool trOpposite = oppositePlanes(rh));
 161         bool lrOpposite = lh.oppositePlanes(rh);
 162         SkASSERT(lrOpposite != trOpposite);
 163         return COMPARE_RESULT(10, lrOpposite);
 164     }
 165     if (lrOrder < 0) {
 166         if (ltOrder < 0) {
 167             return COMPARE_RESULT(11, trOrder);
 168         }
 169         return COMPARE_RESULT(12, ltOrder);
 170     }
 171     return COMPARE_RESULT(13, !lrOrder);
 172 }
 173
 174 // given a line, see if the opposite curve's convex hull is all on one side
 175 // returns -1=not on one side    0=this CW of test   1=this CCW of test
 176 int SkOpAngle::allOnOneSide(const SkOpAngle& test) const {
 177     SkASSERT(!fIsCurve);
 178     SkASSERT(test.fIsCurve);
 179     const SkDPoint& origin = test.fCurvePart[0];
 180     SkVector line;
 181     if (fSegment->verb() == SkPath::kLine_Verb) {
 182         const SkPoint* linePts = fSegment->pts();
 183         int lineStart = fStart < fEnd ? 0 : 1;
 184         line = linePts[lineStart ^ 1] - linePts[lineStart];
 185     } else {
 186         SkPoint shortPts[2] = { fCurvePart[0].asSkPoint(), fCurvePart[1].asSkPoint() };
 187         line = shortPts[1] - shortPts[0];
 188     }
 189     float crosses[3];
 190     SkPath::Verb testVerb = test.fSegment->verb();
 191     int iMax = SkPathOpsVerbToPoints(testVerb);
 192 //    SkASSERT(origin == test.fCurveHalf[0]);
 193     const SkDCubic& testCurve = test.fCurvePart;
 194 //    do {
 195         for (int index = 1; index <= iMax; ++index) {
 196             float xy1 = (float) (line.fX * (testCurve[index].fY - origin.fY));
 197             float xy2 = (float) (line.fY * (testCurve[index].fX - origin.fX));
 198             crosses[index - 1] = AlmostEqualUlps(xy1, xy2) ? 0 : xy1 - xy2;
 199         }
 200         if (crosses[0] * crosses[1] < 0) {
 201             return -1;
 202         }
 203         if (SkPath::kCubic_Verb == testVerb) {
 204             if (crosses[0] * crosses[2] < 0 || crosses[1] * crosses[2] < 0) {
 205                 return -1;
 206             }
 207         }
 208         if (crosses[0]) {
 209             return crosses[0] < 0;
 210         }
 211         if (crosses[1]) {
 212             return crosses[1] < 0;
 213         }
 214         if (SkPath::kCubic_Verb == testVerb && crosses[2]) {
 215             return crosses[2] < 0;
 216         }
 217     fUnorderable = true;
 218     return -1;
 219 }
 220
 221 bool SkOpAngle::calcSlop(double x, double y, double rx, double ry, bool* result) const {
 222     double absX = fabs(x);
 223     double absY = fabs(y);
 224     double length = absX < absY ? absX / 2 + absY : absX + absY / 2;
 225     int exponent;
 226     (void) frexp(length, &exponent);
 227     double epsilon = ldexp(FLT_EPSILON, exponent);
 228     SkPath::Verb verb = fSegment->verb();
 229     SkASSERT(verb == SkPath::kQuad_Verb || verb == SkPath::kCubic_Verb);
 230     // FIXME: the quad and cubic factors are made up ; determine actual values
 231     double slop = verb == SkPath::kQuad_Verb ? 4 * epsilon : 512 * epsilon;
 232     double xSlop = slop;
 233     double ySlop = x * y < 0 ? -xSlop : xSlop; // OPTIMIZATION: use copysign / _copysign ?
 234     double x1 = x - xSlop;
 235     double y1 = y + ySlop;
 236     double x_ry1 = x1 * ry;
 237     double rx_y1 = rx * y1;
 238     *result = x_ry1 < rx_y1;
 239     double x2 = x + xSlop;
 240     double y2 = y - ySlop;
 241     double x_ry2 = x2 * ry;
 242     double rx_y2 = rx * y2;
 243     bool less2 = x_ry2 < rx_y2;
 244     return *result == less2;
 245 }
 246
 247 bool SkOpAngle::checkCrossesZero() const {
 248     int start = SkTMin(fSectorStart, fSectorEnd);
 249     int end = SkTMax(fSectorStart, fSectorEnd);
 250     bool crossesZero = end - start > 16;
 251     return crossesZero;
 252 }
 253
 254 bool SkOpAngle::checkParallel(const SkOpAngle& rh) const {
 255     SkDVector scratch[2];
 256     const SkDVector* sweep, * tweep;
 257     if (!fUnorderedSweep) {
 258         sweep = fSweep;
 259     } else {
 260         scratch[0] = fCurvePart[1] - fCurvePart[0];
 261         sweep = &scratch[0];
 262     }
 263     if (!rh.fUnorderedSweep) {
 264         tweep = rh.fSweep;
 265     } else {
 266         scratch[1] = rh.fCurvePart[1] - rh.fCurvePart[0];
 267         tweep = &scratch[1];
 268     }
 269     double s0xt0 = sweep->crossCheck(*tweep);
 270     if (tangentsDiverge(rh, s0xt0)) {
 271         return s0xt0 < 0;
 272     }
 273     SkDVector m0 = fSegment->dPtAtT(midT()) - fCurvePart[0];
 274     SkDVector m1 = rh.fSegment->dPtAtT(rh.midT()) - rh.fCurvePart[0];
 275     double m0xm1 = m0.crossCheck(m1);
 276     if (m0xm1 == 0) {
 277         fUnorderable = true;
 278         rh.fUnorderable = true;
 279         return true;
 280     }
 281     return m0xm1 < 0;
 282 }
 283
 284 // the original angle is too short to get meaningful sector information
 285 // lengthen it until it is long enough to be meaningful or leave it unset if lengthening it
 286 // would cause it to intersect one of the adjacent angles
 287 bool SkOpAngle::computeSector() {
 288     if (fComputedSector) {
 289         // FIXME: logically, this should return !fUnorderable, but doing so breaks testQuadratic51
 290         // -- but in general, this code may not work so this may be the least of problems
 291         // adding the bang fixes testQuads46x in release, however
 292         return fUnorderable;
 293     }
 294     SkASSERT(fSegment->verb() != SkPath::kLine_Verb && small());
 295     fComputedSector = true;
 296     int step = fStart < fEnd ? 1 : -1;
 297     int limit = step > 0 ? fSegment->count() : -1;
 298     int checkEnd = fEnd;
 299     do {
 300 // advance end
 301         const SkOpSpan& span = fSegment->span(checkEnd);
 302         const SkOpSegment* other = span.fOther;
 303         int oCount = other->count();
 304         for (int oIndex = 0; oIndex < oCount; ++oIndex) {
 305             const SkOpSpan& oSpan = other->span(oIndex);
 306             if (oSpan.fOther != fSegment) {
 307                 continue;
 308             }
 309             if (oSpan.fOtherIndex == checkEnd) {
 310                 continue;
 311             }
 312             if (!approximately_equal(oSpan.fOtherT, span.fT)) {
 313                 continue;
 314             }
 315             goto recomputeSector;
 316         }
 317         checkEnd += step;
 318     } while (checkEnd != limit);
 319 recomputeSector:
 320     if (checkEnd == fEnd || checkEnd - step == fEnd) {
 321         fUnorderable = true;
 322         return false;
 323     }
 324     int saveEnd = fEnd;
 325     fEnd = checkEnd - step;
 326     setSpans();
 327     setSector();
 328     fEnd = saveEnd;
 329     return !fUnorderable;
 330 }
 331
 332 // returns -1 if overlaps   0 if no overlap cw    1 if no overlap ccw
 333 int SkOpAngle::convexHullOverlaps(const SkOpAngle& rh) const {
 334     const SkDVector* sweep = fSweep;
 335     const SkDVector* tweep = rh.fSweep;
 336     double s0xs1 = sweep[0].crossCheck(sweep[1]);
 337     double s0xt0 = sweep[0].crossCheck(tweep[0]);
 338     double s1xt0 = sweep[1].crossCheck(tweep[0]);
 339     bool tBetweenS = s0xs1 > 0 ? s0xt0 > 0 && s1xt0 < 0 : s0xt0 < 0 && s1xt0 > 0;
 340     double s0xt1 = sweep[0].crossCheck(tweep[1]);
 341     double s1xt1 = sweep[1].crossCheck(tweep[1]);
 342     tBetweenS |= s0xs1 > 0 ? s0xt1 > 0 && s1xt1 < 0 : s0xt1 < 0 && s1xt1 > 0;
 343     double t0xt1 = tweep[0].crossCheck(tweep[1]);
 344     if (tBetweenS) {
 345         return -1;
 346     }
 347     if ((s0xt0 == 0 && s1xt1 == 0) || (s1xt0 == 0 && s0xt1 == 0)) {  // s0 to s1 equals t0 to t1
 348         return -1;
 349     }
 350     bool sBetweenT = t0xt1 > 0 ? s0xt0 < 0 && s0xt1 > 0 : s0xt0 > 0 && s0xt1 < 0;
 351     sBetweenT |= t0xt1 > 0 ? s1xt0 < 0 && s1xt1 > 0 : s1xt0 > 0 && s1xt1 < 0;
 352     if (sBetweenT) {
 353         return -1;
 354     }
 355     // if all of the sweeps are in the same half plane, then the order of any pair is enough
 356     if (s0xt0 >= 0 && s0xt1 >= 0 && s1xt0 >= 0 && s1xt1 >= 0) {
 357         return 0;
 358     }
 359     if (s0xt0 <= 0 && s0xt1 <= 0 && s1xt0 <= 0 && s1xt1 <= 0) {
 360         return 1;
 361     }
 362     // if the outside sweeps are greater than 180 degress:
 363         // first assume the inital tangents are the ordering
 364         // if the midpoint direction matches the inital order, that is enough
 365     SkDVector m0 = fSegment->dPtAtT(midT()) - fCurvePart[0];
 366     SkDVector m1 = rh.fSegment->dPtAtT(rh.midT()) - rh.fCurvePart[0];
 367     double m0xm1 = m0.crossCheck(m1);
 368     if (s0xt0 > 0 && m0xm1 > 0) {
 369         return 0;
 370     }
 371     if (s0xt0 < 0 && m0xm1 < 0) {
 372         return 1;
 373     }
 374     if (tangentsDiverge(rh, s0xt0)) {
 375         return s0xt0 < 0;
 376     }
 377     return m0xm1 < 0;
 378 }
 379
 380 // OPTIMIZATION: longest can all be either lazily computed here or precomputed in setup
 381 double SkOpAngle::distEndRatio(double dist) const {
 382     double longest = 0;
 383     const SkOpSegment& segment = *this->segment();
 384     int ptCount = SkPathOpsVerbToPoints(segment.verb());
 385     const SkPoint* pts = segment.pts();
 386     for (int idx1 = 0; idx1 <= ptCount - 1; ++idx1) {
 387         for (int idx2 = idx1 + 1; idx2 <= ptCount; ++idx2) {
 388             if (idx1 == idx2) {
 389                 continue;
 390             }
 391             SkDVector v;
 392             v.set(pts[idx2] - pts[idx1]);
 393             double lenSq = v.lengthSquared();
 394             longest = SkTMax(longest, lenSq);
 395         }
 396     }
 397     return sqrt(longest) / dist;
 398 }
 399
 400 bool SkOpAngle::endsIntersect(const SkOpAngle& rh) const {
 401     SkPath::Verb lVerb = fSegment->verb();
 402     SkPath::Verb rVerb = rh.fSegment->verb();
 403     int lPts = SkPathOpsVerbToPoints(lVerb);
 404     int rPts = SkPathOpsVerbToPoints(rVerb);
 405     SkDLine rays[] = {{{fCurvePart[0], rh.fCurvePart[rPts]}},
 406             {{fCurvePart[0], fCurvePart[lPts]}}};
 407     if (rays[0][1] == rays[1][1]) {
 408         return checkParallel(rh);
 409     }
 410     double smallTs[2] = {-1, -1};
 411     bool limited[2] = {false, false};
 412     for (int index = 0; index < 2; ++index) {
 413         const SkOpSegment& segment = index ? *rh.fSegment : *fSegment;
 414         SkIntersections i;
 415         (*CurveIntersectRay[index ? rPts : lPts])(segment.pts(), rays[index], &i);
 416 //      SkASSERT(i.used() >= 1);
 417         if (i.used() <= 1) {
 418             continue;
 419         }
 420         double tStart = segment.t(index ? rh.fStart : fStart);
 421         double tEnd = segment.t(index ? rh.fEnd : fEnd);
 422         bool testAscends = index ? rh.fStart < rh.fEnd : fStart < fEnd;
 423         double t = testAscends ? 0 : 1;
 424         for (int idx2 = 0; idx2 < i.used(); ++idx2) {
 425             double testT = i[0][idx2];
 426             if (!approximately_between_orderable(tStart, testT, tEnd)) {
 427                 continue;
 428             }
 429             if (approximately_equal_orderable(tStart, testT)) {
 430                 continue;
 431             }
 432             smallTs[index] = t = testAscends ? SkTMax(t, testT) : SkTMin(t, testT);
 433             limited[index] = approximately_equal_orderable(t, tEnd);
 434         }
 435     }
 436 #if 0
 437     if (smallTs[0] < 0 && smallTs[1] < 0) {  // if neither ray intersects, do endpoint sort
 438         double m0xm1 = 0;
 439         if (lVerb == SkPath::kLine_Verb) {
 440             SkASSERT(rVerb != SkPath::kLine_Verb);
 441             SkDVector m0 = rays[1][1] - fCurvePart[0];
 442             SkDPoint endPt;
 443             endPt.set(rh.fSegment->pts()[rh.fStart < rh.fEnd ? rPts : 0]);
 444             SkDVector m1 = endPt - fCurvePart[0];
 445             m0xm1 = m0.crossCheck(m1);
 446         }
 447         if (rVerb == SkPath::kLine_Verb) {
 448             SkDPoint endPt;
 449             endPt.set(fSegment->pts()[fStart < fEnd ? lPts : 0]);
 450             SkDVector m0 = endPt - fCurvePart[0];
 451             SkDVector m1 = rays[0][1] - fCurvePart[0];
 452             m0xm1 = m0.crossCheck(m1);
 453         }
 454         if (m0xm1 != 0) {
 455             return m0xm1 < 0;
 456         }
 457     }
 458 #endif
 459     bool sRayLonger = false;
 460     SkDVector sCept = {0, 0};
 461     double sCeptT = -1;
 462     int sIndex = -1;
 463     bool useIntersect = false;
 464     for (int index = 0; index < 2; ++index) {
 465         if (smallTs[index] < 0) {
 466             continue;
 467         }
 468         const SkOpSegment& segment = index ? *rh.fSegment : *fSegment;
 469         const SkDPoint& dPt = segment.dPtAtT(smallTs[index]);
 470         SkDVector cept = dPt - rays[index][0];
 471         // If this point is on the curve, it should have been detected earlier by ordinary
 472         // curve intersection. This may be hard to determine in general, but for lines,
 473         // the point could be close to or equal to its end, but shouldn't be near the start.
 474         if ((index ? lPts : rPts) == 1) {
 475             SkDVector total = rays[index][1] - rays[index][0];
 476             if (cept.lengthSquared() * 2 < total.lengthSquared()) {
 477                 continue;
 478             }
 479         }
 480         SkDVector end = rays[index][1] - rays[index][0];
 481         if (cept.fX * end.fX < 0 || cept.fY * end.fY < 0) {
 482             continue;
 483         }
 484         double rayDist = cept.length();
 485         double endDist = end.length();
 486         bool rayLonger = rayDist > endDist;
 487         if (limited[0] && limited[1] && rayLonger) {
 488             useIntersect = true;
 489             sRayLonger = rayLonger;
 490             sCept = cept;
 491             sCeptT = smallTs[index];
 492             sIndex = index;
 493             break;
 494         }
 495         double delta = fabs(rayDist - endDist);
 496         double minX, minY, maxX, maxY;
 497         minX = minY = SK_ScalarInfinity;
 498         maxX = maxY = -SK_ScalarInfinity;
 499         const SkDCubic& curve = index ? rh.fCurvePart : fCurvePart;
 500         int ptCount = index ? rPts : lPts;
 501         for (int idx2 = 0; idx2 <= ptCount; ++idx2) {
 502             minX = SkTMin(minX, curve[idx2].fX);
 503             minY = SkTMin(minY, curve[idx2].fY);
 504             maxX = SkTMax(maxX, curve[idx2].fX);
 505             maxY = SkTMax(maxY, curve[idx2].fY);
 506         }
 507         double maxWidth = SkTMax(maxX - minX, maxY - minY);
 508         delta /= maxWidth;
 509         if (delta > 1e-4 && (useIntersect ^= true)) {  // FIXME: move this magic number
 510             sRayLonger = rayLonger;
 511             sCept = cept;
 512             sCeptT = smallTs[index];
 513             sIndex = index;
 514         }
 515     }
 516     if (useIntersect) {
 517         const SkDCubic& curve = sIndex ? rh.fCurvePart : fCurvePart;
 518         const SkOpSegment& segment = sIndex ? *rh.fSegment : *fSegment;
 519         double tStart = segment.t(sIndex ? rh.fStart : fStart);
 520         SkDVector mid = segment.dPtAtT(tStart + (sCeptT - tStart) / 2) - curve[0];
 521         double septDir = mid.crossCheck(sCept);
 522         if (!septDir) {
 523             return checkParallel(rh);
 524         }
 525         return sRayLonger ^ (sIndex == 0) ^ (septDir < 0);
 526     } else {
 527         return checkParallel(rh);
 528     }
 529 }
 530
 531 // Most of the time, the first one can be found trivially by detecting the smallest sector value.
 532 // If all angles have the same sector value, actual sorting is required.
 533 const SkOpAngle* SkOpAngle::findFirst() const {
 534     const SkOpAngle* best = this;
 535     int bestStart = SkTMin(fSectorStart, fSectorEnd);
 536     const SkOpAngle* angle = this;
 537     while ((angle = angle->fNext) != this) {
 538         int angleEnd = SkTMax(angle->fSectorStart, angle->fSectorEnd);
 539         if (angleEnd < bestStart) {
 540             return angle;    // we wrapped around
 541         }
 542         int angleStart = SkTMin(angle->fSectorStart, angle->fSectorEnd);
 543         if (bestStart > angleStart) {
 544             best = angle;
 545             bestStart = angleStart;
 546         }
 547     }
 548     // back up to the first possible angle
 549     const SkOpAngle* firstBest = best;
 550     angle = best;
 551     int bestEnd = SkTMax(best->fSectorStart, best->fSectorEnd);
 552     while ((angle = angle->previous()) != firstBest) {
 553         if (angle->fStop) {
 554             break;
 555         }
 556         int angleStart = SkTMin(angle->fSectorStart, angle->fSectorEnd);
 557         // angles that are smaller by one aren't necessary better, since the larger may be a line
 558         // and the smaller may be a curve that curls to the other side of the line.
 559         if (bestEnd + 1 < angleStart) {
 560             return best;
 561         }
 562         best = angle;
 563         bestEnd = SkTMax(angle->fSectorStart, angle->fSectorEnd);
 564     }
 565     // in the case where all angles are nearly in the same sector, check the order to find the best
 566     firstBest = best;
 567     angle = best;
 568     do {
 569         angle = angle->fNext;
 570         if (angle->fStop) {
 571             return firstBest;
 572         }
 573         bool orderable = best->orderable(*angle);  // note: may return an unorderable angle
 574         if (orderable == 0) {
 575             return angle;
 576         }
 577         best = angle;
 578     } while (angle != firstBest);
 579     // if the angles are equally ordered, fall back on the initial tangent
 580     bool foundBelow = false;
 581     while ((angle = angle->fNext)) {
 582         SkDVector scratch[2];
 583         const SkDVector* sweep;
 584         if (!angle->fUnorderedSweep) {
 585             sweep = angle->fSweep;
 586         } else {
 587             scratch[0] = angle->fCurvePart[1] - angle->fCurvePart[0];
 588             sweep = &scratch[0];
 589         }
 590         bool isAbove = sweep->fY <= 0;
 591         if (isAbove && foundBelow) {
 592             return angle;
 593         }
 594         foundBelow |= !isAbove;
 595         if (angle == firstBest) {
 596             return NULL; // should not loop around
 597         }
 598     }
 599     SkASSERT(0);  // should never get here
 600     return NULL;
 601 }
 602
 603 /*      y<0 y==0 y>0  x<0 x==0 x>0 xy<0 xy==0 xy>0
 604     0    x                      x               x
 605     1    x                      x          x
 606     2    x                      x    x
 607     3    x                  x        x
 608     4    x             x             x
 609     5    x             x                   x
 610     6    x             x                        x
 611     7         x        x                        x
 612     8             x    x                        x
 613     9             x    x                   x
 614     10            x    x             x
 615     11            x         x        x
 616     12            x             x    x
 617     13            x             x          x
 618     14            x             x               x
 619     15        x                 x               x
 620 */
 621 int SkOpAngle::findSector(SkPath::Verb verb, double x, double y) const {
 622     double absX = fabs(x);
 623     double absY = fabs(y);
 624     double xy = SkPath::kLine_Verb == verb || !AlmostEqualUlps(absX, absY) ? absX - absY : 0;
 625     // If there are four quadrants and eight octants, and since the Latin for sixteen is sedecim,
 626     // one could coin the term sedecimant for a space divided into 16 sections.
 627    // http://english.stackexchange.com/questions/133688/word-for-something-partitioned-into-16-parts
 628     static const int sedecimant[3][3][3] = {
 629     //       y<0           y==0           y>0
 630     //   x<0 x==0 x>0  x<0 x==0 x>0  x<0 x==0 x>0
 631         {{ 4,  3,  2}, { 7, -1, 15}, {10, 11, 12}},  // abs(x) <  abs(y)
 632         {{ 5, -1,  1}, {-1, -1, -1}, { 9, -1, 13}},  // abs(x) == abs(y)
 633         {{ 6,  3,  0}, { 7, -1, 15}, { 8, 11, 14}},  // abs(x) >  abs(y)
 634     };
 635     int sector = sedecimant[(xy >= 0) + (xy > 0)][(y >= 0) + (y > 0)][(x >= 0) + (x > 0)] * 2 + 1;
 636     SkASSERT(SkPath::kLine_Verb == verb || sector >= 0);
 637     return sector;
 638 }
 639
 640 // OPTIMIZE: if this loops to only one other angle, after first compare fails, insert on other side
 641 // OPTIMIZE: return where insertion succeeded. Then, start next insertion on opposite side
 642 void SkOpAngle::insert(SkOpAngle* angle) {
 643     if (angle->fNext) {
 644         if (loopCount() >= angle->loopCount()) {
 645             if (!merge(angle)) {
 646                 return;
 647             }
 648         } else if (fNext) {
 649             if (!angle->merge(this)) {
 650                 return;
 651             }
 652         } else {
 653             angle->insert(this);
 654         }
 655         return;
 656     }
 657     bool singleton = NULL == fNext;
 658     if (singleton) {
 659         fNext = this;
 660     }
 661     SkOpAngle* next = fNext;
 662     if (next->fNext == this) {
 663         if (angle->overlap(*this)) {
 664             return;
 665         }
 666         if (singleton || angle->after(this)) {
 667             this->fNext = angle;
 668             angle->fNext = next;
 669         } else {
 670             next->fNext = angle;
 671             angle->fNext = this;
 672         }
 673         debugValidateNext();
 674         return;
 675     }
 676     SkOpAngle* last = this;
 677     do {
 678         SkASSERT(last->fNext == next);
 679         if (angle->overlap(*last) || angle->overlap(*next)) {
 680             return;
 681         }
 682         if (angle->after(last)) {
 683             last->fNext = angle;
 684             angle->fNext = next;
 685             debugValidateNext();
 686             return;
 687         }
 688         last = next;
 689         next = next->fNext;
 690         if (last == this && next->fUnorderable) {
 691             fUnorderable = true;
 692             return;
 693         }
 694         SkASSERT(last != this);
 695     } while (true);
 696 }
 697
 698 bool SkOpAngle::isHorizontal() const {
 699     return !fIsCurve && fSweep[0].fY == 0;
 700 }
 701
 702 SkOpSpan* SkOpAngle::lastMarked() const {
 703     if (fLastMarked) {
 704         if (fLastMarked->fChased) {
 705             return NULL;
 706         }
 707         fLastMarked->fChased = true;
 708     }
 709     return fLastMarked;
 710 }
 711
 712 bool SkOpAngle::loopContains(const SkOpAngle& test) const {
 713     if (!fNext) {
 714         return false;
 715     }
 716     const SkOpAngle* first = this;
 717     const SkOpAngle* loop = this;
 718     const SkOpSegment* tSegment = test.fSegment;
 719     double tStart = tSegment->span(test.fStart).fT;
 720     double tEnd = tSegment->span(test.fEnd).fT;
 721     do {
 722         const SkOpSegment* lSegment = loop->fSegment;
 723         // FIXME : use precisely_equal ? or compare points exactly ?
 724         if (lSegment != tSegment) {
 725             continue;
 726         }
 727         double lStart = lSegment->span(loop->fStart).fT;
 728         if (lStart != tEnd) {
 729             continue;
 730         }
 731         double lEnd = lSegment->span(loop->fEnd).fT;
 732         if (lEnd == tStart) {
 733             return true;
 734         }
 735     } while ((loop = loop->fNext) != first);
 736     return false;
 737 }
 738
 739 int SkOpAngle::loopCount() const {
 740     int count = 0;
 741     const SkOpAngle* first = this;
 742     const SkOpAngle* next = this;
 743     do {
 744         next = next->fNext;
 745         ++count;
 746     } while (next && next != first);
 747     return count;
 748 }
 749
 750 // OPTIMIZATION: can this be done better in after when angles are sorted?
 751 void SkOpAngle::markStops() {
 752     SkOpAngle* angle = this;
 753     int lastEnd = SkTMax(fSectorStart, fSectorEnd);
 754     do {
 755         angle = angle->fNext;
 756         int angleStart = SkTMin(angle->fSectorStart, angle->fSectorEnd);
 757         // angles that are smaller by one aren't necessary better, since the larger may be a line
 758         // and the smaller may be a curve that curls to the other side of the line.
 759         if (lastEnd + 1 < angleStart) {
 760             angle->fStop = true;
 761         }
 762         lastEnd = SkTMax(angle->fSectorStart, angle->fSectorEnd);
 763     } while (angle != this);
 764 }
 765
 766 bool SkOpAngle::merge(SkOpAngle* angle) {
 767     SkASSERT(fNext);
 768     SkASSERT(angle->fNext);
 769     SkOpAngle* working = angle;
 770     do {
 771         if (this == working) {
 772             return false;
 773         }
 774         working = working->fNext;
 775     } while (working != angle);
 776     do {
 777         SkOpAngle* next = working->fNext;
 778         working->fNext = NULL;
 779         insert(working);
 780         working = next;
 781     } while (working != angle);
 782     // it's likely that a pair of the angles are unorderable
 783 #if DEBUG_ANGLE
 784     SkOpAngle* last = angle;
 785     working = angle->fNext;
 786     do {
 787         SkASSERT(last->fNext == working);
 788         last->fNext = working->fNext;
 789         SkASSERT(working->after(last));
 790         last->fNext = working;
 791         last = working;
 792         working = working->fNext;
 793     } while (last != angle);
 794 #endif
 795     debugValidateNext();
 796     return true;
 797 }
 798
 799 double SkOpAngle::midT() const {
 800     return (fSegment->t(fStart) + fSegment->t(fEnd)) / 2;
 801 }
 802
 803 bool SkOpAngle::oppositePlanes(const SkOpAngle& rh) const {
 804     int startSpan = abs(rh.fSectorStart - fSectorStart);
 805     return startSpan >= 8;
 806 }
 807
 808 bool SkOpAngle::orderable(const SkOpAngle& rh) const {
 809     int result;
 810     if (!fIsCurve) {
 811         if (!rh.fIsCurve) {
 812             double leftX = fTangentHalf.dx();
 813             double leftY = fTangentHalf.dy();
 814             double rightX = rh.fTangentHalf.dx();
 815             double rightY = rh.fTangentHalf.dy();
 816             double x_ry = leftX * rightY;
 817             double rx_y = rightX * leftY;
 818             if (x_ry == rx_y) {
 819                 if (leftX * rightX < 0 || leftY * rightY < 0) {
 820                     return true;  // exactly 180 degrees apart
 821                 }
 822                 goto unorderable;
 823             }
 824             SkASSERT(x_ry != rx_y); // indicates an undetected coincidence -- worth finding earlier
 825             return x_ry < rx_y;
 826         }
 827         if ((result = allOnOneSide(rh)) >= 0) {
 828             return result;
 829         }
 830         if (fUnorderable || approximately_zero(rh.fSide)) {
 831             goto unorderable;
 832         }
 833     } else if (!rh.fIsCurve) {
 834         if ((result = rh.allOnOneSide(*this)) >= 0) {
 835             return !result;
 836         }
 837         if (rh.fUnorderable || approximately_zero(fSide)) {
 838             goto unorderable;
 839         }
 840     }
 841     if ((result = convexHullOverlaps(rh)) >= 0) {
 842         return result;
 843     }
 844     return endsIntersect(rh);
 845 unorderable:
 846     fUnorderable = true;
 847     rh.fUnorderable = true;
 848     return true;
 849 }
 850
 851 bool SkOpAngle::overlap(const SkOpAngle& other) const {
 852     int min = SkTMin(fStart, fEnd);
 853     const SkOpSpan& span = fSegment->span(min);
 854     const SkOpSegment* oSeg = other.fSegment;
 855     int oMin = SkTMin(other.fStart, other.fEnd);
 856     const SkOpSpan& oSpan = oSeg->span(oMin);
 857     if (!span.fSmall && !oSpan.fSmall) {
 858         return false;
 859     }
 860     if (fSegment->span(fStart).fPt != oSeg->span(other.fStart).fPt) {
 861         return false;
 862     }
 863     // see if small span is contained by opposite span
 864     return span.fSmall ? oSeg->containsPt(fSegment->span(fEnd).fPt, other.fEnd, other.fStart)
 865             : fSegment->containsPt(oSeg->span(other.fEnd).fPt, fEnd, fStart);
 866 }
 867
 868 // OPTIMIZE: if this shows up in a profile, add a previous pointer
 869 // as is, this should be rarely called
 870 SkOpAngle* SkOpAngle::previous() const {
 871     SkOpAngle* last = fNext;
 872     do {
 873         SkOpAngle* next = last->fNext;
 874         if (next == this) {
 875             return last;
 876         }
 877         last = next;
 878     } while (true);
 879 }
 880
 881 void SkOpAngle::set(const SkOpSegment* segment, int start, int end) {
 882 #if DEBUG_ANGLE
 883     fID = 0;
 884 #endif
 885     fSegment = segment;
 886     fStart = start;
 887     fEnd = end;
 888     fNext = NULL;
 889     fComputeSector = fComputedSector = false;
 890     fStop = false;
 891     setSpans();
 892     setSector();
 893 }
 894
 895 void SkOpAngle::setCurveHullSweep() {
 896     fUnorderedSweep = false;
 897     fSweep[0] = fCurvePart[1] - fCurvePart[0];
 898     if (SkPath::kLine_Verb == fSegment->verb()) {
 899         fSweep[1] = fSweep[0];
 900         return;
 901     }
 902     fSweep[1] = fCurvePart[2] - fCurvePart[0];
 903     if (SkPath::kCubic_Verb != fSegment->verb()) {
 904         if (!fSweep[0].fX && !fSweep[0].fY) {
 905             fSweep[0] = fSweep[1];
 906         }
 907         return;
 908     }
 909     SkDVector thirdSweep = fCurvePart[3] - fCurvePart[0];
 910     if (fSweep[0].fX == 0 && fSweep[0].fY == 0) {
 911         fSweep[0] = fSweep[1];
 912         fSweep[1] = thirdSweep;
 913         if (fSweep[0].fX == 0 && fSweep[0].fY == 0) {
 914             fSweep[0] = fSweep[1];
 915             fCurvePart[1] = fCurvePart[3];
 916             fIsCurve = false;
 917         }
 918         return;
 919     }
 920     double s1x3 = fSweep[0].crossCheck(thirdSweep);
 921     double s3x2 = thirdSweep.crossCheck(fSweep[1]);
 922     if (s1x3 * s3x2 >= 0) {  // if third vector is on or between first two vectors
 923         return;
 924     }
 925     double s2x1 = fSweep[1].crossCheck(fSweep[0]);
 926     // FIXME: If the sweep of the cubic is greater than 180 degrees, we're in trouble
 927     // probably such wide sweeps should be artificially subdivided earlier so that never happens
 928     SkASSERT(s1x3 * s2x1 < 0 || s1x3 * s3x2 < 0);
 929     if (s3x2 * s2x1 < 0) {
 930         SkASSERT(s2x1 * s1x3 > 0);
 931         fSweep[0] = fSweep[1];
 932         fUnorderedSweep = true;
 933     }
 934     fSweep[1] = thirdSweep;
 935 }
 936
 937 void SkOpAngle::setSector() {
 938     SkPath::Verb verb = fSegment->verb();
 939     if (SkPath::kLine_Verb != verb && small()) {
 940         fSectorStart = fSectorEnd = -1;
 941         fSectorMask = 0;
 942         fComputeSector = true;  // can't determine sector until segment length can be found
 943         return;
 944     }
 945     fSectorStart = findSector(verb, fSweep[0].fX, fSweep[0].fY);
 946     if (!fIsCurve) {  // if it's a line or line-like, note that both sectors are the same
 947         SkASSERT(fSectorStart >= 0);
 948         fSectorEnd = fSectorStart;
 949         fSectorMask = 1 << fSectorStart;
 950         return;
 951     }
 952     SkASSERT(SkPath::kLine_Verb != verb);
 953     fSectorEnd = findSector(verb, fSweep[1].fX, fSweep[1].fY);
 954     if (fSectorEnd == fSectorStart) {
 955         SkASSERT((fSectorStart & 3) != 3);  // if the sector has no span, it can't be an exact angle
 956         fSectorMask = 1 << fSectorStart;
 957         return;
 958     }
 959     bool crossesZero = checkCrossesZero();
 960     int start = SkTMin(fSectorStart, fSectorEnd);
 961     bool curveBendsCCW = (fSectorStart == start) ^ crossesZero;
 962     // bump the start and end of the sector span if they are on exact compass points
 963     if ((fSectorStart & 3) == 3) {
 964         fSectorStart = (fSectorStart + (curveBendsCCW ? 1 : 31)) & 0x1f;
 965     }
 966     if ((fSectorEnd & 3) == 3) {
 967         fSectorEnd = (fSectorEnd + (curveBendsCCW ? 31 : 1)) & 0x1f;
 968     }
 969     crossesZero = checkCrossesZero();
 970     start = SkTMin(fSectorStart, fSectorEnd);
 971     int end = SkTMax(fSectorStart, fSectorEnd);
 972     if (!crossesZero) {
 973         fSectorMask = (unsigned) -1 >> (31 - end + start) << start;
 974     } else {
 975         fSectorMask = (unsigned) -1 >> (31 - start) | (-1 << end);
 976     }
 977 }
 978
 979 void SkOpAngle::setSpans() {
 980     fUnorderable = fSegment->isTiny(this);
 981     fLastMarked = NULL;
 982     const SkPoint* pts = fSegment->pts();
 983     SkDEBUGCODE(fCurvePart[2].fX = fCurvePart[2].fY = fCurvePart[3].fX = fCurvePart[3].fY
 984             = SK_ScalarNaN);
 985     fSegment->subDivide(fStart, fEnd, &fCurvePart);
 986     setCurveHullSweep();
 987     const SkPath::Verb verb = fSegment->verb();
 988     if (verb != SkPath::kLine_Verb
 989             && !(fIsCurve = fSweep[0].crossCheck(fSweep[1]) != 0)) {
 990         SkDLine lineHalf;
 991         lineHalf[0].set(fCurvePart[0].asSkPoint());
 992         lineHalf[1].set(fCurvePart[SkPathOpsVerbToPoints(verb)].asSkPoint());
 993         fTangentHalf.lineEndPoints(lineHalf);
 994         fSide = 0;
 995     }
 996     switch (verb) {
 997     case SkPath::kLine_Verb: {
 998         SkASSERT(fStart != fEnd);
 999         const SkPoint& cP1 = pts[fStart < fEnd];
1000         SkDLine lineHalf;
1001         lineHalf[0].set(fSegment->span(fStart).fPt);
1002         lineHalf[1].set(cP1);
1003         fTangentHalf.lineEndPoints(lineHalf);
1004         fSide = 0;
1005         fIsCurve = false;
1006         } return;
1007     case SkPath::kQuad_Verb: {
1008         SkLineParameters tangentPart;
1009         SkDQuad& quad2 = *SkTCast<SkDQuad*>(&fCurvePart);
1010         (void) tangentPart.quadEndPoints(quad2);
1011         fSide = -tangentPart.pointDistance(fCurvePart[2]);  // not normalized -- compare sign only
1012         } break;
1013     case SkPath::kCubic_Verb: {
1014         SkLineParameters tangentPart;
1015         (void) tangentPart.cubicPart(fCurvePart);
1016         fSide = -tangentPart.pointDistance(fCurvePart[3]);
1017         double testTs[4];
1018         // OPTIMIZATION: keep inflections precomputed with cubic segment?
1019         int testCount = SkDCubic::FindInflections(pts, testTs);
1020         double startT = fSegment->t(fStart);
1021         double endT = fSegment->t(fEnd);
1022         double limitT = endT;
1023         int index;
1024         for (index = 0; index < testCount; ++index) {
1025             if (!::between(startT, testTs[index], limitT)) {
1026                 testTs[index] = -1;
1027             }
1028         }
1029         testTs[testCount++] = startT;
1030         testTs[testCount++] = endT;
1031         SkTQSort<double>(testTs, &testTs[testCount - 1]);
1032         double bestSide = 0;
1033         int testCases = (testCount << 1) - 1;
1034         index = 0;
1035         while (testTs[index] < 0) {
1036             ++index;
1037         }
1038         index <<= 1;
1039         for (; index < testCases; ++index) {
1040             int testIndex = index >> 1;
1041             double testT = testTs[testIndex];
1042             if (index & 1) {
1043                 testT = (testT + testTs[testIndex + 1]) / 2;
1044             }
1045             // OPTIMIZE: could avoid call for t == startT, endT
1046             SkDPoint pt = dcubic_xy_at_t(pts, testT);
1047             SkLineParameters tangentPart;
1048             tangentPart.cubicEndPoints(fCurvePart);
1049             double testSide = tangentPart.pointDistance(pt);
1050             if (fabs(bestSide) < fabs(testSide)) {
1051                 bestSide = testSide;
1052             }
1053         }
1054         fSide = -bestSide;  // compare sign only
1055         } break;
1056     default:
1057         SkASSERT(0);
1058     }
1059 }
1060
1061 bool SkOpAngle::small() const {
1062     int min = SkMin32(fStart, fEnd);
1063     int max = SkMax32(fStart, fEnd);
1064     for (int index = min; index < max; ++index) {
1065         const SkOpSpan& mSpan = fSegment->span(index);
1066         if (!mSpan.fSmall) {
1067             return false;
1068         }
1069     }
1070     return true;
1071 }
1072
1073 bool SkOpAngle::tangentsDiverge(const SkOpAngle& rh, double s0xt0) const {
1074     if (s0xt0 == 0) {
1075         return false;
1076     }
1077     // if the ctrl tangents are not nearly parallel, use them
1078     // solve for opposite direction displacement scale factor == m
1079     // initial dir = v1.cross(v2) == v2.x * v1.y - v2.y * v1.x
1080     // displacement of q1[1] : dq1 = { -m * v1.y, m * v1.x } + q1[1]
1081     // straight angle when : v2.x * (dq1.y - q1[0].y) == v2.y * (dq1.x - q1[0].x)
1082     //                       v2.x * (m * v1.x + v1.y) == v2.y * (-m * v1.y + v1.x)
1083     // - m * (v2.x * v1.x + v2.y * v1.y) == v2.x * v1.y - v2.y * v1.x
1084     // m = (v2.y * v1.x - v2.x * v1.y) / (v2.x * v1.x + v2.y * v1.y)
1085     // m = v1.cross(v2) / v1.dot(v2)
1086     const SkDVector* sweep = fSweep;
1087     const SkDVector* tweep = rh.fSweep;
1088     double s0dt0 = sweep[0].dot(tweep[0]);
1089     if (!s0dt0) {
1090         return true;
1091     }
1092     SkASSERT(s0dt0 != 0);
1093     double m = s0xt0 / s0dt0;
1094     double sDist = sweep[0].length() * m;
1095     double tDist = tweep[0].length() * m;
1096     bool useS = fabs(sDist) < fabs(tDist);
1097     double mFactor = fabs(useS ? distEndRatio(sDist) : rh.distEndRatio(tDist));
1098     return mFactor < 5000;  // empirically found limit
1099 }