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