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 */ 7add unit test for quadratic horizontal intersection 8add unit test for cubic horizontal intersection with left/right 9add unit test for ActiveEdge::calcLeft (can currently loop forever) 10does ActiveEdge::isCoincidentWith need to support quad, cubic? 11figure out why variation in ActiveEdge::tooCloseToCall isn't better 12why does 'lastPtr - 2' in addIntersectingTs break testSimplifyTriangle22? 13add code to promote quad to cubic, or add quad/cubic intersection 14figure out why testSimplifySkinnyTriangle13 fails 15 16for quadratics and cubics, once various T values are added, see if consecutive 17Ts have ys that go up instead of down. If so, the edge needs to be broken. 18 19when splitting curves at inflection pts, should I retain the original curve 20data and note that the first/last T are no longer 0/1 ? 21I need to figure this out before I can proceed 22 23would it make sense to leave the InEdge alone, and add multiple copies of 24ActiveEdge, pointing to the same InEdge, where the copy has only the subset 25of Ts that need to be walked in reverse order? 26 27 28-- A Digression Which Shows Why Resolving Coincidence Does Not Make Sense -- 29 30Consider the following fine ASCII art: 31 32 +------>-------+ +------>-------+ 33 | | | | 34 ^ V ^ V 35 | | | | 36 +------<-------+ +------<-------+ 37 +------>-------+ +------<-------+ 38 | | | | 39 ^ V V ^ 40 | | | | 41 +------<-------+ +------>-------+ 42 43(assume the bottom and top of the stacked rectangles are coincident) 44 45Simplifying said rectangles, regardless of rectangle direction, and regardless 46of winding or even/odd, eliminates the coincident edge, i.e., the result is 47always: 48 49 +------>-------+ 50 | | 51 | | 52 | | 53 ^ V 54 | | 55 | | 56 | | 57 +------<-------+ 58 59But when the rectangles are enclosed in a larger rectangle: 60 61+-------->---------+ +-------->---------+ 62| +------>-------+ | | +------>-------+ | 63| | | | | | | | 64| ^ V | | ^ V | 65| | | | | | | | 66| +------<-------+ | | +------<-------+ | 67| +------>-------+ | | +------<-------+ | 68| | | | | | | | 69| ^ V | | V ^ | 70| | | | | | | | 71| +------<-------+ | | +------>-------+ | 72+--------<---------+ +--------<---------+ 73 74Simplifying them gives different results depending on the winding setting: 75 76winding: 77+-------->---------+ +-------->---------+ 78| | | | 79| | | | 80| | | | 81| | | | 82| | | +------<-------+ | 83| | | | | | 84| | | V ^ | 85| | | | | | 86| | | +------>-------+ | 87+--------<---------+ +--------<---------+ 88 89even odd: 90+-------->---------+ +-------->---------+ 91| +------<-------+ | | +------<-------+ | 92| | | | | | | | 93| | | | | | | | 94| | | | | | | | 95| | | | | | | | 96| V ^ | | V ^ | 97| | | | | | | | 98| | | | | | | | 99| | | | | | | | 100| +------>-------+ | | +------>-------+ | 101+--------<---------+ +--------<---------+ 102 103So, given the inner rectangles alone (e.g., given coincident pairs in some local 104context), we can't know whether to keep the coincident edges or not. 105 106 107-- Thoughts About Sortless Ops -- 108 109I can't come up with anything truly sortless. It seems that the crossings need 110to be sorted to know which segment is next on the outside, although sometimes 111we can use that it is not coincident just to follow the direction. 112 113If it is coincident or if there's more than two crossing segments, sorting 114seems inevitable. 115 116Likewise, to resolve whether one contour is inside another, it seems that 117sorting is required. Given a pair of segments on different contours, to know 118if one is inside of the other, I need to know for each which side of the edge 119is the inside/filled side. When the outer contour is walked, it seems like I 120could record the inside info. I guess when the inner contour is found, its 121inside sense is reversed (inside is above the top). But how do I know if the 122next contour is inside another? Maybe shoot out a line and brute-force 123intersect it with all the segments in all the other contours? If every contour 124has an extra segment when the intersections are computed, this may not be as 125crazy as it seems. 126 127Suppose each contour has one extra segment shooting straight up from the top 128(or straight up from any point on the segment). This ray is not intersected 129with the home contour, but is intersected with all other contours as part of 130the normal intersection engine. If it is possible to get from the T values to 131the other segments to the other contours, it would be straightforward to 132count the contour crossings and determine if the home contour is in another 133contour or not (if the count is even, not, if odd, is inside). By itself that 134doesn't tell us about winding, but it's a start. 135 136 137Since intersecting these rays is unrelated to computing other intersections, 138it can be lazily done once the contour is found. 139 140So 141repeat the following 142find the top segment of all contours 143trace the outside, marking touching first and last segments as inside 144continue tracing the touched segments with reversed outside/inside sense 145once the edges are exhausted, remaining must be disjoint contours 146send a ray from a disjoint point through all other contours 147count the crossings, determine if disjoint is inside or outside, then continue 148 149=== 150 151On Quadratic (and Cubic) Intersections 152 153Currently, if only the end points touch, QuadracticIntersections does a lot of 154work to figure that out. Can I test for that up front, then short circuit the 155recursive search for the end points? 156 157Or, is there something defective in the current approach that makes the end 158point recursion go so deep? I'm seeing 56 stack frames (about 28 divides, but 159thankfully, no splits) to find one matching endpoint. 160 161 162Bezier curve focus may allow more quickly determining that end points with 163identical tangents are practically coicident for some range of T, but I don't 164understand the math yet to know. 165 166Another approach is to determine how flat the curve is to make good guesses 167about how far to move away in T before doing the intersection for the remainder 168and/or to determine whether one curve is to the inside or outside of another. 169According to Mike/Rob, the flatness for quadratics increases by 4 for each 170subdivision, and a crude guess of the curvature can be had by comparing P1 to 171(P0+P2)/2. By looking at the ULPS of the numbers, I can guess what value of 172T may be far enough that the curves diverge but don't cross. 173 174==== 175 176Code I May Not Need Any More 177 178 static bool CoincidentCandidate(const Angle* current) { 179 const Segment* segment = current->segment(); 180 int min = SkMin32(current->start(), current->end()); 181 do { 182 const Span& span = segment->fTs[min]; 183 if (span.fCoincident == Span::kStart_Coincidence) { 184 return true; 185 } 186 } while (--min >= 0); 187 return false; 188 } 189 190 static bool CoincidentHalf(const Angle* current, const Angle* next) { 191 const Segment* other = next->segment(); 192 const Segment* segment = current->segment(); 193 int min = SkMin32(current->start(), current->end()); 194 const Span& minSpan = segment->fTs[min]; 195 if (minSpan.fOther == other) { 196 return minSpan.fCoincident == Span::kStart_Coincidence; 197 } 198 int index = min; 199 int spanCount = segment->fTs.count(); 200 while (++index < spanCount) { 201 const Span& span = segment->fTs[index]; 202 if (minSpan.fT != span.fT) { 203 break; 204 } 205 if (span.fOther != other) { 206 continue; 207 } 208 return span.fCoincident == Span::kStart_Coincidence; 209 } 210 index = min; 211 while (--index >= 0) { 212 const Span& span = segment->fTs[index]; 213 if (span.fOther != other) { 214 continue; 215 } 216 return span.fCoincident == Span::kStart_Coincidence; 217 } 218 return false; 219 } 220 221 static bool Coincident(const Angle* current, const Angle* next) { 222 return CoincidentHalf(current, next) && 223 CoincidentHalf(next, current); 224 } 225 226 // If three lines cancel in a - b - c order, a - b may or may not 227 // eliminate the edge that describes the b - c cancellation. Check done to 228 // determine this. 229 static bool CoincidentCancels(const Angle* current, const Angle* next) { 230 int curMin = SkMin32(current->start(), current->end()); 231 if (current->segment()->fTs[curMin].fDone) { 232 return false; 233 } 234 int nextMin = SkMin32(next->start(), next->end()); 235 if (next->segment()->fTs[nextMin].fDone) { 236 return false; 237 } 238 return SkSign32(current->start() - current->end()) 239 != SkSign32(next->start() - next->end()); 240 } 241 242 // FIXME: at this point, just have two functions for the different steps 243 int coincidentEnd(int from, int step) const { 244 double fromT = fTs[from].fT; 245 int count = fTs.count(); 246 int to = from; 247 while (step > 0 ? ++to < count : --to >= 0) { 248 const Span& span = fTs[to]; 249 if ((step > 0 ? span.fT - fromT : fromT - span.fT) >= FLT_EPSILON ) { 250 // FIXME: we assume that if the T changes, we don't care about 251 // coincident -- but in nextSpan, we require that both the T 252 // and actual loc change to represent a span. This asymettry may 253 // be OK or may be trouble -- if trouble, probably will need to 254 // detect coincidence earlier or sort differently 255 break; 256 } 257#if 01 258 if (span.fCoincident == (step < 0 ? Span::kStart_Coincidence : 259 Span::kEnd_Coincidence)) { 260 from = to; 261 } 262#else 263 from = to; 264#endif 265 } 266 return from; 267 } 268 269 // once past current span, if step>0, look for coicident==1 270 // if step<0, look for coincident==-1 271 int nextSpanEnd(int from, int step) const { 272 int result = nextSpan(from, step); 273 if (result < 0) { 274 return result; 275 } 276 return coincidentEnd(result, step); 277 } 278 279 280 void adjustFirst(const SkTDArray<Angle*>& sorted, int& first, int& winding, 281 bool outside) { 282 int firstIndex = first; 283 int angleCount = sorted.count(); 284 if (true || outside) { 285 const Angle* angle = sorted[firstIndex]; 286 int prior = firstIndex; 287 do { 288 if (--prior < 0) { 289 prior = angleCount - 1; 290 } 291 if (prior == firstIndex) { // all are coincident with each other 292 return; 293 } 294 if (!Coincident(sorted[prior], sorted[first])) { 295 return; 296 } 297 winding += angle->sign(); 298 first = prior; 299 angle = sorted[prior]; 300 winding -= angle->sign(); 301 } while (true); 302 } 303 do { 304 int next = first + 1; 305 if (next == angleCount) { 306 next = 0; 307 } 308 if (next == firstIndex) { // all are coincident with each other 309 return; 310 } 311 if (!Coincident(sorted[first], sorted[next])) { 312 return; 313 } 314 first = next; 315 } while (true); 316 } 317 318 bool nextIsCoincident = CoincidentCandidate(nextAngle); 319 bool finalOrNoCoincident = true; 320 bool pairCoincides = false; 321 bool pairCancels = false; 322 if (nextIsCoincident) { 323 int followIndex = nextIndex + 1; 324 if (followIndex == angleCount) { 325 followIndex = 0; 326 } 327 const Angle* followAngle = sorted[followIndex]; 328 finalOrNoCoincident = !Coincident(nextAngle, followAngle); 329 if ((pairCoincides = Coincident(angle, nextAngle))) { 330 pairCancels = CoincidentCancels(angle, nextAngle); 331 } 332 } 333 if (pairCancels && !foundAngle && !nextSegment->done()) { 334 Segment* aSeg = angle->segment(); 335 // alreadyMarked |= aSeg == sorted[firstIndex]->segment(); 336 aSeg->markAndChaseCoincident(angle->start(), angle->end(), 337 nextSegment); 338 if (firstEdge) { 339 return NULL; 340 } 341 } 342 if (pairCoincides) { 343 if (pairCancels) { 344 goto doNext; 345 } 346 int minT = SkMin32(nextAngle->start(), nextAngle->end()); 347 bool markNext = abs(maxWinding) < abs(winding); 348 if (markNext) { 349 nextSegment->markDone(minT, winding); 350 } 351 int oldMinT = SkMin32(angle->start(), angle->end()); 352 if (true || !foundAngle) { 353 // SkASSERT(0); // do we ever get here? 354 Segment* aSeg = angle->segment(); 355 // alreadyMarked |= aSeg == sorted[firstIndex]->segment(); 356 aSeg->markDone(oldMinT, maxWinding); 357 } 358 } 359 360 // OPTIMIZATION: uses tail recursion. Unwise? 361 void innerCoincidentChase(int step, Segment* other) { 362 // find other at index 363 // SkASSERT(!done()); 364 const Span* start = NULL; 365 const Span* end = NULL; 366 int index, startIndex, endIndex; 367 int count = fTs.count(); 368 for (index = 0; index < count; ++index) { 369 const Span& span = fTs[index]; 370 if (!span.fCoincident || span.fOther != other) { 371 continue; 372 } 373 if (!start) { 374 startIndex = index; 375 start = &span; 376 } else { 377 SkASSERT(!end); 378 endIndex = index; 379 end = &span; 380 } 381 } 382 if (!end) { 383 return; 384 } 385 bool thisDone = fTs[SkMin32(startIndex, endIndex)].fDone; 386 bool otherDone = other->fTs[SkMin32(start->fOtherIndex, 387 end->fOtherIndex)].fDone; 388 if (thisDone && otherDone) { 389 return; 390 } 391 Segment* next; 392 Segment* nextOther; 393 if (step < 0) { 394 next = start->fT == 0 ? NULL : this; 395 nextOther = other->fTs[start->fOtherIndex].fT > 1 - FLT_EPSILON ? NULL : other; 396 } else { 397 next = end->fT == 1 ? NULL : this; 398 nextOther = other->fTs[end->fOtherIndex].fT < FLT_EPSILON ? NULL : other; 399 } 400 SkASSERT(!next || !nextOther); 401 for (index = 0; index < count; ++index) { 402 const Span& span = fTs[index]; 403 if (span.fCoincident || span.fOther == other) { 404 continue; 405 } 406 bool checkNext = !next && (step < 0 ? span.fT < FLT_EPSILON 407 && span.fOtherT > 1 - FLT_EPSILON : span.fT > 1 - FLT_EPSILON 408 && span.fOtherT < FLT_EPSILON); 409 bool checkOther = !nextOther && (step < 0 ? fabs(span.fT - start->fT) < FLT_EPSILON 410 && span.fOtherT < FLT_EPSILON : fabs(span.fT - end->fT) < FLT_EPSILON 411 && span.fOtherT > 1 - FLT_EPSILON); 412 if (!checkNext && !checkOther) { 413 continue; 414 } 415 Segment* oSegment = span.fOther; 416 if (oSegment->done()) { 417 continue; 418 } 419 int oCount = oSegment->fTs.count(); 420 for (int oIndex = 0; oIndex < oCount; ++oIndex) { 421 const Span& oSpan = oSegment->fTs[oIndex]; 422 if (oSpan.fT >= FLT_EPSILON && oSpan.fT <= 1 - FLT_EPSILON) { 423 continue; 424 } 425 if (!oSpan.fCoincident) { 426 continue; 427 } 428 if (checkNext && (oSpan.fT < FLT_EPSILON ^ step < 0)) { 429 next = oSegment; 430 checkNext = false; 431 } 432 if (checkOther && (oSpan.fT > 1 - FLT_EPSILON ^ step < 0)) { 433 nextOther = oSegment; 434 checkOther = false; 435 } 436 } 437 } 438 // this needs to walk both spans in lock step, skipping edges that 439 // are already marked done on one or the other 440 markCanceled(startIndex, endIndex); 441 if (next && nextOther) { 442 next->innerCoincidentChase(step, nextOther); 443 } 444 } 445 446 // cancel coincident edges in lock step 447 void markCanceled(int start, int end) { 448 if (done()) { 449 return; 450 } 451 Segment* other = fTs[start].fOther; 452 if (other->done()) { 453 return; 454 } 455 if (start > end) { 456 SkTSwap<int>(start, end); 457 } 458 double maxT = fTs[end].fT - FLT_EPSILON; 459 int spanCount = fTs.count(); 460 // since these cancel, this walks up and other walks down 461 int oStart = fTs[start].fOtherIndex; 462 double oStartT = other->fTs[oStart].fT; 463 while (oStartT - other->fTs[--oStart].fT < FLT_EPSILON) 464 ; 465 double startT = fTs[start].fT; 466 while (start > 0 && startT - fTs[start - 1].fT < FLT_EPSILON) { 467 --start; 468 } 469 do { 470 Span* span = &fTs[start]; 471 Span* oSpan = &other->fTs[oStart]; 472 // find start of each, and see if both are not done 473 bool markDone = !span->fDone && !oSpan->fDone; 474 double spanT = span->fT; 475 do { 476 if (markDone) { 477 span->fCanceled = true; 478 #if DEBUG_MARK_DONE 479 const SkPoint& pt = xyAtT(span); 480 SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g)\n", 481 __FUNCTION__, fID, start, span->fT, pt.fX, pt.fY); 482 #endif 483 SkASSERT(!span->fDone); 484 span->fDone = true; 485 span->fWinding = 0; 486 fDoneSpans++; 487 } 488 if (++start == spanCount) { 489 break; 490 } 491 span = &fTs[start]; 492 } while (span->fT - spanT < FLT_EPSILON); 493 double oSpanT = oSpan->fT; 494 do { 495 if (markDone) { 496 oSpan->fCanceled = true; 497 #if DEBUG_MARK_DONE 498 const SkPoint& oPt = xyAtT(oSpan); 499 SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g)\n", 500 __FUNCTION__, other->fID, oStart, oSpan->fT, 501 oPt.fX, oPt.fY); 502 #endif 503 SkASSERT(!oSpan->fDone); 504 oSpan->fDone = true; 505 oSpan->fWinding = 0; 506 other->fDoneSpans++; 507 } 508 if (--oStart < 0) { 509 break; 510 } 511 oSpan = &other->fTs[oStart]; 512 } while (oSpanT - oSpan->fT < FLT_EPSILON); 513 } while (fTs[start].fT <= maxT); 514 } 515 516 bool canceled(int start, int end) const { 517 int min = SkMin32(start, end); 518 return fTs[min].fCanceled; 519 } 520 521 void markAndChaseCoincident(int index, int endIndex, Segment* other) { 522 int step = SkSign32(endIndex - index); 523 innerCoincidentChase(step, other); 524 } 525 526