SkPathOpsCommon.cpp revision a35ab3e6e024d0b548ded26a2e3b8ecd838ead93
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 14SkScalar 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 29void 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 36const 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 88SkOpSegment* FindUndone(SkOpContourHead* contourList, SkOpSpanBase** startPtr, 89 SkOpSpanBase** endPtr) { 90 SkOpSegment* result; 91 SkOpContour* contour = contourList; 92 do { 93 result = contour->undoneSegment(startPtr, endPtr); 94 if (result) { 95 return result; 96 } 97 } while ((contour = contour->next())); 98 return nullptr; 99} 100 101SkOpSegment* FindChase(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** startPtr, 102 SkOpSpanBase** endPtr) { 103 while (chase->count()) { 104 SkOpSpanBase* span; 105 chase->pop(&span); 106 SkOpSegment* segment = span->segment(); 107 *startPtr = span->ptT()->next()->span(); 108 bool done = true; 109 *endPtr = nullptr; 110 if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done)) { 111 *startPtr = last->start(); 112 *endPtr = last->end(); 113 #if TRY_ROTATE 114 *chase->insert(0) = span; 115 #else 116 *chase->append() = span; 117 #endif 118 return last->segment(); 119 } 120 if (done) { 121 continue; 122 } 123 // find first angle, initialize winding to computed wind sum 124 int winding; 125 bool sortable; 126 const SkOpAngle* angle = AngleWinding(*startPtr, *endPtr, &winding, &sortable); 127 if (!angle) { 128 return nullptr; 129 } 130 if (winding == SK_MinS32) { 131 continue; 132 } 133 int sumWinding SK_INIT_TO_AVOID_WARNING; 134 if (sortable) { 135 segment = angle->segment(); 136 sumWinding = segment->updateWindingReverse(angle); 137 } 138 SkOpSegment* first = nullptr; 139 const SkOpAngle* firstAngle = angle; 140 while ((angle = angle->next()) != firstAngle) { 141 segment = angle->segment(); 142 SkOpSpanBase* start = angle->start(); 143 SkOpSpanBase* end = angle->end(); 144 int maxWinding SK_INIT_TO_AVOID_WARNING; 145 if (sortable) { 146 segment->setUpWinding(start, end, &maxWinding, &sumWinding); 147 } 148 if (!segment->done(angle)) { 149 if (!first && (sortable || start->starter(end)->windSum() != SK_MinS32)) { 150 first = segment; 151 *startPtr = start; 152 *endPtr = end; 153 } 154 // OPTIMIZATION: should this also add to the chase? 155 if (sortable) { 156 (void) segment->markAngle(maxWinding, sumWinding, angle); 157 } 158 } 159 } 160 if (first) { 161 #if TRY_ROTATE 162 *chase->insert(0) = span; 163 #else 164 *chase->append() = span; 165 #endif 166 return first; 167 } 168 } 169 return nullptr; 170} 171 172bool SortContourList(SkOpContourHead** contourList, bool evenOdd, bool oppEvenOdd) { 173 SkTDArray<SkOpContour* > list; 174 SkOpContour* contour = *contourList; 175 do { 176 if (contour->count()) { 177 contour->setOppXor(contour->operand() ? evenOdd : oppEvenOdd); 178 *list.append() = contour; 179 } 180 } while ((contour = contour->next())); 181 int count = list.count(); 182 if (!count) { 183 return false; 184 } 185 if (count > 1) { 186 SkTQSort<SkOpContour>(list.begin(), list.end() - 1); 187 } 188 contour = list[0]; 189 SkOpContourHead* contourHead = static_cast<SkOpContourHead*>(contour); 190 contour->globalState()->setContourHead(contourHead); 191 *contourList = contourHead; 192 for (int index = 1; index < count; ++index) { 193 SkOpContour* next = list[index]; 194 contour->setNext(next); 195 contour = next; 196 } 197 contour->setNext(nullptr); 198 return true; 199} 200 201static void calc_angles(SkOpContourHead* contourList DEBUG_COIN_DECLARE_PARAMS()) { 202 DEBUG_STATIC_SET_PHASE(contourList); 203 SkOpContour* contour = contourList; 204 do { 205 contour->calcAngles(); 206 } while ((contour = contour->next())); 207} 208 209static bool missing_coincidence(SkOpContourHead* contourList DEBUG_COIN_DECLARE_PARAMS()) { 210 DEBUG_STATIC_SET_PHASE(contourList); 211 SkOpContour* contour = contourList; 212 bool result = false; 213 do { 214 result |= contour->missingCoincidence(); 215 } while ((contour = contour->next())); 216 return result; 217} 218 219static bool move_multiples(SkOpContourHead* contourList DEBUG_COIN_DECLARE_PARAMS()) { 220 DEBUG_STATIC_SET_PHASE(contourList); 221 SkOpContour* contour = contourList; 222 do { 223 if (!contour->moveMultiples()) { 224 return false; 225 } 226 } while ((contour = contour->next())); 227 return true; 228} 229 230static void move_nearby(SkOpContourHead* contourList DEBUG_COIN_DECLARE_PARAMS()) { 231 DEBUG_STATIC_SET_PHASE(contourList); 232 SkOpContour* contour = contourList; 233 do { 234 contour->moveNearby(); 235 } while ((contour = contour->next())); 236} 237 238static bool sort_angles(SkOpContourHead* contourList) { 239 SkOpContour* contour = contourList; 240 do { 241 if (!contour->sortAngles()) { 242 return false; 243 } 244 } while ((contour = contour->next())); 245 return true; 246} 247 248bool HandleCoincidence(SkOpContourHead* contourList, SkOpCoincidence* coincidence) { 249 SkOpGlobalState* globalState = contourList->globalState(); 250 // match up points within the coincident runs 251 if (!coincidence->addExpanded(DEBUG_PHASE_ONLY_PARAMS(kIntersecting))) { 252 return false; 253 } 254 // combine t values when multiple intersections occur on some segments but not others 255 if (!move_multiples(contourList DEBUG_PHASE_PARAMS(kWalking))) { 256 return false; 257 } 258 // move t values and points together to eliminate small/tiny gaps 259 move_nearby(contourList DEBUG_COIN_PARAMS()); 260 // add coincidence formed by pairing on curve points and endpoints 261 coincidence->correctEnds(DEBUG_PHASE_ONLY_PARAMS(kIntersecting)); 262 if (!coincidence->addEndMovedSpans(DEBUG_COIN_ONLY_PARAMS())) { 263 return false; 264 } 265 const int SAFETY_COUNT = 3; 266 int safetyHatch = SAFETY_COUNT; 267 // look for coincidence present in A-B and A-C but missing in B-C 268 do { 269 bool added; 270 if (!coincidence->addMissing(&added DEBUG_ITER_PARAMS(SAFETY_COUNT - safetyHatch))) { 271 return false; 272 } 273 if (!added) { 274 break; 275 } 276 if (!--safetyHatch) { 277 SkASSERT(globalState->debugSkipAssert()); 278 return false; 279 } 280 move_nearby(contourList DEBUG_ITER_PARAMS(SAFETY_COUNT - safetyHatch - 1)); 281 } while (true); 282 // check to see if, loosely, coincident ranges may be expanded 283 if (coincidence->expand(DEBUG_COIN_ONLY_PARAMS())) { 284 bool added; 285 if (!coincidence->addMissing(&added DEBUG_COIN_PARAMS())) { 286 return false; 287 } 288 if (!coincidence->addExpanded(DEBUG_COIN_ONLY_PARAMS())) { 289 return false; 290 } 291 if (!move_multiples(contourList DEBUG_COIN_PARAMS())) { 292 return false; 293 } 294 move_nearby(contourList DEBUG_COIN_PARAMS()); 295 } 296 // the expanded ranges may not align -- add the missing spans 297 if (!coincidence->addExpanded(DEBUG_PHASE_ONLY_PARAMS(kWalking))) { 298 return false; 299 } 300 // mark spans of coincident segments as coincident 301 coincidence->mark(DEBUG_COIN_ONLY_PARAMS()); 302 // look for coincidence lines and curves undetected by intersection 303 if (missing_coincidence(contourList DEBUG_COIN_PARAMS())) { 304 (void) coincidence->expand(DEBUG_PHASE_ONLY_PARAMS(kIntersecting)); 305 if (!coincidence->addExpanded(DEBUG_COIN_ONLY_PARAMS())) { 306 return false; 307 } 308 if (!coincidence->mark(DEBUG_PHASE_ONLY_PARAMS(kWalking))) { 309 return false; 310 } 311 } else { 312 (void) coincidence->expand(DEBUG_COIN_ONLY_PARAMS()); 313 } 314 (void) coincidence->expand(DEBUG_COIN_ONLY_PARAMS()); 315 316 SkOpCoincidence overlaps(globalState); 317 safetyHatch = SAFETY_COUNT; 318 do { 319 SkOpCoincidence* pairs = overlaps.isEmpty() ? coincidence : &overlaps; 320 // adjust the winding value to account for coincident edges 321 if (!pairs->apply(DEBUG_ITER_ONLY_PARAMS(SAFETY_COUNT - safetyHatch))) { 322 return false; 323 } 324 // For each coincident pair that overlaps another, when the receivers (the 1st of the pair) 325 // are different, construct a new pair to resolve their mutual span 326 if (!pairs->findOverlaps(&overlaps DEBUG_ITER_PARAMS(SAFETY_COUNT - safetyHatch))) { 327 return false; 328 } 329 if (!--safetyHatch) { 330 SkASSERT(globalState->debugSkipAssert()); 331 return false; 332 } 333 } while (!overlaps.isEmpty()); 334 calc_angles(contourList DEBUG_COIN_PARAMS()); 335 if (!sort_angles(contourList)) { 336 return false; 337 } 338#if DEBUG_COINCIDENCE_VERBOSE 339 coincidence->debugShowCoincidence(); 340#endif 341#if DEBUG_COINCIDENCE 342 coincidence->debugValidate(); 343#endif 344 SkPathOpsDebug::ShowActiveSpans(contourList); 345 return true; 346} 347