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