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 
13 class SkChunkAlloc;
14 struct SkOpAngle;
15 class SkOpContour;
16 class SkOpGlobalState;
17 class SkOpSegment;
18 class SkOpSpanBase;
19 class SkOpSpan;
20 
21 // subset of op span used by terminal span (when t is equal to one)
22 class SkOpPtT {
23 public:
24     enum {
25         kIsAlias = 1,
26         kIsDuplicate = 1
27     };
28 
addOpp(SkOpPtT * opp)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 
debugID()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 
deleted()66     bool deleted() const {
67         return fDeleted;
68     }
69 
duplicate()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 
insert(SkOpPtT * span)80     void insert(SkOpPtT* span) {
81         SkASSERT(span != this);
82         span->fNext = fNext;
83         fNext = span;
84     }
85 
next()86     const SkOpPtT* next() const {
87         return fNext;
88     }
89 
next()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 
setDeleted()102     void setDeleted() {
103         SkASSERT(!fDeleted);
104         fDeleted = true;
105     }
106 
span()107     const SkOpSpanBase* span() const {
108         return fSpan;
109     }
110 
span()111     SkOpSpanBase* span() {
112         return fSpan;
113     }
114 
115     double fT;
116     SkPoint fPt;   // cache of point value at this t
117 protected:
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 
125 class SkOpSpanBase {
126 public:
127     void align();
128 
aligned()129     bool aligned() const {
130         return fAligned;
131     }
132 
133     void alignEnd(double t, const SkPoint& pt);
134 
bumpSpanAdds()135     void bumpSpanAdds() {
136         ++fSpanAdds;
137     }
138 
chased()139     bool chased() const {
140         return fChased;
141     }
142 
clearCoinEnd()143     void clearCoinEnd() {
144         SkASSERT(fCoinEnd != this);
145         fCoinEnd = this;
146     }
147 
coinEnd()148     const SkOpSpanBase* coinEnd() const {
149         return fCoinEnd;
150     }
151 
152     bool contains(const SkOpSpanBase* ) const;
153     SkOpPtT* contains(const SkOpSegment* );
154 
containsCoinEnd(const SkOpSpanBase * coin)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 
debugBumpCount()169     int debugBumpCount() {
170         return SkDEBUGRELEASE(++fCount, -1);
171     }
172 
debugID()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 
deleted()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 
final()195     bool final() const {
196         return fPtT.fT == 1;
197     }
198 
fromAngle()199     SkOpAngle* fromAngle() const {
200         return fFromAngle;
201     }
202 
203     void initBase(SkOpSegment* parent, SkOpSpan* prev, double t, const SkPoint& pt);
204 
insertCoinEnd(SkOpSpanBase * coin)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 
prev()220     SkOpSpan* prev() const {
221         return fPrev;
222     }
223 
pt()224     const SkPoint& pt() const {
225         return fPtT.fPt;
226     }
227 
ptT()228     const SkOpPtT* ptT() const {
229         return &fPtT;
230     }
231 
ptT()232     SkOpPtT* ptT() {
233         return &fPtT;
234     }
235 
segment()236     SkOpSegment* segment() const {
237         return fSegment;
238     }
239 
setChased(bool chased)240     void setChased(bool chased) {
241         fChased = chased;
242     }
243 
244     SkOpPtT* setCoinEnd(SkOpSpanBase* oldCoinEnd, SkOpSegment* oppSegment);
245 
setFromAngle(SkOpAngle * angle)246     void setFromAngle(SkOpAngle* angle) {
247         fFromAngle = angle;
248     }
249 
setPrev(SkOpSpan * prev)250     void setPrev(SkOpSpan* prev) {
251         fPrev = prev;
252     }
253 
simple()254     bool simple() const {
255         fPtT.debugValidate();
256         return fPtT.next()->next() == &fPtT;
257     }
258 
spanAddsCount()259     int spanAddsCount() const {
260         return fSpanAdds;
261     }
262 
starter(const SkOpSpanBase * end)263     const SkOpSpan* starter(const SkOpSpanBase* end) const {
264         const SkOpSpanBase* result = t() < end->t() ? this : end;
265         return result->upCast();
266     }
267 
starter(SkOpSpanBase * end)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 
starter(SkOpSpanBase ** endPtr)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 
step(const SkOpSpanBase * end)287     int step(const SkOpSpanBase* end) const {
288         return t() < end->t() ? 1 : -1;
289     }
290 
t()291     double t() const {
292         return fPtT.fT;
293     }
294 
unaligned()295     void unaligned() {
296         fAligned = false;
297     }
298 
upCast()299     SkOpSpan* upCast() {
300         SkASSERT(!final());
301         return (SkOpSpan*) this;
302     }
303 
upCast()304     const SkOpSpan* upCast() const {
305         SkASSERT(!final());
306         return (const SkOpSpan*) this;
307     }
308 
upCastable()309     SkOpSpan* upCastable() {
310         return final() ? NULL : upCast();
311     }
312 
upCastable()313     const SkOpSpan* upCastable() const {
314         return final() ? NULL : upCast();
315     }
316 
317 private:
318     void alignInner();
319 
320 protected:  // 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 
333 class SkOpSpan : public SkOpSpanBase {
334 public:
clearCoincident()335     bool clearCoincident() {
336         SkASSERT(!final());
337         if (fCoincident == this) {
338             return false;
339         }
340         fCoincident = this;
341         return true;
342     }
343 
344     int computeWindSum();
345     bool containsCoincidence(const SkOpSegment* ) const;
346 
containsCoincidence(const SkOpSpan * coin)347     bool containsCoincidence(const SkOpSpan* coin) const {
348         SkASSERT(this != coin);
349         const SkOpSpan* next = this;
350         while ((next = next->fCoincident) != this) {
351             if (next == coin) {
352                 return true;
353             }
354         }
355         return false;
356     }
357 
358     bool debugCoinLoopCheck() const;
359     void detach(SkOpPtT* );
360 
done()361     bool done() const {
362         SkASSERT(!final());
363         return fDone;
364     }
365 
366     void dumpCoin() const;
367     bool dumpSpan() const;
368     void init(SkOpSegment* parent, SkOpSpan* prev, double t, const SkPoint& pt);
369 
insertCoincidence(SkOpSpan * coin)370     void insertCoincidence(SkOpSpan* coin) {
371         if (containsCoincidence(coin)) {
372             SkASSERT(coin->containsCoincidence(this));
373             return;
374         }
375         debugValidate();
376         SkASSERT(this != coin);
377         SkOpSpan* coinNext = coin->fCoincident;
378         coin->fCoincident = this->fCoincident;
379         this->fCoincident = coinNext;
380         debugValidate();
381     }
382 
isCanceled()383     bool isCanceled() const {
384         SkASSERT(!final());
385         return fWindValue == 0 && fOppValue == 0;
386     }
387 
isCoincident()388     bool isCoincident() const {
389         SkASSERT(!final());
390         return fCoincident != this;
391     }
392 
next()393     SkOpSpanBase* next() const {
394         SkASSERT(!final());
395         return fNext;
396     }
397 
oppSum()398     int oppSum() const {
399         SkASSERT(!final());
400         return fOppSum;
401     }
402 
oppValue()403     int oppValue() const {
404         SkASSERT(!final());
405         return fOppValue;
406     }
407 
408     SkOpPtT* setCoinStart(SkOpSpan* oldCoinStart, SkOpSegment* oppSegment);
409 
setDone(bool done)410     void setDone(bool done) {
411         SkASSERT(!final());
412         fDone = done;
413     }
414 
setNext(SkOpSpanBase * nextT)415     void setNext(SkOpSpanBase* nextT) {
416         SkASSERT(!final());
417         fNext = nextT;
418     }
419 
420     void setOppSum(int oppSum);
421 
setOppValue(int oppValue)422     void setOppValue(int oppValue) {
423         SkASSERT(!final());
424         SkASSERT(fOppSum == SK_MinS32);
425         fOppValue = oppValue;
426     }
427 
setToAngle(SkOpAngle * angle)428     void setToAngle(SkOpAngle* angle) {
429         SkASSERT(!final());
430         fToAngle = angle;
431     }
432 
433     void setWindSum(int windSum);
434 
setWindValue(int windValue)435     void setWindValue(int windValue) {
436         SkASSERT(!final());
437         SkASSERT(windValue >= 0);
438         SkASSERT(fWindSum == SK_MinS32);
439         fWindValue = windValue;
440     }
441 
442     bool sortableTop(SkOpContour* );
443 
toAngle()444     SkOpAngle* toAngle() const {
445         SkASSERT(!final());
446         return fToAngle;
447     }
448 
windSum()449     int windSum() const {
450         SkASSERT(!final());
451         return fWindSum;
452     }
453 
windValue()454     int windValue() const {
455         SkASSERT(!final());
456         return fWindValue;
457     }
458 
459 private:  // no direct access to internals to avoid treating a span base as a span
460     SkOpSpan* fCoincident;  // linked list of spans coincident with this one (may point to itself)
461     SkOpAngle* fToAngle;  // points to next angle from span start to end
462     SkOpSpanBase* fNext;  // next intersection point
463     int fWindSum;  // accumulated from contours surrounding this one.
464     int fOppSum;  // for binary operators: the opposite winding sum
465     int fWindValue;  // 0 == canceled; 1 == normal; >1 == coincident
466     int fOppValue;  // normally 0 -- when binary coincident edges combine, opp value goes here
467     int fTopTTry; // specifies direction and t value to try next
468     bool fDone;  // if set, this span to next higher T has been processed
469 };
470 
471 #endif
472