1/*
2 * Copyright 2014 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 SkPathOpsTSect_DEFINED
8#define SkPathOpsTSect_DEFINED
9
10#include "include/private/SkMacros.h"
11#include "src/core/SkArenaAlloc.h"
12#include "src/pathops/SkIntersections.h"
13#include "src/pathops/SkPathOpsBounds.h"
14#include "src/pathops/SkPathOpsRect.h"
15#include "src/pathops/SkPathOpsTCurve.h"
16
17#include <utility>
18
19#ifdef SK_DEBUG
20typedef uint8_t SkOpDebugBool;
21#else
22typedef bool SkOpDebugBool;
23#endif
24
25static inline bool SkDoubleIsNaN(double x) {
26    return x != x;
27}
28
29class SkTCoincident {
30public:
31    SkTCoincident() {
32        this->init();
33    }
34
35    void debugInit() {
36#ifdef SK_DEBUG
37        this->fPerpPt.fX = this->fPerpPt.fY = SK_ScalarNaN;
38        this->fPerpT = SK_ScalarNaN;
39        this->fMatch = 0xFF;
40#endif
41    }
42
43    char dumpIsCoincidentStr() const;
44    void dump() const;
45
46    bool isMatch() const {
47        SkASSERT(!!fMatch == fMatch);
48        return SkToBool(fMatch);
49    }
50
51    void init() {
52        fPerpT = -1;
53        fMatch = false;
54        fPerpPt.fX = fPerpPt.fY = SK_ScalarNaN;
55    }
56
57    void markCoincident() {
58        if (!fMatch) {
59            fPerpT = -1;
60        }
61        fMatch = true;
62    }
63
64    const SkDPoint& perpPt() const {
65        return fPerpPt;
66    }
67
68    double perpT() const {
69        return fPerpT;
70    }
71
72    void setPerp(const SkTCurve& c1, double t, const SkDPoint& cPt, const SkTCurve& );
73
74private:
75    SkDPoint fPerpPt;
76    double fPerpT;  // perpendicular intersection on opposite curve
77    SkOpDebugBool fMatch;
78};
79
80class SkTSect;
81class SkTSpan;
82
83struct SkTSpanBounded {
84    SkTSpan* fBounded;
85    SkTSpanBounded* fNext;
86};
87
88class SkTSpan {
89public:
90    SkTSpan(const SkTCurve& curve, SkArenaAlloc& heap) {
91        fPart = curve.make(heap);
92    }
93
94    void addBounded(SkTSpan* , SkArenaAlloc* );
95    double closestBoundedT(const SkDPoint& pt) const;
96    bool contains(double t) const;
97
98    void debugInit(const SkTCurve& curve, SkArenaAlloc& heap) {
99#ifdef SK_DEBUG
100        SkTCurve* fake = curve.make(heap);
101        fake->debugInit();
102        init(*fake);
103        initBounds(*fake);
104        fCoinStart.init();
105        fCoinEnd.init();
106#endif
107    }
108
109    const SkTSect* debugOpp() const;
110
111#ifdef SK_DEBUG
112    void debugSetGlobalState(SkOpGlobalState* state) {
113        fDebugGlobalState = state;
114    }
115
116    const SkTSpan* debugSpan(int ) const;
117    const SkTSpan* debugT(double t) const;
118    bool debugIsBefore(const SkTSpan* span) const;
119#endif
120    void dump() const;
121    void dumpAll() const;
122    void dumpBounded(int id) const;
123    void dumpBounds() const;
124    void dumpCoin() const;
125
126    double endT() const {
127        return fEndT;
128    }
129
130    SkTSpan* findOppSpan(const SkTSpan* opp) const;
131
132    SkTSpan* findOppT(double t) const {
133        SkTSpan* result = oppT(t);
134        SkOPASSERT(result);
135        return result;
136    }
137
138    SkDEBUGCODE(SkOpGlobalState* globalState() const { return fDebugGlobalState; })
139
140    bool hasOppT(double t) const {
141        return SkToBool(oppT(t));
142    }
143
144    int hullsIntersect(SkTSpan* span, bool* start, bool* oppStart);
145    void init(const SkTCurve& );
146    bool initBounds(const SkTCurve& );
147
148    bool isBounded() const {
149        return fBounded != nullptr;
150    }
151
152    bool linearsIntersect(SkTSpan* span);
153    double linearT(const SkDPoint& ) const;
154
155    void markCoincident() {
156        fCoinStart.markCoincident();
157        fCoinEnd.markCoincident();
158    }
159
160    const SkTSpan* next() const {
161        return fNext;
162    }
163
164    bool onlyEndPointsInCommon(const SkTSpan* opp, bool* start,
165            bool* oppStart, bool* ptsInCommon);
166
167    const SkTCurve& part() const {
168        return *fPart;
169    }
170
171    int pointCount() const {
172        return fPart->pointCount();
173    }
174
175    const SkDPoint& pointFirst() const {
176        return (*fPart)[0];
177    }
178
179    const SkDPoint& pointLast() const {
180        return (*fPart)[fPart->pointLast()];
181    }
182
183    bool removeAllBounded();
184    bool removeBounded(const SkTSpan* opp);
185
186    void reset() {
187        fBounded = nullptr;
188    }
189
190    void resetBounds(const SkTCurve& curve) {
191        fIsLinear = fIsLine = false;
192        initBounds(curve);
193    }
194
195    bool split(SkTSpan* work, SkArenaAlloc* heap) {
196        return splitAt(work, (work->fStartT + work->fEndT) * 0.5, heap);
197    }
198
199    bool splitAt(SkTSpan* work, double t, SkArenaAlloc* heap);
200
201    double startT() const {
202        return fStartT;
203    }
204
205private:
206
207    // implementation is for testing only
208    int debugID() const {
209        return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1);
210    }
211
212    void dumpID() const;
213
214    int hullCheck(const SkTSpan* opp, bool* start, bool* oppStart);
215    int linearIntersects(const SkTCurve& ) const;
216    SkTSpan* oppT(double t) const;
217
218    void validate() const;
219    void validateBounded() const;
220    void validatePerpT(double oppT) const;
221    void validatePerpPt(double t, const SkDPoint& ) const;
222
223    SkTCurve* fPart;
224    SkTCoincident fCoinStart;
225    SkTCoincident fCoinEnd;
226    SkTSpanBounded* fBounded;
227    SkTSpan* fPrev;
228    SkTSpan* fNext;
229    SkDRect fBounds;
230    double fStartT;
231    double fEndT;
232    double fBoundsMax;
233    SkOpDebugBool fCollapsed;
234    SkOpDebugBool fHasPerp;
235    SkOpDebugBool fIsLinear;
236    SkOpDebugBool fIsLine;
237    SkOpDebugBool fDeleted;
238    SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState);
239    SkDEBUGCODE(SkTSect* fDebugSect);
240    PATH_OPS_DEBUG_T_SECT_CODE(int fID);
241    friend class SkTSect;
242};
243
244class SkTSect {
245public:
246    SkTSect(const SkTCurve& c
247                             SkDEBUGPARAMS(SkOpGlobalState* ) PATH_OPS_DEBUG_T_SECT_PARAMS(int id));
248    static void BinarySearch(SkTSect* sect1, SkTSect* sect2,
249            SkIntersections* intersections);
250
251    SkDEBUGCODE(SkOpGlobalState* globalState() { return fDebugGlobalState; })
252    bool hasBounded(const SkTSpan* ) const;
253
254    const SkTSect* debugOpp() const {
255        return SkDEBUGRELEASE(fOppSect, nullptr);
256    }
257
258#ifdef SK_DEBUG
259    const SkTSpan* debugSpan(int id) const;
260    const SkTSpan* debugT(double t) const;
261#endif
262    void dump() const;
263    void dumpBoth(SkTSect* ) const;
264    void dumpBounded(int id) const;
265    void dumpBounds() const;
266    void dumpCoin() const;
267    void dumpCoinCurves() const;
268    void dumpCurves() const;
269
270private:
271    enum {
272        kZeroS1Set = 1,
273        kOneS1Set = 2,
274        kZeroS2Set = 4,
275        kOneS2Set = 8
276    };
277
278    SkTSpan* addFollowing(SkTSpan* prior);
279    void addForPerp(SkTSpan* span, double t);
280    SkTSpan* addOne();
281
282    SkTSpan* addSplitAt(SkTSpan* span, double t) {
283        SkTSpan* result = this->addOne();
284        SkDEBUGCODE(result->debugSetGlobalState(this->globalState()));
285        result->splitAt(span, t, &fHeap);
286        result->initBounds(fCurve);
287        span->initBounds(fCurve);
288        return result;
289    }
290
291    bool binarySearchCoin(SkTSect* , double tStart, double tStep, double* t,
292                          double* oppT, SkTSpan** oppFirst);
293    SkTSpan* boundsMax();
294    bool coincidentCheck(SkTSect* sect2);
295    void coincidentForce(SkTSect* sect2, double start1s, double start1e);
296    bool coincidentHasT(double t);
297    int collapsed() const;
298    void computePerpendiculars(SkTSect* sect2, SkTSpan* first,
299                               SkTSpan* last);
300    int countConsecutiveSpans(SkTSpan* first,
301                              SkTSpan** last) const;
302
303    int debugID() const {
304        return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1);
305    }
306
307    bool deleteEmptySpans();
308    void dumpCommon(const SkTSpan* ) const;
309    void dumpCommonCurves(const SkTSpan* ) const;
310    static int EndsEqual(const SkTSect* sect1, const SkTSect* sect2,
311                         SkIntersections* );
312    bool extractCoincident(SkTSect* sect2, SkTSpan* first,
313                           SkTSpan* last, SkTSpan** result);
314    SkTSpan* findCoincidentRun(SkTSpan* first, SkTSpan** lastPtr);
315    int intersects(SkTSpan* span, SkTSect* opp,
316                   SkTSpan* oppSpan, int* oppResult);
317    bool isParallel(const SkDLine& thisLine, const SkTSect* opp) const;
318    int linesIntersect(SkTSpan* span, SkTSect* opp,
319                       SkTSpan* oppSpan, SkIntersections* );
320    bool markSpanGone(SkTSpan* span);
321    bool matchedDirection(double t, const SkTSect* sect2, double t2) const;
322    void matchedDirCheck(double t, const SkTSect* sect2, double t2,
323                         bool* calcMatched, bool* oppMatched) const;
324    void mergeCoincidence(SkTSect* sect2);
325
326    const SkDPoint& pointLast() const {
327        return fCurve[fCurve.pointLast()];
328    }
329
330    SkTSpan* prev(SkTSpan* ) const;
331    bool removeByPerpendicular(SkTSect* opp);
332    void recoverCollapsed();
333    bool removeCoincident(SkTSpan* span, bool isBetween);
334    void removeAllBut(const SkTSpan* keep, SkTSpan* span,
335                      SkTSect* opp);
336    bool removeSpan(SkTSpan* span);
337    void removeSpanRange(SkTSpan* first, SkTSpan* last);
338    bool removeSpans(SkTSpan* span, SkTSect* opp);
339    void removedEndCheck(SkTSpan* span);
340
341    void resetRemovedEnds() {
342        fRemovedStartT = fRemovedEndT = false;
343    }
344
345    SkTSpan* spanAtT(double t, SkTSpan** priorSpan);
346    SkTSpan* tail();
347    bool trim(SkTSpan* span, SkTSect* opp);
348    bool unlinkSpan(SkTSpan* span);
349    bool updateBounded(SkTSpan* first, SkTSpan* last,
350                       SkTSpan* oppFirst);
351    void validate() const;
352    void validateBounded() const;
353
354    const SkTCurve& fCurve;
355    SkSTArenaAlloc<1024> fHeap;
356    SkTSpan* fHead;
357    SkTSpan* fCoincident;
358    SkTSpan* fDeleted;
359    int fActiveCount;
360    bool fRemovedStartT;
361    bool fRemovedEndT;
362    bool fHung;
363    SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState);
364    SkDEBUGCODE(SkTSect* fOppSect);
365    PATH_OPS_DEBUG_T_SECT_CODE(int fID);
366    PATH_OPS_DEBUG_T_SECT_CODE(int fDebugCount);
367#if DEBUG_T_SECT
368    int fDebugAllocatedCount;
369#endif
370    friend class SkTSpan;
371};
372
373#endif
374