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#ifndef SkOpSpan_DEFINED
8#define SkOpSpan_DEFINED
9
10#include "include/core/SkPoint.h"
11#include "src/pathops/SkPathOpsDebug.h"
12#include "src/pathops/SkPathOpsTypes.h"
13
14class SkArenaAlloc;
15class SkOpAngle;
16class SkOpContour;
17class SkOpGlobalState;
18class SkOpSegment;
19class SkOpSpanBase;
20class SkOpSpan;
21struct SkPathOpsBounds;
22
23// subset of op span used by terminal span (when t is equal to one)
24class SkOpPtT {
25public:
26 enum {
27 kIsAlias = 1,
28 kIsDuplicate = 1
29 };
30
31 const SkOpPtT* active() const;
32
33 // please keep in sync with debugAddOpp()
34 void addOpp(SkOpPtT* opp, SkOpPtT* oppPrev) {
35 SkOpPtT* oldNext = this->fNext;
36 SkASSERT(this != opp);
37 this->fNext = opp;
38 SkASSERT(oppPrev != oldNext);
39 oppPrev->fNext = oldNext;
40 }
41
42 bool alias() const;
43 bool coincident() const { return fCoincident; }
44 bool contains(const SkOpPtT* ) const;
45 bool contains(const SkOpSegment*, const SkPoint& ) const;
46 bool contains(const SkOpSegment*, double t) const;
47 const SkOpPtT* contains(const SkOpSegment* ) const;
48 SkOpContour* contour() const;
49
50 int debugID() const {
51 return SkDEBUGRELEASE(fID, -1);
52 }
53
54 void debugAddOpp(const SkOpPtT* opp, const SkOpPtT* oppPrev) const;
55 const SkOpAngle* debugAngle(int id) const;
56 const SkOpCoincidence* debugCoincidence() const;
57 bool debugContains(const SkOpPtT* ) const;
58 const SkOpPtT* debugContains(const SkOpSegment* check) const;
59 SkOpContour* debugContour(int id) const;
60 const SkOpPtT* debugEnder(const SkOpPtT* end) const;
61 int debugLoopLimit(bool report) const;
62 bool debugMatchID(int id) const;
63 const SkOpPtT* debugOppPrev(const SkOpPtT* opp) const;
64 const SkOpPtT* debugPtT(int id) const;
65 void debugResetCoinT() const;
66 const SkOpSegment* debugSegment(int id) const;
67 void debugSetCoinT(int ) const;
68 const SkOpSpanBase* debugSpan(int id) const;
69 void debugValidate() const;
70
71 bool deleted() const {
72 return fDeleted;
73 }
74
75 bool duplicate() const {
76 return fDuplicatePt;
77 }
78
79 void dump() const; // available to testing only
80 void dumpAll() const;
81 void dumpBase() const;
82
83 const SkOpPtT* find(const SkOpSegment* ) const;
84 SkOpGlobalState* globalState() const;
85 void init(SkOpSpanBase* , double t, const SkPoint& , bool dup);
86
87 void insert(SkOpPtT* span) {
88 SkASSERT(span != this);
89 span->fNext = fNext;
90 fNext = span;
91 }
92
93 const SkOpPtT* next() const {
94 return fNext;
95 }
96
97 SkOpPtT* next() {
98 return fNext;
99 }
100
101 bool onEnd() const;
102
103 // returns nullptr if this is already in the opp ptT loop
104 SkOpPtT* oppPrev(const SkOpPtT* opp) const {
105 // find the fOpp ptr to opp
106 SkOpPtT* oppPrev = opp->fNext;
107 if (oppPrev == this) {
108 return nullptr;
109 }
110 while (oppPrev->fNext != opp) {
111 oppPrev = oppPrev->fNext;
112 if (oppPrev == this) {
113 return nullptr;
114 }
115 }
116 return oppPrev;
117 }
118
119 static bool Overlaps(const SkOpPtT* s1, const SkOpPtT* e1, const SkOpPtT* s2,
120 const SkOpPtT* e2, const SkOpPtT** sOut, const SkOpPtT** eOut) {
121 const SkOpPtT* start1 = s1->fT < e1->fT ? s1 : e1;
122 const SkOpPtT* start2 = s2->fT < e2->fT ? s2 : e2;
123 *sOut = between(s1->fT, start2->fT, e1->fT) ? start2
124 : between(s2->fT, start1->fT, e2->fT) ? start1 : nullptr;
125 const SkOpPtT* end1 = s1->fT < e1->fT ? e1 : s1;
126 const SkOpPtT* end2 = s2->fT < e2->fT ? e2 : s2;
127 *eOut = between(s1->fT, end2->fT, e1->fT) ? end2
128 : between(s2->fT, end1->fT, e2->fT) ? end1 : nullptr;
129 if (*sOut == *eOut) {
130 SkOPOBJASSERT(s1, start1->fT >= end2->fT || start2->fT >= end1->fT);
131 return false;
132 }
133 SkASSERT(!*sOut || *sOut != *eOut);
134 return *sOut && *eOut;
135 }
136
137 bool ptAlreadySeen(const SkOpPtT* head) const;
138 SkOpPtT* prev();
139
140 const SkOpSegment* segment() const;
141 SkOpSegment* segment();
142
143 void setCoincident() const {
144 SkOPASSERT(!fDeleted);
145 fCoincident = true;
146 }
147
148 void setDeleted();
149
150 void setSpan(const SkOpSpanBase* span) {
151 fSpan = const_cast<SkOpSpanBase*>(span);
152 }
153
154 const SkOpSpanBase* span() const {
155 return fSpan;
156 }
157
158 SkOpSpanBase* span() {
159 return fSpan;
160 }
161
162 const SkOpPtT* starter(const SkOpPtT* end) const {
163 return fT < end->fT ? this : end;
164 }
165
166 double fT;
167 SkPoint fPt; // cache of point value at this t
168protected:
169 SkOpSpanBase* fSpan; // contains winding data
170 SkOpPtT* fNext; // intersection on opposite curve or alias on this curve
171 bool fDeleted; // set if removed from span list
172 bool fDuplicatePt; // set if identical pt is somewhere in the next loop
173 // below mutable since referrer is otherwise always const
174 mutable bool fCoincident; // set if at some point a coincident span pointed here
175 SkDEBUGCODE(int fID);
176};
177
178class SkOpSpanBase {
179public:
180 enum class Collapsed {
181 kNo,
182 kYes,
183 kError,
184 };
185
186 bool addOpp(SkOpSpanBase* opp);
187
188 void bumpSpanAdds() {
189 ++fSpanAdds;
190 }
191
192 bool chased() const {
193 return fChased;
194 }
195
196 void checkForCollapsedCoincidence();
197
198 const SkOpSpanBase* coinEnd() const {
199 return fCoinEnd;
200 }
201
202 Collapsed collapsed(double s, double e) const;
203 bool contains(const SkOpSpanBase* ) const;
204 const SkOpPtT* contains(const SkOpSegment* ) const;
205
206 bool containsCoinEnd(const SkOpSpanBase* coin) const {
207 SkASSERT(this != coin);
208 const SkOpSpanBase* next = this;
209 while ((next = next->fCoinEnd) != this) {
210 if (next == coin) {
211 return true;
212 }
213 }
214 return false;
215 }
216
217 bool containsCoinEnd(const SkOpSegment* ) const;
218 SkOpContour* contour() const;
219
220 int debugBumpCount() {
221 return SkDEBUGRELEASE(++fCount, -1);
222 }
223
224 int debugID() const {
225 return SkDEBUGRELEASE(fID, -1);
226 }
227
228#if DEBUG_COIN
229 void debugAddOpp(SkPathOpsDebug::GlitchLog* , const SkOpSpanBase* opp) const;
230#endif
231 bool debugAlignedEnd(double t, const SkPoint& pt) const;
232 bool debugAlignedInner() const;
233 const SkOpAngle* debugAngle(int id) const;
234#if DEBUG_COIN
235 void debugCheckForCollapsedCoincidence(SkPathOpsDebug::GlitchLog* ) const;
236#endif
237 const SkOpCoincidence* debugCoincidence() const;
238 bool debugCoinEndLoopCheck() const;
239 SkOpContour* debugContour(int id) const;
240#ifdef SK_DEBUG
241 bool debugDeleted() const { return fDebugDeleted; }
242#endif
243#if DEBUG_COIN
244 void debugInsertCoinEnd(SkPathOpsDebug::GlitchLog* ,
245 const SkOpSpanBase* ) const;
246 void debugMergeMatches(SkPathOpsDebug::GlitchLog* log,
247 const SkOpSpanBase* opp) const;
248#endif
249 const SkOpPtT* debugPtT(int id) const;
250 void debugResetCoinT() const;
251 const SkOpSegment* debugSegment(int id) const;
252 void debugSetCoinT(int ) const;
253#ifdef SK_DEBUG
254 void debugSetDeleted() { fDebugDeleted = true; }
255#endif
256 const SkOpSpanBase* debugSpan(int id) const;
257 const SkOpSpan* debugStarter(SkOpSpanBase const** endPtr) const;
258 SkOpGlobalState* globalState() const;
259 void debugValidate() const;
260
261 bool deleted() const {
262 return fPtT.deleted();
263 }
264
265 void dump() const; // available to testing only
266 void dumpCoin() const;
267 void dumpAll() const;
268 void dumpBase() const;
269 void dumpHead() const;
270
271 bool final() const {
272 return fPtT.fT == 1;
273 }
274
275 SkOpAngle* fromAngle() const {
276 return fFromAngle;
277 }
278
279 void initBase(SkOpSegment* parent, SkOpSpan* prev, double t, const SkPoint& pt);
280
281 // Please keep this in sync with debugInsertCoinEnd()
282 void insertCoinEnd(SkOpSpanBase* coin) {
283 if (containsCoinEnd(coin)) {
284 SkASSERT(coin->containsCoinEnd(this));
285 return;
286 }
287 debugValidate();
288 SkASSERT(this != coin);
289 SkOpSpanBase* coinNext = coin->fCoinEnd;
290 coin->fCoinEnd = this->fCoinEnd;
291 this->fCoinEnd = coinNext;
292 debugValidate();
293 }
294
295 void merge(SkOpSpan* span);
296 bool mergeMatches(SkOpSpanBase* opp);
297
298 const SkOpSpan* prev() const {
299 return fPrev;
300 }
301
302 SkOpSpan* prev() {
303 return fPrev;
304 }
305
306 const SkPoint& pt() const {
307 return fPtT.fPt;
308 }
309
310 const SkOpPtT* ptT() const {
311 return &fPtT;
312 }
313
314 SkOpPtT* ptT() {
315 return &fPtT;
316 }
317
318 SkOpSegment* segment() const {
319 return fSegment;
320 }
321
322 void setAligned() {
323 fAligned = true;
324 }
325
326 void setChased(bool chased) {
327 fChased = chased;
328 }
329
330 void setFromAngle(SkOpAngle* angle) {
331 fFromAngle = angle;
332 }
333
334 void setPrev(SkOpSpan* prev) {
335 fPrev = prev;
336 }
337
338 bool simple() const {
339 fPtT.debugValidate();
340 return fPtT.next()->next() == &fPtT;
341 }
342
343 int spanAddsCount() const {
344 return fSpanAdds;
345 }
346
347 const SkOpSpan* starter(const SkOpSpanBase* end) const {
348 const SkOpSpanBase* result = t() < end->t() ? this : end;
349 return result->upCast();
350 }
351
352 SkOpSpan* starter(SkOpSpanBase* end) {
353 SkASSERT(this->segment() == end->segment());
354 SkOpSpanBase* result = t() < end->t() ? this : end;
355 return result->upCast();
356 }
357
358 SkOpSpan* starter(SkOpSpanBase** endPtr) {
359 SkOpSpanBase* end = *endPtr;
360 SkASSERT(this->segment() == end->segment());
361 SkOpSpanBase* result;
362 if (t() < end->t()) {
363 result = this;
364 } else {
365 result = end;
366 *endPtr = this;
367 }
368 return result->upCast();
369 }
370
371 int step(const SkOpSpanBase* end) const {
372 return t() < end->t() ? 1 : -1;
373 }
374
375 double t() const {
376 return fPtT.fT;
377 }
378
379 void unaligned() {
380 fAligned = false;
381 }
382
383 SkOpSpan* upCast() {
384 SkASSERT(!final());
385 return (SkOpSpan*) this;
386 }
387
388 const SkOpSpan* upCast() const {
389 SkOPASSERT(!final());
390 return (const SkOpSpan*) this;
391 }
392
393 SkOpSpan* upCastable() {
394 return final() ? nullptr : upCast();
395 }
396
397 const SkOpSpan* upCastable() const {
398 return final() ? nullptr : upCast();
399 }
400
401private:
402 void alignInner();
403
404protected: // no direct access to internals to avoid treating a span base as a span
405 SkOpPtT fPtT; // list of points and t values associated with the start of this span
406 SkOpSegment* fSegment; // segment that contains this span
407 SkOpSpanBase* fCoinEnd; // linked list of coincident spans that end here (may point to itself)
408 SkOpAngle* fFromAngle; // points to next angle from span start to end
409 SkOpSpan* fPrev; // previous intersection point
410 int fSpanAdds; // number of times intersections have been added to span
411 bool fAligned;
412 bool fChased; // set after span has been added to chase array
413 SkDEBUGCODE(int fCount); // number of pt/t pairs added
414 SkDEBUGCODE(int fID);
415 SkDEBUGCODE(bool fDebugDeleted); // set when span was merged with another span
416};
417
418class SkOpSpan : public SkOpSpanBase {
419public:
420 bool alreadyAdded() const {
421 if (fAlreadyAdded) {
422 return true;
423 }
424 return false;
425 }
426
427 bool clearCoincident() {
428 SkASSERT(!final());
429 if (fCoincident == this) {
430 return false;
431 }
432 fCoincident = this;
433 return true;
434 }
435
436 int computeWindSum();
437 bool containsCoincidence(const SkOpSegment* ) const;
438
439 bool containsCoincidence(const SkOpSpan* coin) const {
440 SkASSERT(this != coin);
441 const SkOpSpan* next = this;
442 while ((next = next->fCoincident) != this) {
443 if (next == coin) {
444 return true;
445 }
446 }
447 return false;
448 }
449
450 bool debugCoinLoopCheck() const;
451#if DEBUG_COIN
452 void debugInsertCoincidence(SkPathOpsDebug::GlitchLog* , const SkOpSpan* ) const;
453 void debugInsertCoincidence(SkPathOpsDebug::GlitchLog* ,
454 const SkOpSegment* , bool flipped, bool ordered) const;
455#endif
456 void dumpCoin() const;
457 bool dumpSpan() const;
458
459 bool done() const {
460 SkASSERT(!final());
461 return fDone;
462 }
463
464 void init(SkOpSegment* parent, SkOpSpan* prev, double t, const SkPoint& pt);
465 bool insertCoincidence(const SkOpSegment* , bool flipped, bool ordered);
466
467 // Please keep this in sync with debugInsertCoincidence()
468 void insertCoincidence(SkOpSpan* coin) {
469 if (containsCoincidence(coin)) {
470 SkASSERT(coin->containsCoincidence(this));
471 return;
472 }
473 debugValidate();
474 SkASSERT(this != coin);
475 SkOpSpan* coinNext = coin->fCoincident;
476 coin->fCoincident = this->fCoincident;
477 this->fCoincident = coinNext;
478 debugValidate();
479 }
480
481 bool isCanceled() const {
482 SkASSERT(!final());
483 return fWindValue == 0 && fOppValue == 0;
484 }
485
486 bool isCoincident() const {
487 SkASSERT(!final());
488 return fCoincident != this;
489 }
490
491 void markAdded() {
492 fAlreadyAdded = true;
493 }
494
495 SkOpSpanBase* next() const {
496 SkASSERT(!final());
497 return fNext;
498 }
499
500 int oppSum() const {
501 SkASSERT(!final());
502 return fOppSum;
503 }
504
505 int oppValue() const {
506 SkASSERT(!final());
507 return fOppValue;
508 }
509
510 void release(const SkOpPtT* );
511
512 SkOpPtT* setCoinStart(SkOpSpan* oldCoinStart, SkOpSegment* oppSegment);
513
514 void setDone(bool done) {
515 SkASSERT(!final());
516 fDone = done;
517 }
518
519 void setNext(SkOpSpanBase* nextT) {
520 SkASSERT(!final());
521 fNext = nextT;
522 }
523
524 void setOppSum(int oppSum);
525
526 void setOppValue(int oppValue) {
527 SkASSERT(!final());
528 SkASSERT(fOppSum == SK_MinS32);
529 SkOPASSERT(!oppValue || !fDone);
530 fOppValue = oppValue;
531 }
532
533 void setToAngle(SkOpAngle* angle) {
534 SkASSERT(!final());
535 fToAngle = angle;
536 }
537
538 void setWindSum(int windSum);
539
540 void setWindValue(int windValue) {
541 SkASSERT(!final());
542 SkASSERT(windValue >= 0);
543 SkASSERT(fWindSum == SK_MinS32);
544 SkOPASSERT(!windValue || !fDone);
545 fWindValue = windValue;
546 }
547
548 bool sortableTop(SkOpContour* );
549
550 SkOpAngle* toAngle() const {
551 SkASSERT(!final());
552 return fToAngle;
553 }
554
555 int windSum() const {
556 SkASSERT(!final());
557 return fWindSum;
558 }
559
560 int windValue() const {
561 SkOPASSERT(!final());
562 return fWindValue;
563 }
564
565private: // no direct access to internals to avoid treating a span base as a span
566 SkOpSpan* fCoincident; // linked list of spans coincident with this one (may point to itself)
567 SkOpAngle* fToAngle; // points to next angle from span start to end
568 SkOpSpanBase* fNext; // next intersection point
569 int fWindSum; // accumulated from contours surrounding this one.
570 int fOppSum; // for binary operators: the opposite winding sum
571 int fWindValue; // 0 == canceled; 1 == normal; >1 == coincident
572 int fOppValue; // normally 0 -- when binary coincident edges combine, opp value goes here
573 int fTopTTry; // specifies direction and t value to try next
574 bool fDone; // if set, this span to next higher T has been processed
575 bool fAlreadyAdded;
576};
577
578#endif
579