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 16 static const char funcName[] = "SkOpSegment::operator<"; 17 static const int bugChar = strlen(funcName) + 1; 18 #endif 19 20 /* Angles are sorted counterclockwise. The smallest angle has a positive x and the smallest 21 positive y. The largest angle has a positive x and a zero y. */ 22 23 #if DEBUG_ANGLE 24 static bool CompareResult(SkString* bugOut, const char* append, bool compare) { 25 bugOut->appendf("%s", append); 26 bugOut->writable_str()[bugChar] = "><"[compare]; 27 SkDebugf("%s\n", bugOut->c_str()); 28 return compare; 29 } 30 31 #define COMPARE_RESULT(append, compare) CompareResult(&bugOut, append, compare) 32 #else 33 #define COMPARE_RESULT(append, compare) compare 34 #endif 35 36 bool SkOpAngle::calcSlop(double x, double y, double rx, double ry, bool* result) const{ 37 double absX = fabs(x); 38 double absY = fabs(y); 39 double length = absX < absY ? absX / 2 + absY : absX + absY / 2; 40 int exponent; 41 (void) frexp(length, &exponent); 42 double epsilon = ldexp(FLT_EPSILON, exponent); 43 SkPath::Verb verb = fSegment->verb(); 44 SkASSERT(verb == SkPath::kQuad_Verb || verb == SkPath::kCubic_Verb); 45 // FIXME: the quad and cubic factors are made up ; determine actual values 46 double slop = verb == SkPath::kQuad_Verb ? 4 * epsilon : 512 * epsilon; 47 double xSlop = slop; 48 double ySlop = x * y < 0 ? -xSlop : xSlop; // OPTIMIZATION: use copysign / _copysign ? 49 double x1 = x - xSlop; 50 double y1 = y + ySlop; 51 double x_ry1 = x1 * ry; 52 double rx_y1 = rx * y1; 53 *result = x_ry1 < rx_y1; 54 double x2 = x + xSlop; 55 double y2 = y - ySlop; 56 double x_ry2 = x2 * ry; 57 double rx_y2 = rx * y2; 58 bool less2 = x_ry2 < rx_y2; 59 return *result == less2; 60 } 61 62 /* 63 for quads and cubics, set up a parameterized line (e.g. LineParameters ) 64 for points [0] to [1]. See if point [2] is on that line, or on one side 65 or the other. If it both quads' end points are on the same side, choose 66 the shorter tangent. If the tangents are equal, choose the better second 67 tangent angle 68 69 FIXME: maybe I could set up LineParameters lazily 70 */ 71 bool SkOpAngle::operator<(const SkOpAngle& rh) const { // this/lh: left-hand; rh: right-hand 72 double y = dy(); 73 double ry = rh.dy(); 74 #if DEBUG_ANGLE 75 SkString bugOut; 76 bugOut.printf("%s _ id=%d segId=%d tStart=%1.9g tEnd=%1.9g" 77 " | id=%d segId=%d tStart=%1.9g tEnd=%1.9g ", funcName, 78 fID, fSegment->debugID(), fSegment->t(fStart), fSegment->t(fEnd), 79 rh.fID, rh.fSegment->debugID(), rh.fSegment->t(rh.fStart), rh.fSegment->t(rh.fEnd)); 80 #endif 81 double y_ry = y * ry; 82 if (y_ry < 0) { // if y's are opposite signs, we can do a quick return 83 return COMPARE_RESULT("1 y * ry < 0", y < 0); 84 } 85 // at this point, both y's must be the same sign, or one (or both) is zero 86 double x = dx(); 87 double rx = rh.dx(); 88 if (x * rx < 0) { // if x's are opposite signs, use y to determine first or second half 89 if (y < 0 && ry < 0) { // if y's are negative, lh x is smaller if positive 90 return COMPARE_RESULT("2 x_rx < 0 && y < 0 ...", x > 0); 91 } 92 if (y >= 0 && ry >= 0) { // if y's are zero or positive, lh x is smaller if negative 93 return COMPARE_RESULT("3 x_rx < 0 && y >= 0 ...", x < 0); 94 } 95 SkASSERT((y == 0) ^ (ry == 0)); // if one y is zero and one is negative, neg y is smaller 96 return COMPARE_RESULT("4 x_rx < 0 && y == 0 ...", y < 0); 97 } 98 // at this point, both x's must be the same sign, or one (or both) is zero 99 if (y_ry == 0) { // if either y is zero 100 if (y + ry < 0) { // if the other y is less than zero, it must be smaller 101 return COMPARE_RESULT("5 y_ry == 0 && y + ry < 0", y < 0); 102 } 103 if (y + ry > 0) { // if a y is greater than zero and an x is positive, non zero is smaller 104 return COMPARE_RESULT("6 y_ry == 0 && y + ry > 0", (x + rx > 0) ^ (y == 0)); 105 } 106 // at this point, both y's are zero, so lines are coincident or one is degenerate 107 SkASSERT(x * rx != 0); // and a degenerate line should haven't gotten this far 108 } 109 // see if either curve can be lengthened before trying the tangent 110 if (fSegment->other(fEnd) != rh.fSegment // tangents not absolutely identical 111 && rh.fSegment->other(rh.fEnd) != fSegment 112 && y != -DBL_EPSILON 113 && ry != -DBL_EPSILON) { // and not intersecting 114 SkOpAngle longer = *this; 115 SkOpAngle rhLonger = rh; 116 if ((longer.lengthen(rh) | rhLonger.lengthen(*this)) // lengthen both 117 && (fUnorderable || !longer.fUnorderable) 118 && (rh.fUnorderable || !rhLonger.fUnorderable)) { 119 #if DEBUG_ANGLE 120 bugOut.prepend(" "); 121 #endif 122 return COMPARE_RESULT("10 longer.lengthen(rh) ...", longer < rhLonger); 123 } 124 } 125 SkPath::Verb verb = fSegment->verb(); 126 SkPath::Verb rVerb = rh.fSegment->verb(); 127 if (y_ry != 0) { // if they aren't coincident, look for a stable cross product 128 // at this point, y's are the same sign, neither is zero 129 // and x's are the same sign, or one (or both) is zero 130 double x_ry = x * ry; 131 double rx_y = rx * y; 132 if (!fComputed && !rh.fComputed) { 133 if (!SkDLine::NearRay(x, y, rx, ry) && x_ry != rx_y) { 134 return COMPARE_RESULT("7 !fComputed && !rh.fComputed", x_ry < rx_y); 135 } 136 if (fSide2 == 0 && rh.fSide2 == 0) { 137 return COMPARE_RESULT("7a !fComputed && !rh.fComputed", x_ry < rx_y); 138 } 139 } else { 140 // if the vector was a result of subdividing a curve, see if it is stable 141 bool sloppy1 = x_ry < rx_y; 142 bool sloppy2 = !sloppy1; 143 if ((!fComputed || calcSlop(x, y, rx, ry, &sloppy1)) 144 && (!rh.fComputed || rh.calcSlop(rx, ry, x, y, &sloppy2)) 145 && sloppy1 != sloppy2) { 146 return COMPARE_RESULT("8 CalcSlop(x, y ...", sloppy1); 147 } 148 } 149 } 150 if (fSide2 * rh.fSide2 == 0) { // one is zero 151 #if DEBUG_ANGLE 152 if (fSide2 == rh.fSide2 && y_ry) { // both is zero; coincidence was undetected 153 SkDebugf("%s coincidence!\n", __FUNCTION__); 154 } 155 #endif 156 return COMPARE_RESULT("9a fSide2 * rh.fSide2 == 0 ...", fSide2 < rh.fSide2); 157 } 158 // at this point, the initial tangent line is nearly coincident 159 // see if edges curl away from each other 160 if (fSide * rh.fSide < 0 && (!approximately_zero(fSide) || !approximately_zero(rh.fSide))) { 161 return COMPARE_RESULT("9b fSide * rh.fSide < 0 ...", fSide < rh.fSide); 162 } 163 if (fUnsortable || rh.fUnsortable) { 164 // even with no solution, return a stable sort 165 return COMPARE_RESULT("11 fUnsortable || rh.fUnsortable", this < &rh); 166 } 167 if ((verb == SkPath::kLine_Verb && approximately_zero(y) && approximately_zero(x)) 168 || (rVerb == SkPath::kLine_Verb 169 && approximately_zero(ry) && approximately_zero(rx))) { 170 // See general unsortable comment below. This case can happen when 171 // one line has a non-zero change in t but no change in x and y. 172 fUnsortable = true; 173 return COMPARE_RESULT("12 verb == SkPath::kLine_Verb ...", this < &rh); 174 } 175 if (fSegment->isTiny(this) || rh.fSegment->isTiny(&rh)) { 176 fUnsortable = true; 177 return COMPARE_RESULT("13 verb == fSegment->isTiny(this) ...", this < &rh); 178 } 179 SkASSERT(verb >= SkPath::kQuad_Verb); 180 SkASSERT(rVerb >= SkPath::kQuad_Verb); 181 // FIXME: until I can think of something better, project a ray from the 182 // end of the shorter tangent to midway between the end points 183 // through both curves and use the resulting angle to sort 184 // FIXME: some of this setup can be moved to set() if it works, or cached if it's expensive 185 double len = fTangentPart.normalSquared(); 186 double rlen = rh.fTangentPart.normalSquared(); 187 SkDLine ray; 188 SkIntersections i, ri; 189 int roots, rroots; 190 bool flip = false; 191 bool useThis; 192 bool leftLessThanRight = fSide > 0; 193 do { 194 useThis = (len < rlen) ^ flip; 195 const SkDCubic& part = useThis ? fCurvePart : rh.fCurvePart; 196 SkPath::Verb partVerb = useThis ? verb : rVerb; 197 ray[0] = partVerb == SkPath::kCubic_Verb && part[0].approximatelyEqual(part[1]) ? 198 part[2] : part[1]; 199 ray[1] = SkDPoint::Mid(part[0], part[SkPathOpsVerbToPoints(partVerb)]); 200 SkASSERT(ray[0] != ray[1]); 201 roots = (i.*CurveRay[SkPathOpsVerbToPoints(verb)])(fSegment->pts(), ray); 202 rroots = (ri.*CurveRay[SkPathOpsVerbToPoints(rVerb)])(rh.fSegment->pts(), ray); 203 } while ((roots == 0 || rroots == 0) && (flip ^= true)); 204 if (roots == 0 || rroots == 0) { 205 // FIXME: we don't have a solution in this case. The interim solution 206 // is to mark the edges as unsortable, exclude them from this and 207 // future computations, and allow the returned path to be fragmented 208 fUnsortable = true; 209 return COMPARE_RESULT("roots == 0 || rroots == 0", this < &rh); 210 } 211 SkASSERT(fSide != 0 && rh.fSide != 0); 212 if (fSide * rh.fSide < 0) { 213 fUnsortable = true; 214 return COMPARE_RESULT("14 fSide * rh.fSide < 0", this < &rh); 215 } 216 SkDPoint lLoc; 217 double best = SK_ScalarInfinity; 218 #if DEBUG_SORT 219 SkDebugf("lh=%d rh=%d use-lh=%d ray={{%1.9g,%1.9g}, {%1.9g,%1.9g}} %c\n", 220 fSegment->debugID(), rh.fSegment->debugID(), useThis, ray[0].fX, ray[0].fY, 221 ray[1].fX, ray[1].fY, "-+"[fSide > 0]); 222 #endif 223 for (int index = 0; index < roots; ++index) { 224 SkDPoint loc = i.pt(index); 225 SkDVector dxy = loc - ray[0]; 226 double dist = dxy.lengthSquared(); 227 #if DEBUG_SORT 228 SkDebugf("best=%1.9g dist=%1.9g loc={%1.9g,%1.9g} dxy={%1.9g,%1.9g}\n", 229 best, dist, loc.fX, loc.fY, dxy.fX, dxy.fY); 230 #endif 231 if (best > dist) { 232 lLoc = loc; 233 best = dist; 234 } 235 } 236 flip = false; 237 SkDPoint rLoc; 238 for (int index = 0; index < rroots; ++index) { 239 rLoc = ri.pt(index); 240 SkDVector dxy = rLoc - ray[0]; 241 double dist = dxy.lengthSquared(); 242 #if DEBUG_SORT 243 SkDebugf("best=%1.9g dist=%1.9g %c=(fSide < 0) rLoc={%1.9g,%1.9g} dxy={%1.9g,%1.9g}\n", 244 best, dist, "><"[fSide < 0], rLoc.fX, rLoc.fY, dxy.fX, dxy.fY); 245 #endif 246 if (best > dist) { 247 flip = true; 248 break; 249 } 250 } 251 if (flip) { 252 leftLessThanRight = !leftLessThanRight; 253 } 254 return COMPARE_RESULT("15 leftLessThanRight", leftLessThanRight); 255 } 256 257 bool SkOpAngle::isHorizontal() const { 258 return dy() == 0 && fSegment->verb() == SkPath::kLine_Verb; 259 } 260 261 // lengthen cannot cross opposite angle 262 bool SkOpAngle::lengthen(const SkOpAngle& opp) { 263 if (fSegment->other(fEnd) == opp.fSegment) { 264 return false; 265 } 266 // FIXME: make this a while loop instead and make it as large as possible? 267 int newEnd = fEnd; 268 if (fStart < fEnd ? ++newEnd < fSegment->count() : --newEnd >= 0) { 269 fEnd = newEnd; 270 setSpans(); 271 return true; 272 } 273 return false; 274 } 275 276 void SkOpAngle::set(const SkOpSegment* segment, int start, int end) { 277 fSegment = segment; 278 fStart = start; 279 fEnd = end; 280 setSpans(); 281 } 282 283 void SkOpAngle::setSpans() { 284 fUnorderable = fSegment->isTiny(this); 285 fLastMarked = NULL; 286 fUnsortable = false; 287 const SkPoint* pts = fSegment->pts(); 288 if (fSegment->verb() != SkPath::kLine_Verb) { 289 fComputed = fSegment->subDivide(fStart, fEnd, &fCurvePart); 290 fSegment->subDivide(fStart, fStart < fEnd ? fSegment->count() - 1 : 0, &fCurveHalf); 291 } 292 // FIXME: slight errors in subdivision cause sort trouble later on. As an experiment, try 293 // rounding the curve part to float precision here 294 // fCurvePart.round(fSegment->verb()); 295 switch (fSegment->verb()) { 296 case SkPath::kLine_Verb: { 297 SkASSERT(fStart != fEnd); 298 fCurvePart[0].set(pts[fStart > fEnd]); 299 fCurvePart[1].set(pts[fStart < fEnd]); 300 fComputed = false; 301 // OPTIMIZATION: for pure line compares, we never need fTangentPart.c 302 fTangentPart.lineEndPoints(*SkTCast<SkDLine*>(&fCurvePart)); 303 fSide = 0; 304 fSide2 = 0; 305 } break; 306 case SkPath::kQuad_Verb: { 307 fSide2 = -fTangentHalf.quadPart(*SkTCast<SkDQuad*>(&fCurveHalf)); 308 SkDQuad& quad = *SkTCast<SkDQuad*>(&fCurvePart); 309 fTangentPart.quadEndPoints(quad); 310 fSide = -fTangentPart.pointDistance(fCurvePart[2]); // not normalized -- compare sign only 311 if (fComputed && dx() > 0 && approximately_zero(dy())) { 312 SkDCubic origCurve; // can't use segment's curve in place since it may be flipped 313 int last = fSegment->count() - 1; 314 fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve); 315 SkLineParameters origTan; 316 origTan.quadEndPoints(*SkTCast<SkDQuad*>(&origCurve)); 317 if (origTan.dx() <= 0 318 || (dy() != origTan.dy() && dy() * origTan.dy() <= 0)) { // signs match? 319 fUnorderable = true; 320 return; 321 } 322 } 323 } break; 324 case SkPath::kCubic_Verb: { 325 double startT = fSegment->t(fStart); 326 fSide2 = -fTangentHalf.cubicPart(fCurveHalf); 327 fTangentPart.cubicEndPoints(fCurvePart); 328 double testTs[4]; 329 // OPTIMIZATION: keep inflections precomputed with cubic segment? 330 int testCount = SkDCubic::FindInflections(pts, testTs); 331 double endT = fSegment->t(fEnd); 332 double limitT = endT; 333 int index; 334 for (index = 0; index < testCount; ++index) { 335 if (!between(startT, testTs[index], limitT)) { 336 testTs[index] = -1; 337 } 338 } 339 testTs[testCount++] = startT; 340 testTs[testCount++] = endT; 341 SkTQSort<double>(testTs, &testTs[testCount - 1]); 342 double bestSide = 0; 343 int testCases = (testCount << 1) - 1; 344 index = 0; 345 while (testTs[index] < 0) { 346 ++index; 347 } 348 index <<= 1; 349 for (; index < testCases; ++index) { 350 int testIndex = index >> 1; 351 double testT = testTs[testIndex]; 352 if (index & 1) { 353 testT = (testT + testTs[testIndex + 1]) / 2; 354 } 355 // OPTIMIZE: could avoid call for t == startT, endT 356 SkDPoint pt = dcubic_xy_at_t(pts, testT); 357 double testSide = fTangentPart.pointDistance(pt); 358 if (fabs(bestSide) < fabs(testSide)) { 359 bestSide = testSide; 360 } 361 } 362 fSide = -bestSide; // compare sign only 363 SkASSERT(fSide == 0 || fSide2 != 0); 364 if (fComputed && dx() > 0 && approximately_zero(dy())) { 365 SkDCubic origCurve; // can't use segment's curve in place since it may be flipped 366 int last = fSegment->count() - 1; 367 fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve); 368 SkDCubicPair split = origCurve.chopAt(startT); 369 SkLineParameters splitTan; 370 splitTan.cubicEndPoints(fStart < fEnd ? split.second() : split.first()); 371 if (splitTan.dx() <= 0) { 372 fUnorderable = true; 373 fUnsortable = fSegment->isTiny(this); 374 return; 375 } 376 // if one is < 0 and the other is >= 0 377 if (dy() * splitTan.dy() < 0) { 378 fUnorderable = true; 379 fUnsortable = fSegment->isTiny(this); 380 return; 381 } 382 } 383 } break; 384 default: 385 SkASSERT(0); 386 } 387 if ((fUnsortable = approximately_zero(dx()) && approximately_zero(dy()))) { 388 return; 389 } 390 if (fSegment->verb() == SkPath::kLine_Verb) { 391 return; 392 } 393 SkASSERT(fStart != fEnd); 394 int smaller = SkMin32(fStart, fEnd); 395 int larger = SkMax32(fStart, fEnd); 396 while (smaller < larger && fSegment->span(smaller).fTiny) { 397 ++smaller; 398 } 399 if (precisely_equal(fSegment->span(smaller).fT, fSegment->span(larger).fT)) { 400 #if DEBUG_UNSORTABLE 401 SkPoint iPt = fSegment->xyAtT(fStart); 402 SkPoint ePt = fSegment->xyAtT(fEnd); 403 SkDebugf("%s all tiny unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__, 404 fStart, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY); 405 #endif 406 fUnsortable = true; 407 return; 408 } 409 fUnsortable = fStart < fEnd ? fSegment->span(smaller).fUnsortableStart 410 : fSegment->span(larger).fUnsortableEnd; 411 #if DEBUG_UNSORTABLE 412 if (fUnsortable) { 413 SkPoint iPt = fSegment->xyAtT(smaller); 414 SkPoint ePt = fSegment->xyAtT(larger); 415 SkDebugf("%s unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__, 416 smaller, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY); 417 } 418 #endif 419 return; 420 } 421 422 #ifdef SK_DEBUG 423 void SkOpAngle::dump() const { 424 const SkOpSpan& spanStart = fSegment->span(fStart); 425 const SkOpSpan& spanEnd = fSegment->span(fEnd); 426 const SkOpSpan& spanMin = fStart < fEnd ? spanStart : spanEnd; 427 SkDebugf("id=%d (%1.9g,%1.9g) start=%d (%1.9g) end=%d (%1.9g) sumWind=", 428 fSegment->debugID(), fSegment->xAtT(fStart), fSegment->yAtT(fStart), 429 fStart, spanStart.fT, fEnd, spanEnd.fT); 430 SkPathOpsDebug::WindingPrintf(spanMin.fWindSum); 431 SkDebugf(" oppWind="); 432 SkPathOpsDebug::WindingPrintf(spanMin.fOppSum), 433 SkDebugf(" done=%d\n", spanMin.fDone); 434 } 435 #endif 436
