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