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 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(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 176 int 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 221 bool 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 247 bool 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 254 bool 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 287 bool SkOpAngle::computeSector() { 288 if (fComputedSector) { 289 // FIXME: logically, this should return !fUnorderable, but doing so breaks testQuadratic51 290 // -- but in general, this code may not work so this may be the least of problems 291 // adding the bang fixes testQuads46x in release, however 292 return !fUnorderable; 293 } 294 SkASSERT(fSegment->verb() != SkPath::kLine_Verb && small()); 295 fComputedSector = true; 296 int step = fStart < fEnd ? 1 : -1; 297 int limit = step > 0 ? fSegment->count() : -1; 298 int checkEnd = fEnd; 299 do { 300 // advance end 301 const SkOpSpan& span = fSegment->span(checkEnd); 302 const SkOpSegment* other = span.fOther; 303 int oCount = other->count(); 304 for (int oIndex = 0; oIndex < oCount; ++oIndex) { 305 const SkOpSpan& oSpan = other->span(oIndex); 306 if (oSpan.fOther != fSegment) { 307 continue; 308 } 309 if (oSpan.fOtherIndex == checkEnd) { 310 continue; 311 } 312 if (!approximately_equal(oSpan.fOtherT, span.fT)) { 313 continue; 314 } 315 goto recomputeSector; 316 } 317 checkEnd += step; 318 } while (checkEnd != limit); 319 recomputeSector: 320 if (checkEnd == fEnd || checkEnd - step == fEnd) { 321 fUnorderable = true; 322 return false; 323 } 324 int saveEnd = fEnd; 325 fComputedEnd = fEnd = checkEnd - step; 326 setSpans(); 327 setSector(); 328 fEnd = saveEnd; 329 return !fUnorderable; 330 } 331 332 // returns -1 if overlaps 0 if no overlap cw 1 if no overlap ccw 333 int SkOpAngle::convexHullOverlaps(const SkOpAngle& rh) const { 334 const SkDVector* sweep = fSweep; 335 const SkDVector* tweep = rh.fSweep; 336 double s0xs1 = sweep[0].crossCheck(sweep[1]); 337 double s0xt0 = sweep[0].crossCheck(tweep[0]); 338 double s1xt0 = sweep[1].crossCheck(tweep[0]); 339 bool tBetweenS = s0xs1 > 0 ? s0xt0 > 0 && s1xt0 < 0 : s0xt0 < 0 && s1xt0 > 0; 340 double s0xt1 = sweep[0].crossCheck(tweep[1]); 341 double s1xt1 = sweep[1].crossCheck(tweep[1]); 342 tBetweenS |= s0xs1 > 0 ? s0xt1 > 0 && s1xt1 < 0 : s0xt1 < 0 && s1xt1 > 0; 343 double t0xt1 = tweep[0].crossCheck(tweep[1]); 344 if (tBetweenS) { 345 return -1; 346 } 347 if ((s0xt0 == 0 && s1xt1 == 0) || (s1xt0 == 0 && s0xt1 == 0)) { // s0 to s1 equals t0 to t1 348 return -1; 349 } 350 bool sBetweenT = t0xt1 > 0 ? s0xt0 < 0 && s0xt1 > 0 : s0xt0 > 0 && s0xt1 < 0; 351 sBetweenT |= t0xt1 > 0 ? s1xt0 < 0 && s1xt1 > 0 : s1xt0 > 0 && s1xt1 < 0; 352 if (sBetweenT) { 353 return -1; 354 } 355 // if all of the sweeps are in the same half plane, then the order of any pair is enough 356 if (s0xt0 >= 0 && s0xt1 >= 0 && s1xt0 >= 0 && s1xt1 >= 0) { 357 return 0; 358 } 359 if (s0xt0 <= 0 && s0xt1 <= 0 && s1xt0 <= 0 && s1xt1 <= 0) { 360 return 1; 361 } 362 // if the outside sweeps are greater than 180 degress: 363 // first assume the inital tangents are the ordering 364 // if the midpoint direction matches the inital order, that is enough 365 SkDVector m0 = fSegment->dPtAtT(midT()) - fCurvePart[0]; 366 SkDVector m1 = rh.fSegment->dPtAtT(rh.midT()) - rh.fCurvePart[0]; 367 double m0xm1 = m0.crossCheck(m1); 368 if (s0xt0 > 0 && m0xm1 > 0) { 369 return 0; 370 } 371 if (s0xt0 < 0 && m0xm1 < 0) { 372 return 1; 373 } 374 if (tangentsDiverge(rh, s0xt0)) { 375 return s0xt0 < 0; 376 } 377 return m0xm1 < 0; 378 } 379 380 // OPTIMIZATION: longest can all be either lazily computed here or precomputed in setup 381 double SkOpAngle::distEndRatio(double dist) const { 382 double longest = 0; 383 const SkOpSegment& segment = *this->segment(); 384 int ptCount = SkPathOpsVerbToPoints(segment.verb()); 385 const SkPoint* pts = segment.pts(); 386 for (int idx1 = 0; idx1 <= ptCount - 1; ++idx1) { 387 for (int idx2 = idx1 + 1; idx2 <= ptCount; ++idx2) { 388 if (idx1 == idx2) { 389 continue; 390 } 391 SkDVector v; 392 v.set(pts[idx2] - pts[idx1]); 393 double lenSq = v.lengthSquared(); 394 longest = SkTMax(longest, lenSq); 395 } 396 } 397 return sqrt(longest) / dist; 398 } 399 400 bool SkOpAngle::endsIntersect(const SkOpAngle& rh) const { 401 SkPath::Verb lVerb = fSegment->verb(); 402 SkPath::Verb rVerb = rh.fSegment->verb(); 403 int lPts = SkPathOpsVerbToPoints(lVerb); 404 int rPts = SkPathOpsVerbToPoints(rVerb); 405 SkDLine rays[] = {{{fCurvePart[0], rh.fCurvePart[rPts]}}, 406 {{fCurvePart[0], fCurvePart[lPts]}}}; 407 if (rays[0][1] == rays[1][1]) { 408 return checkParallel(rh); 409 } 410 double smallTs[2] = {-1, -1}; 411 bool limited[2] = {false, false}; 412 for (int index = 0; index < 2; ++index) { 413 const SkOpSegment& segment = index ? *rh.fSegment : *fSegment; 414 SkIntersections i; 415 (*CurveIntersectRay[index ? rPts : lPts])(segment.pts(), rays[index], &i); 416 // SkASSERT(i.used() >= 1); 417 // if (i.used() <= 1) { 418 // continue; 419 // } 420 double tStart = segment.t(index ? rh.fStart : fStart); 421 double tEnd = segment.t(index ? rh.fComputedEnd : fComputedEnd); 422 bool testAscends = index ? rh.fStart < rh.fComputedEnd : fStart < fComputedEnd; 423 double t = testAscends ? 0 : 1; 424 for (int idx2 = 0; idx2 < i.used(); ++idx2) { 425 double testT = i[0][idx2]; 426 if (!approximately_between_orderable(tStart, testT, tEnd)) { 427 continue; 428 } 429 if (approximately_equal_orderable(tStart, testT)) { 430 continue; 431 } 432 smallTs[index] = t = testAscends ? SkTMax(t, testT) : SkTMin(t, testT); 433 limited[index] = approximately_equal_orderable(t, tEnd); 434 } 435 } 436 #if 0 437 if (smallTs[0] < 0 && smallTs[1] < 0) { // if neither ray intersects, do endpoint sort 438 double m0xm1 = 0; 439 if (lVerb == SkPath::kLine_Verb) { 440 SkASSERT(rVerb != SkPath::kLine_Verb); 441 SkDVector m0 = rays[1][1] - fCurvePart[0]; 442 SkDPoint endPt; 443 endPt.set(rh.fSegment->pts()[rh.fStart < rh.fEnd ? rPts : 0]); 444 SkDVector m1 = endPt - fCurvePart[0]; 445 m0xm1 = m0.crossCheck(m1); 446 } 447 if (rVerb == SkPath::kLine_Verb) { 448 SkDPoint endPt; 449 endPt.set(fSegment->pts()[fStart < fEnd ? lPts : 0]); 450 SkDVector m0 = endPt - fCurvePart[0]; 451 SkDVector m1 = rays[0][1] - fCurvePart[0]; 452 m0xm1 = m0.crossCheck(m1); 453 } 454 if (m0xm1 != 0) { 455 return m0xm1 < 0; 456 } 457 } 458 #endif 459 bool sRayLonger = false; 460 SkDVector sCept = {0, 0}; 461 double sCeptT = -1; 462 int sIndex = -1; 463 bool useIntersect = false; 464 for (int index = 0; index < 2; ++index) { 465 if (smallTs[index] < 0) { 466 continue; 467 } 468 const SkOpSegment& segment = index ? *rh.fSegment : *fSegment; 469 const SkDPoint& dPt = segment.dPtAtT(smallTs[index]); 470 SkDVector cept = dPt - rays[index][0]; 471 // If this point is on the curve, it should have been detected earlier by ordinary 472 // curve intersection. This may be hard to determine in general, but for lines, 473 // the point could be close to or equal to its end, but shouldn't be near the start. 474 if ((index ? lPts : rPts) == 1) { 475 SkDVector total = rays[index][1] - rays[index][0]; 476 if (cept.lengthSquared() * 2 < total.lengthSquared()) { 477 continue; 478 } 479 } 480 SkDVector end = rays[index][1] - rays[index][0]; 481 if (cept.fX * end.fX < 0 || cept.fY * end.fY < 0) { 482 continue; 483 } 484 double rayDist = cept.length(); 485 double endDist = end.length(); 486 bool rayLonger = rayDist > endDist; 487 if (limited[0] && limited[1] && rayLonger) { 488 useIntersect = true; 489 sRayLonger = rayLonger; 490 sCept = cept; 491 sCeptT = smallTs[index]; 492 sIndex = index; 493 break; 494 } 495 double delta = fabs(rayDist - endDist); 496 double minX, minY, maxX, maxY; 497 minX = minY = SK_ScalarInfinity; 498 maxX = maxY = -SK_ScalarInfinity; 499 const SkDCubic& curve = index ? rh.fCurvePart : fCurvePart; 500 int ptCount = index ? rPts : lPts; 501 for (int idx2 = 0; idx2 <= ptCount; ++idx2) { 502 minX = SkTMin(minX, curve[idx2].fX); 503 minY = SkTMin(minY, curve[idx2].fY); 504 maxX = SkTMax(maxX, curve[idx2].fX); 505 maxY = SkTMax(maxY, curve[idx2].fY); 506 } 507 double maxWidth = SkTMax(maxX - minX, maxY - minY); 508 delta /= maxWidth; 509 if (delta > 1e-4 && (useIntersect ^= true)) { // FIXME: move this magic number 510 sRayLonger = rayLonger; 511 sCept = cept; 512 sCeptT = smallTs[index]; 513 sIndex = index; 514 } 515 } 516 if (useIntersect) { 517 const SkDCubic& curve = sIndex ? rh.fCurvePart : fCurvePart; 518 const SkOpSegment& segment = sIndex ? *rh.fSegment : *fSegment; 519 double tStart = segment.t(sIndex ? rh.fStart : fStart); 520 SkDVector mid = segment.dPtAtT(tStart + (sCeptT - tStart) / 2) - curve[0]; 521 double septDir = mid.crossCheck(sCept); 522 if (!septDir) { 523 return checkParallel(rh); 524 } 525 return sRayLonger ^ (sIndex == 0) ^ (septDir < 0); 526 } else { 527 return checkParallel(rh); 528 } 529 } 530 531 // Most of the time, the first one can be found trivially by detecting the smallest sector value. 532 // If all angles have the same sector value, actual sorting is required. 533 const SkOpAngle* SkOpAngle::findFirst() const { 534 const SkOpAngle* best = this; 535 int bestStart = SkTMin(fSectorStart, fSectorEnd); 536 const SkOpAngle* angle = this; 537 while ((angle = angle->fNext) != this) { 538 int angleEnd = SkTMax(angle->fSectorStart, angle->fSectorEnd); 539 if (angleEnd < bestStart) { 540 return angle; // we wrapped around 541 } 542 int angleStart = SkTMin(angle->fSectorStart, angle->fSectorEnd); 543 if (bestStart > angleStart) { 544 best = angle; 545 bestStart = angleStart; 546 } 547 } 548 // back up to the first possible angle 549 const SkOpAngle* firstBest = best; 550 angle = best; 551 int bestEnd = SkTMax(best->fSectorStart, best->fSectorEnd); 552 while ((angle = angle->previous()) != firstBest) { 553 if (angle->fStop) { 554 break; 555 } 556 int angleStart = SkTMin(angle->fSectorStart, angle->fSectorEnd); 557 // angles that are smaller by one aren't necessary better, since the larger may be a line 558 // and the smaller may be a curve that curls to the other side of the line. 559 if (bestEnd + 1 < angleStart) { 560 return best; 561 } 562 best = angle; 563 bestEnd = SkTMax(angle->fSectorStart, angle->fSectorEnd); 564 } 565 // in the case where all angles are nearly in the same sector, check the order to find the best 566 firstBest = best; 567 angle = best; 568 do { 569 angle = angle->fNext; 570 if (angle->fStop) { 571 return firstBest; 572 } 573 bool orderable = best->orderable(*angle); // note: may return an unorderable angle 574 if (orderable == 0) { 575 return angle; 576 } 577 best = angle; 578 } while (angle != firstBest); 579 // if the angles are equally ordered, fall back on the initial tangent 580 bool foundBelow = false; 581 while ((angle = angle->fNext)) { 582 SkDVector scratch[2]; 583 const SkDVector* sweep; 584 if (!angle->fUnorderedSweep) { 585 sweep = angle->fSweep; 586 } else { 587 scratch[0] = angle->fCurvePart[1] - angle->fCurvePart[0]; 588 sweep = &scratch[0]; 589 } 590 bool isAbove = sweep->fY <= 0; 591 if (isAbove && foundBelow) { 592 return angle; 593 } 594 foundBelow |= !isAbove; 595 if (angle == firstBest) { 596 return NULL; // should not loop around 597 } 598 } 599 SkASSERT(0); // should never get here 600 return NULL; 601 } 602 603 /* y<0 y==0 y>0 x<0 x==0 x>0 xy<0 xy==0 xy>0 604 0 x x x 605 1 x x x 606 2 x x x 607 3 x x x 608 4 x x x 609 5 x x x 610 6 x x x 611 7 x x x 612 8 x x x 613 9 x x x 614 10 x x x 615 11 x x x 616 12 x x x 617 13 x x x 618 14 x x x 619 15 x x x 620 */ 621 int SkOpAngle::findSector(SkPath::Verb verb, double x, double y) const { 622 double absX = fabs(x); 623 double absY = fabs(y); 624 double xy = SkPath::kLine_Verb == verb || !AlmostEqualUlps(absX, absY) ? absX - absY : 0; 625 // If there are four quadrants and eight octants, and since the Latin for sixteen is sedecim, 626 // one could coin the term sedecimant for a space divided into 16 sections. 627 // http://english.stackexchange.com/questions/133688/word-for-something-partitioned-into-16-parts 628 static const int sedecimant[3][3][3] = { 629 // y<0 y==0 y>0 630 // x<0 x==0 x>0 x<0 x==0 x>0 x<0 x==0 x>0 631 {{ 4, 3, 2}, { 7, -1, 15}, {10, 11, 12}}, // abs(x) < abs(y) 632 {{ 5, -1, 1}, {-1, -1, -1}, { 9, -1, 13}}, // abs(x) == abs(y) 633 {{ 6, 3, 0}, { 7, -1, 15}, { 8, 11, 14}}, // abs(x) > abs(y) 634 }; 635 int sector = sedecimant[(xy >= 0) + (xy > 0)][(y >= 0) + (y > 0)][(x >= 0) + (x > 0)] * 2 + 1; 636 SkASSERT(SkPath::kLine_Verb == verb || sector >= 0); 637 return sector; 638 } 639 640 // OPTIMIZE: if this loops to only one other angle, after first compare fails, insert on other side 641 // OPTIMIZE: return where insertion succeeded. Then, start next insertion on opposite side 642 void SkOpAngle::insert(SkOpAngle* angle) { 643 if (angle->fNext) { 644 if (loopCount() >= angle->loopCount()) { 645 if (!merge(angle)) { 646 return; 647 } 648 } else if (fNext) { 649 if (!angle->merge(this)) { 650 return; 651 } 652 } else { 653 angle->insert(this); 654 } 655 return; 656 } 657 bool singleton = NULL == fNext; 658 if (singleton) { 659 fNext = this; 660 } 661 SkOpAngle* next = fNext; 662 if (next->fNext == this) { 663 if (angle->overlap(*this)) { 664 return; 665 } 666 if (singleton || angle->after(this)) { 667 this->fNext = angle; 668 angle->fNext = next; 669 } else { 670 next->fNext = angle; 671 angle->fNext = this; 672 } 673 debugValidateNext(); 674 return; 675 } 676 SkOpAngle* last = this; 677 do { 678 SkASSERT(last->fNext == next); 679 if (angle->overlap(*last) || angle->overlap(*next)) { 680 return; 681 } 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 && next->fUnorderable) { 691 fUnorderable = true; 692 return; 693 } 694 SkASSERT(last != this); 695 } while (true); 696 } 697 698 bool SkOpAngle::isHorizontal() const { 699 return !fIsCurve && fSweep[0].fY == 0; 700 } 701 702 SkOpSpan* SkOpAngle::lastMarked() const { 703 if (fLastMarked) { 704 if (fLastMarked->fChased) { 705 return NULL; 706 } 707 fLastMarked->fChased = true; 708 } 709 return fLastMarked; 710 } 711 712 bool SkOpAngle::loopContains(const SkOpAngle& test) const { 713 if (!fNext) { 714 return false; 715 } 716 const SkOpAngle* first = this; 717 const SkOpAngle* loop = this; 718 const SkOpSegment* tSegment = test.fSegment; 719 double tStart = tSegment->span(test.fStart).fT; 720 double tEnd = tSegment->span(test.fEnd).fT; 721 do { 722 const SkOpSegment* lSegment = loop->fSegment; 723 // FIXME : use precisely_equal ? or compare points exactly ? 724 if (lSegment != tSegment) { 725 continue; 726 } 727 double lStart = lSegment->span(loop->fStart).fT; 728 if (lStart != tEnd) { 729 continue; 730 } 731 double lEnd = lSegment->span(loop->fEnd).fT; 732 if (lEnd == tStart) { 733 return true; 734 } 735 } while ((loop = loop->fNext) != first); 736 return false; 737 } 738 739 int SkOpAngle::loopCount() const { 740 int count = 0; 741 const SkOpAngle* first = this; 742 const SkOpAngle* next = this; 743 do { 744 next = next->fNext; 745 ++count; 746 } while (next && next != first); 747 return count; 748 } 749 750 // OPTIMIZATION: can this be done better in after when angles are sorted? 751 void SkOpAngle::markStops() { 752 SkOpAngle* angle = this; 753 int lastEnd = SkTMax(fSectorStart, fSectorEnd); 754 do { 755 angle = angle->fNext; 756 int angleStart = SkTMin(angle->fSectorStart, angle->fSectorEnd); 757 // angles that are smaller by one aren't necessary better, since the larger may be a line 758 // and the smaller may be a curve that curls to the other side of the line. 759 if (lastEnd + 1 < angleStart) { 760 angle->fStop = true; 761 } 762 lastEnd = SkTMax(angle->fSectorStart, angle->fSectorEnd); 763 } while (angle != this); 764 } 765 766 bool SkOpAngle::merge(SkOpAngle* angle) { 767 SkASSERT(fNext); 768 SkASSERT(angle->fNext); 769 SkOpAngle* working = angle; 770 do { 771 if (this == working) { 772 return false; 773 } 774 working = working->fNext; 775 } while (working != angle); 776 do { 777 SkOpAngle* next = working->fNext; 778 working->fNext = NULL; 779 insert(working); 780 working = next; 781 } while (working != angle); 782 // it's likely that a pair of the angles are unorderable 783 #if DEBUG_ANGLE 784 SkOpAngle* last = angle; 785 working = angle->fNext; 786 do { 787 SkASSERT(last->fNext == working); 788 last->fNext = working->fNext; 789 SkASSERT(working->after(last)); 790 last->fNext = working; 791 last = working; 792 working = working->fNext; 793 } while (last != angle); 794 #endif 795 debugValidateNext(); 796 return true; 797 } 798 799 double SkOpAngle::midT() const { 800 return (fSegment->t(fStart) + fSegment->t(fEnd)) / 2; 801 } 802 803 bool SkOpAngle::oppositePlanes(const SkOpAngle& rh) const { 804 int startSpan = abs(rh.fSectorStart - fSectorStart); 805 return startSpan >= 8; 806 } 807 808 bool SkOpAngle::orderable(const SkOpAngle& rh) const { 809 int result; 810 if (!fIsCurve) { 811 if (!rh.fIsCurve) { 812 double leftX = fTangentHalf.dx(); 813 double leftY = fTangentHalf.dy(); 814 double rightX = rh.fTangentHalf.dx(); 815 double rightY = rh.fTangentHalf.dy(); 816 double x_ry = leftX * rightY; 817 double rx_y = rightX * leftY; 818 if (x_ry == rx_y) { 819 if (leftX * rightX < 0 || leftY * rightY < 0) { 820 return true; // exactly 180 degrees apart 821 } 822 goto unorderable; 823 } 824 SkASSERT(x_ry != rx_y); // indicates an undetected coincidence -- worth finding earlier 825 return x_ry < rx_y; 826 } 827 if ((result = allOnOneSide(rh)) >= 0) { 828 return result; 829 } 830 if (fUnorderable || approximately_zero(rh.fSide)) { 831 goto unorderable; 832 } 833 } else if (!rh.fIsCurve) { 834 if ((result = rh.allOnOneSide(*this)) >= 0) { 835 return !result; 836 } 837 if (rh.fUnorderable || approximately_zero(fSide)) { 838 goto unorderable; 839 } 840 } 841 if ((result = convexHullOverlaps(rh)) >= 0) { 842 return result; 843 } 844 return endsIntersect(rh); 845 unorderable: 846 fUnorderable = true; 847 rh.fUnorderable = true; 848 return true; 849 } 850 851 bool SkOpAngle::overlap(const SkOpAngle& other) const { 852 int min = SkTMin(fStart, fEnd); 853 const SkOpSpan& span = fSegment->span(min); 854 const SkOpSegment* oSeg = other.fSegment; 855 int oMin = SkTMin(other.fStart, other.fEnd); 856 const SkOpSpan& oSpan = oSeg->span(oMin); 857 if (!span.fSmall && !oSpan.fSmall) { 858 return false; 859 } 860 if (fSegment->span(fStart).fPt != oSeg->span(other.fStart).fPt) { 861 return false; 862 } 863 // see if small span is contained by opposite span 864 return span.fSmall ? oSeg->containsPt(fSegment->span(fEnd).fPt, other.fEnd, other.fStart) 865 : fSegment->containsPt(oSeg->span(other.fEnd).fPt, fEnd, fStart); 866 } 867 868 // OPTIMIZE: if this shows up in a profile, add a previous pointer 869 // as is, this should be rarely called 870 SkOpAngle* SkOpAngle::previous() const { 871 SkOpAngle* last = fNext; 872 do { 873 SkOpAngle* next = last->fNext; 874 if (next == this) { 875 return last; 876 } 877 last = next; 878 } while (true); 879 } 880 881 void SkOpAngle::set(const SkOpSegment* segment, int start, int end) { 882 fSegment = segment; 883 fStart = start; 884 fComputedEnd = fEnd = end; 885 fNext = NULL; 886 fComputeSector = fComputedSector = false; 887 fStop = false; 888 setSpans(); 889 setSector(); 890 } 891 892 void SkOpAngle::setCurveHullSweep() { 893 fUnorderedSweep = false; 894 fSweep[0] = fCurvePart[1] - fCurvePart[0]; 895 if (SkPath::kLine_Verb == fSegment->verb()) { 896 fSweep[1] = fSweep[0]; 897 return; 898 } 899 fSweep[1] = fCurvePart[2] - fCurvePart[0]; 900 if (SkPath::kCubic_Verb != fSegment->verb()) { 901 if (!fSweep[0].fX && !fSweep[0].fY) { 902 fSweep[0] = fSweep[1]; 903 } 904 return; 905 } 906 SkDVector thirdSweep = fCurvePart[3] - fCurvePart[0]; 907 if (fSweep[0].fX == 0 && fSweep[0].fY == 0) { 908 fSweep[0] = fSweep[1]; 909 fSweep[1] = thirdSweep; 910 if (fSweep[0].fX == 0 && fSweep[0].fY == 0) { 911 fSweep[0] = fSweep[1]; 912 fCurvePart[1] = fCurvePart[3]; 913 fIsCurve = false; 914 } 915 return; 916 } 917 double s1x3 = fSweep[0].crossCheck(thirdSweep); 918 double s3x2 = thirdSweep.crossCheck(fSweep[1]); 919 if (s1x3 * s3x2 >= 0) { // if third vector is on or between first two vectors 920 return; 921 } 922 double s2x1 = fSweep[1].crossCheck(fSweep[0]); 923 // FIXME: If the sweep of the cubic is greater than 180 degrees, we're in trouble 924 // probably such wide sweeps should be artificially subdivided earlier so that never happens 925 SkASSERT(s1x3 * s2x1 < 0 || s1x3 * s3x2 < 0); 926 if (s3x2 * s2x1 < 0) { 927 SkASSERT(s2x1 * s1x3 > 0); 928 fSweep[0] = fSweep[1]; 929 fUnorderedSweep = true; 930 } 931 fSweep[1] = thirdSweep; 932 } 933 934 void SkOpAngle::setSector() { 935 SkPath::Verb verb = fSegment->verb(); 936 if (SkPath::kLine_Verb != verb && small()) { 937 fSectorStart = fSectorEnd = -1; 938 fSectorMask = 0; 939 fComputeSector = true; // can't determine sector until segment length can be found 940 return; 941 } 942 fSectorStart = findSector(verb, fSweep[0].fX, fSweep[0].fY); 943 if (!fIsCurve) { // if it's a line or line-like, note that both sectors are the same 944 SkASSERT(fSectorStart >= 0); 945 fSectorEnd = fSectorStart; 946 fSectorMask = 1 << fSectorStart; 947 return; 948 } 949 SkASSERT(SkPath::kLine_Verb != verb); 950 fSectorEnd = findSector(verb, fSweep[1].fX, fSweep[1].fY); 951 if (fSectorEnd == fSectorStart) { 952 SkASSERT((fSectorStart & 3) != 3); // if the sector has no span, it can't be an exact angle 953 fSectorMask = 1 << fSectorStart; 954 return; 955 } 956 bool crossesZero = checkCrossesZero(); 957 int start = SkTMin(fSectorStart, fSectorEnd); 958 bool curveBendsCCW = (fSectorStart == start) ^ crossesZero; 959 // bump the start and end of the sector span if they are on exact compass points 960 if ((fSectorStart & 3) == 3) { 961 fSectorStart = (fSectorStart + (curveBendsCCW ? 1 : 31)) & 0x1f; 962 } 963 if ((fSectorEnd & 3) == 3) { 964 fSectorEnd = (fSectorEnd + (curveBendsCCW ? 31 : 1)) & 0x1f; 965 } 966 crossesZero = checkCrossesZero(); 967 start = SkTMin(fSectorStart, fSectorEnd); 968 int end = SkTMax(fSectorStart, fSectorEnd); 969 if (!crossesZero) { 970 fSectorMask = (unsigned) -1 >> (31 - end + start) << start; 971 } else { 972 fSectorMask = (unsigned) -1 >> (31 - start) | (-1 << end); 973 } 974 } 975 976 void SkOpAngle::setSpans() { 977 fUnorderable = fSegment->isTiny(this); 978 fLastMarked = NULL; 979 const SkPoint* pts = fSegment->pts(); 980 SkDEBUGCODE(fCurvePart[2].fX = fCurvePart[2].fY = fCurvePart[3].fX = fCurvePart[3].fY 981 = SK_ScalarNaN); 982 fSegment->subDivide(fStart, fEnd, &fCurvePart); 983 setCurveHullSweep(); 984 const SkPath::Verb verb = fSegment->verb(); 985 if (verb != SkPath::kLine_Verb 986 && !(fIsCurve = fSweep[0].crossCheck(fSweep[1]) != 0)) { 987 SkDLine lineHalf; 988 lineHalf[0].set(fCurvePart[0].asSkPoint()); 989 lineHalf[1].set(fCurvePart[SkPathOpsVerbToPoints(verb)].asSkPoint()); 990 fTangentHalf.lineEndPoints(lineHalf); 991 fSide = 0; 992 } 993 switch (verb) { 994 case SkPath::kLine_Verb: { 995 SkASSERT(fStart != fEnd); 996 const SkPoint& cP1 = pts[fStart < fEnd]; 997 SkDLine lineHalf; 998 lineHalf[0].set(fSegment->span(fStart).fPt); 999 lineHalf[1].set(cP1); 1000 fTangentHalf.lineEndPoints(lineHalf); 1001 fSide = 0; 1002 fIsCurve = false; 1003 } return; 1004 case SkPath::kQuad_Verb: { 1005 SkLineParameters tangentPart; 1006 SkDQuad& quad2 = *SkTCast<SkDQuad*>(&fCurvePart); 1007 (void) tangentPart.quadEndPoints(quad2); 1008 fSide = -tangentPart.pointDistance(fCurvePart[2]); // not normalized -- compare sign only 1009 } break; 1010 case SkPath::kCubic_Verb: { 1011 SkLineParameters tangentPart; 1012 (void) tangentPart.cubicPart(fCurvePart); 1013 fSide = -tangentPart.pointDistance(fCurvePart[3]); 1014 double testTs[4]; 1015 // OPTIMIZATION: keep inflections precomputed with cubic segment? 1016 int testCount = SkDCubic::FindInflections(pts, testTs); 1017 double startT = fSegment->t(fStart); 1018 double endT = fSegment->t(fEnd); 1019 double limitT = endT; 1020 int index; 1021 for (index = 0; index < testCount; ++index) { 1022 if (!::between(startT, testTs[index], limitT)) { 1023 testTs[index] = -1; 1024 } 1025 } 1026 testTs[testCount++] = startT; 1027 testTs[testCount++] = endT; 1028 SkTQSort<double>(testTs, &testTs[testCount - 1]); 1029 double bestSide = 0; 1030 int testCases = (testCount << 1) - 1; 1031 index = 0; 1032 while (testTs[index] < 0) { 1033 ++index; 1034 } 1035 index <<= 1; 1036 for (; index < testCases; ++index) { 1037 int testIndex = index >> 1; 1038 double testT = testTs[testIndex]; 1039 if (index & 1) { 1040 testT = (testT + testTs[testIndex + 1]) / 2; 1041 } 1042 // OPTIMIZE: could avoid call for t == startT, endT 1043 SkDPoint pt = dcubic_xy_at_t(pts, testT); 1044 SkLineParameters tangentPart; 1045 tangentPart.cubicEndPoints(fCurvePart); 1046 double testSide = tangentPart.pointDistance(pt); 1047 if (fabs(bestSide) < fabs(testSide)) { 1048 bestSide = testSide; 1049 } 1050 } 1051 fSide = -bestSide; // compare sign only 1052 } break; 1053 default: 1054 SkASSERT(0); 1055 } 1056 } 1057 1058 bool SkOpAngle::small() const { 1059 int min = SkMin32(fStart, fEnd); 1060 int max = SkMax32(fStart, fEnd); 1061 for (int index = min; index < max; ++index) { 1062 const SkOpSpan& mSpan = fSegment->span(index); 1063 if (!mSpan.fSmall) { 1064 return false; 1065 } 1066 } 1067 return true; 1068 } 1069 1070 bool SkOpAngle::tangentsDiverge(const SkOpAngle& rh, double s0xt0) const { 1071 if (s0xt0 == 0) { 1072 return false; 1073 } 1074 // if the ctrl tangents are not nearly parallel, use them 1075 // solve for opposite direction displacement scale factor == m 1076 // initial dir = v1.cross(v2) == v2.x * v1.y - v2.y * v1.x 1077 // displacement of q1[1] : dq1 = { -m * v1.y, m * v1.x } + q1[1] 1078 // straight angle when : v2.x * (dq1.y - q1[0].y) == v2.y * (dq1.x - q1[0].x) 1079 // v2.x * (m * v1.x + v1.y) == v2.y * (-m * v1.y + v1.x) 1080 // - m * (v2.x * v1.x + v2.y * v1.y) == v2.x * v1.y - v2.y * v1.x 1081 // m = (v2.y * v1.x - v2.x * v1.y) / (v2.x * v1.x + v2.y * v1.y) 1082 // m = v1.cross(v2) / v1.dot(v2) 1083 const SkDVector* sweep = fSweep; 1084 const SkDVector* tweep = rh.fSweep; 1085 double s0dt0 = sweep[0].dot(tweep[0]); 1086 if (!s0dt0) { 1087 return true; 1088 } 1089 SkASSERT(s0dt0 != 0); 1090 double m = s0xt0 / s0dt0; 1091 double sDist = sweep[0].length() * m; 1092 double tDist = tweep[0].length() * m; 1093 bool useS = fabs(sDist) < fabs(tDist); 1094 double mFactor = fabs(useS ? distEndRatio(sDist) : rh.distEndRatio(tDist)); 1095 return mFactor < 5000; // empirically found limit 1096 } 1097 1098 SkOpAngleSet::SkOpAngleSet() 1099 : fAngles(NULL) 1100 #if DEBUG_ANGLE 1101 , fCount(0) 1102 #endif 1103 { 1104 } 1105 1106 SkOpAngleSet::~SkOpAngleSet() { 1107 SkDELETE(fAngles); 1108 } 1109 1110 SkOpAngle& SkOpAngleSet::push_back() { 1111 if (!fAngles) { 1112 fAngles = SkNEW_ARGS(SkChunkAlloc, (2)); 1113 } 1114 void* ptr = fAngles->allocThrow(sizeof(SkOpAngle)); 1115 SkOpAngle* angle = (SkOpAngle*) ptr; 1116 #if DEBUG_ANGLE 1117 angle->setID(++fCount); 1118 #endif 1119 return *angle; 1120 } 1121 1122 void SkOpAngleSet::reset() { 1123 if (fAngles) { 1124 fAngles->reset(); 1125 } 1126 } 1127
