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 SkSTArenaAlloc<4096> allocator; // FIXME: constant-ize, tune 150 SkOpContour contour; 151 SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour); 152 SkOpGlobalState globalState(contourList, &allocator 153 SkDEBUGPARAMS(skipAssert) SkDEBUGPARAMS(testName)); 154 SkOpCoincidence coincidence(&globalState); 155 #if DEBUG_DUMP_VERIFY 156 #ifndef SK_DEBUG 157 const char* testName = "release"; 158 #endif 159 if (SkPathOpsDebug::gDumpOp) { 160 SkPathOpsDebug::DumpSimplify(path, testName); 161 } 162 #endif 163 SkScalar scaleFactor = ScaleFactor(path); 164 SkPath scaledPath; 165 const SkPath* workingPath; 166 if (scaleFactor > SK_Scalar1) { 167 ScalePath(path, 1.f / scaleFactor, &scaledPath); 168 workingPath = &scaledPath; 169 } else { 170 workingPath = &path; 171 } 172 #if DEBUG_SORT 173 SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault; 174 #endif 175 SkOpEdgeBuilder builder(*workingPath, contourList, &globalState); 176 if (!builder.finish()) { 177 return false; 178 } 179 #if DEBUG_DUMP_SEGMENTS 180 contour.dumpSegments(); 181 #endif 182 if (!SortContourList(&contourList, false, false)) { 183 result->reset(); 184 result->setFillType(fillType); 185 return true; 186 } 187 // find all intersections between segments 188 SkOpContour* current = contourList; 189 do { 190 SkOpContour* next = current; 191 while (AddIntersectTs(current, next, &coincidence) 192 && (next = next->next())); 193 } while ((current = current->next())); 194 #if DEBUG_VALIDATE 195 globalState.setPhase(SkOpPhase::kWalking); 196 #endif 197 bool success = HandleCoincidence(contourList, &coincidence); 198 #if DEBUG_COIN 199 globalState.debugAddToGlobalCoinDicts(); 200 #endif 201 if (!success) { 202 return false; 203 } 204 #if DEBUG_DUMP_ALIGNMENT 205 contour.dumpSegments("aligned"); 206 #endif 207 // construct closed contours 208 result->reset(); 209 result->setFillType(fillType); 210 SkPathWriter wrapper(*result); 211 if (builder.xorMask() == kWinding_PathOpsMask ? !bridgeWinding(contourList, &wrapper) 212 : !bridgeXor(contourList, &wrapper)) { 213 return false; 214 } 215 wrapper.assemble(); // if some edges could not be resolved, assemble remaining 216 if (scaleFactor > 1) { 217 ScalePath(*result, scaleFactor, result); 218 } 219 return true; 220 } 221 222 bool Simplify(const SkPath& path, SkPath* result) { 223 #if DEBUG_DUMP_VERIFY 224 if (SkPathOpsDebug::gVerifyOp) { 225 if (!SimplifyDebug(path, result SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr))) { 226 SkPathOpsDebug::ReportSimplifyFail(path); 227 return false; 228 } 229 SkPathOpsDebug::VerifySimplify(path, *result); 230 return true; 231 } 232 #endif 233 return SimplifyDebug(path, result SkDEBUGPARAMS(true) SkDEBUGPARAMS(nullptr)); 234 } 235
