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