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 SkSTArenaAlloc<4096> allocator; // FIXME: constant-ize, tune
150 SkOpContour contour;
151 SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour);
152 SkOpGlobalState globalState(contourList, &allocator
153 SkDEBUGPARAMS(skipAssert) SkDEBUGPARAMS(testName));
154 SkOpCoincidence coincidence(&globalState);
155 #if DEBUG_DUMP_VERIFY
156 #ifndef SK_DEBUG
157 const char* testName = "release";
158 #endif
159 if (SkPathOpsDebug::gDumpOp) {
160 SkPathOpsDebug::DumpSimplify(path, testName);
161 }
162 #endif
163 SkScalar scaleFactor = ScaleFactor(path);
164 SkPath scaledPath;
165 const SkPath* workingPath;
166 if (scaleFactor > SK_Scalar1) {
167 ScalePath(path, 1.f / scaleFactor, &scaledPath);
168 workingPath = &scaledPath;
169 } else {
170 workingPath = &path;
171 }
172 #if DEBUG_SORT
173 SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
174 #endif
175 SkOpEdgeBuilder builder(*workingPath, contourList, &globalState);
176 if (!builder.finish()) {
177 return false;
178 }
179 #if DEBUG_DUMP_SEGMENTS
180 contour.dumpSegments();
181 #endif
182 if (!SortContourList(&contourList, false, false)) {
183 result->reset();
184 result->setFillType(fillType);
185 return true;
186 }
187 // find all intersections between segments
188 SkOpContour* current = contourList;
189 do {
190 SkOpContour* next = current;
191 while (AddIntersectTs(current, next, &coincidence)
192 && (next = next->next()));
193 } while ((current = current->next()));
194 #if DEBUG_VALIDATE
195 globalState.setPhase(SkOpPhase::kWalking);
196 #endif
197 bool success = HandleCoincidence(contourList, &coincidence);
198 #if DEBUG_COIN
199 globalState.debugAddToGlobalCoinDicts();
200 #endif
201 if (!success) {
202 return false;
203 }
204 #if DEBUG_DUMP_ALIGNMENT
205 contour.dumpSegments("aligned");
206 #endif
207 // construct closed contours
208 result->reset();
209 result->setFillType(fillType);
210 SkPathWriter wrapper(*result);
211 if (builder.xorMask() == kWinding_PathOpsMask ? !bridgeWinding(contourList, &wrapper)
212 : !bridgeXor(contourList, &wrapper)) {
213 return false;
214 }
215 wrapper.assemble(); // if some edges could not be resolved, assemble remaining
216 if (scaleFactor > 1) {
217 ScalePath(*result, scaleFactor, result);
218 }
219 return true;
220 }
221
Simplify(const SkPath & path,SkPath * result)222 bool Simplify(const SkPath& path, SkPath* result) {
223 #if DEBUG_DUMP_VERIFY
224 if (SkPathOpsDebug::gVerifyOp) {
225 if (!SimplifyDebug(path, result SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr))) {
226 SkPathOpsDebug::ReportSimplifyFail(path);
227 return false;
228 }
229 SkPathOpsDebug::VerifySimplify(path, *result);
230 return true;
231 }
232 #endif
233 return SimplifyDebug(path, result SkDEBUGPARAMS(true) SkDEBUGPARAMS(nullptr));
234 }
235