SkOpSpan.h revision 624637cc8ec22c000409704d0b403ac1b81ad4b0 
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 "SkPoint.h"
12
13class SkChunkAlloc;
14struct SkOpAngle;
15class SkOpContour;
16class SkOpGlobalState;
17class SkOpSegment;
18class SkOpSpanBase;
19class SkOpSpan;
20
21// subset of op span used by terminal span (when t is equal to one)
22class SkOpPtT {
23public:
24    enum {
25        kIsAlias = 1,
26        kIsDuplicate = 1
27    };
28
29    void addOpp(SkOpPtT* opp) {
30        // find the fOpp ptr to opp
31        SkOpPtT* oppPrev = opp->fNext;
32        if (oppPrev == this) {
33            return;
34        }
35        while (oppPrev->fNext != opp) {
36            oppPrev = oppPrev->fNext;
37             if (oppPrev == this) {
38                 return;
39             }
40        }
41
42        SkOpPtT* oldNext = this->fNext;
43        SkASSERT(this != opp);
44        this->fNext = opp;
45        SkASSERT(oppPrev != oldNext);
46        oppPrev->fNext = oldNext;
47    }
48
49    bool alias() const;
50    SkOpContour* contour() const;
51
52    int debugID() const {
53        return SkDEBUGRELEASE(fID, -1);
54    }
55
56    const SkOpAngle* debugAngle(int id) const;
57    SkOpContour* debugContour(int id);
58    int debugLoopLimit(bool report) const;
59    bool debugMatchID(int id) const;
60    const SkOpPtT* debugPtT(int id) const;
61    const SkOpSegment* debugSegment(int id) const;
62    const SkOpSpanBase* debugSpan(int id) const;
63    SkOpGlobalState* globalState() const;
64    void debugValidate() const;
65
66    bool deleted() const {
67        return fDeleted;
68    }
69
70    bool duplicate() const {
71        return fDuplicatePt;
72    }
73
74    void dump() const;  // available to testing only
75    void dumpAll() const;
76    void dumpBase() const;
77
78    void init(SkOpSpanBase* , double t, const SkPoint& , bool dup);
79
80    void insert(SkOpPtT* span) {
81        SkASSERT(span != this);
82        span->fNext = fNext;
83        fNext = span;
84    }
85
86    const SkOpPtT* next() const {
87        return fNext;
88    }
89
90    SkOpPtT* next() {
91        return fNext;
92    }
93
94    bool onEnd() const;
95    SkOpPtT* prev();
96    SkOpPtT* remove();
97    void removeNext(SkOpPtT* kept);
98
99    const SkOpSegment* segment() const;
100    SkOpSegment* segment();
101
102    void setDeleted() {
103        SkASSERT(!fDeleted);
104        fDeleted = true;
105    }
106
107    const SkOpSpanBase* span() const {
108        return fSpan;
109    }
110
111    SkOpSpanBase* span() {
112        return fSpan;
113    }
114
115    double fT;
116    SkPoint fPt;   // cache of point value at this t
117protected:
118    SkOpSpanBase* fSpan;  // contains winding data
119    SkOpPtT* fNext;  // intersection on opposite curve or alias on this curve
120    bool fDeleted;  // set if removed from span list
121    bool fDuplicatePt;  // set if identical pt is somewhere in the next loop
122    SkDEBUGCODE(int fID);
123};
124
125class SkOpSpanBase {
126public:
127    void align();
128
129    bool aligned() const {
130        return fAligned;
131    }
132
133    void alignEnd(double t, const SkPoint& pt);
134
135    void bumpSpanAdds() {
136        ++fSpanAdds;
137    }
138
139    bool chased() const {
140        return fChased;
141    }
142
143    void clearCoinEnd() {
144        SkASSERT(fCoinEnd != this);
145        fCoinEnd = this;
146    }
147
148    const SkOpSpanBase* coinEnd() const {
149        return fCoinEnd;
150    }
151
152    bool contains(const SkOpSpanBase* ) const;
153    SkOpPtT* contains(const SkOpSegment* );
154
155    bool containsCoinEnd(const SkOpSpanBase* coin) const {
156        SkASSERT(this != coin);
157        const SkOpSpanBase* next = this;
158        while ((next = next->fCoinEnd) != this) {
159            if (next == coin) {
160                return true;
161            }
162        }
163        return false;
164    }
165
166    bool containsCoinEnd(const SkOpSegment* ) const;
167    SkOpContour* contour() const;
168
169    int debugBumpCount() {
170        return SkDEBUGRELEASE(++fCount, -1);
171    }
172
173    int debugID() const {
174        return SkDEBUGRELEASE(fID, -1);
175    }
176
177    const SkOpAngle* debugAngle(int id) const;
178    bool debugCoinEndLoopCheck() const;
179    SkOpContour* debugContour(int id);
180    const SkOpPtT* debugPtT(int id) const;
181    const SkOpSegment* debugSegment(int id) const;
182    const SkOpSpanBase* debugSpan(int id) const;
183    SkOpGlobalState* globalState() const;
184    void debugValidate() const;
185
186    bool deleted() const {
187        return fPtT.deleted();
188    }
189
190    void dump() const;  // available to testing only
191    void dumpCoin() const;
192    void dumpAll() const;
193    void dumpBase() const;
194
195    bool final() const {
196        return fPtT.fT == 1;
197    }
198
199    SkOpAngle* fromAngle() const {
200        return fFromAngle;
201    }
202
203    void initBase(SkOpSegment* parent, SkOpSpan* prev, double t, const SkPoint& pt);
204
205    void insertCoinEnd(SkOpSpanBase* coin) {
206        if (containsCoinEnd(coin)) {
207            SkASSERT(coin->containsCoinEnd(this));
208            return;
209        }
210        debugValidate();
211        SkASSERT(this != coin);
212        SkOpSpanBase* coinNext = coin->fCoinEnd;
213        coin->fCoinEnd = this->fCoinEnd;
214        this->fCoinEnd = coinNext;
215        debugValidate();
216    }
217
218    void merge(SkOpSpan* span);
219
220    SkOpSpan* prev() const {
221        return fPrev;
222    }
223
224    const SkPoint& pt() const {
225        return fPtT.fPt;
226    }
227
228    const SkOpPtT* ptT() const {
229        return &fPtT;
230    }
231
232    SkOpPtT* ptT() {
233        return &fPtT;
234    }
235
236    SkOpSegment* segment() const {
237        return fSegment;
238    }
239
240    void setChased(bool chased) {
241        fChased = chased;
242    }
243
244    SkOpPtT* setCoinEnd(SkOpSpanBase* oldCoinEnd, SkOpSegment* oppSegment);
245
246    void setFromAngle(SkOpAngle* angle) {
247        fFromAngle = angle;
248    }
249
250    void setPrev(SkOpSpan* prev) {
251        fPrev = prev;
252    }
253
254    bool simple() const {
255        fPtT.debugValidate();
256        return fPtT.next()->next() == &fPtT;
257    }
258
259    int spanAddsCount() const {
260        return fSpanAdds;
261    }
262
263    const SkOpSpan* starter(const SkOpSpanBase* end) const {
264        const SkOpSpanBase* result = t() < end->t() ? this : end;
265        return result->upCast();
266    }
267
268    SkOpSpan* starter(SkOpSpanBase* end) {
269        SkASSERT(this->segment() == end->segment());
270        SkOpSpanBase* result = t() < end->t() ? this : end;
271        return result->upCast();
272    }
273
274    SkOpSpan* starter(SkOpSpanBase** endPtr) {
275        SkOpSpanBase* end = *endPtr;
276        SkASSERT(this->segment() == end->segment());
277        SkOpSpanBase* result;
278        if (t() < end->t()) {
279            result = this;
280        } else {
281            result = end;
282            *endPtr = this;
283        }
284        return result->upCast();
285    }
286
287    int step(const SkOpSpanBase* end) const {
288        return t() < end->t() ? 1 : -1;
289    }
290
291    double t() const {
292        return fPtT.fT;
293    }
294
295    void unaligned() {
296        fAligned = false;
297    }
298
299    SkOpSpan* upCast() {
300        SkASSERT(!final());
301        return (SkOpSpan*) this;
302    }
303
304    const SkOpSpan* upCast() const {
305        SkASSERT(!final());
306        return (const SkOpSpan*) this;
307    }
308
309    SkOpSpan* upCastable() {
310        return final() ? NULL : upCast();
311    }
312
313    const SkOpSpan* upCastable() const {
314        return final() ? NULL : upCast();
315    }
316
317private:
318    void alignInner();
319
320protected:  // no direct access to internals to avoid treating a span base as a span
321    SkOpPtT fPtT;  // list of points and t values associated with the start of this span
322    SkOpSegment* fSegment;  // segment that contains this span
323    SkOpSpanBase* fCoinEnd;  // linked list of coincident spans that end here (may point to itself)
324    SkOpAngle* fFromAngle;  // points to next angle from span start to end
325    SkOpSpan* fPrev;  // previous intersection point
326    int fSpanAdds;  // number of times intersections have been added to span
327    bool fAligned;
328    bool fChased;  // set after span has been added to chase array
329    SkDEBUGCODE(int fCount);  // number of pt/t pairs added
330    SkDEBUGCODE(int fID);
331};
332
333class SkOpSpan : public SkOpSpanBase {
334public:
335    bool clearCoincident() {
336        SkASSERT(!final());
337        if (fCoincident == this) {
338            return false;
339        }
340        fCoincident = this;
341        return true;
342    }
343
344    bool containsCoincidence(const SkOpSegment* ) const;
345
346    bool containsCoincidence(const SkOpSpan* coin) const {
347        SkASSERT(this != coin);
348        const SkOpSpan* next = this;
349        while ((next = next->fCoincident) != this) {
350            if (next == coin) {
351                return true;
352            }
353        }
354        return false;
355    }
356
357    bool debugCoinLoopCheck() const;
358    void detach(SkOpPtT* );
359
360    bool done() const {
361        SkASSERT(!final());
362        return fDone;
363    }
364
365    void dumpCoin() const;
366    bool dumpSpan() const;
367    void init(SkOpSegment* parent, SkOpSpan* prev, double t, const SkPoint& pt);
368
369    void insertCoincidence(SkOpSpan* coin) {
370        if (containsCoincidence(coin)) {
371            SkASSERT(coin->containsCoincidence(this));
372            return;
373        }
374        debugValidate();
375        SkASSERT(this != coin);
376        SkOpSpan* coinNext = coin->fCoincident;
377        coin->fCoincident = this->fCoincident;
378        this->fCoincident = coinNext;
379        debugValidate();
380    }
381
382    bool isCanceled() const {
383        SkASSERT(!final());
384        return fWindValue == 0 && fOppValue == 0;
385    }
386
387    bool isCoincident() const {
388        SkASSERT(!final());
389        return fCoincident != this;
390    }
391
392    SkOpSpanBase* next() const {
393        SkASSERT(!final());
394        return fNext;
395    }
396
397    int oppSum() const {
398        SkASSERT(!final());
399        return fOppSum;
400    }
401
402    int oppValue() const {
403        SkASSERT(!final());
404        return fOppValue;
405    }
406
407    SkOpPtT* setCoinStart(SkOpSpan* oldCoinStart, SkOpSegment* oppSegment);
408
409    void setDone(bool done) {
410        SkASSERT(!final());
411        fDone = done;
412    }
413
414    void setNext(SkOpSpanBase* nextT) {
415        SkASSERT(!final());
416        fNext = nextT;
417    }
418
419    void setOppSum(int oppSum);
420
421    void setOppValue(int oppValue) {
422        SkASSERT(!final());
423        SkASSERT(fOppSum == SK_MinS32);
424        fOppValue = oppValue;
425    }
426
427    void setToAngle(SkOpAngle* angle) {
428        SkASSERT(!final());
429        fToAngle = angle;
430    }
431
432    void setWindSum(int windSum);
433
434    void setWindValue(int windValue) {
435        SkASSERT(!final());
436        SkASSERT(windValue >= 0);
437        SkASSERT(fWindSum == SK_MinS32);
438        fWindValue = windValue;
439    }
440
441    bool sortableTop(SkOpContour* );
442
443    SkOpAngle* toAngle() const {
444        SkASSERT(!final());
445        return fToAngle;
446    }
447
448    int windSum() const {
449        SkASSERT(!final());
450        return fWindSum;
451    }
452
453    int windValue() const {
454        SkASSERT(!final());
455        return fWindValue;
456    }
457
458private:  // no direct access to internals to avoid treating a span base as a span
459    SkOpSpan* fCoincident;  // linked list of spans coincident with this one (may point to itself)
460    SkOpAngle* fToAngle;  // points to next angle from span start to end
461    SkOpSpanBase* fNext;  // next intersection point
462    int fWindSum;  // accumulated from contours surrounding this one.
463    int fOppSum;  // for binary operators: the opposite winding sum
464    int fWindValue;  // 0 == canceled; 1 == normal; >1 == coincident
465    int fOppValue;  // normally 0 -- when binary coincident edges combine, opp value goes here
466    int fTopTTry; // specifies direction and t value to try next
467    bool fDone;  // if set, this span to next higher T has been processed
468};
469
470#endif
471