Line data Source code
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 "SkTDArray.h"
11 : #include "SkOpTAllocator.h"
12 : #include "SkOpSpan.h"
13 : #include "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
25 0 : SkOpPtT* coinPtTEndWritable() const { return const_cast<SkOpPtT*>(fCoinPtTEnd); }
26 0 : 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 :
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);
59 0 : bool flipped() const { return fOppPtTStart->fT > fOppPtTEnd->fT; }
60 0 : SkDEBUGCODE(SkOpGlobalState* globalState() { return fGlobalState; })
61 :
62 0 : void init(SkDEBUGCODE(SkOpGlobalState* globalState)) {
63 0 : sk_bzero(this, sizeof(*this));
64 0 : SkDEBUGCODE(fGlobalState = globalState);
65 0 : }
66 :
67 0 : SkCoincidentSpans* next() { return fNext; }
68 0 : const SkCoincidentSpans* next() const { return fNext; }
69 0 : 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
74 0 : SkOpPtT* oppPtTStartWritable() const { return const_cast<SkOpPtT*>(fOppPtTStart); }
75 0 : 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 :
81 0 : void setCoinPtTEnd(const SkOpPtT* ptT) {
82 0 : SkOPASSERT(ptT == ptT->span()->ptT());
83 0 : SkOPASSERT(!fCoinPtTStart || ptT->fT != fCoinPtTStart->fT);
84 0 : SkASSERT(!fCoinPtTStart || fCoinPtTStart->segment() == ptT->segment());
85 0 : fCoinPtTEnd = ptT;
86 0 : ptT->setCoincident();
87 0 : }
88 :
89 0 : void setCoinPtTStart(const SkOpPtT* ptT) {
90 0 : SkOPASSERT(ptT == ptT->span()->ptT());
91 0 : SkOPASSERT(!fCoinPtTEnd || ptT->fT != fCoinPtTEnd->fT);
92 0 : SkASSERT(!fCoinPtTEnd || fCoinPtTEnd->segment() == ptT->segment());
93 0 : fCoinPtTStart = ptT;
94 0 : ptT->setCoincident();
95 0 : }
96 :
97 0 : void setEnds(const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTEnd) {
98 0 : this->setCoinPtTEnd(coinPtTEnd);
99 0 : this->setOppPtTEnd(oppPtTEnd);
100 0 : }
101 :
102 0 : void setOppPtTEnd(const SkOpPtT* ptT) {
103 0 : SkOPASSERT(ptT == ptT->span()->ptT());
104 0 : SkOPASSERT(!fOppPtTStart || ptT->fT != fOppPtTStart->fT);
105 0 : SkASSERT(!fOppPtTStart || fOppPtTStart->segment() == ptT->segment());
106 0 : fOppPtTEnd = ptT;
107 0 : ptT->setCoincident();
108 0 : }
109 :
110 0 : void setOppPtTStart(const SkOpPtT* ptT) {
111 0 : SkOPASSERT(ptT == ptT->span()->ptT());
112 0 : SkOPASSERT(!fOppPtTEnd || ptT->fT != fOppPtTEnd->fT);
113 0 : SkASSERT(!fOppPtTEnd || fOppPtTEnd->segment() == ptT->segment());
114 0 : fOppPtTStart = ptT;
115 0 : ptT->setCoincident();
116 0 : }
117 :
118 0 : void setStarts(const SkOpPtT* coinPtTStart, const SkOpPtT* oppPtTStart) {
119 0 : this->setCoinPtTStart(coinPtTStart);
120 0 : this->setOppPtTStart(oppPtTStart);
121 0 : }
122 :
123 0 : 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:
136 0 : SkOpCoincidence(SkOpGlobalState* globalState)
137 0 : : fHead(nullptr)
138 : , fTop(nullptr)
139 : , fGlobalState(globalState)
140 : , fContinue(false)
141 : , fSpanDeleted(false)
142 : , fPtAllocated(false)
143 : , fCoinExtended(false)
144 0 : , fSpanMerged(false) {
145 0 : globalState->setCoincidence(this);
146 0 : }
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 :
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 :
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 :
191 : const SkOpPtT* debugPtT(int id) const {
192 : return SkDEBUGRELEASE(fGlobalState->debugPtT(id), nullptr);
193 : }
194 :
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 :
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 :
218 0 : SkOpGlobalState* globalState() {
219 0 : return fGlobalState;
220 : }
221 :
222 : const SkOpGlobalState* globalState() const {
223 : return fGlobalState;
224 : }
225 :
226 0 : bool isEmpty() const {
227 0 : return !fHead && !fTop;
228 : }
229 :
230 : bool mark(DEBUG_COIN_DECLARE_ONLY_PARAMS());
231 : void markCollapsed(SkOpPtT* );
232 :
233 0 : static bool Ordered(const SkOpPtT* coinPtTStart, const SkOpPtT* oppPtTStart) {
234 0 : 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:
242 0 : 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 0 : const_cast<SkOpPtT*>(oppPtTStart), const_cast<SkOpPtT*>(oppPtTEnd));
246 0 : }
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
|