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/core/SkTSort.h"
13#include "src/pathops/SkIntersections.h"
14#include "src/pathops/SkPathOpsBounds.h"
15#include "src/pathops/SkPathOpsRect.h"
16#include "src/pathops/SkPathOpsTCurve.h"
17
18#include <utility>
19
20#ifdef SK_DEBUG
21typedef uint8_t SkOpDebugBool;
22#else
23typedef bool SkOpDebugBool;
24#endif
25
26static inline bool SkDoubleIsNaN(double x) {
27 return x != x;
28}
29
30class SkTCoincident {
31public:
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
75private:
76 SkDPoint fPerpPt;
77 double fPerpT; // perpendicular intersection on opposite curve
78 SkOpDebugBool fMatch;
79};
80
81class SkTSect;
82class SkTSpan;
83
84struct SkTSpanBounded {
85 SkTSpan* fBounded;
86 SkTSpanBounded* fNext;
87};
88
89class SkTSpan {
90public:
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
206private:
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
245class SkTSect {
246public:
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
271private:
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