caryclark@google.com | 9e49fb6 | 2012-08-27 14:11:33 +0000 | [diff] [blame] | 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 | */ |
caryclark@google.com | 198e054 | 2012-03-30 18:47:02 +0000 | [diff] [blame] | 7 | add unit test for quadratic horizontal intersection |
| 8 | add unit test for cubic horizontal intersection with left/right |
| 9 | add unit test for ActiveEdge::calcLeft (can currently loop forever) |
| 10 | does ActiveEdge::isCoincidentWith need to support quad, cubic? |
| 11 | figure out why variation in ActiveEdge::tooCloseToCall isn't better |
| 12 | why does 'lastPtr - 2' in addIntersectingTs break testSimplifyTriangle22? |
| 13 | add code to promote quad to cubic, or add quad/cubic intersection |
| 14 | figure out why testSimplifySkinnyTriangle13 fails |
| 15 | |
| 16 | for quadratics and cubics, once various T values are added, see if consecutive |
| 17 | Ts have ys that go up instead of down. If so, the edge needs to be broken. |
| 18 | |
| 19 | when splitting curves at inflection pts, should I retain the original curve |
| 20 | data and note that the first/last T are no longer 0/1 ? |
| 21 | I need to figure this out before I can proceed |
| 22 | |
| 23 | would it make sense to leave the InEdge alone, and add multiple copies of |
| 24 | ActiveEdge, pointing to the same InEdge, where the copy has only the subset |
| 25 | of Ts that need to be walked in reverse order? |
| 26 | |
caryclark@google.com | 15fa138 | 2012-05-07 20:49:36 +0000 | [diff] [blame] | 27 | |
| 28 | -- A Digression Which Shows Why Resolving Coincidence Does Not Make Sense -- |
| 29 | |
| 30 | Consider 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 | |
| 45 | Simplifying said rectangles, regardless of rectangle direction, and regardless |
| 46 | of winding or even/odd, eliminates the coincident edge, i.e., the result is |
| 47 | always: |
| 48 | |
| 49 | +------>-------+ |
| 50 | | | |
| 51 | | | |
| 52 | | | |
| 53 | ^ V |
| 54 | | | |
| 55 | | | |
| 56 | | | |
| 57 | +------<-------+ |
| 58 | |
| 59 | But 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 | |
| 74 | Simplifying them gives different results depending on the winding setting: |
| 75 | |
| 76 | winding: |
| 77 | +-------->---------+ +-------->---------+ |
| 78 | | | | | |
| 79 | | | | | |
| 80 | | | | | |
| 81 | | | | | |
| 82 | | | | +------<-------+ | |
| 83 | | | | | | | |
| 84 | | | | V ^ | |
| 85 | | | | | | | |
| 86 | | | | +------>-------+ | |
| 87 | +--------<---------+ +--------<---------+ |
| 88 | |
| 89 | even odd: |
| 90 | +-------->---------+ +-------->---------+ |
| 91 | | +------<-------+ | | +------<-------+ | |
| 92 | | | | | | | | | |
| 93 | | | | | | | | | |
| 94 | | | | | | | | | |
| 95 | | | | | | | | | |
| 96 | | V ^ | | V ^ | |
| 97 | | | | | | | | | |
| 98 | | | | | | | | | |
| 99 | | | | | | | | | |
| 100 | | +------>-------+ | | +------>-------+ | |
| 101 | +--------<---------+ +--------<---------+ |
| 102 | |
| 103 | So, given the inner rectangles alone (e.g., given coincident pairs in some local |
| 104 | context), we can't know whether to keep the coincident edges or not. |
| 105 | |
| 106 | |
| 107 | -- Thoughts About Sortless Ops -- |
| 108 | |
| 109 | I can't come up with anything truly sortless. It seems that the crossings need |
| 110 | to be sorted to know which segment is next on the outside, although sometimes |
| 111 | we can use that it is not coincident just to follow the direction. |
| 112 | |
| 113 | If it is coincident or if there's more than two crossing segments, sorting |
| 114 | seems inevitable. |
| 115 | |
| 116 | Likewise, to resolve whether one contour is inside another, it seems that |
| 117 | sorting is required. Given a pair of segments on different contours, to know |
| 118 | if one is inside of the other, I need to know for each which side of the edge |
| 119 | is the inside/filled side. When the outer contour is walked, it seems like I |
| 120 | could record the inside info. I guess when the inner contour is found, its |
| 121 | inside sense is reversed (inside is above the top). But how do I know if the |
| 122 | next contour is inside another? Maybe shoot out a line and brute-force |
| 123 | intersect it with all the segments in all the other contours? If every contour |
| 124 | has an extra segment when the intersections are computed, this may not be as |
| 125 | crazy as it seems. |
| 126 | |
| 127 | Suppose 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 |
| 129 | with the home contour, but is intersected with all other contours as part of |
| 130 | the normal intersection engine. If it is possible to get from the T values to |
| 131 | the other segments to the other contours, it would be straightforward to |
| 132 | count the contour crossings and determine if the home contour is in another |
| 133 | contour or not (if the count is even, not, if odd, is inside). By itself that |
| 134 | doesn't tell us about winding, but it's a start. |
| 135 | |
| 136 | |
| 137 | Since intersecting these rays is unrelated to computing other intersections, |
| 138 | it can be lazily done once the contour is found. |
| 139 | |
| 140 | So |
| 141 | repeat the following |
| 142 | find the top segment of all contours |
| 143 | trace the outside, marking touching first and last segments as inside |
| 144 | continue tracing the touched segments with reversed outside/inside sense |
| 145 | once the edges are exhausted, remaining must be disjoint contours |
| 146 | send a ray from a disjoint point through all other contours |
| 147 | count the crossings, determine if disjoint is inside or outside, then continue |
caryclark@google.com | b45a1b4 | 2012-05-18 20:50:33 +0000 | [diff] [blame] | 148 | |
| 149 | === |
| 150 | |
| 151 | On Quadratic (and Cubic) Intersections |
| 152 | |
| 153 | Currently, if only the end points touch, QuadracticIntersections does a lot of |
| 154 | work to figure that out. Can I test for that up front, then short circuit the |
| 155 | recursive search for the end points? |
| 156 | |
| 157 | Or, is there something defective in the current approach that makes the end |
| 158 | point recursion go so deep? I'm seeing 56 stack frames (about 28 divides, but |
| 159 | thankfully, no splits) to find one matching endpoint. |
| 160 | |
| 161 | |
| 162 | Bezier curve focus may allow more quickly determining that end points with |
| 163 | identical tangents are practically coicident for some range of T, but I don't |
| 164 | understand the math yet to know. |
| 165 | |
| 166 | Another approach is to determine how flat the curve is to make good guesses |
| 167 | about how far to move away in T before doing the intersection for the remainder |
| 168 | and/or to determine whether one curve is to the inside or outside of another. |
| 169 | According to Mike/Rob, the flatness for quadratics increases by 4 for each |
| 170 | subdivision, 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 |
caryclark@google.com | a3f05fa | 2012-06-01 17:44:28 +0000 | [diff] [blame] | 172 | T may be far enough that the curves diverge but don't cross. |
caryclark@google.com | 8dcf114 | 2012-07-02 20:27:02 +0000 | [diff] [blame] | 173 | |
| 174 | ==== |
| 175 | |
| 176 | Code 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 | |