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 "include/core/SkPath.h"
8 #include "include/core/SkPathTypes.h"
9 #include "include/core/SkTypes.h"
10 #include "include/pathops/SkPathOps.h"
11 #include "include/private/base/SkPoint_impl.h"
12 #include "include/private/base/SkTDArray.h"
13 #include "src/base/SkArenaAlloc.h"
14 #include "src/pathops/SkAddIntersections.h"
15 #include "src/pathops/SkOpCoincidence.h"
16 #include "src/pathops/SkOpContour.h"
17 #include "src/pathops/SkOpEdgeBuilder.h"
18 #include "src/pathops/SkOpSegment.h"
19 #include "src/pathops/SkOpSpan.h"
20 #include "src/pathops/SkPathOpsCommon.h"
21 #include "src/pathops/SkPathOpsTypes.h"
22 #include "src/pathops/SkPathWriter.h"
23
bridgeWinding(SkOpContourHead * contourList,SkPathWriter * writer)24 static bool bridgeWinding(SkOpContourHead* contourList, SkPathWriter* writer) {
25 bool unsortable = false;
26 do {
27 SkOpSpan* span = FindSortableTop(contourList);
28 if (!span) {
29 break;
30 }
31 SkOpSegment* current = span->segment();
32 SkOpSpanBase* start = span->next();
33 SkOpSpanBase* end = span;
34 SkTDArray<SkOpSpanBase*> chase;
35 do {
36 if (current->activeWinding(start, end)) {
37 do {
38 if (!unsortable && current->done()) {
39 break;
40 }
41 SkASSERT(unsortable || !current->done());
42 SkOpSpanBase* nextStart = start;
43 SkOpSpanBase* nextEnd = end;
44 SkOpSegment* next = current->findNextWinding(&chase, &nextStart, &nextEnd,
45 &unsortable);
46 if (!next) {
47 break;
48 }
49 #if DEBUG_FLOW
50 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,
52 end->pt().fX, end->pt().fY);
53 #endif
54 if (!current->addCurveTo(start, end, writer)) {
55 return false;
56 }
57 current = next;
58 start = nextStart;
59 end = nextEnd;
60 } while (!writer->isClosed() && (!unsortable || !start->starter(end)->done()));
61 if (current->activeWinding(start, end) && !writer->isClosed()) {
62 SkOpSpan* spanStart = start->starter(end);
63 if (!spanStart->done()) {
64 if (!current->addCurveTo(start, end, writer)) {
65 return false;
66 }
67 current->markDone(spanStart);
68 }
69 }
70 writer->finishContour();
71 } else {
72 SkOpSpanBase* last;
73 if (!current->markAndChaseDone(start, end, &last)) {
74 return false;
75 }
76 if (last && !last->chased()) {
77 last->setChased(true);
78 SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last));
79 *chase.append() = last;
80 #if DEBUG_WINDING
81 SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segment()->debugID());
82 if (!last->final()) {
83 SkDebugf(" windSum=%d", last->upCast()->windSum());
84 }
85 SkDebugf("\n");
86 #endif
87 }
88 }
89 current = FindChase(&chase, &start, &end);
90 SkPathOpsDebug::ShowActiveSpans(contourList);
91 if (!current) {
92 break;
93 }
94 } while (true);
95 } while (true);
96 return true;
97 }
98
99 // returns true if all edges were processed
bridgeXor(SkOpContourHead * contourList,SkPathWriter * writer)100 static bool bridgeXor(SkOpContourHead* contourList, SkPathWriter* writer) {
101 bool unsortable = false;
102 int safetyNet = 1000000;
103 do {
104 SkOpSpan* span = FindUndone(contourList);
105 if (!span) {
106 break;
107 }
108 SkOpSegment* current = span->segment();
109 SkOpSpanBase* start = span->next();
110 SkOpSpanBase* end = span;
111 do {
112 if (--safetyNet < 0) {
113 return false;
114 }
115 if (!unsortable && current->done()) {
116 break;
117 }
118 SkASSERT(unsortable || !current->done());
119 SkOpSpanBase* nextStart = start;
120 SkOpSpanBase* nextEnd = end;
121 SkOpSegment* next = current->findNextXor(&nextStart, &nextEnd,
122 &unsortable);
123 if (!next) {
124 break;
125 }
126 #if DEBUG_FLOW
127 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,
129 end->pt().fX, end->pt().fY);
130 #endif
131 if (!current->addCurveTo(start, end, writer)) {
132 return false;
133 }
134 current = next;
135 start = nextStart;
136 end = nextEnd;
137 } while (!writer->isClosed() && (!unsortable || !start->starter(end)->done()));
138 if (!writer->isClosed()) {
139 SkOpSpan* spanStart = start->starter(end);
140 if (!spanStart->done()) {
141 return false;
142 }
143 }
144 writer->finishContour();
145 SkPathOpsDebug::ShowActiveSpans(contourList);
146 } while (true);
147 return true;
148 }
149
path_is_trivial(const SkPath & path)150 static bool path_is_trivial(const SkPath& path) {
151 SkPath::Iter iter(path, true);
152
153 SkPath::Verb verb;
154 SkPoint points[4];
155
156 class Trivializer {
157 SkPoint prevPt{0,0};
158 SkVector prevVec{0,0};
159 public:
160 void moveTo(const SkPoint& currPt) {
161 prevPt = currPt;
162 prevVec = {0, 0};
163 }
164 bool addTrivialContourPoint(const SkPoint& currPt) {
165 if (currPt == prevPt) {
166 return true;
167 }
168 // There are more numericaly stable ways of determining if many points are co-linear.
169 // However, this mirrors SkPath's Convexicator for consistency.
170 SkVector currVec = currPt - prevPt;
171 if (SkPoint::CrossProduct(prevVec, currVec) != 0) {
172 return false;
173 }
174 prevVec = currVec;
175 prevPt = currPt;
176 return true;
177 }
178 } triv;
179
180 while ((verb = iter.next(points)) != SkPath::kDone_Verb) {
181 switch (verb) {
182 case SkPath::kMove_Verb:
183 triv.moveTo(points[0]);
184 break;
185 case SkPath::kCubic_Verb:
186 if (!triv.addTrivialContourPoint(points[3])) { return false; }
187 [[fallthrough]];
188 case SkPath::kConic_Verb:
189 case SkPath::kQuad_Verb:
190 if (!triv.addTrivialContourPoint(points[2])) { return false; }
191 [[fallthrough]];
192 case SkPath::kLine_Verb:
193 if (!triv.addTrivialContourPoint(points[1])) { return false; }
194 if (!triv.addTrivialContourPoint(points[0])) { return false; }
195 break;
196 case SkPath::kClose_Verb:
197 case SkPath::kDone_Verb:
198 break;
199 }
200 }
201 return true;
202 }
203
204 // FIXME : add this as a member of SkPath
SimplifyDebug(const SkPath & path,SkPath * result SkDEBUGPARAMS (bool skipAssert)SkDEBUGPARAMS (const char * testName))205 bool SimplifyDebug(const SkPath& path, SkPath* result
206 SkDEBUGPARAMS(bool skipAssert) SkDEBUGPARAMS(const char* testName)) {
207 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
208 SkPathFillType fillType = path.isInverseFillType() ? SkPathFillType::kInverseEvenOdd
209 : SkPathFillType::kEvenOdd;
210
211 if (path.isConvex()) {
212 // If the path is trivially convex, simplify to empty.
213 if (path_is_trivial(path)) {
214 result->reset();
215 } else if (result != &path) {
216 *result = path;
217 }
218 result->setFillType(fillType);
219 return true;
220 }
221 // turn path into list of segments
222 SkSTArenaAlloc<4096> allocator; // FIXME: constant-ize, tune
223 SkOpContour contour;
224 SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour);
225 SkOpGlobalState globalState(contourList, &allocator
226 SkDEBUGPARAMS(skipAssert) SkDEBUGPARAMS(testName));
227 SkOpCoincidence coincidence(&globalState);
228 #if DEBUG_DUMP_VERIFY
229 #ifndef SK_DEBUG
230 const char* testName = "release";
231 #endif
232 if (SkPathOpsDebug::gDumpOp) {
233 DumpSimplify(path, testName);
234 }
235 #endif
236 #if DEBUG_SORT
237 SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
238 #endif
239 SkOpEdgeBuilder builder(path, contourList, &globalState);
240 if (!builder.finish()) {
241 return false;
242 }
243 #if DEBUG_DUMP_SEGMENTS
244 contour.dumpSegments();
245 #endif
246 if (!SortContourList(&contourList, false, false)) {
247 result->reset();
248 result->setFillType(fillType);
249 return true;
250 }
251 // find all intersections between segments
252 SkOpContour* current = contourList;
253 do {
254 SkOpContour* next = current;
255 while (AddIntersectTs(current, next, &coincidence)
256 && (next = next->next()));
257 } while ((current = current->next()));
258 #if DEBUG_VALIDATE
259 globalState.setPhase(SkOpPhase::kWalking);
260 #endif
261 bool success = HandleCoincidence(contourList, &coincidence);
262 #if DEBUG_COIN
263 globalState.debugAddToGlobalCoinDicts();
264 #endif
265 if (!success) {
266 return false;
267 }
268 #if DEBUG_DUMP_ALIGNMENT
269 contour.dumpSegments("aligned");
270 #endif
271 // construct closed contours
272 result->reset();
273 result->setFillType(fillType);
274 SkPathWriter wrapper(*result);
275 if (builder.xorMask() == kWinding_PathOpsMask ? !bridgeWinding(contourList, &wrapper)
276 : !bridgeXor(contourList, &wrapper)) {
277 return false;
278 }
279 wrapper.assemble(); // if some edges could not be resolved, assemble remaining
280 return true;
281 }
282
Simplify(const SkPath & path,SkPath * result)283 bool Simplify(const SkPath& path, SkPath* result) {
284 #if DEBUG_DUMP_VERIFY
285 if (SkPathOpsDebug::gVerifyOp) {
286 if (!SimplifyDebug(path, result SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr))) {
287 ReportSimplifyFail(path);
288 return false;
289 }
290 VerifySimplify(path, *result);
291 return true;
292 }
293 #endif
294 return SimplifyDebug(path, result SkDEBUGPARAMS(true) SkDEBUGPARAMS(nullptr));
295 }
296