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
8#include "include/private/SkMacros.h"
9#include "src/core/SkTSort.h"
10#include "src/pathops/SkAddIntersections.h"
11#include "src/pathops/SkOpCoincidence.h"
12#include "src/pathops/SkOpEdgeBuilder.h"
13#include "src/pathops/SkPathOpsCommon.h"
14#include "src/pathops/SkPathWriter.h"
15
16const SkOpAngle* AngleWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* windingPtr,
17 bool* sortablePtr) {
18 // find first angle, initialize winding to computed fWindSum
19 SkOpSegment* segment = start->segment();
20 const SkOpAngle* angle = segment->spanToAngle(start, end);
21 if (!angle) {
22 *windingPtr = SK_MinS32;
23 return nullptr;
24 }
25 bool computeWinding = false;
26 const SkOpAngle* firstAngle = angle;
27 bool loop = false;
28 bool unorderable = false;
29 int winding = SK_MinS32;
30 do {
31 angle = angle->next();
32 if (!angle) {
33 return nullptr;
34 }
35 unorderable |= angle->unorderable();
36 if ((computeWinding = unorderable || (angle == firstAngle && loop))) {
37 break; // if we get here, there's no winding, loop is unorderable
38 }
39 loop |= angle == firstAngle;
40 segment = angle->segment();
41 winding = segment->windSum(angle);
42 } while (winding == SK_MinS32);
43 // if the angle loop contains an unorderable span, the angle order may be useless
44 // directly compute the winding in this case for each span
45 if (computeWinding) {
46 firstAngle = angle;
47 winding = SK_MinS32;
48 do {
49 SkOpSpanBase* startSpan = angle->start();
50 SkOpSpanBase* endSpan = angle->end();
51 SkOpSpan* lesser = startSpan->starter(endSpan);
52 int testWinding = lesser->windSum();
53 if (testWinding == SK_MinS32) {
54 testWinding = lesser->computeWindSum();
55 }
56 if (testWinding != SK_MinS32) {
57 segment = angle->segment();
58 winding = testWinding;
59 }
60 angle = angle->next();
61 } while (angle != firstAngle);
62 }
63 *sortablePtr = !unorderable;
64 *windingPtr = winding;
65 return angle;
66}
67
68SkOpSpan* FindUndone(SkOpContourHead* contourHead) {
69 SkOpContour* contour = contourHead;
70 do {
71 if (contour->done()) {
72 continue;
73 }
74 SkOpSpan* result = contour->undoneSpan();
75 if (result) {
76 return result;
77 }
78 } while ((contour = contour->next()));
79 return nullptr;
80}
81
82SkOpSegment* FindChase(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** startPtr,
83 SkOpSpanBase** endPtr) {
84 while (chase->count()) {
85 SkOpSpanBase* span;
86 chase->pop(&span);
87 SkOpSegment* segment = span->segment();
88 *startPtr = span->ptT()->next()->span();
89 bool done = true;
90 *endPtr = nullptr;
91 if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done)) {
92 *startPtr = last->start();
93 *endPtr = last->end();
94 #if TRY_ROTATE
95 *chase->insert(0) = span;
96 #else
97 *chase->append() = span;
98 #endif
99 return last->segment();
100 }
101 if (done) {
102 continue;
103 }
104 // find first angle, initialize winding to computed wind sum
105 int winding;
106 bool sortable;
107 const SkOpAngle* angle = AngleWinding(*startPtr, *endPtr, &winding, &sortable);
108 if (!angle) {
109 return nullptr;
110 }
111 if (winding == SK_MinS32) {
112 continue;
113 }
114 int sumWinding SK_INIT_TO_AVOID_WARNING;
115 if (sortable) {
116 segment = angle->segment();
117 sumWinding = segment->updateWindingReverse(angle);
118 }
119 SkOpSegment* first = nullptr;
120 const SkOpAngle* firstAngle = angle;
121 while ((angle = angle->next()) != firstAngle) {
122 segment = angle->segment();
123 SkOpSpanBase* start = angle->start();
124 SkOpSpanBase* end = angle->end();
125 int maxWinding SK_INIT_TO_AVOID_WARNING;
126 if (sortable) {
127 segment->setUpWinding(start, end, &maxWinding, &sumWinding);
128 }
129 if (!segment->done(angle)) {
130 if (!first && (sortable || start->starter(end)->windSum() != SK_MinS32)) {
131 first = segment;
132 *startPtr = start;
133 *endPtr = end;
134 }
135 // OPTIMIZATION: should this also add to the chase?
136 if (sortable) {
137 // TODO: add error handling
138 SkAssertResult(segment->markAngle(maxWinding, sumWinding, angle, nullptr));
139 }
140 }
141 }
142 if (first) {
143 #if TRY_ROTATE
144 *chase->insert(0) = span;
145 #else
146 *chase->append() = span;
147 #endif
148 return first;
149 }
150 }
151 return nullptr;
152}
153
154bool SortContourList(SkOpContourHead** contourList, bool evenOdd, bool oppEvenOdd) {
155 SkTDArray<SkOpContour* > list;
156 SkOpContour* contour = *contourList;
157 do {
158 if (contour->count()) {
159 contour->setOppXor(contour->operand() ? evenOdd : oppEvenOdd);
160 *list.append() = contour;
161 }
162 } while ((contour = contour->next()));
163 int count = list.count();
164 if (!count) {
165 return false;
166 }
167 if (count > 1) {
168 SkTQSort<SkOpContour>(list.begin(), list.end() - 1);
169 }
170 contour = list[0];
171 SkOpContourHead* contourHead = static_cast<SkOpContourHead*>(contour);
172 contour->globalState()->setContourHead(contourHead);
173 *contourList = contourHead;
174 for (int index = 1; index < count; ++index) {
175 SkOpContour* next = list[index];
176 contour->setNext(next);
177 contour = next;
178 }
179 contour->setNext(nullptr);
180 return true;
181}
182
183static void calc_angles(SkOpContourHead* contourList DEBUG_COIN_DECLARE_PARAMS()) {
184 DEBUG_STATIC_SET_PHASE(contourList);
185 SkOpContour* contour = contourList;
186 do {
187 contour->calcAngles();
188 } while ((contour = contour->next()));
189}
190
191static bool missing_coincidence(SkOpContourHead* contourList DEBUG_COIN_DECLARE_PARAMS()) {
192 DEBUG_STATIC_SET_PHASE(contourList);
193 SkOpContour* contour = contourList;
194 bool result = false;
195 do {
196 result |= contour->missingCoincidence();
197 } while ((contour = contour->next()));
198 return result;
199}
200
201static bool move_multiples(SkOpContourHead* contourList DEBUG_COIN_DECLARE_PARAMS()) {
202 DEBUG_STATIC_SET_PHASE(contourList);
203 SkOpContour* contour = contourList;
204 do {
205 if (!contour->moveMultiples()) {
206 return false;
207 }
208 } while ((contour = contour->next()));
209 return true;
210}
211
212static bool move_nearby(SkOpContourHead* contourList DEBUG_COIN_DECLARE_PARAMS()) {
213 DEBUG_STATIC_SET_PHASE(contourList);
214 SkOpContour* contour = contourList;
215 do {
216 if (!contour->moveNearby()) {
217 return false;
218 }
219 } while ((contour = contour->next()));
220 return true;
221}
222
223static bool sort_angles(SkOpContourHead* contourList) {
224 SkOpContour* contour = contourList;
225 do {
226 if (!contour->sortAngles()) {
227 return false;
228 }
229 } while ((contour = contour->next()));
230 return true;
231}
232
233bool HandleCoincidence(SkOpContourHead* contourList, SkOpCoincidence* coincidence) {
234 SkOpGlobalState* globalState = contourList->globalState();
235 // match up points within the coincident runs
236 if (!coincidence->addExpanded(DEBUG_PHASE_ONLY_PARAMS(kIntersecting))) {
237 return false;
238 }
239 // combine t values when multiple intersections occur on some segments but not others
240 if (!move_multiples(contourList DEBUG_PHASE_PARAMS(kWalking))) {
241 return false;
242 }
243 // move t values and points together to eliminate small/tiny gaps
244 if (!move_nearby(contourList DEBUG_COIN_PARAMS())) {
245 return false;
246 }
247 // add coincidence formed by pairing on curve points and endpoints
248 coincidence->correctEnds(DEBUG_PHASE_ONLY_PARAMS(kIntersecting));
249 if (!coincidence->addEndMovedSpans(DEBUG_COIN_ONLY_PARAMS())) {
250 return false;
251 }
252 const int SAFETY_COUNT = 3;
253 int safetyHatch = SAFETY_COUNT;
254 // look for coincidence present in A-B and A-C but missing in B-C
255 do {
256 bool added;
257 if (!coincidence->addMissing(&added DEBUG_ITER_PARAMS(SAFETY_COUNT - safetyHatch))) {
258 return false;
259 }
260 if (!added) {
261 break;
262 }
263 if (!--safetyHatch) {
264 SkASSERT(globalState->debugSkipAssert());
265 return false;
266 }
267 move_nearby(contourList DEBUG_ITER_PARAMS(SAFETY_COUNT - safetyHatch - 1));
268 } while (true);
269 // check to see if, loosely, coincident ranges may be expanded
270 if (coincidence->expand(DEBUG_COIN_ONLY_PARAMS())) {
271 bool added;
272 if (!coincidence->addMissing(&added DEBUG_COIN_PARAMS())) {
273 return false;
274 }
275 if (!coincidence->addExpanded(DEBUG_COIN_ONLY_PARAMS())) {
276 return false;
277 }
278 if (!move_multiples(contourList DEBUG_COIN_PARAMS())) {
279 return false;
280 }
281 move_nearby(contourList DEBUG_COIN_PARAMS());
282 }
283 // the expanded ranges may not align -- add the missing spans
284 if (!coincidence->addExpanded(DEBUG_PHASE_ONLY_PARAMS(kWalking))) {
285 return false;
286 }
287 // mark spans of coincident segments as coincident
288 coincidence->mark(DEBUG_COIN_ONLY_PARAMS());
289 // look for coincidence lines and curves undetected by intersection
290 if (missing_coincidence(contourList DEBUG_COIN_PARAMS())) {
291 (void) coincidence->expand(DEBUG_PHASE_ONLY_PARAMS(kIntersecting));
292 if (!coincidence->addExpanded(DEBUG_COIN_ONLY_PARAMS())) {
293 return false;
294 }
295 if (!coincidence->mark(DEBUG_PHASE_ONLY_PARAMS(kWalking))) {
296 return false;
297 }
298 } else {
299 (void) coincidence->expand(DEBUG_COIN_ONLY_PARAMS());
300 }
301 (void) coincidence->expand(DEBUG_COIN_ONLY_PARAMS());
302
303 SkOpCoincidence overlaps(globalState);
304 safetyHatch = SAFETY_COUNT;
305 do {
306 SkOpCoincidence* pairs = overlaps.isEmpty() ? coincidence : &overlaps;
307 // adjust the winding value to account for coincident edges
308 if (!pairs->apply(DEBUG_ITER_ONLY_PARAMS(SAFETY_COUNT - safetyHatch))) {
309 return false;
310 }
311 // For each coincident pair that overlaps another, when the receivers (the 1st of the pair)
312 // are different, construct a new pair to resolve their mutual span
313 if (!pairs->findOverlaps(&overlaps DEBUG_ITER_PARAMS(SAFETY_COUNT - safetyHatch))) {
314 return false;
315 }
316 if (!--safetyHatch) {
317 SkASSERT(globalState->debugSkipAssert());
318 return false;
319 }
320 } while (!overlaps.isEmpty());
321 calc_angles(contourList DEBUG_COIN_PARAMS());
322 if (!sort_angles(contourList)) {
323 return false;
324 }
325#if DEBUG_COINCIDENCE_VERBOSE
326 coincidence->debugShowCoincidence();
327#endif
328#if DEBUG_COINCIDENCE
329 coincidence->debugValidate();
330#endif
331 SkPathOpsDebug::ShowActiveSpans(contourList);
332 return true;
333}
334