| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright 2012 Google Inc. | 2 * Copyright 2012 Google Inc. |
| 3 * | 3 * |
| 4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
| 5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
| 6 */ | 6 */ |
| 7 #include "SkAddIntersections.h" | 7 #include "SkAddIntersections.h" |
| 8 #include "SkOpCoincidence.h" | 8 #include "SkOpCoincidence.h" |
| 9 #include "SkOpEdgeBuilder.h" | 9 #include "SkOpEdgeBuilder.h" |
| 10 #include "SkPathOpsCommon.h" | 10 #include "SkPathOpsCommon.h" |
| 11 #include "SkPathWriter.h" | 11 #include "SkPathWriter.h" |
| 12 | 12 |
| 13 static bool bridgeWinding(SkOpContourHead* contourList, SkPathWriter* simple, bo
ol* closable) { | 13 static bool bridgeWinding(SkOpContourHead* contourList, SkPathWriter* simple) { |
| 14 bool unsortable = false; | 14 bool unsortable = false; |
| 15 do { | 15 do { |
| 16 SkOpSpan* span = FindSortableTop(contourList); | 16 SkOpSpan* span = FindSortableTop(contourList); |
| 17 if (!span) { | 17 if (!span) { |
| 18 break; | 18 break; |
| 19 } | 19 } |
| 20 SkOpSegment* current = span->segment(); | 20 SkOpSegment* current = span->segment(); |
| 21 SkOpSpanBase* start = span->next(); | 21 SkOpSpanBase* start = span->next(); |
| 22 SkOpSpanBase* end = span; | 22 SkOpSpanBase* end = span; |
| 23 SkTDArray<SkOpSpanBase*> chase; | 23 SkTDArray<SkOpSpanBase*> chase; |
| 24 do { | 24 do { |
| 25 if (current->activeWinding(start, end)) { | 25 if (current->activeWinding(start, end)) { |
| 26 do { | 26 do { |
| 27 if (!unsortable && current->done()) { | 27 if (!unsortable && current->done()) { |
| 28 break; | 28 break; |
| 29 } | 29 } |
| 30 SkASSERT(unsortable || !current->done()); | 30 SkASSERT(unsortable || !current->done()); |
| 31 SkOpSpanBase* nextStart = start; | 31 SkOpSpanBase* nextStart = start; |
| 32 SkOpSpanBase* nextEnd = end; | 32 SkOpSpanBase* nextEnd = end; |
| 33 SkOpSegment* next = current->findNextWinding(&chase, &nextSt
art, &nextEnd, | 33 SkOpSegment* next = current->findNextWinding(&chase, &nextSt
art, &nextEnd, |
| 34 &unsortable); | 34 &unsortable); |
| 35 if (!next) { | 35 if (!next) { |
| 36 if (!unsortable && simple->hasMove() | 36 if (!unsortable && simple->hasMove() |
| 37 && current->verb() != SkPath::kLine_Verb | 37 && current->verb() != SkPath::kLine_Verb |
| 38 && !simple->isClosed()) { | 38 && !simple->isClosed()) { |
| 39 // FIXME: put in the next two lines to avoid handlin
g already added | 39 // FIXME: put in the next two lines to avoid handlin
g already added |
| 40 if (start->starter(end)->checkAlreadyAdded()) { | 40 if (start->starter(end)->checkAlreadyAdded()) { |
| 41 simple->close(); | 41 simple->finishContour(); |
| 42 } else if (!current->addCurveTo(start, end, simple))
{ | 42 } else if (!current->addCurveTo(start, end, simple))
{ |
| 43 return false; | 43 return false; |
| 44 } | 44 } |
| 45 if (!simple->isClosed()) { | 45 if (!simple->isClosed()) { |
| 46 SkPathOpsDebug::ShowActiveSpans(contourList); | 46 SkPathOpsDebug::ShowActiveSpans(contourList); |
| 47 } | 47 } |
| 48 } | 48 } |
| 49 break; | 49 break; |
| 50 } | 50 } |
| 51 #if DEBUG_FLOW | 51 #if DEBUG_FLOW |
| (...skipping 10 matching lines...) Expand all Loading... |
| 62 } while (!simple->isClosed() && (!unsortable || !start->starter(
end)->done())); | 62 } while (!simple->isClosed() && (!unsortable || !start->starter(
end)->done())); |
| 63 if (current->activeWinding(start, end) && !simple->isClosed()) { | 63 if (current->activeWinding(start, end) && !simple->isClosed()) { |
| 64 SkOpSpan* spanStart = start->starter(end); | 64 SkOpSpan* spanStart = start->starter(end); |
| 65 if (!spanStart->done()) { | 65 if (!spanStart->done()) { |
| 66 if (!current->addCurveTo(start, end, simple)) { | 66 if (!current->addCurveTo(start, end, simple)) { |
| 67 return false; | 67 return false; |
| 68 } | 68 } |
| 69 current->markDone(spanStart); | 69 current->markDone(spanStart); |
| 70 } | 70 } |
| 71 } | 71 } |
| 72 simple->close(); | 72 simple->finishContour(); |
| 73 } else { | 73 } else { |
| 74 SkOpSpanBase* last = current->markAndChaseDone(start, end); | 74 SkOpSpanBase* last = current->markAndChaseDone(start, end); |
| 75 if (last && !last->chased()) { | 75 if (last && !last->chased()) { |
| 76 last->setChased(true); | 76 last->setChased(true); |
| 77 SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last)); | 77 SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last)); |
| 78 *chase.append() = last; | 78 *chase.append() = last; |
| 79 #if DEBUG_WINDING | 79 #if DEBUG_WINDING |
| 80 SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segmen
t()->debugID()); | 80 SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segmen
t()->debugID()); |
| 81 if (!last->final()) { | 81 if (!last->final()) { |
| 82 SkDebugf(" windSum=%d", last->upCast()->windSum()); | 82 SkDebugf(" windSum=%d", last->upCast()->windSum()); |
| 83 } | 83 } |
| 84 SkDebugf("\n"); | 84 SkDebugf("\n"); |
| 85 #endif | 85 #endif |
| 86 } | 86 } |
| 87 } | 87 } |
| 88 current = FindChase(&chase, &start, &end); | 88 current = FindChase(&chase, &start, &end); |
| 89 SkPathOpsDebug::ShowActiveSpans(contourList); | 89 SkPathOpsDebug::ShowActiveSpans(contourList); |
| 90 if (!current) { | 90 if (!current) { |
| 91 break; | 91 break; |
| 92 } | 92 } |
| 93 } while (true); | 93 } while (true); |
| 94 } while (true); | 94 } while (true); |
| 95 *closable = !simple->someAssemblyRequired(); | |
| 96 return true; | 95 return true; |
| 97 } | 96 } |
| 98 | 97 |
| 99 // returns true if all edges were processed | 98 // returns true if all edges were processed |
| 100 static bool bridgeXor(SkOpContourHead* contourList, SkPathWriter* simple, bool*
closable) { | 99 static bool bridgeXor(SkOpContourHead* contourList, SkPathWriter* simple) { |
| 101 SkOpSegment* current; | 100 SkOpSegment* current; |
| 102 SkOpSpanBase* start; | 101 SkOpSpanBase* start; |
| 103 SkOpSpanBase* end; | 102 SkOpSpanBase* end; |
| 104 bool unsortable = false; | 103 bool unsortable = false; |
| 105 *closable = true; | |
| 106 while ((current = FindUndone(contourList, &start, &end))) { | 104 while ((current = FindUndone(contourList, &start, &end))) { |
| 107 do { | 105 do { |
| 108 if (!unsortable && current->done()) { | 106 if (!unsortable && current->done()) { |
| 109 SkPathOpsDebug::ShowActiveSpans(contourList); | 107 SkPathOpsDebug::ShowActiveSpans(contourList); |
| 110 } | 108 } |
| 111 SkASSERT(unsortable || !current->done()); | 109 SkASSERT(unsortable || !current->done()); |
| 112 SkOpSpanBase* nextStart = start; | 110 SkOpSpanBase* nextStart = start; |
| 113 SkOpSpanBase* nextEnd = end; | 111 SkOpSpanBase* nextEnd = end; |
| 114 SkOpSegment* next = current->findNextXor(&nextStart, &nextEnd, &unso
rtable); | 112 SkOpSegment* next = current->findNextXor(&nextStart, &nextEnd, &unso
rtable); |
| 115 if (!next) { | 113 if (!next) { |
| (...skipping 23 matching lines...) Expand all Loading... |
| 139 } while (!simple->isClosed() && (!unsortable || !start->starter(end)->do
ne())); | 137 } while (!simple->isClosed() && (!unsortable || !start->starter(end)->do
ne())); |
| 140 if (!simple->isClosed()) { | 138 if (!simple->isClosed()) { |
| 141 SkASSERT(unsortable); | 139 SkASSERT(unsortable); |
| 142 SkOpSpan* spanStart = start->starter(end); | 140 SkOpSpan* spanStart = start->starter(end); |
| 143 if (!spanStart->done()) { | 141 if (!spanStart->done()) { |
| 144 if (!current->addCurveTo(start, end, simple)) { | 142 if (!current->addCurveTo(start, end, simple)) { |
| 145 return false; | 143 return false; |
| 146 } | 144 } |
| 147 current->markDone(spanStart); | 145 current->markDone(spanStart); |
| 148 } | 146 } |
| 149 *closable = false; | |
| 150 } | 147 } |
| 151 simple->close(); | 148 simple->finishContour(); |
| 152 SkPathOpsDebug::ShowActiveSpans(contourList); | 149 SkPathOpsDebug::ShowActiveSpans(contourList); |
| 153 } | 150 } |
| 154 return true; | 151 return true; |
| 155 } | 152 } |
| 156 | 153 |
| 157 // FIXME : add this as a member of SkPath | 154 // FIXME : add this as a member of SkPath |
| 158 bool SimplifyDebug(const SkPath& path, SkPath* result | 155 bool SimplifyDebug(const SkPath& path, SkPath* result |
| 159 SkDEBUGPARAMS(bool skipAssert) SkDEBUGPARAMS(const char* testName)) { | 156 SkDEBUGPARAMS(bool skipAssert) SkDEBUGPARAMS(const char* testName)) { |
| 160 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness | 157 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness |
| 161 SkPath::FillType fillType = path.isInverseFillType() ? SkPath::kInverseEvenO
dd_FillType | 158 SkPath::FillType fillType = path.isInverseFillType() ? SkPath::kInverseEvenO
dd_FillType |
| (...skipping 17 matching lines...) Expand all Loading... |
| 179 const SkPath* workingPath; | 176 const SkPath* workingPath; |
| 180 if (scaleFactor > SK_Scalar1) { | 177 if (scaleFactor > SK_Scalar1) { |
| 181 ScalePath(path, 1.f / scaleFactor, &scaledPath); | 178 ScalePath(path, 1.f / scaleFactor, &scaledPath); |
| 182 workingPath = &scaledPath; | 179 workingPath = &scaledPath; |
| 183 } else { | 180 } else { |
| 184 workingPath = &path; | 181 workingPath = &path; |
| 185 } | 182 } |
| 186 #if DEBUG_SORT | 183 #if DEBUG_SORT |
| 187 SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault; | 184 SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault; |
| 188 #endif | 185 #endif |
| 189 SkOpEdgeBuilder builder(*workingPath, &contour, &globalState); | 186 SkOpEdgeBuilder builder(*workingPath, contourList, &globalState); |
| 190 if (!builder.finish()) { | 187 if (!builder.finish()) { |
| 191 return false; | 188 return false; |
| 192 } | 189 } |
| 193 #if DEBUG_DUMP_SEGMENTS | 190 #if DEBUG_DUMP_SEGMENTS |
| 194 contour.dumpSegments(); | 191 contour.dumpSegments(); |
| 195 #endif | 192 #endif |
| 196 if (!SortContourList(&contourList, false, false)) { | 193 if (!SortContourList(&contourList, false, false)) { |
| 197 result->reset(); | 194 result->reset(); |
| 198 result->setFillType(fillType); | 195 result->setFillType(fillType); |
| 199 return true; | 196 return true; |
| (...skipping 11 matching lines...) Expand all Loading... |
| 211 if (!HandleCoincidence(contourList, &coincidence)) { | 208 if (!HandleCoincidence(contourList, &coincidence)) { |
| 212 return false; | 209 return false; |
| 213 } | 210 } |
| 214 #if DEBUG_DUMP_ALIGNMENT | 211 #if DEBUG_DUMP_ALIGNMENT |
| 215 contour.dumpSegments("aligned"); | 212 contour.dumpSegments("aligned"); |
| 216 #endif | 213 #endif |
| 217 // construct closed contours | 214 // construct closed contours |
| 218 result->reset(); | 215 result->reset(); |
| 219 result->setFillType(fillType); | 216 result->setFillType(fillType); |
| 220 SkPathWriter wrapper(*result); | 217 SkPathWriter wrapper(*result); |
| 221 bool closable SK_INIT_TO_AVOID_WARNING; | 218 if (builder.xorMask() == kWinding_PathOpsMask ? !bridgeWinding(contourList,
&wrapper) |
| 222 if (builder.xorMask() == kWinding_PathOpsMask | 219 : !bridgeXor(contourList, &wrapper)) { |
| 223 ? !bridgeWinding(contourList, &wrapper, &closable) | |
| 224 : !bridgeXor(contourList, &wrapper, &closable)) { | |
| 225 return false; | 220 return false; |
| 226 } | 221 } |
| 227 if (!closable) | 222 wrapper.assemble(); // if some edges could not be resolved, assemble remain
ing |
| 228 { // if some edges could not be resolved, assemble remaining fragments | |
| 229 SkPath temp; | |
| 230 temp.setFillType(fillType); | |
| 231 SkPathWriter assembled(temp); | |
| 232 Assemble(wrapper, &assembled); | |
| 233 *result = *assembled.nativePath(); | |
| 234 result->setFillType(fillType); | |
| 235 } | |
| 236 if (scaleFactor > 1) { | 223 if (scaleFactor > 1) { |
| 237 ScalePath(*result, scaleFactor, result); | 224 ScalePath(*result, scaleFactor, result); |
| 238 } | 225 } |
| 239 return true; | 226 return true; |
| 240 } | 227 } |
| 241 | 228 |
| 242 bool Simplify(const SkPath& path, SkPath* result) { | 229 bool Simplify(const SkPath& path, SkPath* result) { |
| 243 return SimplifyDebug(path, result SkDEBUGPARAMS(true) SkDEBUGPARAMS(nullptr
)); | 230 return SimplifyDebug(path, result SkDEBUGPARAMS(true) SkDEBUGPARAMS(nullptr
)); |
| 244 } | 231 } |
| OLD | NEW |