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 13 static SkOpSegment* findChaseOp(SkTDArray<SkOpSpanBase*>& chase, SkOpSpanBase** startPtr, 14 SkOpSpanBase** endPtr) { 15 while (chase.count()) { 16 SkOpSpanBase* span; 17 chase.pop(&span); 18 // OPTIMIZE: prev makes this compatible with old code -- but is it necessary? 19 *startPtr = span->ptT()->prev()->span(); 20 SkOpSegment* segment = (*startPtr)->segment(); 21 bool done = true; 22 *endPtr = nullptr; 23 if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done)) { 24 *startPtr = last->start(); 25 *endPtr = last->end(); 26 #if TRY_ROTATE 27 *chase.insert(0) = span; 28 #else 29 *chase.append() = span; 30 #endif 31 return last->segment(); 32 } 33 if (done) { 34 continue; 35 } 36 int winding; 37 bool sortable; 38 const SkOpAngle* angle = AngleWinding(*startPtr, *endPtr, &winding, &sortable); 39 if (!angle) { 40 return nullptr; 41 } 42 if (winding == SK_MinS32) { 43 continue; 44 } 45 int sumMiWinding, sumSuWinding; 46 if (sortable) { 47 segment = angle->segment(); 48 sumMiWinding = segment->updateWindingReverse(angle); 49 if (sumMiWinding == SK_MinS32) { 50 SkASSERT(segment->globalState()->debugSkipAssert()); 51 return nullptr; 52 } 53 sumSuWinding = segment->updateOppWindingReverse(angle); 54 if (sumSuWinding == SK_MinS32) { 55 SkASSERT(segment->globalState()->debugSkipAssert()); 56 return nullptr; 57 } 58 if (segment->operand()) { 59 SkTSwap<int>(sumMiWinding, sumSuWinding); 60 } 61 } 62 SkOpSegment* first = nullptr; 63 const SkOpAngle* firstAngle = angle; 64 while ((angle = angle->next()) != firstAngle) { 65 segment = angle->segment(); 66 SkOpSpanBase* start = angle->start(); 67 SkOpSpanBase* end = angle->end(); 68 int maxWinding, sumWinding, oppMaxWinding, oppSumWinding; 69 if (sortable) { 70 segment->setUpWindings(start, end, &sumMiWinding, &sumSuWinding, 71 &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); 72 } 73 if (!segment->done(angle)) { 74 if (!first && (sortable || start->starter(end)->windSum() != SK_MinS32)) { 75 first = segment; 76 *startPtr = start; 77 *endPtr = end; 78 } 79 // OPTIMIZATION: should this also add to the chase? 80 if (sortable) { 81 (void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding, 82 oppSumWinding, angle); 83 } 84 } 85 } 86 if (first) { 87 #if TRY_ROTATE 88 *chase.insert(0) = span; 89 #else 90 *chase.append() = span; 91 #endif 92 return first; 93 } 94 } 95 return nullptr; 96 } 97 98 static bool bridgeOp(SkOpContourHead* contourList, const SkPathOp op, 99 const int xorMask, const int xorOpMask, SkPathWriter* simple) { 100 bool unsortable = false; 101 do { 102 SkOpSpan* span = FindSortableTop(contourList); 103 if (!span) { 104 break; 105 } 106 SkOpSegment* current = span->segment(); 107 SkOpSpanBase* start = span->next(); 108 SkOpSpanBase* end = span; 109 SkTDArray<SkOpSpanBase*> chase; 110 do { 111 if (current->activeOp(start, end, xorMask, xorOpMask, op)) { 112 do { 113 if (!unsortable && current->done()) { 114 break; 115 } 116 SkASSERT(unsortable || !current->done()); 117 SkOpSpanBase* nextStart = start; 118 SkOpSpanBase* nextEnd = end; 119 SkOpSegment* next = current->findNextOp(&chase, &nextStart, &nextEnd, 120 &unsortable, op, xorMask, xorOpMask); 121 if (!next) { 122 if (!unsortable && simple->hasMove() 123 && current->verb() != SkPath::kLine_Verb 124 && !simple->isClosed()) { 125 if (!current->addCurveTo(start, end, simple)) { 126 return false; 127 } 128 if (!simple->isClosed()) { 129 SkPathOpsDebug::ShowActiveSpans(contourList); 130 } 131 } 132 break; 133 } 134 #if DEBUG_FLOW 135 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__, 136 current->debugID(), start->pt().fX, start->pt().fY, 137 end->pt().fX, end->pt().fY); 138 #endif 139 if (!current->addCurveTo(start, end, simple)) { 140 return false; 141 } 142 current = next; 143 start = nextStart; 144 end = nextEnd; 145 } while (!simple->isClosed() && (!unsortable || !start->starter(end)->done())); 146 if (current->activeWinding(start, end) && !simple->isClosed()) { 147 SkOpSpan* spanStart = start->starter(end); 148 if (!spanStart->done()) { 149 if (!current->addCurveTo(start, end, simple)) { 150 return false; 151 } 152 current->markDone(spanStart); 153 } 154 } 155 simple->finishContour(); 156 } else { 157 SkOpSpanBase* last = current->markAndChaseDone(start, end); 158 if (last && !last->chased()) { 159 last->setChased(true); 160 SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last)); 161 *chase.append() = last; 162 #if DEBUG_WINDING 163 SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segment()->debugID()); 164 if (!last->final()) { 165 SkDebugf(" windSum=%d", last->upCast()->windSum()); 166 } 167 SkDebugf("\n"); 168 #endif 169 } 170 } 171 current = findChaseOp(chase, &start, &end); 172 SkPathOpsDebug::ShowActiveSpans(contourList); 173 if (!current) { 174 break; 175 } 176 } while (true); 177 } while (true); 178 return true; 179 } 180 181 // pretty picture: 182 // https://docs.google.com/a/google.com/drawings/d/1sPV8rPfpEFXymBp3iSbDRWAycp1b-7vD9JP2V-kn9Ss/edit?usp=sharing 183 static const SkPathOp gOpInverse[kReverseDifference_SkPathOp + 1][2][2] = { 184 // inside minuend outside minuend 185 // inside subtrahend outside subtrahend inside subtrahend outside subtrahend 186 {{ kDifference_SkPathOp, kIntersect_SkPathOp }, { kUnion_SkPathOp, kReverseDifference_SkPathOp }}, 187 {{ kIntersect_SkPathOp, kDifference_SkPathOp }, { kReverseDifference_SkPathOp, kUnion_SkPathOp }}, 188 {{ kUnion_SkPathOp, kReverseDifference_SkPathOp }, { kDifference_SkPathOp, kIntersect_SkPathOp }}, 189 {{ kXOR_SkPathOp, kXOR_SkPathOp }, { kXOR_SkPathOp, kXOR_SkPathOp }}, 190 {{ kReverseDifference_SkPathOp, kUnion_SkPathOp }, { kIntersect_SkPathOp, kDifference_SkPathOp }}, 191 }; 192 193 static const bool gOutInverse[kReverseDifference_SkPathOp + 1][2][2] = { 194 {{ false, false }, { true, false }}, // diff 195 {{ false, false }, { false, true }}, // sect 196 {{ false, true }, { true, true }}, // union 197 {{ false, true }, { true, false }}, // xor 198 {{ false, true }, { false, false }}, // rev diff 199 }; 200 201 #if DEBUG_T_SECT_LOOP_COUNT 202 203 #include "SkMutex.h" 204 205 SK_DECLARE_STATIC_MUTEX(debugWorstLoop); 206 207 SkOpGlobalState debugWorstState(nullptr, nullptr SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr) 208 SkDEBUGPARAMS(nullptr)); 209 210 void ReportPathOpsDebugging() { 211 debugWorstState.debugLoopReport(); 212 } 213 214 extern void (*gVerboseFinalize)(); 215 216 #endif 217 218 bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result 219 SkDEBUGPARAMS(bool skipAssert) SkDEBUGPARAMS(const char* testName)) { 220 SkSTArenaAlloc<4096> allocator; // FIXME: add a constant expression here, tune 221 SkOpContour contour; 222 SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour); 223 SkOpGlobalState globalState(contourList, &allocator 224 SkDEBUGPARAMS(skipAssert) SkDEBUGPARAMS(testName)); 225 SkOpCoincidence coincidence(&globalState); 226 #if DEBUG_DUMP_VERIFY 227 #ifndef SK_DEBUG 228 const char* testName = "release"; 229 #endif 230 if (SkPathOpsDebug::gDumpOp) { 231 SkPathOpsDebug::DumpOp(one, two, op, testName); 232 } 233 #endif 234 op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()]; 235 SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()] 236 ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType; 237 SkScalar scaleFactor = SkTMax(ScaleFactor(one), ScaleFactor(two)); 238 SkPath scaledOne, scaledTwo; 239 const SkPath* minuend, * subtrahend; 240 if (scaleFactor > SK_Scalar1) { 241 ScalePath(one, 1.f / scaleFactor, &scaledOne); 242 minuend = &scaledOne; 243 ScalePath(two, 1.f / scaleFactor, &scaledTwo); 244 subtrahend = &scaledTwo; 245 } else { 246 minuend = &one; 247 subtrahend = &two; 248 } 249 if (op == kReverseDifference_SkPathOp) { 250 SkTSwap(minuend, subtrahend); 251 op = kDifference_SkPathOp; 252 } 253 #if DEBUG_SORT 254 SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault; 255 #endif 256 // turn path into list of segments 257 SkOpEdgeBuilder builder(*minuend, contourList, &globalState); 258 if (builder.unparseable()) { 259 return false; 260 } 261 const int xorMask = builder.xorMask(); 262 builder.addOperand(*subtrahend); 263 if (!builder.finish()) { 264 return false; 265 } 266 #if DEBUG_DUMP_SEGMENTS 267 contourList->dumpSegments("seg", op); 268 #endif 269 270 const int xorOpMask = builder.xorMask(); 271 if (!SortContourList(&contourList, xorMask == kEvenOdd_PathOpsMask, 272 xorOpMask == kEvenOdd_PathOpsMask)) { 273 result->reset(); 274 result->setFillType(fillType); 275 return true; 276 } 277 // find all intersections between segments 278 SkOpContour* current = contourList; 279 do { 280 SkOpContour* next = current; 281 while (AddIntersectTs(current, next, &coincidence) 282 && (next = next->next())) 283 ; 284 } while ((current = current->next())); 285 #if DEBUG_VALIDATE 286 globalState.setPhase(SkOpPhase::kWalking); 287 #endif 288 bool success = HandleCoincidence(contourList, &coincidence); 289 #if DEBUG_COIN 290 globalState.debugAddToGlobalCoinDicts(); 291 #endif 292 if (!success) { 293 return false; 294 } 295 #if DEBUG_ALIGNMENT 296 contourList->dumpSegments("aligned"); 297 #endif 298 // construct closed contours 299 result->reset(); 300 result->setFillType(fillType); 301 SkPathWriter wrapper(*result); 302 if (!bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper)) { 303 return false; 304 } 305 wrapper.assemble(); // if some edges could not be resolved, assemble remaining 306 #if DEBUG_T_SECT_LOOP_COUNT 307 { 308 SkAutoMutexAcquire autoM(debugWorstLoop); 309 if (!gVerboseFinalize) { 310 gVerboseFinalize = &ReportPathOpsDebugging; 311 } 312 debugWorstState.debugDoYourWorst(&globalState); 313 } 314 #endif 315 if (scaleFactor > 1) { 316 ScalePath(*result, scaleFactor, result); 317 } 318 return true; 319 } 320 321 bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { 322 #if DEBUG_DUMP_VERIFY 323 if (SkPathOpsDebug::gVerifyOp) { 324 if (!OpDebug(one, two, op, result SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr))) { 325 SkPathOpsDebug::ReportOpFail(one, two, op); 326 return false; 327 } 328 SkPathOpsDebug::VerifyOp(one, two, op, *result); 329 return true; 330 } 331 #endif 332 return OpDebug(one, two, op, result SkDEBUGPARAMS(true) SkDEBUGPARAMS(nullptr)); 333 } 334
