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