| OLD | NEW |
|---|
| (Empty) |
| 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 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 | |
| 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 | |
| 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 | |
| 172 T may be far enough that the curves diverge but don't cross. | |
| 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 ? NU
LL : other; | |
| 396 } else { | |
| 397 next = end->fT == 1 ? NULL : this; | |
| 398 nextOther = other->fTs[end->fOtherIndex].fT < FLT_EPSILON ? NULL : o
ther; | |
| 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_EP
SILON | |
| 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 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 867213004:
remove prototype pathops code (Closed)
Base URL: https://skia.googlesource.com/skia.git@master