Line data Source code
1 : /*
2 : * Copyright 2014 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 "SkOpCoincidence.h"
8 : #include "SkOpContour.h"
9 : #include "SkOpSegment.h"
10 : #include "SkPathWriter.h"
11 :
12 0 : bool SkOpPtT::alias() const {
13 0 : return this->span()->ptT() != this;
14 : }
15 :
16 0 : const SkOpPtT* SkOpPtT::active() const {
17 0 : if (!fDeleted) {
18 0 : return this;
19 : }
20 0 : const SkOpPtT* ptT = this;
21 0 : const SkOpPtT* stopPtT = ptT;
22 0 : while ((ptT = ptT->next()) != stopPtT) {
23 0 : if (ptT->fSpan == fSpan && !ptT->fDeleted) {
24 0 : return ptT;
25 : }
26 : }
27 0 : SkASSERT(0); // should never return deleted
28 0 : return this;
29 : }
30 :
31 0 : bool SkOpPtT::contains(const SkOpPtT* check) const {
32 0 : SkOPASSERT(this != check);
33 0 : const SkOpPtT* ptT = this;
34 0 : const SkOpPtT* stopPtT = ptT;
35 0 : while ((ptT = ptT->next()) != stopPtT) {
36 0 : if (ptT == check) {
37 0 : return true;
38 : }
39 : }
40 0 : return false;
41 : }
42 :
43 0 : bool SkOpPtT::contains(const SkOpSegment* segment, const SkPoint& pt) const {
44 0 : SkASSERT(this->segment() != segment);
45 0 : const SkOpPtT* ptT = this;
46 0 : const SkOpPtT* stopPtT = ptT;
47 0 : while ((ptT = ptT->next()) != stopPtT) {
48 0 : if (ptT->fPt == pt && ptT->segment() == segment) {
49 0 : return true;
50 : }
51 : }
52 0 : return false;
53 : }
54 :
55 0 : bool SkOpPtT::contains(const SkOpSegment* segment, double t) const {
56 0 : const SkOpPtT* ptT = this;
57 0 : const SkOpPtT* stopPtT = ptT;
58 0 : while ((ptT = ptT->next()) != stopPtT) {
59 0 : if (ptT->fT == t && ptT->segment() == segment) {
60 0 : return true;
61 : }
62 : }
63 0 : return false;
64 : }
65 :
66 0 : const SkOpPtT* SkOpPtT::contains(const SkOpSegment* check) const {
67 0 : SkASSERT(this->segment() != check);
68 0 : const SkOpPtT* ptT = this;
69 0 : const SkOpPtT* stopPtT = ptT;
70 0 : while ((ptT = ptT->next()) != stopPtT) {
71 0 : if (ptT->segment() == check && !ptT->deleted()) {
72 0 : return ptT;
73 : }
74 : }
75 0 : return nullptr;
76 : }
77 :
78 0 : SkOpContour* SkOpPtT::contour() const {
79 0 : return segment()->contour();
80 : }
81 :
82 0 : const SkOpPtT* SkOpPtT::find(const SkOpSegment* segment) const {
83 0 : const SkOpPtT* ptT = this;
84 0 : const SkOpPtT* stopPtT = ptT;
85 0 : do {
86 0 : if (ptT->segment() == segment && !ptT->deleted()) {
87 0 : return ptT;
88 : }
89 0 : ptT = ptT->fNext;
90 0 : } while (stopPtT != ptT);
91 : // SkASSERT(0);
92 0 : return nullptr;
93 : }
94 :
95 0 : SkOpGlobalState* SkOpPtT::globalState() const {
96 0 : return contour()->globalState();
97 : }
98 :
99 0 : void SkOpPtT::init(SkOpSpanBase* span, double t, const SkPoint& pt, bool duplicate) {
100 0 : fT = t;
101 0 : fPt = pt;
102 0 : fSpan = span;
103 0 : fNext = this;
104 0 : fDuplicatePt = duplicate;
105 0 : fDeleted = false;
106 0 : fCoincident = false;
107 0 : SkDEBUGCODE(fID = span->globalState()->nextPtTID());
108 0 : }
109 :
110 0 : bool SkOpPtT::onEnd() const {
111 0 : const SkOpSpanBase* span = this->span();
112 0 : if (span->ptT() != this) {
113 0 : return false;
114 : }
115 0 : const SkOpSegment* segment = this->segment();
116 0 : return span == segment->head() || span == segment->tail();
117 : }
118 :
119 0 : bool SkOpPtT::ptAlreadySeen(const SkOpPtT* check) const {
120 0 : while (this != check) {
121 0 : if (this->fPt == check->fPt) {
122 0 : return true;
123 : }
124 0 : check = check->fNext;
125 : }
126 0 : return false;
127 : }
128 :
129 0 : SkOpPtT* SkOpPtT::prev() {
130 0 : SkOpPtT* result = this;
131 0 : SkOpPtT* next = this;
132 0 : while ((next = next->fNext) != this) {
133 0 : result = next;
134 : }
135 0 : SkASSERT(result->fNext == this);
136 0 : return result;
137 : }
138 :
139 0 : const SkOpSegment* SkOpPtT::segment() const {
140 0 : return span()->segment();
141 : }
142 :
143 0 : SkOpSegment* SkOpPtT::segment() {
144 0 : return span()->segment();
145 : }
146 :
147 0 : void SkOpPtT::setDeleted() {
148 0 : SkASSERT(this->span()->debugDeleted() || this->span()->ptT() != this);
149 0 : SkOPASSERT(!fDeleted);
150 0 : fDeleted = true;
151 0 : }
152 :
153 0 : void SkOpSpanBase::addOpp(SkOpSpanBase* opp) {
154 0 : SkOpPtT* oppPrev = this->ptT()->oppPrev(opp->ptT());
155 0 : if (!oppPrev) {
156 0 : return;
157 : }
158 0 : this->mergeMatches(opp);
159 0 : this->ptT()->addOpp(opp->ptT(), oppPrev);
160 0 : this->checkForCollapsedCoincidence();
161 : }
162 :
163 0 : bool SkOpSpanBase::collapsed(double s, double e) const {
164 0 : const SkOpPtT* start = &fPtT;
165 0 : const SkOpPtT* walk = start;
166 0 : double min = walk->fT;
167 0 : double max = min;
168 0 : const SkOpSegment* segment = this->segment();
169 0 : while ((walk = walk->next()) != start) {
170 0 : if (walk->segment() != segment) {
171 0 : continue;
172 : }
173 0 : min = SkTMin(min, walk->fT);
174 0 : max = SkTMax(max, walk->fT);
175 0 : if (between(min, s, max) && between(min, e, max)) {
176 0 : return true;
177 : }
178 : }
179 0 : return false;
180 : }
181 :
182 0 : bool SkOpSpanBase::contains(const SkOpSpanBase* span) const {
183 0 : const SkOpPtT* start = &fPtT;
184 0 : const SkOpPtT* check = &span->fPtT;
185 0 : SkOPASSERT(start != check);
186 0 : const SkOpPtT* walk = start;
187 0 : while ((walk = walk->next()) != start) {
188 0 : if (walk == check) {
189 0 : return true;
190 : }
191 : }
192 0 : return false;
193 : }
194 :
195 0 : const SkOpPtT* SkOpSpanBase::contains(const SkOpSegment* segment) const {
196 0 : const SkOpPtT* start = &fPtT;
197 0 : const SkOpPtT* walk = start;
198 0 : while ((walk = walk->next()) != start) {
199 0 : if (walk->deleted()) {
200 0 : continue;
201 : }
202 0 : if (walk->segment() == segment && walk->span()->ptT() == walk) {
203 0 : return walk;
204 : }
205 : }
206 0 : return nullptr;
207 : }
208 :
209 0 : bool SkOpSpanBase::containsCoinEnd(const SkOpSegment* segment) const {
210 0 : SkASSERT(this->segment() != segment);
211 0 : const SkOpSpanBase* next = this;
212 0 : while ((next = next->fCoinEnd) != this) {
213 0 : if (next->segment() == segment) {
214 0 : return true;
215 : }
216 : }
217 0 : return false;
218 : }
219 :
220 0 : SkOpContour* SkOpSpanBase::contour() const {
221 0 : return segment()->contour();
222 : }
223 :
224 0 : SkOpGlobalState* SkOpSpanBase::globalState() const {
225 0 : return contour()->globalState();
226 : }
227 :
228 0 : void SkOpSpanBase::initBase(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoint& pt) {
229 0 : fSegment = segment;
230 0 : fPtT.init(this, t, pt, false);
231 0 : fCoinEnd = this;
232 0 : fFromAngle = nullptr;
233 0 : fPrev = prev;
234 0 : fSpanAdds = 0;
235 0 : fAligned = true;
236 0 : fChased = false;
237 0 : SkDEBUGCODE(fCount = 1);
238 0 : SkDEBUGCODE(fID = globalState()->nextSpanID());
239 0 : SkDEBUGCODE(fDebugDeleted = false);
240 0 : }
241 :
242 : // this pair of spans share a common t value or point; merge them and eliminate duplicates
243 : // this does not compute the best t or pt value; this merely moves all data into a single list
244 0 : void SkOpSpanBase::merge(SkOpSpan* span) {
245 0 : SkOpPtT* spanPtT = span->ptT();
246 0 : SkASSERT(this->t() != spanPtT->fT);
247 0 : SkASSERT(!zero_or_one(spanPtT->fT));
248 0 : span->release(this->ptT());
249 0 : if (this->contains(span)) {
250 0 : SkOPASSERT(0); // check to see if this ever happens -- should have been found earlier
251 0 : return; // merge is already in the ptT loop
252 : }
253 0 : SkOpPtT* remainder = spanPtT->next();
254 0 : this->ptT()->insert(spanPtT);
255 0 : while (remainder != spanPtT) {
256 0 : SkOpPtT* next = remainder->next();
257 0 : SkOpPtT* compare = spanPtT->next();
258 0 : while (compare != spanPtT) {
259 0 : SkOpPtT* nextC = compare->next();
260 0 : if (nextC->span() == remainder->span() && nextC->fT == remainder->fT) {
261 0 : goto tryNextRemainder;
262 : }
263 0 : compare = nextC;
264 : }
265 0 : spanPtT->insert(remainder);
266 : tryNextRemainder:
267 0 : remainder = next;
268 : }
269 0 : fSpanAdds += span->fSpanAdds;
270 : }
271 :
272 0 : SkOpSpanBase* SkOpSpanBase::active() {
273 0 : SkOpSpanBase* result = fPrev ? fPrev->next() : upCast()->next()->prev();
274 0 : SkASSERT(this == result || fDebugDeleted);
275 0 : return result;
276 : }
277 :
278 : // please keep in sync with debugCheckForCollapsedCoincidence()
279 0 : void SkOpSpanBase::checkForCollapsedCoincidence() {
280 0 : SkOpCoincidence* coins = this->globalState()->coincidence();
281 0 : if (coins->isEmpty()) {
282 0 : return;
283 : }
284 : // the insert above may have put both ends of a coincident run in the same span
285 : // for each coincident ptT in loop; see if its opposite in is also in the loop
286 : // this implementation is the motivation for marking that a ptT is referenced by a coincident span
287 0 : SkOpPtT* head = this->ptT();
288 0 : SkOpPtT* test = head;
289 0 : do {
290 0 : if (!test->coincident()) {
291 0 : continue;
292 : }
293 0 : coins->markCollapsed(test);
294 : } while ((test = test->next()) != head);
295 0 : coins->releaseDeleted();
296 : }
297 :
298 : // please keep in sync with debugMergeMatches()
299 : // Look to see if pt-t linked list contains same segment more than once
300 : // if so, and if each pt-t is directly pointed to by spans in that segment,
301 : // merge them
302 : // keep the points, but remove spans so that the segment doesn't have 2 or more
303 : // spans pointing to the same pt-t loop at different loop elements
304 0 : void SkOpSpanBase::mergeMatches(SkOpSpanBase* opp) {
305 0 : SkOpPtT* test = &fPtT;
306 : SkOpPtT* testNext;
307 0 : const SkOpPtT* stop = test;
308 0 : do {
309 0 : testNext = test->next();
310 0 : if (test->deleted()) {
311 0 : continue;
312 : }
313 0 : SkOpSpanBase* testBase = test->span();
314 0 : SkASSERT(testBase->ptT() == test);
315 0 : SkOpSegment* segment = test->segment();
316 0 : if (segment->done()) {
317 0 : continue;
318 : }
319 0 : SkOpPtT* inner = opp->ptT();
320 0 : const SkOpPtT* innerStop = inner;
321 0 : do {
322 0 : if (inner->segment() != segment) {
323 0 : continue;
324 : }
325 0 : if (inner->deleted()) {
326 0 : continue;
327 : }
328 0 : SkOpSpanBase* innerBase = inner->span();
329 0 : SkASSERT(innerBase->ptT() == inner);
330 : // when the intersection is first detected, the span base is marked if there are
331 : // more than one point in the intersection.
332 0 : if (!zero_or_one(inner->fT)) {
333 0 : innerBase->upCast()->release(test);
334 : } else {
335 0 : SkOPASSERT(inner->fT != test->fT);
336 0 : if (!zero_or_one(test->fT)) {
337 0 : testBase->upCast()->release(inner);
338 : } else {
339 0 : segment->markAllDone(); // mark segment as collapsed
340 0 : SkDEBUGCODE(testBase->debugSetDeleted());
341 0 : test->setDeleted();
342 0 : SkDEBUGCODE(innerBase->debugSetDeleted());
343 0 : inner->setDeleted();
344 : }
345 : }
346 : #ifdef SK_DEBUG // assert if another undeleted entry points to segment
347 0 : const SkOpPtT* debugInner = inner;
348 0 : while ((debugInner = debugInner->next()) != innerStop) {
349 0 : if (debugInner->segment() != segment) {
350 0 : continue;
351 : }
352 0 : if (debugInner->deleted()) {
353 0 : continue;
354 : }
355 0 : SkOPASSERT(0);
356 : }
357 : #endif
358 0 : break;
359 : } while ((inner = inner->next()) != innerStop);
360 0 : } while ((test = testNext) != stop);
361 0 : this->checkForCollapsedCoincidence();
362 0 : }
363 :
364 0 : int SkOpSpan::computeWindSum() {
365 0 : SkOpGlobalState* globals = this->globalState();
366 0 : SkOpContour* contourHead = globals->contourHead();
367 0 : int windTry = 0;
368 0 : while (!this->sortableTop(contourHead) && ++windTry < SkOpGlobalState::kMaxWindingTries) {
369 : ;
370 : }
371 0 : return this->windSum();
372 : }
373 :
374 0 : bool SkOpSpan::containsCoincidence(const SkOpSegment* segment) const {
375 0 : SkASSERT(this->segment() != segment);
376 0 : const SkOpSpan* next = fCoincident;
377 0 : do {
378 0 : if (next->segment() == segment) {
379 0 : return true;
380 : }
381 0 : } while ((next = next->fCoincident) != this);
382 0 : return false;
383 : }
384 :
385 0 : void SkOpSpan::init(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoint& pt) {
386 0 : SkASSERT(t != 1);
387 0 : initBase(segment, prev, t, pt);
388 0 : fCoincident = this;
389 0 : fToAngle = nullptr;
390 0 : fWindSum = fOppSum = SK_MinS32;
391 0 : fWindValue = 1;
392 0 : fOppValue = 0;
393 0 : fTopTTry = 0;
394 0 : fChased = fDone = false;
395 0 : segment->bumpCount();
396 0 : fAlreadyAdded = false;
397 0 : }
398 :
399 : // Please keep this in sync with debugInsertCoincidence()
400 0 : bool SkOpSpan::insertCoincidence(const SkOpSegment* segment, bool flipped, bool ordered) {
401 0 : if (this->containsCoincidence(segment)) {
402 0 : return true;
403 : }
404 0 : SkOpPtT* next = &fPtT;
405 0 : while ((next = next->next()) != &fPtT) {
406 0 : if (next->segment() == segment) {
407 : SkOpSpan* span;
408 0 : SkOpSpanBase* base = next->span();
409 0 : if (!ordered) {
410 0 : const SkOpPtT* spanEndPtT = fNext->contains(segment);
411 0 : FAIL_IF(!spanEndPtT);
412 0 : const SkOpSpanBase* spanEnd = spanEndPtT->span();
413 0 : const SkOpPtT* start = base->ptT()->starter(spanEnd->ptT());
414 0 : FAIL_IF(!start->span()->upCastable());
415 0 : span = const_cast<SkOpSpan*>(start->span()->upCast());
416 0 : } else if (flipped) {
417 0 : span = base->prev();
418 0 : FAIL_IF(!span);
419 : } else {
420 0 : FAIL_IF(!base->upCastable());
421 0 : span = base->upCast();
422 : }
423 0 : this->insertCoincidence(span);
424 0 : return true;
425 : }
426 : }
427 : #if DEBUG_COINCIDENCE
428 : SkASSERT(0); // FIXME? if we get here, the span is missing its opposite segment...
429 : #endif
430 0 : return true;
431 : }
432 :
433 0 : void SkOpSpan::release(const SkOpPtT* kept) {
434 0 : SkDEBUGCODE(fDebugDeleted = true);
435 0 : SkOPASSERT(kept->span() != this);
436 0 : SkASSERT(!final());
437 0 : SkOpSpan* prev = this->prev();
438 0 : SkASSERT(prev);
439 0 : SkOpSpanBase* next = this->next();
440 0 : SkASSERT(next);
441 0 : prev->setNext(next);
442 0 : next->setPrev(prev);
443 0 : this->segment()->release(this);
444 0 : SkOpCoincidence* coincidence = this->globalState()->coincidence();
445 0 : if (coincidence) {
446 0 : coincidence->fixUp(this->ptT(), kept);
447 : }
448 0 : this->ptT()->setDeleted();
449 0 : SkOpPtT* stopPtT = this->ptT();
450 0 : SkOpPtT* testPtT = stopPtT;
451 0 : const SkOpSpanBase* keptSpan = kept->span();
452 0 : do {
453 0 : if (this == testPtT->span()) {
454 0 : testPtT->setSpan(keptSpan);
455 : }
456 : } while ((testPtT = testPtT->next()) != stopPtT);
457 0 : }
458 :
459 0 : void SkOpSpan::setOppSum(int oppSum) {
460 0 : SkASSERT(!final());
461 0 : if (fOppSum != SK_MinS32 && fOppSum != oppSum) {
462 0 : this->globalState()->setWindingFailed();
463 0 : return;
464 : }
465 0 : SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(oppSum) <= DEBUG_LIMIT_WIND_SUM);
466 0 : fOppSum = oppSum;
467 : }
468 :
469 0 : void SkOpSpan::setWindSum(int windSum) {
470 0 : SkASSERT(!final());
471 0 : if (fWindSum != SK_MinS32 && fWindSum != windSum) {
472 0 : this->globalState()->setWindingFailed();
473 0 : return;
474 : }
475 0 : SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(windSum) <= DEBUG_LIMIT_WIND_SUM);
476 0 : fWindSum = windSum;
477 : }
|
