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 8 #include "SkAddIntersections.h" 9 #include "SkOpCoincidence.h" 10 #include "SkOpEdgeBuilder.h" 11 #include "SkMacros.h" 12 #include "SkPathOpsCommon.h" 13 #include "SkPathWriter.h" 14 #include "SkTSort.h" 15 16 const SkOpAngle* AngleWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* windingPtr, 17 bool* sortablePtr) { 18 // find first angle, initialize winding to computed fWindSum 19 SkOpSegment* segment = start->segment(); 20 const SkOpAngle* angle = segment->spanToAngle(start, end); 21 if (!angle) { 22 *windingPtr = SK_MinS32; 23 return nullptr; 24 } 25 bool computeWinding = false; 26 const SkOpAngle* firstAngle = angle; 27 bool loop = false; 28 bool unorderable = false; 29 int winding = SK_MinS32; 30 do { 31 angle = angle->next(); 32 if (!angle) { 33 return nullptr; 34 } 35 unorderable |= angle->unorderable(); 36 if ((computeWinding = unorderable || (angle == firstAngle && loop))) { 37 break; // if we get here, there's no winding, loop is unorderable 38 } 39 loop |= angle == firstAngle; 40 segment = angle->segment(); 41 winding = segment->windSum(angle); 42 } while (winding == SK_MinS32); 43 // if the angle loop contains an unorderable span, the angle order may be useless 44 // directly compute the winding in this case for each span 45 if (computeWinding) { 46 firstAngle = angle; 47 winding = SK_MinS32; 48 do { 49 SkOpSpanBase* startSpan = angle->start(); 50 SkOpSpanBase* endSpan = angle->end(); 51 SkOpSpan* lesser = startSpan->starter(endSpan); 52 int testWinding = lesser->windSum(); 53 if (testWinding == SK_MinS32) { 54 testWinding = lesser->computeWindSum(); 55 } 56 if (testWinding != SK_MinS32) { 57 segment = angle->segment(); 58 winding = testWinding; 59 } 60 angle = angle->next(); 61 } while (angle != firstAngle); 62 } 63 *sortablePtr = !unorderable; 64 *windingPtr = winding; 65 return angle; 66 } 67 68 SkOpSpan* FindUndone(SkOpContourHead* contourHead) { 69 SkOpContour* contour = contourHead; 70 do { 71 if (contour->done()) { 72 continue; 73 } 74 SkOpSpan* result = contour->undoneSpan(); 75 if (result) { 76 return result; 77 } 78 } while ((contour = contour->next())); 79 return nullptr; 80 } 81 82 SkOpSegment* FindChase(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** startPtr, 83 SkOpSpanBase** endPtr) { 84 while (chase->count()) { 85 SkOpSpanBase* span; 86 chase->pop(&span); 87 SkOpSegment* segment = span->segment(); 88 *startPtr = span->ptT()->next()->span(); 89 bool done = true; 90 *endPtr = nullptr; 91 if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done)) { 92 *startPtr = last->start(); 93 *endPtr = last->end(); 94 #if TRY_ROTATE 95 *chase->insert(0) = span; 96 #else 97 *chase->append() = span; 98 #endif 99 return last->segment(); 100 } 101 if (done) { 102 continue; 103 } 104 // find first angle, initialize winding to computed wind sum 105 int winding; 106 bool sortable; 107 const SkOpAngle* angle = AngleWinding(*startPtr, *endPtr, &winding, &sortable); 108 if (!angle) { 109 return nullptr; 110 } 111 if (winding == SK_MinS32) { 112 continue; 113 } 114 int sumWinding SK_INIT_TO_AVOID_WARNING; 115 if (sortable) { 116 segment = angle->segment(); 117 sumWinding = segment->updateWindingReverse(angle); 118 } 119 SkOpSegment* first = nullptr; 120 const SkOpAngle* firstAngle = angle; 121 while ((angle = angle->next()) != firstAngle) { 122 segment = angle->segment(); 123 SkOpSpanBase* start = angle->start(); 124 SkOpSpanBase* end = angle->end(); 125 int maxWinding SK_INIT_TO_AVOID_WARNING; 126 if (sortable) { 127 segment->setUpWinding(start, end, &maxWinding, &sumWinding); 128 } 129 if (!segment->done(angle)) { 130 if (!first && (sortable || start->starter(end)->windSum() != SK_MinS32)) { 131 first = segment; 132 *startPtr = start; 133 *endPtr = end; 134 } 135 // OPTIMIZATION: should this also add to the chase? 136 if (sortable) { 137 // TODO: add error handling 138 SkAssertResult(segment->markAngle(maxWinding, sumWinding, angle, nullptr)); 139 } 140 } 141 } 142 if (first) { 143 #if TRY_ROTATE 144 *chase->insert(0) = span; 145 #else 146 *chase->append() = span; 147 #endif 148 return first; 149 } 150 } 151 return nullptr; 152 } 153 154 bool SortContourList(SkOpContourHead** contourList, bool evenOdd, bool oppEvenOdd) { 155 SkTDArray<SkOpContour* > list; 156 SkOpContour* contour = *contourList; 157 do { 158 if (contour->count()) { 159 contour->setOppXor(contour->operand() ? evenOdd : oppEvenOdd); 160 *list.append() = contour; 161 } 162 } while ((contour = contour->next())); 163 int count = list.count(); 164 if (!count) { 165 return false; 166 } 167 if (count > 1) { 168 SkTQSort<SkOpContour>(list.begin(), list.end() - 1); 169 } 170 contour = list[0]; 171 SkOpContourHead* contourHead = static_cast<SkOpContourHead*>(contour); 172 contour->globalState()->setContourHead(contourHead); 173 *contourList = contourHead; 174 for (int index = 1; index < count; ++index) { 175 SkOpContour* next = list[index]; 176 contour->setNext(next); 177 contour = next; 178 } 179 contour->setNext(nullptr); 180 return true; 181 } 182 183 static void calc_angles(SkOpContourHead* contourList DEBUG_COIN_DECLARE_PARAMS()) { 184 DEBUG_STATIC_SET_PHASE(contourList); 185 SkOpContour* contour = contourList; 186 do { 187 contour->calcAngles(); 188 } while ((contour = contour->next())); 189 } 190 191 static bool missing_coincidence(SkOpContourHead* contourList DEBUG_COIN_DECLARE_PARAMS()) { 192 DEBUG_STATIC_SET_PHASE(contourList); 193 SkOpContour* contour = contourList; 194 bool result = false; 195 do { 196 result |= contour->missingCoincidence(); 197 } while ((contour = contour->next())); 198 return result; 199 } 200 201 static bool move_multiples(SkOpContourHead* contourList DEBUG_COIN_DECLARE_PARAMS()) { 202 DEBUG_STATIC_SET_PHASE(contourList); 203 SkOpContour* contour = contourList; 204 do { 205 if (!contour->moveMultiples()) { 206 return false; 207 } 208 } while ((contour = contour->next())); 209 return true; 210 } 211 212 static bool move_nearby(SkOpContourHead* contourList DEBUG_COIN_DECLARE_PARAMS()) { 213 DEBUG_STATIC_SET_PHASE(contourList); 214 SkOpContour* contour = contourList; 215 do { 216 if (!contour->moveNearby()) { 217 return false; 218 } 219 } while ((contour = contour->next())); 220 return true; 221 } 222 223 static bool sort_angles(SkOpContourHead* contourList) { 224 SkOpContour* contour = contourList; 225 do { 226 if (!contour->sortAngles()) { 227 return false; 228 } 229 } while ((contour = contour->next())); 230 return true; 231 } 232 233 bool HandleCoincidence(SkOpContourHead* contourList, SkOpCoincidence* coincidence) { 234 SkOpGlobalState* globalState = contourList->globalState(); 235 // match up points within the coincident runs 236 if (!coincidence->addExpanded(DEBUG_PHASE_ONLY_PARAMS(kIntersecting))) { 237 return false; 238 } 239 // combine t values when multiple intersections occur on some segments but not others 240 if (!move_multiples(contourList DEBUG_PHASE_PARAMS(kWalking))) { 241 return false; 242 } 243 // move t values and points together to eliminate small/tiny gaps 244 if (!move_nearby(contourList DEBUG_COIN_PARAMS())) { 245 return false; 246 } 247 // add coincidence formed by pairing on curve points and endpoints 248 coincidence->correctEnds(DEBUG_PHASE_ONLY_PARAMS(kIntersecting)); 249 if (!coincidence->addEndMovedSpans(DEBUG_COIN_ONLY_PARAMS())) { 250 return false; 251 } 252 const int SAFETY_COUNT = 3; 253 int safetyHatch = SAFETY_COUNT; 254 // look for coincidence present in A-B and A-C but missing in B-C 255 do { 256 bool added; 257 if (!coincidence->addMissing(&added DEBUG_ITER_PARAMS(SAFETY_COUNT - safetyHatch))) { 258 return false; 259 } 260 if (!added) { 261 break; 262 } 263 if (!--safetyHatch) { 264 SkASSERT(globalState->debugSkipAssert()); 265 return false; 266 } 267 move_nearby(contourList DEBUG_ITER_PARAMS(SAFETY_COUNT - safetyHatch - 1)); 268 } while (true); 269 // check to see if, loosely, coincident ranges may be expanded 270 if (coincidence->expand(DEBUG_COIN_ONLY_PARAMS())) { 271 bool added; 272 if (!coincidence->addMissing(&added DEBUG_COIN_PARAMS())) { 273 return false; 274 } 275 if (!coincidence->addExpanded(DEBUG_COIN_ONLY_PARAMS())) { 276 return false; 277 } 278 if (!move_multiples(contourList DEBUG_COIN_PARAMS())) { 279 return false; 280 } 281 move_nearby(contourList DEBUG_COIN_PARAMS()); 282 } 283 // the expanded ranges may not align -- add the missing spans 284 if (!coincidence->addExpanded(DEBUG_PHASE_ONLY_PARAMS(kWalking))) { 285 return false; 286 } 287 // mark spans of coincident segments as coincident 288 coincidence->mark(DEBUG_COIN_ONLY_PARAMS()); 289 // look for coincidence lines and curves undetected by intersection 290 if (missing_coincidence(contourList DEBUG_COIN_PARAMS())) { 291 (void) coincidence->expand(DEBUG_PHASE_ONLY_PARAMS(kIntersecting)); 292 if (!coincidence->addExpanded(DEBUG_COIN_ONLY_PARAMS())) { 293 return false; 294 } 295 if (!coincidence->mark(DEBUG_PHASE_ONLY_PARAMS(kWalking))) { 296 return false; 297 } 298 } else { 299 (void) coincidence->expand(DEBUG_COIN_ONLY_PARAMS()); 300 } 301 (void) coincidence->expand(DEBUG_COIN_ONLY_PARAMS()); 302 303 SkOpCoincidence overlaps(globalState); 304 safetyHatch = SAFETY_COUNT; 305 do { 306 SkOpCoincidence* pairs = overlaps.isEmpty() ? coincidence : &overlaps; 307 // adjust the winding value to account for coincident edges 308 if (!pairs->apply(DEBUG_ITER_ONLY_PARAMS(SAFETY_COUNT - safetyHatch))) { 309 return false; 310 } 311 // For each coincident pair that overlaps another, when the receivers (the 1st of the pair) 312 // are different, construct a new pair to resolve their mutual span 313 if (!pairs->findOverlaps(&overlaps DEBUG_ITER_PARAMS(SAFETY_COUNT - safetyHatch))) { 314 return false; 315 } 316 if (!--safetyHatch) { 317 SkASSERT(globalState->debugSkipAssert()); 318 return false; 319 } 320 } while (!overlaps.isEmpty()); 321 calc_angles(contourList DEBUG_COIN_PARAMS()); 322 if (!sort_angles(contourList)) { 323 return false; 324 } 325 #if DEBUG_COINCIDENCE_VERBOSE 326 coincidence->debugShowCoincidence(); 327 #endif 328 #if DEBUG_COINCIDENCE 329 coincidence->debugValidate(); 330 #endif 331 SkPathOpsDebug::ShowActiveSpans(contourList); 332 return true; 333 } 334