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