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 "SkOpAngle.h" 8 #include "SkOpSegment.h" 9 #include "SkPathOpsCurve.h" 10 #include "SkTSort.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 = (int) lh->orderable(rh); 124 if (!ltrOverlap) { 125 return COMPARE_RESULT(5, !lrOrder); 126 } 127 } 128 int ltOrder; 129 SkASSERT((lh->fSectorMask & fSectorMask) || (rh->fSectorMask & fSectorMask)); 130 if (lh->fSectorMask & fSectorMask) { 131 ltOrder = (int) 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 = (int) 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 (lrOrder < 0) { 171 if (ltOrder < 0) { 172 return COMPARE_RESULT(11, trOrder); 173 } 174 return COMPARE_RESULT(12, ltOrder); 175 } 176 return COMPARE_RESULT(13, !lrOrder); 177 } 178 179 // given a line, see if the opposite curve's convex hull is all on one side 180 // returns -1=not on one side 0=this CW of test 1=this CCW of test 181 int SkOpAngle::allOnOneSide(const SkOpAngle* test) { 182 SkASSERT(!fPart.isCurve()); 183 SkASSERT(test->fPart.isCurve()); 184 SkDPoint origin = fPart.fCurve[0]; 185 SkDVector line = fPart.fCurve[1] - origin; 186 double crosses[3]; 187 SkPath::Verb testVerb = test->segment()->verb(); 188 int iMax = SkPathOpsVerbToPoints(testVerb); 189 // SkASSERT(origin == test.fCurveHalf[0]); 190 const SkDCurve& testCurve = test->fPart.fCurve; 191 for (int index = 1; index <= iMax; ++index) { 192 double xy1 = line.fX * (testCurve[index].fY - origin.fY); 193 double xy2 = line.fY * (testCurve[index].fX - origin.fX); 194 crosses[index - 1] = AlmostBequalUlps(xy1, xy2) ? 0 : xy1 - xy2; 195 } 196 if (crosses[0] * crosses[1] < 0) { 197 return -1; 198 } 199 if (SkPath::kCubic_Verb == testVerb) { 200 if (crosses[0] * crosses[2] < 0 || crosses[1] * crosses[2] < 0) { 201 return -1; 202 } 203 } 204 if (crosses[0]) { 205 return crosses[0] < 0; 206 } 207 if (crosses[1]) { 208 return crosses[1] < 0; 209 } 210 if (SkPath::kCubic_Verb == testVerb && crosses[2]) { 211 return crosses[2] < 0; 212 } 213 fUnorderable = true; 214 return -1; 215 } 216 217 // To sort the angles, all curves are translated to have the same starting point. 218 // If the curve's control point in its original position is on one side of a compared line, 219 // and translated is on the opposite side, reverse the previously computed order. 220 void SkOpAngle::alignmentSameSide(const SkOpAngle* test, int* order) const { 221 if (*order < 0) { 222 return; 223 } 224 if (fPart.isCurve()) { 225 // This should support all curve types, but only bug that requires this has lines 226 // Turning on for curves causes existing tests to fail 227 return; 228 } 229 if (test->fPart.isCurve()) { 230 return; 231 } 232 const SkDPoint& xOrigin = test->fPart.fCurve.fLine[0]; 233 const SkDPoint& oOrigin = test->fOriginalCurvePart.fLine[0]; 234 if (xOrigin == oOrigin) { 235 return; 236 } 237 int iMax = SkPathOpsVerbToPoints(this->segment()->verb()); 238 SkDVector xLine = test->fPart.fCurve.fLine[1] - xOrigin; 239 SkDVector oLine = test->fOriginalCurvePart.fLine[1] - oOrigin; 240 for (int index = 1; index <= iMax; ++index) { 241 const SkDPoint& testPt = fPart.fCurve[index]; 242 double xCross = oLine.crossCheck(testPt - xOrigin); 243 double oCross = xLine.crossCheck(testPt - oOrigin); 244 if (oCross * xCross < 0) { 245 *order ^= 1; 246 break; 247 } 248 } 249 } 250 251 bool SkOpAngle::checkCrossesZero() const { 252 int start = SkTMin(fSectorStart, fSectorEnd); 253 int end = SkTMax(fSectorStart, fSectorEnd); 254 bool crossesZero = end - start > 16; 255 return crossesZero; 256 } 257 258 bool SkOpAngle::checkParallel(SkOpAngle* rh) { 259 SkDVector scratch[2]; 260 const SkDVector* sweep, * tweep; 261 if (this->fPart.isOrdered()) { 262 sweep = this->fPart.fSweep; 263 } else { 264 scratch[0] = this->fPart.fCurve[1] - this->fPart.fCurve[0]; 265 sweep = &scratch[0]; 266 } 267 if (rh->fPart.isOrdered()) { 268 tweep = rh->fPart.fSweep; 269 } else { 270 scratch[1] = rh->fPart.fCurve[1] - rh->fPart.fCurve[0]; 271 tweep = &scratch[1]; 272 } 273 double s0xt0 = sweep->crossCheck(*tweep); 274 if (tangentsDiverge(rh, s0xt0)) { 275 return s0xt0 < 0; 276 } 277 // compute the perpendicular to the endpoints and see where it intersects the opposite curve 278 // if the intersections within the t range, do a cross check on those 279 bool inside; 280 if (!fEnd->contains(rh->fEnd)) { 281 if (this->endToSide(rh, &inside)) { 282 return inside; 283 } 284 if (rh->endToSide(this, &inside)) { 285 return !inside; 286 } 287 } 288 if (this->midToSide(rh, &inside)) { 289 return inside; 290 } 291 if (rh->midToSide(this, &inside)) { 292 return !inside; 293 } 294 // compute the cross check from the mid T values (last resort) 295 SkDVector m0 = segment()->dPtAtT(this->midT()) - this->fPart.fCurve[0]; 296 SkDVector m1 = rh->segment()->dPtAtT(rh->midT()) - rh->fPart.fCurve[0]; 297 double m0xm1 = m0.crossCheck(m1); 298 if (m0xm1 == 0) { 299 this->fUnorderable = true; 300 rh->fUnorderable = true; 301 return true; 302 } 303 return m0xm1 < 0; 304 } 305 306 // the original angle is too short to get meaningful sector information 307 // lengthen it until it is long enough to be meaningful or leave it unset if lengthening it 308 // would cause it to intersect one of the adjacent angles 309 bool SkOpAngle::computeSector() { 310 if (fComputedSector) { 311 return !fUnorderable; 312 } 313 fComputedSector = true; 314 bool stepUp = fStart->t() < fEnd->t(); 315 SkOpSpanBase* checkEnd = fEnd; 316 if (checkEnd->final() && stepUp) { 317 fUnorderable = true; 318 return false; 319 } 320 do { 321 // advance end 322 const SkOpSegment* other = checkEnd->segment(); 323 const SkOpSpanBase* oSpan = other->head(); 324 do { 325 if (oSpan->segment() != segment()) { 326 continue; 327 } 328 if (oSpan == checkEnd) { 329 continue; 330 } 331 if (!approximately_equal(oSpan->t(), checkEnd->t())) { 332 continue; 333 } 334 goto recomputeSector; 335 } while (!oSpan->final() && (oSpan = oSpan->upCast()->next())); 336 checkEnd = stepUp ? !checkEnd->final() 337 ? checkEnd->upCast()->next() : nullptr 338 : checkEnd->prev(); 339 } while (checkEnd); 340 recomputeSector: 341 SkOpSpanBase* computedEnd = stepUp ? checkEnd ? checkEnd->prev() : fEnd->segment()->head() 342 : checkEnd ? checkEnd->upCast()->next() : fEnd->segment()->tail(); 343 if (checkEnd == fEnd || computedEnd == fEnd || computedEnd == fStart) { 344 fUnorderable = true; 345 return false; 346 } 347 if (stepUp != (fStart->t() < computedEnd->t())) { 348 fUnorderable = true; 349 return false; 350 } 351 SkOpSpanBase* saveEnd = fEnd; 352 fComputedEnd = fEnd = computedEnd; 353 setSpans(); 354 setSector(); 355 fEnd = saveEnd; 356 return !fUnorderable; 357 } 358 359 int SkOpAngle::convexHullOverlaps(const SkOpAngle* rh) { 360 const SkDVector* sweep = this->fPart.fSweep; 361 const SkDVector* tweep = rh->fPart.fSweep; 362 double s0xs1 = sweep[0].crossCheck(sweep[1]); 363 double s0xt0 = sweep[0].crossCheck(tweep[0]); 364 double s1xt0 = sweep[1].crossCheck(tweep[0]); 365 bool tBetweenS = s0xs1 > 0 ? s0xt0 > 0 && s1xt0 < 0 : s0xt0 < 0 && s1xt0 > 0; 366 double s0xt1 = sweep[0].crossCheck(tweep[1]); 367 double s1xt1 = sweep[1].crossCheck(tweep[1]); 368 tBetweenS |= s0xs1 > 0 ? s0xt1 > 0 && s1xt1 < 0 : s0xt1 < 0 && s1xt1 > 0; 369 double t0xt1 = tweep[0].crossCheck(tweep[1]); 370 if (tBetweenS) { 371 return -1; 372 } 373 if ((s0xt0 == 0 && s1xt1 == 0) || (s1xt0 == 0 && s0xt1 == 0)) { // s0 to s1 equals t0 to t1 374 return -1; 375 } 376 bool sBetweenT = t0xt1 > 0 ? s0xt0 < 0 && s0xt1 > 0 : s0xt0 > 0 && s0xt1 < 0; 377 sBetweenT |= t0xt1 > 0 ? s1xt0 < 0 && s1xt1 > 0 : s1xt0 > 0 && s1xt1 < 0; 378 if (sBetweenT) { 379 return -1; 380 } 381 // if all of the sweeps are in the same half plane, then the order of any pair is enough 382 if (s0xt0 >= 0 && s0xt1 >= 0 && s1xt0 >= 0 && s1xt1 >= 0) { 383 return 0; 384 } 385 if (s0xt0 <= 0 && s0xt1 <= 0 && s1xt0 <= 0 && s1xt1 <= 0) { 386 return 1; 387 } 388 // if the outside sweeps are greater than 180 degress: 389 // first assume the inital tangents are the ordering 390 // if the midpoint direction matches the inital order, that is enough 391 SkDVector m0 = this->segment()->dPtAtT(this->midT()) - this->fPart.fCurve[0]; 392 SkDVector m1 = rh->segment()->dPtAtT(rh->midT()) - rh->fPart.fCurve[0]; 393 double m0xm1 = m0.crossCheck(m1); 394 if (s0xt0 > 0 && m0xm1 > 0) { 395 return 0; 396 } 397 if (s0xt0 < 0 && m0xm1 < 0) { 398 return 1; 399 } 400 if (tangentsDiverge(rh, s0xt0)) { 401 return s0xt0 < 0; 402 } 403 return m0xm1 < 0; 404 } 405 406 // OPTIMIZATION: longest can all be either lazily computed here or precomputed in setup 407 double SkOpAngle::distEndRatio(double dist) const { 408 double longest = 0; 409 const SkOpSegment& segment = *this->segment(); 410 int ptCount = SkPathOpsVerbToPoints(segment.verb()); 411 const SkPoint* pts = segment.pts(); 412 for (int idx1 = 0; idx1 <= ptCount - 1; ++idx1) { 413 for (int idx2 = idx1 + 1; idx2 <= ptCount; ++idx2) { 414 if (idx1 == idx2) { 415 continue; 416 } 417 SkDVector v; 418 v.set(pts[idx2] - pts[idx1]); 419 double lenSq = v.lengthSquared(); 420 longest = SkTMax(longest, lenSq); 421 } 422 } 423 return sqrt(longest) / dist; 424 } 425 426 bool SkOpAngle::endsIntersect(SkOpAngle* rh) { 427 SkPath::Verb lVerb = this->segment()->verb(); 428 SkPath::Verb rVerb = rh->segment()->verb(); 429 int lPts = SkPathOpsVerbToPoints(lVerb); 430 int rPts = SkPathOpsVerbToPoints(rVerb); 431 SkDLine rays[] = {{{this->fPart.fCurve[0], rh->fPart.fCurve[rPts]}}, 432 {{this->fPart.fCurve[0], this->fPart.fCurve[lPts]}}}; 433 if (this->fEnd->contains(rh->fEnd)) { 434 return checkParallel(rh); 435 } 436 double smallTs[2] = {-1, -1}; 437 bool limited[2] = {false, false}; 438 for (int index = 0; index < 2; ++index) { 439 SkPath::Verb cVerb = index ? rVerb : lVerb; 440 // if the curve is a line, then the line and the ray intersect only at their crossing 441 if (cVerb == SkPath::kLine_Verb) { 442 continue; 443 } 444 const SkOpSegment& segment = index ? *rh->segment() : *this->segment(); 445 SkIntersections i; 446 (*CurveIntersectRay[cVerb])(segment.pts(), segment.weight(), rays[index], &i); 447 double tStart = index ? rh->fStart->t() : this->fStart->t(); 448 double tEnd = index ? rh->fComputedEnd->t() : this->fComputedEnd->t(); 449 bool testAscends = tStart < (index ? rh->fComputedEnd->t() : this->fComputedEnd->t()); 450 double t = testAscends ? 0 : 1; 451 for (int idx2 = 0; idx2 < i.used(); ++idx2) { 452 double testT = i[0][idx2]; 453 if (!approximately_between_orderable(tStart, testT, tEnd)) { 454 continue; 455 } 456 if (approximately_equal_orderable(tStart, testT)) { 457 continue; 458 } 459 smallTs[index] = t = testAscends ? SkTMax(t, testT) : SkTMin(t, testT); 460 limited[index] = approximately_equal_orderable(t, tEnd); 461 } 462 } 463 bool sRayLonger = false; 464 SkDVector sCept = {0, 0}; 465 double sCeptT = -1; 466 int sIndex = -1; 467 bool useIntersect = false; 468 for (int index = 0; index < 2; ++index) { 469 if (smallTs[index] < 0) { 470 continue; 471 } 472 const SkOpSegment& segment = index ? *rh->segment() : *this->segment(); 473 const SkDPoint& dPt = segment.dPtAtT(smallTs[index]); 474 SkDVector cept = dPt - rays[index][0]; 475 // If this point is on the curve, it should have been detected earlier by ordinary 476 // curve intersection. This may be hard to determine in general, but for lines, 477 // the point could be close to or equal to its end, but shouldn't be near the start. 478 if ((index ? lPts : rPts) == 1) { 479 SkDVector total = rays[index][1] - rays[index][0]; 480 if (cept.lengthSquared() * 2 < total.lengthSquared()) { 481 continue; 482 } 483 } 484 SkDVector end = rays[index][1] - rays[index][0]; 485 if (cept.fX * end.fX < 0 || cept.fY * end.fY < 0) { 486 continue; 487 } 488 double rayDist = cept.length(); 489 double endDist = end.length(); 490 bool rayLonger = rayDist > endDist; 491 if (limited[0] && limited[1] && rayLonger) { 492 useIntersect = true; 493 sRayLonger = rayLonger; 494 sCept = cept; 495 sCeptT = smallTs[index]; 496 sIndex = index; 497 break; 498 } 499 double delta = fabs(rayDist - endDist); 500 double minX, minY, maxX, maxY; 501 minX = minY = SK_ScalarInfinity; 502 maxX = maxY = -SK_ScalarInfinity; 503 const SkDCurve& curve = index ? rh->fPart.fCurve : this->fPart.fCurve; 504 int ptCount = index ? rPts : lPts; 505 for (int idx2 = 0; idx2 <= ptCount; ++idx2) { 506 minX = SkTMin(minX, curve[idx2].fX); 507 minY = SkTMin(minY, curve[idx2].fY); 508 maxX = SkTMax(maxX, curve[idx2].fX); 509 maxY = SkTMax(maxY, curve[idx2].fY); 510 } 511 double maxWidth = SkTMax(maxX - minX, maxY - minY); 512 delta /= maxWidth; 513 if (delta > 1e-3 && (useIntersect ^= true)) { // FIXME: move this magic number 514 sRayLonger = rayLonger; 515 sCept = cept; 516 sCeptT = smallTs[index]; 517 sIndex = index; 518 } 519 } 520 if (useIntersect) { 521 const SkDCurve& curve = sIndex ? rh->fPart.fCurve : this->fPart.fCurve; 522 const SkOpSegment& segment = sIndex ? *rh->segment() : *this->segment(); 523 double tStart = sIndex ? rh->fStart->t() : fStart->t(); 524 SkDVector mid = segment.dPtAtT(tStart + (sCeptT - tStart) / 2) - curve[0]; 525 double septDir = mid.crossCheck(sCept); 526 if (!septDir) { 527 return checkParallel(rh); 528 } 529 return sRayLonger ^ (sIndex == 0) ^ (septDir < 0); 530 } else { 531 return checkParallel(rh); 532 } 533 } 534 535 bool SkOpAngle::endToSide(const SkOpAngle* rh, bool* inside) const { 536 const SkOpSegment* segment = this->segment(); 537 SkPath::Verb verb = segment->verb(); 538 SkDLine rayEnd; 539 rayEnd[0].set(this->fEnd->pt()); 540 rayEnd[1] = rayEnd[0]; 541 SkDVector slopeAtEnd = (*CurveDSlopeAtT[verb])(segment->pts(), segment->weight(), 542 this->fEnd->t()); 543 rayEnd[1].fX += slopeAtEnd.fY; 544 rayEnd[1].fY -= slopeAtEnd.fX; 545 SkIntersections iEnd; 546 const SkOpSegment* oppSegment = rh->segment(); 547 SkPath::Verb oppVerb = oppSegment->verb(); 548 (*CurveIntersectRay[oppVerb])(oppSegment->pts(), oppSegment->weight(), rayEnd, &iEnd); 549 double endDist; 550 int closestEnd = iEnd.closestTo(rh->fStart->t(), rh->fEnd->t(), rayEnd[0], &endDist); 551 if (closestEnd < 0) { 552 return false; 553 } 554 if (!endDist) { 555 return false; 556 } 557 SkDPoint start; 558 start.set(this->fStart->pt()); 559 // OPTIMIZATION: multiple times in the code we find the max scalar 560 double minX, minY, maxX, maxY; 561 minX = minY = SK_ScalarInfinity; 562 maxX = maxY = -SK_ScalarInfinity; 563 const SkDCurve& curve = rh->fPart.fCurve; 564 int oppPts = SkPathOpsVerbToPoints(oppVerb); 565 for (int idx2 = 0; idx2 <= oppPts; ++idx2) { 566 minX = SkTMin(minX, curve[idx2].fX); 567 minY = SkTMin(minY, curve[idx2].fY); 568 maxX = SkTMax(maxX, curve[idx2].fX); 569 maxY = SkTMax(maxY, curve[idx2].fY); 570 } 571 double maxWidth = SkTMax(maxX - minX, maxY - minY); 572 endDist /= maxWidth; 573 if (endDist < 5e-12) { // empirically found 574 return false; 575 } 576 const SkDPoint* endPt = &rayEnd[0]; 577 SkDPoint oppPt = iEnd.pt(closestEnd); 578 SkDVector vLeft = *endPt - start; 579 SkDVector vRight = oppPt - start; 580 double dir = vLeft.crossNoNormalCheck(vRight); 581 if (!dir) { 582 return false; 583 } 584 *inside = dir < 0; 585 return true; 586 } 587 588 /* y<0 y==0 y>0 x<0 x==0 x>0 xy<0 xy==0 xy>0 589 0 x x x 590 1 x x x 591 2 x x x 592 3 x x x 593 4 x x x 594 5 x x x 595 6 x x x 596 7 x x x 597 8 x x x 598 9 x x x 599 10 x x x 600 11 x x x 601 12 x x x 602 13 x x x 603 14 x x x 604 15 x x x 605 */ 606 int SkOpAngle::findSector(SkPath::Verb verb, double x, double y) const { 607 double absX = fabs(x); 608 double absY = fabs(y); 609 double xy = SkPath::kLine_Verb == verb || !AlmostEqualUlps(absX, absY) ? absX - absY : 0; 610 // If there are four quadrants and eight octants, and since the Latin for sixteen is sedecim, 611 // one could coin the term sedecimant for a space divided into 16 sections. 612 // http://english.stackexchange.com/questions/133688/word-for-something-partitioned-into-16-parts 613 static const int sedecimant[3][3][3] = { 614 // y<0 y==0 y>0 615 // x<0 x==0 x>0 x<0 x==0 x>0 x<0 x==0 x>0 616 {{ 4, 3, 2}, { 7, -1, 15}, {10, 11, 12}}, // abs(x) < abs(y) 617 {{ 5, -1, 1}, {-1, -1, -1}, { 9, -1, 13}}, // abs(x) == abs(y) 618 {{ 6, 3, 0}, { 7, -1, 15}, { 8, 11, 14}}, // abs(x) > abs(y) 619 }; 620 int sector = sedecimant[(xy >= 0) + (xy > 0)][(y >= 0) + (y > 0)][(x >= 0) + (x > 0)] * 2 + 1; 621 // SkASSERT(SkPath::kLine_Verb == verb || sector >= 0); 622 return sector; 623 } 624 625 SkOpGlobalState* SkOpAngle::globalState() const { 626 return this->segment()->globalState(); 627 } 628 629 630 // OPTIMIZE: if this loops to only one other angle, after first compare fails, insert on other side 631 // OPTIMIZE: return where insertion succeeded. Then, start next insertion on opposite side 632 bool SkOpAngle::insert(SkOpAngle* angle) { 633 if (angle->fNext) { 634 if (loopCount() >= angle->loopCount()) { 635 if (!merge(angle)) { 636 return true; 637 } 638 } else if (fNext) { 639 if (!angle->merge(this)) { 640 return true; 641 } 642 } else { 643 angle->insert(this); 644 } 645 return true; 646 } 647 bool singleton = nullptr == fNext; 648 if (singleton) { 649 fNext = this; 650 } 651 SkOpAngle* next = fNext; 652 if (next->fNext == this) { 653 if (singleton || angle->after(this)) { 654 this->fNext = angle; 655 angle->fNext = next; 656 } else { 657 next->fNext = angle; 658 angle->fNext = this; 659 } 660 debugValidateNext(); 661 return true; 662 } 663 SkOpAngle* last = this; 664 bool flipAmbiguity = false; 665 do { 666 SkASSERT(last->fNext == next); 667 if (angle->after(last) ^ (angle->tangentsAmbiguous() & flipAmbiguity)) { 668 last->fNext = angle; 669 angle->fNext = next; 670 debugValidateNext(); 671 return true; 672 } 673 last = next; 674 if (last == this) { 675 FAIL_IF(flipAmbiguity); 676 // We're in a loop. If a sort was ambiguous, flip it to end the loop. 677 flipAmbiguity = true; 678 } 679 next = next->fNext; 680 } while (true); 681 return true; 682 } 683 684 SkOpSpanBase* SkOpAngle::lastMarked() const { 685 if (fLastMarked) { 686 if (fLastMarked->chased()) { 687 return nullptr; 688 } 689 fLastMarked->setChased(true); 690 } 691 return fLastMarked; 692 } 693 694 bool SkOpAngle::loopContains(const SkOpAngle* angle) const { 695 if (!fNext) { 696 return false; 697 } 698 const SkOpAngle* first = this; 699 const SkOpAngle* loop = this; 700 const SkOpSegment* tSegment = angle->fStart->segment(); 701 double tStart = angle->fStart->t(); 702 double tEnd = angle->fEnd->t(); 703 do { 704 const SkOpSegment* lSegment = loop->fStart->segment(); 705 if (lSegment != tSegment) { 706 continue; 707 } 708 double lStart = loop->fStart->t(); 709 if (lStart != tEnd) { 710 continue; 711 } 712 double lEnd = loop->fEnd->t(); 713 if (lEnd == tStart) { 714 return true; 715 } 716 } while ((loop = loop->fNext) != first); 717 return false; 718 } 719 720 int SkOpAngle::loopCount() const { 721 int count = 0; 722 const SkOpAngle* first = this; 723 const SkOpAngle* next = this; 724 do { 725 next = next->fNext; 726 ++count; 727 } while (next && next != first); 728 return count; 729 } 730 731 bool SkOpAngle::merge(SkOpAngle* angle) { 732 SkASSERT(fNext); 733 SkASSERT(angle->fNext); 734 SkOpAngle* working = angle; 735 do { 736 if (this == working) { 737 return false; 738 } 739 working = working->fNext; 740 } while (working != angle); 741 do { 742 SkOpAngle* next = working->fNext; 743 working->fNext = nullptr; 744 insert(working); 745 working = next; 746 } while (working != angle); 747 // it's likely that a pair of the angles are unorderable 748 debugValidateNext(); 749 return true; 750 } 751 752 double SkOpAngle::midT() const { 753 return (fStart->t() + fEnd->t()) / 2; 754 } 755 756 bool SkOpAngle::midToSide(const SkOpAngle* rh, bool* inside) const { 757 const SkOpSegment* segment = this->segment(); 758 SkPath::Verb verb = segment->verb(); 759 const SkPoint& startPt = this->fStart->pt(); 760 const SkPoint& endPt = this->fEnd->pt(); 761 SkDPoint dStartPt; 762 dStartPt.set(startPt); 763 SkDLine rayMid; 764 rayMid[0].fX = (startPt.fX + endPt.fX) / 2; 765 rayMid[0].fY = (startPt.fY + endPt.fY) / 2; 766 rayMid[1].fX = rayMid[0].fX + (endPt.fY - startPt.fY); 767 rayMid[1].fY = rayMid[0].fY - (endPt.fX - startPt.fX); 768 SkIntersections iMid; 769 (*CurveIntersectRay[verb])(segment->pts(), segment->weight(), rayMid, &iMid); 770 int iOutside = iMid.mostOutside(this->fStart->t(), this->fEnd->t(), dStartPt); 771 if (iOutside < 0) { 772 return false; 773 } 774 const SkOpSegment* oppSegment = rh->segment(); 775 SkPath::Verb oppVerb = oppSegment->verb(); 776 SkIntersections oppMid; 777 (*CurveIntersectRay[oppVerb])(oppSegment->pts(), oppSegment->weight(), rayMid, &oppMid); 778 int oppOutside = oppMid.mostOutside(rh->fStart->t(), rh->fEnd->t(), dStartPt); 779 if (oppOutside < 0) { 780 return false; 781 } 782 SkDVector iSide = iMid.pt(iOutside) - dStartPt; 783 SkDVector oppSide = oppMid.pt(oppOutside) - dStartPt; 784 double dir = iSide.crossCheck(oppSide); 785 if (!dir) { 786 return false; 787 } 788 *inside = dir < 0; 789 return true; 790 } 791 792 bool SkOpAngle::oppositePlanes(const SkOpAngle* rh) const { 793 int startSpan = SkTAbs(rh->fSectorStart - fSectorStart); 794 return startSpan >= 8; 795 } 796 797 bool SkOpAngle::orderable(SkOpAngle* rh) { 798 int result; 799 if (!fPart.isCurve()) { 800 if (!rh->fPart.isCurve()) { 801 double leftX = fTangentHalf.dx(); 802 double leftY = fTangentHalf.dy(); 803 double rightX = rh->fTangentHalf.dx(); 804 double rightY = rh->fTangentHalf.dy(); 805 double x_ry = leftX * rightY; 806 double rx_y = rightX * leftY; 807 if (x_ry == rx_y) { 808 if (leftX * rightX < 0 || leftY * rightY < 0) { 809 return true; // exactly 180 degrees apart 810 } 811 goto unorderable; 812 } 813 SkASSERT(x_ry != rx_y); // indicates an undetected coincidence -- worth finding earlier 814 return x_ry < rx_y; 815 } 816 if ((result = this->allOnOneSide(rh)) >= 0) { 817 return result; 818 } 819 if (fUnorderable || approximately_zero(rh->fSide)) { 820 goto unorderable; 821 } 822 } else if (!rh->fPart.isCurve()) { 823 if ((result = rh->allOnOneSide(this)) >= 0) { 824 return !result; 825 } 826 if (rh->fUnorderable || approximately_zero(fSide)) { 827 goto unorderable; 828 } 829 } else if ((result = this->convexHullOverlaps(rh)) >= 0) { 830 return result; 831 } 832 return this->endsIntersect(rh); 833 unorderable: 834 fUnorderable = true; 835 rh->fUnorderable = true; 836 return true; 837 } 838 839 // OPTIMIZE: if this shows up in a profile, add a previous pointer 840 // as is, this should be rarely called 841 SkOpAngle* SkOpAngle::previous() const { 842 SkOpAngle* last = fNext; 843 do { 844 SkOpAngle* next = last->fNext; 845 if (next == this) { 846 return last; 847 } 848 last = next; 849 } while (true); 850 } 851 852 SkOpSegment* SkOpAngle::segment() const { 853 return fStart->segment(); 854 } 855 856 void SkOpAngle::set(SkOpSpanBase* start, SkOpSpanBase* end) { 857 fStart = start; 858 fComputedEnd = fEnd = end; 859 SkASSERT(start != end); 860 fNext = nullptr; 861 fComputeSector = fComputedSector = fCheckCoincidence = fTangentsAmbiguous = false; 862 setSpans(); 863 setSector(); 864 SkDEBUGCODE(fID = start ? start->globalState()->nextAngleID() : -1); 865 } 866 867 void SkOpAngle::setSpans() { 868 fUnorderable = false; 869 fLastMarked = nullptr; 870 if (!fStart) { 871 fUnorderable = true; 872 return; 873 } 874 const SkOpSegment* segment = fStart->segment(); 875 const SkPoint* pts = segment->pts(); 876 SkDEBUGCODE(fPart.fCurve.fVerb = SkPath::kCubic_Verb); // required for SkDCurve debug check 877 SkDEBUGCODE(fPart.fCurve[2].fX = fPart.fCurve[2].fY = fPart.fCurve[3].fX = fPart.fCurve[3].fY 878 = SK_ScalarNaN); // make the non-line part uninitialized 879 SkDEBUGCODE(fPart.fCurve.fVerb = segment->verb()); // set the curve type for real 880 segment->subDivide(fStart, fEnd, &fPart.fCurve); // set at least the line part if not more 881 fOriginalCurvePart = fPart.fCurve; 882 const SkPath::Verb verb = segment->verb(); 883 fPart.setCurveHullSweep(verb); 884 if (SkPath::kLine_Verb != verb && !fPart.isCurve()) { 885 SkDLine lineHalf; 886 fPart.fCurve[1] = fPart.fCurve[SkPathOpsVerbToPoints(verb)]; 887 fOriginalCurvePart[1] = fPart.fCurve[1]; 888 lineHalf[0].set(fPart.fCurve[0].asSkPoint()); 889 lineHalf[1].set(fPart.fCurve[1].asSkPoint()); 890 fTangentHalf.lineEndPoints(lineHalf); 891 fSide = 0; 892 } 893 switch (verb) { 894 case SkPath::kLine_Verb: { 895 SkASSERT(fStart != fEnd); 896 const SkPoint& cP1 = pts[fStart->t() < fEnd->t()]; 897 SkDLine lineHalf; 898 lineHalf[0].set(fStart->pt()); 899 lineHalf[1].set(cP1); 900 fTangentHalf.lineEndPoints(lineHalf); 901 fSide = 0; 902 } return; 903 case SkPath::kQuad_Verb: 904 case SkPath::kConic_Verb: { 905 SkLineParameters tangentPart; 906 (void) tangentPart.quadEndPoints(fPart.fCurve.fQuad); 907 fSide = -tangentPart.pointDistance(fPart.fCurve[2]); // not normalized -- compare sign only 908 } break; 909 case SkPath::kCubic_Verb: { 910 SkLineParameters tangentPart; 911 (void) tangentPart.cubicPart(fPart.fCurve.fCubic); 912 fSide = -tangentPart.pointDistance(fPart.fCurve[3]); 913 double testTs[4]; 914 // OPTIMIZATION: keep inflections precomputed with cubic segment? 915 int testCount = SkDCubic::FindInflections(pts, testTs); 916 double startT = fStart->t(); 917 double endT = fEnd->t(); 918 double limitT = endT; 919 int index; 920 for (index = 0; index < testCount; ++index) { 921 if (!::between(startT, testTs[index], limitT)) { 922 testTs[index] = -1; 923 } 924 } 925 testTs[testCount++] = startT; 926 testTs[testCount++] = endT; 927 SkTQSort<double>(testTs, &testTs[testCount - 1]); 928 double bestSide = 0; 929 int testCases = (testCount << 1) - 1; 930 index = 0; 931 while (testTs[index] < 0) { 932 ++index; 933 } 934 index <<= 1; 935 for (; index < testCases; ++index) { 936 int testIndex = index >> 1; 937 double testT = testTs[testIndex]; 938 if (index & 1) { 939 testT = (testT + testTs[testIndex + 1]) / 2; 940 } 941 // OPTIMIZE: could avoid call for t == startT, endT 942 SkDPoint pt = dcubic_xy_at_t(pts, segment->weight(), testT); 943 SkLineParameters tangentPart; 944 tangentPart.cubicEndPoints(fPart.fCurve.fCubic); 945 double testSide = tangentPart.pointDistance(pt); 946 if (fabs(bestSide) < fabs(testSide)) { 947 bestSide = testSide; 948 } 949 } 950 fSide = -bestSide; // compare sign only 951 } break; 952 default: 953 SkASSERT(0); 954 } 955 } 956 957 void SkOpAngle::setSector() { 958 if (!fStart) { 959 fUnorderable = true; 960 return; 961 } 962 const SkOpSegment* segment = fStart->segment(); 963 SkPath::Verb verb = segment->verb(); 964 fSectorStart = this->findSector(verb, fPart.fSweep[0].fX, fPart.fSweep[0].fY); 965 if (fSectorStart < 0) { 966 goto deferTilLater; 967 } 968 if (!fPart.isCurve()) { // if it's a line or line-like, note that both sectors are the same 969 SkASSERT(fSectorStart >= 0); 970 fSectorEnd = fSectorStart; 971 fSectorMask = 1 << fSectorStart; 972 return; 973 } 974 SkASSERT(SkPath::kLine_Verb != verb); 975 fSectorEnd = this->findSector(verb, fPart.fSweep[1].fX, fPart.fSweep[1].fY); 976 if (fSectorEnd < 0) { 977 deferTilLater: 978 fSectorStart = fSectorEnd = -1; 979 fSectorMask = 0; 980 fComputeSector = true; // can't determine sector until segment length can be found 981 return; 982 } 983 if (fSectorEnd == fSectorStart 984 && (fSectorStart & 3) != 3) { // if the sector has no span, it can't be an exact angle 985 fSectorMask = 1 << fSectorStart; 986 return; 987 } 988 bool crossesZero = this->checkCrossesZero(); 989 int start = SkTMin(fSectorStart, fSectorEnd); 990 bool curveBendsCCW = (fSectorStart == start) ^ crossesZero; 991 // bump the start and end of the sector span if they are on exact compass points 992 if ((fSectorStart & 3) == 3) { 993 fSectorStart = (fSectorStart + (curveBendsCCW ? 1 : 31)) & 0x1f; 994 } 995 if ((fSectorEnd & 3) == 3) { 996 fSectorEnd = (fSectorEnd + (curveBendsCCW ? 31 : 1)) & 0x1f; 997 } 998 crossesZero = this->checkCrossesZero(); 999 start = SkTMin(fSectorStart, fSectorEnd); 1000 int end = SkTMax(fSectorStart, fSectorEnd); 1001 if (!crossesZero) { 1002 fSectorMask = (unsigned) -1 >> (31 - end + start) << start; 1003 } else { 1004 fSectorMask = (unsigned) -1 >> (31 - start) | ((unsigned) -1 << end); 1005 } 1006 } 1007 1008 SkOpSpan* SkOpAngle::starter() { 1009 return fStart->starter(fEnd); 1010 } 1011 1012 bool SkOpAngle::tangentsDiverge(const SkOpAngle* rh, double s0xt0) { 1013 if (s0xt0 == 0) { 1014 return false; 1015 } 1016 // if the ctrl tangents are not nearly parallel, use them 1017 // solve for opposite direction displacement scale factor == m 1018 // initial dir = v1.cross(v2) == v2.x * v1.y - v2.y * v1.x 1019 // displacement of q1[1] : dq1 = { -m * v1.y, m * v1.x } + q1[1] 1020 // straight angle when : v2.x * (dq1.y - q1[0].y) == v2.y * (dq1.x - q1[0].x) 1021 // v2.x * (m * v1.x + v1.y) == v2.y * (-m * v1.y + v1.x) 1022 // - m * (v2.x * v1.x + v2.y * v1.y) == v2.x * v1.y - v2.y * v1.x 1023 // m = (v2.y * v1.x - v2.x * v1.y) / (v2.x * v1.x + v2.y * v1.y) 1024 // m = v1.cross(v2) / v1.dot(v2) 1025 const SkDVector* sweep = fPart.fSweep; 1026 const SkDVector* tweep = rh->fPart.fSweep; 1027 double s0dt0 = sweep[0].dot(tweep[0]); 1028 if (!s0dt0) { 1029 return true; 1030 } 1031 SkASSERT(s0dt0 != 0); 1032 double m = s0xt0 / s0dt0; 1033 double sDist = sweep[0].length() * m; 1034 double tDist = tweep[0].length() * m; 1035 bool useS = fabs(sDist) < fabs(tDist); 1036 double mFactor = fabs(useS ? this->distEndRatio(sDist) : rh->distEndRatio(tDist)); 1037 fTangentsAmbiguous = mFactor >= 50 && mFactor < 200; 1038 return mFactor < 50; // empirically found limit 1039 } 1040
