Line data Source code
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 :
13 0 : static bool bridgeWinding(SkOpContourHead* contourList, SkPathWriter* simple) {
14 0 : bool unsortable = false;
15 : do {
16 0 : SkOpSpan* span = FindSortableTop(contourList);
17 0 : if (!span) {
18 0 : break;
19 : }
20 0 : SkOpSegment* current = span->segment();
21 0 : SkOpSpanBase* start = span->next();
22 0 : SkOpSpanBase* end = span;
23 0 : SkTDArray<SkOpSpanBase*> chase;
24 : do {
25 0 : if (current->activeWinding(start, end)) {
26 0 : do {
27 0 : if (!unsortable && current->done()) {
28 0 : break;
29 : }
30 0 : SkASSERT(unsortable || !current->done());
31 0 : SkOpSpanBase* nextStart = start;
32 0 : SkOpSpanBase* nextEnd = end;
33 : SkOpSegment* next = current->findNextWinding(&chase, &nextStart, &nextEnd,
34 0 : &unsortable);
35 0 : if (!next) {
36 0 : 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 0 : if (!current->addCurveTo(start, end, simple)) {
44 0 : return false;
45 : }
46 0 : current = next;
47 0 : start = nextStart;
48 0 : end = nextEnd;
49 0 : } while (!simple->isClosed() && (!unsortable || !start->starter(end)->done()));
50 0 : if (current->activeWinding(start, end) && !simple->isClosed()) {
51 0 : SkOpSpan* spanStart = start->starter(end);
52 0 : if (!spanStart->done()) {
53 0 : if (!current->addCurveTo(start, end, simple)) {
54 0 : return false;
55 : }
56 0 : current->markDone(spanStart);
57 : }
58 : }
59 0 : simple->finishContour();
60 : } else {
61 0 : SkOpSpanBase* last = current->markAndChaseDone(start, end);
62 0 : if (last && !last->chased()) {
63 0 : last->setChased(true);
64 0 : SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last));
65 0 : *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 0 : current = FindChase(&chase, &start, &end);
76 0 : SkPathOpsDebug::ShowActiveSpans(contourList);
77 0 : if (!current) {
78 0 : break;
79 0 : }
80 0 : } while (true);
81 : } while (true);
82 0 : return true;
83 : }
84 :
85 : // returns true if all edges were processed
86 0 : static bool bridgeXor(SkOpContourHead* contourList, SkPathWriter* simple) {
87 0 : bool unsortable = false;
88 : do {
89 0 : SkOpSpan* span = FindUndone(contourList);
90 0 : if (!span) {
91 0 : break;
92 : }
93 0 : SkOpSegment* current = span->segment();
94 0 : SkOpSpanBase* start = span->next();
95 0 : SkOpSpanBase* end = span;
96 0 : do {
97 0 : if (!unsortable && current->done()) {
98 0 : break;
99 : }
100 0 : SkASSERT(unsortable || !current->done());
101 0 : SkOpSpanBase* nextStart = start;
102 0 : SkOpSpanBase* nextEnd = end;
103 : SkOpSegment* next = current->findNextXor(&nextStart, &nextEnd,
104 0 : &unsortable);
105 0 : if (!next) {
106 0 : 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 0 : if (!current->addCurveTo(start, end, simple)) {
114 0 : return false;
115 : }
116 0 : current = next;
117 0 : start = nextStart;
118 0 : end = nextEnd;
119 0 : } while (!simple->isClosed() && (!unsortable || !start->starter(end)->done()));
120 0 : if (!simple->isClosed()) {
121 0 : SkOpSpan* spanStart = start->starter(end);
122 0 : if (!spanStart->done()) {
123 0 : if (!current->addCurveTo(start, end, simple)) {
124 0 : return false;
125 : }
126 0 : current->markDone(spanStart);
127 : }
128 : }
129 0 : simple->finishContour();
130 0 : SkPathOpsDebug::ShowActiveSpans(contourList);
131 : } while (true);
132 0 : return true;
133 : }
134 :
135 : // FIXME : add this as a member of SkPath
136 0 : 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 0 : SkPath::FillType fillType = path.isInverseFillType() ? SkPath::kInverseEvenOdd_FillType
140 0 : : SkPath::kEvenOdd_FillType;
141 0 : if (path.isConvex()) {
142 0 : if (result != &path) {
143 0 : *result = path;
144 : }
145 0 : result->setFillType(fillType);
146 0 : return true;
147 : }
148 : // turn path into list of segments
149 : char storage[4096];
150 0 : SkArenaAlloc allocator(storage); // FIXME: constant-ize, tune
151 0 : SkOpContour contour;
152 0 : SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour);
153 : SkOpGlobalState globalState(contourList, &allocator
154 0 : SkDEBUGPARAMS(skipAssert) SkDEBUGPARAMS(testName));
155 0 : 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 0 : SkScalar scaleFactor = ScaleFactor(path);
165 0 : SkPath scaledPath;
166 : const SkPath* workingPath;
167 0 : if (scaleFactor > SK_Scalar1) {
168 0 : ScalePath(path, 1.f / scaleFactor, &scaledPath);
169 0 : workingPath = &scaledPath;
170 : } else {
171 0 : workingPath = &path;
172 : }
173 : #if DEBUG_SORT
174 : SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
175 : #endif
176 0 : SkOpEdgeBuilder builder(*workingPath, contourList, &globalState);
177 0 : if (!builder.finish()) {
178 0 : return false;
179 : }
180 : #if DEBUG_DUMP_SEGMENTS
181 : contour.dumpSegments();
182 : #endif
183 0 : if (!SortContourList(&contourList, false, false)) {
184 0 : result->reset();
185 0 : result->setFillType(fillType);
186 0 : return true;
187 : }
188 : // find all intersections between segments
189 0 : SkOpContour* current = contourList;
190 0 : do {
191 0 : SkOpContour* next = current;
192 0 : while (AddIntersectTs(current, next, &coincidence)
193 0 : && (next = next->next()));
194 : } while ((current = current->next()));
195 : #if DEBUG_VALIDATE
196 : globalState.setPhase(SkOpPhase::kWalking);
197 : #endif
198 0 : bool success = HandleCoincidence(contourList, &coincidence);
199 : #if DEBUG_COIN
200 : globalState.debugAddToGlobalCoinDicts();
201 : #endif
202 0 : if (!success) {
203 0 : return false;
204 : }
205 : #if DEBUG_DUMP_ALIGNMENT
206 : contour.dumpSegments("aligned");
207 : #endif
208 : // construct closed contours
209 0 : result->reset();
210 0 : result->setFillType(fillType);
211 0 : SkPathWriter wrapper(*result);
212 0 : if (builder.xorMask() == kWinding_PathOpsMask ? !bridgeWinding(contourList, &wrapper)
213 0 : : !bridgeXor(contourList, &wrapper)) {
214 0 : return false;
215 : }
216 0 : wrapper.assemble(); // if some edges could not be resolved, assemble remaining
217 0 : if (scaleFactor > 1) {
218 0 : ScalePath(*result, scaleFactor, result);
219 : }
220 0 : return true;
221 : }
222 :
223 0 : 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 0 : return SimplifyDebug(path, result SkDEBUGPARAMS(true) SkDEBUGPARAMS(nullptr));
235 : }
|
