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