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 bool bridgeWinding(SkOpContourHead* contourList, SkPathWriter* simple) { 14 bool unsortable = false; 15 do { 16 SkOpSpan* span = FindSortableTop(contourList); 17 if (!span) { 18 break; 19 } 20 SkOpSegment* current = span->segment(); 21 SkOpSpanBase* start = span->next(); 22 SkOpSpanBase* end = span; 23 SkTDArray<SkOpSpanBase*> chase; 24 do { 25 if (current->activeWinding(start, end)) { 26 do { 27 if (!unsortable && current->done()) { 28 break; 29 } 30 SkASSERT(unsortable || !current->done()); 31 SkOpSpanBase* nextStart = start; 32 SkOpSpanBase* nextEnd = end; 33 SkOpSegment* next = current->findNextWinding(&chase, &nextStart, &nextEnd, 34 &unsortable); 35 if (!next) { 36 break; 37 } 38 #if DEBUG_FLOW 39 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__, 40 current->debugID(), start->pt().fX, start->pt().fY, 41 end->pt().fX, end->pt().fY); 42 #endif 43 if (!current->addCurveTo(start, end, simple)) { 44 return false; 45 } 46 current = next; 47 start = nextStart; 48 end = nextEnd; 49 } while (!simple->isClosed() && (!unsortable || !start->starter(end)->done())); 50 if (current->activeWinding(start, end) && !simple->isClosed()) { 51 SkOpSpan* spanStart = start->starter(end); 52 if (!spanStart->done()) { 53 if (!current->addCurveTo(start, end, simple)) { 54 return false; 55 } 56 current->markDone(spanStart); 57 } 58 } 59 simple->finishContour(); 60 } else { 61 SkOpSpanBase* last = current->markAndChaseDone(start, end); 62 if (last && !last->chased()) { 63 last->setChased(true); 64 SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last)); 65 *chase.append() = last; 66 #if DEBUG_WINDING 67 SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segment()->debugID()); 68 if (!last->final()) { 69 SkDebugf(" windSum=%d", last->upCast()->windSum()); 70 } 71 SkDebugf("\n"); 72 #endif 73 } 74 } 75 current = FindChase(&chase, &start, &end); 76 SkPathOpsDebug::ShowActiveSpans(contourList); 77 if (!current) { 78 break; 79 } 80 } while (true); 81 } while (true); 82 return true; 83 } 84 85 // returns true if all edges were processed 86 static bool bridgeXor(SkOpContourHead* contourList, SkPathWriter* simple) { 87 bool unsortable = false; 88 do { 89 SkOpSpan* span = FindUndone(contourList); 90 if (!span) { 91 break; 92 } 93 SkOpSegment* current = span->segment(); 94 SkOpSpanBase* start = span->next(); 95 SkOpSpanBase* end = span; 96 do { 97 if (!unsortable && current->done()) { 98 break; 99 } 100 SkASSERT(unsortable || !current->done()); 101 SkOpSpanBase* nextStart = start; 102 SkOpSpanBase* nextEnd = end; 103 SkOpSegment* next = current->findNextXor(&nextStart, &nextEnd, 104 &unsortable); 105 if (!next) { 106 break; 107 } 108 #if DEBUG_FLOW 109 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__, 110 current->debugID(), start->pt().fX, start->pt().fY, 111 end->pt().fX, end->pt().fY); 112 #endif 113 if (!current->addCurveTo(start, end, simple)) { 114 return false; 115 } 116 current = next; 117 start = nextStart; 118 end = nextEnd; 119 } while (!simple->isClosed() && (!unsortable || !start->starter(end)->done())); 120 if (!simple->isClosed()) { 121 SkOpSpan* spanStart = start->starter(end); 122 if (!spanStart->done()) { 123 if (!current->addCurveTo(start, end, simple)) { 124 return false; 125 } 126 current->markDone(spanStart); 127 } 128 } 129 simple->finishContour(); 130 SkPathOpsDebug::ShowActiveSpans(contourList); 131 } while (true); 132 return true; 133 } 134 135 // FIXME : add this as a member of SkPath 136 bool SimplifyDebug(const SkPath& path, SkPath* result 137 SkDEBUGPARAMS(bool skipAssert) SkDEBUGPARAMS(const char* testName)) { 138 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness 139 SkPath::FillType fillType = path.isInverseFillType() ? SkPath::kInverseEvenOdd_FillType 140 : SkPath::kEvenOdd_FillType; 141 if (path.isConvex()) { 142 if (result != &path) { 143 *result = path; 144 } 145 result->setFillType(fillType); 146 return true; 147 } 148 // turn path into list of segments 149 char storage[4096]; 150 SkArenaAlloc allocator(storage); // FIXME: constant-ize, tune 151 SkOpContour contour; 152 SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour); 153 SkOpGlobalState globalState(contourList, &allocator 154 SkDEBUGPARAMS(skipAssert) SkDEBUGPARAMS(testName)); 155 SkOpCoincidence coincidence(&globalState); 156 #if DEBUG_DUMP_VERIFY 157 #ifndef SK_DEBUG 158 const char* testName = "release"; 159 #endif 160 if (SkPathOpsDebug::gDumpOp) { 161 SkPathOpsDebug::DumpSimplify(path, testName); 162 } 163 #endif 164 SkScalar scaleFactor = ScaleFactor(path); 165 SkPath scaledPath; 166 const SkPath* workingPath; 167 if (scaleFactor > SK_Scalar1) { 168 ScalePath(path, 1.f / scaleFactor, &scaledPath); 169 workingPath = &scaledPath; 170 } else { 171 workingPath = &path; 172 } 173 #if DEBUG_SORT 174 SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault; 175 #endif 176 SkOpEdgeBuilder builder(*workingPath, contourList, &globalState); 177 if (!builder.finish()) { 178 return false; 179 } 180 #if DEBUG_DUMP_SEGMENTS 181 contour.dumpSegments(); 182 #endif 183 if (!SortContourList(&contourList, false, false)) { 184 result->reset(); 185 result->setFillType(fillType); 186 return true; 187 } 188 // find all intersections between segments 189 SkOpContour* current = contourList; 190 do { 191 SkOpContour* next = current; 192 while (AddIntersectTs(current, next, &coincidence) 193 && (next = next->next())); 194 } while ((current = current->next())); 195 #if DEBUG_VALIDATE 196 globalState.setPhase(SkOpPhase::kWalking); 197 #endif 198 bool success = HandleCoincidence(contourList, &coincidence); 199 #if DEBUG_COIN 200 globalState.debugAddToGlobalCoinDicts(); 201 #endif 202 if (!success) { 203 return false; 204 } 205 #if DEBUG_DUMP_ALIGNMENT 206 contour.dumpSegments("aligned"); 207 #endif 208 // construct closed contours 209 result->reset(); 210 result->setFillType(fillType); 211 SkPathWriter wrapper(*result); 212 if (builder.xorMask() == kWinding_PathOpsMask ? !bridgeWinding(contourList, &wrapper) 213 : !bridgeXor(contourList, &wrapper)) { 214 return false; 215 } 216 wrapper.assemble(); // if some edges could not be resolved, assemble remaining 217 if (scaleFactor > 1) { 218 ScalePath(*result, scaleFactor, result); 219 } 220 return true; 221 } 222 223 bool Simplify(const SkPath& path, SkPath* result) { 224 #if DEBUG_DUMP_VERIFY 225 if (SkPathOpsDebug::gVerifyOp) { 226 if (!SimplifyDebug(path, result SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr))) { 227 SkPathOpsDebug::ReportSimplifyFail(path); 228 return false; 229 } 230 SkPathOpsDebug::VerifySimplify(path, *result); 231 return true; 232 } 233 #endif 234 return SimplifyDebug(path, result SkDEBUGPARAMS(true) SkDEBUGPARAMS(nullptr)); 235 } 236
