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