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
15class SkOpPtT;
16class SkOpSpanBase;
17
18class SkCoincidentSpans {
19public:
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 SkOpPtT* coinPtTEndWritable() const { return const_cast<SkOpPtT*>(fCoinPtTEnd); }
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
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 bool flipped() const { return fOppPtTStart->fT > fOppPtTEnd->fT; }
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
67 SkCoincidentSpans* next() { return fNext; }
68 const SkCoincidentSpans* next() const { return fNext; }
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
74 SkOpPtT* oppPtTStartWritable() const { return const_cast<SkOpPtT*>(fOppPtTStart); }
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
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
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
97 void setEnds(const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTEnd) {
98 this->setCoinPtTEnd(coinPtTEnd);
99 this->setOppPtTEnd(oppPtTEnd);
100 }
101
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
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
118 void setStarts(const SkOpPtT* coinPtTStart, const SkOpPtT* oppPtTStart) {
119 this->setCoinPtTStart(coinPtTStart);
120 this->setOppPtTStart(oppPtTStart);
121 }
122
123 void setNext(SkCoincidentSpans* next) { fNext = next; }
124
125private:
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
134class SkOpCoincidence {
135public:
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
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 SkOpGlobalState* globalState() {
219 return fGlobalState;
220 }
221
222 const SkOpGlobalState* globalState() const {
223 return fGlobalState;
224 }
225
226 bool isEmpty() const {
227 return !fHead && !fTop;
228 }
229
230 bool mark(DEBUG_COIN_DECLARE_ONLY_PARAMS());
231 void markCollapsed(SkOpPtT* );
232
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
241private:
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