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