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 3331 x > 0, y == 0 horizontal line (to the right) 340 x > 0, y == epsilon quad/cubic horizontal tangent eventually going +y 351 x > 0, y > 0, x > y nearer horizontal angle 362 x + e == y quad/cubic 45 going horiz 373 x > 0, y > 0, x == y 45 angle 384 x == y + e quad/cubic 45 going vert 395 x > 0, y > 0, x < y nearer vertical angle 406 x == epsilon, y > 0 quad/cubic vertical tangent eventually going +x 417 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 61bool 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, <Order); 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 215int 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 249int 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 263int 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. 297void 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 328bool 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 335bool 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 386bool 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); 417recomputeSector: 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 436int 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 484double 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 503bool 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 637bool 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*/ 708int 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 727SkOpGlobalState* 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 734bool 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 786SkOpSpanBase* SkOpAngle::lastMarked() const { 787 if (fLastMarked) { 788 if (fLastMarked->chased()) { 789 return nullptr; 790 } 791 fLastMarked->setChased(true); 792 } 793 return fLastMarked; 794} 795 796bool 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 822int 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 833bool 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 854double SkOpAngle::midT() const { 855 return (fStart->t() + fEnd->t()) / 2; 856} 857 858bool 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 894bool SkOpAngle::oppositePlanes(const SkOpAngle* rh) const { 895 int startSpan = SkTAbs(rh->fSectorStart - fSectorStart); 896 return startSpan >= 8; 897} 898 899int 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; 935unorderable: 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 943SkOpAngle* 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 954SkOpSegment* SkOpAngle::segment() const { 955 return fStart->segment(); 956} 957 958void 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 969void 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 1059void 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) { 1079deferTilLater: 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 1110SkOpSpan* SkOpAngle::starter() { 1111 return fStart->starter(fEnd); 1112} 1113 1114bool 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} 1142