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 "SkPathOpsDebug.h"
11#include "SkPathOpsTypes.h"
12#include "SkPoint.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            SkASSERT(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    SkOpSpanBase* active();
181    void addOpp(SkOpSpanBase* opp);
182
183    void bumpSpanAdds() {
184        ++fSpanAdds;
185    }
186
187    bool chased() const {
188        return fChased;
189    }
190
191    void checkForCollapsedCoincidence();
192
193    const SkOpSpanBase* coinEnd() const {
194        return fCoinEnd;
195    }
196
197    bool collapsed(double s, double e) const;
198    bool contains(const SkOpSpanBase* ) const;
199    const SkOpPtT* contains(const SkOpSegment* ) const;
200
201    bool containsCoinEnd(const SkOpSpanBase* coin) const {
202        SkASSERT(this != coin);
203        const SkOpSpanBase* next = this;
204        while ((next = next->fCoinEnd) != this) {
205            if (next == coin) {
206                return true;
207            }
208        }
209        return false;
210    }
211
212    bool containsCoinEnd(const SkOpSegment* ) const;
213    SkOpContour* contour() const;
214
215    int debugBumpCount() {
216        return SkDEBUGRELEASE(++fCount, -1);
217    }
218
219    int debugID() const {
220        return SkDEBUGRELEASE(fID, -1);
221    }
222
223#if DEBUG_COIN
224    void debugAddOpp(SkPathOpsDebug::GlitchLog* , const SkOpSpanBase* opp) const;
225#endif
226    bool debugAlignedEnd(double t, const SkPoint& pt) const;
227    bool debugAlignedInner() const;
228    const SkOpAngle* debugAngle(int id) const;
229#if DEBUG_COIN
230    void debugCheckForCollapsedCoincidence(SkPathOpsDebug::GlitchLog* ) const;
231#endif
232    const SkOpCoincidence* debugCoincidence() const;
233    bool debugCoinEndLoopCheck() const;
234    SkOpContour* debugContour(int id) const;
235#ifdef SK_DEBUG
236    bool debugDeleted() const { return fDebugDeleted; }
237#endif
238#if DEBUG_COIN
239    void debugInsertCoinEnd(SkPathOpsDebug::GlitchLog* ,
240                            const SkOpSpanBase* ) const;
241    void debugMergeMatches(SkPathOpsDebug::GlitchLog* log,
242                           const SkOpSpanBase* opp) const;
243#endif
244    const SkOpPtT* debugPtT(int id) const;
245    void debugResetCoinT() const;
246    const SkOpSegment* debugSegment(int id) const;
247    void debugSetCoinT(int ) const;
248#ifdef SK_DEBUG
249    void debugSetDeleted() { fDebugDeleted = true; }
250#endif
251    const SkOpSpanBase* debugSpan(int id) const;
252    const SkOpSpan* debugStarter(SkOpSpanBase const** endPtr) const;
253    SkOpGlobalState* globalState() const;
254    void debugValidate() const;
255
256    bool deleted() const {
257        return fPtT.deleted();
258    }
259
260    void dump() const;  // available to testing only
261    void dumpCoin() const;
262    void dumpAll() const;
263    void dumpBase() const;
264    void dumpHead() const;
265
266    bool final() const {
267        return fPtT.fT == 1;
268    }
269
270    SkOpAngle* fromAngle() const {
271        return fFromAngle;
272    }
273
274    void initBase(SkOpSegment* parent, SkOpSpan* prev, double t, const SkPoint& pt);
275
276    // Please keep this in sync with debugInsertCoinEnd()
277    void insertCoinEnd(SkOpSpanBase* coin) {
278        if (containsCoinEnd(coin)) {
279            SkASSERT(coin->containsCoinEnd(this));
280            return;
281        }
282        debugValidate();
283        SkASSERT(this != coin);
284        SkOpSpanBase* coinNext = coin->fCoinEnd;
285        coin->fCoinEnd = this->fCoinEnd;
286        this->fCoinEnd = coinNext;
287        debugValidate();
288    }
289
290    void merge(SkOpSpan* span);
291    void mergeMatches(SkOpSpanBase* opp);
292
293    const SkOpSpan* prev() const {
294        return fPrev;
295    }
296
297    SkOpSpan* prev() {
298        return fPrev;
299    }
300
301    const SkPoint& pt() const {
302        return fPtT.fPt;
303    }
304
305    const SkOpPtT* ptT() const {
306        return &fPtT;
307    }
308
309    SkOpPtT* ptT() {
310        return &fPtT;
311    }
312
313    SkOpSegment* segment() const {
314        return fSegment;
315    }
316
317    void setAligned() {
318        fAligned = true;
319    }
320
321    void setChased(bool chased) {
322        fChased = chased;
323    }
324
325    void setFromAngle(SkOpAngle* angle) {
326        fFromAngle = angle;
327    }
328
329    void setPrev(SkOpSpan* prev) {
330        fPrev = prev;
331    }
332
333    bool simple() const {
334        fPtT.debugValidate();
335        return fPtT.next()->next() == &fPtT;
336    }
337
338    int spanAddsCount() const {
339        return fSpanAdds;
340    }
341
342    const SkOpSpan* starter(const SkOpSpanBase* end) const {
343        const SkOpSpanBase* result = t() < end->t() ? this : end;
344        return result->upCast();
345    }
346
347    SkOpSpan* starter(SkOpSpanBase* end) {
348        SkASSERT(this->segment() == end->segment());
349        SkOpSpanBase* result = t() < end->t() ? this : end;
350        return result->upCast();
351    }
352
353    SkOpSpan* starter(SkOpSpanBase** endPtr) {
354        SkOpSpanBase* end = *endPtr;
355        SkASSERT(this->segment() == end->segment());
356        SkOpSpanBase* result;
357        if (t() < end->t()) {
358            result = this;
359        } else {
360            result = end;
361            *endPtr = this;
362        }
363        return result->upCast();
364    }
365
366    int step(const SkOpSpanBase* end) const {
367        return t() < end->t() ? 1 : -1;
368    }
369
370    double t() const {
371        return fPtT.fT;
372    }
373
374    void unaligned() {
375        fAligned = false;
376    }
377
378    SkOpSpan* upCast() {
379        SkASSERT(!final());
380        return (SkOpSpan*) this;
381    }
382
383    const SkOpSpan* upCast() const {
384        SkOPASSERT(!final());
385        return (const SkOpSpan*) this;
386    }
387
388    SkOpSpan* upCastable() {
389        return final() ? nullptr : upCast();
390    }
391
392    const SkOpSpan* upCastable() const {
393        return final() ? nullptr : upCast();
394    }
395
396private:
397    void alignInner();
398
399protected:  // no direct access to internals to avoid treating a span base as a span
400    SkOpPtT fPtT;  // list of points and t values associated with the start of this span
401    SkOpSegment* fSegment;  // segment that contains this span
402    SkOpSpanBase* fCoinEnd;  // linked list of coincident spans that end here (may point to itself)
403    SkOpAngle* fFromAngle;  // points to next angle from span start to end
404    SkOpSpan* fPrev;  // previous intersection point
405    int fSpanAdds;  // number of times intersections have been added to span
406    bool fAligned;
407    bool fChased;  // set after span has been added to chase array
408    SkDEBUGCODE(int fCount);  // number of pt/t pairs added
409    SkDEBUGCODE(int fID);
410    SkDEBUGCODE(bool fDebugDeleted);  // set when span was merged with another span
411};
412
413class SkOpSpan : public SkOpSpanBase {
414public:
415    bool alreadyAdded() const {
416        if (fAlreadyAdded) {
417            return true;
418        }
419        fAlreadyAdded = true;
420        return false;
421    }
422
423    bool clearCoincident() {
424        SkASSERT(!final());
425        if (fCoincident == this) {
426            return false;
427        }
428        fCoincident = this;
429        return true;
430    }
431
432    int computeWindSum();
433    bool containsCoincidence(const SkOpSegment* ) const;
434
435    bool containsCoincidence(const SkOpSpan* coin) const {
436        SkASSERT(this != coin);
437        const SkOpSpan* next = this;
438        while ((next = next->fCoincident) != this) {
439            if (next == coin) {
440                return true;
441            }
442        }
443        return false;
444    }
445
446    bool debugCoinLoopCheck() const;
447#if DEBUG_COIN
448    void debugInsertCoincidence(SkPathOpsDebug::GlitchLog* , const SkOpSpan* ) const;
449    void debugInsertCoincidence(SkPathOpsDebug::GlitchLog* ,
450                                const SkOpSegment* , bool flipped, bool ordered) const;
451#endif
452    void dumpCoin() const;
453    bool dumpSpan() const;
454
455    bool done() const {
456        SkASSERT(!final());
457        return fDone;
458    }
459
460    void init(SkOpSegment* parent, SkOpSpan* prev, double t, const SkPoint& pt);
461    bool insertCoincidence(const SkOpSegment* , bool flipped, bool ordered);
462
463    // Please keep this in sync with debugInsertCoincidence()
464    void insertCoincidence(SkOpSpan* coin) {
465        if (containsCoincidence(coin)) {
466            SkASSERT(coin->containsCoincidence(this));
467            return;
468        }
469        debugValidate();
470        SkASSERT(this != coin);
471        SkOpSpan* coinNext = coin->fCoincident;
472        coin->fCoincident = this->fCoincident;
473        this->fCoincident = coinNext;
474        debugValidate();
475    }
476
477    bool isCanceled() const {
478        SkASSERT(!final());
479        return fWindValue == 0 && fOppValue == 0;
480    }
481
482    bool isCoincident() const {
483        SkASSERT(!final());
484        return fCoincident != this;
485    }
486
487    SkOpSpanBase* next() const {
488        SkASSERT(!final());
489        return fNext;
490    }
491
492    int oppSum() const {
493        SkASSERT(!final());
494        return fOppSum;
495    }
496
497    int oppValue() const {
498        SkASSERT(!final());
499        return fOppValue;
500    }
501
502    void release(const SkOpPtT* );
503
504    SkOpPtT* setCoinStart(SkOpSpan* oldCoinStart, SkOpSegment* oppSegment);
505
506    void setDone(bool done) {
507        SkASSERT(!final());
508        fDone = done;
509    }
510
511    void setNext(SkOpSpanBase* nextT) {
512        SkASSERT(!final());
513        fNext = nextT;
514    }
515
516    void setOppSum(int oppSum);
517
518    void setOppValue(int oppValue) {
519        SkASSERT(!final());
520        SkASSERT(fOppSum == SK_MinS32);
521        SkOPASSERT(!oppValue || !fDone);
522        fOppValue = oppValue;
523    }
524
525    void setToAngle(SkOpAngle* angle) {
526        SkASSERT(!final());
527        fToAngle = angle;
528    }
529
530    void setWindSum(int windSum);
531
532    void setWindValue(int windValue) {
533        SkASSERT(!final());
534        SkASSERT(windValue >= 0);
535        SkASSERT(fWindSum == SK_MinS32);
536        SkOPASSERT(!windValue || !fDone);
537        fWindValue = windValue;
538    }
539
540    bool sortableTop(SkOpContour* );
541
542    SkOpAngle* toAngle() const {
543        SkASSERT(!final());
544        return fToAngle;
545    }
546
547    int windSum() const {
548        SkASSERT(!final());
549        return fWindSum;
550    }
551
552    int windValue() const {
553        SkOPASSERT(!final());
554        return fWindValue;
555    }
556
557private:  // no direct access to internals to avoid treating a span base as a span
558    SkOpSpan* fCoincident;  // linked list of spans coincident with this one (may point to itself)
559    SkOpAngle* fToAngle;  // points to next angle from span start to end
560    SkOpSpanBase* fNext;  // next intersection point
561    int fWindSum;  // accumulated from contours surrounding this one.
562    int fOppSum;  // for binary operators: the opposite winding sum
563    int fWindValue;  // 0 == canceled; 1 == normal; >1 == coincident
564    int fOppValue;  // normally 0 -- when binary coincident edges combine, opp value goes here
565    int fTopTTry; // specifies direction and t value to try next
566    bool fDone;  // if set, this span to next higher T has been processed
567    mutable bool fAlreadyAdded;
568};
569
570#endif
571