SkOpCoincidence.cpp revision 9de097639f04e5a18da2d2b123dace9d24ab50e4
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 1955888e44171ffd48b591d19256884a969fe4da17caryclark// sets the span's end to the ptT referenced by the previous-next 2055888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkCoincidentSpans::correctOneEnd( 2155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* (SkCoincidentSpans::* getEnd)() const, 2255888e44171ffd48b591d19256884a969fe4da17caryclark void (SkCoincidentSpans::*setEnd)(const SkOpPtT* ptT) ) { 2355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* origPtT = (this->*getEnd)(); 2455888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* origSpan = origPtT->span(); 2555888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpan* prev = origSpan->prev(); 2655888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* testPtT = prev ? prev->next()->ptT() 2755888e44171ffd48b591d19256884a969fe4da17caryclark : origSpan->upCast()->next()->prev()->ptT(); 2855888e44171ffd48b591d19256884a969fe4da17caryclark if (origPtT != testPtT) { 2955888e44171ffd48b591d19256884a969fe4da17caryclark (this->*setEnd)(testPtT); 3055888e44171ffd48b591d19256884a969fe4da17caryclark } 3155888e44171ffd48b591d19256884a969fe4da17caryclark} 3255888e44171ffd48b591d19256884a969fe4da17caryclark 33ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark/* Please keep this in sync with debugCorrectEnds */ 3455888e44171ffd48b591d19256884a969fe4da17caryclark// FIXME: member pointers have fallen out of favor and can be replaced with 3555888e44171ffd48b591d19256884a969fe4da17caryclark// an alternative approach. 3655888e44171ffd48b591d19256884a969fe4da17caryclark// makes all span ends agree with the segment's spans that define them 3755888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkCoincidentSpans::correctEnds() { 3855888e44171ffd48b591d19256884a969fe4da17caryclark this->correctOneEnd(&SkCoincidentSpans::coinPtTStart, &SkCoincidentSpans::setCoinPtTStart); 3955888e44171ffd48b591d19256884a969fe4da17caryclark this->correctOneEnd(&SkCoincidentSpans::coinPtTEnd, &SkCoincidentSpans::setCoinPtTEnd); 4055888e44171ffd48b591d19256884a969fe4da17caryclark this->correctOneEnd(&SkCoincidentSpans::oppPtTStart, &SkCoincidentSpans::setOppPtTStart); 4155888e44171ffd48b591d19256884a969fe4da17caryclark this->correctOneEnd(&SkCoincidentSpans::oppPtTEnd, &SkCoincidentSpans::setOppPtTEnd); 4255888e44171ffd48b591d19256884a969fe4da17caryclark} 4355888e44171ffd48b591d19256884a969fe4da17caryclark 4455888e44171ffd48b591d19256884a969fe4da17caryclark/* Please keep this in sync with debugExpand */ 4555888e44171ffd48b591d19256884a969fe4da17caryclark// expand the range by checking adjacent spans for coincidence 4655888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkCoincidentSpans::expand() { 4755888e44171ffd48b591d19256884a969fe4da17caryclark bool expanded = false; 4855888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* segment = coinPtTStart()->segment(); 4955888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* oppSegment = oppPtTStart()->segment(); 5055888e44171ffd48b591d19256884a969fe4da17caryclark do { 5155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpan* start = coinPtTStart()->span()->upCast(); 5255888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpan* prev = start->prev(); 5355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* oppPtT; 5455888e44171ffd48b591d19256884a969fe4da17caryclark if (!prev || !(oppPtT = prev->contains(oppSegment))) { 5555888e44171ffd48b591d19256884a969fe4da17caryclark break; 5655888e44171ffd48b591d19256884a969fe4da17caryclark } 5755888e44171ffd48b591d19256884a969fe4da17caryclark double midT = (prev->t() + start->t()) / 2; 5855888e44171ffd48b591d19256884a969fe4da17caryclark if (!segment->isClose(midT, oppSegment)) { 5955888e44171ffd48b591d19256884a969fe4da17caryclark break; 6055888e44171ffd48b591d19256884a969fe4da17caryclark } 6155888e44171ffd48b591d19256884a969fe4da17caryclark setStarts(prev->ptT(), oppPtT); 6255888e44171ffd48b591d19256884a969fe4da17caryclark expanded = true; 6355888e44171ffd48b591d19256884a969fe4da17caryclark } while (true); 6455888e44171ffd48b591d19256884a969fe4da17caryclark do { 6555888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* end = coinPtTEnd()->span(); 6655888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next(); 67c6d855f7f3d548c52f450299dc6975820cda3387caryclark if (next && next->deleted()) { 68c6d855f7f3d548c52f450299dc6975820cda3387caryclark break; 69c6d855f7f3d548c52f450299dc6975820cda3387caryclark } 7055888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* oppPtT; 7155888e44171ffd48b591d19256884a969fe4da17caryclark if (!next || !(oppPtT = next->contains(oppSegment))) { 7255888e44171ffd48b591d19256884a969fe4da17caryclark break; 7355888e44171ffd48b591d19256884a969fe4da17caryclark } 7455888e44171ffd48b591d19256884a969fe4da17caryclark double midT = (end->t() + next->t()) / 2; 7555888e44171ffd48b591d19256884a969fe4da17caryclark if (!segment->isClose(midT, oppSegment)) { 7655888e44171ffd48b591d19256884a969fe4da17caryclark break; 7755888e44171ffd48b591d19256884a969fe4da17caryclark } 7855888e44171ffd48b591d19256884a969fe4da17caryclark setEnds(next->ptT(), oppPtT); 7955888e44171ffd48b591d19256884a969fe4da17caryclark expanded = true; 8055888e44171ffd48b591d19256884a969fe4da17caryclark } while (true); 8155888e44171ffd48b591d19256884a969fe4da17caryclark return expanded; 8255888e44171ffd48b591d19256884a969fe4da17caryclark} 8355888e44171ffd48b591d19256884a969fe4da17caryclark 8455888e44171ffd48b591d19256884a969fe4da17caryclark// increase the range of this span 8555888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkCoincidentSpans::extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, 8655888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) { 8755888e44171ffd48b591d19256884a969fe4da17caryclark bool result = false; 8855888e44171ffd48b591d19256884a969fe4da17caryclark if (fCoinPtTStart->fT > coinPtTStart->fT || (this->flipped() 8955888e44171ffd48b591d19256884a969fe4da17caryclark ? fOppPtTStart->fT < oppPtTStart->fT : fOppPtTStart->fT > oppPtTStart->fT)) { 9055888e44171ffd48b591d19256884a969fe4da17caryclark this->setStarts(coinPtTStart, oppPtTStart); 9155888e44171ffd48b591d19256884a969fe4da17caryclark result = true; 9255888e44171ffd48b591d19256884a969fe4da17caryclark } 9355888e44171ffd48b591d19256884a969fe4da17caryclark if (fCoinPtTEnd->fT < coinPtTEnd->fT || (this->flipped() 9455888e44171ffd48b591d19256884a969fe4da17caryclark ? fOppPtTEnd->fT > oppPtTEnd->fT : fOppPtTEnd->fT < oppPtTEnd->fT)) { 9555888e44171ffd48b591d19256884a969fe4da17caryclark this->setEnds(coinPtTEnd, oppPtTEnd); 9655888e44171ffd48b591d19256884a969fe4da17caryclark result = true; 9755888e44171ffd48b591d19256884a969fe4da17caryclark } 9855888e44171ffd48b591d19256884a969fe4da17caryclark return result; 9955888e44171ffd48b591d19256884a969fe4da17caryclark} 10055888e44171ffd48b591d19256884a969fe4da17caryclark 10155888e44171ffd48b591d19256884a969fe4da17caryclark// set the range of this span 10255888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkCoincidentSpans::set(SkCoincidentSpans* next, const SkOpPtT* coinPtTStart, 103ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) { 10455888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(SkOpCoincidence::Ordered(coinPtTStart, oppPtTStart)); 10555888e44171ffd48b591d19256884a969fe4da17caryclark fNext = next; 10655888e44171ffd48b591d19256884a969fe4da17caryclark this->setStarts(coinPtTStart, oppPtTStart); 10755888e44171ffd48b591d19256884a969fe4da17caryclark this->setEnds(coinPtTEnd, oppPtTEnd); 10855888e44171ffd48b591d19256884a969fe4da17caryclark} 10955888e44171ffd48b591d19256884a969fe4da17caryclark 11055888e44171ffd48b591d19256884a969fe4da17caryclark// returns true if both points are inside this 11155888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkCoincidentSpans::contains(const SkOpPtT* s, const SkOpPtT* e) const { 11255888e44171ffd48b591d19256884a969fe4da17caryclark if (s->fT > e->fT) { 11355888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(s, e); 11455888e44171ffd48b591d19256884a969fe4da17caryclark } 11555888e44171ffd48b591d19256884a969fe4da17caryclark if (s->segment() == fCoinPtTStart->segment()) { 11655888e44171ffd48b591d19256884a969fe4da17caryclark return fCoinPtTStart->fT <= s->fT && e->fT <= fCoinPtTEnd->fT; 11755888e44171ffd48b591d19256884a969fe4da17caryclark } else { 11855888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(s->segment() == fOppPtTStart->segment()); 11955888e44171ffd48b591d19256884a969fe4da17caryclark double oppTs = fOppPtTStart->fT; 12055888e44171ffd48b591d19256884a969fe4da17caryclark double oppTe = fOppPtTEnd->fT; 12155888e44171ffd48b591d19256884a969fe4da17caryclark if (oppTs > oppTe) { 12255888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(oppTs, oppTe); 12355888e44171ffd48b591d19256884a969fe4da17caryclark } 12455888e44171ffd48b591d19256884a969fe4da17caryclark return oppTs <= s->fT && e->fT <= oppTe; 12555888e44171ffd48b591d19256884a969fe4da17caryclark } 12655888e44171ffd48b591d19256884a969fe4da17caryclark} 12755888e44171ffd48b591d19256884a969fe4da17caryclark 12881a478ca6c36aac3e53ce0373a281ac8940f4780caryclark// A coincident span is unordered if the pairs of points in the main and opposite curves' 12981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark// t values do not ascend or descend. For instance, if a tightly arced quadratic is 13081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark// coincident with another curve, it may intersect it out of order. 131a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclarkbool SkCoincidentSpans::ordered(bool* result) const { 13281a478ca6c36aac3e53ce0373a281ac8940f4780caryclark const SkOpSpanBase* start = this->coinPtTStart()->span(); 13381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark const SkOpSpanBase* end = this->coinPtTEnd()->span(); 13481a478ca6c36aac3e53ce0373a281ac8940f4780caryclark const SkOpSpanBase* next = start->upCast()->next(); 13581a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if (next == end) { 136a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark *result = true; 13781a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 13881a478ca6c36aac3e53ce0373a281ac8940f4780caryclark } 13981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark bool flipped = this->flipped(); 14081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark const SkOpSegment* oppSeg = this->oppPtTStart()->segment(); 14181a478ca6c36aac3e53ce0373a281ac8940f4780caryclark double oppLastT = fOppPtTStart->fT; 14281a478ca6c36aac3e53ce0373a281ac8940f4780caryclark do { 14381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark const SkOpPtT* opp = next->contains(oppSeg); 14481a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if (!opp) { 145a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark SkOPOBJASSERT(start, 0); // may assert if coincident span isn't fully processed 146a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark return false; 14781a478ca6c36aac3e53ce0373a281ac8940f4780caryclark } 14881a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if ((oppLastT > opp->fT) != flipped) { 149a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark *result = false; 150a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark return true; 15181a478ca6c36aac3e53ce0373a281ac8940f4780caryclark } 15281a478ca6c36aac3e53ce0373a281ac8940f4780caryclark oppLastT = opp->fT; 15381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if (next == end) { 15481a478ca6c36aac3e53ce0373a281ac8940f4780caryclark break; 15581a478ca6c36aac3e53ce0373a281ac8940f4780caryclark } 156bbfe92bc1dd2b0a65e63b3caed9873dbc4df522acaryclark if (!next->upCastable()) { 157a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark *result = false; 158a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark return true; 159bbfe92bc1dd2b0a65e63b3caed9873dbc4df522acaryclark } 16081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark next = next->upCast()->next(); 16181a478ca6c36aac3e53ce0373a281ac8940f4780caryclark } while (true); 162a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark *result = true; 16381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 16481a478ca6c36aac3e53ce0373a281ac8940f4780caryclark} 16581a478ca6c36aac3e53ce0373a281ac8940f4780caryclark 16655888e44171ffd48b591d19256884a969fe4da17caryclark// if there is an existing pair that overlaps the addition, extend it 16755888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, 16855888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) { 16955888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* test = fHead; 17055888e44171ffd48b591d19256884a969fe4da17caryclark if (!test) { 17155888e44171ffd48b591d19256884a969fe4da17caryclark return false; 17255888e44171ffd48b591d19256884a969fe4da17caryclark } 17355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* coinSeg = coinPtTStart->segment(); 17455888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* oppSeg = oppPtTStart->segment(); 17555888e44171ffd48b591d19256884a969fe4da17caryclark if (!Ordered(coinPtTStart, oppPtTStart)) { 17655888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinSeg, oppSeg); 17755888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinPtTStart, oppPtTStart); 17855888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinPtTEnd, oppPtTEnd); 17955888e44171ffd48b591d19256884a969fe4da17caryclark if (coinPtTStart->fT > coinPtTEnd->fT) { 18055888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinPtTStart, coinPtTEnd); 18155888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(oppPtTStart, oppPtTEnd); 18255888e44171ffd48b591d19256884a969fe4da17caryclark } 18355888e44171ffd48b591d19256884a969fe4da17caryclark } 18455888e44171ffd48b591d19256884a969fe4da17caryclark double oppMinT = SkTMin(oppPtTStart->fT, oppPtTEnd->fT); 18555888e44171ffd48b591d19256884a969fe4da17caryclark SkDEBUGCODE(double oppMaxT = SkTMax(oppPtTStart->fT, oppPtTEnd->fT)); 18655888e44171ffd48b591d19256884a969fe4da17caryclark do { 18755888e44171ffd48b591d19256884a969fe4da17caryclark if (coinSeg != test->coinPtTStart()->segment()) { 18855888e44171ffd48b591d19256884a969fe4da17caryclark continue; 18955888e44171ffd48b591d19256884a969fe4da17caryclark } 19055888e44171ffd48b591d19256884a969fe4da17caryclark if (oppSeg != test->oppPtTStart()->segment()) { 19155888e44171ffd48b591d19256884a969fe4da17caryclark continue; 19255888e44171ffd48b591d19256884a969fe4da17caryclark } 19355888e44171ffd48b591d19256884a969fe4da17caryclark double oTestMinT = SkTMin(test->oppPtTStart()->fT, test->oppPtTEnd()->fT); 19455888e44171ffd48b591d19256884a969fe4da17caryclark double oTestMaxT = SkTMax(test->oppPtTStart()->fT, test->oppPtTEnd()->fT); 19555888e44171ffd48b591d19256884a969fe4da17caryclark // if debug check triggers, caller failed to check if extended already exists 19655888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(test->coinPtTStart()->fT > coinPtTStart->fT 19755888e44171ffd48b591d19256884a969fe4da17caryclark || coinPtTEnd->fT > test->coinPtTEnd()->fT 19855888e44171ffd48b591d19256884a969fe4da17caryclark || oTestMinT > oppMinT || oppMaxT > oTestMaxT); 19955888e44171ffd48b591d19256884a969fe4da17caryclark if ((test->coinPtTStart()->fT <= coinPtTEnd->fT 20055888e44171ffd48b591d19256884a969fe4da17caryclark && coinPtTStart->fT <= test->coinPtTEnd()->fT) 20155888e44171ffd48b591d19256884a969fe4da17caryclark || (oTestMinT <= oTestMaxT && oppMinT <= oTestMaxT)) { 20255888e44171ffd48b591d19256884a969fe4da17caryclark test->extend(coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd); 20355888e44171ffd48b591d19256884a969fe4da17caryclark return true; 20455888e44171ffd48b591d19256884a969fe4da17caryclark } 20555888e44171ffd48b591d19256884a969fe4da17caryclark } while ((test = test->next())); 20655888e44171ffd48b591d19256884a969fe4da17caryclark return false; 20755888e44171ffd48b591d19256884a969fe4da17caryclark} 20855888e44171ffd48b591d19256884a969fe4da17caryclark 20955888e44171ffd48b591d19256884a969fe4da17caryclark// verifies that the coincidence hasn't already been added 21055888e44171ffd48b591d19256884a969fe4da17caryclarkstatic void DebugCheckAdd(const SkCoincidentSpans* check, const SkOpPtT* coinPtTStart, 21155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) { 21255888e44171ffd48b591d19256884a969fe4da17caryclark#if DEBUG_COINCIDENCE 21355888e44171ffd48b591d19256884a969fe4da17caryclark while (check) { 21455888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(check->coinPtTStart() != coinPtTStart || check->coinPtTEnd() != coinPtTEnd 21555888e44171ffd48b591d19256884a969fe4da17caryclark || check->oppPtTStart() != oppPtTStart || check->oppPtTEnd() != oppPtTEnd); 21655888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(check->coinPtTStart() != oppPtTStart || check->coinPtTEnd() != oppPtTEnd 21755888e44171ffd48b591d19256884a969fe4da17caryclark || check->oppPtTStart() != coinPtTStart || check->oppPtTEnd() != coinPtTEnd); 21855888e44171ffd48b591d19256884a969fe4da17caryclark check = check->next(); 21955888e44171ffd48b591d19256884a969fe4da17caryclark } 22055888e44171ffd48b591d19256884a969fe4da17caryclark#endif 22155888e44171ffd48b591d19256884a969fe4da17caryclark} 22255888e44171ffd48b591d19256884a969fe4da17caryclark 22355888e44171ffd48b591d19256884a969fe4da17caryclark// adds a new coincident pair 22455888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpCoincidence::add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart, 22555888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* oppPtTEnd) { 22655888e44171ffd48b591d19256884a969fe4da17caryclark // OPTIMIZE: caller should have already sorted 22755888e44171ffd48b591d19256884a969fe4da17caryclark if (!Ordered(coinPtTStart, oppPtTStart)) { 22855888e44171ffd48b591d19256884a969fe4da17caryclark if (oppPtTStart->fT < oppPtTEnd->fT) { 22955888e44171ffd48b591d19256884a969fe4da17caryclark this->add(oppPtTStart, oppPtTEnd, coinPtTStart, coinPtTEnd); 23055888e44171ffd48b591d19256884a969fe4da17caryclark } else { 23155888e44171ffd48b591d19256884a969fe4da17caryclark this->add(oppPtTEnd, oppPtTStart, coinPtTEnd, coinPtTStart); 23255888e44171ffd48b591d19256884a969fe4da17caryclark } 23355888e44171ffd48b591d19256884a969fe4da17caryclark return; 23455888e44171ffd48b591d19256884a969fe4da17caryclark } 23555888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(Ordered(coinPtTStart, oppPtTStart)); 23655888e44171ffd48b591d19256884a969fe4da17caryclark // choose the ptT at the front of the list to track 23755888e44171ffd48b591d19256884a969fe4da17caryclark coinPtTStart = coinPtTStart->span()->ptT(); 23855888e44171ffd48b591d19256884a969fe4da17caryclark coinPtTEnd = coinPtTEnd->span()->ptT(); 23955888e44171ffd48b591d19256884a969fe4da17caryclark oppPtTStart = oppPtTStart->span()->ptT(); 24055888e44171ffd48b591d19256884a969fe4da17caryclark oppPtTEnd = oppPtTEnd->span()->ptT(); 241a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark SkOPASSERT(coinPtTStart->fT < coinPtTEnd->fT); 24296dc1c9efaab4636e30f90aa377f25863f9bf3bacaryclark SkOPASSERT(oppPtTStart->fT != oppPtTEnd->fT); 24330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOPASSERT(!coinPtTStart->deleted()); 24430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOPASSERT(!coinPtTEnd->deleted()); 24530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOPASSERT(!oppPtTStart->deleted()); 24630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOPASSERT(!oppPtTEnd->deleted()); 24755888e44171ffd48b591d19256884a969fe4da17caryclark DebugCheckAdd(fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd); 24855888e44171ffd48b591d19256884a969fe4da17caryclark DebugCheckAdd(fTop, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd); 24955888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* coinRec = SkOpTAllocator<SkCoincidentSpans>::Allocate( 25055888e44171ffd48b591d19256884a969fe4da17caryclark this->globalState()->allocator()); 251fc560e09b3f777bb32dccb9f52d715383a10a620caryclark coinRec->init(SkDEBUGCODE(fGlobalState)); 252ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark coinRec->set(this->fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd); 25355888e44171ffd48b591d19256884a969fe4da17caryclark fHead = coinRec; 25455888e44171ffd48b591d19256884a969fe4da17caryclark} 25555888e44171ffd48b591d19256884a969fe4da17caryclark 25655888e44171ffd48b591d19256884a969fe4da17caryclark// description below 2571597628fa38d24f23ad505bfb40e70e7c8617457caryclarkbool SkOpCoincidence::addEndMovedSpans(const SkOpSpan* base, const SkOpSpanBase* testSpan) { 25855888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* testPtT = testSpan->ptT(); 25955888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* stopPtT = testPtT; 26055888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* baseSeg = base->segment(); 26155888e44171ffd48b591d19256884a969fe4da17caryclark while ((testPtT = testPtT->next()) != stopPtT) { 26255888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* testSeg = testPtT->segment(); 26355888e44171ffd48b591d19256884a969fe4da17caryclark if (testPtT->deleted()) { 26455888e44171ffd48b591d19256884a969fe4da17caryclark continue; 26555888e44171ffd48b591d19256884a969fe4da17caryclark } 26655888e44171ffd48b591d19256884a969fe4da17caryclark if (testSeg == baseSeg) { 26755888e44171ffd48b591d19256884a969fe4da17caryclark continue; 26855888e44171ffd48b591d19256884a969fe4da17caryclark } 269c6d855f7f3d548c52f450299dc6975820cda3387caryclark if (testPtT->span()->ptT() != testPtT) { 270c6d855f7f3d548c52f450299dc6975820cda3387caryclark continue; 271c6d855f7f3d548c52f450299dc6975820cda3387caryclark } 27255888e44171ffd48b591d19256884a969fe4da17caryclark if (this->contains(baseSeg, testSeg, testPtT->fT)) { 27355888e44171ffd48b591d19256884a969fe4da17caryclark continue; 27455888e44171ffd48b591d19256884a969fe4da17caryclark } 27555888e44171ffd48b591d19256884a969fe4da17caryclark // intersect perp with base->ptT() with testPtT->segment() 27655888e44171ffd48b591d19256884a969fe4da17caryclark SkDVector dxdy = baseSeg->dSlopeAtT(base->t()); 27755888e44171ffd48b591d19256884a969fe4da17caryclark const SkPoint& pt = base->pt(); 27855888e44171ffd48b591d19256884a969fe4da17caryclark SkDLine ray = {{{pt.fX, pt.fY}, {pt.fX + dxdy.fY, pt.fY - dxdy.fX}}}; 27955888e44171ffd48b591d19256884a969fe4da17caryclark SkIntersections i; 28055888e44171ffd48b591d19256884a969fe4da17caryclark (*CurveIntersectRay[testSeg->verb()])(testSeg->pts(), testSeg->weight(), ray, &i); 28155888e44171ffd48b591d19256884a969fe4da17caryclark for (int index = 0; index < i.used(); ++index) { 28255888e44171ffd48b591d19256884a969fe4da17caryclark double t = i[0][index]; 28355888e44171ffd48b591d19256884a969fe4da17caryclark if (!between(0, t, 1)) { 284bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark continue; 285bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 28655888e44171ffd48b591d19256884a969fe4da17caryclark SkDPoint oppPt = i.pt(index); 28755888e44171ffd48b591d19256884a969fe4da17caryclark if (!oppPt.approximatelyEqual(pt)) { 288bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark continue; 289bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 29055888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSegment* writableSeg = const_cast<SkOpSegment*>(testSeg); 29129b2563afb1677515739f1d24fb27733626eca92caryclark SkOpPtT* oppStart = writableSeg->addT(t); 29227c015dfcf4e2b8fb1abe327cc40204e2a4f452acaryclark if (oppStart == testPtT) { 29327c015dfcf4e2b8fb1abe327cc40204e2a4f452acaryclark continue; 29427c015dfcf4e2b8fb1abe327cc40204e2a4f452acaryclark } 29555888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpan* writableBase = const_cast<SkOpSpan*>(base); 29630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark oppStart->span()->addOpp(writableBase); 29755888e44171ffd48b591d19256884a969fe4da17caryclark if (oppStart->deleted()) { 298bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark continue; 299bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 30055888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSegment* coinSeg = base->segment(); 30155888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSegment* oppSeg = oppStart->segment(); 30255888e44171ffd48b591d19256884a969fe4da17caryclark double coinTs, coinTe, oppTs, oppTe; 3038016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (Ordered(coinSeg, oppSeg)) { 30455888e44171ffd48b591d19256884a969fe4da17caryclark coinTs = base->t(); 30555888e44171ffd48b591d19256884a969fe4da17caryclark coinTe = testSpan->t(); 30655888e44171ffd48b591d19256884a969fe4da17caryclark oppTs = oppStart->fT; 30755888e44171ffd48b591d19256884a969fe4da17caryclark oppTe = testPtT->fT; 30855888e44171ffd48b591d19256884a969fe4da17caryclark } else { 30955888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinSeg, oppSeg); 31055888e44171ffd48b591d19256884a969fe4da17caryclark coinTs = oppStart->fT; 31155888e44171ffd48b591d19256884a969fe4da17caryclark coinTe = testPtT->fT; 31255888e44171ffd48b591d19256884a969fe4da17caryclark oppTs = base->t(); 31355888e44171ffd48b591d19256884a969fe4da17caryclark oppTe = testSpan->t(); 314bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 31555888e44171ffd48b591d19256884a969fe4da17caryclark if (coinTs > coinTe) { 31655888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinTs, coinTe); 31755888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(oppTs, oppTe); 318bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 31981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark bool added; 32081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if (!this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &added)) { 3211597628fa38d24f23ad505bfb40e70e7c8617457caryclark return false; 3221597628fa38d24f23ad505bfb40e70e7c8617457caryclark } 32355888e44171ffd48b591d19256884a969fe4da17caryclark } 324bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 3251597628fa38d24f23ad505bfb40e70e7c8617457caryclark return true; 326bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark} 327bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark 32855888e44171ffd48b591d19256884a969fe4da17caryclark// description below 32955888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::addEndMovedSpans(const SkOpPtT* ptT) { 330025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark FAIL_IF(!ptT->span()->upCastable()); 33155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpan* base = ptT->span()->upCast(); 33255888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpan* prev = base->prev(); 333025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark FAIL_IF(!prev); 33455888e44171ffd48b591d19256884a969fe4da17caryclark if (!prev->isCanceled()) { 3351597628fa38d24f23ad505bfb40e70e7c8617457caryclark if (!this->addEndMovedSpans(base, base->prev())) { 3361597628fa38d24f23ad505bfb40e70e7c8617457caryclark return false; 3371597628fa38d24f23ad505bfb40e70e7c8617457caryclark } 33855888e44171ffd48b591d19256884a969fe4da17caryclark } 33955888e44171ffd48b591d19256884a969fe4da17caryclark if (!base->isCanceled()) { 3401597628fa38d24f23ad505bfb40e70e7c8617457caryclark if (!this->addEndMovedSpans(base, base->next())) { 3411597628fa38d24f23ad505bfb40e70e7c8617457caryclark return false; 3421597628fa38d24f23ad505bfb40e70e7c8617457caryclark } 34355888e44171ffd48b591d19256884a969fe4da17caryclark } 34455888e44171ffd48b591d19256884a969fe4da17caryclark return true; 34554359294a7c9dc54802d512a5d891a35c1663392caryclark} 34654359294a7c9dc54802d512a5d891a35c1663392caryclark 34755888e44171ffd48b591d19256884a969fe4da17caryclark/* If A is coincident with B and B includes an endpoint, and A's matching point 34855888e44171ffd48b591d19256884a969fe4da17caryclark is not the endpoint (i.e., there's an implied line connecting B-end and A) 34955888e44171ffd48b591d19256884a969fe4da17caryclark then assume that the same implied line may intersect another curve close to B. 35055888e44171ffd48b591d19256884a969fe4da17caryclark Since we only care about coincidence that was undetected, look at the 35155888e44171ffd48b591d19256884a969fe4da17caryclark ptT list on B-segment adjacent to the B-end/A ptT loop (not in the loop, but 35255888e44171ffd48b591d19256884a969fe4da17caryclark next door) and see if the A matching point is close enough to form another 35355888e44171ffd48b591d19256884a969fe4da17caryclark coincident pair. If so, check for a new coincident span between B-end/A ptT loop 35455888e44171ffd48b591d19256884a969fe4da17caryclark and the adjacent ptT loop. 35555888e44171ffd48b591d19256884a969fe4da17caryclark*/ 356ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clarkbool SkOpCoincidence::addEndMovedSpans(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 357ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark DEBUG_SET_PHASE(); 35855888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* span = fHead; 35955888e44171ffd48b591d19256884a969fe4da17caryclark if (!span) { 36055888e44171ffd48b591d19256884a969fe4da17caryclark return true; 36155888e44171ffd48b591d19256884a969fe4da17caryclark } 36255888e44171ffd48b591d19256884a969fe4da17caryclark fTop = span; 36355888e44171ffd48b591d19256884a969fe4da17caryclark fHead = nullptr; 36455888e44171ffd48b591d19256884a969fe4da17caryclark do { 36555888e44171ffd48b591d19256884a969fe4da17caryclark if (span->coinPtTStart()->fPt != span->oppPtTStart()->fPt) { 366025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark FAIL_IF(1 == span->coinPtTStart()->fT); 36755888e44171ffd48b591d19256884a969fe4da17caryclark bool onEnd = span->coinPtTStart()->fT == 0; 36855888e44171ffd48b591d19256884a969fe4da17caryclark bool oOnEnd = zero_or_one(span->oppPtTStart()->fT); 36955888e44171ffd48b591d19256884a969fe4da17caryclark if (onEnd) { 37055888e44171ffd48b591d19256884a969fe4da17caryclark if (!oOnEnd) { // if both are on end, any nearby intersect was already found 37155888e44171ffd48b591d19256884a969fe4da17caryclark if (!this->addEndMovedSpans(span->oppPtTStart())) { 37255888e44171ffd48b591d19256884a969fe4da17caryclark return false; 37355888e44171ffd48b591d19256884a969fe4da17caryclark } 37455888e44171ffd48b591d19256884a969fe4da17caryclark } 37555888e44171ffd48b591d19256884a969fe4da17caryclark } else if (oOnEnd) { 37655888e44171ffd48b591d19256884a969fe4da17caryclark if (!this->addEndMovedSpans(span->coinPtTStart())) { 37755888e44171ffd48b591d19256884a969fe4da17caryclark return false; 37855888e44171ffd48b591d19256884a969fe4da17caryclark } 37955888e44171ffd48b591d19256884a969fe4da17caryclark } 38055888e44171ffd48b591d19256884a969fe4da17caryclark } 38155888e44171ffd48b591d19256884a969fe4da17caryclark if (span->coinPtTEnd()->fPt != span->oppPtTEnd()->fPt) { 38255888e44171ffd48b591d19256884a969fe4da17caryclark bool onEnd = span->coinPtTEnd()->fT == 1; 38355888e44171ffd48b591d19256884a969fe4da17caryclark bool oOnEnd = zero_or_one(span->oppPtTEnd()->fT); 38455888e44171ffd48b591d19256884a969fe4da17caryclark if (onEnd) { 38555888e44171ffd48b591d19256884a969fe4da17caryclark if (!oOnEnd) { 38655888e44171ffd48b591d19256884a969fe4da17caryclark if (!this->addEndMovedSpans(span->oppPtTEnd())) { 38755888e44171ffd48b591d19256884a969fe4da17caryclark return false; 38855888e44171ffd48b591d19256884a969fe4da17caryclark } 38955888e44171ffd48b591d19256884a969fe4da17caryclark } 39055888e44171ffd48b591d19256884a969fe4da17caryclark } else if (oOnEnd) { 39155888e44171ffd48b591d19256884a969fe4da17caryclark if (!this->addEndMovedSpans(span->coinPtTEnd())) { 39255888e44171ffd48b591d19256884a969fe4da17caryclark return false; 39355888e44171ffd48b591d19256884a969fe4da17caryclark } 39455888e44171ffd48b591d19256884a969fe4da17caryclark } 39555888e44171ffd48b591d19256884a969fe4da17caryclark } 39655888e44171ffd48b591d19256884a969fe4da17caryclark } while ((span = span->next())); 39755888e44171ffd48b591d19256884a969fe4da17caryclark this->restoreHead(); 39855888e44171ffd48b591d19256884a969fe4da17caryclark return true; 39954359294a7c9dc54802d512a5d891a35c1663392caryclark} 40054359294a7c9dc54802d512a5d891a35c1663392caryclark 40155888e44171ffd48b591d19256884a969fe4da17caryclark/* Please keep this in sync with debugAddExpanded */ 40255888e44171ffd48b591d19256884a969fe4da17caryclark// for each coincident pair, match the spans 40355888e44171ffd48b591d19256884a969fe4da17caryclark// if the spans don't match, add the missing pt to the segment and loop it in the opposite span 404ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clarkbool SkOpCoincidence::addExpanded(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 405ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark DEBUG_SET_PHASE(); 40627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkCoincidentSpans* coin = this->fHead; 40755888e44171ffd48b591d19256884a969fe4da17caryclark if (!coin) { 40855888e44171ffd48b591d19256884a969fe4da17caryclark return true; 40955888e44171ffd48b591d19256884a969fe4da17caryclark } 41027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark do { 41155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* startPtT = coin->coinPtTStart(); 41255888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* oStartPtT = coin->oppPtTStart(); 4138016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double priorT = startPtT->fT; 4148016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double oPriorT = oStartPtT->fT; 415bbfe92bc1dd2b0a65e63b3caed9873dbc4df522acaryclark FAIL_IF(!startPtT->contains(oStartPtT)); 416c6d855f7f3d548c52f450299dc6975820cda3387caryclark SkOPASSERT(coin->coinPtTEnd()->contains(coin->oppPtTEnd())); 41755888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* start = startPtT->span(); 41855888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* oStart = oStartPtT->span(); 41955888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* end = coin->coinPtTEnd()->span(); 42055888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* oEnd = coin->oppPtTEnd()->span(); 42155888e44171ffd48b591d19256884a969fe4da17caryclark FAIL_IF(oEnd->deleted()); 422e25a4f6cbeaccfdc34cf031103f0fbc3e53a3ee5caryclark FAIL_IF(!start->upCastable()); 42355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* test = start->upCast()->next(); 424e7bb5b226662f01c91574b29f435acae71c76c46caryclark FAIL_IF(!coin->flipped() && !oStart->upCastable()); 42555888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* oTest = coin->flipped() ? oStart->prev() : oStart->upCast()->next(); 42630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark FAIL_IF(!oTest); 4278016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkOpSegment* seg = start->segment(); 4288016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkOpSegment* oSeg = oStart->segment(); 42927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark while (test != end || oTest != oEnd) { 4308016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* containedOpp = test->ptT()->contains(oSeg); 4318016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* containedThis = oTest->ptT()->contains(seg); 4328016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (!containedOpp || !containedThis) { 4338016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark // choose the ends, or the first common pt-t list shared by both 4348016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double nextT, oNextT; 4358016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (containedOpp) { 4368016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark nextT = test->t(); 4378016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark oNextT = containedOpp->fT; 4388016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark } else if (containedThis) { 4398016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark nextT = containedThis->fT; 4408016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark oNextT = oTest->t(); 4418016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark } else { 4428016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark // iterate through until a pt-t list found that contains the other 4438016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpSpanBase* walk = test; 4448016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* walkOpp; 4458016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark do { 4468016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark FAIL_IF(!walk->upCastable()); 4478016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark walk = walk->upCast()->next(); 4488016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark } while (!(walkOpp = walk->ptT()->contains(oSeg)) 4498016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark && walk != coin->coinPtTEnd()->span()); 4503fdf52cf389d58be9ce4b948dfecffd53edb5da2Cary Clark FAIL_IF(!walkOpp); 4518016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark nextT = walk->t(); 4528016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark oNextT = walkOpp->fT; 4538016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark } 45427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark // use t ranges to guess which one is missing 4558016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double startRange = nextT - priorT; 45655888e44171ffd48b591d19256884a969fe4da17caryclark FAIL_IF(!startRange); 4578016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double startPart = (test->t() - priorT) / startRange; 4588016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double oStartRange = oNextT - oPriorT; 45955888e44171ffd48b591d19256884a969fe4da17caryclark FAIL_IF(!oStartRange); 4608016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double oStartPart = (oTest->t() - oPriorT) / oStartRange; 46155888e44171ffd48b591d19256884a969fe4da17caryclark FAIL_IF(startPart == oStartPart); 4628016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark bool addToOpp = !containedOpp && !containedThis ? startPart < oStartPart 4638016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark : !!containedThis; 46455888e44171ffd48b591d19256884a969fe4da17caryclark bool startOver = false; 4658016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark bool success = addToOpp ? oSeg->addExpanded( 4668016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark oPriorT + oStartRange * startPart, test, &startOver) 4678016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark : seg->addExpanded( 4688016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark priorT + startRange * oStartPart, oTest, &startOver); 46930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark FAIL_IF(!success); 47055888e44171ffd48b591d19256884a969fe4da17caryclark if (startOver) { 47155888e44171ffd48b591d19256884a969fe4da17caryclark test = start; 47255888e44171ffd48b591d19256884a969fe4da17caryclark oTest = oStart; 47327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 47430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark end = coin->coinPtTEnd()->span(); 47530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark oEnd = coin->oppPtTEnd()->span(); 47627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 47727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (test != end) { 47830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark FAIL_IF(!test->upCastable()); 4798016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark priorT = test->t(); 48027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark test = test->upCast()->next(); 48127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 48226ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark if (oTest != oEnd) { 4838016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark oPriorT = oTest->t(); 48478a37a53365c24670b050acf993818c435922745caryclark if (coin->flipped()) { 48578a37a53365c24670b050acf993818c435922745caryclark oTest = oTest->prev(); 48678a37a53365c24670b050acf993818c435922745caryclark } else { 48778a37a53365c24670b050acf993818c435922745caryclark FAIL_IF(!oTest->upCastable()); 48878a37a53365c24670b050acf993818c435922745caryclark oTest = oTest->upCast()->next(); 48978a37a53365c24670b050acf993818c435922745caryclark } 49030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark FAIL_IF(!oTest); 49127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 4928016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark 49327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 49455888e44171ffd48b591d19256884a969fe4da17caryclark } while ((coin = coin->next())); 49526ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark return true; 49627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 49727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 49855888e44171ffd48b591d19256884a969fe4da17caryclark// given a t span, map the same range on the coincident span 4998016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark/* 5008016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclarkthe curves may not scale linearly, so interpolation may only happen within known points 5018016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclarkremap over1s, over1e, cointPtTStart, coinPtTEnd to smallest range that captures over1s 5028016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclarkthen repeat to capture over1e 5038016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark*/ 5048016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclarkdouble SkOpCoincidence::TRange(const SkOpPtT* overS, double t, 5058016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpSegment* coinSeg SkDEBUGPARAMS(const SkOpPtT* overE)) { 5068016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpSpanBase* work = overS->span(); 5078016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* foundStart = nullptr; 5088016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* foundEnd = nullptr; 5098016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* coinStart = nullptr; 5108016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* coinEnd = nullptr; 5118016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark do { 5128016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* contained = work->contains(coinSeg); 5138016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (!contained) { 514c9b90d15df5fcee848812fbab3d714aba9e41e69caryclark if (work->final()) { 515c9b90d15df5fcee848812fbab3d714aba9e41e69caryclark break; 516b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark } 5178016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark continue; 5188016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark } 5198016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (work->t() <= t) { 5208016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark coinStart = contained; 5218016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark foundStart = work->ptT(); 5228016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark } 5238016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (work->t() >= t) { 5248016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark coinEnd = contained; 5258016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark foundEnd = work->ptT(); 5268016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark break; 5278016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark } 5288016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(work->ptT() != overE); 5298016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark } while ((work = work->upCast()->next())); 530c9b90d15df5fcee848812fbab3d714aba9e41e69caryclark if (!coinStart || !coinEnd) { 531c9b90d15df5fcee848812fbab3d714aba9e41e69caryclark return 1; 532c9b90d15df5fcee848812fbab3d714aba9e41e69caryclark } 5338016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark // while overS->fT <=t and overS contains coinSeg 5348016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double denom = foundEnd->fT - foundStart->fT; 5358016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double sRatio = denom ? (t - foundStart->fT) / denom : 1; 5368016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark return coinStart->fT + (coinEnd->fT - coinStart->fT) * sRatio; 53755888e44171ffd48b591d19256884a969fe4da17caryclark} 53855888e44171ffd48b591d19256884a969fe4da17caryclark 53955888e44171ffd48b591d19256884a969fe4da17caryclark// return true if span overlaps existing and needs to adjust the coincident list 54055888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::checkOverlap(SkCoincidentSpans* check, 54155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* coinSeg, const SkOpSegment* oppSeg, 54255888e44171ffd48b591d19256884a969fe4da17caryclark double coinTs, double coinTe, double oppTs, double oppTe, 54355888e44171ffd48b591d19256884a969fe4da17caryclark SkTDArray<SkCoincidentSpans*>* overlaps) const { 54455888e44171ffd48b591d19256884a969fe4da17caryclark if (!Ordered(coinSeg, oppSeg)) { 54555888e44171ffd48b591d19256884a969fe4da17caryclark if (oppTs < oppTe) { 54655888e44171ffd48b591d19256884a969fe4da17caryclark return this->checkOverlap(check, oppSeg, coinSeg, oppTs, oppTe, coinTs, coinTe, 54755888e44171ffd48b591d19256884a969fe4da17caryclark overlaps); 54855888e44171ffd48b591d19256884a969fe4da17caryclark } 54955888e44171ffd48b591d19256884a969fe4da17caryclark return this->checkOverlap(check, oppSeg, coinSeg, oppTe, oppTs, coinTe, coinTs, overlaps); 55055888e44171ffd48b591d19256884a969fe4da17caryclark } 55155888e44171ffd48b591d19256884a969fe4da17caryclark bool swapOpp = oppTs > oppTe; 55255888e44171ffd48b591d19256884a969fe4da17caryclark if (swapOpp) { 55355888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(oppTs, oppTe); 55455888e44171ffd48b591d19256884a969fe4da17caryclark } 55527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark do { 55655888e44171ffd48b591d19256884a969fe4da17caryclark if (check->coinPtTStart()->segment() != coinSeg) { 55755888e44171ffd48b591d19256884a969fe4da17caryclark continue; 55827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 55955888e44171ffd48b591d19256884a969fe4da17caryclark if (check->oppPtTStart()->segment() != oppSeg) { 56055888e44171ffd48b591d19256884a969fe4da17caryclark continue; 56127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 56255888e44171ffd48b591d19256884a969fe4da17caryclark double checkTs = check->coinPtTStart()->fT; 56355888e44171ffd48b591d19256884a969fe4da17caryclark double checkTe = check->coinPtTEnd()->fT; 56455888e44171ffd48b591d19256884a969fe4da17caryclark bool coinOutside = coinTe < checkTs || coinTs > checkTe; 56555888e44171ffd48b591d19256884a969fe4da17caryclark double oCheckTs = check->oppPtTStart()->fT; 56655888e44171ffd48b591d19256884a969fe4da17caryclark double oCheckTe = check->oppPtTEnd()->fT; 56755888e44171ffd48b591d19256884a969fe4da17caryclark if (swapOpp) { 56855888e44171ffd48b591d19256884a969fe4da17caryclark if (oCheckTs <= oCheckTe) { 56981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return false; 57055888e44171ffd48b591d19256884a969fe4da17caryclark } 57155888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(oCheckTs, oCheckTe); 57255888e44171ffd48b591d19256884a969fe4da17caryclark } 57355888e44171ffd48b591d19256884a969fe4da17caryclark bool oppOutside = oppTe < oCheckTs || oppTs > oCheckTe; 57455888e44171ffd48b591d19256884a969fe4da17caryclark if (coinOutside && oppOutside) { 57555888e44171ffd48b591d19256884a969fe4da17caryclark continue; 57655888e44171ffd48b591d19256884a969fe4da17caryclark } 57755888e44171ffd48b591d19256884a969fe4da17caryclark bool coinInside = coinTe <= checkTe && coinTs >= checkTs; 57855888e44171ffd48b591d19256884a969fe4da17caryclark bool oppInside = oppTe <= oCheckTe && oppTs >= oCheckTs; 57981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if (coinInside && oppInside) { // already included, do nothing 58081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return false; 58155888e44171ffd48b591d19256884a969fe4da17caryclark } 58255888e44171ffd48b591d19256884a969fe4da17caryclark *overlaps->append() = check; // partial overlap, extend existing entry 58355888e44171ffd48b591d19256884a969fe4da17caryclark } while ((check = check->next())); 58426ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark return true; 58527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 58627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 58755888e44171ffd48b591d19256884a969fe4da17caryclark/* Please keep this in sync with debugAddIfMissing() */ 5888016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark// note that over1s, over1e, over2s, over2e are ordered 5898016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclarkbool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over2s, 59081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark double tStart, double tEnd, SkOpSegment* coinSeg, SkOpSegment* oppSeg, bool* added 5918016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(const SkOpPtT* over1e) SkDEBUGPARAMS(const SkOpPtT* over2e)) { 5928016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(tStart < tEnd); 5938016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(over1s->fT < over1e->fT); 5948016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(between(over1s->fT, tStart, over1e->fT)); 5958016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(between(over1s->fT, tEnd, over1e->fT)); 5968016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(over2s->fT < over2e->fT); 5978016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(between(over2s->fT, tStart, over2e->fT)); 5988016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(between(over2s->fT, tEnd, over2e->fT)); 5998016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(over1s->segment() == over1e->segment()); 6008016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(over2s->segment() == over2e->segment()); 6018016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(over1s->segment() == over2s->segment()); 6028016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(over1s->segment() != coinSeg); 6038016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(over1s->segment() != oppSeg); 6048016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(coinSeg != oppSeg); 60554359294a7c9dc54802d512a5d891a35c1663392caryclark double coinTs, coinTe, oppTs, oppTe; 6068016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark coinTs = TRange(over1s, tStart, coinSeg SkDEBUGPARAMS(over1e)); 6078016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark coinTe = TRange(over1s, tEnd, coinSeg SkDEBUGPARAMS(over1e)); 60830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (coinSeg->collapsed(coinTs, coinTe)) { 60981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 61030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 6118016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark oppTs = TRange(over2s, tStart, oppSeg SkDEBUGPARAMS(over2e)); 6128016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark oppTe = TRange(over2s, tEnd, oppSeg SkDEBUGPARAMS(over2e)); 61330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (oppSeg->collapsed(oppTs, oppTe)) { 61481a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 61530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 6168016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (coinTs > coinTe) { 61755888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinTs, coinTe); 61855888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(oppTs, oppTe); 61955888e44171ffd48b591d19256884a969fe4da17caryclark } 62081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, added); 62155888e44171ffd48b591d19256884a969fe4da17caryclark} 62255888e44171ffd48b591d19256884a969fe4da17caryclark 62355888e44171ffd48b591d19256884a969fe4da17caryclark/* Please keep this in sync with debugAddOrOverlap() */ 624025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark// If this is called by addEndMovedSpans(), a returned false propogates out to an abort. 625025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark// If this is called by AddIfMissing(), a returned false indicates there was nothing to add 62655888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg, 62781a478ca6c36aac3e53ce0373a281ac8940f4780caryclark double coinTs, double coinTe, double oppTs, double oppTe, bool* added) { 62855888e44171ffd48b591d19256884a969fe4da17caryclark SkTDArray<SkCoincidentSpans*> overlaps; 62981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(!fTop); 63055888e44171ffd48b591d19256884a969fe4da17caryclark if (!this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &overlaps)) { 63181a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 63255888e44171ffd48b591d19256884a969fe4da17caryclark } 63355888e44171ffd48b591d19256884a969fe4da17caryclark if (fHead && !this->checkOverlap(fHead, coinSeg, oppSeg, coinTs, 63455888e44171ffd48b591d19256884a969fe4da17caryclark coinTe, oppTs, oppTe, &overlaps)) { 63581a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 63655888e44171ffd48b591d19256884a969fe4da17caryclark } 63755888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* overlap = overlaps.count() ? overlaps[0] : nullptr; 63855888e44171ffd48b591d19256884a969fe4da17caryclark for (int index = 1; index < overlaps.count(); ++index) { // combine overlaps before continuing 63955888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* test = overlaps[index]; 64055888e44171ffd48b591d19256884a969fe4da17caryclark if (overlap->coinPtTStart()->fT > test->coinPtTStart()->fT) { 64155888e44171ffd48b591d19256884a969fe4da17caryclark overlap->setCoinPtTStart(test->coinPtTStart()); 64254359294a7c9dc54802d512a5d891a35c1663392caryclark } 64355888e44171ffd48b591d19256884a969fe4da17caryclark if (overlap->coinPtTEnd()->fT < test->coinPtTEnd()->fT) { 64455888e44171ffd48b591d19256884a969fe4da17caryclark overlap->setCoinPtTEnd(test->coinPtTEnd()); 64555888e44171ffd48b591d19256884a969fe4da17caryclark } 64655888e44171ffd48b591d19256884a969fe4da17caryclark if (overlap->flipped() 64755888e44171ffd48b591d19256884a969fe4da17caryclark ? overlap->oppPtTStart()->fT < test->oppPtTStart()->fT 64855888e44171ffd48b591d19256884a969fe4da17caryclark : overlap->oppPtTStart()->fT > test->oppPtTStart()->fT) { 64955888e44171ffd48b591d19256884a969fe4da17caryclark overlap->setOppPtTStart(test->oppPtTStart()); 65054359294a7c9dc54802d512a5d891a35c1663392caryclark } 65155888e44171ffd48b591d19256884a969fe4da17caryclark if (overlap->flipped() 65255888e44171ffd48b591d19256884a969fe4da17caryclark ? overlap->oppPtTEnd()->fT > test->oppPtTEnd()->fT 65355888e44171ffd48b591d19256884a969fe4da17caryclark : overlap->oppPtTEnd()->fT < test->oppPtTEnd()->fT) { 65455888e44171ffd48b591d19256884a969fe4da17caryclark overlap->setOppPtTEnd(test->oppPtTEnd()); 65555888e44171ffd48b591d19256884a969fe4da17caryclark } 65655888e44171ffd48b591d19256884a969fe4da17caryclark if (!fHead || !this->release(fHead, test)) { 65755888e44171ffd48b591d19256884a969fe4da17caryclark SkAssertResult(this->release(fTop, test)); 65855888e44171ffd48b591d19256884a969fe4da17caryclark } 65955888e44171ffd48b591d19256884a969fe4da17caryclark } 66055888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* cs = coinSeg->existing(coinTs, oppSeg); 66155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* ce = coinSeg->existing(coinTe, oppSeg); 66281a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if (overlap && cs && ce && overlap->contains(cs, ce)) { 66381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 66481a478ca6c36aac3e53ce0373a281ac8940f4780caryclark } 66581a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(cs == ce && cs); 66655888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* os = oppSeg->existing(oppTs, coinSeg); 66755888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* oe = oppSeg->existing(oppTe, coinSeg); 66881a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if (overlap && os && oe && overlap->contains(os, oe)) { 66981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 67081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark } 67155888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(!cs || !cs->deleted()); 67255888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(!os || !os->deleted()); 67355888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(!ce || !ce->deleted()); 67455888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(!oe || !oe->deleted()); 67555888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* csExisting = !cs ? coinSeg->existing(coinTs, nullptr) : nullptr; 67655888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* ceExisting = !ce ? coinSeg->existing(coinTe, nullptr) : nullptr; 67781a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(csExisting && csExisting == ceExisting); 678e839e78443e48d4ccad89059b4bc4b3d894fcfddcaryclark// FAIL_IF(csExisting && (csExisting == ce || 679e839e78443e48d4ccad89059b4bc4b3d894fcfddcaryclark// csExisting->contains(ceExisting ? ceExisting : ce))); 68081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(ceExisting && (ceExisting == cs || 681025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark ceExisting->contains(csExisting ? csExisting : cs))); 68255888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* osExisting = !os ? oppSeg->existing(oppTs, nullptr) : nullptr; 68355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* oeExisting = !oe ? oppSeg->existing(oppTe, nullptr) : nullptr; 68481a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(osExisting && osExisting == oeExisting); 68581a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(osExisting && (osExisting == oe || 686025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark osExisting->contains(oeExisting ? oeExisting : oe))); 68781a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(oeExisting && (oeExisting == os || 688025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark oeExisting->contains(osExisting ? osExisting : os))); 68955888e44171ffd48b591d19256884a969fe4da17caryclark // extra line in debug code 69055888e44171ffd48b591d19256884a969fe4da17caryclark this->debugValidate(); 69155888e44171ffd48b591d19256884a969fe4da17caryclark if (!cs || !os) { 69255888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* csWritable = cs ? const_cast<SkOpPtT*>(cs) 69329b2563afb1677515739f1d24fb27733626eca92caryclark : coinSeg->addT(coinTs); 694e839e78443e48d4ccad89059b4bc4b3d894fcfddcaryclark if (csWritable == ce) { 695e839e78443e48d4ccad89059b4bc4b3d894fcfddcaryclark return true; 696e839e78443e48d4ccad89059b4bc4b3d894fcfddcaryclark } 69755888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* osWritable = os ? const_cast<SkOpPtT*>(os) 69829b2563afb1677515739f1d24fb27733626eca92caryclark : oppSeg->addT(oppTs); 69981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(!csWritable || !osWritable); 70030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark csWritable->span()->addOpp(osWritable->span()); 70155888e44171ffd48b591d19256884a969fe4da17caryclark cs = csWritable; 70230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark os = osWritable->active(); 70381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF((ce && ce->deleted()) || (oe && oe->deleted())); 70454359294a7c9dc54802d512a5d891a35c1663392caryclark } 70555888e44171ffd48b591d19256884a969fe4da17caryclark if (!ce || !oe) { 70655888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* ceWritable = ce ? const_cast<SkOpPtT*>(ce) 70729b2563afb1677515739f1d24fb27733626eca92caryclark : coinSeg->addT(coinTe); 70855888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* oeWritable = oe ? const_cast<SkOpPtT*>(oe) 70929b2563afb1677515739f1d24fb27733626eca92caryclark : oppSeg->addT(oppTe); 71030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark ceWritable->span()->addOpp(oeWritable->span()); 71155888e44171ffd48b591d19256884a969fe4da17caryclark ce = ceWritable; 71255888e44171ffd48b591d19256884a969fe4da17caryclark oe = oeWritable; 71354359294a7c9dc54802d512a5d891a35c1663392caryclark } 71455888e44171ffd48b591d19256884a969fe4da17caryclark this->debugValidate(); 71581a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(cs->deleted()); 71681a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(os->deleted()); 71781a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(ce->deleted()); 71881a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(oe->deleted()); 71981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(cs->contains(ce) || os->contains(oe)); 72055888e44171ffd48b591d19256884a969fe4da17caryclark bool result = true; 72155888e44171ffd48b591d19256884a969fe4da17caryclark if (overlap) { 72255888e44171ffd48b591d19256884a969fe4da17caryclark if (overlap->coinPtTStart()->segment() == coinSeg) { 72355888e44171ffd48b591d19256884a969fe4da17caryclark result = overlap->extend(cs, ce, os, oe); 72455888e44171ffd48b591d19256884a969fe4da17caryclark } else { 72555888e44171ffd48b591d19256884a969fe4da17caryclark if (os->fT > oe->fT) { 72655888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(cs, ce); 72755888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(os, oe); 72855888e44171ffd48b591d19256884a969fe4da17caryclark } 72955888e44171ffd48b591d19256884a969fe4da17caryclark result = overlap->extend(os, oe, cs, ce); 73055888e44171ffd48b591d19256884a969fe4da17caryclark } 73155888e44171ffd48b591d19256884a969fe4da17caryclark#if DEBUG_COINCIDENCE_VERBOSE 73255888e44171ffd48b591d19256884a969fe4da17caryclark if (result) { 73355888e44171ffd48b591d19256884a969fe4da17caryclark overlaps[0]->debugShow(); 73455888e44171ffd48b591d19256884a969fe4da17caryclark } 73555888e44171ffd48b591d19256884a969fe4da17caryclark#endif 73655888e44171ffd48b591d19256884a969fe4da17caryclark } else { 73755888e44171ffd48b591d19256884a969fe4da17caryclark this->add(cs, ce, os, oe); 73855888e44171ffd48b591d19256884a969fe4da17caryclark#if DEBUG_COINCIDENCE_VERBOSE 73955888e44171ffd48b591d19256884a969fe4da17caryclark fHead->debugShow(); 74055888e44171ffd48b591d19256884a969fe4da17caryclark#endif 74155888e44171ffd48b591d19256884a969fe4da17caryclark } 74255888e44171ffd48b591d19256884a969fe4da17caryclark this->debugValidate(); 74381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if (result) { 74481a478ca6c36aac3e53ce0373a281ac8940f4780caryclark *added = true; 74581a478ca6c36aac3e53ce0373a281ac8940f4780caryclark } 74681a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 74754359294a7c9dc54802d512a5d891a35c1663392caryclark} 74854359294a7c9dc54802d512a5d891a35c1663392caryclark 74955888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with debugAddMissing() 75027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark/* detects overlaps of different coincident runs on same segment */ 75127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark/* does not detect overlaps for pairs without any segments in common */ 75255888e44171ffd48b591d19256884a969fe4da17caryclark// returns true if caller should loop again 753ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clarkbool SkOpCoincidence::addMissing(bool* added DEBUG_COIN_DECLARE_PARAMS()) { 75427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkCoincidentSpans* outer = fHead; 75581a478ca6c36aac3e53ce0373a281ac8940f4780caryclark *added = false; 75654359294a7c9dc54802d512a5d891a35c1663392caryclark if (!outer) { 75781a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 75854359294a7c9dc54802d512a5d891a35c1663392caryclark } 75927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark fTop = outer; 76096fcdcc219d2a0d3579719b84b28bede76efba64halcanary fHead = nullptr; 76154359294a7c9dc54802d512a5d891a35c1663392caryclark do { 76227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark // addifmissing can modify the list that this is walking 76326ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark // save head so that walker can iterate over old data unperturbed 76426ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark // addifmissing adds to head freely then add saved head in the end 7658016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ocs = outer->coinPtTStart(); 766a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(ocs->deleted()); 7678016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpSegment* outerCoin = ocs->segment(); 7688016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(!outerCoin->done()); // if it's done, should have already been removed from list 7698016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* oos = outer->oppPtTStart(); 770b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark if (oos->deleted()) { 77181a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 772b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark } 7738016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpSegment* outerOpp = oos->segment(); 7748016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(!outerOpp->done()); 7758016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkOpSegment* outerCoinWritable = const_cast<SkOpSegment*>(outerCoin); 7768016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkOpSegment* outerOppWritable = const_cast<SkOpSegment*>(outerOpp); 77754359294a7c9dc54802d512a5d891a35c1663392caryclark SkCoincidentSpans* inner = outer; 77855888e44171ffd48b591d19256884a969fe4da17caryclark while ((inner = inner->next())) { 77955888e44171ffd48b591d19256884a969fe4da17caryclark this->debugValidate(); 78054359294a7c9dc54802d512a5d891a35c1663392caryclark double overS, overE; 7818016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ics = inner->coinPtTStart(); 782221a4bb55b51a6ba3882811990581d4bdb6bd539caryclark FAIL_IF(ics->deleted()); 7838016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpSegment* innerCoin = ics->segment(); 784a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(innerCoin->done()); 7858016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ios = inner->oppPtTStart(); 786a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(ios->deleted()); 7878016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpSegment* innerOpp = ios->segment(); 7888016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(!innerOpp->done()); 7898016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkOpSegment* innerCoinWritable = const_cast<SkOpSegment*>(innerCoin); 7908016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkOpSegment* innerOppWritable = const_cast<SkOpSegment*>(innerOpp); 79155888e44171ffd48b591d19256884a969fe4da17caryclark if (outerCoin == innerCoin) { 7928016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* oce = outer->coinPtTEnd(); 793b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark if (oce->deleted()) { 79481a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 795b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark } 7968016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ice = inner->coinPtTEnd(); 797595ac28c3990ea89ee40ec14117dc1667acfc126caryclark FAIL_IF(ice->deleted()); 7988016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (outerOpp != innerOpp && this->overlap(ocs, oce, ics, ice, &overS, &overE)) { 79981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark (void) this->addIfMissing(ocs->starter(oce), ics->starter(ice), 80081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark overS, overE, outerOppWritable, innerOppWritable, added 8018016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(ocs->debugEnder(oce)) 8028016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(ics->debugEnder(ice))); 80355888e44171ffd48b591d19256884a969fe4da17caryclark } 80455888e44171ffd48b591d19256884a969fe4da17caryclark } else if (outerCoin == innerOpp) { 8058016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* oce = outer->coinPtTEnd(); 8068016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(!oce->deleted()); 8078016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ioe = inner->oppPtTEnd(); 8088016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(!ioe->deleted()); 8098016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (outerOpp != innerCoin && this->overlap(ocs, oce, ios, ioe, &overS, &overE)) { 81081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark (void) this->addIfMissing(ocs->starter(oce), ios->starter(ioe), 81181a478ca6c36aac3e53ce0373a281ac8940f4780caryclark overS, overE, outerOppWritable, innerCoinWritable, added 8128016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(ocs->debugEnder(oce)) 8138016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(ios->debugEnder(ioe))); 81455888e44171ffd48b591d19256884a969fe4da17caryclark } 81555888e44171ffd48b591d19256884a969fe4da17caryclark } else if (outerOpp == innerCoin) { 8168016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ooe = outer->oppPtTEnd(); 8178016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(!ooe->deleted()); 8188016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ice = inner->coinPtTEnd(); 8198016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(!ice->deleted()); 82055888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(outerCoin != innerOpp); 8218016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (this->overlap(oos, ooe, ics, ice, &overS, &overE)) { 82281a478ca6c36aac3e53ce0373a281ac8940f4780caryclark (void) this->addIfMissing(oos->starter(ooe), ics->starter(ice), 82381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark overS, overE, outerCoinWritable, innerOppWritable, added 8248016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(oos->debugEnder(ooe)) 8258016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(ics->debugEnder(ice))); 82655888e44171ffd48b591d19256884a969fe4da17caryclark } 82755888e44171ffd48b591d19256884a969fe4da17caryclark } else if (outerOpp == innerOpp) { 8288016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ooe = outer->oppPtTEnd(); 8298016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(!ooe->deleted()); 8308016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ioe = inner->oppPtTEnd(); 831b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark if (ioe->deleted()) { 83281a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 833b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark } 83455888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(outerCoin != innerCoin); 8358016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (this->overlap(oos, ooe, ios, ioe, &overS, &overE)) { 83681a478ca6c36aac3e53ce0373a281ac8940f4780caryclark (void) this->addIfMissing(oos->starter(ooe), ios->starter(ioe), 83781a478ca6c36aac3e53ce0373a281ac8940f4780caryclark overS, overE, outerCoinWritable, innerCoinWritable, added 8388016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(oos->debugEnder(ooe)) 8398016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(ios->debugEnder(ioe))); 84054359294a7c9dc54802d512a5d891a35c1663392caryclark } 84154359294a7c9dc54802d512a5d891a35c1663392caryclark } 84255888e44171ffd48b591d19256884a969fe4da17caryclark this->debugValidate(); 84354359294a7c9dc54802d512a5d891a35c1663392caryclark } 84455888e44171ffd48b591d19256884a969fe4da17caryclark } while ((outer = outer->next())); 84555888e44171ffd48b591d19256884a969fe4da17caryclark this->restoreHead(); 84681a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 84727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 84827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 84955888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::addOverlap(const SkOpSegment* seg1, const SkOpSegment* seg1o, 85055888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* seg2, const SkOpSegment* seg2o, 85155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* overS, const SkOpPtT* overE) { 852e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark const SkOpPtT* s1 = overS->find(seg1); 853e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark const SkOpPtT* e1 = overE->find(seg1); 854087140153861f4c2a003ce6b22a612acc9cc3cf9caryclark FAIL_IF(!s1); 85540f23780e7ca36818660add0faf783fda81bf0b1Cary Clark FAIL_IF(!e1); 85627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (!s1->starter(e1)->span()->upCast()->windValue()) { 857e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark s1 = overS->find(seg1o); 858e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark e1 = overE->find(seg1o); 859221a4bb55b51a6ba3882811990581d4bdb6bd539caryclark FAIL_IF(!s1); 86040f23780e7ca36818660add0faf783fda81bf0b1Cary Clark FAIL_IF(!e1); 86127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (!s1->starter(e1)->span()->upCast()->windValue()) { 8623f0753d3eccece8ac7f02f6af36d66a96c3dfb26caryclark return true; 86327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 86427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 865e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark const SkOpPtT* s2 = overS->find(seg2); 866e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark const SkOpPtT* e2 = overE->find(seg2); 867826167111f80a4251266812cf720ad712bd29446caryclark FAIL_IF(!s2); 868a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(!e2); 86927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (!s2->starter(e2)->span()->upCast()->windValue()) { 870e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark s2 = overS->find(seg2o); 871e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark e2 = overE->find(seg2o); 872a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(!s2); 87378a37a53365c24670b050acf993818c435922745caryclark FAIL_IF(!e2); 87427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (!s2->starter(e2)->span()->upCast()->windValue()) { 8753f0753d3eccece8ac7f02f6af36d66a96c3dfb26caryclark return true; 87627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 87727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 87827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (s1->segment() == s2->segment()) { 8793f0753d3eccece8ac7f02f6af36d66a96c3dfb26caryclark return true; 88027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 88127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (s1->fT > e1->fT) { 88227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkTSwap(s1, e1); 88327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkTSwap(s2, e2); 88427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 88555888e44171ffd48b591d19256884a969fe4da17caryclark this->add(s1, e1, s2, e2); 8863f0753d3eccece8ac7f02f6af36d66a96c3dfb26caryclark return true; 88754359294a7c9dc54802d512a5d891a35c1663392caryclark} 88854359294a7c9dc54802d512a5d891a35c1663392caryclark 88955888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::contains(const SkOpSegment* seg, const SkOpSegment* opp, double oppT) const { 89055888e44171ffd48b591d19256884a969fe4da17caryclark if (this->contains(fHead, seg, opp, oppT)) { 89155888e44171ffd48b591d19256884a969fe4da17caryclark return true; 89255888e44171ffd48b591d19256884a969fe4da17caryclark } 89355888e44171ffd48b591d19256884a969fe4da17caryclark if (this->contains(fTop, seg, opp, oppT)) { 89455888e44171ffd48b591d19256884a969fe4da17caryclark return true; 89555888e44171ffd48b591d19256884a969fe4da17caryclark } 89655888e44171ffd48b591d19256884a969fe4da17caryclark return false; 89755888e44171ffd48b591d19256884a969fe4da17caryclark} 89855888e44171ffd48b591d19256884a969fe4da17caryclark 89955888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::contains(const SkCoincidentSpans* coin, const SkOpSegment* seg, 90055888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* opp, double oppT) const { 90155888e44171ffd48b591d19256884a969fe4da17caryclark if (!coin) { 90255888e44171ffd48b591d19256884a969fe4da17caryclark return false; 90355888e44171ffd48b591d19256884a969fe4da17caryclark } 90455888e44171ffd48b591d19256884a969fe4da17caryclark do { 90555888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->coinPtTStart()->segment() == seg && coin->oppPtTStart()->segment() == opp 90655888e44171ffd48b591d19256884a969fe4da17caryclark && between(coin->oppPtTStart()->fT, oppT, coin->oppPtTEnd()->fT)) { 90754359294a7c9dc54802d512a5d891a35c1663392caryclark return true; 90854359294a7c9dc54802d512a5d891a35c1663392caryclark } 90955888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->oppPtTStart()->segment() == seg && coin->coinPtTStart()->segment() == opp 91055888e44171ffd48b591d19256884a969fe4da17caryclark && between(coin->coinPtTStart()->fT, oppT, coin->coinPtTEnd()->fT)) { 91155888e44171ffd48b591d19256884a969fe4da17caryclark return true; 91255888e44171ffd48b591d19256884a969fe4da17caryclark } 91355888e44171ffd48b591d19256884a969fe4da17caryclark } while ((coin = coin->next())); 91455888e44171ffd48b591d19256884a969fe4da17caryclark return false; 91555888e44171ffd48b591d19256884a969fe4da17caryclark} 91655888e44171ffd48b591d19256884a969fe4da17caryclark 91755888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::contains(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, 91855888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) const { 91955888e44171ffd48b591d19256884a969fe4da17caryclark const SkCoincidentSpans* test = fHead; 92055888e44171ffd48b591d19256884a969fe4da17caryclark if (!test) { 92155888e44171ffd48b591d19256884a969fe4da17caryclark return false; 92255888e44171ffd48b591d19256884a969fe4da17caryclark } 92355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* coinSeg = coinPtTStart->segment(); 92455888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* oppSeg = oppPtTStart->segment(); 92555888e44171ffd48b591d19256884a969fe4da17caryclark if (!Ordered(coinPtTStart, oppPtTStart)) { 92655888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinSeg, oppSeg); 92755888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinPtTStart, oppPtTStart); 92855888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinPtTEnd, oppPtTEnd); 92955888e44171ffd48b591d19256884a969fe4da17caryclark if (coinPtTStart->fT > coinPtTEnd->fT) { 93055888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinPtTStart, coinPtTEnd); 93155888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(oppPtTStart, oppPtTEnd); 93255888e44171ffd48b591d19256884a969fe4da17caryclark } 93355888e44171ffd48b591d19256884a969fe4da17caryclark } 93455888e44171ffd48b591d19256884a969fe4da17caryclark double oppMinT = SkTMin(oppPtTStart->fT, oppPtTEnd->fT); 93555888e44171ffd48b591d19256884a969fe4da17caryclark double oppMaxT = SkTMax(oppPtTStart->fT, oppPtTEnd->fT); 93655888e44171ffd48b591d19256884a969fe4da17caryclark do { 93755888e44171ffd48b591d19256884a969fe4da17caryclark if (coinSeg != test->coinPtTStart()->segment()) { 93855888e44171ffd48b591d19256884a969fe4da17caryclark continue; 93955888e44171ffd48b591d19256884a969fe4da17caryclark } 94055888e44171ffd48b591d19256884a969fe4da17caryclark if (coinPtTStart->fT < test->coinPtTStart()->fT) { 94155888e44171ffd48b591d19256884a969fe4da17caryclark continue; 94255888e44171ffd48b591d19256884a969fe4da17caryclark } 94355888e44171ffd48b591d19256884a969fe4da17caryclark if (coinPtTEnd->fT > test->coinPtTEnd()->fT) { 94455888e44171ffd48b591d19256884a969fe4da17caryclark continue; 94555888e44171ffd48b591d19256884a969fe4da17caryclark } 94655888e44171ffd48b591d19256884a969fe4da17caryclark if (oppSeg != test->oppPtTStart()->segment()) { 94755888e44171ffd48b591d19256884a969fe4da17caryclark continue; 94855888e44171ffd48b591d19256884a969fe4da17caryclark } 94955888e44171ffd48b591d19256884a969fe4da17caryclark if (oppMinT < SkTMin(test->oppPtTStart()->fT, test->oppPtTEnd()->fT)) { 95055888e44171ffd48b591d19256884a969fe4da17caryclark continue; 95155888e44171ffd48b591d19256884a969fe4da17caryclark } 95255888e44171ffd48b591d19256884a969fe4da17caryclark if (oppMaxT > SkTMax(test->oppPtTStart()->fT, test->oppPtTEnd()->fT)) { 95355888e44171ffd48b591d19256884a969fe4da17caryclark continue; 95455888e44171ffd48b591d19256884a969fe4da17caryclark } 95555888e44171ffd48b591d19256884a969fe4da17caryclark return true; 95655888e44171ffd48b591d19256884a969fe4da17caryclark } while ((test = test->next())); 95754359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 95854359294a7c9dc54802d512a5d891a35c1663392caryclark} 95954359294a7c9dc54802d512a5d891a35c1663392caryclark 960ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clarkvoid SkOpCoincidence::correctEnds(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 961ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark DEBUG_SET_PHASE(); 96255888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* coin = fHead; 96355888e44171ffd48b591d19256884a969fe4da17caryclark if (!coin) { 96455888e44171ffd48b591d19256884a969fe4da17caryclark return; 96555888e44171ffd48b591d19256884a969fe4da17caryclark } 96655888e44171ffd48b591d19256884a969fe4da17caryclark do { 96755888e44171ffd48b591d19256884a969fe4da17caryclark coin->correctEnds(); 96855888e44171ffd48b591d19256884a969fe4da17caryclark } while ((coin = coin->next())); 96955888e44171ffd48b591d19256884a969fe4da17caryclark} 97055888e44171ffd48b591d19256884a969fe4da17caryclark 97154359294a7c9dc54802d512a5d891a35c1663392caryclark// walk span sets in parallel, moving winding from one to the other 972a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclarkbool SkOpCoincidence::apply(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 973ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark DEBUG_SET_PHASE(); 97454359294a7c9dc54802d512a5d891a35c1663392caryclark SkCoincidentSpans* coin = fHead; 97554359294a7c9dc54802d512a5d891a35c1663392caryclark if (!coin) { 976a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark return true; 97754359294a7c9dc54802d512a5d891a35c1663392caryclark } 97854359294a7c9dc54802d512a5d891a35c1663392caryclark do { 97955888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpan* start = coin->coinPtTStartWritable()->span()->upCast(); 980182b499cd75c971f85cdf52c1827b3c220cc9011caryclark if (start->deleted()) { 981182b499cd75c971f85cdf52c1827b3c220cc9011caryclark continue; 982182b499cd75c971f85cdf52c1827b3c220cc9011caryclark } 98355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* end = coin->coinPtTEnd()->span(); 98454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start == start->starter(end)); 98555888e44171ffd48b591d19256884a969fe4da17caryclark bool flipped = coin->flipped(); 98696dc1c9efaab4636e30f90aa377f25863f9bf3bacaryclark SkOpSpanBase* oStartBase = (flipped ? coin->oppPtTEndWritable() 98796dc1c9efaab4636e30f90aa377f25863f9bf3bacaryclark : coin->oppPtTStartWritable())->span(); 98896dc1c9efaab4636e30f90aa377f25863f9bf3bacaryclark FAIL_IF(!oStartBase->upCastable()); 98996dc1c9efaab4636e30f90aa377f25863f9bf3bacaryclark SkOpSpan* oStart = oStartBase->upCast(); 990182b499cd75c971f85cdf52c1827b3c220cc9011caryclark if (oStart->deleted()) { 991182b499cd75c971f85cdf52c1827b3c220cc9011caryclark continue; 992182b499cd75c971f85cdf52c1827b3c220cc9011caryclark } 99355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* oEnd = (flipped ? coin->oppPtTStart() : coin->oppPtTEnd())->span(); 99454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(oStart == oStart->starter(oEnd)); 99554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* segment = start->segment(); 99654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* oSegment = oStart->segment(); 99754359294a7c9dc54802d512a5d891a35c1663392caryclark bool operandSwap = segment->operand() != oSegment->operand(); 99854359294a7c9dc54802d512a5d891a35c1663392caryclark if (flipped) { 999364a0074c33f91ded60232f173f7a57a312e9280caryclark if (oEnd->deleted()) { 1000364a0074c33f91ded60232f173f7a57a312e9280caryclark continue; 1001364a0074c33f91ded60232f173f7a57a312e9280caryclark } 100254359294a7c9dc54802d512a5d891a35c1663392caryclark do { 100354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* oNext = oStart->next(); 100454359294a7c9dc54802d512a5d891a35c1663392caryclark if (oNext == oEnd) { 100554359294a7c9dc54802d512a5d891a35c1663392caryclark break; 100654359294a7c9dc54802d512a5d891a35c1663392caryclark } 100754359294a7c9dc54802d512a5d891a35c1663392caryclark oStart = oNext->upCast(); 100854359294a7c9dc54802d512a5d891a35c1663392caryclark } while (true); 100954359294a7c9dc54802d512a5d891a35c1663392caryclark } 101054359294a7c9dc54802d512a5d891a35c1663392caryclark do { 101154359294a7c9dc54802d512a5d891a35c1663392caryclark int windValue = start->windValue(); 101254359294a7c9dc54802d512a5d891a35c1663392caryclark int oppValue = start->oppValue(); 10131049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int oWindValue = oStart->windValue(); 101454359294a7c9dc54802d512a5d891a35c1663392caryclark int oOppValue = oStart->oppValue(); 101554359294a7c9dc54802d512a5d891a35c1663392caryclark // winding values are added or subtracted depending on direction and wind type 101654359294a7c9dc54802d512a5d891a35c1663392caryclark // same or opposite values are summed depending on the operand value 10171049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int windDiff = operandSwap ? oOppValue : oWindValue; 10181049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int oWindDiff = operandSwap ? oppValue : windValue; 10191049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (!flipped) { 10201049f1246e7be4ccb68001361efceb8933e6f81ccaryclark windDiff = -windDiff; 10211049f1246e7be4ccb68001361efceb8933e6f81ccaryclark oWindDiff = -oWindDiff; 10221049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 102355888e44171ffd48b591d19256884a969fe4da17caryclark bool addToStart = windValue && (windValue > windDiff || (windValue == windDiff 102455888e44171ffd48b591d19256884a969fe4da17caryclark && oWindValue <= oWindDiff)); 102555888e44171ffd48b591d19256884a969fe4da17caryclark if (addToStart ? start->done() : oStart->done()) { 102655888e44171ffd48b591d19256884a969fe4da17caryclark addToStart ^= true; 102755888e44171ffd48b591d19256884a969fe4da17caryclark } 102855888e44171ffd48b591d19256884a969fe4da17caryclark if (addToStart) { 102954359294a7c9dc54802d512a5d891a35c1663392caryclark if (operandSwap) { 103054359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(oWindValue, oOppValue); 103154359294a7c9dc54802d512a5d891a35c1663392caryclark } 103254359294a7c9dc54802d512a5d891a35c1663392caryclark if (flipped) { 103354359294a7c9dc54802d512a5d891a35c1663392caryclark windValue -= oWindValue; 103454359294a7c9dc54802d512a5d891a35c1663392caryclark oppValue -= oOppValue; 103554359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 103654359294a7c9dc54802d512a5d891a35c1663392caryclark windValue += oWindValue; 103754359294a7c9dc54802d512a5d891a35c1663392caryclark oppValue += oOppValue; 103854359294a7c9dc54802d512a5d891a35c1663392caryclark } 10391049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (segment->isXor()) { 104054359294a7c9dc54802d512a5d891a35c1663392caryclark windValue &= 1; 104154359294a7c9dc54802d512a5d891a35c1663392caryclark } 10421049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (segment->oppXor()) { 104354359294a7c9dc54802d512a5d891a35c1663392caryclark oppValue &= 1; 104454359294a7c9dc54802d512a5d891a35c1663392caryclark } 104554359294a7c9dc54802d512a5d891a35c1663392caryclark oWindValue = oOppValue = 0; 104654359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 104754359294a7c9dc54802d512a5d891a35c1663392caryclark if (operandSwap) { 104854359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(windValue, oppValue); 104954359294a7c9dc54802d512a5d891a35c1663392caryclark } 105054359294a7c9dc54802d512a5d891a35c1663392caryclark if (flipped) { 105154359294a7c9dc54802d512a5d891a35c1663392caryclark oWindValue -= windValue; 105254359294a7c9dc54802d512a5d891a35c1663392caryclark oOppValue -= oppValue; 105354359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 105454359294a7c9dc54802d512a5d891a35c1663392caryclark oWindValue += windValue; 105554359294a7c9dc54802d512a5d891a35c1663392caryclark oOppValue += oppValue; 105654359294a7c9dc54802d512a5d891a35c1663392caryclark } 10571049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (oSegment->isXor()) { 105854359294a7c9dc54802d512a5d891a35c1663392caryclark oWindValue &= 1; 105954359294a7c9dc54802d512a5d891a35c1663392caryclark } 10601049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (oSegment->oppXor()) { 10611049f1246e7be4ccb68001361efceb8933e6f81ccaryclark oOppValue &= 1; 10621049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 106354359294a7c9dc54802d512a5d891a35c1663392caryclark windValue = oppValue = 0; 106454359294a7c9dc54802d512a5d891a35c1663392caryclark } 10656c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark#if 0 && DEBUG_COINCIDENCE 106655888e44171ffd48b591d19256884a969fe4da17caryclark SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", segment->debugID(), 106755888e44171ffd48b591d19256884a969fe4da17caryclark start->debugID(), windValue, oppValue); 106855888e44171ffd48b591d19256884a969fe4da17caryclark SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", oSegment->debugID(), 106955888e44171ffd48b591d19256884a969fe4da17caryclark oStart->debugID(), oWindValue, oOppValue); 107055888e44171ffd48b591d19256884a969fe4da17caryclark#endif 107154359294a7c9dc54802d512a5d891a35c1663392caryclark start->setWindValue(windValue); 107254359294a7c9dc54802d512a5d891a35c1663392caryclark start->setOppValue(oppValue); 1073a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(oWindValue == -1); 107454359294a7c9dc54802d512a5d891a35c1663392caryclark oStart->setWindValue(oWindValue); 107554359294a7c9dc54802d512a5d891a35c1663392caryclark oStart->setOppValue(oOppValue); 107654359294a7c9dc54802d512a5d891a35c1663392caryclark if (!windValue && !oppValue) { 107754359294a7c9dc54802d512a5d891a35c1663392caryclark segment->markDone(start); 107854359294a7c9dc54802d512a5d891a35c1663392caryclark } 107954359294a7c9dc54802d512a5d891a35c1663392caryclark if (!oWindValue && !oOppValue) { 108054359294a7c9dc54802d512a5d891a35c1663392caryclark oSegment->markDone(oStart); 108154359294a7c9dc54802d512a5d891a35c1663392caryclark } 108254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* next = start->next(); 108354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* oNext = flipped ? oStart->prev() : oStart->next(); 108454359294a7c9dc54802d512a5d891a35c1663392caryclark if (next == end) { 108554359294a7c9dc54802d512a5d891a35c1663392caryclark break; 108654359294a7c9dc54802d512a5d891a35c1663392caryclark } 108796dc1c9efaab4636e30f90aa377f25863f9bf3bacaryclark FAIL_IF(!next->upCastable()); 108854359294a7c9dc54802d512a5d891a35c1663392caryclark start = next->upCast(); 10891049f1246e7be4ccb68001361efceb8933e6f81ccaryclark // if the opposite ran out too soon, just reuse the last span 10901049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (!oNext || !oNext->upCastable()) { 10911049f1246e7be4ccb68001361efceb8933e6f81ccaryclark oNext = oStart; 109254359294a7c9dc54802d512a5d891a35c1663392caryclark } 109354359294a7c9dc54802d512a5d891a35c1663392caryclark oStart = oNext->upCast(); 109454359294a7c9dc54802d512a5d891a35c1663392caryclark } while (true); 109555888e44171ffd48b591d19256884a969fe4da17caryclark } while ((coin = coin->next())); 1096a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark return true; 109754359294a7c9dc54802d512a5d891a35c1663392caryclark} 109854359294a7c9dc54802d512a5d891a35c1663392caryclark 109955888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with debugRelease() 110055888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::release(SkCoincidentSpans* coin, SkCoincidentSpans* remove) { 110155888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* head = coin; 110296fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkCoincidentSpans* prev = nullptr; 110354359294a7c9dc54802d512a5d891a35c1663392caryclark SkCoincidentSpans* next; 110454359294a7c9dc54802d512a5d891a35c1663392caryclark do { 110555888e44171ffd48b591d19256884a969fe4da17caryclark next = coin->next(); 110654359294a7c9dc54802d512a5d891a35c1663392caryclark if (coin == remove) { 110754359294a7c9dc54802d512a5d891a35c1663392caryclark if (prev) { 110855888e44171ffd48b591d19256884a969fe4da17caryclark prev->setNext(next); 110955888e44171ffd48b591d19256884a969fe4da17caryclark } else if (head == fHead) { 111054359294a7c9dc54802d512a5d891a35c1663392caryclark fHead = next; 111155888e44171ffd48b591d19256884a969fe4da17caryclark } else { 111255888e44171ffd48b591d19256884a969fe4da17caryclark fTop = next; 111354359294a7c9dc54802d512a5d891a35c1663392caryclark } 111454359294a7c9dc54802d512a5d891a35c1663392caryclark break; 111554359294a7c9dc54802d512a5d891a35c1663392caryclark } 111654359294a7c9dc54802d512a5d891a35c1663392caryclark prev = coin; 111754359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((coin = next)); 111855888e44171ffd48b591d19256884a969fe4da17caryclark return coin != nullptr; 111955888e44171ffd48b591d19256884a969fe4da17caryclark} 112055888e44171ffd48b591d19256884a969fe4da17caryclark 112130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclarkvoid SkOpCoincidence::releaseDeleted(SkCoincidentSpans* coin) { 112230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (!coin) { 112330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark return; 112430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 112530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkCoincidentSpans* head = coin; 112630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkCoincidentSpans* prev = nullptr; 112730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkCoincidentSpans* next; 112830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark do { 112930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark next = coin->next(); 113030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (coin->coinPtTStart()->deleted()) { 113130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOPASSERT(coin->flipped() ? coin->oppPtTEnd()->deleted() : 113230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark coin->oppPtTStart()->deleted()); 113330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (prev) { 113430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark prev->setNext(next); 113530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } else if (head == fHead) { 113630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark fHead = next; 113730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } else { 113830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark fTop = next; 113930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 114030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } else { 114130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOPASSERT(coin->flipped() ? !coin->oppPtTEnd()->deleted() : 114230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark !coin->oppPtTStart()->deleted()); 114330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark prev = coin; 114430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 114530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } while ((coin = next)); 114630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark} 114730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark 114830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclarkvoid SkOpCoincidence::releaseDeleted() { 114930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark this->releaseDeleted(fHead); 115030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark this->releaseDeleted(fTop); 115130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark} 115230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark 115355888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpCoincidence::restoreHead() { 115455888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans** headPtr = &fHead; 115555888e44171ffd48b591d19256884a969fe4da17caryclark while (*headPtr) { 115655888e44171ffd48b591d19256884a969fe4da17caryclark headPtr = (*headPtr)->nextPtr(); 115755888e44171ffd48b591d19256884a969fe4da17caryclark } 115855888e44171ffd48b591d19256884a969fe4da17caryclark *headPtr = fTop; 115955888e44171ffd48b591d19256884a969fe4da17caryclark fTop = nullptr; 116055888e44171ffd48b591d19256884a969fe4da17caryclark // segments may have collapsed in the meantime; remove empty referenced segments 116155888e44171ffd48b591d19256884a969fe4da17caryclark headPtr = &fHead; 116255888e44171ffd48b591d19256884a969fe4da17caryclark while (*headPtr) { 116355888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* test = *headPtr; 116455888e44171ffd48b591d19256884a969fe4da17caryclark if (test->coinPtTStart()->segment()->done() || test->oppPtTStart()->segment()->done()) { 116555888e44171ffd48b591d19256884a969fe4da17caryclark *headPtr = test->next(); 116655888e44171ffd48b591d19256884a969fe4da17caryclark continue; 116755888e44171ffd48b591d19256884a969fe4da17caryclark } 116855888e44171ffd48b591d19256884a969fe4da17caryclark headPtr = (*headPtr)->nextPtr(); 116955888e44171ffd48b591d19256884a969fe4da17caryclark } 117055888e44171ffd48b591d19256884a969fe4da17caryclark} 117155888e44171ffd48b591d19256884a969fe4da17caryclark 117255888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with debugExpand() 117330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark// expand the range by checking adjacent spans for coincidence 1174ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clarkbool SkOpCoincidence::expand(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 1175ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark DEBUG_SET_PHASE(); 117654359294a7c9dc54802d512a5d891a35c1663392caryclark SkCoincidentSpans* coin = fHead; 117754359294a7c9dc54802d512a5d891a35c1663392caryclark if (!coin) { 117827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark return false; 117954359294a7c9dc54802d512a5d891a35c1663392caryclark } 118027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark bool expanded = false; 118154359294a7c9dc54802d512a5d891a35c1663392caryclark do { 118255888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->expand()) { 118355888e44171ffd48b591d19256884a969fe4da17caryclark // check to see if multiple spans expanded so they are now identical 118455888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* test = fHead; 118555888e44171ffd48b591d19256884a969fe4da17caryclark do { 118655888e44171ffd48b591d19256884a969fe4da17caryclark if (coin == test) { 118755888e44171ffd48b591d19256884a969fe4da17caryclark continue; 118855888e44171ffd48b591d19256884a969fe4da17caryclark } 118955888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->coinPtTStart() == test->coinPtTStart() 119055888e44171ffd48b591d19256884a969fe4da17caryclark && coin->oppPtTStart() == test->oppPtTStart()) { 119155888e44171ffd48b591d19256884a969fe4da17caryclark this->release(fHead, test); 119255888e44171ffd48b591d19256884a969fe4da17caryclark break; 119355888e44171ffd48b591d19256884a969fe4da17caryclark } 119455888e44171ffd48b591d19256884a969fe4da17caryclark } while ((test = test->next())); 119555888e44171ffd48b591d19256884a969fe4da17caryclark expanded = true; 119627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 119755888e44171ffd48b591d19256884a969fe4da17caryclark } while ((coin = coin->next())); 119827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark return expanded; 119927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 120027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 120140f23780e7ca36818660add0faf783fda81bf0b1Cary Clarkbool SkOpCoincidence::findOverlaps(SkOpCoincidence* overlaps DEBUG_COIN_DECLARE_PARAMS()) const { 1202ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark DEBUG_SET_PHASE(); 120396fcdcc219d2a0d3579719b84b28bede76efba64halcanary overlaps->fHead = overlaps->fTop = nullptr; 120427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkCoincidentSpans* outer = fHead; 120527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark while (outer) { 120655888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* outerCoin = outer->coinPtTStart()->segment(); 120755888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* outerOpp = outer->oppPtTStart()->segment(); 120827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkCoincidentSpans* inner = outer; 120955888e44171ffd48b591d19256884a969fe4da17caryclark while ((inner = inner->next())) { 121055888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* innerCoin = inner->coinPtTStart()->segment(); 121127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (outerCoin == innerCoin) { 121227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark continue; // both winners are the same segment, so there's no additional overlap 121354359294a7c9dc54802d512a5d891a35c1663392caryclark } 121455888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* innerOpp = inner->oppPtTStart()->segment(); 121555888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* overlapS; 121655888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* overlapE; 121755888e44171ffd48b591d19256884a969fe4da17caryclark if ((outerOpp == innerCoin && SkOpPtT::Overlaps(outer->oppPtTStart(), 121855888e44171ffd48b591d19256884a969fe4da17caryclark outer->oppPtTEnd(),inner->coinPtTStart(), inner->coinPtTEnd(), &overlapS, 121955888e44171ffd48b591d19256884a969fe4da17caryclark &overlapE)) 122055888e44171ffd48b591d19256884a969fe4da17caryclark || (outerCoin == innerOpp && SkOpPtT::Overlaps(outer->coinPtTStart(), 122155888e44171ffd48b591d19256884a969fe4da17caryclark outer->coinPtTEnd(), inner->oppPtTStart(), inner->oppPtTEnd(), 122227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark &overlapS, &overlapE)) 122355888e44171ffd48b591d19256884a969fe4da17caryclark || (outerOpp == innerOpp && SkOpPtT::Overlaps(outer->oppPtTStart(), 122455888e44171ffd48b591d19256884a969fe4da17caryclark outer->oppPtTEnd(), inner->oppPtTStart(), inner->oppPtTEnd(), 122527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark &overlapS, &overlapE))) { 122640f23780e7ca36818660add0faf783fda81bf0b1Cary Clark if (!overlaps->addOverlap(outerCoin, outerOpp, innerCoin, innerOpp, 122740f23780e7ca36818660add0faf783fda81bf0b1Cary Clark overlapS, overlapE)) { 122840f23780e7ca36818660add0faf783fda81bf0b1Cary Clark return false; 122940f23780e7ca36818660add0faf783fda81bf0b1Cary Clark } 1230e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark } 123127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 123255888e44171ffd48b591d19256884a969fe4da17caryclark outer = outer->next(); 123327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 123440f23780e7ca36818660add0faf783fda81bf0b1Cary Clark return true; 123527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 123627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 123755888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpCoincidence::fixUp(SkOpPtT* deleted, const SkOpPtT* kept) { 1238b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark SkOPASSERT(deleted != kept); 123955888e44171ffd48b591d19256884a969fe4da17caryclark if (fHead) { 124055888e44171ffd48b591d19256884a969fe4da17caryclark this->fixUp(fHead, deleted, kept); 124155888e44171ffd48b591d19256884a969fe4da17caryclark } 124255888e44171ffd48b591d19256884a969fe4da17caryclark if (fTop) { 124355888e44171ffd48b591d19256884a969fe4da17caryclark this->fixUp(fTop, deleted, kept); 124454359294a7c9dc54802d512a5d891a35c1663392caryclark } 124555888e44171ffd48b591d19256884a969fe4da17caryclark} 124655888e44171ffd48b591d19256884a969fe4da17caryclark 124755888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpCoincidence::fixUp(SkCoincidentSpans* coin, SkOpPtT* deleted, const SkOpPtT* kept) { 124855888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* head = coin; 124954359294a7c9dc54802d512a5d891a35c1663392caryclark do { 125055888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->coinPtTStart() == deleted) { 125155888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->coinPtTEnd()->span() == kept->span()) { 125255888e44171ffd48b591d19256884a969fe4da17caryclark this->release(head, coin); 125327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark continue; 125454359294a7c9dc54802d512a5d891a35c1663392caryclark } 125555888e44171ffd48b591d19256884a969fe4da17caryclark coin->setCoinPtTStart(kept); 125654359294a7c9dc54802d512a5d891a35c1663392caryclark } 125755888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->coinPtTEnd() == deleted) { 125855888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->coinPtTStart()->span() == kept->span()) { 125955888e44171ffd48b591d19256884a969fe4da17caryclark this->release(head, coin); 126027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark continue; 126154359294a7c9dc54802d512a5d891a35c1663392caryclark } 126255888e44171ffd48b591d19256884a969fe4da17caryclark coin->setCoinPtTEnd(kept); 126355888e44171ffd48b591d19256884a969fe4da17caryclark } 126455888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->oppPtTStart() == deleted) { 126555888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->oppPtTEnd()->span() == kept->span()) { 126655888e44171ffd48b591d19256884a969fe4da17caryclark this->release(head, coin); 126727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark continue; 126854359294a7c9dc54802d512a5d891a35c1663392caryclark } 126955888e44171ffd48b591d19256884a969fe4da17caryclark coin->setOppPtTStart(kept); 127054359294a7c9dc54802d512a5d891a35c1663392caryclark } 127155888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->oppPtTEnd() == deleted) { 127255888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->oppPtTStart()->span() == kept->span()) { 127355888e44171ffd48b591d19256884a969fe4da17caryclark this->release(head, coin); 127427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark continue; 127554359294a7c9dc54802d512a5d891a35c1663392caryclark } 127655888e44171ffd48b591d19256884a969fe4da17caryclark coin->setOppPtTEnd(kept); 127754359294a7c9dc54802d512a5d891a35c1663392caryclark } 127855888e44171ffd48b591d19256884a969fe4da17caryclark } while ((coin = coin->next())); 127954359294a7c9dc54802d512a5d891a35c1663392caryclark} 128054359294a7c9dc54802d512a5d891a35c1663392caryclark 128155888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with debugMark() 128227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark/* this sets up the coincidence links in the segments when the coincidence crosses multiple spans */ 1283e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclarkbool SkOpCoincidence::mark(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 1284ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark DEBUG_SET_PHASE(); 128554359294a7c9dc54802d512a5d891a35c1663392caryclark SkCoincidentSpans* coin = fHead; 128654359294a7c9dc54802d512a5d891a35c1663392caryclark if (!coin) { 1287e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclark return true; 128854359294a7c9dc54802d512a5d891a35c1663392caryclark } 128954359294a7c9dc54802d512a5d891a35c1663392caryclark do { 1290e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclark SkOpSpanBase* startBase = coin->coinPtTStartWritable()->span(); 1291e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclark FAIL_IF(!startBase->upCastable()); 1292e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclark SkOpSpan* start = startBase->upCast(); 1293a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(start->deleted()); 129455888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpanBase* end = coin->coinPtTEndWritable()->span(); 129540f23780e7ca36818660add0faf783fda81bf0b1Cary Clark SkOPASSERT(!end->deleted()); 129655888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpanBase* oStart = coin->oppPtTStartWritable()->span(); 129740f23780e7ca36818660add0faf783fda81bf0b1Cary Clark SkOPASSERT(!oStart->deleted()); 129855888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpanBase* oEnd = coin->oppPtTEndWritable()->span(); 129955888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(!oEnd->deleted()); 130055888e44171ffd48b591d19256884a969fe4da17caryclark bool flipped = coin->flipped(); 130154359294a7c9dc54802d512a5d891a35c1663392caryclark if (flipped) { 130254359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(oStart, oEnd); 130354359294a7c9dc54802d512a5d891a35c1663392caryclark } 130455888e44171ffd48b591d19256884a969fe4da17caryclark /* coin and opp spans may not match up. Mark the ends, and then let the interior 130555888e44171ffd48b591d19256884a969fe4da17caryclark get marked as many times as the spans allow */ 13069de097639f04e5a18da2d2b123dace9d24ab50e4Cary Clark FAIL_IF(!oStart->upCastable()); 130755888e44171ffd48b591d19256884a969fe4da17caryclark start->insertCoincidence(oStart->upCast()); 130855888e44171ffd48b591d19256884a969fe4da17caryclark end->insertCoinEnd(oEnd); 130955888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* segment = start->segment(); 131055888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* oSegment = oStart->segment(); 131154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* next = start; 131254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* oNext = oStart; 1313a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark bool ordered; 1314a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(!coin->ordered(&ordered)); 131555888e44171ffd48b591d19256884a969fe4da17caryclark while ((next = next->upCast()->next()) != end) { 1316e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclark FAIL_IF(!next->upCastable()); 1317e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark SkAssertResult(next->upCast()->insertCoincidence(oSegment, flipped, ordered)); 131855888e44171ffd48b591d19256884a969fe4da17caryclark } 131955888e44171ffd48b591d19256884a969fe4da17caryclark while ((oNext = oNext->upCast()->next()) != oEnd) { 132096dc1c9efaab4636e30f90aa377f25863f9bf3bacaryclark FAIL_IF(!oNext->upCastable()); 1321e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclark FAIL_IF(!oNext->upCast()->insertCoincidence(segment, flipped, ordered)); 132255888e44171ffd48b591d19256884a969fe4da17caryclark } 132355888e44171ffd48b591d19256884a969fe4da17caryclark } while ((coin = coin->next())); 1324e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclark return true; 132555888e44171ffd48b591d19256884a969fe4da17caryclark} 132655888e44171ffd48b591d19256884a969fe4da17caryclark 132755888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep in sync with debugMarkCollapsed() 132855888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpCoincidence::markCollapsed(SkCoincidentSpans* coin, SkOpPtT* test) { 132955888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* head = coin; 133055888e44171ffd48b591d19256884a969fe4da17caryclark while (coin) { 133155888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->collapsed(test)) { 133255888e44171ffd48b591d19256884a969fe4da17caryclark if (zero_or_one(coin->coinPtTStart()->fT) && zero_or_one(coin->coinPtTEnd()->fT)) { 133355888e44171ffd48b591d19256884a969fe4da17caryclark coin->coinPtTStartWritable()->segment()->markAllDone(); 133454359294a7c9dc54802d512a5d891a35c1663392caryclark } 133555888e44171ffd48b591d19256884a969fe4da17caryclark if (zero_or_one(coin->oppPtTStart()->fT) && zero_or_one(coin->oppPtTEnd()->fT)) { 133655888e44171ffd48b591d19256884a969fe4da17caryclark coin->oppPtTStartWritable()->segment()->markAllDone(); 133755888e44171ffd48b591d19256884a969fe4da17caryclark } 133855888e44171ffd48b591d19256884a969fe4da17caryclark this->release(head, coin); 133955888e44171ffd48b591d19256884a969fe4da17caryclark } 134055888e44171ffd48b591d19256884a969fe4da17caryclark coin = coin->next(); 134155888e44171ffd48b591d19256884a969fe4da17caryclark } 134255888e44171ffd48b591d19256884a969fe4da17caryclark} 134355888e44171ffd48b591d19256884a969fe4da17caryclark 134455888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep in sync with debugMarkCollapsed() 134555888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpCoincidence::markCollapsed(SkOpPtT* test) { 134655888e44171ffd48b591d19256884a969fe4da17caryclark markCollapsed(fHead, test); 134755888e44171ffd48b591d19256884a969fe4da17caryclark markCollapsed(fTop, test); 134855888e44171ffd48b591d19256884a969fe4da17caryclark} 134955888e44171ffd48b591d19256884a969fe4da17caryclark 135055888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::Ordered(const SkOpSegment* coinSeg, const SkOpSegment* oppSeg) { 135155888e44171ffd48b591d19256884a969fe4da17caryclark if (coinSeg->verb() < oppSeg->verb()) { 135255888e44171ffd48b591d19256884a969fe4da17caryclark return true; 135355888e44171ffd48b591d19256884a969fe4da17caryclark } 135455888e44171ffd48b591d19256884a969fe4da17caryclark if (coinSeg->verb() > oppSeg->verb()) { 135555888e44171ffd48b591d19256884a969fe4da17caryclark return false; 135655888e44171ffd48b591d19256884a969fe4da17caryclark } 135755888e44171ffd48b591d19256884a969fe4da17caryclark int count = (SkPathOpsVerbToPoints(coinSeg->verb()) + 1) * 2; 135855888e44171ffd48b591d19256884a969fe4da17caryclark const SkScalar* cPt = &coinSeg->pts()[0].fX; 135955888e44171ffd48b591d19256884a969fe4da17caryclark const SkScalar* oPt = &oppSeg->pts()[0].fX; 136055888e44171ffd48b591d19256884a969fe4da17caryclark for (int index = 0; index < count; ++index) { 136155888e44171ffd48b591d19256884a969fe4da17caryclark if (*cPt < *oPt) { 136255888e44171ffd48b591d19256884a969fe4da17caryclark return true; 136355888e44171ffd48b591d19256884a969fe4da17caryclark } 136455888e44171ffd48b591d19256884a969fe4da17caryclark if (*cPt > *oPt) { 136555888e44171ffd48b591d19256884a969fe4da17caryclark return false; 136655888e44171ffd48b591d19256884a969fe4da17caryclark } 136755888e44171ffd48b591d19256884a969fe4da17caryclark ++cPt; 136855888e44171ffd48b591d19256884a969fe4da17caryclark ++oPt; 136955888e44171ffd48b591d19256884a969fe4da17caryclark } 13705c5cfe24efe4c728e787447dabffe345080d1fb9caryclark return true; 137154359294a7c9dc54802d512a5d891a35c1663392caryclark} 137254359294a7c9dc54802d512a5d891a35c1663392caryclark 137355888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::overlap(const SkOpPtT* coin1s, const SkOpPtT* coin1e, 137454359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpPtT* coin2s, const SkOpPtT* coin2e, double* overS, double* overE) const { 137527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkASSERT(coin1s->segment() == coin2s->segment()); 137654359294a7c9dc54802d512a5d891a35c1663392caryclark *overS = SkTMax(SkTMin(coin1s->fT, coin1e->fT), SkTMin(coin2s->fT, coin2e->fT)); 137754359294a7c9dc54802d512a5d891a35c1663392caryclark *overE = SkTMin(SkTMax(coin1s->fT, coin1e->fT), SkTMax(coin2s->fT, coin2e->fT)); 137854359294a7c9dc54802d512a5d891a35c1663392caryclark return *overS < *overE; 137954359294a7c9dc54802d512a5d891a35c1663392caryclark} 138027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 138155888e44171ffd48b591d19256884a969fe4da17caryclark// Commented-out lines keep this in sync with debugRelease() 138255888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpCoincidence::release(const SkOpSegment* deleted) { 138355888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* coin = fHead; 138455888e44171ffd48b591d19256884a969fe4da17caryclark if (!coin) { 138555888e44171ffd48b591d19256884a969fe4da17caryclark return; 138655888e44171ffd48b591d19256884a969fe4da17caryclark } 138755888e44171ffd48b591d19256884a969fe4da17caryclark do { 138855888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->coinPtTStart()->segment() == deleted 138955888e44171ffd48b591d19256884a969fe4da17caryclark || coin->coinPtTEnd()->segment() == deleted 139055888e44171ffd48b591d19256884a969fe4da17caryclark || coin->oppPtTStart()->segment() == deleted 139155888e44171ffd48b591d19256884a969fe4da17caryclark || coin->oppPtTEnd()->segment() == deleted) { 139255888e44171ffd48b591d19256884a969fe4da17caryclark this->release(fHead, coin); 139355888e44171ffd48b591d19256884a969fe4da17caryclark } 139455888e44171ffd48b591d19256884a969fe4da17caryclark } while ((coin = coin->next())); 139555888e44171ffd48b591d19256884a969fe4da17caryclark} 1396