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, | 13 static bool bridgeWinding(SkOpContourHead* contourList, SkPathWriter* simple, |
14 SkChunkAlloc* allocator) { | 14 SkChunkAlloc* allocator, bool* closable) { |
15 bool unsortable = false; | 15 bool unsortable = false; |
16 do { | 16 do { |
17 SkOpSpan* span = FindSortableTop(contourList); | 17 SkOpSpan* span = FindSortableTop(contourList); |
18 if (!span) { | 18 if (!span) { |
19 break; | 19 break; |
20 } | 20 } |
21 SkOpSegment* current = span->segment(); | 21 SkOpSegment* current = span->segment(); |
22 SkOpSpanBase* start = span->next(); | 22 SkOpSpanBase* start = span->next(); |
23 SkOpSpanBase* end = span; | 23 SkOpSpanBase* end = span; |
24 SkTDArray<SkOpSpanBase*> chase; | 24 SkTDArray<SkOpSpanBase*> chase; |
25 do { | 25 do { |
26 if (current->activeWinding(start, end)) { | 26 if (current->activeWinding(start, end)) { |
27 do { | 27 do { |
28 if (!unsortable && current->done()) { | 28 if (!unsortable && current->done()) { |
29 break; | 29 break; |
30 } | 30 } |
31 SkASSERT(unsortable || !current->done()); | 31 SkASSERT(unsortable || !current->done()); |
32 SkOpSpanBase* nextStart = start; | 32 SkOpSpanBase* nextStart = start; |
33 SkOpSpanBase* nextEnd = end; | 33 SkOpSpanBase* nextEnd = end; |
34 SkOpSegment* next = current->findNextWinding(&chase, &nextSt
art, &nextEnd, | 34 SkOpSegment* next = current->findNextWinding(&chase, &nextSt
art, &nextEnd, |
35 &unsortable); | 35 &unsortable); |
36 if (!next) { | 36 if (!next) { |
37 if (!unsortable && simple->hasMove() | 37 if (!unsortable && simple->hasMove() |
38 && current->verb() != SkPath::kLine_Verb | 38 && current->verb() != SkPath::kLine_Verb |
39 && !simple->isClosed()) { | 39 && !simple->isClosed()) { |
40 current->addCurveTo(start, end, simple, true); | 40 if (!current->addCurveTo(start, end, simple)) { |
| 41 return false; |
| 42 } |
41 #if DEBUG_ACTIVE_SPANS | 43 #if DEBUG_ACTIVE_SPANS |
42 if (!simple->isClosed()) { | 44 if (!simple->isClosed()) { |
43 DebugShowActiveSpans(contourList); | 45 DebugShowActiveSpans(contourList); |
44 } | 46 } |
45 #endif | 47 #endif |
46 } | 48 } |
47 break; | 49 break; |
48 } | 50 } |
49 #if DEBUG_FLOW | 51 #if DEBUG_FLOW |
50 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", _
_FUNCTION__, | 52 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", _
_FUNCTION__, |
51 current->debugID(), start->pt().fX, start->pt().fY, | 53 current->debugID(), start->pt().fX, start->pt().fY, |
52 end->pt().fX, end->pt().fY); | 54 end->pt().fX, end->pt().fY); |
53 #endif | 55 #endif |
54 current->addCurveTo(start, end, simple, true); | 56 if (!current->addCurveTo(start, end, simple)) { |
| 57 return false; |
| 58 } |
55 current = next; | 59 current = next; |
56 start = nextStart; | 60 start = nextStart; |
57 end = nextEnd; | 61 end = nextEnd; |
58 } while (!simple->isClosed() && (!unsortable || !start->starter(
end)->done())); | 62 } while (!simple->isClosed() && (!unsortable || !start->starter(
end)->done())); |
59 if (current->activeWinding(start, end) && !simple->isClosed()) { | 63 if (current->activeWinding(start, end) && !simple->isClosed()) { |
60 SkOpSpan* spanStart = start->starter(end); | 64 SkOpSpan* spanStart = start->starter(end); |
61 if (!spanStart->done()) { | 65 if (!spanStart->done()) { |
62 current->addCurveTo(start, end, simple, true); | 66 if (!current->addCurveTo(start, end, simple)) { |
| 67 return false; |
| 68 } |
63 current->markDone(spanStart); | 69 current->markDone(spanStart); |
64 } | 70 } |
65 } | 71 } |
66 simple->close(); | 72 simple->close(); |
67 } else { | 73 } else { |
68 SkOpSpanBase* last = current->markAndChaseDone(start, end); | 74 SkOpSpanBase* last = current->markAndChaseDone(start, end); |
69 if (last && !last->chased()) { | 75 if (last && !last->chased()) { |
70 last->setChased(true); | 76 last->setChased(true); |
71 SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last)); | 77 SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last)); |
72 *chase.append() = last; | 78 *chase.append() = last; |
73 #if DEBUG_WINDING | 79 #if DEBUG_WINDING |
74 SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segmen
t()->debugID()); | 80 SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segmen
t()->debugID()); |
75 if (!last->final()) { | 81 if (!last->final()) { |
76 SkDebugf(" windSum=%d", last->upCast()->windSum()); | 82 SkDebugf(" windSum=%d", last->upCast()->windSum()); |
77 } | 83 } |
78 SkDebugf("\n"); | 84 SkDebugf("\n"); |
79 #endif | 85 #endif |
80 } | 86 } |
81 } | 87 } |
82 current = FindChase(&chase, &start, &end); | 88 current = FindChase(&chase, &start, &end); |
83 #if DEBUG_ACTIVE_SPANS | 89 #if DEBUG_ACTIVE_SPANS |
84 DebugShowActiveSpans(contourList); | 90 DebugShowActiveSpans(contourList); |
85 #endif | 91 #endif |
86 if (!current) { | 92 if (!current) { |
87 break; | 93 break; |
88 } | 94 } |
89 } while (true); | 95 } while (true); |
90 } while (true); | 96 } while (true); |
91 return simple->someAssemblyRequired(); | 97 *closable = !simple->someAssemblyRequired(); |
| 98 return true; |
92 } | 99 } |
93 | 100 |
94 // returns true if all edges were processed | 101 // returns true if all edges were processed |
95 static bool bridgeXor(SkOpContourHead* contourList, SkPathWriter* simple, | 102 static bool bridgeXor(SkOpContourHead* contourList, SkPathWriter* simple, |
96 SkChunkAlloc* allocator) { | 103 SkChunkAlloc* allocator, bool* closable) { |
97 SkOpSegment* current; | 104 SkOpSegment* current; |
98 SkOpSpanBase* start; | 105 SkOpSpanBase* start; |
99 SkOpSpanBase* end; | 106 SkOpSpanBase* end; |
100 bool unsortable = false; | 107 bool unsortable = false; |
101 bool closable = true; | 108 *closable = true; |
102 while ((current = FindUndone(contourList, &start, &end))) { | 109 while ((current = FindUndone(contourList, &start, &end))) { |
103 do { | 110 do { |
104 #if DEBUG_ACTIVE_SPANS | 111 #if DEBUG_ACTIVE_SPANS |
105 if (!unsortable && current->done()) { | 112 if (!unsortable && current->done()) { |
106 DebugShowActiveSpans(contourList); | 113 DebugShowActiveSpans(contourList); |
107 } | 114 } |
108 #endif | 115 #endif |
109 SkASSERT(unsortable || !current->done()); | 116 SkASSERT(unsortable || !current->done()); |
110 SkOpSpanBase* nextStart = start; | 117 SkOpSpanBase* nextStart = start; |
111 SkOpSpanBase* nextEnd = end; | 118 SkOpSpanBase* nextEnd = end; |
112 SkOpSegment* next = current->findNextXor(&nextStart, &nextEnd, &unso
rtable); | 119 SkOpSegment* next = current->findNextXor(&nextStart, &nextEnd, &unso
rtable); |
113 if (!next) { | 120 if (!next) { |
114 if (!unsortable && simple->hasMove() | 121 if (!unsortable && simple->hasMove() |
115 && current->verb() != SkPath::kLine_Verb | 122 && current->verb() != SkPath::kLine_Verb |
116 && !simple->isClosed()) { | 123 && !simple->isClosed()) { |
117 current->addCurveTo(start, end, simple, true); | 124 if (!current->addCurveTo(start, end, simple)) { |
| 125 return false; |
| 126 } |
118 #if DEBUG_ACTIVE_SPANS | 127 #if DEBUG_ACTIVE_SPANS |
119 if (!simple->isClosed()) { | 128 if (!simple->isClosed()) { |
120 DebugShowActiveSpans(contourList); | 129 DebugShowActiveSpans(contourList); |
121 } | 130 } |
122 #endif | 131 #endif |
123 } | 132 } |
124 break; | 133 break; |
125 } | 134 } |
126 #if DEBUG_FLOW | 135 #if DEBUG_FLOW |
127 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", _
_FUNCTION__, | 136 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", _
_FUNCTION__, |
128 current->debugID(), start->pt().fX, start->pt().fY, | 137 current->debugID(), start->pt().fX, start->pt().fY, |
129 end->pt().fX, end->pt().fY); | 138 end->pt().fX, end->pt().fY); |
130 #endif | 139 #endif |
131 current->addCurveTo(start, end, simple, true); | 140 if (!current->addCurveTo(start, end, simple)) { |
| 141 return false; |
| 142 } |
132 current = next; | 143 current = next; |
133 start = nextStart; | 144 start = nextStart; |
134 end = nextEnd; | 145 end = nextEnd; |
135 } while (!simple->isClosed() && (!unsortable || !start->starter(end)->do
ne())); | 146 } while (!simple->isClosed() && (!unsortable || !start->starter(end)->do
ne())); |
136 if (!simple->isClosed()) { | 147 if (!simple->isClosed()) { |
137 SkASSERT(unsortable); | 148 SkASSERT(unsortable); |
138 SkOpSpan* spanStart = start->starter(end); | 149 SkOpSpan* spanStart = start->starter(end); |
139 if (!spanStart->done()) { | 150 if (!spanStart->done()) { |
140 current->addCurveTo(start, end, simple, true); | 151 if (!current->addCurveTo(start, end, simple)) { |
| 152 return false; |
| 153 } |
141 current->markDone(spanStart); | 154 current->markDone(spanStart); |
142 } | 155 } |
143 closable = false; | 156 *closable = false; |
144 } | 157 } |
145 simple->close(); | 158 simple->close(); |
146 #if DEBUG_ACTIVE_SPANS | 159 #if DEBUG_ACTIVE_SPANS |
147 DebugShowActiveSpans(contourList); | 160 DebugShowActiveSpans(contourList); |
148 #endif | 161 #endif |
149 } | 162 } |
150 return closable; | 163 return true; |
151 } | 164 } |
152 | 165 |
153 // FIXME : add this as a member of SkPath | 166 // FIXME : add this as a member of SkPath |
154 bool Simplify(const SkPath& path, SkPath* result) { | 167 bool Simplify(const SkPath& path, SkPath* result) { |
155 SkChunkAlloc allocator(4096); // FIXME: constant-ize, tune | 168 SkChunkAlloc allocator(4096); // FIXME: constant-ize, tune |
156 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness | 169 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness |
157 SkPath::FillType fillType = path.isInverseFillType() ? SkPath::kInverseEvenO
dd_FillType | 170 SkPath::FillType fillType = path.isInverseFillType() ? SkPath::kInverseEvenO
dd_FillType |
158 : SkPath::kEvenOdd_FillType; | 171 : SkPath::kEvenOdd_FillType; |
159 if (path.isConvex()) { | 172 if (path.isConvex()) { |
160 if (result != &path) { | 173 if (result != &path) { |
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
196 if (!HandleCoincidence(contourList, &coincidence, &allocator)) { | 209 if (!HandleCoincidence(contourList, &coincidence, &allocator)) { |
197 return false; | 210 return false; |
198 } | 211 } |
199 #if DEBUG_DUMP_ALIGNMENT | 212 #if DEBUG_DUMP_ALIGNMENT |
200 contour.dumpSegments("aligned"); | 213 contour.dumpSegments("aligned"); |
201 #endif | 214 #endif |
202 // construct closed contours | 215 // construct closed contours |
203 result->reset(); | 216 result->reset(); |
204 result->setFillType(fillType); | 217 result->setFillType(fillType); |
205 SkPathWriter wrapper(*result); | 218 SkPathWriter wrapper(*result); |
206 if (builder.xorMask() == kWinding_PathOpsMask ? bridgeWinding(contourList, &
wrapper, &allocator) | 219 bool closable; |
207 : !bridgeXor(contourList, &wrapper, &allocator)) | 220 if (builder.xorMask() == kWinding_PathOpsMask |
| 221 ? !bridgeWinding(contourList, &wrapper, &allocator, &closable) |
| 222 : !bridgeXor(contourList, &wrapper, &allocator, &closable)) { |
| 223 return false; |
| 224 } |
| 225 if (!closable) |
208 { // if some edges could not be resolved, assemble remaining fragments | 226 { // if some edges could not be resolved, assemble remaining fragments |
209 SkPath temp; | 227 SkPath temp; |
210 temp.setFillType(fillType); | 228 temp.setFillType(fillType); |
211 SkPathWriter assembled(temp); | 229 SkPathWriter assembled(temp); |
212 Assemble(wrapper, &assembled); | 230 Assemble(wrapper, &assembled); |
213 *result = *assembled.nativePath(); | 231 *result = *assembled.nativePath(); |
214 result->setFillType(fillType); | 232 result->setFillType(fillType); |
215 } | 233 } |
216 return true; | 234 return true; |
217 } | 235 } |
218 | 236 |
OLD | NEW |