SkPathOpsTSect.h revision 1049f1246e7be4ccb68001361efceb8933e6f81c
145fa447460f70ec21d22cf4e1531490acfd3c578caryclark/* 245fa447460f70ec21d22cf4e1531490acfd3c578caryclark * Copyright 2014 Google Inc. 345fa447460f70ec21d22cf4e1531490acfd3c578caryclark * 445fa447460f70ec21d22cf4e1531490acfd3c578caryclark * Use of this source code is governed by a BSD-style license that can be 545fa447460f70ec21d22cf4e1531490acfd3c578caryclark * found in the LICENSE file. 645fa447460f70ec21d22cf4e1531490acfd3c578caryclark */ 745fa447460f70ec21d22cf4e1531490acfd3c578caryclark 845fa447460f70ec21d22cf4e1531490acfd3c578caryclark#include "SkChunkAlloc.h" 954359294a7c9dc54802d512a5d891a35c1663392caryclark#include "SkPathOpsBounds.h" 1045fa447460f70ec21d22cf4e1531490acfd3c578caryclark#include "SkPathOpsRect.h" 1145fa447460f70ec21d22cf4e1531490acfd3c578caryclark#include "SkIntersections.h" 1254359294a7c9dc54802d512a5d891a35c1663392caryclark#include "SkTSort.h" 1345fa447460f70ec21d22cf4e1531490acfd3c578caryclark 141049f1246e7be4ccb68001361efceb8933e6f81ccaryclark/* TCurve and OppCurve are one of { SkDQuadratic, SkDConic, SkDCubic } */ 151049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 1645fa447460f70ec21d22cf4e1531490acfd3c578caryclarkclass SkTCoincident { 1745fa447460f70ec21d22cf4e1531490acfd3c578caryclarkpublic: 18697ac1c138e8ff83cb90449ff378a000796f8a04caryclark SkTCoincident() { 191049f1246e7be4ccb68001361efceb8933e6f81ccaryclark this->clear(); 2054359294a7c9dc54802d512a5d891a35c1663392caryclark } 2154359294a7c9dc54802d512a5d891a35c1663392caryclark 2254359294a7c9dc54802d512a5d891a35c1663392caryclark void clear() { 2354359294a7c9dc54802d512a5d891a35c1663392caryclark fPerpT = -1; 2454359294a7c9dc54802d512a5d891a35c1663392caryclark fCoincident = false; 2554359294a7c9dc54802d512a5d891a35c1663392caryclark } 2654359294a7c9dc54802d512a5d891a35c1663392caryclark 271049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void debugInit() { 281049f1246e7be4ccb68001361efceb8933e6f81ccaryclark this->clear(); 291049f1246e7be4ccb68001361efceb8933e6f81ccaryclark fPerpPt.fX = fPerpPt.fY = SK_ScalarNaN; 301049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 311049f1246e7be4ccb68001361efceb8933e6f81ccaryclark 321049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void dump() const; 331049f1246e7be4ccb68001361efceb8933e6f81ccaryclark 3445fa447460f70ec21d22cf4e1531490acfd3c578caryclark bool isCoincident() const { 3545fa447460f70ec21d22cf4e1531490acfd3c578caryclark return fCoincident; 3645fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 3745fa447460f70ec21d22cf4e1531490acfd3c578caryclark 3845fa447460f70ec21d22cf4e1531490acfd3c578caryclark void init() { 391049f1246e7be4ccb68001361efceb8933e6f81ccaryclark this->clear(); 4045fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkDEBUGCODE(fPerpPt.fX = fPerpPt.fY = SK_ScalarNaN); 4145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 4245fa447460f70ec21d22cf4e1531490acfd3c578caryclark 4345fa447460f70ec21d22cf4e1531490acfd3c578caryclark void markCoincident() { 4445fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (!fCoincident) { 4545fa447460f70ec21d22cf4e1531490acfd3c578caryclark fPerpT = -1; 4645fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 4745fa447460f70ec21d22cf4e1531490acfd3c578caryclark fCoincident = true; 4845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 4945fa447460f70ec21d22cf4e1531490acfd3c578caryclark 5045fa447460f70ec21d22cf4e1531490acfd3c578caryclark const SkDPoint& perpPt() const { 5145fa447460f70ec21d22cf4e1531490acfd3c578caryclark return fPerpPt; 5245fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 5345fa447460f70ec21d22cf4e1531490acfd3c578caryclark 5445fa447460f70ec21d22cf4e1531490acfd3c578caryclark double perpT() const { 5545fa447460f70ec21d22cf4e1531490acfd3c578caryclark return fPerpT; 5645fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 5745fa447460f70ec21d22cf4e1531490acfd3c578caryclark 581049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void setPerp(const TCurve& c1, double t, const SkDPoint& cPt, const OppCurve& ); 5945fa447460f70ec21d22cf4e1531490acfd3c578caryclark 6045fa447460f70ec21d22cf4e1531490acfd3c578caryclarkprivate: 6145fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkDPoint fPerpPt; 6245fa447460f70ec21d22cf4e1531490acfd3c578caryclark double fPerpT; // perpendicular intersection on opposite curve 6345fa447460f70ec21d22cf4e1531490acfd3c578caryclark bool fCoincident; 6445fa447460f70ec21d22cf4e1531490acfd3c578caryclark}; 6545fa447460f70ec21d22cf4e1531490acfd3c578caryclark 661049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> class SkTSect; 671049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> class SkTSpan; 6854359294a7c9dc54802d512a5d891a35c1663392caryclark 691049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 7054359294a7c9dc54802d512a5d891a35c1663392caryclarkstruct SkTSpanBounded { 711049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* fBounded; 7254359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSpanBounded* fNext; 7354359294a7c9dc54802d512a5d891a35c1663392caryclark}; 7445fa447460f70ec21d22cf4e1531490acfd3c578caryclark 7545fa447460f70ec21d22cf4e1531490acfd3c578caryclark/* Curve is either TCurve or SkDCubic */ 761049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 7745fa447460f70ec21d22cf4e1531490acfd3c578caryclarkclass SkTSpan { 7845fa447460f70ec21d22cf4e1531490acfd3c578caryclarkpublic: 791049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void addBounded(SkTSpan<OppCurve, TCurve>* , SkChunkAlloc* ); 8045fa447460f70ec21d22cf4e1531490acfd3c578caryclark double closestBoundedT(const SkDPoint& pt) const; 8154359294a7c9dc54802d512a5d891a35c1663392caryclark bool contains(double t) const; 8245fa447460f70ec21d22cf4e1531490acfd3c578caryclark 831049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void debugInit() { 841049f1246e7be4ccb68001361efceb8933e6f81ccaryclark TCurve dummy; 851049f1246e7be4ccb68001361efceb8933e6f81ccaryclark dummy.debugInit(); 861049f1246e7be4ccb68001361efceb8933e6f81ccaryclark init(dummy); 871049f1246e7be4ccb68001361efceb8933e6f81ccaryclark initBounds(dummy); 881049f1246e7be4ccb68001361efceb8933e6f81ccaryclark fCoinStart.debugInit(); 891049f1246e7be4ccb68001361efceb8933e6f81ccaryclark fCoinEnd.debugInit(); 901049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 911049f1246e7be4ccb68001361efceb8933e6f81ccaryclark 921049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSect<OppCurve, TCurve>* debugOpp() const; 9354359294a7c9dc54802d512a5d891a35c1663392caryclark const SkTSpan* debugSpan(int ) const; 9454359294a7c9dc54802d512a5d891a35c1663392caryclark const SkTSpan* debugT(double t) const; 9554359294a7c9dc54802d512a5d891a35c1663392caryclark#ifdef SK_DEBUG 9654359294a7c9dc54802d512a5d891a35c1663392caryclark bool debugIsBefore(const SkTSpan* span) const; 9754359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 9854359294a7c9dc54802d512a5d891a35c1663392caryclark void dump() const; 991049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void dumpBounded(int id) const; 1001049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void dumpBounds() const; 1011049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void dumpCoin() const; 10245fa447460f70ec21d22cf4e1531490acfd3c578caryclark 10345fa447460f70ec21d22cf4e1531490acfd3c578caryclark double endT() const { 10445fa447460f70ec21d22cf4e1531490acfd3c578caryclark return fEndT; 10545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 10645fa447460f70ec21d22cf4e1531490acfd3c578caryclark 1071049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* findOppSpan(const SkTSpan<OppCurve, TCurve>* opp) const; 10854359294a7c9dc54802d512a5d891a35c1663392caryclark 1091049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* findOppT(double t) const { 1101049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* result = oppT(t); 11145fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkASSERT(result); 11245fa447460f70ec21d22cf4e1531490acfd3c578caryclark return result; 11345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 11445fa447460f70ec21d22cf4e1531490acfd3c578caryclark 11554359294a7c9dc54802d512a5d891a35c1663392caryclark bool hasOppT(double t) const { 11654359294a7c9dc54802d512a5d891a35c1663392caryclark return SkToBool(oppT(t)); 11754359294a7c9dc54802d512a5d891a35c1663392caryclark } 11854359294a7c9dc54802d512a5d891a35c1663392caryclark 1191049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int hullsIntersect(SkTSpan<OppCurve, TCurve>* span, bool* start, bool* oppStart); 12054359294a7c9dc54802d512a5d891a35c1663392caryclark void init(const TCurve& ); 12154359294a7c9dc54802d512a5d891a35c1663392caryclark void initBounds(const TCurve& ); 12254359294a7c9dc54802d512a5d891a35c1663392caryclark 12354359294a7c9dc54802d512a5d891a35c1663392caryclark bool isBounded() const { 12454359294a7c9dc54802d512a5d891a35c1663392caryclark return fBounded != NULL; 12554359294a7c9dc54802d512a5d891a35c1663392caryclark } 12654359294a7c9dc54802d512a5d891a35c1663392caryclark 1271049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool linearsIntersect(SkTSpan<OppCurve, TCurve>* span); 12854359294a7c9dc54802d512a5d891a35c1663392caryclark double linearT(const SkDPoint& ) const; 12954359294a7c9dc54802d512a5d891a35c1663392caryclark 13054359294a7c9dc54802d512a5d891a35c1663392caryclark void markCoincident() { 13154359294a7c9dc54802d512a5d891a35c1663392caryclark fCoinStart.markCoincident(); 13254359294a7c9dc54802d512a5d891a35c1663392caryclark fCoinEnd.markCoincident(); 13354359294a7c9dc54802d512a5d891a35c1663392caryclark } 13445fa447460f70ec21d22cf4e1531490acfd3c578caryclark 13545fa447460f70ec21d22cf4e1531490acfd3c578caryclark const SkTSpan* next() const { 13645fa447460f70ec21d22cf4e1531490acfd3c578caryclark return fNext; 13745fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 13845fa447460f70ec21d22cf4e1531490acfd3c578caryclark 1391049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool onlyEndPointsInCommon(const SkTSpan<OppCurve, TCurve>* opp, bool* start, 1401049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool* oppStart, bool* ptsInCommon); 14154359294a7c9dc54802d512a5d891a35c1663392caryclark 14245fa447460f70ec21d22cf4e1531490acfd3c578caryclark const TCurve& part() const { 14345fa447460f70ec21d22cf4e1531490acfd3c578caryclark return fPart; 14445fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 14545fa447460f70ec21d22cf4e1531490acfd3c578caryclark 14654359294a7c9dc54802d512a5d891a35c1663392caryclark bool removeAllBounded(); 1471049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool removeBounded(const SkTSpan<OppCurve, TCurve>* opp); 14854359294a7c9dc54802d512a5d891a35c1663392caryclark 14945fa447460f70ec21d22cf4e1531490acfd3c578caryclark void reset() { 15054359294a7c9dc54802d512a5d891a35c1663392caryclark fBounded = NULL; 15154359294a7c9dc54802d512a5d891a35c1663392caryclark } 15254359294a7c9dc54802d512a5d891a35c1663392caryclark 15354359294a7c9dc54802d512a5d891a35c1663392caryclark void resetBounds(const TCurve& curve) { 15454359294a7c9dc54802d512a5d891a35c1663392caryclark fIsLinear = fIsLine = false; 15554359294a7c9dc54802d512a5d891a35c1663392caryclark initBounds(curve); 15645fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 15745fa447460f70ec21d22cf4e1531490acfd3c578caryclark 15854359294a7c9dc54802d512a5d891a35c1663392caryclark bool split(SkTSpan* work, SkChunkAlloc* heap) { 15954359294a7c9dc54802d512a5d891a35c1663392caryclark return splitAt(work, (work->fStartT + work->fEndT) * 0.5, heap); 16045fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 16145fa447460f70ec21d22cf4e1531490acfd3c578caryclark 16254359294a7c9dc54802d512a5d891a35c1663392caryclark bool splitAt(SkTSpan* work, double t, SkChunkAlloc* heap); 16345fa447460f70ec21d22cf4e1531490acfd3c578caryclark 16445fa447460f70ec21d22cf4e1531490acfd3c578caryclark double startT() const { 16545fa447460f70ec21d22cf4e1531490acfd3c578caryclark return fStartT; 16645fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 16745fa447460f70ec21d22cf4e1531490acfd3c578caryclark 16854359294a7c9dc54802d512a5d891a35c1663392caryclarkprivate: 16945fa447460f70ec21d22cf4e1531490acfd3c578caryclark 17045fa447460f70ec21d22cf4e1531490acfd3c578caryclark // implementation is for testing only 17154359294a7c9dc54802d512a5d891a35c1663392caryclark int debugID() const { 17254359294a7c9dc54802d512a5d891a35c1663392caryclark return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1); 17345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 17445fa447460f70ec21d22cf4e1531490acfd3c578caryclark 17554359294a7c9dc54802d512a5d891a35c1663392caryclark void dumpID() const; 17645fa447460f70ec21d22cf4e1531490acfd3c578caryclark 1771049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int hullCheck(const SkTSpan<OppCurve, TCurve>* opp, bool* start, bool* oppStart); 1781049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int linearIntersects(const OppCurve& ) const; 1791049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* oppT(double t) const; 18045fa447460f70ec21d22cf4e1531490acfd3c578caryclark 18145fa447460f70ec21d22cf4e1531490acfd3c578caryclark void validate() const; 18254359294a7c9dc54802d512a5d891a35c1663392caryclark void validateBounded() const; 18354359294a7c9dc54802d512a5d891a35c1663392caryclark void validatePerpT(double oppT) const; 18454359294a7c9dc54802d512a5d891a35c1663392caryclark void validatePerpPt(double t, const SkDPoint& ) const; 18545fa447460f70ec21d22cf4e1531490acfd3c578caryclark 18645fa447460f70ec21d22cf4e1531490acfd3c578caryclark TCurve fPart; 1871049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTCoincident<TCurve, OppCurve> fCoinStart; 1881049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTCoincident<TCurve, OppCurve> fCoinEnd; 1891049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpanBounded<OppCurve, TCurve>* fBounded; 19045fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkTSpan* fPrev; 19145fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkTSpan* fNext; 19245fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkDRect fBounds; 19345fa447460f70ec21d22cf4e1531490acfd3c578caryclark double fStartT; 19445fa447460f70ec21d22cf4e1531490acfd3c578caryclark double fEndT; 19545fa447460f70ec21d22cf4e1531490acfd3c578caryclark double fBoundsMax; 19645fa447460f70ec21d22cf4e1531490acfd3c578caryclark bool fCollapsed; 19745fa447460f70ec21d22cf4e1531490acfd3c578caryclark bool fHasPerp; 19845fa447460f70ec21d22cf4e1531490acfd3c578caryclark bool fIsLinear; 19954359294a7c9dc54802d512a5d891a35c1663392caryclark bool fIsLine; 20054359294a7c9dc54802d512a5d891a35c1663392caryclark bool fDeleted; 2011049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE_(SkTSect<TCurve, OppCurve>* fDebugSect); 20254359294a7c9dc54802d512a5d891a35c1663392caryclark PATH_OPS_DEBUG_T_SECT_CODE(int fID); 2031049f1246e7be4ccb68001361efceb8933e6f81ccaryclark friend class SkTSect<TCurve, OppCurve>; 2041049f1246e7be4ccb68001361efceb8933e6f81ccaryclark friend class SkTSect<OppCurve, TCurve>; 2051049f1246e7be4ccb68001361efceb8933e6f81ccaryclark friend class SkTSpan<OppCurve, TCurve>; 20645fa447460f70ec21d22cf4e1531490acfd3c578caryclark}; 20745fa447460f70ec21d22cf4e1531490acfd3c578caryclark 2081049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 20945fa447460f70ec21d22cf4e1531490acfd3c578caryclarkclass SkTSect { 21045fa447460f70ec21d22cf4e1531490acfd3c578caryclarkpublic: 21154359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSect(const TCurve& c PATH_OPS_DEBUG_T_SECT_PARAMS(int id)); 2121049f1246e7be4ccb68001361efceb8933e6f81ccaryclark static void BinarySearch(SkTSect* sect1, SkTSect<OppCurve, TCurve>* sect2, 2131049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkIntersections* intersections); 21445fa447460f70ec21d22cf4e1531490acfd3c578caryclark 21545fa447460f70ec21d22cf4e1531490acfd3c578caryclark // for testing only 2161049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool debugHasBounded(const SkTSpan<OppCurve, TCurve>* ) const; 21754359294a7c9dc54802d512a5d891a35c1663392caryclark 2181049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSect<OppCurve, TCurve>* debugOpp() const { 2191049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return SkDEBUGRELEASE(fOppSect, NULL); 22054359294a7c9dc54802d512a5d891a35c1663392caryclark } 22154359294a7c9dc54802d512a5d891a35c1663392caryclark 2221049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<TCurve, OppCurve>* debugSpan(int id) const; 2231049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<TCurve, OppCurve>* debugT(double t) const; 22445fa447460f70ec21d22cf4e1531490acfd3c578caryclark void dump() const; 2251049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void dumpBoth(SkTSect<OppCurve, TCurve>* ) const; 2261049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void dumpBounded(int id) const; 2271049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void dumpBounds() const; 22854359294a7c9dc54802d512a5d891a35c1663392caryclark void dumpCoin() const; 22954359294a7c9dc54802d512a5d891a35c1663392caryclark void dumpCoinCurves() const; 23045fa447460f70ec21d22cf4e1531490acfd3c578caryclark void dumpCurves() const; 23145fa447460f70ec21d22cf4e1531490acfd3c578caryclark 23245fa447460f70ec21d22cf4e1531490acfd3c578caryclarkprivate: 23345fa447460f70ec21d22cf4e1531490acfd3c578caryclark enum { 23445fa447460f70ec21d22cf4e1531490acfd3c578caryclark kZeroS1Set = 1, 23545fa447460f70ec21d22cf4e1531490acfd3c578caryclark kOneS1Set = 2, 23645fa447460f70ec21d22cf4e1531490acfd3c578caryclark kZeroS2Set = 4, 23745fa447460f70ec21d22cf4e1531490acfd3c578caryclark kOneS2Set = 8 23845fa447460f70ec21d22cf4e1531490acfd3c578caryclark }; 23945fa447460f70ec21d22cf4e1531490acfd3c578caryclark 2401049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* addFollowing(SkTSpan<TCurve, OppCurve>* prior); 2411049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void addForPerp(SkTSpan<OppCurve, TCurve>* span, double t); 2421049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* addOne(); 24354359294a7c9dc54802d512a5d891a35c1663392caryclark 2441049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* addSplitAt(SkTSpan<TCurve, OppCurve>* span, double t) { 2451049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* result = this->addOne(); 24654359294a7c9dc54802d512a5d891a35c1663392caryclark result->splitAt(span, t, &fHeap); 24754359294a7c9dc54802d512a5d891a35c1663392caryclark result->initBounds(fCurve); 24854359294a7c9dc54802d512a5d891a35c1663392caryclark span->initBounds(fCurve); 24954359294a7c9dc54802d512a5d891a35c1663392caryclark return result; 25054359294a7c9dc54802d512a5d891a35c1663392caryclark } 25154359294a7c9dc54802d512a5d891a35c1663392caryclark 2521049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool binarySearchCoin(SkTSect<OppCurve, TCurve>* , double tStart, double tStep, double* t, 2531049f1246e7be4ccb68001361efceb8933e6f81ccaryclark double* oppT); 2541049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* boundsMax() const; 2551049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void coincidentCheck(SkTSect<OppCurve, TCurve>* sect2); 25654359294a7c9dc54802d512a5d891a35c1663392caryclark bool coincidentHasT(double t); 2571049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int collapsed() const; 2581049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void computePerpendiculars(SkTSect<OppCurve, TCurve>* sect2, SkTSpan<TCurve, OppCurve>* first, 2591049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* last); 2601049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int countConsecutiveSpans(SkTSpan<TCurve, OppCurve>* first, 2611049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>** last) const; 26254359294a7c9dc54802d512a5d891a35c1663392caryclark 26354359294a7c9dc54802d512a5d891a35c1663392caryclark int debugID() const { 26454359294a7c9dc54802d512a5d891a35c1663392caryclark return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1); 26554359294a7c9dc54802d512a5d891a35c1663392caryclark } 26654359294a7c9dc54802d512a5d891a35c1663392caryclark 26754359294a7c9dc54802d512a5d891a35c1663392caryclark void deleteEmptySpans(); 2681049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void dumpCommon(const SkTSpan<TCurve, OppCurve>* ) const; 2691049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void dumpCommonCurves(const SkTSpan<TCurve, OppCurve>* ) const; 2701049f1246e7be4ccb68001361efceb8933e6f81ccaryclark static int EndsEqual(const SkTSect* sect1, const SkTSect<OppCurve, TCurve>* sect2, 2711049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkIntersections* ); 2721049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* extractCoincident(SkTSect<OppCurve, TCurve>* sect2, 2731049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* first, 2741049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* last); 2751049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* findCoincidentRun(SkTSpan<TCurve, OppCurve>* first, 2761049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>** lastPtr); 2771049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int intersects(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp, 2781049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* oppSpan, int* oppResult); 2791049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int linesIntersect(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp, 2801049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* oppSpan, SkIntersections* ); 2811049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void markSpanGone(SkTSpan<TCurve, OppCurve>* span); 2821049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool matchedDirection(double t, const SkTSect<OppCurve, TCurve>* sect2, double t2) const; 2831049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void matchedDirCheck(double t, const SkTSect<OppCurve, TCurve>* sect2, double t2, 28454359294a7c9dc54802d512a5d891a35c1663392caryclark bool* calcMatched, bool* oppMatched) const; 2851049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void mergeCoincidence(SkTSect<OppCurve, TCurve>* sect2); 2861049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* prev(SkTSpan<TCurve, OppCurve>* ) const; 2871049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void removeByPerpendicular(SkTSect<OppCurve, TCurve>* opp); 28845fa447460f70ec21d22cf4e1531490acfd3c578caryclark void recoverCollapsed(); 2891049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void removeCoincident(SkTSpan<TCurve, OppCurve>* span, bool isBetween); 2901049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void removeAllBut(const SkTSpan<OppCurve, TCurve>* keep, SkTSpan<TCurve, OppCurve>* span, 2911049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSect<OppCurve, TCurve>* opp); 2921049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void removeSpan(SkTSpan<TCurve, OppCurve>* span); 2931049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void removeSpanRange(SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last); 2941049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void removeSpans(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp); 2951049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* spanAtT(double t, SkTSpan<TCurve, OppCurve>** priorSpan); 2961049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* tail(); 2971049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void trim(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp); 2981049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void unlinkSpan(SkTSpan<TCurve, OppCurve>* span); 2991049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool updateBounded(SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last, 3001049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* oppFirst); 3010dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed void validate() const; 30254359294a7c9dc54802d512a5d891a35c1663392caryclark void validateBounded() const; 30354359294a7c9dc54802d512a5d891a35c1663392caryclark 30445fa447460f70ec21d22cf4e1531490acfd3c578caryclark const TCurve& fCurve; 30545fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkChunkAlloc fHeap; 3061049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* fHead; 3071049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* fCoincident; 3081049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* fDeleted; 30945fa447460f70ec21d22cf4e1531490acfd3c578caryclark int fActiveCount; 3101049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE_(SkTSect<OppCurve, TCurve>* fOppSect); 31154359294a7c9dc54802d512a5d891a35c1663392caryclark PATH_OPS_DEBUG_T_SECT_CODE(int fID); 31254359294a7c9dc54802d512a5d891a35c1663392caryclark PATH_OPS_DEBUG_T_SECT_CODE(int fDebugCount); 31345fa447460f70ec21d22cf4e1531490acfd3c578caryclark#if DEBUG_T_SECT 31445fa447460f70ec21d22cf4e1531490acfd3c578caryclark int fDebugAllocatedCount; 31545fa447460f70ec21d22cf4e1531490acfd3c578caryclark#endif 3161049f1246e7be4ccb68001361efceb8933e6f81ccaryclark friend class SkTSpan<TCurve, OppCurve>; 3171049f1246e7be4ccb68001361efceb8933e6f81ccaryclark friend class SkTSpan<OppCurve, TCurve>; 3181049f1246e7be4ccb68001361efceb8933e6f81ccaryclark friend class SkTSect<OppCurve, TCurve>; 31945fa447460f70ec21d22cf4e1531490acfd3c578caryclark}; 32045fa447460f70ec21d22cf4e1531490acfd3c578caryclark 32145fa447460f70ec21d22cf4e1531490acfd3c578caryclark#define COINCIDENT_SPAN_COUNT 9 32245fa447460f70ec21d22cf4e1531490acfd3c578caryclark 3231049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 3241049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTCoincident<TCurve, OppCurve>::setPerp(const TCurve& c1, double t, 3251049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkDPoint& cPt, const OppCurve& c2) { 32645fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkDVector dxdy = c1.dxdyAtT(t); 32745fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }}; 32845fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkIntersections i; 32945fa447460f70ec21d22cf4e1531490acfd3c578caryclark int used = i.intersectRay(c2, perp); 33045fa447460f70ec21d22cf4e1531490acfd3c578caryclark // only keep closest 33154359294a7c9dc54802d512a5d891a35c1663392caryclark if (used == 0 || used == 3) { 33254359294a7c9dc54802d512a5d891a35c1663392caryclark this->clear(); 33345fa447460f70ec21d22cf4e1531490acfd3c578caryclark return; 33445fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 33545fa447460f70ec21d22cf4e1531490acfd3c578caryclark fPerpT = i[0][0]; 33645fa447460f70ec21d22cf4e1531490acfd3c578caryclark fPerpPt = i.pt(0); 33745fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkASSERT(used <= 2); 33845fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (used == 2) { 33945fa447460f70ec21d22cf4e1531490acfd3c578caryclark double distSq = (fPerpPt - cPt).lengthSquared(); 34045fa447460f70ec21d22cf4e1531490acfd3c578caryclark double dist2Sq = (i.pt(1) - cPt).lengthSquared(); 34145fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (dist2Sq < distSq) { 34245fa447460f70ec21d22cf4e1531490acfd3c578caryclark fPerpT = i[0][1]; 34345fa447460f70ec21d22cf4e1531490acfd3c578caryclark fPerpPt = i.pt(1); 34445fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 34545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 34654359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_T_SECT 3471049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDebugf("setPerp t=%1.9g cPt=(%1.9g,%1.9g) %s oppT=%1.9g fPerpPt=(%1.9g,%1.9g)\n", 3481049f1246e7be4ccb68001361efceb8933e6f81ccaryclark t, cPt.fX, cPt.fY, 3491049f1246e7be4ccb68001361efceb8933e6f81ccaryclark cPt.approximatelyEqual(fPerpPt) ? "==" : "!=", fPerpT, fPerpPt.fX, fPerpPt.fY); 35054359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 35145fa447460f70ec21d22cf4e1531490acfd3c578caryclark fCoincident = cPt.approximatelyEqual(fPerpPt); 35245fa447460f70ec21d22cf4e1531490acfd3c578caryclark#if DEBUG_T_SECT 35345fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (fCoincident) { 35445fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkDebugf(""); // allow setting breakpoint 35545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 35645fa447460f70ec21d22cf4e1531490acfd3c578caryclark#endif 35745fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 35845fa447460f70ec21d22cf4e1531490acfd3c578caryclark 3591049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 3601049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSpan<TCurve, OppCurve>::addBounded(SkTSpan<OppCurve, TCurve>* span, SkChunkAlloc* heap) { 3611049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpanBounded<OppCurve, TCurve>* bounded = SkNEW_PLACEMENT(heap->allocThrow( 3621049f1246e7be4ccb68001361efceb8933e6f81ccaryclark sizeof(SkTSpanBounded<OppCurve, TCurve>)), (SkTSpanBounded<OppCurve, TCurve>)); 36354359294a7c9dc54802d512a5d891a35c1663392caryclark bounded->fBounded = span; 36454359294a7c9dc54802d512a5d891a35c1663392caryclark bounded->fNext = fBounded; 36554359294a7c9dc54802d512a5d891a35c1663392caryclark fBounded = bounded; 36645fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 36745fa447460f70ec21d22cf4e1531490acfd3c578caryclark 3681049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 3691049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkSkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::addFollowing( 3701049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* prior) { 3711049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* result = this->addOne(); 37254359294a7c9dc54802d512a5d891a35c1663392caryclark result->fStartT = prior ? prior->fEndT : 0; 3731049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* next = prior ? prior->fNext : fHead; 37454359294a7c9dc54802d512a5d891a35c1663392caryclark result->fEndT = next ? next->fStartT : 1; 37554359294a7c9dc54802d512a5d891a35c1663392caryclark result->fPrev = prior; 37654359294a7c9dc54802d512a5d891a35c1663392caryclark result->fNext = next; 37754359294a7c9dc54802d512a5d891a35c1663392caryclark if (prior) { 37854359294a7c9dc54802d512a5d891a35c1663392caryclark prior->fNext = result; 37954359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 38054359294a7c9dc54802d512a5d891a35c1663392caryclark fHead = result; 38154359294a7c9dc54802d512a5d891a35c1663392caryclark } 38254359294a7c9dc54802d512a5d891a35c1663392caryclark if (next) { 38354359294a7c9dc54802d512a5d891a35c1663392caryclark next->fPrev = result; 384ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 38554359294a7c9dc54802d512a5d891a35c1663392caryclark result->resetBounds(fCurve); 38654359294a7c9dc54802d512a5d891a35c1663392caryclark return result; 38754359294a7c9dc54802d512a5d891a35c1663392caryclark} 38854359294a7c9dc54802d512a5d891a35c1663392caryclark 3891049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 3901049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::addForPerp(SkTSpan<OppCurve, TCurve>* span, double t) { 39154359294a7c9dc54802d512a5d891a35c1663392caryclark if (!span->hasOppT(t)) { 3921049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* priorSpan; 3931049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* opp = this->spanAtT(t, &priorSpan); 39454359294a7c9dc54802d512a5d891a35c1663392caryclark if (!opp) { 39554359294a7c9dc54802d512a5d891a35c1663392caryclark opp = this->addFollowing(priorSpan); 39654359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_PERP 39754359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s priorSpan=%d t=%1.9g opp=%d\n", __FUNCTION__, priorSpan->debugID(), t, 39854359294a7c9dc54802d512a5d891a35c1663392caryclark opp->debugID()); 39954359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 40054359294a7c9dc54802d512a5d891a35c1663392caryclark } 40154359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_PERP 40254359294a7c9dc54802d512a5d891a35c1663392caryclark opp->dump(); SkDebugf("\n"); 40354359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s addBounded span=%d opp=%d\n", __FUNCTION__, priorSpan->debugID(), 40454359294a7c9dc54802d512a5d891a35c1663392caryclark opp->debugID()); 40545fa447460f70ec21d22cf4e1531490acfd3c578caryclark#endif 40654359294a7c9dc54802d512a5d891a35c1663392caryclark opp->addBounded(span, &fHeap); 40754359294a7c9dc54802d512a5d891a35c1663392caryclark span->addBounded(opp, &fHeap); 40854359294a7c9dc54802d512a5d891a35c1663392caryclark } 40954359294a7c9dc54802d512a5d891a35c1663392caryclark this->validate(); 4101049f1246e7be4ccb68001361efceb8933e6f81ccaryclark#if DEBUG_T_SECT 41154359294a7c9dc54802d512a5d891a35c1663392caryclark span->validatePerpT(t); 4121049f1246e7be4ccb68001361efceb8933e6f81ccaryclark#endif 41345fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 41445fa447460f70ec21d22cf4e1531490acfd3c578caryclark 4151049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 4161049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkdouble SkTSpan<TCurve, OppCurve>::closestBoundedT(const SkDPoint& pt) const { 41745fa447460f70ec21d22cf4e1531490acfd3c578caryclark double result = -1; 41845fa447460f70ec21d22cf4e1531490acfd3c578caryclark double closest = FLT_MAX; 4191049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded; 42054359294a7c9dc54802d512a5d891a35c1663392caryclark while (testBounded) { 4211049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<OppCurve, TCurve>* test = testBounded->fBounded; 42245fa447460f70ec21d22cf4e1531490acfd3c578caryclark double startDist = test->fPart[0].distanceSquared(pt); 42345fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (closest > startDist) { 42445fa447460f70ec21d22cf4e1531490acfd3c578caryclark closest = startDist; 42545fa447460f70ec21d22cf4e1531490acfd3c578caryclark result = test->fStartT; 42645fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 4271049f1246e7be4ccb68001361efceb8933e6f81ccaryclark double endDist = test->fPart[OppCurve::kPointLast].distanceSquared(pt); 42845fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (closest > endDist) { 42945fa447460f70ec21d22cf4e1531490acfd3c578caryclark closest = endDist; 43045fa447460f70ec21d22cf4e1531490acfd3c578caryclark result = test->fEndT; 43145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 43254359294a7c9dc54802d512a5d891a35c1663392caryclark testBounded = testBounded->fNext; 43345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 43445fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkASSERT(between(0, result, 1)); 43545fa447460f70ec21d22cf4e1531490acfd3c578caryclark return result; 43645fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 43745fa447460f70ec21d22cf4e1531490acfd3c578caryclark 43854359294a7c9dc54802d512a5d891a35c1663392caryclark#ifdef SK_DEBUG 4391049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 4401049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkbool SkTSpan<TCurve, OppCurve>::debugIsBefore(const SkTSpan* span) const { 44154359294a7c9dc54802d512a5d891a35c1663392caryclark const SkTSpan* work = this; 44254359294a7c9dc54802d512a5d891a35c1663392caryclark do { 44354359294a7c9dc54802d512a5d891a35c1663392caryclark if (span == work) { 44445fa447460f70ec21d22cf4e1531490acfd3c578caryclark return true; 44545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 44654359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((work = work->fNext)); 44745fa447460f70ec21d22cf4e1531490acfd3c578caryclark return false; 44845fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 44954359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 45045fa447460f70ec21d22cf4e1531490acfd3c578caryclark 4511049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 4521049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkbool SkTSpan<TCurve, OppCurve>::contains(double t) const { 45354359294a7c9dc54802d512a5d891a35c1663392caryclark const SkTSpan* work = this; 45445fa447460f70ec21d22cf4e1531490acfd3c578caryclark do { 45545fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (between(work->fStartT, t, work->fEndT)) { 45654359294a7c9dc54802d512a5d891a35c1663392caryclark return true; 45745fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 45845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } while ((work = work->fNext)); 45954359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 46054359294a7c9dc54802d512a5d891a35c1663392caryclark} 46154359294a7c9dc54802d512a5d891a35c1663392caryclark 4621049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 4631049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkconst SkTSect<OppCurve, TCurve>* SkTSpan<TCurve, OppCurve>::debugOpp() const { 4641049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return SkDEBUGRELEASE(fDebugSect->debugOpp(), NULL); 46554359294a7c9dc54802d512a5d891a35c1663392caryclark} 46654359294a7c9dc54802d512a5d891a35c1663392caryclark 4671049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 4681049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkSkTSpan<OppCurve, TCurve>* SkTSpan<TCurve, OppCurve>::findOppSpan( 4691049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<OppCurve, TCurve>* opp) const { 4701049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded; 47154359294a7c9dc54802d512a5d891a35c1663392caryclark while (bounded) { 4721049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* test = bounded->fBounded; 47354359294a7c9dc54802d512a5d891a35c1663392caryclark if (opp == test) { 47454359294a7c9dc54802d512a5d891a35c1663392caryclark return test; 47554359294a7c9dc54802d512a5d891a35c1663392caryclark } 47654359294a7c9dc54802d512a5d891a35c1663392caryclark bounded = bounded->fNext; 47754359294a7c9dc54802d512a5d891a35c1663392caryclark } 47845fa447460f70ec21d22cf4e1531490acfd3c578caryclark return NULL; 47945fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 48045fa447460f70ec21d22cf4e1531490acfd3c578caryclark 48154359294a7c9dc54802d512a5d891a35c1663392caryclark// returns 0 if no hull intersection 48254359294a7c9dc54802d512a5d891a35c1663392caryclark// 1 if hulls intersect 48354359294a7c9dc54802d512a5d891a35c1663392caryclark// 2 if hulls only share a common endpoint 48454359294a7c9dc54802d512a5d891a35c1663392caryclark// -1 if linear and further checking is required 4851049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 4861049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkint SkTSpan<TCurve, OppCurve>::hullCheck(const SkTSpan<OppCurve, TCurve>* opp, 4871049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool* start, bool* oppStart) { 48854359294a7c9dc54802d512a5d891a35c1663392caryclark if (fIsLinear) { 48954359294a7c9dc54802d512a5d891a35c1663392caryclark return -1; 49054359294a7c9dc54802d512a5d891a35c1663392caryclark } 49154359294a7c9dc54802d512a5d891a35c1663392caryclark bool ptsInCommon; 49254359294a7c9dc54802d512a5d891a35c1663392caryclark if (onlyEndPointsInCommon(opp, start, oppStart, &ptsInCommon)) { 49354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(ptsInCommon); 49454359294a7c9dc54802d512a5d891a35c1663392caryclark return 2; 49554359294a7c9dc54802d512a5d891a35c1663392caryclark } 49654359294a7c9dc54802d512a5d891a35c1663392caryclark bool linear; 49754359294a7c9dc54802d512a5d891a35c1663392caryclark if (fPart.hullIntersects(opp->fPart, &linear)) { 49854359294a7c9dc54802d512a5d891a35c1663392caryclark if (!linear) { // check set true if linear 49954359294a7c9dc54802d512a5d891a35c1663392caryclark return 1; 50054359294a7c9dc54802d512a5d891a35c1663392caryclark } 50154359294a7c9dc54802d512a5d891a35c1663392caryclark fIsLinear = true; 50254359294a7c9dc54802d512a5d891a35c1663392caryclark fIsLine = fPart.controlsInside(); 50354359294a7c9dc54802d512a5d891a35c1663392caryclark return ptsInCommon ? 2 : -1; 50454359294a7c9dc54802d512a5d891a35c1663392caryclark } else { // hull is not linear; check set true if intersected at the end points 50554359294a7c9dc54802d512a5d891a35c1663392caryclark return ((int) ptsInCommon) << 1; // 0 or 2 50654359294a7c9dc54802d512a5d891a35c1663392caryclark } 50754359294a7c9dc54802d512a5d891a35c1663392caryclark return 0; 50854359294a7c9dc54802d512a5d891a35c1663392caryclark} 50954359294a7c9dc54802d512a5d891a35c1663392caryclark 51045fa447460f70ec21d22cf4e1531490acfd3c578caryclark// OPTIMIZE ? If at_most_end_pts_in_common detects that one quad is near linear, 51145fa447460f70ec21d22cf4e1531490acfd3c578caryclark// use line intersection to guess a better split than 0.5 51245fa447460f70ec21d22cf4e1531490acfd3c578caryclark// OPTIMIZE Once at_most_end_pts_in_common detects linear, mark span so all future splits are linear 5131049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 5141049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkint SkTSpan<TCurve, OppCurve>::hullsIntersect(SkTSpan<OppCurve, TCurve>* opp, 5151049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool* start, bool* oppStart) { 51654359294a7c9dc54802d512a5d891a35c1663392caryclark if (!fBounds.intersects(opp->fBounds)) { 51754359294a7c9dc54802d512a5d891a35c1663392caryclark return 0; 51845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 51954359294a7c9dc54802d512a5d891a35c1663392caryclark int hullSect = this->hullCheck(opp, start, oppStart); 52054359294a7c9dc54802d512a5d891a35c1663392caryclark if (hullSect >= 0) { 52154359294a7c9dc54802d512a5d891a35c1663392caryclark return hullSect; 522ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 52354359294a7c9dc54802d512a5d891a35c1663392caryclark hullSect = opp->hullCheck(this, oppStart, start); 52454359294a7c9dc54802d512a5d891a35c1663392caryclark if (hullSect >= 0) { 52554359294a7c9dc54802d512a5d891a35c1663392caryclark return hullSect; 52654359294a7c9dc54802d512a5d891a35c1663392caryclark } 52754359294a7c9dc54802d512a5d891a35c1663392caryclark return -1; 52854359294a7c9dc54802d512a5d891a35c1663392caryclark} 52954359294a7c9dc54802d512a5d891a35c1663392caryclark 5301049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 5311049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSpan<TCurve, OppCurve>::init(const TCurve& c) { 53254359294a7c9dc54802d512a5d891a35c1663392caryclark fPrev = fNext = NULL; 53354359294a7c9dc54802d512a5d891a35c1663392caryclark fStartT = 0; 53454359294a7c9dc54802d512a5d891a35c1663392caryclark fEndT = 1; 53554359294a7c9dc54802d512a5d891a35c1663392caryclark fBounded = NULL; 53654359294a7c9dc54802d512a5d891a35c1663392caryclark resetBounds(c); 53754359294a7c9dc54802d512a5d891a35c1663392caryclark} 53854359294a7c9dc54802d512a5d891a35c1663392caryclark 5391049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 5401049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSpan<TCurve, OppCurve>::initBounds(const TCurve& c) { 54154359294a7c9dc54802d512a5d891a35c1663392caryclark fPart = c.subDivide(fStartT, fEndT); 54254359294a7c9dc54802d512a5d891a35c1663392caryclark fBounds.setBounds(fPart); 54354359294a7c9dc54802d512a5d891a35c1663392caryclark fCoinStart.init(); 54454359294a7c9dc54802d512a5d891a35c1663392caryclark fCoinEnd.init(); 54554359294a7c9dc54802d512a5d891a35c1663392caryclark fBoundsMax = SkTMax(fBounds.width(), fBounds.height()); 54654359294a7c9dc54802d512a5d891a35c1663392caryclark fCollapsed = fPart.collapsed(); 54754359294a7c9dc54802d512a5d891a35c1663392caryclark fHasPerp = false; 54854359294a7c9dc54802d512a5d891a35c1663392caryclark fDeleted = false; 54954359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_T_SECT 55054359294a7c9dc54802d512a5d891a35c1663392caryclark if (fCollapsed) { 55154359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf(""); // for convenient breakpoints 55245fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 55354359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 55454359294a7c9dc54802d512a5d891a35c1663392caryclark} 55554359294a7c9dc54802d512a5d891a35c1663392caryclark 5561049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 5571049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkbool SkTSpan<TCurve, OppCurve>::linearsIntersect(SkTSpan<OppCurve, TCurve>* span) { 55854359294a7c9dc54802d512a5d891a35c1663392caryclark int result = this->linearIntersects(span->fPart); 55954359294a7c9dc54802d512a5d891a35c1663392caryclark if (result <= 1) { 56054359294a7c9dc54802d512a5d891a35c1663392caryclark return SkToBool(result); 56154359294a7c9dc54802d512a5d891a35c1663392caryclark } 56254359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(span->fIsLinear); 56354359294a7c9dc54802d512a5d891a35c1663392caryclark result = span->linearIntersects(this->fPart); 56454359294a7c9dc54802d512a5d891a35c1663392caryclark// SkASSERT(result <= 1); 56554359294a7c9dc54802d512a5d891a35c1663392caryclark return SkToBool(result); 56654359294a7c9dc54802d512a5d891a35c1663392caryclark} 56754359294a7c9dc54802d512a5d891a35c1663392caryclark 5681049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 5691049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkdouble SkTSpan<TCurve, OppCurve>::linearT(const SkDPoint& pt) const { 57054359294a7c9dc54802d512a5d891a35c1663392caryclark SkDVector len = fPart[TCurve::kPointLast] - fPart[0]; 57154359294a7c9dc54802d512a5d891a35c1663392caryclark return fabs(len.fX) > fabs(len.fY) 57254359294a7c9dc54802d512a5d891a35c1663392caryclark ? (pt.fX - fPart[0].fX) / len.fX 57354359294a7c9dc54802d512a5d891a35c1663392caryclark : (pt.fY - fPart[0].fY) / len.fY; 57445fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 57545fa447460f70ec21d22cf4e1531490acfd3c578caryclark 5761049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 5771049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkint SkTSpan<TCurve, OppCurve>::linearIntersects(const OppCurve& q2) const { 57845fa447460f70ec21d22cf4e1531490acfd3c578caryclark // looks like q1 is near-linear 57954359294a7c9dc54802d512a5d891a35c1663392caryclark int start = 0, end = TCurve::kPointLast; // the outside points are usually the extremes 58045fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (!fPart.controlsInside()) { 58145fa447460f70ec21d22cf4e1531490acfd3c578caryclark double dist = 0; // if there's any question, compute distance to find best outsiders 58245fa447460f70ec21d22cf4e1531490acfd3c578caryclark for (int outer = 0; outer < TCurve::kPointCount - 1; ++outer) { 58345fa447460f70ec21d22cf4e1531490acfd3c578caryclark for (int inner = outer + 1; inner < TCurve::kPointCount; ++inner) { 58445fa447460f70ec21d22cf4e1531490acfd3c578caryclark double test = (fPart[outer] - fPart[inner]).lengthSquared(); 58545fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (dist > test) { 58645fa447460f70ec21d22cf4e1531490acfd3c578caryclark continue; 58745fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 58845fa447460f70ec21d22cf4e1531490acfd3c578caryclark dist = test; 58945fa447460f70ec21d22cf4e1531490acfd3c578caryclark start = outer; 59045fa447460f70ec21d22cf4e1531490acfd3c578caryclark end = inner; 59145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 59245fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 59345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 59445fa447460f70ec21d22cf4e1531490acfd3c578caryclark // see if q2 is on one side of the line formed by the extreme points 59545fa447460f70ec21d22cf4e1531490acfd3c578caryclark double origX = fPart[start].fX; 59645fa447460f70ec21d22cf4e1531490acfd3c578caryclark double origY = fPart[start].fY; 59745fa447460f70ec21d22cf4e1531490acfd3c578caryclark double adj = fPart[end].fX - origX; 59845fa447460f70ec21d22cf4e1531490acfd3c578caryclark double opp = fPart[end].fY - origY; 59954359294a7c9dc54802d512a5d891a35c1663392caryclark double maxPart = SkTMax(fabs(adj), fabs(opp)); 60054359294a7c9dc54802d512a5d891a35c1663392caryclark double sign = 0; // initialization to shut up warning in release build 6011049f1246e7be4ccb68001361efceb8933e6f81ccaryclark for (int n = 0; n < OppCurve::kPointCount; ++n) { 60254359294a7c9dc54802d512a5d891a35c1663392caryclark double dx = q2[n].fY - origY; 60354359294a7c9dc54802d512a5d891a35c1663392caryclark double dy = q2[n].fX - origX; 60454359294a7c9dc54802d512a5d891a35c1663392caryclark double maxVal = SkTMax(maxPart, SkTMax(fabs(dx), fabs(dy))); 60545fa447460f70ec21d22cf4e1531490acfd3c578caryclark double test = (q2[n].fY - origY) * adj - (q2[n].fX - origX) * opp; 60654359294a7c9dc54802d512a5d891a35c1663392caryclark if (precisely_zero_when_compared_to(test, maxVal)) { 60754359294a7c9dc54802d512a5d891a35c1663392caryclark return 1; 60854359294a7c9dc54802d512a5d891a35c1663392caryclark } 60954359294a7c9dc54802d512a5d891a35c1663392caryclark if (approximately_zero_when_compared_to(test, maxVal)) { 61054359294a7c9dc54802d512a5d891a35c1663392caryclark return 3; 61145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 61245fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (n == 0) { 61345fa447460f70ec21d22cf4e1531490acfd3c578caryclark sign = test; 61445fa447460f70ec21d22cf4e1531490acfd3c578caryclark continue; 61545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 61645fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (test * sign < 0) { 61754359294a7c9dc54802d512a5d891a35c1663392caryclark return 1; 61854359294a7c9dc54802d512a5d891a35c1663392caryclark } 61954359294a7c9dc54802d512a5d891a35c1663392caryclark } 62054359294a7c9dc54802d512a5d891a35c1663392caryclark return 0; 62154359294a7c9dc54802d512a5d891a35c1663392caryclark} 62254359294a7c9dc54802d512a5d891a35c1663392caryclark 6231049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 6241049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkbool SkTSpan<TCurve, OppCurve>::onlyEndPointsInCommon(const SkTSpan<OppCurve, TCurve>* opp, 6251049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool* start, bool* oppStart, bool* ptsInCommon) { 62654359294a7c9dc54802d512a5d891a35c1663392caryclark if (opp->fPart[0] == fPart[0]) { 62754359294a7c9dc54802d512a5d891a35c1663392caryclark *start = *oppStart = true; 62854359294a7c9dc54802d512a5d891a35c1663392caryclark } else if (opp->fPart[0] == fPart[TCurve::kPointLast]) { 62954359294a7c9dc54802d512a5d891a35c1663392caryclark *start = false; 63054359294a7c9dc54802d512a5d891a35c1663392caryclark *oppStart = true; 6311049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } else if (opp->fPart[OppCurve::kPointLast] == fPart[0]) { 63254359294a7c9dc54802d512a5d891a35c1663392caryclark *start = true; 63354359294a7c9dc54802d512a5d891a35c1663392caryclark *oppStart = false; 6341049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } else if (opp->fPart[OppCurve::kPointLast] == fPart[TCurve::kPointLast]) { 63554359294a7c9dc54802d512a5d891a35c1663392caryclark *start = *oppStart = false; 63654359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 63754359294a7c9dc54802d512a5d891a35c1663392caryclark *ptsInCommon = false; 63854359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 63954359294a7c9dc54802d512a5d891a35c1663392caryclark } 64054359294a7c9dc54802d512a5d891a35c1663392caryclark *ptsInCommon = true; 6411049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkDPoint* otherPts[TCurve::kPointCount - 1], * oppOtherPts[OppCurve::kPointCount - 1]; 64254359294a7c9dc54802d512a5d891a35c1663392caryclark int baseIndex = *start ? 0 : TCurve::kPointLast; 6431049f1246e7be4ccb68001361efceb8933e6f81ccaryclark fPart.otherPts(baseIndex, otherPts); 6441049f1246e7be4ccb68001361efceb8933e6f81ccaryclark opp->fPart.otherPts(*oppStart ? 0 : OppCurve::kPointLast, oppOtherPts); 64554359294a7c9dc54802d512a5d891a35c1663392caryclark const SkDPoint& base = fPart[baseIndex]; 6461049f1246e7be4ccb68001361efceb8933e6f81ccaryclark for (int o1 = 0; o1 < (int) SK_ARRAY_COUNT(otherPts); ++o1) { 6471049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDVector v1 = *otherPts[o1] - base; 6481049f1246e7be4ccb68001361efceb8933e6f81ccaryclark for (int o2 = 0; o2 < (int) SK_ARRAY_COUNT(oppOtherPts); ++o2) { 6491049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDVector v2 = *oppOtherPts[o2] - base; 65054359294a7c9dc54802d512a5d891a35c1663392caryclark if (v2.dot(v1) >= 0) { 65154359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 65254359294a7c9dc54802d512a5d891a35c1663392caryclark } 65354359294a7c9dc54802d512a5d891a35c1663392caryclark } 65454359294a7c9dc54802d512a5d891a35c1663392caryclark } 65554359294a7c9dc54802d512a5d891a35c1663392caryclark return true; 65654359294a7c9dc54802d512a5d891a35c1663392caryclark} 65754359294a7c9dc54802d512a5d891a35c1663392caryclark 6581049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 6591049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkSkTSpan<OppCurve, TCurve>* SkTSpan<TCurve, OppCurve>::oppT(double t) const { 6601049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded; 66154359294a7c9dc54802d512a5d891a35c1663392caryclark while (bounded) { 6621049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* test = bounded->fBounded; 66354359294a7c9dc54802d512a5d891a35c1663392caryclark if (between(test->fStartT, t, test->fEndT)) { 66454359294a7c9dc54802d512a5d891a35c1663392caryclark return test; 66554359294a7c9dc54802d512a5d891a35c1663392caryclark } 66654359294a7c9dc54802d512a5d891a35c1663392caryclark bounded = bounded->fNext; 66754359294a7c9dc54802d512a5d891a35c1663392caryclark } 66854359294a7c9dc54802d512a5d891a35c1663392caryclark return NULL; 66954359294a7c9dc54802d512a5d891a35c1663392caryclark} 67054359294a7c9dc54802d512a5d891a35c1663392caryclark 6711049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 6721049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkbool SkTSpan<TCurve, OppCurve>::removeAllBounded() { 67354359294a7c9dc54802d512a5d891a35c1663392caryclark bool deleteSpan = false; 6741049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded; 67554359294a7c9dc54802d512a5d891a35c1663392caryclark while (bounded) { 6761049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* opp = bounded->fBounded; 67754359294a7c9dc54802d512a5d891a35c1663392caryclark deleteSpan |= opp->removeBounded(this); 67854359294a7c9dc54802d512a5d891a35c1663392caryclark bounded = bounded->fNext; 67954359294a7c9dc54802d512a5d891a35c1663392caryclark } 68054359294a7c9dc54802d512a5d891a35c1663392caryclark return deleteSpan; 68154359294a7c9dc54802d512a5d891a35c1663392caryclark} 68254359294a7c9dc54802d512a5d891a35c1663392caryclark 6831049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 6841049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkbool SkTSpan<TCurve, OppCurve>::removeBounded(const SkTSpan<OppCurve, TCurve>* opp) { 68554359294a7c9dc54802d512a5d891a35c1663392caryclark if (fHasPerp) { 68654359294a7c9dc54802d512a5d891a35c1663392caryclark bool foundStart = false; 68754359294a7c9dc54802d512a5d891a35c1663392caryclark bool foundEnd = false; 6881049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded; 68954359294a7c9dc54802d512a5d891a35c1663392caryclark while (bounded) { 6901049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* test = bounded->fBounded; 69154359294a7c9dc54802d512a5d891a35c1663392caryclark if (opp != test) { 69254359294a7c9dc54802d512a5d891a35c1663392caryclark foundStart |= between(test->fStartT, fCoinStart.perpT(), test->fEndT); 69354359294a7c9dc54802d512a5d891a35c1663392caryclark foundEnd |= between(test->fStartT, fCoinEnd.perpT(), test->fEndT); 69454359294a7c9dc54802d512a5d891a35c1663392caryclark } 69554359294a7c9dc54802d512a5d891a35c1663392caryclark bounded = bounded->fNext; 69654359294a7c9dc54802d512a5d891a35c1663392caryclark } 69754359294a7c9dc54802d512a5d891a35c1663392caryclark if (!foundStart || !foundEnd) { 69854359294a7c9dc54802d512a5d891a35c1663392caryclark fHasPerp = false; 69954359294a7c9dc54802d512a5d891a35c1663392caryclark fCoinStart.init(); 70054359294a7c9dc54802d512a5d891a35c1663392caryclark fCoinEnd.init(); 70154359294a7c9dc54802d512a5d891a35c1663392caryclark } 70254359294a7c9dc54802d512a5d891a35c1663392caryclark } 7031049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded; 7041049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpanBounded<OppCurve, TCurve>* prev = NULL; 70554359294a7c9dc54802d512a5d891a35c1663392caryclark while (bounded) { 7061049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpanBounded<OppCurve, TCurve>* boundedNext = bounded->fNext; 70754359294a7c9dc54802d512a5d891a35c1663392caryclark if (opp == bounded->fBounded) { 70854359294a7c9dc54802d512a5d891a35c1663392caryclark if (prev) { 70954359294a7c9dc54802d512a5d891a35c1663392caryclark prev->fNext = boundedNext; 71054359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 71154359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 71254359294a7c9dc54802d512a5d891a35c1663392caryclark fBounded = boundedNext; 71354359294a7c9dc54802d512a5d891a35c1663392caryclark return fBounded == NULL; 71454359294a7c9dc54802d512a5d891a35c1663392caryclark } 71545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 71654359294a7c9dc54802d512a5d891a35c1663392caryclark prev = bounded; 71754359294a7c9dc54802d512a5d891a35c1663392caryclark bounded = boundedNext; 71845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 71954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(0); 72045fa447460f70ec21d22cf4e1531490acfd3c578caryclark return false; 72145fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 72245fa447460f70ec21d22cf4e1531490acfd3c578caryclark 7231049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 7241049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkbool SkTSpan<TCurve, OppCurve>::splitAt(SkTSpan* work, double t, SkChunkAlloc* heap) { 72545fa447460f70ec21d22cf4e1531490acfd3c578caryclark fStartT = t; 72645fa447460f70ec21d22cf4e1531490acfd3c578caryclark fEndT = work->fEndT; 72745fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (fStartT == fEndT) { 72845fa447460f70ec21d22cf4e1531490acfd3c578caryclark fCollapsed = true; 72945fa447460f70ec21d22cf4e1531490acfd3c578caryclark return false; 73045fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 73145fa447460f70ec21d22cf4e1531490acfd3c578caryclark work->fEndT = t; 73245fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (work->fStartT == work->fEndT) { 73345fa447460f70ec21d22cf4e1531490acfd3c578caryclark work->fCollapsed = true; 73445fa447460f70ec21d22cf4e1531490acfd3c578caryclark return false; 73545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 73645fa447460f70ec21d22cf4e1531490acfd3c578caryclark fPrev = work; 73745fa447460f70ec21d22cf4e1531490acfd3c578caryclark fNext = work->fNext; 73845fa447460f70ec21d22cf4e1531490acfd3c578caryclark fIsLinear = work->fIsLinear; 73954359294a7c9dc54802d512a5d891a35c1663392caryclark fIsLine = work->fIsLine; 74054359294a7c9dc54802d512a5d891a35c1663392caryclark 74145fa447460f70ec21d22cf4e1531490acfd3c578caryclark work->fNext = this; 74245fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (fNext) { 74345fa447460f70ec21d22cf4e1531490acfd3c578caryclark fNext->fPrev = this; 74445fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 7451049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpanBounded<OppCurve, TCurve>* bounded = work->fBounded; 74654359294a7c9dc54802d512a5d891a35c1663392caryclark fBounded = NULL; 74754359294a7c9dc54802d512a5d891a35c1663392caryclark while (bounded) { 74854359294a7c9dc54802d512a5d891a35c1663392caryclark this->addBounded(bounded->fBounded, heap); 74954359294a7c9dc54802d512a5d891a35c1663392caryclark bounded = bounded->fNext; 75054359294a7c9dc54802d512a5d891a35c1663392caryclark } 75154359294a7c9dc54802d512a5d891a35c1663392caryclark bounded = fBounded; 75254359294a7c9dc54802d512a5d891a35c1663392caryclark while (bounded) { 75354359294a7c9dc54802d512a5d891a35c1663392caryclark bounded->fBounded->addBounded(this, heap); 75454359294a7c9dc54802d512a5d891a35c1663392caryclark bounded = bounded->fNext; 75545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 75645fa447460f70ec21d22cf4e1531490acfd3c578caryclark return true; 75745fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 75845fa447460f70ec21d22cf4e1531490acfd3c578caryclark 7591049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 7601049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSpan<TCurve, OppCurve>::validate() const { 76154359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_T_SECT 76254359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(fNext == NULL || fNext != fPrev); 76354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(fNext == NULL || this == fNext->fPrev); 76454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(fPrev == NULL || this == fPrev->fNext); 76554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(fBounds.width() || fBounds.height() || fCollapsed); 76654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(fBoundsMax == SkTMax(fBounds.width(), fBounds.height())); 76754359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(0 <= fStartT); 76854359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(fEndT <= 1); 76954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(fStartT <= fEndT); 77054359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(fBounded); 77154359294a7c9dc54802d512a5d891a35c1663392caryclark this->validateBounded(); 77254359294a7c9dc54802d512a5d891a35c1663392caryclark if (fHasPerp) { 77354359294a7c9dc54802d512a5d891a35c1663392caryclark if (fCoinStart.isCoincident()) { 77454359294a7c9dc54802d512a5d891a35c1663392caryclark validatePerpT(fCoinStart.perpT()); 77554359294a7c9dc54802d512a5d891a35c1663392caryclark validatePerpPt(fCoinStart.perpT(), fCoinStart.perpPt()); 776ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 77754359294a7c9dc54802d512a5d891a35c1663392caryclark if (fCoinEnd.isCoincident()) { 77854359294a7c9dc54802d512a5d891a35c1663392caryclark validatePerpT(fCoinEnd.perpT()); 77954359294a7c9dc54802d512a5d891a35c1663392caryclark validatePerpPt(fCoinEnd.perpT(), fCoinEnd.perpPt()); 780ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 781ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 78254359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 78354359294a7c9dc54802d512a5d891a35c1663392caryclark} 78454359294a7c9dc54802d512a5d891a35c1663392caryclark 7851049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 7861049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSpan<TCurve, OppCurve>::validateBounded() const { 78754359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_VALIDATE 7881049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded; 78954359294a7c9dc54802d512a5d891a35c1663392caryclark while (testBounded) { 7901049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE_(const SkTSpan<OppCurve, TCurve>* overlap = testBounded->fBounded); 79154359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!overlap->fDeleted); 79254359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(((this->debugID() ^ overlap->debugID()) & 1) == 1); 79354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(overlap->findOppSpan(this)); 79454359294a7c9dc54802d512a5d891a35c1663392caryclark testBounded = testBounded->fNext; 795ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 79654359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 797ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark} 798ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark 7991049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 8001049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSpan<TCurve, OppCurve>::validatePerpT(double oppT) const { 8011049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded; 80254359294a7c9dc54802d512a5d891a35c1663392caryclark while (testBounded) { 8031049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<OppCurve, TCurve>* overlap = testBounded->fBounded; 80454359294a7c9dc54802d512a5d891a35c1663392caryclark if (between(overlap->fStartT, oppT, overlap->fEndT)) { 80554359294a7c9dc54802d512a5d891a35c1663392caryclark return; 80654359294a7c9dc54802d512a5d891a35c1663392caryclark } 80754359294a7c9dc54802d512a5d891a35c1663392caryclark testBounded = testBounded->fNext; 80845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 80954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(0); 81045fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 81154359294a7c9dc54802d512a5d891a35c1663392caryclark 8121049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 8131049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSpan<TCurve, OppCurve>::validatePerpPt(double t, const SkDPoint& pt) const { 8141049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkASSERT(fDebugSect->fOppSect->fCurve.ptAtT(t) == pt); 81554359294a7c9dc54802d512a5d891a35c1663392caryclark} 81654359294a7c9dc54802d512a5d891a35c1663392caryclark 81745fa447460f70ec21d22cf4e1531490acfd3c578caryclark 8181049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 8191049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkSkTSect<TCurve, OppCurve>::SkTSect(const TCurve& c PATH_OPS_DEBUG_T_SECT_PARAMS(int id)) 82045fa447460f70ec21d22cf4e1531490acfd3c578caryclark : fCurve(c) 8211049f1246e7be4ccb68001361efceb8933e6f81ccaryclark , fHeap(sizeof(SkTSpan<TCurve, OppCurve>) * 4) 82254359294a7c9dc54802d512a5d891a35c1663392caryclark , fCoincident(NULL) 82345fa447460f70ec21d22cf4e1531490acfd3c578caryclark , fDeleted(NULL) 82445fa447460f70ec21d22cf4e1531490acfd3c578caryclark , fActiveCount(0) 82554359294a7c9dc54802d512a5d891a35c1663392caryclark PATH_OPS_DEBUG_T_SECT_PARAMS(fID(id)) 82654359294a7c9dc54802d512a5d891a35c1663392caryclark PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugCount(0)) 82754359294a7c9dc54802d512a5d891a35c1663392caryclark PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugAllocatedCount(0)) 82845fa447460f70ec21d22cf4e1531490acfd3c578caryclark{ 82945fa447460f70ec21d22cf4e1531490acfd3c578caryclark fHead = addOne(); 83045fa447460f70ec21d22cf4e1531490acfd3c578caryclark fHead->init(c); 83145fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 83245fa447460f70ec21d22cf4e1531490acfd3c578caryclark 8331049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 8341049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkSkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::addOne() { 8351049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* result; 83645fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (fDeleted) { 83745fa447460f70ec21d22cf4e1531490acfd3c578caryclark result = fDeleted; 83845fa447460f70ec21d22cf4e1531490acfd3c578caryclark result->reset(); 83945fa447460f70ec21d22cf4e1531490acfd3c578caryclark fDeleted = result->fNext; 84045fa447460f70ec21d22cf4e1531490acfd3c578caryclark } else { 8411049f1246e7be4ccb68001361efceb8933e6f81ccaryclark result = SkNEW_PLACEMENT(fHeap.allocThrow(sizeof(SkTSpan<TCurve, OppCurve>)), 8421049f1246e7be4ccb68001361efceb8933e6f81ccaryclark (SkTSpan<TCurve, OppCurve>)); 84354359294a7c9dc54802d512a5d891a35c1663392caryclark result->fBounded = NULL; 84445fa447460f70ec21d22cf4e1531490acfd3c578caryclark#if DEBUG_T_SECT 84545fa447460f70ec21d22cf4e1531490acfd3c578caryclark ++fDebugAllocatedCount; 84645fa447460f70ec21d22cf4e1531490acfd3c578caryclark#endif 84745fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 84808b3249494782cc401ab1cac57ef4d8e560ed11dcaryclark result->fHasPerp = false; 84908b3249494782cc401ab1cac57ef4d8e560ed11dcaryclark result->fDeleted = false; 85045fa447460f70ec21d22cf4e1531490acfd3c578caryclark ++fActiveCount; 85154359294a7c9dc54802d512a5d891a35c1663392caryclark PATH_OPS_DEBUG_T_SECT_CODE(result->fID = fDebugCount++ * 2 + fID); 8521049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(result->fDebugSect = this); 85345fa447460f70ec21d22cf4e1531490acfd3c578caryclark return result; 85445fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 85545fa447460f70ec21d22cf4e1531490acfd3c578caryclark 8561049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 8571049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkbool SkTSect<TCurve, OppCurve>::binarySearchCoin(SkTSect<OppCurve, TCurve>* sect2, double tStart, 8581049f1246e7be4ccb68001361efceb8933e6f81ccaryclark double tStep, double* resultT, double* oppT) { 8591049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve> work; 86045fa447460f70ec21d22cf4e1531490acfd3c578caryclark double result = work.fStartT = work.fEndT = tStart; 8611049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(work.fDebugSect = this); 86245fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkDPoint last = fCurve.ptAtT(tStart); 86345fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkDPoint oppPt; 86445fa447460f70ec21d22cf4e1531490acfd3c578caryclark bool flip = false; 86545fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkDEBUGCODE(bool down = tStep < 0); 8661049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const OppCurve& opp = sect2->fCurve; 86745fa447460f70ec21d22cf4e1531490acfd3c578caryclark do { 86845fa447460f70ec21d22cf4e1531490acfd3c578caryclark tStep *= 0.5; 86945fa447460f70ec21d22cf4e1531490acfd3c578caryclark work.fStartT += tStep; 87045fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (flip) { 87145fa447460f70ec21d22cf4e1531490acfd3c578caryclark tStep = -tStep; 87245fa447460f70ec21d22cf4e1531490acfd3c578caryclark flip = false; 87345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 87445fa447460f70ec21d22cf4e1531490acfd3c578caryclark work.initBounds(fCurve); 87545fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (work.fCollapsed) { 87645fa447460f70ec21d22cf4e1531490acfd3c578caryclark return false; 87745fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 87845fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (last.approximatelyEqual(work.fPart[0])) { 87945fa447460f70ec21d22cf4e1531490acfd3c578caryclark break; 88045fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 88145fa447460f70ec21d22cf4e1531490acfd3c578caryclark last = work.fPart[0]; 88245fa447460f70ec21d22cf4e1531490acfd3c578caryclark work.fCoinStart.setPerp(fCurve, work.fStartT, last, opp); 88345fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (work.fCoinStart.isCoincident()) { 88454359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_T_SECT 88554359294a7c9dc54802d512a5d891a35c1663392caryclark work.validatePerpPt(work.fCoinStart.perpT(), work.fCoinStart.perpPt()); 88654359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 88745fa447460f70ec21d22cf4e1531490acfd3c578caryclark double oppTTest = work.fCoinStart.perpT(); 88854359294a7c9dc54802d512a5d891a35c1663392caryclark if (sect2->fHead->contains(oppTTest)) { 88945fa447460f70ec21d22cf4e1531490acfd3c578caryclark *oppT = oppTTest; 89045fa447460f70ec21d22cf4e1531490acfd3c578caryclark oppPt = work.fCoinStart.perpPt(); 89145fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkASSERT(down ? result > work.fStartT : result < work.fStartT); 89245fa447460f70ec21d22cf4e1531490acfd3c578caryclark result = work.fStartT; 89345fa447460f70ec21d22cf4e1531490acfd3c578caryclark continue; 89445fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 89545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 89645fa447460f70ec21d22cf4e1531490acfd3c578caryclark tStep = -tStep; 89745fa447460f70ec21d22cf4e1531490acfd3c578caryclark flip = true; 89845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } while (true); 89945fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (last.approximatelyEqual(fCurve[0])) { 90045fa447460f70ec21d22cf4e1531490acfd3c578caryclark result = 0; 90145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } else if (last.approximatelyEqual(fCurve[TCurve::kPointLast])) { 90245fa447460f70ec21d22cf4e1531490acfd3c578caryclark result = 1; 90345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 90445fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (oppPt.approximatelyEqual(opp[0])) { 90545fa447460f70ec21d22cf4e1531490acfd3c578caryclark *oppT = 0; 9061049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } else if (oppPt.approximatelyEqual(opp[OppCurve::kPointLast])) { 90745fa447460f70ec21d22cf4e1531490acfd3c578caryclark *oppT = 1; 90845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 90945fa447460f70ec21d22cf4e1531490acfd3c578caryclark *resultT = result; 91045fa447460f70ec21d22cf4e1531490acfd3c578caryclark return true; 91145fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 91245fa447460f70ec21d22cf4e1531490acfd3c578caryclark 91345fa447460f70ec21d22cf4e1531490acfd3c578caryclark// OPTIMIZE ? keep a sorted list of sizes in the form of a doubly-linked list in quad span 91445fa447460f70ec21d22cf4e1531490acfd3c578caryclark// so that each quad sect has a pointer to the largest, and can update it as spans 91545fa447460f70ec21d22cf4e1531490acfd3c578caryclark// are split 9161049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 9171049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkSkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::boundsMax() const { 9181049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* test = fHead; 9191049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* largest = fHead; 92054359294a7c9dc54802d512a5d891a35c1663392caryclark bool lCollapsed = largest->fCollapsed; 92145fa447460f70ec21d22cf4e1531490acfd3c578caryclark while ((test = test->fNext)) { 92254359294a7c9dc54802d512a5d891a35c1663392caryclark bool tCollapsed = test->fCollapsed; 92354359294a7c9dc54802d512a5d891a35c1663392caryclark if ((lCollapsed && !tCollapsed) || (lCollapsed == tCollapsed && 92454359294a7c9dc54802d512a5d891a35c1663392caryclark largest->fBoundsMax < test->fBoundsMax)) { 92545fa447460f70ec21d22cf4e1531490acfd3c578caryclark largest = test; 9261049f1246e7be4ccb68001361efceb8933e6f81ccaryclark lCollapsed = test->fCollapsed; 92745fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 92845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 92954359294a7c9dc54802d512a5d891a35c1663392caryclark return largest; 93045fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 93145fa447460f70ec21d22cf4e1531490acfd3c578caryclark 9321049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 9331049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::coincidentCheck(SkTSect<OppCurve, TCurve>* sect2) { 9341049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* first = fHead; 9351049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* last, * next; 93645fa447460f70ec21d22cf4e1531490acfd3c578caryclark do { 93754359294a7c9dc54802d512a5d891a35c1663392caryclark int consecutive = this->countConsecutiveSpans(first, &last); 93854359294a7c9dc54802d512a5d891a35c1663392caryclark next = last->fNext; 93945fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (consecutive < COINCIDENT_SPAN_COUNT) { 94045fa447460f70ec21d22cf4e1531490acfd3c578caryclark continue; 94145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 94254359294a7c9dc54802d512a5d891a35c1663392caryclark this->validate(); 94354359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->validate(); 94454359294a7c9dc54802d512a5d891a35c1663392caryclark this->computePerpendiculars(sect2, first, last); 94554359294a7c9dc54802d512a5d891a35c1663392caryclark this->validate(); 94654359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->validate(); 94745fa447460f70ec21d22cf4e1531490acfd3c578caryclark // check to see if a range of points are on the curve 9481049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* coinStart = first; 94954359294a7c9dc54802d512a5d891a35c1663392caryclark do { 95054359294a7c9dc54802d512a5d891a35c1663392caryclark coinStart = this->extractCoincident(sect2, coinStart, last); 95154359294a7c9dc54802d512a5d891a35c1663392caryclark } while (coinStart && !last->fDeleted); 95245fa447460f70ec21d22cf4e1531490acfd3c578caryclark } while ((first = next)); 95345fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 95445fa447460f70ec21d22cf4e1531490acfd3c578caryclark 9551049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 9561049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkbool SkTSect<TCurve, OppCurve>::coincidentHasT(double t) { 9571049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* test = fCoincident; 95854359294a7c9dc54802d512a5d891a35c1663392caryclark while (test) { 95954359294a7c9dc54802d512a5d891a35c1663392caryclark if (between(test->fStartT, t, test->fEndT)) { 96054359294a7c9dc54802d512a5d891a35c1663392caryclark return true; 96154359294a7c9dc54802d512a5d891a35c1663392caryclark } 96254359294a7c9dc54802d512a5d891a35c1663392caryclark test = test->fNext; 9630dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 96454359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 96545fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 96645fa447460f70ec21d22cf4e1531490acfd3c578caryclark 9671049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 9681049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkint SkTSect<TCurve, OppCurve>::collapsed() const { 9691049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int result = 0; 9701049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<TCurve, OppCurve>* test = fHead; 9711049f1246e7be4ccb68001361efceb8933e6f81ccaryclark while (test) { 9721049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (test->fCollapsed) { 9731049f1246e7be4ccb68001361efceb8933e6f81ccaryclark ++result; 9741049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 9751049f1246e7be4ccb68001361efceb8933e6f81ccaryclark test = test->next(); 9761049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 9771049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return result; 9781049f1246e7be4ccb68001361efceb8933e6f81ccaryclark} 9791049f1246e7be4ccb68001361efceb8933e6f81ccaryclark 9801049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 9811049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::computePerpendiculars(SkTSect<OppCurve, TCurve>* sect2, 9821049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last) { 9831049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const OppCurve& opp = sect2->fCurve; 9841049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* work = first; 9851049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* prior = NULL; 98645fa447460f70ec21d22cf4e1531490acfd3c578caryclark do { 98754359294a7c9dc54802d512a5d891a35c1663392caryclark if (!work->fHasPerp && !work->fCollapsed) { 98854359294a7c9dc54802d512a5d891a35c1663392caryclark if (prior) { 98954359294a7c9dc54802d512a5d891a35c1663392caryclark work->fCoinStart = prior->fCoinEnd; 99054359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 99154359294a7c9dc54802d512a5d891a35c1663392caryclark work->fCoinStart.setPerp(fCurve, work->fStartT, work->fPart[0], opp); 992ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 99354359294a7c9dc54802d512a5d891a35c1663392caryclark if (work->fCoinStart.isCoincident()) { 99454359294a7c9dc54802d512a5d891a35c1663392caryclark double perpT = work->fCoinStart.perpT(); 99554359294a7c9dc54802d512a5d891a35c1663392caryclark if (sect2->coincidentHasT(perpT)) { 99654359294a7c9dc54802d512a5d891a35c1663392caryclark work->fCoinStart.clear(); 99754359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 99854359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->addForPerp(work, perpT); 99954359294a7c9dc54802d512a5d891a35c1663392caryclark } 100054359294a7c9dc54802d512a5d891a35c1663392caryclark } 100154359294a7c9dc54802d512a5d891a35c1663392caryclark work->fCoinEnd.setPerp(fCurve, work->fEndT, work->fPart[TCurve::kPointLast], opp); 100254359294a7c9dc54802d512a5d891a35c1663392caryclark if (work->fCoinEnd.isCoincident()) { 100354359294a7c9dc54802d512a5d891a35c1663392caryclark double perpT = work->fCoinEnd.perpT(); 100454359294a7c9dc54802d512a5d891a35c1663392caryclark if (sect2->coincidentHasT(perpT)) { 100554359294a7c9dc54802d512a5d891a35c1663392caryclark work->fCoinEnd.clear(); 100654359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 100754359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->addForPerp(work, perpT); 100854359294a7c9dc54802d512a5d891a35c1663392caryclark } 100954359294a7c9dc54802d512a5d891a35c1663392caryclark } 101054359294a7c9dc54802d512a5d891a35c1663392caryclark work->fHasPerp = true; 101145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 101245fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (work == last) { 101345fa447460f70ec21d22cf4e1531490acfd3c578caryclark break; 101445fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 101554359294a7c9dc54802d512a5d891a35c1663392caryclark prior = work; 101645fa447460f70ec21d22cf4e1531490acfd3c578caryclark work = work->fNext; 101745fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkASSERT(work); 101845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } while (true); 101954359294a7c9dc54802d512a5d891a35c1663392caryclark} 102054359294a7c9dc54802d512a5d891a35c1663392caryclark 10211049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 10221049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkint SkTSect<TCurve, OppCurve>::countConsecutiveSpans(SkTSpan<TCurve, OppCurve>* first, 10231049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>** lastPtr) const { 102454359294a7c9dc54802d512a5d891a35c1663392caryclark int consecutive = 1; 10251049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* last = first; 102654359294a7c9dc54802d512a5d891a35c1663392caryclark do { 10271049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* next = last->fNext; 102854359294a7c9dc54802d512a5d891a35c1663392caryclark if (!next) { 102954359294a7c9dc54802d512a5d891a35c1663392caryclark break; 103054359294a7c9dc54802d512a5d891a35c1663392caryclark } 103154359294a7c9dc54802d512a5d891a35c1663392caryclark if (next->fStartT > last->fEndT) { 103254359294a7c9dc54802d512a5d891a35c1663392caryclark break; 103354359294a7c9dc54802d512a5d891a35c1663392caryclark } 103454359294a7c9dc54802d512a5d891a35c1663392caryclark ++consecutive; 103554359294a7c9dc54802d512a5d891a35c1663392caryclark last = next; 103654359294a7c9dc54802d512a5d891a35c1663392caryclark } while (true); 103754359294a7c9dc54802d512a5d891a35c1663392caryclark *lastPtr = last; 103854359294a7c9dc54802d512a5d891a35c1663392caryclark return consecutive; 103954359294a7c9dc54802d512a5d891a35c1663392caryclark} 104054359294a7c9dc54802d512a5d891a35c1663392caryclark 10411049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 10421049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkbool SkTSect<TCurve, OppCurve>::debugHasBounded(const SkTSpan<OppCurve, TCurve>* span) const { 10431049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<TCurve, OppCurve>* test = fHead; 104454359294a7c9dc54802d512a5d891a35c1663392caryclark if (!test) { 104554359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 104654359294a7c9dc54802d512a5d891a35c1663392caryclark } 104754359294a7c9dc54802d512a5d891a35c1663392caryclark do { 104854359294a7c9dc54802d512a5d891a35c1663392caryclark if (test->findOppSpan(span)) { 104954359294a7c9dc54802d512a5d891a35c1663392caryclark return true; 105054359294a7c9dc54802d512a5d891a35c1663392caryclark } 105154359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((test = test->next())); 105254359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 105354359294a7c9dc54802d512a5d891a35c1663392caryclark} 105454359294a7c9dc54802d512a5d891a35c1663392caryclark 10551049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 10561049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::deleteEmptySpans() { 10571049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* test; 10581049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* next = fHead; 105954359294a7c9dc54802d512a5d891a35c1663392caryclark while ((test = next)) { 106054359294a7c9dc54802d512a5d891a35c1663392caryclark next = test->fNext; 106154359294a7c9dc54802d512a5d891a35c1663392caryclark if (!test->fBounded) { 106254359294a7c9dc54802d512a5d891a35c1663392caryclark this->removeSpan(test); 106354359294a7c9dc54802d512a5d891a35c1663392caryclark } 106454359294a7c9dc54802d512a5d891a35c1663392caryclark } 106554359294a7c9dc54802d512a5d891a35c1663392caryclark} 106654359294a7c9dc54802d512a5d891a35c1663392caryclark 10671049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 10681049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkSkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::extractCoincident( 10691049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSect<OppCurve, TCurve>* sect2, 10701049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last) { 10711049f1246e7be4ccb68001361efceb8933e6f81ccaryclark first = findCoincidentRun(first, &last); 107254359294a7c9dc54802d512a5d891a35c1663392caryclark if (!first) { 107354359294a7c9dc54802d512a5d891a35c1663392caryclark return NULL; 107454359294a7c9dc54802d512a5d891a35c1663392caryclark } 107545fa447460f70ec21d22cf4e1531490acfd3c578caryclark // march outwards to find limit of coincidence from here to previous and next spans 107645fa447460f70ec21d22cf4e1531490acfd3c578caryclark double startT = first->fStartT; 1077d8bc16b306f8453a86d0af070d68c327f4bb41ebcaryclark double oppStartT SK_INIT_TO_AVOID_WARNING; 107854359294a7c9dc54802d512a5d891a35c1663392caryclark double oppEndT SK_INIT_TO_AVOID_WARNING; 10791049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* prev = first->fPrev; 108054359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(first->fCoinStart.isCoincident()); 10811049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* oppFirst = first->findOppT(first->fCoinStart.perpT()); 108254359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(last->fCoinEnd.isCoincident()); 108354359294a7c9dc54802d512a5d891a35c1663392caryclark bool oppMatched = first->fCoinStart.perpT() < first->fCoinEnd.perpT(); 108454359294a7c9dc54802d512a5d891a35c1663392caryclark double coinStart; 108554359294a7c9dc54802d512a5d891a35c1663392caryclark SkDEBUGCODE(double coinEnd); 10861049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* cutFirst; 108754359294a7c9dc54802d512a5d891a35c1663392caryclark if (prev && prev->fEndT == startT 108854359294a7c9dc54802d512a5d891a35c1663392caryclark && this->binarySearchCoin(sect2, startT, prev->fStartT - startT, &coinStart, 108954359294a7c9dc54802d512a5d891a35c1663392caryclark &oppStartT) 10901049f1246e7be4ccb68001361efceb8933e6f81ccaryclark && prev->fStartT < coinStart && coinStart < startT 10911049f1246e7be4ccb68001361efceb8933e6f81ccaryclark && (cutFirst = prev->oppT(oppStartT))) { 10921049f1246e7be4ccb68001361efceb8933e6f81ccaryclark oppFirst = cutFirst; 109354359294a7c9dc54802d512a5d891a35c1663392caryclark first = this->addSplitAt(prev, coinStart); 109454359294a7c9dc54802d512a5d891a35c1663392caryclark first->markCoincident(); 109554359294a7c9dc54802d512a5d891a35c1663392caryclark prev->fCoinEnd.markCoincident(); 109654359294a7c9dc54802d512a5d891a35c1663392caryclark if (oppFirst->fStartT < oppStartT && oppStartT < oppFirst->fEndT) { 10971049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* oppHalf = sect2->addSplitAt(oppFirst, oppStartT); 109854359294a7c9dc54802d512a5d891a35c1663392caryclark if (oppMatched) { 109954359294a7c9dc54802d512a5d891a35c1663392caryclark oppFirst->fCoinEnd.markCoincident(); 110054359294a7c9dc54802d512a5d891a35c1663392caryclark oppHalf->markCoincident(); 110154359294a7c9dc54802d512a5d891a35c1663392caryclark oppFirst = oppHalf; 110254359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 110354359294a7c9dc54802d512a5d891a35c1663392caryclark oppFirst->markCoincident(); 110454359294a7c9dc54802d512a5d891a35c1663392caryclark oppHalf->fCoinStart.markCoincident(); 110554359294a7c9dc54802d512a5d891a35c1663392caryclark } 110654359294a7c9dc54802d512a5d891a35c1663392caryclark } 110754359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 110854359294a7c9dc54802d512a5d891a35c1663392caryclark SkDEBUGCODE(coinStart = first->fStartT); 110954359294a7c9dc54802d512a5d891a35c1663392caryclark SkDEBUGCODE(oppStartT = oppMatched ? oppFirst->fStartT : oppFirst->fEndT); 111054359294a7c9dc54802d512a5d891a35c1663392caryclark } 11111049f1246e7be4ccb68001361efceb8933e6f81ccaryclark // FIXME: incomplete : if we're not at the end, find end of coin 11121049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* oppLast; 111354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(last->fCoinEnd.isCoincident()); 111454359294a7c9dc54802d512a5d891a35c1663392caryclark oppLast = last->findOppT(last->fCoinEnd.perpT()); 111554359294a7c9dc54802d512a5d891a35c1663392caryclark SkDEBUGCODE(coinEnd = last->fEndT); 111654359294a7c9dc54802d512a5d891a35c1663392caryclark SkDEBUGCODE(oppEndT = oppMatched ? oppLast->fEndT : oppLast->fStartT); 111754359294a7c9dc54802d512a5d891a35c1663392caryclark if (!oppMatched) { 111854359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(oppFirst, oppLast); 111954359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(oppStartT, oppEndT); 112054359294a7c9dc54802d512a5d891a35c1663392caryclark } 112154359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(oppStartT < oppEndT); 112254359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(coinStart == first->fStartT); 112354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(coinEnd == last->fEndT); 112454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(oppStartT == oppFirst->fStartT); 112554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(oppEndT == oppLast->fEndT); 112654359294a7c9dc54802d512a5d891a35c1663392caryclark // reduce coincident runs to single entries 112754359294a7c9dc54802d512a5d891a35c1663392caryclark this->validate(); 112854359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->validate(); 11291049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool deleteEmptySpans = this->updateBounded(first, last, oppFirst); 11301049f1246e7be4ccb68001361efceb8933e6f81ccaryclark deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first); 113154359294a7c9dc54802d512a5d891a35c1663392caryclark this->removeSpanRange(first, last); 113254359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->removeSpanRange(oppFirst, oppLast); 113354359294a7c9dc54802d512a5d891a35c1663392caryclark first->fEndT = last->fEndT; 113454359294a7c9dc54802d512a5d891a35c1663392caryclark first->resetBounds(this->fCurve); 113554359294a7c9dc54802d512a5d891a35c1663392caryclark first->fCoinStart.setPerp(fCurve, first->fStartT, first->fPart[0], sect2->fCurve); 113654359294a7c9dc54802d512a5d891a35c1663392caryclark first->fCoinEnd.setPerp(fCurve, first->fEndT, first->fPart[TCurve::kPointLast], sect2->fCurve); 113754359294a7c9dc54802d512a5d891a35c1663392caryclark oppStartT = first->fCoinStart.perpT(); 113854359294a7c9dc54802d512a5d891a35c1663392caryclark oppEndT = first->fCoinEnd.perpT(); 113954359294a7c9dc54802d512a5d891a35c1663392caryclark if (between(0, oppStartT, 1) && between(0, oppEndT, 1)) { 114054359294a7c9dc54802d512a5d891a35c1663392caryclark if (!oppMatched) { 114154359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(oppStartT, oppEndT); 114254359294a7c9dc54802d512a5d891a35c1663392caryclark } 114354359294a7c9dc54802d512a5d891a35c1663392caryclark oppFirst->fStartT = oppStartT; 114454359294a7c9dc54802d512a5d891a35c1663392caryclark oppFirst->fEndT = oppEndT; 114554359294a7c9dc54802d512a5d891a35c1663392caryclark oppFirst->resetBounds(sect2->fCurve); 114654359294a7c9dc54802d512a5d891a35c1663392caryclark } 114754359294a7c9dc54802d512a5d891a35c1663392caryclark this->validateBounded(); 114854359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->validateBounded(); 114954359294a7c9dc54802d512a5d891a35c1663392caryclark last = first->fNext; 115054359294a7c9dc54802d512a5d891a35c1663392caryclark this->removeCoincident(first, false); 115154359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->removeCoincident(oppFirst, true); 11521049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (deleteEmptySpans) { 115354359294a7c9dc54802d512a5d891a35c1663392caryclark this->deleteEmptySpans(); 115454359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->deleteEmptySpans(); 115554359294a7c9dc54802d512a5d891a35c1663392caryclark } 115654359294a7c9dc54802d512a5d891a35c1663392caryclark this->validate(); 115754359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->validate(); 115854359294a7c9dc54802d512a5d891a35c1663392caryclark return last && !last->fDeleted ? last : NULL; 115954359294a7c9dc54802d512a5d891a35c1663392caryclark} 116054359294a7c9dc54802d512a5d891a35c1663392caryclark 11611049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 11621049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkSkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::findCoincidentRun( 11631049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>** lastPtr) { 11641049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* work = first; 11651049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* lastCandidate = NULL; 116654359294a7c9dc54802d512a5d891a35c1663392caryclark first = NULL; 116754359294a7c9dc54802d512a5d891a35c1663392caryclark // find the first fully coincident span 116854359294a7c9dc54802d512a5d891a35c1663392caryclark do { 116954359294a7c9dc54802d512a5d891a35c1663392caryclark if (work->fCoinStart.isCoincident()) { 11701049f1246e7be4ccb68001361efceb8933e6f81ccaryclark#if DEBUG_T_SECT 117154359294a7c9dc54802d512a5d891a35c1663392caryclark work->validatePerpT(work->fCoinStart.perpT()); 117254359294a7c9dc54802d512a5d891a35c1663392caryclark work->validatePerpPt(work->fCoinStart.perpT(), work->fCoinStart.perpPt()); 11731049f1246e7be4ccb68001361efceb8933e6f81ccaryclark#endif 117454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(work->hasOppT(work->fCoinStart.perpT())); 117554359294a7c9dc54802d512a5d891a35c1663392caryclark if (!work->fCoinEnd.isCoincident()) { 117654359294a7c9dc54802d512a5d891a35c1663392caryclark break; 117754359294a7c9dc54802d512a5d891a35c1663392caryclark } 117854359294a7c9dc54802d512a5d891a35c1663392caryclark lastCandidate = work; 117954359294a7c9dc54802d512a5d891a35c1663392caryclark if (!first) { 118054359294a7c9dc54802d512a5d891a35c1663392caryclark first = work; 118154359294a7c9dc54802d512a5d891a35c1663392caryclark } 11821049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } else if (first && work->fCollapsed) { 11831049f1246e7be4ccb68001361efceb8933e6f81ccaryclark *lastPtr = lastCandidate; 11841049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return first; 118554359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 118654359294a7c9dc54802d512a5d891a35c1663392caryclark lastCandidate = NULL; 118754359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!first); 118854359294a7c9dc54802d512a5d891a35c1663392caryclark } 118954359294a7c9dc54802d512a5d891a35c1663392caryclark if (work == *lastPtr) { 119054359294a7c9dc54802d512a5d891a35c1663392caryclark return first; 119154359294a7c9dc54802d512a5d891a35c1663392caryclark } 119254359294a7c9dc54802d512a5d891a35c1663392caryclark work = work->fNext; 119354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(work); 119454359294a7c9dc54802d512a5d891a35c1663392caryclark } while (true); 119554359294a7c9dc54802d512a5d891a35c1663392caryclark if (lastCandidate) { 119654359294a7c9dc54802d512a5d891a35c1663392caryclark *lastPtr = lastCandidate; 119754359294a7c9dc54802d512a5d891a35c1663392caryclark } 119854359294a7c9dc54802d512a5d891a35c1663392caryclark return first; 119954359294a7c9dc54802d512a5d891a35c1663392caryclark} 120054359294a7c9dc54802d512a5d891a35c1663392caryclark 12011049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 12021049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkint SkTSect<TCurve, OppCurve>::intersects(SkTSpan<TCurve, OppCurve>* span, 12031049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSect<OppCurve, TCurve>* opp, 12041049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* oppSpan, int* oppResult) { 120554359294a7c9dc54802d512a5d891a35c1663392caryclark bool spanStart, oppStart; 120654359294a7c9dc54802d512a5d891a35c1663392caryclark int hullResult = span->hullsIntersect(oppSpan, &spanStart, &oppStart); 120754359294a7c9dc54802d512a5d891a35c1663392caryclark if (hullResult >= 0) { 120854359294a7c9dc54802d512a5d891a35c1663392caryclark if (hullResult == 2) { // hulls have one point in common 120954359294a7c9dc54802d512a5d891a35c1663392caryclark if (!span->fBounded || !span->fBounded->fNext) { 121054359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!span->fBounded || span->fBounded->fBounded == oppSpan); 121154359294a7c9dc54802d512a5d891a35c1663392caryclark if (spanStart) { 121254359294a7c9dc54802d512a5d891a35c1663392caryclark span->fEndT = span->fStartT; 121345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } else { 121454359294a7c9dc54802d512a5d891a35c1663392caryclark span->fStartT = span->fEndT; 121545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 121654359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 121754359294a7c9dc54802d512a5d891a35c1663392caryclark hullResult = 1; 121845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 121954359294a7c9dc54802d512a5d891a35c1663392caryclark if (!oppSpan->fBounded || !oppSpan->fBounded->fNext) { 122054359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!oppSpan->fBounded || oppSpan->fBounded->fBounded == span); 122154359294a7c9dc54802d512a5d891a35c1663392caryclark if (oppStart) { 122254359294a7c9dc54802d512a5d891a35c1663392caryclark oppSpan->fEndT = oppSpan->fStartT; 122354359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 122454359294a7c9dc54802d512a5d891a35c1663392caryclark oppSpan->fStartT = oppSpan->fEndT; 122554359294a7c9dc54802d512a5d891a35c1663392caryclark } 122654359294a7c9dc54802d512a5d891a35c1663392caryclark *oppResult = 2; 122754359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 122854359294a7c9dc54802d512a5d891a35c1663392caryclark *oppResult = 1; 122954359294a7c9dc54802d512a5d891a35c1663392caryclark } 123054359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 123154359294a7c9dc54802d512a5d891a35c1663392caryclark *oppResult = 1; 1232ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 123354359294a7c9dc54802d512a5d891a35c1663392caryclark return hullResult; 1234ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 123554359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->fIsLine && oppSpan->fIsLine) { 123654359294a7c9dc54802d512a5d891a35c1663392caryclark SkIntersections i; 123754359294a7c9dc54802d512a5d891a35c1663392caryclark int sects = this->linesIntersect(span, opp, oppSpan, &i); 123854359294a7c9dc54802d512a5d891a35c1663392caryclark if (!sects) { 123954359294a7c9dc54802d512a5d891a35c1663392caryclark return -1; 124054359294a7c9dc54802d512a5d891a35c1663392caryclark } 124154359294a7c9dc54802d512a5d891a35c1663392caryclark span->fStartT = span->fEndT = i[0][0]; 124254359294a7c9dc54802d512a5d891a35c1663392caryclark oppSpan->fStartT = oppSpan->fEndT = i[1][0]; 124354359294a7c9dc54802d512a5d891a35c1663392caryclark return *oppResult = 2; 124454359294a7c9dc54802d512a5d891a35c1663392caryclark } 124554359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->fIsLinear || oppSpan->fIsLinear) { 124654359294a7c9dc54802d512a5d891a35c1663392caryclark return *oppResult = (int) span->linearsIntersect(oppSpan); 124754359294a7c9dc54802d512a5d891a35c1663392caryclark } 124854359294a7c9dc54802d512a5d891a35c1663392caryclark return *oppResult = 1; 124954359294a7c9dc54802d512a5d891a35c1663392caryclark} 125054359294a7c9dc54802d512a5d891a35c1663392caryclark 125154359294a7c9dc54802d512a5d891a35c1663392caryclark// while the intersection points are sufficiently far apart: 125254359294a7c9dc54802d512a5d891a35c1663392caryclark// construct the tangent lines from the intersections 125354359294a7c9dc54802d512a5d891a35c1663392caryclark// find the point where the tangent line intersects the opposite curve 12541049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 12551049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkint SkTSect<TCurve, OppCurve>::linesIntersect(SkTSpan<TCurve, OppCurve>* span, 12561049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSect<OppCurve, TCurve>* opp, 12571049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* oppSpan, SkIntersections* i) { 125854359294a7c9dc54802d512a5d891a35c1663392caryclark SkIntersections thisRayI, oppRayI; 125954359294a7c9dc54802d512a5d891a35c1663392caryclark SkDLine thisLine = {{ span->fPart[0], span->fPart[TCurve::kPointLast] }}; 12601049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDLine oppLine = {{ oppSpan->fPart[0], oppSpan->fPart[OppCurve::kPointLast] }}; 126154359294a7c9dc54802d512a5d891a35c1663392caryclark int loopCount = 0; 126254359294a7c9dc54802d512a5d891a35c1663392caryclark double bestDistSq = DBL_MAX; 12631049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (!thisRayI.intersectRay(opp->fCurve, thisLine)) { 12641049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return 0; 12651049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 12661049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (!oppRayI.intersectRay(this->fCurve, oppLine)) { 12671049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return 0; 12681049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 126954359294a7c9dc54802d512a5d891a35c1663392caryclark do { 127054359294a7c9dc54802d512a5d891a35c1663392caryclark // pick the closest pair of points 127154359294a7c9dc54802d512a5d891a35c1663392caryclark double closest = DBL_MAX; 127254359294a7c9dc54802d512a5d891a35c1663392caryclark int closeIndex SK_INIT_TO_AVOID_WARNING; 127354359294a7c9dc54802d512a5d891a35c1663392caryclark int oppCloseIndex SK_INIT_TO_AVOID_WARNING; 127454359294a7c9dc54802d512a5d891a35c1663392caryclark for (int index = 0; index < oppRayI.used(); ++index) { 127554359294a7c9dc54802d512a5d891a35c1663392caryclark if (!roughly_between(span->fStartT, oppRayI[0][index], span->fEndT)) { 127654359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 127754359294a7c9dc54802d512a5d891a35c1663392caryclark } 127854359294a7c9dc54802d512a5d891a35c1663392caryclark for (int oIndex = 0; oIndex < thisRayI.used(); ++oIndex) { 127954359294a7c9dc54802d512a5d891a35c1663392caryclark if (!roughly_between(oppSpan->fStartT, thisRayI[0][oIndex], oppSpan->fEndT)) { 128054359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 128154359294a7c9dc54802d512a5d891a35c1663392caryclark } 128254359294a7c9dc54802d512a5d891a35c1663392caryclark double distSq = thisRayI.pt(index).distanceSquared(oppRayI.pt(oIndex)); 128354359294a7c9dc54802d512a5d891a35c1663392caryclark if (closest > distSq) { 128454359294a7c9dc54802d512a5d891a35c1663392caryclark closest = distSq; 128554359294a7c9dc54802d512a5d891a35c1663392caryclark closeIndex = index; 128654359294a7c9dc54802d512a5d891a35c1663392caryclark oppCloseIndex = oIndex; 128745fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 128845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 128945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 129054359294a7c9dc54802d512a5d891a35c1663392caryclark if (closest == DBL_MAX) { 12911049f1246e7be4ccb68001361efceb8933e6f81ccaryclark break; 129254359294a7c9dc54802d512a5d891a35c1663392caryclark } 129354359294a7c9dc54802d512a5d891a35c1663392caryclark const SkDPoint& oppIPt = thisRayI.pt(oppCloseIndex); 129454359294a7c9dc54802d512a5d891a35c1663392caryclark const SkDPoint& iPt = oppRayI.pt(closeIndex); 129554359294a7c9dc54802d512a5d891a35c1663392caryclark if (between(span->fStartT, oppRayI[0][closeIndex], span->fEndT) 129654359294a7c9dc54802d512a5d891a35c1663392caryclark && between(oppSpan->fStartT, thisRayI[0][oppCloseIndex], oppSpan->fEndT) 129754359294a7c9dc54802d512a5d891a35c1663392caryclark && oppIPt.approximatelyEqual(iPt)) { 129854359294a7c9dc54802d512a5d891a35c1663392caryclark i->merge(oppRayI, closeIndex, thisRayI, oppCloseIndex); 129954359294a7c9dc54802d512a5d891a35c1663392caryclark return i->used(); 130054359294a7c9dc54802d512a5d891a35c1663392caryclark } 130154359294a7c9dc54802d512a5d891a35c1663392caryclark double distSq = oppIPt.distanceSquared(iPt); 130254359294a7c9dc54802d512a5d891a35c1663392caryclark if (bestDistSq < distSq || ++loopCount > 5) { 13031049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return 0; 130454359294a7c9dc54802d512a5d891a35c1663392caryclark } 130554359294a7c9dc54802d512a5d891a35c1663392caryclark bestDistSq = distSq; 13061049f1246e7be4ccb68001361efceb8933e6f81ccaryclark double oppStart = oppRayI[0][closeIndex]; 13071049f1246e7be4ccb68001361efceb8933e6f81ccaryclark thisLine[0] = fCurve.ptAtT(oppStart); 13081049f1246e7be4ccb68001361efceb8933e6f81ccaryclark thisLine[1] = thisLine[0] + fCurve.dxdyAtT(oppStart); 13091049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (!thisRayI.intersectRay(opp->fCurve, thisLine)) { 13101049f1246e7be4ccb68001361efceb8933e6f81ccaryclark break; 13111049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 13121049f1246e7be4ccb68001361efceb8933e6f81ccaryclark double start = thisRayI[0][oppCloseIndex]; 13131049f1246e7be4ccb68001361efceb8933e6f81ccaryclark oppLine[0] = opp->fCurve.ptAtT(start); 13141049f1246e7be4ccb68001361efceb8933e6f81ccaryclark oppLine[1] = oppLine[0] + opp->fCurve.dxdyAtT(start); 13151049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (!oppRayI.intersectRay(this->fCurve, oppLine)) { 13161049f1246e7be4ccb68001361efceb8933e6f81ccaryclark break; 13171049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 131854359294a7c9dc54802d512a5d891a35c1663392caryclark } while (true); 13191049f1246e7be4ccb68001361efceb8933e6f81ccaryclark // convergence may fail if the curves are nearly coincident 13201049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTCoincident<OppCurve, TCurve> oCoinS, oCoinE; 13211049f1246e7be4ccb68001361efceb8933e6f81ccaryclark oCoinS.setPerp(opp->fCurve, oppSpan->fStartT, oppSpan->fPart[0], fCurve); 13221049f1246e7be4ccb68001361efceb8933e6f81ccaryclark oCoinE.setPerp(opp->fCurve, oppSpan->fEndT, oppSpan->fPart[OppCurve::kPointLast], fCurve); 13231049f1246e7be4ccb68001361efceb8933e6f81ccaryclark double tStart = oCoinS.perpT(); 13241049f1246e7be4ccb68001361efceb8933e6f81ccaryclark double tEnd = oCoinE.perpT(); 13251049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool swap = tStart > tEnd; 13261049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (swap) { 13271049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSwap(tStart, tEnd); 13281049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 13291049f1246e7be4ccb68001361efceb8933e6f81ccaryclark tStart = SkTMax(tStart, span->fStartT); 13301049f1246e7be4ccb68001361efceb8933e6f81ccaryclark tEnd = SkTMin(tEnd, span->fEndT); 13311049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (tStart > tEnd) { 13321049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return 0; 13331049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 13341049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDVector perpS, perpE; 13351049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (tStart == span->fStartT) { 13361049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTCoincident<TCurve, OppCurve> coinS; 13371049f1246e7be4ccb68001361efceb8933e6f81ccaryclark coinS.setPerp(fCurve, span->fStartT, span->fPart[0], opp->fCurve); 13381049f1246e7be4ccb68001361efceb8933e6f81ccaryclark perpS = span->fPart[0] - coinS.perpPt(); 13391049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } else if (swap) { 13401049f1246e7be4ccb68001361efceb8933e6f81ccaryclark perpS = oCoinE.perpPt() - oppSpan->fPart[OppCurve::kPointLast]; 13411049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } else { 13421049f1246e7be4ccb68001361efceb8933e6f81ccaryclark perpS = oCoinS.perpPt() - oppSpan->fPart[0]; 13431049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 13441049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (tEnd == span->fEndT) { 13451049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTCoincident<TCurve, OppCurve> coinE; 13461049f1246e7be4ccb68001361efceb8933e6f81ccaryclark coinE.setPerp(fCurve, span->fEndT, span->fPart[TCurve::kPointLast], opp->fCurve); 13471049f1246e7be4ccb68001361efceb8933e6f81ccaryclark perpE = span->fPart[TCurve::kPointLast] - coinE.perpPt(); 13481049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } else if (swap) { 13491049f1246e7be4ccb68001361efceb8933e6f81ccaryclark perpE = oCoinS.perpPt() - oppSpan->fPart[0]; 13501049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } else { 13511049f1246e7be4ccb68001361efceb8933e6f81ccaryclark perpE = oCoinE.perpPt() - oppSpan->fPart[OppCurve::kPointLast]; 13521049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 13531049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (perpS.dot(perpE) >= 0) { 13541049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return 0; 13551049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 13561049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTCoincident<TCurve, OppCurve> coinW; 13571049f1246e7be4ccb68001361efceb8933e6f81ccaryclark double workT = tStart; 13581049f1246e7be4ccb68001361efceb8933e6f81ccaryclark double tStep = tEnd - tStart; 13591049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDPoint workPt; 13601049f1246e7be4ccb68001361efceb8933e6f81ccaryclark do { 13611049f1246e7be4ccb68001361efceb8933e6f81ccaryclark tStep *= 0.5; 13621049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (precisely_zero(tStep)) { 13631049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return 0; 13641049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 13651049f1246e7be4ccb68001361efceb8933e6f81ccaryclark workT += tStep; 13661049f1246e7be4ccb68001361efceb8933e6f81ccaryclark workPt = fCurve.ptAtT(workT); 13671049f1246e7be4ccb68001361efceb8933e6f81ccaryclark coinW.setPerp(fCurve, workT, workPt, opp->fCurve); 13681049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDVector perpW = workPt - coinW.perpPt(); 13691049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if ((perpS.dot(perpW) >= 0) == (tStep < 0)) { 13701049f1246e7be4ccb68001361efceb8933e6f81ccaryclark tStep = -tStep; 13711049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 13721049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } while (!workPt.approximatelyEqual(coinW.perpPt())); 13731049f1246e7be4ccb68001361efceb8933e6f81ccaryclark double oppTTest = coinW.perpT(); 13741049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (!opp->fHead->contains(oppTTest)) { 13751049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return 0; 13761049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 13771049f1246e7be4ccb68001361efceb8933e6f81ccaryclark i->setMax(1); 13781049f1246e7be4ccb68001361efceb8933e6f81ccaryclark i->insert(workT, oppTTest, workPt); 13791049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return 1; 138054359294a7c9dc54802d512a5d891a35c1663392caryclark} 138154359294a7c9dc54802d512a5d891a35c1663392caryclark 138254359294a7c9dc54802d512a5d891a35c1663392caryclark 13831049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 13841049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::markSpanGone(SkTSpan<TCurve, OppCurve>* span) { 138554359294a7c9dc54802d512a5d891a35c1663392caryclark --fActiveCount; 138654359294a7c9dc54802d512a5d891a35c1663392caryclark span->fNext = fDeleted; 138754359294a7c9dc54802d512a5d891a35c1663392caryclark fDeleted = span; 138854359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!span->fDeleted); 138954359294a7c9dc54802d512a5d891a35c1663392caryclark span->fDeleted = true; 139054359294a7c9dc54802d512a5d891a35c1663392caryclark} 139154359294a7c9dc54802d512a5d891a35c1663392caryclark 13921049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 13931049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkbool SkTSect<TCurve, OppCurve>::matchedDirection(double t, const SkTSect<OppCurve, TCurve>* sect2, 13941049f1246e7be4ccb68001361efceb8933e6f81ccaryclark double t2) const { 139554359294a7c9dc54802d512a5d891a35c1663392caryclark SkDVector dxdy = this->fCurve.dxdyAtT(t); 139654359294a7c9dc54802d512a5d891a35c1663392caryclark SkDVector dxdy2 = sect2->fCurve.dxdyAtT(t2); 139754359294a7c9dc54802d512a5d891a35c1663392caryclark return dxdy.dot(dxdy2) >= 0; 139854359294a7c9dc54802d512a5d891a35c1663392caryclark} 139954359294a7c9dc54802d512a5d891a35c1663392caryclark 14001049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 14011049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::matchedDirCheck(double t, const SkTSect<OppCurve, TCurve>* sect2, 14021049f1246e7be4ccb68001361efceb8933e6f81ccaryclark double t2, bool* calcMatched, bool* oppMatched) const { 140354359294a7c9dc54802d512a5d891a35c1663392caryclark if (*calcMatched) { 140454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(*oppMatched == this->matchedDirection(t, sect2, t2)); 140554359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 140654359294a7c9dc54802d512a5d891a35c1663392caryclark *oppMatched = this->matchedDirection(t, sect2, t2); 140754359294a7c9dc54802d512a5d891a35c1663392caryclark *calcMatched = true; 140854359294a7c9dc54802d512a5d891a35c1663392caryclark } 140954359294a7c9dc54802d512a5d891a35c1663392caryclark} 141054359294a7c9dc54802d512a5d891a35c1663392caryclark 14111049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 14121049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::mergeCoincidence(SkTSect<OppCurve, TCurve>* sect2) { 141354359294a7c9dc54802d512a5d891a35c1663392caryclark double smallLimit = 0; 141454359294a7c9dc54802d512a5d891a35c1663392caryclark do { 141554359294a7c9dc54802d512a5d891a35c1663392caryclark // find the smallest unprocessed span 14161049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* smaller = NULL; 14171049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* test = fCoincident; 141854359294a7c9dc54802d512a5d891a35c1663392caryclark do { 141954359294a7c9dc54802d512a5d891a35c1663392caryclark if (test->fStartT < smallLimit) { 142054359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 142154359294a7c9dc54802d512a5d891a35c1663392caryclark } 142254359294a7c9dc54802d512a5d891a35c1663392caryclark if (smaller && smaller->fEndT < test->fStartT) { 142354359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 142454359294a7c9dc54802d512a5d891a35c1663392caryclark } 142554359294a7c9dc54802d512a5d891a35c1663392caryclark smaller = test; 142654359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((test = test->fNext)); 142754359294a7c9dc54802d512a5d891a35c1663392caryclark if (!smaller) { 142854359294a7c9dc54802d512a5d891a35c1663392caryclark return; 142954359294a7c9dc54802d512a5d891a35c1663392caryclark } 143054359294a7c9dc54802d512a5d891a35c1663392caryclark smallLimit = smaller->fEndT; 143154359294a7c9dc54802d512a5d891a35c1663392caryclark // find next larger span 14321049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* prior = NULL; 14331049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* larger = NULL; 14341049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* largerPrior = NULL; 143554359294a7c9dc54802d512a5d891a35c1663392caryclark test = fCoincident; 143654359294a7c9dc54802d512a5d891a35c1663392caryclark do { 143754359294a7c9dc54802d512a5d891a35c1663392caryclark if (test->fStartT < smaller->fEndT) { 143854359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 143954359294a7c9dc54802d512a5d891a35c1663392caryclark } 144054359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(test->fStartT != smaller->fEndT); 144154359294a7c9dc54802d512a5d891a35c1663392caryclark if (larger && larger->fStartT < test->fStartT) { 144254359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 144354359294a7c9dc54802d512a5d891a35c1663392caryclark } 144454359294a7c9dc54802d512a5d891a35c1663392caryclark largerPrior = prior; 144554359294a7c9dc54802d512a5d891a35c1663392caryclark larger = test; 144654359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((prior = test), (test = test->fNext)); 144754359294a7c9dc54802d512a5d891a35c1663392caryclark if (!larger) { 144854359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 144954359294a7c9dc54802d512a5d891a35c1663392caryclark } 145054359294a7c9dc54802d512a5d891a35c1663392caryclark // check middle t value to see if it is coincident as well 145154359294a7c9dc54802d512a5d891a35c1663392caryclark double midT = (smaller->fEndT + larger->fStartT) / 2; 145254359294a7c9dc54802d512a5d891a35c1663392caryclark SkDPoint midPt = fCurve.ptAtT(midT); 14531049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTCoincident<TCurve, OppCurve> coin; 145454359294a7c9dc54802d512a5d891a35c1663392caryclark coin.setPerp(fCurve, midT, midPt, sect2->fCurve); 145554359294a7c9dc54802d512a5d891a35c1663392caryclark if (coin.isCoincident()) { 145654359294a7c9dc54802d512a5d891a35c1663392caryclark smaller->fEndT = larger->fEndT; 145754359294a7c9dc54802d512a5d891a35c1663392caryclark smaller->fCoinEnd = larger->fCoinEnd; 145854359294a7c9dc54802d512a5d891a35c1663392caryclark if (largerPrior) { 145954359294a7c9dc54802d512a5d891a35c1663392caryclark largerPrior->fNext = larger->fNext; 146054359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 146154359294a7c9dc54802d512a5d891a35c1663392caryclark fCoincident = larger->fNext; 146254359294a7c9dc54802d512a5d891a35c1663392caryclark } 146354359294a7c9dc54802d512a5d891a35c1663392caryclark } 146454359294a7c9dc54802d512a5d891a35c1663392caryclark } while (true); 146554359294a7c9dc54802d512a5d891a35c1663392caryclark} 146654359294a7c9dc54802d512a5d891a35c1663392caryclark 14671049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 14681049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkSkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::prev( 14691049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* span) const { 14701049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* result = NULL; 14711049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* test = fHead; 147254359294a7c9dc54802d512a5d891a35c1663392caryclark while (span != test) { 147354359294a7c9dc54802d512a5d891a35c1663392caryclark result = test; 147454359294a7c9dc54802d512a5d891a35c1663392caryclark test = test->fNext; 147554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(test); 147645fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 147754359294a7c9dc54802d512a5d891a35c1663392caryclark return result; 147845fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 147945fa447460f70ec21d22cf4e1531490acfd3c578caryclark 14801049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 14811049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::recoverCollapsed() { 14821049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* deleted = fDeleted; 148345fa447460f70ec21d22cf4e1531490acfd3c578caryclark while (deleted) { 14841049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* delNext = deleted->fNext; 148545fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (deleted->fCollapsed) { 14861049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>** spanPtr = &fHead; 148745fa447460f70ec21d22cf4e1531490acfd3c578caryclark while (*spanPtr && (*spanPtr)->fEndT <= deleted->fStartT) { 148845fa447460f70ec21d22cf4e1531490acfd3c578caryclark spanPtr = &(*spanPtr)->fNext; 148945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 149045fa447460f70ec21d22cf4e1531490acfd3c578caryclark deleted->fNext = *spanPtr; 149145fa447460f70ec21d22cf4e1531490acfd3c578caryclark *spanPtr = deleted; 149245fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 149345fa447460f70ec21d22cf4e1531490acfd3c578caryclark deleted = delNext; 149445fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 149545fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 149645fa447460f70ec21d22cf4e1531490acfd3c578caryclark 14971049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 14981049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::removeAllBut(const SkTSpan<OppCurve, TCurve>* keep, 14991049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp) { 15001049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpanBounded<OppCurve, TCurve>* testBounded = span->fBounded; 150154359294a7c9dc54802d512a5d891a35c1663392caryclark while (testBounded) { 15021049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* bounded = testBounded->fBounded; 15031049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpanBounded<OppCurve, TCurve>* next = testBounded->fNext; 150454359294a7c9dc54802d512a5d891a35c1663392caryclark // may have been deleted when opp did 'remove all but' 150554359294a7c9dc54802d512a5d891a35c1663392caryclark if (bounded != keep && !bounded->fDeleted) { 150654359294a7c9dc54802d512a5d891a35c1663392caryclark SkAssertResult(SkDEBUGCODE(!) span->removeBounded(bounded)); 150754359294a7c9dc54802d512a5d891a35c1663392caryclark if (bounded->removeBounded(span)) { 150854359294a7c9dc54802d512a5d891a35c1663392caryclark opp->removeSpan(bounded); 150954359294a7c9dc54802d512a5d891a35c1663392caryclark } 151045fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 151154359294a7c9dc54802d512a5d891a35c1663392caryclark testBounded = next; 151245fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 151354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!span->fDeleted); 151454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(span->findOppSpan(keep)); 151554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(keep->findOppSpan(span)); 151654359294a7c9dc54802d512a5d891a35c1663392caryclark} 151754359294a7c9dc54802d512a5d891a35c1663392caryclark 15181049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 15191049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::removeByPerpendicular(SkTSect<OppCurve, TCurve>* opp) { 15201049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* test = fHead; 15211049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* next; 152254359294a7c9dc54802d512a5d891a35c1663392caryclark do { 152354359294a7c9dc54802d512a5d891a35c1663392caryclark next = test->fNext; 152454359294a7c9dc54802d512a5d891a35c1663392caryclark if (test->fCoinStart.perpT() < 0 || test->fCoinEnd.perpT() < 0) { 152554359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 152654359294a7c9dc54802d512a5d891a35c1663392caryclark } 152754359294a7c9dc54802d512a5d891a35c1663392caryclark SkDVector startV = test->fCoinStart.perpPt() - test->fPart[0]; 152854359294a7c9dc54802d512a5d891a35c1663392caryclark SkDVector endV = test->fCoinEnd.perpPt() - test->fPart[TCurve::kPointLast]; 152945fa447460f70ec21d22cf4e1531490acfd3c578caryclark#if DEBUG_T_SECT 153054359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s startV=(%1.9g,%1.9g) endV=(%1.9g,%1.9g) dot=%1.9g\n", __FUNCTION__, 153154359294a7c9dc54802d512a5d891a35c1663392caryclark startV.fX, startV.fY, endV.fX, endV.fY, startV.dot(endV)); 153245fa447460f70ec21d22cf4e1531490acfd3c578caryclark#endif 153354359294a7c9dc54802d512a5d891a35c1663392caryclark if (startV.dot(endV) <= 0) { 153454359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 153554359294a7c9dc54802d512a5d891a35c1663392caryclark } 153654359294a7c9dc54802d512a5d891a35c1663392caryclark this->removeSpans(test, opp); 153754359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((test = next)); 153845fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 153945fa447460f70ec21d22cf4e1531490acfd3c578caryclark 15401049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 15411049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::removeCoincident(SkTSpan<TCurve, OppCurve>* span, bool isBetween) { 154254359294a7c9dc54802d512a5d891a35c1663392caryclark this->unlinkSpan(span); 154354359294a7c9dc54802d512a5d891a35c1663392caryclark if (isBetween || between(0, span->fCoinStart.perpT(), 1)) { 154454359294a7c9dc54802d512a5d891a35c1663392caryclark --fActiveCount; 154554359294a7c9dc54802d512a5d891a35c1663392caryclark span->fNext = fCoincident; 154654359294a7c9dc54802d512a5d891a35c1663392caryclark fCoincident = span; 154754359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 154854359294a7c9dc54802d512a5d891a35c1663392caryclark this->markSpanGone(span); 1549ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 1550ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark} 1551ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark 15521049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 15531049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::removeSpan(SkTSpan<TCurve, OppCurve>* span) { 155454359294a7c9dc54802d512a5d891a35c1663392caryclark this->unlinkSpan(span); 155554359294a7c9dc54802d512a5d891a35c1663392caryclark this->markSpanGone(span); 155645fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 155745fa447460f70ec21d22cf4e1531490acfd3c578caryclark 15581049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 15591049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::removeSpanRange(SkTSpan<TCurve, OppCurve>* first, 15601049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* last) { 156154359294a7c9dc54802d512a5d891a35c1663392caryclark if (first == last) { 156254359294a7c9dc54802d512a5d891a35c1663392caryclark return; 156345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 15641049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* span = first; 156554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(span); 15661049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* final = last->fNext; 15671049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* next = span->fNext; 156854359294a7c9dc54802d512a5d891a35c1663392caryclark while ((span = next) && span != final) { 156954359294a7c9dc54802d512a5d891a35c1663392caryclark next = span->fNext; 157054359294a7c9dc54802d512a5d891a35c1663392caryclark this->markSpanGone(span); 157154359294a7c9dc54802d512a5d891a35c1663392caryclark } 157254359294a7c9dc54802d512a5d891a35c1663392caryclark if (final) { 157354359294a7c9dc54802d512a5d891a35c1663392caryclark final->fPrev = first; 157454359294a7c9dc54802d512a5d891a35c1663392caryclark } 157554359294a7c9dc54802d512a5d891a35c1663392caryclark first->fNext = final; 157654359294a7c9dc54802d512a5d891a35c1663392caryclark} 157754359294a7c9dc54802d512a5d891a35c1663392caryclark 15781049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 15791049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::removeSpans(SkTSpan<TCurve, OppCurve>* span, 15801049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSect<OppCurve, TCurve>* opp) { 15811049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpanBounded<OppCurve, TCurve>* bounded = span->fBounded; 158254359294a7c9dc54802d512a5d891a35c1663392caryclark while (bounded) { 15831049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* spanBounded = bounded->fBounded; 15841049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpanBounded<OppCurve, TCurve>* next = bounded->fNext; 158554359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->removeBounded(spanBounded)) { // shuffles last into position 0 158654359294a7c9dc54802d512a5d891a35c1663392caryclark this->removeSpan(span); 15870dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 158854359294a7c9dc54802d512a5d891a35c1663392caryclark if (spanBounded->removeBounded(span)) { 158954359294a7c9dc54802d512a5d891a35c1663392caryclark opp->removeSpan(spanBounded); 15900dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 159154359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!span->fDeleted || !opp->debugHasBounded(span)); 159254359294a7c9dc54802d512a5d891a35c1663392caryclark bounded = next; 159354359294a7c9dc54802d512a5d891a35c1663392caryclark } 159454359294a7c9dc54802d512a5d891a35c1663392caryclark} 159554359294a7c9dc54802d512a5d891a35c1663392caryclark 15961049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 15971049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkSkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::spanAtT(double t, 15981049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>** priorSpan) { 15991049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* test = fHead; 16001049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* prev = NULL; 160154359294a7c9dc54802d512a5d891a35c1663392caryclark while (test && test->fEndT < t) { 160254359294a7c9dc54802d512a5d891a35c1663392caryclark prev = test; 160354359294a7c9dc54802d512a5d891a35c1663392caryclark test = test->fNext; 160454359294a7c9dc54802d512a5d891a35c1663392caryclark } 160554359294a7c9dc54802d512a5d891a35c1663392caryclark *priorSpan = prev; 160654359294a7c9dc54802d512a5d891a35c1663392caryclark return test && test->fStartT <= t ? test : NULL; 160745fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 160845fa447460f70ec21d22cf4e1531490acfd3c578caryclark 16091049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 16101049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkSkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::tail() { 16111049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* result = fHead; 16121049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* next = fHead; 161345fa447460f70ec21d22cf4e1531490acfd3c578caryclark while ((next = next->fNext)) { 161445fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (next->fEndT > result->fEndT) { 161545fa447460f70ec21d22cf4e1531490acfd3c578caryclark result = next; 161645fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 161745fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 161845fa447460f70ec21d22cf4e1531490acfd3c578caryclark return result; 161945fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 162045fa447460f70ec21d22cf4e1531490acfd3c578caryclark 162145fa447460f70ec21d22cf4e1531490acfd3c578caryclark/* Each span has a range of opposite spans it intersects. After the span is split in two, 162245fa447460f70ec21d22cf4e1531490acfd3c578caryclark adjust the range to its new size */ 16231049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 16241049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::trim(SkTSpan<TCurve, OppCurve>* span, 16251049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSect<OppCurve, TCurve>* opp) { 162645fa447460f70ec21d22cf4e1531490acfd3c578caryclark span->initBounds(fCurve); 16271049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpanBounded<OppCurve, TCurve>* testBounded = span->fBounded; 162854359294a7c9dc54802d512a5d891a35c1663392caryclark while (testBounded) { 16291049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* test = testBounded->fBounded; 16301049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpanBounded<OppCurve, TCurve>* next = testBounded->fNext; 163154359294a7c9dc54802d512a5d891a35c1663392caryclark int oppSects, sects = this->intersects(span, opp, test, &oppSects); 163254359294a7c9dc54802d512a5d891a35c1663392caryclark if (sects >= 1) { 163354359294a7c9dc54802d512a5d891a35c1663392caryclark if (oppSects == 2) { 163454359294a7c9dc54802d512a5d891a35c1663392caryclark test->initBounds(opp->fCurve); 163554359294a7c9dc54802d512a5d891a35c1663392caryclark opp->removeAllBut(span, test, this); 163654359294a7c9dc54802d512a5d891a35c1663392caryclark } 163754359294a7c9dc54802d512a5d891a35c1663392caryclark if (sects == 2) { 163854359294a7c9dc54802d512a5d891a35c1663392caryclark span->initBounds(fCurve); 163954359294a7c9dc54802d512a5d891a35c1663392caryclark this->removeAllBut(test, span, opp); 164054359294a7c9dc54802d512a5d891a35c1663392caryclark return; 164154359294a7c9dc54802d512a5d891a35c1663392caryclark } 164245fa447460f70ec21d22cf4e1531490acfd3c578caryclark } else { 164354359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->removeBounded(test)) { 164454359294a7c9dc54802d512a5d891a35c1663392caryclark this->removeSpan(span); 164554359294a7c9dc54802d512a5d891a35c1663392caryclark } 164654359294a7c9dc54802d512a5d891a35c1663392caryclark if (test->removeBounded(span)) { 164754359294a7c9dc54802d512a5d891a35c1663392caryclark opp->removeSpan(test); 164854359294a7c9dc54802d512a5d891a35c1663392caryclark } 164945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 165054359294a7c9dc54802d512a5d891a35c1663392caryclark testBounded = next; 165145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 165245fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 165345fa447460f70ec21d22cf4e1531490acfd3c578caryclark 16541049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 16551049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::unlinkSpan(SkTSpan<TCurve, OppCurve>* span) { 16561049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* prev = span->fPrev; 16571049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* next = span->fNext; 165854359294a7c9dc54802d512a5d891a35c1663392caryclark if (prev) { 165954359294a7c9dc54802d512a5d891a35c1663392caryclark prev->fNext = next; 166054359294a7c9dc54802d512a5d891a35c1663392caryclark if (next) { 166154359294a7c9dc54802d512a5d891a35c1663392caryclark next->fPrev = prev; 166254359294a7c9dc54802d512a5d891a35c1663392caryclark } 166354359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 166454359294a7c9dc54802d512a5d891a35c1663392caryclark fHead = next; 166554359294a7c9dc54802d512a5d891a35c1663392caryclark if (next) { 166654359294a7c9dc54802d512a5d891a35c1663392caryclark next->fPrev = NULL; 166754359294a7c9dc54802d512a5d891a35c1663392caryclark } 166854359294a7c9dc54802d512a5d891a35c1663392caryclark } 166954359294a7c9dc54802d512a5d891a35c1663392caryclark} 167054359294a7c9dc54802d512a5d891a35c1663392caryclark 16711049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 16721049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkbool SkTSect<TCurve, OppCurve>::updateBounded(SkTSpan<TCurve, OppCurve>* first, 16731049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* last, SkTSpan<OppCurve, TCurve>* oppFirst) { 16741049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* test = first; 16751049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<TCurve, OppCurve>* final = last->next(); 167654359294a7c9dc54802d512a5d891a35c1663392caryclark bool deleteSpan = false; 167754359294a7c9dc54802d512a5d891a35c1663392caryclark do { 167854359294a7c9dc54802d512a5d891a35c1663392caryclark deleteSpan |= test->removeAllBounded(); 167954359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((test = test->fNext) != final); 168054359294a7c9dc54802d512a5d891a35c1663392caryclark first->fBounded = NULL; 168154359294a7c9dc54802d512a5d891a35c1663392caryclark first->addBounded(oppFirst, &fHeap); 168254359294a7c9dc54802d512a5d891a35c1663392caryclark // cannot call validate until remove span range is called 168354359294a7c9dc54802d512a5d891a35c1663392caryclark return deleteSpan; 168454359294a7c9dc54802d512a5d891a35c1663392caryclark} 168554359294a7c9dc54802d512a5d891a35c1663392caryclark 168654359294a7c9dc54802d512a5d891a35c1663392caryclark 16871049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 16881049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::validate() const { 168954359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_T_SECT 169045fa447460f70ec21d22cf4e1531490acfd3c578caryclark int count = 0; 169145fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (fHead) { 16921049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<TCurve, OppCurve>* span = fHead; 169345fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkASSERT(!span->fPrev); 169454359294a7c9dc54802d512a5d891a35c1663392caryclark SkDEBUGCODE(double last = 0); 169545fa447460f70ec21d22cf4e1531490acfd3c578caryclark do { 169645fa447460f70ec21d22cf4e1531490acfd3c578caryclark span->validate(); 169745fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkASSERT(span->fStartT >= last); 169854359294a7c9dc54802d512a5d891a35c1663392caryclark SkDEBUGCODE(last = span->fEndT); 169945fa447460f70ec21d22cf4e1531490acfd3c578caryclark ++count; 170045fa447460f70ec21d22cf4e1531490acfd3c578caryclark } while ((span = span->fNext) != NULL); 170145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 170245fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkASSERT(count == fActiveCount); 170345fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkASSERT(fActiveCount <= fDebugAllocatedCount); 170445fa447460f70ec21d22cf4e1531490acfd3c578caryclark int deletedCount = 0; 17051049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<TCurve, OppCurve>* deleted = fDeleted; 170645fa447460f70ec21d22cf4e1531490acfd3c578caryclark while (deleted) { 170745fa447460f70ec21d22cf4e1531490acfd3c578caryclark ++deletedCount; 170845fa447460f70ec21d22cf4e1531490acfd3c578caryclark deleted = deleted->fNext; 170945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 17101049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<TCurve, OppCurve>* coincident = fCoincident; 171154359294a7c9dc54802d512a5d891a35c1663392caryclark while (coincident) { 171254359294a7c9dc54802d512a5d891a35c1663392caryclark ++deletedCount; 171354359294a7c9dc54802d512a5d891a35c1663392caryclark coincident = coincident->fNext; 171454359294a7c9dc54802d512a5d891a35c1663392caryclark } 171545fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkASSERT(fActiveCount + deletedCount == fDebugAllocatedCount); 171654359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 171745fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 171854359294a7c9dc54802d512a5d891a35c1663392caryclark 17191049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 17201049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::validateBounded() const { 172154359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_T_SECT 172254359294a7c9dc54802d512a5d891a35c1663392caryclark if (!fHead) { 172354359294a7c9dc54802d512a5d891a35c1663392caryclark return; 172454359294a7c9dc54802d512a5d891a35c1663392caryclark } 17251049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<TCurve, OppCurve>* span = fHead; 172654359294a7c9dc54802d512a5d891a35c1663392caryclark do { 172754359294a7c9dc54802d512a5d891a35c1663392caryclark span->validateBounded(); 172854359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((span = span->fNext) != NULL); 172945fa447460f70ec21d22cf4e1531490acfd3c578caryclark#endif 173054359294a7c9dc54802d512a5d891a35c1663392caryclark} 173145fa447460f70ec21d22cf4e1531490acfd3c578caryclark 17321049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 17331049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkint SkTSect<TCurve, OppCurve>::EndsEqual(const SkTSect<TCurve, OppCurve>* sect1, 17341049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSect<OppCurve, TCurve>* sect2, SkIntersections* intersections) { 173545fa447460f70ec21d22cf4e1531490acfd3c578caryclark int zeroOneSet = 0; 173654359294a7c9dc54802d512a5d891a35c1663392caryclark if (sect1->fCurve[0] == sect2->fCurve[0]) { 173754359294a7c9dc54802d512a5d891a35c1663392caryclark zeroOneSet |= kZeroS1Set | kZeroS2Set; 173854359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->insert(0, 0, sect1->fCurve[0]); 173954359294a7c9dc54802d512a5d891a35c1663392caryclark } 17401049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (sect1->fCurve[0] == sect2->fCurve[OppCurve::kPointLast]) { 174154359294a7c9dc54802d512a5d891a35c1663392caryclark zeroOneSet |= kZeroS1Set | kOneS2Set; 174254359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->insert(0, 1, sect1->fCurve[0]); 174354359294a7c9dc54802d512a5d891a35c1663392caryclark } 174454359294a7c9dc54802d512a5d891a35c1663392caryclark if (sect1->fCurve[TCurve::kPointLast] == sect2->fCurve[0]) { 174554359294a7c9dc54802d512a5d891a35c1663392caryclark zeroOneSet |= kOneS1Set | kZeroS2Set; 174654359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->insert(1, 0, sect1->fCurve[TCurve::kPointLast]); 174754359294a7c9dc54802d512a5d891a35c1663392caryclark } 17481049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (sect1->fCurve[TCurve::kPointLast] == sect2->fCurve[OppCurve::kPointLast]) { 174954359294a7c9dc54802d512a5d891a35c1663392caryclark zeroOneSet |= kOneS1Set | kOneS2Set; 175054359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->insert(1, 1, sect1->fCurve[TCurve::kPointLast]); 175154359294a7c9dc54802d512a5d891a35c1663392caryclark } 175245fa447460f70ec21d22cf4e1531490acfd3c578caryclark // check for zero 175354359294a7c9dc54802d512a5d891a35c1663392caryclark if (!(zeroOneSet & (kZeroS1Set | kZeroS2Set)) 175454359294a7c9dc54802d512a5d891a35c1663392caryclark && sect1->fCurve[0].approximatelyEqual(sect2->fCurve[0])) { 175545fa447460f70ec21d22cf4e1531490acfd3c578caryclark zeroOneSet |= kZeroS1Set | kZeroS2Set; 175654359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->insertNear(0, 0, sect1->fCurve[0], sect2->fCurve[0]); 175754359294a7c9dc54802d512a5d891a35c1663392caryclark } 175854359294a7c9dc54802d512a5d891a35c1663392caryclark if (!(zeroOneSet & (kZeroS1Set | kOneS2Set)) 17591049f1246e7be4ccb68001361efceb8933e6f81ccaryclark && sect1->fCurve[0].approximatelyEqual(sect2->fCurve[OppCurve::kPointLast])) { 176045fa447460f70ec21d22cf4e1531490acfd3c578caryclark zeroOneSet |= kZeroS1Set | kOneS2Set; 17611049f1246e7be4ccb68001361efceb8933e6f81ccaryclark intersections->insertNear(0, 1, sect1->fCurve[0], sect2->fCurve[OppCurve::kPointLast]); 176254359294a7c9dc54802d512a5d891a35c1663392caryclark } 176345fa447460f70ec21d22cf4e1531490acfd3c578caryclark // check for one 176454359294a7c9dc54802d512a5d891a35c1663392caryclark if (!(zeroOneSet & (kOneS1Set | kZeroS2Set)) 176554359294a7c9dc54802d512a5d891a35c1663392caryclark && sect1->fCurve[TCurve::kPointLast].approximatelyEqual(sect2->fCurve[0])) { 176645fa447460f70ec21d22cf4e1531490acfd3c578caryclark zeroOneSet |= kOneS1Set | kZeroS2Set; 176754359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->insertNear(1, 0, sect1->fCurve[TCurve::kPointLast], sect2->fCurve[0]); 176854359294a7c9dc54802d512a5d891a35c1663392caryclark } 176954359294a7c9dc54802d512a5d891a35c1663392caryclark if (!(zeroOneSet & (kOneS1Set | kOneS2Set)) 177054359294a7c9dc54802d512a5d891a35c1663392caryclark && sect1->fCurve[TCurve::kPointLast].approximatelyEqual(sect2->fCurve[ 17711049f1246e7be4ccb68001361efceb8933e6f81ccaryclark OppCurve::kPointLast])) { 177245fa447460f70ec21d22cf4e1531490acfd3c578caryclark zeroOneSet |= kOneS1Set | kOneS2Set; 177354359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->insertNear(1, 1, sect1->fCurve[TCurve::kPointLast], 17741049f1246e7be4ccb68001361efceb8933e6f81ccaryclark sect2->fCurve[OppCurve::kPointLast]); 177545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 177645fa447460f70ec21d22cf4e1531490acfd3c578caryclark return zeroOneSet; 177745fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 177845fa447460f70ec21d22cf4e1531490acfd3c578caryclark 17791049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 178045fa447460f70ec21d22cf4e1531490acfd3c578caryclarkstruct SkClosestRecord { 178154359294a7c9dc54802d512a5d891a35c1663392caryclark bool operator<(const SkClosestRecord& rh) const { 178254359294a7c9dc54802d512a5d891a35c1663392caryclark return fClosest < rh.fClosest; 178354359294a7c9dc54802d512a5d891a35c1663392caryclark } 178454359294a7c9dc54802d512a5d891a35c1663392caryclark 178545fa447460f70ec21d22cf4e1531490acfd3c578caryclark void addIntersection(SkIntersections* intersections) const { 178645fa447460f70ec21d22cf4e1531490acfd3c578caryclark double r1t = fC1Index ? fC1Span->endT() : fC1Span->startT(); 178745fa447460f70ec21d22cf4e1531490acfd3c578caryclark double r2t = fC2Index ? fC2Span->endT() : fC2Span->startT(); 178845fa447460f70ec21d22cf4e1531490acfd3c578caryclark intersections->insert(r1t, r2t, fC1Span->part()[fC1Index]); 178945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 179045fa447460f70ec21d22cf4e1531490acfd3c578caryclark 17911049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void findEnd(const SkTSpan<TCurve, OppCurve>* span1, const SkTSpan<OppCurve, TCurve>* span2, 179245fa447460f70ec21d22cf4e1531490acfd3c578caryclark int c1Index, int c2Index) { 179345fa447460f70ec21d22cf4e1531490acfd3c578caryclark const TCurve& c1 = span1->part(); 17941049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const OppCurve& c2 = span2->part(); 179545fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (!c1[c1Index].approximatelyEqual(c2[c2Index])) { 179645fa447460f70ec21d22cf4e1531490acfd3c578caryclark return; 179745fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 179845fa447460f70ec21d22cf4e1531490acfd3c578caryclark double dist = c1[c1Index].distanceSquared(c2[c2Index]); 179945fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (fClosest < dist) { 180045fa447460f70ec21d22cf4e1531490acfd3c578caryclark return; 180145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 180245fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC1Span = span1; 180345fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC2Span = span2; 180445fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC1StartT = span1->startT(); 180545fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC1EndT = span1->endT(); 180645fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC2StartT = span2->startT(); 180745fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC2EndT = span2->endT(); 180845fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC1Index = c1Index; 180945fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC2Index = c2Index; 181045fa447460f70ec21d22cf4e1531490acfd3c578caryclark fClosest = dist; 181145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 181245fa447460f70ec21d22cf4e1531490acfd3c578caryclark 181345fa447460f70ec21d22cf4e1531490acfd3c578caryclark bool matesWith(const SkClosestRecord& mate) const { 181445fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkASSERT(fC1Span == mate.fC1Span || fC1Span->endT() <= mate.fC1Span->startT() 181545fa447460f70ec21d22cf4e1531490acfd3c578caryclark || mate.fC1Span->endT() <= fC1Span->startT()); 181645fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkASSERT(fC2Span == mate.fC2Span || fC2Span->endT() <= mate.fC2Span->startT() 181745fa447460f70ec21d22cf4e1531490acfd3c578caryclark || mate.fC2Span->endT() <= fC2Span->startT()); 181845fa447460f70ec21d22cf4e1531490acfd3c578caryclark return fC1Span == mate.fC1Span || fC1Span->endT() == mate.fC1Span->startT() 181945fa447460f70ec21d22cf4e1531490acfd3c578caryclark || fC1Span->startT() == mate.fC1Span->endT() 182045fa447460f70ec21d22cf4e1531490acfd3c578caryclark || fC2Span == mate.fC2Span 182145fa447460f70ec21d22cf4e1531490acfd3c578caryclark || fC2Span->endT() == mate.fC2Span->startT() 182245fa447460f70ec21d22cf4e1531490acfd3c578caryclark || fC2Span->startT() == mate.fC2Span->endT(); 182345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 182445fa447460f70ec21d22cf4e1531490acfd3c578caryclark 182545fa447460f70ec21d22cf4e1531490acfd3c578caryclark void merge(const SkClosestRecord& mate) { 182645fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC1Span = mate.fC1Span; 182745fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC2Span = mate.fC2Span; 182845fa447460f70ec21d22cf4e1531490acfd3c578caryclark fClosest = mate.fClosest; 182945fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC1Index = mate.fC1Index; 183045fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC2Index = mate.fC2Index; 183145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 183245fa447460f70ec21d22cf4e1531490acfd3c578caryclark 183345fa447460f70ec21d22cf4e1531490acfd3c578caryclark void reset() { 183445fa447460f70ec21d22cf4e1531490acfd3c578caryclark fClosest = FLT_MAX; 18351049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(fC1Span = NULL); 18361049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(fC2Span = NULL); 183745fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkDEBUGCODE(fC1Index = fC2Index = -1); 183845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 183945fa447460f70ec21d22cf4e1531490acfd3c578caryclark 184045fa447460f70ec21d22cf4e1531490acfd3c578caryclark void update(const SkClosestRecord& mate) { 184145fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC1StartT = SkTMin(fC1StartT, mate.fC1StartT); 184245fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC1EndT = SkTMax(fC1EndT, mate.fC1EndT); 184345fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC2StartT = SkTMin(fC2StartT, mate.fC2StartT); 184445fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC2EndT = SkTMax(fC2EndT, mate.fC2EndT); 184545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 184645fa447460f70ec21d22cf4e1531490acfd3c578caryclark 18471049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<TCurve, OppCurve>* fC1Span; 18481049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<OppCurve, TCurve>* fC2Span; 184945fa447460f70ec21d22cf4e1531490acfd3c578caryclark double fC1StartT; 185045fa447460f70ec21d22cf4e1531490acfd3c578caryclark double fC1EndT; 185145fa447460f70ec21d22cf4e1531490acfd3c578caryclark double fC2StartT; 185245fa447460f70ec21d22cf4e1531490acfd3c578caryclark double fC2EndT; 185345fa447460f70ec21d22cf4e1531490acfd3c578caryclark double fClosest; 185445fa447460f70ec21d22cf4e1531490acfd3c578caryclark int fC1Index; 185545fa447460f70ec21d22cf4e1531490acfd3c578caryclark int fC2Index; 185645fa447460f70ec21d22cf4e1531490acfd3c578caryclark}; 185745fa447460f70ec21d22cf4e1531490acfd3c578caryclark 18581049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 185945fa447460f70ec21d22cf4e1531490acfd3c578caryclarkstruct SkClosestSect { 186045fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkClosestSect() 186145fa447460f70ec21d22cf4e1531490acfd3c578caryclark : fUsed(0) { 186245fa447460f70ec21d22cf4e1531490acfd3c578caryclark fClosest.push_back().reset(); 186345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 186445fa447460f70ec21d22cf4e1531490acfd3c578caryclark 18651049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool find(const SkTSpan<TCurve, OppCurve>* span1, const SkTSpan<OppCurve, TCurve>* span2) { 18661049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkClosestRecord<TCurve, OppCurve>* record = &fClosest[fUsed]; 186745fa447460f70ec21d22cf4e1531490acfd3c578caryclark record->findEnd(span1, span2, 0, 0); 18681049f1246e7be4ccb68001361efceb8933e6f81ccaryclark record->findEnd(span1, span2, 0, OppCurve::kPointLast); 186945fa447460f70ec21d22cf4e1531490acfd3c578caryclark record->findEnd(span1, span2, TCurve::kPointLast, 0); 18701049f1246e7be4ccb68001361efceb8933e6f81ccaryclark record->findEnd(span1, span2, TCurve::kPointLast, OppCurve::kPointLast); 187145fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (record->fClosest == FLT_MAX) { 187254359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 187345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 187445fa447460f70ec21d22cf4e1531490acfd3c578caryclark for (int index = 0; index < fUsed; ++index) { 18751049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkClosestRecord<TCurve, OppCurve>* test = &fClosest[index]; 187645fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (test->matesWith(*record)) { 187745fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (test->fClosest > record->fClosest) { 187845fa447460f70ec21d22cf4e1531490acfd3c578caryclark test->merge(*record); 187945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 188045fa447460f70ec21d22cf4e1531490acfd3c578caryclark test->update(*record); 188145fa447460f70ec21d22cf4e1531490acfd3c578caryclark record->reset(); 188254359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 188345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 188445fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 188545fa447460f70ec21d22cf4e1531490acfd3c578caryclark ++fUsed; 188645fa447460f70ec21d22cf4e1531490acfd3c578caryclark fClosest.push_back().reset(); 188754359294a7c9dc54802d512a5d891a35c1663392caryclark return true; 188845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 188945fa447460f70ec21d22cf4e1531490acfd3c578caryclark 189045fa447460f70ec21d22cf4e1531490acfd3c578caryclark void finish(SkIntersections* intersections) const { 18911049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkSTArray<TCurve::kMaxIntersections * 3, 18921049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkClosestRecord<TCurve, OppCurve>*, true> closestPtrs; 189354359294a7c9dc54802d512a5d891a35c1663392caryclark for (int index = 0; index < fUsed; ++index) { 189454359294a7c9dc54802d512a5d891a35c1663392caryclark closestPtrs.push_back(&fClosest[index]); 189554359294a7c9dc54802d512a5d891a35c1663392caryclark } 18961049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTQSort<const SkClosestRecord<TCurve, OppCurve> >(closestPtrs.begin(), closestPtrs.end() 18971049f1246e7be4ccb68001361efceb8933e6f81ccaryclark - 1); 189845fa447460f70ec21d22cf4e1531490acfd3c578caryclark for (int index = 0; index < fUsed; ++index) { 18991049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkClosestRecord<TCurve, OppCurve>* test = closestPtrs[index]; 190054359294a7c9dc54802d512a5d891a35c1663392caryclark test->addIntersection(intersections); 190145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 190245fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 190345fa447460f70ec21d22cf4e1531490acfd3c578caryclark 190454359294a7c9dc54802d512a5d891a35c1663392caryclark // this is oversized so that an extra records can merge into final one 19051049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkSTArray<TCurve::kMaxIntersections * 2, SkClosestRecord<TCurve, OppCurve>, true> fClosest; 190645fa447460f70ec21d22cf4e1531490acfd3c578caryclark int fUsed; 190745fa447460f70ec21d22cf4e1531490acfd3c578caryclark}; 190845fa447460f70ec21d22cf4e1531490acfd3c578caryclark 190945fa447460f70ec21d22cf4e1531490acfd3c578caryclark// returns true if the rect is too small to consider 19101049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 19111049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::BinarySearch(SkTSect<TCurve, OppCurve>* sect1, 19121049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSect<OppCurve, TCurve>* sect2, SkIntersections* intersections) { 191354359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_T_SECT_DUMP > 1 191454359294a7c9dc54802d512a5d891a35c1663392caryclark gDumpTSectNum = 0; 191554359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 19161049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(sect1->fOppSect = sect2); 19171049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(sect2->fOppSect = sect1); 191845fa447460f70ec21d22cf4e1531490acfd3c578caryclark intersections->reset(); 19191049f1246e7be4ccb68001361efceb8933e6f81ccaryclark intersections->setMax(TCurve::kMaxIntersections * 3); // give extra for slop 19201049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* span1 = sect1->fHead; 19211049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* span2 = sect2->fHead; 192254359294a7c9dc54802d512a5d891a35c1663392caryclark int oppSect, sect = sect1->intersects(span1, sect2, span2, &oppSect); 192354359294a7c9dc54802d512a5d891a35c1663392caryclark// SkASSERT(between(0, sect, 2)); 192454359294a7c9dc54802d512a5d891a35c1663392caryclark if (!sect) { 192545fa447460f70ec21d22cf4e1531490acfd3c578caryclark return; 192645fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 192754359294a7c9dc54802d512a5d891a35c1663392caryclark if (sect == 2 && oppSect == 2) { 192845fa447460f70ec21d22cf4e1531490acfd3c578caryclark (void) EndsEqual(sect1, sect2, intersections); 192945fa447460f70ec21d22cf4e1531490acfd3c578caryclark return; 193045fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 193154359294a7c9dc54802d512a5d891a35c1663392caryclark span1->addBounded(span2, §1->fHeap); 193254359294a7c9dc54802d512a5d891a35c1663392caryclark span2->addBounded(span1, §2->fHeap); 193345fa447460f70ec21d22cf4e1531490acfd3c578caryclark do { 193445fa447460f70ec21d22cf4e1531490acfd3c578caryclark // find the largest bounds 19351049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* largest1 = sect1->boundsMax(); 193645fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (!largest1) { 193745fa447460f70ec21d22cf4e1531490acfd3c578caryclark break; 193845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 19391049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* largest2 = sect2->boundsMax(); 194045fa447460f70ec21d22cf4e1531490acfd3c578caryclark // split it 19411049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (!largest2 || (largest1 && (largest1->fBoundsMax > largest2->fBoundsMax 19421049f1246e7be4ccb68001361efceb8933e6f81ccaryclark || (!largest1->fCollapsed && largest2->fCollapsed)))) { 19431049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (largest1->fCollapsed) { 19441049f1246e7be4ccb68001361efceb8933e6f81ccaryclark break; 19451049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 19461049f1246e7be4ccb68001361efceb8933e6f81ccaryclark // trim parts that don't intersect the opposite 19471049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* half1 = sect1->addOne(); 19481049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (!half1->split(largest1, §1->fHeap)) { 19491049f1246e7be4ccb68001361efceb8933e6f81ccaryclark break; 19501049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 19511049f1246e7be4ccb68001361efceb8933e6f81ccaryclark sect1->trim(largest1, sect2); 19521049f1246e7be4ccb68001361efceb8933e6f81ccaryclark sect1->trim(half1, sect2); 19531049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } else { 19541049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (largest2->fCollapsed) { 19551049f1246e7be4ccb68001361efceb8933e6f81ccaryclark break; 19561049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 19571049f1246e7be4ccb68001361efceb8933e6f81ccaryclark // trim parts that don't intersect the opposite 19581049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* half2 = sect2->addOne(); 19591049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (!half2->split(largest2, §2->fHeap)) { 19601049f1246e7be4ccb68001361efceb8933e6f81ccaryclark break; 19611049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 19621049f1246e7be4ccb68001361efceb8933e6f81ccaryclark sect2->trim(largest2, sect1); 19631049f1246e7be4ccb68001361efceb8933e6f81ccaryclark sect2->trim(half2, sect1); 196445fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 196554359294a7c9dc54802d512a5d891a35c1663392caryclark sect1->validate(); 196654359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->validate(); 196745fa447460f70ec21d22cf4e1531490acfd3c578caryclark // if there are 9 or more continuous spans on both sects, suspect coincidence 196845fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT 196945fa447460f70ec21d22cf4e1531490acfd3c578caryclark && sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) { 197045fa447460f70ec21d22cf4e1531490acfd3c578caryclark sect1->coincidentCheck(sect2); 197154359294a7c9dc54802d512a5d891a35c1663392caryclark sect1->validate(); 197254359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->validate(); 197345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 197454359294a7c9dc54802d512a5d891a35c1663392caryclark if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT 197554359294a7c9dc54802d512a5d891a35c1663392caryclark && sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) { 197654359294a7c9dc54802d512a5d891a35c1663392caryclark sect1->computePerpendiculars(sect2, sect1->fHead, sect1->tail()); 197754359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->computePerpendiculars(sect1, sect2->fHead, sect2->tail()); 197854359294a7c9dc54802d512a5d891a35c1663392caryclark sect1->removeByPerpendicular(sect2); 197954359294a7c9dc54802d512a5d891a35c1663392caryclark sect1->validate(); 198054359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->validate(); 19811049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (sect1->collapsed() > TCurve::kMaxIntersections) { 19821049f1246e7be4ccb68001361efceb8933e6f81ccaryclark break; 19831049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 198454359294a7c9dc54802d512a5d891a35c1663392caryclark } 198554359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_T_SECT_DUMP 198654359294a7c9dc54802d512a5d891a35c1663392caryclark sect1->dumpBoth(sect2); 198745fa447460f70ec21d22cf4e1531490acfd3c578caryclark#endif 198845fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (!sect1->fHead || !sect2->fHead) { 198954359294a7c9dc54802d512a5d891a35c1663392caryclark break; 199045fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 199145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } while (true); 19921049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* coincident = sect1->fCoincident; 199354359294a7c9dc54802d512a5d891a35c1663392caryclark if (coincident) { 199454359294a7c9dc54802d512a5d891a35c1663392caryclark // if there is more than one coincident span, check loosely to see if they should be joined 199554359294a7c9dc54802d512a5d891a35c1663392caryclark if (coincident->fNext) { 199654359294a7c9dc54802d512a5d891a35c1663392caryclark sect1->mergeCoincidence(sect2); 199754359294a7c9dc54802d512a5d891a35c1663392caryclark coincident = sect1->fCoincident; 199854359294a7c9dc54802d512a5d891a35c1663392caryclark } 199954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(sect2->fCoincident); // courtesy check : coincidence only looks at sect 1 200045fa447460f70ec21d22cf4e1531490acfd3c578caryclark do { 200154359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(coincident->fCoinStart.isCoincident()); 200254359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(coincident->fCoinEnd.isCoincident()); 200354359294a7c9dc54802d512a5d891a35c1663392caryclark int index = intersections->insertCoincident(coincident->fStartT, 200454359294a7c9dc54802d512a5d891a35c1663392caryclark coincident->fCoinStart.perpT(), coincident->fPart[0]); 200554359294a7c9dc54802d512a5d891a35c1663392caryclark if ((intersections->insertCoincident(coincident->fEndT, 200654359294a7c9dc54802d512a5d891a35c1663392caryclark coincident->fCoinEnd.perpT(), 200754359294a7c9dc54802d512a5d891a35c1663392caryclark coincident->fPart[TCurve::kPointLast]) < 0) && index >= 0) { 200845fa447460f70ec21d22cf4e1531490acfd3c578caryclark intersections->clearCoincidence(index); 200945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 201054359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((coincident = coincident->fNext)); 201154359294a7c9dc54802d512a5d891a35c1663392caryclark } 20121049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int zeroOneSet = EndsEqual(sect1, sect2, intersections); 201354359294a7c9dc54802d512a5d891a35c1663392caryclark if (!sect1->fHead || !sect2->fHead) { 201454359294a7c9dc54802d512a5d891a35c1663392caryclark return; 201545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 201645fa447460f70ec21d22cf4e1531490acfd3c578caryclark sect1->recoverCollapsed(); 201745fa447460f70ec21d22cf4e1531490acfd3c578caryclark sect2->recoverCollapsed(); 20181049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* result1 = sect1->fHead; 201945fa447460f70ec21d22cf4e1531490acfd3c578caryclark // check heads and tails for zero and ones and insert them if we haven't already done so 20201049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<TCurve, OppCurve>* head1 = result1; 202145fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (!(zeroOneSet & kZeroS1Set) && approximately_less_than_zero(head1->fStartT)) { 202245fa447460f70ec21d22cf4e1531490acfd3c578caryclark const SkDPoint& start1 = sect1->fCurve[0]; 202354359294a7c9dc54802d512a5d891a35c1663392caryclark if (head1->isBounded()) { 202454359294a7c9dc54802d512a5d891a35c1663392caryclark double t = head1->closestBoundedT(start1); 202554359294a7c9dc54802d512a5d891a35c1663392caryclark if (sect2->fCurve.ptAtT(t).approximatelyEqual(start1)) { 202654359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->insert(0, t, start1); 202754359294a7c9dc54802d512a5d891a35c1663392caryclark } 202845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 202945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 20301049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<OppCurve, TCurve>* head2 = sect2->fHead; 203145fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (!(zeroOneSet & kZeroS2Set) && approximately_less_than_zero(head2->fStartT)) { 203245fa447460f70ec21d22cf4e1531490acfd3c578caryclark const SkDPoint& start2 = sect2->fCurve[0]; 203354359294a7c9dc54802d512a5d891a35c1663392caryclark if (head2->isBounded()) { 203454359294a7c9dc54802d512a5d891a35c1663392caryclark double t = head2->closestBoundedT(start2); 203554359294a7c9dc54802d512a5d891a35c1663392caryclark if (sect1->fCurve.ptAtT(t).approximatelyEqual(start2)) { 203654359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->insert(t, 0, start2); 203754359294a7c9dc54802d512a5d891a35c1663392caryclark } 203845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 203945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 20401049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<TCurve, OppCurve>* tail1 = sect1->tail(); 204145fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (!(zeroOneSet & kOneS1Set) && approximately_greater_than_one(tail1->fEndT)) { 204245fa447460f70ec21d22cf4e1531490acfd3c578caryclark const SkDPoint& end1 = sect1->fCurve[TCurve::kPointLast]; 204354359294a7c9dc54802d512a5d891a35c1663392caryclark if (tail1->isBounded()) { 204454359294a7c9dc54802d512a5d891a35c1663392caryclark double t = tail1->closestBoundedT(end1); 204554359294a7c9dc54802d512a5d891a35c1663392caryclark if (sect2->fCurve.ptAtT(t).approximatelyEqual(end1)) { 204654359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->insert(1, t, end1); 204754359294a7c9dc54802d512a5d891a35c1663392caryclark } 204845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 204945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 20501049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<OppCurve, TCurve>* tail2 = sect2->tail(); 205145fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (!(zeroOneSet & kOneS2Set) && approximately_greater_than_one(tail2->fEndT)) { 20521049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkDPoint& end2 = sect2->fCurve[OppCurve::kPointLast]; 205354359294a7c9dc54802d512a5d891a35c1663392caryclark if (tail2->isBounded()) { 205454359294a7c9dc54802d512a5d891a35c1663392caryclark double t = tail2->closestBoundedT(end2); 205554359294a7c9dc54802d512a5d891a35c1663392caryclark if (sect1->fCurve.ptAtT(t).approximatelyEqual(end2)) { 205654359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->insert(t, 1, end2); 205754359294a7c9dc54802d512a5d891a35c1663392caryclark } 205845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 205945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 20601049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkClosestSect<TCurve, OppCurve> closest; 206145fa447460f70ec21d22cf4e1531490acfd3c578caryclark do { 206245fa447460f70ec21d22cf4e1531490acfd3c578caryclark while (result1 && result1->fCoinStart.isCoincident() && result1->fCoinEnd.isCoincident()) { 206345fa447460f70ec21d22cf4e1531490acfd3c578caryclark result1 = result1->fNext; 206445fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 206545fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (!result1) { 206645fa447460f70ec21d22cf4e1531490acfd3c578caryclark break; 206745fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 20681049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* result2 = sect2->fHead; 206954359294a7c9dc54802d512a5d891a35c1663392caryclark bool found = false; 207045fa447460f70ec21d22cf4e1531490acfd3c578caryclark while (result2) { 207154359294a7c9dc54802d512a5d891a35c1663392caryclark found |= closest.find(result1, result2); 207245fa447460f70ec21d22cf4e1531490acfd3c578caryclark result2 = result2->fNext; 207345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 207445fa447460f70ec21d22cf4e1531490acfd3c578caryclark } while ((result1 = result1->fNext)); 207545fa447460f70ec21d22cf4e1531490acfd3c578caryclark closest.finish(intersections); 207654359294a7c9dc54802d512a5d891a35c1663392caryclark // if there is more than one intersection and it isn't already coincident, check 207754359294a7c9dc54802d512a5d891a35c1663392caryclark int last = intersections->used() - 1; 207854359294a7c9dc54802d512a5d891a35c1663392caryclark for (int index = 0; index < last; ) { 207954359294a7c9dc54802d512a5d891a35c1663392caryclark if (intersections->isCoincident(index) && intersections->isCoincident(index + 1)) { 208054359294a7c9dc54802d512a5d891a35c1663392caryclark ++index; 208154359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 208254359294a7c9dc54802d512a5d891a35c1663392caryclark } 208354359294a7c9dc54802d512a5d891a35c1663392caryclark double midT = ((*intersections)[0][index] + (*intersections)[0][index + 1]) / 2; 208454359294a7c9dc54802d512a5d891a35c1663392caryclark SkDPoint midPt = sect1->fCurve.ptAtT(midT); 208554359294a7c9dc54802d512a5d891a35c1663392caryclark // intersect perpendicular with opposite curve 20861049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTCoincident<TCurve, OppCurve> perp; 208754359294a7c9dc54802d512a5d891a35c1663392caryclark perp.setPerp(sect1->fCurve, midT, midPt, sect2->fCurve); 208854359294a7c9dc54802d512a5d891a35c1663392caryclark if (!perp.isCoincident()) { 208954359294a7c9dc54802d512a5d891a35c1663392caryclark ++index; 209054359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 209154359294a7c9dc54802d512a5d891a35c1663392caryclark } 209254359294a7c9dc54802d512a5d891a35c1663392caryclark if (intersections->isCoincident(index)) { 209354359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->removeOne(index); 209454359294a7c9dc54802d512a5d891a35c1663392caryclark --last; 209554359294a7c9dc54802d512a5d891a35c1663392caryclark } else if (intersections->isCoincident(index + 1)) { 209654359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->removeOne(index + 1); 209754359294a7c9dc54802d512a5d891a35c1663392caryclark --last; 209854359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 209954359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->setCoincident(index++); 210054359294a7c9dc54802d512a5d891a35c1663392caryclark } 210154359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->setCoincident(index); 210254359294a7c9dc54802d512a5d891a35c1663392caryclark } 210354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(intersections->used() <= TCurve::kMaxIntersections); 210445fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 2105