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