SkOpCoincidence.cpp revision 4c76c41c981dd7ea95062a1895a6e3415b70bce1
154359294a7c9dc54802d512a5d891a35c1663392caryclark/* 254359294a7c9dc54802d512a5d891a35c1663392caryclark * Copyright 2015 Google Inc. 354359294a7c9dc54802d512a5d891a35c1663392caryclark * 454359294a7c9dc54802d512a5d891a35c1663392caryclark * Use of this source code is governed by a BSD-style license that can be 554359294a7c9dc54802d512a5d891a35c1663392caryclark * found in the LICENSE file. 654359294a7c9dc54802d512a5d891a35c1663392caryclark */ 754359294a7c9dc54802d512a5d891a35c1663392caryclark#include "SkOpCoincidence.h" 854359294a7c9dc54802d512a5d891a35c1663392caryclark#include "SkOpSegment.h" 954359294a7c9dc54802d512a5d891a35c1663392caryclark#include "SkPathOpsTSect.h" 1054359294a7c9dc54802d512a5d891a35c1663392caryclark 1155888e44171ffd48b591d19256884a969fe4da17caryclark// returns true if coincident span's start and end are the same 1255888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkCoincidentSpans::collapsed(const SkOpPtT* test) const { 1355888e44171ffd48b591d19256884a969fe4da17caryclark return (fCoinPtTStart == test && fCoinPtTEnd->contains(test)) 1455888e44171ffd48b591d19256884a969fe4da17caryclark || (fCoinPtTEnd == test && fCoinPtTStart->contains(test)) 1555888e44171ffd48b591d19256884a969fe4da17caryclark || (fOppPtTStart == test && fOppPtTEnd->contains(test)) 1655888e44171ffd48b591d19256884a969fe4da17caryclark || (fOppPtTEnd == test && fOppPtTStart->contains(test)); 1755888e44171ffd48b591d19256884a969fe4da17caryclark} 1855888e44171ffd48b591d19256884a969fe4da17caryclark 19db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark// out of line since this function is referenced by address 20db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clarkconst SkOpPtT* SkCoincidentSpans::coinPtTEnd() const { 21db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark return fCoinPtTEnd; 22db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark} 23db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark 24db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark// out of line since this function is referenced by address 25db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clarkconst SkOpPtT* SkCoincidentSpans::coinPtTStart() const { 26db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark return fCoinPtTStart; 27db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark} 28db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark 2955888e44171ffd48b591d19256884a969fe4da17caryclark// sets the span's end to the ptT referenced by the previous-next 3055888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkCoincidentSpans::correctOneEnd( 3155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* (SkCoincidentSpans::* getEnd)() const, 3255888e44171ffd48b591d19256884a969fe4da17caryclark void (SkCoincidentSpans::*setEnd)(const SkOpPtT* ptT) ) { 3355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* origPtT = (this->*getEnd)(); 3455888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* origSpan = origPtT->span(); 3555888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpan* prev = origSpan->prev(); 3655888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* testPtT = prev ? prev->next()->ptT() 3755888e44171ffd48b591d19256884a969fe4da17caryclark : origSpan->upCast()->next()->prev()->ptT(); 3855888e44171ffd48b591d19256884a969fe4da17caryclark if (origPtT != testPtT) { 3955888e44171ffd48b591d19256884a969fe4da17caryclark (this->*setEnd)(testPtT); 4055888e44171ffd48b591d19256884a969fe4da17caryclark } 4155888e44171ffd48b591d19256884a969fe4da17caryclark} 4255888e44171ffd48b591d19256884a969fe4da17caryclark 43ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark/* Please keep this in sync with debugCorrectEnds */ 4455888e44171ffd48b591d19256884a969fe4da17caryclark// FIXME: member pointers have fallen out of favor and can be replaced with 4555888e44171ffd48b591d19256884a969fe4da17caryclark// an alternative approach. 4655888e44171ffd48b591d19256884a969fe4da17caryclark// makes all span ends agree with the segment's spans that define them 4755888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkCoincidentSpans::correctEnds() { 4855888e44171ffd48b591d19256884a969fe4da17caryclark this->correctOneEnd(&SkCoincidentSpans::coinPtTStart, &SkCoincidentSpans::setCoinPtTStart); 4955888e44171ffd48b591d19256884a969fe4da17caryclark this->correctOneEnd(&SkCoincidentSpans::coinPtTEnd, &SkCoincidentSpans::setCoinPtTEnd); 5055888e44171ffd48b591d19256884a969fe4da17caryclark this->correctOneEnd(&SkCoincidentSpans::oppPtTStart, &SkCoincidentSpans::setOppPtTStart); 5155888e44171ffd48b591d19256884a969fe4da17caryclark this->correctOneEnd(&SkCoincidentSpans::oppPtTEnd, &SkCoincidentSpans::setOppPtTEnd); 5255888e44171ffd48b591d19256884a969fe4da17caryclark} 5355888e44171ffd48b591d19256884a969fe4da17caryclark 5455888e44171ffd48b591d19256884a969fe4da17caryclark/* Please keep this in sync with debugExpand */ 5555888e44171ffd48b591d19256884a969fe4da17caryclark// expand the range by checking adjacent spans for coincidence 5655888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkCoincidentSpans::expand() { 5755888e44171ffd48b591d19256884a969fe4da17caryclark bool expanded = false; 5855888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* segment = coinPtTStart()->segment(); 5955888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* oppSegment = oppPtTStart()->segment(); 6055888e44171ffd48b591d19256884a969fe4da17caryclark do { 6155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpan* start = coinPtTStart()->span()->upCast(); 6255888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpan* prev = start->prev(); 6355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* oppPtT; 6455888e44171ffd48b591d19256884a969fe4da17caryclark if (!prev || !(oppPtT = prev->contains(oppSegment))) { 6555888e44171ffd48b591d19256884a969fe4da17caryclark break; 6655888e44171ffd48b591d19256884a969fe4da17caryclark } 6755888e44171ffd48b591d19256884a969fe4da17caryclark double midT = (prev->t() + start->t()) / 2; 6855888e44171ffd48b591d19256884a969fe4da17caryclark if (!segment->isClose(midT, oppSegment)) { 6955888e44171ffd48b591d19256884a969fe4da17caryclark break; 7055888e44171ffd48b591d19256884a969fe4da17caryclark } 7155888e44171ffd48b591d19256884a969fe4da17caryclark setStarts(prev->ptT(), oppPtT); 7255888e44171ffd48b591d19256884a969fe4da17caryclark expanded = true; 7355888e44171ffd48b591d19256884a969fe4da17caryclark } while (true); 7455888e44171ffd48b591d19256884a969fe4da17caryclark do { 7555888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* end = coinPtTEnd()->span(); 7655888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next(); 77c6d855f7f3d548c52f450299dc6975820cda3387caryclark if (next && next->deleted()) { 78c6d855f7f3d548c52f450299dc6975820cda3387caryclark break; 79c6d855f7f3d548c52f450299dc6975820cda3387caryclark } 8055888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* oppPtT; 8155888e44171ffd48b591d19256884a969fe4da17caryclark if (!next || !(oppPtT = next->contains(oppSegment))) { 8255888e44171ffd48b591d19256884a969fe4da17caryclark break; 8355888e44171ffd48b591d19256884a969fe4da17caryclark } 8455888e44171ffd48b591d19256884a969fe4da17caryclark double midT = (end->t() + next->t()) / 2; 8555888e44171ffd48b591d19256884a969fe4da17caryclark if (!segment->isClose(midT, oppSegment)) { 8655888e44171ffd48b591d19256884a969fe4da17caryclark break; 8755888e44171ffd48b591d19256884a969fe4da17caryclark } 8855888e44171ffd48b591d19256884a969fe4da17caryclark setEnds(next->ptT(), oppPtT); 8955888e44171ffd48b591d19256884a969fe4da17caryclark expanded = true; 9055888e44171ffd48b591d19256884a969fe4da17caryclark } while (true); 9155888e44171ffd48b591d19256884a969fe4da17caryclark return expanded; 9255888e44171ffd48b591d19256884a969fe4da17caryclark} 9355888e44171ffd48b591d19256884a969fe4da17caryclark 9455888e44171ffd48b591d19256884a969fe4da17caryclark// increase the range of this span 9555888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkCoincidentSpans::extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, 9655888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) { 9755888e44171ffd48b591d19256884a969fe4da17caryclark bool result = false; 9855888e44171ffd48b591d19256884a969fe4da17caryclark if (fCoinPtTStart->fT > coinPtTStart->fT || (this->flipped() 9955888e44171ffd48b591d19256884a969fe4da17caryclark ? fOppPtTStart->fT < oppPtTStart->fT : fOppPtTStart->fT > oppPtTStart->fT)) { 10055888e44171ffd48b591d19256884a969fe4da17caryclark this->setStarts(coinPtTStart, oppPtTStart); 10155888e44171ffd48b591d19256884a969fe4da17caryclark result = true; 10255888e44171ffd48b591d19256884a969fe4da17caryclark } 10355888e44171ffd48b591d19256884a969fe4da17caryclark if (fCoinPtTEnd->fT < coinPtTEnd->fT || (this->flipped() 10455888e44171ffd48b591d19256884a969fe4da17caryclark ? fOppPtTEnd->fT > oppPtTEnd->fT : fOppPtTEnd->fT < oppPtTEnd->fT)) { 10555888e44171ffd48b591d19256884a969fe4da17caryclark this->setEnds(coinPtTEnd, oppPtTEnd); 10655888e44171ffd48b591d19256884a969fe4da17caryclark result = true; 10755888e44171ffd48b591d19256884a969fe4da17caryclark } 10855888e44171ffd48b591d19256884a969fe4da17caryclark return result; 10955888e44171ffd48b591d19256884a969fe4da17caryclark} 11055888e44171ffd48b591d19256884a969fe4da17caryclark 11155888e44171ffd48b591d19256884a969fe4da17caryclark// set the range of this span 11255888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkCoincidentSpans::set(SkCoincidentSpans* next, const SkOpPtT* coinPtTStart, 113ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) { 11455888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(SkOpCoincidence::Ordered(coinPtTStart, oppPtTStart)); 11555888e44171ffd48b591d19256884a969fe4da17caryclark fNext = next; 11655888e44171ffd48b591d19256884a969fe4da17caryclark this->setStarts(coinPtTStart, oppPtTStart); 11755888e44171ffd48b591d19256884a969fe4da17caryclark this->setEnds(coinPtTEnd, oppPtTEnd); 11855888e44171ffd48b591d19256884a969fe4da17caryclark} 11955888e44171ffd48b591d19256884a969fe4da17caryclark 12055888e44171ffd48b591d19256884a969fe4da17caryclark// returns true if both points are inside this 12155888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkCoincidentSpans::contains(const SkOpPtT* s, const SkOpPtT* e) const { 12255888e44171ffd48b591d19256884a969fe4da17caryclark if (s->fT > e->fT) { 12355888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(s, e); 12455888e44171ffd48b591d19256884a969fe4da17caryclark } 12555888e44171ffd48b591d19256884a969fe4da17caryclark if (s->segment() == fCoinPtTStart->segment()) { 12655888e44171ffd48b591d19256884a969fe4da17caryclark return fCoinPtTStart->fT <= s->fT && e->fT <= fCoinPtTEnd->fT; 12755888e44171ffd48b591d19256884a969fe4da17caryclark } else { 12855888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(s->segment() == fOppPtTStart->segment()); 12955888e44171ffd48b591d19256884a969fe4da17caryclark double oppTs = fOppPtTStart->fT; 13055888e44171ffd48b591d19256884a969fe4da17caryclark double oppTe = fOppPtTEnd->fT; 13155888e44171ffd48b591d19256884a969fe4da17caryclark if (oppTs > oppTe) { 13255888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(oppTs, oppTe); 13355888e44171ffd48b591d19256884a969fe4da17caryclark } 13455888e44171ffd48b591d19256884a969fe4da17caryclark return oppTs <= s->fT && e->fT <= oppTe; 13555888e44171ffd48b591d19256884a969fe4da17caryclark } 13655888e44171ffd48b591d19256884a969fe4da17caryclark} 13755888e44171ffd48b591d19256884a969fe4da17caryclark 138db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark// out of line since this function is referenced by address 139db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clarkconst SkOpPtT* SkCoincidentSpans::oppPtTStart() const { 140db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark return fOppPtTStart; 141db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark} 142db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark 143db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark// out of line since this function is referenced by address 144db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clarkconst SkOpPtT* SkCoincidentSpans::oppPtTEnd() const { 145db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark return fOppPtTEnd; 146db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark} 147db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark 14881a478ca6c36aac3e53ce0373a281ac8940f4780caryclark// A coincident span is unordered if the pairs of points in the main and opposite curves' 14981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark// t values do not ascend or descend. For instance, if a tightly arced quadratic is 15081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark// coincident with another curve, it may intersect it out of order. 151a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclarkbool SkCoincidentSpans::ordered(bool* result) const { 15281a478ca6c36aac3e53ce0373a281ac8940f4780caryclark const SkOpSpanBase* start = this->coinPtTStart()->span(); 15381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark const SkOpSpanBase* end = this->coinPtTEnd()->span(); 15481a478ca6c36aac3e53ce0373a281ac8940f4780caryclark const SkOpSpanBase* next = start->upCast()->next(); 15581a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if (next == end) { 156a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark *result = true; 15781a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 15881a478ca6c36aac3e53ce0373a281ac8940f4780caryclark } 15981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark bool flipped = this->flipped(); 16081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark const SkOpSegment* oppSeg = this->oppPtTStart()->segment(); 16181a478ca6c36aac3e53ce0373a281ac8940f4780caryclark double oppLastT = fOppPtTStart->fT; 16281a478ca6c36aac3e53ce0373a281ac8940f4780caryclark do { 16381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark const SkOpPtT* opp = next->contains(oppSeg); 16481a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if (!opp) { 165ab2d73b06fe6c518be1d399a79c9cc39db21abb6Cary Clark// SkOPOBJASSERT(start, 0); // may assert if coincident span isn't fully processed 166a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark return false; 16781a478ca6c36aac3e53ce0373a281ac8940f4780caryclark } 16881a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if ((oppLastT > opp->fT) != flipped) { 169a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark *result = false; 170a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark return true; 17181a478ca6c36aac3e53ce0373a281ac8940f4780caryclark } 17281a478ca6c36aac3e53ce0373a281ac8940f4780caryclark oppLastT = opp->fT; 17381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if (next == end) { 17481a478ca6c36aac3e53ce0373a281ac8940f4780caryclark break; 17581a478ca6c36aac3e53ce0373a281ac8940f4780caryclark } 176bbfe92bc1dd2b0a65e63b3caed9873dbc4df522acaryclark if (!next->upCastable()) { 177a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark *result = false; 178a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark return true; 179bbfe92bc1dd2b0a65e63b3caed9873dbc4df522acaryclark } 18081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark next = next->upCast()->next(); 18181a478ca6c36aac3e53ce0373a281ac8940f4780caryclark } while (true); 182a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark *result = true; 18381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 18481a478ca6c36aac3e53ce0373a281ac8940f4780caryclark} 18581a478ca6c36aac3e53ce0373a281ac8940f4780caryclark 18655888e44171ffd48b591d19256884a969fe4da17caryclark// if there is an existing pair that overlaps the addition, extend it 18755888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, 18855888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) { 18955888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* test = fHead; 19055888e44171ffd48b591d19256884a969fe4da17caryclark if (!test) { 19155888e44171ffd48b591d19256884a969fe4da17caryclark return false; 19255888e44171ffd48b591d19256884a969fe4da17caryclark } 19355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* coinSeg = coinPtTStart->segment(); 19455888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* oppSeg = oppPtTStart->segment(); 19555888e44171ffd48b591d19256884a969fe4da17caryclark if (!Ordered(coinPtTStart, oppPtTStart)) { 19655888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinSeg, oppSeg); 19755888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinPtTStart, oppPtTStart); 19855888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinPtTEnd, oppPtTEnd); 19955888e44171ffd48b591d19256884a969fe4da17caryclark if (coinPtTStart->fT > coinPtTEnd->fT) { 20055888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinPtTStart, coinPtTEnd); 20155888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(oppPtTStart, oppPtTEnd); 20255888e44171ffd48b591d19256884a969fe4da17caryclark } 20355888e44171ffd48b591d19256884a969fe4da17caryclark } 20455888e44171ffd48b591d19256884a969fe4da17caryclark double oppMinT = SkTMin(oppPtTStart->fT, oppPtTEnd->fT); 20555888e44171ffd48b591d19256884a969fe4da17caryclark SkDEBUGCODE(double oppMaxT = SkTMax(oppPtTStart->fT, oppPtTEnd->fT)); 20655888e44171ffd48b591d19256884a969fe4da17caryclark do { 20755888e44171ffd48b591d19256884a969fe4da17caryclark if (coinSeg != test->coinPtTStart()->segment()) { 20855888e44171ffd48b591d19256884a969fe4da17caryclark continue; 20955888e44171ffd48b591d19256884a969fe4da17caryclark } 21055888e44171ffd48b591d19256884a969fe4da17caryclark if (oppSeg != test->oppPtTStart()->segment()) { 21155888e44171ffd48b591d19256884a969fe4da17caryclark continue; 21255888e44171ffd48b591d19256884a969fe4da17caryclark } 21355888e44171ffd48b591d19256884a969fe4da17caryclark double oTestMinT = SkTMin(test->oppPtTStart()->fT, test->oppPtTEnd()->fT); 21455888e44171ffd48b591d19256884a969fe4da17caryclark double oTestMaxT = SkTMax(test->oppPtTStart()->fT, test->oppPtTEnd()->fT); 21555888e44171ffd48b591d19256884a969fe4da17caryclark // if debug check triggers, caller failed to check if extended already exists 21655888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(test->coinPtTStart()->fT > coinPtTStart->fT 21755888e44171ffd48b591d19256884a969fe4da17caryclark || coinPtTEnd->fT > test->coinPtTEnd()->fT 21855888e44171ffd48b591d19256884a969fe4da17caryclark || oTestMinT > oppMinT || oppMaxT > oTestMaxT); 21955888e44171ffd48b591d19256884a969fe4da17caryclark if ((test->coinPtTStart()->fT <= coinPtTEnd->fT 22055888e44171ffd48b591d19256884a969fe4da17caryclark && coinPtTStart->fT <= test->coinPtTEnd()->fT) 22155888e44171ffd48b591d19256884a969fe4da17caryclark || (oTestMinT <= oTestMaxT && oppMinT <= oTestMaxT)) { 22255888e44171ffd48b591d19256884a969fe4da17caryclark test->extend(coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd); 22355888e44171ffd48b591d19256884a969fe4da17caryclark return true; 22455888e44171ffd48b591d19256884a969fe4da17caryclark } 22555888e44171ffd48b591d19256884a969fe4da17caryclark } while ((test = test->next())); 22655888e44171ffd48b591d19256884a969fe4da17caryclark return false; 22755888e44171ffd48b591d19256884a969fe4da17caryclark} 22855888e44171ffd48b591d19256884a969fe4da17caryclark 22955888e44171ffd48b591d19256884a969fe4da17caryclark// verifies that the coincidence hasn't already been added 23055888e44171ffd48b591d19256884a969fe4da17caryclarkstatic void DebugCheckAdd(const SkCoincidentSpans* check, const SkOpPtT* coinPtTStart, 23155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) { 23255888e44171ffd48b591d19256884a969fe4da17caryclark#if DEBUG_COINCIDENCE 23355888e44171ffd48b591d19256884a969fe4da17caryclark while (check) { 23455888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(check->coinPtTStart() != coinPtTStart || check->coinPtTEnd() != coinPtTEnd 23555888e44171ffd48b591d19256884a969fe4da17caryclark || check->oppPtTStart() != oppPtTStart || check->oppPtTEnd() != oppPtTEnd); 23655888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(check->coinPtTStart() != oppPtTStart || check->coinPtTEnd() != oppPtTEnd 23755888e44171ffd48b591d19256884a969fe4da17caryclark || check->oppPtTStart() != coinPtTStart || check->oppPtTEnd() != coinPtTEnd); 23855888e44171ffd48b591d19256884a969fe4da17caryclark check = check->next(); 23955888e44171ffd48b591d19256884a969fe4da17caryclark } 24055888e44171ffd48b591d19256884a969fe4da17caryclark#endif 24155888e44171ffd48b591d19256884a969fe4da17caryclark} 24255888e44171ffd48b591d19256884a969fe4da17caryclark 24355888e44171ffd48b591d19256884a969fe4da17caryclark// adds a new coincident pair 24455888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpCoincidence::add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart, 24555888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* oppPtTEnd) { 24655888e44171ffd48b591d19256884a969fe4da17caryclark // OPTIMIZE: caller should have already sorted 24755888e44171ffd48b591d19256884a969fe4da17caryclark if (!Ordered(coinPtTStart, oppPtTStart)) { 24855888e44171ffd48b591d19256884a969fe4da17caryclark if (oppPtTStart->fT < oppPtTEnd->fT) { 24955888e44171ffd48b591d19256884a969fe4da17caryclark this->add(oppPtTStart, oppPtTEnd, coinPtTStart, coinPtTEnd); 25055888e44171ffd48b591d19256884a969fe4da17caryclark } else { 25155888e44171ffd48b591d19256884a969fe4da17caryclark this->add(oppPtTEnd, oppPtTStart, coinPtTEnd, coinPtTStart); 25255888e44171ffd48b591d19256884a969fe4da17caryclark } 25355888e44171ffd48b591d19256884a969fe4da17caryclark return; 25455888e44171ffd48b591d19256884a969fe4da17caryclark } 25555888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(Ordered(coinPtTStart, oppPtTStart)); 25655888e44171ffd48b591d19256884a969fe4da17caryclark // choose the ptT at the front of the list to track 25755888e44171ffd48b591d19256884a969fe4da17caryclark coinPtTStart = coinPtTStart->span()->ptT(); 25855888e44171ffd48b591d19256884a969fe4da17caryclark coinPtTEnd = coinPtTEnd->span()->ptT(); 25955888e44171ffd48b591d19256884a969fe4da17caryclark oppPtTStart = oppPtTStart->span()->ptT(); 26055888e44171ffd48b591d19256884a969fe4da17caryclark oppPtTEnd = oppPtTEnd->span()->ptT(); 261a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark SkOPASSERT(coinPtTStart->fT < coinPtTEnd->fT); 26296dc1c9efaab4636e30f90aa377f25863f9bf3bacaryclark SkOPASSERT(oppPtTStart->fT != oppPtTEnd->fT); 26330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOPASSERT(!coinPtTStart->deleted()); 26430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOPASSERT(!coinPtTEnd->deleted()); 26530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOPASSERT(!oppPtTStart->deleted()); 26630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOPASSERT(!oppPtTEnd->deleted()); 26755888e44171ffd48b591d19256884a969fe4da17caryclark DebugCheckAdd(fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd); 26855888e44171ffd48b591d19256884a969fe4da17caryclark DebugCheckAdd(fTop, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd); 26955888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* coinRec = SkOpTAllocator<SkCoincidentSpans>::Allocate( 27055888e44171ffd48b591d19256884a969fe4da17caryclark this->globalState()->allocator()); 271fc560e09b3f777bb32dccb9f52d715383a10a620caryclark coinRec->init(SkDEBUGCODE(fGlobalState)); 272ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark coinRec->set(this->fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd); 27355888e44171ffd48b591d19256884a969fe4da17caryclark fHead = coinRec; 27455888e44171ffd48b591d19256884a969fe4da17caryclark} 27555888e44171ffd48b591d19256884a969fe4da17caryclark 27655888e44171ffd48b591d19256884a969fe4da17caryclark// description below 2771597628fa38d24f23ad505bfb40e70e7c8617457caryclarkbool SkOpCoincidence::addEndMovedSpans(const SkOpSpan* base, const SkOpSpanBase* testSpan) { 27855888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* testPtT = testSpan->ptT(); 27955888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* stopPtT = testPtT; 28055888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* baseSeg = base->segment(); 28155888e44171ffd48b591d19256884a969fe4da17caryclark while ((testPtT = testPtT->next()) != stopPtT) { 28255888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* testSeg = testPtT->segment(); 28355888e44171ffd48b591d19256884a969fe4da17caryclark if (testPtT->deleted()) { 28455888e44171ffd48b591d19256884a969fe4da17caryclark continue; 28555888e44171ffd48b591d19256884a969fe4da17caryclark } 28655888e44171ffd48b591d19256884a969fe4da17caryclark if (testSeg == baseSeg) { 28755888e44171ffd48b591d19256884a969fe4da17caryclark continue; 28855888e44171ffd48b591d19256884a969fe4da17caryclark } 289c6d855f7f3d548c52f450299dc6975820cda3387caryclark if (testPtT->span()->ptT() != testPtT) { 290c6d855f7f3d548c52f450299dc6975820cda3387caryclark continue; 291c6d855f7f3d548c52f450299dc6975820cda3387caryclark } 29255888e44171ffd48b591d19256884a969fe4da17caryclark if (this->contains(baseSeg, testSeg, testPtT->fT)) { 29355888e44171ffd48b591d19256884a969fe4da17caryclark continue; 29455888e44171ffd48b591d19256884a969fe4da17caryclark } 29555888e44171ffd48b591d19256884a969fe4da17caryclark // intersect perp with base->ptT() with testPtT->segment() 29655888e44171ffd48b591d19256884a969fe4da17caryclark SkDVector dxdy = baseSeg->dSlopeAtT(base->t()); 29755888e44171ffd48b591d19256884a969fe4da17caryclark const SkPoint& pt = base->pt(); 29855888e44171ffd48b591d19256884a969fe4da17caryclark SkDLine ray = {{{pt.fX, pt.fY}, {pt.fX + dxdy.fY, pt.fY - dxdy.fX}}}; 2994c76c41c981dd7ea95062a1895a6e3415b70bce1Cary Clark SkIntersections i SkDEBUGCODE((this->globalState())); 30055888e44171ffd48b591d19256884a969fe4da17caryclark (*CurveIntersectRay[testSeg->verb()])(testSeg->pts(), testSeg->weight(), ray, &i); 30155888e44171ffd48b591d19256884a969fe4da17caryclark for (int index = 0; index < i.used(); ++index) { 30255888e44171ffd48b591d19256884a969fe4da17caryclark double t = i[0][index]; 30355888e44171ffd48b591d19256884a969fe4da17caryclark if (!between(0, t, 1)) { 304bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark continue; 305bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 30655888e44171ffd48b591d19256884a969fe4da17caryclark SkDPoint oppPt = i.pt(index); 30755888e44171ffd48b591d19256884a969fe4da17caryclark if (!oppPt.approximatelyEqual(pt)) { 308bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark continue; 309bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 31055888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSegment* writableSeg = const_cast<SkOpSegment*>(testSeg); 31129b2563afb1677515739f1d24fb27733626eca92caryclark SkOpPtT* oppStart = writableSeg->addT(t); 31227c015dfcf4e2b8fb1abe327cc40204e2a4f452acaryclark if (oppStart == testPtT) { 31327c015dfcf4e2b8fb1abe327cc40204e2a4f452acaryclark continue; 31427c015dfcf4e2b8fb1abe327cc40204e2a4f452acaryclark } 31555888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpan* writableBase = const_cast<SkOpSpan*>(base); 31630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark oppStart->span()->addOpp(writableBase); 31755888e44171ffd48b591d19256884a969fe4da17caryclark if (oppStart->deleted()) { 318bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark continue; 319bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 32055888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSegment* coinSeg = base->segment(); 32155888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSegment* oppSeg = oppStart->segment(); 32255888e44171ffd48b591d19256884a969fe4da17caryclark double coinTs, coinTe, oppTs, oppTe; 3238016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (Ordered(coinSeg, oppSeg)) { 32455888e44171ffd48b591d19256884a969fe4da17caryclark coinTs = base->t(); 32555888e44171ffd48b591d19256884a969fe4da17caryclark coinTe = testSpan->t(); 32655888e44171ffd48b591d19256884a969fe4da17caryclark oppTs = oppStart->fT; 32755888e44171ffd48b591d19256884a969fe4da17caryclark oppTe = testPtT->fT; 32855888e44171ffd48b591d19256884a969fe4da17caryclark } else { 32955888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinSeg, oppSeg); 33055888e44171ffd48b591d19256884a969fe4da17caryclark coinTs = oppStart->fT; 33155888e44171ffd48b591d19256884a969fe4da17caryclark coinTe = testPtT->fT; 33255888e44171ffd48b591d19256884a969fe4da17caryclark oppTs = base->t(); 33355888e44171ffd48b591d19256884a969fe4da17caryclark oppTe = testSpan->t(); 334bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 33555888e44171ffd48b591d19256884a969fe4da17caryclark if (coinTs > coinTe) { 33655888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinTs, coinTe); 33755888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(oppTs, oppTe); 338bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 33981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark bool added; 34081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if (!this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &added)) { 3411597628fa38d24f23ad505bfb40e70e7c8617457caryclark return false; 3421597628fa38d24f23ad505bfb40e70e7c8617457caryclark } 34355888e44171ffd48b591d19256884a969fe4da17caryclark } 344bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 3451597628fa38d24f23ad505bfb40e70e7c8617457caryclark return true; 346bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark} 347bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark 34855888e44171ffd48b591d19256884a969fe4da17caryclark// description below 34955888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::addEndMovedSpans(const SkOpPtT* ptT) { 350025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark FAIL_IF(!ptT->span()->upCastable()); 35155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpan* base = ptT->span()->upCast(); 35255888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpan* prev = base->prev(); 353025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark FAIL_IF(!prev); 35455888e44171ffd48b591d19256884a969fe4da17caryclark if (!prev->isCanceled()) { 3551597628fa38d24f23ad505bfb40e70e7c8617457caryclark if (!this->addEndMovedSpans(base, base->prev())) { 3561597628fa38d24f23ad505bfb40e70e7c8617457caryclark return false; 3571597628fa38d24f23ad505bfb40e70e7c8617457caryclark } 35855888e44171ffd48b591d19256884a969fe4da17caryclark } 35955888e44171ffd48b591d19256884a969fe4da17caryclark if (!base->isCanceled()) { 3601597628fa38d24f23ad505bfb40e70e7c8617457caryclark if (!this->addEndMovedSpans(base, base->next())) { 3611597628fa38d24f23ad505bfb40e70e7c8617457caryclark return false; 3621597628fa38d24f23ad505bfb40e70e7c8617457caryclark } 36355888e44171ffd48b591d19256884a969fe4da17caryclark } 36455888e44171ffd48b591d19256884a969fe4da17caryclark return true; 36554359294a7c9dc54802d512a5d891a35c1663392caryclark} 36654359294a7c9dc54802d512a5d891a35c1663392caryclark 36755888e44171ffd48b591d19256884a969fe4da17caryclark/* If A is coincident with B and B includes an endpoint, and A's matching point 36855888e44171ffd48b591d19256884a969fe4da17caryclark is not the endpoint (i.e., there's an implied line connecting B-end and A) 36955888e44171ffd48b591d19256884a969fe4da17caryclark then assume that the same implied line may intersect another curve close to B. 37055888e44171ffd48b591d19256884a969fe4da17caryclark Since we only care about coincidence that was undetected, look at the 37155888e44171ffd48b591d19256884a969fe4da17caryclark ptT list on B-segment adjacent to the B-end/A ptT loop (not in the loop, but 37255888e44171ffd48b591d19256884a969fe4da17caryclark next door) and see if the A matching point is close enough to form another 37355888e44171ffd48b591d19256884a969fe4da17caryclark coincident pair. If so, check for a new coincident span between B-end/A ptT loop 37455888e44171ffd48b591d19256884a969fe4da17caryclark and the adjacent ptT loop. 37555888e44171ffd48b591d19256884a969fe4da17caryclark*/ 376ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clarkbool SkOpCoincidence::addEndMovedSpans(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 377ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark DEBUG_SET_PHASE(); 37855888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* span = fHead; 37955888e44171ffd48b591d19256884a969fe4da17caryclark if (!span) { 38055888e44171ffd48b591d19256884a969fe4da17caryclark return true; 38155888e44171ffd48b591d19256884a969fe4da17caryclark } 38255888e44171ffd48b591d19256884a969fe4da17caryclark fTop = span; 38355888e44171ffd48b591d19256884a969fe4da17caryclark fHead = nullptr; 38455888e44171ffd48b591d19256884a969fe4da17caryclark do { 38555888e44171ffd48b591d19256884a969fe4da17caryclark if (span->coinPtTStart()->fPt != span->oppPtTStart()->fPt) { 386025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark FAIL_IF(1 == span->coinPtTStart()->fT); 38755888e44171ffd48b591d19256884a969fe4da17caryclark bool onEnd = span->coinPtTStart()->fT == 0; 38855888e44171ffd48b591d19256884a969fe4da17caryclark bool oOnEnd = zero_or_one(span->oppPtTStart()->fT); 38955888e44171ffd48b591d19256884a969fe4da17caryclark if (onEnd) { 39055888e44171ffd48b591d19256884a969fe4da17caryclark if (!oOnEnd) { // if both are on end, any nearby intersect was already found 39155888e44171ffd48b591d19256884a969fe4da17caryclark if (!this->addEndMovedSpans(span->oppPtTStart())) { 39255888e44171ffd48b591d19256884a969fe4da17caryclark return false; 39355888e44171ffd48b591d19256884a969fe4da17caryclark } 39455888e44171ffd48b591d19256884a969fe4da17caryclark } 39555888e44171ffd48b591d19256884a969fe4da17caryclark } else if (oOnEnd) { 39655888e44171ffd48b591d19256884a969fe4da17caryclark if (!this->addEndMovedSpans(span->coinPtTStart())) { 39755888e44171ffd48b591d19256884a969fe4da17caryclark return false; 39855888e44171ffd48b591d19256884a969fe4da17caryclark } 39955888e44171ffd48b591d19256884a969fe4da17caryclark } 40055888e44171ffd48b591d19256884a969fe4da17caryclark } 40155888e44171ffd48b591d19256884a969fe4da17caryclark if (span->coinPtTEnd()->fPt != span->oppPtTEnd()->fPt) { 40255888e44171ffd48b591d19256884a969fe4da17caryclark bool onEnd = span->coinPtTEnd()->fT == 1; 40355888e44171ffd48b591d19256884a969fe4da17caryclark bool oOnEnd = zero_or_one(span->oppPtTEnd()->fT); 40455888e44171ffd48b591d19256884a969fe4da17caryclark if (onEnd) { 40555888e44171ffd48b591d19256884a969fe4da17caryclark if (!oOnEnd) { 40655888e44171ffd48b591d19256884a969fe4da17caryclark if (!this->addEndMovedSpans(span->oppPtTEnd())) { 40755888e44171ffd48b591d19256884a969fe4da17caryclark return false; 40855888e44171ffd48b591d19256884a969fe4da17caryclark } 40955888e44171ffd48b591d19256884a969fe4da17caryclark } 41055888e44171ffd48b591d19256884a969fe4da17caryclark } else if (oOnEnd) { 41155888e44171ffd48b591d19256884a969fe4da17caryclark if (!this->addEndMovedSpans(span->coinPtTEnd())) { 41255888e44171ffd48b591d19256884a969fe4da17caryclark return false; 41355888e44171ffd48b591d19256884a969fe4da17caryclark } 41455888e44171ffd48b591d19256884a969fe4da17caryclark } 41555888e44171ffd48b591d19256884a969fe4da17caryclark } 41655888e44171ffd48b591d19256884a969fe4da17caryclark } while ((span = span->next())); 41755888e44171ffd48b591d19256884a969fe4da17caryclark this->restoreHead(); 41855888e44171ffd48b591d19256884a969fe4da17caryclark return true; 41954359294a7c9dc54802d512a5d891a35c1663392caryclark} 42054359294a7c9dc54802d512a5d891a35c1663392caryclark 42155888e44171ffd48b591d19256884a969fe4da17caryclark/* Please keep this in sync with debugAddExpanded */ 42255888e44171ffd48b591d19256884a969fe4da17caryclark// for each coincident pair, match the spans 42355888e44171ffd48b591d19256884a969fe4da17caryclark// if the spans don't match, add the missing pt to the segment and loop it in the opposite span 424ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clarkbool SkOpCoincidence::addExpanded(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 425ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark DEBUG_SET_PHASE(); 42627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkCoincidentSpans* coin = this->fHead; 42755888e44171ffd48b591d19256884a969fe4da17caryclark if (!coin) { 42855888e44171ffd48b591d19256884a969fe4da17caryclark return true; 42955888e44171ffd48b591d19256884a969fe4da17caryclark } 43027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark do { 43155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* startPtT = coin->coinPtTStart(); 43255888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* oStartPtT = coin->oppPtTStart(); 4338016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double priorT = startPtT->fT; 4348016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double oPriorT = oStartPtT->fT; 435bbfe92bc1dd2b0a65e63b3caed9873dbc4df522acaryclark FAIL_IF(!startPtT->contains(oStartPtT)); 436c6d855f7f3d548c52f450299dc6975820cda3387caryclark SkOPASSERT(coin->coinPtTEnd()->contains(coin->oppPtTEnd())); 43755888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* start = startPtT->span(); 43855888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* oStart = oStartPtT->span(); 43955888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* end = coin->coinPtTEnd()->span(); 44055888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* oEnd = coin->oppPtTEnd()->span(); 44155888e44171ffd48b591d19256884a969fe4da17caryclark FAIL_IF(oEnd->deleted()); 442e25a4f6cbeaccfdc34cf031103f0fbc3e53a3ee5caryclark FAIL_IF(!start->upCastable()); 44355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* test = start->upCast()->next(); 444e7bb5b226662f01c91574b29f435acae71c76c46caryclark FAIL_IF(!coin->flipped() && !oStart->upCastable()); 44555888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* oTest = coin->flipped() ? oStart->prev() : oStart->upCast()->next(); 44630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark FAIL_IF(!oTest); 4478016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkOpSegment* seg = start->segment(); 4488016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkOpSegment* oSeg = oStart->segment(); 44927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark while (test != end || oTest != oEnd) { 4508016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* containedOpp = test->ptT()->contains(oSeg); 4518016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* containedThis = oTest->ptT()->contains(seg); 4528016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (!containedOpp || !containedThis) { 4538016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark // choose the ends, or the first common pt-t list shared by both 4548016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double nextT, oNextT; 4558016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (containedOpp) { 4568016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark nextT = test->t(); 4578016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark oNextT = containedOpp->fT; 4588016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark } else if (containedThis) { 4598016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark nextT = containedThis->fT; 4608016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark oNextT = oTest->t(); 4618016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark } else { 4628016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark // iterate through until a pt-t list found that contains the other 4638016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpSpanBase* walk = test; 4648016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* walkOpp; 4658016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark do { 4668016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark FAIL_IF(!walk->upCastable()); 4678016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark walk = walk->upCast()->next(); 4688016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark } while (!(walkOpp = walk->ptT()->contains(oSeg)) 4698016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark && walk != coin->coinPtTEnd()->span()); 4703fdf52cf389d58be9ce4b948dfecffd53edb5da2Cary Clark FAIL_IF(!walkOpp); 4718016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark nextT = walk->t(); 4728016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark oNextT = walkOpp->fT; 4738016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark } 47427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark // use t ranges to guess which one is missing 4758016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double startRange = nextT - priorT; 47655888e44171ffd48b591d19256884a969fe4da17caryclark FAIL_IF(!startRange); 4778016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double startPart = (test->t() - priorT) / startRange; 4788016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double oStartRange = oNextT - oPriorT; 47955888e44171ffd48b591d19256884a969fe4da17caryclark FAIL_IF(!oStartRange); 4808016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double oStartPart = (oTest->t() - oPriorT) / oStartRange; 48155888e44171ffd48b591d19256884a969fe4da17caryclark FAIL_IF(startPart == oStartPart); 4828016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark bool addToOpp = !containedOpp && !containedThis ? startPart < oStartPart 4838016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark : !!containedThis; 48455888e44171ffd48b591d19256884a969fe4da17caryclark bool startOver = false; 4858016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark bool success = addToOpp ? oSeg->addExpanded( 4868016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark oPriorT + oStartRange * startPart, test, &startOver) 4878016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark : seg->addExpanded( 4888016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark priorT + startRange * oStartPart, oTest, &startOver); 48930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark FAIL_IF(!success); 49055888e44171ffd48b591d19256884a969fe4da17caryclark if (startOver) { 49155888e44171ffd48b591d19256884a969fe4da17caryclark test = start; 49255888e44171ffd48b591d19256884a969fe4da17caryclark oTest = oStart; 49327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 49430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark end = coin->coinPtTEnd()->span(); 49530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark oEnd = coin->oppPtTEnd()->span(); 49627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 49727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (test != end) { 49830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark FAIL_IF(!test->upCastable()); 4998016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark priorT = test->t(); 50027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark test = test->upCast()->next(); 50127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 50226ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark if (oTest != oEnd) { 5038016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark oPriorT = oTest->t(); 50478a37a53365c24670b050acf993818c435922745caryclark if (coin->flipped()) { 50578a37a53365c24670b050acf993818c435922745caryclark oTest = oTest->prev(); 50678a37a53365c24670b050acf993818c435922745caryclark } else { 50778a37a53365c24670b050acf993818c435922745caryclark FAIL_IF(!oTest->upCastable()); 50878a37a53365c24670b050acf993818c435922745caryclark oTest = oTest->upCast()->next(); 50978a37a53365c24670b050acf993818c435922745caryclark } 51030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark FAIL_IF(!oTest); 51127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 5128016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark 51327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 51455888e44171ffd48b591d19256884a969fe4da17caryclark } while ((coin = coin->next())); 51526ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark return true; 51627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 51727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 51855888e44171ffd48b591d19256884a969fe4da17caryclark// given a t span, map the same range on the coincident span 5198016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark/* 5208016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclarkthe curves may not scale linearly, so interpolation may only happen within known points 5218016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclarkremap over1s, over1e, cointPtTStart, coinPtTEnd to smallest range that captures over1s 5228016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclarkthen repeat to capture over1e 5238016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark*/ 5248016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclarkdouble SkOpCoincidence::TRange(const SkOpPtT* overS, double t, 5258016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpSegment* coinSeg SkDEBUGPARAMS(const SkOpPtT* overE)) { 5268016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpSpanBase* work = overS->span(); 5278016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* foundStart = nullptr; 5288016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* foundEnd = nullptr; 5298016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* coinStart = nullptr; 5308016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* coinEnd = nullptr; 5318016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark do { 5328016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* contained = work->contains(coinSeg); 5338016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (!contained) { 534c9b90d15df5fcee848812fbab3d714aba9e41e69caryclark if (work->final()) { 535c9b90d15df5fcee848812fbab3d714aba9e41e69caryclark break; 536b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark } 5378016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark continue; 5388016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark } 5398016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (work->t() <= t) { 5408016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark coinStart = contained; 5418016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark foundStart = work->ptT(); 5428016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark } 5438016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (work->t() >= t) { 5448016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark coinEnd = contained; 5458016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark foundEnd = work->ptT(); 5468016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark break; 5478016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark } 5488016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(work->ptT() != overE); 5498016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark } while ((work = work->upCast()->next())); 550c9b90d15df5fcee848812fbab3d714aba9e41e69caryclark if (!coinStart || !coinEnd) { 551c9b90d15df5fcee848812fbab3d714aba9e41e69caryclark return 1; 552c9b90d15df5fcee848812fbab3d714aba9e41e69caryclark } 5538016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark // while overS->fT <=t and overS contains coinSeg 5548016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double denom = foundEnd->fT - foundStart->fT; 5558016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double sRatio = denom ? (t - foundStart->fT) / denom : 1; 5568016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark return coinStart->fT + (coinEnd->fT - coinStart->fT) * sRatio; 55755888e44171ffd48b591d19256884a969fe4da17caryclark} 55855888e44171ffd48b591d19256884a969fe4da17caryclark 55955888e44171ffd48b591d19256884a969fe4da17caryclark// return true if span overlaps existing and needs to adjust the coincident list 56055888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::checkOverlap(SkCoincidentSpans* check, 56155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* coinSeg, const SkOpSegment* oppSeg, 56255888e44171ffd48b591d19256884a969fe4da17caryclark double coinTs, double coinTe, double oppTs, double oppTe, 56355888e44171ffd48b591d19256884a969fe4da17caryclark SkTDArray<SkCoincidentSpans*>* overlaps) const { 56455888e44171ffd48b591d19256884a969fe4da17caryclark if (!Ordered(coinSeg, oppSeg)) { 56555888e44171ffd48b591d19256884a969fe4da17caryclark if (oppTs < oppTe) { 56655888e44171ffd48b591d19256884a969fe4da17caryclark return this->checkOverlap(check, oppSeg, coinSeg, oppTs, oppTe, coinTs, coinTe, 56755888e44171ffd48b591d19256884a969fe4da17caryclark overlaps); 56855888e44171ffd48b591d19256884a969fe4da17caryclark } 56955888e44171ffd48b591d19256884a969fe4da17caryclark return this->checkOverlap(check, oppSeg, coinSeg, oppTe, oppTs, coinTe, coinTs, overlaps); 57055888e44171ffd48b591d19256884a969fe4da17caryclark } 57155888e44171ffd48b591d19256884a969fe4da17caryclark bool swapOpp = oppTs > oppTe; 57255888e44171ffd48b591d19256884a969fe4da17caryclark if (swapOpp) { 57355888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(oppTs, oppTe); 57455888e44171ffd48b591d19256884a969fe4da17caryclark } 57527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark do { 57655888e44171ffd48b591d19256884a969fe4da17caryclark if (check->coinPtTStart()->segment() != coinSeg) { 57755888e44171ffd48b591d19256884a969fe4da17caryclark continue; 57827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 57955888e44171ffd48b591d19256884a969fe4da17caryclark if (check->oppPtTStart()->segment() != oppSeg) { 58055888e44171ffd48b591d19256884a969fe4da17caryclark continue; 58127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 58255888e44171ffd48b591d19256884a969fe4da17caryclark double checkTs = check->coinPtTStart()->fT; 58355888e44171ffd48b591d19256884a969fe4da17caryclark double checkTe = check->coinPtTEnd()->fT; 58455888e44171ffd48b591d19256884a969fe4da17caryclark bool coinOutside = coinTe < checkTs || coinTs > checkTe; 58555888e44171ffd48b591d19256884a969fe4da17caryclark double oCheckTs = check->oppPtTStart()->fT; 58655888e44171ffd48b591d19256884a969fe4da17caryclark double oCheckTe = check->oppPtTEnd()->fT; 58755888e44171ffd48b591d19256884a969fe4da17caryclark if (swapOpp) { 58855888e44171ffd48b591d19256884a969fe4da17caryclark if (oCheckTs <= oCheckTe) { 58981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return false; 59055888e44171ffd48b591d19256884a969fe4da17caryclark } 59155888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(oCheckTs, oCheckTe); 59255888e44171ffd48b591d19256884a969fe4da17caryclark } 59355888e44171ffd48b591d19256884a969fe4da17caryclark bool oppOutside = oppTe < oCheckTs || oppTs > oCheckTe; 59455888e44171ffd48b591d19256884a969fe4da17caryclark if (coinOutside && oppOutside) { 59555888e44171ffd48b591d19256884a969fe4da17caryclark continue; 59655888e44171ffd48b591d19256884a969fe4da17caryclark } 59755888e44171ffd48b591d19256884a969fe4da17caryclark bool coinInside = coinTe <= checkTe && coinTs >= checkTs; 59855888e44171ffd48b591d19256884a969fe4da17caryclark bool oppInside = oppTe <= oCheckTe && oppTs >= oCheckTs; 59981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if (coinInside && oppInside) { // already included, do nothing 60081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return false; 60155888e44171ffd48b591d19256884a969fe4da17caryclark } 60255888e44171ffd48b591d19256884a969fe4da17caryclark *overlaps->append() = check; // partial overlap, extend existing entry 60355888e44171ffd48b591d19256884a969fe4da17caryclark } while ((check = check->next())); 60426ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark return true; 60527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 60627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 60755888e44171ffd48b591d19256884a969fe4da17caryclark/* Please keep this in sync with debugAddIfMissing() */ 6088016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark// note that over1s, over1e, over2s, over2e are ordered 6098016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclarkbool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over2s, 61081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark double tStart, double tEnd, SkOpSegment* coinSeg, SkOpSegment* oppSeg, bool* added 6118016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(const SkOpPtT* over1e) SkDEBUGPARAMS(const SkOpPtT* over2e)) { 6128016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(tStart < tEnd); 6138016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(over1s->fT < over1e->fT); 6148016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(between(over1s->fT, tStart, over1e->fT)); 6158016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(between(over1s->fT, tEnd, over1e->fT)); 6168016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(over2s->fT < over2e->fT); 6178016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(between(over2s->fT, tStart, over2e->fT)); 6188016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(between(over2s->fT, tEnd, over2e->fT)); 6198016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(over1s->segment() == over1e->segment()); 6208016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(over2s->segment() == over2e->segment()); 6218016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(over1s->segment() == over2s->segment()); 6228016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(over1s->segment() != coinSeg); 6238016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(over1s->segment() != oppSeg); 6248016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(coinSeg != oppSeg); 62554359294a7c9dc54802d512a5d891a35c1663392caryclark double coinTs, coinTe, oppTs, oppTe; 6268016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark coinTs = TRange(over1s, tStart, coinSeg SkDEBUGPARAMS(over1e)); 6278016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark coinTe = TRange(over1s, tEnd, coinSeg SkDEBUGPARAMS(over1e)); 62830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (coinSeg->collapsed(coinTs, coinTe)) { 62981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 63030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 6318016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark oppTs = TRange(over2s, tStart, oppSeg SkDEBUGPARAMS(over2e)); 6328016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark oppTe = TRange(over2s, tEnd, oppSeg SkDEBUGPARAMS(over2e)); 63330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (oppSeg->collapsed(oppTs, oppTe)) { 63481a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 63530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 6368016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (coinTs > coinTe) { 63755888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinTs, coinTe); 63855888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(oppTs, oppTe); 63955888e44171ffd48b591d19256884a969fe4da17caryclark } 64081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, added); 64155888e44171ffd48b591d19256884a969fe4da17caryclark} 64255888e44171ffd48b591d19256884a969fe4da17caryclark 64355888e44171ffd48b591d19256884a969fe4da17caryclark/* Please keep this in sync with debugAddOrOverlap() */ 644025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark// If this is called by addEndMovedSpans(), a returned false propogates out to an abort. 645025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark// If this is called by AddIfMissing(), a returned false indicates there was nothing to add 64655888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg, 64781a478ca6c36aac3e53ce0373a281ac8940f4780caryclark double coinTs, double coinTe, double oppTs, double oppTe, bool* added) { 64855888e44171ffd48b591d19256884a969fe4da17caryclark SkTDArray<SkCoincidentSpans*> overlaps; 64981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(!fTop); 65055888e44171ffd48b591d19256884a969fe4da17caryclark if (!this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &overlaps)) { 65181a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 65255888e44171ffd48b591d19256884a969fe4da17caryclark } 65355888e44171ffd48b591d19256884a969fe4da17caryclark if (fHead && !this->checkOverlap(fHead, coinSeg, oppSeg, coinTs, 65455888e44171ffd48b591d19256884a969fe4da17caryclark coinTe, oppTs, oppTe, &overlaps)) { 65581a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 65655888e44171ffd48b591d19256884a969fe4da17caryclark } 65755888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* overlap = overlaps.count() ? overlaps[0] : nullptr; 65855888e44171ffd48b591d19256884a969fe4da17caryclark for (int index = 1; index < overlaps.count(); ++index) { // combine overlaps before continuing 65955888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* test = overlaps[index]; 66055888e44171ffd48b591d19256884a969fe4da17caryclark if (overlap->coinPtTStart()->fT > test->coinPtTStart()->fT) { 66155888e44171ffd48b591d19256884a969fe4da17caryclark overlap->setCoinPtTStart(test->coinPtTStart()); 66254359294a7c9dc54802d512a5d891a35c1663392caryclark } 66355888e44171ffd48b591d19256884a969fe4da17caryclark if (overlap->coinPtTEnd()->fT < test->coinPtTEnd()->fT) { 66455888e44171ffd48b591d19256884a969fe4da17caryclark overlap->setCoinPtTEnd(test->coinPtTEnd()); 66555888e44171ffd48b591d19256884a969fe4da17caryclark } 66655888e44171ffd48b591d19256884a969fe4da17caryclark if (overlap->flipped() 66755888e44171ffd48b591d19256884a969fe4da17caryclark ? overlap->oppPtTStart()->fT < test->oppPtTStart()->fT 66855888e44171ffd48b591d19256884a969fe4da17caryclark : overlap->oppPtTStart()->fT > test->oppPtTStart()->fT) { 66955888e44171ffd48b591d19256884a969fe4da17caryclark overlap->setOppPtTStart(test->oppPtTStart()); 67054359294a7c9dc54802d512a5d891a35c1663392caryclark } 67155888e44171ffd48b591d19256884a969fe4da17caryclark if (overlap->flipped() 67255888e44171ffd48b591d19256884a969fe4da17caryclark ? overlap->oppPtTEnd()->fT > test->oppPtTEnd()->fT 67355888e44171ffd48b591d19256884a969fe4da17caryclark : overlap->oppPtTEnd()->fT < test->oppPtTEnd()->fT) { 67455888e44171ffd48b591d19256884a969fe4da17caryclark overlap->setOppPtTEnd(test->oppPtTEnd()); 67555888e44171ffd48b591d19256884a969fe4da17caryclark } 67655888e44171ffd48b591d19256884a969fe4da17caryclark if (!fHead || !this->release(fHead, test)) { 67755888e44171ffd48b591d19256884a969fe4da17caryclark SkAssertResult(this->release(fTop, test)); 67855888e44171ffd48b591d19256884a969fe4da17caryclark } 67955888e44171ffd48b591d19256884a969fe4da17caryclark } 68055888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* cs = coinSeg->existing(coinTs, oppSeg); 68155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* ce = coinSeg->existing(coinTe, oppSeg); 68281a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if (overlap && cs && ce && overlap->contains(cs, ce)) { 68381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 68481a478ca6c36aac3e53ce0373a281ac8940f4780caryclark } 68581a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(cs == ce && cs); 68655888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* os = oppSeg->existing(oppTs, coinSeg); 68755888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* oe = oppSeg->existing(oppTe, coinSeg); 68881a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if (overlap && os && oe && overlap->contains(os, oe)) { 68981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 69081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark } 69155888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(!cs || !cs->deleted()); 69255888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(!os || !os->deleted()); 69355888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(!ce || !ce->deleted()); 69455888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(!oe || !oe->deleted()); 69555888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* csExisting = !cs ? coinSeg->existing(coinTs, nullptr) : nullptr; 69655888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* ceExisting = !ce ? coinSeg->existing(coinTe, nullptr) : nullptr; 69781a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(csExisting && csExisting == ceExisting); 698e839e78443e48d4ccad89059b4bc4b3d894fcfddcaryclark// FAIL_IF(csExisting && (csExisting == ce || 699e839e78443e48d4ccad89059b4bc4b3d894fcfddcaryclark// csExisting->contains(ceExisting ? ceExisting : ce))); 70081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(ceExisting && (ceExisting == cs || 701025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark ceExisting->contains(csExisting ? csExisting : cs))); 70255888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* osExisting = !os ? oppSeg->existing(oppTs, nullptr) : nullptr; 70355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* oeExisting = !oe ? oppSeg->existing(oppTe, nullptr) : nullptr; 70481a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(osExisting && osExisting == oeExisting); 70581a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(osExisting && (osExisting == oe || 706025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark osExisting->contains(oeExisting ? oeExisting : oe))); 70781a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(oeExisting && (oeExisting == os || 708025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark oeExisting->contains(osExisting ? osExisting : os))); 70955888e44171ffd48b591d19256884a969fe4da17caryclark // extra line in debug code 71055888e44171ffd48b591d19256884a969fe4da17caryclark this->debugValidate(); 71155888e44171ffd48b591d19256884a969fe4da17caryclark if (!cs || !os) { 71255888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* csWritable = cs ? const_cast<SkOpPtT*>(cs) 71329b2563afb1677515739f1d24fb27733626eca92caryclark : coinSeg->addT(coinTs); 714e839e78443e48d4ccad89059b4bc4b3d894fcfddcaryclark if (csWritable == ce) { 715e839e78443e48d4ccad89059b4bc4b3d894fcfddcaryclark return true; 716e839e78443e48d4ccad89059b4bc4b3d894fcfddcaryclark } 71755888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* osWritable = os ? const_cast<SkOpPtT*>(os) 71829b2563afb1677515739f1d24fb27733626eca92caryclark : oppSeg->addT(oppTs); 71981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(!csWritable || !osWritable); 72030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark csWritable->span()->addOpp(osWritable->span()); 72155888e44171ffd48b591d19256884a969fe4da17caryclark cs = csWritable; 72230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark os = osWritable->active(); 72381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF((ce && ce->deleted()) || (oe && oe->deleted())); 72454359294a7c9dc54802d512a5d891a35c1663392caryclark } 72555888e44171ffd48b591d19256884a969fe4da17caryclark if (!ce || !oe) { 72655888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* ceWritable = ce ? const_cast<SkOpPtT*>(ce) 72729b2563afb1677515739f1d24fb27733626eca92caryclark : coinSeg->addT(coinTe); 72855888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* oeWritable = oe ? const_cast<SkOpPtT*>(oe) 72929b2563afb1677515739f1d24fb27733626eca92caryclark : oppSeg->addT(oppTe); 73030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark ceWritable->span()->addOpp(oeWritable->span()); 73155888e44171ffd48b591d19256884a969fe4da17caryclark ce = ceWritable; 73255888e44171ffd48b591d19256884a969fe4da17caryclark oe = oeWritable; 73354359294a7c9dc54802d512a5d891a35c1663392caryclark } 73455888e44171ffd48b591d19256884a969fe4da17caryclark this->debugValidate(); 73581a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(cs->deleted()); 73681a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(os->deleted()); 73781a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(ce->deleted()); 73881a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(oe->deleted()); 73981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(cs->contains(ce) || os->contains(oe)); 74055888e44171ffd48b591d19256884a969fe4da17caryclark bool result = true; 74155888e44171ffd48b591d19256884a969fe4da17caryclark if (overlap) { 74255888e44171ffd48b591d19256884a969fe4da17caryclark if (overlap->coinPtTStart()->segment() == coinSeg) { 74355888e44171ffd48b591d19256884a969fe4da17caryclark result = overlap->extend(cs, ce, os, oe); 74455888e44171ffd48b591d19256884a969fe4da17caryclark } else { 74555888e44171ffd48b591d19256884a969fe4da17caryclark if (os->fT > oe->fT) { 74655888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(cs, ce); 74755888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(os, oe); 74855888e44171ffd48b591d19256884a969fe4da17caryclark } 74955888e44171ffd48b591d19256884a969fe4da17caryclark result = overlap->extend(os, oe, cs, ce); 75055888e44171ffd48b591d19256884a969fe4da17caryclark } 75155888e44171ffd48b591d19256884a969fe4da17caryclark#if DEBUG_COINCIDENCE_VERBOSE 75255888e44171ffd48b591d19256884a969fe4da17caryclark if (result) { 75355888e44171ffd48b591d19256884a969fe4da17caryclark overlaps[0]->debugShow(); 75455888e44171ffd48b591d19256884a969fe4da17caryclark } 75555888e44171ffd48b591d19256884a969fe4da17caryclark#endif 75655888e44171ffd48b591d19256884a969fe4da17caryclark } else { 75755888e44171ffd48b591d19256884a969fe4da17caryclark this->add(cs, ce, os, oe); 75855888e44171ffd48b591d19256884a969fe4da17caryclark#if DEBUG_COINCIDENCE_VERBOSE 75955888e44171ffd48b591d19256884a969fe4da17caryclark fHead->debugShow(); 76055888e44171ffd48b591d19256884a969fe4da17caryclark#endif 76155888e44171ffd48b591d19256884a969fe4da17caryclark } 76255888e44171ffd48b591d19256884a969fe4da17caryclark this->debugValidate(); 76381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if (result) { 76481a478ca6c36aac3e53ce0373a281ac8940f4780caryclark *added = true; 76581a478ca6c36aac3e53ce0373a281ac8940f4780caryclark } 76681a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 76754359294a7c9dc54802d512a5d891a35c1663392caryclark} 76854359294a7c9dc54802d512a5d891a35c1663392caryclark 76955888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with debugAddMissing() 77027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark/* detects overlaps of different coincident runs on same segment */ 77127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark/* does not detect overlaps for pairs without any segments in common */ 77255888e44171ffd48b591d19256884a969fe4da17caryclark// returns true if caller should loop again 773ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clarkbool SkOpCoincidence::addMissing(bool* added DEBUG_COIN_DECLARE_PARAMS()) { 77427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkCoincidentSpans* outer = fHead; 77581a478ca6c36aac3e53ce0373a281ac8940f4780caryclark *added = false; 77654359294a7c9dc54802d512a5d891a35c1663392caryclark if (!outer) { 77781a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 77854359294a7c9dc54802d512a5d891a35c1663392caryclark } 77927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark fTop = outer; 78096fcdcc219d2a0d3579719b84b28bede76efba64halcanary fHead = nullptr; 78154359294a7c9dc54802d512a5d891a35c1663392caryclark do { 78227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark // addifmissing can modify the list that this is walking 78326ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark // save head so that walker can iterate over old data unperturbed 78426ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark // addifmissing adds to head freely then add saved head in the end 7858016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ocs = outer->coinPtTStart(); 786a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(ocs->deleted()); 7878016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpSegment* outerCoin = ocs->segment(); 7888016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(!outerCoin->done()); // if it's done, should have already been removed from list 7898016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* oos = outer->oppPtTStart(); 790b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark if (oos->deleted()) { 79181a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 792b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark } 7938016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpSegment* outerOpp = oos->segment(); 7944c76c41c981dd7ea95062a1895a6e3415b70bce1Cary Clark SkOPASSERT(!outerOpp->done()); 7958016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkOpSegment* outerCoinWritable = const_cast<SkOpSegment*>(outerCoin); 7968016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkOpSegment* outerOppWritable = const_cast<SkOpSegment*>(outerOpp); 79754359294a7c9dc54802d512a5d891a35c1663392caryclark SkCoincidentSpans* inner = outer; 79855888e44171ffd48b591d19256884a969fe4da17caryclark while ((inner = inner->next())) { 79955888e44171ffd48b591d19256884a969fe4da17caryclark this->debugValidate(); 80054359294a7c9dc54802d512a5d891a35c1663392caryclark double overS, overE; 8018016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ics = inner->coinPtTStart(); 802221a4bb55b51a6ba3882811990581d4bdb6bd539caryclark FAIL_IF(ics->deleted()); 8038016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpSegment* innerCoin = ics->segment(); 804a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(innerCoin->done()); 8058016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ios = inner->oppPtTStart(); 806a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(ios->deleted()); 8078016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpSegment* innerOpp = ios->segment(); 8084c76c41c981dd7ea95062a1895a6e3415b70bce1Cary Clark SkOPASSERT(!innerOpp->done()); 8098016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkOpSegment* innerCoinWritable = const_cast<SkOpSegment*>(innerCoin); 8108016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkOpSegment* innerOppWritable = const_cast<SkOpSegment*>(innerOpp); 81155888e44171ffd48b591d19256884a969fe4da17caryclark if (outerCoin == innerCoin) { 8128016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* oce = outer->coinPtTEnd(); 813b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark if (oce->deleted()) { 81481a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 815b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark } 8168016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ice = inner->coinPtTEnd(); 817595ac28c3990ea89ee40ec14117dc1667acfc126caryclark FAIL_IF(ice->deleted()); 8188016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (outerOpp != innerOpp && this->overlap(ocs, oce, ics, ice, &overS, &overE)) { 81981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark (void) this->addIfMissing(ocs->starter(oce), ics->starter(ice), 82081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark overS, overE, outerOppWritable, innerOppWritable, added 8218016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(ocs->debugEnder(oce)) 8228016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(ics->debugEnder(ice))); 82355888e44171ffd48b591d19256884a969fe4da17caryclark } 82455888e44171ffd48b591d19256884a969fe4da17caryclark } else if (outerCoin == innerOpp) { 8258016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* oce = outer->coinPtTEnd(); 8268016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(!oce->deleted()); 8278016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ioe = inner->oppPtTEnd(); 8288016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(!ioe->deleted()); 8298016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (outerOpp != innerCoin && this->overlap(ocs, oce, ios, ioe, &overS, &overE)) { 83081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark (void) this->addIfMissing(ocs->starter(oce), ios->starter(ioe), 83181a478ca6c36aac3e53ce0373a281ac8940f4780caryclark overS, overE, outerOppWritable, innerCoinWritable, added 8328016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(ocs->debugEnder(oce)) 8338016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(ios->debugEnder(ioe))); 83455888e44171ffd48b591d19256884a969fe4da17caryclark } 83555888e44171ffd48b591d19256884a969fe4da17caryclark } else if (outerOpp == innerCoin) { 8368016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ooe = outer->oppPtTEnd(); 8378016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(!ooe->deleted()); 8388016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ice = inner->coinPtTEnd(); 8398016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(!ice->deleted()); 84055888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(outerCoin != innerOpp); 8418016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (this->overlap(oos, ooe, ics, ice, &overS, &overE)) { 84281a478ca6c36aac3e53ce0373a281ac8940f4780caryclark (void) this->addIfMissing(oos->starter(ooe), ics->starter(ice), 84381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark overS, overE, outerCoinWritable, innerOppWritable, added 8448016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(oos->debugEnder(ooe)) 8458016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(ics->debugEnder(ice))); 84655888e44171ffd48b591d19256884a969fe4da17caryclark } 84755888e44171ffd48b591d19256884a969fe4da17caryclark } else if (outerOpp == innerOpp) { 8488016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ooe = outer->oppPtTEnd(); 8498016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(!ooe->deleted()); 8508016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ioe = inner->oppPtTEnd(); 851b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark if (ioe->deleted()) { 85281a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 853b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark } 85455888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(outerCoin != innerCoin); 8558016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (this->overlap(oos, ooe, ios, ioe, &overS, &overE)) { 85681a478ca6c36aac3e53ce0373a281ac8940f4780caryclark (void) this->addIfMissing(oos->starter(ooe), ios->starter(ioe), 85781a478ca6c36aac3e53ce0373a281ac8940f4780caryclark overS, overE, outerCoinWritable, innerCoinWritable, added 8588016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(oos->debugEnder(ooe)) 8598016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(ios->debugEnder(ioe))); 86054359294a7c9dc54802d512a5d891a35c1663392caryclark } 86154359294a7c9dc54802d512a5d891a35c1663392caryclark } 86255888e44171ffd48b591d19256884a969fe4da17caryclark this->debugValidate(); 86354359294a7c9dc54802d512a5d891a35c1663392caryclark } 86455888e44171ffd48b591d19256884a969fe4da17caryclark } while ((outer = outer->next())); 86555888e44171ffd48b591d19256884a969fe4da17caryclark this->restoreHead(); 86681a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 86727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 86827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 86955888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::addOverlap(const SkOpSegment* seg1, const SkOpSegment* seg1o, 87055888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* seg2, const SkOpSegment* seg2o, 87155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* overS, const SkOpPtT* overE) { 872e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark const SkOpPtT* s1 = overS->find(seg1); 873e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark const SkOpPtT* e1 = overE->find(seg1); 874087140153861f4c2a003ce6b22a612acc9cc3cf9caryclark FAIL_IF(!s1); 87540f23780e7ca36818660add0faf783fda81bf0b1Cary Clark FAIL_IF(!e1); 87627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (!s1->starter(e1)->span()->upCast()->windValue()) { 877e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark s1 = overS->find(seg1o); 878e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark e1 = overE->find(seg1o); 879221a4bb55b51a6ba3882811990581d4bdb6bd539caryclark FAIL_IF(!s1); 88040f23780e7ca36818660add0faf783fda81bf0b1Cary Clark FAIL_IF(!e1); 88127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (!s1->starter(e1)->span()->upCast()->windValue()) { 8823f0753d3eccece8ac7f02f6af36d66a96c3dfb26caryclark return true; 88327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 88427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 885e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark const SkOpPtT* s2 = overS->find(seg2); 886e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark const SkOpPtT* e2 = overE->find(seg2); 887826167111f80a4251266812cf720ad712bd29446caryclark FAIL_IF(!s2); 888a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(!e2); 88927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (!s2->starter(e2)->span()->upCast()->windValue()) { 890e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark s2 = overS->find(seg2o); 891e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark e2 = overE->find(seg2o); 892a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(!s2); 89378a37a53365c24670b050acf993818c435922745caryclark FAIL_IF(!e2); 89427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (!s2->starter(e2)->span()->upCast()->windValue()) { 8953f0753d3eccece8ac7f02f6af36d66a96c3dfb26caryclark return true; 89627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 89727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 89827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (s1->segment() == s2->segment()) { 8993f0753d3eccece8ac7f02f6af36d66a96c3dfb26caryclark return true; 90027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 90127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (s1->fT > e1->fT) { 90227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkTSwap(s1, e1); 90327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkTSwap(s2, e2); 90427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 90555888e44171ffd48b591d19256884a969fe4da17caryclark this->add(s1, e1, s2, e2); 9063f0753d3eccece8ac7f02f6af36d66a96c3dfb26caryclark return true; 90754359294a7c9dc54802d512a5d891a35c1663392caryclark} 90854359294a7c9dc54802d512a5d891a35c1663392caryclark 90955888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::contains(const SkOpSegment* seg, const SkOpSegment* opp, double oppT) const { 91055888e44171ffd48b591d19256884a969fe4da17caryclark if (this->contains(fHead, seg, opp, oppT)) { 91155888e44171ffd48b591d19256884a969fe4da17caryclark return true; 91255888e44171ffd48b591d19256884a969fe4da17caryclark } 91355888e44171ffd48b591d19256884a969fe4da17caryclark if (this->contains(fTop, seg, opp, oppT)) { 91455888e44171ffd48b591d19256884a969fe4da17caryclark return true; 91555888e44171ffd48b591d19256884a969fe4da17caryclark } 91655888e44171ffd48b591d19256884a969fe4da17caryclark return false; 91755888e44171ffd48b591d19256884a969fe4da17caryclark} 91855888e44171ffd48b591d19256884a969fe4da17caryclark 91955888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::contains(const SkCoincidentSpans* coin, const SkOpSegment* seg, 92055888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* opp, double oppT) const { 92155888e44171ffd48b591d19256884a969fe4da17caryclark if (!coin) { 92255888e44171ffd48b591d19256884a969fe4da17caryclark return false; 92355888e44171ffd48b591d19256884a969fe4da17caryclark } 92455888e44171ffd48b591d19256884a969fe4da17caryclark do { 92555888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->coinPtTStart()->segment() == seg && coin->oppPtTStart()->segment() == opp 92655888e44171ffd48b591d19256884a969fe4da17caryclark && between(coin->oppPtTStart()->fT, oppT, coin->oppPtTEnd()->fT)) { 92754359294a7c9dc54802d512a5d891a35c1663392caryclark return true; 92854359294a7c9dc54802d512a5d891a35c1663392caryclark } 92955888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->oppPtTStart()->segment() == seg && coin->coinPtTStart()->segment() == opp 93055888e44171ffd48b591d19256884a969fe4da17caryclark && between(coin->coinPtTStart()->fT, oppT, coin->coinPtTEnd()->fT)) { 93155888e44171ffd48b591d19256884a969fe4da17caryclark return true; 93255888e44171ffd48b591d19256884a969fe4da17caryclark } 93355888e44171ffd48b591d19256884a969fe4da17caryclark } while ((coin = coin->next())); 93455888e44171ffd48b591d19256884a969fe4da17caryclark return false; 93555888e44171ffd48b591d19256884a969fe4da17caryclark} 93655888e44171ffd48b591d19256884a969fe4da17caryclark 93755888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::contains(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, 93855888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) const { 93955888e44171ffd48b591d19256884a969fe4da17caryclark const SkCoincidentSpans* test = fHead; 94055888e44171ffd48b591d19256884a969fe4da17caryclark if (!test) { 94155888e44171ffd48b591d19256884a969fe4da17caryclark return false; 94255888e44171ffd48b591d19256884a969fe4da17caryclark } 94355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* coinSeg = coinPtTStart->segment(); 94455888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* oppSeg = oppPtTStart->segment(); 94555888e44171ffd48b591d19256884a969fe4da17caryclark if (!Ordered(coinPtTStart, oppPtTStart)) { 94655888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinSeg, oppSeg); 94755888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinPtTStart, oppPtTStart); 94855888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinPtTEnd, oppPtTEnd); 94955888e44171ffd48b591d19256884a969fe4da17caryclark if (coinPtTStart->fT > coinPtTEnd->fT) { 95055888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinPtTStart, coinPtTEnd); 95155888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(oppPtTStart, oppPtTEnd); 95255888e44171ffd48b591d19256884a969fe4da17caryclark } 95355888e44171ffd48b591d19256884a969fe4da17caryclark } 95455888e44171ffd48b591d19256884a969fe4da17caryclark double oppMinT = SkTMin(oppPtTStart->fT, oppPtTEnd->fT); 95555888e44171ffd48b591d19256884a969fe4da17caryclark double oppMaxT = SkTMax(oppPtTStart->fT, oppPtTEnd->fT); 95655888e44171ffd48b591d19256884a969fe4da17caryclark do { 95755888e44171ffd48b591d19256884a969fe4da17caryclark if (coinSeg != test->coinPtTStart()->segment()) { 95855888e44171ffd48b591d19256884a969fe4da17caryclark continue; 95955888e44171ffd48b591d19256884a969fe4da17caryclark } 96055888e44171ffd48b591d19256884a969fe4da17caryclark if (coinPtTStart->fT < test->coinPtTStart()->fT) { 96155888e44171ffd48b591d19256884a969fe4da17caryclark continue; 96255888e44171ffd48b591d19256884a969fe4da17caryclark } 96355888e44171ffd48b591d19256884a969fe4da17caryclark if (coinPtTEnd->fT > test->coinPtTEnd()->fT) { 96455888e44171ffd48b591d19256884a969fe4da17caryclark continue; 96555888e44171ffd48b591d19256884a969fe4da17caryclark } 96655888e44171ffd48b591d19256884a969fe4da17caryclark if (oppSeg != test->oppPtTStart()->segment()) { 96755888e44171ffd48b591d19256884a969fe4da17caryclark continue; 96855888e44171ffd48b591d19256884a969fe4da17caryclark } 96955888e44171ffd48b591d19256884a969fe4da17caryclark if (oppMinT < SkTMin(test->oppPtTStart()->fT, test->oppPtTEnd()->fT)) { 97055888e44171ffd48b591d19256884a969fe4da17caryclark continue; 97155888e44171ffd48b591d19256884a969fe4da17caryclark } 97255888e44171ffd48b591d19256884a969fe4da17caryclark if (oppMaxT > SkTMax(test->oppPtTStart()->fT, test->oppPtTEnd()->fT)) { 97355888e44171ffd48b591d19256884a969fe4da17caryclark continue; 97455888e44171ffd48b591d19256884a969fe4da17caryclark } 97555888e44171ffd48b591d19256884a969fe4da17caryclark return true; 97655888e44171ffd48b591d19256884a969fe4da17caryclark } while ((test = test->next())); 97754359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 97854359294a7c9dc54802d512a5d891a35c1663392caryclark} 97954359294a7c9dc54802d512a5d891a35c1663392caryclark 980ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clarkvoid SkOpCoincidence::correctEnds(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 981ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark DEBUG_SET_PHASE(); 98255888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* coin = fHead; 98355888e44171ffd48b591d19256884a969fe4da17caryclark if (!coin) { 98455888e44171ffd48b591d19256884a969fe4da17caryclark return; 98555888e44171ffd48b591d19256884a969fe4da17caryclark } 98655888e44171ffd48b591d19256884a969fe4da17caryclark do { 98755888e44171ffd48b591d19256884a969fe4da17caryclark coin->correctEnds(); 98855888e44171ffd48b591d19256884a969fe4da17caryclark } while ((coin = coin->next())); 98955888e44171ffd48b591d19256884a969fe4da17caryclark} 99055888e44171ffd48b591d19256884a969fe4da17caryclark 99154359294a7c9dc54802d512a5d891a35c1663392caryclark// walk span sets in parallel, moving winding from one to the other 992a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclarkbool SkOpCoincidence::apply(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 993ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark DEBUG_SET_PHASE(); 99454359294a7c9dc54802d512a5d891a35c1663392caryclark SkCoincidentSpans* coin = fHead; 99554359294a7c9dc54802d512a5d891a35c1663392caryclark if (!coin) { 996a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark return true; 99754359294a7c9dc54802d512a5d891a35c1663392caryclark } 99854359294a7c9dc54802d512a5d891a35c1663392caryclark do { 9995a2057aee9c6293c3dc78cfb013c06ea707d39e4Cary Clark SkOpSpanBase* startSpan = coin->coinPtTStartWritable()->span(); 10005a2057aee9c6293c3dc78cfb013c06ea707d39e4Cary Clark FAIL_IF(!startSpan->upCastable()); 10015a2057aee9c6293c3dc78cfb013c06ea707d39e4Cary Clark SkOpSpan* start = startSpan->upCast(); 1002182b499cd75c971f85cdf52c1827b3c220cc9011caryclark if (start->deleted()) { 1003182b499cd75c971f85cdf52c1827b3c220cc9011caryclark continue; 1004182b499cd75c971f85cdf52c1827b3c220cc9011caryclark } 100555888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* end = coin->coinPtTEnd()->span(); 100654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start == start->starter(end)); 100755888e44171ffd48b591d19256884a969fe4da17caryclark bool flipped = coin->flipped(); 100896dc1c9efaab4636e30f90aa377f25863f9bf3bacaryclark SkOpSpanBase* oStartBase = (flipped ? coin->oppPtTEndWritable() 100996dc1c9efaab4636e30f90aa377f25863f9bf3bacaryclark : coin->oppPtTStartWritable())->span(); 101096dc1c9efaab4636e30f90aa377f25863f9bf3bacaryclark FAIL_IF(!oStartBase->upCastable()); 101196dc1c9efaab4636e30f90aa377f25863f9bf3bacaryclark SkOpSpan* oStart = oStartBase->upCast(); 1012182b499cd75c971f85cdf52c1827b3c220cc9011caryclark if (oStart->deleted()) { 1013182b499cd75c971f85cdf52c1827b3c220cc9011caryclark continue; 1014182b499cd75c971f85cdf52c1827b3c220cc9011caryclark } 101555888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* oEnd = (flipped ? coin->oppPtTStart() : coin->oppPtTEnd())->span(); 101654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(oStart == oStart->starter(oEnd)); 101754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* segment = start->segment(); 101854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* oSegment = oStart->segment(); 101954359294a7c9dc54802d512a5d891a35c1663392caryclark bool operandSwap = segment->operand() != oSegment->operand(); 102054359294a7c9dc54802d512a5d891a35c1663392caryclark if (flipped) { 1021364a0074c33f91ded60232f173f7a57a312e9280caryclark if (oEnd->deleted()) { 1022364a0074c33f91ded60232f173f7a57a312e9280caryclark continue; 1023364a0074c33f91ded60232f173f7a57a312e9280caryclark } 102454359294a7c9dc54802d512a5d891a35c1663392caryclark do { 102554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* oNext = oStart->next(); 102654359294a7c9dc54802d512a5d891a35c1663392caryclark if (oNext == oEnd) { 102754359294a7c9dc54802d512a5d891a35c1663392caryclark break; 102854359294a7c9dc54802d512a5d891a35c1663392caryclark } 102926ae5aba592d4169c1c53aa7fafa660589a4d554Cary Clark FAIL_IF(!oNext->upCastable()); 103054359294a7c9dc54802d512a5d891a35c1663392caryclark oStart = oNext->upCast(); 103154359294a7c9dc54802d512a5d891a35c1663392caryclark } while (true); 103254359294a7c9dc54802d512a5d891a35c1663392caryclark } 103354359294a7c9dc54802d512a5d891a35c1663392caryclark do { 103454359294a7c9dc54802d512a5d891a35c1663392caryclark int windValue = start->windValue(); 103554359294a7c9dc54802d512a5d891a35c1663392caryclark int oppValue = start->oppValue(); 10361049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int oWindValue = oStart->windValue(); 103754359294a7c9dc54802d512a5d891a35c1663392caryclark int oOppValue = oStart->oppValue(); 103854359294a7c9dc54802d512a5d891a35c1663392caryclark // winding values are added or subtracted depending on direction and wind type 103954359294a7c9dc54802d512a5d891a35c1663392caryclark // same or opposite values are summed depending on the operand value 10401049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int windDiff = operandSwap ? oOppValue : oWindValue; 10411049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int oWindDiff = operandSwap ? oppValue : windValue; 10421049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (!flipped) { 10431049f1246e7be4ccb68001361efceb8933e6f81ccaryclark windDiff = -windDiff; 10441049f1246e7be4ccb68001361efceb8933e6f81ccaryclark oWindDiff = -oWindDiff; 10451049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 104655888e44171ffd48b591d19256884a969fe4da17caryclark bool addToStart = windValue && (windValue > windDiff || (windValue == windDiff 104755888e44171ffd48b591d19256884a969fe4da17caryclark && oWindValue <= oWindDiff)); 104855888e44171ffd48b591d19256884a969fe4da17caryclark if (addToStart ? start->done() : oStart->done()) { 104955888e44171ffd48b591d19256884a969fe4da17caryclark addToStart ^= true; 105055888e44171ffd48b591d19256884a969fe4da17caryclark } 105155888e44171ffd48b591d19256884a969fe4da17caryclark if (addToStart) { 105254359294a7c9dc54802d512a5d891a35c1663392caryclark if (operandSwap) { 105354359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(oWindValue, oOppValue); 105454359294a7c9dc54802d512a5d891a35c1663392caryclark } 105554359294a7c9dc54802d512a5d891a35c1663392caryclark if (flipped) { 105654359294a7c9dc54802d512a5d891a35c1663392caryclark windValue -= oWindValue; 105754359294a7c9dc54802d512a5d891a35c1663392caryclark oppValue -= oOppValue; 105854359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 105954359294a7c9dc54802d512a5d891a35c1663392caryclark windValue += oWindValue; 106054359294a7c9dc54802d512a5d891a35c1663392caryclark oppValue += oOppValue; 106154359294a7c9dc54802d512a5d891a35c1663392caryclark } 10621049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (segment->isXor()) { 106354359294a7c9dc54802d512a5d891a35c1663392caryclark windValue &= 1; 106454359294a7c9dc54802d512a5d891a35c1663392caryclark } 10651049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (segment->oppXor()) { 106654359294a7c9dc54802d512a5d891a35c1663392caryclark oppValue &= 1; 106754359294a7c9dc54802d512a5d891a35c1663392caryclark } 106854359294a7c9dc54802d512a5d891a35c1663392caryclark oWindValue = oOppValue = 0; 106954359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 107054359294a7c9dc54802d512a5d891a35c1663392caryclark if (operandSwap) { 107154359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(windValue, oppValue); 107254359294a7c9dc54802d512a5d891a35c1663392caryclark } 107354359294a7c9dc54802d512a5d891a35c1663392caryclark if (flipped) { 107454359294a7c9dc54802d512a5d891a35c1663392caryclark oWindValue -= windValue; 107554359294a7c9dc54802d512a5d891a35c1663392caryclark oOppValue -= oppValue; 107654359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 107754359294a7c9dc54802d512a5d891a35c1663392caryclark oWindValue += windValue; 107854359294a7c9dc54802d512a5d891a35c1663392caryclark oOppValue += oppValue; 107954359294a7c9dc54802d512a5d891a35c1663392caryclark } 10801049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (oSegment->isXor()) { 108154359294a7c9dc54802d512a5d891a35c1663392caryclark oWindValue &= 1; 108254359294a7c9dc54802d512a5d891a35c1663392caryclark } 10831049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (oSegment->oppXor()) { 10841049f1246e7be4ccb68001361efceb8933e6f81ccaryclark oOppValue &= 1; 10851049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 108654359294a7c9dc54802d512a5d891a35c1663392caryclark windValue = oppValue = 0; 108754359294a7c9dc54802d512a5d891a35c1663392caryclark } 10886c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark#if 0 && DEBUG_COINCIDENCE 108955888e44171ffd48b591d19256884a969fe4da17caryclark SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", segment->debugID(), 109055888e44171ffd48b591d19256884a969fe4da17caryclark start->debugID(), windValue, oppValue); 109155888e44171ffd48b591d19256884a969fe4da17caryclark SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", oSegment->debugID(), 109255888e44171ffd48b591d19256884a969fe4da17caryclark oStart->debugID(), oWindValue, oOppValue); 109355888e44171ffd48b591d19256884a969fe4da17caryclark#endif 109454359294a7c9dc54802d512a5d891a35c1663392caryclark start->setWindValue(windValue); 109554359294a7c9dc54802d512a5d891a35c1663392caryclark start->setOppValue(oppValue); 1096a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(oWindValue == -1); 109754359294a7c9dc54802d512a5d891a35c1663392caryclark oStart->setWindValue(oWindValue); 109854359294a7c9dc54802d512a5d891a35c1663392caryclark oStart->setOppValue(oOppValue); 109954359294a7c9dc54802d512a5d891a35c1663392caryclark if (!windValue && !oppValue) { 110054359294a7c9dc54802d512a5d891a35c1663392caryclark segment->markDone(start); 110154359294a7c9dc54802d512a5d891a35c1663392caryclark } 110254359294a7c9dc54802d512a5d891a35c1663392caryclark if (!oWindValue && !oOppValue) { 110354359294a7c9dc54802d512a5d891a35c1663392caryclark oSegment->markDone(oStart); 110454359294a7c9dc54802d512a5d891a35c1663392caryclark } 110554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* next = start->next(); 110654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* oNext = flipped ? oStart->prev() : oStart->next(); 110754359294a7c9dc54802d512a5d891a35c1663392caryclark if (next == end) { 110854359294a7c9dc54802d512a5d891a35c1663392caryclark break; 110954359294a7c9dc54802d512a5d891a35c1663392caryclark } 111096dc1c9efaab4636e30f90aa377f25863f9bf3bacaryclark FAIL_IF(!next->upCastable()); 111154359294a7c9dc54802d512a5d891a35c1663392caryclark start = next->upCast(); 11121049f1246e7be4ccb68001361efceb8933e6f81ccaryclark // if the opposite ran out too soon, just reuse the last span 11131049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (!oNext || !oNext->upCastable()) { 11141049f1246e7be4ccb68001361efceb8933e6f81ccaryclark oNext = oStart; 111554359294a7c9dc54802d512a5d891a35c1663392caryclark } 111654359294a7c9dc54802d512a5d891a35c1663392caryclark oStart = oNext->upCast(); 111754359294a7c9dc54802d512a5d891a35c1663392caryclark } while (true); 111855888e44171ffd48b591d19256884a969fe4da17caryclark } while ((coin = coin->next())); 1119a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark return true; 112054359294a7c9dc54802d512a5d891a35c1663392caryclark} 112154359294a7c9dc54802d512a5d891a35c1663392caryclark 112255888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with debugRelease() 112355888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::release(SkCoincidentSpans* coin, SkCoincidentSpans* remove) { 112455888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* head = coin; 112596fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkCoincidentSpans* prev = nullptr; 112654359294a7c9dc54802d512a5d891a35c1663392caryclark SkCoincidentSpans* next; 112754359294a7c9dc54802d512a5d891a35c1663392caryclark do { 112855888e44171ffd48b591d19256884a969fe4da17caryclark next = coin->next(); 112954359294a7c9dc54802d512a5d891a35c1663392caryclark if (coin == remove) { 113054359294a7c9dc54802d512a5d891a35c1663392caryclark if (prev) { 113155888e44171ffd48b591d19256884a969fe4da17caryclark prev->setNext(next); 113255888e44171ffd48b591d19256884a969fe4da17caryclark } else if (head == fHead) { 113354359294a7c9dc54802d512a5d891a35c1663392caryclark fHead = next; 113455888e44171ffd48b591d19256884a969fe4da17caryclark } else { 113555888e44171ffd48b591d19256884a969fe4da17caryclark fTop = next; 113654359294a7c9dc54802d512a5d891a35c1663392caryclark } 113754359294a7c9dc54802d512a5d891a35c1663392caryclark break; 113854359294a7c9dc54802d512a5d891a35c1663392caryclark } 113954359294a7c9dc54802d512a5d891a35c1663392caryclark prev = coin; 114054359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((coin = next)); 114155888e44171ffd48b591d19256884a969fe4da17caryclark return coin != nullptr; 114255888e44171ffd48b591d19256884a969fe4da17caryclark} 114355888e44171ffd48b591d19256884a969fe4da17caryclark 114430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclarkvoid SkOpCoincidence::releaseDeleted(SkCoincidentSpans* coin) { 114530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (!coin) { 114630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark return; 114730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 114830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkCoincidentSpans* head = coin; 114930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkCoincidentSpans* prev = nullptr; 115030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkCoincidentSpans* next; 115130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark do { 115230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark next = coin->next(); 115330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (coin->coinPtTStart()->deleted()) { 115430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOPASSERT(coin->flipped() ? coin->oppPtTEnd()->deleted() : 115530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark coin->oppPtTStart()->deleted()); 115630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (prev) { 115730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark prev->setNext(next); 115830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } else if (head == fHead) { 115930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark fHead = next; 116030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } else { 116130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark fTop = next; 116230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 116330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } else { 116430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOPASSERT(coin->flipped() ? !coin->oppPtTEnd()->deleted() : 116530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark !coin->oppPtTStart()->deleted()); 116630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark prev = coin; 116730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 116830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } while ((coin = next)); 116930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark} 117030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark 117130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclarkvoid SkOpCoincidence::releaseDeleted() { 117230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark this->releaseDeleted(fHead); 117330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark this->releaseDeleted(fTop); 117430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark} 117530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark 117655888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpCoincidence::restoreHead() { 117755888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans** headPtr = &fHead; 117855888e44171ffd48b591d19256884a969fe4da17caryclark while (*headPtr) { 117955888e44171ffd48b591d19256884a969fe4da17caryclark headPtr = (*headPtr)->nextPtr(); 118055888e44171ffd48b591d19256884a969fe4da17caryclark } 118155888e44171ffd48b591d19256884a969fe4da17caryclark *headPtr = fTop; 118255888e44171ffd48b591d19256884a969fe4da17caryclark fTop = nullptr; 118355888e44171ffd48b591d19256884a969fe4da17caryclark // segments may have collapsed in the meantime; remove empty referenced segments 118455888e44171ffd48b591d19256884a969fe4da17caryclark headPtr = &fHead; 118555888e44171ffd48b591d19256884a969fe4da17caryclark while (*headPtr) { 118655888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* test = *headPtr; 118755888e44171ffd48b591d19256884a969fe4da17caryclark if (test->coinPtTStart()->segment()->done() || test->oppPtTStart()->segment()->done()) { 118855888e44171ffd48b591d19256884a969fe4da17caryclark *headPtr = test->next(); 118955888e44171ffd48b591d19256884a969fe4da17caryclark continue; 119055888e44171ffd48b591d19256884a969fe4da17caryclark } 119155888e44171ffd48b591d19256884a969fe4da17caryclark headPtr = (*headPtr)->nextPtr(); 119255888e44171ffd48b591d19256884a969fe4da17caryclark } 119355888e44171ffd48b591d19256884a969fe4da17caryclark} 119455888e44171ffd48b591d19256884a969fe4da17caryclark 119555888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with debugExpand() 119630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark// expand the range by checking adjacent spans for coincidence 1197ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clarkbool SkOpCoincidence::expand(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 1198ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark DEBUG_SET_PHASE(); 119954359294a7c9dc54802d512a5d891a35c1663392caryclark SkCoincidentSpans* coin = fHead; 120054359294a7c9dc54802d512a5d891a35c1663392caryclark if (!coin) { 120127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark return false; 120254359294a7c9dc54802d512a5d891a35c1663392caryclark } 120327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark bool expanded = false; 120454359294a7c9dc54802d512a5d891a35c1663392caryclark do { 120555888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->expand()) { 120655888e44171ffd48b591d19256884a969fe4da17caryclark // check to see if multiple spans expanded so they are now identical 120755888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* test = fHead; 120855888e44171ffd48b591d19256884a969fe4da17caryclark do { 120955888e44171ffd48b591d19256884a969fe4da17caryclark if (coin == test) { 121055888e44171ffd48b591d19256884a969fe4da17caryclark continue; 121155888e44171ffd48b591d19256884a969fe4da17caryclark } 121255888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->coinPtTStart() == test->coinPtTStart() 121355888e44171ffd48b591d19256884a969fe4da17caryclark && coin->oppPtTStart() == test->oppPtTStart()) { 121455888e44171ffd48b591d19256884a969fe4da17caryclark this->release(fHead, test); 121555888e44171ffd48b591d19256884a969fe4da17caryclark break; 121655888e44171ffd48b591d19256884a969fe4da17caryclark } 121755888e44171ffd48b591d19256884a969fe4da17caryclark } while ((test = test->next())); 121855888e44171ffd48b591d19256884a969fe4da17caryclark expanded = true; 121927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 122055888e44171ffd48b591d19256884a969fe4da17caryclark } while ((coin = coin->next())); 122127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark return expanded; 122227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 122327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 122440f23780e7ca36818660add0faf783fda81bf0b1Cary Clarkbool SkOpCoincidence::findOverlaps(SkOpCoincidence* overlaps DEBUG_COIN_DECLARE_PARAMS()) const { 1225ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark DEBUG_SET_PHASE(); 122696fcdcc219d2a0d3579719b84b28bede76efba64halcanary overlaps->fHead = overlaps->fTop = nullptr; 122727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkCoincidentSpans* outer = fHead; 122827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark while (outer) { 122955888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* outerCoin = outer->coinPtTStart()->segment(); 123055888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* outerOpp = outer->oppPtTStart()->segment(); 123127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkCoincidentSpans* inner = outer; 123255888e44171ffd48b591d19256884a969fe4da17caryclark while ((inner = inner->next())) { 123355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* innerCoin = inner->coinPtTStart()->segment(); 123427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (outerCoin == innerCoin) { 123527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark continue; // both winners are the same segment, so there's no additional overlap 123654359294a7c9dc54802d512a5d891a35c1663392caryclark } 123755888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* innerOpp = inner->oppPtTStart()->segment(); 123855888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* overlapS; 123955888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* overlapE; 124055888e44171ffd48b591d19256884a969fe4da17caryclark if ((outerOpp == innerCoin && SkOpPtT::Overlaps(outer->oppPtTStart(), 124155888e44171ffd48b591d19256884a969fe4da17caryclark outer->oppPtTEnd(),inner->coinPtTStart(), inner->coinPtTEnd(), &overlapS, 124255888e44171ffd48b591d19256884a969fe4da17caryclark &overlapE)) 124355888e44171ffd48b591d19256884a969fe4da17caryclark || (outerCoin == innerOpp && SkOpPtT::Overlaps(outer->coinPtTStart(), 124455888e44171ffd48b591d19256884a969fe4da17caryclark outer->coinPtTEnd(), inner->oppPtTStart(), inner->oppPtTEnd(), 124527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark &overlapS, &overlapE)) 124655888e44171ffd48b591d19256884a969fe4da17caryclark || (outerOpp == innerOpp && SkOpPtT::Overlaps(outer->oppPtTStart(), 124755888e44171ffd48b591d19256884a969fe4da17caryclark outer->oppPtTEnd(), inner->oppPtTStart(), inner->oppPtTEnd(), 124827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark &overlapS, &overlapE))) { 124940f23780e7ca36818660add0faf783fda81bf0b1Cary Clark if (!overlaps->addOverlap(outerCoin, outerOpp, innerCoin, innerOpp, 125040f23780e7ca36818660add0faf783fda81bf0b1Cary Clark overlapS, overlapE)) { 125140f23780e7ca36818660add0faf783fda81bf0b1Cary Clark return false; 125240f23780e7ca36818660add0faf783fda81bf0b1Cary Clark } 1253e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark } 125427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 125555888e44171ffd48b591d19256884a969fe4da17caryclark outer = outer->next(); 125627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 125740f23780e7ca36818660add0faf783fda81bf0b1Cary Clark return true; 125827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 125927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 126055888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpCoincidence::fixUp(SkOpPtT* deleted, const SkOpPtT* kept) { 1261b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark SkOPASSERT(deleted != kept); 126255888e44171ffd48b591d19256884a969fe4da17caryclark if (fHead) { 126355888e44171ffd48b591d19256884a969fe4da17caryclark this->fixUp(fHead, deleted, kept); 126455888e44171ffd48b591d19256884a969fe4da17caryclark } 126555888e44171ffd48b591d19256884a969fe4da17caryclark if (fTop) { 126655888e44171ffd48b591d19256884a969fe4da17caryclark this->fixUp(fTop, deleted, kept); 126754359294a7c9dc54802d512a5d891a35c1663392caryclark } 126855888e44171ffd48b591d19256884a969fe4da17caryclark} 126955888e44171ffd48b591d19256884a969fe4da17caryclark 127055888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpCoincidence::fixUp(SkCoincidentSpans* coin, SkOpPtT* deleted, const SkOpPtT* kept) { 127155888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* head = coin; 127254359294a7c9dc54802d512a5d891a35c1663392caryclark do { 127355888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->coinPtTStart() == deleted) { 127455888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->coinPtTEnd()->span() == kept->span()) { 127555888e44171ffd48b591d19256884a969fe4da17caryclark this->release(head, coin); 127627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark continue; 127754359294a7c9dc54802d512a5d891a35c1663392caryclark } 127855888e44171ffd48b591d19256884a969fe4da17caryclark coin->setCoinPtTStart(kept); 127954359294a7c9dc54802d512a5d891a35c1663392caryclark } 128055888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->coinPtTEnd() == deleted) { 128155888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->coinPtTStart()->span() == kept->span()) { 128255888e44171ffd48b591d19256884a969fe4da17caryclark this->release(head, coin); 128327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark continue; 128454359294a7c9dc54802d512a5d891a35c1663392caryclark } 128555888e44171ffd48b591d19256884a969fe4da17caryclark coin->setCoinPtTEnd(kept); 128655888e44171ffd48b591d19256884a969fe4da17caryclark } 128755888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->oppPtTStart() == deleted) { 128855888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->oppPtTEnd()->span() == kept->span()) { 128955888e44171ffd48b591d19256884a969fe4da17caryclark this->release(head, coin); 129027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark continue; 129154359294a7c9dc54802d512a5d891a35c1663392caryclark } 129255888e44171ffd48b591d19256884a969fe4da17caryclark coin->setOppPtTStart(kept); 129354359294a7c9dc54802d512a5d891a35c1663392caryclark } 129455888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->oppPtTEnd() == deleted) { 129555888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->oppPtTStart()->span() == kept->span()) { 129655888e44171ffd48b591d19256884a969fe4da17caryclark this->release(head, coin); 129727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark continue; 129854359294a7c9dc54802d512a5d891a35c1663392caryclark } 129955888e44171ffd48b591d19256884a969fe4da17caryclark coin->setOppPtTEnd(kept); 130054359294a7c9dc54802d512a5d891a35c1663392caryclark } 130155888e44171ffd48b591d19256884a969fe4da17caryclark } while ((coin = coin->next())); 130254359294a7c9dc54802d512a5d891a35c1663392caryclark} 130354359294a7c9dc54802d512a5d891a35c1663392caryclark 130455888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with debugMark() 130527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark/* this sets up the coincidence links in the segments when the coincidence crosses multiple spans */ 1306e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclarkbool SkOpCoincidence::mark(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 1307ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark DEBUG_SET_PHASE(); 130854359294a7c9dc54802d512a5d891a35c1663392caryclark SkCoincidentSpans* coin = fHead; 130954359294a7c9dc54802d512a5d891a35c1663392caryclark if (!coin) { 1310e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclark return true; 131154359294a7c9dc54802d512a5d891a35c1663392caryclark } 131254359294a7c9dc54802d512a5d891a35c1663392caryclark do { 1313e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclark SkOpSpanBase* startBase = coin->coinPtTStartWritable()->span(); 1314e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclark FAIL_IF(!startBase->upCastable()); 1315e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclark SkOpSpan* start = startBase->upCast(); 1316a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(start->deleted()); 131755888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpanBase* end = coin->coinPtTEndWritable()->span(); 131840f23780e7ca36818660add0faf783fda81bf0b1Cary Clark SkOPASSERT(!end->deleted()); 131955888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpanBase* oStart = coin->oppPtTStartWritable()->span(); 132040f23780e7ca36818660add0faf783fda81bf0b1Cary Clark SkOPASSERT(!oStart->deleted()); 132155888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpanBase* oEnd = coin->oppPtTEndWritable()->span(); 132255888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(!oEnd->deleted()); 132355888e44171ffd48b591d19256884a969fe4da17caryclark bool flipped = coin->flipped(); 132454359294a7c9dc54802d512a5d891a35c1663392caryclark if (flipped) { 132554359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(oStart, oEnd); 132654359294a7c9dc54802d512a5d891a35c1663392caryclark } 132755888e44171ffd48b591d19256884a969fe4da17caryclark /* coin and opp spans may not match up. Mark the ends, and then let the interior 132855888e44171ffd48b591d19256884a969fe4da17caryclark get marked as many times as the spans allow */ 13299de097639f04e5a18da2d2b123dace9d24ab50e4Cary Clark FAIL_IF(!oStart->upCastable()); 133055888e44171ffd48b591d19256884a969fe4da17caryclark start->insertCoincidence(oStart->upCast()); 133155888e44171ffd48b591d19256884a969fe4da17caryclark end->insertCoinEnd(oEnd); 133255888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* segment = start->segment(); 133355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* oSegment = oStart->segment(); 133454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* next = start; 133554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* oNext = oStart; 1336a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark bool ordered; 1337a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(!coin->ordered(&ordered)); 133855888e44171ffd48b591d19256884a969fe4da17caryclark while ((next = next->upCast()->next()) != end) { 1339e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclark FAIL_IF(!next->upCastable()); 134059ed482af72beec6812b28d833d8bdf80ba32df7Cary Clark FAIL_IF(!next->upCast()->insertCoincidence(oSegment, flipped, ordered)); 134155888e44171ffd48b591d19256884a969fe4da17caryclark } 134255888e44171ffd48b591d19256884a969fe4da17caryclark while ((oNext = oNext->upCast()->next()) != oEnd) { 134396dc1c9efaab4636e30f90aa377f25863f9bf3bacaryclark FAIL_IF(!oNext->upCastable()); 1344e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclark FAIL_IF(!oNext->upCast()->insertCoincidence(segment, flipped, ordered)); 134555888e44171ffd48b591d19256884a969fe4da17caryclark } 134655888e44171ffd48b591d19256884a969fe4da17caryclark } while ((coin = coin->next())); 1347e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclark return true; 134855888e44171ffd48b591d19256884a969fe4da17caryclark} 134955888e44171ffd48b591d19256884a969fe4da17caryclark 135055888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep in sync with debugMarkCollapsed() 135155888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpCoincidence::markCollapsed(SkCoincidentSpans* coin, SkOpPtT* test) { 135255888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* head = coin; 135355888e44171ffd48b591d19256884a969fe4da17caryclark while (coin) { 135455888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->collapsed(test)) { 135555888e44171ffd48b591d19256884a969fe4da17caryclark if (zero_or_one(coin->coinPtTStart()->fT) && zero_or_one(coin->coinPtTEnd()->fT)) { 135655888e44171ffd48b591d19256884a969fe4da17caryclark coin->coinPtTStartWritable()->segment()->markAllDone(); 135754359294a7c9dc54802d512a5d891a35c1663392caryclark } 135855888e44171ffd48b591d19256884a969fe4da17caryclark if (zero_or_one(coin->oppPtTStart()->fT) && zero_or_one(coin->oppPtTEnd()->fT)) { 135955888e44171ffd48b591d19256884a969fe4da17caryclark coin->oppPtTStartWritable()->segment()->markAllDone(); 136055888e44171ffd48b591d19256884a969fe4da17caryclark } 136155888e44171ffd48b591d19256884a969fe4da17caryclark this->release(head, coin); 136255888e44171ffd48b591d19256884a969fe4da17caryclark } 136355888e44171ffd48b591d19256884a969fe4da17caryclark coin = coin->next(); 136455888e44171ffd48b591d19256884a969fe4da17caryclark } 136555888e44171ffd48b591d19256884a969fe4da17caryclark} 136655888e44171ffd48b591d19256884a969fe4da17caryclark 136755888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep in sync with debugMarkCollapsed() 136855888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpCoincidence::markCollapsed(SkOpPtT* test) { 136955888e44171ffd48b591d19256884a969fe4da17caryclark markCollapsed(fHead, test); 137055888e44171ffd48b591d19256884a969fe4da17caryclark markCollapsed(fTop, test); 137155888e44171ffd48b591d19256884a969fe4da17caryclark} 137255888e44171ffd48b591d19256884a969fe4da17caryclark 137355888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::Ordered(const SkOpSegment* coinSeg, const SkOpSegment* oppSeg) { 137455888e44171ffd48b591d19256884a969fe4da17caryclark if (coinSeg->verb() < oppSeg->verb()) { 137555888e44171ffd48b591d19256884a969fe4da17caryclark return true; 137655888e44171ffd48b591d19256884a969fe4da17caryclark } 137755888e44171ffd48b591d19256884a969fe4da17caryclark if (coinSeg->verb() > oppSeg->verb()) { 137855888e44171ffd48b591d19256884a969fe4da17caryclark return false; 137955888e44171ffd48b591d19256884a969fe4da17caryclark } 138055888e44171ffd48b591d19256884a969fe4da17caryclark int count = (SkPathOpsVerbToPoints(coinSeg->verb()) + 1) * 2; 138155888e44171ffd48b591d19256884a969fe4da17caryclark const SkScalar* cPt = &coinSeg->pts()[0].fX; 138255888e44171ffd48b591d19256884a969fe4da17caryclark const SkScalar* oPt = &oppSeg->pts()[0].fX; 138355888e44171ffd48b591d19256884a969fe4da17caryclark for (int index = 0; index < count; ++index) { 138455888e44171ffd48b591d19256884a969fe4da17caryclark if (*cPt < *oPt) { 138555888e44171ffd48b591d19256884a969fe4da17caryclark return true; 138655888e44171ffd48b591d19256884a969fe4da17caryclark } 138755888e44171ffd48b591d19256884a969fe4da17caryclark if (*cPt > *oPt) { 138855888e44171ffd48b591d19256884a969fe4da17caryclark return false; 138955888e44171ffd48b591d19256884a969fe4da17caryclark } 139055888e44171ffd48b591d19256884a969fe4da17caryclark ++cPt; 139155888e44171ffd48b591d19256884a969fe4da17caryclark ++oPt; 139255888e44171ffd48b591d19256884a969fe4da17caryclark } 13935c5cfe24efe4c728e787447dabffe345080d1fb9caryclark return true; 139454359294a7c9dc54802d512a5d891a35c1663392caryclark} 139554359294a7c9dc54802d512a5d891a35c1663392caryclark 139655888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::overlap(const SkOpPtT* coin1s, const SkOpPtT* coin1e, 139754359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpPtT* coin2s, const SkOpPtT* coin2e, double* overS, double* overE) const { 139827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkASSERT(coin1s->segment() == coin2s->segment()); 139954359294a7c9dc54802d512a5d891a35c1663392caryclark *overS = SkTMax(SkTMin(coin1s->fT, coin1e->fT), SkTMin(coin2s->fT, coin2e->fT)); 140054359294a7c9dc54802d512a5d891a35c1663392caryclark *overE = SkTMin(SkTMax(coin1s->fT, coin1e->fT), SkTMax(coin2s->fT, coin2e->fT)); 140154359294a7c9dc54802d512a5d891a35c1663392caryclark return *overS < *overE; 140254359294a7c9dc54802d512a5d891a35c1663392caryclark} 140327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 140455888e44171ffd48b591d19256884a969fe4da17caryclark// Commented-out lines keep this in sync with debugRelease() 140555888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpCoincidence::release(const SkOpSegment* deleted) { 140655888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* coin = fHead; 140755888e44171ffd48b591d19256884a969fe4da17caryclark if (!coin) { 140855888e44171ffd48b591d19256884a969fe4da17caryclark return; 140955888e44171ffd48b591d19256884a969fe4da17caryclark } 141055888e44171ffd48b591d19256884a969fe4da17caryclark do { 141155888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->coinPtTStart()->segment() == deleted 141255888e44171ffd48b591d19256884a969fe4da17caryclark || coin->coinPtTEnd()->segment() == deleted 141355888e44171ffd48b591d19256884a969fe4da17caryclark || coin->oppPtTStart()->segment() == deleted 141455888e44171ffd48b591d19256884a969fe4da17caryclark || coin->oppPtTEnd()->segment() == deleted) { 141555888e44171ffd48b591d19256884a969fe4da17caryclark this->release(fHead, coin); 141655888e44171ffd48b591d19256884a969fe4da17caryclark } 141755888e44171ffd48b591d19256884a969fe4da17caryclark } while ((coin = coin->next())); 141855888e44171ffd48b591d19256884a969fe4da17caryclark} 1419