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