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