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