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 "SkOpEdgeBuilder.h" 9 #include "SkPathOpsCommon.h" 10 #include "SkPathWriter.h" 11 12 static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int* tIndex, int* endIndex) { 13 while (chase.count()) { 14 SkOpSpan* span; 15 chase.pop(&span); 16 const SkOpSpan& backPtr = span->fOther->span(span->fOtherIndex); 17 SkOpSegment* segment = backPtr.fOther; 18 *tIndex = backPtr.fOtherIndex; 19 bool sortable = true; 20 bool done = true; 21 *endIndex = -1; 22 if (const SkOpAngle* last = segment->activeAngle(*tIndex, tIndex, endIndex, &done, 23 &sortable)) { 24 if (last->unorderable()) { 25 continue; 26 } 27 *tIndex = last->start(); 28 *endIndex = last->end(); 29 #if TRY_ROTATE 30 *chase.insert(0) = span; 31 #else 32 *chase.append() = span; 33 #endif 34 return last->segment(); 35 } 36 if (done) { 37 continue; 38 } 39 if (!sortable) { 40 continue; 41 } 42 // find first angle, initialize winding to computed fWindSum 43 const SkOpAngle* angle = segment->spanToAngle(*tIndex, *endIndex); 44 if (!angle) { 45 continue; 46 } 47 const SkOpAngle* firstAngle = angle; 48 SkDEBUGCODE(bool loop = false); 49 int winding; 50 do { 51 angle = angle->next(); 52 SkASSERT(angle != firstAngle || !loop); 53 SkDEBUGCODE(loop |= angle == firstAngle); 54 segment = angle->segment(); 55 winding = segment->windSum(angle); 56 } while (winding == SK_MinS32); 57 int sumMiWinding = segment->updateWindingReverse(angle); 58 int sumSuWinding = segment->updateOppWindingReverse(angle); 59 if (segment->operand()) { 60 SkTSwap<int>(sumMiWinding, sumSuWinding); 61 } 62 SkOpSegment* first = NULL; 63 while ((angle = angle->next()) != firstAngle) { 64 segment = angle->segment(); 65 int start = angle->start(); 66 int end = angle->end(); 67 int maxWinding, sumWinding, oppMaxWinding, oppSumWinding; 68 segment->setUpWindings(start, end, &sumMiWinding, &sumSuWinding, 69 &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); 70 if (!segment->done(angle)) { 71 if (!first) { 72 first = segment; 73 *tIndex = start; 74 *endIndex = end; 75 } 76 // OPTIMIZATION: should this also add to the chase? 77 (void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding, 78 oppSumWinding, angle); 79 } 80 } 81 if (first) { 82 #if TRY_ROTATE 83 *chase.insert(0) = span; 84 #else 85 *chase.append() = span; 86 #endif 87 return first; 88 } 89 } 90 return NULL; 91 } 92 93 /* 94 static bool windingIsActive(int winding, int oppWinding, int spanWinding, int oppSpanWinding, 95 bool windingIsOp, PathOp op) { 96 bool active = windingIsActive(winding, spanWinding); 97 if (!active) { 98 return false; 99 } 100 if (oppSpanWinding && windingIsActive(oppWinding, oppSpanWinding)) { 101 switch (op) { 102 case kIntersect_Op: 103 case kUnion_Op: 104 return true; 105 case kDifference_Op: { 106 int absSpan = abs(spanWinding); 107 int absOpp = abs(oppSpanWinding); 108 return windingIsOp ? absSpan < absOpp : absSpan > absOpp; 109 } 110 case kXor_Op: 111 return spanWinding != oppSpanWinding; 112 default: 113 SkASSERT(0); 114 } 115 } 116 bool opActive = oppWinding != 0; 117 return gOpLookup[op][opActive][windingIsOp]; 118 } 119 */ 120 121 static bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp op, 122 const int xorMask, const int xorOpMask, SkPathWriter* simple) { 123 bool firstContour = true; 124 bool unsortable = false; 125 bool topUnsortable = false; 126 bool firstPass = true; 127 SkPoint lastTopLeft; 128 SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin}; 129 do { 130 int index, endIndex; 131 bool topDone; 132 bool onlyVertical = false; 133 lastTopLeft = topLeft; 134 SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kBinarySingle, &firstContour, 135 &index, &endIndex, &topLeft, &topUnsortable, &topDone, &onlyVertical, firstPass); 136 if (!current) { 137 if ((!topUnsortable || firstPass) && !topDone) { 138 SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin); 139 if (lastTopLeft.fX == SK_ScalarMin && lastTopLeft.fY == SK_ScalarMin) { 140 if (firstPass) { 141 firstPass = false; 142 } else { 143 break; 144 } 145 } 146 topLeft.fX = topLeft.fY = SK_ScalarMin; 147 continue; 148 } 149 break; 150 } else if (onlyVertical) { 151 break; 152 } 153 firstPass = !topUnsortable || lastTopLeft != topLeft; 154 SkTDArray<SkOpSpan*> chase; 155 do { 156 if (current->activeOp(index, endIndex, xorMask, xorOpMask, op)) { 157 do { 158 if (!unsortable && current->done()) { 159 break; 160 } 161 SkASSERT(unsortable || !current->done()); 162 int nextStart = index; 163 int nextEnd = endIndex; 164 SkOpSegment* next = current->findNextOp(&chase, &nextStart, &nextEnd, 165 &unsortable, op, xorMask, xorOpMask); 166 if (!next) { 167 if (!unsortable && simple->hasMove() 168 && current->verb() != SkPath::kLine_Verb 169 && !simple->isClosed()) { 170 current->addCurveTo(index, endIndex, simple, true); 171 #if DEBUG_ACTIVE_SPANS 172 if (!simple->isClosed()) { 173 DebugShowActiveSpans(contourList); 174 } 175 #endif 176 // SkASSERT(simple->isClosed()); 177 } 178 break; 179 } 180 #if DEBUG_FLOW 181 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__, 182 current->debugID(), current->xyAtT(index).fX, current->xyAtT(index).fY, 183 current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY); 184 #endif 185 current->addCurveTo(index, endIndex, simple, true); 186 current = next; 187 index = nextStart; 188 endIndex = nextEnd; 189 } while (!simple->isClosed() && (!unsortable 190 || !current->done(SkMin32(index, endIndex)))); 191 if (current->activeWinding(index, endIndex) && !simple->isClosed()) { 192 // FIXME : add to simplify, xor cpaths 193 int min = SkMin32(index, endIndex); 194 if (!unsortable && !simple->isEmpty()) { 195 unsortable = current->checkSmall(min); 196 } 197 if (!current->done(min)) { 198 current->addCurveTo(index, endIndex, simple, true); 199 current->markDoneBinary(min); 200 } 201 } 202 simple->close(); 203 } else { 204 SkOpSpan* last = current->markAndChaseDoneBinary(index, endIndex); 205 if (last && !last->fChased && !last->fLoop) { 206 last->fChased = true; 207 SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last)); 208 *chase.append() = last; 209 #if DEBUG_WINDING 210 SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__, 211 last->fOther->span(last->fOtherIndex).fOther->debugID(), last->fWindSum, 212 last->fSmall); 213 #endif 214 } 215 } 216 current = findChaseOp(chase, &index, &endIndex); 217 #if DEBUG_ACTIVE_SPANS 218 DebugShowActiveSpans(contourList); 219 #endif 220 if (!current) { 221 break; 222 } 223 } while (true); 224 } while (true); 225 return simple->someAssemblyRequired(); 226 } 227 228 // pretty picture: 229 // https://docs.google.com/a/google.com/drawings/d/1sPV8rPfpEFXymBp3iSbDRWAycp1b-7vD9JP2V-kn9Ss/edit?usp=sharing 230 static const SkPathOp gOpInverse[kReverseDifference_PathOp + 1][2][2] = { 231 // inside minuend outside minuend 232 // inside subtrahend outside subtrahend inside subtrahend outside subtrahend 233 {{ kDifference_PathOp, kIntersect_PathOp }, { kUnion_PathOp, kReverseDifference_PathOp }}, 234 {{ kIntersect_PathOp, kDifference_PathOp }, { kReverseDifference_PathOp, kUnion_PathOp }}, 235 {{ kUnion_PathOp, kReverseDifference_PathOp }, { kDifference_PathOp, kIntersect_PathOp }}, 236 {{ kXOR_PathOp, kXOR_PathOp }, { kXOR_PathOp, kXOR_PathOp }}, 237 {{ kReverseDifference_PathOp, kUnion_PathOp }, { kIntersect_PathOp, kDifference_PathOp }}, 238 }; 239 240 static const bool gOutInverse[kReverseDifference_PathOp + 1][2][2] = { 241 {{ false, false }, { true, false }}, // diff 242 {{ false, false }, { false, true }}, // sect 243 {{ false, true }, { true, true }}, // union 244 {{ false, true }, { true, false }}, // xor 245 {{ false, true }, { false, false }}, // rev diff 246 }; 247 248 bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { 249 #if DEBUG_SHOW_TEST_NAME 250 char* debugName = DEBUG_FILENAME_STRING; 251 if (debugName && debugName[0]) { 252 SkPathOpsDebug::BumpTestName(debugName); 253 SkPathOpsDebug::ShowPath(one, two, op, debugName); 254 } 255 #endif 256 op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()]; 257 SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()] 258 ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType; 259 const SkPath* minuend = &one; 260 const SkPath* subtrahend = &two; 261 if (op == kReverseDifference_PathOp) { 262 minuend = &two; 263 subtrahend = &one; 264 op = kDifference_PathOp; 265 } 266 #if DEBUG_SORT || DEBUG_SWAP_TOP 267 SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault; 268 #endif 269 // turn path into list of segments 270 SkTArray<SkOpContour> contours; 271 // FIXME: add self-intersecting cubics' T values to segment 272 SkOpEdgeBuilder builder(*minuend, contours); 273 const int xorMask = builder.xorMask(); 274 builder.addOperand(*subtrahend); 275 if (!builder.finish()) { 276 return false; 277 } 278 result->reset(); 279 result->setFillType(fillType); 280 const int xorOpMask = builder.xorMask(); 281 SkTArray<SkOpContour*, true> contourList; 282 MakeContourList(contours, contourList, xorMask == kEvenOdd_PathOpsMask, 283 xorOpMask == kEvenOdd_PathOpsMask); 284 SkOpContour** currentPtr = contourList.begin(); 285 if (!currentPtr) { 286 return true; 287 } 288 SkOpContour** listEnd = contourList.end(); 289 // find all intersections between segments 290 do { 291 SkOpContour** nextPtr = currentPtr; 292 SkOpContour* current = *currentPtr++; 293 if (current->containsCubics()) { 294 AddSelfIntersectTs(current); 295 } 296 SkOpContour* next; 297 do { 298 next = *nextPtr++; 299 } while (AddIntersectTs(current, next) && nextPtr != listEnd); 300 } while (currentPtr != listEnd); 301 // eat through coincident edges 302 303 int total = 0; 304 int index; 305 for (index = 0; index < contourList.count(); ++index) { 306 total += contourList[index]->segments().count(); 307 } 308 if (!HandleCoincidence(&contourList, total)) { 309 return false; 310 } 311 // construct closed contours 312 SkPathWriter wrapper(*result); 313 bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper); 314 { // if some edges could not be resolved, assemble remaining fragments 315 SkPath temp; 316 temp.setFillType(fillType); 317 SkPathWriter assembled(temp); 318 Assemble(wrapper, &assembled); 319 *result = *assembled.nativePath(); 320 result->setFillType(fillType); 321 } 322 return true; 323 } 324
