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