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