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 |