• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright 2013 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 SkOpCoincidence_DEFINED
8 #define SkOpCoincidence_DEFINED
9 
10 #include "include/private/SkTDArray.h"
11 #include "src/core/SkArenaAlloc.h"
12 #include "src/pathops/SkOpSpan.h"
13 #include "src/pathops/SkPathOpsTypes.h"
14 
15 class SkOpPtT;
16 class SkOpSpanBase;
17 
18 class SkCoincidentSpans {
19 public:
20     const SkOpPtT* coinPtTEnd() const;
21     const SkOpPtT* coinPtTStart() const;
22 
23     // These return non-const pointers so that, as copies, they can be added
24     // to a new span pair
coinPtTEndWritable()25     SkOpPtT* coinPtTEndWritable() const { return const_cast<SkOpPtT*>(fCoinPtTEnd); }
coinPtTStartWritable()26     SkOpPtT* coinPtTStartWritable() const { return const_cast<SkOpPtT*>(fCoinPtTStart); }
27 
28     bool collapsed(const SkOpPtT* ) const;
29     bool contains(const SkOpPtT* s, const SkOpPtT* e) const;
30     void correctEnds();
31     void correctOneEnd(const SkOpPtT* (SkCoincidentSpans::* getEnd)() const,
32                        void (SkCoincidentSpans::* setEnd)(const SkOpPtT* ptT) );
33 
34 #if DEBUG_COIN
35     void debugCorrectEnds(SkPathOpsDebug::GlitchLog* log) const;
36     void debugCorrectOneEnd(SkPathOpsDebug::GlitchLog* log,
37                             const SkOpPtT* (SkCoincidentSpans::* getEnd)() const,
38                             void (SkCoincidentSpans::* setEnd)(const SkOpPtT* ptT) const) const;
39     bool debugExpand(SkPathOpsDebug::GlitchLog* log) const;
40 #endif
41 
debugID()42     const char* debugID() const {
43 #if DEBUG_COIN
44         return fGlobalState->debugCoinDictEntry().fFunctionName;
45 #else
46         return nullptr;
47 #endif
48     }
49 
50     void debugShow() const;
51 #ifdef SK_DEBUG
52     void debugStartCheck(const SkOpSpanBase* outer, const SkOpSpanBase* over,
53             const SkOpGlobalState* debugState) const;
54 #endif
55     void dump() const;
56     bool expand();
57     bool extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
58                 const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd);
flipped()59     bool flipped() const { return fOppPtTStart->fT > fOppPtTEnd->fT; }
SkDEBUGCODE(SkOpGlobalState * globalState (){ return fGlobalState; })60     SkDEBUGCODE(SkOpGlobalState* globalState() { return fGlobalState; })
61 
62     void init(SkDEBUGCODE(SkOpGlobalState* globalState)) {
63         sk_bzero(this, sizeof(*this));
64         SkDEBUGCODE(fGlobalState = globalState);
65     }
66 
next()67     SkCoincidentSpans* next() { return fNext; }
next()68     const SkCoincidentSpans* next() const { return fNext; }
nextPtr()69     SkCoincidentSpans** nextPtr() { return &fNext; }
70     const SkOpPtT* oppPtTStart() const;
71     const SkOpPtT* oppPtTEnd() const;
72     // These return non-const pointers so that, as copies, they can be added
73     // to a new span pair
oppPtTStartWritable()74     SkOpPtT* oppPtTStartWritable() const { return const_cast<SkOpPtT*>(fOppPtTStart); }
oppPtTEndWritable()75     SkOpPtT* oppPtTEndWritable() const { return const_cast<SkOpPtT*>(fOppPtTEnd); }
76     bool ordered(bool* result) const;
77 
78     void set(SkCoincidentSpans* next, const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
79             const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd);
80 
setCoinPtTEnd(const SkOpPtT * ptT)81     void setCoinPtTEnd(const SkOpPtT* ptT) {
82         SkOPASSERT(ptT == ptT->span()->ptT());
83         SkOPASSERT(!fCoinPtTStart || ptT->fT != fCoinPtTStart->fT);
84         SkASSERT(!fCoinPtTStart || fCoinPtTStart->segment() == ptT->segment());
85         fCoinPtTEnd = ptT;
86         ptT->setCoincident();
87     }
88 
setCoinPtTStart(const SkOpPtT * ptT)89     void setCoinPtTStart(const SkOpPtT* ptT) {
90         SkOPASSERT(ptT == ptT->span()->ptT());
91         SkOPASSERT(!fCoinPtTEnd || ptT->fT != fCoinPtTEnd->fT);
92         SkASSERT(!fCoinPtTEnd || fCoinPtTEnd->segment() == ptT->segment());
93         fCoinPtTStart = ptT;
94         ptT->setCoincident();
95     }
96 
setEnds(const SkOpPtT * coinPtTEnd,const SkOpPtT * oppPtTEnd)97     void setEnds(const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTEnd) {
98         this->setCoinPtTEnd(coinPtTEnd);
99         this->setOppPtTEnd(oppPtTEnd);
100     }
101 
setOppPtTEnd(const SkOpPtT * ptT)102     void setOppPtTEnd(const SkOpPtT* ptT) {
103         SkOPASSERT(ptT == ptT->span()->ptT());
104         SkOPASSERT(!fOppPtTStart || ptT->fT != fOppPtTStart->fT);
105         SkASSERT(!fOppPtTStart || fOppPtTStart->segment() == ptT->segment());
106         fOppPtTEnd = ptT;
107         ptT->setCoincident();
108     }
109 
setOppPtTStart(const SkOpPtT * ptT)110     void setOppPtTStart(const SkOpPtT* ptT) {
111         SkOPASSERT(ptT == ptT->span()->ptT());
112         SkOPASSERT(!fOppPtTEnd || ptT->fT != fOppPtTEnd->fT);
113         SkASSERT(!fOppPtTEnd || fOppPtTEnd->segment() == ptT->segment());
114         fOppPtTStart = ptT;
115         ptT->setCoincident();
116     }
117 
setStarts(const SkOpPtT * coinPtTStart,const SkOpPtT * oppPtTStart)118     void setStarts(const SkOpPtT* coinPtTStart, const SkOpPtT* oppPtTStart) {
119         this->setCoinPtTStart(coinPtTStart);
120         this->setOppPtTStart(oppPtTStart);
121     }
122 
setNext(SkCoincidentSpans * next)123     void setNext(SkCoincidentSpans* next) { fNext = next; }
124 
125 private:
126     SkCoincidentSpans* fNext;
127     const SkOpPtT* fCoinPtTStart;
128     const SkOpPtT* fCoinPtTEnd;
129     const SkOpPtT* fOppPtTStart;
130     const SkOpPtT* fOppPtTEnd;
131     SkDEBUGCODE(SkOpGlobalState* fGlobalState);
132 };
133 
134 class SkOpCoincidence {
135 public:
SkOpCoincidence(SkOpGlobalState * globalState)136     SkOpCoincidence(SkOpGlobalState* globalState)
137         : fHead(nullptr)
138         , fTop(nullptr)
139         , fGlobalState(globalState)
140         , fContinue(false)
141         , fSpanDeleted(false)
142         , fPtAllocated(false)
143         , fCoinExtended(false)
144         , fSpanMerged(false) {
145         globalState->setCoincidence(this);
146     }
147 
148     void add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart,
149              SkOpPtT* oppPtTEnd);
150     bool addEndMovedSpans(DEBUG_COIN_DECLARE_ONLY_PARAMS());
151     bool addExpanded(DEBUG_COIN_DECLARE_ONLY_PARAMS());
152     bool addMissing(bool* added  DEBUG_COIN_DECLARE_PARAMS());
153     bool apply(DEBUG_COIN_DECLARE_ONLY_PARAMS());
154     bool contains(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
155                   const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) const;
156     void correctEnds(DEBUG_COIN_DECLARE_ONLY_PARAMS());
157 
158 #if DEBUG_COIN
159     void debugAddEndMovedSpans(SkPathOpsDebug::GlitchLog* log) const;
160     void debugAddExpanded(SkPathOpsDebug::GlitchLog* ) const;
161     void debugAddMissing(SkPathOpsDebug::GlitchLog* , bool* added) const;
162     void debugAddOrOverlap(SkPathOpsDebug::GlitchLog* log,
163                            const SkOpSegment* coinSeg, const SkOpSegment* oppSeg,
164                            double coinTs, double coinTe, double oppTs, double oppTe,
165                            bool* added) const;
166 #endif
167 
debugAngle(int id)168     const SkOpAngle* debugAngle(int id) const {
169         return SkDEBUGRELEASE(fGlobalState->debugAngle(id), nullptr);
170     }
171 
172     void debugCheckBetween() const;
173 
174 #if DEBUG_COIN
175     void debugCheckValid(SkPathOpsDebug::GlitchLog* log) const;
176 #endif
177 
debugContour(int id)178     SkOpContour* debugContour(int id) const {
179         return SkDEBUGRELEASE(fGlobalState->debugContour(id), nullptr);
180     }
181 
182 #if DEBUG_COIN
183     void debugCorrectEnds(SkPathOpsDebug::GlitchLog* log) const;
184     bool debugExpand(SkPathOpsDebug::GlitchLog* ) const;
185     void debugMark(SkPathOpsDebug::GlitchLog* ) const;
186     void debugMarkCollapsed(SkPathOpsDebug::GlitchLog* ,
187                             const SkCoincidentSpans* coin, const SkOpPtT* test) const;
188     void debugMarkCollapsed(SkPathOpsDebug::GlitchLog* , const SkOpPtT* test) const;
189 #endif
190 
debugPtT(int id)191     const SkOpPtT* debugPtT(int id) const {
192         return SkDEBUGRELEASE(fGlobalState->debugPtT(id), nullptr);
193     }
194 
debugSegment(int id)195     const SkOpSegment* debugSegment(int id) const {
196         return SkDEBUGRELEASE(fGlobalState->debugSegment(id), nullptr);
197     }
198 
199 #if DEBUG_COIN
200     void debugRelease(SkPathOpsDebug::GlitchLog* , const SkCoincidentSpans* ,
201                       const SkCoincidentSpans* ) const;
202     void debugRelease(SkPathOpsDebug::GlitchLog* , const SkOpSegment* ) const;
203 #endif
204     void debugShowCoincidence() const;
205 
debugSpan(int id)206     const SkOpSpanBase* debugSpan(int id) const {
207         return SkDEBUGRELEASE(fGlobalState->debugSpan(id), nullptr);
208     }
209 
210     void debugValidate() const;
211     void dump() const;
212     bool expand(DEBUG_COIN_DECLARE_ONLY_PARAMS());
213     bool extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart,
214                 const SkOpPtT* oppPtTEnd);
215     bool findOverlaps(SkOpCoincidence*  DEBUG_COIN_DECLARE_PARAMS()) const;
216     void fixUp(SkOpPtT* deleted, const SkOpPtT* kept);
217 
globalState()218     SkOpGlobalState* globalState() {
219         return fGlobalState;
220     }
221 
globalState()222     const SkOpGlobalState* globalState() const {
223         return fGlobalState;
224     }
225 
isEmpty()226     bool isEmpty() const {
227         return !fHead && !fTop;
228     }
229 
230     bool mark(DEBUG_COIN_DECLARE_ONLY_PARAMS());
231     void markCollapsed(SkOpPtT* );
232 
Ordered(const SkOpPtT * coinPtTStart,const SkOpPtT * oppPtTStart)233     static bool Ordered(const SkOpPtT* coinPtTStart, const SkOpPtT* oppPtTStart) {
234       return Ordered(coinPtTStart->segment(), oppPtTStart->segment());
235     }
236 
237     static bool Ordered(const SkOpSegment* coin, const SkOpSegment* opp);
238     void release(const SkOpSegment* );
239     void releaseDeleted();
240 
241 private:
add(const SkOpPtT * coinPtTStart,const SkOpPtT * coinPtTEnd,const SkOpPtT * oppPtTStart,const SkOpPtT * oppPtTEnd)242     void add(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart,
243              const SkOpPtT* oppPtTEnd) {
244         this->add(const_cast<SkOpPtT*>(coinPtTStart), const_cast<SkOpPtT*>(coinPtTEnd),
245             const_cast<SkOpPtT*>(oppPtTStart), const_cast<SkOpPtT*>(oppPtTEnd));
246     }
247 
248     bool addEndMovedSpans(const SkOpSpan* base, const SkOpSpanBase* testSpan);
249     bool addEndMovedSpans(const SkOpPtT* ptT);
250 
251     bool addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over2s,
252                       double tStart, double tEnd, SkOpSegment* coinSeg, SkOpSegment* oppSeg,
253                       bool* added
254                       SkDEBUGPARAMS(const SkOpPtT* over1e) SkDEBUGPARAMS(const SkOpPtT* over2e));
255     bool addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg,
256                       double coinTs, double coinTe, double oppTs, double oppTe, bool* added);
257     bool addOverlap(const SkOpSegment* seg1, const SkOpSegment* seg1o,
258                     const SkOpSegment* seg2, const SkOpSegment* seg2o,
259                     const SkOpPtT* overS, const SkOpPtT* overE);
260     bool checkOverlap(SkCoincidentSpans* check,
261                       const SkOpSegment* coinSeg, const SkOpSegment* oppSeg,
262                       double coinTs, double coinTe, double oppTs, double oppTe,
263                       SkTDArray<SkCoincidentSpans*>* overlaps) const;
264     bool contains(const SkOpSegment* seg, const SkOpSegment* opp, double oppT) const;
265     bool contains(const SkCoincidentSpans* coin, const SkOpSegment* seg,
266                   const SkOpSegment* opp, double oppT) const;
267 #if DEBUG_COIN
268     void debugAddIfMissing(SkPathOpsDebug::GlitchLog* ,
269                            const SkCoincidentSpans* outer, const SkOpPtT* over1s,
270                            const SkOpPtT* over1e) const;
271     void debugAddIfMissing(SkPathOpsDebug::GlitchLog* ,
272                            const SkOpPtT* over1s, const SkOpPtT* over2s,
273                            double tStart, double tEnd,
274                            const SkOpSegment* coinSeg, const SkOpSegment* oppSeg, bool* added,
275                            const SkOpPtT* over1e, const SkOpPtT* over2e) const;
276     void debugAddEndMovedSpans(SkPathOpsDebug::GlitchLog* ,
277                                const SkOpSpan* base, const SkOpSpanBase* testSpan) const;
278     void debugAddEndMovedSpans(SkPathOpsDebug::GlitchLog* ,
279                                const SkOpPtT* ptT) const;
280 #endif
281     void fixUp(SkCoincidentSpans* coin, SkOpPtT* deleted, const SkOpPtT* kept);
282     void markCollapsed(SkCoincidentSpans* head, SkOpPtT* test);
283     bool overlap(const SkOpPtT* coinStart1, const SkOpPtT* coinEnd1,
284                  const SkOpPtT* coinStart2, const SkOpPtT* coinEnd2,
285                  double* overS, double* overE) const;
286     bool release(SkCoincidentSpans* coin, SkCoincidentSpans* );
287     void releaseDeleted(SkCoincidentSpans* );
288     void restoreHead();
289     // return coinPtT->segment()->t mapped from overS->fT <= t <= overE->fT
290     static double TRange(const SkOpPtT* overS, double t, const SkOpSegment* coinPtT
291                          SkDEBUGPARAMS(const SkOpPtT* overE));
292 
293     SkCoincidentSpans* fHead;
294     SkCoincidentSpans* fTop;
295     SkOpGlobalState* fGlobalState;
296     bool fContinue;
297     bool fSpanDeleted;
298     bool fPtAllocated;
299     bool fCoinExtended;
300     bool fSpanMerged;
301 };
302 
303 #endif
304