107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* 207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Copyright 2012 Google Inc. 307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * 407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Use of this source code is governed by a BSD-style license that can be 507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * found in the LICENSE file. 607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com */ 707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#ifndef SkOpSpan_DEFINED 807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#define SkOpSpan_DEFINED 907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1054359294a7c9dc54802d512a5d891a35c1663392caryclark#include "SkPathOpsDebug.h" 1107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPoint.h" 1207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1354359294a7c9dc54802d512a5d891a35c1663392caryclarkclass SkChunkAlloc; 1454359294a7c9dc54802d512a5d891a35c1663392caryclarkstruct SkOpAngle; 1554359294a7c9dc54802d512a5d891a35c1663392caryclarkclass SkOpContour; 1654359294a7c9dc54802d512a5d891a35c1663392caryclarkclass SkOpGlobalState; 1707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comclass SkOpSegment; 1854359294a7c9dc54802d512a5d891a35c1663392caryclarkclass SkOpSpanBase; 1954359294a7c9dc54802d512a5d891a35c1663392caryclarkclass SkOpSpan; 2007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 2154359294a7c9dc54802d512a5d891a35c1663392caryclark// subset of op span used by terminal span (when t is equal to one) 2254359294a7c9dc54802d512a5d891a35c1663392caryclarkclass SkOpPtT { 2354359294a7c9dc54802d512a5d891a35c1663392caryclarkpublic: 2454359294a7c9dc54802d512a5d891a35c1663392caryclark enum { 2554359294a7c9dc54802d512a5d891a35c1663392caryclark kIsAlias = 1, 2654359294a7c9dc54802d512a5d891a35c1663392caryclark kIsDuplicate = 1 2754359294a7c9dc54802d512a5d891a35c1663392caryclark }; 2854359294a7c9dc54802d512a5d891a35c1663392caryclark 2954359294a7c9dc54802d512a5d891a35c1663392caryclark void addOpp(SkOpPtT* opp) { 3054359294a7c9dc54802d512a5d891a35c1663392caryclark // find the fOpp ptr to opp 3154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* oppPrev = opp->fNext; 3254359294a7c9dc54802d512a5d891a35c1663392caryclark if (oppPrev == this) { 3354359294a7c9dc54802d512a5d891a35c1663392caryclark return; 3454359294a7c9dc54802d512a5d891a35c1663392caryclark } 3554359294a7c9dc54802d512a5d891a35c1663392caryclark while (oppPrev->fNext != opp) { 3654359294a7c9dc54802d512a5d891a35c1663392caryclark oppPrev = oppPrev->fNext; 3754359294a7c9dc54802d512a5d891a35c1663392caryclark if (oppPrev == this) { 3854359294a7c9dc54802d512a5d891a35c1663392caryclark return; 3954359294a7c9dc54802d512a5d891a35c1663392caryclark } 4054359294a7c9dc54802d512a5d891a35c1663392caryclark } 4154359294a7c9dc54802d512a5d891a35c1663392caryclark 4254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* oldNext = this->fNext; 4354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this != opp); 4454359294a7c9dc54802d512a5d891a35c1663392caryclark this->fNext = opp; 4554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(oppPrev != oldNext); 4654359294a7c9dc54802d512a5d891a35c1663392caryclark oppPrev->fNext = oldNext; 4754359294a7c9dc54802d512a5d891a35c1663392caryclark } 4854359294a7c9dc54802d512a5d891a35c1663392caryclark 4954359294a7c9dc54802d512a5d891a35c1663392caryclark bool alias() const; 5054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpContour* contour() const; 5154359294a7c9dc54802d512a5d891a35c1663392caryclark 5254359294a7c9dc54802d512a5d891a35c1663392caryclark int debugID() const { 531049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return SkDEBUGRELEASE(fID, -1); 5454359294a7c9dc54802d512a5d891a35c1663392caryclark } 5554359294a7c9dc54802d512a5d891a35c1663392caryclark 5654359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpAngle* debugAngle(int id) const; 5754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpContour* debugContour(int id); 5854359294a7c9dc54802d512a5d891a35c1663392caryclark int debugLoopLimit(bool report) const; 5954359294a7c9dc54802d512a5d891a35c1663392caryclark bool debugMatchID(int id) const; 6054359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpPtT* debugPtT(int id) const; 6154359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSegment* debugSegment(int id) const; 6254359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* debugSpan(int id) const; 6354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpGlobalState* globalState() const; 6454359294a7c9dc54802d512a5d891a35c1663392caryclark void debugValidate() const; 6554359294a7c9dc54802d512a5d891a35c1663392caryclark 6654359294a7c9dc54802d512a5d891a35c1663392caryclark bool deleted() const { 6754359294a7c9dc54802d512a5d891a35c1663392caryclark return fDeleted; 6854359294a7c9dc54802d512a5d891a35c1663392caryclark } 6954359294a7c9dc54802d512a5d891a35c1663392caryclark 7054359294a7c9dc54802d512a5d891a35c1663392caryclark bool duplicate() const { 7154359294a7c9dc54802d512a5d891a35c1663392caryclark return fDuplicatePt; 7254359294a7c9dc54802d512a5d891a35c1663392caryclark } 7354359294a7c9dc54802d512a5d891a35c1663392caryclark 7454359294a7c9dc54802d512a5d891a35c1663392caryclark void dump() const; // available to testing only 7554359294a7c9dc54802d512a5d891a35c1663392caryclark void dumpAll() const; 7654359294a7c9dc54802d512a5d891a35c1663392caryclark void dumpBase() const; 7754359294a7c9dc54802d512a5d891a35c1663392caryclark 7854359294a7c9dc54802d512a5d891a35c1663392caryclark void init(SkOpSpanBase* , double t, const SkPoint& , bool dup); 7954359294a7c9dc54802d512a5d891a35c1663392caryclark 8054359294a7c9dc54802d512a5d891a35c1663392caryclark void insert(SkOpPtT* span) { 8154359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(span != this); 8254359294a7c9dc54802d512a5d891a35c1663392caryclark span->fNext = fNext; 8354359294a7c9dc54802d512a5d891a35c1663392caryclark fNext = span; 8454359294a7c9dc54802d512a5d891a35c1663392caryclark } 8554359294a7c9dc54802d512a5d891a35c1663392caryclark 8654359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpPtT* next() const { 8754359294a7c9dc54802d512a5d891a35c1663392caryclark return fNext; 8854359294a7c9dc54802d512a5d891a35c1663392caryclark } 8954359294a7c9dc54802d512a5d891a35c1663392caryclark 9054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* next() { 9154359294a7c9dc54802d512a5d891a35c1663392caryclark return fNext; 9254359294a7c9dc54802d512a5d891a35c1663392caryclark } 9354359294a7c9dc54802d512a5d891a35c1663392caryclark 9454359294a7c9dc54802d512a5d891a35c1663392caryclark bool onEnd() const; 9554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* prev(); 9654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* remove(); 9754359294a7c9dc54802d512a5d891a35c1663392caryclark void removeNext(SkOpPtT* kept); 9854359294a7c9dc54802d512a5d891a35c1663392caryclark 9954359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSegment* segment() const; 10054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* segment(); 10154359294a7c9dc54802d512a5d891a35c1663392caryclark 10254359294a7c9dc54802d512a5d891a35c1663392caryclark void setDeleted() { 10354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!fDeleted); 10454359294a7c9dc54802d512a5d891a35c1663392caryclark fDeleted = true; 10554359294a7c9dc54802d512a5d891a35c1663392caryclark } 10654359294a7c9dc54802d512a5d891a35c1663392caryclark 10754359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* span() const { 10854359294a7c9dc54802d512a5d891a35c1663392caryclark return fSpan; 10954359294a7c9dc54802d512a5d891a35c1663392caryclark } 11054359294a7c9dc54802d512a5d891a35c1663392caryclark 11154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* span() { 11254359294a7c9dc54802d512a5d891a35c1663392caryclark return fSpan; 11354359294a7c9dc54802d512a5d891a35c1663392caryclark } 11454359294a7c9dc54802d512a5d891a35c1663392caryclark 11554359294a7c9dc54802d512a5d891a35c1663392caryclark double fT; 11654359294a7c9dc54802d512a5d891a35c1663392caryclark SkPoint fPt; // cache of point value at this t 11754359294a7c9dc54802d512a5d891a35c1663392caryclarkprotected: 11854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* fSpan; // contains winding data 11954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* fNext; // intersection on opposite curve or alias on this curve 12054359294a7c9dc54802d512a5d891a35c1663392caryclark bool fDeleted; // set if removed from span list 12154359294a7c9dc54802d512a5d891a35c1663392caryclark bool fDuplicatePt; // set if identical pt is somewhere in the next loop 1221049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(int fID); 12354359294a7c9dc54802d512a5d891a35c1663392caryclark}; 12454359294a7c9dc54802d512a5d891a35c1663392caryclark 12554359294a7c9dc54802d512a5d891a35c1663392caryclarkclass SkOpSpanBase { 12654359294a7c9dc54802d512a5d891a35c1663392caryclarkpublic: 12754359294a7c9dc54802d512a5d891a35c1663392caryclark void align(); 12854359294a7c9dc54802d512a5d891a35c1663392caryclark 12954359294a7c9dc54802d512a5d891a35c1663392caryclark bool aligned() const { 13054359294a7c9dc54802d512a5d891a35c1663392caryclark return fAligned; 13154359294a7c9dc54802d512a5d891a35c1663392caryclark } 13254359294a7c9dc54802d512a5d891a35c1663392caryclark 13354359294a7c9dc54802d512a5d891a35c1663392caryclark void alignEnd(double t, const SkPoint& pt); 13454359294a7c9dc54802d512a5d891a35c1663392caryclark 13508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark void bumpSpanAdds() { 13608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark ++fSpanAdds; 13708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 13808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark 13954359294a7c9dc54802d512a5d891a35c1663392caryclark bool chased() const { 14054359294a7c9dc54802d512a5d891a35c1663392caryclark return fChased; 14154359294a7c9dc54802d512a5d891a35c1663392caryclark } 14254359294a7c9dc54802d512a5d891a35c1663392caryclark 14354359294a7c9dc54802d512a5d891a35c1663392caryclark void clearCoinEnd() { 14454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(fCoinEnd != this); 14554359294a7c9dc54802d512a5d891a35c1663392caryclark fCoinEnd = this; 14654359294a7c9dc54802d512a5d891a35c1663392caryclark } 14754359294a7c9dc54802d512a5d891a35c1663392caryclark 14854359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* coinEnd() const { 14954359294a7c9dc54802d512a5d891a35c1663392caryclark return fCoinEnd; 15054359294a7c9dc54802d512a5d891a35c1663392caryclark } 15154359294a7c9dc54802d512a5d891a35c1663392caryclark 15254359294a7c9dc54802d512a5d891a35c1663392caryclark bool contains(const SkOpSpanBase* ) const; 15354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* contains(const SkOpSegment* ); 15454359294a7c9dc54802d512a5d891a35c1663392caryclark 15554359294a7c9dc54802d512a5d891a35c1663392caryclark bool containsCoinEnd(const SkOpSpanBase* coin) const { 15654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this != coin); 15754359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* next = this; 15854359294a7c9dc54802d512a5d891a35c1663392caryclark while ((next = next->fCoinEnd) != this) { 15954359294a7c9dc54802d512a5d891a35c1663392caryclark if (next == coin) { 16054359294a7c9dc54802d512a5d891a35c1663392caryclark return true; 16154359294a7c9dc54802d512a5d891a35c1663392caryclark } 16254359294a7c9dc54802d512a5d891a35c1663392caryclark } 16354359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 16454359294a7c9dc54802d512a5d891a35c1663392caryclark } 16554359294a7c9dc54802d512a5d891a35c1663392caryclark 16654359294a7c9dc54802d512a5d891a35c1663392caryclark bool containsCoinEnd(const SkOpSegment* ) const; 16754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpContour* contour() const; 16854359294a7c9dc54802d512a5d891a35c1663392caryclark 16954359294a7c9dc54802d512a5d891a35c1663392caryclark int debugBumpCount() { 1701049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return SkDEBUGRELEASE(++fCount, -1); 17154359294a7c9dc54802d512a5d891a35c1663392caryclark } 17254359294a7c9dc54802d512a5d891a35c1663392caryclark 17354359294a7c9dc54802d512a5d891a35c1663392caryclark int debugID() const { 1741049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return SkDEBUGRELEASE(fID, -1); 17554359294a7c9dc54802d512a5d891a35c1663392caryclark } 17654359294a7c9dc54802d512a5d891a35c1663392caryclark 17754359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpAngle* debugAngle(int id) const; 17854359294a7c9dc54802d512a5d891a35c1663392caryclark bool debugCoinEndLoopCheck() const; 17954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpContour* debugContour(int id); 18054359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpPtT* debugPtT(int id) const; 18154359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSegment* debugSegment(int id) const; 18254359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* debugSpan(int id) const; 18354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpGlobalState* globalState() const; 18454359294a7c9dc54802d512a5d891a35c1663392caryclark void debugValidate() const; 18554359294a7c9dc54802d512a5d891a35c1663392caryclark 18654359294a7c9dc54802d512a5d891a35c1663392caryclark bool deleted() const { 18754359294a7c9dc54802d512a5d891a35c1663392caryclark return fPtT.deleted(); 18854359294a7c9dc54802d512a5d891a35c1663392caryclark } 18954359294a7c9dc54802d512a5d891a35c1663392caryclark 19054359294a7c9dc54802d512a5d891a35c1663392caryclark void dump() const; // available to testing only 19154359294a7c9dc54802d512a5d891a35c1663392caryclark void dumpCoin() const; 19254359294a7c9dc54802d512a5d891a35c1663392caryclark void dumpAll() const; 19354359294a7c9dc54802d512a5d891a35c1663392caryclark void dumpBase() const; 19454359294a7c9dc54802d512a5d891a35c1663392caryclark 19554359294a7c9dc54802d512a5d891a35c1663392caryclark bool final() const { 19654359294a7c9dc54802d512a5d891a35c1663392caryclark return fPtT.fT == 1; 19754359294a7c9dc54802d512a5d891a35c1663392caryclark } 19854359294a7c9dc54802d512a5d891a35c1663392caryclark 19954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* fromAngle() const { 20054359294a7c9dc54802d512a5d891a35c1663392caryclark return fFromAngle; 20154359294a7c9dc54802d512a5d891a35c1663392caryclark } 20254359294a7c9dc54802d512a5d891a35c1663392caryclark 20354359294a7c9dc54802d512a5d891a35c1663392caryclark void initBase(SkOpSegment* parent, SkOpSpan* prev, double t, const SkPoint& pt); 20454359294a7c9dc54802d512a5d891a35c1663392caryclark 20554359294a7c9dc54802d512a5d891a35c1663392caryclark void insertCoinEnd(SkOpSpanBase* coin) { 20654359294a7c9dc54802d512a5d891a35c1663392caryclark if (containsCoinEnd(coin)) { 20754359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(coin->containsCoinEnd(this)); 20854359294a7c9dc54802d512a5d891a35c1663392caryclark return; 20954359294a7c9dc54802d512a5d891a35c1663392caryclark } 21054359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 21154359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this != coin); 21254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* coinNext = coin->fCoinEnd; 21354359294a7c9dc54802d512a5d891a35c1663392caryclark coin->fCoinEnd = this->fCoinEnd; 21454359294a7c9dc54802d512a5d891a35c1663392caryclark this->fCoinEnd = coinNext; 21554359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 21654359294a7c9dc54802d512a5d891a35c1663392caryclark } 21754359294a7c9dc54802d512a5d891a35c1663392caryclark 21854359294a7c9dc54802d512a5d891a35c1663392caryclark void merge(SkOpSpan* span); 21954359294a7c9dc54802d512a5d891a35c1663392caryclark 22054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* prev() const { 22154359294a7c9dc54802d512a5d891a35c1663392caryclark return fPrev; 22254359294a7c9dc54802d512a5d891a35c1663392caryclark } 22354359294a7c9dc54802d512a5d891a35c1663392caryclark 22454359294a7c9dc54802d512a5d891a35c1663392caryclark const SkPoint& pt() const { 22554359294a7c9dc54802d512a5d891a35c1663392caryclark return fPtT.fPt; 22654359294a7c9dc54802d512a5d891a35c1663392caryclark } 22754359294a7c9dc54802d512a5d891a35c1663392caryclark 22854359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpPtT* ptT() const { 22954359294a7c9dc54802d512a5d891a35c1663392caryclark return &fPtT; 23054359294a7c9dc54802d512a5d891a35c1663392caryclark } 23154359294a7c9dc54802d512a5d891a35c1663392caryclark 23254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* ptT() { 23354359294a7c9dc54802d512a5d891a35c1663392caryclark return &fPtT; 23454359294a7c9dc54802d512a5d891a35c1663392caryclark } 23554359294a7c9dc54802d512a5d891a35c1663392caryclark 23654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* segment() const { 23754359294a7c9dc54802d512a5d891a35c1663392caryclark return fSegment; 23854359294a7c9dc54802d512a5d891a35c1663392caryclark } 23954359294a7c9dc54802d512a5d891a35c1663392caryclark 24054359294a7c9dc54802d512a5d891a35c1663392caryclark void setChased(bool chased) { 24154359294a7c9dc54802d512a5d891a35c1663392caryclark fChased = chased; 24254359294a7c9dc54802d512a5d891a35c1663392caryclark } 24354359294a7c9dc54802d512a5d891a35c1663392caryclark 24454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* setCoinEnd(SkOpSpanBase* oldCoinEnd, SkOpSegment* oppSegment); 24554359294a7c9dc54802d512a5d891a35c1663392caryclark 24654359294a7c9dc54802d512a5d891a35c1663392caryclark void setFromAngle(SkOpAngle* angle) { 24754359294a7c9dc54802d512a5d891a35c1663392caryclark fFromAngle = angle; 24854359294a7c9dc54802d512a5d891a35c1663392caryclark } 24954359294a7c9dc54802d512a5d891a35c1663392caryclark 25054359294a7c9dc54802d512a5d891a35c1663392caryclark void setPrev(SkOpSpan* prev) { 25154359294a7c9dc54802d512a5d891a35c1663392caryclark fPrev = prev; 25254359294a7c9dc54802d512a5d891a35c1663392caryclark } 25354359294a7c9dc54802d512a5d891a35c1663392caryclark 25454359294a7c9dc54802d512a5d891a35c1663392caryclark bool simple() const { 25554359294a7c9dc54802d512a5d891a35c1663392caryclark fPtT.debugValidate(); 25654359294a7c9dc54802d512a5d891a35c1663392caryclark return fPtT.next()->next() == &fPtT; 25754359294a7c9dc54802d512a5d891a35c1663392caryclark } 25854359294a7c9dc54802d512a5d891a35c1663392caryclark 25908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark int spanAddsCount() const { 26008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark return fSpanAdds; 26108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 26208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark 26354359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpan* starter(const SkOpSpanBase* end) const { 26454359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* result = t() < end->t() ? this : end; 26554359294a7c9dc54802d512a5d891a35c1663392caryclark return result->upCast(); 26654359294a7c9dc54802d512a5d891a35c1663392caryclark } 26754359294a7c9dc54802d512a5d891a35c1663392caryclark 26854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* starter(SkOpSpanBase* end) { 26954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this->segment() == end->segment()); 27054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* result = t() < end->t() ? this : end; 27154359294a7c9dc54802d512a5d891a35c1663392caryclark return result->upCast(); 27254359294a7c9dc54802d512a5d891a35c1663392caryclark } 27354359294a7c9dc54802d512a5d891a35c1663392caryclark 27454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* starter(SkOpSpanBase** endPtr) { 27554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* end = *endPtr; 27654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this->segment() == end->segment()); 27754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* result; 27854359294a7c9dc54802d512a5d891a35c1663392caryclark if (t() < end->t()) { 27954359294a7c9dc54802d512a5d891a35c1663392caryclark result = this; 28054359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 28154359294a7c9dc54802d512a5d891a35c1663392caryclark result = end; 28254359294a7c9dc54802d512a5d891a35c1663392caryclark *endPtr = this; 28354359294a7c9dc54802d512a5d891a35c1663392caryclark } 28454359294a7c9dc54802d512a5d891a35c1663392caryclark return result->upCast(); 28554359294a7c9dc54802d512a5d891a35c1663392caryclark } 28654359294a7c9dc54802d512a5d891a35c1663392caryclark 28754359294a7c9dc54802d512a5d891a35c1663392caryclark int step(const SkOpSpanBase* end) const { 28854359294a7c9dc54802d512a5d891a35c1663392caryclark return t() < end->t() ? 1 : -1; 28954359294a7c9dc54802d512a5d891a35c1663392caryclark } 29054359294a7c9dc54802d512a5d891a35c1663392caryclark 29154359294a7c9dc54802d512a5d891a35c1663392caryclark double t() const { 29254359294a7c9dc54802d512a5d891a35c1663392caryclark return fPtT.fT; 29354359294a7c9dc54802d512a5d891a35c1663392caryclark } 29454359294a7c9dc54802d512a5d891a35c1663392caryclark 29554359294a7c9dc54802d512a5d891a35c1663392caryclark void unaligned() { 29654359294a7c9dc54802d512a5d891a35c1663392caryclark fAligned = false; 29754359294a7c9dc54802d512a5d891a35c1663392caryclark } 29854359294a7c9dc54802d512a5d891a35c1663392caryclark 29954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* upCast() { 30054359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!final()); 30154359294a7c9dc54802d512a5d891a35c1663392caryclark return (SkOpSpan*) this; 30254359294a7c9dc54802d512a5d891a35c1663392caryclark } 30354359294a7c9dc54802d512a5d891a35c1663392caryclark 30454359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpan* upCast() const { 30554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!final()); 30654359294a7c9dc54802d512a5d891a35c1663392caryclark return (const SkOpSpan*) this; 30754359294a7c9dc54802d512a5d891a35c1663392caryclark } 30854359294a7c9dc54802d512a5d891a35c1663392caryclark 30954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* upCastable() { 31054359294a7c9dc54802d512a5d891a35c1663392caryclark return final() ? NULL : upCast(); 31154359294a7c9dc54802d512a5d891a35c1663392caryclark } 31254359294a7c9dc54802d512a5d891a35c1663392caryclark 31354359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpan* upCastable() const { 31454359294a7c9dc54802d512a5d891a35c1663392caryclark return final() ? NULL : upCast(); 31554359294a7c9dc54802d512a5d891a35c1663392caryclark } 31654359294a7c9dc54802d512a5d891a35c1663392caryclark 31754359294a7c9dc54802d512a5d891a35c1663392caryclarkprivate: 31854359294a7c9dc54802d512a5d891a35c1663392caryclark void alignInner(); 31954359294a7c9dc54802d512a5d891a35c1663392caryclark 32054359294a7c9dc54802d512a5d891a35c1663392caryclarkprotected: // no direct access to internals to avoid treating a span base as a span 32154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT fPtT; // list of points and t values associated with the start of this span 32254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* fSegment; // segment that contains this span 32354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* fCoinEnd; // linked list of coincident spans that end here (may point to itself) 32454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* fFromAngle; // points to next angle from span start to end 32554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* fPrev; // previous intersection point 32608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark int fSpanAdds; // number of times intersections have been added to span 32754359294a7c9dc54802d512a5d891a35c1663392caryclark bool fAligned; 32854359294a7c9dc54802d512a5d891a35c1663392caryclark bool fChased; // set after span has been added to chase array 3291049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(int fCount); // number of pt/t pairs added 3301049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(int fID); 33154359294a7c9dc54802d512a5d891a35c1663392caryclark}; 33254359294a7c9dc54802d512a5d891a35c1663392caryclark 33354359294a7c9dc54802d512a5d891a35c1663392caryclarkclass SkOpSpan : public SkOpSpanBase { 33454359294a7c9dc54802d512a5d891a35c1663392caryclarkpublic: 33554359294a7c9dc54802d512a5d891a35c1663392caryclark bool clearCoincident() { 33654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!final()); 33754359294a7c9dc54802d512a5d891a35c1663392caryclark if (fCoincident == this) { 33854359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 33954359294a7c9dc54802d512a5d891a35c1663392caryclark } 34054359294a7c9dc54802d512a5d891a35c1663392caryclark fCoincident = this; 34154359294a7c9dc54802d512a5d891a35c1663392caryclark return true; 34254359294a7c9dc54802d512a5d891a35c1663392caryclark } 34354359294a7c9dc54802d512a5d891a35c1663392caryclark 344bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark int computeWindSum(); 34554359294a7c9dc54802d512a5d891a35c1663392caryclark bool containsCoincidence(const SkOpSegment* ) const; 34654359294a7c9dc54802d512a5d891a35c1663392caryclark 34754359294a7c9dc54802d512a5d891a35c1663392caryclark bool containsCoincidence(const SkOpSpan* coin) const { 34854359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this != coin); 34954359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpan* next = this; 35054359294a7c9dc54802d512a5d891a35c1663392caryclark while ((next = next->fCoincident) != this) { 35154359294a7c9dc54802d512a5d891a35c1663392caryclark if (next == coin) { 35254359294a7c9dc54802d512a5d891a35c1663392caryclark return true; 35354359294a7c9dc54802d512a5d891a35c1663392caryclark } 35454359294a7c9dc54802d512a5d891a35c1663392caryclark } 35554359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 35654359294a7c9dc54802d512a5d891a35c1663392caryclark } 35754359294a7c9dc54802d512a5d891a35c1663392caryclark 35854359294a7c9dc54802d512a5d891a35c1663392caryclark bool debugCoinLoopCheck() const; 35954359294a7c9dc54802d512a5d891a35c1663392caryclark void detach(SkOpPtT* ); 36054359294a7c9dc54802d512a5d891a35c1663392caryclark 36154359294a7c9dc54802d512a5d891a35c1663392caryclark bool done() const { 36254359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!final()); 36354359294a7c9dc54802d512a5d891a35c1663392caryclark return fDone; 36454359294a7c9dc54802d512a5d891a35c1663392caryclark } 36554359294a7c9dc54802d512a5d891a35c1663392caryclark 36654359294a7c9dc54802d512a5d891a35c1663392caryclark void dumpCoin() const; 36754359294a7c9dc54802d512a5d891a35c1663392caryclark bool dumpSpan() const; 36854359294a7c9dc54802d512a5d891a35c1663392caryclark void init(SkOpSegment* parent, SkOpSpan* prev, double t, const SkPoint& pt); 36954359294a7c9dc54802d512a5d891a35c1663392caryclark 37054359294a7c9dc54802d512a5d891a35c1663392caryclark void insertCoincidence(SkOpSpan* coin) { 37154359294a7c9dc54802d512a5d891a35c1663392caryclark if (containsCoincidence(coin)) { 37254359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(coin->containsCoincidence(this)); 37354359294a7c9dc54802d512a5d891a35c1663392caryclark return; 37454359294a7c9dc54802d512a5d891a35c1663392caryclark } 37554359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 37654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this != coin); 37754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* coinNext = coin->fCoincident; 37854359294a7c9dc54802d512a5d891a35c1663392caryclark coin->fCoincident = this->fCoincident; 37954359294a7c9dc54802d512a5d891a35c1663392caryclark this->fCoincident = coinNext; 38054359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 38154359294a7c9dc54802d512a5d891a35c1663392caryclark } 38254359294a7c9dc54802d512a5d891a35c1663392caryclark 38354359294a7c9dc54802d512a5d891a35c1663392caryclark bool isCanceled() const { 38454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!final()); 38554359294a7c9dc54802d512a5d891a35c1663392caryclark return fWindValue == 0 && fOppValue == 0; 38654359294a7c9dc54802d512a5d891a35c1663392caryclark } 38754359294a7c9dc54802d512a5d891a35c1663392caryclark 38854359294a7c9dc54802d512a5d891a35c1663392caryclark bool isCoincident() const { 38954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!final()); 39054359294a7c9dc54802d512a5d891a35c1663392caryclark return fCoincident != this; 39154359294a7c9dc54802d512a5d891a35c1663392caryclark } 39254359294a7c9dc54802d512a5d891a35c1663392caryclark 39354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* next() const { 39454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!final()); 39554359294a7c9dc54802d512a5d891a35c1663392caryclark return fNext; 39654359294a7c9dc54802d512a5d891a35c1663392caryclark } 39754359294a7c9dc54802d512a5d891a35c1663392caryclark 39854359294a7c9dc54802d512a5d891a35c1663392caryclark int oppSum() const { 39954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!final()); 40054359294a7c9dc54802d512a5d891a35c1663392caryclark return fOppSum; 40154359294a7c9dc54802d512a5d891a35c1663392caryclark } 40254359294a7c9dc54802d512a5d891a35c1663392caryclark 40354359294a7c9dc54802d512a5d891a35c1663392caryclark int oppValue() const { 40454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!final()); 40554359294a7c9dc54802d512a5d891a35c1663392caryclark return fOppValue; 40654359294a7c9dc54802d512a5d891a35c1663392caryclark } 40754359294a7c9dc54802d512a5d891a35c1663392caryclark 40854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* setCoinStart(SkOpSpan* oldCoinStart, SkOpSegment* oppSegment); 40954359294a7c9dc54802d512a5d891a35c1663392caryclark 41054359294a7c9dc54802d512a5d891a35c1663392caryclark void setDone(bool done) { 41154359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!final()); 41254359294a7c9dc54802d512a5d891a35c1663392caryclark fDone = done; 41354359294a7c9dc54802d512a5d891a35c1663392caryclark } 41454359294a7c9dc54802d512a5d891a35c1663392caryclark 41554359294a7c9dc54802d512a5d891a35c1663392caryclark void setNext(SkOpSpanBase* nextT) { 41654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!final()); 41754359294a7c9dc54802d512a5d891a35c1663392caryclark fNext = nextT; 41854359294a7c9dc54802d512a5d891a35c1663392caryclark } 41954359294a7c9dc54802d512a5d891a35c1663392caryclark 42054359294a7c9dc54802d512a5d891a35c1663392caryclark void setOppSum(int oppSum); 42154359294a7c9dc54802d512a5d891a35c1663392caryclark 42254359294a7c9dc54802d512a5d891a35c1663392caryclark void setOppValue(int oppValue) { 42354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!final()); 42454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(fOppSum == SK_MinS32); 42554359294a7c9dc54802d512a5d891a35c1663392caryclark fOppValue = oppValue; 42654359294a7c9dc54802d512a5d891a35c1663392caryclark } 42754359294a7c9dc54802d512a5d891a35c1663392caryclark 42854359294a7c9dc54802d512a5d891a35c1663392caryclark void setToAngle(SkOpAngle* angle) { 42954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!final()); 43054359294a7c9dc54802d512a5d891a35c1663392caryclark fToAngle = angle; 43154359294a7c9dc54802d512a5d891a35c1663392caryclark } 43254359294a7c9dc54802d512a5d891a35c1663392caryclark 433624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark void setWindSum(int windSum); 43454359294a7c9dc54802d512a5d891a35c1663392caryclark 43554359294a7c9dc54802d512a5d891a35c1663392caryclark void setWindValue(int windValue) { 43654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!final()); 43754359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(windValue >= 0); 43854359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(fWindSum == SK_MinS32); 43954359294a7c9dc54802d512a5d891a35c1663392caryclark fWindValue = windValue; 44054359294a7c9dc54802d512a5d891a35c1663392caryclark } 44154359294a7c9dc54802d512a5d891a35c1663392caryclark 442624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark bool sortableTop(SkOpContour* ); 443624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 44454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* toAngle() const { 44554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!final()); 44654359294a7c9dc54802d512a5d891a35c1663392caryclark return fToAngle; 44754359294a7c9dc54802d512a5d891a35c1663392caryclark } 44854359294a7c9dc54802d512a5d891a35c1663392caryclark 44954359294a7c9dc54802d512a5d891a35c1663392caryclark int windSum() const { 45054359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!final()); 45154359294a7c9dc54802d512a5d891a35c1663392caryclark return fWindSum; 45254359294a7c9dc54802d512a5d891a35c1663392caryclark } 45354359294a7c9dc54802d512a5d891a35c1663392caryclark 45454359294a7c9dc54802d512a5d891a35c1663392caryclark int windValue() const { 45554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!final()); 45654359294a7c9dc54802d512a5d891a35c1663392caryclark return fWindValue; 45754359294a7c9dc54802d512a5d891a35c1663392caryclark } 45854359294a7c9dc54802d512a5d891a35c1663392caryclark 45954359294a7c9dc54802d512a5d891a35c1663392caryclarkprivate: // no direct access to internals to avoid treating a span base as a span 46054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* fCoincident; // linked list of spans coincident with this one (may point to itself) 46154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* fToAngle; // points to next angle from span start to end 46254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* fNext; // next intersection point 46307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int fWindSum; // accumulated from contours surrounding this one. 46407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int fOppSum; // for binary operators: the opposite winding sum 46507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int fWindValue; // 0 == canceled; 1 == normal; >1 == coincident 46607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int fOppValue; // normally 0 -- when binary coincident edges combine, opp value goes here 467624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int fTopTTry; // specifies direction and t value to try next 46807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool fDone; // if set, this span to next higher T has been processed 46907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com}; 47007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 47107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 472