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