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 */ 712670eb63b743283cf6f0e6e568c1713756e4006deanm#ifndef SkPathOpsTSect_DEFINED 812670eb63b743283cf6f0e6e568c1713756e4006deanm#define SkPathOpsTSect_DEFINED 945fa447460f70ec21d22cf4e1531490acfd3c578caryclark 10c3cc5fa6de0a8237d9241dbf3e6c0786a9040069Herb Derby#include "SkArenaAlloc.h" 1154359294a7c9dc54802d512a5d891a35c1663392caryclark#include "SkPathOpsBounds.h" 1245fa447460f70ec21d22cf4e1531490acfd3c578caryclark#include "SkPathOpsRect.h" 1345fa447460f70ec21d22cf4e1531490acfd3c578caryclark#include "SkIntersections.h" 1454359294a7c9dc54802d512a5d891a35c1663392caryclark#include "SkTSort.h" 1545fa447460f70ec21d22cf4e1531490acfd3c578caryclark 16ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark#ifdef SK_DEBUG 17ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclarktypedef uint8_t SkOpDebugBool; 18ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark#else 19ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclarktypedef bool SkOpDebugBool; 20ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark#endif 21ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark 221049f1246e7be4ccb68001361efceb8933e6f81ccaryclark/* TCurve and OppCurve are one of { SkDQuadratic, SkDConic, SkDCubic } */ 231049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 2445fa447460f70ec21d22cf4e1531490acfd3c578caryclarkclass SkTCoincident { 2545fa447460f70ec21d22cf4e1531490acfd3c578caryclarkpublic: 26697ac1c138e8ff83cb90449ff378a000796f8a04caryclark SkTCoincident() { 27df386c54bd4b6643af42281631de42e84b07cea7caryclark this->init(); 281049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 291049f1246e7be4ccb68001361efceb8933e6f81ccaryclark 30ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark void debugInit() { 31ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark#ifdef SK_DEBUG 32ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark this->fPerpPt.fX = this->fPerpPt.fY = SK_ScalarNaN; 33ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark this->fPerpT = SK_ScalarNaN; 346c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark this->fMatch = 0xFF; 35ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark#endif 36ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark } 37ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark 38ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark char dumpIsCoincidentStr() const; 391049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void dump() const; 401049f1246e7be4ccb68001361efceb8933e6f81ccaryclark 416c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark bool isMatch() const { 426c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark SkASSERT(!!fMatch == fMatch); 436c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark return SkToBool(fMatch); 4445fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 4545fa447460f70ec21d22cf4e1531490acfd3c578caryclark 4645fa447460f70ec21d22cf4e1531490acfd3c578caryclark void init() { 47df386c54bd4b6643af42281631de42e84b07cea7caryclark fPerpT = -1; 486c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark fMatch = false; 49df386c54bd4b6643af42281631de42e84b07cea7caryclark fPerpPt.fX = fPerpPt.fY = SK_ScalarNaN; 5045fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 5145fa447460f70ec21d22cf4e1531490acfd3c578caryclark 5245fa447460f70ec21d22cf4e1531490acfd3c578caryclark void markCoincident() { 536c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark if (!fMatch) { 5445fa447460f70ec21d22cf4e1531490acfd3c578caryclark fPerpT = -1; 5545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 566c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark fMatch = true; 5745fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 5845fa447460f70ec21d22cf4e1531490acfd3c578caryclark 5945fa447460f70ec21d22cf4e1531490acfd3c578caryclark const SkDPoint& perpPt() const { 6045fa447460f70ec21d22cf4e1531490acfd3c578caryclark return fPerpPt; 6145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 6245fa447460f70ec21d22cf4e1531490acfd3c578caryclark 6345fa447460f70ec21d22cf4e1531490acfd3c578caryclark double perpT() const { 6445fa447460f70ec21d22cf4e1531490acfd3c578caryclark return fPerpT; 6545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 6645fa447460f70ec21d22cf4e1531490acfd3c578caryclark 671049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void setPerp(const TCurve& c1, double t, const SkDPoint& cPt, const OppCurve& ); 6845fa447460f70ec21d22cf4e1531490acfd3c578caryclark 6945fa447460f70ec21d22cf4e1531490acfd3c578caryclarkprivate: 7045fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkDPoint fPerpPt; 7145fa447460f70ec21d22cf4e1531490acfd3c578caryclark double fPerpT; // perpendicular intersection on opposite curve 726c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark SkOpDebugBool fMatch; 7345fa447460f70ec21d22cf4e1531490acfd3c578caryclark}; 7445fa447460f70ec21d22cf4e1531490acfd3c578caryclark 751049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> class SkTSect; 761049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> class SkTSpan; 7754359294a7c9dc54802d512a5d891a35c1663392caryclark 781049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 7954359294a7c9dc54802d512a5d891a35c1663392caryclarkstruct SkTSpanBounded { 801049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* fBounded; 8154359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSpanBounded* fNext; 8254359294a7c9dc54802d512a5d891a35c1663392caryclark}; 8345fa447460f70ec21d22cf4e1531490acfd3c578caryclark 8445fa447460f70ec21d22cf4e1531490acfd3c578caryclark/* Curve is either TCurve or SkDCubic */ 851049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 8645fa447460f70ec21d22cf4e1531490acfd3c578caryclarkclass SkTSpan { 8745fa447460f70ec21d22cf4e1531490acfd3c578caryclarkpublic: 88c3cc5fa6de0a8237d9241dbf3e6c0786a9040069Herb Derby void addBounded(SkTSpan<OppCurve, TCurve>* , SkArenaAlloc* ); 8945fa447460f70ec21d22cf4e1531490acfd3c578caryclark double closestBoundedT(const SkDPoint& pt) const; 9054359294a7c9dc54802d512a5d891a35c1663392caryclark bool contains(double t) const; 9145fa447460f70ec21d22cf4e1531490acfd3c578caryclark 921049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void debugInit() { 931049f1246e7be4ccb68001361efceb8933e6f81ccaryclark TCurve dummy; 941049f1246e7be4ccb68001361efceb8933e6f81ccaryclark dummy.debugInit(); 951049f1246e7be4ccb68001361efceb8933e6f81ccaryclark init(dummy); 961049f1246e7be4ccb68001361efceb8933e6f81ccaryclark initBounds(dummy); 97df386c54bd4b6643af42281631de42e84b07cea7caryclark fCoinStart.init(); 98df386c54bd4b6643af42281631de42e84b07cea7caryclark fCoinEnd.init(); 991049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 1001049f1246e7be4ccb68001361efceb8933e6f81ccaryclark 1011049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSect<OppCurve, TCurve>* debugOpp() const; 102643ede69216c073c2dd497c382577dc9fde36b3ecaryclark 103643ede69216c073c2dd497c382577dc9fde36b3ecaryclark#ifdef SK_DEBUG 104643ede69216c073c2dd497c382577dc9fde36b3ecaryclark void debugSetGlobalState(SkOpGlobalState* state) { 105643ede69216c073c2dd497c382577dc9fde36b3ecaryclark fDebugGlobalState = state; 106643ede69216c073c2dd497c382577dc9fde36b3ecaryclark } 107643ede69216c073c2dd497c382577dc9fde36b3ecaryclark#endif 108643ede69216c073c2dd497c382577dc9fde36b3ecaryclark 10954359294a7c9dc54802d512a5d891a35c1663392caryclark const SkTSpan* debugSpan(int ) const; 11054359294a7c9dc54802d512a5d891a35c1663392caryclark const SkTSpan* debugT(double t) const; 11154359294a7c9dc54802d512a5d891a35c1663392caryclark#ifdef SK_DEBUG 11254359294a7c9dc54802d512a5d891a35c1663392caryclark bool debugIsBefore(const SkTSpan* span) const; 11354359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 11454359294a7c9dc54802d512a5d891a35c1663392caryclark void dump() const; 11526ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark void dumpAll() const; 1161049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void dumpBounded(int id) const; 1171049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void dumpBounds() const; 1181049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void dumpCoin() const; 11945fa447460f70ec21d22cf4e1531490acfd3c578caryclark 12045fa447460f70ec21d22cf4e1531490acfd3c578caryclark double endT() const { 12145fa447460f70ec21d22cf4e1531490acfd3c578caryclark return fEndT; 12245fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 12345fa447460f70ec21d22cf4e1531490acfd3c578caryclark 1241049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* findOppSpan(const SkTSpan<OppCurve, TCurve>* opp) const; 12554359294a7c9dc54802d512a5d891a35c1663392caryclark 1261049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* findOppT(double t) const { 1271049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* result = oppT(t); 128643ede69216c073c2dd497c382577dc9fde36b3ecaryclark SkOPASSERT(result); 12945fa447460f70ec21d22cf4e1531490acfd3c578caryclark return result; 13045fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 13145fa447460f70ec21d22cf4e1531490acfd3c578caryclark 132643ede69216c073c2dd497c382577dc9fde36b3ecaryclark SkDEBUGCODE(SkOpGlobalState* globalState() const { return fDebugGlobalState; }) 133643ede69216c073c2dd497c382577dc9fde36b3ecaryclark 13454359294a7c9dc54802d512a5d891a35c1663392caryclark bool hasOppT(double t) const { 13554359294a7c9dc54802d512a5d891a35c1663392caryclark return SkToBool(oppT(t)); 13654359294a7c9dc54802d512a5d891a35c1663392caryclark } 13754359294a7c9dc54802d512a5d891a35c1663392caryclark 1381049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int hullsIntersect(SkTSpan<OppCurve, TCurve>* span, bool* start, bool* oppStart); 13954359294a7c9dc54802d512a5d891a35c1663392caryclark void init(const TCurve& ); 140a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark bool initBounds(const TCurve& ); 14154359294a7c9dc54802d512a5d891a35c1663392caryclark 14254359294a7c9dc54802d512a5d891a35c1663392caryclark bool isBounded() const { 14396fcdcc219d2a0d3579719b84b28bede76efba64halcanary return fBounded != nullptr; 14454359294a7c9dc54802d512a5d891a35c1663392caryclark } 14554359294a7c9dc54802d512a5d891a35c1663392caryclark 1461049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool linearsIntersect(SkTSpan<OppCurve, TCurve>* span); 14754359294a7c9dc54802d512a5d891a35c1663392caryclark double linearT(const SkDPoint& ) const; 14854359294a7c9dc54802d512a5d891a35c1663392caryclark 14954359294a7c9dc54802d512a5d891a35c1663392caryclark void markCoincident() { 15054359294a7c9dc54802d512a5d891a35c1663392caryclark fCoinStart.markCoincident(); 15154359294a7c9dc54802d512a5d891a35c1663392caryclark fCoinEnd.markCoincident(); 15254359294a7c9dc54802d512a5d891a35c1663392caryclark } 15345fa447460f70ec21d22cf4e1531490acfd3c578caryclark 15445fa447460f70ec21d22cf4e1531490acfd3c578caryclark const SkTSpan* next() const { 15545fa447460f70ec21d22cf4e1531490acfd3c578caryclark return fNext; 15645fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 15745fa447460f70ec21d22cf4e1531490acfd3c578caryclark 1581049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool onlyEndPointsInCommon(const SkTSpan<OppCurve, TCurve>* opp, bool* start, 1591049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool* oppStart, bool* ptsInCommon); 16054359294a7c9dc54802d512a5d891a35c1663392caryclark 16145fa447460f70ec21d22cf4e1531490acfd3c578caryclark const TCurve& part() const { 16245fa447460f70ec21d22cf4e1531490acfd3c578caryclark return fPart; 16345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 16445fa447460f70ec21d22cf4e1531490acfd3c578caryclark 16554359294a7c9dc54802d512a5d891a35c1663392caryclark bool removeAllBounded(); 1661049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool removeBounded(const SkTSpan<OppCurve, TCurve>* opp); 16754359294a7c9dc54802d512a5d891a35c1663392caryclark 16845fa447460f70ec21d22cf4e1531490acfd3c578caryclark void reset() { 16996fcdcc219d2a0d3579719b84b28bede76efba64halcanary fBounded = nullptr; 17054359294a7c9dc54802d512a5d891a35c1663392caryclark } 17154359294a7c9dc54802d512a5d891a35c1663392caryclark 17254359294a7c9dc54802d512a5d891a35c1663392caryclark void resetBounds(const TCurve& curve) { 17354359294a7c9dc54802d512a5d891a35c1663392caryclark fIsLinear = fIsLine = false; 17454359294a7c9dc54802d512a5d891a35c1663392caryclark initBounds(curve); 17545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 17645fa447460f70ec21d22cf4e1531490acfd3c578caryclark 177c3cc5fa6de0a8237d9241dbf3e6c0786a9040069Herb Derby bool split(SkTSpan* work, SkArenaAlloc* heap) { 17854359294a7c9dc54802d512a5d891a35c1663392caryclark return splitAt(work, (work->fStartT + work->fEndT) * 0.5, heap); 17945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 18045fa447460f70ec21d22cf4e1531490acfd3c578caryclark 181c3cc5fa6de0a8237d9241dbf3e6c0786a9040069Herb Derby bool splitAt(SkTSpan* work, double t, SkArenaAlloc* heap); 18245fa447460f70ec21d22cf4e1531490acfd3c578caryclark 18345fa447460f70ec21d22cf4e1531490acfd3c578caryclark double startT() const { 18445fa447460f70ec21d22cf4e1531490acfd3c578caryclark return fStartT; 18545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 18645fa447460f70ec21d22cf4e1531490acfd3c578caryclark 18754359294a7c9dc54802d512a5d891a35c1663392caryclarkprivate: 18845fa447460f70ec21d22cf4e1531490acfd3c578caryclark 18945fa447460f70ec21d22cf4e1531490acfd3c578caryclark // implementation is for testing only 19054359294a7c9dc54802d512a5d891a35c1663392caryclark int debugID() const { 19154359294a7c9dc54802d512a5d891a35c1663392caryclark return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1); 19245fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 19345fa447460f70ec21d22cf4e1531490acfd3c578caryclark 19454359294a7c9dc54802d512a5d891a35c1663392caryclark void dumpID() const; 19545fa447460f70ec21d22cf4e1531490acfd3c578caryclark 1961049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int hullCheck(const SkTSpan<OppCurve, TCurve>* opp, bool* start, bool* oppStart); 1971049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int linearIntersects(const OppCurve& ) const; 1981049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* oppT(double t) const; 19945fa447460f70ec21d22cf4e1531490acfd3c578caryclark 20045fa447460f70ec21d22cf4e1531490acfd3c578caryclark void validate() const; 20154359294a7c9dc54802d512a5d891a35c1663392caryclark void validateBounded() const; 20254359294a7c9dc54802d512a5d891a35c1663392caryclark void validatePerpT(double oppT) const; 20354359294a7c9dc54802d512a5d891a35c1663392caryclark void validatePerpPt(double t, const SkDPoint& ) const; 20445fa447460f70ec21d22cf4e1531490acfd3c578caryclark 20545fa447460f70ec21d22cf4e1531490acfd3c578caryclark TCurve fPart; 2061049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTCoincident<TCurve, OppCurve> fCoinStart; 2071049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTCoincident<TCurve, OppCurve> fCoinEnd; 2081049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpanBounded<OppCurve, TCurve>* fBounded; 20945fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkTSpan* fPrev; 21045fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkTSpan* fNext; 21145fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkDRect fBounds; 21245fa447460f70ec21d22cf4e1531490acfd3c578caryclark double fStartT; 21345fa447460f70ec21d22cf4e1531490acfd3c578caryclark double fEndT; 21445fa447460f70ec21d22cf4e1531490acfd3c578caryclark double fBoundsMax; 215ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark SkOpDebugBool fCollapsed; 216ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark SkOpDebugBool fHasPerp; 217ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark SkOpDebugBool fIsLinear; 218ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark SkOpDebugBool fIsLine; 219ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark SkOpDebugBool fDeleted; 220643ede69216c073c2dd497c382577dc9fde36b3ecaryclark SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState); 221ceeaa78713dde9cc6e3ccd688aca6021b260af4dcsmartdalton SkDEBUGCODE(SkTSect<TCurve, OppCurve>* fDebugSect); 22254359294a7c9dc54802d512a5d891a35c1663392caryclark PATH_OPS_DEBUG_T_SECT_CODE(int fID); 2231049f1246e7be4ccb68001361efceb8933e6f81ccaryclark friend class SkTSect<TCurve, OppCurve>; 2241049f1246e7be4ccb68001361efceb8933e6f81ccaryclark friend class SkTSect<OppCurve, TCurve>; 2251049f1246e7be4ccb68001361efceb8933e6f81ccaryclark friend class SkTSpan<OppCurve, TCurve>; 22645fa447460f70ec21d22cf4e1531490acfd3c578caryclark}; 22745fa447460f70ec21d22cf4e1531490acfd3c578caryclark 2281049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 22945fa447460f70ec21d22cf4e1531490acfd3c578caryclarkclass SkTSect { 23045fa447460f70ec21d22cf4e1531490acfd3c578caryclarkpublic: 231e25a4f6cbeaccfdc34cf031103f0fbc3e53a3ee5caryclark SkTSect(const TCurve& c SkDEBUGPARAMS(SkOpGlobalState* ) PATH_OPS_DEBUG_T_SECT_PARAMS(int id)); 2321049f1246e7be4ccb68001361efceb8933e6f81ccaryclark static void BinarySearch(SkTSect* sect1, SkTSect<OppCurve, TCurve>* sect2, 2331049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkIntersections* intersections); 23445fa447460f70ec21d22cf4e1531490acfd3c578caryclark 235e25a4f6cbeaccfdc34cf031103f0fbc3e53a3ee5caryclark SkDEBUGCODE(SkOpGlobalState* globalState() { return fDebugGlobalState; }) 23645fa447460f70ec21d22cf4e1531490acfd3c578caryclark // for testing only 2371049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool debugHasBounded(const SkTSpan<OppCurve, TCurve>* ) const; 23854359294a7c9dc54802d512a5d891a35c1663392caryclark 2391049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSect<OppCurve, TCurve>* debugOpp() const { 24096fcdcc219d2a0d3579719b84b28bede76efba64halcanary return SkDEBUGRELEASE(fOppSect, nullptr); 24154359294a7c9dc54802d512a5d891a35c1663392caryclark } 24254359294a7c9dc54802d512a5d891a35c1663392caryclark 2431049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<TCurve, OppCurve>* debugSpan(int id) const; 2441049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<TCurve, OppCurve>* debugT(double t) const; 24545fa447460f70ec21d22cf4e1531490acfd3c578caryclark void dump() const; 2461049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void dumpBoth(SkTSect<OppCurve, TCurve>* ) const; 2471049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void dumpBounded(int id) const; 2481049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void dumpBounds() const; 24954359294a7c9dc54802d512a5d891a35c1663392caryclark void dumpCoin() const; 25054359294a7c9dc54802d512a5d891a35c1663392caryclark void dumpCoinCurves() const; 25145fa447460f70ec21d22cf4e1531490acfd3c578caryclark void dumpCurves() const; 25245fa447460f70ec21d22cf4e1531490acfd3c578caryclark 25345fa447460f70ec21d22cf4e1531490acfd3c578caryclarkprivate: 25445fa447460f70ec21d22cf4e1531490acfd3c578caryclark enum { 25545fa447460f70ec21d22cf4e1531490acfd3c578caryclark kZeroS1Set = 1, 25645fa447460f70ec21d22cf4e1531490acfd3c578caryclark kOneS1Set = 2, 25745fa447460f70ec21d22cf4e1531490acfd3c578caryclark kZeroS2Set = 4, 25845fa447460f70ec21d22cf4e1531490acfd3c578caryclark kOneS2Set = 8 25945fa447460f70ec21d22cf4e1531490acfd3c578caryclark }; 26045fa447460f70ec21d22cf4e1531490acfd3c578caryclark 2611049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* addFollowing(SkTSpan<TCurve, OppCurve>* prior); 2621049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void addForPerp(SkTSpan<OppCurve, TCurve>* span, double t); 2631049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* addOne(); 26455888e44171ffd48b591d19256884a969fe4da17caryclark 2651049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* addSplitAt(SkTSpan<TCurve, OppCurve>* span, double t) { 2661049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* result = this->addOne(); 267643ede69216c073c2dd497c382577dc9fde36b3ecaryclark SkDEBUGCODE(result->debugSetGlobalState(this->globalState())); 26854359294a7c9dc54802d512a5d891a35c1663392caryclark result->splitAt(span, t, &fHeap); 26954359294a7c9dc54802d512a5d891a35c1663392caryclark result->initBounds(fCurve); 27054359294a7c9dc54802d512a5d891a35c1663392caryclark span->initBounds(fCurve); 27154359294a7c9dc54802d512a5d891a35c1663392caryclark return result; 27254359294a7c9dc54802d512a5d891a35c1663392caryclark } 27354359294a7c9dc54802d512a5d891a35c1663392caryclark 2741049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool binarySearchCoin(SkTSect<OppCurve, TCurve>* , double tStart, double tStep, double* t, 2751049f1246e7be4ccb68001361efceb8933e6f81ccaryclark double* oppT); 2761049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* boundsMax() const; 277ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark bool coincidentCheck(SkTSect<OppCurve, TCurve>* sect2); 27826ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark void coincidentForce(SkTSect<OppCurve, TCurve>* sect2, double start1s, double start1e); 27954359294a7c9dc54802d512a5d891a35c1663392caryclark bool coincidentHasT(double t); 2801049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int collapsed() const; 2811049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void computePerpendiculars(SkTSect<OppCurve, TCurve>* sect2, SkTSpan<TCurve, OppCurve>* first, 2821049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* last); 2831049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int countConsecutiveSpans(SkTSpan<TCurve, OppCurve>* first, 2841049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>** last) const; 28554359294a7c9dc54802d512a5d891a35c1663392caryclark 28654359294a7c9dc54802d512a5d891a35c1663392caryclark int debugID() const { 28754359294a7c9dc54802d512a5d891a35c1663392caryclark return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1); 28854359294a7c9dc54802d512a5d891a35c1663392caryclark } 28954359294a7c9dc54802d512a5d891a35c1663392caryclark 290ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark bool deleteEmptySpans(); 2911049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void dumpCommon(const SkTSpan<TCurve, OppCurve>* ) const; 2921049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void dumpCommonCurves(const SkTSpan<TCurve, OppCurve>* ) const; 2931049f1246e7be4ccb68001361efceb8933e6f81ccaryclark static int EndsEqual(const SkTSect* sect1, const SkTSect<OppCurve, TCurve>* sect2, 2941049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkIntersections* ); 295ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark bool extractCoincident(SkTSect<OppCurve, TCurve>* sect2, SkTSpan<TCurve, OppCurve>* first, 296ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark SkTSpan<TCurve, OppCurve>* last, SkTSpan<TCurve, OppCurve>** result); 2971049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* findCoincidentRun(SkTSpan<TCurve, OppCurve>* first, 2981049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>** lastPtr); 2991049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int intersects(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp, 3001049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* oppSpan, int* oppResult); 301ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark bool isParallel(const SkDLine& thisLine, const SkTSect<OppCurve, TCurve>* opp) const; 3021049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int linesIntersect(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp, 3031049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* oppSpan, SkIntersections* ); 304ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark bool markSpanGone(SkTSpan<TCurve, OppCurve>* span); 3051049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool matchedDirection(double t, const SkTSect<OppCurve, TCurve>* sect2, double t2) const; 3061049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void matchedDirCheck(double t, const SkTSect<OppCurve, TCurve>* sect2, double t2, 30754359294a7c9dc54802d512a5d891a35c1663392caryclark bool* calcMatched, bool* oppMatched) const; 3081049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void mergeCoincidence(SkTSect<OppCurve, TCurve>* sect2); 3091049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* prev(SkTSpan<TCurve, OppCurve>* ) const; 3101049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void removeByPerpendicular(SkTSect<OppCurve, TCurve>* opp); 31145fa447460f70ec21d22cf4e1531490acfd3c578caryclark void recoverCollapsed(); 3121049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void removeCoincident(SkTSpan<TCurve, OppCurve>* span, bool isBetween); 3131049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void removeAllBut(const SkTSpan<OppCurve, TCurve>* keep, SkTSpan<TCurve, OppCurve>* span, 3141049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSect<OppCurve, TCurve>* opp); 315ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark bool removeSpan(SkTSpan<TCurve, OppCurve>* span); 3161049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void removeSpanRange(SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last); 3171049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void removeSpans(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp); 31834efb7039851d7796ba06aa58e5c5882ede503accaryclark void removedEndCheck(SkTSpan<TCurve, OppCurve>* span); 31934efb7039851d7796ba06aa58e5c5882ede503accaryclark 320c3cc5fa6de0a8237d9241dbf3e6c0786a9040069Herb Derby void resetRemovedEnds() { 32134efb7039851d7796ba06aa58e5c5882ede503accaryclark fRemovedStartT = fRemovedEndT = false; 32234efb7039851d7796ba06aa58e5c5882ede503accaryclark } 32334efb7039851d7796ba06aa58e5c5882ede503accaryclark 3241049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* spanAtT(double t, SkTSpan<TCurve, OppCurve>** priorSpan); 3251049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* tail(); 326a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark bool trim(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp); 3271049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void unlinkSpan(SkTSpan<TCurve, OppCurve>* span); 3281049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool updateBounded(SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last, 3291049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* oppFirst); 3300dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed void validate() const; 33154359294a7c9dc54802d512a5d891a35c1663392caryclark void validateBounded() const; 33254359294a7c9dc54802d512a5d891a35c1663392caryclark 33345fa447460f70ec21d22cf4e1531490acfd3c578caryclark const TCurve& fCurve; 334c3cc5fa6de0a8237d9241dbf3e6c0786a9040069Herb Derby SkArenaAlloc fHeap; 3351049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* fHead; 3361049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* fCoincident; 3371049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* fDeleted; 33845fa447460f70ec21d22cf4e1531490acfd3c578caryclark int fActiveCount; 3396c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark bool fRemovedStartT; 3406c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark bool fRemovedEndT; 341e25a4f6cbeaccfdc34cf031103f0fbc3e53a3ee5caryclark SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState); 342ceeaa78713dde9cc6e3ccd688aca6021b260af4dcsmartdalton SkDEBUGCODE(SkTSect<OppCurve, TCurve>* fOppSect); 34354359294a7c9dc54802d512a5d891a35c1663392caryclark PATH_OPS_DEBUG_T_SECT_CODE(int fID); 34454359294a7c9dc54802d512a5d891a35c1663392caryclark PATH_OPS_DEBUG_T_SECT_CODE(int fDebugCount); 34545fa447460f70ec21d22cf4e1531490acfd3c578caryclark#if DEBUG_T_SECT 34645fa447460f70ec21d22cf4e1531490acfd3c578caryclark int fDebugAllocatedCount; 34745fa447460f70ec21d22cf4e1531490acfd3c578caryclark#endif 3481049f1246e7be4ccb68001361efceb8933e6f81ccaryclark friend class SkTSpan<TCurve, OppCurve>; 3491049f1246e7be4ccb68001361efceb8933e6f81ccaryclark friend class SkTSpan<OppCurve, TCurve>; 3501049f1246e7be4ccb68001361efceb8933e6f81ccaryclark friend class SkTSect<OppCurve, TCurve>; 35145fa447460f70ec21d22cf4e1531490acfd3c578caryclark}; 35245fa447460f70ec21d22cf4e1531490acfd3c578caryclark 35345fa447460f70ec21d22cf4e1531490acfd3c578caryclark#define COINCIDENT_SPAN_COUNT 9 35445fa447460f70ec21d22cf4e1531490acfd3c578caryclark 3551049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 3561049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTCoincident<TCurve, OppCurve>::setPerp(const TCurve& c1, double t, 3571049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkDPoint& cPt, const OppCurve& c2) { 35845fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkDVector dxdy = c1.dxdyAtT(t); 35945fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }}; 360a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark SkIntersections i SkDEBUGCODE((c1.globalState())); 36145fa447460f70ec21d22cf4e1531490acfd3c578caryclark int used = i.intersectRay(c2, perp); 36245fa447460f70ec21d22cf4e1531490acfd3c578caryclark // only keep closest 36354359294a7c9dc54802d512a5d891a35c1663392caryclark if (used == 0 || used == 3) { 364df386c54bd4b6643af42281631de42e84b07cea7caryclark this->init(); 36545fa447460f70ec21d22cf4e1531490acfd3c578caryclark return; 36655888e44171ffd48b591d19256884a969fe4da17caryclark } 36745fa447460f70ec21d22cf4e1531490acfd3c578caryclark fPerpT = i[0][0]; 36845fa447460f70ec21d22cf4e1531490acfd3c578caryclark fPerpPt = i.pt(0); 36945fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkASSERT(used <= 2); 37045fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (used == 2) { 37145fa447460f70ec21d22cf4e1531490acfd3c578caryclark double distSq = (fPerpPt - cPt).lengthSquared(); 37245fa447460f70ec21d22cf4e1531490acfd3c578caryclark double dist2Sq = (i.pt(1) - cPt).lengthSquared(); 37345fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (dist2Sq < distSq) { 37445fa447460f70ec21d22cf4e1531490acfd3c578caryclark fPerpT = i[0][1]; 37545fa447460f70ec21d22cf4e1531490acfd3c578caryclark fPerpPt = i.pt(1); 37645fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 37745fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 37854359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_T_SECT 3791049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDebugf("setPerp t=%1.9g cPt=(%1.9g,%1.9g) %s oppT=%1.9g fPerpPt=(%1.9g,%1.9g)\n", 3801049f1246e7be4ccb68001361efceb8933e6f81ccaryclark t, cPt.fX, cPt.fY, 3811049f1246e7be4ccb68001361efceb8933e6f81ccaryclark cPt.approximatelyEqual(fPerpPt) ? "==" : "!=", fPerpT, fPerpPt.fX, fPerpPt.fY); 38254359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 3836c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark fMatch = cPt.approximatelyEqual(fPerpPt); 38445fa447460f70ec21d22cf4e1531490acfd3c578caryclark#if DEBUG_T_SECT 3856c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark if (fMatch) { 38645fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkDebugf(""); // allow setting breakpoint 38745fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 38845fa447460f70ec21d22cf4e1531490acfd3c578caryclark#endif 38945fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 39045fa447460f70ec21d22cf4e1531490acfd3c578caryclark 3911049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 392c3cc5fa6de0a8237d9241dbf3e6c0786a9040069Herb Derbyvoid SkTSpan<TCurve, OppCurve>::addBounded(SkTSpan<OppCurve, TCurve>* span, SkArenaAlloc* heap) { 393c3cc5fa6de0a8237d9241dbf3e6c0786a9040069Herb Derby SkTSpanBounded<OppCurve, TCurve>* bounded = heap->make<SkTSpanBounded<OppCurve, TCurve>>(); 39454359294a7c9dc54802d512a5d891a35c1663392caryclark bounded->fBounded = span; 39554359294a7c9dc54802d512a5d891a35c1663392caryclark bounded->fNext = fBounded; 39654359294a7c9dc54802d512a5d891a35c1663392caryclark fBounded = bounded; 39745fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 39845fa447460f70ec21d22cf4e1531490acfd3c578caryclark 3991049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 4001049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkSkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::addFollowing( 4011049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* prior) { 4021049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* result = this->addOne(); 403643ede69216c073c2dd497c382577dc9fde36b3ecaryclark SkDEBUGCODE(result->debugSetGlobalState(this->globalState())); 40454359294a7c9dc54802d512a5d891a35c1663392caryclark result->fStartT = prior ? prior->fEndT : 0; 4051049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* next = prior ? prior->fNext : fHead; 40654359294a7c9dc54802d512a5d891a35c1663392caryclark result->fEndT = next ? next->fStartT : 1; 40754359294a7c9dc54802d512a5d891a35c1663392caryclark result->fPrev = prior; 40854359294a7c9dc54802d512a5d891a35c1663392caryclark result->fNext = next; 40954359294a7c9dc54802d512a5d891a35c1663392caryclark if (prior) { 41054359294a7c9dc54802d512a5d891a35c1663392caryclark prior->fNext = result; 41154359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 41254359294a7c9dc54802d512a5d891a35c1663392caryclark fHead = result; 41354359294a7c9dc54802d512a5d891a35c1663392caryclark } 41454359294a7c9dc54802d512a5d891a35c1663392caryclark if (next) { 41554359294a7c9dc54802d512a5d891a35c1663392caryclark next->fPrev = result; 416ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 41754359294a7c9dc54802d512a5d891a35c1663392caryclark result->resetBounds(fCurve); 418643ede69216c073c2dd497c382577dc9fde36b3ecaryclark result->validate(); 41954359294a7c9dc54802d512a5d891a35c1663392caryclark return result; 42054359294a7c9dc54802d512a5d891a35c1663392caryclark} 42154359294a7c9dc54802d512a5d891a35c1663392caryclark 4221049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 4231049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::addForPerp(SkTSpan<OppCurve, TCurve>* span, double t) { 42454359294a7c9dc54802d512a5d891a35c1663392caryclark if (!span->hasOppT(t)) { 4251049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* priorSpan; 4261049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* opp = this->spanAtT(t, &priorSpan); 42754359294a7c9dc54802d512a5d891a35c1663392caryclark if (!opp) { 42854359294a7c9dc54802d512a5d891a35c1663392caryclark opp = this->addFollowing(priorSpan); 42954359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_PERP 43026ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark SkDebugf("%s priorSpan=%d t=%1.9g opp=%d\n", __FUNCTION__, priorSpan ? 43126ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark priorSpan->debugID() : -1, t, opp->debugID()); 43254359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 43354359294a7c9dc54802d512a5d891a35c1663392caryclark } 43454359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_PERP 43554359294a7c9dc54802d512a5d891a35c1663392caryclark opp->dump(); SkDebugf("\n"); 43626ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark SkDebugf("%s addBounded span=%d opp=%d\n", __FUNCTION__, priorSpan ? 43726ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark priorSpan->debugID() : -1, opp->debugID()); 43845fa447460f70ec21d22cf4e1531490acfd3c578caryclark#endif 43954359294a7c9dc54802d512a5d891a35c1663392caryclark opp->addBounded(span, &fHeap); 44054359294a7c9dc54802d512a5d891a35c1663392caryclark span->addBounded(opp, &fHeap); 44154359294a7c9dc54802d512a5d891a35c1663392caryclark } 44254359294a7c9dc54802d512a5d891a35c1663392caryclark this->validate(); 4431049f1246e7be4ccb68001361efceb8933e6f81ccaryclark#if DEBUG_T_SECT 44454359294a7c9dc54802d512a5d891a35c1663392caryclark span->validatePerpT(t); 4451049f1246e7be4ccb68001361efceb8933e6f81ccaryclark#endif 44645fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 44745fa447460f70ec21d22cf4e1531490acfd3c578caryclark 4481049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 4491049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkdouble SkTSpan<TCurve, OppCurve>::closestBoundedT(const SkDPoint& pt) const { 45045fa447460f70ec21d22cf4e1531490acfd3c578caryclark double result = -1; 451343382e3acc8369f7bd4328e7c807255b5776fe5caryclark double closest = DBL_MAX; 4521049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded; 45354359294a7c9dc54802d512a5d891a35c1663392caryclark while (testBounded) { 4541049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<OppCurve, TCurve>* test = testBounded->fBounded; 45545fa447460f70ec21d22cf4e1531490acfd3c578caryclark double startDist = test->fPart[0].distanceSquared(pt); 45645fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (closest > startDist) { 45745fa447460f70ec21d22cf4e1531490acfd3c578caryclark closest = startDist; 45845fa447460f70ec21d22cf4e1531490acfd3c578caryclark result = test->fStartT; 45945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 4601049f1246e7be4ccb68001361efceb8933e6f81ccaryclark double endDist = test->fPart[OppCurve::kPointLast].distanceSquared(pt); 46145fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (closest > endDist) { 46245fa447460f70ec21d22cf4e1531490acfd3c578caryclark closest = endDist; 46345fa447460f70ec21d22cf4e1531490acfd3c578caryclark result = test->fEndT; 46445fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 46554359294a7c9dc54802d512a5d891a35c1663392caryclark testBounded = testBounded->fNext; 46645fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 46745fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkASSERT(between(0, result, 1)); 46845fa447460f70ec21d22cf4e1531490acfd3c578caryclark return result; 46945fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 47045fa447460f70ec21d22cf4e1531490acfd3c578caryclark 47154359294a7c9dc54802d512a5d891a35c1663392caryclark#ifdef SK_DEBUG 4721049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 4731049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkbool SkTSpan<TCurve, OppCurve>::debugIsBefore(const SkTSpan* span) const { 47454359294a7c9dc54802d512a5d891a35c1663392caryclark const SkTSpan* work = this; 47554359294a7c9dc54802d512a5d891a35c1663392caryclark do { 47654359294a7c9dc54802d512a5d891a35c1663392caryclark if (span == work) { 47745fa447460f70ec21d22cf4e1531490acfd3c578caryclark return true; 47845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 47954359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((work = work->fNext)); 48045fa447460f70ec21d22cf4e1531490acfd3c578caryclark return false; 48145fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 48254359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 48345fa447460f70ec21d22cf4e1531490acfd3c578caryclark 4841049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 4851049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkbool SkTSpan<TCurve, OppCurve>::contains(double t) const { 48654359294a7c9dc54802d512a5d891a35c1663392caryclark const SkTSpan* work = this; 48745fa447460f70ec21d22cf4e1531490acfd3c578caryclark do { 48845fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (between(work->fStartT, t, work->fEndT)) { 48954359294a7c9dc54802d512a5d891a35c1663392caryclark return true; 49045fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 49145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } while ((work = work->fNext)); 49254359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 49354359294a7c9dc54802d512a5d891a35c1663392caryclark} 49454359294a7c9dc54802d512a5d891a35c1663392caryclark 4951049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 4961049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkconst SkTSect<OppCurve, TCurve>* SkTSpan<TCurve, OppCurve>::debugOpp() const { 49796fcdcc219d2a0d3579719b84b28bede76efba64halcanary return SkDEBUGRELEASE(fDebugSect->debugOpp(), nullptr); 49854359294a7c9dc54802d512a5d891a35c1663392caryclark} 49954359294a7c9dc54802d512a5d891a35c1663392caryclark 5001049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 5011049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkSkTSpan<OppCurve, TCurve>* SkTSpan<TCurve, OppCurve>::findOppSpan( 5021049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<OppCurve, TCurve>* opp) const { 5031049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded; 50454359294a7c9dc54802d512a5d891a35c1663392caryclark while (bounded) { 5051049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* test = bounded->fBounded; 50654359294a7c9dc54802d512a5d891a35c1663392caryclark if (opp == test) { 50754359294a7c9dc54802d512a5d891a35c1663392caryclark return test; 50854359294a7c9dc54802d512a5d891a35c1663392caryclark } 50954359294a7c9dc54802d512a5d891a35c1663392caryclark bounded = bounded->fNext; 51054359294a7c9dc54802d512a5d891a35c1663392caryclark } 51196fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 51245fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 51345fa447460f70ec21d22cf4e1531490acfd3c578caryclark 51454359294a7c9dc54802d512a5d891a35c1663392caryclark// returns 0 if no hull intersection 51554359294a7c9dc54802d512a5d891a35c1663392caryclark// 1 if hulls intersect 51654359294a7c9dc54802d512a5d891a35c1663392caryclark// 2 if hulls only share a common endpoint 51754359294a7c9dc54802d512a5d891a35c1663392caryclark// -1 if linear and further checking is required 5181049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 5191049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkint SkTSpan<TCurve, OppCurve>::hullCheck(const SkTSpan<OppCurve, TCurve>* opp, 5201049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool* start, bool* oppStart) { 52154359294a7c9dc54802d512a5d891a35c1663392caryclark if (fIsLinear) { 52254359294a7c9dc54802d512a5d891a35c1663392caryclark return -1; 52354359294a7c9dc54802d512a5d891a35c1663392caryclark } 52454359294a7c9dc54802d512a5d891a35c1663392caryclark bool ptsInCommon; 52554359294a7c9dc54802d512a5d891a35c1663392caryclark if (onlyEndPointsInCommon(opp, start, oppStart, &ptsInCommon)) { 52654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(ptsInCommon); 52754359294a7c9dc54802d512a5d891a35c1663392caryclark return 2; 52854359294a7c9dc54802d512a5d891a35c1663392caryclark } 52954359294a7c9dc54802d512a5d891a35c1663392caryclark bool linear; 53054359294a7c9dc54802d512a5d891a35c1663392caryclark if (fPart.hullIntersects(opp->fPart, &linear)) { 53154359294a7c9dc54802d512a5d891a35c1663392caryclark if (!linear) { // check set true if linear 53254359294a7c9dc54802d512a5d891a35c1663392caryclark return 1; 53354359294a7c9dc54802d512a5d891a35c1663392caryclark } 53454359294a7c9dc54802d512a5d891a35c1663392caryclark fIsLinear = true; 53554359294a7c9dc54802d512a5d891a35c1663392caryclark fIsLine = fPart.controlsInside(); 5362bec26a71698105729c6a7cb0163f499b4361840caryclark return ptsInCommon ? 1 : -1; 53754359294a7c9dc54802d512a5d891a35c1663392caryclark } else { // hull is not linear; check set true if intersected at the end points 53854359294a7c9dc54802d512a5d891a35c1663392caryclark return ((int) ptsInCommon) << 1; // 0 or 2 53954359294a7c9dc54802d512a5d891a35c1663392caryclark } 54054359294a7c9dc54802d512a5d891a35c1663392caryclark return 0; 54154359294a7c9dc54802d512a5d891a35c1663392caryclark} 54254359294a7c9dc54802d512a5d891a35c1663392caryclark 54345fa447460f70ec21d22cf4e1531490acfd3c578caryclark// OPTIMIZE ? If at_most_end_pts_in_common detects that one quad is near linear, 54445fa447460f70ec21d22cf4e1531490acfd3c578caryclark// use line intersection to guess a better split than 0.5 54545fa447460f70ec21d22cf4e1531490acfd3c578caryclark// OPTIMIZE Once at_most_end_pts_in_common detects linear, mark span so all future splits are linear 5461049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 5471049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkint SkTSpan<TCurve, OppCurve>::hullsIntersect(SkTSpan<OppCurve, TCurve>* opp, 5481049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool* start, bool* oppStart) { 54954359294a7c9dc54802d512a5d891a35c1663392caryclark if (!fBounds.intersects(opp->fBounds)) { 55054359294a7c9dc54802d512a5d891a35c1663392caryclark return 0; 55145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 55254359294a7c9dc54802d512a5d891a35c1663392caryclark int hullSect = this->hullCheck(opp, start, oppStart); 55354359294a7c9dc54802d512a5d891a35c1663392caryclark if (hullSect >= 0) { 55454359294a7c9dc54802d512a5d891a35c1663392caryclark return hullSect; 555ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 55654359294a7c9dc54802d512a5d891a35c1663392caryclark hullSect = opp->hullCheck(this, oppStart, start); 55754359294a7c9dc54802d512a5d891a35c1663392caryclark if (hullSect >= 0) { 55854359294a7c9dc54802d512a5d891a35c1663392caryclark return hullSect; 55954359294a7c9dc54802d512a5d891a35c1663392caryclark } 56054359294a7c9dc54802d512a5d891a35c1663392caryclark return -1; 56154359294a7c9dc54802d512a5d891a35c1663392caryclark} 56254359294a7c9dc54802d512a5d891a35c1663392caryclark 5631049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 5641049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSpan<TCurve, OppCurve>::init(const TCurve& c) { 56596fcdcc219d2a0d3579719b84b28bede76efba64halcanary fPrev = fNext = nullptr; 56654359294a7c9dc54802d512a5d891a35c1663392caryclark fStartT = 0; 56754359294a7c9dc54802d512a5d891a35c1663392caryclark fEndT = 1; 56896fcdcc219d2a0d3579719b84b28bede76efba64halcanary fBounded = nullptr; 56954359294a7c9dc54802d512a5d891a35c1663392caryclark resetBounds(c); 57054359294a7c9dc54802d512a5d891a35c1663392caryclark} 57154359294a7c9dc54802d512a5d891a35c1663392caryclark 5721049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 573a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclarkbool SkTSpan<TCurve, OppCurve>::initBounds(const TCurve& c) { 57454359294a7c9dc54802d512a5d891a35c1663392caryclark fPart = c.subDivide(fStartT, fEndT); 57554359294a7c9dc54802d512a5d891a35c1663392caryclark fBounds.setBounds(fPart); 57654359294a7c9dc54802d512a5d891a35c1663392caryclark fCoinStart.init(); 57754359294a7c9dc54802d512a5d891a35c1663392caryclark fCoinEnd.init(); 57854359294a7c9dc54802d512a5d891a35c1663392caryclark fBoundsMax = SkTMax(fBounds.width(), fBounds.height()); 57954359294a7c9dc54802d512a5d891a35c1663392caryclark fCollapsed = fPart.collapsed(); 58054359294a7c9dc54802d512a5d891a35c1663392caryclark fHasPerp = false; 58154359294a7c9dc54802d512a5d891a35c1663392caryclark fDeleted = false; 58254359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_T_SECT 58354359294a7c9dc54802d512a5d891a35c1663392caryclark if (fCollapsed) { 58454359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf(""); // for convenient breakpoints 58545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 58654359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 587a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark return fBounds.valid(); 58854359294a7c9dc54802d512a5d891a35c1663392caryclark} 58954359294a7c9dc54802d512a5d891a35c1663392caryclark 5901049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 5911049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkbool SkTSpan<TCurve, OppCurve>::linearsIntersect(SkTSpan<OppCurve, TCurve>* span) { 59254359294a7c9dc54802d512a5d891a35c1663392caryclark int result = this->linearIntersects(span->fPart); 59354359294a7c9dc54802d512a5d891a35c1663392caryclark if (result <= 1) { 59454359294a7c9dc54802d512a5d891a35c1663392caryclark return SkToBool(result); 59554359294a7c9dc54802d512a5d891a35c1663392caryclark } 59654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(span->fIsLinear); 59754359294a7c9dc54802d512a5d891a35c1663392caryclark result = span->linearIntersects(this->fPart); 59854359294a7c9dc54802d512a5d891a35c1663392caryclark// SkASSERT(result <= 1); 59954359294a7c9dc54802d512a5d891a35c1663392caryclark return SkToBool(result); 60054359294a7c9dc54802d512a5d891a35c1663392caryclark} 60154359294a7c9dc54802d512a5d891a35c1663392caryclark 6021049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 6031049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkdouble SkTSpan<TCurve, OppCurve>::linearT(const SkDPoint& pt) const { 60454359294a7c9dc54802d512a5d891a35c1663392caryclark SkDVector len = fPart[TCurve::kPointLast] - fPart[0]; 60554359294a7c9dc54802d512a5d891a35c1663392caryclark return fabs(len.fX) > fabs(len.fY) 60654359294a7c9dc54802d512a5d891a35c1663392caryclark ? (pt.fX - fPart[0].fX) / len.fX 60754359294a7c9dc54802d512a5d891a35c1663392caryclark : (pt.fY - fPart[0].fY) / len.fY; 60845fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 60945fa447460f70ec21d22cf4e1531490acfd3c578caryclark 6101049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 6111049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkint SkTSpan<TCurve, OppCurve>::linearIntersects(const OppCurve& q2) const { 61245fa447460f70ec21d22cf4e1531490acfd3c578caryclark // looks like q1 is near-linear 61354359294a7c9dc54802d512a5d891a35c1663392caryclark int start = 0, end = TCurve::kPointLast; // the outside points are usually the extremes 61445fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (!fPart.controlsInside()) { 61545fa447460f70ec21d22cf4e1531490acfd3c578caryclark double dist = 0; // if there's any question, compute distance to find best outsiders 61645fa447460f70ec21d22cf4e1531490acfd3c578caryclark for (int outer = 0; outer < TCurve::kPointCount - 1; ++outer) { 61745fa447460f70ec21d22cf4e1531490acfd3c578caryclark for (int inner = outer + 1; inner < TCurve::kPointCount; ++inner) { 61845fa447460f70ec21d22cf4e1531490acfd3c578caryclark double test = (fPart[outer] - fPart[inner]).lengthSquared(); 61945fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (dist > test) { 62045fa447460f70ec21d22cf4e1531490acfd3c578caryclark continue; 62145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 62245fa447460f70ec21d22cf4e1531490acfd3c578caryclark dist = test; 62345fa447460f70ec21d22cf4e1531490acfd3c578caryclark start = outer; 62445fa447460f70ec21d22cf4e1531490acfd3c578caryclark end = inner; 62545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 62645fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 62745fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 62845fa447460f70ec21d22cf4e1531490acfd3c578caryclark // see if q2 is on one side of the line formed by the extreme points 62945fa447460f70ec21d22cf4e1531490acfd3c578caryclark double origX = fPart[start].fX; 63045fa447460f70ec21d22cf4e1531490acfd3c578caryclark double origY = fPart[start].fY; 63145fa447460f70ec21d22cf4e1531490acfd3c578caryclark double adj = fPart[end].fX - origX; 63245fa447460f70ec21d22cf4e1531490acfd3c578caryclark double opp = fPart[end].fY - origY; 63354359294a7c9dc54802d512a5d891a35c1663392caryclark double maxPart = SkTMax(fabs(adj), fabs(opp)); 63454359294a7c9dc54802d512a5d891a35c1663392caryclark double sign = 0; // initialization to shut up warning in release build 6351049f1246e7be4ccb68001361efceb8933e6f81ccaryclark for (int n = 0; n < OppCurve::kPointCount; ++n) { 63654359294a7c9dc54802d512a5d891a35c1663392caryclark double dx = q2[n].fY - origY; 63754359294a7c9dc54802d512a5d891a35c1663392caryclark double dy = q2[n].fX - origX; 63854359294a7c9dc54802d512a5d891a35c1663392caryclark double maxVal = SkTMax(maxPart, SkTMax(fabs(dx), fabs(dy))); 63945fa447460f70ec21d22cf4e1531490acfd3c578caryclark double test = (q2[n].fY - origY) * adj - (q2[n].fX - origX) * opp; 64054359294a7c9dc54802d512a5d891a35c1663392caryclark if (precisely_zero_when_compared_to(test, maxVal)) { 64154359294a7c9dc54802d512a5d891a35c1663392caryclark return 1; 64254359294a7c9dc54802d512a5d891a35c1663392caryclark } 64354359294a7c9dc54802d512a5d891a35c1663392caryclark if (approximately_zero_when_compared_to(test, maxVal)) { 64454359294a7c9dc54802d512a5d891a35c1663392caryclark return 3; 64545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 64645fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (n == 0) { 64745fa447460f70ec21d22cf4e1531490acfd3c578caryclark sign = test; 64845fa447460f70ec21d22cf4e1531490acfd3c578caryclark continue; 64945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 65045fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (test * sign < 0) { 65154359294a7c9dc54802d512a5d891a35c1663392caryclark return 1; 65254359294a7c9dc54802d512a5d891a35c1663392caryclark } 65354359294a7c9dc54802d512a5d891a35c1663392caryclark } 65454359294a7c9dc54802d512a5d891a35c1663392caryclark return 0; 65554359294a7c9dc54802d512a5d891a35c1663392caryclark} 65654359294a7c9dc54802d512a5d891a35c1663392caryclark 6571049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 6581049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkbool SkTSpan<TCurve, OppCurve>::onlyEndPointsInCommon(const SkTSpan<OppCurve, TCurve>* opp, 6591049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool* start, bool* oppStart, bool* ptsInCommon) { 66054359294a7c9dc54802d512a5d891a35c1663392caryclark if (opp->fPart[0] == fPart[0]) { 66154359294a7c9dc54802d512a5d891a35c1663392caryclark *start = *oppStart = true; 66254359294a7c9dc54802d512a5d891a35c1663392caryclark } else if (opp->fPart[0] == fPart[TCurve::kPointLast]) { 66354359294a7c9dc54802d512a5d891a35c1663392caryclark *start = false; 66454359294a7c9dc54802d512a5d891a35c1663392caryclark *oppStart = true; 6651049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } else if (opp->fPart[OppCurve::kPointLast] == fPart[0]) { 66654359294a7c9dc54802d512a5d891a35c1663392caryclark *start = true; 66754359294a7c9dc54802d512a5d891a35c1663392caryclark *oppStart = false; 6681049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } else if (opp->fPart[OppCurve::kPointLast] == fPart[TCurve::kPointLast]) { 66954359294a7c9dc54802d512a5d891a35c1663392caryclark *start = *oppStart = false; 67054359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 67154359294a7c9dc54802d512a5d891a35c1663392caryclark *ptsInCommon = false; 67254359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 67354359294a7c9dc54802d512a5d891a35c1663392caryclark } 67454359294a7c9dc54802d512a5d891a35c1663392caryclark *ptsInCommon = true; 6751049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkDPoint* otherPts[TCurve::kPointCount - 1], * oppOtherPts[OppCurve::kPointCount - 1]; 67654359294a7c9dc54802d512a5d891a35c1663392caryclark int baseIndex = *start ? 0 : TCurve::kPointLast; 6771049f1246e7be4ccb68001361efceb8933e6f81ccaryclark fPart.otherPts(baseIndex, otherPts); 6781049f1246e7be4ccb68001361efceb8933e6f81ccaryclark opp->fPart.otherPts(*oppStart ? 0 : OppCurve::kPointLast, oppOtherPts); 67954359294a7c9dc54802d512a5d891a35c1663392caryclark const SkDPoint& base = fPart[baseIndex]; 6801049f1246e7be4ccb68001361efceb8933e6f81ccaryclark for (int o1 = 0; o1 < (int) SK_ARRAY_COUNT(otherPts); ++o1) { 6811049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDVector v1 = *otherPts[o1] - base; 6821049f1246e7be4ccb68001361efceb8933e6f81ccaryclark for (int o2 = 0; o2 < (int) SK_ARRAY_COUNT(oppOtherPts); ++o2) { 6831049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDVector v2 = *oppOtherPts[o2] - base; 68454359294a7c9dc54802d512a5d891a35c1663392caryclark if (v2.dot(v1) >= 0) { 68554359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 68654359294a7c9dc54802d512a5d891a35c1663392caryclark } 68754359294a7c9dc54802d512a5d891a35c1663392caryclark } 68854359294a7c9dc54802d512a5d891a35c1663392caryclark } 68954359294a7c9dc54802d512a5d891a35c1663392caryclark return true; 69054359294a7c9dc54802d512a5d891a35c1663392caryclark} 69154359294a7c9dc54802d512a5d891a35c1663392caryclark 6921049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 6931049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkSkTSpan<OppCurve, TCurve>* SkTSpan<TCurve, OppCurve>::oppT(double t) const { 6941049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded; 69554359294a7c9dc54802d512a5d891a35c1663392caryclark while (bounded) { 6961049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* test = bounded->fBounded; 69754359294a7c9dc54802d512a5d891a35c1663392caryclark if (between(test->fStartT, t, test->fEndT)) { 69854359294a7c9dc54802d512a5d891a35c1663392caryclark return test; 69954359294a7c9dc54802d512a5d891a35c1663392caryclark } 70054359294a7c9dc54802d512a5d891a35c1663392caryclark bounded = bounded->fNext; 70154359294a7c9dc54802d512a5d891a35c1663392caryclark } 70296fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 70354359294a7c9dc54802d512a5d891a35c1663392caryclark} 70454359294a7c9dc54802d512a5d891a35c1663392caryclark 7051049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 7061049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkbool SkTSpan<TCurve, OppCurve>::removeAllBounded() { 70754359294a7c9dc54802d512a5d891a35c1663392caryclark bool deleteSpan = false; 7081049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded; 70954359294a7c9dc54802d512a5d891a35c1663392caryclark while (bounded) { 7101049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* opp = bounded->fBounded; 71154359294a7c9dc54802d512a5d891a35c1663392caryclark deleteSpan |= opp->removeBounded(this); 71254359294a7c9dc54802d512a5d891a35c1663392caryclark bounded = bounded->fNext; 71354359294a7c9dc54802d512a5d891a35c1663392caryclark } 71454359294a7c9dc54802d512a5d891a35c1663392caryclark return deleteSpan; 71554359294a7c9dc54802d512a5d891a35c1663392caryclark} 71654359294a7c9dc54802d512a5d891a35c1663392caryclark 7171049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 7181049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkbool SkTSpan<TCurve, OppCurve>::removeBounded(const SkTSpan<OppCurve, TCurve>* opp) { 71954359294a7c9dc54802d512a5d891a35c1663392caryclark if (fHasPerp) { 72054359294a7c9dc54802d512a5d891a35c1663392caryclark bool foundStart = false; 72154359294a7c9dc54802d512a5d891a35c1663392caryclark bool foundEnd = false; 7221049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded; 72354359294a7c9dc54802d512a5d891a35c1663392caryclark while (bounded) { 7241049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* test = bounded->fBounded; 72554359294a7c9dc54802d512a5d891a35c1663392caryclark if (opp != test) { 72654359294a7c9dc54802d512a5d891a35c1663392caryclark foundStart |= between(test->fStartT, fCoinStart.perpT(), test->fEndT); 72754359294a7c9dc54802d512a5d891a35c1663392caryclark foundEnd |= between(test->fStartT, fCoinEnd.perpT(), test->fEndT); 72854359294a7c9dc54802d512a5d891a35c1663392caryclark } 72954359294a7c9dc54802d512a5d891a35c1663392caryclark bounded = bounded->fNext; 73054359294a7c9dc54802d512a5d891a35c1663392caryclark } 73154359294a7c9dc54802d512a5d891a35c1663392caryclark if (!foundStart || !foundEnd) { 73254359294a7c9dc54802d512a5d891a35c1663392caryclark fHasPerp = false; 73354359294a7c9dc54802d512a5d891a35c1663392caryclark fCoinStart.init(); 73454359294a7c9dc54802d512a5d891a35c1663392caryclark fCoinEnd.init(); 73554359294a7c9dc54802d512a5d891a35c1663392caryclark } 73654359294a7c9dc54802d512a5d891a35c1663392caryclark } 7371049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded; 73896fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkTSpanBounded<OppCurve, TCurve>* prev = nullptr; 73954359294a7c9dc54802d512a5d891a35c1663392caryclark while (bounded) { 7401049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpanBounded<OppCurve, TCurve>* boundedNext = bounded->fNext; 74154359294a7c9dc54802d512a5d891a35c1663392caryclark if (opp == bounded->fBounded) { 74254359294a7c9dc54802d512a5d891a35c1663392caryclark if (prev) { 74354359294a7c9dc54802d512a5d891a35c1663392caryclark prev->fNext = boundedNext; 74454359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 74554359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 74654359294a7c9dc54802d512a5d891a35c1663392caryclark fBounded = boundedNext; 74796fcdcc219d2a0d3579719b84b28bede76efba64halcanary return fBounded == nullptr; 74854359294a7c9dc54802d512a5d891a35c1663392caryclark } 74945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 75054359294a7c9dc54802d512a5d891a35c1663392caryclark prev = bounded; 75154359294a7c9dc54802d512a5d891a35c1663392caryclark bounded = boundedNext; 75245fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 753643ede69216c073c2dd497c382577dc9fde36b3ecaryclark SkOPASSERT(0); 75445fa447460f70ec21d22cf4e1531490acfd3c578caryclark return false; 75545fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 75645fa447460f70ec21d22cf4e1531490acfd3c578caryclark 7571049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 758c3cc5fa6de0a8237d9241dbf3e6c0786a9040069Herb Derbybool SkTSpan<TCurve, OppCurve>::splitAt(SkTSpan* work, double t, SkArenaAlloc* heap) { 75945fa447460f70ec21d22cf4e1531490acfd3c578caryclark fStartT = t; 76045fa447460f70ec21d22cf4e1531490acfd3c578caryclark fEndT = work->fEndT; 76145fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (fStartT == fEndT) { 76245fa447460f70ec21d22cf4e1531490acfd3c578caryclark fCollapsed = true; 76345fa447460f70ec21d22cf4e1531490acfd3c578caryclark return false; 76445fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 76545fa447460f70ec21d22cf4e1531490acfd3c578caryclark work->fEndT = t; 76645fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (work->fStartT == work->fEndT) { 76745fa447460f70ec21d22cf4e1531490acfd3c578caryclark work->fCollapsed = true; 76845fa447460f70ec21d22cf4e1531490acfd3c578caryclark return false; 76945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 77045fa447460f70ec21d22cf4e1531490acfd3c578caryclark fPrev = work; 77145fa447460f70ec21d22cf4e1531490acfd3c578caryclark fNext = work->fNext; 77245fa447460f70ec21d22cf4e1531490acfd3c578caryclark fIsLinear = work->fIsLinear; 77354359294a7c9dc54802d512a5d891a35c1663392caryclark fIsLine = work->fIsLine; 77454359294a7c9dc54802d512a5d891a35c1663392caryclark 77545fa447460f70ec21d22cf4e1531490acfd3c578caryclark work->fNext = this; 77645fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (fNext) { 77745fa447460f70ec21d22cf4e1531490acfd3c578caryclark fNext->fPrev = this; 77845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 779643ede69216c073c2dd497c382577dc9fde36b3ecaryclark this->validate(); 7801049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpanBounded<OppCurve, TCurve>* bounded = work->fBounded; 78196fcdcc219d2a0d3579719b84b28bede76efba64halcanary fBounded = nullptr; 78254359294a7c9dc54802d512a5d891a35c1663392caryclark while (bounded) { 78354359294a7c9dc54802d512a5d891a35c1663392caryclark this->addBounded(bounded->fBounded, heap); 78454359294a7c9dc54802d512a5d891a35c1663392caryclark bounded = bounded->fNext; 78554359294a7c9dc54802d512a5d891a35c1663392caryclark } 78654359294a7c9dc54802d512a5d891a35c1663392caryclark bounded = fBounded; 78754359294a7c9dc54802d512a5d891a35c1663392caryclark while (bounded) { 78854359294a7c9dc54802d512a5d891a35c1663392caryclark bounded->fBounded->addBounded(this, heap); 78954359294a7c9dc54802d512a5d891a35c1663392caryclark bounded = bounded->fNext; 79045fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 79145fa447460f70ec21d22cf4e1531490acfd3c578caryclark return true; 79245fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 79345fa447460f70ec21d22cf4e1531490acfd3c578caryclark 7941049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 7951049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSpan<TCurve, OppCurve>::validate() const { 796643ede69216c073c2dd497c382577dc9fde36b3ecaryclark#if DEBUG_VALIDATE 797643ede69216c073c2dd497c382577dc9fde36b3ecaryclark SkASSERT(this != fPrev); 798643ede69216c073c2dd497c382577dc9fde36b3ecaryclark SkASSERT(this != fNext); 79996fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkASSERT(fNext == nullptr || fNext != fPrev); 80096fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkASSERT(fNext == nullptr || this == fNext->fPrev); 80196fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkASSERT(fPrev == nullptr || this == fPrev->fNext); 802643ede69216c073c2dd497c382577dc9fde36b3ecaryclark this->validateBounded(); 803643ede69216c073c2dd497c382577dc9fde36b3ecaryclark#endif 804643ede69216c073c2dd497c382577dc9fde36b3ecaryclark#if DEBUG_T_SECT 80554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(fBounds.width() || fBounds.height() || fCollapsed); 806e839e78443e48d4ccad89059b4bc4b3d894fcfddcaryclark SkASSERT(fBoundsMax == SkTMax(fBounds.width(), fBounds.height()) || fCollapsed == 0xFF); 80754359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(0 <= fStartT); 80854359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(fEndT <= 1); 80954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(fStartT <= fEndT); 810e839e78443e48d4ccad89059b4bc4b3d894fcfddcaryclark SkASSERT(fBounded || fCollapsed == 0xFF); 81154359294a7c9dc54802d512a5d891a35c1663392caryclark if (fHasPerp) { 8126c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark if (fCoinStart.isMatch()) { 81354359294a7c9dc54802d512a5d891a35c1663392caryclark validatePerpT(fCoinStart.perpT()); 81454359294a7c9dc54802d512a5d891a35c1663392caryclark validatePerpPt(fCoinStart.perpT(), fCoinStart.perpPt()); 815ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 8166c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark if (fCoinEnd.isMatch()) { 81754359294a7c9dc54802d512a5d891a35c1663392caryclark validatePerpT(fCoinEnd.perpT()); 81854359294a7c9dc54802d512a5d891a35c1663392caryclark validatePerpPt(fCoinEnd.perpT(), fCoinEnd.perpPt()); 819ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 820ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 82154359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 82254359294a7c9dc54802d512a5d891a35c1663392caryclark} 82354359294a7c9dc54802d512a5d891a35c1663392caryclark 8241049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 8251049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSpan<TCurve, OppCurve>::validateBounded() const { 82654359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_VALIDATE 8271049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded; 82854359294a7c9dc54802d512a5d891a35c1663392caryclark while (testBounded) { 829ceeaa78713dde9cc6e3ccd688aca6021b260af4dcsmartdalton SkDEBUGCODE(const SkTSpan<OppCurve, TCurve>* overlap = testBounded->fBounded); 83054359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!overlap->fDeleted); 831643ede69216c073c2dd497c382577dc9fde36b3ecaryclark#if DEBUG_T_SECT 83254359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(((this->debugID() ^ overlap->debugID()) & 1) == 1); 83354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(overlap->findOppSpan(this)); 834643ede69216c073c2dd497c382577dc9fde36b3ecaryclark#endif 83554359294a7c9dc54802d512a5d891a35c1663392caryclark testBounded = testBounded->fNext; 836ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 83754359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 838ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark} 839ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark 8401049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 8411049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSpan<TCurve, OppCurve>::validatePerpT(double oppT) const { 8421049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded; 84354359294a7c9dc54802d512a5d891a35c1663392caryclark while (testBounded) { 8441049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<OppCurve, TCurve>* overlap = testBounded->fBounded; 84526ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark if (precisely_between(overlap->fStartT, oppT, overlap->fEndT)) { 84654359294a7c9dc54802d512a5d891a35c1663392caryclark return; 84754359294a7c9dc54802d512a5d891a35c1663392caryclark } 84854359294a7c9dc54802d512a5d891a35c1663392caryclark testBounded = testBounded->fNext; 84945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 85054359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(0); 85145fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 85254359294a7c9dc54802d512a5d891a35c1663392caryclark 8531049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 8541049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSpan<TCurve, OppCurve>::validatePerpPt(double t, const SkDPoint& pt) const { 8551049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkASSERT(fDebugSect->fOppSect->fCurve.ptAtT(t) == pt); 85654359294a7c9dc54802d512a5d891a35c1663392caryclark} 85754359294a7c9dc54802d512a5d891a35c1663392caryclark 85845fa447460f70ec21d22cf4e1531490acfd3c578caryclark 8591049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 860c3cc5fa6de0a8237d9241dbf3e6c0786a9040069Herb DerbySkTSect<TCurve, OppCurve>::SkTSect(const TCurve& c 861e25a4f6cbeaccfdc34cf031103f0fbc3e53a3ee5caryclark SkDEBUGPARAMS(SkOpGlobalState* debugGlobalState) 862e25a4f6cbeaccfdc34cf031103f0fbc3e53a3ee5caryclark PATH_OPS_DEBUG_T_SECT_PARAMS(int id)) 86345fa447460f70ec21d22cf4e1531490acfd3c578caryclark : fCurve(c) 8641049f1246e7be4ccb68001361efceb8933e6f81ccaryclark , fHeap(sizeof(SkTSpan<TCurve, OppCurve>) * 4) 86596fcdcc219d2a0d3579719b84b28bede76efba64halcanary , fCoincident(nullptr) 86696fcdcc219d2a0d3579719b84b28bede76efba64halcanary , fDeleted(nullptr) 86745fa447460f70ec21d22cf4e1531490acfd3c578caryclark , fActiveCount(0) 868e25a4f6cbeaccfdc34cf031103f0fbc3e53a3ee5caryclark SkDEBUGPARAMS(fDebugGlobalState(debugGlobalState)) 86954359294a7c9dc54802d512a5d891a35c1663392caryclark PATH_OPS_DEBUG_T_SECT_PARAMS(fID(id)) 87054359294a7c9dc54802d512a5d891a35c1663392caryclark PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugCount(0)) 87154359294a7c9dc54802d512a5d891a35c1663392caryclark PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugAllocatedCount(0)) 87245fa447460f70ec21d22cf4e1531490acfd3c578caryclark{ 87334efb7039851d7796ba06aa58e5c5882ede503accaryclark this->resetRemovedEnds(); 87434efb7039851d7796ba06aa58e5c5882ede503accaryclark fHead = this->addOne(); 875643ede69216c073c2dd497c382577dc9fde36b3ecaryclark SkDEBUGCODE(fHead->debugSetGlobalState(debugGlobalState)); 87645fa447460f70ec21d22cf4e1531490acfd3c578caryclark fHead->init(c); 87745fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 87845fa447460f70ec21d22cf4e1531490acfd3c578caryclark 8791049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 8801049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkSkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::addOne() { 8811049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* result; 88245fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (fDeleted) { 88345fa447460f70ec21d22cf4e1531490acfd3c578caryclark result = fDeleted; 88445fa447460f70ec21d22cf4e1531490acfd3c578caryclark fDeleted = result->fNext; 88545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } else { 886c3cc5fa6de0a8237d9241dbf3e6c0786a9040069Herb Derby result = fHeap.make<SkTSpan<TCurve, OppCurve>>(); 88745fa447460f70ec21d22cf4e1531490acfd3c578caryclark#if DEBUG_T_SECT 88845fa447460f70ec21d22cf4e1531490acfd3c578caryclark ++fDebugAllocatedCount; 88945fa447460f70ec21d22cf4e1531490acfd3c578caryclark#endif 89045fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 891ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark result->reset(); 89208b3249494782cc401ab1cac57ef4d8e560ed11dcaryclark result->fHasPerp = false; 89308b3249494782cc401ab1cac57ef4d8e560ed11dcaryclark result->fDeleted = false; 89455888e44171ffd48b591d19256884a969fe4da17caryclark ++fActiveCount; 89554359294a7c9dc54802d512a5d891a35c1663392caryclark PATH_OPS_DEBUG_T_SECT_CODE(result->fID = fDebugCount++ * 2 + fID); 8961049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(result->fDebugSect = this); 897ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark#ifdef SK_DEBUG 898ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark result->fPart.debugInit(); 899ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark result->fCoinStart.debugInit(); 900ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark result->fCoinEnd.debugInit(); 901ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark result->fPrev = result->fNext = nullptr; 902ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark result->fBounds.debugInit(); 903ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark result->fStartT = result->fEndT = result->fBoundsMax = SK_ScalarNaN; 904ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark result->fCollapsed = result->fIsLinear = result->fIsLine = 0xFF; 905ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark#endif 90645fa447460f70ec21d22cf4e1531490acfd3c578caryclark return result; 90745fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 90845fa447460f70ec21d22cf4e1531490acfd3c578caryclark 9091049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 9101049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkbool SkTSect<TCurve, OppCurve>::binarySearchCoin(SkTSect<OppCurve, TCurve>* sect2, double tStart, 9111049f1246e7be4ccb68001361efceb8933e6f81ccaryclark double tStep, double* resultT, double* oppT) { 9121049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve> work; 91345fa447460f70ec21d22cf4e1531490acfd3c578caryclark double result = work.fStartT = work.fEndT = tStart; 9141049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(work.fDebugSect = this); 91545fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkDPoint last = fCurve.ptAtT(tStart); 91645fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkDPoint oppPt; 91745fa447460f70ec21d22cf4e1531490acfd3c578caryclark bool flip = false; 918cdeff81bdb2e5cde422b6850634c5d3977fcbae9caryclark bool contained = false; 91945fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkDEBUGCODE(bool down = tStep < 0); 9201049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const OppCurve& opp = sect2->fCurve; 92145fa447460f70ec21d22cf4e1531490acfd3c578caryclark do { 92245fa447460f70ec21d22cf4e1531490acfd3c578caryclark tStep *= 0.5; 92345fa447460f70ec21d22cf4e1531490acfd3c578caryclark work.fStartT += tStep; 92445fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (flip) { 92545fa447460f70ec21d22cf4e1531490acfd3c578caryclark tStep = -tStep; 92645fa447460f70ec21d22cf4e1531490acfd3c578caryclark flip = false; 92745fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 92845fa447460f70ec21d22cf4e1531490acfd3c578caryclark work.initBounds(fCurve); 92945fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (work.fCollapsed) { 93045fa447460f70ec21d22cf4e1531490acfd3c578caryclark return false; 93145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 93245fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (last.approximatelyEqual(work.fPart[0])) { 93345fa447460f70ec21d22cf4e1531490acfd3c578caryclark break; 93445fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 93545fa447460f70ec21d22cf4e1531490acfd3c578caryclark last = work.fPart[0]; 93645fa447460f70ec21d22cf4e1531490acfd3c578caryclark work.fCoinStart.setPerp(fCurve, work.fStartT, last, opp); 9376c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark if (work.fCoinStart.isMatch()) { 93854359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_T_SECT 93954359294a7c9dc54802d512a5d891a35c1663392caryclark work.validatePerpPt(work.fCoinStart.perpT(), work.fCoinStart.perpPt()); 94054359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 94145fa447460f70ec21d22cf4e1531490acfd3c578caryclark double oppTTest = work.fCoinStart.perpT(); 94254359294a7c9dc54802d512a5d891a35c1663392caryclark if (sect2->fHead->contains(oppTTest)) { 94345fa447460f70ec21d22cf4e1531490acfd3c578caryclark *oppT = oppTTest; 94445fa447460f70ec21d22cf4e1531490acfd3c578caryclark oppPt = work.fCoinStart.perpPt(); 945cdeff81bdb2e5cde422b6850634c5d3977fcbae9caryclark contained = true; 94645fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkASSERT(down ? result > work.fStartT : result < work.fStartT); 94745fa447460f70ec21d22cf4e1531490acfd3c578caryclark result = work.fStartT; 94845fa447460f70ec21d22cf4e1531490acfd3c578caryclark continue; 94945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 95045fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 95145fa447460f70ec21d22cf4e1531490acfd3c578caryclark tStep = -tStep; 95245fa447460f70ec21d22cf4e1531490acfd3c578caryclark flip = true; 95345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } while (true); 954cdeff81bdb2e5cde422b6850634c5d3977fcbae9caryclark if (!contained) { 955cdeff81bdb2e5cde422b6850634c5d3977fcbae9caryclark return false; 956cdeff81bdb2e5cde422b6850634c5d3977fcbae9caryclark } 95745fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (last.approximatelyEqual(fCurve[0])) { 95845fa447460f70ec21d22cf4e1531490acfd3c578caryclark result = 0; 95945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } else if (last.approximatelyEqual(fCurve[TCurve::kPointLast])) { 96045fa447460f70ec21d22cf4e1531490acfd3c578caryclark result = 1; 96145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 96245fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (oppPt.approximatelyEqual(opp[0])) { 96345fa447460f70ec21d22cf4e1531490acfd3c578caryclark *oppT = 0; 9641049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } else if (oppPt.approximatelyEqual(opp[OppCurve::kPointLast])) { 96545fa447460f70ec21d22cf4e1531490acfd3c578caryclark *oppT = 1; 96645fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 96745fa447460f70ec21d22cf4e1531490acfd3c578caryclark *resultT = result; 96845fa447460f70ec21d22cf4e1531490acfd3c578caryclark return true; 96945fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 97045fa447460f70ec21d22cf4e1531490acfd3c578caryclark 97145fa447460f70ec21d22cf4e1531490acfd3c578caryclark// OPTIMIZE ? keep a sorted list of sizes in the form of a doubly-linked list in quad span 97245fa447460f70ec21d22cf4e1531490acfd3c578caryclark// so that each quad sect has a pointer to the largest, and can update it as spans 97345fa447460f70ec21d22cf4e1531490acfd3c578caryclark// are split 9741049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 9751049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkSkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::boundsMax() const { 9761049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* test = fHead; 9771049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* largest = fHead; 97854359294a7c9dc54802d512a5d891a35c1663392caryclark bool lCollapsed = largest->fCollapsed; 97945fa447460f70ec21d22cf4e1531490acfd3c578caryclark while ((test = test->fNext)) { 98054359294a7c9dc54802d512a5d891a35c1663392caryclark bool tCollapsed = test->fCollapsed; 98154359294a7c9dc54802d512a5d891a35c1663392caryclark if ((lCollapsed && !tCollapsed) || (lCollapsed == tCollapsed && 98254359294a7c9dc54802d512a5d891a35c1663392caryclark largest->fBoundsMax < test->fBoundsMax)) { 98345fa447460f70ec21d22cf4e1531490acfd3c578caryclark largest = test; 9841049f1246e7be4ccb68001361efceb8933e6f81ccaryclark lCollapsed = test->fCollapsed; 98545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 98645fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 98754359294a7c9dc54802d512a5d891a35c1663392caryclark return largest; 98845fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 98945fa447460f70ec21d22cf4e1531490acfd3c578caryclark 9901049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 991ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclarkbool SkTSect<TCurve, OppCurve>::coincidentCheck(SkTSect<OppCurve, TCurve>* sect2) { 9921049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* first = fHead; 9939feb6326d0c5407247ed1e3d8fade2f86b233001caryclark if (!first) { 9949feb6326d0c5407247ed1e3d8fade2f86b233001caryclark return false; 9959feb6326d0c5407247ed1e3d8fade2f86b233001caryclark } 9961049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* last, * next; 99745fa447460f70ec21d22cf4e1531490acfd3c578caryclark do { 99854359294a7c9dc54802d512a5d891a35c1663392caryclark int consecutive = this->countConsecutiveSpans(first, &last); 99954359294a7c9dc54802d512a5d891a35c1663392caryclark next = last->fNext; 100045fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (consecutive < COINCIDENT_SPAN_COUNT) { 100145fa447460f70ec21d22cf4e1531490acfd3c578caryclark continue; 100245fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 100354359294a7c9dc54802d512a5d891a35c1663392caryclark this->validate(); 100454359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->validate(); 100554359294a7c9dc54802d512a5d891a35c1663392caryclark this->computePerpendiculars(sect2, first, last); 100654359294a7c9dc54802d512a5d891a35c1663392caryclark this->validate(); 100754359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->validate(); 100845fa447460f70ec21d22cf4e1531490acfd3c578caryclark // check to see if a range of points are on the curve 10091049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* coinStart = first; 101054359294a7c9dc54802d512a5d891a35c1663392caryclark do { 1011ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark bool success = this->extractCoincident(sect2, coinStart, last, &coinStart); 1012ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark if (!success) { 1013ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark return false; 1014ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark } 101554359294a7c9dc54802d512a5d891a35c1663392caryclark } while (coinStart && !last->fDeleted); 101655888e44171ffd48b591d19256884a969fe4da17caryclark if (!fHead || !sect2->fHead) { 101755888e44171ffd48b591d19256884a969fe4da17caryclark break; 101855888e44171ffd48b591d19256884a969fe4da17caryclark } 1019643ede69216c073c2dd497c382577dc9fde36b3ecaryclark if (!next || next->fDeleted) { 1020643ede69216c073c2dd497c382577dc9fde36b3ecaryclark break; 1021643ede69216c073c2dd497c382577dc9fde36b3ecaryclark } 102245fa447460f70ec21d22cf4e1531490acfd3c578caryclark } while ((first = next)); 1023ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark return true; 102445fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 102545fa447460f70ec21d22cf4e1531490acfd3c578caryclark 10261049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 102726ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclarkvoid SkTSect<TCurve, OppCurve>::coincidentForce(SkTSect<OppCurve, TCurve>* sect2, 102826ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark double start1s, double start1e) { 102926ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark SkTSpan<TCurve, OppCurve>* first = fHead; 103026ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark SkTSpan<TCurve, OppCurve>* last = this->tail(); 103126ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark SkTSpan<OppCurve, TCurve>* oppFirst = sect2->fHead; 103226ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark SkTSpan<OppCurve, TCurve>* oppLast = sect2->tail(); 103326ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark bool deleteEmptySpans = this->updateBounded(first, last, oppFirst); 103426ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first); 103526ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark this->removeSpanRange(first, last); 103626ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark sect2->removeSpanRange(oppFirst, oppLast); 103726ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark first->fStartT = start1s; 103826ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark first->fEndT = start1e; 103926ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark first->resetBounds(fCurve); 104026ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark first->fCoinStart.setPerp(fCurve, start1s, fCurve[0], sect2->fCurve); 104126ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark first->fCoinEnd.setPerp(fCurve, start1e, fCurve[TCurve::kPointLast], sect2->fCurve); 104226ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark bool oppMatched = first->fCoinStart.perpT() < first->fCoinEnd.perpT(); 1043ef784fb7f58c9c021172045a8e0b396c81fdc425caryclark double oppStartT = first->fCoinStart.perpT() == -1 ? 0 : SkTMax(0., first->fCoinStart.perpT()); 1044ef784fb7f58c9c021172045a8e0b396c81fdc425caryclark double oppEndT = first->fCoinEnd.perpT() == -1 ? 1 : SkTMin(1., first->fCoinEnd.perpT()); 104526ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark if (!oppMatched) { 104626ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark SkTSwap(oppStartT, oppEndT); 104726ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark } 104826ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark oppFirst->fStartT = oppStartT; 104926ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark oppFirst->fEndT = oppEndT; 105026ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark oppFirst->resetBounds(sect2->fCurve); 105126ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark this->removeCoincident(first, false); 105226ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark sect2->removeCoincident(oppFirst, true); 105326ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark if (deleteEmptySpans) { 105426ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark this->deleteEmptySpans(); 105526ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark sect2->deleteEmptySpans(); 105626ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark } 105726ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark} 105826ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark 105926ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclarktemplate<typename TCurve, typename OppCurve> 10601049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkbool SkTSect<TCurve, OppCurve>::coincidentHasT(double t) { 10611049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* test = fCoincident; 106254359294a7c9dc54802d512a5d891a35c1663392caryclark while (test) { 106354359294a7c9dc54802d512a5d891a35c1663392caryclark if (between(test->fStartT, t, test->fEndT)) { 106454359294a7c9dc54802d512a5d891a35c1663392caryclark return true; 106554359294a7c9dc54802d512a5d891a35c1663392caryclark } 106654359294a7c9dc54802d512a5d891a35c1663392caryclark test = test->fNext; 10670dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 106854359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 106945fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 107045fa447460f70ec21d22cf4e1531490acfd3c578caryclark 10711049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 10721049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkint SkTSect<TCurve, OppCurve>::collapsed() const { 10731049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int result = 0; 10741049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<TCurve, OppCurve>* test = fHead; 10751049f1246e7be4ccb68001361efceb8933e6f81ccaryclark while (test) { 10761049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (test->fCollapsed) { 10771049f1246e7be4ccb68001361efceb8933e6f81ccaryclark ++result; 10781049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 10791049f1246e7be4ccb68001361efceb8933e6f81ccaryclark test = test->next(); 10801049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 10811049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return result; 10821049f1246e7be4ccb68001361efceb8933e6f81ccaryclark} 10831049f1246e7be4ccb68001361efceb8933e6f81ccaryclark 10841049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 10851049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::computePerpendiculars(SkTSect<OppCurve, TCurve>* sect2, 10861049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last) { 10871049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const OppCurve& opp = sect2->fCurve; 10881049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* work = first; 108996fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkTSpan<TCurve, OppCurve>* prior = nullptr; 109045fa447460f70ec21d22cf4e1531490acfd3c578caryclark do { 109154359294a7c9dc54802d512a5d891a35c1663392caryclark if (!work->fHasPerp && !work->fCollapsed) { 109254359294a7c9dc54802d512a5d891a35c1663392caryclark if (prior) { 109354359294a7c9dc54802d512a5d891a35c1663392caryclark work->fCoinStart = prior->fCoinEnd; 109454359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 109554359294a7c9dc54802d512a5d891a35c1663392caryclark work->fCoinStart.setPerp(fCurve, work->fStartT, work->fPart[0], opp); 1096ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 10976c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark if (work->fCoinStart.isMatch()) { 109854359294a7c9dc54802d512a5d891a35c1663392caryclark double perpT = work->fCoinStart.perpT(); 109954359294a7c9dc54802d512a5d891a35c1663392caryclark if (sect2->coincidentHasT(perpT)) { 1100df386c54bd4b6643af42281631de42e84b07cea7caryclark work->fCoinStart.init(); 110154359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 110254359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->addForPerp(work, perpT); 110354359294a7c9dc54802d512a5d891a35c1663392caryclark } 110454359294a7c9dc54802d512a5d891a35c1663392caryclark } 110554359294a7c9dc54802d512a5d891a35c1663392caryclark work->fCoinEnd.setPerp(fCurve, work->fEndT, work->fPart[TCurve::kPointLast], opp); 11066c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark if (work->fCoinEnd.isMatch()) { 110754359294a7c9dc54802d512a5d891a35c1663392caryclark double perpT = work->fCoinEnd.perpT(); 110854359294a7c9dc54802d512a5d891a35c1663392caryclark if (sect2->coincidentHasT(perpT)) { 1109df386c54bd4b6643af42281631de42e84b07cea7caryclark work->fCoinEnd.init(); 111054359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 111154359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->addForPerp(work, perpT); 111254359294a7c9dc54802d512a5d891a35c1663392caryclark } 111354359294a7c9dc54802d512a5d891a35c1663392caryclark } 111454359294a7c9dc54802d512a5d891a35c1663392caryclark work->fHasPerp = true; 111545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 111645fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (work == last) { 111745fa447460f70ec21d22cf4e1531490acfd3c578caryclark break; 111845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 111954359294a7c9dc54802d512a5d891a35c1663392caryclark prior = work; 112045fa447460f70ec21d22cf4e1531490acfd3c578caryclark work = work->fNext; 112145fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkASSERT(work); 112245fa447460f70ec21d22cf4e1531490acfd3c578caryclark } while (true); 112354359294a7c9dc54802d512a5d891a35c1663392caryclark} 112454359294a7c9dc54802d512a5d891a35c1663392caryclark 11251049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 11261049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkint SkTSect<TCurve, OppCurve>::countConsecutiveSpans(SkTSpan<TCurve, OppCurve>* first, 11271049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>** lastPtr) const { 112854359294a7c9dc54802d512a5d891a35c1663392caryclark int consecutive = 1; 11291049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* last = first; 113054359294a7c9dc54802d512a5d891a35c1663392caryclark do { 11311049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* next = last->fNext; 113254359294a7c9dc54802d512a5d891a35c1663392caryclark if (!next) { 113354359294a7c9dc54802d512a5d891a35c1663392caryclark break; 113454359294a7c9dc54802d512a5d891a35c1663392caryclark } 113554359294a7c9dc54802d512a5d891a35c1663392caryclark if (next->fStartT > last->fEndT) { 113654359294a7c9dc54802d512a5d891a35c1663392caryclark break; 113754359294a7c9dc54802d512a5d891a35c1663392caryclark } 113854359294a7c9dc54802d512a5d891a35c1663392caryclark ++consecutive; 113954359294a7c9dc54802d512a5d891a35c1663392caryclark last = next; 114054359294a7c9dc54802d512a5d891a35c1663392caryclark } while (true); 114154359294a7c9dc54802d512a5d891a35c1663392caryclark *lastPtr = last; 114254359294a7c9dc54802d512a5d891a35c1663392caryclark return consecutive; 114354359294a7c9dc54802d512a5d891a35c1663392caryclark} 114454359294a7c9dc54802d512a5d891a35c1663392caryclark 11451049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 11461049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkbool SkTSect<TCurve, OppCurve>::debugHasBounded(const SkTSpan<OppCurve, TCurve>* span) const { 11471049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<TCurve, OppCurve>* test = fHead; 114854359294a7c9dc54802d512a5d891a35c1663392caryclark if (!test) { 114954359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 115054359294a7c9dc54802d512a5d891a35c1663392caryclark } 115154359294a7c9dc54802d512a5d891a35c1663392caryclark do { 115254359294a7c9dc54802d512a5d891a35c1663392caryclark if (test->findOppSpan(span)) { 115354359294a7c9dc54802d512a5d891a35c1663392caryclark return true; 115454359294a7c9dc54802d512a5d891a35c1663392caryclark } 115554359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((test = test->next())); 115654359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 115754359294a7c9dc54802d512a5d891a35c1663392caryclark} 115854359294a7c9dc54802d512a5d891a35c1663392caryclark 11591049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 1160ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclarkbool SkTSect<TCurve, OppCurve>::deleteEmptySpans() { 11611049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* test; 11621049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* next = fHead; 116359ed482af72beec6812b28d833d8bdf80ba32df7Cary Clark int safetyHatch = 1000; 116454359294a7c9dc54802d512a5d891a35c1663392caryclark while ((test = next)) { 116554359294a7c9dc54802d512a5d891a35c1663392caryclark next = test->fNext; 116654359294a7c9dc54802d512a5d891a35c1663392caryclark if (!test->fBounded) { 1167ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark if (!this->removeSpan(test)) { 1168ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark return false; 1169ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark } 117054359294a7c9dc54802d512a5d891a35c1663392caryclark } 117159ed482af72beec6812b28d833d8bdf80ba32df7Cary Clark if (--safetyHatch < 0) { 117259ed482af72beec6812b28d833d8bdf80ba32df7Cary Clark return false; 117359ed482af72beec6812b28d833d8bdf80ba32df7Cary Clark } 117454359294a7c9dc54802d512a5d891a35c1663392caryclark } 1175ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark return true; 117654359294a7c9dc54802d512a5d891a35c1663392caryclark} 117754359294a7c9dc54802d512a5d891a35c1663392caryclark 11781049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 1179ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclarkbool SkTSect<TCurve, OppCurve>::extractCoincident( 11801049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSect<OppCurve, TCurve>* sect2, 1181ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last, 1182ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark SkTSpan<TCurve, OppCurve>** result) { 11831049f1246e7be4ccb68001361efceb8933e6f81ccaryclark first = findCoincidentRun(first, &last); 1184a1b42d91a5726683d7933b81a6e00ed28649e7edcaryclark if (!first || !last) { 1185ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark *result = nullptr; 1186ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark return true; 118754359294a7c9dc54802d512a5d891a35c1663392caryclark } 118845fa447460f70ec21d22cf4e1531490acfd3c578caryclark // march outwards to find limit of coincidence from here to previous and next spans 118945fa447460f70ec21d22cf4e1531490acfd3c578caryclark double startT = first->fStartT; 1190d8bc16b306f8453a86d0af070d68c327f4bb41ebcaryclark double oppStartT SK_INIT_TO_AVOID_WARNING; 119154359294a7c9dc54802d512a5d891a35c1663392caryclark double oppEndT SK_INIT_TO_AVOID_WARNING; 11921049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* prev = first->fPrev; 11936c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark SkASSERT(first->fCoinStart.isMatch()); 11941049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* oppFirst = first->findOppT(first->fCoinStart.perpT()); 11956c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark SkOPASSERT(last->fCoinEnd.isMatch()); 119654359294a7c9dc54802d512a5d891a35c1663392caryclark bool oppMatched = first->fCoinStart.perpT() < first->fCoinEnd.perpT(); 119754359294a7c9dc54802d512a5d891a35c1663392caryclark double coinStart; 119854359294a7c9dc54802d512a5d891a35c1663392caryclark SkDEBUGCODE(double coinEnd); 11991049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* cutFirst; 120054359294a7c9dc54802d512a5d891a35c1663392caryclark if (prev && prev->fEndT == startT 120154359294a7c9dc54802d512a5d891a35c1663392caryclark && this->binarySearchCoin(sect2, startT, prev->fStartT - startT, &coinStart, 120254359294a7c9dc54802d512a5d891a35c1663392caryclark &oppStartT) 12031049f1246e7be4ccb68001361efceb8933e6f81ccaryclark && prev->fStartT < coinStart && coinStart < startT 12041049f1246e7be4ccb68001361efceb8933e6f81ccaryclark && (cutFirst = prev->oppT(oppStartT))) { 12051049f1246e7be4ccb68001361efceb8933e6f81ccaryclark oppFirst = cutFirst; 120654359294a7c9dc54802d512a5d891a35c1663392caryclark first = this->addSplitAt(prev, coinStart); 120754359294a7c9dc54802d512a5d891a35c1663392caryclark first->markCoincident(); 120854359294a7c9dc54802d512a5d891a35c1663392caryclark prev->fCoinEnd.markCoincident(); 120954359294a7c9dc54802d512a5d891a35c1663392caryclark if (oppFirst->fStartT < oppStartT && oppStartT < oppFirst->fEndT) { 12101049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* oppHalf = sect2->addSplitAt(oppFirst, oppStartT); 121154359294a7c9dc54802d512a5d891a35c1663392caryclark if (oppMatched) { 121254359294a7c9dc54802d512a5d891a35c1663392caryclark oppFirst->fCoinEnd.markCoincident(); 121354359294a7c9dc54802d512a5d891a35c1663392caryclark oppHalf->markCoincident(); 121454359294a7c9dc54802d512a5d891a35c1663392caryclark oppFirst = oppHalf; 121554359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 121654359294a7c9dc54802d512a5d891a35c1663392caryclark oppFirst->markCoincident(); 121754359294a7c9dc54802d512a5d891a35c1663392caryclark oppHalf->fCoinStart.markCoincident(); 121854359294a7c9dc54802d512a5d891a35c1663392caryclark } 121954359294a7c9dc54802d512a5d891a35c1663392caryclark } 122054359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 122154359294a7c9dc54802d512a5d891a35c1663392caryclark SkDEBUGCODE(coinStart = first->fStartT); 1222a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(!oppFirst); 122354359294a7c9dc54802d512a5d891a35c1663392caryclark SkDEBUGCODE(oppStartT = oppMatched ? oppFirst->fStartT : oppFirst->fEndT); 122454359294a7c9dc54802d512a5d891a35c1663392caryclark } 12251049f1246e7be4ccb68001361efceb8933e6f81ccaryclark // FIXME: incomplete : if we're not at the end, find end of coin 12261049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* oppLast; 12276c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark SkOPASSERT(last->fCoinEnd.isMatch()); 122854359294a7c9dc54802d512a5d891a35c1663392caryclark oppLast = last->findOppT(last->fCoinEnd.perpT()); 122954359294a7c9dc54802d512a5d891a35c1663392caryclark SkDEBUGCODE(coinEnd = last->fEndT); 1230643ede69216c073c2dd497c382577dc9fde36b3ecaryclark#ifdef SK_DEBUG 1231643ede69216c073c2dd497c382577dc9fde36b3ecaryclark if (!this->globalState() || !this->globalState()->debugSkipAssert()) { 1232643ede69216c073c2dd497c382577dc9fde36b3ecaryclark oppEndT = oppMatched ? oppLast->fEndT : oppLast->fStartT; 1233643ede69216c073c2dd497c382577dc9fde36b3ecaryclark } 1234643ede69216c073c2dd497c382577dc9fde36b3ecaryclark#endif 123554359294a7c9dc54802d512a5d891a35c1663392caryclark if (!oppMatched) { 123654359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(oppFirst, oppLast); 123754359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(oppStartT, oppEndT); 123854359294a7c9dc54802d512a5d891a35c1663392caryclark } 1239e25a4f6cbeaccfdc34cf031103f0fbc3e53a3ee5caryclark SkOPASSERT(oppStartT < oppEndT); 124054359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(coinStart == first->fStartT); 124154359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(coinEnd == last->fEndT); 1242643ede69216c073c2dd497c382577dc9fde36b3ecaryclark SkOPASSERT(oppStartT == oppFirst->fStartT); 1243643ede69216c073c2dd497c382577dc9fde36b3ecaryclark SkOPASSERT(oppEndT == oppLast->fEndT); 1244643ede69216c073c2dd497c382577dc9fde36b3ecaryclark if (!oppFirst) { 1245ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark *result = nullptr; 1246ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark return true; 1247643ede69216c073c2dd497c382577dc9fde36b3ecaryclark } 1248429428660b247bb3ccb3195aa8b3abe3194d4d5bcaryclark if (!oppLast) { 1249ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark *result = nullptr; 1250ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark return true; 1251429428660b247bb3ccb3195aa8b3abe3194d4d5bcaryclark } 125254359294a7c9dc54802d512a5d891a35c1663392caryclark // reduce coincident runs to single entries 125354359294a7c9dc54802d512a5d891a35c1663392caryclark this->validate(); 125454359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->validate(); 12551049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool deleteEmptySpans = this->updateBounded(first, last, oppFirst); 12561049f1246e7be4ccb68001361efceb8933e6f81ccaryclark deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first); 125754359294a7c9dc54802d512a5d891a35c1663392caryclark this->removeSpanRange(first, last); 125854359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->removeSpanRange(oppFirst, oppLast); 125954359294a7c9dc54802d512a5d891a35c1663392caryclark first->fEndT = last->fEndT; 126054359294a7c9dc54802d512a5d891a35c1663392caryclark first->resetBounds(this->fCurve); 126154359294a7c9dc54802d512a5d891a35c1663392caryclark first->fCoinStart.setPerp(fCurve, first->fStartT, first->fPart[0], sect2->fCurve); 126254359294a7c9dc54802d512a5d891a35c1663392caryclark first->fCoinEnd.setPerp(fCurve, first->fEndT, first->fPart[TCurve::kPointLast], sect2->fCurve); 126354359294a7c9dc54802d512a5d891a35c1663392caryclark oppStartT = first->fCoinStart.perpT(); 126454359294a7c9dc54802d512a5d891a35c1663392caryclark oppEndT = first->fCoinEnd.perpT(); 126554359294a7c9dc54802d512a5d891a35c1663392caryclark if (between(0, oppStartT, 1) && between(0, oppEndT, 1)) { 126654359294a7c9dc54802d512a5d891a35c1663392caryclark if (!oppMatched) { 126754359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(oppStartT, oppEndT); 126854359294a7c9dc54802d512a5d891a35c1663392caryclark } 126954359294a7c9dc54802d512a5d891a35c1663392caryclark oppFirst->fStartT = oppStartT; 127054359294a7c9dc54802d512a5d891a35c1663392caryclark oppFirst->fEndT = oppEndT; 127154359294a7c9dc54802d512a5d891a35c1663392caryclark oppFirst->resetBounds(sect2->fCurve); 127254359294a7c9dc54802d512a5d891a35c1663392caryclark } 127354359294a7c9dc54802d512a5d891a35c1663392caryclark this->validateBounded(); 127454359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->validateBounded(); 127554359294a7c9dc54802d512a5d891a35c1663392caryclark last = first->fNext; 127654359294a7c9dc54802d512a5d891a35c1663392caryclark this->removeCoincident(first, false); 127754359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->removeCoincident(oppFirst, true); 12781049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (deleteEmptySpans) { 1279ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark if (!this->deleteEmptySpans() || !sect2->deleteEmptySpans()) { 1280ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark *result = nullptr; 1281ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark return false; 1282ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark } 128354359294a7c9dc54802d512a5d891a35c1663392caryclark } 128454359294a7c9dc54802d512a5d891a35c1663392caryclark this->validate(); 128554359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->validate(); 1286ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark *result = last && !last->fDeleted && fHead && sect2->fHead ? last : nullptr; 1287ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark return true; 128854359294a7c9dc54802d512a5d891a35c1663392caryclark} 128954359294a7c9dc54802d512a5d891a35c1663392caryclark 12901049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 12911049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkSkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::findCoincidentRun( 12921049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>** lastPtr) { 12931049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* work = first; 129496fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkTSpan<TCurve, OppCurve>* lastCandidate = nullptr; 129596fcdcc219d2a0d3579719b84b28bede76efba64halcanary first = nullptr; 129654359294a7c9dc54802d512a5d891a35c1663392caryclark // find the first fully coincident span 129754359294a7c9dc54802d512a5d891a35c1663392caryclark do { 12986c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark if (work->fCoinStart.isMatch()) { 12991049f1246e7be4ccb68001361efceb8933e6f81ccaryclark#if DEBUG_T_SECT 130054359294a7c9dc54802d512a5d891a35c1663392caryclark work->validatePerpT(work->fCoinStart.perpT()); 130154359294a7c9dc54802d512a5d891a35c1663392caryclark work->validatePerpPt(work->fCoinStart.perpT(), work->fCoinStart.perpPt()); 13021049f1246e7be4ccb68001361efceb8933e6f81ccaryclark#endif 1303a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark SkOPASSERT(work->hasOppT(work->fCoinStart.perpT())); 13046c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark if (!work->fCoinEnd.isMatch()) { 130554359294a7c9dc54802d512a5d891a35c1663392caryclark break; 130654359294a7c9dc54802d512a5d891a35c1663392caryclark } 130754359294a7c9dc54802d512a5d891a35c1663392caryclark lastCandidate = work; 130854359294a7c9dc54802d512a5d891a35c1663392caryclark if (!first) { 130954359294a7c9dc54802d512a5d891a35c1663392caryclark first = work; 131054359294a7c9dc54802d512a5d891a35c1663392caryclark } 13111049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } else if (first && work->fCollapsed) { 13121049f1246e7be4ccb68001361efceb8933e6f81ccaryclark *lastPtr = lastCandidate; 13131049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return first; 131454359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 131596fcdcc219d2a0d3579719b84b28bede76efba64halcanary lastCandidate = nullptr; 1316643ede69216c073c2dd497c382577dc9fde36b3ecaryclark SkOPASSERT(!first); 131754359294a7c9dc54802d512a5d891a35c1663392caryclark } 131854359294a7c9dc54802d512a5d891a35c1663392caryclark if (work == *lastPtr) { 131954359294a7c9dc54802d512a5d891a35c1663392caryclark return first; 132054359294a7c9dc54802d512a5d891a35c1663392caryclark } 132154359294a7c9dc54802d512a5d891a35c1663392caryclark work = work->fNext; 1322e25a4f6cbeaccfdc34cf031103f0fbc3e53a3ee5caryclark if (!work) { 1323e25a4f6cbeaccfdc34cf031103f0fbc3e53a3ee5caryclark return nullptr; 1324e25a4f6cbeaccfdc34cf031103f0fbc3e53a3ee5caryclark } 132554359294a7c9dc54802d512a5d891a35c1663392caryclark } while (true); 132654359294a7c9dc54802d512a5d891a35c1663392caryclark if (lastCandidate) { 132754359294a7c9dc54802d512a5d891a35c1663392caryclark *lastPtr = lastCandidate; 132854359294a7c9dc54802d512a5d891a35c1663392caryclark } 132954359294a7c9dc54802d512a5d891a35c1663392caryclark return first; 133054359294a7c9dc54802d512a5d891a35c1663392caryclark} 133154359294a7c9dc54802d512a5d891a35c1663392caryclark 13321049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 13331049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkint SkTSect<TCurve, OppCurve>::intersects(SkTSpan<TCurve, OppCurve>* span, 13341049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSect<OppCurve, TCurve>* opp, 13351049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* oppSpan, int* oppResult) { 133654359294a7c9dc54802d512a5d891a35c1663392caryclark bool spanStart, oppStart; 133754359294a7c9dc54802d512a5d891a35c1663392caryclark int hullResult = span->hullsIntersect(oppSpan, &spanStart, &oppStart); 133854359294a7c9dc54802d512a5d891a35c1663392caryclark if (hullResult >= 0) { 133954359294a7c9dc54802d512a5d891a35c1663392caryclark if (hullResult == 2) { // hulls have one point in common 134054359294a7c9dc54802d512a5d891a35c1663392caryclark if (!span->fBounded || !span->fBounded->fNext) { 134154359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!span->fBounded || span->fBounded->fBounded == oppSpan); 134254359294a7c9dc54802d512a5d891a35c1663392caryclark if (spanStart) { 134354359294a7c9dc54802d512a5d891a35c1663392caryclark span->fEndT = span->fStartT; 134445fa447460f70ec21d22cf4e1531490acfd3c578caryclark } else { 134554359294a7c9dc54802d512a5d891a35c1663392caryclark span->fStartT = span->fEndT; 134645fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 134754359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 134854359294a7c9dc54802d512a5d891a35c1663392caryclark hullResult = 1; 134945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 135054359294a7c9dc54802d512a5d891a35c1663392caryclark if (!oppSpan->fBounded || !oppSpan->fBounded->fNext) { 135154359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!oppSpan->fBounded || oppSpan->fBounded->fBounded == span); 135254359294a7c9dc54802d512a5d891a35c1663392caryclark if (oppStart) { 135354359294a7c9dc54802d512a5d891a35c1663392caryclark oppSpan->fEndT = oppSpan->fStartT; 135454359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 135554359294a7c9dc54802d512a5d891a35c1663392caryclark oppSpan->fStartT = oppSpan->fEndT; 135654359294a7c9dc54802d512a5d891a35c1663392caryclark } 135754359294a7c9dc54802d512a5d891a35c1663392caryclark *oppResult = 2; 135854359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 135954359294a7c9dc54802d512a5d891a35c1663392caryclark *oppResult = 1; 136054359294a7c9dc54802d512a5d891a35c1663392caryclark } 136154359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 136254359294a7c9dc54802d512a5d891a35c1663392caryclark *oppResult = 1; 1363ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 136454359294a7c9dc54802d512a5d891a35c1663392caryclark return hullResult; 1365ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 136654359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->fIsLine && oppSpan->fIsLine) { 136754359294a7c9dc54802d512a5d891a35c1663392caryclark SkIntersections i; 136854359294a7c9dc54802d512a5d891a35c1663392caryclark int sects = this->linesIntersect(span, opp, oppSpan, &i); 136926ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark if (sects == 2) { 137026ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark return *oppResult = 1; 137126ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark } 137254359294a7c9dc54802d512a5d891a35c1663392caryclark if (!sects) { 137354359294a7c9dc54802d512a5d891a35c1663392caryclark return -1; 137454359294a7c9dc54802d512a5d891a35c1663392caryclark } 137534efb7039851d7796ba06aa58e5c5882ede503accaryclark this->removedEndCheck(span); 137654359294a7c9dc54802d512a5d891a35c1663392caryclark span->fStartT = span->fEndT = i[0][0]; 137734efb7039851d7796ba06aa58e5c5882ede503accaryclark opp->removedEndCheck(oppSpan); 137854359294a7c9dc54802d512a5d891a35c1663392caryclark oppSpan->fStartT = oppSpan->fEndT = i[1][0]; 137954359294a7c9dc54802d512a5d891a35c1663392caryclark return *oppResult = 2; 138054359294a7c9dc54802d512a5d891a35c1663392caryclark } 138154359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->fIsLinear || oppSpan->fIsLinear) { 138254359294a7c9dc54802d512a5d891a35c1663392caryclark return *oppResult = (int) span->linearsIntersect(oppSpan); 138354359294a7c9dc54802d512a5d891a35c1663392caryclark } 138454359294a7c9dc54802d512a5d891a35c1663392caryclark return *oppResult = 1; 138554359294a7c9dc54802d512a5d891a35c1663392caryclark} 138654359294a7c9dc54802d512a5d891a35c1663392caryclark 1387ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclarktemplate<typename TCurve> 1388ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclarkstatic bool is_parallel(const SkDLine& thisLine, const TCurve& opp) { 1389ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark if (!opp.IsConic()) { 1390ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark return false; // FIXME : breaks a lot of stuff now 1391ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark } 1392ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark int finds = 0; 1393ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark SkDLine thisPerp; 1394ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark thisPerp.fPts[0].fX = thisLine.fPts[1].fX + (thisLine.fPts[1].fY - thisLine.fPts[0].fY); 1395ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark thisPerp.fPts[0].fY = thisLine.fPts[1].fY + (thisLine.fPts[0].fX - thisLine.fPts[1].fX); 1396ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark thisPerp.fPts[1] = thisLine.fPts[1]; 1397ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark SkIntersections perpRayI; 1398ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark perpRayI.intersectRay(opp, thisPerp); 1399ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark for (int pIndex = 0; pIndex < perpRayI.used(); ++pIndex) { 1400ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark finds += perpRayI.pt(pIndex).approximatelyEqual(thisPerp.fPts[1]); 1401ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark } 1402ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark thisPerp.fPts[1].fX = thisLine.fPts[0].fX + (thisLine.fPts[1].fY - thisLine.fPts[0].fY); 1403ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark thisPerp.fPts[1].fY = thisLine.fPts[0].fY + (thisLine.fPts[0].fX - thisLine.fPts[1].fX); 1404ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark thisPerp.fPts[0] = thisLine.fPts[0]; 1405ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark perpRayI.intersectRay(opp, thisPerp); 1406ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark for (int pIndex = 0; pIndex < perpRayI.used(); ++pIndex) { 1407ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark finds += perpRayI.pt(pIndex).approximatelyEqual(thisPerp.fPts[0]); 1408ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark } 1409ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark return finds >= 2; 1410ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark} 1411ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark 141254359294a7c9dc54802d512a5d891a35c1663392caryclark// while the intersection points are sufficiently far apart: 141354359294a7c9dc54802d512a5d891a35c1663392caryclark// construct the tangent lines from the intersections 141454359294a7c9dc54802d512a5d891a35c1663392caryclark// find the point where the tangent line intersects the opposite curve 14151049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 14161049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkint SkTSect<TCurve, OppCurve>::linesIntersect(SkTSpan<TCurve, OppCurve>* span, 14171049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSect<OppCurve, TCurve>* opp, 14181049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* oppSpan, SkIntersections* i) { 1419a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark SkIntersections thisRayI SkDEBUGCODE((span->fDebugGlobalState)); 1420a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark SkIntersections oppRayI SkDEBUGCODE((span->fDebugGlobalState)); 142154359294a7c9dc54802d512a5d891a35c1663392caryclark SkDLine thisLine = {{ span->fPart[0], span->fPart[TCurve::kPointLast] }}; 14221049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDLine oppLine = {{ oppSpan->fPart[0], oppSpan->fPart[OppCurve::kPointLast] }}; 142354359294a7c9dc54802d512a5d891a35c1663392caryclark int loopCount = 0; 142454359294a7c9dc54802d512a5d891a35c1663392caryclark double bestDistSq = DBL_MAX; 14251049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (!thisRayI.intersectRay(opp->fCurve, thisLine)) { 14261049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return 0; 14271049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 14281049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (!oppRayI.intersectRay(this->fCurve, oppLine)) { 14291049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return 0; 14301049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 143126ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark // if the ends of each line intersect the opposite curve, the lines are coincident 143226ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark if (thisRayI.used() > 1) { 143326ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark int ptMatches = 0; 143426ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark for (int tIndex = 0; tIndex < thisRayI.used(); ++tIndex) { 143526ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark for (int lIndex = 0; lIndex < (int) SK_ARRAY_COUNT(thisLine.fPts); ++lIndex) { 143626ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark ptMatches += thisRayI.pt(tIndex).approximatelyEqual(thisLine.fPts[lIndex]); 143726ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark } 143826ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark } 1439ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark if (ptMatches == 2 || is_parallel(thisLine, opp->fCurve)) { 144026ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark return 2; 144126ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark } 144226ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark } 144326ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark if (oppRayI.used() > 1) { 144426ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark int ptMatches = 0; 144526ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark for (int oIndex = 0; oIndex < oppRayI.used(); ++oIndex) { 144626ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark for (int lIndex = 0; lIndex < (int) SK_ARRAY_COUNT(thisLine.fPts); ++lIndex) { 144726ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark ptMatches += oppRayI.pt(oIndex).approximatelyEqual(oppLine.fPts[lIndex]); 144826ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark } 144926ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark } 1450ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark if (ptMatches == 2|| is_parallel(oppLine, this->fCurve)) { 145126ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark return 2; 145226ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark } 145326ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark } 145454359294a7c9dc54802d512a5d891a35c1663392caryclark do { 145554359294a7c9dc54802d512a5d891a35c1663392caryclark // pick the closest pair of points 145654359294a7c9dc54802d512a5d891a35c1663392caryclark double closest = DBL_MAX; 145754359294a7c9dc54802d512a5d891a35c1663392caryclark int closeIndex SK_INIT_TO_AVOID_WARNING; 145854359294a7c9dc54802d512a5d891a35c1663392caryclark int oppCloseIndex SK_INIT_TO_AVOID_WARNING; 145954359294a7c9dc54802d512a5d891a35c1663392caryclark for (int index = 0; index < oppRayI.used(); ++index) { 146054359294a7c9dc54802d512a5d891a35c1663392caryclark if (!roughly_between(span->fStartT, oppRayI[0][index], span->fEndT)) { 146154359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 146254359294a7c9dc54802d512a5d891a35c1663392caryclark } 146354359294a7c9dc54802d512a5d891a35c1663392caryclark for (int oIndex = 0; oIndex < thisRayI.used(); ++oIndex) { 146454359294a7c9dc54802d512a5d891a35c1663392caryclark if (!roughly_between(oppSpan->fStartT, thisRayI[0][oIndex], oppSpan->fEndT)) { 146554359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 146654359294a7c9dc54802d512a5d891a35c1663392caryclark } 146754359294a7c9dc54802d512a5d891a35c1663392caryclark double distSq = thisRayI.pt(index).distanceSquared(oppRayI.pt(oIndex)); 146854359294a7c9dc54802d512a5d891a35c1663392caryclark if (closest > distSq) { 146954359294a7c9dc54802d512a5d891a35c1663392caryclark closest = distSq; 147054359294a7c9dc54802d512a5d891a35c1663392caryclark closeIndex = index; 147154359294a7c9dc54802d512a5d891a35c1663392caryclark oppCloseIndex = oIndex; 147245fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 147345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 147445fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 147554359294a7c9dc54802d512a5d891a35c1663392caryclark if (closest == DBL_MAX) { 14761049f1246e7be4ccb68001361efceb8933e6f81ccaryclark break; 147754359294a7c9dc54802d512a5d891a35c1663392caryclark } 147854359294a7c9dc54802d512a5d891a35c1663392caryclark const SkDPoint& oppIPt = thisRayI.pt(oppCloseIndex); 147954359294a7c9dc54802d512a5d891a35c1663392caryclark const SkDPoint& iPt = oppRayI.pt(closeIndex); 148054359294a7c9dc54802d512a5d891a35c1663392caryclark if (between(span->fStartT, oppRayI[0][closeIndex], span->fEndT) 148154359294a7c9dc54802d512a5d891a35c1663392caryclark && between(oppSpan->fStartT, thisRayI[0][oppCloseIndex], oppSpan->fEndT) 148254359294a7c9dc54802d512a5d891a35c1663392caryclark && oppIPt.approximatelyEqual(iPt)) { 148354359294a7c9dc54802d512a5d891a35c1663392caryclark i->merge(oppRayI, closeIndex, thisRayI, oppCloseIndex); 148454359294a7c9dc54802d512a5d891a35c1663392caryclark return i->used(); 148554359294a7c9dc54802d512a5d891a35c1663392caryclark } 148654359294a7c9dc54802d512a5d891a35c1663392caryclark double distSq = oppIPt.distanceSquared(iPt); 148754359294a7c9dc54802d512a5d891a35c1663392caryclark if (bestDistSq < distSq || ++loopCount > 5) { 14881049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return 0; 148954359294a7c9dc54802d512a5d891a35c1663392caryclark } 149054359294a7c9dc54802d512a5d891a35c1663392caryclark bestDistSq = distSq; 14911049f1246e7be4ccb68001361efceb8933e6f81ccaryclark double oppStart = oppRayI[0][closeIndex]; 14921049f1246e7be4ccb68001361efceb8933e6f81ccaryclark thisLine[0] = fCurve.ptAtT(oppStart); 14931049f1246e7be4ccb68001361efceb8933e6f81ccaryclark thisLine[1] = thisLine[0] + fCurve.dxdyAtT(oppStart); 14941049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (!thisRayI.intersectRay(opp->fCurve, thisLine)) { 14951049f1246e7be4ccb68001361efceb8933e6f81ccaryclark break; 14961049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 14971049f1246e7be4ccb68001361efceb8933e6f81ccaryclark double start = thisRayI[0][oppCloseIndex]; 14981049f1246e7be4ccb68001361efceb8933e6f81ccaryclark oppLine[0] = opp->fCurve.ptAtT(start); 14991049f1246e7be4ccb68001361efceb8933e6f81ccaryclark oppLine[1] = oppLine[0] + opp->fCurve.dxdyAtT(start); 15001049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (!oppRayI.intersectRay(this->fCurve, oppLine)) { 15011049f1246e7be4ccb68001361efceb8933e6f81ccaryclark break; 15021049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 150354359294a7c9dc54802d512a5d891a35c1663392caryclark } while (true); 15041049f1246e7be4ccb68001361efceb8933e6f81ccaryclark // convergence may fail if the curves are nearly coincident 15051049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTCoincident<OppCurve, TCurve> oCoinS, oCoinE; 15061049f1246e7be4ccb68001361efceb8933e6f81ccaryclark oCoinS.setPerp(opp->fCurve, oppSpan->fStartT, oppSpan->fPart[0], fCurve); 15071049f1246e7be4ccb68001361efceb8933e6f81ccaryclark oCoinE.setPerp(opp->fCurve, oppSpan->fEndT, oppSpan->fPart[OppCurve::kPointLast], fCurve); 15081049f1246e7be4ccb68001361efceb8933e6f81ccaryclark double tStart = oCoinS.perpT(); 15091049f1246e7be4ccb68001361efceb8933e6f81ccaryclark double tEnd = oCoinE.perpT(); 15101049f1246e7be4ccb68001361efceb8933e6f81ccaryclark bool swap = tStart > tEnd; 15111049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (swap) { 15121049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSwap(tStart, tEnd); 15131049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 15141049f1246e7be4ccb68001361efceb8933e6f81ccaryclark tStart = SkTMax(tStart, span->fStartT); 15151049f1246e7be4ccb68001361efceb8933e6f81ccaryclark tEnd = SkTMin(tEnd, span->fEndT); 15161049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (tStart > tEnd) { 15171049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return 0; 15181049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 15191049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDVector perpS, perpE; 15201049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (tStart == span->fStartT) { 15211049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTCoincident<TCurve, OppCurve> coinS; 15221049f1246e7be4ccb68001361efceb8933e6f81ccaryclark coinS.setPerp(fCurve, span->fStartT, span->fPart[0], opp->fCurve); 15231049f1246e7be4ccb68001361efceb8933e6f81ccaryclark perpS = span->fPart[0] - coinS.perpPt(); 15241049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } else if (swap) { 15251049f1246e7be4ccb68001361efceb8933e6f81ccaryclark perpS = oCoinE.perpPt() - oppSpan->fPart[OppCurve::kPointLast]; 15261049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } else { 15271049f1246e7be4ccb68001361efceb8933e6f81ccaryclark perpS = oCoinS.perpPt() - oppSpan->fPart[0]; 15281049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 15291049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (tEnd == span->fEndT) { 15301049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTCoincident<TCurve, OppCurve> coinE; 15311049f1246e7be4ccb68001361efceb8933e6f81ccaryclark coinE.setPerp(fCurve, span->fEndT, span->fPart[TCurve::kPointLast], opp->fCurve); 15321049f1246e7be4ccb68001361efceb8933e6f81ccaryclark perpE = span->fPart[TCurve::kPointLast] - coinE.perpPt(); 15331049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } else if (swap) { 15341049f1246e7be4ccb68001361efceb8933e6f81ccaryclark perpE = oCoinS.perpPt() - oppSpan->fPart[0]; 15351049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } else { 15361049f1246e7be4ccb68001361efceb8933e6f81ccaryclark perpE = oCoinE.perpPt() - oppSpan->fPart[OppCurve::kPointLast]; 15371049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 15381049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (perpS.dot(perpE) >= 0) { 15391049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return 0; 15401049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 15411049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTCoincident<TCurve, OppCurve> coinW; 15421049f1246e7be4ccb68001361efceb8933e6f81ccaryclark double workT = tStart; 15431049f1246e7be4ccb68001361efceb8933e6f81ccaryclark double tStep = tEnd - tStart; 15441049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDPoint workPt; 15451049f1246e7be4ccb68001361efceb8933e6f81ccaryclark do { 15461049f1246e7be4ccb68001361efceb8933e6f81ccaryclark tStep *= 0.5; 15471049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (precisely_zero(tStep)) { 15481049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return 0; 15491049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 15501049f1246e7be4ccb68001361efceb8933e6f81ccaryclark workT += tStep; 15511049f1246e7be4ccb68001361efceb8933e6f81ccaryclark workPt = fCurve.ptAtT(workT); 15521049f1246e7be4ccb68001361efceb8933e6f81ccaryclark coinW.setPerp(fCurve, workT, workPt, opp->fCurve); 155327c015dfcf4e2b8fb1abe327cc40204e2a4f452acaryclark double perpT = coinW.perpT(); 15546c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark if (coinW.isMatch() ? !between(oppSpan->fStartT, perpT, oppSpan->fEndT) : perpT < 0) { 1555b669300a9753893ef900207c38aeff2d467764e5caryclark continue; 1556b669300a9753893ef900207c38aeff2d467764e5caryclark } 15571049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDVector perpW = workPt - coinW.perpPt(); 15581049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if ((perpS.dot(perpW) >= 0) == (tStep < 0)) { 15591049f1246e7be4ccb68001361efceb8933e6f81ccaryclark tStep = -tStep; 15601049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 1561b669300a9753893ef900207c38aeff2d467764e5caryclark if (workPt.approximatelyEqual(coinW.perpPt())) { 1562b669300a9753893ef900207c38aeff2d467764e5caryclark break; 1563b669300a9753893ef900207c38aeff2d467764e5caryclark } 1564b669300a9753893ef900207c38aeff2d467764e5caryclark } while (true); 15651049f1246e7be4ccb68001361efceb8933e6f81ccaryclark double oppTTest = coinW.perpT(); 15661049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (!opp->fHead->contains(oppTTest)) { 15671049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return 0; 15681049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 15691049f1246e7be4ccb68001361efceb8933e6f81ccaryclark i->setMax(1); 15701049f1246e7be4ccb68001361efceb8933e6f81ccaryclark i->insert(workT, oppTTest, workPt); 15711049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return 1; 157254359294a7c9dc54802d512a5d891a35c1663392caryclark} 157354359294a7c9dc54802d512a5d891a35c1663392caryclark 157454359294a7c9dc54802d512a5d891a35c1663392caryclark 15751049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 1576ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclarkbool SkTSect<TCurve, OppCurve>::markSpanGone(SkTSpan<TCurve, OppCurve>* span) { 1577ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark if (--fActiveCount < 0) { 1578ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark return false; 1579ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark } 158054359294a7c9dc54802d512a5d891a35c1663392caryclark span->fNext = fDeleted; 158154359294a7c9dc54802d512a5d891a35c1663392caryclark fDeleted = span; 1582e25a4f6cbeaccfdc34cf031103f0fbc3e53a3ee5caryclark SkOPASSERT(!span->fDeleted); 158354359294a7c9dc54802d512a5d891a35c1663392caryclark span->fDeleted = true; 1584ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark return true; 158554359294a7c9dc54802d512a5d891a35c1663392caryclark} 158654359294a7c9dc54802d512a5d891a35c1663392caryclark 15871049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 15881049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkbool SkTSect<TCurve, OppCurve>::matchedDirection(double t, const SkTSect<OppCurve, TCurve>* sect2, 15891049f1246e7be4ccb68001361efceb8933e6f81ccaryclark double t2) const { 159054359294a7c9dc54802d512a5d891a35c1663392caryclark SkDVector dxdy = this->fCurve.dxdyAtT(t); 159154359294a7c9dc54802d512a5d891a35c1663392caryclark SkDVector dxdy2 = sect2->fCurve.dxdyAtT(t2); 159254359294a7c9dc54802d512a5d891a35c1663392caryclark return dxdy.dot(dxdy2) >= 0; 159354359294a7c9dc54802d512a5d891a35c1663392caryclark} 159454359294a7c9dc54802d512a5d891a35c1663392caryclark 15951049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 15961049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::matchedDirCheck(double t, const SkTSect<OppCurve, TCurve>* sect2, 15971049f1246e7be4ccb68001361efceb8933e6f81ccaryclark double t2, bool* calcMatched, bool* oppMatched) const { 159854359294a7c9dc54802d512a5d891a35c1663392caryclark if (*calcMatched) { 159955888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(*oppMatched == this->matchedDirection(t, sect2, t2)); 160054359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 160154359294a7c9dc54802d512a5d891a35c1663392caryclark *oppMatched = this->matchedDirection(t, sect2, t2); 160254359294a7c9dc54802d512a5d891a35c1663392caryclark *calcMatched = true; 160354359294a7c9dc54802d512a5d891a35c1663392caryclark } 160454359294a7c9dc54802d512a5d891a35c1663392caryclark} 160554359294a7c9dc54802d512a5d891a35c1663392caryclark 16061049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 16071049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::mergeCoincidence(SkTSect<OppCurve, TCurve>* sect2) { 160854359294a7c9dc54802d512a5d891a35c1663392caryclark double smallLimit = 0; 160954359294a7c9dc54802d512a5d891a35c1663392caryclark do { 161054359294a7c9dc54802d512a5d891a35c1663392caryclark // find the smallest unprocessed span 161196fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkTSpan<TCurve, OppCurve>* smaller = nullptr; 16121049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* test = fCoincident; 161354359294a7c9dc54802d512a5d891a35c1663392caryclark do { 1614221a4bb55b51a6ba3882811990581d4bdb6bd539caryclark if (!test) { 1615221a4bb55b51a6ba3882811990581d4bdb6bd539caryclark return; 1616221a4bb55b51a6ba3882811990581d4bdb6bd539caryclark } 161754359294a7c9dc54802d512a5d891a35c1663392caryclark if (test->fStartT < smallLimit) { 161854359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 161954359294a7c9dc54802d512a5d891a35c1663392caryclark } 162054359294a7c9dc54802d512a5d891a35c1663392caryclark if (smaller && smaller->fEndT < test->fStartT) { 162154359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 162254359294a7c9dc54802d512a5d891a35c1663392caryclark } 162354359294a7c9dc54802d512a5d891a35c1663392caryclark smaller = test; 162454359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((test = test->fNext)); 162554359294a7c9dc54802d512a5d891a35c1663392caryclark if (!smaller) { 162654359294a7c9dc54802d512a5d891a35c1663392caryclark return; 162754359294a7c9dc54802d512a5d891a35c1663392caryclark } 162854359294a7c9dc54802d512a5d891a35c1663392caryclark smallLimit = smaller->fEndT; 162954359294a7c9dc54802d512a5d891a35c1663392caryclark // find next larger span 163096fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkTSpan<TCurve, OppCurve>* prior = nullptr; 163196fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkTSpan<TCurve, OppCurve>* larger = nullptr; 163296fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkTSpan<TCurve, OppCurve>* largerPrior = nullptr; 163354359294a7c9dc54802d512a5d891a35c1663392caryclark test = fCoincident; 163454359294a7c9dc54802d512a5d891a35c1663392caryclark do { 163554359294a7c9dc54802d512a5d891a35c1663392caryclark if (test->fStartT < smaller->fEndT) { 163654359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 163754359294a7c9dc54802d512a5d891a35c1663392caryclark } 1638221a4bb55b51a6ba3882811990581d4bdb6bd539caryclark SkOPASSERT(test->fStartT != smaller->fEndT); 163954359294a7c9dc54802d512a5d891a35c1663392caryclark if (larger && larger->fStartT < test->fStartT) { 164054359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 164154359294a7c9dc54802d512a5d891a35c1663392caryclark } 164254359294a7c9dc54802d512a5d891a35c1663392caryclark largerPrior = prior; 164354359294a7c9dc54802d512a5d891a35c1663392caryclark larger = test; 164454359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((prior = test), (test = test->fNext)); 164554359294a7c9dc54802d512a5d891a35c1663392caryclark if (!larger) { 164654359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 164754359294a7c9dc54802d512a5d891a35c1663392caryclark } 164854359294a7c9dc54802d512a5d891a35c1663392caryclark // check middle t value to see if it is coincident as well 164954359294a7c9dc54802d512a5d891a35c1663392caryclark double midT = (smaller->fEndT + larger->fStartT) / 2; 165054359294a7c9dc54802d512a5d891a35c1663392caryclark SkDPoint midPt = fCurve.ptAtT(midT); 16511049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTCoincident<TCurve, OppCurve> coin; 165254359294a7c9dc54802d512a5d891a35c1663392caryclark coin.setPerp(fCurve, midT, midPt, sect2->fCurve); 16536c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark if (coin.isMatch()) { 165454359294a7c9dc54802d512a5d891a35c1663392caryclark smaller->fEndT = larger->fEndT; 165554359294a7c9dc54802d512a5d891a35c1663392caryclark smaller->fCoinEnd = larger->fCoinEnd; 165654359294a7c9dc54802d512a5d891a35c1663392caryclark if (largerPrior) { 165754359294a7c9dc54802d512a5d891a35c1663392caryclark largerPrior->fNext = larger->fNext; 1658643ede69216c073c2dd497c382577dc9fde36b3ecaryclark largerPrior->validate(); 165954359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 166054359294a7c9dc54802d512a5d891a35c1663392caryclark fCoincident = larger->fNext; 166154359294a7c9dc54802d512a5d891a35c1663392caryclark } 166254359294a7c9dc54802d512a5d891a35c1663392caryclark } 166354359294a7c9dc54802d512a5d891a35c1663392caryclark } while (true); 166454359294a7c9dc54802d512a5d891a35c1663392caryclark} 166554359294a7c9dc54802d512a5d891a35c1663392caryclark 16661049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 16671049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkSkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::prev( 16681049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* span) const { 166996fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkTSpan<TCurve, OppCurve>* result = nullptr; 16701049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* test = fHead; 167154359294a7c9dc54802d512a5d891a35c1663392caryclark while (span != test) { 167254359294a7c9dc54802d512a5d891a35c1663392caryclark result = test; 167354359294a7c9dc54802d512a5d891a35c1663392caryclark test = test->fNext; 167454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(test); 167545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 167655888e44171ffd48b591d19256884a969fe4da17caryclark return result; 167745fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 167845fa447460f70ec21d22cf4e1531490acfd3c578caryclark 16791049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 16801049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::recoverCollapsed() { 16811049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* deleted = fDeleted; 168245fa447460f70ec21d22cf4e1531490acfd3c578caryclark while (deleted) { 16831049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* delNext = deleted->fNext; 168445fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (deleted->fCollapsed) { 16851049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>** spanPtr = &fHead; 168645fa447460f70ec21d22cf4e1531490acfd3c578caryclark while (*spanPtr && (*spanPtr)->fEndT <= deleted->fStartT) { 168745fa447460f70ec21d22cf4e1531490acfd3c578caryclark spanPtr = &(*spanPtr)->fNext; 168845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 168945fa447460f70ec21d22cf4e1531490acfd3c578caryclark deleted->fNext = *spanPtr; 169045fa447460f70ec21d22cf4e1531490acfd3c578caryclark *spanPtr = deleted; 169145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 169245fa447460f70ec21d22cf4e1531490acfd3c578caryclark deleted = delNext; 169345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 169445fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 169545fa447460f70ec21d22cf4e1531490acfd3c578caryclark 16961049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 16971049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::removeAllBut(const SkTSpan<OppCurve, TCurve>* keep, 16981049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp) { 16991049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpanBounded<OppCurve, TCurve>* testBounded = span->fBounded; 170054359294a7c9dc54802d512a5d891a35c1663392caryclark while (testBounded) { 17011049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* bounded = testBounded->fBounded; 17021049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpanBounded<OppCurve, TCurve>* next = testBounded->fNext; 170354359294a7c9dc54802d512a5d891a35c1663392caryclark // may have been deleted when opp did 'remove all but' 170454359294a7c9dc54802d512a5d891a35c1663392caryclark if (bounded != keep && !bounded->fDeleted) { 170554359294a7c9dc54802d512a5d891a35c1663392caryclark SkAssertResult(SkDEBUGCODE(!) span->removeBounded(bounded)); 170654359294a7c9dc54802d512a5d891a35c1663392caryclark if (bounded->removeBounded(span)) { 170754359294a7c9dc54802d512a5d891a35c1663392caryclark opp->removeSpan(bounded); 170854359294a7c9dc54802d512a5d891a35c1663392caryclark } 170945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 171054359294a7c9dc54802d512a5d891a35c1663392caryclark testBounded = next; 171145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 171254359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!span->fDeleted); 171354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(span->findOppSpan(keep)); 171454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(keep->findOppSpan(span)); 171554359294a7c9dc54802d512a5d891a35c1663392caryclark} 171654359294a7c9dc54802d512a5d891a35c1663392caryclark 17171049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 17181049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::removeByPerpendicular(SkTSect<OppCurve, TCurve>* opp) { 17191049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* test = fHead; 17201049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* next; 172154359294a7c9dc54802d512a5d891a35c1663392caryclark do { 172254359294a7c9dc54802d512a5d891a35c1663392caryclark next = test->fNext; 172354359294a7c9dc54802d512a5d891a35c1663392caryclark if (test->fCoinStart.perpT() < 0 || test->fCoinEnd.perpT() < 0) { 172454359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 172554359294a7c9dc54802d512a5d891a35c1663392caryclark } 172654359294a7c9dc54802d512a5d891a35c1663392caryclark SkDVector startV = test->fCoinStart.perpPt() - test->fPart[0]; 172754359294a7c9dc54802d512a5d891a35c1663392caryclark SkDVector endV = test->fCoinEnd.perpPt() - test->fPart[TCurve::kPointLast]; 172845fa447460f70ec21d22cf4e1531490acfd3c578caryclark#if DEBUG_T_SECT 172954359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s startV=(%1.9g,%1.9g) endV=(%1.9g,%1.9g) dot=%1.9g\n", __FUNCTION__, 173054359294a7c9dc54802d512a5d891a35c1663392caryclark startV.fX, startV.fY, endV.fX, endV.fY, startV.dot(endV)); 173145fa447460f70ec21d22cf4e1531490acfd3c578caryclark#endif 173254359294a7c9dc54802d512a5d891a35c1663392caryclark if (startV.dot(endV) <= 0) { 173354359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 173454359294a7c9dc54802d512a5d891a35c1663392caryclark } 173554359294a7c9dc54802d512a5d891a35c1663392caryclark this->removeSpans(test, opp); 173654359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((test = next)); 173745fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 173845fa447460f70ec21d22cf4e1531490acfd3c578caryclark 17391049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 17401049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::removeCoincident(SkTSpan<TCurve, OppCurve>* span, bool isBetween) { 174154359294a7c9dc54802d512a5d891a35c1663392caryclark this->unlinkSpan(span); 174254359294a7c9dc54802d512a5d891a35c1663392caryclark if (isBetween || between(0, span->fCoinStart.perpT(), 1)) { 174354359294a7c9dc54802d512a5d891a35c1663392caryclark --fActiveCount; 174454359294a7c9dc54802d512a5d891a35c1663392caryclark span->fNext = fCoincident; 174554359294a7c9dc54802d512a5d891a35c1663392caryclark fCoincident = span; 174654359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 174754359294a7c9dc54802d512a5d891a35c1663392caryclark this->markSpanGone(span); 1748ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 1749ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark} 1750ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark 17511049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 175234efb7039851d7796ba06aa58e5c5882ede503accaryclarkvoid SkTSect<TCurve, OppCurve>::removedEndCheck(SkTSpan<TCurve, OppCurve>* span) { 17536c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark if (!span->fStartT) { 17546c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark fRemovedStartT = true; 17556c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark } 17566c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark if (1 == span->fEndT) { 17576c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark fRemovedEndT = true; 17586c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark } 175934efb7039851d7796ba06aa58e5c5882ede503accaryclark} 176034efb7039851d7796ba06aa58e5c5882ede503accaryclark 176134efb7039851d7796ba06aa58e5c5882ede503accaryclarktemplate<typename TCurve, typename OppCurve> 176234efb7039851d7796ba06aa58e5c5882ede503accaryclarkbool SkTSect<TCurve, OppCurve>::removeSpan(SkTSpan<TCurve, OppCurve>* span) {\ 176334efb7039851d7796ba06aa58e5c5882ede503accaryclark this->removedEndCheck(span); 176454359294a7c9dc54802d512a5d891a35c1663392caryclark this->unlinkSpan(span); 1765ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark return this->markSpanGone(span); 176645fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 176745fa447460f70ec21d22cf4e1531490acfd3c578caryclark 17681049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 17691049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::removeSpanRange(SkTSpan<TCurve, OppCurve>* first, 17701049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* last) { 177154359294a7c9dc54802d512a5d891a35c1663392caryclark if (first == last) { 177254359294a7c9dc54802d512a5d891a35c1663392caryclark return; 177345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 17741049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* span = first; 177554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(span); 17761049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* final = last->fNext; 17771049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* next = span->fNext; 177854359294a7c9dc54802d512a5d891a35c1663392caryclark while ((span = next) && span != final) { 177954359294a7c9dc54802d512a5d891a35c1663392caryclark next = span->fNext; 178054359294a7c9dc54802d512a5d891a35c1663392caryclark this->markSpanGone(span); 178154359294a7c9dc54802d512a5d891a35c1663392caryclark } 178254359294a7c9dc54802d512a5d891a35c1663392caryclark if (final) { 178354359294a7c9dc54802d512a5d891a35c1663392caryclark final->fPrev = first; 178454359294a7c9dc54802d512a5d891a35c1663392caryclark } 178554359294a7c9dc54802d512a5d891a35c1663392caryclark first->fNext = final; 1786643ede69216c073c2dd497c382577dc9fde36b3ecaryclark first->validate(); 178754359294a7c9dc54802d512a5d891a35c1663392caryclark} 178854359294a7c9dc54802d512a5d891a35c1663392caryclark 17891049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 17901049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::removeSpans(SkTSpan<TCurve, OppCurve>* span, 17911049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSect<OppCurve, TCurve>* opp) { 17921049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpanBounded<OppCurve, TCurve>* bounded = span->fBounded; 179354359294a7c9dc54802d512a5d891a35c1663392caryclark while (bounded) { 17941049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* spanBounded = bounded->fBounded; 17951049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpanBounded<OppCurve, TCurve>* next = bounded->fNext; 179654359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->removeBounded(spanBounded)) { // shuffles last into position 0 179754359294a7c9dc54802d512a5d891a35c1663392caryclark this->removeSpan(span); 17980dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 179954359294a7c9dc54802d512a5d891a35c1663392caryclark if (spanBounded->removeBounded(span)) { 180054359294a7c9dc54802d512a5d891a35c1663392caryclark opp->removeSpan(spanBounded); 18010dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 180254359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!span->fDeleted || !opp->debugHasBounded(span)); 180354359294a7c9dc54802d512a5d891a35c1663392caryclark bounded = next; 180454359294a7c9dc54802d512a5d891a35c1663392caryclark } 180554359294a7c9dc54802d512a5d891a35c1663392caryclark} 180654359294a7c9dc54802d512a5d891a35c1663392caryclark 18071049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 18081049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkSkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::spanAtT(double t, 18091049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>** priorSpan) { 18101049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* test = fHead; 181196fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkTSpan<TCurve, OppCurve>* prev = nullptr; 181254359294a7c9dc54802d512a5d891a35c1663392caryclark while (test && test->fEndT < t) { 181354359294a7c9dc54802d512a5d891a35c1663392caryclark prev = test; 181454359294a7c9dc54802d512a5d891a35c1663392caryclark test = test->fNext; 181554359294a7c9dc54802d512a5d891a35c1663392caryclark } 181654359294a7c9dc54802d512a5d891a35c1663392caryclark *priorSpan = prev; 181796fcdcc219d2a0d3579719b84b28bede76efba64halcanary return test && test->fStartT <= t ? test : nullptr; 181845fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 181945fa447460f70ec21d22cf4e1531490acfd3c578caryclark 18201049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 18211049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkSkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::tail() { 18221049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* result = fHead; 18231049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* next = fHead; 182445fa447460f70ec21d22cf4e1531490acfd3c578caryclark while ((next = next->fNext)) { 182545fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (next->fEndT > result->fEndT) { 182645fa447460f70ec21d22cf4e1531490acfd3c578caryclark result = next; 182745fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 182845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 182945fa447460f70ec21d22cf4e1531490acfd3c578caryclark return result; 183045fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 183145fa447460f70ec21d22cf4e1531490acfd3c578caryclark 183245fa447460f70ec21d22cf4e1531490acfd3c578caryclark/* Each span has a range of opposite spans it intersects. After the span is split in two, 183345fa447460f70ec21d22cf4e1531490acfd3c578caryclark adjust the range to its new size */ 18341049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 1835a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclarkbool SkTSect<TCurve, OppCurve>::trim(SkTSpan<TCurve, OppCurve>* span, 18361049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSect<OppCurve, TCurve>* opp) { 1837a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(!span->initBounds(fCurve)); 18381049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpanBounded<OppCurve, TCurve>* testBounded = span->fBounded; 183954359294a7c9dc54802d512a5d891a35c1663392caryclark while (testBounded) { 18401049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* test = testBounded->fBounded; 18411049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpanBounded<OppCurve, TCurve>* next = testBounded->fNext; 184254359294a7c9dc54802d512a5d891a35c1663392caryclark int oppSects, sects = this->intersects(span, opp, test, &oppSects); 184354359294a7c9dc54802d512a5d891a35c1663392caryclark if (sects >= 1) { 184454359294a7c9dc54802d512a5d891a35c1663392caryclark if (oppSects == 2) { 184554359294a7c9dc54802d512a5d891a35c1663392caryclark test->initBounds(opp->fCurve); 184654359294a7c9dc54802d512a5d891a35c1663392caryclark opp->removeAllBut(span, test, this); 184754359294a7c9dc54802d512a5d891a35c1663392caryclark } 184854359294a7c9dc54802d512a5d891a35c1663392caryclark if (sects == 2) { 184954359294a7c9dc54802d512a5d891a35c1663392caryclark span->initBounds(fCurve); 185054359294a7c9dc54802d512a5d891a35c1663392caryclark this->removeAllBut(test, span, opp); 1851a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark return true; 185254359294a7c9dc54802d512a5d891a35c1663392caryclark } 185345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } else { 185454359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->removeBounded(test)) { 185554359294a7c9dc54802d512a5d891a35c1663392caryclark this->removeSpan(span); 185654359294a7c9dc54802d512a5d891a35c1663392caryclark } 185754359294a7c9dc54802d512a5d891a35c1663392caryclark if (test->removeBounded(span)) { 185854359294a7c9dc54802d512a5d891a35c1663392caryclark opp->removeSpan(test); 185954359294a7c9dc54802d512a5d891a35c1663392caryclark } 186045fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 186154359294a7c9dc54802d512a5d891a35c1663392caryclark testBounded = next; 186245fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 1863a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark return true; 186445fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 186545fa447460f70ec21d22cf4e1531490acfd3c578caryclark 18661049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 18671049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::unlinkSpan(SkTSpan<TCurve, OppCurve>* span) { 18681049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* prev = span->fPrev; 18691049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* next = span->fNext; 187054359294a7c9dc54802d512a5d891a35c1663392caryclark if (prev) { 187154359294a7c9dc54802d512a5d891a35c1663392caryclark prev->fNext = next; 187254359294a7c9dc54802d512a5d891a35c1663392caryclark if (next) { 187354359294a7c9dc54802d512a5d891a35c1663392caryclark next->fPrev = prev; 1874643ede69216c073c2dd497c382577dc9fde36b3ecaryclark next->validate(); 187554359294a7c9dc54802d512a5d891a35c1663392caryclark } 187654359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 187754359294a7c9dc54802d512a5d891a35c1663392caryclark fHead = next; 187854359294a7c9dc54802d512a5d891a35c1663392caryclark if (next) { 187996fcdcc219d2a0d3579719b84b28bede76efba64halcanary next->fPrev = nullptr; 188054359294a7c9dc54802d512a5d891a35c1663392caryclark } 188154359294a7c9dc54802d512a5d891a35c1663392caryclark } 188254359294a7c9dc54802d512a5d891a35c1663392caryclark} 188354359294a7c9dc54802d512a5d891a35c1663392caryclark 18841049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 18851049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkbool SkTSect<TCurve, OppCurve>::updateBounded(SkTSpan<TCurve, OppCurve>* first, 18861049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* last, SkTSpan<OppCurve, TCurve>* oppFirst) { 18871049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* test = first; 18881049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<TCurve, OppCurve>* final = last->next(); 188954359294a7c9dc54802d512a5d891a35c1663392caryclark bool deleteSpan = false; 189054359294a7c9dc54802d512a5d891a35c1663392caryclark do { 189154359294a7c9dc54802d512a5d891a35c1663392caryclark deleteSpan |= test->removeAllBounded(); 1892e25a4f6cbeaccfdc34cf031103f0fbc3e53a3ee5caryclark } while ((test = test->fNext) != final && test); 189396fcdcc219d2a0d3579719b84b28bede76efba64halcanary first->fBounded = nullptr; 189454359294a7c9dc54802d512a5d891a35c1663392caryclark first->addBounded(oppFirst, &fHeap); 189554359294a7c9dc54802d512a5d891a35c1663392caryclark // cannot call validate until remove span range is called 189654359294a7c9dc54802d512a5d891a35c1663392caryclark return deleteSpan; 189754359294a7c9dc54802d512a5d891a35c1663392caryclark} 189854359294a7c9dc54802d512a5d891a35c1663392caryclark 189954359294a7c9dc54802d512a5d891a35c1663392caryclark 19001049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 19011049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::validate() const { 1902643ede69216c073c2dd497c382577dc9fde36b3ecaryclark#if DEBUG_VALIDATE 190345fa447460f70ec21d22cf4e1531490acfd3c578caryclark int count = 0; 1904643ede69216c073c2dd497c382577dc9fde36b3ecaryclark double last = 0; 190545fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (fHead) { 19061049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<TCurve, OppCurve>* span = fHead; 190745fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkASSERT(!span->fPrev); 1908643ede69216c073c2dd497c382577dc9fde36b3ecaryclark const SkTSpan<TCurve, OppCurve>* next; 190945fa447460f70ec21d22cf4e1531490acfd3c578caryclark do { 191045fa447460f70ec21d22cf4e1531490acfd3c578caryclark span->validate(); 191145fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkASSERT(span->fStartT >= last); 1912643ede69216c073c2dd497c382577dc9fde36b3ecaryclark last = span->fEndT; 191345fa447460f70ec21d22cf4e1531490acfd3c578caryclark ++count; 1914643ede69216c073c2dd497c382577dc9fde36b3ecaryclark next = span->fNext; 1915643ede69216c073c2dd497c382577dc9fde36b3ecaryclark SkASSERT(next != span); 1916643ede69216c073c2dd497c382577dc9fde36b3ecaryclark } while ((span = next) != nullptr); 191745fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 191845fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkASSERT(count == fActiveCount); 1919643ede69216c073c2dd497c382577dc9fde36b3ecaryclark#endif 1920643ede69216c073c2dd497c382577dc9fde36b3ecaryclark#if DEBUG_T_SECT 192145fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkASSERT(fActiveCount <= fDebugAllocatedCount); 192245fa447460f70ec21d22cf4e1531490acfd3c578caryclark int deletedCount = 0; 19231049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<TCurve, OppCurve>* deleted = fDeleted; 192445fa447460f70ec21d22cf4e1531490acfd3c578caryclark while (deleted) { 192545fa447460f70ec21d22cf4e1531490acfd3c578caryclark ++deletedCount; 192645fa447460f70ec21d22cf4e1531490acfd3c578caryclark deleted = deleted->fNext; 192745fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 19281049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<TCurve, OppCurve>* coincident = fCoincident; 192954359294a7c9dc54802d512a5d891a35c1663392caryclark while (coincident) { 193054359294a7c9dc54802d512a5d891a35c1663392caryclark ++deletedCount; 193154359294a7c9dc54802d512a5d891a35c1663392caryclark coincident = coincident->fNext; 193254359294a7c9dc54802d512a5d891a35c1663392caryclark } 193345fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkASSERT(fActiveCount + deletedCount == fDebugAllocatedCount); 193454359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 193545fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 193654359294a7c9dc54802d512a5d891a35c1663392caryclark 19371049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 19381049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::validateBounded() const { 1939643ede69216c073c2dd497c382577dc9fde36b3ecaryclark#if DEBUG_VALIDATE 194054359294a7c9dc54802d512a5d891a35c1663392caryclark if (!fHead) { 194154359294a7c9dc54802d512a5d891a35c1663392caryclark return; 194254359294a7c9dc54802d512a5d891a35c1663392caryclark } 19431049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<TCurve, OppCurve>* span = fHead; 194454359294a7c9dc54802d512a5d891a35c1663392caryclark do { 194554359294a7c9dc54802d512a5d891a35c1663392caryclark span->validateBounded(); 194696fcdcc219d2a0d3579719b84b28bede76efba64halcanary } while ((span = span->fNext) != nullptr); 194745fa447460f70ec21d22cf4e1531490acfd3c578caryclark#endif 194854359294a7c9dc54802d512a5d891a35c1663392caryclark} 194945fa447460f70ec21d22cf4e1531490acfd3c578caryclark 19501049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 19511049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkint SkTSect<TCurve, OppCurve>::EndsEqual(const SkTSect<TCurve, OppCurve>* sect1, 19521049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSect<OppCurve, TCurve>* sect2, SkIntersections* intersections) { 195345fa447460f70ec21d22cf4e1531490acfd3c578caryclark int zeroOneSet = 0; 195454359294a7c9dc54802d512a5d891a35c1663392caryclark if (sect1->fCurve[0] == sect2->fCurve[0]) { 195554359294a7c9dc54802d512a5d891a35c1663392caryclark zeroOneSet |= kZeroS1Set | kZeroS2Set; 195654359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->insert(0, 0, sect1->fCurve[0]); 195754359294a7c9dc54802d512a5d891a35c1663392caryclark } 19581049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (sect1->fCurve[0] == sect2->fCurve[OppCurve::kPointLast]) { 195954359294a7c9dc54802d512a5d891a35c1663392caryclark zeroOneSet |= kZeroS1Set | kOneS2Set; 196054359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->insert(0, 1, sect1->fCurve[0]); 196154359294a7c9dc54802d512a5d891a35c1663392caryclark } 196254359294a7c9dc54802d512a5d891a35c1663392caryclark if (sect1->fCurve[TCurve::kPointLast] == sect2->fCurve[0]) { 196354359294a7c9dc54802d512a5d891a35c1663392caryclark zeroOneSet |= kOneS1Set | kZeroS2Set; 196454359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->insert(1, 0, sect1->fCurve[TCurve::kPointLast]); 196554359294a7c9dc54802d512a5d891a35c1663392caryclark } 19661049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (sect1->fCurve[TCurve::kPointLast] == sect2->fCurve[OppCurve::kPointLast]) { 196754359294a7c9dc54802d512a5d891a35c1663392caryclark zeroOneSet |= kOneS1Set | kOneS2Set; 196854359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->insert(1, 1, sect1->fCurve[TCurve::kPointLast]); 196954359294a7c9dc54802d512a5d891a35c1663392caryclark } 197045fa447460f70ec21d22cf4e1531490acfd3c578caryclark // check for zero 197154359294a7c9dc54802d512a5d891a35c1663392caryclark if (!(zeroOneSet & (kZeroS1Set | kZeroS2Set)) 197254359294a7c9dc54802d512a5d891a35c1663392caryclark && sect1->fCurve[0].approximatelyEqual(sect2->fCurve[0])) { 197345fa447460f70ec21d22cf4e1531490acfd3c578caryclark zeroOneSet |= kZeroS1Set | kZeroS2Set; 197454359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->insertNear(0, 0, sect1->fCurve[0], sect2->fCurve[0]); 197554359294a7c9dc54802d512a5d891a35c1663392caryclark } 197654359294a7c9dc54802d512a5d891a35c1663392caryclark if (!(zeroOneSet & (kZeroS1Set | kOneS2Set)) 19771049f1246e7be4ccb68001361efceb8933e6f81ccaryclark && sect1->fCurve[0].approximatelyEqual(sect2->fCurve[OppCurve::kPointLast])) { 197845fa447460f70ec21d22cf4e1531490acfd3c578caryclark zeroOneSet |= kZeroS1Set | kOneS2Set; 19791049f1246e7be4ccb68001361efceb8933e6f81ccaryclark intersections->insertNear(0, 1, sect1->fCurve[0], sect2->fCurve[OppCurve::kPointLast]); 198054359294a7c9dc54802d512a5d891a35c1663392caryclark } 198145fa447460f70ec21d22cf4e1531490acfd3c578caryclark // check for one 198254359294a7c9dc54802d512a5d891a35c1663392caryclark if (!(zeroOneSet & (kOneS1Set | kZeroS2Set)) 198354359294a7c9dc54802d512a5d891a35c1663392caryclark && sect1->fCurve[TCurve::kPointLast].approximatelyEqual(sect2->fCurve[0])) { 198445fa447460f70ec21d22cf4e1531490acfd3c578caryclark zeroOneSet |= kOneS1Set | kZeroS2Set; 198554359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->insertNear(1, 0, sect1->fCurve[TCurve::kPointLast], sect2->fCurve[0]); 198654359294a7c9dc54802d512a5d891a35c1663392caryclark } 198754359294a7c9dc54802d512a5d891a35c1663392caryclark if (!(zeroOneSet & (kOneS1Set | kOneS2Set)) 198854359294a7c9dc54802d512a5d891a35c1663392caryclark && sect1->fCurve[TCurve::kPointLast].approximatelyEqual(sect2->fCurve[ 19891049f1246e7be4ccb68001361efceb8933e6f81ccaryclark OppCurve::kPointLast])) { 199045fa447460f70ec21d22cf4e1531490acfd3c578caryclark zeroOneSet |= kOneS1Set | kOneS2Set; 199154359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->insertNear(1, 1, sect1->fCurve[TCurve::kPointLast], 19921049f1246e7be4ccb68001361efceb8933e6f81ccaryclark sect2->fCurve[OppCurve::kPointLast]); 199345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 199445fa447460f70ec21d22cf4e1531490acfd3c578caryclark return zeroOneSet; 199545fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 199645fa447460f70ec21d22cf4e1531490acfd3c578caryclark 19971049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 199845fa447460f70ec21d22cf4e1531490acfd3c578caryclarkstruct SkClosestRecord { 199954359294a7c9dc54802d512a5d891a35c1663392caryclark bool operator<(const SkClosestRecord& rh) const { 200054359294a7c9dc54802d512a5d891a35c1663392caryclark return fClosest < rh.fClosest; 200154359294a7c9dc54802d512a5d891a35c1663392caryclark } 200254359294a7c9dc54802d512a5d891a35c1663392caryclark 200345fa447460f70ec21d22cf4e1531490acfd3c578caryclark void addIntersection(SkIntersections* intersections) const { 200445fa447460f70ec21d22cf4e1531490acfd3c578caryclark double r1t = fC1Index ? fC1Span->endT() : fC1Span->startT(); 200545fa447460f70ec21d22cf4e1531490acfd3c578caryclark double r2t = fC2Index ? fC2Span->endT() : fC2Span->startT(); 200645fa447460f70ec21d22cf4e1531490acfd3c578caryclark intersections->insert(r1t, r2t, fC1Span->part()[fC1Index]); 200745fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 200845fa447460f70ec21d22cf4e1531490acfd3c578caryclark 20091049f1246e7be4ccb68001361efceb8933e6f81ccaryclark void findEnd(const SkTSpan<TCurve, OppCurve>* span1, const SkTSpan<OppCurve, TCurve>* span2, 201045fa447460f70ec21d22cf4e1531490acfd3c578caryclark int c1Index, int c2Index) { 201145fa447460f70ec21d22cf4e1531490acfd3c578caryclark const TCurve& c1 = span1->part(); 20121049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const OppCurve& c2 = span2->part(); 201345fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (!c1[c1Index].approximatelyEqual(c2[c2Index])) { 201445fa447460f70ec21d22cf4e1531490acfd3c578caryclark return; 201545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 201645fa447460f70ec21d22cf4e1531490acfd3c578caryclark double dist = c1[c1Index].distanceSquared(c2[c2Index]); 201745fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (fClosest < dist) { 201845fa447460f70ec21d22cf4e1531490acfd3c578caryclark return; 201945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 202045fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC1Span = span1; 202145fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC2Span = span2; 202245fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC1StartT = span1->startT(); 202345fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC1EndT = span1->endT(); 202445fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC2StartT = span2->startT(); 202545fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC2EndT = span2->endT(); 202645fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC1Index = c1Index; 202745fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC2Index = c2Index; 202845fa447460f70ec21d22cf4e1531490acfd3c578caryclark fClosest = dist; 202945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 203045fa447460f70ec21d22cf4e1531490acfd3c578caryclark 2031cdeff81bdb2e5cde422b6850634c5d3977fcbae9caryclark bool matesWith(const SkClosestRecord& mate SkDEBUGPARAMS(SkIntersections* i)) const { 203267116384368195913ec014972b4fc38de2087fb8Cary Clark SkOPOBJASSERT(i, fC1Span == mate.fC1Span || fC1Span->endT() <= mate.fC1Span->startT() 203345fa447460f70ec21d22cf4e1531490acfd3c578caryclark || mate.fC1Span->endT() <= fC1Span->startT()); 2034cdeff81bdb2e5cde422b6850634c5d3977fcbae9caryclark SkOPOBJASSERT(i, fC2Span == mate.fC2Span || fC2Span->endT() <= mate.fC2Span->startT() 203545fa447460f70ec21d22cf4e1531490acfd3c578caryclark || mate.fC2Span->endT() <= fC2Span->startT()); 203645fa447460f70ec21d22cf4e1531490acfd3c578caryclark return fC1Span == mate.fC1Span || fC1Span->endT() == mate.fC1Span->startT() 203745fa447460f70ec21d22cf4e1531490acfd3c578caryclark || fC1Span->startT() == mate.fC1Span->endT() 203845fa447460f70ec21d22cf4e1531490acfd3c578caryclark || fC2Span == mate.fC2Span 203945fa447460f70ec21d22cf4e1531490acfd3c578caryclark || fC2Span->endT() == mate.fC2Span->startT() 204045fa447460f70ec21d22cf4e1531490acfd3c578caryclark || fC2Span->startT() == mate.fC2Span->endT(); 204145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 204245fa447460f70ec21d22cf4e1531490acfd3c578caryclark 204345fa447460f70ec21d22cf4e1531490acfd3c578caryclark void merge(const SkClosestRecord& mate) { 204445fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC1Span = mate.fC1Span; 204545fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC2Span = mate.fC2Span; 204645fa447460f70ec21d22cf4e1531490acfd3c578caryclark fClosest = mate.fClosest; 204745fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC1Index = mate.fC1Index; 204845fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC2Index = mate.fC2Index; 204945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 205055888e44171ffd48b591d19256884a969fe4da17caryclark 205145fa447460f70ec21d22cf4e1531490acfd3c578caryclark void reset() { 205245fa447460f70ec21d22cf4e1531490acfd3c578caryclark fClosest = FLT_MAX; 205396fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkDEBUGCODE(fC1Span = nullptr); 205496fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkDEBUGCODE(fC2Span = nullptr); 205545fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkDEBUGCODE(fC1Index = fC2Index = -1); 205645fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 205745fa447460f70ec21d22cf4e1531490acfd3c578caryclark 205845fa447460f70ec21d22cf4e1531490acfd3c578caryclark void update(const SkClosestRecord& mate) { 205945fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC1StartT = SkTMin(fC1StartT, mate.fC1StartT); 206045fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC1EndT = SkTMax(fC1EndT, mate.fC1EndT); 206145fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC2StartT = SkTMin(fC2StartT, mate.fC2StartT); 206245fa447460f70ec21d22cf4e1531490acfd3c578caryclark fC2EndT = SkTMax(fC2EndT, mate.fC2EndT); 206345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 206445fa447460f70ec21d22cf4e1531490acfd3c578caryclark 20651049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<TCurve, OppCurve>* fC1Span; 20661049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<OppCurve, TCurve>* fC2Span; 206745fa447460f70ec21d22cf4e1531490acfd3c578caryclark double fC1StartT; 206845fa447460f70ec21d22cf4e1531490acfd3c578caryclark double fC1EndT; 206945fa447460f70ec21d22cf4e1531490acfd3c578caryclark double fC2StartT; 207045fa447460f70ec21d22cf4e1531490acfd3c578caryclark double fC2EndT; 207145fa447460f70ec21d22cf4e1531490acfd3c578caryclark double fClosest; 207245fa447460f70ec21d22cf4e1531490acfd3c578caryclark int fC1Index; 207345fa447460f70ec21d22cf4e1531490acfd3c578caryclark int fC2Index; 207445fa447460f70ec21d22cf4e1531490acfd3c578caryclark}; 207545fa447460f70ec21d22cf4e1531490acfd3c578caryclark 20761049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 207745fa447460f70ec21d22cf4e1531490acfd3c578caryclarkstruct SkClosestSect { 207845fa447460f70ec21d22cf4e1531490acfd3c578caryclark SkClosestSect() 207945fa447460f70ec21d22cf4e1531490acfd3c578caryclark : fUsed(0) { 208045fa447460f70ec21d22cf4e1531490acfd3c578caryclark fClosest.push_back().reset(); 208145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 208245fa447460f70ec21d22cf4e1531490acfd3c578caryclark 2083cdeff81bdb2e5cde422b6850634c5d3977fcbae9caryclark bool find(const SkTSpan<TCurve, OppCurve>* span1, const SkTSpan<OppCurve, TCurve>* span2 2084cdeff81bdb2e5cde422b6850634c5d3977fcbae9caryclark SkDEBUGPARAMS(SkIntersections* i)) { 20851049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkClosestRecord<TCurve, OppCurve>* record = &fClosest[fUsed]; 208645fa447460f70ec21d22cf4e1531490acfd3c578caryclark record->findEnd(span1, span2, 0, 0); 20871049f1246e7be4ccb68001361efceb8933e6f81ccaryclark record->findEnd(span1, span2, 0, OppCurve::kPointLast); 208845fa447460f70ec21d22cf4e1531490acfd3c578caryclark record->findEnd(span1, span2, TCurve::kPointLast, 0); 20891049f1246e7be4ccb68001361efceb8933e6f81ccaryclark record->findEnd(span1, span2, TCurve::kPointLast, OppCurve::kPointLast); 209045fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (record->fClosest == FLT_MAX) { 209154359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 209245fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 209345fa447460f70ec21d22cf4e1531490acfd3c578caryclark for (int index = 0; index < fUsed; ++index) { 20941049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkClosestRecord<TCurve, OppCurve>* test = &fClosest[index]; 2095cdeff81bdb2e5cde422b6850634c5d3977fcbae9caryclark if (test->matesWith(*record SkDEBUGPARAMS(i))) { 209645fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (test->fClosest > record->fClosest) { 209745fa447460f70ec21d22cf4e1531490acfd3c578caryclark test->merge(*record); 209845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 209945fa447460f70ec21d22cf4e1531490acfd3c578caryclark test->update(*record); 210045fa447460f70ec21d22cf4e1531490acfd3c578caryclark record->reset(); 210154359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 210245fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 210345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 210445fa447460f70ec21d22cf4e1531490acfd3c578caryclark ++fUsed; 210545fa447460f70ec21d22cf4e1531490acfd3c578caryclark fClosest.push_back().reset(); 210654359294a7c9dc54802d512a5d891a35c1663392caryclark return true; 210745fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 210845fa447460f70ec21d22cf4e1531490acfd3c578caryclark 210945fa447460f70ec21d22cf4e1531490acfd3c578caryclark void finish(SkIntersections* intersections) const { 21101049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkSTArray<TCurve::kMaxIntersections * 3, 21111049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkClosestRecord<TCurve, OppCurve>*, true> closestPtrs; 211254359294a7c9dc54802d512a5d891a35c1663392caryclark for (int index = 0; index < fUsed; ++index) { 211354359294a7c9dc54802d512a5d891a35c1663392caryclark closestPtrs.push_back(&fClosest[index]); 211454359294a7c9dc54802d512a5d891a35c1663392caryclark } 21151049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTQSort<const SkClosestRecord<TCurve, OppCurve> >(closestPtrs.begin(), closestPtrs.end() 21161049f1246e7be4ccb68001361efceb8933e6f81ccaryclark - 1); 211745fa447460f70ec21d22cf4e1531490acfd3c578caryclark for (int index = 0; index < fUsed; ++index) { 21181049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkClosestRecord<TCurve, OppCurve>* test = closestPtrs[index]; 211954359294a7c9dc54802d512a5d891a35c1663392caryclark test->addIntersection(intersections); 212045fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 212145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 212245fa447460f70ec21d22cf4e1531490acfd3c578caryclark 212354359294a7c9dc54802d512a5d891a35c1663392caryclark // this is oversized so that an extra records can merge into final one 21241049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkSTArray<TCurve::kMaxIntersections * 2, SkClosestRecord<TCurve, OppCurve>, true> fClosest; 212545fa447460f70ec21d22cf4e1531490acfd3c578caryclark int fUsed; 212645fa447460f70ec21d22cf4e1531490acfd3c578caryclark}; 212745fa447460f70ec21d22cf4e1531490acfd3c578caryclark 212845fa447460f70ec21d22cf4e1531490acfd3c578caryclark// returns true if the rect is too small to consider 21291049f1246e7be4ccb68001361efceb8933e6f81ccaryclarktemplate<typename TCurve, typename OppCurve> 21301049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkTSect<TCurve, OppCurve>::BinarySearch(SkTSect<TCurve, OppCurve>* sect1, 21311049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSect<OppCurve, TCurve>* sect2, SkIntersections* intersections) { 213254359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_T_SECT_DUMP > 1 213354359294a7c9dc54802d512a5d891a35c1663392caryclark gDumpTSectNum = 0; 213454359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 21351049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(sect1->fOppSect = sect2); 21361049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(sect2->fOppSect = sect1); 213745fa447460f70ec21d22cf4e1531490acfd3c578caryclark intersections->reset(); 2138a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark intersections->setMax(TCurve::kMaxIntersections + 4); // give extra for slop 21391049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* span1 = sect1->fHead; 21401049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* span2 = sect2->fHead; 214154359294a7c9dc54802d512a5d891a35c1663392caryclark int oppSect, sect = sect1->intersects(span1, sect2, span2, &oppSect); 214254359294a7c9dc54802d512a5d891a35c1663392caryclark// SkASSERT(between(0, sect, 2)); 214354359294a7c9dc54802d512a5d891a35c1663392caryclark if (!sect) { 214445fa447460f70ec21d22cf4e1531490acfd3c578caryclark return; 214545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 214654359294a7c9dc54802d512a5d891a35c1663392caryclark if (sect == 2 && oppSect == 2) { 214745fa447460f70ec21d22cf4e1531490acfd3c578caryclark (void) EndsEqual(sect1, sect2, intersections); 214845fa447460f70ec21d22cf4e1531490acfd3c578caryclark return; 214945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 215054359294a7c9dc54802d512a5d891a35c1663392caryclark span1->addBounded(span2, §1->fHeap); 215154359294a7c9dc54802d512a5d891a35c1663392caryclark span2->addBounded(span1, §2->fHeap); 215226ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark const int kMaxCoinLoopCount = 8; 215326ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark int coinLoopCount = kMaxCoinLoopCount; 215426ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark double start1s SK_INIT_TO_AVOID_WARNING; 215526ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark double start1e SK_INIT_TO_AVOID_WARNING; 215645fa447460f70ec21d22cf4e1531490acfd3c578caryclark do { 215745fa447460f70ec21d22cf4e1531490acfd3c578caryclark // find the largest bounds 21581049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* largest1 = sect1->boundsMax(); 215945fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (!largest1) { 216045fa447460f70ec21d22cf4e1531490acfd3c578caryclark break; 216145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 21621049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* largest2 = sect2->boundsMax(); 216345fa447460f70ec21d22cf4e1531490acfd3c578caryclark // split it 21641049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (!largest2 || (largest1 && (largest1->fBoundsMax > largest2->fBoundsMax 21651049f1246e7be4ccb68001361efceb8933e6f81ccaryclark || (!largest1->fCollapsed && largest2->fCollapsed)))) { 21661049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (largest1->fCollapsed) { 21671049f1246e7be4ccb68001361efceb8933e6f81ccaryclark break; 21681049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 216934efb7039851d7796ba06aa58e5c5882ede503accaryclark sect1->resetRemovedEnds(); 217034efb7039851d7796ba06aa58e5c5882ede503accaryclark sect2->resetRemovedEnds(); 21711049f1246e7be4ccb68001361efceb8933e6f81ccaryclark // trim parts that don't intersect the opposite 21721049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* half1 = sect1->addOne(); 2173643ede69216c073c2dd497c382577dc9fde36b3ecaryclark SkDEBUGCODE(half1->debugSetGlobalState(sect1->globalState())); 21741049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (!half1->split(largest1, §1->fHeap)) { 21751049f1246e7be4ccb68001361efceb8933e6f81ccaryclark break; 21761049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 2177a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark if (!sect1->trim(largest1, sect2)) { 2178a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark SkOPOBJASSERT(intersections, 0); 2179a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark return; 2180a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark } 2181a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark if (!sect1->trim(half1, sect2)) { 2182a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark SkOPOBJASSERT(intersections, 0); 2183a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark return; 2184a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark } 21851049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } else { 21861049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (largest2->fCollapsed) { 21871049f1246e7be4ccb68001361efceb8933e6f81ccaryclark break; 21881049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 218934efb7039851d7796ba06aa58e5c5882ede503accaryclark sect1->resetRemovedEnds(); 219034efb7039851d7796ba06aa58e5c5882ede503accaryclark sect2->resetRemovedEnds(); 21911049f1246e7be4ccb68001361efceb8933e6f81ccaryclark // trim parts that don't intersect the opposite 21921049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* half2 = sect2->addOne(); 2193643ede69216c073c2dd497c382577dc9fde36b3ecaryclark SkDEBUGCODE(half2->debugSetGlobalState(sect2->globalState())); 21941049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (!half2->split(largest2, §2->fHeap)) { 21951049f1246e7be4ccb68001361efceb8933e6f81ccaryclark break; 21961049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 2197a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark if (!sect2->trim(largest2, sect1)) { 2198a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark SkOPOBJASSERT(intersections, 0); 2199a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark return; 2200a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark } 2201a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark if (!sect2->trim(half2, sect1)) { 2202a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark SkOPOBJASSERT(intersections, 0); 2203a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark return; 2204a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark } 220545fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 220654359294a7c9dc54802d512a5d891a35c1663392caryclark sect1->validate(); 220754359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->validate(); 220826ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark#if DEBUG_T_SECT_LOOP_COUNT 220926ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark intersections->debugBumpLoopCount(SkIntersections::kIterations_DebugLoop); 221026ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark#endif 221145fa447460f70ec21d22cf4e1531490acfd3c578caryclark // if there are 9 or more continuous spans on both sects, suspect coincidence 221245fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT 221345fa447460f70ec21d22cf4e1531490acfd3c578caryclark && sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) { 221426ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark if (coinLoopCount == kMaxCoinLoopCount) { 221526ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark start1s = sect1->fHead->fStartT; 221626ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark start1e = sect1->tail()->fEndT; 221726ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark } 2218ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark if (!sect1->coincidentCheck(sect2)) { 2219ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark return; 2220ef7cee4bbc7c4c1c21b00834de7119634a3c35c9caryclark } 222154359294a7c9dc54802d512a5d891a35c1663392caryclark sect1->validate(); 222254359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->validate(); 222326ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark#if DEBUG_T_SECT_LOOP_COUNT 222426ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark intersections->debugBumpLoopCount(SkIntersections::kCoinCheck_DebugLoop); 222526ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark#endif 2226ef784fb7f58c9c021172045a8e0b396c81fdc425caryclark if (!--coinLoopCount && sect1->fHead && sect2->fHead) { 222726ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark /* All known working cases resolve in two tries. Sadly, cubicConicTests[0] 222826ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark gets stuck in a loop. It adds an extension to allow a coincident end 222926ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark perpendicular to track its intersection in the opposite curve. However, 223026ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark the bounding box of the extension does not intersect the original curve, 223155888e44171ffd48b591d19256884a969fe4da17caryclark so the extension is discarded, only to be added again the next time around. */ 223226ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark sect1->coincidentForce(sect2, start1s, start1e); 223326ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark sect1->validate(); 223426ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark sect2->validate(); 223526ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark } 223645fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 223754359294a7c9dc54802d512a5d891a35c1663392caryclark if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT 223854359294a7c9dc54802d512a5d891a35c1663392caryclark && sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) { 223959ed482af72beec6812b28d833d8bdf80ba32df7Cary Clark if (!sect1->fHead) { 224059ed482af72beec6812b28d833d8bdf80ba32df7Cary Clark return; 224159ed482af72beec6812b28d833d8bdf80ba32df7Cary Clark } 224254359294a7c9dc54802d512a5d891a35c1663392caryclark sect1->computePerpendiculars(sect2, sect1->fHead, sect1->tail()); 224359ed482af72beec6812b28d833d8bdf80ba32df7Cary Clark if (!sect2->fHead) { 224459ed482af72beec6812b28d833d8bdf80ba32df7Cary Clark return; 224559ed482af72beec6812b28d833d8bdf80ba32df7Cary Clark } 224654359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->computePerpendiculars(sect1, sect2->fHead, sect2->tail()); 224754359294a7c9dc54802d512a5d891a35c1663392caryclark sect1->removeByPerpendicular(sect2); 224854359294a7c9dc54802d512a5d891a35c1663392caryclark sect1->validate(); 224954359294a7c9dc54802d512a5d891a35c1663392caryclark sect2->validate(); 225026ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark#if DEBUG_T_SECT_LOOP_COUNT 225126ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark intersections->debugBumpLoopCount(SkIntersections::kComputePerp_DebugLoop); 225226ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark#endif 22531049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (sect1->collapsed() > TCurve::kMaxIntersections) { 22541049f1246e7be4ccb68001361efceb8933e6f81ccaryclark break; 22551049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 225654359294a7c9dc54802d512a5d891a35c1663392caryclark } 225754359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_T_SECT_DUMP 225854359294a7c9dc54802d512a5d891a35c1663392caryclark sect1->dumpBoth(sect2); 225945fa447460f70ec21d22cf4e1531490acfd3c578caryclark#endif 226045fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (!sect1->fHead || !sect2->fHead) { 226154359294a7c9dc54802d512a5d891a35c1663392caryclark break; 226245fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 226345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } while (true); 22641049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* coincident = sect1->fCoincident; 226554359294a7c9dc54802d512a5d891a35c1663392caryclark if (coincident) { 226654359294a7c9dc54802d512a5d891a35c1663392caryclark // if there is more than one coincident span, check loosely to see if they should be joined 226754359294a7c9dc54802d512a5d891a35c1663392caryclark if (coincident->fNext) { 226854359294a7c9dc54802d512a5d891a35c1663392caryclark sect1->mergeCoincidence(sect2); 226954359294a7c9dc54802d512a5d891a35c1663392caryclark coincident = sect1->fCoincident; 227054359294a7c9dc54802d512a5d891a35c1663392caryclark } 227154359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(sect2->fCoincident); // courtesy check : coincidence only looks at sect 1 227245fa447460f70ec21d22cf4e1531490acfd3c578caryclark do { 2273221a4bb55b51a6ba3882811990581d4bdb6bd539caryclark if (!coincident) { 2274221a4bb55b51a6ba3882811990581d4bdb6bd539caryclark return; 2275221a4bb55b51a6ba3882811990581d4bdb6bd539caryclark } 22766c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark if (!coincident->fCoinStart.isMatch()) { 2277ef784fb7f58c9c021172045a8e0b396c81fdc425caryclark continue; 2278ef784fb7f58c9c021172045a8e0b396c81fdc425caryclark } 22796c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark if (!coincident->fCoinEnd.isMatch()) { 2280ef784fb7f58c9c021172045a8e0b396c81fdc425caryclark continue; 2281ef784fb7f58c9c021172045a8e0b396c81fdc425caryclark } 228267116384368195913ec014972b4fc38de2087fb8Cary Clark double perpT = coincident->fCoinStart.perpT(); 228367116384368195913ec014972b4fc38de2087fb8Cary Clark if (perpT < 0) { 228467116384368195913ec014972b4fc38de2087fb8Cary Clark return; 228567116384368195913ec014972b4fc38de2087fb8Cary Clark } 228654359294a7c9dc54802d512a5d891a35c1663392caryclark int index = intersections->insertCoincident(coincident->fStartT, 228767116384368195913ec014972b4fc38de2087fb8Cary Clark perpT, coincident->fPart[0]); 228854359294a7c9dc54802d512a5d891a35c1663392caryclark if ((intersections->insertCoincident(coincident->fEndT, 228954359294a7c9dc54802d512a5d891a35c1663392caryclark coincident->fCoinEnd.perpT(), 229054359294a7c9dc54802d512a5d891a35c1663392caryclark coincident->fPart[TCurve::kPointLast]) < 0) && index >= 0) { 229145fa447460f70ec21d22cf4e1531490acfd3c578caryclark intersections->clearCoincidence(index); 229245fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 229354359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((coincident = coincident->fNext)); 229454359294a7c9dc54802d512a5d891a35c1663392caryclark } 22951049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int zeroOneSet = EndsEqual(sect1, sect2, intersections); 229634efb7039851d7796ba06aa58e5c5882ede503accaryclark// if (!sect1->fHead || !sect2->fHead) { 22976c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark // if the final iteration contains an end (0 or 1), 22986c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark if (sect1->fRemovedStartT && !(zeroOneSet & kZeroS1Set)) { 22996c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark SkTCoincident<TCurve, OppCurve> perp; // intersect perpendicular with opposite curve 2300a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark perp.setPerp(sect1->fCurve, 0, sect1->fCurve[0], sect2->fCurve); 23016c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark if (perp.isMatch()) { 23026c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark intersections->insert(0, perp.perpT(), perp.perpPt()); 23036c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark } 23046c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark } 23056c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark if (sect1->fRemovedEndT && !(zeroOneSet & kOneS1Set)) { 23066c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark SkTCoincident<TCurve, OppCurve> perp; 2307a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark perp.setPerp(sect1->fCurve, 1, sect1->fCurve[TCurve::kPointLast], sect2->fCurve); 23086c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark if (perp.isMatch()) { 23096c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark intersections->insert(1, perp.perpT(), perp.perpPt()); 23106c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark } 23116c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark } 23126c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark if (sect2->fRemovedStartT && !(zeroOneSet & kZeroS2Set)) { 23136c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark SkTCoincident<OppCurve, TCurve> perp; 2314a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark perp.setPerp(sect2->fCurve, 0, sect2->fCurve[0], sect1->fCurve); 23156c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark if (perp.isMatch()) { 23166c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark intersections->insert(perp.perpT(), 0, perp.perpPt()); 23176c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark } 23186c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark } 23196c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark if (sect2->fRemovedEndT && !(zeroOneSet & kOneS2Set)) { 23206c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark SkTCoincident<OppCurve, TCurve> perp; 2321a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark perp.setPerp(sect2->fCurve, 1, sect2->fCurve[OppCurve::kPointLast], sect1->fCurve); 23226c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark if (perp.isMatch()) { 23236c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark intersections->insert(perp.perpT(), 1, perp.perpPt()); 23246c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark } 23256c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark } 232634efb7039851d7796ba06aa58e5c5882ede503accaryclark// } 232734efb7039851d7796ba06aa58e5c5882ede503accaryclark if (!sect1->fHead || !sect2->fHead) { 232854359294a7c9dc54802d512a5d891a35c1663392caryclark return; 232945fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 233045fa447460f70ec21d22cf4e1531490acfd3c578caryclark sect1->recoverCollapsed(); 233145fa447460f70ec21d22cf4e1531490acfd3c578caryclark sect2->recoverCollapsed(); 23321049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<TCurve, OppCurve>* result1 = sect1->fHead; 233345fa447460f70ec21d22cf4e1531490acfd3c578caryclark // check heads and tails for zero and ones and insert them if we haven't already done so 23341049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<TCurve, OppCurve>* head1 = result1; 233545fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (!(zeroOneSet & kZeroS1Set) && approximately_less_than_zero(head1->fStartT)) { 233645fa447460f70ec21d22cf4e1531490acfd3c578caryclark const SkDPoint& start1 = sect1->fCurve[0]; 233754359294a7c9dc54802d512a5d891a35c1663392caryclark if (head1->isBounded()) { 233854359294a7c9dc54802d512a5d891a35c1663392caryclark double t = head1->closestBoundedT(start1); 233954359294a7c9dc54802d512a5d891a35c1663392caryclark if (sect2->fCurve.ptAtT(t).approximatelyEqual(start1)) { 234054359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->insert(0, t, start1); 234154359294a7c9dc54802d512a5d891a35c1663392caryclark } 234245fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 234345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 23441049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<OppCurve, TCurve>* head2 = sect2->fHead; 234545fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (!(zeroOneSet & kZeroS2Set) && approximately_less_than_zero(head2->fStartT)) { 234645fa447460f70ec21d22cf4e1531490acfd3c578caryclark const SkDPoint& start2 = sect2->fCurve[0]; 234754359294a7c9dc54802d512a5d891a35c1663392caryclark if (head2->isBounded()) { 234854359294a7c9dc54802d512a5d891a35c1663392caryclark double t = head2->closestBoundedT(start2); 234954359294a7c9dc54802d512a5d891a35c1663392caryclark if (sect1->fCurve.ptAtT(t).approximatelyEqual(start2)) { 235054359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->insert(t, 0, start2); 235154359294a7c9dc54802d512a5d891a35c1663392caryclark } 235245fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 235345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 23541049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<TCurve, OppCurve>* tail1 = sect1->tail(); 235545fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (!(zeroOneSet & kOneS1Set) && approximately_greater_than_one(tail1->fEndT)) { 235645fa447460f70ec21d22cf4e1531490acfd3c578caryclark const SkDPoint& end1 = sect1->fCurve[TCurve::kPointLast]; 235754359294a7c9dc54802d512a5d891a35c1663392caryclark if (tail1->isBounded()) { 235854359294a7c9dc54802d512a5d891a35c1663392caryclark double t = tail1->closestBoundedT(end1); 235954359294a7c9dc54802d512a5d891a35c1663392caryclark if (sect2->fCurve.ptAtT(t).approximatelyEqual(end1)) { 236054359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->insert(1, t, end1); 236154359294a7c9dc54802d512a5d891a35c1663392caryclark } 236245fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 236345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 23641049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkTSpan<OppCurve, TCurve>* tail2 = sect2->tail(); 236545fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (!(zeroOneSet & kOneS2Set) && approximately_greater_than_one(tail2->fEndT)) { 23661049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkDPoint& end2 = sect2->fCurve[OppCurve::kPointLast]; 236754359294a7c9dc54802d512a5d891a35c1663392caryclark if (tail2->isBounded()) { 236854359294a7c9dc54802d512a5d891a35c1663392caryclark double t = tail2->closestBoundedT(end2); 236954359294a7c9dc54802d512a5d891a35c1663392caryclark if (sect1->fCurve.ptAtT(t).approximatelyEqual(end2)) { 237054359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->insert(t, 1, end2); 237154359294a7c9dc54802d512a5d891a35c1663392caryclark } 237245fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 237345fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 23741049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkClosestSect<TCurve, OppCurve> closest; 237545fa447460f70ec21d22cf4e1531490acfd3c578caryclark do { 23766c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark while (result1 && result1->fCoinStart.isMatch() && result1->fCoinEnd.isMatch()) { 237745fa447460f70ec21d22cf4e1531490acfd3c578caryclark result1 = result1->fNext; 237845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 237945fa447460f70ec21d22cf4e1531490acfd3c578caryclark if (!result1) { 238045fa447460f70ec21d22cf4e1531490acfd3c578caryclark break; 238145fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 23821049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTSpan<OppCurve, TCurve>* result2 = sect2->fHead; 238354359294a7c9dc54802d512a5d891a35c1663392caryclark bool found = false; 238445fa447460f70ec21d22cf4e1531490acfd3c578caryclark while (result2) { 2385cdeff81bdb2e5cde422b6850634c5d3977fcbae9caryclark found |= closest.find(result1, result2 SkDEBUGPARAMS(intersections)); 238645fa447460f70ec21d22cf4e1531490acfd3c578caryclark result2 = result2->fNext; 238745fa447460f70ec21d22cf4e1531490acfd3c578caryclark } 238845fa447460f70ec21d22cf4e1531490acfd3c578caryclark } while ((result1 = result1->fNext)); 238945fa447460f70ec21d22cf4e1531490acfd3c578caryclark closest.finish(intersections); 239054359294a7c9dc54802d512a5d891a35c1663392caryclark // if there is more than one intersection and it isn't already coincident, check 239154359294a7c9dc54802d512a5d891a35c1663392caryclark int last = intersections->used() - 1; 239254359294a7c9dc54802d512a5d891a35c1663392caryclark for (int index = 0; index < last; ) { 239354359294a7c9dc54802d512a5d891a35c1663392caryclark if (intersections->isCoincident(index) && intersections->isCoincident(index + 1)) { 239454359294a7c9dc54802d512a5d891a35c1663392caryclark ++index; 239554359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 239654359294a7c9dc54802d512a5d891a35c1663392caryclark } 239754359294a7c9dc54802d512a5d891a35c1663392caryclark double midT = ((*intersections)[0][index] + (*intersections)[0][index + 1]) / 2; 239854359294a7c9dc54802d512a5d891a35c1663392caryclark SkDPoint midPt = sect1->fCurve.ptAtT(midT); 239954359294a7c9dc54802d512a5d891a35c1663392caryclark // intersect perpendicular with opposite curve 24001049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkTCoincident<TCurve, OppCurve> perp; 240154359294a7c9dc54802d512a5d891a35c1663392caryclark perp.setPerp(sect1->fCurve, midT, midPt, sect2->fCurve); 24026c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark if (!perp.isMatch()) { 240354359294a7c9dc54802d512a5d891a35c1663392caryclark ++index; 240454359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 240554359294a7c9dc54802d512a5d891a35c1663392caryclark } 240654359294a7c9dc54802d512a5d891a35c1663392caryclark if (intersections->isCoincident(index)) { 240754359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->removeOne(index); 240854359294a7c9dc54802d512a5d891a35c1663392caryclark --last; 240954359294a7c9dc54802d512a5d891a35c1663392caryclark } else if (intersections->isCoincident(index + 1)) { 241054359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->removeOne(index + 1); 241154359294a7c9dc54802d512a5d891a35c1663392caryclark --last; 241254359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 241354359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->setCoincident(index++); 241454359294a7c9dc54802d512a5d891a35c1663392caryclark } 241554359294a7c9dc54802d512a5d891a35c1663392caryclark intersections->setCoincident(index); 241654359294a7c9dc54802d512a5d891a35c1663392caryclark } 2417a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark SkOPOBJASSERT(intersections, intersections->used() <= TCurve::kMaxIntersections); 241845fa447460f70ec21d22cf4e1531490acfd3c578caryclark} 241912670eb63b743283cf6f0e6e568c1713756e4006deanm 242012670eb63b743283cf6f0e6e568c1713756e4006deanm#endif 2421