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 "SkAddIntersections.h" 8 #include "SkOpCoincidence.h" 9 #include "SkOpEdgeBuilder.h" 10 #include "SkPathOpsCommon.h" 11 #include "SkPathWriter.h" 12 #include "SkTSort.h" 13 14 const SkOpAngle* AngleWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* windingPtr, 15 bool* sortablePtr) { 16 // find first angle, initialize winding to computed fWindSum 17 SkOpSegment* segment = start->segment(); 18 const SkOpAngle* angle = segment->spanToAngle(start, end); 19 if (!angle) { 20 *windingPtr = SK_MinS32; 21 return NULL; 22 } 23 bool computeWinding = false; 24 const SkOpAngle* firstAngle = angle; 25 bool loop = false; 26 bool unorderable = false; 27 int winding = SK_MinS32; 28 do { 29 angle = angle->next(); 30 unorderable |= angle->unorderable(); 31 if ((computeWinding = unorderable || (angle == firstAngle && loop))) { 32 break; // if we get here, there's no winding, loop is unorderable 33 } 34 loop |= angle == firstAngle; 35 segment = angle->segment(); 36 winding = segment->windSum(angle); 37 } while (winding == SK_MinS32); 38 // if the angle loop contains an unorderable span, the angle order may be useless 39 // directly compute the winding in this case for each span 40 if (computeWinding) { 41 firstAngle = angle; 42 winding = SK_MinS32; 43 do { 44 SkOpSpanBase* startSpan = angle->start(); 45 SkOpSpanBase* endSpan = angle->end(); 46 SkOpSpan* lesser = startSpan->starter(endSpan); 47 int testWinding = lesser->windSum(); 48 if (testWinding == SK_MinS32) { 49 testWinding = lesser->computeWindSum(); 50 } 51 if (testWinding != SK_MinS32) { 52 segment = angle->segment(); 53 winding = testWinding; 54 } 55 angle = angle->next(); 56 } while (angle != firstAngle); 57 } 58 *sortablePtr = !unorderable; 59 *windingPtr = winding; 60 return angle; 61 } 62 63 SkOpSegment* FindUndone(SkOpContourHead* contourList, SkOpSpanBase** startPtr, 64 SkOpSpanBase** endPtr) { 65 SkOpSegment* result; 66 SkOpContour* contour = contourList; 67 do { 68 result = contour->undoneSegment(startPtr, endPtr); 69 if (result) { 70 return result; 71 } 72 } while ((contour = contour->next())); 73 return NULL; 74 } 75 76 SkOpSegment* FindChase(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** startPtr, 77 SkOpSpanBase** endPtr) { 78 while (chase->count()) { 79 SkOpSpanBase* span; 80 chase->pop(&span); 81 SkOpSegment* segment = span->segment(); 82 *startPtr = span->ptT()->next()->span(); 83 bool done = true; 84 *endPtr = NULL; 85 if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done)) { 86 *startPtr = last->start(); 87 *endPtr = last->end(); 88 #if TRY_ROTATE 89 *chase->insert(0) = span; 90 #else 91 *chase->append() = span; 92 #endif 93 return last->segment(); 94 } 95 if (done) { 96 continue; 97 } 98 // find first angle, initialize winding to computed wind sum 99 int winding; 100 bool sortable; 101 const SkOpAngle* angle = AngleWinding(*startPtr, *endPtr, &winding, &sortable); 102 if (winding == SK_MinS32) { 103 continue; 104 } 105 int sumWinding SK_INIT_TO_AVOID_WARNING; 106 if (sortable) { 107 segment = angle->segment(); 108 sumWinding = segment->updateWindingReverse(angle); 109 } 110 SkOpSegment* first = NULL; 111 const SkOpAngle* firstAngle = angle; 112 while ((angle = angle->next()) != firstAngle) { 113 segment = angle->segment(); 114 SkOpSpanBase* start = angle->start(); 115 SkOpSpanBase* end = angle->end(); 116 int maxWinding; 117 if (sortable) { 118 segment->setUpWinding(start, end, &maxWinding, &sumWinding); 119 } 120 if (!segment->done(angle)) { 121 if (!first && (sortable || start->starter(end)->windSum() != SK_MinS32)) { 122 first = segment; 123 *startPtr = start; 124 *endPtr = end; 125 } 126 // OPTIMIZATION: should this also add to the chase? 127 if (sortable) { 128 (void) segment->markAngle(maxWinding, sumWinding, angle); 129 } 130 } 131 } 132 if (first) { 133 #if TRY_ROTATE 134 *chase->insert(0) = span; 135 #else 136 *chase->append() = span; 137 #endif 138 return first; 139 } 140 } 141 return NULL; 142 } 143 144 #if DEBUG_ACTIVE_SPANS 145 void DebugShowActiveSpans(SkOpContourHead* contourList) { 146 SkOpContour* contour = contourList; 147 do { 148 contour->debugShowActiveSpans(); 149 } while ((contour = contour->next())); 150 } 151 #endif 152 153 bool SortContourList(SkOpContourHead** contourList, bool evenOdd, bool oppEvenOdd) { 154 SkTDArray<SkOpContour* > list; 155 SkOpContour* contour = *contourList; 156 do { 157 if (contour->count()) { 158 contour->setOppXor(contour->operand() ? evenOdd : oppEvenOdd); 159 *list.append() = contour; 160 } 161 } while ((contour = contour->next())); 162 int count = list.count(); 163 if (!count) { 164 return false; 165 } 166 if (count > 1) { 167 SkTQSort<SkOpContour>(list.begin(), list.end() - 1); 168 } 169 contour = list[0]; 170 SkOpContourHead* contourHead = static_cast<SkOpContourHead*>(contour); 171 contour->globalState()->setContourHead(contourHead); 172 *contourList = contourHead; 173 for (int index = 1; index < count; ++index) { 174 SkOpContour* next = list[index]; 175 contour->setNext(next); 176 contour = next; 177 } 178 contour->setNext(NULL); 179 return true; 180 } 181 182 class DistanceLessThan { 183 public: 184 DistanceLessThan(double* distances) : fDistances(distances) { } 185 double* fDistances; 186 bool operator()(const int one, const int two) { 187 return fDistances[one] < fDistances[two]; 188 } 189 }; 190 191 /* 192 check start and end of each contour 193 if not the same, record them 194 match them up 195 connect closest 196 reassemble contour pieces into new path 197 */ 198 void Assemble(const SkPathWriter& path, SkPathWriter* simple) { 199 SkChunkAlloc allocator(4096); // FIXME: constant-ize, tune 200 SkOpContourHead contour; 201 SkOpGlobalState globalState(NULL, &contour); 202 #if DEBUG_SHOW_TEST_NAME 203 SkDebugf("</div>\n"); 204 #endif 205 #if DEBUG_PATH_CONSTRUCTION 206 SkDebugf("%s\n", __FUNCTION__); 207 #endif 208 SkOpEdgeBuilder builder(path, &contour, &allocator, &globalState); 209 builder.finish(&allocator); 210 SkTDArray<const SkOpContour* > runs; // indices of partial contours 211 const SkOpContour* eContour = builder.head(); 212 do { 213 if (!eContour->count()) { 214 continue; 215 } 216 const SkPoint& eStart = eContour->start(); 217 const SkPoint& eEnd = eContour->end(); 218 #if DEBUG_ASSEMBLE 219 SkDebugf("%s contour", __FUNCTION__); 220 if (!SkDPoint::ApproximatelyEqual(eStart, eEnd)) { 221 SkDebugf("[%d]", runs.count()); 222 } else { 223 SkDebugf(" "); 224 } 225 SkDebugf(" start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n", 226 eStart.fX, eStart.fY, eEnd.fX, eEnd.fY); 227 #endif 228 if (SkDPoint::ApproximatelyEqual(eStart, eEnd)) { 229 eContour->toPath(simple); 230 continue; 231 } 232 *runs.append() = eContour; 233 } while ((eContour = eContour->next())); 234 int count = runs.count(); 235 if (count == 0) { 236 return; 237 } 238 SkTDArray<int> sLink, eLink; 239 sLink.append(count); 240 eLink.append(count); 241 int rIndex, iIndex; 242 for (rIndex = 0; rIndex < count; ++rIndex) { 243 sLink[rIndex] = eLink[rIndex] = SK_MaxS32; 244 } 245 const int ends = count * 2; // all starts and ends 246 const int entries = (ends - 1) * count; // folded triangle : n * (n - 1) / 2 247 SkTDArray<double> distances; 248 distances.append(entries); 249 for (rIndex = 0; rIndex < ends - 1; ++rIndex) { 250 const SkOpContour* oContour = runs[rIndex >> 1]; 251 const SkPoint& oPt = rIndex & 1 ? oContour->end() : oContour->start(); 252 const int row = rIndex < count - 1 ? rIndex * ends : (ends - rIndex - 2) 253 * ends - rIndex - 1; 254 for (iIndex = rIndex + 1; iIndex < ends; ++iIndex) { 255 const SkOpContour* iContour = runs[iIndex >> 1]; 256 const SkPoint& iPt = iIndex & 1 ? iContour->end() : iContour->start(); 257 double dx = iPt.fX - oPt.fX; 258 double dy = iPt.fY - oPt.fY; 259 double dist = dx * dx + dy * dy; 260 distances[row + iIndex] = dist; // oStart distance from iStart 261 } 262 } 263 SkTDArray<int> sortedDist; 264 sortedDist.append(entries); 265 for (rIndex = 0; rIndex < entries; ++rIndex) { 266 sortedDist[rIndex] = rIndex; 267 } 268 SkTQSort<int>(sortedDist.begin(), sortedDist.end() - 1, DistanceLessThan(distances.begin())); 269 int remaining = count; // number of start/end pairs 270 for (rIndex = 0; rIndex < entries; ++rIndex) { 271 int pair = sortedDist[rIndex]; 272 int row = pair / ends; 273 int col = pair - row * ends; 274 int thingOne = row < col ? row : ends - row - 2; 275 int ndxOne = thingOne >> 1; 276 bool endOne = thingOne & 1; 277 int* linkOne = endOne ? eLink.begin() : sLink.begin(); 278 if (linkOne[ndxOne] != SK_MaxS32) { 279 continue; 280 } 281 int thingTwo = row < col ? col : ends - row + col - 1; 282 int ndxTwo = thingTwo >> 1; 283 bool endTwo = thingTwo & 1; 284 int* linkTwo = endTwo ? eLink.begin() : sLink.begin(); 285 if (linkTwo[ndxTwo] != SK_MaxS32) { 286 continue; 287 } 288 SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]); 289 bool flip = endOne == endTwo; 290 linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo; 291 linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne; 292 if (!--remaining) { 293 break; 294 } 295 } 296 SkASSERT(!remaining); 297 #if DEBUG_ASSEMBLE 298 for (rIndex = 0; rIndex < count; ++rIndex) { 299 int s = sLink[rIndex]; 300 int e = eLink[rIndex]; 301 SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e', 302 s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e); 303 } 304 #endif 305 rIndex = 0; 306 do { 307 bool forward = true; 308 bool first = true; 309 int sIndex = sLink[rIndex]; 310 SkASSERT(sIndex != SK_MaxS32); 311 sLink[rIndex] = SK_MaxS32; 312 int eIndex; 313 if (sIndex < 0) { 314 eIndex = sLink[~sIndex]; 315 sLink[~sIndex] = SK_MaxS32; 316 } else { 317 eIndex = eLink[sIndex]; 318 eLink[sIndex] = SK_MaxS32; 319 } 320 SkASSERT(eIndex != SK_MaxS32); 321 #if DEBUG_ASSEMBLE 322 SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e', 323 sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e', 324 eIndex < 0 ? ~eIndex : eIndex); 325 #endif 326 do { 327 const SkOpContour* contour = runs[rIndex]; 328 if (first) { 329 first = false; 330 const SkPoint* startPtr = &contour->start(); 331 simple->deferredMove(startPtr[0]); 332 } 333 if (forward) { 334 contour->toPartialForward(simple); 335 } else { 336 contour->toPartialBackward(simple); 337 } 338 #if DEBUG_ASSEMBLE 339 SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex, 340 eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex, 341 sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)); 342 #endif 343 if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) { 344 simple->close(); 345 break; 346 } 347 if (forward) { 348 eIndex = eLink[rIndex]; 349 SkASSERT(eIndex != SK_MaxS32); 350 eLink[rIndex] = SK_MaxS32; 351 if (eIndex >= 0) { 352 SkASSERT(sLink[eIndex] == rIndex); 353 sLink[eIndex] = SK_MaxS32; 354 } else { 355 SkASSERT(eLink[~eIndex] == ~rIndex); 356 eLink[~eIndex] = SK_MaxS32; 357 } 358 } else { 359 eIndex = sLink[rIndex]; 360 SkASSERT(eIndex != SK_MaxS32); 361 sLink[rIndex] = SK_MaxS32; 362 if (eIndex >= 0) { 363 SkASSERT(eLink[eIndex] == rIndex); 364 eLink[eIndex] = SK_MaxS32; 365 } else { 366 SkASSERT(sLink[~eIndex] == ~rIndex); 367 sLink[~eIndex] = SK_MaxS32; 368 } 369 } 370 rIndex = eIndex; 371 if (rIndex < 0) { 372 forward ^= 1; 373 rIndex = ~rIndex; 374 } 375 } while (true); 376 for (rIndex = 0; rIndex < count; ++rIndex) { 377 if (sLink[rIndex] != SK_MaxS32) { 378 break; 379 } 380 } 381 } while (rIndex < count); 382 #if DEBUG_ASSEMBLE 383 for (rIndex = 0; rIndex < count; ++rIndex) { 384 SkASSERT(sLink[rIndex] == SK_MaxS32); 385 SkASSERT(eLink[rIndex] == SK_MaxS32); 386 } 387 #endif 388 } 389 390 static void align(SkOpContourHead* contourList) { 391 SkOpContour* contour = contourList; 392 do { 393 contour->align(); 394 } while ((contour = contour->next())); 395 } 396 397 static void calcAngles(SkOpContourHead* contourList, SkChunkAlloc* allocator) { 398 SkOpContour* contour = contourList; 399 do { 400 contour->calcAngles(allocator); 401 } while ((contour = contour->next())); 402 } 403 404 static void missingCoincidence(SkOpContourHead* contourList, 405 SkOpCoincidence* coincidence, SkChunkAlloc* allocator) { 406 SkOpContour* contour = contourList; 407 do { 408 contour->missingCoincidence(coincidence, allocator); 409 } while ((contour = contour->next())); 410 } 411 412 static void moveMultiples(SkOpContourHead* contourList) { 413 SkOpContour* contour = contourList; 414 do { 415 contour->moveMultiples(); 416 } while ((contour = contour->next())); 417 } 418 419 static void moveNearby(SkOpContourHead* contourList) { 420 SkOpContour* contour = contourList; 421 do { 422 contour->moveNearby(); 423 } while ((contour = contour->next())); 424 } 425 426 static void sortAngles(SkOpContourHead* contourList) { 427 SkOpContour* contour = contourList; 428 do { 429 contour->sortAngles(); 430 } while ((contour = contour->next())); 431 } 432 433 bool HandleCoincidence(SkOpContourHead* contourList, SkOpCoincidence* coincidence, 434 SkChunkAlloc* allocator) { 435 SkOpGlobalState* globalState = contourList->globalState(); 436 // combine t values when multiple intersections occur on some segments but not others 437 moveMultiples(contourList); 438 // move t values and points together to eliminate small/tiny gaps 439 moveNearby(contourList); 440 align(contourList); // give all span members common values 441 #if DEBUG_VALIDATE 442 globalState->setPhase(SkOpGlobalState::kIntersecting); 443 #endif 444 coincidence->addMissing(allocator); 445 #if DEBUG_VALIDATE 446 globalState->setPhase(SkOpGlobalState::kWalking); 447 #endif 448 coincidence->expand(); // check to see if, loosely, coincident ranges may be expanded 449 coincidence->mark(); // mark spans of coincident segments as coincident 450 missingCoincidence(contourList, coincidence, allocator); // look for coincidence missed earlier 451 if (!coincidence->apply()) { // adjust the winding value to account for coincident edges 452 return false; 453 } 454 calcAngles(contourList, allocator); 455 sortAngles(contourList); 456 if (globalState->angleCoincidence()) { 457 missingCoincidence(contourList, coincidence, allocator); 458 if (!coincidence->apply()) { 459 return false; 460 } 461 } 462 #if DEBUG_ACTIVE_SPANS 463 coincidence->debugShowCoincidence(); 464 DebugShowActiveSpans(contourList); 465 #endif 466 return true; 467 } 468
