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
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