xref: /third_party/skia/src/pathops/SkOpSpan.h (revision cb93a386) 
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