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