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