1 | /* |
2 | * Copyright 2012 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 SkOpSpan_DEFINED |
8 | #define SkOpSpan_DEFINED |
9 | |
10 | #include "include/core/SkPoint.h" |
11 | #include "src/pathops/SkPathOpsDebug.h" |
12 | #include "src/pathops/SkPathOpsTypes.h" |
13 | |
14 | class SkArenaAlloc; |
15 | class SkOpAngle; |
16 | class SkOpContour; |
17 | class SkOpGlobalState; |
18 | class SkOpSegment; |
19 | class SkOpSpanBase; |
20 | class SkOpSpan; |
21 | struct SkPathOpsBounds; |
22 | |
23 | // subset of op span used by terminal span (when t is equal to one) |
24 | class SkOpPtT { |
25 | public: |
26 | enum { |
27 | kIsAlias = 1, |
28 | kIsDuplicate = 1 |
29 | }; |
30 | |
31 | const SkOpPtT* active() const; |
32 | |
33 | // please keep in sync with debugAddOpp() |
34 | void addOpp(SkOpPtT* opp, SkOpPtT* oppPrev) { |
35 | SkOpPtT* oldNext = this->fNext; |
36 | SkASSERT(this != opp); |
37 | this->fNext = opp; |
38 | SkASSERT(oppPrev != oldNext); |
39 | oppPrev->fNext = oldNext; |
40 | } |
41 | |
42 | bool alias() const; |
43 | bool coincident() const { return fCoincident; } |
44 | bool contains(const SkOpPtT* ) const; |
45 | bool contains(const SkOpSegment*, const SkPoint& ) const; |
46 | bool contains(const SkOpSegment*, double t) const; |
47 | const SkOpPtT* contains(const SkOpSegment* ) const; |
48 | SkOpContour* contour() const; |
49 | |
50 | int debugID() const { |
51 | return SkDEBUGRELEASE(fID, -1); |
52 | } |
53 | |
54 | void debugAddOpp(const SkOpPtT* opp, const SkOpPtT* oppPrev) const; |
55 | const SkOpAngle* debugAngle(int id) const; |
56 | const SkOpCoincidence* debugCoincidence() const; |
57 | bool debugContains(const SkOpPtT* ) const; |
58 | const SkOpPtT* debugContains(const SkOpSegment* check) const; |
59 | SkOpContour* debugContour(int id) const; |
60 | const SkOpPtT* debugEnder(const SkOpPtT* end) const; |
61 | int debugLoopLimit(bool report) const; |
62 | bool debugMatchID(int id) const; |
63 | const SkOpPtT* debugOppPrev(const SkOpPtT* opp) const; |
64 | const SkOpPtT* debugPtT(int id) const; |
65 | void debugResetCoinT() const; |
66 | const SkOpSegment* debugSegment(int id) const; |
67 | void debugSetCoinT(int ) const; |
68 | const SkOpSpanBase* debugSpan(int id) const; |
69 | void debugValidate() const; |
70 | |
71 | bool deleted() const { |
72 | return fDeleted; |
73 | } |
74 | |
75 | bool duplicate() const { |
76 | return fDuplicatePt; |
77 | } |
78 | |
79 | void dump() const; // available to testing only |
80 | void dumpAll() const; |
81 | void dumpBase() const; |
82 | |
83 | const SkOpPtT* find(const SkOpSegment* ) const; |
84 | SkOpGlobalState* globalState() const; |
85 | void init(SkOpSpanBase* , double t, const SkPoint& , bool dup); |
86 | |
87 | void insert(SkOpPtT* span) { |
88 | SkASSERT(span != this); |
89 | span->fNext = fNext; |
90 | fNext = span; |
91 | } |
92 | |
93 | const SkOpPtT* next() const { |
94 | return fNext; |
95 | } |
96 | |
97 | SkOpPtT* next() { |
98 | return fNext; |
99 | } |
100 | |
101 | bool onEnd() const; |
102 | |
103 | // returns nullptr if this is already in the opp ptT loop |
104 | SkOpPtT* oppPrev(const SkOpPtT* opp) const { |
105 | // find the fOpp ptr to opp |
106 | SkOpPtT* oppPrev = opp->fNext; |
107 | if (oppPrev == this) { |
108 | return nullptr; |
109 | } |
110 | while (oppPrev->fNext != opp) { |
111 | oppPrev = oppPrev->fNext; |
112 | if (oppPrev == this) { |
113 | return nullptr; |
114 | } |
115 | } |
116 | return oppPrev; |
117 | } |
118 | |
119 | static bool Overlaps(const SkOpPtT* s1, const SkOpPtT* e1, const SkOpPtT* s2, |
120 | const SkOpPtT* e2, const SkOpPtT** sOut, const SkOpPtT** eOut) { |
121 | const SkOpPtT* start1 = s1->fT < e1->fT ? s1 : e1; |
122 | const SkOpPtT* start2 = s2->fT < e2->fT ? s2 : e2; |
123 | *sOut = between(s1->fT, start2->fT, e1->fT) ? start2 |
124 | : between(s2->fT, start1->fT, e2->fT) ? start1 : nullptr; |
125 | const SkOpPtT* end1 = s1->fT < e1->fT ? e1 : s1; |
126 | const SkOpPtT* end2 = s2->fT < e2->fT ? e2 : s2; |
127 | *eOut = between(s1->fT, end2->fT, e1->fT) ? end2 |
128 | : between(s2->fT, end1->fT, e2->fT) ? end1 : nullptr; |
129 | if (*sOut == *eOut) { |
130 | SkOPOBJASSERT(s1, start1->fT >= end2->fT || start2->fT >= end1->fT); |
131 | return false; |
132 | } |
133 | SkASSERT(!*sOut || *sOut != *eOut); |
134 | return *sOut && *eOut; |
135 | } |
136 | |
137 | bool ptAlreadySeen(const SkOpPtT* head) const; |
138 | SkOpPtT* prev(); |
139 | |
140 | const SkOpSegment* segment() const; |
141 | SkOpSegment* segment(); |
142 | |
143 | void setCoincident() const { |
144 | SkOPASSERT(!fDeleted); |
145 | fCoincident = true; |
146 | } |
147 | |
148 | void setDeleted(); |
149 | |
150 | void setSpan(const SkOpSpanBase* span) { |
151 | fSpan = const_cast<SkOpSpanBase*>(span); |
152 | } |
153 | |
154 | const SkOpSpanBase* span() const { |
155 | return fSpan; |
156 | } |
157 | |
158 | SkOpSpanBase* span() { |
159 | return fSpan; |
160 | } |
161 | |
162 | const SkOpPtT* starter(const SkOpPtT* end) const { |
163 | return fT < end->fT ? this : end; |
164 | } |
165 | |
166 | double fT; |
167 | SkPoint fPt; // cache of point value at this t |
168 | protected: |
169 | SkOpSpanBase* fSpan; // contains winding data |
170 | SkOpPtT* fNext; // intersection on opposite curve or alias on this curve |
171 | bool fDeleted; // set if removed from span list |
172 | bool fDuplicatePt; // set if identical pt is somewhere in the next loop |
173 | // below mutable since referrer is otherwise always const |
174 | mutable bool fCoincident; // set if at some point a coincident span pointed here |
175 | SkDEBUGCODE(int fID); |
176 | }; |
177 | |
178 | class SkOpSpanBase { |
179 | public: |
180 | enum class Collapsed { |
181 | kNo, |
182 | kYes, |
183 | kError, |
184 | }; |
185 | |
186 | bool addOpp(SkOpSpanBase* opp); |
187 | |
188 | void bumpSpanAdds() { |
189 | ++fSpanAdds; |
190 | } |
191 | |
192 | bool chased() const { |
193 | return fChased; |
194 | } |
195 | |
196 | void checkForCollapsedCoincidence(); |
197 | |
198 | const SkOpSpanBase* coinEnd() const { |
199 | return fCoinEnd; |
200 | } |
201 | |
202 | Collapsed collapsed(double s, double e) const; |
203 | bool contains(const SkOpSpanBase* ) const; |
204 | const SkOpPtT* contains(const SkOpSegment* ) const; |
205 | |
206 | bool containsCoinEnd(const SkOpSpanBase* coin) const { |
207 | SkASSERT(this != coin); |
208 | const SkOpSpanBase* next = this; |
209 | while ((next = next->fCoinEnd) != this) { |
210 | if (next == coin) { |
211 | return true; |
212 | } |
213 | } |
214 | return false; |
215 | } |
216 | |
217 | bool containsCoinEnd(const SkOpSegment* ) const; |
218 | SkOpContour* contour() const; |
219 | |
220 | int debugBumpCount() { |
221 | return SkDEBUGRELEASE(++fCount, -1); |
222 | } |
223 | |
224 | int debugID() const { |
225 | return SkDEBUGRELEASE(fID, -1); |
226 | } |
227 | |
228 | #if DEBUG_COIN |
229 | void debugAddOpp(SkPathOpsDebug::GlitchLog* , const SkOpSpanBase* opp) const; |
230 | #endif |
231 | bool debugAlignedEnd(double t, const SkPoint& pt) const; |
232 | bool debugAlignedInner() const; |
233 | const SkOpAngle* debugAngle(int id) const; |
234 | #if DEBUG_COIN |
235 | void debugCheckForCollapsedCoincidence(SkPathOpsDebug::GlitchLog* ) const; |
236 | #endif |
237 | const SkOpCoincidence* debugCoincidence() const; |
238 | bool debugCoinEndLoopCheck() const; |
239 | SkOpContour* debugContour(int id) const; |
240 | #ifdef SK_DEBUG |
241 | bool debugDeleted() const { return fDebugDeleted; } |
242 | #endif |
243 | #if DEBUG_COIN |
244 | void debugInsertCoinEnd(SkPathOpsDebug::GlitchLog* , |
245 | const SkOpSpanBase* ) const; |
246 | void debugMergeMatches(SkPathOpsDebug::GlitchLog* log, |
247 | const SkOpSpanBase* opp) const; |
248 | #endif |
249 | const SkOpPtT* debugPtT(int id) const; |
250 | void debugResetCoinT() const; |
251 | const SkOpSegment* debugSegment(int id) const; |
252 | void debugSetCoinT(int ) const; |
253 | #ifdef SK_DEBUG |
254 | void debugSetDeleted() { fDebugDeleted = true; } |
255 | #endif |
256 | const SkOpSpanBase* debugSpan(int id) const; |
257 | const SkOpSpan* debugStarter(SkOpSpanBase const** endPtr) const; |
258 | SkOpGlobalState* globalState() const; |
259 | void debugValidate() const; |
260 | |
261 | bool deleted() const { |
262 | return fPtT.deleted(); |
263 | } |
264 | |
265 | void dump() const; // available to testing only |
266 | void dumpCoin() const; |
267 | void dumpAll() const; |
268 | void dumpBase() const; |
269 | void dumpHead() const; |
270 | |
271 | bool final() const { |
272 | return fPtT.fT == 1; |
273 | } |
274 | |
275 | SkOpAngle* fromAngle() const { |
276 | return fFromAngle; |
277 | } |
278 | |
279 | void initBase(SkOpSegment* parent, SkOpSpan* prev, double t, const SkPoint& pt); |
280 | |
281 | // Please keep this in sync with debugInsertCoinEnd() |
282 | void insertCoinEnd(SkOpSpanBase* coin) { |
283 | if (containsCoinEnd(coin)) { |
284 | SkASSERT(coin->containsCoinEnd(this)); |
285 | return; |
286 | } |
287 | debugValidate(); |
288 | SkASSERT(this != coin); |
289 | SkOpSpanBase* coinNext = coin->fCoinEnd; |
290 | coin->fCoinEnd = this->fCoinEnd; |
291 | this->fCoinEnd = coinNext; |
292 | debugValidate(); |
293 | } |
294 | |
295 | void merge(SkOpSpan* span); |
296 | bool mergeMatches(SkOpSpanBase* opp); |
297 | |
298 | const SkOpSpan* prev() const { |
299 | return fPrev; |
300 | } |
301 | |
302 | SkOpSpan* prev() { |
303 | return fPrev; |
304 | } |
305 | |
306 | const SkPoint& pt() const { |
307 | return fPtT.fPt; |
308 | } |
309 | |
310 | const SkOpPtT* ptT() const { |
311 | return &fPtT; |
312 | } |
313 | |
314 | SkOpPtT* ptT() { |
315 | return &fPtT; |
316 | } |
317 | |
318 | SkOpSegment* segment() const { |
319 | return fSegment; |
320 | } |
321 | |
322 | void setAligned() { |
323 | fAligned = true; |
324 | } |
325 | |
326 | void setChased(bool chased) { |
327 | fChased = chased; |
328 | } |
329 | |
330 | void setFromAngle(SkOpAngle* angle) { |
331 | fFromAngle = angle; |
332 | } |
333 | |
334 | void setPrev(SkOpSpan* prev) { |
335 | fPrev = prev; |
336 | } |
337 | |
338 | bool simple() const { |
339 | fPtT.debugValidate(); |
340 | return fPtT.next()->next() == &fPtT; |
341 | } |
342 | |
343 | int spanAddsCount() const { |
344 | return fSpanAdds; |
345 | } |
346 | |
347 | const SkOpSpan* starter(const SkOpSpanBase* end) const { |
348 | const SkOpSpanBase* result = t() < end->t() ? this : end; |
349 | return result->upCast(); |
350 | } |
351 | |
352 | SkOpSpan* starter(SkOpSpanBase* end) { |
353 | SkASSERT(this->segment() == end->segment()); |
354 | SkOpSpanBase* result = t() < end->t() ? this : end; |
355 | return result->upCast(); |
356 | } |
357 | |
358 | SkOpSpan* starter(SkOpSpanBase** endPtr) { |
359 | SkOpSpanBase* end = *endPtr; |
360 | SkASSERT(this->segment() == end->segment()); |
361 | SkOpSpanBase* result; |
362 | if (t() < end->t()) { |
363 | result = this; |
364 | } else { |
365 | result = end; |
366 | *endPtr = this; |
367 | } |
368 | return result->upCast(); |
369 | } |
370 | |
371 | int step(const SkOpSpanBase* end) const { |
372 | return t() < end->t() ? 1 : -1; |
373 | } |
374 | |
375 | double t() const { |
376 | return fPtT.fT; |
377 | } |
378 | |
379 | void unaligned() { |
380 | fAligned = false; |
381 | } |
382 | |
383 | SkOpSpan* upCast() { |
384 | SkASSERT(!final()); |
385 | return (SkOpSpan*) this; |
386 | } |
387 | |
388 | const SkOpSpan* upCast() const { |
389 | SkOPASSERT(!final()); |
390 | return (const SkOpSpan*) this; |
391 | } |
392 | |
393 | SkOpSpan* upCastable() { |
394 | return final() ? nullptr : upCast(); |
395 | } |
396 | |
397 | const SkOpSpan* upCastable() const { |
398 | return final() ? nullptr : upCast(); |
399 | } |
400 | |
401 | private: |
402 | void alignInner(); |
403 | |
404 | protected: // no direct access to internals to avoid treating a span base as a span |
405 | SkOpPtT fPtT; // list of points and t values associated with the start of this span |
406 | SkOpSegment* fSegment; // segment that contains this span |
407 | SkOpSpanBase* fCoinEnd; // linked list of coincident spans that end here (may point to itself) |
408 | SkOpAngle* fFromAngle; // points to next angle from span start to end |
409 | SkOpSpan* fPrev; // previous intersection point |
410 | int fSpanAdds; // number of times intersections have been added to span |
411 | bool fAligned; |
412 | bool fChased; // set after span has been added to chase array |
413 | SkDEBUGCODE(int fCount); // number of pt/t pairs added |
414 | SkDEBUGCODE(int fID); |
415 | SkDEBUGCODE(bool fDebugDeleted); // set when span was merged with another span |
416 | }; |
417 | |
418 | class SkOpSpan : public SkOpSpanBase { |
419 | public: |
420 | bool alreadyAdded() const { |
421 | if (fAlreadyAdded) { |
422 | return true; |
423 | } |
424 | return false; |
425 | } |
426 | |
427 | bool clearCoincident() { |
428 | SkASSERT(!final()); |
429 | if (fCoincident == this) { |
430 | return false; |
431 | } |
432 | fCoincident = this; |
433 | return true; |
434 | } |
435 | |
436 | int computeWindSum(); |
437 | bool containsCoincidence(const SkOpSegment* ) const; |
438 | |
439 | bool containsCoincidence(const SkOpSpan* coin) const { |
440 | SkASSERT(this != coin); |
441 | const SkOpSpan* next = this; |
442 | while ((next = next->fCoincident) != this) { |
443 | if (next == coin) { |
444 | return true; |
445 | } |
446 | } |
447 | return false; |
448 | } |
449 | |
450 | bool debugCoinLoopCheck() const; |
451 | #if DEBUG_COIN |
452 | void debugInsertCoincidence(SkPathOpsDebug::GlitchLog* , const SkOpSpan* ) const; |
453 | void debugInsertCoincidence(SkPathOpsDebug::GlitchLog* , |
454 | const SkOpSegment* , bool flipped, bool ordered) const; |
455 | #endif |
456 | void dumpCoin() const; |
457 | bool dumpSpan() const; |
458 | |
459 | bool done() const { |
460 | SkASSERT(!final()); |
461 | return fDone; |
462 | } |
463 | |
464 | void init(SkOpSegment* parent, SkOpSpan* prev, double t, const SkPoint& pt); |
465 | bool insertCoincidence(const SkOpSegment* , bool flipped, bool ordered); |
466 | |
467 | // Please keep this in sync with debugInsertCoincidence() |
468 | void insertCoincidence(SkOpSpan* coin) { |
469 | if (containsCoincidence(coin)) { |
470 | SkASSERT(coin->containsCoincidence(this)); |
471 | return; |
472 | } |
473 | debugValidate(); |
474 | SkASSERT(this != coin); |
475 | SkOpSpan* coinNext = coin->fCoincident; |
476 | coin->fCoincident = this->fCoincident; |
477 | this->fCoincident = coinNext; |
478 | debugValidate(); |
479 | } |
480 | |
481 | bool isCanceled() const { |
482 | SkASSERT(!final()); |
483 | return fWindValue == 0 && fOppValue == 0; |
484 | } |
485 | |
486 | bool isCoincident() const { |
487 | SkASSERT(!final()); |
488 | return fCoincident != this; |
489 | } |
490 | |
491 | void markAdded() { |
492 | fAlreadyAdded = true; |
493 | } |
494 | |
495 | SkOpSpanBase* next() const { |
496 | SkASSERT(!final()); |
497 | return fNext; |
498 | } |
499 | |
500 | int oppSum() const { |
501 | SkASSERT(!final()); |
502 | return fOppSum; |
503 | } |
504 | |
505 | int oppValue() const { |
506 | SkASSERT(!final()); |
507 | return fOppValue; |
508 | } |
509 | |
510 | void release(const SkOpPtT* ); |
511 | |
512 | SkOpPtT* setCoinStart(SkOpSpan* oldCoinStart, SkOpSegment* oppSegment); |
513 | |
514 | void setDone(bool done) { |
515 | SkASSERT(!final()); |
516 | fDone = done; |
517 | } |
518 | |
519 | void setNext(SkOpSpanBase* nextT) { |
520 | SkASSERT(!final()); |
521 | fNext = nextT; |
522 | } |
523 | |
524 | void setOppSum(int oppSum); |
525 | |
526 | void setOppValue(int oppValue) { |
527 | SkASSERT(!final()); |
528 | SkASSERT(fOppSum == SK_MinS32); |
529 | SkOPASSERT(!oppValue || !fDone); |
530 | fOppValue = oppValue; |
531 | } |
532 | |
533 | void setToAngle(SkOpAngle* angle) { |
534 | SkASSERT(!final()); |
535 | fToAngle = angle; |
536 | } |
537 | |
538 | void setWindSum(int windSum); |
539 | |
540 | void setWindValue(int windValue) { |
541 | SkASSERT(!final()); |
542 | SkASSERT(windValue >= 0); |
543 | SkASSERT(fWindSum == SK_MinS32); |
544 | SkOPASSERT(!windValue || !fDone); |
545 | fWindValue = windValue; |
546 | } |
547 | |
548 | bool sortableTop(SkOpContour* ); |
549 | |
550 | SkOpAngle* toAngle() const { |
551 | SkASSERT(!final()); |
552 | return fToAngle; |
553 | } |
554 | |
555 | int windSum() const { |
556 | SkASSERT(!final()); |
557 | return fWindSum; |
558 | } |
559 | |
560 | int windValue() const { |
561 | SkOPASSERT(!final()); |
562 | return fWindValue; |
563 | } |
564 | |
565 | private: // no direct access to internals to avoid treating a span base as a span |
566 | SkOpSpan* fCoincident; // linked list of spans coincident with this one (may point to itself) |
567 | SkOpAngle* fToAngle; // points to next angle from span start to end |
568 | SkOpSpanBase* fNext; // next intersection point |
569 | int fWindSum; // accumulated from contours surrounding this one. |
570 | int fOppSum; // for binary operators: the opposite winding sum |
571 | int fWindValue; // 0 == canceled; 1 == normal; >1 == coincident |
572 | int fOppValue; // normally 0 -- when binary coincident edges combine, opp value goes here |
573 | int fTopTTry; // specifies direction and t value to try next |
574 | bool fDone; // if set, this span to next higher T has been processed |
575 | bool fAlreadyAdded; |
576 | }; |
577 | |
578 | #endif |
579 | |