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