154359294a7c9dc54802d512a5d891a35c1663392caryclark/* 254359294a7c9dc54802d512a5d891a35c1663392caryclark * Copyright 2014 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 "SkOpContour.h" 954359294a7c9dc54802d512a5d891a35c1663392caryclark#include "SkOpSegment.h" 1054359294a7c9dc54802d512a5d891a35c1663392caryclark#include "SkPathWriter.h" 1154359294a7c9dc54802d512a5d891a35c1663392caryclark 1254359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpPtT::alias() const { 1354359294a7c9dc54802d512a5d891a35c1663392caryclark return this->span()->ptT() != this; 1454359294a7c9dc54802d512a5d891a35c1663392caryclark} 1554359294a7c9dc54802d512a5d891a35c1663392caryclark 1630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclarkconst SkOpPtT* SkOpPtT::active() const { 1730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (!fDeleted) { 1830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark return this; 1930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 2030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark const SkOpPtT* ptT = this; 2130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark const SkOpPtT* stopPtT = ptT; 2230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark while ((ptT = ptT->next()) != stopPtT) { 2330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (ptT->fSpan == fSpan && !ptT->fDeleted) { 2430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark return ptT; 2530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 2630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 2730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkASSERT(0); // should never return deleted 2830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark return this; 2930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark} 3030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark 3127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclarkbool SkOpPtT::contains(const SkOpPtT* check) const { 32e7bb5b226662f01c91574b29f435acae71c76c46caryclark SkOPASSERT(this != check); 3327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark const SkOpPtT* ptT = this; 3427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark const SkOpPtT* stopPtT = ptT; 3527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark while ((ptT = ptT->next()) != stopPtT) { 3627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (ptT == check) { 3727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark return true; 3827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 3927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 4027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark return false; 4127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 4227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 4355888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpPtT::contains(const SkOpSegment* segment, const SkPoint& pt) const { 4455888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(this->segment() != segment); 4555888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* ptT = this; 4627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark const SkOpPtT* stopPtT = ptT; 4727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark while ((ptT = ptT->next()) != stopPtT) { 4855888e44171ffd48b591d19256884a969fe4da17caryclark if (ptT->fPt == pt && ptT->segment() == segment) { 4955888e44171ffd48b591d19256884a969fe4da17caryclark return true; 5027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 5127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 5255888e44171ffd48b591d19256884a969fe4da17caryclark return false; 5327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 5427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 5555888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpPtT::contains(const SkOpSegment* segment, double t) const { 5655888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* ptT = this; 5755888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* stopPtT = ptT; 5855888e44171ffd48b591d19256884a969fe4da17caryclark while ((ptT = ptT->next()) != stopPtT) { 5955888e44171ffd48b591d19256884a969fe4da17caryclark if (ptT->fT == t && ptT->segment() == segment) { 6055888e44171ffd48b591d19256884a969fe4da17caryclark return true; 6155888e44171ffd48b591d19256884a969fe4da17caryclark } 6255888e44171ffd48b591d19256884a969fe4da17caryclark } 6355888e44171ffd48b591d19256884a969fe4da17caryclark return false; 6454359294a7c9dc54802d512a5d891a35c1663392caryclark} 6554359294a7c9dc54802d512a5d891a35c1663392caryclark 6655888e44171ffd48b591d19256884a969fe4da17caryclarkconst SkOpPtT* SkOpPtT::contains(const SkOpSegment* check) const { 6755888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(this->segment() != check); 6855888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* ptT = this; 6927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark const SkOpPtT* stopPtT = ptT; 7055888e44171ffd48b591d19256884a969fe4da17caryclark while ((ptT = ptT->next()) != stopPtT) { 7155888e44171ffd48b591d19256884a969fe4da17caryclark if (ptT->segment() == check && !ptT->deleted()) { 7227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark return ptT; 7327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 7455888e44171ffd48b591d19256884a969fe4da17caryclark } 7596fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 7627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 7727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 7855888e44171ffd48b591d19256884a969fe4da17caryclarkSkOpContour* SkOpPtT::contour() const { 7955888e44171ffd48b591d19256884a969fe4da17caryclark return segment()->contour(); 8055888e44171ffd48b591d19256884a969fe4da17caryclark} 8155888e44171ffd48b591d19256884a969fe4da17caryclark 8255888e44171ffd48b591d19256884a969fe4da17caryclarkconst SkOpPtT* SkOpPtT::find(const SkOpSegment* segment) const { 8355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* ptT = this; 8427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark const SkOpPtT* stopPtT = ptT; 8527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark do { 8655888e44171ffd48b591d19256884a969fe4da17caryclark if (ptT->segment() == segment && !ptT->deleted()) { 8727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark return ptT; 8827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 8927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark ptT = ptT->fNext; 9027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } while (stopPtT != ptT); 9155888e44171ffd48b591d19256884a969fe4da17caryclark// SkASSERT(0); 9296fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 9327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 9427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 9554359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpGlobalState* SkOpPtT::globalState() const { 9655888e44171ffd48b591d19256884a969fe4da17caryclark return contour()->globalState(); 9754359294a7c9dc54802d512a5d891a35c1663392caryclark} 9854359294a7c9dc54802d512a5d891a35c1663392caryclark 9954359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpPtT::init(SkOpSpanBase* span, double t, const SkPoint& pt, bool duplicate) { 10054359294a7c9dc54802d512a5d891a35c1663392caryclark fT = t; 10154359294a7c9dc54802d512a5d891a35c1663392caryclark fPt = pt; 10254359294a7c9dc54802d512a5d891a35c1663392caryclark fSpan = span; 10354359294a7c9dc54802d512a5d891a35c1663392caryclark fNext = this; 10454359294a7c9dc54802d512a5d891a35c1663392caryclark fDuplicatePt = duplicate; 10554359294a7c9dc54802d512a5d891a35c1663392caryclark fDeleted = false; 10655888e44171ffd48b591d19256884a969fe4da17caryclark fCoincident = false; 1071049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(fID = span->globalState()->nextPtTID()); 10854359294a7c9dc54802d512a5d891a35c1663392caryclark} 10954359294a7c9dc54802d512a5d891a35c1663392caryclark 11054359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpPtT::onEnd() const { 11154359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* span = this->span(); 11254359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->ptT() != this) { 11354359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 11454359294a7c9dc54802d512a5d891a35c1663392caryclark } 11554359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSegment* segment = this->segment(); 11654359294a7c9dc54802d512a5d891a35c1663392caryclark return span == segment->head() || span == segment->tail(); 11754359294a7c9dc54802d512a5d891a35c1663392caryclark} 11854359294a7c9dc54802d512a5d891a35c1663392caryclark 11955888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpPtT::ptAlreadySeen(const SkOpPtT* check) const { 12055888e44171ffd48b591d19256884a969fe4da17caryclark while (this != check) { 12155888e44171ffd48b591d19256884a969fe4da17caryclark if (this->fPt == check->fPt) { 12255888e44171ffd48b591d19256884a969fe4da17caryclark return true; 12355888e44171ffd48b591d19256884a969fe4da17caryclark } 12455888e44171ffd48b591d19256884a969fe4da17caryclark check = check->fNext; 12555888e44171ffd48b591d19256884a969fe4da17caryclark } 12655888e44171ffd48b591d19256884a969fe4da17caryclark return false; 12755888e44171ffd48b591d19256884a969fe4da17caryclark} 12855888e44171ffd48b591d19256884a969fe4da17caryclark 12954359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpPtT* SkOpPtT::prev() { 13054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* result = this; 13154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* next = this; 13254359294a7c9dc54802d512a5d891a35c1663392caryclark while ((next = next->fNext) != this) { 13354359294a7c9dc54802d512a5d891a35c1663392caryclark result = next; 13454359294a7c9dc54802d512a5d891a35c1663392caryclark } 13554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(result->fNext == this); 13654359294a7c9dc54802d512a5d891a35c1663392caryclark return result; 13754359294a7c9dc54802d512a5d891a35c1663392caryclark} 13854359294a7c9dc54802d512a5d891a35c1663392caryclark 13954359294a7c9dc54802d512a5d891a35c1663392caryclarkconst SkOpSegment* SkOpPtT::segment() const { 14054359294a7c9dc54802d512a5d891a35c1663392caryclark return span()->segment(); 14154359294a7c9dc54802d512a5d891a35c1663392caryclark} 14254359294a7c9dc54802d512a5d891a35c1663392caryclark 14354359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSegment* SkOpPtT::segment() { 14454359294a7c9dc54802d512a5d891a35c1663392caryclark return span()->segment(); 14554359294a7c9dc54802d512a5d891a35c1663392caryclark} 14654359294a7c9dc54802d512a5d891a35c1663392caryclark 14755888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpPtT::setDeleted() { 14855888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(this->span()->debugDeleted() || this->span()->ptT() != this); 1491597628fa38d24f23ad505bfb40e70e7c8617457caryclark SkOPASSERT(!fDeleted); 15055888e44171ffd48b591d19256884a969fe4da17caryclark fDeleted = true; 15155888e44171ffd48b591d19256884a969fe4da17caryclark} 15255888e44171ffd48b591d19256884a969fe4da17caryclark 15330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclarkvoid SkOpSpanBase::addOpp(SkOpSpanBase* opp) { 15429b2563afb1677515739f1d24fb27733626eca92caryclark SkOpPtT* oppPrev = this->ptT()->oppPrev(opp->ptT()); 15530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (!oppPrev) { 15654359294a7c9dc54802d512a5d891a35c1663392caryclark return; 15754359294a7c9dc54802d512a5d891a35c1663392caryclark } 15830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark this->mergeMatches(opp); 15930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark this->ptT()->addOpp(opp->ptT(), oppPrev); 16030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark this->checkForCollapsedCoincidence(); 16155888e44171ffd48b591d19256884a969fe4da17caryclark} 16255888e44171ffd48b591d19256884a969fe4da17caryclark 16330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclarkbool SkOpSpanBase::collapsed(double s, double e) const { 16430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark const SkOpPtT* start = &fPtT; 16530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark const SkOpPtT* walk = start; 16630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark double min = walk->fT; 16730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark double max = min; 16830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark const SkOpSegment* segment = this->segment(); 16930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark while ((walk = walk->next()) != start) { 17030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (walk->segment() != segment) { 17130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark continue; 17230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 17330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark min = SkTMin(min, walk->fT); 17430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark max = SkTMax(max, walk->fT); 17530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (between(min, s, max) && between(min, e, max)) { 17630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark return true; 17730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 17830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 17930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark return false; 18030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark} 18130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark 18254359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSpanBase::contains(const SkOpSpanBase* span) const { 18354359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpPtT* start = &fPtT; 18454359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpPtT* check = &span->fPtT; 185ef4f32ac858825dc443cfe4739ea878fb0bf550fcaryclark SkOPASSERT(start != check); 18654359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpPtT* walk = start; 18754359294a7c9dc54802d512a5d891a35c1663392caryclark while ((walk = walk->next()) != start) { 18854359294a7c9dc54802d512a5d891a35c1663392caryclark if (walk == check) { 18954359294a7c9dc54802d512a5d891a35c1663392caryclark return true; 19054359294a7c9dc54802d512a5d891a35c1663392caryclark } 19154359294a7c9dc54802d512a5d891a35c1663392caryclark } 19254359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 19354359294a7c9dc54802d512a5d891a35c1663392caryclark} 19454359294a7c9dc54802d512a5d891a35c1663392caryclark 19555888e44171ffd48b591d19256884a969fe4da17caryclarkconst SkOpPtT* SkOpSpanBase::contains(const SkOpSegment* segment) const { 19655888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* start = &fPtT; 19755888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* walk = start; 19854359294a7c9dc54802d512a5d891a35c1663392caryclark while ((walk = walk->next()) != start) { 19955888e44171ffd48b591d19256884a969fe4da17caryclark if (walk->deleted()) { 20055888e44171ffd48b591d19256884a969fe4da17caryclark continue; 20155888e44171ffd48b591d19256884a969fe4da17caryclark } 20255888e44171ffd48b591d19256884a969fe4da17caryclark if (walk->segment() == segment && walk->span()->ptT() == walk) { 20354359294a7c9dc54802d512a5d891a35c1663392caryclark return walk; 20454359294a7c9dc54802d512a5d891a35c1663392caryclark } 20554359294a7c9dc54802d512a5d891a35c1663392caryclark } 20696fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 20754359294a7c9dc54802d512a5d891a35c1663392caryclark} 20854359294a7c9dc54802d512a5d891a35c1663392caryclark 20954359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSpanBase::containsCoinEnd(const SkOpSegment* segment) const { 21054359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this->segment() != segment); 21154359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* next = this; 21254359294a7c9dc54802d512a5d891a35c1663392caryclark while ((next = next->fCoinEnd) != this) { 21354359294a7c9dc54802d512a5d891a35c1663392caryclark if (next->segment() == segment) { 21454359294a7c9dc54802d512a5d891a35c1663392caryclark return true; 21554359294a7c9dc54802d512a5d891a35c1663392caryclark } 21654359294a7c9dc54802d512a5d891a35c1663392caryclark } 21754359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 21854359294a7c9dc54802d512a5d891a35c1663392caryclark} 21954359294a7c9dc54802d512a5d891a35c1663392caryclark 22054359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpContour* SkOpSpanBase::contour() const { 22154359294a7c9dc54802d512a5d891a35c1663392caryclark return segment()->contour(); 22254359294a7c9dc54802d512a5d891a35c1663392caryclark} 22354359294a7c9dc54802d512a5d891a35c1663392caryclark 22454359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpGlobalState* SkOpSpanBase::globalState() const { 22555888e44171ffd48b591d19256884a969fe4da17caryclark return contour()->globalState(); 22654359294a7c9dc54802d512a5d891a35c1663392caryclark} 22754359294a7c9dc54802d512a5d891a35c1663392caryclark 22854359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSpanBase::initBase(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoint& pt) { 22954359294a7c9dc54802d512a5d891a35c1663392caryclark fSegment = segment; 23054359294a7c9dc54802d512a5d891a35c1663392caryclark fPtT.init(this, t, pt, false); 23154359294a7c9dc54802d512a5d891a35c1663392caryclark fCoinEnd = this; 23296fcdcc219d2a0d3579719b84b28bede76efba64halcanary fFromAngle = nullptr; 23354359294a7c9dc54802d512a5d891a35c1663392caryclark fPrev = prev; 23408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark fSpanAdds = 0; 23554359294a7c9dc54802d512a5d891a35c1663392caryclark fAligned = true; 23654359294a7c9dc54802d512a5d891a35c1663392caryclark fChased = false; 2371049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(fCount = 1); 2381049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(fID = globalState()->nextSpanID()); 23930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkDEBUGCODE(fDebugDeleted = false); 24054359294a7c9dc54802d512a5d891a35c1663392caryclark} 24154359294a7c9dc54802d512a5d891a35c1663392caryclark 24254359294a7c9dc54802d512a5d891a35c1663392caryclark// this pair of spans share a common t value or point; merge them and eliminate duplicates 24354359294a7c9dc54802d512a5d891a35c1663392caryclark// this does not compute the best t or pt value; this merely moves all data into a single list 24454359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSpanBase::merge(SkOpSpan* span) { 24554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* spanPtT = span->ptT(); 24654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this->t() != spanPtT->fT); 24754359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!zero_or_one(spanPtT->fT)); 24818300a3aa7cb6eb55d21bb0450dffa58b6fc062cmtklein span->release(this->ptT()); 24955888e44171ffd48b591d19256884a969fe4da17caryclark if (this->contains(span)) { 25030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOPASSERT(0); // check to see if this ever happens -- should have been found earlier 25155888e44171ffd48b591d19256884a969fe4da17caryclark return; // merge is already in the ptT loop 25255888e44171ffd48b591d19256884a969fe4da17caryclark } 25354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* remainder = spanPtT->next(); 25455888e44171ffd48b591d19256884a969fe4da17caryclark this->ptT()->insert(spanPtT); 25554359294a7c9dc54802d512a5d891a35c1663392caryclark while (remainder != spanPtT) { 25654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* next = remainder->next(); 25754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* compare = spanPtT->next(); 25854359294a7c9dc54802d512a5d891a35c1663392caryclark while (compare != spanPtT) { 25954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* nextC = compare->next(); 26054359294a7c9dc54802d512a5d891a35c1663392caryclark if (nextC->span() == remainder->span() && nextC->fT == remainder->fT) { 26154359294a7c9dc54802d512a5d891a35c1663392caryclark goto tryNextRemainder; 26254359294a7c9dc54802d512a5d891a35c1663392caryclark } 26354359294a7c9dc54802d512a5d891a35c1663392caryclark compare = nextC; 26454359294a7c9dc54802d512a5d891a35c1663392caryclark } 26554359294a7c9dc54802d512a5d891a35c1663392caryclark spanPtT->insert(remainder); 26654359294a7c9dc54802d512a5d891a35c1663392caryclarktryNextRemainder: 26754359294a7c9dc54802d512a5d891a35c1663392caryclark remainder = next; 26854359294a7c9dc54802d512a5d891a35c1663392caryclark } 26908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark fSpanAdds += span->fSpanAdds; 27030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark} 27130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark 27230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclarkSkOpSpanBase* SkOpSpanBase::active() { 27330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOpSpanBase* result = fPrev ? fPrev->next() : upCast()->next()->prev(); 27430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkASSERT(this == result || fDebugDeleted); 27530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark return result; 27655888e44171ffd48b591d19256884a969fe4da17caryclark} 27755888e44171ffd48b591d19256884a969fe4da17caryclark 27855888e44171ffd48b591d19256884a969fe4da17caryclark// please keep in sync with debugCheckForCollapsedCoincidence() 27955888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpSpanBase::checkForCollapsedCoincidence() { 28055888e44171ffd48b591d19256884a969fe4da17caryclark SkOpCoincidence* coins = this->globalState()->coincidence(); 28155888e44171ffd48b591d19256884a969fe4da17caryclark if (coins->isEmpty()) { 28255888e44171ffd48b591d19256884a969fe4da17caryclark return; 28355888e44171ffd48b591d19256884a969fe4da17caryclark } 28455888e44171ffd48b591d19256884a969fe4da17caryclark// the insert above may have put both ends of a coincident run in the same span 28555888e44171ffd48b591d19256884a969fe4da17caryclark// for each coincident ptT in loop; see if its opposite in is also in the loop 28655888e44171ffd48b591d19256884a969fe4da17caryclark// this implementation is the motivation for marking that a ptT is referenced by a coincident span 28755888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* head = this->ptT(); 28855888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* test = head; 28955888e44171ffd48b591d19256884a969fe4da17caryclark do { 29055888e44171ffd48b591d19256884a969fe4da17caryclark if (!test->coincident()) { 29155888e44171ffd48b591d19256884a969fe4da17caryclark continue; 29255888e44171ffd48b591d19256884a969fe4da17caryclark } 29355888e44171ffd48b591d19256884a969fe4da17caryclark coins->markCollapsed(test); 29455888e44171ffd48b591d19256884a969fe4da17caryclark } while ((test = test->next()) != head); 29530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark coins->releaseDeleted(); 29630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark} 29730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark 29830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark// please keep in sync with debugMergeMatches() 29930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark// Look to see if pt-t linked list contains same segment more than once 30030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark// if so, and if each pt-t is directly pointed to by spans in that segment, 30130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark// merge them 30230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark// keep the points, but remove spans so that the segment doesn't have 2 or more 30330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark// spans pointing to the same pt-t loop at different loop elements 30430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclarkvoid SkOpSpanBase::mergeMatches(SkOpSpanBase* opp) { 30530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOpPtT* test = &fPtT; 30630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOpPtT* testNext; 30730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark const SkOpPtT* stop = test; 30830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark do { 30930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark testNext = test->next(); 31030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (test->deleted()) { 31130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark continue; 31230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 31330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOpSpanBase* testBase = test->span(); 31430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkASSERT(testBase->ptT() == test); 31530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOpSegment* segment = test->segment(); 31630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (segment->done()) { 31730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark continue; 31830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 31930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOpPtT* inner = opp->ptT(); 32030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark const SkOpPtT* innerStop = inner; 32130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark do { 32230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (inner->segment() != segment) { 32330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark continue; 32430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 32530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (inner->deleted()) { 32630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark continue; 32730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 32830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOpSpanBase* innerBase = inner->span(); 32930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkASSERT(innerBase->ptT() == inner); 33030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark // when the intersection is first detected, the span base is marked if there are 33130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark // more than one point in the intersection. 33230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (!zero_or_one(inner->fT)) { 33330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark innerBase->upCast()->release(test); 33430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } else { 335b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark SkOPASSERT(inner->fT != test->fT); 33630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (!zero_or_one(test->fT)) { 33730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark testBase->upCast()->release(inner); 33830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } else { 33930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark segment->markAllDone(); // mark segment as collapsed 34030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkDEBUGCODE(testBase->debugSetDeleted()); 34130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark test->setDeleted(); 34230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkDEBUGCODE(innerBase->debugSetDeleted()); 34330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark inner->setDeleted(); 34430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 34530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 34630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark#ifdef SK_DEBUG // assert if another undeleted entry points to segment 34730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark const SkOpPtT* debugInner = inner; 34830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark while ((debugInner = debugInner->next()) != innerStop) { 34930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (debugInner->segment() != segment) { 35030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark continue; 35130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 35230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (debugInner->deleted()) { 35330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark continue; 35430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 35530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOPASSERT(0); 35630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 35730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark#endif 35830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark break; 35930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } while ((inner = inner->next()) != innerStop); 36030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } while ((test = testNext) != stop); 36130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark this->checkForCollapsedCoincidence(); 36254359294a7c9dc54802d512a5d891a35c1663392caryclark} 36354359294a7c9dc54802d512a5d891a35c1663392caryclark 364bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclarkint SkOpSpan::computeWindSum() { 365bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpGlobalState* globals = this->globalState(); 366bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpContour* contourHead = globals->contourHead(); 367bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark int windTry = 0; 368bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark while (!this->sortableTop(contourHead) && ++windTry < SkOpGlobalState::kMaxWindingTries) { 369bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark ; 370bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 371bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark return this->windSum(); 372bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark} 373bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark 37454359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSpan::containsCoincidence(const SkOpSegment* segment) const { 37554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this->segment() != segment); 37654359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpan* next = fCoincident; 37754359294a7c9dc54802d512a5d891a35c1663392caryclark do { 37854359294a7c9dc54802d512a5d891a35c1663392caryclark if (next->segment() == segment) { 37954359294a7c9dc54802d512a5d891a35c1663392caryclark return true; 38054359294a7c9dc54802d512a5d891a35c1663392caryclark } 38154359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((next = next->fCoincident) != this); 38254359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 38354359294a7c9dc54802d512a5d891a35c1663392caryclark} 38454359294a7c9dc54802d512a5d891a35c1663392caryclark 38555888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpSpan::init(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoint& pt) { 38655888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(t != 1); 38755888e44171ffd48b591d19256884a969fe4da17caryclark initBase(segment, prev, t, pt); 38855888e44171ffd48b591d19256884a969fe4da17caryclark fCoincident = this; 38955888e44171ffd48b591d19256884a969fe4da17caryclark fToAngle = nullptr; 39055888e44171ffd48b591d19256884a969fe4da17caryclark fWindSum = fOppSum = SK_MinS32; 39155888e44171ffd48b591d19256884a969fe4da17caryclark fWindValue = 1; 39255888e44171ffd48b591d19256884a969fe4da17caryclark fOppValue = 0; 39355888e44171ffd48b591d19256884a969fe4da17caryclark fTopTTry = 0; 39455888e44171ffd48b591d19256884a969fe4da17caryclark fChased = fDone = false; 39555888e44171ffd48b591d19256884a969fe4da17caryclark segment->bumpCount(); 39655888e44171ffd48b591d19256884a969fe4da17caryclark fAlreadyAdded = false; 39755888e44171ffd48b591d19256884a969fe4da17caryclark} 39855888e44171ffd48b591d19256884a969fe4da17caryclark 39955888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with debugInsertCoincidence() 40081a478ca6c36aac3e53ce0373a281ac8940f4780caryclarkbool SkOpSpan::insertCoincidence(const SkOpSegment* segment, bool flipped, bool ordered) { 40155888e44171ffd48b591d19256884a969fe4da17caryclark if (this->containsCoincidence(segment)) { 40255888e44171ffd48b591d19256884a969fe4da17caryclark return true; 40355888e44171ffd48b591d19256884a969fe4da17caryclark } 40455888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* next = &fPtT; 40555888e44171ffd48b591d19256884a969fe4da17caryclark while ((next = next->next()) != &fPtT) { 40655888e44171ffd48b591d19256884a969fe4da17caryclark if (next->segment() == segment) { 4071493b9772d6fad455a222ec6f242903128e049a0caryclark SkOpSpan* span; 40881a478ca6c36aac3e53ce0373a281ac8940f4780caryclark SkOpSpanBase* base = next->span(); 40981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if (!ordered) { 410e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclark const SkOpPtT* spanEndPtT = fNext->contains(segment); 411e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclark FAIL_IF(!spanEndPtT); 412e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclark const SkOpSpanBase* spanEnd = spanEndPtT->span(); 41381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark const SkOpPtT* start = base->ptT()->starter(spanEnd->ptT()); 41445f04b8ea8256476d87c677e23d9efbcb0ab937ecaryclark FAIL_IF(!start->span()->upCastable()); 41581a478ca6c36aac3e53ce0373a281ac8940f4780caryclark span = const_cast<SkOpSpan*>(start->span()->upCast()); 41681a478ca6c36aac3e53ce0373a281ac8940f4780caryclark } else if (flipped) { 41781a478ca6c36aac3e53ce0373a281ac8940f4780caryclark span = base->prev(); 41881a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(!span); 4191493b9772d6fad455a222ec6f242903128e049a0caryclark } else { 42081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(!base->upCastable()); 4211493b9772d6fad455a222ec6f242903128e049a0caryclark span = base->upCast(); 42255888e44171ffd48b591d19256884a969fe4da17caryclark } 42355888e44171ffd48b591d19256884a969fe4da17caryclark this->insertCoincidence(span); 42455888e44171ffd48b591d19256884a969fe4da17caryclark return true; 42555888e44171ffd48b591d19256884a969fe4da17caryclark } 42655888e44171ffd48b591d19256884a969fe4da17caryclark } 42755888e44171ffd48b591d19256884a969fe4da17caryclark#if DEBUG_COINCIDENCE 42855888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(0); // FIXME? if we get here, the span is missing its opposite segment... 42955888e44171ffd48b591d19256884a969fe4da17caryclark#endif 43055888e44171ffd48b591d19256884a969fe4da17caryclark return true; 43155888e44171ffd48b591d19256884a969fe4da17caryclark} 43255888e44171ffd48b591d19256884a969fe4da17caryclark 43355888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpSpan::release(const SkOpPtT* kept) { 43430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkDEBUGCODE(fDebugDeleted = true); 435b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark SkOPASSERT(kept->span() != this); 43654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!final()); 43754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* prev = this->prev(); 43854359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(prev); 43954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* next = this->next(); 44054359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(next); 44154359294a7c9dc54802d512a5d891a35c1663392caryclark prev->setNext(next); 44254359294a7c9dc54802d512a5d891a35c1663392caryclark next->setPrev(prev); 44318300a3aa7cb6eb55d21bb0450dffa58b6fc062cmtklein this->segment()->release(this); 444218f21ac09c70b98a10cb8e1999b85a22fa0b151caryclark SkOpCoincidence* coincidence = this->globalState()->coincidence(); 445218f21ac09c70b98a10cb8e1999b85a22fa0b151caryclark if (coincidence) { 446218f21ac09c70b98a10cb8e1999b85a22fa0b151caryclark coincidence->fixUp(this->ptT(), kept); 447218f21ac09c70b98a10cb8e1999b85a22fa0b151caryclark } 44854359294a7c9dc54802d512a5d891a35c1663392caryclark this->ptT()->setDeleted(); 44955888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* stopPtT = this->ptT(); 45055888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* testPtT = stopPtT; 45155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* keptSpan = kept->span(); 45255888e44171ffd48b591d19256884a969fe4da17caryclark do { 45355888e44171ffd48b591d19256884a969fe4da17caryclark if (this == testPtT->span()) { 45455888e44171ffd48b591d19256884a969fe4da17caryclark testPtT->setSpan(keptSpan); 45555888e44171ffd48b591d19256884a969fe4da17caryclark } 45655888e44171ffd48b591d19256884a969fe4da17caryclark } while ((testPtT = testPtT->next()) != stopPtT); 45754359294a7c9dc54802d512a5d891a35c1663392caryclark} 45854359294a7c9dc54802d512a5d891a35c1663392caryclark 45954359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSpan::setOppSum(int oppSum) { 46054359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!final()); 46154359294a7c9dc54802d512a5d891a35c1663392caryclark if (fOppSum != SK_MinS32 && fOppSum != oppSum) { 46254359294a7c9dc54802d512a5d891a35c1663392caryclark this->globalState()->setWindingFailed(); 46354359294a7c9dc54802d512a5d891a35c1663392caryclark return; 46454359294a7c9dc54802d512a5d891a35c1663392caryclark } 46560e0fee6d4acff638ccc9670c4055aced529a7a0bungeman SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(oppSum) <= DEBUG_LIMIT_WIND_SUM); 46654359294a7c9dc54802d512a5d891a35c1663392caryclark fOppSum = oppSum; 46754359294a7c9dc54802d512a5d891a35c1663392caryclark} 468624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 469624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkvoid SkOpSpan::setWindSum(int windSum) { 470624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkASSERT(!final()); 471624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (fWindSum != SK_MinS32 && fWindSum != windSum) { 472624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark this->globalState()->setWindingFailed(); 473624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return; 474624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 47560e0fee6d4acff638ccc9670c4055aced529a7a0bungeman SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(windSum) <= DEBUG_LIMIT_WIND_SUM); 476624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark fWindSum = windSum; 477624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 478